Segmented channel routing
作者： Jonathan Greene , Vwani Roychowdhury , Sinan Kaptanoglu , Abbas El Gamal
关键词:
摘要: Routing channels in a field-programmable gate array contain predefined wiring segments of various lengths. These may be connected to the pins gates or joined end-to-end form longer by programmable switches. A segmented channel routing problem is formulated, and polynomial time algorithms are given for certain special cases. The general NP-complete, but it can adequately solved practice with reasonable CPU heuristics. experiments show that generally accommodate connections using only few more tracks than conventional would. >
acm.org
sci-hub.se 参考文章(5)
Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness ,(1979)
Kenneth Steiglitz, Christos H. Papadimitriou, Combinatorial Optimization: Algorithms and Complexity ,(1981)
Akihiro Hashimoto, James Stevens, Wire routing by optimizing channel assignment within large apertures design automation conference. pp. 155- 169 ,(1971) , 10.1145/800158.805069
E. Hamdy, J. McCollum, S.-O. Chen, S. Chiang, S. Eltoukhy, J. Chang, T. Speers, A. Mohsen, Dielectric based antifuse for logic and memory ICs international electron devices meeting. ,vol. 136, pp. 786- 789 ,(1988) , 10.1109/IEDM.1988.32929
A. El Gamal, J. Greene, J. Reyneri, E. Rogoyski, K.A. El-Ayat, A. Mohsen, An architecture for electrically configurable gate arrays IEEE Journal of Solid-state Circuits. ,vol. 24, pp. 394- 398 ,(1989) , 10.1109/4.18600