A complete placement system, UPlace, for mixed mode designs is presented, which consists of a force-directed global placement, and a zone-refinement based detailed placement. For global placement, a unified objective function capturing both wire length and cell distribution is proposed; quadratic programming is formulated to optimize the unified object function efficiently; a discrete cosine transformation method is devised to calculate the uneven cell distribution cost. A dynamic approach for decomposing multi-pin nets into two-pin nets is also introduced for better wire length modeling. Zone refinement method is used for a unified legalization and detailed placement process. Experimental results show that the placement algorithm is very promising.

This paper presents a new approach to timing optimization for FPGA designs, namely incremental physical resynthesis, to answer the challenge of effectively integrating logic and physical optimizations without incurring unmanageable runtime complexity. Unlike previous approaches to this problem which limit the types of operations and/or architectural features, we take advantage of many architectural characteristics of modern FPGA devices, and utilize many types of optimizations including cell repacking, signal rerouting, resource retargeting, and logic restructuring, accompanied by efficient incremental placement, to gradually transform a design via a series of localized logic and physical optimizations that verifiably improve overall compliance with timing constraints. This procedure works well on small and large designs, and can be administered through either an automatic optimizer, or an interactive user interface. Our preliminary experiments showed that this approach is very effective in fixing or reducing timing violations that cannot be reduced by other optimization techniques: For a set of test cases to which this is applicable, the worst timing violation is reduced by an average of 42.8%.

Buhler and Tompa introduced the random projection algorithm for the motif discovery problem and demonstrated that this algorithm performs well on both simulated and biological samples. We describe a modification of the random projection algorithm, called the uniform projection algorithm, which utilizes a different choice of projections. We replace the random selection of projections by a greedy heuristic that approximately equalizes the coverage of the projections. We show that this change in selection of projections leads to improved performance on motif discovery problems. Furthermore, the uniform projection algorithm is directly applicable to other problems where the random projection algorithm has been used, including comparison of protein sequence databases.

This paper addresses the problem of partitioning a circuit into a tree hierarchy with an objective of minimizing a global interconnection cost.An efficient and effective algorithm is necessary when the circuit is huge and the tree has many levels of hierarchy.We propose a heuristic algorithm for improving a partition with respect to a given tree structure.The algorithm utilizes the tree hierarchy as an efficient mechanism for iterative improvement.We also extend the tree hierarchy to apply a multi-phase partitioning approach.Experimental results show that the algorithm significantly improves the initial partitions produced by multiway partitioning and by recursive partitioning.

This paper addresses the linear placement problem by using a spectral approach.It has been demonstrated that, by giving a more a c curate representation of the linear placement problem, a linear objective function yields better placement quality in terms of wire length than a quadratic objective function as in the eigenvector approach [4][11][6].On the other hand, the quadratic objective function has an advantage in that it tends to place c omponents more s p arsely than the linear objective function, resulting in a continuous solution closer to a physically feasible discrete solution.In this paper, we propose an -order objective function to capture the strengths of both the linear and quadratic objective functions.We demonstrate that our approach yields improved s p e ctral placements.We also present a bottom-up clustering algorithm which iteratively collapses pairs of nodes in a graph using local and global connectivity information, where the global connectivity information is derived f r om the clustering property of the eigenvector approach.The eect of our new spectral linear placement and clustering approach is demonstrated o n b enchmark circuits from MCNC.

In this paper, a Fiduccia-Mattheyses (FM) algorithm incorporating a novel initial partition generating method is proposed. The proposed algorithm applies to both bipartitioning and multi-way partitioning problems with or without replication. The initial partition generating method is based on a gradient descent algorithm. On partitioning without replication, our algorithm achieves an average of 17% improvement over the analytical method, PARABOLI, on bipartitioning, 10% better than Primal-Dual method on 4-way partitioning and 51% better than net-based method. On partitioning allowing replication, our algorithm achieves an average of 23% improvement over the directed Fiduccia-Mattheyses algorithm on Replication Graph (FMRG) method on bipartitioning.

In this paper, we consider the problem of decomposing a Finite State Machine (FSM) into communicating FSMs to minimize the number of inputs/outputs. We propose an FSM decomposition procedure based on partitioning the set of transitions that describes the behavior of an FSM. An extended FM-based partitioning algorithm is applied for transition partitioning. We also devise a state output encoding technique to further reduce the number of interconnections between the FSMs required for communication. Experimental results for MCNC benchmarks show that our algorithm has favorable results over circuit partitioning algorithms on the netlist level.

Given a system represented at gate level, we propose an algorithm mapping the design into the minimum number of FPGA's for logic emulation. We first devise a Local Ratio-cut clustering scheme to reduce the circuit complexity. Then a Set Covering partitioning approach, utilizing the paradigm of Espresso II, is proposed as an alternative to the widely adopted recursive partitioning paradigm. Experimental results have shown that our approach achieved significant improvement with much shorter run times compared to the recursive Fiduccia-Mattheyses approach on large designs. For instance, on a benchmark of 160 K gates and 90 K nets, we reduced the number of FPGA's required and the run time by 41 and 86%, respectively.>

