Llama is a widely used open-source large language model.This paper presents the design and implementation of the parallelism techniques used in Llama 3 pre-training.To achieve efficient training on tens of thousands of GPUs, Llama 3 employs a combination of four-dimensional parallelism: fully sharded data parallelism, tensor parallelism, pipeline parallelism, and context parallelism.Beyond achieving efficiency through parallelism and model co-design, we

Hardware systems composed of diverse execution resources are being deployed to cope with the complexity and performance requirements of Artificial Intelligence (AI) and Machine Learning (ML) applications. With the emergence of new hardware platforms, system-wide programming support has become much more important. While this is true for various devices ranging from CPUs to GPUs, it is especially critical for specific neural network accelerators implemented on FPGAs. For example, Intel’s recent HARP platform encompasses a Xeon CPU and an FPGA, which requires an intense software stack to be used effectively. Programming such a hybrid system will be a challenge for most of the non-expert users. High-level language solutions such as Intel OpenCL for FPGA try to address the problem. However, as the abstraction level increases, the efficiency of implementation decreases, depicting two opposing requirements. In this work, we propose a framework to generate HLS-based, FPGA-accelerated, high-throughput/work-efficient, synthesizable, and template-based graph-processing pipeline. While a fixed and clock-wise precisely designed deep-pipeline architecture, written in SystemC, is responsible for processing graph vertices, the user implements the intended iterative graph algorithm by implementing/modifying only a single module in C/C++. This way, efficiency and high performance can be achieved with better programmability and productivity. With similar programming efforts, it is shown that the proposed template outperforms a high-throughput OpenCL baseline by up to 50% in terms of edge throughput. Furthermore, the novel work-efficient design significantly improves execution time and power consumption by up to 100×.

Deep learning recommendation models (DLRMs) have been used across many business-critical services at Meta and are the single largest AI application in terms of infrastructure demand in its data-centers. In this paper, we present Neo, a software-hardware co-designed system for high-performance distributed training of large-scale DLRMs. Neo employs a novel 4D parallelism strategy that combines table-wise, row-wise, column-wise, and data parallelism for training massive embedding operators in DLRMs. In addition, Neo enables extremely high-performance and memory-efficient embedding computations using a variety of critical systems optimizations, including hybrid kernel fusion, software-managed caching, and quality-preserving compression. Finally, Neo is paired with ZionEX, a new hardware platform co-designed with Neo's 4D parallelism for optimizing communications for large-scale DLRM training. Our evaluation on 128 GPUs using 16 ZionEX nodes shows that Neo outperforms existing systems by up to 40× for training 12-trillion-parameter DLRM models deployed in production.

Datacenter-scale AI training clusters consisting of thousands of domain-specific accelerators (DSA) are used to train increasingly-complex deep learning models. These clusters rely on a data storage and ingestion (DSI) pipeline, responsible for storing exabytes of training data and serving it at tens of terabytes per second. As DSAs continue to push training efficiency and throughput, the DSI pipeline is becoming the dominating factor that constrains the overall training performance and capacity. Innovations that improve the efficiency and performance of DSI systems and hardware are urgent, demanding a deep understanding of DSI characteristics and infrastructure at scale.

Large-scale graph analytics has gained importance due to emergence of new applications in different contexts such as web, social networks, and computational biology. It is known that typical CPU/GPU implementations for sparse graph applications cannot efficiently utilize the available compute resources. In our previous work, we have shown that significant performance and energy efficiency improvements can be achieved using custom hardware accelerators for graph applications. On the other hand, designing application-specific hardware is expensive in terms of engineering, manufacturing, and maintenance costs. Since FPGAs are known to provide a good tradeoff between customizability and efficiency, several prominent vendors have started offering data-center solutions with FPGAs.

