Search

This article introduces Cpp-Taskflow, a high-performance parallel task programming system, to streamline the building of large and complex parallel applications. Cpp-Taskflow leverages the power of modern C++ and task-based approaches to enable efficient implementations of parallel decomposition strategies. Our programming model can quickly handle not only traditional loop-level parallelism but also irregular patterns, such as graph algorithms and dynamic control flows. Compared with existing libraries, Cpp-Taskflow is more cost efficient in performance scaling and software integration. We have evaluated Cpp-Taskflow on both micro-benchmarks and large-scale design automation problems of million-scale tasking. In a particular timing analysis workload, Cpp-Taskflow outperformed OpenMP by 2× faster using 2× fewer lines of code. We have also shown Cpp-Taskflow achieved up to 47.81% speed-up with 28.5% less code over the industrial-strength library, Intel Threading Building Blocks, on a detailed placement problem. [ABSTRACT FROM AUTHOR]

Since the first release in 2015, OpenTimer v1 has been used in many industrial and academic projects for analyzing the timing of custom designs. After four-year research and developments, we have announced OpenTimer v2—a major release that efficiently supports: 1) a new task-based parallel incremental timing analysis engine to break through the performance bottleneck of existing loop-based methods; 2) a new application programming interface (API) concept to exploit high degrees of parallelisms; and 3) an enhanced support for industry-standard design formats to improve user experience. Compared with OpenTimer v1, we rearchitect v2 with a modern C++ programming language and advanced parallel computing techniques to largely improve the tool performance and usability. For a particular example, OpenTimer v2 achieved up to 5.33 × speedup over v1 in incremental timing, and scaled higher with increasing cores. Our contributions include both technical innovations and engineering knowledge that are open and accessible to promote timing research in the community. [ABSTRACT FROM AUTHOR]

Rectangular grid graph (RGG) and diagonal grid graph (DGG) are induced subgraphs of a rectangular or diagonal grid, respectively. Their $k$ -coloring problem has direct applications in printing contact/via layouts by multipatterning lithography (MPL). However, the problem in general is computationally difficult for $k>2$ , while it remains an open question on grid graphs due to their regularity and sparsity. On the other hand, directed self-assembly (DSA) technique can work with MPL to optimize the graph by grouping neighboring vertices such that $k$ can be reduced, but the problem of deploying the grouping for coloring is even more intractable. In this paper, we study both of the $k$ -coloring problems, with and without DSA grouping, on RGG and DGG. Without grouping, a complete $k$ -coloring analysis is conducted and particularly the NP-completeness of 3-coloring on a diagonal grid is proved. When considering grouping, we present a 3-coloring solution and prove the NP-completeness to solve the problem of $k=2$. [ABSTRACT FROM AUTHOR]

Recent years have seen rapid growth in data-driven distributed systems, such as Hadoop MapReduce, Spark, and Dryad. However, the counterparts for high-performance or compute-intensive applications including large-scale optimizations, modeling, and simulations are still nascent. In this paper, we introduce DtCraft, a modern C++ based distributed execution engine to streamline the development of high-performance parallel applications. Users need no understanding of distributed computing and can focus on high-level developments, leaving difficult details, such as concurrency controls, workload distribution, and fault tolerance handled by our system transparently. We have evaluated DtCraft on both micro-benchmarks and large-scale optimization problems, and shown the promising performance from single multicore machines to clusters of computers. In a particular semiconductor design problem, we achieved ${30\times }$ speedup with 40 nodes and ${15\times }$ less development efforts over hand-crafted implementation. [ABSTRACT FROM AUTHOR]

