Modern field-programmable gate arrays (FPGAs) may feature critical path portions of designs prearranged into movable macros during synthesis. These movable macros, with constraints of shape and resources, pose a challenge for mixed-size placement in FPGA designs that previous analytical placers cannot handle. Additionally, general timing-driven placement algorithms face challenges when dealing with real-world application designs and ultrascale FPGA architectures. To address these challenges, we present AMF-Placer 2.0, an open-source FPGA placer that supports mixed-size placement of heterogeneous resources. Building on AMF-Placer 1.0, AMF-Placer 2.0 incorporates new techniques for timing optimization, including an effective regression-based timing model, placement-blockage-aware anchor insertion, TNS/WNS-aware timing-driven quadratic placement, and sector-guided detailed placement. It is evaluated by a set of the latest large open-source benchmarks from various domains for AMD Xilinx Ultrascale FPGAs. Experimental results indicate that AMF-Placer 2.0 achieves critical path delays that are on average only 2.3% and 0.69% higher than those achieved by commercial tool AMD Xilinx Vivado 2020.2 and 2021.2, respectively. Furthermore, the average runtime of the placement procedure in AMF-Placer 2.0 is 7.0% and 11.5% lower than that of AMD Xilinx Vivado 2020.2 and 2021.2, respectively. Although limited by the absence of detailed information of devices and designs, AMF-Placer 2.0 is the first open-source FPGA placer that can handle timing-driven mixed-size placement for practical complex designs with various FPGA resources and achieve comparable quality to the latest commercial tools.

Detailed routing is one of the most complex and time-consuming stages of VLSI design process. Due to the rapidly growing problem scale and increasing number of design rules in advanced technology nodes, a feasible routing result can only be achieved after many rounds of rip-up and reroute (R&R) iterations, which takes a significantly long runtime. In this paper, we propose several effective and efficient techniques to handle the design rule violations in detailed routing. An adaptive rip-up scheme with two strategies of different effort is designed, which can speed up the R&R phase with comparable solution quality. To cope with the pin access challenge with complex design rule constraints, approaches to refine the pin connections are proposed. Besides, some specific design rules are handled in a post-processing manner efficiently. Experiment result shows that the number of design rule violations can be reduced by 69% with 28% lower runtime on average, after integrating these techniques in Dr. CU 2.0.

Placement is one of the most critical stages in the physical synthesis flow. Circuits with increasing numbers of cells of multirow height have brought challenges to traditional placers on efficiency and effectiveness. Besides providing an overlap-free solution close to the global placement (GP) solution, constraints on power and ground (P/G) alignments, fence region, and routability (e.g., edge spacing and pin short/inaccessible) should be considered. In this article, we propose a legalization method for mixed-cell-height circuits by a window-based cell insertion technique and two post-processing network flow-based optimizations. Compared with the champion of the ICCAD 2017 Contest, our algorithm achieves 35% and 13% less average and maximum displacement, respectively, as well as significantly fewer routability violations. Comparing our algorithm with the state-of-the-art algorithms on this problem, there is an 8% improvement in average displacement with comparable maximum displacement. The source code of our legalization is available athttps://github.com/cuhk-eda/ripple.

To meet the growing demand from deep learning applications for computing resources, accelerators by ASIC are necessary. A wafer-scale engine (WSE) is recently proposed [1], which is able to simultaneously accelerate multiple layers from a neural network (NN). However, without a high-quality placement that properly maps NN layers onto the WSE, the acceleration efficiency cannot be achieved. Here, the WSE placement resembles the traditional ASIC floor plan problem of placing blocks onto a chip region, but they are fundamentally different. Since the slowest layer determines the compute time of the whole NN on WSE, a layer with a heavier workload needs more computing resources. Besides, locations of layers and protocol adapter cost of internal 10 connections will influence inter-layer communication overhead. In this paper, we propose GigaPlacer to handle this new challenge. A binary-search-based framework is developed to obtain a minimum compute time of the NN. Two dynamic-programming-based algorithms with different optimizing strategies are integrated to produce legal placement. The distance and adapter cost between connected layers will be further minimized by some refinements. Compared with the first place of the ISPD2020 Contest, GigaPlacer reduces the contest metric by up to 6.89% and on average 2.09%, while runs 7.23X faster.

