The emergence of back-side interconnects aims to sustain the continued scaling of semiconductor technology. To extend existing back-end tools, netlist planning has been introduced to transform single-sided netlists into double-sided ones, thereby exploring the potential of utilizing bridging cells for double-sided signal routing. However, the lack of a native double-sided routing approach that fully leverages both front-side and back-side resources hinders the effective handling of complex systematic requirements. In light of this, we propose a native double-sided signal routing approach DSR for the first time, which realizes efficient cross-layer path selection in 3D routing space by unified modeling of front-side and back-side resources. We develop a native double-sided global routing algorithm that jointly considers resource allocation and bridging cell insertion, guided by delay models for performance optimization. Under the guidance of global routing, we further extend the double-sided routing graph and incorporate delay-aware mechanisms to enhance resource allocation and routing quality in detailed routing. Experimental results demonstrate that, compared with existing works, the proposed approach achieves significant improvements in delay and runtime, while maintaining wirelength and eliminating Design Rule Violations (DRVs).

Fully programmable valve array (FPVA) biochips have emerged as a next-generation platform for flow-based microfluidics, offering high flexibility and programmability for executing complex bioassays. However, physical faults such as channel blockage and leakage are inevitable during chip manufacturing and operation, and the widely adopted single-port architecture in existing research serializes fluid injection, severely limiting throughput and fault-tolerant routing quality under large-scale conditions. To address this challenge, this paper proposes MP-FTRouter, a fault-tolerant routing algorithm for multi-port FPVA using deep reinforcement learning. The proposed algorithm introduces a multi-port flow-layer architecture to alleviate the serialization bottleneck of single-port designs, and models the concurrent routing process as a Markov decision process. By combining value decomposition networks with double deep Q-networks, MP-FTRouter achieves conflict avoidance and path optimization under fault constraints through staged concurrent batch generation and multi-agent cooperative decision-making. Experimental results on large-scale benchmarks demonstrate that, compared with existing work, the proposed algorithm reduces the completion time of bioassays by an average of 40.6%, the total length of flow paths by an average of 47.8%, and improves the fault-tolerance success rate by 6%.

With the widespread application of distributed supply chains in the field of microfluidic biochips, significant improvements have been made in the design, manufacturing, and application efficiency of biochips. However, this model also introduces new security risks, as malicious attackers could tamper with biochemical protocols at any stage of the supply chain, leading to experimental failures. To this end, we propose an automated anomaly detection method for biochemical protocols in continuous-flow microfluidic biochips for the first time. On one hand, we propose a preprocessing method for watermark embedding in biochemical protocols, which performs abstract modeling of biochemical protocols to calculate the variable bit range of protocol parameters, thereby providing necessary preprocessing support for subsequent watermark embedding. On the other hand, we propose an optimization method for watermark embedding in biochemical protocols, which integrates the design of a weighted loss function based on attribute importance with the selection of watermark embedding positions based on simulated annealing to determine the optimal embedding position, thereby ensuring the robustness of watermark embedding. Experimental results on multiple benchmarks indicate that the proposed method can efficiently realize the abnormal detection of biochemical protocols and has high detection probability and strong robustness.

Continuous-flow microfluidic biochips (CFMBs) are advanced platforms that precisely manipulate fluids through micron-scale channels and have been widely applied in biomedical research and disease diagnostics. Their internal architecture typically employs multiplexer-based control logic, where control channels transmit input signals to flow valves to dynamically switch fluid paths and achieve precise control. However, the reuse and elimination operations of control channels introduce a large number of L-shaped structures. These structures are prone to channel deformation and, under high-frequency usage, can accelerate structural fatigue, thereby reducing the reliability of the control logic. In addition, improper control channel reuse may lead to signal conflicts and interference. To address these problems, we propose a control logic architecture design approach for CFMBs that simultaneously considers channel length and straightness. First, we propose a placement preprocessing strategy that integrates a heuristic initialization with a critical-path-first approach to improve the quality of the initial placement and ensure feasibility. Second, we design a placement algorithm based on discrete particle swarm optimization with a twin-swarm cooperative mechanism, which effectively explores better placement solutions through cooperative search between the two swarms and feedback from routing results. Finally, we propose a two-stage routing algorithm that integrates error recovery and reuse constraints. By incorporating straightened routing and reasonable reuse, this algorithm significantly reduces channel length and the number of bends while ensuring the correctness of the control logic. Experimental results demonstrate that the proposed approach enables reliable control of flow valves with fewer resources and effectively reduces signal propagation delay in control channels, significantly enhancing the overall performance and reliability of the control logic.

Very large scale integration (VLSI) circuits typically consist of millions of nets, posing significant challenges for efficient physical design. Interconnect delay has become a critical factor for timing performance in technology nodes at 5nm and beyond. Additionally, the coupling effect among the wires increases the complexity of delay optimization. Moreover, tapering constraints are essential in advanced technology nodes to ensure manufacturability. Furthermore, the ever-increasing scale of modern designs necessitates a high-performance computing (HPC) framework to accelerate delay-driven layer assignment in advanced technology nodes. To address these challenges, we propose ParDelay, a parallel delay-driven layer assignment leveraging hierarchical task graph modeling while considering tapering constraints for advanced technology nodes, which includes the following five key techniques: 1) A general deterministic parallel framework is proposed for delay-driven layer assignment, leveraging a hierarchical task graph to enable both internet and inter-node parallelism. 2) A delay- and overflow-driven tapering repairing strategy is proposed to eliminate tapering violations while further optimizing net delay. 3) A local delay-critical net filtering method is proposed to analyze local delay criticality to guide layer assignment, thereby minimizing delay while eliminating overflow. 4) To mitigate the coupling effect, we propose a net shielding algorithm that reduces wire density for maximum delay candidate nets to optimize maximum delay. 5) A delay-aware refinement strategy is proposed to classify nets by their delay rank and assign distinct non-default-rule (NDR) wire permissions and refinement objectives, thereby reducing delay. Experimental results demonstrate that, compared to existing layer assignment algorithms and parallel routing frameworks, our approach effectively reduces delay, via count, and runtime under the tapering constraints.

