Boolean Matching problem determines whether two Boolean functions are functionally equivalent under the permutation and negation of inputs and outputs. Prior contest [1] has extended the problem to allow inputs binding with constant value and the ports matching can be one-to-many projection. In this contest, we further extended the problem to consider the ports grouping information, which is caused by the buses or datapaths in the modern digital IC design.

Functional ECO is an essential solution in the VLSI design flow. The technique is to realize the functional changes with a minimal patch netlist in the gate-level netlist. As the increasing of the design complexity, functional ECO becomes more and more difficult to generate a minimal patch. ICCAD 2021 CAD contest calls for a feasible and efficient ECO algorithm with behavioral change guidance. More than ordinary functional ECO problems, the RTL designs are provided. Contestants can utilize the behavioral change in RTL designs to minimize the patch for G1.

Equivalence checking is the practical industrial solution to sign-off digital functionality for large-scale circuits. However, when design contains implicit and explicit X-values, the complexity of equivalence checking increases and heuristics used in binary-value equivalence checking may not be applicable for X-value equivalence checking. The goal of the ICCAD 2020 CAD contest is to ask the good algorithm and heuristic to solve the X-value equivalence checking. In this contest, we provide the benchmark suites for contestant to evaluate their program. We hope the contest result can improve industry applications and bring more research interests.

Using sampling patterns is always a powerful method to save efforts for the problems with large input space since it can quickly help identify cases' properties. The meaning behind these sampling results can be informative and useful, but these results may be unreadable to humans. Therefore, in 2019 CAD Contest [1], we formulate a problem of “logic regression on high dimensional Boolean space”. Given a blackboxed input-output relation generator, contestants are required to find a minimal Boolean logic circuit which matches the input-output relations of the given generator. In this contest, we provide benchmarks that address industrial applications of logic regression with several scenarios and different scales of input space to evaluate contestants' algorithms. We expect that the contest results can help industrial application and attract interesting academic research.

With a functional Engineering Change Order (ECO) problem, the quality of patch plays an important role in the performance of the patched circuit. In this contest, contestants need to generate patch functions that will make two circuits equivalent, while minimizing the resource cost of the generated patches. Resource cost is the comprehensive physical cost of all the patches, and minimizing the resource cost implies improving patch quality (timing, power, routing, or area). The resource cost of patches can be modeled as a weighting function with respect to several physical properties of nodes used for patches. In ICCAD 2017 CAD Contest, we have assigned each internal node a reasonable constant weight to represent the corresponding physical cost if the node is used for generating patches. Also, the resource cost of the patches is calculated as the weight summation of patches' support nodes. This formulation can elegantly identify wanted algorithms for the resource-aware patch generation problem.

Boolean Matching is significant to industry applications, such as library binding, synthesis, engineer change order, and hardware Trojan detection. Instead of basic Boolean matching, Non-exact Projective NPNP Boolean Matching allows to match two designs by not only negating and permuting inputs/outputs but also merging them or binding constants to inputs. Besides, the matching goal is extended to achieve the largest number of output equivalences between two designs. This kind of Boolean matching may get better quality in the related applications due to more flexibility and scalability, and the development of its algorithms is more challengeable. Hence, this problem has some research values. In ICCAD 2016 CAD contest, given two designs, participants need to decide how to permute, negate and merge designs' inputs/outputs or bind constants for achieving largest number of output equivalences. The score will be evaluated by how many outputs are equivalent and the runtime. We expect the contest result can improve industry applications and bring more research interests.

Sequential clock-gating can lead to easier equivalence checking problems, compared to the general sequential equivalence checking (SEC) problem. Modern sequential clock-gating techniques introduce control structures to disable unnecessary clocking. This violates combinational equivalence but maintains sequential equivalence between the original and revised circuits. We propose the use of characteristic graphs (CGs) to extract essential LTL clock-gating properties, which when proved imply certain sequential redundancies. The extraction, proof and subsequent removal of the implied redundancies lead to an efficient SEC procedure for clock-gated circuits. Experiments show that the proposed SEC procedure substantially outperforms existing methods in terms of speed and scalability when applied to several difficult cases.

