There are situations (e.g. for reverse engineering or formal verification) circuit designers would need to extract complicated arithmetic circuitry deeply embedded inside a fully synthesized (or manually touched) million-gate flattened netlist without the knowing of module boundary and IO positions. Besides not knowing the IO and boundary, a formal verification task like comparing two netlists implementing (4A+3B)×C and 4A×C+3B×C respectively is quite challenging for it is an NP-Complete Circuit-SAT problem too. To tackle this problem, we propose a novel Complementary Greedy Coupling (CGC) approach coupling reverse engineering and SAT techniques together for each of them only performs well at proving equality or inequality respectively. The scheme is quite powerful, being able to handle commonly implemented arithmetic modules (Ripple/CLA adders, MUX, various multipliers and their combinations) with runtime complexity nearly linear to the number of circuit gates. For an example, our scheme can verify two 32-bit multipliers (Wallace vs Modified-Booth) within 5 seconds (regardless of their equality or inequality), while running SAT alone might take 1010 centuries. We compared our tool Easy-LEC with the two on market commercial tools using the 182 open benchmarks posted for ICCAD CAD Contest 2014. Besides running at least 400 to 1400 times faster, our scheme also solves 32% to 45% more cases (93% vs 61% or 48%).

During the EDA process, a design may be tampered directly by dishonest engineers (or “industry spy”), or may be tampered indirectly through the use of malicious modules from a third party Intellectual Property (3PIP) block vendor. During integration and fabrication, the chips may also be tampered by untrusted system integrator or even foundry. Particularly for high-end commercial or classified military chips, Hardware Trojan (HT) Detect-Locate-and-Mask (DL&M) is crucially necessary so as to make sure a design is produced exactly as the original specification (golden). Our objectives are (1) to detect any functionality difference which might be caused by bugs or HTs, (2) to locate/output the difference circuitry to correct the bugs or to investigate the tampering intention or purpose, and (3) to “kill” (mask) the HTs by restoring the chip's functionality back to golden with a minimum circuitry change. Besides blocking the plotted damage in an early stage and pointing the spy source by revealing the HT intention, the masking circuit revision must also be minimized to avoid affecting the chip performance (timing) too much. In this paper, we propose a scheme that integrates reverse engineering, formal verification, functional ECO, and logic rewiring to detect, locate and mask Hardware Trojans with minimized cost. This formal verification based scheme can guarantee catching 100% of the hidden combinational circuit HTs and can handle multiple HTs (no number limit) automatically in one run. Some techniques within our scheme won the first places of the CAD Contests at ICCAD 2012, 2013, and 2014 [1-3].

A macro-fault is defined as a group of signal faults such that the errors induced cannot be observed unless two or more faults (either permanent or temporary) in the group happen simultaneously. Since adding a redundant (alternative) wire for an existing (target) wire can mask some certain faults of these two wires mutually, a macro-fault can be formed by redundant wire addition. The faults that are dominated by or equivalent to the masked faults are also included in the macro-fault. As the feature size of integrated circuit technologies continue to scale down, manufacturing fault-free chips is getting more difficult and fault tolerance techniques will become more critical. In the past, redundancy has been adopted for memory for improving fault tolerance. For critical circuit components, even the costly triple modular redundancy techniques have to be applied. In this work, we study the implications of our new fault model, macro-fault, on the potential impact on fault tolerance and manufacturing yield. Based on the findings, a heuristic approach based on redundant wire addition is designed for improving fault tolerance. The approach can be incorporated with other fault tolerance techniques to form a hierarchical cross-layer fault tolerance scheme.

Based on a simple intuitive notion, in this paper, we propose an efficient post-placement improvement scheme. Based on the given timing slack distribution of a circuit, a corresponding “slack mountain map” can be visualized with peaks representing most violating (negative) slacks and valleys representing non-critical (positive) slacks respectively. Guided by this map, violating paths are eliminated or improved when slack mountains are flattened by applying a local logic perturbation technique (rewiring) iteratively to shift logic resources from critical to non-critical areas. Due to the locality property of the rewiring technique, to better avoid being stuck at local minimums, instead of running rewiring operations from the peak top towards lower areas, we do this local logic shifting starting from “sea areas” (most non-critical) towards peak (most critical) areas. At the end, as the slack map is more flattened, a circuit with slack violations more evenly distributed can be yielded. Comparing to the recent work [1], our experimental results demonstrate that this scheme can obtain a better or comparable delay reduction but with CPU time one order of magnitude smaller.

A reconfigurable interconnection network (RIN) is a custom-designed on-chip switching network yielding routing solutions for a pre-given set of applications. Like field programmable gate array (FPGA) routing networks, the RIN is used to make reconfigurable interconnections among functional blocks. Unlike FPGAs, the network topology of a RIN is irregular as it is designed for a given set of routing requirements and optimized for the area cost subject to given delay constraints. In this paper, we propose an automatic design scheme for RINs, including routing specification formulation, graph modelings, network topology designs, routing algorithms and multiplexer-based network circuit implementation. The choice of the design scheme is based on the existing routing network design practices and research, which give feasible solutions. Our scheme is to optimize the designs with the choice of design parameters. A computer-aided design (CAD) tool is developed based on the design scheme, which takes a set of routing requirements as input and produces the corresponding RIN network topology and network circuit in hardware description language format. We present the area costs of various RINs generated by the CAD tool subject to delay constraints, and illustrate the RIN design scheme with a reconfigurable multistream video system.