Physically unclonable functions (PUFs) provide a device-unique challenge–response mapping and are employed for authentication and encryption purposes. Unpredictability and reliability are the core requirements of PUFs: unpredictability implies that an adversary cannot sufficiently predict future responses from previous observations. Reliability is important as it increases the reproducibility of PUF responses and hence allows validation of expected responses. However, advanced machine-learning algorithms have been shown to be a significant threat to the practical validity of PUFs, as they are able to accurately model PUF behavior. The most effective technique was shown to be the XOR-based combination of multiple PUFs, but as this approach drastically reduces reliability, it does not scale well against software-based machine-learning attacks. In this paper, we analyze threats to PUF security and propose PolyPUF, a scalable and secure architecture to introduce polymorphic PUF behavior. This architecture significantly increases model-building resistivity while maintaining reliability. An extensive experimental evaluation and comparison demonstrate that the PolyPUF architecture can secure various PUF configurations and is the only evaluated approach to withstand highly complex neural network machine-learning attacks. Furthermore, we show that PolyPUF consumes less energy and has less implementation overhead in comparison to lightweight reference architectures. [ABSTRACT FROM PUBLISHER]

Double patterning lithography (DPL) technologies have become a must for today's sub-32 nm technology nodes. Currently, there are two leading DPL technologies: self-aligned double patterning (SADP) and litho-etch-litho-etch (LELE). Among them, SADP has the significant advantage over LELE in its ability to avoid overlay, making it the likely DPL candidate for the next technology node of 14 nm. In any DPL technology, layout decomposition is the key problem. While the layout decomposition problem for LELE has been well studied in the literature, only a few attempts have been made to address the SADP layout decomposition problem. In this paper, we present a polynomial time exact (optimal) algorithm to determine if a given layout has SADP decompositions that do not have any overlay at specified critical edges. The previous approaches tried to minimize the total overlay of a given layout, which may be a problematic objective. Furthermore, all previous exact algorithms were computationally expensive exponential time algorithms based on SAT or ILP. Other previous algorithms for the problem were heuristics without having any guarantee that an overlay-free solution can be found even if one exists. [ABSTRACT FROM AUTHOR]

In this paper, we introduce and study the rectangle escape problem (REP), which is motivated by printed circuit board (PCB) bus escape routing. Given a rectangular region R and a set S of rectangles within R, the REP is to choose a direction for each rectangle to escape to the boundary of R, such that the resultant maximum density over R is minimized. We prove that the REP is NP-complete, and show that it can be formulated as an integer linear programming (ILP). A provably good approximation algorithm for the REP is developed by applying linear programming (LP) relaxation and a special rounding technique to the ILP. In addition, an iterative refinement procedure is proposed as a postprocessing step to further improve the results. Our approximation algorithm is also shown to work for more general versions of REP: weighted REP and simultaneous REP. Our approach is tested on a set of industrial PCB bus escape routing problems. Experimental results show that the optimal solution can be obtained within several seconds for each of the test cases. [ABSTRACT FROM AUTHOR]

Escape routing for packages and printed circuit boards (PCBs) has been studied extensively in the past. Network flow is pervasively used to model this problem. However, none of the previous works correctly models the diagonal capacity, which is essential for 45 \circ routing in most packages and PCBs. As a result, existing algorithms may either produce routing solutions that violate the diagonal capacity or fail to output a legal routing even though there exists one. In this paper, we propose a new network flow model that guarantees the correctness when diagonal capacity is taken into consideration. This model leads to the first optimal algorithm for escape routing. We also extend our model to handle missing pins. 45 [ABSTRACT FROM AUTHOR]

With the thermal effect, improper analog placements may degrade circuit performance because the thermal impact from power devices can affect electrical characteristics of the thermally-sensitive devices. There is not much previous work that considers the desired placement configuration between power and thermally-sensitive devices for a better thermal profile to reduce the thermally-induced mismatches. This paper first introduces the properties of a desired thermal profile for better thermal matching of the matched devices. It then presents a thermal-driven analog placement methodology to achieve the desired thermal profile and to consider the best device matching under the thermal profile while satisfying the symmetry and the common-centroid constraints. Experimental results based on real analog circuits show that the proposed approach can achieve the best analog circuit performance/accuracy with the least impact due to the thermal gradient, among existing works. [ABSTRACT FROM PUBLISHER]

