With the increasing number of I/O pins in highly integrated semiconductor products, semiconductor packaging has become an essential yet complex part of integrated circuit (IC) design. The substrate plays an important role in advanced semiconductor packaging and provides the chip with electrical connections and heat dissipation. While numerous studies have addressed the substrate routing problem, only one state-of-the-art work provides a customized routing flow specifically designed for packages with wire-bonding style and fine-pitch ball grid arrays (FBGA), which are more widely used than advanced packaging due to their maturity and lower cost. However, the existing router suffers from unsatisfactory routability due to its simplistic implementation and lack of necessary consideration for finger connections. Therefore, this paper proposes several optimization heuristics, such as finger accessibility enhancement, progressive rerouting, and half-grid rerouting techniques, to further improve the overall routing completion rate. Experimental results show that the proposed heuristics are capable of avoiding routing resource wastage, achieving better routing quality, and eliminating design-rule violations.

As an important intermediate between integrated circuits (ICs) and the printed circuit board (PCB), the routing in the package substrate plays a crucial role in the efficiency and accuracy of signal and power transmission. While numerous research efforts have focused on substrate routing to avoid inefficient, time-consuming, and error-prone manual processes, few of them have addressed the challenge of routing multi-pin nets, particularly those with a large number of pins. This article presents a three-stage framework of multi-pin net routing for packages with fine-pitch ball grid arrays, consisting of pin grouping, minimum spanning tree topology generation, and group topology connection. Our framework classifies net connections into different categories, prioritizes their routing ordering, and applies different routing approaches and strategies to boost overall routability. The results of the experiments conducted on six real industrial designs demonstrate that our framework can simultaneously and effectively handle two-pin nets and multi-pin nets with better routing performance compared to the state-of-the-art work.

Package design has become increasingly complex with the evolution of technology nodes and heterogeneous integration. To optimize timing performance and signal integrity, it is essential to separate different pairs of geometrically adjacent nets with distinct spacing values, which is referred to as the paired-spacing constraint. This paper presents the first free-assignment package routing algorithm flow considering the paired-spacing constraint. To minimize the routing resource demand and overall wirelength, we propose a dynamic programming-based net ordering method to maximize the number of nets with the same/similar spacing rules positioned next to each other. In addition, the free-assignment routing problem is elegantly solved with a minimum-cost maximum-flow problem on a delicately designed graph model. Experimental results show that the proposed flow can achieve 100% routability for the adopted industrial-modified benchmarks. In contrast, even with modifications to superficially consider paired spacings, a classic model experiences significant routability degradation.

Wire bonding is a mature packaging technique that enables chip pins to transmit signals to bonding fingers on the substrate through bonding wires. Such commodity technology is also essential in supporting the rapid development of the system in package and heterogeneous integration technologies. However, the automation tools are relatively deficient compared to other packaging techniques, resulting in tremendous manual design time and engineering effort due to numerous wire-bonding design constraints. This paper addresses the finger placement problem and serves as the first work considering the orientation constraint of fingers. The finger placement flow is divided into three stages. First, an integer linear programming (ILP) formulation is developed to allocate each net finger row. After that, we utilize mixed-integer quadratic programming (MIQP) to place the bonding fingers and consider the wire crossing constraint. Finally, the locations of the bonding finger are refined by considering both the bonding finger orientation angle and the finger spacing constraints. The final layouts generated by our integrated finger placement and substrate routing framework outperform manual designs in terms of the design time, the total wirelength, and the routing completion rate.

The "CAD Contest at ICCAD" is a challenging, multi-month, research and development competition, focusing on advanced, real-world problems in the field of electronic design automation (EDA). Since 2012, the contest has been publishing many sophisticated circuit design problems, from system-level design to physical design, together with industrial benchmarks and solution evaluators. Contestants can participate in one or more problems provided by EDA/IC industry. The winners will be awarded at an ICCAD special session dedicated to this contest. Every year, the contest attracts more than a hundred teams, fosters productive industry-academia collaborations, and leads to hundreds of publications in top-tier conferences and journals. The 2025 CAD Contest has 247 teams from all over the world, which generates the highest participation record. Moreover, the problems of this year cover state-of-the-art EDA research trends such as hardware trojan detection, design optimization with multibit flip-flops, and performance-driven incremental placement optimization from well-known EDA/IC companies. We believe the contest keeps enhancing impact and boosting EDA researches.