Deep learning has emerged as the predominant technique for predicting routability in Very-Large-Scale-Integrated (VLSI) circuits. However, it often struggles to generalize to various tasks and performs poorly when addressing inherent data imbalance issues in electronic design automation. Overcoming these challenges typically requires retraining or fine-tuning models, which poses significant difficulties for chip engineers who lack resources and expertise in neural network training. In light of this, we propose and address the universal problem of routability prediction for the first time. By framing this issue as a meta-learning scenario, we propose a Few-Shot Learning (FSL)-based approach, URoute, which adapts flexibly to new tasks by utilizing features of the query chip and labeled examples without additional training. To tackle the data imbalance problem, we further propose a meta-learning strategy based on importance sampling to optimize the model training process. To validate the generality and adaptability of URoute, we construct an FSL dataset based on CircuitNet and ISPD2015 datasets. Experimental results demonstrate that URoute exhibits greater robustness and flexibility compared to existing methods when handling unseen routability prediction tasks, achieving competitive results.

With the increasing integration level of flow-based microfluidics, fully programmable valve arrays (FPVAs) have emerged as the next generation of flow-based microfluidic devices. Microvalves in an FPVA are typically managed by a control logic, where valves are connected to a core input via control channels to receive control signals that guide their state switchings. When executing bioassays using an FPVA, however, some valves need to be switched synchronously at different time points, so that both fluid transportation and biochemical operations can be executed correctly. Consequently, the channel lengths from the core input to these valves must be equal, which poses a big challenge to the channel routing of the control logic. To solve this problem, we propose a deep reinforcement learning-based adaptive routing flow for the control logic of FPVAs. With the proposed routing flow, an efficient control-channel network can be automatically constructed to realize accurate control signal propagation. Meanwhile, timing skews among synchronized valves and the total length of control channels are minimized simultaneously, thus generating an optimized control logic with excellent timing performance. Furthermore, by introducing backups of identified critical valves and flexible routing of backup paths without restrictions on control valve locations, a novel fault-tolerant design method considering length matching is implemented to efficiently improve the reliability of the control logic. Simulation results on multiple benchmarks demonstrate that the proposed routing flow leads to control logics with accurate valve synchronization, low cost, and high reliability.

Traffic flow prediction is crucial to intelligent transportation systems (ITSs). However, the existing methods usually ignore the problem that the prediction difficulty of nodes in the traffic network is actually different. Besides, they fail to effectively handle the dilution of the original semantic information passed layer by layer when capturing the global dependency. To address these issues, this article proposes a curriculum learning guided spatial–temporal network (CurST-Net). Inspired by the human learning process, CurST-Net introduces a curriculum learning (CL) module that defines four metrics from multiple views to evaluate node difficulty and uses a training scheduler (TNS) to gradually introduce easy-to-difficult training nodes to the model to improve prediction ability. Moreover, we design a global spatial–temporal encoder that uses a multihead spatial–temporal attention mechanism and performs interlayer residual scaling on the original semantic information to efficiently capture the global spatial–temporal correlation of nodes. To the best of our knowledge, this is the first work that uses CL to solve the varying prediction difficulty of nodes in traffic flow prediction. The effectiveness of our model is validated through extensive experiments with 12 baseline models on three real-world traffic datasets. For the 1-h prediction horizon, the MAE values of our model on the three datasets are 15.19, 19.22, and 15.50, respectively. Our method yields an overall reduction of 6.51% in MAE across all three datasets compared to DSTAGNN, an advanced traffic flow prediction method. Additionally, the inference time on the PEMSD8 dataset is 5.44 s, requiring only 45% of the inference time of DSTAGNN, which demonstrates a significant improvement in inference speed.

The track assignment has been introduced between global routing and detail routing. Based on the independence and divisibility of track assignment, we propose a GPU-accelerated parallel track assignment algorithm. To estimate routability more accurately, the proposed algorithm simultaneously considers global and local nets, and incorporates several strategies for optimization. Moreover, an asynchronous parallelism strategy is proposed to divide the computation of routing resources and the track assignment into fine-grained tasks. Experimental results show that, compared to related work, our algorithm achieves a significant speedup with a better routability estimation.

Escape routing is a critical problem in PCB routing, and its quality dramatically affects the cost of the PCB design. Unlike the traditional escape routing that works mainly for the BGA with unique line width and space, this paper presents a high-performance escape routing algorithm to handle problems with variable design rules and multiple constraints. We first propose a novel obstacle-avoiding method to project pins to the boundary and construct a channel projection graph combined with a channel merging technique to handle complex irregular packages. We then construct a bi-projection graph and propose a matching-based hierarchical sequencing algorithm to consider manual constraints. We perform global routing for each pin/differential pair by congestion-avoiding path initializing and rip-up and reroute path optimizing. Finally, a length-aware detail routing algorithm is developed to optimize the line length while ensuring the differential pair constraints. The experimental results on industrial PCB instances show that our algorithm can achieve 100% routability without violating the design rules and constraints, while two state-of-the-art PCB routers, FreeRouting and Allegro, cannot complete escape routing.

