A Reduction Technique for Layers in Multilayer Printed Wiring Boards--Using Additional Vias between Grid Points--

Mohsen GHAMESHLU  Noriyoshi YOSHIDA  

IEICE TRANSACTIONS (1976-1990)   Vol.E71   No.9   pp.887-894
Publication Date: 1988/09/25
Online ISSN: 
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.