Traditional packaging routers are typically limited to 90- and 135-degree routing angles. However, with the advancement in advanced packaging technologies and the increasing demand for a higher number of I/Os, any-angle routing has become a promising solution thanks to its ability to explore a larger solution space and reduce overall wirelength. Therefore, we proposed an any-angle routing framework for die-to-substrate connections. First, the proposed routing graph enables accurate estimation of routing resource utilization in the global routing stage. After the global routing stage, we introduce two wire-length optimization strategies: (1) a concurrent adjustment of access points to reduce total wirelength by considering all nets simultaneously, and (2) a dynamic programming-based method to minimize the number of wire segments in each single net. Experimental results demonstrate that our two-stage refinement strategies achieve superior routing quality compared to the global routing result.

The "CAD Contest at ICCAD" is a challenging, multi-month, research and development competition, focusing on advanced, real-world problems in the field of electronic design automation (EDA). Since 2012, the contest has been publishing many sophisticated circuit design problems, from system-level design to physical design, together with industrial benchmarks and solution evaluators. Contestants can participate in one or more problems provided by EDA/IC industry. The winners will be awarded at an ICCAD special session dedicated to this contest. Every year, the contest attracts more than a hundred teams, fosters productive industry-academia collaborations, and leads to hundreds of publications in top-tier conferences and journals. The 2024 CAD Contest has 221 teams from all over the world, which generates the highest participation record. Moreover, the problems of this year cover state-of-the-art EDA research trends such as logic optimization, multibit flip-flop, and Machine Learning (ML) for EDA from well-known EDA/IC companies. We believe the contest keeps enhancing impact and boosting EDA researches.

Three-dimensional integration circuit (3D IC) offers significant benefits in terms of performance and cost. Existing research in through-silicon via (TSV)-based 3D IC partitioning has focused on minimizing the number of TSVs to reduce costs. Partitioning methods based on heterogeneous integration have emerged as viable approaches for cost optimization. Leveraging mature processes to manufacture not timing-critical blocks can yield cost benefits. Nevertheless, none of the previous 3D partitioning work has focused on reducing the overall cost, including both design and manufacturing costs, for heterogeneous 3D integration. Moreover, throughput constraints have not been considered. This article presents a cost-aware integer linear programming-based formulation and a heuristic algorithm that partition the functional blocks in the design into different technological groups. Each group of functional blocks will be implemented using a particular process technology, and then integrated into a 3D IC. Our results show that 3D heterogeneous integration chip implementation can reduce overall cost while satisfying various timing constraints.

Lamellar directed self-assembly (DSA) technology in combination with the self-aligned via (SAV) process has emerged as a novel and promising choice for via/contact layer fabrication, where a via between Metal-$x$and Metal-$(x+1)$is generated at the intersection of a wire segment on Metal-$(x+1)$and a rectangular and perpendicular guiding template. Compared to the highly investigated cylindrical DSA, lamellar DSA does not suffer from the overlay error of generated holes and thus can have better yield, and it also benefits from the better flexibility of various via pitches a single template can produce. A state-of-the-art work has addressed the guiding template design problem for the new process, and an integer linear programming (ILP) formulation that can optimally solve the problem as well as a simple heuristic approach are proposed. However, solving the ILP formulation is time consuming, and the heuristic method suffers from unignorable degradation in solution quality due to several algorithm deficiencies. In this article, we propose an enhanced and efficient template design algorithm flow for the lamellar DSA and SAV process by using graph monomorphism for pattern conflict check in multiple patterning lithography. Experimental results show that the proposed flow can greatly reduce the numbers of conflicts and short templates and is almost as efficient as the existing heuristic approach.

