標題: Algorithms for an FPGA switch module routing problem with application to global routing
作者: Thakur, S
Chang, YW
Wong, DF
Muthukrishnan, S
資訊工程學系
Department of Computer Science
關鍵字: field-programmable gate array;global routing
公開日期: 1-一月-1997
摘要: We consider a switch module routing problem for symmetrical-array field-programmable gate arrays (FPGA's). This problem was first introduced in [21], They used it to evaluate the routability properties of switch modules which they proposed, Only an approximation algorithm for the problem was proposed by them, We give an optimal algorithm for the problem based on integer linear programming (ILP), Experiments show that this formulation leads to fast and efficient solutions to practical-sized problems, We then propose a precomputation that eliminates the need to use ILP era-line, We also identify special cases of this problem that reduce to problems for whom efficient algorithms are known, Thus, the switch module routing problem can be solved in polynomial time for these special cases, Using our solution to the switch module routing problem, we propose a new metric to estimate the congestion in each switch module in the FPGA. We demonstrate the use of this metric in a global router, A comparison with a global router guided by the density of the routing channels shows that our metric leads to far superior global and detailed routing solutions.
URI: http://dx.doi.org/10.1109/43.559330
http://hdl.handle.net/11536/816
ISSN: 0278-0070
DOI: 10.1109/43.559330
期刊: IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS
Volume: 16
Issue: 1
起始頁: 32
結束頁: 46
顯示於類別:期刊論文


文件中的檔案:

  1. A1997WN99700004.pdf