Equivalence checking (EC) and functional Engineering Change Order (ECO) on large-scale designs becomes a crucial industrial topic as the design scale expands. In this topic, we are especially interested in how to partition the large-scale problems into smaller EC and ECO problem with lower complexity. In this contest, we ask the participants to design the algorithm to insert the corresponding cuts as the partitioned points on given two designs as simplifying the EC and ECO problems. The team correctly simplifying the problem most wins the contest. The benchmark suites are extracted from the real designs in our interesting applications. We look forward to triggering the academic area to investigate on this problem.

Efficiently solving numerous relevant circuit satisfiability (CircuitSAT) problems becomes a crucial industrial topic as the design scale expands. In this topic, we are especially interested in: how to select the best setting of the Boolean satisfiability (SAT) solver based on sample problems, and what is the most useful conjunctive normal form (CNF) encoding for some particular designs and particular applications. From practical experience, the run time yielded by solving SAT problems using the default setting is far from best run time; same is true for CNF encoding. In this contest, we ask the participants to design the algorithm for exploring the best setting based on some sample cases, and we determine the contest winners by evaluating the run time for solving the remaining problems. The benchmark suites are extracted from the real designs in our applications of interest. We look forward to triggering the academic area in further investigating this problem.

As technology advances, there is an increasing need in the industrial domain for an algorithm that can map macro blocks. This type of algorithm would solve several front-end problems. For example, existing structural or functional algorithms cannot solve the challenge of mapping large-scale functions without boundary information. Fortunately, in practical problems, we only consider the target mapping functions that are the constructs of the datapath, and these macro blocks are easily recognized through their special arithmetic signatures. In this problem, the contestants need to design a mapping algorithm that recognizes macro blocks and replaces the mapped region with the macro blocks. Therefore, we can fairly evaluate the quality of the mapping algorithm as the size reduction of the revised netlist. Under our well-designed benchmarks, we will clearly differentiate the capability of proposed algorithms with several indexes. We look forward to triggering the academic area to investigate on this problem.

In this paper, an automatic functional Engineering Change Order (ECO) problem is proposed. The contestants need to implement programs to identify the logic difference of the old netlist and the newly synthesized netlist, which agrees with new specification. How the logic difference can be presented as patch and how we measure the patch quality is explained. The program that can find the minimal patch wins.

Constant-coefficient multipliers are fundamental components in digital signal processing and arithmetic-based systems. Their verification, however, remains difficult and time-consuming. This is caused by the inability to identify the partial products from the number representation system of the constant. In this paper, we introduce an efficient number representation system as an observation on how modern synthesizers interpret constants. We also propose a robust and efficient partial product identification algorithm to improve the verification process. Experimental results show that our algorithm not only reduces the number of failing cases of the verification to one third but also speeds up the verification process by at least an average of 25%.

This paper is the first to combine the joint module-selection and retiming problem with the use of carry-save representation in the optimization of a synchronous circuit. To solve this problem efficiently, we first create a mixed-representation data-flow graph (MFG) by inserting signal representation conversion vertices into the data-flow graph, thus allowing carry-save representation to be freely selected for use. We then identify key properties of an optimal implementation of the MFG that consider the different signal representations as well as the sharing of registers and adders. These properties enable us to formulate the problem as a mixed-integer linear programming problem with cost functions that accurately reflect the true implementation costs of the circuit. Our algorithm, by allowing carry-save representation, can produce a wider range of solutions. In our experiments, our fastest implementation is 27% faster and our smallest implementation is 27% smaller, in comparison with solutions obtained using the previously known joint module-selection and retiming technique.

Advances of very large scale integration technologies present two challenges for routing problems: (1) the higher integration of transistors due to shrinking of featuring size and (2) the requirement for off-grid routing due to the variable-width variable-spacing design rules imposed by optimization techniques. In this paper, we present a multilayer gridless detailed routing system for deep submicrometer physical designs. Our detailed routing system uses a hybrid approach consisting of two parts: (1) an efficient variable-width variable-spacing detailed routing engine and (2) a wire-planning algorithm providing high-level guidance as well as ripup and reroute capabilities. Our gridless routing engine is based on an efficient point-to-point gridless routing algorithm using an implicit representation of a nonuniform grid graph. We proved that such a graph guarantees a gridless connection of the minimum cost in multilayer variable-width and variable-spacing routing problem. A novel data structure using a two-level slit tree plus interval tree in combination of cache structure is developed to support efficient queries into the connection graph. Our experiments show that this data structure is very efficient in memory usage while very fast in answering maze expansion related queries. Our detailed routing system also features a coarse grid-based wire-planning algorithm that uses exact gridless design rules (variable-width and variable-spacing) to accurately estimate the routing resources and distribute nets into routing regions. The wire-planning method also enables efficient ripup and reroute in gridless routing. Unlike previous approaches for gridless routing that explore alternatives of blocked nets by gradually tightening the design rules, our planning-based approach can take the exact gridless rules and resolve the congestion and blockage at a higher level. Our experimental results show that using the wire-planning algorithm in our detailed routing system can improve the routability and also speed up the runtime by 3 to 17 times.

