As the size of circuit designs continues to grow, it has long been a significant challenge to accelerate the circuit compilation flow for modern FPGAs. Many parallel algorithms have been proposed to speed up routing, the most time-consuming stage of FPGA circuit compilation, by leveraging more computing resources. However, the high density of net distribution in modern FPGAs leads to severe data conflicts, making it difficult to achieve high parallelism. In this work, we propose a mixed-grained FPGA parallel routing framework, RND, which implements task decoupling by dividing the FPGA routing graph into disjoint regions and decomposing the signal nets into in-region connections. In the FPGA 2024 routing contest benchmarks, our proposed router achieves an average 5.41× speedup with 32 threads over the serial router RWRoute and is 26.7% faster than Potter-S, the fastest deterministic router for UltraScale FPGAs. Meanwhile, our router does not sacrifice routing quality for acceleration.

With the growth of circuit size and FPGA complexity, routing becomes an increasingly complicated and timeconsuming task for modern FPGAs. To accelerate FPGA routing, many parallel algorithms have been proposed to perform concurrent routing for multiple independent nets that have no overlaps in routing resources. The requirement on net independence can help reduce the synchronization overhead by circumventing the data race in different threads, but it will significantly limit the parallelism due to the large number of overlapping nets in modern circuit designs. Therefore, to strive for large-scale parallelism, it is a promising direction to explore the parallel routing for overlapping nets. In this work, we first propose a parallel overlap-tolerant router, called Potter, including the runtimefirst Potter-R and the stability-first Potter-S. Potter-R employs a partitioning-based recursive net scheduling algorithm to divide nets into balanced groups while minimizing resource overlaps among net groups. These net groups are then routed independently and concurrently. A novel factor updating mechanism is proposed to accelerate solving congestion in the negotiation-based routing algorithm. Furthermore, based on Potter-R, we devise an efficient synchronization strategy in Potter-S to maintain determinism when concurrently routing overlapping nets. An enhanced clustering-based net scheduling method is developed to minimize overlaps among different net groups. In the FPGA24 routing contest benchmarks, our proposed method outperforms the state-of-the-art methods in both running time and wire length. Potter-R not only achieves the largest 12.34× speedup to the sequential router RWRoute but also has the best 4% improvements on wire length. Furthermore, compared with the fastest deterministic parallel router CUFR, Potter-S can

Reinforcement learning (RL)-based macro placement has garnered significant interest in both the fields of artificial intelligence and electronic design automation (EDA), due to its excellent potential for achieving better performance, power and area optimization compared to analytical methods. However, existing techniques are restricted in the ASIC and ignore the other hardware architectures like FPGA. Neglecting the intrinsic characters of FPGA structures, conventional RL-based methods for ASICs may result in a large exploration space and low sample efficiency. In this work, we propose TRPlaceFPGA-MP, a two-stage RL-based macro placement framework for Ultrascale FPGAs. Leveraging the columnar architecture, we first train a tiny RL model to determine the candidate columns for each macro in the first stage. With the pruned searching space, a more sophisticated RL model is then trained in the second stage to determine the ultimate positions of the macros. Experimental results on the MLCAD2023 contest benchmark demonstrate that TRPlaceFPGA-MP still maintains superior placement performance compared with Vivado and DreamplaceFPGA-MP. Furthermore, it improves the convergence rate by 2.28 x and accelerates the exploration process by$1.61 x$compared to the one-stage RL approach.

Macro placement significantly influences the performance of the FPGA placement. However, constraints in modern designs like relative placement constraint (RPC) and regional constraint (RC) are often overlooked in existing routability-driven FPGA placers during macro placement. These constraints introduce challenges in optimizing routability during global placement and macro legalization stages. In this paper, we propose a novel macro placer that specifically addresses these constraints while optimizing routability. Our macro placer integrates macro size-aware pseudo nets, RC guided spreading, and multi-stage look-ahead legalization techniques to enhance routability with specified design constraints. Experimental results show that compared with DreamplaceFPGA-MP and the macro placer in Vivado, our proposed approach achieves 6% and 8% total routing score reduction on the MLCAD2023 contest benchmark. Moreover, the place and route time is reduced by 3.5% on average and up to 43% after our macro placer is integrated into Vivado. These compelling results demonstrate the efficiency gains and superior routability optimization achieved through our approach.

