Detailed routing is one of the most challenging aspects of the physical design process. Many of the violations that occur during the detailed routing stage stem from the placement of the cells. In this paper, we propose a deep learning framework to identify short violations that can occur during detailed routing from a placed netlist. One of the advantages of our technique is that by using the proposed deep learning-based predictor, global routing is no longer required as frequently and hence the total runtime for place and route can be significantly reduced. In this paper, we discuss the proposed framework and the methodology for analyzing the extracted features. The experimental results show that the average sensitivity, specificity, and accuracy of Eh?Predictor is above 90%. In addition, we show that Eh?Predictor is up to 14 times faster than NCTUgr for smaller designs and up to 96 times faster for larger designs.

Modern analytic placement tools are commonly built around the idea of iterative Lower Bound (LB) and Upper Bound (UB) placement. The LB step optimizes wirelength and timing while ignoring overlap and cell-type constraints, whereas the UB step attempts to spread cells and satisfy constraints without harming design quality. Top-down geometric partitioning techniques have traditionally been used to spread cells during UB placement. We propose a new, network flow-based approach for UB placement which does a better job of preserving quality by optimizing the displacement of cells from their LB positions. Our approach not only addresses cell overlap, but also accommodates complex region constraints and simultaneously spreads unit-sized logic, carry chains, and blocks like RAMs and DSPs. Our technique is scalable, does not require geometric partitioning, and is suitable for both flat and clustered placement flows.We deployed our algorithm in a commercial FPGA CAD flow, and show that it reduces HPWL by 6.4% on average (up to 22.8% in the best case) while improving worst-slack timing in over 90% of designs, compared to a state-of-the-art alternative.

Detecting and preventing routing violations has become a critical issue in physical design, especially in the early stages. Lack of correlation between global and detailed routing congestion estimations and the long runtime required to frequently consult a global router adds to the problem. In this paper, we propose a machine learning framework to predict detailed routing short violations from a placed netlist. Factors contributing to routing violations are determined and a supervised neural network model is implemented to detect these violations. Experimental results show that the proposed method is able to predict on average 90% of the shorts with only 7% false alarms and considerably reduced computational time.

The legalization step is performed after global placement where wire length and routability are optimized or during timing optimization where buffer insertion or gate sizing are applied to meet timing requirements. Therefore, an ideal legalization approach must preserve the quality of the input placement in terms of routability, wire length, and timing constraints. These requirements indirectly impose maximum and average cell movement constraints during legalization. In addition, the legalization step should effectively manage white space availability with a highly efficient runtime in order to be used in an iterative process such as timing optimization. In this article, a robust and fast legalization method called Eh?Legalizer for standard-cell placement is presented. Eh?Legalizer legalizes input placements while minimizing the maximum and average cell movements using a highly efficient novel network flow-based approach. In contrast to the traditional network flow-based legalizers, areas with high cell utilizations are effectively legalized by finding several candidate paths and there is no need for a post-process step. The experimental results conducted on several benchmarks show that Eh?Legalizer results in 2.5 times and 3.3 times less the maximum and average cell movement, respectively, while its runtime is significantly (18×) lower compared to traditional legalizers. In addition, the experimental results illustrate the scalability and robustness of Eh?Legalizer with respect to the floorplan complexity. Finally, the detailed-routing results show detailed-routing violations are reduced on average by 23% when Eh?Legalizer is used to generate legal solutions.

An increasing number of multi-deck cells occupying multiple rows (e.g. multi-bit registers) are used in advanced node technologies to achieve low power and high performance. The multi-deck standard cell legalization not only should remove all overlaps between cells but also should satisfy delicate and complicated design rules with preserving the quality of the given placement by applying the minimal perturbation. In addition, the process must be fast and robust to handle the sheer number of cells in the state-of-the-art designs. For this purpose, we have defined an evaluation metric based on maximum, average cell movements, and Half Perimeter Wire Length (HPWL) as well as runtime of the legalization algorithm. In addition, we have introduced a set of benchmarks that include multi-deck cells with a range of heights (1-4 row heights).