The Steiner minimum tree (SMT) serves as an optimal connection model for multiterminal nets in very large scale integration (VLSI). Constructing both rectilinear SMT (RSMT) and octilinear SMT (OSMT) are known to be NP-hard problems. Simultaneously, constructing multiple topologies of SMTs for a given net holds significant importance in alleviating routing constraints such as alleviating congestion and ensuring timing convergence. However, existing efforts predominantly focus on designing specialized methods to construct a specifically structured SMT for a given net, making it challenging to extend to different structures or topologies of SMTs, while also exhibiting insufficient optimization capabilities. In this work, we propose a unified approach based on deep reinforcement learning (DRL) to address both RSMT and OSMT problems while generating diverse routing topologies. First, we design an edge point sequence (EPS) that leverages the structural characteristics of SMT to connect the output of the deep learning model with the SMT structure. Second, we propose a deep learning model tailored for EPS, employing the negative wirelength of SMT as a reward to train the model using DRL. Third, we provide a corresponding rapid and accurate wirelength computation algorithm for evaluating the quality of the construction solution to expedite model training. Finally, we leverage the stochastic nature of machine learning to construct diverse SMT construction solutions. To the best of our knowledge, this is the first unified approach capable of simultaneously addressing both RSMT and OSMT problems while generating diverse solutions. The proposed unified approach demonstrates superior solution quality and higher efficiency compared to specifically designed algorithms.

As a new generation of flow-based microfluidics, Fully Programmable Valve Array (FPVA) biochips have gained widespread adoption as a biochemical experimental platform, thanks to their enhanced programmability and flexibility. Environmental and human factors, however, often introduce physical faults during the manufacturing process such as channel blockage and leakage, which, undoubtedly, can affect the results of bioassays and even cause execution failure. In this paper, we focus on the fault-tolerant co-design of flow and control layers in FPVA biochips for the first time. For the flow layer, three dynamic fault-tolerant techniques, i.e., a cell function conversion method, a bidirectional redundancy scheme, and a fault mapping method, are presented and integrated into the device placement and flow routing stages. As a consequence, we further realize an efficient and effective fault-tolerance-oriented physical design method, thus ensuring the robustness of chip architecture and correctness of assay outcomes. For the control layer, we design another three fault-tolerant techniques including a series duplication scheme of leakage valves, allocation and merging rules of backup valves, and a logic conflict-aware adjustment strategy of redundant architecture. Based on these techniques, we construct a fault-tolerant control system to realize dynamic recovery of control signals. Experimental results on multiple test cases demonstrate that the proposed method can produce optimized fault-tolerant FPVA architectures with low fabrication cost, high execution efficiency, and high fault-tolerance success rate.

Routability has always been a significant challenge in Very Large Scale Integration (VLSI) design. To overcome the potential mismatch between the global routing results and the detailed routing requirements, track assignment is introduced to achieve an efficient routability estimation. Moreover, with the increasing scale of circuits, the intricate interconnections among the components on the chip lead to increased timing delay in signal transmission, thereby significantly impacting the performance and reliability of the circuit. Thus, to further improve the routability of the circuit, it is also critical to realize an accurate estimation of the timing delay within the track assignment stage. Existing heuristic track assignment algorithms, however, are prone to local optimality, and thus fail to provide accurate routability estimations. In this article, we propose an enhanced scalable parallel track assignment algorithm called SPTA 2.0 for VLSI design, employing a two-stage partition strategy and considering timing delay. First, the proposed algorithm achieves efficient assignment of all wires by considering the routing information from both the global and local nets. Second, the overlap cost, the blockage cost, and the wirelength cost can be minimized to significantly improve the routability. Third, a critical wire controlling strategy is proposed to optimize signal timing delays inside nets. Finally, a two-stage partition strategy and a panel-subpanel-level parallelism are designed to further reduce the runtime, improving the scalability of the proposed methodology. Experimental results on multiple benchmarks demonstrate that the proposed method provides better routability estimations, and leads to superior track assignment solutions compared with existing algorithms.

As interconnect delay increasingly becomes the primary source of chip delay, timing analysis in the very large-scale integration (VLSI) routing process is becoming more crucial. Concurrently, to maintain computational synchronization in the chip, the bounded-skew constraint must be introduced. Additionally, the issue of obstacle-avoiding has gained attention due to the presence of routing obstacles on the chip. Furthermore, the introduction of X-architecture enables more efficient utilization of routing resources. In this article, we propose an obstacle-avoiding X-architecture bounded-skew tree (BST) algorithm under timing slack constraints, which, for the first time, simultaneously considers timing slack, bounded-skew, obstacle-avoidance, and X-architecture in a unified framework. First, an effective preprocessing strategy is presented to support fast information retrieval for the subsequent strategies. Second, a BST construction strategy is developed to ensure compliance with skew constraints by consulting and updating a dedicated skew table. Third, a local worst negative slack (WNS) optimization strategy is designed to improve the WNS of critical paths by balancing wirelength (WL) and radius. Fourth, an obstacle-avoiding strategy is implemented to navigate around routing obstacles while minimizing unnecessary WL overhead. Finally, a path refinement strategy is designed to select routing structures with maximal edge sharing to replace the initial structure, thereby further optimizing WL. Experimental results demonstrate that the proposed algorithm significantly improves both WL and the key timing metric WNS, while satisfying obstacle-avoidance and bounded-skew constraints.