Memory access is known to be the main bottleneck for shared-memory parallel graph applications especially for large and irregular graphs. Propagation blocking (PB) idea was proposed recently to improve the parallel performance of PageRank and sparse matrix and vector multiplication operations. The idea is based on separating parallel computation into two phases, binning and accumulation, such that random memory accesses are replaced with contiguous accesses. In this paper, we propose an algorithm that allows execution of these two phases concurrently. We propose several improvements to increase parallel throughput, reduce memory overhead, and improve work efficiency. Our experimental results show that our proposed algorithms improve shared-memory parallel throughput by a factor of up to 2× compared to the original PB algorithms. We also show that the memory overhead can be reduced significantly (from 170 percent down to less than 5 percent) without significant degradation of performance. Finally, we demonstrate that our concurrent execution model allows asynchronous parallel execution, leading to significant work efficiency in addition to throughput improvements.

Graph applications have been gaining importance in the last decade due to emerging big data analytics problems such as Web graphs, social networks, and biological networks. For these applications, traditional CPU and GPU architectures suffer in terms of performance and power consumption due to irregular communications, random memory accesses, and load balancing problems. It has been shown that specialized hardware accelerators can achieve much better power and energy efficiency compared to the general purpose CPUs and GPUs. In this paper, we present a template-based methodology specifically targeted for hardware accelerator design of big-data graph applications. Important architectural features that are key for energy efficient execution are implemented in a common template. The proposed template-based methodology is used to design hardware accelerators for different graph applications with little effort. Compared to an application-specific high-level synthesis methodology, we show that the proposed methodology can generate hardware accelerators with up to 18× better energy efficiency and requires less design effort.

No abstract available.

Specialized hardware accelerators can significantly improve the performance and power efficiency of compute systems. In this paper, we focus on hardware accelerators for graph analytics applications and propose a configurable architecture template that is specifically optimized for iterative vertex-centric graph applications with irregular access patterns and asymmetric convergence. The proposed architecture addresses the limitations of the existing multi-core CPU and GPU architectures for these types of applications. The SystemC-based template we provide can be customized easily for different vertex-centric applications by inserting application-level data structures and functions. After that, a cycle-accurate simulator and RTL can be generated to model the target hardware accelerators. In our experiments, we study several graph-parallel applications, and show that the hardware accelerators generated by our template can outperform a 24 core high end server CPU system by up to 3x in terms of performance. We also estimate the area requirement and power consumption of these hardware accelerators through physical-aware logic synthesis, and show up to 65x better power consumption with significantly smaller area.

Intelligent data analysis has become more important in the last decade especially because of the significant increase in the size and availability of data. In this paper, we focus on the common execution models and characteristics of iterative graph analytics applications. We show that the features that improve work efficiency can lead to significant overheads on existing systems. We identify the opportunities for custom hardware implementation, and outline the desired architectural features for energy efficient computation of graph analytics applications.

As the size of available data is increasing, it is becoming inefficient to scale the computational power of traditional systems. To overcome this problem, customized application-specific accelerators are becoming integral parts of modern system on chip (SOC) architectures. In this paper, we summarize existing hardware accelerators for data centers and discuss the techniques to implement and embed them along with the existing SOCs.

Advanced technology nodes have engendered new challenges in the design of integrated circuits (ICs), which can only be addressed through innovations in physical design techniques and algorithms. These challenges stem from factors such as increasingly complex manufacturing design rules, cell pin access in technologies utilizing multiple patterning and FinFETs, various types of restrictions and blockages on the routing layers, and complexity of the physical floorplan, for example due to irregular shapes of placeable areas. This issue and the next issue feature the special section on physical design aimed at addressing these challenges.

Heterogeneous architectures with single-instruction set architecture (ISA) asymmetric cores can improve both the performance and energy efficiency of software execution by dynamically selecting the most appropriate core type to run each execution thread. In this paper, we propose a trace-based methodology to explore power and performance benefits of single-ISA heterogeneous core architectures. The basic idea is to collect multiple traces by running a workload on different homogeneous platforms, and to align these traces for offline analysis. For this, we propose a wavelet-based similarity metric, which captures both fine-grain and coarse-grain software phases across different traces. Then, we propose a scalable dynamic programming algorithm to optimize this metric to align the traces. Our experiments show that the runtime and energy values predicted by our offline methodology have good accuracy with respect to the real measurements from a prototype heterogeneous system.

