Browsing by Author "Wu, GM"

Now showing 1 - 7 of 7

A clustering- and probability-based approach for time-multiplexed FPGA partitioning
(2004-12-01)
Wu, GM
;
Chao, MCT
;
Chang, YW
;
交大名義發表
;
National Chiao Tung University
Improving logic density by time-sharing, time-multiplexed FPGAs (TMFPGAs) have become an important research topic for reconfigurable computing. Due to the precedence and capacity constraints in TMFPGAs, the clustering and partitioning problems for TMFPGAs are different from the traditional ones. In this paper, we propose a two-phase hierarchical approach to solve the partitioning problem for TMFPGAs. With the precedence and capacity considerations for both phases, the first phase clusters nodes to reduce the problem size, and the second phase applies a probability-based iterative-improvement approach to minimize cut cost. Experimental results based on the Xilinx TMFPGA architecture show that our algorithm significantly outperforms previous works. (C) 2004 Elsevier B.V. All rights reserved.
B*-trees: A new representation for non-slicing floorplans
(2000)
Chang, YC
;
Chang, YW
;
Wu, GM
;
Wu, SW
;
資訊工程學系
We present in this paper an efficient, flexible, and effective data structure, B*-trees, for non-slicing floorplans. B*-trees are based on ordered binary trees and the admissible placement presented in [1]. Inheriting from the nice properties of ordered binary trees, B*-trees are very easy for implementation and can perform the respective primitive tree operations search, insertion, and deletion in only O(1), O(1), and O(n) least O(n) time for each of these operations, where n is the number of modules. The correspondence between an admissible placement and its induced B*-tree is 1-to-1 (i.e., no redundancy); further, the transformation between them takes only linear time. Unlike other representations for non-slicing floorplans that need to construct constraint graphs for cost evaluation, in particular, the evaluation can be performed on B*-trees and their corresponding placements directly and incrementally. We further show the flexibility of B*-trees by exploring how to handle rotated, pre-placed, soft, and rectilinear modules. Experimental results on MCNC benchmarks show that the B*-tree representation runs about 4.5 times faster, consumes about 60% less memory, and results in smaller silicon area than the O-tree one [1]. We also develop a B*-tree based simulated annealing scheme for floorplan design; the scheme achieves near optimum area utilization even for rectilinear modules.
Generic ILP-based approaches for time-multiplexed FPGA partitioning
(2001-10-01)
Wu, GM
;
Lin, JM
;
Chang, YW
;
資訊工程學系
;
Department of Computer Science
Due to the precedence constraints among vertices, the partitioning problem for time-multiplexed field-programmable gate arrays (TMFPGAs) is different from the traditional one. In this paper, we first derive logic formulations for the precedence-constrained partitioning problems and then transform the formulations into integer linear programs (ILPs). The ILPs can handle the precedence constraints and minimize cut sizes simultaneously. To enhance performance, we also propose a clustering method to reduce the problem size. Experimental results based on the Xilinx TMFPGA architecture show that our approach outperforms the list-scheduling (List), the network-flow-based (FBB-m) (Liu and Wong, 1998), and the probability-based (PAT) (Chao, 1999) methods by respective average improvements of 46.6%, 32.3%, and 21.5% in cut sizes. Our approach is practical and scales well to larger problems; the empirical runtime grows close to linearly in the circuit size. More importantly, our approach is very flexible and can readily extend to the partitioning problems with various objectives and constraints, which makes the ILP formulations superior alternatives to the TMFPGA partitioning problems.
Maximally routable switch matrices for FPD design
(1998)
Wu, GM
;
Chang, YW
;
資訊工程學系
;
Department of Computer Science
An FPD switch matrix: is said to be maximally routable if it has the maximum routing capacity among all switch matrices of the same size. In this paper, we present two classes of most economical maximally routable switch matrices.
MPT-based branch-and-bound strategy for scheduling problem in high-level synthesis
(1998-11-01)
Hsiao, PY
;
Wu, GM
;
Su, JY
;
電機資訊學士班
;
Undergraduate Honors Program of Electrical Engineering and Computer Science
A branch-and-bound algorithm based on a maximum possibility table (MPT) is proposed to solve scheduling problems in high-level synthesis. Six efficient priority rules are developed as bounding functions in the algorithm. Extensions for real-world constraints are also considered, including chained operations, multicycle operations, mutually exclusive operations and pipelined data paths. Experimental results indicate that the MPT-based algorithm returns competitive scheduling results at significant savings in execution time as compared with other methods.
Quasi-universal switch matrices for FPD design
(1999-10-01)
Wu, GM
;
Chang, YW
;
資訊工程學系
;
Department of Computer Science
An FPD switch module M with omega terminals on each side is said to be universal if every set of nets satisfying the dimension constraint (i.e., the number of nets on each side of M is at most omega) is simultaneously routable through M [8]. Chang-et al, have identified a class of universal switch blocks in [8]. In this paper, we consider the design and routing problems for another popular model of switch modules called switch matrices. Unlike switch blocks, we prove that there exist no universal switch matrices. Nevertheless, we present quasi-universal switch matrices which have the maximum possible routing capacities among all switch matrices of the same size and show that their routing capacities converge to those of universal switch blocks. Each of the quasi-universal switch matrices of size omega has a total of only 14 omega - 20 (14 omega - 21) switches if omega is even (odd), omega > 1, compared to a fully populated one which has 3 omega(2) - 2 omega switches. We prove that no switch matrix with less than 14 omega - 20 (14 omega - 21) switches can be quasi-universal. Experimental results demonstrate that the quasi-universal switch matrices improve routabilty at the chip level.
Universal switch blocks for three-dimensional FPGA design
(2004-02-01)
Wu, GM
;
Shyu, M
;
Chang, YM
;
資訊工程學系
;
Department of Computer Science
The authors consider the switch-block design problem for three-dimensional FPGAs. A three-dimensional switch block M with W terminals on each face is said to be universal if every set of nets satisfying the dimension constraint (i.e. the number of nets on each face of M is at most K) is simultaneously routable through M. A class of universal switch blocks for three-dimensional FPGAs is presented. Each of the switch blocks has 15 W switches and switch-block flexibility 5 (i.e. F-S=5). It is proved that no switch block with less than 15W switches can be universal. The proposed switch blocks are compared with others of the topology associated with those used in the Xilinx XC4000 FPGAs. Experimental results demonstrate that the proposed universal switch blocks improve routabilty at the chip level. Further, the decomposition property of a universal switch block provides a key insight into its layout implementation with a smaller silicon area.