The standard-cell placement legalization problem has become critical due to increasing design rule complexity and design utilization at 16nm and lower technology nodes. An ideal legalization approach should preserve the quality of the input placement in terms of routability and timing, as well as effectively manage white space availability and have low runtime. In this work, we present a robust legalization algorithm for standard cell placement that minimizes maximum cell movements fast and effectively based on a novel network-flow approach. The idea is inspired by path augmentation but with important differences. In contrast to the classical path augmentation approaches, we resolve bin overflows by finding several candidate paths that guarantee realizable (legal) flow solutions. In addition, we show how the proposed algorithm can be seamlessly extended to handle relevant cell edge spacing design rules. Our experimental results on the ISPD 2014 benchmarks illustrate that our proposed method yields 2.5x and 3.3x less maximum and average cell movement, respectively, and the runtime is significantly (18x) lower compared to best-in-class academic legalizers.

The placement problem has become more complex and challenging due to a wide variety of complicated constraints imposed by modern process technologies. Some of the most challenging constraints and objectives were highlighted during the most recent ACM/IEEE International Symposium on Physical Design (ISPD) contests. In this article, the framework of Eh?Placer and its developed algorithms are elaborated, with the main focus on modern technology constraints and runtime. The technology constraints considered as part of Eh?Placer are fence region, target density, and detailed routability constraints. We present a complete description on how these constraints are considered in different stages of Eh?Placer. The results obtained from the contests indicate that Eh?Placer is able to efficiently handle modern technology constraints and ranks highly among top academic placement tools.

We present a Discrete Cosine Transform (DCT) unit embedded with Error Detection Sequential (EDS) and Dynamic Voltage Scaling (DVS) circuits to speculatively monitor its noncritical datapaths. This monitoring strategy requires no buffer insertions with only minimal modifications to the existing digital design methodology and is therefore applicable for Field-Programmable Gate Array (FPGA) implementations. The proposed design is implemented in an FPGA. The duty cycles of the constraint clock and the actual clock are differentiated to guide the synthesizer to place the EDS circuits with specific timing margin. The proposed design is tested with two classic images and is able to detect timing errors in the noncritical datapaths due to dynamic process, voltage and temperature (PVT) variations. The DVS circuit correspondingly controls a linear voltage regulator to adjust the supply voltage to the Point of First Failure (PoFF). No actual timing errors are generated, primarily because of the unique speculative characteristic of the proposed monitoring strategy. Our proposed design incurs a 0.3% logic element overhead and 3.5% maximum frequency degradation. By lowering the supply voltage by 8.3%, the proposed design saves up to 16.5% energy when operating at the same frequency as a highly optimized baseline DCT implementation.

With a specified Mean Timing Between Failure (MTBF), the metastability resolution time of synchronizers possibly constrains the system performance. To enhance metastability resolution time under single low-voltage supply environments, Voltage-Boosted Synchronizers (VBSs) consisting of a basic minimum-sized Jamb latch and a switched-capacitor-based charge pump are proposed. The capacitor of the charge pump is sized 13 times the area of the Jamb latch. Two powering strategies of the charge pump, namely Metastability-driven VBS (MVBS) and Clock-driven VBS (CVBS), are proposed. For a 1-year MTBF specification, MVBS and CVBS show 2.0-2.7 and 5.1-9.8 times the performance improvement over the basic Jamb latch, respectively, without incurring large power consumption.

The placement problem has become challenging due to a variety of complicated constraints imposed by modern process technologies. Some of the most challenging constraints were highlighted during the ISPD 2015 placement contest and include fence region and target density constraints; these constraints are in addition to those issues that affect detailed routability such as pin shorts, pin access problems and cell spacing issues. These constraints not only make cell placement more difficult, but can impact the placement objectives such as wire length, routability and so forth. In this paper, we present a comprehensive technique to address fence region constraints in global placement and legalization while still considering detailed-routing issues. We combine concepts from image processing such as region coloring with parallel programming to efficiently deal with fence regions. We also introduce a heuristic method to adjust target densities while avoiding adverse effects on the quality of global routability. Numerical results using both the released and hidden benchmarks from the ISPD 2015 placement contest demonstrate the efficacy of our proposed techniques.

