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

Mohsen GHAMESHLU; Noriyoshi YOSHIDA

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

Mohsen GHAMESHLU, Noriyoshi YOSHIDA

Full Text Views

0

Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on transactions Vol.E71-E No.9 pp.887-894

Publication Date: 1988/09/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Computer Hardware and Design

Authors

Mohsen GHAMESHLU
Noriyoshi YOSHIDA

Keyword

Cite this

Copy

Mohsen GHAMESHLU, Noriyoshi YOSHIDA, "A Reduction Technique for Layers in Multilayer Printed Wiring Boards--Using Additional Vias between Grid Points--" in IEICE TRANSACTIONS on transactions, vol. E71-E, no. 9, pp. 887-894, September 1988, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/transactions/10.1587/e71-e_9_887/_p

Copy

@ARTICLE{e71-e_9_887,
author={Mohsen GHAMESHLU, Noriyoshi YOSHIDA, },
journal={IEICE TRANSACTIONS on transactions},
title={A Reduction Technique for Layers in Multilayer Printed Wiring Boards--Using Additional Vias between Grid Points--},
year={1988},
volume={E71-E},
number={9},
pages={887-894},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={September},}

Copy

TY - JOUR
TI - A Reduction Technique for Layers in Multilayer Printed Wiring Boards--Using Additional Vias between Grid Points--
T2 - IEICE TRANSACTIONS on transactions
SP - 887
EP - 894
AU - Mohsen GHAMESHLU
AU - Noriyoshi YOSHIDA
PY - 1988
DO -
JO - IEICE TRANSACTIONS on transactions
SN -
VL - E71-E
IS - 9
JA - IEICE TRANSACTIONS on transactions
Y1 - September 1988
AB - 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.
ER -