Recent work has shown that machine-learned predictions can provably improve the performance of classic algorithms. In this work, we propose the first minimum-cost network flow algorithm augmented with a dual prediction. Our method is based on a classic minimum-cost flow algorithm, namely ε-relaxation. We provide time complexity bounds in terms of the infinity norm prediction error, which is both consistent and robust. We also prove sample complexity bounds for PAC-learning the prediction. We empirically validate our theoretical results on two applications of minimum-cost flow, i.e., traffic networks and chip escape routing, in which we learn a fixed prediction, and a feature-based neural network model to infer the prediction, respectively. Experimental results illustrate 12.74× and 1.64× average speedup on two applications.

Facing the complexity of escape routing in high-density interconnects within chiplet systems, conventional methods often struggle to balance efficiency and quality under large-scale design scenarios. This paper presents a Sliding-Window-based progressive Integer linear Programming (ILP) for scalable Escape Routing of chiplet interconnects, called SWIPER, which maintains high routing quality with controllable complexity by sequentially optimizing localized subproblems. Our approach uses predefined geometric patterns to adaptively select single- or multi-layer paths using ILP model, to avoid routing conflicts, thereby improving routing flexibility. Experimental results demonstrate that, compared with existing methods, SWIPER improves the routing completion rate by up to 28% in obstacle-dense scenarios, reduces the number of vias by up to 18%, and reduces the wirelength by up to 1.5%, exhibiting excellent scalability and practical robustness.

With the rapid advancement of 5G communication, AI accelerators, and high-performance computing (HPC) systems, the data rate of BGA differential signals has surpassed 56Gbps. Traditional 45° routing causes impedance discontinuity and EMI issues, while also triggering design rule violations (DRVs) with route-keepout areas in dense BGA packages. In contrast, curved routing can provide superior signal integrity (SI), but relies on labor-intensive manual design. To address the above issues, this paper proposes CERT, a novel smooth (tangent-continuous) curved escape routing framework for high-speed differential pairs in dense BGA packages. A tailored hexagonal graph model with polyline-to-arc conversion rules is proposed, which guarantees the tangent continuity of curved wires for differential pairs and enables the direct reuse of traditional polyline escape routing algorithms. Experiments show CERT completes routing of the industrial benchmark in 2s (vs. 1 week for manual routing). To the best of our knowledge, this is the first automatic curved escape routing work for differential signals with route-keepout area adaptability.

As semiconductor manufacturing advances toward smaller technology nodes, triple-patterning lithography (TPL) has become indispensable. Existing TPL-aware routers address manufacturability constraints too late, leading to numerous stitches, conflicts, and mask density imbalances. To overcome this, we propose a "shift-TPL-left" strategy that, for the first time, integrates TPL awareness into the track assignment (TA) stage and tightly coordinates it with detailed routing (DR). This approach guides the TPL-aware detailed routing from a more macroscopic level, resulting in faster convergence and fewer DRC violations. Experimental results demonstrate that our method achieves DRC clean in 80% of cases on the ISPD’18 dataset, outperforms the state-of-the-art TPL-aware routing method by 7 × in mask balance score, and achieves a 6 × speedup in runtime.

The use of digital microfluidic biochips (DMFBs) has highlighted their superiority in automatically executing biochemical assays by controlling tiny nano/picoliter droplets, which are moved in parallel to enhance throughput. Routing-based synthesis for DMFBs yields faster assay execution times compared to module-based synthesis when on-chip resource constraints are stringent. However, without predefining modules, it is very challenging to handle all the droplets directly on the chip for successfully executing the desired biochemical assay, especially in dynamic environments. Through modeling routing-based synthesis into two kinds of real-time decision tasks, i.e., transportation and mixing, this paper proposes a new routing-based synthesis framework that uses deep reinforcement learning (DRL) to train transportation and mixing agents respectively. Additionally, we design effective partial observations and curriculum learning (CL) schemes for both kinds of agents to improve their generalization ability and accelerate the training process. Compared to the state-of-the-art heuristic routing-based synthesis methods, more efficient synthesis processes of the given assays can be achieved using the proposed method of combining DRL and CL. For example, the average completion time on several real-world bioassay benchmarks (PCR, INVITRO, and PROTEIN) was reduced by 12.9% 18.5% approximately.

Wirelength is the fundamental metric for VLSI routing. With the advancement of new technologies, wire delay has also become a significant factor for timing performances. It is thus necessary to consider both wirelength and delay in routing tree construction, i.e., timing-driven routing trees. Prior methods propose various heuristics to balance wirelength and delay with a tunable parameter, which cannot compute the full Pareto frontier. In this work, we propose PatLabor, a practical method for timing-driven routing. PatLabor directly optimizes the Pareto set, which obtains tighter Pareto curves than prior methods and does not require parameter tuning. PatLabor obtains all Paretooptimal solutions on small-degree nets up to 9 pins and is theoretically guaranteed by provable time complexity and approximation bounds. Experimental results verify our theoretical findings and show that PatLabor obtains tighter Pareto curves than state-of-the-art methods on ICCAD-15 benchmarks. For example, PatLabor obtains up to 58.5% more Pareto-optimal solutions than prior methods for degree-9 nets.

Coarse-grained reconfigurable architecture (CGRA) has emerged as a promising solution for accelerating computationally intensive applications, particularly in the field of artificial intelligence. One of the primary challenges for CGRA compilers is generating effective mapping results for complex applications within a limited time-frame. This paper presents an enhanced pre-scheduling method that integrates Integer Linear Programming (ILP) and Graph Neural Networks (GNN), along with a corresponding two-stage mapping approach. This combination significantly reduces the search space and accelerates the solution process for mapping problems. Experimental results demonstrate performance improvements ranging from $29.4 \%$ to $406.7 \%$, along with compilation time reductions of up to $1106.8 \times$ compared to existing compilation techniques, as well as excellent scalability.

Triple patterning lithography (TPL) has been recognized as one of the most promising solutions to print critical features in advanced technology nodes. A critical challenge within TPL is the effective assignment of the layout to masks. Recently, various layout decomposition methods and TPL-aware routing methods have been proposed to consider TPL. However, these methods typically result in numerous conflicts and stitches, and are mainly designed for 2-pin nets. This paper proposes a multipin net routing method in triple patterning lithography, called Mr.TPL. Experimental results demonstrate that Mr.TPL reduces color conflicts by 81.17%, decreases stitches by 76.89%, and achieves up to $5.4 \times$ speed improvement compared to the state-of-the-art TPL-aware routing method.