To maintain a lower re-masking cost, Engineering Change Order (ECO) using pre-placed spare cells for buffer insertion and gate sizing has been shown to be practical for fixing timing violating paths (ECO paths). However, in the previously known best scheme DCP [1, 2], re-routings are done with each path optimized according to its surrounding available spare cells without considering potential exchanges with neighboring active cells, and spare cell arbitration between competing ECO paths are less addressed. Besides, the extra flexibility for allowing logic restructuring was not exploited. In this work, we develop a framework harnessing the following more flexible strategies to make the usage of spare cells for ECO timing optimization more powerful: (1) a negotiation based re-routing scheme yielding a more global view in solving resource competition arbitration; (2) an extended gate sizing operation to allow exchanges of active gates with spare gates of different function types through equivalent logic re-structuring. Our experiments upon MCNC and ITC benchmarks with highly injected timing violations show that compared to DCP, our newly proposed framework can cut down the average total negative slack (TNS) by 50% and reduce the number of unsolved ECO paths by 31%.

Rewiring is a flexible and useful logic transformation technique through which a target wire can be removed by adding its alternative logics without changing the circuit functionality. In today's deep sub-micron era, circuit wires have become a dominating factor in most EDA processes and there are situations where removing a certain set of (perhaps extremely unwanted) wires is very useful. However, it has been experimentally suggested that the rewiring rate (percentage of original circuit wires being removable by rewiring) is only 30 to 40% for optimized circuits in the past. In this paper, we propose a generalized error cancellation modeling and flow to show that theoretically almost every circuit wire is removable under this flow. In the Flow graph Error Cancellation based Rewiring (FECR) scheme we propose here, a rewiring rate of 95% of even optimized circuits is obtainable under this scheme, affirming the basic claim of this paper. To our knowledge, this is the first known rewiring scheme being able to achieve this near complete rewiring rate. Consequently, this wire-removal process can now be considered as a powerful atomic and universal operation for logic transformations, as virtually every circuit node can also be removed through repetitions of this rewiring process. Besides, this modeling can also serve as a general framework containing many other rewiring techniques as its special cases.

This paper presents WRIP - a Wirelength-driven Rewiring-based Incremental Placement which effectively reduces wirelength of the optimized placement of industrial large-scale standard cell designs. WRIP uses a powerful logic synthesis technique called logic rewiring which restructures the local circuits while preserving the logic functionality and reduces the wirelength under an accurate estimation of the half perimeter wirelength (HPWL) metric. We integrated WRIP into an industrial EDA tool and tested it upon several real designs with hundreds of thousands of movable objects. Tested on circuits which has been fully optimized by the state-of-the-art industrial placement tool, our experiments showed that on average WRIP reduces wirelength by 2.25% after placement and 2.45% after global routing in HPWL and Steiner WL model respectively. The runtime of WRIP is only about half an hour for the largest tested ASIC circuit. This is the first attempt to fully integrate powerful logic synthesis into industrial placement tools with real-life effectiveness and efficiency.

Rewiring is known to be a class of logic restructuring technique that is at least equally powerful in flexibility compared to other logic transformation techniques. Especially it is wiring sensitive and is particularly useful for interconnect-based circuit synthesis processes. One of the most well-studied rewiring techniques is the ATPG-based Redundancy Addition and Removal (RAR) technique which adds a redundant alternative wire to make an originally irredundant target wire become redundant and thus removable. In this article, we propose a new Error-Cancellation-based Rewiring scheme (ECR) which can also identify non-RAR-based rewiring operations with high efficiency. In ECR scheme, it is not necessary for alternative wires to be redundant. Based on the notion of error cancellation, we analyze and reformulate the rewiring problem, and a more generalized rewiring scheme is developed to detect more rewiring cases which are not obtainable by existing schemes while it still maintains a low runtime complexity. Comparing with the most recent non-RAR rewiring tool IRRA, the total number of alternative wires found by our approach is about doubled (202%) while the CPU time used is just slightly more (8%) upon benchmarks preoptimized by ABC’s rewriting. Our experimental results also suggest that the ECR engine is more powerful than IRRA in FPGA technology mapping.

