Floorplanning, as an early step in physical design, will greatly affect the PPA of the later stages. To achieve better performance while main-taining relatively the same chip size, the utilization of the generated floorplan needs to be high and constraints related to design rules, routability, power should be honored. In this paper, we propose a two-step framework, called TOFU, for floorplan whitespace reduction with fixed-outline and soft/pre- placed/hard modules modeled. Whitespace is first reduced by iteratively refining the locations of modules. Then the modules near whitespace will be changed into rectilinear shapes to further improve the utilization. To ensure the legality and quality of the intermediate floorplan during the refinement process, a constraint graph-based legalizer with a novel constraint graph construction method is proposed. Experimental results show that the whitespace of the initial floorplans generated by Corblivar [1] can be reduced by about 70% on average and up to 90% in several cases. Moreover, the resulting wirelength is also 3% shorter due to a higher utilization.

Gate Sizing is an important step in logic synthesis, where the cells are resized to optimize metrics such as area, timing, power, leakage, etc. In this work, we consider the gate sizing problem for leakage power optimization with timing constraints. Lagrangian Relaxation is a widely employed optimization method for gate sizing problems. We accelerate Lagrangian Relaxation-based algorithms by narrowing down the range of cells to resize. In particular, we formulate a heterogeneous directed graph to represent the timing graph, propose a heterogeneous graph neural network as the encoder, and train in the way of imitation learning to mimic the selection behavior of each iteration in Lagrangian Relaxation. This network is used to predict the set of cells that need to be changed during the optimization process of Lagrangian Relaxation. Experiments show that our accelerated gate sizer could achieve comparable performance to the baseline with an average of 22.5% runtime reduction.

In multi-FPGA systems, time-division multiplexing (TDM) is a widely used technique to transfer signals between FPGAs. While TDM can greatly increase logic utilization, the inter-FPGA delay will also become longer. A good time-multiplexing scheme for inter-FPGA signals is very important for optimizing the system performance. In this work, we propose a fast algorithm to generate high quality time-multiplexed routing results for multiple FPGA systems. A hybrid routing algorithm is proposed to route the nets between FPGAs, by maze routing and by a fast minimum terminal spanning tree method. After obtaining a routing topology, a two-step method is applied to perform TDM assignment to optimize timing, which includes an initial assignment and a competitive-based refinement. Experiments show that our system-level routing and TDM assignment algorithm can outperform both the top winner of the ICCAD 2019 Contest and the state-of-the-art methods. Moreover, compared to the state-of-the-art works [17, 22], our approach has better run time by more than 2x with better or comparable TDM performance.

Many competitive global routers adopt the technique of compressing the 3D routing space into 2D in order to handle today's massive circuit scales. It has been shown as an effective way to shorten the routing time, however, quality will inevitably be sacrificed to different extents. In this paper, we propose two routing techniques that directly operate on the 3D routing space and can maximally utilize the 3D structure of a grid graph. The first technique is called 3D pattern routing, by which we combine pattern routing and layer assignment, and we are able to produce optimal solutions with respect to the patterns under consideration in terms of a cost function in wire length and routability. The second technique is called multi-level 3D maze routing. Two levels of maze routing with different cost functions and objectives are designed to maximize the routability and to search for the minimum cost path efficiently. Besides, we also designed a cost function that is sensitive to resources changes and a post-processing technique called patching that gives the detailed router more flexibility in escaping congested regions. Finally, the experimental results show that our global router outperforms all the contestants in the ICCAD'19 global routing contest.

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 global routing, both timing and routability are critical criteria to measure the performance of a design. However, these two objectives naturally conflict with each other during routing. In this paper, we propose reconnection approaches to fix timing. We first formulated a quadratic program (QP), which adjusts routing topologies of all the nets by only reconnecting critical sinks and takes congestion into consideration to tradeoff timing and routability objectives. A machine learning (ML)-based technique is applied to accelerate our algorithm, which offers a fast and effective way to solve the problem. By exploring more reconnection candidates, we then formulated a QP to reconnect any sink of a net and utilized a multilabel classifier to accelerate the process. The experimental results on ICCAD 2015 benchmarks show that our algorithms can achieve timing improvement with no significant degradation in routability and wirelength. With ML-based acceleration, our results can be obtained in almost negligible runtime.

