A neural network model for multilayer topological via minimization in a switchbox

被引:9
作者
Funabiki, N
Nishikawa, S
机构
[1] Department of Information and Computer Sciences, Faculty of Engineering Science, Osaka University, Toyonaka
关键词
D O I
10.1109/43.511580
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
This paper presents a new approach using a neural network model for the multilayer topological via minimization problem in a switchbox. Our algorithm consists of three steps: 1) dividing multiterminal nets into two-terminal nets, 2) finding a layer-assignment of the two-terminal nets by a neural network model so as to minimize the number of unassigned nets, and 3) embedding one via for each unassigned net by Marek-Sadowska's algorithm. The neural network model is composed of M x M processing elements to assign N two-terminal nets in an M-layer switchbox. The performance of our algorithm is verified by 15 benchmark problems where it can find optimum or near-optimum solutions. In the two-layer Burstein's switchbox, our algorithm finds a 15-via solution while the best known solution requires 20 vias.
引用
收藏
页码:1012 / 1020
页数:9
相关论文
共 19 条
[11]  
McCulloch Warren S., 1943, BULL MATH BIOPHYS, V5, P115, DOI 10.1007/BF02478259
[12]   EXACT ALGORITHMS FOR MULTILAYER TOPOLOGICAL VIA MINIMIZATION [J].
RIM, CS ;
KASHIWABARA, T ;
NAKAJIMA, K .
IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 1989, 8 (11) :1165-1173
[13]   A NEW APPROACH TO TOPOLOGICAL VIA MINIMIZATION [J].
SARRAFZADEH, M ;
LEE, DT .
IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 1989, 8 (08) :890-900
[14]   TOPOLOGICAL VIA MINIMIZATION REVISITED [J].
SARRAFZADEH, M ;
LEE, DT .
IEEE TRANSACTIONS ON COMPUTERS, 1991, 40 (11) :1307-1312
[15]   UNCONSTRAINED VIA MINIMIZATION FOR TOPOLOGICAL MULTILAYER ROUTING [J].
STALLMANN, M ;
HUGHES, T ;
LIU, WT .
IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 1990, 9 (09) :970-980
[16]   FINDING A MAXIMUM PLANAR SUBSET OF A SET OF NETS IN A CHANNEL [J].
SUPOWIT, KJ .
IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 1987, 6 (01) :93-94
[17]  
Takefuji Y., 2012, Neural network parallel computing, V164
[18]   SIMPLE NEURAL OPTIMIZATION NETWORKS - AN A/D CONVERTER, SIGNAL DECISION CIRCUIT, AND A LINEAR-PROGRAMMING CIRCUIT [J].
TANK, DW ;
HOPFIELD, JJ .
IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS, 1986, 33 (05) :533-541
[19]  
YAMASHITA H, 1994, T IEICE, P2130