Coarse-Grained Reconfigurable Architectures (CGRAs) have emerged as promising solutions for energyefficient computing in edge devices and datacenter accelerators. While offering substantial performance benefits, their adoption is hindered by the NP-hard loop mapping problem during compilation. In this paper, we present NaviMap, a neuralsymbolic framework combining partial order-aware graph embeddings with deep reinforcement learning. Experimental results demonstrate that NaviMap achieves a$1.95 \times$speedup in solving CGRA mapping problems compared with state-of-the-art methods, while producing mappings with equivalent or superior performance.

Multi-objective optimization problems arise widely in various fields. In practice, multi-objective optimization is generally solved by heuristics with tunable parameters that are highly application-specific. Tuning parameters based on real-world instances (a.k.a. algorithm configuration) are generally empirical without theoretical guarantees. In this work, we establish the theoretical foundation of data-driven multi-objective optimization through the lens of machine learning theory. We provide generalization guarantees on selecting parameters for multi-objective optimization algorithms based on sampled problem instances. Moreover, if the performance metric of the algorithm is the Pareto volume, we can PAC-learn the approximately optimal configuration in polynomial time. We apply our framework to various algorithms, including approximation algorithms, local search, and linear programming. Experiments on multiple problems verify our theoretical findings.

Algorithm configuration, which involves selecting algorithm parameters based on sampled problem instances, is a crucial step in applying modern algorithms such as SAT solvers. Although prior work has attempted to understand the theoretical foundations of algorithm configuration, we still lack a comprehensive understanding of why practical algorithm configurators exhibit strong generalization performances in real-world scenarios. In this paper, through the lens of machine learning theory, we provide an algorithm-dependent generalization bound for the widely used model-based algorithm configurators under mild assumptions. Our approach is based on the algorithmic stability framework for generalization bounds. To the best of our knowledge, this is the first generalization bound that applies to a model closely approximating practical model-based algorithm configurators.

Microfluidic biochips have emerged with significant promise and versatility in automating a variety of biochemical protocols. Accurate preparation of fluid samples with microfluidic mixers is an essential component of these protocols, where concentration prediction and generation are critical. Recently, machine learning models have been adopted in concentration prediction, which demonstrate great potential in enhancing the efficiency and scalability over the traditional finite element analysis (FEA) methods. However, the state-of-the-art machine learning-based method can only predict the concentration of microfluidic mixers with fixed input flow rates, but suffers poor prediction accuracy for multiple input flow rates. To address this issue, this paper proposes a new concentration prediction method based on the graph attention networks (GAT). By modeling each channel of the mixer as a graph node in a GAT, the proposed method efficiently and accurately predicts the generated concentration of random microfluidic mixers with multiple input flow rates. Experimental results show that compared with the state-of-the-art method, the proposed GAT-based simulation method obtains a reduction of 85% in terms of errors of predicted concentration, which validates the effectiveness of the proposed GAT model.

In paper-based digital microfluidic biochips (P-DMFBs), conductive electrodes and control lines are printed on the same side of the photo paper, which introduces a critical design challenge on the so-called control interference issue. This introduces a distinct escape routing problem, named Self-Obstacle Avoiding Escape Routing (SOAER). In the SOAER problem, each electrode has a specific set of routing obstacles of its own, which are forbidden to be crossed over by the control line of the electrode. Based on an enhanced network flow model, this paper proposes an effective SOAER routing method for P-DMFBs. Experimental results show that compared with the state-of-the-art method, SOAER obtains 49x speedup in runtime. Our proposed method also shows the efficiency and effectiveness of the overall system. The success rate is up to 100% and the runtime is decreased significantly.

Ordered escape routing is a critical stage for printed circuit board design. State-of-the-art solutions to ordered escape routing are either heuristic and non-optimal, or trapped in exponential time complexity. In this work, for the first time, we prove that ordered escape routing is not only NP-hard, but also hard to approximate in polynomial time, indicating the limitation of optimal algorithms. We further present NeuroEscape, an efficient ordered escape routing method, which is based on reinforcement learning with a Monte-Carlo tree search (MCTS) and heuristic rollouts for design space exploration. A neural policy model is incorporated to further enhance the MCTS process. Theoretical results show that the number of samples required to train the model is upper bounded by a polynomial. Experimental results show that NeuroEscape solves 69% more testcases, with an average acceleration of 19.4x compared with state-of-the-art methods.

Digital microfluidic biochips (DMFBs) have shown great advantages in automatically executing biochemical protocols through manipulating discrete nano/picoliter droplets which are transported in parallel to achieve high-throughput outcomes. However, because of electrode degradations, the droplet transportation may fail, causing incorrect fluidic operations. To perform safety-critical bio-protocols, the reliability of droplet transportation becomes an utmost concern for DMFBs. It has been shown by the previous works that a reliable transportation policy can be learned using reinforcement learning (RL)-based methods by capturing the underlying health conditions of electrodes and making online decisions. However, previous RL methods may fail to accomplish routing tasks with multiple droplets, because there is a lack of cooperation among different agents (each agent represents one droplet). To deal with this problem and scale RL methods to many droplets, this article proposes a new cooperative centralized learning and distributed execution multiagent RL (MARL) framework for droplet routing in DMFBs using value-decomposition networks (VDNs). Moreover, to speed up the training and decision process as well as apply our method in large biochips, we use a partial observation space where agents can only observe environment in a limited field of view (FOV) centered around themselves. Compared with the state-of-the-art approach, the superior performance of the proposed approach is demonstrated on different DMFBs in terms of success rate and average completion time. We also validate our method on large biochips (e.g.,$\mathbf {50\times 50}$DMFBs) with more droplets than state-of-the-art approach (e.g., ten droplets).

Coarse-grained reconfigurable architectures (CGRAs) are energy-efficient and processing-flexible platforms to perform parallel computation. CGRAs combine the advantages of flexibility of general-purpose processors (GPPs) and energy efficiency of application-specific integrated circuits (ASICs). During the compilation process, the CGRA compiler needs to convert the high-level language codes into a data flow graph, and then map it onto CGRA to generate instruction flow and configuration context. The instruction mapping schemes of the CGRA compiler have a great impact on the efficiency and energy consumption of CGRAs. Furthermore, the quality of the instruction mapping schemes of the CGRA compiler highly depends on how the compiler maps data dependencies using different CGRA resources. This article proposes an enhanced transfer-aware loop mapping method, TAEM 2.0, based on state-of-the-art TAEM algorithm. Based on a parallel iterative IBBMCX algorithm and comprehensive CGRA resources analysis strategy, this method efficiently processes the complex situations of utilizing all those heterogeneous resources on CGRA and significantly accelerates the compilation process. Experimental results show TAEM 2.0 can accelerate the compilation process by$4.40\times $while generating the same or better mapping results on CGRA, when compared to the state-of-art mapping technique.