Simultaneous escape routing on dense circuit boards is a very challenging task and a great amount of manual effort is still needed in order to achieve high routability. In this paper, we present a new simultaneous escape routing algorithm which is based upon a novel boundary routing approach. Our algorithm can solve complicated escape problems in a very short time. For a set of industrial escape problems, our algorithm successfully solved all of them while Cadence Allegro PCB router was only able to complete the routing of half of the problems. In addition, we propose a clustering strategy targeting at large escape routing problems. Experimental results show that this clustering strategy can significantly cut down the runtime of our router when solving large problems. [ABSTRACT FROM AUTHOR]

This paper presents a novel approach to reduce dynamic power in field-programmable gate arrays (FPGAs) by reducing glitches during routing. It finds alternative routes for early-arriving signals so that signal arrival times at look-up tables are aligned. We developed an efficient algorithm to find routes with target delays and then built a glitch-aware router aiming at reducing dynamic power. To the best of our knowledge, this is the first glitch-aware routing algorithm for FPGAs. Experiments show that an average of 27% reduction in glitch power is achieved, which translates into an 11% reduction in dynamic power, compared to the glitch-unaware versatile place and route's router. [ABSTRACT FROM AUTHOR]

Length-constrained routing is a very important issue for printed circuit board (PCB) routing. Previous length-constrained routers all have assumptions on the routing topology, whereas practical designs may be free of any topological constraint. In this paper, we propose a routing scheme that deals with general topology. Unlike previous works, our approach does not impose any restriction on the routing topology. Moreover, our routing scheme is gridless. Its performance does not depend on the routing grid size of the input while the routers in the papers of Ozdal and Wong and Kubo et al. do. This is a big advantage because modern PCB routing configurations usually imply huge routing grids. The novelty of this work is that we view the length-constrained routing problem as an area assignment problem and use a placement structure, which is the bounded-slice line grid, to help transform the area assignment problem into a mathematical programming problem. We then use an iterative approach to solve this mathematical programming problem. Experimental results show that our routing scheme can handle practical designs that previous routers cannot handle. For designs that they could handle, our router runs much faster. For example, in one of our data, we obtain the result in 88 s while the Lagrangian relaxation based router by Ozdal and Wong takes more than one day. [ABSTRACT FROM AUTHOR]

Global routing is an important step in the physical design process. In this paper, we propose a new global routing algorithm Archer, which resolves some of the most common problems with the state-of-the-art global routers. It is known that concurrent global routing algorithms are typically too expensive to be applied on today's large designs, which may contain up to a million nets. On the other hand, iterative rip-up and reroute (RNR)-based algorithms are susceptible to getting stuck in local optimal solutions. In this paper, we propose an RNR-based global routing algorithm that guides the routing iterations out of local optima through effective usage of congestion histories. We also focus on the problem of how to enable a smooth tradeoff between seemingly conflicting objectives of overflow and wirelength minimization. Furthermore, we propose a Lagrangian relaxation-based bounded-length mm-cost topology improvement algorithm that enables Steiner trees to change dynamically for the purpose of congestion optimization. Our experiments on public benchmarks show the effectiveness of Archer compared to other state-of-the-art global routers. [ABSTRACT FROM AUTHOR]

Design for low power has become a key requirement in today's System-on-a-Chip design, particularly for mobile applications. Multi-Vdd (MSV) is an effective method to reduce both leakage and dynamic powers. In a MSV design, cells of different supply voltages are often grouped into a small number of voltage islands, in order to avoid complex power-supply system and excessive amount of level shifters. In 2005, Wu et a!. proposed an elegant algorithm for voltage-island grouping based on the physical proximity of the critical cells in a postplacement voltage assignment and, in 2006, proposed an efficient algorithm for voltage assignment which not only meets timing but also forms good proximity of the critical cells. However, due to insufficient slack, a few isolated critical cells (called outliers) may still exist in the resulting voltage assignment, causing disproportionately expensive penalty to the final voltage-island grouping. In this paper, we propose a novel approach to improve the voltage assignment by automatic outlier detection followed by incremental placement. The outlier detection is based on a modified algorithm for the facility-location problem and proper parameter setting. We also propose a novel partial-sort technique which speeds up this algorithm significantly (up to 3 × in our experiments). The incremental placement is guided by setting proper constraints on the paths containing the detected outliers, such that the outliers can be eliminated later. Our experiments on industry designs show that our algorithm leads to 12%-54% improvement in the final voltage-island grouping, with quick turn-around time. [ABSTRACT FROM AUTHOR]