Joint module selection and retiming is a powerful technique to optimize the implementation cost and the speed of a circuit specified using a synchronous data-flow graph (DFG). In implementing high-speed circuits, the use of carry-save signal representation is also a powerful technique to optimize the implementation cost and the speed of arithmetic circuits. This paper is the first to combine these two techniques to solve the joint module selection and retiming problem while allowing the use of carry-save representation. To solve this problem efficiently, we first propose a mixed-representation data-flow graph (MFG) that allows signals to be expressed in carry-save representation. We also propose techniques to accurately model the costs associated with different signal representations. In addition, we propose a solution-space pruning technique that significantly reduces the run-time of our algorithm. Our algorithm, by allowing carry-save representation, can produce a wider range of solutions. In our experiments, our fastest implementation is 28% faster and our smallest implementation is 47% smaller, in comparison to solutions obtained using the previously known joint module selection and retiming technique.

Article Free Access Share on DUNE: a multi-layer gridless routing system with wire planning Authors: Jason Cong UCLA Computer Science Dept, Los Angeles, CA UCLA Computer Science Dept, Los Angeles, CAView Profile , Jie Fang UCLA Computer Science Dept, Los Angeles, CA UCLA Computer Science Dept, Los Angeles, CAView Profile , Kei-Yong Khoo Synopsys Corp, Mountain View, CA Synopsys Corp, Mountain View, CAView Profile Authors Info & Claims ISPD '00: Proceedings of the 2000 international symposium on Physical designMay 2000 Pages 12–18https://doi.org/10.1145/332357.332367Published:01 May 2000Publication History 28citation484DownloadsMetricsTotal Citations28Total Downloads484Last 12 Months27Last 6 weeks7 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

Maze routing algorithms are widely used for finding an optimal path in detailed routing for very large scale integration, printed circuit board and multichip modules. In this paper, we show that finding an optimal route of a two-pin net in a multilayer routing environment under practical via design rules can be surprisingly difficult. A straightforward extension to the maze routing algorithm that disallows via-rule incorrect routes may either cause a suboptimal route to be found, or more seriously, cause the failure to find any route even if one exists. We present a refined heuristic to this problem by embedding the distance to the most recently placed via in an extended connection graph so that the maze routing algorithm has a higher chance of finding a via-rule correct optimum path in the extended connection graph. We further present efficient data-structures to implement the maze routing algorithm without the need to preconstruct the extended connection graph. Experimental results confirmed the usefulness of our algorithm and its applicability to a wide range of CMOS technologies.

ECO routing is a very important design capability in advanced IC, MCM and PCB designs when additional routings need to be made at the latter stage of the physical design. ECO is difficult in two aspects: first, there are a large number of existing interconnects which become obstacles in the region. A hierarchical approach is not applicable in this situation, and we need to search a large, congested region thoroughly. Second, advances in circuit designs require variable width and variable spacing on interconnects. Thus, a gridless routing algorithm is needed. We propose to use an implicit representation of a non-uniform grid graph for a gridless maze routing algorithm. A novel slit-tree plus interval-tree data structure is developed, combined with a cache structure, to support efficient queries into the connection graph. Our experiments show that this data structure is very small in memory usage while very fast in answering maze expansion related queries. This makes the framework very useful in the ECO type of routing.