In the routing tree construction, both wirelength (WL) and path-length (PL) are of importance. Among all methods, PD-II and SALT are the two most prominent ones. However, neither PD-II nor SALT always dominates the other one in terms of both WL and PL for all nets. In addition, estimating the best parameters for both algorithms is still an open problem. In this paper, we model the pins of a net as point cloud and formalize a set of special properties of such point cloud. Considering these properties, we propose a novel deep neural net architecture, TreeNet, to obtain the embedding of the point cloud. Based on the obtained cloud embedding, an adaptive workflow is designed for the routing tree construction. Experimental results show that the proposed TreeNet is superior to other mainstream models for the point cloud on classification tasks. Moreover, the proposed adaptive workflow for the routing tree construction outperforms SALT and PD-II in terms of both efficiency and effectiveness.

Rectilinear Steiner Minimum Tree (RSMT) is the shortest way to interconnect a net’s n pins using rectilinear edges only. Constructing the optimal RSMT is NP-complete and nontrivial. In this work, we design a reinforcement learning based algorithm called REST for RSMT construction. After training, REST constructs RSMT of $\leq 0.36\%$ length error on average for nets with $\leq 50$ pins. The average time needed for one net is fewer than 1.9 ms, and is much faster than traditional heuristics of similar quality. This is also the first successful attempt to solve this problem using a machine learning approach.

To enable the performance optimization of application mapping on modern field-programmable gate arrays (FPGAs), certain critical path portions of the designs might be prearranged into many multi-cell macros during synthesis. These movable macros with constraints of shape and resources lead to challenging mixed-size placement for FPGA designs which cannot be addressed by previous works of analytical placers. In this work, we propose AMF-Placer, an open-source Analytical Mixed-size FPGA placer supporting mixed-size placement on FPGA, with an interface to Xilinx Vivado. To speed up the convergence and improve the quality of the placement, AMF-Placer is equipped with a series of new techniques for wirelength optimization, cell spreading, packing, and legalization. Based on a set of the latest large open-source benchmarks from various domains for Xilinx Ultrascale FPGAs, experimental results indicate that AMF-Placer can improve HPWL by 20.4%-89.3% and reduce runtime by 8.0%-84.2%, compared to the baseline. Furthermore, utilizing the parallelism of the proposed algorithms, with 8 threads, the placement procedure can be accelerated by 2.41x on average.

Different from global routing, detailed routing takes care of many detailed design rules and is performed on a significantly larger routing grid graph. In advanced technology nodes, it becomes the most complicated and time-consuming stage in the very large-scale integration physical design flow. We propose Dr. CU, an efficient and effective detailed router, to tackle the challenges. To handle a 3-D detailed routing grid graph of enormous size, a set of two-level sparse data structures is designed for runtime and memory efficiency. For handling the minimum-area constraint, an optimal correct-by-construction path search algorithm is proposed. Besides, an efficient bulk synchronous parallel scheme is adopted to further reduce the runtime usage. Compared with the other state-of-the-art academic detailed routers, Dr. CU reduces the number of design rule violations by one or two orders of magnitude. At the same time, it uses shorter wire length, fewer vias, and significantly less runtime. The source code of Dr. CU is available at https://github.com/cuhk-eda/dr-cu.

In a weighted undirected graph, a spanning/Steiner shallow-light tree (SLT) simultaneously approximates: 1) shortest distances from a root to the other vertices and 2) the minimum tree weight. The Steiner SLT has been proved to be exponentially lighter than the spanning one. In this paper, we propose a novel Steiner SLT construction method called Steiner SLT (SALT), which is efficient and has the tightest bound over all the state-of-the-art general-graph SLT algorithms. Applying SALT to Manhattan space offers a smooth tradeoff between rectilinear Steiner minimum tree and rectilinear Steiner minimum arborescence for VLSI routing. The adaption also reduces the time complexity from O(n2) to O(n log n). Besides, several effective post-processing methods, including safe refinement and shallowness-constrained edge substitution, are proposed to further improve the result. The experimental results show that SALT can achieve not only short path lengths and wirelength but also small delay, compared to both classical and recent routing tree construction methods.

Different from global routing, detailed routing takes care of many detailed design rules and is performed on a significantly larger routing grid graph. In advanced technology nodes, it becomes the most complicated and time-consuming stage. We propose Dr. CU, an efficient and effective detailed router, to tackle the challenges. To handle a 3D detailed routing grid graph of enormous size, a set of two-level sparse data structures is designed for runtime and memory efficiency. For handling the minimum-area constraint, an optimal correct-by-construction path search algorithm is proposed. Besides, an efficient bulk synchronous parallel scheme is adopted to further reduce the runtime usage. Compared with the first place of ISPD 2018 Contest, our router improves the routing quality by up to 65% and on average 39%, according to the contest metric. At the same time, it achieves 80--93% memory reduction, and 2.5--15X speed-up.

