I presented my first technical paper in the EDA area at the Nineteenth Design Automation Conference in 1982. The thirty years since then was such a short, long, and wonderful period of time!

Simulation-based power estimation is commonly used for its high accuracy despite excessive computation times. Techniques have been proposed to speed it up by compacting an input sequence while preserving its power-consumption characteristics. We propose a novel method to compact a sequence that preserves transition frequencies. We prove the problem is NP-complete, and propose a graph model to reduce it to that of finding a heaviest-weighted trail, and a heuristic utilizing this model. We also propose using multiple sequences for better accuracy with even shorter sequences. Experiments show that power dissipation can be estimated with an error of only 2.3%, while simulation times are reduced by 10. Proposed methods generate solutions that effectively preserve transition frequencies and that are very close to optimal. Experiments also show that multiple sequences grant more accurate results with even shorter sequences.

Coupling effect due to line-to-line capacitance is of serious concern in timing analysis of circuits in ultra deep submicrometer CMOS technology. Often coupling delay is heavily dependent on temporal correlation of signal switching in relevant wires. Temporal decorrelation by shifting timing window can alleviate performance degradation induced by tight coupling. This paper presents an algorithm for minimizing circuit delay through timing window modulation in dual V/sub t/ technology. Experimental results on the ISCAS85 benchmark circuits indicate that the critical delay will be reduced significantly when low V/sub t/ is applied properly.

Realization of high-performance domino logic depends strongly on energy-efficient and noise-tolerant interconnect design in ultradeep submicrometer processes. We characterize the cycle-averaged power model for interconnects accounting for switching statistics and dynamic behaviors. For the sake of signal integrity, cross-coupling effects are also characterized, which reflect logical correlation between adjacent wires. Based on the new models for interconnect power and capacitive crosstalk, we optimize the coupling power consumed by interconnects with crosstalk constraints. Experimental results show that optimized designs save the power consumption about 14% on average.

In this paper, we propose a technology mapping algorithm for CPLD architectures. Our algorithm proceeds in two phases: mapping for single-output PLAs and packing for multiple-output PLAs. In the mapping phase we propose a look-up-table (LUT) based mapping algorithm. We will take advantage of existing LUT mapping algorithms for area and depth minimization. Benchmark results show that our algorithm produce better results in terms of area and depth as compared to TEMPLA.

In this paper, we present a new approach to the problem of inverter elimination in domino logic synthesis. A small piece of static CMOS logic is introduced to the circuit to avoid significant area penalty resulting from duplication. To maximize the domino logic part and to minimize the static CMOS logic part, a generalized automatic test pattern generation (ATPG)-based logic transformation is proposed to eliminate or relocate a target inverter. Based on the new concept of dominating set of mandatory assignment (DSMA) and the corresponding implication graph, we propose algorithms to identify a minimum candidate set for a target inverter. Experimental results show that logic transformation based on the implication graph can reduce transistor counts by 25% on average, while the delay increases less than 3%.

In this article we present a new approach to the problem of local logic transformation for reducing power dissipation in logic circuits. The proposed approach overcomes one of the critical limitations common to the previous approaches of local logic transformations for low power, namely, a sequential greedy transformation that identifies signals with high switching activities and then resynthesizes the signals one by one. Instead, we identify a set of signal lines as a group for logic transformation, and determine an order of transformation of the signals with the maximum reduction of power dissipation in the circuit. As a practically feasible solution to this problem, we develop a power model called a finite state input transition (FIT) model, which allows the efficient measurement of the change of power dissipation of the circuit for every possible sequence of logic transformations among the signal lines. Experimental results show that the proposed approach performs an extensive local logic transformation, reducing power consumption by 33% on average without any increase of circuit delay.

Coupling effect due to line-to-line capacitance is of serious concern in timing analysis of circuits in ultra deep submicron CMOS technology. Often coupling delay is strongly dependent on temporal correlation of signal switching in relevant wires. Temporal decorrelation by shifting timing window can alleviate performance degradation induced by tight coupling. This paper presents an algorithm for minimizing circuit delay through timing window modulation in dual $V_t$ technology. Experimental results on the ISCAS85 benchmark circuits indicate that the critical delay will be reduced significantly when low $V_t$ is applied properly.

We present methods to generate a Binary Decision Diagram (BDD) with minimum expected path length. A BDD is a generic data structure which is widely used in several fields. One important application is the representation of Boolean functions. A BDD representation enables us to evaluate a Boolean function: Simply traverse the BDD from the root node to the terminal node and retrieve the value in the terminal node. For a BDD with minimum expected path length will be also minimized the evaluation time for the corresponding Boolean function. Three efficient algorithms for constructing BDDs with minimum expected path length are proposed.

Traditionally, interconnects in multilayer routing technologies have been routed greedily, one at a time. This yields good routings for the first few interconnect trees, but poor routings for the remaining trees. In contrast, we present a new performance-driven approach for layer assignment and routing in which the quality of the routing is largely order independent, minimizing the peak tree delays in the process. We introduce a dynamically adjusted area quota for each tree on each routing layer. This ensures that no tree uses up excessive routing space on the "good" layers. Since the parasitic coupling of different layers varies over a large range, assignment of the edges in the trees to specific routing layers has a large impact on the interconnect delay. Furthermore, we derive an expression for the contribution of an edge in a tree to the total delay of that tree as a function of the layer to which the edge is assigned. We use this expression to introduce a lookahead key for each edge of each tree that enables us to decide whether to route that edge immediately on the current layer or to postpone it to a subsequent layer. Our approach can be used to construct a performance-driven layer assignment and routing algorithm specifically tailored toward any given combination of the timing, routing and technology models. Our experimental results demonstrate that this approach consistently outperforms the multipass greedy scheme currently in vogue, both in worst case delay and in routability.