With the rapidly growing demand for system-level integration, package substrates have become one of the most important carriers in semiconductor industry. Fine pitch ball grid array (FBGA) packaging is a widely used technology thanks to its relative cost-effectiveness compared to other advanced packaging technologies. In addition, it is also widely used in space-constrained applications, such as mobile and handheld devices. These packaging substrate interconnections are usually customized by layout engineers taking many complex and stringent design rules into consideration. However, fully net-by-net manual design for FBGA is time-consuming and error-prone. In this article, we propose an integer linear programming (ILP)-based router for wire-bonding FBGA packaging design. Our ILP formulation not only can handle design-dependent constraints but also take the problem of mismatched via dimension into account, which is caused by the mechanical processes and greatly increases design complexity. In addition to the ILP formulation for substrate routing, three optimization stages and several ILP constraint reduction techniques are also developed to boost the run time of ILP solver. Experimental results indicate that the proposed framework can achieve high routing completion rates, which could effectively reduce the cycle time of substrate layout design. In addition, in combination with the proposed optimization strategies, 278× speedup can be achieved compared to the ILP constraint optimized router.

Spin-transfer torque RAM (STT-RAM) is an emerging non-volatile memory that has been recognized as the potential candidate to replace SRAM. Compared with SRAM, STT-RAM has advantages of non-volatility, zero leakage power, and higher density. To further improve data density, multi-level cell (MLC) STT-RAM that can store two bits per cell has been proposed. However, writing hard bit of a cell would write its soft bit to the same value as well, which complicates the write operation of MLC STT-RAM. Although two-step transition (TT) is usually adopted to ensure the data correctness during a write operation, it incurs overhead of additional energy consumption and performance degradation. In this article, we propose the two-step elimination (TSE) scheme to eliminate TTs while ensure data integrity. By flipping hard bits of the cells that suffered from TTs, the TSE scheme could reduce TTs to soft transitions (STs) or zero transitions (ZTs), which incur much less overhead than TTs. To keep track of the flipped cells effectively, 6-bit TSE tag is introduced. We exploit tag reversing and advanced mode of the TSE scheme to further improve the performance. The experimental results showed that our scheme could reduce 61 percent TTs and achieve significant lifetime improvement, compared with conventional MLC STT-RAM (CMLC) scheme.

Directed self-assembly (DSA) with block copolymers (BCP) has become a promising lithography technology for generating tiny features in integrated circuits. There have been many existing studies investigating the design methodologies using cylinder-forming BCP for via/contact layer manufacturing. However, cylindrical DSA suffers from the limited natural pitch of generated holes and the displacement errors due to guiding template distortions. Consequently, only few feasible hole patterns are manufacturable with a template and the unsatisfactory yield is still one of the major concerns. On the other hand, lamellar DSA using lamella-forming BCP emerges as another solution for hole generation, which in combination with the self-aligned via (SAV) process is immune to hole displacement errors and able to produce various linear hole patterns. In this paper, we propose the first work of guiding template design for lamellar DSA by using the SAV process and multiple patterning lithography (MPL). An integer linear programming (ILP)-based approach and a heuristic method are respectively proposed that consider the design constraints induced by lamellar DSA with SAV. Experimental results demonstrate the optimality of the ILP-based approach, and the heuristic method can also efficiently derive near-optimal solutions.

We propose a cache architecture using a 7T/14T SRAM (Fujiwara et al., 2009) and a control mechanism for reliability enhancements. Our control mechanism differs from conventional dynamic voltage-frequency scaling (DVFS) methods in that it considers not only the cycles per instruction behaviors but also the cache utilization. To measure cache utilization, a novel metric is proposed. The experimental results show that our proposed method achieves 1000 times less bit-error occurrences compared with conventional DVFS methods under the ultralow-voltage operation. Moreover, the results indicate that our proposed method surprisingly not only incurs no performance and energy overheads but also achieves on average a 2.10% performance improvement and a 6.66% energy reduction compared with conventional DVFS methods.

Cache performance is an important factor in modern computing systems due to large memory access latency. To exploit the principle of spatial locality, a requested data set and its adjacent data sets are often loaded from memory to a cache block simultaneously. However, the definition of adjacent data sets is strongly correlated with the memory organization. Commodity memory is a two-dimensional structure with two (row and column) access phases to locate the requested data set. Therefore, the adjacent data sets are neighbors of the requested data set in a linear order. In this paper, we propose a novel memory organization with dual-addressing modes as well as orthogonal memory access mechanisms. Our dual-addressing memory can be efficiently applied to two-dimensional memory access patterns. Furthermore, we propose a cache coherence protocol to tackle the cache coherence issue due to synonym data set of the dual-addressing memory. For benchmark kernels with two-dimensional memory access patterns, the dual-addressing memory achieves 60% performance improvement as compared to conventional memory. Both cache hit rate and cache utilization are improved after removing two-dimensional memory access patterns from conventional memory.