In parallel linear iterative solvers, sparse matrix vector multiplication (SpMxV) incurs irregular point-to-point (P2P) communications, whereas inner product computations incur regular collective communications. These P2P communications cause an additional synchronization point with relatively high message latency costs due to small message sizes. In these solvers, each SpMxV is usually followed by an inner product computation that involves the output vector of SpMxV. Here, we exploit this property to propose a novel parallelization method that avoids the latency costs and synchronization overhead of P2P communications. Our method involves a computational and a communication rearrangement scheme. The computational rearrangement provides an alternative method for forming input vector of SpMxV and allows P2P and collective communications to be performed in a single phase. The communication rearrangement realizes this opportunity by embedding P2P communications into global collective communication operations. The proposed method grants a certain value on the maximum number of messages communicated regardless of the sparsity pattern of the matrix. The downside, however, is the increased message volume and the negligible redundant computation. We favor reducing the message latency costs at the expense of increasing message volume. Yet, we propose two iterative-improvementbased heuristics to alleviate the increase in the volume through one-to-one task-to-processor mapping. Our experiments on two supercomputers, Cray XE6 and IBM BlueGene/Q, up to 2,048 processors show that the proposed parallelization method exhibits superior scalable performance compared to the conventional parallelization method.

Exact route matching is an important constraint for analog and mixed signal designs with nonuniform metal stacks. In this paper, we propose a constrained-path-based maze routing algorithm that can handle exact matching constraints for multiple nets. We also propose a scalable framework that utilizes the proposed maze routing algorithm for realistic problem sizes. Compared to the pattern routing algorithms proposed recently , our algorithms allow a more thorough exploration of the solution space by allowing bends to be inserted to avoid congested regions. Furthermore, we propose an ILP-based model to explore the impact of the initial routing topologies on the final solutions. Our experimental study demonstrates that the proposed algorithm leads to significant reductions in congestion costs compared to the previous algorithm.

Heterogeneous architectures with single-ISA asymmetric cores have the potential to improve both the performance and energy efficiency of software execution by dynamically selecting the most appropriate core type to run each execution thread. In this paper, we propose a trace-based methodology to explore power and performance benefits of single-ISA heterogeneous core architectures. The basic idea is to collect multiple traces by running a workload on different homogeneous platforms, and to align these traces for offline analysis. For this, we propose a wavelet-based similarity metric, which captures both fine-grain and coarse-grain software phases across different traces. Then, we propose a scalable dynamic programming algorithm to optimize this metric to align the traces. Our experiments show that the runtime and energy values predicted by our offline methodology have good accuracy with respect to the real measurements from a prototype heterogeneous system. The proposed methodology can enable design space exploration of single-ISA heterogeneous multi-core systems using traces from off-the-shelf homogeneous systems.

Gate sizing and threshold voltage selection is an important step in the VLSI design process to optimize power and performance of a given netlist. In this paper, we provide an overview of the ISPD-2013 Discrete Cell Sizing Contest. Compared to the ISPD-2012 Contest, we propose improvements in terms of the benchmark suite and the timing models utilized. In this paper, we briefly describe the contest, and provide some details about the standard cell library, benchmark suite, timing infrastructure and the evaluation metrics.

Design automation for analog and mixed signal designs has become more important, as analog and digital components are integrated on the same system-on-chips (SOCs). Exact route matching is an important constraint for analog and mixed signal designs with non-uniform metal stacks. In this paper, we propose a constrained-path based maze routing algorithm that can handle exact matching constraints for multiple nets. We also propose a scalable framework that utilizes the proposed maze routing algorithm for realistic problem sizes. Compared to the pattern routing algorithms proposed recently [8], our algorithms allow a more thorough exploration of the solution space by allowing bends to be inserted to avoid congested regions. The experimental study demonstrates that the proposed algorithm leads to significant reductions in congestion costs compared to the previous algorithm.

Circuit optimization is essential to minimize power consumption of designs while satisfying timing constraints. The CAD problem focused on in the ISPD-2012 Contest is simultaneous gate sizing and threshold voltage assignment. In this paper, we describe an overview of the contest objectives and the provided benchmark suite. Furthermore, some details are provided in terms of the standard cell library, timing models, and the evaluation metrics of the ISPD-2012 Contest.