All of today's known clock gating techniques only disable clocks on valid (”correct”) clock gating conditions, like idle states or observability don't cares (ODC), whose applying will not change the circuit functionality. In this paper, we explore a technique that allows shutting down certain clocks during invalid cycles, which if applied alone will certainly cause erroneous results. However, the erroneous results will be corrected either during the current or later stages by injecting other clock gating conditions to cancel out each other's error effects before they reach the primary outputs. Under this model, conditions across multiple flip-flop stages can also be analyzed to locate easily correctable erroneous clock gating conditions. Experimental results show that by using this error cancellation technique, a total power (including dynamic and leakage power) cut of up to 23% and in average of around 6% could be stably achieved, no matter with or without applying Power Compiler (which brought a power cut of 4% in average) together. The results indicate that the power saving conditions found by this new technique were nearly orthogonal (independent) to what can be done by the popular commercial power optimization tool. The idea of these new multi-stage logic error cancellation operations can potentially be applied to other sequential logic synthesis problems as well.

Traditional retiming processes are mostly MILP based with the physical interconnect information less correctly reflected, thus could be very CPU intensive and incorrect on the final clock period estimations. Moreover, the number of flip-flops tends to be undesirably increased after the retiming process, which can cause a significant area/power penalty on the retimed circuit. To overcome these major drawbacks of the conventional retiming technique, we first propose a fast retiming algorithm which avoids solving MILP, and with both gate and interconnect delay formulated together. For a more accurate delay estimation, all interconnect delays are formulated and calculated based on real placements. Additionally, we integrate it with a specific rewiring algorithm to cut down the number of flip-flops (FFs) without sacrificing retimed clock periods. Experimental results show that our pure retiming algorithm can achieve an average of 5.75% optimization on the clock period in a very fast speed. With a rewiring algorithm targeting for FF reduction applied, a FF reduction of up to 31.2% (11.3% on average) can be obtained without the compromise on the retimed clock period compared to the pure retimed results.

Rewiring is known to be a new class of logic restructuring technique at least equally powerful in flexibility compared to other logic transformation techniques while being wiring-sensitive, a property particularly useful for interconnect based circuit synthesis processes. One of the most mature rewiring techniques is the ATPG-based Redundancy Addition and Removal (RAR) technique which adds a redundant alternative wire to make an originally irredundant target wire become redundant and thus removable. In this paper, we propose a new Error Cancellation based Rewiring scheme (ECR) which can also do non-RAR based rewiring operations with high efficiency. Based on the notion of error cancellation, we analyze and reformulate the rewiring problem and develop a generalized rewiring scheme being able to detect more rewiring cases which are not obtainable by existing schemes while still maintains low runtime complexity. Comparing with the most recent non-RAR rewiring tool IRRA, the total number of alternative wires found by our approach is about twice while CPU time is just slightly more (26%) upon benchmarks pre-optimized by rewriting of ABC.

Traditionally, clock gating for power saving is mainly done at Register Transistor Level (RTL), while in a lower logical level some synthesis techniques, e.g. Observability Don't Care (ODC) can also be used to provide more power savings. In this paper, we propose an effective logic level ODC-based clock gating scheme that aims to reduce the intra-module dynamic power of sequential circuits. It is accompanied with a rewiring-based pruning scheme to trim down the incurred area overhead. Switching activity is put into account in the optimization processes. Extensive experimental results obtained by using ModelSim and PowerCompiler on the ISCAS-89 benchmarks showed that without rewired area trimming, an average of 40% on clock power and 12% on total dynamic power can be saved with a total cell area overhead of 6%. When rewiring was applied to trim down the area overhead, a similar clock power saving of 40% and an appealing 17% of total dynamic power saving can be achieved with area similar (-1%) to the original non ODC-clock-gated circuits.

Redundancy Addition and Removal (RAR), one of the major combinational logic perturbation techniques, has been shown to be very useful for many EDA optimization tasks. However, all the currently known RAR techniques did not analyze and make use of unreachable states, which are abundant in sequential circuits. These unreachable states can be considered as input don't cares and can add an extra flexibility in locating alternative wires. In this paper, we study the fundamental theory and propose a reasoning scheme for locating alternative wires without performing wasteful redundancy tests. To explore the deeper effect of unreachable states, the concept is extended to illegal assignments and the fault independent redundancy identification is applied on illegal assignments to find flexibilities introduced by unreachable states. On the experiments carried for both MCNC and industry benchmarks, it is shown that using such an idea, a remarkable increase of more than 100% (averagely) in the number of alternative wires can be found, which should be quite useful as most of today's practical circuits are sequential.

A Customized Reconfigurable Interconnection Network (CRIN) refers to a minimal switching network, yielding routing solutions for any element in a pre-given set of routing requirements. The CRIN design problem looks for the best performance and resource-flexibility trade-off between two extreme design contexts ASIC and FPGA. In this paper we give the modeling of this problem for both directed and undirected interconnections. A heuristic algorithm for automatic generation of CRIN is proposed along with its experimental justifications. This study was motivated from the design of reconfigurable systems-on-a-chip for multiple applications.