With the increasing integration level of flow-based microfluidics, fully programmable valve arrays (FPVAs) have emerged as the next generation of microfluidic devices. Mi-crovalves in an FPVA are typically managed by a control logic, where valves are connected to a core input via control channels to receive control signals that guide states switching. The critical valves that suffer from asynchronous actuation leading to chip malfunctions, however, need to be switched simultaneously in a specific bioassay. As a result, the channel lengths from the core input to these valves are required to be equal or similar, which poses a challenge to the channel routing of the control logic. To solve this problem, we propose a deep reinforcement learning-based adaptive routing flow for the control logic of FPVAs. With the proposed routing flow, an efficient control channel network can be automatically constructed to realize accurate control signals propagation. Meanwhile, the timing skews among synchronized valves and the total length of control channels can be minimized, thus generating an optimized control logic with excellent timing behavior. Simulation results on multiple benchmarks demonstrate the effectiveness of the proposed routing flow.

Fully Programmable Valve Array (FPVA) biochips have attracted much attention as a new generation of continuous-flow microfluidic platform for biochemical experiments automation. With the increasing density of microvalves in FPVA biochips, the control system for managing the open/close of these valves has become more and more complex. To improve the scalability of biochips and reduce the number of control pins, a highly efficient control system using multiplexer and boolean logic has been introduced in FPVA biochips. In the manufacturing and using of such systems, however, various faults such as channel blockage, channel leakage, and reliability issues caused by frequent valve switching can occur in the multiplexers. Accordingly, in this paper, we propose the first automated fault test method for the multiplexer of FPVA control systems. The proposed method includes the following key techniques: 1) an automated test pattern generation algorithm based on integer linear programming and 2) an automated fault test strategy based on image recognition technology. Experiment results on multiple benchmarks have shown that the proposed method can generate fewer test patterns, while achiving 100% fault coverage.

In recent years, Fully Programmable Valve Array (FPVA) has emerged as a promising alternative for microfluidic biochips with flexible features. When two fluids flow sequentially through the same microchannel, the latter will be contaminated by the former’s residues. To solve the contamination problem, the buffer should be injected into microchannel to wash the contaminated area before reusing the microchannel. Considering the buffer capacity limitation, this paper proposes a washing optimization method based on Deep Reinforcement Learning (DRL), which aims to minimize the washing time and buffer washing capacity. First, a preprocessing method for the washing optimization problem is designed to generate the inputs for the initial state of the DRL environment based on the given physical design scheme. Second, an FPVA biochip simulation environment is constructed. In addition, the corresponding state, action space and high-precision reward function are designed. Finally, a new washing optimization framework is formulated based on DRL, which adopts the Proximal Policy Optimization (PPO) algorithm and Convolutional Neural Networks (CNN) to implement the washing decision. Experimental results on several benchmarks show that the proposed washing optimization method can further reduce the washing time and buffer washing capacity in comparison with related work.

Due to manufacturing defects, chip aging, and potential malicious attacks, unexpected errors may occur in the valves of Fully Programmable Valve Array (FPVA) biochips. To address this issue, an error recovery method based on Deep Reinforcement Learning (DRL) for FPVA biochips to handle valve-related unexpected errors is proposed, which involves designing specific error recovery operations for different error types, introducing a sequencing graph adjustment method to generate error recovery sequencing graph, and designing a resynthesis method to realize error recovery. The resynthesis method contains a priority-based scheduling adjustment, a DRL-based placement adjustment, and a DRL-based routing adjustment, which aims at updating the execution timetable for operations, component placements, and fluid transport paths. The model parameters are updated using a proximal policy optimization algorithm, continually learning from a large number of randomly simulated error scenarios, resulting in strong generalization performance. In comparison to existing work, the proposed method achieves lower probability of error recovery failure, shorter completion time of bioassay, and faster runtime.

Continuous-Flow Microfluidic Biochips (CFMBs) have been widely applied in various biochemical fields due to their capabilities of precise control, high integration, and automation. However, insecure supply chains enable malicious actors to tamper with biochips, compromising their integrity and leading to failed bioassays. Additionally, the limited availability of detection resources leads to increased costs and reduced efficiency in conducting bioassays. To ensure accurate and efficient execution of bioassays, this paper defines fluid scheduling tampering and activation sequences tampering as two types of security threats and proposes an Anomaly Detection method based on Discrete Particle Swarm Optimization (AD-DPSO) for CFMBs. The AD-DPSO method presents a weight calculation strategy based on fluid scheduling and a checkpoint selection strategy based on DPSO to effectively deploy checkpoints on the biochips. The weight calculation strategy ensures effective and secure checkpoint deployment strategies by favoring units with high usage frequency and low detection cost. The checkpoint selection strategy comprehensively considers chip resources and security requirements, thus maximizing the probability of anomaly detection while minimizing associated costs. Compared to the existing work, the proposed AD-DPSO achieves higher Return on Investment and lower detection costs with high detection probability.

Fully programmable valve array (FPVA) biochips have emerged as a promising alternative for traditional application-specific microfluidic platforms thanks to their advantages in terms of flexibility and reconfigurability. By regularly deploying microvalves along vertical and horizontal flow channels, microfluidic modules with different sizes and shapes can be constructed dynamically on the chip, thereby enabling the automatic execution of various assay procedures in biology and biochemistry. The above advantages, however, result largely from the large-scale integration of valves as well as accurate control of their switchings, leading to very complicated control-logic design of such chips. In this article, we propose an reinforcement learning (RL)-based synthesis flow for the control-logic design of fully programmable valve array (FPVA) biochips, taking multichannel switching and control-cost minimization into consideration simultaneously. By employing a double deep$Q$-network (DDQN) and two Boolean-logic simplification techniques, control logics with both high-switching efficiency and low-fabrication cost can be constructed automatically. Furthermore, the solution space of multichannel-switching combinations is reduced to improve the search efficiency of the proposed method. Experimental results on multiple benchmarks demonstrate that the proposed synthesis flow leads to better-design solutions compared with the state-of-the-art techniques.