In the face of escalating complexity and size of contemporary FPGAs and circuits, routing emerges as a pivotal and time-intensive phase in FPGA compilation flows. In response to this challenge, we present an open-source parallel routing methodology designed to expedite routing procedures for commercial FPGAs. Our approach introduces a novel recursive partitioning ternary tree to augment the parallelism of multi-net routing. Additionally, we propose a hybrid updating strategy for congestion coefficients within the routing cost function to accelerate congestion resolution in negotiation-based routing algorithms. Evaluation on public benchmarks from the FPGA24 routing contest demonstrates the efficacy of our parallel router. It achieves a 2 × speedup compared to the academic serial router RWRoute. Furthermore, when compared to the industry-standard tool Vivado, our approach not only delivers a 2 × acceleration but also yields a notable 31% enhancement in critical-path wirelength.

Large-scale multi-FPGA prototyping platforms play an indispensable role in the functional verification of complex IC designs. The process of compiling circuit designs typically entails tasks such as partitioning, global placement and routing using a fixed multi-FPGA network. However, different circuit designs often exhibit varying inter-FPGA communication requirements after compilation. Neglecting this distinction, the use of fixed multi-FPGA networks may impede the performance enhancement of circuit verification. In this study, we investigate dynamic networking for multi-FPGA platforms and propose a comprehensive framework, which integrates simultaneous networking and system-level placement and routing. Based on theoretical analysis, we formulate this dynamic networking problem as an Integer Linear Programming (ILP) problem. Additionally, we introduce two innovative techniques, namely two-level ILP optimization and edge grouping, to expedite the ILP-solving process. Compared to the baselines on Titan23 and ICEEC22 benchmarks, our method achieves remarkable 11% and 47% improvements in system frequency respectively.

Routing is a time-consuming stage in FPGA compilation, and various parallel approaches have been proposed to accelerate it by concurrently routing non-overlapping nets. However, the requirement for non-overlapping nets limits the potential for large-scale parallelism, primarily due to two factors: (1) large circuits inherently contain many nets with overlapping bounding boxes, and (2) in modern FPGAs, such as Xilinx UltraScale FPGAs, a net with a large bounding box often has high occupancy but low utilization of the routing resources. To overcome these limitations, we present Potter, a novel parallel overlap-tolerant router designed to maximize parallelism. Our approach employs recursive partitioning to divide nets into balanced partitions with minimized overlap and allows for routing these partitions in parallel. Additionally, we propose an innovative mechanism for updating the congestion factors to enhance PathFinder in handling routing resource overflows. Evaluations on the FPGA 2024 contest benchmarks demonstrate that Potter achieves significant performance improvements, with average speedups of 12× and 8× compared to RWRoute and Vivado, respectively, while also reducing wire lengths by 4% and 45%. Notably, in some congested benchmarks, Potter exhibits a substantial 30× speedup over RWRoute.

Circuit partitioning is a critical step in hardware-assisted functional verification that involves splitting a circuit into multiple partitions and assigning them to specific hardware. However, partitioning a large circuit can require considerable computation resources and time, especially when complex hardware constraints are involved. Moreover, the path delay after partitioning can have a significant impact on verification efficiency, making early path delay prediction crucial for refining the circuit effectively. In this work, we propose a novel circuit partitioning predictor, named CPP, to rapidly and accurately predict the path delay after partitioning. To achieve this, we use circuit coarsening to develop a multi-level path representation and employ a convolutional neural network (CNN) that can capture both local and global path structures for delay prediction. Through extensive experiments on large industrial circuits, we demonstrate the superiority of our prediction framework.

