Browsing by Author "Wong, DF"

Now showing 1 - 4 of 4

A graph-theoretic sufficient condition for FPGA/FPIC switch-module routability
(1997)
Chang, YW
;
Wong, DF
;
Wong, CK
;
交大名義發表
;
資訊工程學系
Switch modules are the most important component of the routing resources in FPGA's/FPIC's. We consider in this paper an FPGA/FPIC switch-module analysis problem: The in puts consist of a switch-module description and the number of nets required to be routed through the switch module; the question is to determine if there exists a feasible routing for the routing requirements on the switch module. This problem is applicable to the routability evaluation of FPGA/FPIC switch modules, the switch-module design for FPGA's/FPIC's, and FPGA/FPIC routing. We present a graph-theoretic sufficient condition for the analysis problem. The implications of the condition are: (1) there exist several classes of efficient approximation algorithms for the analysis problem; (2) there exist several classes of switch-module architectures on which the analysis problem can be solved efficiently.
Algorithms for an FPGA switch module routing problem with application to global routing
(1997-01-01)
Thakur, S
;
Chang, YW
;
Wong, DF
;
Muthukrishnan, S
;
資訊工程學系
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.
Graph matching-based algorithms for FPGA segmentation design
(1998)
Chang, YW
;
Lin, JM
;
Wong, DF
;
資訊工程學系
;
Department of Computer Science
Process technology advances will soon make the one-million gate FPGA a reality. A key issue that needs to be solved for the large-scale FPGAs to realize their full potential lies in the design of their segmentation architectures [10]. One-dimensional segmentation designs have been studied to some degree in much of the literature; most of the previously proposed methods are based on stochastic or analytical analysis. In this paper, we address a new direction for studying segmentation architectures. Our method is based on graph-theoretic formulation. We first formulate a net matching problem and present a polynomial-time optimal algorithm to solve the problem. Based on the solution to the problem, we develop an effective and efficient matching-based algorithm for FPGA segmentation designs. Experimental results show that our method significantly outperforms previous work. For example, our method achieves averages of 18.2% and 8.9% improvements in routability, compared with the work in [14] and the most recent work in [7] respectively. More importantly, our approaches are very flexible and can readily extend to higher-order segmentation designs (e.g., two- or three-dimensional segmentation design, etc), which are crucial to the design of large-scale FPGAs.
Timing-driven routing for symmetrical array-based FPGAs
(2000-07-01)
Chang, YW
;
Zhu, K
;
Wong, DF
;
資訊工程學系
;
Department of Computer Science
In this paper we present a timing-driven router for symmetrical array-based FPGAs. The routing resources in the FPGAs consist of segments of various lengths. Researchers have shown that the number of segments, instead of wirelength, used by a net is the most critical factor in controlling routing delay in an FPGA. Thus, the traditional measure of routing delay on the basis of geometric distance of a signal is not accurate. To consider wirelength and delay simultaneously, we study a model of timing-driven routing trees, arising from the special properties of FPGA routing architectures. Based on the solutions to the routing-tree problem, we present a routing algorithm that is able to utilize various routing segments with global considerations to meet timing constraints. Experimental results show that our approach is very effective in reducing timing violations.