We improve the efficiency of static timing analysis when false paths are considered. The efficiency of timing analysis is critical for the performance driven optimization program because timing analysis is invoked heavily in the inner loop. However, when false paths are dealt with in timing analysis, a large number of tags needs to be created and propagated, thus deteriorating efficiency. In this paper, weminimize the number of the tags through a biclique-covering approach, which iteratively removes a tag if the false path information in the tag is covered by the union of other tags.With the produced tags, we remove the false path timing and guarantee to cover the nonfalse path timing. Since the minimum biclique covering of the general bipartite graph is NP complete [Indag. Math., vol. 39, p. 211, 1977], [Discrete Math., vol. 149, no. 1–3, p. 159, 1996], we use a minimal degree ordering approach to perform the biclique-covering minimization. The experimental results show significant reduction on the number of tags.

This paper presents a heuristic cut-based retiming algorithm for FPGA designs. It handles complex retiming constraints including timing, architectural and structural constraints; improves retimeability by incorporating logic resynthesis; and efficiently integrates with incremental placement. Thus, the algorithm improves timing compliance by allowing groups of registers to be rapidly retimed across blocks of combinational logic in the physical domain without violating any complex constraints. Experiments have shown that this algorithm can improve the performance of FPGA designs by 16% on average, while achieving a 61.7% speedup in terms of runtime compared with classic retiming algorithms.

In this paper we study the effect of post-layout pin permutation of designs for FPGA devices with non-uniform cell delays. We present a simple, but timing optimal, pin permutation scheme, and report the results of applying the scheme on a set of public logic synthesis benchmark designs that were synthesized and placed by state-of-the-art commercial FPGA design tools configured to maximum optimization level. Despite the preceding optimizations, we still observed an average timing improvement of 3.7%. This demonstrates the importance of fully utilizing non-uniform cell delays during design optimizations for modern FPGA devices and the still presenting potential of improvement.

This paper explores the effectiveness of the simultaneous application of pipelining and parallel processing as a total power (static plus dynamic) reduction technique in digital systems. Previous studies have been limited to either pipelining or parallel processing, but both techniques can be used together to reduce supply voltage at a fixed throughput point. According to our first-order analyses, there exist optimal combinations of pipelining depth and parallel processing width to minimize total power consumption. We show that the leakage power from both subthreshold and gate-oxide tunneling plays a significant role in determining the optimal combination of pipelining depth and parallel processing width. Our experiments are conducted with timing information derived from a 65nm technology and fanout-of-four (FO4) inverter chains. The experiments show that the optimal combinations of both pipelining and parallel processing - 8 /spl sim/ 12 /spl times/ FO4 logic depth pipelining with 2 /spl sim/ 3-wide parallel processing - can reduce the total power by as much as 40% compared to an optimal system using only pipelining or parallel processing alone. We extend our study to show how process parameter variations - an increasingly important factor in nanometer technologies - affects these results. Our analyses reveal that the variations shift the optimal points to shallower pipelining and narrower parallel processing - 12 /spl times/ FO4 logic depth with 2-wide parallel processing - at a fixed yield point.

We improve the efficiency of static timing analysis when false paths are considered. The efficiency of timing analysis is critical for the performance driven optimization program because timing analysis is invoked heavily in the inner loop. However, when false paths are dealt in timing analysis, a large number of tags need to be created and propagated, and thus deteriorated the efficiency. In this paper, we minimize the number of the tags through a biclique covering approach, which iteratively removes a tag if the false path information in the tag is covered by the union of other tags. The produced tags remove the false path timing and guarantee to cover the true path timings. Since the minimum biclique covering of the general bipartite graph is NP complete, we use a minimal degree ordering approach to perform the biclique covering minimization. The experimental results show significant reduction on the number of tags.

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.

Binary addition is one of the most frequent operations in computation systems. Dedicated carry logic in modern FPGA devices allows ripple-carry adders to outperform other kinds of adders. However, a long carry chain is still time-consuming in a wide bit-width adder. We propose a new methodology to partition the long carry chain into short segments and organize these segments by applying carry-select or carry-skip schemes. Therefore, the resulting adder can take advantage of fast carry ripple locally, reduce the long signal delay globally, and produce high performance calculations.

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%.

An efficient matrix solver is critical to the analytical placement. As the size of the matrix becomes huge, the multilevel methods turn out to be more efficient and more scalable. Algebraic Multigrid (AMG) is a multilevel technique to speedup the iterative matrix solver [10]. We apply the algebraic multigrid method to solve the linear equations that arise from the analytical placement. A layout based clustering scheme is put forward to generate coarsening levels for the multigrid method. The experimental results show that the algebraic multigrid solver is promising for analytical placement.

In this paper, we present a physical retiming algorithm for sequential circuits implemented in field programmable gate arrays (FPGAs). This algorithm can speed up the sequential circuits by reducing delay of all critical paths with negative slacks. By taking advantage of the physical information provided by placed circuits, this algorithm integrates two operations: retiming and register duplication. Retiming moves registers across combinational components. Register duplication moves registers across interconnect. Circuit functionality remains unchanged while performing these operations. A concept of timing budget is proposed to guide register moves. An accurate delay estimator for FPGA designs is developed to make register moves much more acceptable compared to conventional retiming technique. Experiments show that the physical retiming algorithm proposed in this paper can effectively reduce the critical path delays, increasing maximum frequency by 13.54%, on average, and improving by 59.54%, on average, the minimum slack for sequential circuits implemented in FPGAs.

Timing convergence problem arises when the estimations made during logic synthesis can not be met during physical design. In this paper, an efficient rewiring engine is proposed to explore maximal freedom after placement. The most important feature of this approach is that the existing placement solution is left intact throughout the optimization. A linear time algorithm is proposed to detect functional symmetries in the Boolean network and is used as the basis for rewiring. Integration with an existing gate sizing algorithm further proves the effectiveness of our technique. Experimental results are very promising.

System design, i.e. the design of board-level circuits andsystems-on-a-chip, focuses on the integration of off-the-shelf andapplication-specific VLSI components. A key aspect of systemdesign is to ensure the satisfaction of component interface timingrequirements. This is necessary for the correct exchange ofinformation among components on a system. We present amethodology for the interface timing verification and subsequenttiming-driven floorplanning of systems. We present results on theapplication of this methodology to real-world circuits.

In this paper we present a placement-intelligent resynthesis methodology and optimization algorithms to meet post-layout timing constraints while at the same time reducing the interconnect congestion.We b egin with the synthesized design netlist after initial placement and make incremental modi cations { taking placement into account { to generate a nal netlist and placement that meets the delay constraints after place and route.The algorithms described have been implemented a s p art of a tool for placement based r esynthesis.The tool has been used with a number of pre-optimized designs from industry and to obtain improvements in post-placement delays ranging from 13 to 22% with improved r outability.

A description is given of a placement technique based on hypergraph quadrisection. The authors have developed a standard cell placement procedure based on recursively dividing the netlist into four parts, while minimizing the division cost. They have combined two ideas for placement. One is the extension of the min-cut bisection algorithm to handle quadrisection. The second idea is the simultaneous calculation of min-cut quadrisection and hierarchical global routing. The implementation details are discussed. The results show the implementation to be competitive with simulated annealing.>