With the size of modern VLSI circuits growing in size to billions of transistors, multi-FPGA systems have been widely applied in circuit emulation and prototyping. To make full advantage of limited FPGA resources and improve the system frequency, designing a flexible multi-FPGA system with a corresponding design compilation flow is an important research problem in both industry and academia. In this work, we propose a practical and scalable partitioning and routing framework, named SPARK, for a multi-FPGA system with an adjustable near-square mesh shape and the minimum number of FPGAs. To resolve the significant constraints on multiple hardware resources for partitioning, SPARK leverages the general hypergraph partitioning tool by combining it with an efficient legalization algorithm to minimize cut size without resource overflow. We also propose novel max_cut-driven maze routing and max_hop-driven refinement algorithms to optimize the max_cut and max_hop in multi-FPGA systems meanwhile and improve the system frequency. Extensive experiments using the largest public circuit benchmarks for FPGA and several small FPGA settings from the industry demonstrate the effectiveness and efficiency of SPARK.

Multiple patterning lithography decomposition (MPLD) and mask optimization enable the ever-shrinking device feature sizes far below the lithography system limit. Conventional MPLD is solved by mathematical programming or graph-based approaches, where a set of predetermined rules is indispensable to identify the conflicts to be resolved. In this article, we explore rule-free layout decomposition following a simple but sweet principle, let the mask optimizer “teach” the layout decomposer how to generate suitable decompositions. Our flow includes a reinforcement-learning-based layout decomposer and a deep-learning-based mask optimizer. Without any handcrafted rules, our framework can perform competitively and even surpass the state-of-the-art rule-based methods with notable$(7\times \sim 63\times)$turn-around-time speedup.

The finite element method (FEM) is a well-known technique for approximately solving partial differential equations and it finds application in various engineering disciplines. The recently introduced wafer-scale engine (WSE) has shown the potential to accelerate FEM by up to 10,000×. However, accelerating FEM to the full potential of a WSE is non-trivial. Thus, in this work, we propose a partitioning algorithm to partition a 3D finite element model into tiles. The tiles can be thought of as a special netlist and are placed onto the 2D array of a WSE by our placement algorithm. Compared to the best-known approach, our partitioning has around 5% higher accuracy, and our placement algorithm can produce around 11% shorter wirelength (L1.5-normalized) on average.

Placement and routing are two crucial steps in the physical design of integrated circuits (ICs). To close the gap between placement and routing, the routing with cell movement problem has attracted great attention recently. In this problem, a certain number of cells can be moved to new positions and the nets can be rerouted to improve the total wire length. In this work, we advance the study on this problem by proposing a two-level layer-aware scheme, named ATLAS. A coarse-level cluster-based cell movement is first performed to optimize via usage and provides a better starting point for the next fine-level single cell movement. To further encourage routing on the upper metal layers, we utilize a set of adjusted layer weights to increase the routing cost on lower layers. Experimental results on the ICCAD 2020 contest benchmarks show that ATLAS achieves much more wire length reduction compared with the state-of-the-art routing with cell movement engine. Furthermore, applied on the ICCAD 2021 contest benchmarks, ATLAS outperforms the first place team of the contest with much better solution quality while being 3× faster.

Placement and routing (P&R) are two important stages in the physical design flow. After circuit components are assigned locations by a placer, routing will take place to make the connections. Defined as two separate problems, placement and routing aim to optimize different objectives. For instance, placement usually focuses on optimizing the half-perimeter wire length (HPWL) and estimated congestion while routing will try to minimize the routed wire length and the number of overflows. The misalignment between the objectives will inevitably lead to a significant degradation in solution quality. Therefore, in this paper, we present Starfish, an efficient P&R co-optimization engine that bridges the gap between placement and routing. To incrementally optimize the routed wire length, Starfish conducts cell movements and reconnects broken nets by A*-based partial rerouting. Experimental results on the ICCAD 2020 contest benchmark suites [1] show that our co-optimizer outperforms all the contestants with better solution quality and much shorter runtime.