Recent years have witnessed significant advances brought by microfluidic biochips in automating biochemical processing. Accurate preparation of fluid samples with microfluidic mixers is a fundamental step in various biomedical applications, where concentration prediction and generation are critical. Finite element analysis (FEA) is the most commonly used simulation method for accurate concentration prediction of a given biochip design, such as COMSOL. However, the FEA simulation process is time-consuming with poor scalability for large biochip sizes. This paper proposes a new concentration prediction method based on the graph neural networks (GNN), which efficiently and accurately predicts the generated concentration by random microfluidic mixers of different sizes. Experimental results show that compared with the state-of-the-art method, the proposed GNN-based simulation method obtains a reduction of 88% in terms of errors of predicted concentration, which validates the effectiveness of the proposed GNN model.

Coarse-grained reconfigurable architecture (CGRA) is an emerging hardware architecture, with reconfigurable Processing Elements (PEs) for executing operations efficiently and flexibly. One major challenge for current CGRA compilers is the scalability issue for large loop applications, where valid loop mapping results cannot be obtained in an acceptable time. This paper proposes an enhanced loop mapping method based on Graph Neural Network (GNN), which effectively addresses the scalability issue and generates valid loop mapping results for large applications. Experimental results show that the proposed method enhances the compilation time by 10.8x on average over existing methods, with even better loop mapping solutions.

With the rapid development of deep learning, training big neural network models demands huge amount of computing power.Therefore, many accelerators are designed to meet the performance requirements. Recently, series of Kunlun chips have been released, which claim comparable performance over GPUs. However, there lacks an end-to-end compiler to support both training and inference on Kunlun chip,leaving large performance optimization space to be explored. This paper presents KunlunTVM, the first end-to-end compiler based on TVM, supporting both training and inference tasks on Kunlun Chip. Experimental results show that KunlunTVM achieves up to 5x training performance improvement over the existing framework PaddlePaddle supporting Kunlun chip. It is noteworthy that the proposed methods are general and extensible for the TVM framework targeting different backends.

High-level synthesis (HLS) is widely used for transferring behavior-level specifications into circuit-level implementations. As a critical step in HLS, scheduling arranges the execution order of operations for enhanced performance. However, existing scheduling methods suffer from either exponential runtime or poor quality of solutions. This paper proposes an efficient and effective GNN-based scheduling method called NeuroSchedule, with both fast runtime and enhanced solution quality. Major features are as follows: (1) The learning problem for HLS scheduling is formulated for the first time, and a new machine learning framework is proposed. (2) Pre-training models are adopted to further enhance the scalability for various scheduling problems with different settings. Experimental results show that NeuroSchedule obtains near-optimal solutions while achieving more than 50,000x improvement in runtime compared with the ILP-based scheduling method. At the same time, NeuroSchedule improves the scheduling results by 6.10% on average compared with state-of-the-art entropy-directed method. To the best of our knowledge, this is the first GNN-based scheduling method for HLS.

Programmable microfluidic devices (PMDs) have emerged as a new software-controlled architecture for next-generation flow-based biochips. These devices can be dynamically reconfigured to perform different bioassays flexibly and efficiently owing to their 2-D regularly arranged valve structure. However, PMDs are confronted with critical contamination issues due to the matrix-like structure with intersecting channels. In this article, a block-flushing method is proposed for contamination removal, based on which an overall contamination-aware synthesis flow is proposed. In the proposed block-flushing approach, contaminated areas are first collected according to specific patterns and then flushed as a whole to increase washing efficiency. Then, the synthesis flow integrating the block-flushing method is further optimized such that functional bioassay operations and washing operations can be performed simultaneously for higher efficiency. Experimental results demonstrate that the proposed washing approach reduces the washing time by 28% on commonly used bioassays. Equipped with the proposed washing method, our contamination-aware synthesis flow effectively reduces 30% of the completion time of the bioassays compared with the baseline method.

Escape routing, especially ordered escape routing, is a critical design stage for both printed circuit boards (PCBs) and integrated fan-out (InFO) wafer-level chip-scale packages. Previous works formulate ordered escape routing as boolean satisfiability (SAT) or integer linear programming (ILP) problems. Although optimal routing solutions can be obtained by above-mentioned approaches, the runtime is unacceptable for large-scale designs due to the exponential time complexity of SAT and ILP solvers. In this paper, we first attempt to address ordered escape routing problems with machine learning. We propose a learning-based method to accelerate existing solvers by reducing the solution space of the original problem. The proposed method is flexible, which can be combined with different ordered escape routing algorithms. Specifically, a fully convolutional neural network is trained to predict the probability of each routing grid to be occupied by routing paths. Thus, routing grids with low-probability usage can be removed to reduce the solution space. Experimental results show that the proposed method is effective for both SAT and ILP solvers of ordered escape routing. It achieves an acceleration of 4∼ 370x on average, with a slight increase in the total wirelength. Also, our model has a strong generalization ability. Although it is trained on $10\times 10$ pin array problems, it works well on larger problem sizes such as 14 x 14.

Concentration gradient generation is of great importance for high-throughput drug screening. The classic Christmas tree structure is typically used for generating concentration gradients with uniform distribution. However, the variation in lengths of the outlet channels of the Christmas-tree structure causes serious biases in the generated concentration values. This paper first quantifies the biases in concentration gradients, and then proposes a fast look-up table-based method, along with a further Bayesian Optimization method for tuning the outlet channels of a given Christmas tree in order to enhance the uniformity of the generated concentration gradients. Specifically, the look-up table is based on the kd-tree data structure, and thus is very efficient and effective. Moreover, the table entries are generated by COMSOL simulation, which guarantees the accuracy of the predicted concentration values. Computational simulation results are promising, which verify the effectiveness of the proposed method.

