For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Reduction Technique for Layers in Multilayer Printed Wiring Boards--Using Additional Vias between Grid Points--
Mohsen GHAMESHLU Noriyoshi YOSHIDA
IEICE TRANSACTIONS (1976-1990)
Publication Date: 1988/09/25
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Category: Computer Hardware and Design
Full Text: PDF(720KB)
>>Buy this Article
The single-row routing approach to the design of multilayer printed wiring boards decomposes the general problem into a number of independent phases. The layering phase is considered in this paper. We assume that the street capacity is exactly two in each layer. Recent advances in the technology of microelectronics, which enables us to produce high density boards, show that it is possible to drill one via between any two adjacent vertices on the single-row where at most two wire segments are passed. We call these vias as additional vias. We give a new upper bound to the number of layers while using additional vias is permitted. A polynomial time algorithm SPLIT is given for assigning nets to m layers where m is less than or equal to the new upper bound. The number of additional vias is not limited in algorithm SPLIT. For having a reasonable number of additional vias on the single-row, a heuristic algorithm LIMIT_SPLIT is proposed. LIMIT_SPLIT is implemented and compared with a related conventional algorithm. Experimental results show that LIMIT_SPLIT takes the shorter run time and provides smaller number of layers for 59% of the randomly generated net lists while using no more than two additional vias in each case.