In this paper, we propose an architecture driven partitioning algorithm for netlists with multiterminal nets. Our target architecture is a multifield-programmable gate array (FPGA) emulation system with folded-Clos network for board routing. Our goal is to minimize the number of FPGA chips used and maximize routability. To that end, we introduce a new cost function: the average number of pseudoterminals per net in a multiway cut. Experimental result shows that our algorithm is very effective in terms of the number of chips used and routability as compared to other methods.

Wallace-tree compressor style has been widely recognized as one of the most effective implementation schemes for arithmetic computation sin VLSI design. However, the scheme has been applied only in a rather restrictive way, that is, for implementing fast multipliers and for generating fixed structures without considering the characteristic of the input signals. The contributions of our work are (1) to extend the applicability of the Wallace scheme to any arithmetic circuit which consists of additions/substractions/multiplications globally (instead of applying it to each operation) to produce a globally efficient architecture of the circuit; (2) to optimize the timing of the circuit for uneven signal arrival profiles; (Specifically, we present an efficient algorithm for generating a delay-optimal (bit-level) carry-save addition structure of an arithmetic circuit.) (3) to provide a comprehensive analysis of the switching activity of a (bit-level) carry-save addition structure, and based on which we derive an effective algorithm for synthesizing low power circuits. Putting these arithmetic optimization solutions together, a circuit designer will be able to fully understand the synthesis of arithmetic circuit based on the bit-level carry-save addition.

Coupling effects between on-chip interconnects must be addressed in ultra deep submicron VLSI and system-on-a-chip (SoC) designs. A new low-power bus encoding scheme is proposed to minimize coupled switchings which dominate the on-chip bus power consumption. The coupling-driven bus invert method use slim encoder and decoder architecture to minimize the hardware overhead. Experimental results indicate that our encoding methods save effective switchings as much as 30% in an 8-bit bus with one-cycle redundancy.

Realization of high-performance domino logic depends strongly on energy-efficient and noise-tolerant interconnect design in ultra deep sub-micron processes. We characterize the cycle-averaged power model for interconnects accounting for switching statistics and dynamic behaviors. For the sake of signal integrity, cross-coupling effects are also characterized which reflect logical correlation between adjacent wires. Based on the new models for interconnect power and capacitive crosstalk, we optimize the coupling power consumed by interconnects with crosstalk constraints. Experimental results show that optimized designs save the power consumption significantly.

Much of the previous work on crosstalk minimization attempted to handle crosstalk during the process of routing the nets. However, this necessitates the estimation of the expected crosstalk due to nets that are yet to be routed. In contrast, post-processing algorithms can use accurate crosstalk measurements to respace the wires, thus improving the crosstalk even in routings produced by crosstalk-aware routers. However, the postprocessing algorithms presented so far have been restricted either by the use of a gridded model or by the difficulty of optimizing the highly nonlinear crosstalk-based objective functions. We address the problem of minimizing the peak crosstalk in a routed region by respacing its critical nets and their neighbors. We study the variation of the crosstalk in a net and its neighbors when one of its trunks is perturbed, showing that the trunk's perturbation range can be efficiently divided into subintervals having monotonic or unimodal crosstalk variation. This result enables us to determine the optimum location for the trunk without needing to solve any nonlinear equations. Using this, we construct an algorithm to minimize the peak crosstalk in the nets of a gridless channel. Although we present our results in terms of channel routing, our theory is also applicable to more general routing models. Furthermore, our crosstalk model subsumes the models used in most prior works on noise-aware routing. Our experiments verify the effectiveness of our approach.

We study the variation of the crosstalk in a net and its neighbors when one of its trunks is perturbed, showing that the trunk's perturbation range can be efficiently divided into subintervals having monotonic or unimodal crosstalk variation.We can therefore determine the optimum trunk location without solving any non-linear equations.Using this, we construct and experimentally verify an algorithm to minimize the peak net crosstalk in a gridless channel.

In this paper we present a new approach to the problem of local logic transformation for reduction of power dissipation in logic circuits. Based on the finite-state input transition (FIT) power dissipation model, we introduce a cost function which accounts for the effects of input capacitance, input slew rate, internal parasitic capacitance of logic gates, interconnect capacitance, as well as switching power. Our approach provides an efficient way of estimating estimating the global effect of local logic transformations in logic circuits. In our approach, the FIT model for the transitive fanout cells of a locally transformed subcircuit can be reused to measure the global power dissipation by varying the input probabilities of the transitive fanout cells. Local logic transformation is carried our based on compatible sets of permissible functions (CSPF). Experimental results show that local logic transformation based on CSPF using our cost function can reduce power consumption by about 36% on average without increase in the worst-case circuit delay.

In this paper, we present a new approach to the problem of inverter elimination in domino logic synthesis. A small piece of static CMOS logic is introduced to the circuit to avoid significant area penalty resulting from duplication. To maximize the domino logic part and to minimize the static CMOS logic part, a generalized ATPG based logic transformation is proposed to eliminate or relocate a target inverter. Based on the new concept of dominating set of mandatory assignment (DSMA) and the corresponding implication graph, we propose algorithms to identify a minimum candidate set for a target inverter. Experimental results show that logic transformation based on an implication graph can reduce transistor counts by 25% and power delay product by 25% on average.

Carry-save-adder(CSA) is one of the most widely used schemes for fast arithmetic in industry. This paper provides a solution to the problem of finding an optimal-timing allocation of CSAs. Specifically, we present a polynomial time algorithm which finds an optimal-timing CSA allocation for a given arithmetic expression. In addition, we extend our result for CSA allocation to the problem of optimizing arithmetic expressions across the boundary of design hierarchy by introducing a new concept, called auxiliary ports. Our algorithm can be used to carry out the CSA allocation step optimally and automatically, and this can be done within the context of a standard HDL synthesis environment.