In the routing architecture of a structured application-specific integrated circuit (ASIC), the crossbar is one of the most area-efficient switch blocks. Nevertheless, a dangling wire occurs when there is a routing bend in a crossbar switch. Dangling wires incur longer wire lengths as well as a higher interconnection capacitance. In this article, we tackle dangling wire issues for structured ASIC routability optimization. We first propose a compact graph model for crossbar-switch routing. With our graph model, switch connectivity relations can be removed to keep the 2D structured ASIC routing graph efficient and to speed up the runtime of our routing algorithm. Furthermore, we propose a heuristic dangling-wire-avoidance routing framework containing deferred pin assignment, Steiner point reassignment, and anchor pair insertion in order to minimize dangling wires and channel width. Finally, in order to take routing bends and channel width into account simultaneously, we propose concurrent and sequential integer linear programming (ILP) formulations and ILP variable/constraint degeneration techniques. The experimental results demonstrate that our proposed heuristic routing framework reduces dangling wires by 19%, channel width by 38%, and wire length by 13% to VPR using the crossbar switch (VPR-C). In addition, our sequential ILP router reduces dangling wires by 38%, channel width by 40%, and wire length by 15% compared to VPR-C. Thus, the runtime efficiency of our sequential ILP router is attractive for crossbar-switch structured ASIC routing.

The identification of significant disease-related genes and networks is an important issue in understanding underlying mechanisms of cells. We integrate phenotype networks, protein networks and efficiently utilize gene expression data to identify human disease networks. We use prostate cancer data as our test domain. In comparison with statistical methods such as t-test and Wilcoxon test, our method identifies more prostate cancer-related genes reported in published database and literature. Interleukin-type growth factors, Ras related oncogenes and cytokine interactions canonical pathways are found to be significantly related to prostate cancer.

In recent years, structured application-specific integrated circuit (ASIC) design style has lessened the importance of mask cost. Multiple structured ASIC chip designs share the same pre-fabricated device and wire masks. Nevertheless, the interconnection delay in a pre-fabricated wire slows down circuit performance as a result of high capacitive load. We propose a dual-rail routing architecture that reduces wire delay by 10% to 15% compared to the original routing architecture. Furthermore, we propose a dual-rail insertion algorithm to reduce routing area overhead. The experimental results demonstrate that our dual-rail technique reduces wire delay by 9.8% with 4.8% routing area overhead and improves overall circuit performance by 7.0%.

In recent years, pre-fabricated design styles grow up rapidly to amortize the mask cost. However, the interconnection delay of the pre-fabricated design styles slows down the circuit performance due to the high capacitive load. In this paper, we propose a technique to insert dual-rail wires for pre-fabricated design styles. Furthermore, we propose an effective dual-rail insertion algorithm to reduce the routing area overheads caused by the inserted dual-rail wires. Taking the wire criticality, the delay significance, and the wire congestion into consideration, our proposed algorithm is capable of trading additional routing area overheads for the interconnection performance improvement. The experimental results demonstrate that our proposed algorithm reduces the interconnection delay by 11.4% with 5.8% routing area overheads.

The interconnection delay of pre-fabricated design style dominates circuit delay due to the heavily downstream capacitance. Buffer insertion is a widely used technique to split off a long wire into several buffered wire segments for circuit performance improvement. In this paper, we are motivated to investigate the buffer insertion issues in LUT-based structured ASIC design style. We design the layouts of two dedicated buffers and extract the technology dependent parameters for evaluations. After that, we propose a channel migration technique, which employs both intra-channel migration and inter-channel migration, to alleviate the sub-channel saturation problem. The experimental results demonstrate that dedicated buffers are essential for structured ASIC design style.