Addresses the bit-level optimization of carry-save adder (CSA) arrays when the operands are of unequal wordlength (such as in some datapaths in digital signal processing circuits). We first show that by relaxing the carry-save representation to allow for more than two signals per bit position, we gain flexibility in the bit-level implementation of CSA arrays that can be exploited to achieve a more efficient design. We then propose algorithms to optimize a single adder array at the bit-level. In addition, we proposed a heuristic to optimize a series of adder arrays that might occur in a datapath. We have applied our algorithms to the optimization of high-speed digital FIR filters and have achieved 15% to 30% savings (weighted cost) in the overall filter implementation array in comparison to the standard carry-save implementation.

Maze routing algorithms are widely used for finding an optimal path in detailed routing for VLSI, PCB and MCMs.In this paper, we show that finding an optimal route of a two-pin net in a multi-layer routing environment under practical via design rules can be surprisely difficult.Furthermore, a straightforward extension to the maze routing algorithm that disallows via-rule incorrect routes may either cause a suboptimal route to be found, or more seriously, cause the failure to find any route even if one exists.We present a refined heuristic to this problem by embedding the distance to the most recently placed via in an extended connection graph so that the maze routing algorithm has a higher chance of finding a via-rule correct optimum path in the extended connection graph.We further present efficient data-structures to implement the maze routing algorithm without the need to preconstruct the extended connection graph.Experimental results confirmed the usefulness of our algorithm and its applicability to a wide range of CMOS technologies.

A new logic-timing simulation algorithm, applicable to cycle-based simulation of acyclic combinational logic blocks or synchronous logic designs, is described and implemented. The algorithm is based on evaluating ordered sequences of events, called event-streams, instead of individual events as in a traditional event-driven simulator. This allows very efficient gate evaluations using states unrolling and look-ahead processing. When processing long event-streams, the performance of our simulator can approach that of a compiled-code simulator without the poor instruction-cache behavior of large compiled-code simulations. In addition, the simulator can perform multi-cycle simulations that result in longer event-streams, which enhances the efficiency of gate evaluations. Experimental results show that our simulator runs about four times faster than the Verilog-XL simulator.

An improved algorithm is presented for designing digital filters with coefficients expressed as sums of signed power-of-two (SPT) terms. Our algorithm allocates SPT terms based on minimizing the filter's approximating error using two l/sup /spl infin// norms, one in the time domain and one in the frequency domain. For any specified filter gain, the time complexity of the algorithm is a second-order polynomial in the filter order. Examples show that our improved algorithm is capable of designing filters with better characteristics while using fewer SPT terms.

In this paper, we present an efficient multilayer general area router, named V4R, for MCM and dense PCB designs. One unique feature of the V4R router is that it uses no more than four interconnection vias to route every net and yet produces high quality routing solutions. Another unique feature of the V4R router is it combines global routing and detailed routing in one step and produces high quality detailed routing solutions directly from the given netlist and module placement. Several combinatorial optimization techniques, including efficient algorithms for computing a maximum weighted k-cofamily in a partially ordered set and a maximum weighted noncrossing matching in a bipartite graph, are used to solve the combined problem efficiently. As a result, the V4R router is independent of net ordering, runs much faster, and uses far less memory compared to other multilayer general area routers. We tested our router on several examples, including three industrial MCM designs from MCC. Compared with the 3-D maze router, on average the V4R router uses 44% fewer vias, 2% less wirelength, and runs 26 times faster. Compared with the SLICE router, on average the V4R router uses 9% fewer vias, 4% less wirelength, and runs 3.5 times faster. The V4R also uses fewer routing layers compared to the 3-D maze router and the SLICE router.>

Modern high speed CMOS processors using on-chip phase-locked-loops often require a clock buffer with stringent specifications on the signal's rise time and fall time rather than on the buffer's delay time. For these applications, we propose a low power CMOS clock buffer that momentarily tri-states its output to minimize its power dissipation and its area requirement below those that are achievable by the traditional tapered CMOS buffers.>

... area router, named V4R, for MCM and dense PCB designs. It uses no more than four vias to route every net and yet produces high quality routing solutions. It combines global routing and detailed routing in one step and produces high quality detailed routing solutions directly from the given netlist and module placement. As a result, V4R is independent of net ordering, runs much faster, and uses far less memory compared to other multilayer general area routers. Experimental results show that V4R outperforms both the 3D maze router and the SLICE router significantly.

A near-optimal algorithm for the channel pin assignment problem is presented. This algorithm, called the alternative packing algorithm, can always produce an assignment solution whose density is at most one more than the density of an optimal solution, i.e., d(S)>