Search

Chip planning deals with large modules such as caches, embedded memories, and intellectual property (IP) cores that have known areas, fixed or changeable shapes, and possibly fixed locations. When modules are not clearly specified, chip planning relies on netlist partitioning (Chap. 2) to identify such modules in large designs. Assigning shapes and locations to circuit modules during chip planning produces blocks, and enables early estimates of interconnect length, circuit delay and chip performance. Such early analysis can identify modules that need improvement. Chip planning consists of three major stages (1) floorplanning, (2) pin assignment, and (3) power planning. [ABSTRACT FROM AUTHOR]

The layout of an integrated circuit (IC) must not only satisfy geometric requirements, e.g., non-overlapping cells and routability, but also meet the design΄s timing constraints, e.g., setup (long-path) and hold (short-path) constraints. The optimization process that meets these requirements and constraints is often called timing closure. It integrates point optimizations discussed in previous chapters, such as placement (Chap. 4) and routing (Chaps. 5–7), with specialized methods to improve circuit performance. [ABSTRACT FROM AUTHOR]

Recall from Chap. 5 that the layout region is represented by a coarse grid consisting of global routing cells (gcells) or more general routing regions (channels, switchboxes) during global routing. Afterward, each net undergoes detailed routing. [ABSTRACT FROM AUTHOR]

After partitioning the circuit into smaller modules and floorplanning the layout to determine block outlines and pin locations, placement seeks to determine the locations of standard cells or logic elements within each block while addressing optimization objectives, e.g., minimizing the total length of connections between elements. Specifically, global placement (Sec. 4.3) assigns general locations to movable objects, while detailed placement (Sec. 4.4) refines object locations to legal cell sites and enforces nonoverlapping constraints. The detailed locations enable more accurate estimates of circuit delay for the purpose of timing optimization. [ABSTRACT FROM AUTHOR]

For signal wires in digital integrated circuits, global routing (Chap. 5) is performed first, and detailed routing next (Chap. 6). However, some types of designs, such as analog circuits and printed circuit boards (PCBs) with gridless (trackless) routing, do not warrant this distinction. Smaller, older designs with only one or two metal layers also fall into this category. When global and detailed routing are not performed separately, area routing (Secs. 7.1–7.2) directly constructs metal routes for signal connections. Unlike routing with multiple metal layers, area routing emphasizes crossing minimization. Non-Manhattan routing is discussed in Sec. 7.3, and nets that require special treatment, such as clock signals, are discussed in Secs. 7.4–7.5. [ABSTRACT FROM AUTHOR]

The design complexity of modern integrated circuits has reached unprecedented scale, making full-chip layout, FPGA-based emulation and other important tasks increasingly difficult. A common strategy is to partition or divide the design into smaller portions, each of which can be processed with some degree of independence and parallelism. A divide-and-conquer strategy for chip design can be implemented by laying out each block individually and reassembling the results as geometric partitions. Historically, this strategy was used for manual partitioning, but became infeasible for large netlists. Instead, manual partitioning can be performed in the context of system-level modules by viewing them as single entities, in cases where hierarchical information is available. In contrast, automated netlist partitioning (Secs. 2.1–2.4) can handle large netlists and can redefine a physical hierarchy of an electronic system, ranging from boards to chips and from chips to blocks. Traditional netlist partitioning can be extended to multilevel partitioning (Sec. 2.5), which can be used to handle large-scale circuits and system partitioning on FPGAs (Sec. 2.6). [ABSTRACT FROM AUTHOR]

During global routing, pins with the same electric potential are connected using wire segments. Specifically, after placement (Chap. 4), the layout area is represented as routing regions (Sec. 5.4) and all nets in the netlist are routed in a systematic manner (Sec. 5.5). To minimize total routed length, or optimize other objectives (Sec. 5.3), the route of each net should be short (Sec. 5.6). However, these routes often compete for the same set of limited resources. Such conflicts can be resolved by concurrent routing of all nets (Sec. 5.7), e.g., integer linear programming (ILP), or by sequential routing techniques, e.g., rip-up and reroute. Several algorithmic techniques enable scalability of modern global routers (Sec. 5.8). [ABSTRACT FROM AUTHOR]

The design and optimization of integrated circuits (ICs) are essential to the production of new semiconductor chips. Modern chip design has become so complex that it is largely performed by specialized software, which is frequently updated to reflect improvements in semiconductor technologies and increasing design complexities. A user of this software needs a high-level understanding of the implemented algorithms. On the other hand, a developer of this software must have a strong computerscience background, including a keen understanding of how various algorithms operate and interact, and what their performance bottlenecks are. [ABSTRACT FROM AUTHOR]

The past few years have seen significant progress in algorithms and heuristics for both SAT and symmetry detection. Additionally, the thesis that some of SAT΄s intractability can be explained by the presence of symmetry, and that it can be addressed by the introduction of symmetry-breaking constraints, was tested, albeit only to a rather limited extent. In this paper we explore further connections between symmetry and satisfiability and demonstrate the existence of intractable SAT instances that exhibit few or no symmetries. Specifically, we describe a highly scalable symmetry detection algorithm based on a decision tree that combines elements of group-theoretic computation and SAT-inspired backtracking search, and provide results of its application on the SAT 2009 competition benchmarks. For SAT instances with significant symmetry we also compare SAT runtimes with and without the addition of symmetry-breaking constraints. [ABSTRACT FROM AUTHOR]

In this chapter, we describe the robust and scalable academic placement tool Capo. Capo uses the min-cut placement paradigm and performs (a) scalable multiway partitioning, (b) routable standard-cell placement, (c) integrated mixed-size placement, (d) wire length-driven fixed-outline floorplanning as well as (e) incremental placement. [ABSTRACT FROM AUTHOR]

We introduce a framework for studying and solving a class of CSP formulations. The framework allows constraints to be expressed as linear and non-linear equations, then compiles them into SAT instances via Boolean logic circuits. While in general reduction to SAT may lead to the loss of structure, we specifically detect several types of structure in high-level input and use them in compilation. Linearity is preserved by the use of pseudo-Boolean (PB) constraints in conjunction with a 0-1 ILP solver that extends common SAT-solving techniques. Symmetries are detected in high-level constraints by solving the graph automorphism problem on parse trees. Symmetry-breaking predicates are added during compilation. Our system generalizes earlier work on symmetries in SAT and 0-1 ILP problems. Empirical evaluation is performed on instances of the social golfers and Hamming code generation problems. We show substantial speedups with symmetry-breaking, especially on unsatisfiable instances. In general, our runtimes with the specialized 0-1 ILP solver Pueblo are competitive with results recently reported for ILOG Solver. [ABSTRACT FROM AUTHOR]