It is becoming increasingly important to design high-performance circuits with as low power as possible. In this paper, we study the gate sizing and device parameter selection problem for today's industrial designs. We first outline the typical practical problems that make it difficult to use traditional algorithms on high-performance industrial designs. Then, we propose a Lagrangian relaxation-based formulation that decouples timing analysis from optimization without a resulting loss in accuracy. We also propose a graph model that accurately captures discrete cell-type characteristics based on library data. We model the relaxed Lagrangian subproblem as a graph problem and propose algorithms to solve it. In our experiments, we demonstrate the importance of using the signoff timing engine to guide the optimization. We also show the benefit of the graph model we propose to solve the discrete optimization problem. Compared to a state-of-the art industrial optimization flow, we show that our algorithms can obtain up to 38% leakage power reductions and better overall timing for real high-performance microprocessor blocks.

It is becoming more and more important to design high performance designs with as low power as possible. In this paper, we study the gate sizing and device technology selection problem for today's industrial designs. We first outline the typical practical problems that make it difficult to use the traditional algorithms on high-performance industrial designs. Then, we propose a Lagrangian Relaxation (LR) based formulation that decouples timing analysis from optimization without resulting in loss of accuracy. We also propose a graph model that accurately captures discrete cell type characteristics based on library data. We model the relaxed Lagrangian subproblem as a discrete graph problem, and propose algorithms to solve it. In our experiments, we demonstrate the importance of using the signoff timing engine to guide the optimization. Compared to a state-of-the art industrial optimization flow, we show that our algorithms can obtain up to 38% leakage power reductions and better overall timing for real high-performance microprocessor blocks.

As system-on-chip designs are getting more popular, the importance of design automation for analog and mixed-signal integrated circuits is increasing. In this paper, we study the problem of exact route matching, which is an important physical design constraint commonly imposed on specific analog signals for the purpose of correct functionality. For this, we first propose a mathematical formulation that models the route matching problem exactly. Based on this formulation, we derive important theoretical conclusions, and propose dynamic-programming and heuristic search algorithms to solve the min-cost route matching problem. We also discuss various practical considerations related to this problem. Our experimental results show the effectiveness of our algorithms.

As SOC designs are getting more popular, the importance of design automation for analog and mixed-signal ICs is increasing. In this paper, we study the problem of exact route matching, which is an important physical design constraint commonly imposed on specific analog signals for the purpose of correct analog functionality. For this, we first propose a mathematical formulation that models the route matching problem exactly. Based on this formulation, we derive important theoretical conclusions, and propose dynamic-programming algorithms to solve the problem. We also discuss how to use heuristic search techniques to enable faster computations. Our experimental results show the effectiveness of our algorithms.

As design complexities and circuit densities are increasing, the detailed-routing (DR) problem is becoming a more and more challenging problem. Due to the high complexity of DR algorithms, it is very important to start the routing process with clean solutions rather than starting with suboptimal routes and trying to fix them in an iterative process. In this paper, we propose an escape-routing algorithm that can optimize routing of a set of nets around their terminals. For this, we first propose a polynomial-time algorithm that guarantees to find the optimal escape-routing solution for a set of nets when the track structures are uniform. Then, we use this algorithm as a baseline and study the general problem with arbitrary track structures. For this, we propose a novel multicommodity-flow (MCF) model that has a one-to-one correspondence with the escape-routing problem. This MCF model is novel in the sense that the interdependence and contention between different flow commodities is minimal. Using this model, we propose a Lagrangian-relaxation-based algorithm to solve the escape problem. Our experiments demonstrate that this algorithm improves the overall routability significantly by reducing the number of nets that require rip-up and reroute.

Global routing is an important step in the physical design process. In this paper, we propose a new global routing algorithm Archer, which resolves some of the most common problems with the state-of-the-art global routers. It is known that concurrent global routing algorithms are typically too expensive to be applied on today's large designs, which may contain up to a million nets. On the other hand, iterative rip-up and reroute (RNR)-based algorithms are susceptible to getting stuck in local optimal solutions. In this paper, we propose an RNR-based global routing algorithm that guides the routing iterations out of local optima through effective usage of congestion histories. We also focus on the problem of how to enable a smooth tradeoff between seemingly conflicting objectives of overflow and wirelength minimization. Furthermore, we propose a Lagrangian relaxation-based bounded-length min-cost topology improvement algorithm that enables Steiner trees to change dynamically for the purpose of congestion optimization. Our experiments on public benchmarks show the effectiveness of Archer compared to other state-of-the-art global routers.