With the advances in microfluidics, electrowettingon-dielectric (EWOD) chips have widely been applied to various biological and chemical laboratory protocols. Glass-based EWOD chips with non-regular electrodes are proposed, which allow more reliable droplet operations and facilitate the integration of optical sensors for many biochemical applications. Furthermore, non-regular electrode designs are utilized in EWOD chips, e.g., interdigitated electrodes for more reliable droplet manipulation, custom shaped electrodes for specific applications like concentric heating, etc. However, due to the technical challenges of fabricating multi-layer interconnection on the glass substrate, e.g., unreliable process and high cost, both control electrodes and wires are fabricated with a single-layer configuration, which poses significant challenges to pin selection for non-regular electrodes. In this paper, we propose a minimum-cost flow-based routing algorithm called NR-Router+ that features efficient and robust routing for single-layer EWOD chips with non-regular electrodes. To the best of our knowledge, this is the first work that overcomes the aforementioned challenges. We construct a minimum-cost flow algorithm to generate optimal routing paths followed by a light-weight model to handle flow capacity. A grid reduction strategy is proposed to reduce the computational overhead. Additionally, a flow collocation algorithm based on integer linear programming is presented to efficiently prevent wire overlapping. Experimental results show that NR-Router+ achieves 100% routability while minimizing wirelength with shorter run time. Moreover, NR-Router+ can generate mask files feasible for manufacturing via adjustments of design parameters, thus demonstrating its robustness and efficiency.

Continuous-flow microfluidic biochips are gaining increasing attention with promising applications for automatically executing various laboratory procedures in biology and biochemistry. Biochips with distributed channel-storage architectures enable each channel to switch between the roles of transportation and storage. Consequently, fluid transportation, caching, and fetch can occur concurrently through different flow paths. When two dissimilar types of fluidic flows occur through the same channels in a time-interleaved manner, it may cause contamination to the latter as some residues of the former flow may be stuck at the channel wall during transportation. To remove the residues, wash operations are introduced as an essential step to avoid incorrect assay outcomes. However, existing work has been considered that the washing capacity of a buffer fluid is unlimited. In the actual scenario, a fixed-volume buffer fluid irrefutably possesses a limited washing capacity, which can be successively consumed while washing away residues from the channels. Hence, capacity-aware wash scheme is a basic requirement to fulfil the dynamic fluid scheduling and channel storage. In this paper, we formulate a practical wash optimization problem for microfluidic biochips, which considers the requirements of dynamic fluid scheduling, channel storage, as well as washing capacity constraints of buffer fluids simultaneously, and present an efficient design flow to solve this problem systematically. Given the high-level synthesis result of a biochemical application and the corresponding component placement solution, our goal is to complete a contamination-aware flow-path planning with short flow-channel length. Meanwhile, the biochemical application can be executed efficiently and correctly with an optimized capacity-aware wash scheme. Experimental results show that compared to a state-of-the-art washing method, the proposed method achieves an average reduction of 26.1%, 43.1%, and 34.1% across all the benchmarks with respect to the total channel length, total wash time, and execution time of bioassays, respectively.

Global routing is an extremely important stage of very large scale integration (VLSI) physical design. With the rise of nano-scale integrated circuit design, the multilayer global routing problem has attracted considerable research interest during the past few years. In this article, a multilayer X-architecture global routing (ML-XGR) system based on particle swarm optimization (PSO), called FZU-Router, is proposed to solve the ML-XGR problem for the first time. FZU-Router contains a multilayer X-architecture integer linear programming (MX-ILP) model and a multilayer X-architecture PSO (MX-PSO) algorithm, which are presented to formulate and solve the ML-XGR problem, respectively. Moreover, four effective strategies are designed to enhance the efficiency of FZU-Router: 1) a strategy for generating new routing modes is proposed to strengthen the robustness of encoding strategy of MX-PSO; 2) a strategy for combining MX-PSO with maze routing is proposed to improve the routability; 3) a strategy for reducing the channel capacity is proposed to make better use of optimization ability of MX-PSO; and 4) a strategy for dynamic resource assignment is proposed to make better use of routing resources and shorten the running time. Experimental results on multiple benchmarks confirm that the proposed FZU-Router leads to fewer total overflow and shorter total wirelength compared with the state-of-the-art routers.

SMT is an optimized model for solving the routing problem of a multipin net in very large-scale integrated circuits. As the appearance of various obstacles on chips, the obstacle-avoiding problem has attracted much attention in recent years. Meanwhile, since interconnect delay plays a major role in chip delay, timing analysis is another critical problem worthy of consideration when constructing an Steiner minimum tree (SMT). Furthermore, the introduction of theX-architecture allows for better utilization of routing resources. In this article, a timing-driven obstacle-avoiding X-architecture Steiner minimum tree algorithm with slack constraints (TD-OAXSMT-SC) is proposed to consider obstacle-avoiding, timing slack constraints, andX-architecture simultaneously for the first time. The TD-OAXSMT-SC algorithm consists of four major stages: 1) in the routing tree initialization stage, this article constructs anX-architecture Prim–Dijkstra spanning tree as the initial routing tree with minimum total delay; 2) in the particle swarm optimization (PSO)-based routing tree iteration stage, a novel discrete PSO algorithm based on genetic operators is proposed to obtain a high-quality routing tree; 3) in the routing tree standardization stage, two effective standardization strategies are proposed to obtain a routing tree that satisfies both obstacle-avoiding and timing slack constraints; and 4) in the routing tree optimization stage, the connection of interconnected wires is optimized in a global manner, thus obtaining an optimized routing tree. Experimental results show that the proposed TD-OAXSMT-SC algorithm outperforms the state-of-the-art methods in routing quality with slack constraints.

