SEGMENTED CHANNEL ROUTING

被引：17
作者：
ROYCHOWDHURY, VP
GREENE, JW
ELGAMAL, A
机构：
[1] ACTEL CORP,SUNNYVALE,CA
[2] STANFORD UNIV,INFORMAT SYST LAB,STANFORD,CA 94305
[3] COLUMBIA UNIV,DEPT CHEM,NEW YORK,NY 10027
来源：
IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS | 1993年 / 12卷 / 01期
关键词：
D O I：
10.1109/43.184845
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
Novel problems concerning routing in a segmented routing channel are introduced. These problems are fundamental to routing and design automation for field programmable gate arrays (FPGA's), a new type of electrically programmable VLSI. The first known theoretical results on the combinatorial complexity and algorithm design for segmented channel routing are presented. It is shown that the segmented channel routing problem is in general NP-complete. Efficient polynomial time algorithms for a number of important special cases are presented.
引用
收藏
页码：79 / 95
页数：17
相关论文
共 12 条
[1]  
DALLY WJ, 1989, VLSI89564 MIT
[2]   AN ARCHITECTURE FOR ELECTRICALLY CONFIGURABLE GATE ARRAYS [J].
ELGAMAL, A ;
GREENE, J ;
REYNERI, J ;
ROGOYSKI, E ;
ELAYAT, KA ;
MOHSEN, A .
IEEE JOURNAL OF SOLID-STATE CIRCUITS, 1989, 24 (02) :394-398
[3]  
ELGAMAL A, 1991, 13TH P C ADV RES VLS, P192
[4]  
ELGAMAL AA, 1981, IEEE T CIRCUITS SYST, V28, P127, DOI 10.1109/TCS.1981.1084958
[5]  
Greene J., 1990, 27th ACM/IEEE Design Automation Conference. Proceedings 1990 (Cat. No.90CH2894-4), P567, DOI 10.1109/DAC.1990.114919
[6]  
HASHIMOTO A, 1971, 8TH P IEEE DES AUT W
[7]  
HSIEH H, 1987, MAY P CUST INT CIRC, P515
[8]  
LORENZETTI M, 1988, PHYSICAL DESIGN AUTO, VB, pCH5
[9]  
Papadimitriou C. H., 1998, COMBINATORIAL OPTIMI
[10]   DOGLEG CHANNEL ROUTING IS NP-COMPLETE [J].
SZYMANSKI, TG .
IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 1985, 4 (01) :31-41
12