<?tight?>To increase the resource utilization in multi-FPGA (field-programmable gate array) systems, time-division multiplexing (TDM) is a widely used technique to accommodate a large number of inter-FPGA signals. However, with this technique, the delay imposed by the inter-FPGA connections becomes significant. Previous research has shown that the TDM ratios of signals can greatly affect the performance of a system. In this article, to minimize the system clock period and support more practical constraints in modern multi-FPGA systems, we propose an analytical framework to optimize the TDM ratios of inter-FPGA nets. A Lagrangian relaxation-based method first gives a continuous result under relaxed constraints. A binary search--based discretization algorithm is then used to assign the TDM ratio of each net such that the resulting maximum displacement is optimal and all the constraints are satisfied. Finally, a swapping-based post refinement is performed to further optimize the TDM ratios. For comparison, we also solve the problem using linear programming (LP)--based methods, which have guaranteed error bounds to the optimal solutions. Experimental results show that our framework can achieve similar quality with much shorter runtime compared to the LP-based methods. Moreover, our framework scales for designs with over 45,000 inter-FPGA nets while the runtime and memory usage of the LP-based methods will increase dramatically as the design scale becomes larger.

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.

To increase the resource utilization in multi-FPGA systems, time-division multiplexing (TDM) is a widely used technique to accommodate a large number of inter-FPGA signals. However, with this technique, the delay imposed by the inter-FPGA connections becomes significant. Previous research has shown that the TDM ratios of signals can greatly affect the performance of a system. In this paper, to minimize the system clock period and support more practical constraints in modern multi-FPGA systems, we propose a two-step analytical framework to optimize the TDM ratios of inter-FPGA nets. A Lagrangian relaxation-based method first gives a continuous result under relaxed constraints. A binary search-based discretization algorithm is then used to finalize the TDM ratios such that the resulted maximum displacement is optimal. For comparison, we also solve the problem using linear programming (LP)-based methods, which have guaranteed error bounds to the optimal solutions. Experimental results show that our framework can achieve similar quality with much shorter runtime compared to the LP-based methods. Moreover, our framework scales for designs with over 45000 inter-FPGA nets while the runtime and memory usage of the LP-based methods will increase dramatically as the design scale becomes larger.

The layouts of analog/mixed-signal (AMS) integrated circuits (ICs) are dramatically different from their digital counterparts. AMS circuit layouts usually include a variety of devices, including transistors, capacitors, resistors, and inductors. A complicated AMS IC system with hierarchical structure may also consist of pre-laid out subcircuits. Different types of devices can occupy different manufacturing layers. Therefore, during the layout stage, the devices require co-optimization to achieve high circuit performance. Leveraging the fact that some devices can be built by mutually exclusive layers, they can be carefully designed to overlap each other to effectively reduce the total area and wirelength without degrading the circuit performance. In this paper, we propose an analytical framework to tackle the device layer-aware analog placement problem. Experimental results show that on average the proposed techniques can reduce the total area and half-perimeter wirelength by 9% and 23%, respectively. To verify the routability of the placement results, we also develop an analog global router, which demonstrates that the device layer-aware placement can achieve 18% shorter wirelength during global routing.

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.

In global routing, both timing and routability are critical criterions to measure the performance of a design. However, these two objectives naturally conflict with each other during routing. In this paper, a tree surgery technique is presented to adjust routing tree topologies in global routing to fix timing. We formulate the problem as a quadratic program(QP), which adjusts routing topologies of all the nets from a global perspective and takes congestion into consideration to trade off timing and routability objectives. We also apply machine learning-based techniques to accelerate our algorithm, which offers a fast and effective way to solve the problem. Experimental results on ICCAD~2015 benchmarks show that our algorithms can achieve 10.12% timing improvement with no significant degradation in routability and wirelength. With machine learning-based acceleration (MLA), our results can be obtained in almost negligible runtime.

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.

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.

Typical standard cell placement algorithms assume that all cells are of the same height such that cells can be aligned along the placement rows. However, modern standard cell designs are getting more complicated and multiple-row height cell becomes more common. With multiple-row height cells, placement of cells are not independent among different rows. It turns out that most of the commonly used detailed placement and legalization techniques cannot be extended easily to handle the problem. We propose a novel algorithm in handling legalization of placement involving multiple-row height cells. The algorithm can efficiently legalize a local region of cells with various heights, which is especially useful for local cell movement, cell sizing, and buffer insertion. Experiments on the application of the technique in detailed placement show that our approach can effectively and efficiently legalize global placement results and obtain significant improvement in the objective function.

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.