As a new generation of flow-based microfluidics, the Fully Programmable Valve Array (FPVA) biochips have become a popular biochemical experimental platform that provide higher flexibility and programmability. Due to environmental and human factors, however, there are usually some physical faults in the manufacturing process such as channel blockage and leakage, which, undoubtedly, can affect the results of bioassays and even cause execution failure. Accordingly, we focus on the fault-tolerant design of FPVA biochips for the first time in this paper, and present three dynamic fault-tolerant techniques including a cell function conversion method, a bidirectional redundancy scheme, and a fault mapping method. By integrating these techniques into the component placement and channel routing stages, we further realize an efficient and effective fault-tolerance-oriented physical design approach for FPVA biochips, thus ensuring the robustness of chip architecture and correctness of assay outcomes. Experimental results on multiple benchmarks confirm that the proposed approach can generate fault-tolerant FPVA architectures with both high execution efficiency and low fabrication cost.

Continuous-flow microfluidic biochips have emerged as a potential low-cost and fast-responsive lab-on-chip platform. They have attracted much attention due to their capability of performing various biochemical applications concurrently and automatically within a coin-sized chip area. To improve execution efficiency and reduce fabrication cost, a distributed channel-storage architecture can be implemented in which the same channels can be switched between the roles of transportation and storage. Accordingly, fluid transportation, caching, and fetch can be performed simultaneously through different flow paths. Such a flow-path planning needs to be considered carefully in the mapping procedure from a biochemical application to a given biochip architecture. Moreover, all the on-chip valves should be actuated correctly and promptly to temporally block the fluid transportation in unwanted directions and seal the fluids in caching channels. Such an exact control of the valves needs to be considered systematically in control-system design to support the mapping scheme for bioassay execution. In this article, we formulate the practical mapping-control co-design problem for microfluidic biochips with distributed channel storage, considering application mapping, valve synchronization, and control-system design simultaneously, and present an efficient synthesis flow to solve this problem systematically. Given the protocol of a biochemical application and the corresponding chip layout in the flow layer, our goal is to map the biochemical application onto the chip with short execution time. Meanwhile, a practical control system considering the real valve-switching requirements can be constructed efficiently with low fabrication cost. Experimental results on multiple real-life bioassays and synthetic benchmarks demonstrate the effectiveness of the proposed design flow.

As the last stage of VLSI routing, detailed routing should consider complicated design rules in order to meet the manufacturability of chips. With the continuous development of VLSI technology node, the design rules are changing and increasing which makes detailed routing a hard task. In this paper, we present a practical track-assignment-based detailed router to deal with the most representative design rules in modern designs. The proposed router consists of four major stages: (1) a graph-based track assignment algorithm is proposed to optimize the design rule violations of an entire die area; (2) an effective rip-up and reroute method is used to reduce the design rule violations in local regions; (3) a segment migration algorithm is proposed to reduce short violations; and (4) a stack via optimization technique is proposed to reduce minimum area violations. Practical benchmarks from 2019 ISPD contest are used to evaluate the proposed router. Compared with the state-of-the-art detailed router, Dr. CU 2.0, the number of violations can be reduced by up to 35.11 % with an average reduction rate of 10.08 %. The area of short can be reduced by up to 61.49 % with an average reduction rate of 44.80 %.

Timing optimization has always been a key issue affecting the chip performance. Most of the previous layer assignment algorithms mainly optimize timing from the perspective of interconnect delay, and often ignore the impact of slew on signal integrity. Therefore, this paper proposes LA-SVR, a high-performance layer assignment algorithm with slew violations reduction. The proposed algorithm mainly includes three key techniques: 1) an effective classified reassignment strategy is proposed to re-assign nets in terms of different optimization priorities for overflow avoidance; 2) an effective net adjustment method is adopted to reduce the potential slew violations; 3) a layer restricting strategy is proposed to optimize delay of nets and slew violations simultaneously by restricting the candidate better routing layers of different nets. Experimental results show that the proposed algorithm has a significant effect on slew violations reduction.

Routability has always been a very challenging issue in Very Large Scale Integrated (VLSI) circuit design. The routability is considered in track assignment so that the global routing results can better match the requirements of detailed routing. However, existing heuristic track assignment algorithms are prone to local optimality, which cannot provide the accurate routability estimation. To overcome this limitation, we propose a scalable parallel Integer Linear Programming (ILP)-based track assignment algorithm, called SPTA, which employs a two-stage partition strategy. First, by taking into account both the global and local nets, all wires are assigned to tracks, making full use of the information from the global routing results. Second, an efficient ILP model for track assignment is proposed to minimize the overlap between iroutes1, thus significantly improving routability. Third, a two-stage partition strategy is designed to reduce the runtime. Finally, a panel-subpanel-level parallelism is proposed to further speed up the algorithm without sacrificing the quality of the solutions. Experimental results show that SPTA has a better routability estimation compared with the existing algorithms.

Recent advances in continuous-flow microfluidics have enabled highly integrated lab-on-a-chip biochips. These chips can execute complex biochemical applications precisely and efficiently within a tiny area, but they require a large number of control ports and the corresponding control logic to generate required pressure patterns for flow control, which, consequently, offset their advantages and prevent their wide adoption. In this article, we propose the first flow-control layer co-synthesis flow called MiniControl, for continuous-flow microfluidic biochips under strict constraints for control ports, incorporating high-level synthesis, physical design, and control system design simultaneously, which has never been considered in previous work. With the maximum number of allowed control ports specified in advance, this synthesis flow aims to generate biochip architectures with high execution efficiency and the corresponding control systems with optimized timing performance. Besides, the overall cost of a biochip can be reduced and the tradeoff between a control system and execution efficiency of biochemical applications can be evaluated for the first time. The experimental results demonstrate that MiniControl leads to high execution efficiency, low platform cost, as well as excellent timing performance, while strictly satisfying the given control-port constraints.