One unique property of an FPGA chip is that any logic perturbation inside its Look-Up-Tables (LUTs) is totally area/delay-free. Amongst others, this free LUT-internal resource perturbation can also be used to trade for critical LUT-external logic/wire removals for EDA improvements, an extra flexibility ignored before. Using rewiring technique for such logic perturbations, we show that significant cut-downs upon already excellent results from the state-of-the-art DAOmap mappings and the TVPR place-and-route can still be obtained. This logic perturbation operation can further reduce the number of LUTs by up to 33.7% (avg. 10%) without delay penalty and also reduce critical path delay by up to 31.7% (avg. 11%) without disturbing placement or sacrificing area in the final routing. For delay reduction, under proper rewiring strategy, the CPU time used by rewiring is only 5% of the total run time consumed by TVPR's placement and routing. This idea of perturbing logic between the free LUT-internal and critical LUT-external circuit resources is simple and proved to be powerful. The encouraging results suggest a new technique for an optimization domain less explored for FPGA design flow.

FPGA technology mapping is conventionally solved without altering the circuit by modeling the circuit as a direct acyclic graph for the ease of applying graph algorithms. Clearly there is room for further improvement on even optimal technology mapping results if logic perturbation can be applied. In this paper, we propose logic-aware minimization methods to further reduce both depth and area for the purely-graph-based depth-optimal FPGA mapped results. For area minimization, the proposed method perturbs the subject circuit using rewiring technique and incrementally reduce the mapping area. Improving the outstanding technology mapping algorithm DAOMap, the method can further reduce area by 10.9%. An area reduction of 13.4% is achieved with synthesis results from BDS-pga. A logic level reduction scheme is also proposed and it further reduces LUT depth for half of the circuits tested without area penalty. A combination of logic level reduction and area minimization techniques can improve both the LUT depth and area by 11.3% and 6.1%, compared to results of FlowMap and FlowSYN respectively.

A switch block of k sides W terminals on each side is said to be universal (a ( k , W )-USB) if it is routable for every set of 2-pin nets of channel density at most W . The generic optimum universal switch block design problem is to design a ( k , W )-USB with the minimum number of switches for every pair of ( k , W ). This problem was first proposed and solved for k =4 in Chang et al. [1996], and then solved for even W or for k ≤6 in Shuy et al. [2000] and Fan et al. [2002b]. No optimum ( k , W )-USB is known for k ≥7 and odd W ≥3. But it is already known that when W is a large odd number, a near-optimum ( k , W )-USB can be obtained by a disjoint union of ( W − f 2 ( k ))/2 copies of the optimum ( k , 2)-USB and a noncompound ( k , f 2 ( k ))-USB, where the value of f 2 ( k ) is unknown for k ≥8. In this article, we show that f 2 ( k ) = k +3− i /3, where 1≤ i ≤6 and i ≡ k (mod 6), and present an explicit design for the noncompound ( k , f 2 ( k ))-USB. Combining these two results we obtain the exact designs of ( k , W )-USBs for all k ≥7 and odd W ≥3. The new ( k , W )-USB designs also yield an efficient detailed routing algorithm.

We consider the optimal design problem for arbitrary-shaped switch box, (r1...rk) which r, terminals are located on side i for i= 1...k and programmable switches are joining pairs of terminals from different sides. Previous investigations on switch box designs mainly focused on regular switch boxes in which all sides have the same number of terminals. By allowing different numbers of terminals on different sides, irregular switch boxes are more general and flexible for applications such as customized FPGAs and reconfigurable interconnection networks. The optimal switch box design problem is to design a switch box satisfying the given shape and routing capacity specifications with the minimum number of switches. We present a decomposition design method for a wide range of irregular switch boxes. The main idea of our method is to model a routing requirement as a nonnegative integer vector satisfying a system of linear equations and then derive a decomposition theory of routing requirements based on the theory of systems of linear Diophantine equations. The decomposition theory makes it possible to construct a large irregular switch box by combining small switch boxes of fixed sizes. Specifically, we can design a family of hyperuniversal (universal) (u-d + c)-SBs with B(h-) switches, where d and c are constant vectors and w is a scalar. We illustrate the design method by designing a class of optimal hyperuniversal irregular 3-sided switch boxes and a class of optimal rectangular universal switch boxes. Experimental results on the rectangular universal switch boxes with the VPR router show that the optimal design of irregular switch boxes does pay off.

Crossbars have been considered one of the most standard switching modules in conventional communication networks due to its simplicity in routing algorithm and fabrication regularity. While in programmable on-chip interconnection networks such as the routing networks in field programmable gate arrays (FPGAs), switch boxes are often used for a better tradeoff between routability and area efficiency. Much work has been done on the topology design of switch boxes, e.g. universal switch boxes and hyper-universal switch boxes. However, the layout design of switch boxes tends to be difficult when the topology of switch boxes is less regular. In this paper we revisit the theoretical design aspects of the classic crossbar design schemes and further investigate a new design style, a so called meta-crossbar, which is obtained from a crossbar by adding the least number of switches and direct contacts to achieve the desired optimal routability. We show that a switch box can always be implemented by a meta-crossbar. This means that the layout design of switch boxes can be done almost like crossbars. As a result, we present a hyper-universal meta-crossbar design, and a three level meta-crossbar based interconnection network design, which is capable of routing all group communication requirements.