Circuit placement involves the arrangement of a large number of cells which must be aligned to sites in rows without overlap. Placement is done via a sequence of optimization steps which include global placement, legalization and detailed placement. Global placement determines a rough position for each cell throughout the chip while optimizing objectives such as wirelength and routability. The rough placement is legalized and cells are aligned to sites in rows without overlap. Detailed placement attempts to further improve the placement while keeping the placement feasible. In reality, the placement of cells is more complicated than aligning cells to sites without overlap; detailed routability issues compound the placement problem by introducing issues such as pin shorts, pin access problems, and other spacing requirements. The importance of addressing these issues were highlighted during the recent ISPD2014 placement contest [1]. In many cases, detailed routability issues can be addressed during placement to avoid later problems. We describe our ISPD2014 contest legalizer and detailed placer (plus additional extensions) that can address many detailed routing issues without negatively impacting the quality of the final placement. Numerical results are presented to demonstrate the effectiveness of our techniques.

Dynamic power management for multi-core system on chip (MPSoC) platforms has become an increasingly critical design problem. In this paper, we present EmPower, an FPGA based emulation, validation and prototyping framework for dynamic power management research targeted at MPSoC platforms. EmPower supports two advanced power management features -- per-core dynamic frequency scaling and clock gating, and power-aware thread migration. We also provide two fully-functional parallel applications for benchmarking -- video encoding and software-defined radio. Our experimental results indicate that EmPower provides up to 36 -- improvement in run-time compared to cycle-accurate software simulations, and enables accurate and efficient exploration of the design space of power management algorithms.

Dynamic power management for multi-core system on chip (MPSoC) platforms has become an increasingly critical design problem. In this paper, we present EmPower, an FPGA based rapid prototyping framework for dynamic power management algorithms targeted at MPSoC platforms. EmPower supports two advanced power management techniques (per-core dynamic frequency scaling and clock gating, and thread migration), enables software based expression of the power management algorithm, and provides on-chip power measurement capabilities. EmPower also includes two fully-functional parallel applications for benchmarking - video encoding and software-defined radio. We demonstrate the use of EmPower in rapid exploration of the large design space of power management algorithms using two illustrative case studies.

We reconsider guarded evaluation as a means to reduce FPGA dynamic power consumption. We augment and evaluate guarded evaluation as proposed in [1] after different stages of the FPGA CAD flow. Guarding later in the flow provides more feedback to the algorithm and yields a more effective cost-benefit analysis of newly added signals. Numerical results show that guarding later in the flow yields slightly less power savings versus guarding after technology mapping. However, fewer guards are inserted which results in fewer netlist changes and less impact on routing resource usage.

Guarded evaluation is a power reduction technique that involves identifying subcircuits (within a larger circuit) whose inputs can be held constant (guarded) at specific times during circuit operation, thereby reducing switching activity and lowering dynamic power. The concept is rooted in the property that under certain conditions, some signals within digital designs are not “observable” at design outputs, making the circuitry that generates such signals a candidate for guarding. Guarded evaluation has been demonstrated successfully for application-specific integrated circuits (ASICs); in this paper, we apply the technique to field-programmable gate arrays (FPGAs). In ASICs, guarded evaluation entails adding additional hardware to the design, increasing silicon area and cost. Here, we apply the technique in a way that imposes minimal area overhead by leveraging existing unused circuitry within the FPGA. The primary challenge in guarded evaluation is in determining the specific conditions under which a subcircuit's inputs can be held constant without impacting the larger circuit's functional correctness. We propose a simple solution to this problem based on discovering gating inputs using “noninverting” and “partial noninverting” paths in a circuit's AND-inverter graph representation. Experimental results show that guarded evaluation can reduce switching activity on average by as much as 32% and 25% for 6-input look-up table (6-LUT) and 4-LUT architectures, respectively. Dynamic power consumption in the FPGA interconnect is reduced on average by as much as 24% and 22% for 6-LUT and 4-LUT architectures, respectively. The impact to critical path delay ranges from 1% to 43%, depending on the guarding scenario and the desired power/delay tradeoff.