As the complexity of circuit designs continues growing, multi-FPGA systems are becoming more and more popular for logic emulation and rapid prototyping. In a multi-FPGA system, different FPGAs are connected by limited physical wires, in other words, one FPGA usually has direct connections with only a few FPGAs. During the circuit partitioning stage, assigning two directly connected nodes to two FPGAs without physical links would significantly increase the delay and degrade the overall performance. However, some well-known partitioners, like hMETIS and PaToH, mainly focus on cut size minimization without considering such topology constraints of FPGAs, which limits their practical usage. In this paper, we propose a multi-level topology-driven partitioning framework, named as TopoPart, to deal with topology constraints in a multi-FPGA system. In particular, we firstly devise a candidate FPGA propagation algorithm in the coarsening phase to guarantee the later stages free of topology violations. In the last refinement phase, cut size is iteratively optimized maintaining both topology and resource constraints. Compared with the proposed baseline, our partitioning algorithm achieves zero topology violation while giving less cut size.

Using reinforcement learning for traffic signal control has attracted increasing interests recently. Various value-based reinforcement learning methods have been proposed to deal with this classical transportation problem and achieved better performances compared with traditional transportation methods. However, current reinforcement learning models rely on tremendous training data and computational resources, which may have bad consequences (e.g., traffic jams or accidents) in the real world. In traffic signal control, some algorithms have been proposed to empower quick learning from scratch, but little attention is paid to learning by transferring and reusing learned experience. In this paper, we propose a novel framework, named as MetaLight, to speed up the learning process in new scenarios by leveraging the knowledge learned from existing scenarios. MetaLight is a value-based meta-reinforcement learning workflow based on the representative gradient-based meta-learning algorithm (MAML), which includes periodically alternate individual-level adaptation and global-level adaptation. Moreover, MetaLight improves the-state-of-the-art reinforcement learning model FRAP in traffic signal control by optimizing its model structure and updating paradigm. The experiments on four real-world datasets show that our proposed MetaLight not only adapts more quickly and stably in new traffic scenarios, but also achieves better performance.

Cooperation among the traffic signals enables vehicles to move through intersections more quickly. Conventional transportation approaches implement cooperation by pre-calculating the offsets between two intersections. Such pre-calculated offsets are not suitable for dynamic traffic environments. To enable cooperation of traffic signals, in this paper, we propose a model, CoLight, which uses graph attentional networks to facilitate communication. Specifically, for a target intersection in a network, CoLight can not only incorporate the temporal and spatial influences of neighboring intersections to the target intersection, but also build up index-free modeling of neighboring intersections. To the best of our knowledge, we are the first to use graph attentional networks in the setting of reinforcement learning for traffic signal control and to conduct experiments on the large-scale road network with hundreds of traffic signals. In experiments, we demonstrate that by learning the communication, the proposed model can achieve superior performance against the state-of-the-art methods.

Increasingly available city data and advanced learning techniques have empowered people to improve the efficiency of our city functions. Among them, improving urban transportation efficiency is one of the most prominent topics. Recent studies have proposed to use reinforcement learning (RL) for traffic signal control. Different from traditional transportation approaches which rely heavily on prior knowledge, RL can learn directly from the feedback. However, without a careful model design, existing RL methods typically take a long time to converge and the learned models may fail to adapt to new scenarios. For example, a model trained well for morning traffic may not work for the afternoon traffic because the traffic flow could be reversed, resulting in very different state representation. In this paper, we propose a novel design called FRAP, which is based on the intuitive principle of phase competition in traffic signal control: when two traffic signals conflict, priority should be given to one with larger traffic movement (i.e., higher demand). Through the phase competition modeling, our model achieves invariance to symmetrical cases such as flipping and rotation in traffic flow. By conducting comprehensive experiments, we demonstrate that our model finds better solutions than existing RL methods in the complicated all-phase selection problem, converges much faster during training, and achieves superior generalizability for different road structures and traffic conditions.