Graph partitioning is crucial in multiple-chip design, floorplanning and mapping large logic networks into multiple FPGA's. Replication logic can be used to improve the partitioning. Given a network G with only two-pin nets and a pair of nodes s and t to be separated, we introduce a replication graph and an O(mn log(n/sup 2//m)) algorithm for optimum partitioning with replication and without size constraints, where m and n denote the number of nets and the number of nodes in G, respectively. In VLSI designs, each partition has size constraints and the given network contains multiple-pin nets. A heuristic extension is adopted to construct replication graphs with multiple-pin nets. Then we use a directed Fiduccia-Mattheyses algorithm in the constructed replication graph to solve the replication cut problem with size constraints.>

Abstract|Given a huge system represented at gate level, we propose an algorithm mapping the design into the minimum number of FPGAs for logic emulation. We rst devise a Local Ratio-cut clustering scheme to reduce the circuit complexity. Then a Set Covering partitioning approach, utilizing the paradigm of Espresso II, is proposed to replace the widely adopted recursive partitioning paradigm. Experimental results show that our approach achieves signi cant improvement inamuch shorter run time compared to the recursive Fiduccia-Mattheyses approach on large designs. For example, on a benchmark of 160K gates and 90K nets, we reduced the number of FPGAs required by 29 % and reduced the run time by 78%. 1

Abstract| W e propose an ecient performancedriven two-way partitioning algorithm to take i n to account clock cycle period and latency with retiming.W e model the problem with a Quadratic Programming formulation to minimize the crossing edge coun t with nonlinear timing constraints.By using Lagrangian Approach on Modular Partitioning (LAMP), w e merge nonlinear constraints to the objective function.The problem is then decomposed into primal and dual two subprograms.The primal and dual problems are solv ed by a Quadratic Boolean Programming approac h and by a subgradient method using cycle mean method, respectively.Experimental results show our algorithm achieves an average of 23.25% clock cycle period and 19.54% latency reductions compared to the Fiduccia-Mattheyses algorithm.In terms of the a verage number of the crossing edges, our results are only 1.85% more.1 Problem F orm ulation A synchronous digital system can be represented by a directed graph, G(V = R [ C; E); where R is the set of register nodes and C is the set of combinational block nodes.Each n o d e i has an associated size s i and delay d i .E is the set of directed edges which correspond to signal ow in the system.Each edge (i; j) is associated with an attribute c i;j , which denotes the number of the interconnections from nodes i to j.A t w o-way partition P. The capacity limits of these modules are denoted by S 1 and S 2 , respectively.An edge (i; j) i s a crossing edge of P if node i and node j are in dierent subsets V 1 and V 2 .W e assume register nodes and non-crossing edges are of zero delay.The crossing edges have a n i n termodule delay determined by technologies. Assum ptionsW e make the following assumptions in this paper: 1.The intermodule delay is less than the desired clock period, T. 2. Data ow are ne-grained in nature.Although we assume the combinational blocks are negrained, some structures, e.g. the delays on crossing edges, are inherently coarse-grained and cannot be split.

A block-oriented programmable design with switching network interconnect is proposed for fast turn-around, low manufacturing cost, and layout-independent high-speed systems. We introduce the architecture and investigate the constraints and properties originated from the architecture. We show that routability is the most crucial concern for a successful design, and propose objective functions as well as algorithms for switching network optimization. The mapping for the circuits is performed by partitioning, placement, and routing using a maximum matching method. The integration of the whole system demonstrates excellent results in terms of circuit usage.>

We propose a novel paradigm for two-way circuit partitioning which minimizes the clock cycle. The replication technique is suggested for feedback loops to minimize the impacts of intermodule delays and the crossing edges when necessary. A flow timing cut is devised to produce partitions which can be guaranteed to achieve clock cycles equal to their lower bound with respect to the partitions using retiming. When the clock cycle optimization is the major objective and feedback loop sizes are not large, we propose an efficient, easy to implement algorithm which still guarantees achieving the lower bound clock cycle with respect to its partition. Experimental results have shown that our algorithms can achieve an average of 15% clock cycle time reduction compared to the best retimed results produced by 20 runs on each test case using a Fiduccia-Mattheyses algorithm.

The authors propose two nonrecursive algorithms for reconstructing the original binary tree from its inorder and preorder traversals. The proposed algorithms proceed in two stages: the first stage establishes the i-p sequence while the second stage reconstructs the binary tree from the i-p sequence. One algorithm, which requires O(N) time, is time-optimal but space-inefficient, while the other requires O(N log N) time and O(N) space. If sorting and binary search are used, then the space required is optimal within a constant factor. If, instead, hashing is used, the computation time required is optimal within a constant factor. Simple modifications of the proposed algorithm can be used to reconstruct the original binary tree from its inorder and postorder traversals.>