Interconnect delay is a key factor that affects the chip performance in layer assignment. Particularly in the advanced process technologies of 5 nm and beyond, interconnect delay has grown significantly due to the increase of circuit scale. Moreover, coupling effect existed in wires reduces the accuracy of delay evaluation. On the other hand, the size of vias is often ignored in layer assignment, which enlarges the mismatch between global routing and detailed routing. To solve these problems, we proposeVPT, a timing-aware layer assignment algorithm considering via pillars, which includes the following five key techniques: 1) via pillar structure combined with nondefault-rule (NDR) wires is adopted to form a net delay optimization system for advanced process technologies; 2) a synthetical model that can adapt to varying types and sizes of both vias and wires is designed to evaluate overflow effectively; 3) a sorting strategy is devised to reduce uncertainty of layer assignment flow and improve stability of the proposed algorithm; 4) an awareness strategy based on multiaspect congestion assessment is designed to reduce overflow significantly; and 5) a net scalpel algorithm is devised to minimize the maximum delay of nets, so that the timing behaviors can be improved systematically. The experimental results on multiple benchmarks confirm that the proposed algorithm leads to lower delay and less overflow, while achieving the best solution quality among the existing algorithms with the shortest runtime.

As the scale of VLSI circuits increases rapidly, multi-FPGA prototyping systems have been widely used for logic verification. Due to the limited number of connections between FPGAs, however, the routability of prototyping systems is a bottleneck. As a consequence, timing division multiplexing (TDM) technique has been proposed to improve the usability of prototyping systems, but it causes a dramatic increase in system delay. In this paper, we propose ALIFRouter, a practical architecture-level inter-FPGA router, to improve the chip performance by reducing the corresponding system delay. ALIFRouter consists of three major stages, including i) routing topology generation, ii) TDM ratio assignment, and iii) system delay optimization. Additionally, a multi-thread parallelization method is integrated into the three stages to improve the efficiency of ALIFRouter. With the proposed algorithm, major performance indicators of multi-FPGA systems such as signal multiplexing ratio can be improved significantly.

Gene-expression profiling can define the cell state and gene-expression pattern of cells at the genetic level in a high-throughput manner. With the development of transcriptome techniques, processing high-dimensional genetic data has become a major challenge in expression profiling. Thanks to the recent widespread use of matrix decomposition methods in bioinformatics, a computational framework based on compressed sensing was adopted to reduce dimensionality. However, compressed sensing requires an optimization strategy to learn the modular dictionaries and activity levels from the low-dimensional random composite measurements to reconstruct the high-dimensional gene-expression data. Considering this, here we introduce and compare four compressed sensing frameworks coming from nature-inspired optimization algorithms (CSCS, ABCCS, BACS and FACS) to improve the quality of the decompression process. Several experiments establish that the three proposed methods outperform benchmark methods on nine different datasets, especially the FACS method. We illustrate therefore, the robustness and convergence of FACS in various aspects; notably, time complexity and parameter analyses highlight properties of our proposed FACS. Furthermore, differential gene-expression analysis, cell-type clustering, gene ontology enrichment and pathology analysis are conducted, which bring novel insights into cell-type identification and characterization mechanisms from different perspectives. All algorithms are written in Python and available at https://github.com/Philyzh8/Nature-inspired-CS.

Layer assignment, a major step in global routing of integrated circuits, is usually performed to assign segments of nets to multiple layers. Besides the traditional optimization goals such as overflow and via count, interconnect delay plays an important role in determining chip performance and has been attracting much attention in recent years. Accordingly, in this paper, we propose MiniDelay, a timing-aware layer assignment algorithm to minimize delay for advanced technology nodes, taking both wire congestion and coupling effect into account. MiniDelay consists of the following three key techniques: 1) a non-default-rule routing technique is adopted to reduce the delay of timing critical nets, 2) an effective congestion assessment method is proposed to optimize delay of nets and via count simultaneously, and 3) a net scalpel technique is proposed to further reduce the maximum delay of nets, so that the chip performance can be improved in a global manner. Experimental results on multiple benchmarks confirm that the proposed algorithm leads to lower delay and few vias, while achieving the best solution quality among the existing algorithms with the shortest runtime.

As the scale of VLSI circuits and fabrication costs increase rapidly, multi-FPGA prototyping systems are widely adopted in industry to make logic verification faster and cheaper. Since routing signals can usually exceed the number of I/O pins in an FPGA, timing division multiplexing (TDM) technique is required to solve this problem. FPGA routing for developing a prototyping system is a big challenge due to the signal delay of TDM. This paper presents MSFRoute, a multi-stage FPGA routing framework for timing division multiplexing technique, to optimize the signal delay and the routability for prototyping systems. In this work, a TDM ratios assignment algorithm with an efficient parallelization method is proposed to optimize inter-FPGA signal delay. Meanwhile, we propose a practical system clock period optimization method to solve critical signal delay problem. Experimental results show that our routing framework reduces TDM ratios by up to 88.3% with an average reduction rate of 41.8%. With the proposed parallelization method, total flow of MSFRoute can get up to 4.38X speedup with a 2.77X speedup on average.