Shrinking transistor sizes, increasing circuit complexities, and high clock frequencies bring new board-routing challenges that cannot be handled effectively by traditional routing algorithms. Many high-end designs in the industry today require manual routing efforts, which increases the design-cycle times considerably. In this paper, we propose an escape-routing algorithm to route nets within multiple dense components simultaneously so that the number of crossings in the intermediate area is minimized. We also show how to handle high-speed-design constraints within the framework of this algorithm. Experimental comparisons with a recently proposed algorithm show that our algorithm reduces the via requirements of industrial test cases on average by 39%.

As the circuit densities and transistor counts are increasing, the package routing problem is becoming more and more challenging. In this article, we study an important routing problem encountered in typical high-end MCM designs: routing within dense pin clusters. Pin clusters are often formed by pins that belong to the same functional unit or the same data bus, and can become bottlenecks in terms of overall routability. Typically, these clusters have irregular shapes, which can be approximated with rectilinear convex boundaries. Since such boundaries have often irregular shapes, a traditional escape routing algorithm may give unroutable solutions. In this article, we study how the positions of escape terminals on a convex boundary affect the overall routability. For this purpose, we propose a set of necessary and sufficient conditions to model routability outside a rectilinear convex boundary. Given an escape routing solution, we propose an optimal algorithm to select the maximal subset of nets that are routable outside the boundary. After that, we focus on an integrated approach to consider routability constraints (outside the boundary) during the actual escape routing algorithm. Here, we propose an optimal algorithm to find the best escape routing solution that satisfies all routability constraints. Our experiments demonstrate that we can reduce the number of layers by 17% on the average, by using this integrated methodology.

As the design complexities and circuit densities are increasing, the detailed routing (DR) problem is becoming a more and more challenging problem. Due to the high complexity of DR algorithms, it is very important to start the routing process with clean solutions, rather than starting with suboptimal routes and trying to fix them in iterative process. In this paper, we propose an escape routing algorithm that can optimize routing of a set of nets around their terminals. For this, we first propose a polynomial-time algorithm that guarantees to find the optimal escape routing solution for a set of nets when the track structures are uniform. Then, we use this algorithm as a baseline, and study the general problem with arbitrary track structures. For this, we propose a novel multi-commodity flow (MCF) model that has a one-to-one correspondence with the escape routing problem. This MCF model is novel in the sense that the inter-dependency and contention between different flow commodities is minimal. Using this model, we propose a Lagrangian-relaxation (LR) based algorithm to solve the escape problem. Our experiments demonstrate that this algorithm improves the overall routability significantly by reducing the number of nets that require rip-up and reroute.

The PCB routing problem has become so difficult that no commercial CAD software can provide an automatic solution for high-end boards. Existing algorithms for escape routing, an important step in PCB routing, are net-centric. Directly applying these algorithms will result in mixing nets of different buses together. But in practice, it is preferred to bundle together nets in a bus. Thus the bus-centric escape routing problem can be naturally divided into two subproblems: (1) finding a subset of buses that can be routed on the same layer without net mixings and crossings, which we refer to as the bus sequencing problem, and (2) finding the escape routing solutions for each chosen bus, which can be solved by a net-centric escape router. In this paper, we solve the bus sequencing problem. We introduce a new optimization problem called the longest common interval Sequence (LCIS) problem and model the bus sequencing problem as an LCIS problem. By using dynamic programming and balanced search tree data structure, we present an LCIS algorithm which can find an optimal solution in O(n log n) time. We also show that O(n log n) is a lower-bound for this problem and thus the time complexity of our algorithm is also the best possible.

Global routing is an important step in the physical design process. In this paper, we propose a new global routing algorithm Archer, which resolves some of the most common problems with the state-of- the-art global routers. It is known that concurrent global rou- ting algorithms are typically too expensive to be applied on today’s large designs, which may contain up to a million nets. On the other hand, iterative rip-up and reroute (RNR) based algorithms are sus- ceptible to getting stuck in local optimal solutions. In this paper, we propose an RNR-based global routing algorithm that guides the routing iterations out of local optima through effective usage of con- gestion histories. We also focus on the problem of how to enable a smooth trade-off between seemingly conflicting objectives of over- flow and wirelength minimization. Furthermore, we propose a Lagrangian relaxation based bounded-length min-cost topology improvement algorithm that enables Steiner trees to change dynamically for the purpose of congestion optimization. Our experiments show that Archer obtains congestion-free solutions for all circuits in the standard ISPD98 benchmarks, which is the best result published so far. Furthermore, it produces better results than the best results reported in the ISPD-07 Global Routing Contest in terms of routability. Compared to FastRoute [18, 19], which is the state-of- the-art RNR-based global routing algorithm, Archer improves routability by 30%, and reduces the wirelengths by 32% on the av- erage on ISPD07 benchmarks.

As the clock frequencies used in industrial applications increase, the timing requirements on routing problems become tighter, and current routing tools cannot successfully handle these constraints any more. In this paper, the authors focus on the high-performance single-layer bus routing problem, where the objective is to match the lengths of all nets belonging to each bus. An effective approach to solve this problem is to allocate extra routing resources around short nets during routing, and use those resources for length extension afterwards. First, a provably optimal algorithm for routing nets with minimum-area maximum-length constraints is proposed. Then, this algorithm is extended to the case where minimum constraints are given as exact length bounds, and it is also proven that this algorithm is near-optimal. Both algorithms proposed are shown to be scalable for large circuits, since the respective time complexities are O(A) and O(AlogA), where A is the area of the intermediate region between chips.

As die sizes are shrinking, and circuit complexities are increasing, the printed circuit board routing problem becomes more and more challenging. Traditional routing algorithms cannot handle these challenges effectively, and many high-end designs in the industry require manual routing efforts. This paper proposes a problem decomposition that distinguishes routing under dense components from routing in the intermediate area. In particular, it proposes an effective methodology to find the escape routing solution for multiple components simultaneously such that the number of crossings in the intermediate area is minimized. For this, the problem is modeled as a longest path with forbidden pairs problem, and two algorithms are proposed for it. The first is an exact polynomial-time algorithm that is guaranteed to find the maximal planar routing solution on one layer. The second is a randomized algorithm that has good scalability characteristics for large circuits. Then, these algorithms are used to assign the maximal subset of planar nets to each layer, and then the remaining nets are distributed at the end. This paper demonstrates the effectiveness of these algorithms through experiments on industrial circuits.

As the clock frequencies used in industrial applications increase, the timing requirements imposed on routing problems become tighter. Therefore, it becomes important to route the nets within tight minimum and maximum length bounds. Although the problem of routing nets to satisfy maximum length constraints is a well-studied problem, there exists no sophisticated algorithm in literature that ensures that minimum length constraints are also satisfied. In this paper, the authors propose a novel algorithm that effectively incorporates the min–max length constraints into the routing problem. The approach is to use a Lagrangian-relaxation (LR) framework to allocate extra routing resources around nets simultaneously during routing them. The authors also propose a graph model that ensures that all the allocated routing resources can be used effectively for extending lengths. Their routing algorithm automatically prioritizes resource allocation for shorter nets and length minimization for longer nets so that all nets can satisfy their min–max length constraints. This paper demonstrates that this algorithm is effective even in the cases where length constraints are tight, and the spacing between adjacent nets is small.

The increasing clock frequencies in high-end industrial circuits bring new routing challenges that cannot be handled by traditional algorithms. An important design automation problem for high-speed boards today is routing nets within tight minimum and maximum length bounds. In this article, we propose an algorithm for routing bus structures between components on two layers such that all length constraints are satisfied. This algorithm handles length extension simultaneously during the actual routing process so that maximum resource utilization is achieved during length extension. Our approach here is to process one track at a time, and choose the best subset of nets to be routed on each track. The algorithm we propose for single-track routing is guaranteed to find the optimal subset of nets together with the optimal solution with length extension on one track. The experimental comparison with a recently proposed technique shows the effectiveness of this algorithm both in terms of solution quality and run-time.

Shrinking transistor sizes, increasing circuit complexities, and high clock frequencies bring new board routing challenges that cannot be handled effectively by traditional routing algorithms. Many high-end designs in the industry today require manual routing efforts, which increases the design cycle times considerably. In this paper, we propose an escape routing algorithm to route nets within multiple dense components simultaneously so that the number of crossings in the intermediate area is minimized. We also show how to handle high-speed design constraints within the framework of this algorithm. Experimental comparisons with a recently proposed algorithm (Ozdal and Wong, 2004) show that our algorithm reduces the via requirements of industrial test cases on average by 39%.

Optimal routing algorithms for pin clusters in high-density multichip modules As the circuit densities and transistor counts are increasing, the package routing problem is becoming more and more challenging. In this paper, we study an important routing problem encountered in typical high-end MCM designs: routing within dense pin clusters. Pin clusters are often formed by pins that belong to the same functional unit or the same data bus, and can become bottlenecks in terms of overall routability. Topically, these clusters have irregular shapes, which can be approximated with rectilinear convex boundaries. Since such boundaries have often irregular shapes, a traditional escape routing algorithm may give unroutable solutions. In this paper, we study how the positions of escape terminals on a convex boundary affect the overall routability. For this purpose, we propose a set of necessary and sufficient conditions to model routability outside a rectilinear convex boundary. Given an escape routing solution, we propose an optimal algorithm to select the maximal subset of nets that are routable outside the boundary. After that, we focus on an integrated approach to consider routability constraints (outside the boundary) during the actual escape routing algorithm. Here, we propose an optimal algorithm to find the best escape routing solution that satisfies all routability constraints. Our experiments demonstrate that we can reduce the number of layers by 17% on the average, by using this integrated methodology.

As die sizes are shrinking, and circuit complexities are increasing, the PCB routing problem becomes more and more challenging. Traditional routing algorithms can not handle these challenges effectively, and many high-end designs in the industry require manual routing efforts. In this paper, we propose a problem decomposition that distinguishes routing within dense components from routing in the intermediate area. In particular, we propose an effective methodology to find the escape routing solution for multiple components simultaneously such that the number of crossings in the intermediate area is minimized. For this, we model the problem as a longest path with forbidden pairs (LPFP) problem, and propose two algorithms for it. The first is an exact polynomial-time algorithm that is guaranteed to find the maximal planar routing solution on one layer. The second is a randomized algorithm that has good scalability characteristics for large circuits. Then we use these algorithms to assign the maximal subset of planar nets to each layer, and then distribute the remaining nets at the end. We demonstrate the effectiveness of these algorithms through experiments on industrial circuits.

As the clock frequencies used in industrial applications increase, the timing requirements on routing problems become tighter, and current routing tools can not successfully handle these constraints any more. We focus on the high-performance single-layer bus routing problem, where the objective is to match the lengths of all nets belonging to each bus. An effective approach to solve this problem is to allocate extra routing resources around short nets during routing; and use those resources for length extension afterwards. We first propose a provably optimal algorithm for routing nets with min-area max-length constraints. Then, we extend this algorithm to the case where minimum constraints are given as exact length bounds. We also prove that this algorithm is optimal within a constant factor. Both algorithms proposed are also shown to be scalable for large circuits, since the respective time complexities are O(A) and O(A log A), where A is the area of the intermediate region between chips.

The increasing clock frequencies in high-end industrial circuits bring new routing challenges that cannot be handled by traditional algorithms. An important design automation problem for high-speed boards today is routing nets within tight minimum and maximum length bounds. In this paper, we propose an algorithm for routing bus structures between components on two layers such that all length constraints are satisfied. This algorithm handles length extension simultaneously during the actual routing process so that maximum resource utilization is achieved during length extension. Our approach here is to process one track at a time, and choose the best subset of nets to be routed on each track. The algorithm we propose for single-track routing is guaranteed to find the optimal subset of nets together with the optimal solution with length extension on one track. The experimental comparison with a recently proposed technique shows the effectiveness of this algorithm both in terms of solution quality and run-time.