Scan forest is an efficient scan architecture which can reduce the test application cost, test power of scan testing and test data volume greatly. The scan forest is modified for scan-based BIST. Techniques are used to make the existing scan forest architecture to an improved scan forest that is more suitable for BIST. A scan flip-flop regrouping technique is introduced to make the scan flip-flop groups have similar sizes. Sufficient experimental results show that the proposed techniques improve the popular test-per-scan test architecture greatly on fault coverage and test length. It is shown according to the experimental results that test length is reduced 77.3% on average for all benchmark circuits.

A built-in self-test (BIST) scheme which partitions the fixed (instead of movable) capacitance plates of a capacitive MEMS device is proposed. The BIST technique divides the fixed capacitance plate(s) at each side of the movable microstructure into three portions: one for electrostatic activation and the other two equal portions for capacitance sensing. Due to such partitioning, the BIST technique can be applied to surface-, bulk-micromachined MEMS devices and other technologies. Further, sensitivity and symmetry BIST methods based on this partitioning are also introduced. The combination of both BIST modes covers a larger defect set, thus a robust testing for the device can be expected. The BIST technique is verified by three typical capacitive MEMS devices. Simulation results show that the proposed technique is an effective BIST solution for various capacitive MEMS devices.

In this paper, we propose a new FPGA switch box design style --- the extended switch boxes. An extended switch box is multi-level in nature. It consists of a kernel and extension(s) connected to the kernel, while many conventional switch boxes only consist of the kernel part and are referred to as single-level switch boxes. We show that with a much reduced total number of manufactured switches in the chip, this new design has a guaranteed complete mappability from any global routing to a feasible detailed routing of the entire FPGA chip. The interesting results seem to open a new avenue for designing FPGA routing structures.

A new scan architecture is proposed for full scan designed circuits. Scan flip-flops are grouped together if they do not have any common successors. This technique produces no new redundant faults. Scan flip-flops in the same group have the same values in all test vectors. All scan flip-flop groups form a scan forest, where each primary input drives the root of one scan tree. Test application time and test power based on the proposed scan forest architecture can be reduced drastically while pin overhead and delay overhead should be the same as that of conventional scan design. It is shown that test application cost and test power with the proposed scan forest architecture can be reduced to the level of non-scan design circuits.

An FPGA switch box is said to be hyper-universal if it is detailed-routable for any set of multipin nets specifying a routing requirement over the switch box. Comparing with the known "universal switch modules", where only 2-pin nets are considered, the hyper-universal switch box model is more general and powerful. This paper studies the generic problem and proposes a systematic designing methodology for hyper-universal (k, W)-switch boxes, where k is the number of sides and W is the number of terminals on each side. We formulate this hyper-universal (k, W)-switch box design problem as a k-parfite graph design problem and propose an efficient reduction design technique. Applying this technique, we can design hyper-universal (k, W)-switch boxes with low O(W) switches for any fixed k. For illustration, we provide optimum hyper-universal (2, W) and (3, W)-switch boxes and a hyper-universal (4, W)-switch box with switch number quite close to the lower bound 6W, which is used in a well-known commercial design without hyper-universal routability. We also conclude that the proposed reduction method can yield an efficient detailed routing algorithm for any given routing requirement as well.

This paper explores theories on designing optimal multipoint interconnection structures, and proposes a simple switch box design scheme which can be directly applied to field programmable gate arrays (FPGAs), switch box designs, and communication switching network designs. We present a new hyperuniversal switch box designs with four sides and W terminals on each side, which is routable for every multipin net-routing requirement. This new design is proved to be optimum for W = 1, ..., 5 and close to optimum for W /spl ges/ 6 with 6.3 W switches. We also give a formal analysis and extensive benchmark experiments on routability comparisons between today's most well-known FPGA switch boxes like disjoint switch blocks (Xilinx XC4000 Type), Wilton's switch blocks, Universal switch blocks, and our Hyperuniversal switch boxes. We apply the design scheme to rearrangeable switching network designs targeting for applications of connecting multiple terminals (e.g., teleconferencing). Simply using a /spl kappa/-sided hyperuniversal switch block with a W /spl times/ W crossbar attached to each side, one can build a three-stage one-sided polygonal switching network capable of realizing every multipoint connection requirement on kW terminals. Besides, due to the fine-grained decomposition property of our design scheme, the new switch box designs are highly scalable and simple on physical layout and routing algorithm implementations.

Efficient circuit partitioning is becoming more and more important as the size of modern circuits keeps increasing. Conventionally, circuit partitioning is solved without altering the circuit by modeling the circuit as a hypergraph for the ease of applying graph algorithms. However, there is room for further improvement on even optimal hypergraph partitioning results, if logic information can be applied for circuit perturbation. Such logic transformation based partitioning techniques are relatively less addressed. In this paper, we present a powerful multiway partitioning technique which applies efficient logic rewiring techniques for further improvement over already superior hypergraph partitioning results. The approach can integrate with any graph partitioner. We perform experiments on two-, three-, and four-way partitionings for MCNC benchmark circuits whose physical and logical information are both available. Our experimental results show that this partitioning approach is very powerful. For example, it can achieve a further 12.3% reduction in cut size upon already excellent pure graph partitioner (hMetis) results on two-way partitioning with an area penalty of only 0.34%. The outperforming results demonstrate the usefulness of this new partitioning technique.