Aided by the advancement of super-conductive materials, rapid single flux quantum (RSFQ) digital circuits are emerging as a promising complement or even replacement of the traditional CMOS digital integrated circuits. RSFQ digital circuits typically work at a low temperature of around 4.2 K, i.e., around −268.95 °C. Nevertheless, the operating frequency of RSFQ digital circuits reaches up to 770 GHz, which is orders of magnitudes faster than contemporary CMOS digital circuits. The high operating frequency causes critical design challenges especially for the clock networks and data path signals, where relative skew on wires need to be observed for achieving the correct functionality. Therefore, for designing a timing-variability-aware SFQ layout, it is necessary to match the PTL delays that are proportional to their respective lengths. And the matching of PTL delays should be carried out by extensions in PTL lengths. To meet the above-mentioned critical timing requirements, it is necessary to incorporate length-matching constraints into a routing problem, which is transformed from the timing requirements of matching the PTL delays during the logical synthesis stage. However, existing routing algorithms are inherently limited by preallocated splitters (SPLs), which complicates the subsequent routing stage under length-matching constraints. In this article, in order to effectively address the length-matching constraints, we reallocate SPLs to fully utilize routing resources. We propose the first multiterminal routing algorithm for RSFQ circuits, which integrates SPL reallocation into the routing stage and achieves 100% routing completion in the tested benchmarks. Compared with the state-of-the-art method, the proposed multiterminal routing algorithm reduces the required area by 17% and the runtime by 7%.

Flow-based microfluidic biochips have attracted much attention in the EDA community due to their miniaturized size and execution efficiency. Previous research, however, still follows the traditional computing model with a dedicated storage unit, which actually becomes a bottleneck of the performance of biochips. In this article, we propose a distributed channel-storage architecture (DCSA) to cache fluid samples inside flow channels temporarily. Since distributed storage can be accessed more efficiently than a dedicated storage unit and channels can switch between the roles of transportation and storage easily, biochips with this architecture can achieve a higher execution efficiency even with fewer resources. Furthermore, we also address the flow-path planning that enables the manipulation of actual fluid transportation/caching on a chip. The simulation results confirm that the execution efficiency of a bioassay can be improved significantly, while the number of valves in the biochip can be reduced accordingly. Also, flow paths for transportation tasks can be constructed and planned automatically with minimum extra resources.

Due to the complexity of human physiology and variability among individuals, e.g., genes, environment, lifestyle exposures, etc., personalized medicine has attracted great interest in the past few years. For synthesizing personalized medicine, it is critical to prepare customized samples with specific concentrations by microfluidic biochips because of the advantages in saving costly reagents and rare samples. The current state-of-the-art of concentration generation for microfluidic biochips is to construct a database by random design methods. However, due to the complex multidimentional parameters such as molecule diameters, inlets, outlets, etc, the whole process is error prone and time consuming. To speedup database construction and reduce the errors in concentration generation, this paper proposes the first transfer learning-based method based on an artificial neural network model (ANN). Given an initial ANN model, transfer learning method can fine-tune weights of ANN to obtain all ANN models needed in the database, which can significantly reduce the amount of required training data. Computational simulation results show that the time for database construction is reduced from several months to 2 days, and the query error is reduced by 83% compared with the existing method.

Coarse-grained reconfigurable architecture (CGRA) is an energy-efficient and processing-flexible parallel computing architecture. Efficiency of CGRA highly depends on how to map data dependencies using different CGRA resources. Previous works investigated different strategies for transferring data dependencies, using registers, processing elements (PEs) and memory. However, these works do not consider all those resources in CGRA and take a long time during compilation period. This paper proposes a Transfer-Aware Effective loop Mapping (TAEM) method for CGRA, which can efficiently utilize all those heterogeneous resources on CGRA and significantly accelerate the compilation time. Experimental results show that TAEM is able to reduce the compilation time by 11.1x over the state-of-the-art technique RAMP, while keeping the same or better performance of loop mapping results.

According to the complexity of human physiology and variability among individuals, e.g., genes, environment, lifestyle exposures, etc., personalized medicine aims to synthesize the specific efficacious drug for each individual patient. For synthesizing personalized medicine, customized solutions with specific concentrations are required. Equipped with the advantages in saving costly reagents and rare samples, microfluidic biochips are promising in generating different concentrations for personalized medicine. On the one hand, digital microfluidic biochips require the programming control for driving the movement of the droplets, which suffer from random errors caused by imbalanced droplet splitting. On the other hand, existing flow-based microfluidic biochips can only generate linear concentration gradients, which cause significant waste for synthesizing personalized medicine. To address the above issues, this article proposes the first artificial neural network (ANN)-based design method for flow-based microfluidic biochips, which accurately generates the customized concentration gradients. According to the required concentration, an initial chip is first selected from the prebuilt database and then fine-tuned by ANN to better match the required concentration. The computational simulation results show that the induced deviations in generated concentrations are generally less than 0.014, which validates the accuracy of the proposed neural network model.

Reliability of the prepared fluidic samples is a major concern for automated sample preparation using microfluidic biochips, where induced errors in the resultant concentration values severely affect the assay outcome. However, the existing design automation techniques have not thoroughly considered the reliability model to reduce the induced concentration errors during sample preparation. This article proposes a fast reliability-aware sample preparation (RASP) method for determining the optimized sequence of mixing steps (mixing process) with the enhanced reliability. In RASP, a probabilistic concentration prediction model is proposed for analyzing the reliability of a given mixing process. Based on this probabilistic model, a lookup table construction algorithm along with the table query method is proposed to obtain the optimized mixing process. The simulation results show that for any user-specified target concentration, RASP can effectively determine the optimized mixing process, which generates the droplets with target concentration within the error tolerance of 0.1%. Compared with the state-of-the-art sample preparation algorithm, RASP improves the reliability-related accuracy by 91.4% on average via 2048 testcases.

Paper-based digital microfluidic biochips (P-DMFBs) have recently emerged as a promising low-cost and fast-responsive platform for biochemical assays. In P-DMFBs, electrodes and control lines are printed on a piece of photograph paper using an inkjet printer and carbon nanotubes (CNTs) conductive ink. Compared with traditional digital microfluidic biochips (DMFBs), P-DMFBs enjoy significant advantages, such as faster in-place fabrication with printer and ink, lower costs, and better disposability. Since electrodes and CNT control lines are printed on the same side of this paper, a critical design challenge for P-DMFB is to prevent control interference between moving droplets and the voltages on CNT control lines. Control interference may result in unexpected droplet movements and thus incorrect assay outputs. To address this design challenge, a control-fluidic codesign methodology is proposed in this paper, along with two demonstrative design flows integrating both fluidic design and control design, i.e., the droplet-oriented codesign flow and the electrode-oriented codesign flow. The droplet-oriented flow is suitable for designing biochips with sparse electrodes and relatively larger number of droplets, whereas the electrode-oriented flow is suitable for biochips with dense electrodes and smaller number of droplets. The computational simulation results of real-life bioassays demonstrate the effectiveness of the proposed codesign flows.