Technology mapping is an important step in the FPGA CAD flow in which a network of simple gates is converted into a network of logic blocks. This article considers enhancements to a traditional LUT-based mapping algorithm for an FPGA comprised of logic blocks which implement only a subset of functions of up to k variables; specifically, the logic block is a partial LUT, but it possesses more inputs than a typical LUT. An analysis of the logic block is presented, and techniques for postmapping area recovery and timing-driven buffer insertion are also described. Numerical results are put forth which substantiate the efficacy of the proposed methods using real circuits mapped to a commercial FPGA architecture.

The ability to efficiently match logic functions to structures of K-input look-up tables (K-LUTs) is a central problem in FPGA resynthesis algorithms. This paper addresses the problem of matching logic functions of ~ 9 to 12 inputs to K-LUT structures. Our method is based on the off-line generation of libraries of LUT structures. During resynthesis, matching is accomplished efficiently using NPN encoding and hash table look-ups. Generating an effective library of LUT structures may seem prohibitive due to the overwhelming number of logic functions which must be considered and represented in the library. We show that, by careful consideration of which logic functions and LUT structures to keep, it is possible to generate useful, compact libraries. We present numerical results demonstrating the effectiveness of our ideas when used during area-oriented resynthesis after FPGA technology mapping.

Technology mapping is an important step in the FPGA CAD flow in which a network of simple gates is converted into a network of logic blocks. We consider enhancements to a traditional LUT-based mapping algorithm for an FPGA comprised of logic blocks which implement only a subset of functions of up to k variables--specifically, the logic block is a partial LUT, but it possesses more inputs than typical LUTs. Numerical results are presented to demonstrate the efficacy of our proposed techniques using real circuits mapped to a commercial FPGA architecture.

Due to poor correlations between pre- and post-placement timing analysis, many post-placement optimization strategies have been proposed for the FPGA CAD flow to improve circuit performance. Typically, these methods depend on logic duplication or decomposition methods combine together with incremental placement.

Simulated annealing remains a widely used heuristic for field-programmable gate array placement due, in part, to its ability to produce high-quality placements while accommodating complex objective functions. This paper discusses enhancements to annealing-based placement which improve upon both quality and run-time. Specifically, intelligent strategies for selecting and placing cells are interspersed with traditional random moves during an anneal, allowing the annealer to converge more quickly and to attain better quality with less statistical variability. For thesameamountofcomputationaleffort, the contributions discussed in this paper consistently improve both critical path delay and wire length compared to traditional annealing perturbations.

This paper considers the implementation of an annealing technique for dynamic power reduction in FPGAs. The proposed method comprises a power-aware objective function for placement and is implemented in a commercial tool. In particular, a capacitance model based on multi-dimensional nonlinear regression is described, as well as a new capacitance model for global nets. The importance and advantages of these models are highlighted in terms of the overall attainable reduction in power in a real, commercially-available architecture and tool flow. The results are quantified across a range of industrial benchmarks targeting the ActelregIGLOOtradeFPGA architecture. Power measurements show that, across a suite of 120 industrial designs, the technique described in this paper reduces dynamic power by 13% on average, with only a 1% degradation in timing performance.

The traditional approach to FPGA packing and CLB-level placement has been shown to yield significantly worse quality than approaches which allow BLEs to move during placement. In practice, however, modern FPGA architectures require expensive DRC checks which can render full BLE-level placement impractical. We address this problem by proposing a novel clustering framework that uses physical information to produce better initial packings which can, in turn, reduce the amount of BLE-level placement that is required. We quantify our packing technique across accepted benchmarks and show that it produces results with 16% less wire length, 19% smaller minimum channel widths, and 8% less critical path delay, on average, than leading methods.

Simulated annealing remains a widely-used heuristic for FPGA placement due, in part, to its ability to produce high-quality placements while accommodating complex objective functions and architectural constraints. In this work, we investigate the concept of "directed moves" during annealing as a means of improving upon the quality and run-time of the technique. We intersperse "intelligent" strategies for selecting and placing cells along with traditional, random moves during an anneal. This allows our annealer to converge more quickly and to attain better-quality placements with less statistical variability. Our results confirm that, for the same amount of computational effort, directed moves achieve 5% and 10% improvement in critical path delay and wire length, respectively, compared to traditional annealing perturbations.

