In order to handle device matching for analog circuits, some pairs of modules need to be placed symmetrically with respect to a common axis. In this paper, we deal with the module placement with symmetry constraints for analog design using the Transitive Closure Graph-Sequence (TCG-S) representation. Since the geometric relationships of modules are transparent to TCG-S and its induced operations, TCG-S has better flexibility than previous works in dealing with symmetry constraints. We first propose the necessary and sufficient conditions of TCG-S for symmetry modules. Then, we propose a polynomial-time packing algorithm for a TCG-S with symmetry constraints. Experimental results show that the TCG-S based algorithm results in the best area utilization.

Switch modules are the most important component of the routing resources in FPGAs/FPICs. Previous works have shown that switch modules with higher routability result in better area performance for practical applications. We consider in this paper an FPGA/FPIC switch-module analysis problem: the inputs 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. As a fundamental problem for the analysis of switch modules, this problem is applicable to the design and routability evaluation of FPGA/FPIC switch modules and FPGA/FPIC routing. We present a network-flow-based approximation algorithm for this problem. Based on mathematical analyses, we show that this algorithm has provably good performance with the bounds 5 and 5/4 away from the optima for two types of switch modules, respectively. Extensive experiments show that this algorithm is highly accurate and runs very efficiently.

Due to the layout complexity in modern VLSI designs, integrated circuit blocks may not be rectangular. However, literature on general rectilinear block placement is still quite limited. In this article, we present approaches for handling the placement for arbitrarily shaped rectilinear blocks using B*-trees [Chang et al. 2000]. We derive the feasibility conditions of B*-trees to guide the placement of rectilinear blocks. Experimental results show that our algorithm achieves optimal or near-optimal block placement for benchmarks with various shaped blocks.

In this article, we introduce a new placement problem motivated by the Dynamically Reconfigurable FPGA (DRFPGA) architectures. Unlike traditional placement, the problem for DRFPGAs must consider the precedence constraints among logic components. For the placement, we develop an effective metric that can consider wirelength, register requirement, and power consumption simultaneously. With the considerations of the new metric and the precedence constraints, we then present a three-stage scheme of partitioning, initial placement generation, and placement refinement to solve the new placement problem. Experimental results show that our placement scheme with the new metric achieves respective improvements of 17.2, 27.0, and 35.9% in wirelength, the number of registers, and power consumption requirements, compared with the list scheduling method.

In this paper, we introduce a new placement problem motivated by the Dynamically Reconfigurable FPGA (DRFPGA) architectures. Unlike traditional placement, the problem for DRFPGAs must consider the precedence constraints among logic components. For the placement, we develop an effective metric that can consider wirelength, register requirement, and power consumption simultaneously. With the considerations of the new metric and the precedence constraints, we then present a three-stage scheme of partitioning, initial placement generation, and placement refinement to solve the new placement problem. Experimental results show that our placement scheme with the new metric achieves respective improvements of 17.2%, 27.0%, and 35.9% in wirelength, the number of registers, and power consumption requirements, compared with the list scheduling method.

Due to the precedence constraints among vertices, the partitioning problem for dynamically reconfigurable FPGAs (DRFPGAs) 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 DRFPGA architecture show that our approach outperforms the list scheduling, the network flow based, and the probability based 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 DRFPGA partitioning problems.

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.

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) times while existing representations for non-slicing floorplans need at 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.

Due to the layout complexity in deep sub-micron technology, integrated circuit blocks are often not rectangular. However, literature on general rectilinear block placement is still quite limited. In this paper, we present approaches for handling the placement for arbitrarily shaped rectilinear blocks, based on a newly developed data structure called B*-trees. Experimental results show that our algorithm achieves optimal or near optimal block placement for benchmarks with multiple shaped blocks.

A switch block M with W 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 W) is simultaneously routable through M. In this paper, we present an algorithm to construct N-sided universal switch blocks with W terminals on each side. Each of our universal switch blocks has (/sub 2//sup N/) W switches and switch-block flexibility N-1 (i.e., F/sub S/=N-1). We prove that no switch block with less than (/sub 2//sup N/)W switches can be universal. We also compare our universal switch blocks with others of the topology associated with Xilinx XC4000-type FPGAs. To explore the area performance of the universal switch blocks, we develop a detailed router for hierarchical FPGAs (HFPGAs) with 5-sided switch blocks. Experimental results demonstrate that our universal switch blocks improve routability at the chip level. Based on extensive experiments, we also provide key insights into the interactions between switch-block architectures and routing.

No abstract available.

Improving logic density by time-sharing, time-multiplexed FPGAs (TMFPGAs) has 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. 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.

A switch block M with W 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 W) is simultaneously routable through M (Y.W. Chang et al., 1996). We present an algorithm to construct N-sided universal switch blocks with W terminals on each side. Each of our universal switch blocks has (/sub 2//sup N/)W switches and switch-block flexibility N-1 (i.e., F/sub S/=N-1). We prove that no switch block with less than (/sub 2//sup N/)W switches can be universal. Further, the decomposition property of a universal switch block provides a key insight into its layout implementation with a smaller silicon area. We also compare our universal switch blocks with others of the topology associated with Xilinx XC4000-type FPGAs. Experimental results demonstrate that our universal switch blocks improve routability at the chip level.

An FPD switch module M with /spl 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 EA is at most /spl omega/) is simultaneously routable through M. Chang et al. (1996) have identified a class of universal switch blocks. 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 /spl omega/ has a total of only 14/spl omega/-20 (14/spl omega/-21) switches if /spl omega/ is even (odd), /spl omega/>1, compared to a fully populated one which has 3/spl omega//sup 2/-2/spl omega/ switches. We prove that no switch matrix with less than 14/spl omega/-20 (14/spl omega/-21) switches can be quasi-universal. Experimental results demonstrate that the quasi-universal switch matrices improve routability at the chip level.

An FPD switch module M with w terminals on each side is said to be universal if every set of nets satisfying the dimensional constraint (i.e., the number of nets on each side of M is at most w) is simultaneously routable through M [8]. Chang, Wong, and Wong have identified a class of universal switch blocks [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 w has a total of only 14w - 20 (14w - 21) switches if w is even (odd), w > 1, compared to a fully populated one which has 3w2 - 2w switches. We prove that no switch matrix with less than 14w - 20 (14w - 21) switches can be quasi-universal. Experimental results demonstrate that the quasi-universal switch matrices improve routabilty at the chip level.