The continuous development of modern VLSI technology has brought new challenges for on-chip interconnections. Different from classic net-by-net routing, bus routing requires all the nets (bits) in the same bus to share similar or even the same topology, besides considering wire length, via count, and other design rules. In this paper, we present MARCH, an efficient maze routing method under a concurrent and hierarchical scheme for buses. In MARCH, to achieve the same topology, all the bits in a bus are routed concurrently like marching in a path. For efficiency, our method is hierarchical, consisting of a coarse-grained topology-aware path planning and a fine-grained track assignment for bits. Additionally, an effective rip-up and reroute scheme is applied to further improve the solution quality. In experimental results, MARCH significantly outperforms the first place at 2018 IC/CAD Contest in both quality and runtime.

Dummy fill insertion is a mandatory step in modern semiconductor manufacturing process to reduce dielectric thickness variation, and provide nearly uniform pattern density for the chemical mechanical planarization (CMP) process. However, with the continuous shrinking of the VLSI technology nodes, the coupling effects between the inserted metal fills and signal tracks can severely affect the original timing closure of the layout design. In this paper, we propose a robust, efficient and high-performance framework for timing-aware dummy fill insertion, which simultaneously minimizes the coupling capacitance of critical signal wires and other wires. The experimental results on IC/CAD 2018 contest benchmarks shows that our proposed framework outperforms contest winner by 8% on critical coupling capacitance with 3.3× runtime speedup.

By retrospecting the classical deferred-merge embedding (DME) algorithm, we found an intrinsic relationship between the zero-skew tree (ZST) problem and the hierarchical clustering (HC) problem. To be more specific, the wire length of a ZST is proved a linear function of the sum of diameters of its corresponding HC. With this new insight, an effective O(n log n)-time O(1)-approximation algorithm and an optimal dynamic programming for ZST are designed. Using the ZST construction black box and a linear-time optimal tree decomposition algorithm, an improved algorithm for constructing the bounded-skew tree (BST) is derived. In the experiment, our approach shows superior wire length compared with previous methods for both ZST and BST.

Detailed routing becomes a crucial challenge in VLSI design with shrinking feature size and increasing design complexity. More complicated design rules were added to guarantee manufacturability, which made detailed routing an even harder task to achieve in the design flow. In this paper, we propose a detailed router that judiciously handles hard-to-access pins and new design rules including length-dependent parallel run length spacing, end-of-line spacing with parallel edges, and corner-to-corner spacing. Our experimental results show that our framework can effectively reduce the number of violations with comparable wirelength. Comparing our algorithm with the best score of each released designs in the ISPD'19 Contest, there is 2% score improvement. Compared with the state-of-the-art work, our algorithm achieves 69% better scores. The source code of Dr. CU 2.0 is available at https://github.com/cuhk-eda/dr-cu.

Boolean matching is one of the most widely used engines in industrial applications. However, existing Boolean matching researches mainly focus on NPNP-equivalence. In this paper, we study a more practical problem of Boolean matching, which is Non-exact Projective NPNP (NP3). A two-step search engine is used to solve the problem and several heuristics and constraints are proposed to accelerate the whole process. In particular, we explore a new kind of symmetry properties in NP3 equivalence checking which helps to prune the solution space efficiently. Experimental results show that our proposed approach can achieve the best results among the winning teams of the ICCAD 2016 contest in quality within a given time limit.

Placement is one of the most critical stages in the physical synthesis flow. Circuits with increasing numbers of cells of multi-row height have brought challenges to traditional placers on efficiency and effectiveness. Furthermore, constraints on fence region and routability (e.g., edge spacing, pin access/short) should be considered, besides providing an overlap-free solution close to the global placement (GP) solution and fulfilling the power and ground (P/G) alignments. In this paper, we propose a legalization method for mixed-cell-height circuits by a window-based cell insertion technique and two post-processing network-flow-based optimizations. Compared with the champion of the IC/CAD 2017 Contest, our algorithm achieves 18% and 12% less average and maximum displacement respectively as well as significantly fewer routability violations. Comparing our algorithm with the state-of-the-art algorithms on this problem, there is a 9% improvement in total displacement with 20% less running time.