M. Shyu et al. (2000) defined the well-structured symmetric switch block M/sub N,W/ and showed that M/sub N,W/ is universal for any pair of positive integers N and W. However, we find that this result is partially correct. In this paper, we show that, when N/spl ges/7, M/sub N,W/ is not universal for odd Ws (/spl ges/3) and it is universal for any even W.

A k -side switch block with W terminals per side is said to be a universal switch block (( k , W )-USB) if every set of the nets satisfying the routing constraint (i.e., the number of nets on each side is at most W ) is simultaneously routable through the switch block. The (4, W )-USB was originated by designing better switch modules for 2-D FPGAs, such as Xilinx XC4000-type FPGAs, whereas the generic USBs can be applied in multidimensional or some nonconventional 2-D FPGA architectures. The problem we study in this article is to design ( k , W )-USBs with the minimum number of switches for any given pair of ( k , W ). We provide graph models for routing requirements and switch blocks and develop a series of decomposition theorems for routing requirements with the help of a new graph model. The powerful decomposition theory leads to the automatic generation of routing requirements and a detailed routing algorithm, as well as the reduction design method of building large USBs by smaller ones. As a result, we derive a class of well-structured and highly scalable optimum ( k , W )-USBs for k ≤ 6, or even W s, and near-optimum ( k , W )-USBs for k ≥ 7 and odd W s. We also give routing experiments to justify the routing improvement upon the entire chip using the USBs. The results demonstrate the usefulness of USBs.

A switch block with k sides and W terminals per side ((k; W)-SB) is said to be universal if every set of 2-pin nets satisfying the dimension constraint is simultaneously routable through the switch block. It has been shown that the universal switch blocks (USB) outperform the XC4000-typed switch blocks in routability. In this paper, we present a new combinatorial model and routing requirement decomposition theory for analyzing and designing generalized USB models. As a result, we obtain optimum (k,W)-USBs for k≤6 with all W's, k = 7,8 with even W's; and nearly optimum (k,W)-UBSs for k = 7; 8 with odd W's, which is a revised result on the previously published.

In this paper, we present a competent algorithm to the alternative wiring problem by exploring the relationship between dominators of a target wire. Alternative wiring refers to the process of adding a redundant connection to a circuit such that a target connection will become redundant and can be removed from the circuit. The well-known ATPG-based alternative wiring scheme. Redundancy Addition and Removal for Multi-level Boolean Optimization (RAMBO), has shown its effectiveness in solving the problem in the last decade. The deficiency of RAMBO lies in its long execution time for redundancy identification among a large set of candidate alternative wires in the circuit. Implication-tree Based Alternative Wiring Logic Transformation Algorithm (IBAW) improves the speed of RAMBO by introducing an implication-tree structure for source node identification. Our approach of investigating the dominator relationship suggest that a large subset of unnecessary redundancy checks can be further avoided in order to improve the efficiency. Experiments were performed on MCNC benchmark circuits and results are compared to those of RAMBO and IBAW. Results show that our proposed algorithm improves IBAW with a 2.3 times speedup. Moreover, our implementation runs 8.8 times faster than RAMBO while solution quality is still maintained.

All in-text\treferences\tunderlined\tin\tblue\tare\tlinked\tto\tpublications\ton\tResearchGate, letting you\taccess\tand\tread\tthem\timmediately.

Efficient circuit partitioning is gaining more importance with the increasing size of modern circuits. Conventionally, circuit partitioning is solved by modeling a circuit as a hypergraph for the ease of applying graph algorithms. However there exists room for further improvement on even optimum hypergraph partitioning results, if logic information can be applied for perturbation. In this paper we present a multi-way partitioning framework which can couple any excellent hypergraph partitioner and a noval logic perturbation based technique (GBAW) for further improvement over very excellent partitioning results. Our approach can integrate with any graph partitioner. We performed experiments on 2-, 3-, 4-, and 5-way partitionings for various circuits of different sizes from MCNC benchmarks. We have chosen the state-of-the-art hMetis-Kway to obtain high quality initial solutions for the experiments. Our experiments showed that this partitioning approach can achieve a further 15% reduction in cut size for 2-way partitioning with an area penalty of only 0.33%. The good results demonstrated the effectiveness of this new partitioning technique.