In high-throughput drug screening applications, as manual drug sample delivery is time-consuming and error-prone, there is an urgent need for accurate and efficient drug sample delivery biochip for large-scale microwell arrays. This paper proposes a new microfluidic biochip architecture, where drugs are automatically prepared with different concentration values, and then delivered into multiple microwells. For large-scale drug sample delivery biochips, the routing of drug sample delivery channels is a very challenging task without effective routing solutions. This paper proposes an ultrafast rule-based escape routing method, called URBER, to address the large-scale routing of drug sample delivery channels, which scales well in both runtime and memory even for a very large problem size. URBER runs very fast because it routes channels based on a set of predefined rules, which avoids runtime consumed in solution space exploration. All benchmarks for 30 ≤ N, M ≤ 100 have been tested, where N and M are the number of columns and rows of the terminal array. Among these benchmarks, about ~91.9% are routed with optimal solutions, and the runtime is order of magnitudes faster than optimal min-cost flow-based methods (speedup is from ~600 to ~340 k). Specifically, for all benchmarks with (M/N) E ((3/4), (4/3)), optimal routing solutions are always obtained. URBER also shows promise of routing large-scale designs with up to 500 k terminals efficiently.

Flow-based microfluidic biochips are one of the most promising platforms used in biochemical and pharmaceutical laboratories due to their high efficiency and low costs. Inside such a chip, fluids of nanoliter volumes are transported between devices for various operations, such as mixing and detection. The transportation channels and corresponding operation devices are controlled by microvalves driven by external pressure sources. Since assigning an independent pressure source to every microvalve would be impractical due to high costs and limited system dimensions, states of microvalves are switched by a control logic using time multiplexing. Existing control-logic designs, however, still switch only a single control channel per operation, leading to a low efficiency. In this article, we present the first automatic synthesis approach for a control logic that is able to switch multiple control channels simultaneously. Moreover, we propose the first fault-aware design in control logic by introducing backup control paths to maintain the correct function even when manufacturing defects occur. The construction of control logic is achieved by a highly efficient framework based on particle swarm optimization, Boolean logic simplification, grid routing, together with mixing multiplexing. The simulation results demonstrate that the proposed multichannel switching mechanism leads to fewer valve-switching times and lower total logic cost, while realizing fault tolerance for all control channels.

Thin-film transistor (TFT) circuits are important for flexible electronics which are promising in the area of wearable devices and Internet of Things. However, most flexible TFT technologies only have unipolar devices and the process variation and defective rate are relatively high, which impose challenges to TFT circuit design. In this paper, we propose a novel logic array design based on pseudo-CMOS logic to address the problems of unipolar TFT circuit design. A multilayer interconnection architecture is presented to improve the routability of circuit and the area efficiency. Cell mapping and wire routing algorithms, which aim to map the logic gates of circuit to logic array and then route the interconnection wires, are devised to improve the performance of circuit in consideration of parameter variations of TFT and meanwhile enhance the routability. The experimental results show that the proposed logic array along with design methodologies can reduce more than 80% area compared with transistor level scheme and help to improve performance significantly.

Continuous flow-based biochips are one of the promising platforms used in biochemical and pharmaceutical laboratories due to their efficiency and low costs. Inside such a chip, fluid volumes of nanoliter size are transported between devices for various operations, such as mixing and detection. The transportation channels and corresponding operation devices are controlled by microvalves driven by external pressure sources. Since assigning an independent pressure source to every microvalve would be impractical due to high costs and limited system dimensions, states of microvalves are switched using a control logic by time multiplexing. Existing control logic designs, however, still switch only a single control channel per operation – leading to a low efficiency. In this paper, we propose the first automatic synthesis approach for a control logic that is able to switch multiple control channels simultaneously to reduce the overall switching time of valve states. In addition, we propose the first fault-aware design in control logic to introduce redundant control paths to maintain the correct function even when manufacturing defects occur. Compared with the existing direct connection method, the proposed multi-channel switching mechanism can reduce the switching time of valve states by up to 64%. In addition, all control paths for fault tolerance have been realized.

Digital microfluidic biochips (DMFBs) have become popular in the healthcare industry recently because of its lowcost, high-throughput, and portability. Users can execute the experiments on biochips with high resolution, and the biochips market therefore grows significantly. However, malicious attackers exploit Intellectual Property (IP) piracy and Trojan attacks to gain illegal profits. The conventional approaches present defense mechanisms that target either IP piracy or Trojan attacks. In practical, DMFBs may suffer from the threat of being attacked by these two attacks at the same time. This paper presents a comprehensive security system to protect DMFBs from IP piracy and Trojan attacks. We propose an authentication mechanism to protect IP and detect errors caused by Trojans with CCD cameras. By our security system, we could generate secret keys for authentication and determine whether the bioassay is under the IP piracy and Trojan attacks. Experimental results demonstrate the efficacy of our security system without overhead of the bioassay completion time.

Flow-based microfluidic biochips are attracting increasing attention with successful applications in biochemical experiments, point-of-care diagnosis, etc. Existing works in design automation consider the flow-layer design and control-layer design separately, lacking a global optimization and hence resulting in degraded routability and reliability. This paper presents a novel integrated physical co-design methodology, which seamlessly integrates the flow-layer and control-layer design stages. In the flow-layer design stage, a sequence-pair-based placement method is presented, which allows for an iterative placement refinement based on routing feedbacks. In the control-layer design stage, the minimum cost flow formulation is adopted to further improve the routability. Besides that, effective placement adjustment strategies are proposed to iteratively enhance the solution quality of the overall control-layer design. Experimental results show that compared with the existing work, the proposed design flow obtains an average reduction of 40.44% in flow-channel crossings, 31.95% in total chip area, and 22.02% in total flow-channel length. Moreover, all the valves are successfully routed in the control-layer design stage.

Flow-based microfluidic biochips are promising with significant applications for automating and miniaturizing laboratory procedures in biochemistry. Automated design methods for flow-based microfluidic biochips are becoming increasingly important due to the advancement in both integration scale and design complexity for complicated biochemical applications. Though the multilayer soft lithography fabrication provides flexibility to route both flow and control channels in any angle, existing routing algorithms still adopt Manhattan routing metrics, which design channel in either vertical or horizontal direction only. Moreover, based on the computational fluid dynamics analysis, rectilinear channels with 90° bends have the following issues: 1) reduced the fluidic flow rate, which degrades the performance of the biochip and may even result in the erroneous outcome of the whole procedure and 2) increased pressure at the right-angle bend, which negatively affects the reliability of the biochip. To fully utilize the routing flexibility, this paper proposes the first any-angle routing algorithm for flow-based microfluidic biochip, called AARF. Computational simulation results show that compared with traditional Manhattan routing method, the proposed AARF significantly improves the total wirelength and total effective wirelength (considering the turning angles) by 17.11% and 35.91%, respectively, which prove the effectiveness of the AARF routing flow.

