Abstract
近年來可程式閘陣積體電路(Field Programmable Gate Array)廣泛地被 使用在電路原型(prototype)製作及模擬系統 (emulation system)上。在 模擬系統方面，連接架構可分為二類，一為可程式閘陣積體電路 (FPGA) 直接與其他可程式閘陣積體電路連接，另一種為可程式閘陣積體電路透過 可程式連接晶片(Field Programmable Interconnection Chip)再與其他 可程式閘陣積體電路相接。一般需要可程式連接晶片(Field Programmable Interconnection Chip)做連接的架構，有APTIX、BORG network、Realizer ....等系統。而可作為可程式連接晶片(Field Programmable Interconnection Chip)的元件，一般有Aptix FPIC、 IQ160、TI crosbar和FPGA....等。在此探討的架構為第二類，且其連接 方式為部分連接組織(partial crossbar interconnection structure)， 我們探討此連接組織方式的切線連接設定(net asignment)和架構( architecture)的問題。部分連接組織的二端點切線連接設定(net assignment for two-terminal nets)可在 polynomial time 解決，但多 端點切線連接設定(net assignment for multi- terminal nets)為 NP- hard，所以我們提出兩個有效的 greedy 方法來解決。在架構方面，當部 分連接組織的集合大小(set-ize)不一樣時，其結構(configuration)亦會 不同，所以切線連接設定與硬體價格也會有所不同。我們發現當集合大 小(set-ize)愈大，切線連接設定(net asignment)愈容易，但所需之硬體 價格亦愈高。 In this paper, we will study architecture and net assignment problems in partial crossbar interconnection structures. For the net assignment problem, we will show that net assignment of two-terminal nets in this interconnection structure is guaran teed to be completed in polynomial time. However, net assignment of multi-terminal nets becomes NP-hard. Previous paper has proposed a simple heuristic to perform net assignment for multi-terminal nets. Its results showed that it failed to complete routing all nets for many cases. In this paper, we will present two improved heuristic algorithms For the architecture problem, we will discuss different partial crossbar interconnection configurations and study how they affec the feasibility of net assignment and the hardware cost.