The global environment has become more polluted due to the rapid development of industrial technology. However, the existing machine learning prediction methods of air quality fail to analyze the reasons for the change of air pollution concentration because most of the prediction methods take more focus on the model selection. Since the framework of recent deep learning is very flexible, the model may be deep and complex in order to fit the dataset. Therefore, overfitting problems may exist in a single deep neural network model when the number of weights in the deep neural network model is large. Besides, the learning rate of stochastic gradient descent (SGD) treats all parameters equally, resulting in local optimal solution. In this paper, the Pearson correlation coefficient is used to analyze the inherent correlation of PM2.5 and other auxiliary data such as meteorological data, season data, and time stamp data which are applied to cluster for enhancing the performance. Extracted features are helpful to build a deep ensemble network (EN) model which combines the recurrent neural network (RNN), long short-term memory (LSTM) network, and gated recurrent unit (GRU) network to predict the PM2.5 concentration of the next hour. The weights of the submodel change with the accuracy of them in the validation set, so the ensemble has generalization ability. The adaptive moment estimation (Adam) an algorithm for stochastic optimization is used to optimize the weights instead of SGD. In order to compare the overall performance of different algorithms, the mean absolute error (MAE) and mean absolute percentage error (MAPE) are used as accuracy metrics in the experiments of this study. The experiment results show that the proposed method achieves an accuracy rate (i.e., MAE=6.19 and MAPE=16.20 %) and outperforms the comparative models.

This paper presents a routability-driven track assignment algorithm (RDTA) to efficiently estimate routability. Routability has become a very challenging issue in modern IC design and it can be effectively estimated by routing congestion. Track assignment is a stage towards bridging the gap between global routing and detailed routing. And track assignment can also analyze routing congestion more accurate than other routing stages like global routing. Some works have used track assignment to estimate routability. In this work, wire segments extracted from a global routing solution are assigned to proper tracks considering local nets, via locations and pin access. The overlap between wire segments extracted from a global routing solution can be effectively reduced by the algorithm so that the solution of RDTA can effectively estimate the routability.

In this paper, we propose an approach to estimate and quantify the degree of extraversion for crowd motion based on individual trajectories. Extraversion is a typical personality that is often observed in human behaviors. We present a composite motion descriptor, which integrates the basic motion information and social metrics, to describe the extraversion of each individual in a crowd. In order to train a universal scoring function that can measure the degrees of extraversion, we incorporate the active learning technique with the relative attribute approach based on the social grouping behavior in crowd motions. In addition, we demonstrate the performance of the proposed method by measuring the degree of extraversion for real individual trajectories in a crowd and analyzing crowd scenes from a real-world dataset.

With the sharp increase of very large-scale integrated (VLSI) circuit density, we are faced with many knotty issues. Particularly in the routing phase of VLSI physical design, the interconnection effects directly relate to the final performance of circuits. However, the optimization capability of traditional rectilinear architecture is limited; thus, both academia and industry have been devoted to nonrectilinear architecture in recent years, especially octilinear architecture, which is the most promising because it can greatly improve the performance of modern chips. In this article, we design FH-OAOS, an obstacle-avoiding algorithm in octilinear architecture, by constructing an obstacle-avoiding the octilinear Steiner minimal tree (OAOSMT). Our approach first constructs an obstacle-free Euclidean minimal spanning tree (OFEMST) on the given pins based on Delaunay triangulation (DT). Then, two lookup tables about OFEMST’s edge are generated, which can be seen as the information center of FH-OAOS and can provide information support for algorithm operation. Next, an efficient obstacle-avoiding strategy is proposed to convert the OFEMST into an obstacle-avoiding octilinear Steiner tree (OAOST). Finally, the generated OAOST is refined to construct the final OAOSMT by applying three effective strategies. Experimental results on various benchmarks show that FH-OAOS achieves 66.39 times speedup on average, while the average wirelength of the final OAOSMT is only 0.36% larger than the best existing solution.

As the basic model for very large scale integration routing, the Steiner minimal tree (SMT) can be used in various practical problems, such as wire length optimization, congestion, and time delay estimation. In this paper, an effective algorithm based on particle swarm optimization is presented to construct a multilayer obstacle-avoiding X-architecture SMT (ML-OAXSMT). First, a pretreatment strategy is presented to reduce the total number of judgments for the routing conditions around obstacles and vias. Second, an edge transformation strategy is employed to make the particles have the ability to bypass the obstacles while the union-find partition is used to prevent invalid solutions. Third, according to the feature of ML-OAXSMT problem, we design an edge-vertex encoding strategy, which has the advantage of simple and effective. Moreover, a penalty mechanism is proposed to help the particle bypass the obstacles, and reduce the generation of via at the same time. Experimental results show that our algorithm from a global perspective of multilayer structure can achieve the best solution quality among the existing algorithms. Finally, to our best knowledge, we redefine the edge cost and then construct the obstacle-avoiding preferred direction X-architecture Steiner tree, which is the first work to address this problem and can offer the theory supports for chip design based on non-Manhattan architecture.

Obstacle-avoiding Steiner minimal tree (OASMT) construction has become a focus problem in the physical design of modern very large-scale integration (VLSI) chips. In this article, an effective algorithm is presented to construct an OASMT based on X-architecturex for a given set of pins and obstacles. First, a kind of special particle swarm optimization (PSO) algorithm is proposed that successfully combines the classic genetic algorithm (GA), and greatly improves its own search capability. Second, a pretreatment strategy is put forward to deal with obstacles and pins, which can provide a fast information inquiry for the whole algorithm by generating a precomputed lookup table. Third, we present an efficient adjustment method, which enables particles to avoid all the obstacles by introducing some corner points of obstacles. Finally, an excellent refinement method is discussed to further enhance the quality of the final routing tree, which can improve the quality of the solution by 7.93% on average. To our best knowledge, this is the first time to specially solve the single-layer obstacle-avoiding problem in X-architecture. Experimental results show that the proposed algorithm can further shorten wirelength in the presence of obstacles. And it achieves the best solution quality in a reasonable runtime among the existing algorithms.