The exponential increase in scale and complexity of very large-scale integrated circuits (VLSIs) poses a great challenge to current electronic design automation (EDA) techniques. As an essential step in the whole EDA layout synthesis, placement is attracting more and more attention, especially for analog and mixed-signal integrated circuits. Recently, experts in this field have observed a variety of analog-specific layout constraints to obtain high-performance placement solutions. These constraints include symmetry, alignment, boundary, preplace, abutment, range and maximum separation, and routability of the placement solutions. In this article, the effectiveness of slicing and nonslicing representation is investigated. Additionally, the technique of congestion-based virtual sizing is proposed. Experimental results show that the routability can be improved significantly by applying congestion-based virtual sizing. Results also show that the slicing representation can improve the regularity of the placement solutions and hence improve the routability with higher efficiency compared to the nonslicing representation.

Continuous-flow microfluidics rapidly evolved in the last decades as a solution to automate laboratory procedures in molecular biology and biochemistry. Therefore, the physical design of the corresponding chips, i.e., the placement and routing of the involved components and channels, received significant attention. Recently, several physical design solutions for this task have been presented. However, they often rely on general heuristics which traverse the search space in a rather arbitrary fashion and, additionally, consider placement and routing independently from each other. Consequently, the obtained results are often far from being optimal. In this work, a methodology is proposed which aims for determining close-to-optimal physical designs for continuous-flow microfluidic biochips. To this end, we consider all - or, at least, as much as possible - of the valid solutions. As this obviously yields a significant complexity, solving engines are utilized to efficiently traverse the search space and pruning schemes are proposed to reduce the search space without discarding too many promising solutions. Evaluations show that the proposed methodology is capable of determining optimal results for small experiments to be realized. For larger experiments, close-to-optimal results can efficiently be derived. Moreover, compared to the current state-of-the-art, improvements of up to 1-2 orders of magnitude can be observed.

Flow-based microfluidic biochips have progressed significantly in the past decade. Thanks to innovations in multilayer soft lithography (MSL) fabrication technology, the integration of thousands of microvalves along with large-scale networks of microchannels on a chip has been enabled. This progress has even been compared to the evolution of VLSI circuits following Moore's Law. In flow-based microfluidic biochips, microvalves are critical components to control the fluidic transportation for complex operations. To activate the open/close states of a microvalve, off-chip control pins are required. Due to the tremendous increase of the number of microvalves, a software-programmable microfluidic platform has been proposed to reduce the number of off-chip control pins, which integrates a microfluidic multiplexer on a separate control layer to control the array of microvalves. The multiplexer needs to be switched when the states of microvalves are changed between every two adjacent time slots. High switching frequency will make the multiplexer vulnerable and decrease the chip's reliability. We observe that different switching orders of microvalves lead to different switching frequencies of a multiplexer. Based on this observation, this paper proposes the first Hamming-distance-based switching order optimization method for microvalves to enhance the reliability of the multiplexer. Experimental results show that our method can significantly reduce the switching frequency of multiplexer, and the solution is very close to the theoretical optimal lower bound.

Flow-based microfluidic biochips have attracted much attention in the EDA community due to their miniaturized size and execution efficiency. Previous research, however, still follows the traditional computing model with a dedicated storage unit, which actually becomes a bottleneck of the performance of biochips. In this paper, we propose the first architectural synthesis framework considering distributed storage constructed temporarily from transportation channels to cache fluid samples. Since distributed storage can be accessed more efficiently than a dedicated storage unit and channels can switch between the roles of transportation and storage easily, biochips with this distributed computing architecture can achieve a higher execution efficiency even with fewer resources. Experimental results confirm that the execution efficiency of a bioassay can be improved by up to 28% while the number of valves in the biochip can be reduced effectively.

Thin-film transistor (TFT) circuits are important for flexible electronics which are promising in the area of wearable devices. However, most TFT technologies only have unipolar devices and the process variation and defective rate are relatively high, which impose challenges to TFT circuit design. In this paper, we propose a novel logic array based on pseudo-CMOS logic to address the problem of unipolar TFT circuit design. A multi-layer interconnect architecture and wire routing methodology are presented to improve the routability and meanwhile the area efficiency. The experimental results show that the proposed logic array reduces more than 80% area compared with transistor level scheme.

Existing sample preparation algorithms are either based on NP-style problem formulations, e.g., using integer linear programming (ILP), which runs very slowly, or based on heuristic algorithms, which cannot obtain optimal solutions regarding different objectives. This paper proposes the first online sample preparation algorithm based on the lookup table method, named LUTOSAP. LUTOSAP enables fast query response for online sample preparation requirements with the solution where the weighted sum of sample consumption, buffer consumption, and the number of mix-split operations is optimized. Experimental results show that LUTOSAP obtains optimal sample preparation solutions in microseconds within the accuracy tolerance of $0.2\%$ for both single and double concentration values, which is orders of magnitude faster than existing algorithms. For multiple concentration values, the multiple-target sample preparation algorithm in LUTOSAP obtains near-optimal solution based on the constructed lookup table in microseconds, which well meets the critical fast-response requirements in online sample preparation.

Flow-based microfluidic biochips are attracting increasing attention with successful applications in lab-on-a-chip experiments and point-of-care diagnosis. Physical design for flow-based biochips determines the number of flow-channel intersections, and thus affects the number of microvalves. As reducing microvalves will significantly improve the overall design quality and reliability, physical design is of great importance. Typically, physical design consists of two major stages, i.e., component placement and routing. Existing works follow the step-by-step scheme, which perform placement and routing separately. The lack of interactions between the two design stages results in degraded design with large number of unfavorable channel intersections and microvalves. This paper presents a novel placement and routing method based on the sequence-pair representation, which seamlessly integrates placement and routing stages and allows iterative placement adjustment upon routing feedbacks. Experimental results show that compared with the existing work, the proposed method obtains average 54.10% improvement in flow-channel crossings, 42.15% improvement in total chip area, and 23.43% improvement in total channel length.