Article Free Access Share on IBAW: an implication-tree based alternative-wiring logic transformation algorithm Authors: Wangning Long Dept. Computer Sci. & Tech., Tsinghua University, Beijing, 100084, China Dept. Computer Sci. & Tech., Tsinghua University, Beijing, 100084, ChinaView Profile , Yu-Liang Wu Dept. Computer Sci. & Eng., The Chinese University of HK, Shatin, NT, Hong kong Dept. Computer Sci. & Eng., The Chinese University of HK, Shatin, NT, Hong kongView Profile , Jinian Bian Dept. Computer Sci. & Tech., Tsinghua University, Beijing, 100084, China Dept. Computer Sci. & Tech., Tsinghua University, Beijing, 100084, ChinaView Profile Authors Info & Claims ASP-DAC '00: Proceedings of the 2000 Asia and South Pacific Design Automation ConferenceJanuary 2000 Pages 415–422https://doi.org/10.1145/368434.368720Online:28 January 2000Publication History 6citation79DownloadsMetricsTotal Citations6Total Downloads79Last 12 Months1Last 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 Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article Free Access Share on Circuit partitioning with coupled logic restructuring techniques Authors: Yu-Liang Wu Dept. Computer Sci. & Eng., The Chinese University of HK, Shatin, NT, Hong Kong Dept. Computer Sci. & Eng., The Chinese University of HK, Shatin, NT, Hong KongView Profile , Xiao-Long Yuan Dept. Computer Sci. & Eng., The Northwest Polytechnical University, Xi'an, 710072, China Dept. Computer Sci. & Eng., The Northwest Polytechnical University, Xi'an, 710072, ChinaView Profile , David Ihsin Cheng Ultima Interconnect Technology, Sunnyvale, CA Ultima Interconnect Technology, Sunnyvale, CAView Profile Authors Info & Claims ASP-DAC '00: Proceedings of the 2000 Asia and South Pacific Design Automation ConferenceJanuary 2000 Pages 655–660https://doi.org/10.1145/368434.368862Online:28 January 2000Publication History 4citation102DownloadsMetricsTotal Citations4Total Downloads102Last 12 Months0Last 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 Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

An FPGA switch box is said to be hyper-universal if it is routable for all possible surrounding multi-pin net topologies satisfying the routing resource constraints. It is desirable to design hyper-universal switch boxes with the minimum number of switches. A previous work, Universal Switch Module, considered such a design problem concerning 2-pin net routings around a single FPGA switch box. However, as most nets are multi-pin nets in practice, it is imperative to study the problem that involves multi-pin nets. In this paper, we provide a new view of global routings and formulate the most general k-sided switch box design problem into an optimum k-partite graph design problem. Applying a powerful decomposition theorem of global routings, we prove that, for a fixed k, the number of switches in an optimum k-sided switch box with W terminals on each side is O (W), by constructing some hyper-universal switch boxes with O(W) switches. Furthermore, we obtain optimum, hyper-universal 2-sided and 3-sided switch boxes, and propose hyper-universal 4-sided switch boxes with less than 6.7 W switches, which is very close to the lower bound 6 W obtained for pure 2-pin net models.

In this paper, we analyze the basic properties of some Boolean function classes and propose a low complexity OBDD variable ordering algorithm, which is exact (optimum) to some classes of functions and very effective to general two-level form functions. We show that the class of series-parallel functions, which can be expressed by a factored form where each variable appears exactly once, can yield exact OBDD variable orderings in polynomial time. We also study the thin Boolean functions whose corresponding OBDDs can be represented by the form of thin OBDDs in which the number of nonterminal nodes is equal to the number of input variables. We show,that a thin Boolean function always has an essential prime cube cover and the class of series-parallel functions is a proper subset of thin Boolean functions. We propose a heuristic viewing OBDDs as evaluation machines with function cube covers as their inputs and apply a queuing principle in the algorithm design. Our heuristic, the augmented Dynamic Shortest Cube First algorithm, is proven to be optimum for the series-parallel functions and also be very effective for general two-level form functions. Experimental results on a large number of two-level form benchmark circuits show that the algorithm yields an OBDD total size reduction of over 51 percent with only 7 percent CPU time compared to the well-known network-based Fan-in Heuristic implemented in the SIS package. Comparing to the known exact results, ours is only 49 percent larger in size while only uses 0.001 percent CPU time.

In this paper, the natures of random and pseudo-random input sequences and their influence on permanent and intermittent fault detecting are analyzed. The aliasing fault coverage between the pseudo-random and random sequences is estimated. The activity probability features of the intermittent faults are considered. The self-test circuits of the intermittent faults are illustrated. The experimental results based on real circuits are obtained through simulation. The mathematical analysis and experimental results show that the quality of the pseudo-random testing is better than that of the random testing for permanent and intermittent faults. The Markov chain models are used in obtaining the input sequence length needed for determining if a circuit fault is intermittent or permanent.

For the FPGA Greedy Routing Architectures (GRAs), the optimal mapping problem of the entire chip can be decomposed into a sequence of three kinds of optimal m-side predetermined 4-way FPGA mapping problems, where m could be 1, 2, or 3. In this paper, we formulate the graph models of such sub-routing problems and investigate their minimum structures. The results give the lower bounds of routing resources in achieving all such kinds of GRAs and the theoretic models developed could be useful to studies on other FPGA routing problems as well.