As a good tradeoff between central processing unit (CPU) and application specific integrated circuit (ASIC), field-programmable gate array (FPGA) is becoming more widely used in both industry and academia. The increasing complexity and scale of modern FPGA, however, impose great challenges on the FPGA placement and packing problem. In this paper, we propose RippleFPGA to solve the packing and placement simultaneously through a set of novel techniques: 1) smooth stair-step flow; 2) implicit packing similar to ASIC legalization (LG); and 3) two-level detailed placement (DP). To enable the flow, a generic, efficient, and false-alarm-free legality checking method is also proposed. Besides, due to the insufficiency of ASIC-like congestion alleviation methods, some FPGA-routing-architecture-aware optimization techniques are proposed to improve the routability. When evaluated by ISPD 2016 Contest benchmarks, RippleFPGA has 5.1% better routed wirelength and 5.5× speedup compared to all the state-of-the-art FPGA placers.

Liquid cooling shows great potential in resolving the huge thermal obstacle in 3D ICs. However, it brings new challenges including large thermal gradient and high pumping requirement. In this paper, liquid cooling networks with flexible topology are investigated to achieve more desirable trade-offs between energy efficiency and thermal profile. Specifically, a fast thermal model for the cooling network is proposed and analyzed, followed by our optimization methodologies to construct cooling networks targeting at pumping power saving and thermal gradient reduction, respectively. Experimental results show that, under the same constraints, the cooling network can save as much as 84.03% pumping power or reduce 37.65% thermal gradient compared to straight microchannels.

In a weighted undirected graph, a spanning/Steiner shallow-light tree (SLT) simultaneously approximates (i) shortest distances from a root to the other vertices, and (ii) the minimum tree weight. The Steiner SLT has been proved to be exponentially lighter than the spanning one [1], [2]. In this paper, we propose a novel Steiner SLT construction method called SALT (Steiner shAllow-Light Tree), which is efficient and has the tightest bound over all the state-of-the-art SLT algorithms. Applying SALT to Manhattan space offers a smooth trade-off between rectilinear Steiner minimum tree (RSMT) and rectilinear Steiner minimum arborescence (RSMA) for VLSI routing. In addition, the adaption further reduces the time complexity from O(n2) to O(n log n). The experimental results show that SALT can achieve not only short path lengths and wirelength but also small delay, compared to both classical and recent routing tree construction methods.

As the complexity and scale of circuits keep growing, clocking architectures of FPGAs have become more complex to meet the timing requirement. In this paper, to optimize wirelength and meanwhile meet emerging clocking architectural constraints, we propose several detailed placement techniques, i.e., two-step clock constraint legalization and chain move. After integrating these techniques into our FPGA placement framework, experimental results on ISPD 2017 benchmarks show that our proposed approach yields 2.3% shorter routed wirelength and the running time is 2x faster compared to the first place winner in the ISPD 2017 contest. Moreover, we explore the possibilities to use machine learning-based methods to predict routing congestion in UltraScale FPGAs. Experimental results on both ISPD 2016 and ISPD 2017 benchmarks show that our proposed congestion estimation model is a good approximation to the one obtained from Vivado and can lead to good placement results compared to the previous methods.

As the complexity and scale of FPGA circuits grows, resolving routing congestion becomes more important in FPGA placement. In this paper, we propose a routability-driven placement algorithm for large-scale heterogeneous FPGAs. Our proposed algorithm consists of (1) partitioning, (2) packing, (3) global placement with congestion estimation, (4) window-base legalization, and (5) routing resource-aware detailed placement. Experimental results show that our proposed approach can give routable placement results for all the benchmarks in the ISPD2016 contest and can achieve good result compared to the other wining teams of the ISPD2016 contest.

Tracking with a Pan-Tilt-Zoom (PTZ) camera has been a research topic in computer vision for many years. However, it is difficult to assess the progress that has been made because there is no standard evaluation methodology. The difficulty in evaluating PTZ tracking algorithms arises from their dynamic nature. In contrast to other forms of tracking, PTZ tracking involves both locating the target in the image and controlling the motors of the camera to aim it so that the target stays in its field of view. This type of tracking can only be performed online. In this paper, we propose a new evaluation framework based on a virtual PTZ camera. With this framework, tracking scenarios do not change for each experiment and we are able to replicate the main principles of online PTZ camera control and behavior including camera positioning delays, tracker processing delays, and numerical zoom. We tested our evaluation framework with the Camshift tracker to show its viability and to establish baseline results.