To achieve minimum signal propagation delay, the non-uniform wire width routing architecture has been widely used in modern VLSI design. The non-uniform routing architecture exploits the wire width flexibilities to trade area for performance. However, many additional design rules, which confine the routing flexibilities, are introduced in nanoscale circuit designs. With the increasing difficulties of fabricating nanoscale circuits, the conventional non-uniform routing architecture becomes clumsy. We propose an uniform dual-rail routing architecture to cope with these new challenges. The proposed architecture exploits the anti-Miller effect between two adjacent wires with the same signal source. Hence, the coupling capacitance between these two wires is reduced. The simulation results demonstrate that our proposed architecture provides a signal propagation channel with similar propagation delay, less crosstalk noise, and less power consumption to the conventional non-uniform routing architecture with moderate routing area overheads. In terms of the properties and the scalabilities, we argue that the uniform dual-rail routing architecture is a wire sizing alternative without incurring layout irregularity and stacked vias overheads.

We propose a logic synthesis flow to synthesize a domino-cell network with less crosstalk effect. Crosstalk-immunity property of or gate and relations between wire adjacency and cell I/O are exploited in technology mapping. Meanwhile, a metric to measure the crosstalk sensitivity of domino cells in synthesis level is proposed. Experimental results demonstrate that the crosstalk sensitivity of the synthesized domino-cell network is greatly reduced by 52% using our synthesis flow as compared with conventional methodology. Furthermore, after placement and routing are performed, the ratio of the number of crosstalk-immune wire pairs to the number of total wire pairs is about 24% using our methodology as compared to 9% using conventional techniques, and the maximum wire coupling can be greatly reduced from 95% to 60%

We propose a logic synthesis flow which utilizes the functionality of circuit to synthesize a domino-cell network which will have more wires crosstalk-immune to each other For that purpose, techniques of output phase flipping and crosstalk-aware technology mapping are used. Meanwhile, metric to measure the crosstalk sensitivity of domino cells in synthesis level is proposed. Experimental results demonstrate that the crosstalk sensitivity of the synthesized domino-cell network is greatly reduced by 51% using our synthesis flow as compared with conventional methodology. Furthermore, after placement and routing are performed, the ratio of the number of crosstalk-immune wire pairs to the number of total wire pairs is about 25% using our methodology as compared to 9% using conventional techniques.

We propose a maximum crosstalk effect minimization algorithm that takes logic synthesis into consideration for PLA structures. To minimize the crosstalk effect, a technique for permuting wire is used which contains the following steps. First, product terms are partitioned into long and short sets, and then the product terms in the long and short sets are interleaved. After that, we take advantage of the crosstalk immunity of product terms in the long set to further reduce the maximum coupling capacitance of the PLA. Finally, synthesis techniques such as local and global transformations are taken into consideration to search for a better result. The experiments demonstrate that our algorithm can effectively minimize the maximum coupling capacitance of a circuit by 51% as compared with the original area-minimized PLA without crosstalk effect minimization.

We propose a maximum crosstalk minimization algorithm taking logic synthesis into consideration for PLA structure. To minimize the crosstalk, technique of permuting wire is used which includes the following steps. First, product lines are partitioned into long set and short set, and then product lines in long set and short set are interleaved. By interleaving algorithm, an upper bound on the maximum coupling capacitance of the product lines can be derived. Then, we take advantage of crosstalk immunity of product lines in long set to further reduce the maximum crosstalk effect of the PLA. Finally, synthesis techniques such as local transformation and global transformation are taken into consideration to search for a better result. The experiments demonstrate that our algorithm can effectively minimize the maximum crosstalk effect of a circuit by 48% as compared with the original area-minimized PLA without crosstalk minimization.

In this paper, we will study the construction of a Steiner routing tree for a given net with the objective of minimizing the delay of the routing tree. Previous researches adopt Elmore delay model to compute delay. However, with the advancement of IC technology, a more accurate delay model is required. Therefore, in this paper, we will use two-pole delay model to compute the cost function of a Steiner tree. Moreover, we propose a new algorithm to construct the Steiner tree. Our algorithm takes into consideration the net topology, the total wire length and the longest path from the source to sink. Experimental results show that our algorithm is very effective and efficient as compared to [8].

We present methods to generate a Binary Decision Diagram (BDD) with minimum expected path length. A BDD is a generic data structure which is widely used in several fields. One important application is the representation of Boolean functions. A BDD representation enables us to evaluate a Boolean function: Simply traverse the BDD from the root node to the terminal node and retrieve the value in the terminal node. For a BDD with minimum expected path length will be also minimized the evaluation time for the corresponding Boolean function. Three efficient algorithms for constructing BDDs with minimum expected path length are proposed.