We describe an efficient, top-down strategy for overlap removal and floorplan repair which repairs overlaps in floorplans produced by placement algorithms or rough floorplanning methodologies. The algorithmic framework that we propose incorporates a novel geometric shifting technique within a top-down flow. The effect of our algorithm is quantified across a broad range of floorplans produced by multiple tools. Our method succeeds in producing valid placements in almost all cases; moreover, compared to leading methods, it requires only one fifth the run-time and produces placements with 4 to 13% less HPWL and up to 43% less cell movement.

The complexity and size of digital circuits have grown exponentially, and today's circuits can contain millions of logic elements. Clustering algorithms have become popular due to their ability to reduce circuit sizes, so that the circuit layout can be performed faster and with higher quality. This paper presents a deterministic net-reduction-based clustering algorithm called Net Cluster. The basic idea of the proposed technique is to put the emphasis on reducing the number of nets versus the number of cells, thereby capturing the natural clusters of a circuit. The proposed algorithm has proven a linear-time complexity of O(p), where p is the number of pins in a circuit. To demonstrate the effectiveness of the proposed clustering technique, it has been applied to multilevel partitioning and wire length-driven placement. The numerical experiments on the ISPD98 benchmark suite for partitioning and the ICCAD 2004 benchmark suite for placement demonstrate that by applying Net Cluster as a preprocessing step, the performance of state-of-the-art multilevel partitioners and placers can be further improved

This paper describes the implementation of a wire length-driven force-directed placer named FDP for generic placement. Specifically, it describes efficient force computation for cell spreading, numerical instabilities during force-directed placement, a means to avoid instabilities, and metrics for proper assessment of cell distribution throughout the placement region. It demonstrates that one of the greatest impediments to achieving high-quality placements using a force-directed placer lies in the large amount of cell overlap present in initial placements. This overlap makes the determination of cell ordering difficult and can lead to the inadvertent separation of highly connected cells. It is shown that median improvement and multilevel clustering improve cell ordering and aid in wire length minimization. Numerical results are presented for both standard cell and mixed-size placement problems. For standard cell problems, the tool generates placements that are, on average, 3% better than Capo9.0, but 5% worse than FengShui2.6. For mixed-size problems, FDP generated placements that are, on average, 2%-5% better than Capo9.0 and -5%--2% better than Fengshui2.6, depending on the presence (or absence) of pin offsets. Run times for FDP are higher than both Capo9.0 and FengShu2.6, although reasonable

Vendor-provided softcore processors often support advanced features such as caching that work well in uniprocessor or uncoupled multiprocessor architectures. However, it is a challenge to implement symmetric multiprocessor on a programmable chip (SMPoPC) systems using such processors. This paper presents an implementation of a tightly coupled, cache-coherent symmetric multiprocessing architecture using a vendor-provided softcore processor. Experimental results show that this implementation can be achieved without invasive changes to the vendor-provided softcore processor and without degradation of the performance of the memory system.

One of the greatest impediments to achieving high quality placements using force-directed methods lies in the large amount of overlap initially present in these techniques. This overlap makes the determination of cell ordering difficult and can lead to the inadvertent separation of highly connected cells by the spreading forces. We show that a multi-level clustering strategy can minimize the ill effects of overlap and improve the quality of placements generated by the force-directed tool FDP. Moreover, we present a means of improving initial cell ordering through the unification of min-cut partitioning and force-based placement, and describe an enhanced median improvement heuristic which further aids in minimizing HPWL. Numerical results are presented showing that our flow generates placements which are, on average, 15% better than mPG and 4% better than Capo 9.0 on mixed-size designs.

We describe a remarkably simple yet very effective line search technique for cell placement. Our method "corrects" errors in force scaling by sampling different force weights in each iteration of placement and selecting the best candidate placements based on an objective function. Our technique is not only very fast, but it does away with the need for the ad hoc scaling that has plagued prior force-directed methods. We describe the implementation of our method within a multilevel flow and show that it can achieve good wire lengths with competitive run-times compared to other academic tools. Specifically, we produce placements with 12% and 15% better HPWL than FengShui 5.0 and Capo 9.1, respectively, on the ICCAD04 mixed-size benchmarks, while presenting run-times that are 37% faster than Capo 9.1.