This paper deals with partial scan approaches that select scan signals oblivious to the availability of flip-flops (FFs). Such approaches can greatly reduce the number of scan signals since maximum freedom is presented when selecting signals. However, to actually scan the selected signals, one must make them drive FFs. We study the problem of replicating and retiming a circuit to make a set of scan signals drive FFs while preserving the set of cycles broken by the signals. We present a framework for solving the problem. Based on the framework, we present an efficient algorithm which also minimizes the amount of logic replication.

b thw paper, we propose an architecture driven partitioning algorithm for nethsts tith mtiti-termind nets.Our target architecture is a mtiti-FPGA emulation system with folded-Clos network for board routing.Our gord is to minimize the number of FPGA chips used and maximize the routabfity.To that end, we introduce a new cost function: the average number of pseudo terrninrds per net in a mdti-way cut.Experiment restit shows that our flg~ rithm is very effective in terms of the number of chips used and the routabfity as compared to other methods. 1

Simrdation-based po~verestirnation is commody used for its high accuracy, despite excessive computation times.Techniques have been proposed to speed it up by transforming a given sequence into a shorter one ~v~e preserving the po}ver consumption characteristic of the original sequence.This ~vorkproposes a novel method to compact a given input vector sequence to improve on the etisting techniques.We pro pose a graph model to transform the problem to the problem of finding a heaviest ~veighted trti in a dmected graph.We also propose a heuristic b~ed on rnin-cost flo~v algorithms, using the graph model.Furthermore, ~ve sho~v that generating multiple input.sequences yields better solutions in terms of both accuracy and simtiation time.Experiments sho~ved tbat significant reduction in simtiation times can be achieved ~vith extremely accurate resdts.Experiments *O sho~ved that the generation of mtitiple sequences improved the resrdts further both in terms of accuracy and simtiation time.

With the advent of DSM technologies, interconnect delays increasingly overshadow the transistor delays. Furthermore, since the electrical characteristics of di#erentlayers in multilayer routing technologies vary widely, the assignment of the interconnect tree edges to speci#c routing layers has a large impact on the interconnect delays. Traditionally, critical global interconnect trees were routed greedily, one at a time. This caused the #good" layers to be used up largely for the #rst few trees, yielding poor routings for the remaining trees. Multiple passes with di#erent tree orderings were usually used to remedy the situation, although with limited success. We propose the use of dynamically adjusted area quotas to prevent the #rst few trees from monopolizing the #good" layers. Our approach is independent of the routing model or the router employed, and reduces the maximum tree delays by around 15# as compared to traditional algorithms. 1 Introduction The traditional problem of ass...

In this pap er, we present sever al optimization techniques for power reduction utilizing circuit symmetries. There are four kinds of symmetries that we dete ct in a given circuit implementation. First, we pr op ose an algorithm for dete cting the four different typ es ofsymmetries in a given circuit implementation of a Boole an function. Sever alre-synthesis techniques utilizing such symmetries are prop ose d. These techniques enable us to optimize power consumption and delay with no (or very little) ar ea overhead. We have carrie dout experiments on MCNC benchmark circuits to demonstrate the efficiency of the prop ose dtechniques. The aver age power reduction is 14% with little or none ar ea and/or delay overhead.

Till now most efforts in low power lo gic synthesis have oncentr ated on minimizing the total switching activity of a circuit under a zero delay model. This simplification ignor es the effe cts of glitch tr ansitions which may contribute as much as 30% of the total power c onsumption of a circuit. Hence, low power logic synthesis techniques which optimize power under a zer o delay model ar e often not successful in attaining “r eal” p ower savings as measured under a more accurate gener al delay model. In pr actice, to ac curately estimate the switching activity in a circuit under a gener al delay model can be computationally expensive. Hence, to repeatedly call accurate but slow power estimation tools to dir ect the synthesis flow is not a viable approach in the design of low power synthesis tools. In this pap er we take advantage of a fast method for estimating the total switching activity in a circuit under a general delay model to synthesize low power circuits. Sp ecific ally,we use the appr oximation as a basis for algorithms that solve two problems: (1) low power te chnolo gy decomposition of gates under a gener al delay model (2) low power r etiming of sequential cir cuits under a general delay model.

