Power consumption and the thermal wall have become the major factors limiting the speed of very-large-scale integration (VLSI) circuits, while interconnect is becoming a primary power consumer. These factors bring new demands on the communication architecture of system-on-chips (SoCs). High bandwidth is desired to enhance parallelism for better performance, and the power efficiency on this bandwidth is critical to the overall SoC power consumption. Current bus architectures such as AMBA, Coreconnect, and Avalon are convenient for designers but not efficient on power. This paper proposes a physical synthesis scheme for on-chip buses and bus matrices to minimize the power consumption, without changing the interface or arbitration protocols. By using a bus gating technique, data transactions can take shortest paths on chip, reducing the power consumption of bus wires to minimal. Routing resource and bandwidth capacity are also optimized by the construction of a shortest-path Steiner graph, wire sharing among multiple data transactions, and wire reduction heuristics on the Steiner graph. Experiments indicate that the gated bus from our synthesis flow can save more than 90% dynamic power on average data transactions in current AMBA bus systems, which is about 5-10% of total SoC power consumption, based on comparable amount of chip area and routing resources.

Power consumption of system-level on-chip communications is becoming more significant in the overall system-on-chip (SoC) power as technology scales down. In this paper, we propose a low power design technique of gated bus which can greatly reduce power consumption on state-of-the-art bus architectures. By adding demultiplxers and adopting a novel shortest-path Steiner graph, we achieve a flexible tradeoff between large power reduction versus small wire-length increment. According to our experiments, using the gated bus we can reduce on average 93.2% of wire capacitance per transaction, nearly half of bus dynamic power and on a scale of 5%~10% of total system power.

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.

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.

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

We propose a simulated annealing based zero-skew clock net construction algorithm that works in any routing spaces, from Manhattan to Euclidean, with the added flexibility of optimizing either the wire length or the propagation delay. We first devise an O(log n) tree grafting perturbation function to construct a zero-skew clock tree under the Elmore delay model. This tree grafting scheme is able to explore the entire solution space asymptotically. A Gauss-Seidel iteration procedure is then applied to optimize the Steiner point positions. Experimental results have shown that our algorithm can achieve substantial delay reduction and encouraging wire length minimization compared to previous works.>

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

Multi-chip module (MCM) technology has become an important means to package high performance systems. An important task during the packaging process is to check for possible open, short, and high resistance faults in the wiring networks of the bare MCM substrates, which is called substrate testing. After examining several substrate testing methodologies, we find that multi-probe or k-probe testers are cost-effective for substrate testing. However, the testing speed of this method is not high; hence, we focus on improving the throughput by reducing the number of tests and by deriving good probe routes. For test size reduction, we propose a routing tree model to capture the wiring structure of a given net; then by taking advantage of the routing tree, we generate a minimum number of tests while ensuring complete open fault coverage. Our algorithm reduces the number of tests by up to 50% compared to that of previous approaches. Given a routing tree with its node degree bounded by a constant, our test generation algorithm runs in linear time with respect to the number of leaves of the tree. For probe route scheduling, we observe that in order to obtain a balanced and efficient scheduling, the routes of different probes must be considered simultaneously, which motivates our Multi-Dimensional Traveling Salesman Problem (MDTSP) formulation. Our package has been installed on existing substrate testers and has achieved encouraging results.>

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 k-probe testing methodology is an effective approach to detect open and short faults in MCM substrates. An algorithm which generates the minimum number of tests for complete open fault coverage is proposed. For k equals two, the algorithm is able to reduce the test size by up to 50% compared with that generated by an ordinary approach. A multidimensional traveling salesman problem formulation is developed to optimize probe routes. The approach has been tested on substrate testers and has achieved excellent results.>