Paper-based digital microfluidic biochips (P-DMFBs) have recently emerged as a promising low-cost and fast-responsive platform for biochemical assays. In P-DMFBs, electrodes and control lines are printed on a piece of photo paper using inkjet printer and conductive ink of carbon nanotubes (CNTs). Compared with traditional digital microfluidic biochips (DMFBs), P-DMFBs enjoy notable advantages, such as faster in-place fabrication with printer and ink, lower costs, better disposability, etc. Because electrodes and CNT control lines are printed on the same side of a paper, a new design challenge for P-DMFB is to prevent the interference between moving droplets and the voltages on CNT control lines. These interactions may result in unexpected droplet movements and thus incorrect assay outputs. To address the new challenges in automated design of P-DMFBs, this paper proposes the first control-fluidic codesign flow, which simultaneously adjusts the control line routing and fluidic droplet scheduling to achieve an optimized solution. As the control line routing may not be able to address all the interferences between moving droplets and the voltages on control lines, droplet rescheduling is performed to effectively deal with the remaining interferences in the routing solution. Computational simulation results on real-life bioassays show that the proposed codesign method successfully eliminates all the interferences, while a state-of-the-art maze routing method cannot solve any of the benchmarks without conflicts.

Digital microfluidic biochips (DMFBs) are gaining increasing attention with promising applications for automating and miniaturizing laboratory procedures in biochemistry. In DMFBs, cross-contamination of droplets with different biomolecules is a major issue, which causes significant errors in bioassays. Washing operations are introduced to clean the cross-contamination spots. However, existing works have oversimplified assumptions on the washing behavior, which either assume infinite washing capacity, or ignore the routing conflicts between functional and washing droplets. This paper proposes the first integrated functional and washing droplet routing flow, which considers practical issues including the finite washing capacity constraint, and the routing conflicts between functional and washing droplets. Washing droplets of different sizes are also proposed to wash the congested cross-contamination spots. Effectiveness of the proposed method is validated by real-life biochemical applications.

In flow-based microfluidic biochips, microvalves on the control layer need to be connected to control pins via control channels. In application-specific and portable microfluidic devices, critical microvalves need to switch at the same time for correct functionality. Those microvalves are required to have equal or similar channel lengths to the control pin, so that the control signal can reach them simultaneously. This paper presents a practical control-layer routing flow (PACOR) considering the critical length-matching constraint. Major features of PACOR include: (1) effective candidate Steiner tree construction and selection methods for multiple microvalves based on the deferred-merge embedding (DME) algorithm and maximum weight clique problem (MWCP) formulation, (2) minimum cost flow-based formulation for simultaneous escape routing for improved routability, and (3) minimum-length bounded routing method to detour paths for length matching. Computational simulation results show effectiveness and efficiency of PACOR with promising matching results and 100% routing completion rate.

The chip-level design problem is critical in pin-constrained electrowetting-on-dielectric (EWOD) biochips, which not only affects the number of control pins and PCB routing layers from the manufacturing cost point of view, but also determines the functional reliability induced by excessive applied voltage. Existing works either greedily minimize the number of control pins with degraded routability, or disregard the differences in driving voltages on the electrodes, where the trapped charge due to excessive applied voltage causes significant reliability issue. This paper presents the first SVM-based classifier for electrode addressing in chip-level design stage, which simultaneously optimizes the number of control pins, routability, as well as reliability. Experimental results on both real-life chips and synthesized benchmarks show that, compared with the state-of-the-art method, the SVM-based electrode addressing method obtains significant improvements in both routability and reliability.

As VLSI technology continuously scales down, buffered clock tree synthesis (CTS) has become increasingly critical in an attempt to generate a high-performance synchronous chip design. This paper presents a novel obstacle-avoiding CTS approach with slew constraints satisfied and signal polarity corrected. We build a look-up table through NGSPICE simulation to achieve accurate buffer delay and slew, which guarantees that the final skew after NGSPICE simulation is as satisfactory as expected. Aiming at skew optimization under constraints of slew and obstacles, our CTS approach features the clock tree construction stage with the obstacle-aware topology generation algorithm called OBB, balanced insertion of candidate buffer positions and a fast heuristic buffer insertion algorithm. With an overall view on obstacles to explore the global optimization space, our CTS approach effectively overcomes the negative influence on skew brought by the obstacles. Experimental results show the effectiveness of our CTS approach with significantly improved skew and latency by 69.0% and 72.0% on average. In addition, the accuracy of the look-up table is demonstrated through the huge skew reduction by 87.3% on average. Moreover, our OBB heuristic algorithm obtains 53.2% improvement in skew than the classic balanced bipartition algorithm.

In digital microfluidic biochips, cross-contamination of different biomolecule droplets is a major issue. Washing operations are introduced to clean the cross-contamination sites. Existing works have oversimplified assumptions on the washing behavior, which either assume unrealistic infinite washing capacity, or ignore the execution time constraint and/or the routing conflicts between functional and washing droplets. This paper presents the first practical droplet routing flow, which considers realistic issues including the finite washing capacity constraint, and the routing conflicts between washing and functional droplets. Effectiveness of the presented method are validated by real-life biochemical applications.

Enabled by the heterogeneous integration in modern System-On-Chips (SOCs), the design automation for analog and mixed signal circuit components in SOCs is attracting increasing interests. Matching constraints for specific analog signals are critical for correct functionalities. This paper presents a novel single-layer detailed routing algorithm with the length matching constraint, called LEMAR. LEMAR features an innovative routing model for partitioning the routing layout for wire detouring, effective detouring patterns according to the geometric shapes of the partitioned tiles, an enhanced A*-search algorithm along with the backtrack technique for finding the routing path, and an iterative rip-up and reroute procedure for finding the feasible routing solution with the matching constraint. Experimental results are promising and show that LEMAR is both effective and efficient.

Buered clock tree synthesis (CTS) is increasingly critical as VLSI technology continually scales down. Many researches have been done on this topic due to its key role in CTS, but current approaches either lack the obstacle-avoiding functionality or lead to large clock latency and/or skew. This paper presents a new obstacle-avoiding CTS approach with separate clock tree construction and buer insertion stages based on an integral view to explore the global optimization space. Aiming at skew optimization under constraints of slew and obstacles, our CTS approach features the clock tree construction stage with the obstacle-aware topology generation algorithm called OBB, balanced insertion of candidate buer positions, and a fast heuristic buer insertion algorithm. Experimental results show the eectiveness of our CTS approach with significantly improved skew and latency than [6] by 46% and 63% on average, and 15.3% reduction in skew than [5]. Our OBB heuristic obtains 36% improvement in skew than the classic balanced bipartition algorithm (BB) in [10].