Analytic placement methods that simultaneously minimize wire length and spread cells are receiving renewed attention from both academia and industry. We describe the implementation details of a force-directed placer, FDP. Specifically, we provide: (1) a description of efficient force computation for spreading cells; (2) an illustration of numerical instability in these methods and a means by which these instabilities are avoided; (3) spread metrics for measuring cell distribution throughout the placement region; and (4) a complementary technique which aids in directly minimizing HPWL. We present results comparing our analytic placer to other academic tools for both standard cell and mixed-size designs. Compared to Kraftwerk and Capo 8.7, our tool produces results with an average improvement of 9% and 3%, respectively.

Segmented channel routing is fundamental to the routing of row-based FPGAs. In this paper, we study segmented channel routability via satisfiability. Our method encodes the horizontal and vertical constraints of the routing problem as Boolean conditions. The routability constraint is satisfiable if and only if the net connections in the segmented channel are routable. Empirical results show that the method is time-efficient and applicable to large problem instances.

This paper presents a satisfiability-based method for solving the board-level multiterminal net routing problem in the digital design of clos-folded field-programmable gate array (FPGA) based logic emulation systems. The approach transforms the FPGA board-level routing task into a Boolean equation. Any assignment of input variables that satisfies the equation specifies a valid routing. We use two of the fastest Boolean satisfiability (SAT) solvers: Chaff and DLMSAT to perform our experiments. Empirical results show that the method is time-efficient and applicable to large layout problem instances.

The paper presents a satisfiability-based method for solving the board-level multiterminal net routing problem in Clos-Folded FPGA based logic emulation systems. The approach transforms the FPGA board-level routing task into a single, large Boolean equation with the property that any assignment of input variables that satisfies the equation specifies a valid routing. The approach considers all nets simultaneously and the absence of a satisfying assignment implies that the layout is unroutable. We use two of the fastest SAT solvers: Chaff and DLM to perform our experiments. Empirical results show that the method is time-efficient and applicable to large layout problem instances.

Global placement ofhypergraphs is critical in the top-down placement of large timing-driven designs [10, 16]. Placement quality is evaluated in terms of the half-perimeter wirelength (HPWL) of hyperedges in the original circuit hypergraph provided timing constraints are met. Analytical placers are instrumental in handling non-linear timing models [9, 3], but have twoimportant drawbacks: (a) corresponding optimization algorithms are typically slower than top-down methods driven by multi-level mincut partitioning [2], and (b) hyperedges must be represented with net

We present approximations to non-smooth continuous functions by differentiable functions which are parameterized by a scalar /spl beta/>0 and have convenient limit behavior as /spl beta//spl rarr/0. For standard numerical methods, this translates into a tradeoff between solution quality and speed. We show the utility of our approximations for wirelength and delay estimations used by analytical placers for VLSI layout. Our approximations lead to more "solvable" problems.

Article Hypergraph partitioning for VLSI CAD: methodology for heuristic development, experimentation and reporting Share on Authors: Andrew E. Caldwell UCLA Computer Science Department, Los Angeles, CA UCLA Computer Science Department, Los Angeles, CAView Profile , Andrew B. Kahng UCLA Computer Science Department, Los Angeles, CA UCLA Computer Science Department, Los Angeles, CAView Profile , Andrew A. Kennings Cypress Semiconductor, Beaverton, OR Cypress Semiconductor, Beaverton, ORView Profile , Igor L. Markov UCLA Computer Science Department, Los Angeles, CA UCLA Computer Science Department, Los Angeles, CAView Profile Authors Info & Claims DAC '99: Proceedings of the 36th annual ACM/IEEE Design Automation ConferenceJune 1999 Pages 349–354https://doi.org/10.1145/309847.309955Online:01 June 1999Publication History 20citation418DownloadsMetricsTotal Citations20Total Downloads418Last 12 Months8Last 6 weeks2 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 SiteGet Access