In this paper we consider the problem of clustering sequential circuits subject to a bound on the area of each cluster, with the objective of minimizing the clock period. Current algorithms address combinational circuits only, and treat a sequential circuit as a special case, by removing all flip-flops (FF's) and clustering the combinational part of the sequential circuit. This approach breaks the signal dependencies and assumes the positions of FF's are fixed. The positions of the FF's in a sequential circuit are in fact dynamic, because of retiming. As a result, current algorithms can only consider a small portion of the whole solution space. In this paper, we present a clustering algorithm that does not segment circuits by removing FF's. In additional, it considers the effect of retiming. The algorithm can produce clustering solutions with the optimal clock period under the unit delay model. For the general delay model, it can produce clustering solutions with a clock period provably close to optimal.

We study the technology mapping problem for sequential circuits for look-up table (LUT) based field programmable gate arrays (FPGAs). Existing approaches to the problem simply remove the flip-flops (FFs), then map the remaining combinational logic, and finally put the FFs back. These approaches ignore the sequential nature of a circuit and assume the positions of the FFs are fixed. However, FFs in a sequential circuit can be reposistioned by a functionality-preserving transformation called retiming. As a result, existing approaches can only consider a very small portion of the available solution space. We propose in this paper a novel approach to the technology mapping problem. In our approach, retiming is integrated into the technology mapping process so as to consider the full solution space. We then present a polynomial technology mapping algorithm that, for a given circuit, produces a mapping solution with the minimum clock period among all possible ways of retiming. The effectiveness of the algorithm is also demonstrated experimentally.

In this paper, technology mapping algorithmsfor minimizing power consumption in FPGA design are studied.The technology mapping problem for power minimizationhas been shown to be NP-complete.Furthermore, thereare other important objectives, such as the number of PLBs(Programmable Logic Blocks), the number of levels and soon, that should also be optimized simultaneously.We proposea transformational approach in which we start with amapping solution which optimizes certain objective(s) (e.g., the number of PLBs.)The mapping solution is then transformedto reduce the power consumption while keeping thenumber of PLBs fixed.Our algorithm explores the possibilitiesof transforming the functionality of the PLBs so thatthe switching densities of the output edges of the PLBs willbe reduced, leading to a reduction in total power consumption.Our transformational approach can also be viewed as are-engineering approach in which power reduction is achievedthrough re-routing after the PLBs have been placed, utilizingeffectively the capability of a PLB to realize any booleanfunction of up to k variables.

An abundance of research efforts in low power logic synthesis have so far been focused on AND/OR or NAND/NOR based logic. A typical approach is to first generate an initial multi level AND/OR or NAND/NOR representation of a Boolean function. Next, the representation, is optimized in terms of power. However, there are major classes of circuits such as arithmetic functions which have sizable AND/OR representations but have very compact AND/XOR representations. For these functions, the AND/OR based optimization approach often yields poor results. We propose a paradigm for low power logic synthesis based on AND/XOR representations of Boolean functions. Specifically, we propose transforming a Boolean function into a Fixed Polarity Reed Muller form that allows us to efficiently synthesize XOR trees and AND trees with provably minimum switching activity. Preliminary experimental results show that we attain good power savings with negligible area overhead and often area reduction when compared to conventional AND/XOR based synthesis methods and the Berkeley SIS system.

We consider the problem of clustering sequential circuits subject to a bound on the area of each cluster, with the objective of minimizing clock period. Current algorithms address combinational circuits only, and treat a sequential circuit as a special case, by removing the flip-flops (FFs) and clustering the remaining combinational logic. This approach segments a circuit and assumes the positions of the FFs are fixed. The positions of FFs are in fact dynamic, because of retiming. As a result, current algorithms can only consider a small portion of the available solution space. In this paper, we present a clustering algorithm that does not remove the FFs. It also considers the effect of retiming. The algorithm can produce clustering solutions with optimal clock periods under the unit delay model. For the general delay model, it can produce clustering solutions with clock periods provably close to minimum.

We present a new iterative algorithm for timing-driven placement applicable to regular architectures such as field-programmable gate arrays (FPGAs). Our algorithm has two phases in each iteration: a compression phase and a relaxation phase. We employ a novel compression strategy based on the longest path tree of a cone for improving the timing performance of a given placement. Compression might cause a feasible placement to become infeasible. The concept of a slack neighborhood graph is introduced, and is used in the relaxation phase to transform an infeasible placement into a feasible one using a mincost maxflow formulation. The slack neighborhood graph approach used in the relaxation phase guarantees a bounded increase in delay during the relaxation phase. Our analytical results regarding the bounds on delay increase during relaxation are validated by the rapid convergence of our algorithm on benchmark circuits, We obtain placements that have 13% less critical path delay (on the average) than those generated by the Xilinx automatic place and route tool (apr) on technology-mapped MCNC benchmark circuits. The running time of our algorithm is significantly less than that of apr. Slack neighborhood graphs are of independent interest because they can also be used for timing-driven reconfiguration for yield enhancement and for handling incremental design changes efficiently.

A new class of routing structures with fixed orthogonal wire segments and field programmable switches at the intersections of the wire segments is proposed. In comparison with the conventional two-dimensional field-programmable gate array (FPGA) routing structure, this class of routing structures has the advantage of using a smaller number of active programmable switches. An existing field-programmable interconnect chip (FPIC) routing structure can be included as a special case in our class of routing structures. Using a probabilistic model, we prove that complete routing can be achieved with a high degree of probability in a routing structure of this class in which the number of tracks in each channel approaches the lower bound asymptotically. We present a sequential routing algorithm based on the solution of the single net routing problem. We take into account the delay introduced by the active programmable switches on a routing path and formulate the single net routing problem as a node-weighted Steiner minimum tree (NWSMT) problem in a bipartite graph G. Since our single net routing problem is NP-complete, a polynomial time approximate algorithm is proposed. We prove that our single net routing algorithm produces an optimal solution for some special classes of bipartite graphs. In general, the solution obtained by our algorithm bas a performance bound of min{/spl Delta/(V/Z), |Z|-1}. Experimental results for several industrial circuits show a reduction of up to 41% in the number of active programmable switches when compared with corresponding results for the conventional FPGA routing structure.

In this paper, we describe a t e chnique for power reduction in sequential circuits.Existing signals in the circuit are used to selectively disable some of the registers so that a portion of the circuit will be d e activated.Consequently, average power consumption in the circuit is reduced a t a c ost of small increases in area and delay.We present an algorithm for determining the desensitizing signal for each register.A signi cant amount of power reduction is achieved in a number of benchmark circuits according to our experimental results.

In this paper, we study the technology mapping problem for sequential circuits for LUTbased FPGAs.Existing approaches map the combinational logic between ip-ops (FFs) while assuming the positions of the FFs are xed.We study in this paper a new approach to the problem, in which retiming is integrated into the technology mapping process.We present a polynomial time technology mapping algorithm that can produce a mapping solution with the minimum clock period while assuming FFs can be arbitrarily repositioned by retiming.The algorithm has been implemented.Experimental results on benchmark circuits clearly demonstrate the advantage of our approach.For many benchmark circuits, our algorithm produced mapping solutions with clock periods not attainable by a mapping algorithm based on existing approaches, even when it employs an optimal delay mapping algorithm for combinational circuits.

No abstract available.

We describe an algorithm for the synthesis and optimization of interface circuits for embedded system components such as microprocessors, memory ASIC, and network subsystems with fixed interfaces. The algorithm accepts the timing characteristics of two system components as input, and generates a combinational interface (glue logic) circuit. The algorithm consists of two parts. In the first part, we determine the direct pin-to-pin connections in the interface circuit employing a 0/1 ILP formulation to minimize wiring area and dynamic power consumption. In the second part, we determine logic subcircuits in the interface circuit, utilizing the timing diagrams of the system components. The proposed algorithm has been implemented in a software package SYNTERFACE. Experimental results are presented to demonstrate the effectiveness of the algorithm.

As technology advances, interconnection wires are placed in closer proximity and circuits operate at higher frequencies. Consequently, reduction of crosstalk between interconnection wires becomes an important consideration in VLSI design. In this paper, we study the gridded channel routing problem with the objective of satisfying crosstalk constraints for the nets. We proposed a new approach to the problem which utilizes existing channel routing algorithms and improves upon the routing results by permuting the routing tracks. The permutation problem is proven to be NP-complete. A novel mixed ILP formulation and effective procedures for reducing the number of variables and constraints in the mixed ILP formulation are then presented. The new algorithm is tested on three large benchmark circuits as well as many randomly generated circuits. The experimental results are very promising.

We present in this article a new approach to the synthesis problem for finite state machines with the reduction of power dissipation as a design objective. A finite state machine is decomposed into a number of coupled submachines. Most of the time, only one of the submachines will be activated which, consequently, could lead to substantial savings in power consumption. The key steps in our approach are: (1) decomposition of a finite state machine into submachines so that there is a high probability that state transitions will be confined to the smaller of the submachines most of the time, and (2) synthesis of the coupled submachines to optimize the logic circuits. Experimental results confirmed that our approach produced very good results (in particular, for finite state machines with a large number of states.)

A partial scan approach proposed recently selects scan signals without considering the availability of the ip-ops (FFs).Such a n approach can greatly reduce the number of scan signals since maximum freedom is allowed in scan signal selection.To actually scan the selected signals, we, however, must make them FF-driving signals.In this paper, we study the problem of modifying and retiming a circuit to make a pre-selected set of scan signals FF-driving signals while preserving the set of cycles being broken.We present a new approach for solving this problem.Based on the new approach w e design an ecient algorithm.Unlike a previous algorithm which inherently has no control over the area overhead incurred during the modi cation, our algorithm explicitly minimizes the area overhead.The algorithm has been implemented and encouraging results were obtained.

In this paper we examine three different problems related to FPGA placement: timing driven placement of a technology mapped circuit, timing driven reconfiguration for yield enhancement and fault tolerance in FPGAs and timing driven design re-engineering for FPGAs. We show that timing driven relocation which transforms an infeasible placement into a feasible one is a key problem the solution of which will lead to good algorithms for all three of these optimization problems. We introduce the concept of a slack neighborhood graph (SNG) as a general tool for timing driven relocation of modules in an infeasible placement with a bounded increase in critical path delay. The slack neighborhood graph approach provides a unified approach to the solution of three timing driven optimization problems of interest in this paper.

In a typical design flow, the design may be altered slightly several times after the initial design cycle according to minor changes in the design specification either as a result of design debugging or as a result of changes in engineering requirements. These modifications are usually local and are referred to as engineering changes. In this paper we study the problem of timing driven placement re-engineering: the problem of altering the placement of a circuit to incorporate engineering changes without degrading the timing performance of the circuit. We focus on the re-engineering problem for regular architectures such as FPGAs and gate arrays. Our algorithms exploit the locality of the re-engineering design changes and use the current placement to generate the new placement for the altered circuit. Our experiments on the Xilinx 3000 FPGA architecture demonstrate the effectiveness of our algorithm in handling engineering changes efficiently.

In this paper we study the area minimization problem in floorplanning (also known as the floorplan sizing problem). For a given floorplan, the problem is to select a layout alternative for each subcircuit on a chip so as to minimize the chip area. Two area minimization methods for general floorplans are proposed. Both methods can be viewed as generalizations of the classical algorithm for slicing floorplans of Otten (1982) and Stockmeyer (1983) in the sense that they reduce naturally to their algorithm for slicing floorplans. Compared with the branch-and-bound algorithm of Wimer et al (1989), which does not have a nontrivial performance bound, our methods are provably better than an exhaustive method for all the examples we examined.>

In this paper we consider the problem of reconfiguring processor arrays subject to computational loads that alternate between two modes. A strict mode is characterized by a heavy computational load and severe constraints on response time while a relaxed mode is characterized by a relatively light computational load and relaxed constraints on response time. In the strict mode, reconfiguration is performed by a distributed local algorithm in order to achieve fast recovery from faults. In the relaxed mode, a global reconfiguration algorithm is used to restore the system to a state that maximizes the probability that future faults occurring in subsequent strict modes will be repairable. Several new results are given for this problem. Efficient reconfiguration algorithms are described for a number of general classes of architectures. These general algorithms obviate the need for architecture-specific algorithms for architectures in these classes. We show that it is unlikely that similar algorithms can be obtained for related classes of architectures since the reconfiguration problem for these classes is NP-complete. Finally, a general approximation algorithm is described that can be used for any architecture. Experimental results are given, suggesting that our algorithms are very effective.>

This paper studies the routing problem for a new Field-Programmable Gate Array (FPGA) and Field-Programmable Interconnect Chip (FPIC) routing architecture which improves upon the one proposed in [9] by providing continuing switches along the horizontal and vertical wire segments.The addition of continuing switches leads to higher routability and better timing performance than that for the routing architecture in [9].A two-phase routing algorithm for the new routing architecture is developed.Both the initial routing phase and the rip-up and reroute phase employ a dynamic programming technique.The rip-up and reroute phase can also be applied to the segmented channel routing problem for row-based FPGA routing structures.Experimental results show that routability is improved dramatically and the number of active programmable switches in connecting paths and the total number of programmable switches are reduced, when compared with the results in [9] and [3].The running time of the algorithm is less than 7 seconds for each o f v e industrial circuits.

A new scheduling algorithm for dataflow graphs with nested conditional branches is presented. The algorithm employs a bottom-up approach to transform a dataflow graph with conditional branches into an "equivalent" one that has no conditional branches. A schedule is then obtained for the latter, using a conventional scheduling algorithm, from which a schedule for the former is derived. Our approach is particularly effective when there is a large number of nested conditional branches in a dataflow graph.>

In this paper, a new approach to the problem of allocating multiport memory modules for data storage is presented. Previous approaches divide the allocation problem into two separate steps: (i) grouping the variables (or registers) to form memory modules and (ii) determining the interconnections between the memory modules and functional units. Yet, there is no easy way to predict the result of step (ii) during step (i). In our approach, we place primary importance on the cost of interconnections. Consequently, we try to minimize the cost of interconnections first and then to group the variables to form memory modules later. For a number of benchmark problems, it has been shown that this approach is quite effective.

Article Free Access Share on Optimal graph constraint reduction for symbolic layout compaction Authors: Peichen Pan View Profile , Sai-keung Dong View Profile , C. L. Liu View Profile Authors Info & Claims DAC '93: Proceedings of the 30th international Design Automation ConferenceJuly 1993Pages 401–406https://doi.org/10.1145/157485.164950Published:01 July 1993Publication History 3citation291DownloadsMetricsTotal Citations3Total Downloads291Last 12 Months14Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Publisher SiteeReaderPDF

As technology advances, interconnection wires are placed in closer proximity and circuits operate at higher frequencies. Consequently, reduction of crosstalks between interconnection wires becomes an important consideration in VLSI design. In this paper, we study the gridded channel routing problem with the objective of satisfying crosstalk constraints for the nets. We propose a new approach which utilizes existing channel routing algorithms and improves upon the routing results by permuting the routing tracks. A novel mixed integer linear programming (ILP) formulation and effective procedures for reducing the number of variables and constraints in the mixed ILP formulation are then presented. The experimental results are encouraging.

A new class of routing structures with fixed orthogonal wire segments and field programmable switches at the intersections of the wire segments is proposed. In comparison with the conventional two dimensional field-programmable gate array (FPGA) routing structure, this class of routing structures has the advantage of using a smaller number of programmable switches. Using a probabilistic model, we prove that complete routing can be achieved with a high degree of probability in a routing structure of this class in which the number of tracks in each channel approaches the lower bound asymptotically. A sequential routing algorithm which is based on the solution of the single net routing problem is presented. We take into account the delay introduced by the programmable switches on a routing path and formulate the single net routing problem as a Node-Weighted Steiner Minimum Tree (NWSMT) problem in a bipartite graph G. Since our single net routing algorithm is proposed. We prove that our single net routing algorithm produces an optimal solution for some special classes of bipartite graphs. In general, the solution obtained by our algorithm has a performance bound of min{/spl Delta/(VZ), |Z|-1}. On the other hand, we also prove that it is NP-complete to determine a solution which approximates the optimal solution without any constant bound. Experimental results show a reduction of up to 41% in the number of programmable switches when compared with corresponding results for the conventional FPGA routing structure.

Three physical models for utilizing the area over the cells for routing in standard cell designs are presented. Efficient algorithms for choosing and routing a planar subset of nets over the cells so that the resulting channel density is reduced as much as possible are given. For each of the physical models, it is shown how to arrange intercell routing, over-the-cell routing, and power/ground buses to achieve valid routing solutions. Each algorithm exploits the particular arrangement in the corresponding physical model and produces provably good results in polynomial time. Tests of the algorithms on two industrial standard cell designs show that the method reduces total channel density by as much as 21%.>

The deadline of a request is the time instant at which its execution must complete. The deadline of the request in any period of a job with deferred deadline is some time instant after the end of the period. The authors describe a semi-static priority-driven algorithm for scheduling periodic jobs with deferred deadlines: each job is assigned two priorities, the higher one for old requests and the lower one for the current request. This algorithm is called the modified rate-monotonic algorithm and is based on the well-known rate-monotonic algorithm. It is shown that the modified rate-monotonic algorithm is optimal when the deadline of every job is deferred by max (1, gamma -1) periods or more, where gamma is the ratio between the longest period and the shortest period. When the deadline of each job is deferred by one period of the job, any set of n independent jobs whose total utilization is equal to or less than (1+n(2/sup 1/n/-1))/2 can be feasibly scheduled by this algorithm. This bound approaches 0.845 when n approaches infinity.>

Two methods for the area minimization problem in floorplanning are presented. These methods can be viewed as generalizations of Stockmeyer's algorithm in the sense that they reduce to Stockmeyer's algorithm for floorplans that are slicing. The present methods can also be applied to general floorplans. Compared with the branch-and-bound algorithm, which is enumerative in nature and does not have any nontrivial performance bound for general floorplans, these methods are probably better than exhaustive methods for all the floorplans studied.>

Given a floorplan with L-shaped regions, the problem considered is to choose an implementation from a set of possible implementations for each module such that the resultant floorplan will have minimum area, subject to the constraint that the dual polar graphs of the floorplan must be preserved. The concept of a cut line is extended, and eight types of cut lines that are used to decompose floorplans with L-shaped regions are defined. An O(n/sup 3/) time algorithm for deciding whether a given floorplan is decomposable is presented. A heuristic algorithm, which uses the cut tree obtained by the decomposition algorithm to solve the area minimization problem, is proposed. For floorplans that can not be decomposed by the decomposition algorithm, a branch-and-bound algorithm can be incorporated into the algorithm to solve the area minimization problem. The results obtained are superior to those obtained by running an existing mathematical programming package for at least 1 h, and the execution time is less than 3 min for the most complex test problem.>

The authors present a novel performance driven placement algorithm. They use a convex programming algorithm to compute a set of upper bounds on the net wire lengths. A modified min-cut algorithm is then used to generate a placement with the objective of minimizing the number of nets, the wire lengths of which exceed their corresponding upper bounds. The situation in which the modified min-cut algorithm fails to generate a placement that satisfies the timing requirements is addressed, and an iterative approach is used to modify the set of upper bounds making use of information from previous placements. The algorithm was implemented in C and tested on eight problems on a Sparc 2 workstation.>

A novel scheduling algorithm for dataflow graphs with nested conditional branches is presented. The algorithm employs a bottom-up approach to transform a dataflow graph with conditional branches into an 'equivalent' one that has no conditional branches. A schedule is then obtained for the latter, using a conventional scheduling algorithm, from which a schedule for the former is derived. Experimental results demonstrated that such an approach is quite effective. The proposed bottom-up hierarchical approach is computationally more effective than a global nonhierarchical one.>

The authors propose an algorithm for solving the channel routing problem that arises in QCL (quickly customized logic) technology. Routing in the upper and lower regions of the channel is handled by the algorithms UPPER and LOWER, respectively. All patterns are systematically examined one by one until a routing solution is found. Little computational time is used in determining the routability of each pattern. Consequently, the total running time is reasonable even when a large number of patterns are to be examined. Experimental results are given.>

Reconfigurable chips are fabricated with redundant elements that can be used to replace the faulty elements. The fault cover problem consists of finding an assignment of redundant elements to the faulty elements such that all of the faults are repaired. In reconfigurable chips that consist of arrays of elements, redundant elements are configured as spare rows and spare columns. This paper considers the problem in which a chip contains several replicates of a heterogeneous array, one or more sets of spare rows, and one or more sets of spare columns. Each set of spare rows is identical to the set of rows in the array, and each set of spare columns is identical to the set of columns in the array. Specifically, an ith spare row can only be used to replace an ith row of an array, and similarly with spare columns. Repairing the chip reduces to finding a cover for the faults in each of the arrays. These covers must be disjoint; that is, a particular spare row or spare column can be used in the cover of at most one array. Results are presented for three fault cover problems that arise under these conditions.

Two closely related problems important for performance-driven layout design, the k-layer planar subset problem (k-PSP) and the k-layer topological via minimization problem, are studied. It is shown that both are NP-complete. Moreover, both problems can be solved in polynomial time when the routing regions are crossing channels. It can be shown that under a suitable assumption, all the channels for interblock connections in the general cell design style are crossing channels. The algorithms are based on an efficient algorithm for computing a maximum weighted k-cofamily in a partially ordered set.>

When an over-the-cell routing layer is available for standard cell layout, efficient utilization of routing space over the cells can significantly reduce layout area. In this paper, we present three physical models to utilize the area over the cells for routing in standard cell designs. We also present efficient algorithms to choose and to route a planar subset of nets over the cells so that the resulting channel density is reduced as much as possible. For each of the physical models, we show how to arrange inter-cell routing, over-the-cell routing and power/ground busses to achieve valid routing solutions. Each algorithm exploits the particular arrangement in the corresponding physical model and produces provably good results in polynomial time. We tested our algorithms on several industrial standard cell designs. In our tests, this method reduces total channel density as much as 21%.

A common approach to the over-the-cell channel routing problem is to divide the problem into three steps: (1) routing over the cells; (2) choosing net segments; and (3) routing within the channel. It is shown that the first step can be reduced to the problem and finding a maximum independent set of a circle graph, and thus can be solved optimally in quadratic time. Also, it is shown that to determine an optimal choice of net segments in the second step is NP-hard in general, and an efficient heuristic algorithm for this step is presented. The third step can be carried out using a conventional channel router. On the basis of these theoretical results, an over-the-cell channel router that produces solutions which are better than the optimal two-layer channel routing solutions for all test examples is designed. The over-the-cell channel router also outperforms the over-the-cell channel router described by Y. Shiraishi and Y. Sakemi (ibid., vol.CAD-6, no.3, p.462-71, 1987). In particular, for Deutsch's difficult example, the solution yields a saving of 10.5% in channel routing area when compared with the optimal two-layer channel routing solution, and a saving of 15% in channel routing area when compared with the routing solution produced by the over-the-cell channel router.>

In this paper we study two strategies for modifying a given placement of modules in order to improve the quality of the routing results in the next stage of design. We assume that the modules have already been placed. The first strategy seeks to minimize the total wire length by flipping each module about its vertical and/or horizontal axes of symmetry. The second strategy seeks to minimize the total wire length by rotating each module by a multiple of 90 degrees. We introduce a new algorithm based on the Hopfield-Tank neural-net model to solve these problems. Our algorithm performs better than the best algorithms known for these problems. Both problems are shown to be NP-Complete.

The authors propose a simple and fast iterative improvement algorithm for solving the constrained floorplan design problem. The algorithm allows users to specify an aspect ratio for the bounding rectangle and constraints on the relative positions and separation requirements of blocks. In the first phase of the algorithm, two scaling factors for each flexible block are computed for adjusting the block dimensions iteratively. In the second phase, blocks are placed according to the constraint graphs. If no overlaps are detected, the algorithm stops; otherwise an edge is inserted into one of the constraint graphs to resolve the overlap between one pair of blocks. The algorithm then goes back to the first phase. Experimental results show that this algorithm tends to achieve the prespecified overall aspect ratio and produces floorplans with small overall area.>

A study, motivated by the goal of integrating the placement and routing steps in the physical design of VLSI circuits, of the pin assignment problem for macrocells is discussed. It is assumed that the macrocells have already been placed. It is also assumed that the design of the macrocells is still soft in that although the pins in a cell have a fixed relative order, they can be shifted around the boundary of the cell. An algorithm to determine how the pins are to be shifted so that the weighted sum of the lengths of the connecting wires is minimal is developed. Good experimental results were obtained.>

A common approach to the over-the-cell channel routing problem is to divide the problem into three steps: (1) routing over the cells, (2) choosing net segments, (3) routing within the channel. It is shown that the first step can be reduced to the problem of finding a maximum independent set of a circle graph and thus can be solved optimally in O(n/sup 2/) time. It is also shown that to determine an optimal choice of net segments in the second step is NP-hard in general, and an efficient heuristic algorithm for this step is presented. The third step can be done easily using a conventional channel router. Based on these theoretical results, an over-the-cell channel router was designed which produces better solutions than by the over-the-cell router of Y. Shiraishi and Y. Sakemi (IEEE Trans. Computer-Aided Design, vol.6, no.3, p.462-71, 1987).>

The covering problem assigns redundant elements to replace defective elements so that the chip will function properly. A general model that can be used to represent the relationship between redundant elements and defective elements in a uniform way is presented. This model subsumes many of the models discussed in previous approaches. A complete characterization of the complexity of the covering problems in all the subcases of the model, most of which have not been studied before, is given. It is hoped that the formulation will also lead to new ways of designing reconfigurable chips.>

An approach to the three-layer or four-layer channel-routing problem is presented. A general technique that transforms a two-layer routing solution systematically into a three-layer routing solution is developed. The proposed router performs well in comparison with other three-layer channel routers proposed thus far. In particular, it provides a ten-track optimal solution for the famous Deutsch's difficult example, whereas other well-known three-layer channel routers required 11 or more tracks. The approach is extended to four-layer channel routing. Given any two-layer channel-routing solution without an unrestricted dogleg that uses w tracks, the router can obtain a four-layer routing solution using no more than w/2 tracks. A theoretical upper bound d/2+2 for arbitrary four-layer channel routing problems is also given.>

We present in this paper an algorithm that solves a general array optimization problem. The algorithm can be used for compacting Gate Matrix layouts, SLA's, Weinberger Arrays, and for multiple folding of PLA's. Our approach is based on the technique of simulated annealing. A major contribution of this paper is the formulation of the solution space which facilitates an effective search for an optimal solution. Experimental results are very encouraging.

We present in this paper a new algorithm for floorplan design using the method of simulated annealing. The major contributions of the paper are: 1. A new representation of floorplans (normalized Polish expressions) which enables us to carry out the neighborhood search effectively. 2. A simultaneous minimization of area and total interconnection length in the final solution. Experimental results indicate that the algorithm performs well in many test problems.

A more restricted definition of a PLA folding is introduced, which is called bipartite folding. The additional constraints of a bipartite folding force the resulting PLA to have a more uniform structure. This structure of a column bipartite folding is then exploited when subsequently folding the rows of the PLA. A column bipartite folding creates fewer constraints upon the ability to fold the rows of the resulting PLA; thus there is a greater probability of folding the rows. Obviously, the more columns and rows of the PLA that are folded, the less area that is needed to implement the PLA. An efficient branch and bound algorithm is presented which finds an optimal bipartite folding of a PLA. Our experimental results shows that the size of an optimal bipartite folding compares favorably to the size of a folding discovered by a heuristic algorithm. This algorithm can also be used to partition a large PLA into smaller PLA's.

The time-slot assignment problem for a satellite-switched time-division multiple access system where only a restricted set of all possible switching modes is to be used is studied. An efficient algorithm for finding an optimal assignment is proposed. Also, methods for selecting restricted sets of switching modes are presented.

The notion of a bipartite folding of a PLA is introduced. An efficient branch and bound algorithm is presented which finds an optimal bipartite folding of a PLA. The experimental results give additional justification to this folding technique.

The problem of multiprogram scheduling on a single processor is studied from the viewpoint of the characteristics peculiar to the program functions that need guaranteed service. It is shown that an optimum fixed priority scheduler possesses an upper bound to processor utilization which may be as low as 70 percent for large task sets. It is also shown that full processor utilization can be achieved by dynamically assigning priorities on the basis of their current deadlines. A combination of these two scheduling techniques is also discussed.

The problem of analyzing and synthesizing sorting algorithms is studied. That is, given a sorting algorithm we want to investigate how it works in a step-by-step manner and consequently to assert that it indeed arranges the objects according to a certain ordering relationship, and conversely, given an ordering relationship according to which a set of objects are to be arranged, we want to determine an algorithm that will yield the desired result.

A set of equally long finite sequences, the elements of which are either + 1 or - 1, is said to be a complementary set of sequences if the sum of autocorrelation functions of the sequences in that set is zero except for a zero-shift term. A complementary set of sequences is said to be a mate of another set if the sum of the cross-correlation functions of the corresponding sequences in these two sets is zero everywhere. Complementary sets of sequences are said to be mutually orthogonal complementary sets if any two of them are mates to each other. In this paper we discuss the properties of such complementary sets of sequences. Algorithms for synthesizing new sets from a given set are given. Recursive formulas for constructing mutually orthogonal complementary sets are presented. It is shown that matrices consisting of mutually orthogonal complementary sets of sequences can be used as operators so as to per form transformations and inverse transformations on a one- or two-dimensional array of real time or spatial functions. The similarity between such new transformations and the Hadamard transformation suggests applications of such new transformations to signal processing and image coding.

article Free AccessLattice Functions, Pair Algebras, and Finite-State Machines Author: C. L. Liu Massachusetts Institute of Technology, Department of Electrical Engineering, and Project MAC, Cambridge, Massachusetts Massachusetts Institute of Technology, Department of Electrical Engineering, and Project MAC, Cambridge, MassachusettsView Profile Authors Info & Claims Journal of the ACMVolume 16Issue 3July 1969 pp 442–454https://doi.org/10.1145/321526.321533Published:01 July 1969Publication History 4citation210DownloadsMetricsTotal Citations4Total Downloads210Last 12 Months14Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF