A chief enabler of large-scale deep learning is the distribution of computation across multiple interconnected hardware accelerators. In order to unlock the maximum possible performance, a compiler must first select a reasonable strategy to parallelize a model's operations. Since neural network architectures admit multiple flavors of parallelism, determining the proper strategy for each instruction is a critical (albeit non-trivial) task. To solicit new ideas toward solving this challenging combinatorial optimization problem, we organized the ASPLOS 2025 / EuroSys 2025 Contest on Intra-Operator Parallelism for Distributed Deep Learning, a multi-month competition focused on advancing the state-of-the-art for model partitioning algorithms. In this paper, we offer a retrospective of this event, including the basic problem formulation, key challenges & opportunities, our new benchmark suite, and the quality of submissions received.

We present a new approach to static memory allocation, a key problem that arises in the compilation of machine learning models onto the resources of a specialized hardware accelerator. Our methodology involves a recursive depth-first search that limits exploration to a special class of canonical solutions, dramatically reducing the size of the search space. We also develop a spatial inference technique that exploits this special structure by pruning unpromising partial assignments and backtracking more effectively than otherwise possible. Finally, we introduce a new mechanism capable of detecting and eliminating dominated solutions from consideration. Empirical results demonstrate orders of magnitude improvement in performance as compared to the previous state-of-the-art on many benchmarks, as well as a substantial reduction in library size.

We consider an application of combinatorial search to the optimization of topologies in series-parallel networks. We propose a recursive search over the space of decomposition trees, in which partial solutions are obtained by exploring k-way partitionings of expandable nodes. We present two complementary pruning techniques that bound the value of intermediate solutions from above and below, applying monotonic operations to the contents of unresolved leaves. We also develop a means to exploit the convexity of our objective function, so as to prevent the redundant recomputation of subcircuit configurations. Finally, we evaluate our approach on a parameterized benchmark suite of electrical circuits, demonstrating over an order of magnitude improvement in performance as compared to a baseline implementation.

The NP-hard number-partitioning problem is to separate a multiset S of n positive integers into k subsets such that the largest sum of the integers assigned to any subset is minimized. The classic application is scheduling a set of n jobs with different runtimes on k identical machines such that the makespan, the elapsed time to complete the schedule, is minimized. The two-way number-partitioning decision problem is one of the original 21 problems that Richard Karp proved NP-complete. It is also one of Garey and Johnson’s six fundamental NP-complete problems and the only one based on numbers. This article explores algorithms for solving multi-way number-partitioning problems optimally. We explore previous algorithms as well as our own algorithms, which fall into three categories: sequential number partitioning (SNP), a branch-and-bound algorithm; binary-search improved bin completion (BSIBC), a bin-packing algorithm; and cached iterative weakening (CIW), an iterative weakening algorithm. We show experimentally that, for large random numbers, SNP and CIW are state-of-the-art algorithms depending on the values of n and k . Both algorithms outperform the previous state of the art by up to seven orders of magnitude in terms of runtime.

Hardware acceleration is a critical component in any modern functional verification methodology. To achieve the best possible utilization, a compiler must intelligently map a logical netlist to the various resources available in the machine architecture. For instance, instructions that serve to route signals between processors must be carefully balanced with those that encode Boolean operations. In addition, chip-to-chip communication should be reduced whilst also ensuring that logic is appropriately partitioned to be executed concurrently. This process is exacerbated by hard constraints on accelerator capacity, as well as rapidly growing industrial designs that approach billions of gates in size. In this paper, we present several compilation strategies that optimize resource allocation to curtail simulation depth, leverage design hierarchy to reduce runtime and memory, and exploit parallel processing to further improve performance. We also review the history of hardware acceleration within IBM, and describe the evolution in architecture that has driven many of these advances in compilation.

Despite remarkable progress in the area of global routing, the burdens imposed by modern physical synthesis flows are far greater than those expected or anticipated by available (academic) routing engines. As interconnects dominate the path delay, physical synthesis such as buffer insertion and gate sizing has to integrate with layer assignment. Layer directives - commonly generated during wire synthesis to meet tight frequency targets - play a critical role in reducing interconnect delay of smaller technology nodes. Unfortunately, they are not presently understood or honored by leading global routers, nor do existing techniques trivially extend toward their resolution. The shortcomings contribute to a dangerous blindspot in optimization and timing closure, leading to unroutable and/or underperforming designs. In this paper, we aim to resolve the layer compliance problem in routing congestion evaluation and global routing, which is very critical for timing closure with physical synthesis. We propose a method of progressive projection to account for wire tags and layer directives, in which classes of nets are successively applied and locked while performing partial aggregation. The method effectively models the resource contention of layer constraints by faithfully accumulating capacity of bounded layer ranges, enabling three-dimensional assignment to subsequently achieve complete directive compliance. The approach is general, and can piggyback on existing interfaces used to communicate with popular academic engines. Empirical results on the IC-CAD 2009 benchmarks demonstrate that our approach successfully routes many designs that are otherwise unroutable with existing techniques and naïve approaches.

We introduce a method of partitioning for massively-parallel hardware accelerated functional verification. Our approach augments classical hypergraph partitioning to model temporal dependencies that maximize parallelization within the instruction memories of the machine. Simulation depth is further reduced by optimizing path criticality and cut directionality. Our techniques are demonstrated on an industrial accelerator containing 262,144 parallel processors, and benchmarked across designs containing up to 200 million gates.

Traditionally, the goal of physical synthesis has been to produce a physical realization of the input netlist that meets its timing constraints with minimum area. However, design routability has emerged from a secondary objective to perhaps the primary objective, in no small part due to the myriad of rules and constraints that emerge with each successive technology. This work overviews the complexities with modeling congestion during physical synthesis and discusses how optimizations may be able to provide some relief.

Recent progress in the area of global routing has been remarkable; yet, in many ways, the classical formulation has yet to catch up with the demands imposed by modern physical synthesis flows. In this work, we visit (and revisit) the topic of global routing. We provide a brief review of global routing's history, and touch on recent work that has contributed to the state-of-the-art in the field. While we cover in depth the basic principles behind leading approaches, we also emphasize open challenges and problems that remain unresolved. We argue that not only does the current academic formulation lack key components of the true routing problem - such as scenic control, layer directives, and capabilities for integration with physical synthesis - but also that present methods are likely to fail when extended toward the more generalized formulation. Finally, we offer a revised incarnation of the ISPD benchmarks to encourage continued progress in the research community.

In this paper, we present the complete design and architectural details of MAIZEROUTER.MAIZEROUTER reflects a significant leap in progress over existing publicly available routing tools yet relies upon relatively simple operations, including extreme edge shifting, a technique aimed primarily at the efficient reduction of routing congestion, and edge retraction, a counterpart to extreme edge shifting that serves to reduce unnecessary wirelength.We present enhanced variations of these operations to enable the rapid exploration of candidate paths, along with a form of dynamic cost deflation that provides our various path computation procedures with progressively more accurate (and less optimistic) cost information as search continues.These algorithmic contributions are built upon a framework of interdependent net decomposition, a representation that improves upon traditional two-pin net decomposition by preventing duplication of routing resources while enabling cheap and incremental topological reconstruction.Collectively, these operations permit a broad search space that previous algorithms have been unable to achieve, resulting in solutions of considerably higher quality than those of well-established routers.

A fundamental problem in timing-driven physical synthesis is the reduction of critical paths in a design. In this work, we propose a powerful new technique that moves (and can also resize) multiple cells simultaneously to smooth critical paths, thereby reducing delay and improving worst negative slack or a figure-of-merit. Our approach offers several key advantages over previous formulations, including the accurate modeling of objectives and constraints in the true timing model, and a guarantee of legality for all cell locations.

Wire routing, an important step in modern VLSI design, is increasingly responsible for timing closure and manufacturability. The CAD community has witnessed remarkable improvements in speed and quality of global routing algorithms in response to the inaugural ISPD 2007 Global Routing Contest, where prizes were awarded for best results on a new set of large industry benchmarks.

Physical synthesis tools are responsible for achieving timing closure. Starting with 130nm designs, multiple cycles are required to cross the chip, making latch placement critical to success. We present a new physical synthesis optimization for latch placement called RUMBLE (Rip Up and Move Boxes with Linear Evaluation) that uses a linear timing model to optimize timing by simultaneously re-placing multiple gates. RUMBLE runs incrementally and in conjunction with static timing analysis to improve the timing for critical paths that have already been optimized by placement, gate sizing, and buffering. Experimental results validate the effectiveness of the approach: our techniques improve slack by 41.3% of cycle time on average for a large commercial ASIC design

In this paper, we present the complete design and architectural details of MaizeRouter. MaizeRouter reflects a significant leap in progress over existing publicly available routing tools yet relies upon relatively simple operations, includingextremeedgeshifting, a technique aimed primarily at the efficient reduction of routing congestion, andedgeretraction, a counterpart to extreme edge shifting that serves to reduce unnecessary wirelength. We present enhanced variations of these operations to enable therapidexplorationof candidate paths, along with a form ofdynamiccostdeflationthat provides our various path computation procedures with progressively more accurate (and less optimistic) cost information as search continues. These algorithmic contributions are built upon a framework ofinterdependentnet decomposition, a representation that improves upon traditional two-pin net decomposition by preventing duplication of routing resources while enabling cheap and incremental topological reconstruction. Collectively, these operations permit a broad search space that previous algorithms have been unable to achieve, resulting in solutions of considerably higher quality than those of well-established routers.

Physical-synthesis tools are responsible for achieving timing closure. Starting with 130-nm designs, multiple cycles are required to cross the chip, making latch placement critical to success. We present a new physical-synthesis optimization for latch placement called Rip Up and Move Boxes with Linear Evaluation (RUMBLE) that uses a linear timing model to optimize timing by simultaneously replacing multiple gates. RUMBLE runs incrementally and in conjunction with static timing analysis to improve the timing for critical paths that have already been optimized by placement, gate sizing, and buffering. Experimental results validate the effectiveness of the approach: Our techniques improve slack by 41.3% of cycle time on average for a large commercial ASIC design.

In this work, we propose a new and efficient approach to the floorplan repair problem, where violated design constraints are satisfied by applying small changes to an existing rough floorplan. Such a floorplan can be produced by a human designer, a scalable placement algorithm, or result from engineering adjustments to an existing floorplan. In such cases, overlapping modules must be separated, and others may need to be repositioned to satisfy additional requirements. Our algorithmic framework uses an expressive graph-based encoding of constraints which can reflect fixed-outline, region, proximity and alignment constraints. By tracking the implications of existing constraints, we resolve violations by imposing gradual modifications to the floorplan, in an attempt to preserve the characteristics of its initial design. Empirically, our approach is effective at removing overlaps and repairing violations that may occur when design constraints are acquired and imposed dynamically.

Floorplanning algorithms have traditionally underperformed experienced designers, even when relatively simple interconnect metrics are concerned. However, the sheer scale of modern systems on chip makes an all-manual design flow infeasible. In this paper, we propose a new efficient automated approach to the floorplan repair problem, where a set of violated design constraints are satisfied by applying small changes to an existing rough floorplan. Such a floorplan can be produced by a human designer, by a scalable placement algorithm, or result from engineering adjustments to a pre-existing floorplan. In all cases, overlapping modules must be separated, and in some instances, modules may need to be repositioned to satisfy other requirements.The algorithmic framework we propose is built upon an expressive graph-based encoding of constraints. While capable of representing floorplans with or without overlapping modules, it can also support the outline of the core area, fixed module locations, region constraints, proximity and alignment constraints, etc. Instead of applying randomized local search in the hope of satisfying these constraints, we track all implications of imposed constraints and resolve violations by invoking gradual modifications to the floorplan.The primary focus of this paper is on a particularly efficient conflict-directed algorithm for floorplan repair and legalization. It is shown to completely eliminate overlaps from layouts produced by Capo 9.4, Feng Shui 5.1 and APlace 2.01 on IBM-HB benchmarks with hard blocks, typically requiring negligible runtime and increasing interconnect length by only several percent. Furthermore, we are able to generate legal solutions for these instances that surpass previously reported results in wirelength by an average of roughly 7%.

We present PLIANT, a learning system that supports adaptive assistance in an open calendaring system. PLIANT learns user preferences from the feedback that naturally occurs during interactive scheduling. It contributes a novel application of active learning in a domain where the choice of candidate schedules to present to the user must balance usefulness to the learning module with immediate benefit to the user. Our experimental results provide evidence of PLIANT's ability to learn user preferences under various conditions and reveal the tradeoffs made by the different active learning selection strategies.