In this paper, we target field-programmable gate array (FPGA) performance optimization using a novel binary decision diagram (BDD)-based synthesis paradigm. Most previous works have focused on BDD size reduction during logic synthesis. In this paper, we concentrate on delay reduction and conclude that there is a large optimization margin through BDD synthesis for FPGA performance optimization. Our contributions are threefold: 1) we propose a gain-based clustering and partial collapsing algorithm to prepare the initial design for BDD synthesis for better delay; 2) we use a technique called linear expansion for BDD decomposition, which, in turn, enables a dynamic programming algorithm to efficiently search through the optimization space for the BDD of each node in the clustered circuit; and 3) we consider special decomposition scenarios coupled with linear expansion for further improvement on the quality of results. Experimental results show that we can achieve a 30% performance gain with a 22% area overhead on the average compared to a previous state-of-the-art BDD-based FPGA synthesis tool, namely, BDS-pga. Compared to DAOmap, we can achieve a 33% performance gain with only an 8% area overhead. Compared to the ABC mapper, we can achieve a 20% performance gain with only an 8% area overhead. [ABSTRACT FROM AUTHOR]

As the device shapes keep shrinking, the designs are more sensitive to manufacturing processes. In order to improve performance predictability and yield, mask-layout uniformity/ evenness is highly desired, and it is usually measured by the feature densities within defined feasible ranges determined by the manufacturing-process design rules. To address the density-control problem, one fundamental problem is how to calculate density accurately and efficiently. In this paper, we propose a fast exact algorithm to identify the maximum/minimum density for a given layout. Compared with the existing exact algorithms, our algorithm reduces the running time from days/long hours to a few minutes/seconds. Moreover, it is even faster than the existing approximate algorithms in the literature. [ABSTRACT FROM AUTHOR]

Shrinking transistor sizes, increasing circuit complexities, and high clock frequencies bring new board-routing challenges that cannot be handled effectively by traditional routing algorithms. Many high-end designs in the industry today require manual routing efforts, which increases the design-cycle times considerably. In this paper, we propose an escape-routing algorithm to route nets within multiple dense components simultaneously so that the number of crossings in the intermediate area is minimized. We also show how to handle high-speed-design constraints within the framework of this algorithm. Experimental comparisons with a recently proposed algorithm show that our algorithm reduces the via requirements of industrial test cases on average by 39%. [ABSTRACT FROM AUTHOR]

High power consumption not only leads to short battery life for hand-held devices but also causes on-chip thermal and reliability problems in general. As power consumption is proportional to the square of supply voltage, reducing supply voltage can significantly reduce power consumption. Multi-supply voltage (MSV) has previously been introduced to provide finer grain power and performance tradeoff. In this paper, we propose a methodology on top of a set of algorithms to exploit nontrivial voltage island boundaries for optimal power versus design-cost tradeoff under performance requirement. Our algorithms are efficient, robust, and error-bounded and can be flexibly tuned to optimize for various design objectives (e.g., minimal power within a given number of voltage islands, or minimal fragmentation in voltage islands within a given power bound) depending on the design requirement. Our experiment on real industry designs shows a tenfold improvement of our method over current logical-boundary-based industry approach. [ABSTRACT FROM AUTHOR]

As the clock frequencies used in industrial applications increase, the timing requirements imposed on routing problems become tighter. Therefore, it becomes important to route the nets within tight minimum and maximum length bounds. Although the problem of routing nets to satisfy maximum length constraints is a well-studied problem, there exists no sophisticated algorithm in literature that ensures that minimum length constraints are also satisfied. In this paper, the authors propose a novel algorithm that effectively incorporates the min-max length constraints into the routing problem. The approach is to use a Lagrangian-relaxation (LR) framework to allocate extra routing resources around nets simultaneously during routing them. The authors also propose a graph model that ensures that all the allocated routing resources can be used effectively for extending lengths. Their routing algorithm automatically prioritizes resource allocation for shorter nets and length minimization for longer nets so that all nets can satisfy their min-max length constraints. This paper demonstrates that this algorithm is effective even in the cases where length constraints are tight, and the spacing between adjacent nets is small. [ABSTRACT FROM AUTHOR]

Modern field-programmable gate arrays (FPGAs) have multimillions of gates and future generations of FPGAs will be even more complex. This means that floorplanning tools will soon be extremely important for the physical design of FPGAs. Due to the heterogeneous logic and routing resources of an FPGA, FPGA floorplanning is very different from the traditional floorplanning for application-specific integrated circuits. This paper presents the first FPGA-floorplanning algorithm targeted for FPGAs with heterogeneous resources (e.g., Xilinx's Spartan3 chips consisting of columns of configurable logic blocks, RAM blocks, and multiplier blocks). This algorithm can generate floorplans for Xilinx's XC3S5000 architecture (largest of the Spartan3 family) in a few minutes. [ABSTRACT FROM AUTHOR]

Input-output (I/O) placement has always been a concern in modern integrated circuit design. Due to flip-chip technology, I/O can be placed throughout the whole chip without long wires from the periphery of the chip. However, because of I/O placement constraints in design cost (DC) and performance, I/O buffer planning becomes a pressing problem. During the early stages of circuits and package co-design, I/O layout should be evaluated to optimize DC and to avoid product failures. The objective of this brief is to improve the existing/initial standard cell placement by I/O clustering, considering DC reduction and signal integrity preservation. The authors formulate it as a minimum cost flow problem that minimizes αW +βD, where W is the I/O wirelength of the placement and D is the total voltage drop in the power network and, at the same time, reduces the number of I/O buffer blocks. The experimental results on some Microelectronics Center of North Carolina benchmarks show that the author's method averagely achieves better timing performance and over 32% DC reduction when compared with a conventional rule-of-thumb design that is popularly used by circuit designers. [ABSTRACT FROM AUTHOR]

Engineering change order changes are almost inevitable in the late stages of a design process. Based on an existing design, incremental change is favored since it can avoid considerable efforts of redoing the whole process and can minimize the disturbance on the existing converged design. The coupling-capacitance violation elimination (CVE) problem is addressed. Due to the changes in the multiple layer routing design, the total coupling capacitance on some signal wire segments on a layer may be larger than their allowable bounds after postlayout timing/noise analysis. The target is to find a new routing solution without coupling-capacitance violations under certain constraints, which helps to keep the new design close to the original one. This paper proposes a two-stage algorithm to solve CVE problems, and present optimization strategies to speed up the execution. Experimental results demonstrate the efficiency and effectiveness of this algorithm. [ABSTRACT FROM AUTHOR]

Existing floorplanning algorithms compact blocks to the left and bottom. Although the compaction obtains an optimal area, it may not be good for meeting other objectives such as minimizing the total wire length, which is the first-order objective. It is not known in the literature how to place blocks to obtain an optimal wire length. This paper first shows that the problem can be formulated by linear programming. Thereafter, instead of using the general, but slow, linear programming, this paper proposes an efficient minimum-cost flow-based approach to solve it. This approach guarantees to obtain the minimum total wire length in polynomial time and meanwhile keep the minimum area by distributing white space smarter for a given floorplan topology. This paper also shows that the approach can be easily extended to handle constraints such as fixed frame (fixed area), input-output (IO) pins, preplaced blocks, boundary blocks, range placement, alignment and abutment, rectilinear blocks, soft blocks, one-dimensional cluster placement, and bounded net delay, without loss of optimality. Practically, the algorithm is so efficient that it finishes in less than 0.4 s for all Microelectronics Center of North Carolina (MCNC) benchmarks of block placement. It is also very effective. Experimental results show that the wire length of very compact floorplans can even be improved by 4.2%. Thus, it provides an ideal way for postfloorplanning refinement. [ABSTRACT FROM AUTHOR]

As die sizes are shrinking, and circuit complexities are increasing, the printed circuit board routing problem becomes more and more challenging. Traditional routing algorithms cannot handle these challenges effectively, and many high-end designs in the industry require manual routing efforts. This paper proposes a problem decomposition that distinguishes routing under dense components from routing in the intermediate area. In particular, it proposes an effective methodology to find the escape routing solution for multiple components simultaneously such that the number of crossings in the intermediate area is minimized. For this, the problem is modeled as a longest path with forbidden pairs problem, and two algorithms are proposed for it. The first is an exact polynomial-time algorithm that is guaranteed to find the maximal planar routing solution on one layer. The second is a randomized algorithm that has good scalability characteristics for large circuits. Then, these algorithms are used to assign the maximal subset of planar nets to each layer, and then the remaining nets are distributed at the end. This paper demonstrates the effectiveness of these algorithms through experiments on industrial circuits. [ABSTRACT FROM AUTHOR]

As the clock frequencies used in industrial applications increase, the timing requirements on routing problems become tighter, and current routing tools cannot successfully handle these constraints anymore. In this paper, the authors focus on the high-performance single-layer bus routing problem, where the objective is to match the lengths of all nets belonging to each bus. An effective approach to solve this problem is to allocate extra routing resources around short nets during routing, and use those resources for length extension afterwards. First, a provably optimal algorithm for routing nets with minimum-area maximum-length constraints is proposed. Then, this algorithm is extended to the case where minimum constraints are given as exact length bounds, and it is also proven that this algorithm is near-optimal. Both algorithms proposed are shown to be scalable for large circuits, since the respective time complexities are O (A) and O (A log A), where A is the area of the intermediate region between chips. [ABSTRACT FROM AUTHOR]

With today's advanced integrated circuit manufacturing technology in deep submicron (DSM) environment, we can integrate entire electronic systems on a single system on a chip. However, without careful power supply planning in layout, the design of chips will suffer from local hot spots, insufficient power supply, and signal integrity problems. Postfloorplanning or postroute methodologies in solving power delivery and signal integrity problems have been applied but they will cause a long turnaround time, which adds costly delays to time-to-market. In this paper, we study the problem of simultaneous power supply planning and noise avoidance as early as in the floorplanning stage. We show that the problem of simultaneous power supply planning and noise avoidance can be formulated as a constrained maximum flow problem and present an efficient yet effective heuristic to handle the problem. Experimental results are encouraging. With a slight increase of total wirelength, we achieve almost no static IR (voltage)-drop requirement violation in meeting the current and power demand requirement imposed by the circuit blocks compared with a traditional floorplanner and 45.7% of improvement on a SI noise constraint violation compared with the approach that only considers power supply planning. [ABSTRACT FROM AUTHOR]

In this paper, we present an integrated approach for floorplanning and bus planning, i.e., bus-driven floorplanning (BDF). We are given a set of circuit blocks and the bus specifications (i.e., the net list of blocks for the buses). A feasible BDF solution is a placement of all circuit blocks such that each bus can be realized as a rectangular strip (horizontal or vertical) going through all the blocks connected by the bus. The objective is to determine a feasible BDF solution that minimizes the floorplan area and the total bus area. Our approach is based upon the sequence pair floorplan representation. After a careful analysis of the relationship between bus ordering and block ordering in the floorplan represented by a sequence pair, we derive feasibility conditions on sequence pairs that give feasible BDF solutions. Experimental results demonstrate the efficiency and effectiveness of our algorithm. [ABSTRACT FROM AUTHOR]

Introduces series of articles which deals on computer-aided design.