As analog and mixed-signal (AMS) circuitry gains increasing portions in modern SoCs, automotive analog routing is becoming more and more important. This paper presents a fast real-time interactive analog router called SIAR based on a splitting graph. A key feature is that SIAR allows real-time interactions between the router and the designer. The designer can try different guiding points by moving the cursor in the user window and the router will show the corresponding routing solutions in real-time for the designer to select the most satisfactory one. To enable real-time interactions, we present a new splitting graph to represent the routing area, which greatly enhances the routing efficiency. Different design rules such as variable wire and via width/spacing are supported by the router. Moreover, SIAR supports different routing modes such as point-to-point, point-to-module and module-to-module. Experimental results show that SIAR obtains promising routing efficiency with upto 28.6x speedup and better routing solutions compared with the commercial router Laker as well as upto 108x speedup compared with a modified implication-graph-based gridless routing approach [13].

Analog signals are more sensitive to crosstalk than digital signals, resulting in instability of analog circuits. To eliminate coupling, it is common practice to insert shielding wires on one or both sides of critical signals. In this paper, a novel analog circuit shielding routing algorithm based on net classification is proposed. Circuit performance requirements are transformed into geometric properties of nets according to the result of placement, and different shielding wire routing algorithms are designed to meet these geometric properties. A* algorithm is adopted to route the critical nets, and shielding wires are added at the same time. Maze algorithm is used to route the P/G nets and other general nets. Experimental results show that the router is efficient in routing and effective in reducing crosstalk. Although capacitive load and routing area increase, the resulting coupling is negligible and the circuit performance is significantly improved.

In sub-100nm CMOS processes, delay and leakage power reduction continue to be among the most critical design concerns. We propose to exploit the recent availability of fine-grain exposure dose control in the step-and-scan tool to achieve both design-time (placement) and manufacturing-time (yield-aware dose mapping) optimizations of timing yield and leakage power. Our placement and dose map co-optimization can improve both timing yield and leakage power of a given design. We formulate the placement-aware dose map optimization as quadratic and quadratic constraint programs which are solved using efficient quadratic program solvers. In this paper, we mainly focus on the placement-aware dose map optimization problem; in the Appendix, we describe a complementary but less impactful dose map-aware placement optimization based on an efficient cell swapping heuristic. Experimental results show noticeable improvements in minimum cycle time without leakage power increase, or in leakage power reduction without degradation of circuit performance.

In double patterning lithography (DPL) layout decomposition for 45 nm and below process nodes, two features must be assigned opposite colors (corresponding to different exposures) if their spacing is less than theminimum coloring spacing. However, there exist pattern configurations for which pattern features separated by less than the minimum coloring spacing cannot be assigned different colors. In such cases, DPL requires that a layout feature be split into two parts. We address this problem using two layout decomposition approaches based on aconflict graph. First, node splitting is performed at all feasible dividing points. Then, one approach detects conflict cycles in the graph which are unresolvable for DPL coloring, and determines the coloring solution for the remaining nodes using integer linear programming (ILP). The other approach, based on a different ILP problem formulation, deletes some edges in the graph to make it two-colorable, then finds the coloring solution in the new graph. We evaluate our methods on both real and artificial 45 nm testcases. Experimental results show that our proposed layout decomposition approaches effectively decompose given layouts to satisfy the key goals of minimized line-ends and maximized overlap margin. There are no design rule violations in the final decomposed layout.

In sub-100nm CMOS processes, delay and leakage power reduction continue to be among the most critical design concerns. We propose to exploit the recent availability of fine-grain exposure dose control in the stepper to achieve both design-time (placement) and manufacturing-time (yield-aware dose mapping) optimizations of timing yield and leakage power. Our placement and dose map co-optimization can simultaneously improve both timing yield and leakage power of a given design. We formulate the placement-aware dose map optimization as a quadratic program, and solve it using an efficient quadratic programming solver. In this paper, we mainly focus on the placement-aware dose map optimization problem; in the Appendix, we describe the complementary but less impactful dose map-aware placement optimization, and an efficient cell swapping heuristic. Experimental results are promising: with typical 90nm stepper (ASML Dose Mapper) parameters, we achieve more than 8% improvement in minimum cycle time of the circuit without any leakage power degradation.

In double patterning lithography (DPL) layout decomposition for 45nm and below process nodes, two features must be assigned opposite colors (corresponding to different exposures) if their spacing is less than the minimum coloring spacing [11, 9, 5]. However, there exist pattern configurations for which pattern features separated by less than the minimum color spacing cannot be assigned different colors. In such cases, DPL requires that a layout feature be split into two parts. We address this problem using a layout decomposition algorithm that includes graph construction, conflict cycle detection, and node splitting processes. We evaluate our technique on both real-world and artificially generated testcases in 45nm technology. Experimental results show that our proposed layout decomposition method effectively decomposes given layouts to satisfy the key goals of minimized line-ends and maximized overlap margin. There are no design rule violations in the final decomposed layout.

In current manufacturing processes, certain layout configurations are likely to have reduced yield and/or reliability due to increased susceptibility to stress effects or poor tolerance to certain processes like lithography. These problematic layout configurations need to be efficiently detected and eliminated from a design layout to enable better yield. In this paper, such layout configurations are called processhotspots and an efficient and scalable algorithm is proposed to detect such process-hotspots in a given layout.

This paper presents a novel W-shape multilevel full-chip routing framework. The framework features the W-shape optimization flow. The first V-shape flow aims to optimize the global routing solution. And the second V-shape flow intends to improve the quality of the detailed routing result. The framework is tested on a set of commonly used benchmark circuits and compared with the previous multilevel routing systems. The experimental results are promising.

This paper presents an improved multilevel Full-chip routing system which integrates global routing and detailed routing algorithms to achieve great enhancement in yield and reliability considering the redundant via placement. The system features a pre-coarsening stage which is equipped with a fast congestion-driven L-pattern global routing followed by the rvia-driven detailed routing. The L-pattern global routing benefits a lot to the reduction of vias and thus relieves the burden of redundant via addition. Then the rvia-driven maze routing algorithm considers the addition of redundant vias during routing. Finally the redundant via placement heuristic also contributes to improve the completion rate. We have tested the system on a set of commonly used benchmark circuits and compared the results with a previous multilevel routing framework. The experimental results are promising.