This paper investigates the optimum OBDD representation problem based on two classes of Boolean functions. The first class is defined by OBDDs, in which the number of non-terminal nodes is equal to the number of input variables. We refer to such OBDDs and their corresponding Boolean functions as thin OBDDs and thin Boolean functions. The second class is the thin factored Boolean functions, which is defined by factored forms with each variable appearing exactly once. Many interesting properties of these two classes of functions are presented. Based on which, a revised dynamic shortest cube first OBDD variable ordering algorithm is developed. This algorithm is shown to be optimum for thin factored Boolean functions.

This paper presents a new test architecture, called Tree-LFSR/SR, to more effectively generate pseudo-exhaustive test patterns for combinational VLSI circuits. Instead of using a single scan chain, the proposed test architecture routes a scan tree driven by the LFSR to generate all possible input patterns for each output cone. The new test architecture is able to take advantages of both signal sharing and signal reuse. The benefits are: (1) the hardware overhead can be greatly reduced by saving routing area and XOR circuits, and (2) the difficulty of test architecture synthesis can be eased by accelerating the searching process of appropriate residues. The Tree-LFSR/SR configuration is then extended, if necessary, by adding XOR networks to deal with more complex input-output relations. An efficient method to directly synthesize the XOR network is also included. Experimental results obtained by simulating combinational benchmark circuits are very encouraging.

It has been observed experimentally that the mapping of global to detailed routing in a conventional FPGA routing architecture (2D array) yields unpredictable results. A different class of FPGA structures called greedy routing architectures (GRAs), where a locally optimal switch box routing can be extended to an optimal entire-chip routing, were investigated by Wu et al. (1994), Takashima et al. (1996) and Wu et al. (1996). It was shown that GRAs have good mapping properties. An H-tree GRA with W/sup 2/+2W switches per switch box (SpSB) and a 2D array GRA with 4W/sup 2/+2W SpSB were proposed by those authors (W is the number of tracks in each switch box). We continue this work by introducing an H-tree GRA with W/sup 2//2+2W SpSB and a 2D array GRA with 3.5 W/sup 2/+2 W SpSB. These new GRAs have the same good mapping properties but use fewer switches. We also show a class of FPGA architectures in which the mapping problem remains NP-complete, even with 6(W-1)/sup 2/+6W/sup 2/ SpSB (this is close to the maximum number of SpSB, which is 6W/sup 2/). Thus, more switches do not necessarily result in more routability.

In this paper, the routing problem for two-dimensional (2-D) field programmable gate arrays of a Xilinx-like architecture is studied. We first propose an efficient one-step router that makes use of the main characteristics of the architecture. Then we propose an improved approach of coupling two greedy heuristics designed to avoid an undesired decaying effect, a dramatically degenerated router performance on the near completion stages. This phenomenon is commonly observed on results produced by the conventional deterministic routing strategies using a single optimization cost function. Consequently, our results are significantly improved on both the number of routing tracks and routing segments by just applying low-complexity algorithms. On the tested MCNC and industrial benchmarks, the total number of tracks used by the best known two-step global/detailed router is 28% more than that used by our proposed method.

In this paper, we study the two-dimensional FPGA, Xilinx-like routing architectures and present the first known computational complexity results for them. The routing problem is formulated as a two-dimensional interval packing problem and is proved to be NP-complete with or without doglegs. Next, we consider other routing structures obtained from the industrial one by arbitrarily changing switch box connection topology while maintaining the same connection flexibility. There is an exponentially large number of such routing structures. We further prove that there does not exist a better routing architecture among the members of this large domain. In addition, we prove that there is no constant bound on the mapping ratio of a track number required by a detailed routing to a global routing channel density for the studied architectures. Finally, we show two directions of changing the routing architectures which yield polynomial time mapping solutions and constant bounded mapping ratios. Our theoretical analysis is intended to give some insight to, and understanding of this new routing problem's fundamental properties.

No abstract available.

We propose a novel optimization scheme that can improve the routing by reducing a newly observed router decaying effect.A pair of greedy-grow algorithms, each emphasizing a different optimization target are designed.By applying one algorithm first and then switching to the other when the first one approaches its decaying stage, the undesired effect can be significantly reduced and thus better results are produced.On the tested MCNC and industry benchmarks, in addition to our very low segment consumption the total number of tracks used by our scheme is 37% less than a published conventional maze router and 22% less than the best known 2-step global/detailed router [4,5].Our results show that complicated multi-objective problems could be effectively attacked by coupling low complexity algorithms that traverse the solution space in orthogonal directions.This idea is applicable on both algorithmic and architectural optimization approaches [7].

In this paper, we consider the problem of mapping a given global route to a detailed route for two dimensional homogeneous FPGAs. It has been shown that this problem is NP-complete on a popular Xilinx-4000-like routing architecture. Here, we further prove that this problem remains NP-complete for an arbitrary fixed switch box topology of the same connection flexibility, with or without doglegs allowed in detailed routes.>