Spatial accelerators are promising to satiate the growing demands for performance and energy efficiency in deep neural networks (DNNs). Due to the speed gap between onchip compute cores and off-chip memory bandwidth, common DNNs suffer from poor operational intensity and are increasingly memory-bound. While operator fusion has shown potential in alleviating this bottleneck, existing approaches suffer from two key limitations. They rely on predefined fusion templates before tensor mapping and impose tile constraints during mapping. As a result, they overlook the potential of fusing more operators and lead to sub-optimal performance. In this paper, we propose a segment fusion dataflow optimization framework called SFD. Central to this framework is the dataflow abstraction that enables template-free operator fusion after mapping and supports tile constraint relaxation through tile scheduling. Based on this abstraction, we first introduce a memory-centric mapper, which defines a design space and incorporates an algorithm to facilitate design space exploration (DSE). Then we propose an analytical network segmenter, which leverages mapping results to analyze tensor lifetimes and on-chip memory usage, fusing operators into variable-length segments. Finally, we introduce a dependency-aware tile scheduler, which develops a priority queue for each segment to ensure correct execution order. Extensive experiments with different DNNs demonstrate SFD achieves$1.4 \times$to$2.2 \times$speedup for spatial accelerators over state-of-the-art fusion frameworks.

Scheduling determines the execution order and time of operations in program. The order is related to operation dependencies, including data and resource dependencies. Data dependencies are intrinsic in programs, while resource dependencies are determined by scheduling methods. Existing scheduling methods lack an accurate and complete operation dependency graph (ODG), leading to poor performance. In this paper, we propose an ODG-based scheduling method for HLS with GNN and RL. We adopt GNN to perceive accurate relations between operations. We use the relations to guide an RL agent in building a complete ODG. We perform feedback-guided iterative scheduling with the graph to converge to a high-quality solution. Experiments show that our method reduces 23.8% and 16.4% latency on average, compared with the latest GNN-based and RL-based methods, respectively.

Tensor algorithms increasingly rely on specialized accelerators to meet growing performance and efficiency demands. Given the rapid evolution of these algorithms and the high cost of designing accelerators, automated solutions for jointly optimizing both architectures and mappings have gained attention. However, the joint design space is non-convex and non-smooth, hindering the finding of optimal or near-optimal designs. Moreover, prior work conducts two-level exploration, resulting in a combinatorial explosion. In this paper, we propose Poros, a one-level architecture-mapping co-exploration framework. Poros directly explores a batch of architecture-mapping configurations and evaluates their performance. It then exploits reinforcement learning to perform gradient-based search in the non-smooth joint design space. By sampling from the policy, Poros keeps exploring new actions to address non-convexity. Experimental results demonstrate that Poros achieves up to 5.32 × and 2.15 × better EDP compared with hand-designed accelerators and state-of-the-art automatic approaches respectively. Through one-level exploration scheme, Poros also converges at least 20% faster than other approaches.

Hybrid quantum-classical algorithms have shown great promise in leveraging the computational potential of quantum systems.However, the efficiency of these algorithms is severely constrained by the limitations of current quantum hardware architectures.These architectures, which typically feature a decoupled design, lack both hardware support for low-latency communication and software support for fine-grained optimization.In this paper, we propose Qtenon, a tightly coupled system for efficient hybrid quantum-classical algorithm acceleration.Qtenon is composed of both hardware part and software part.To enable efficient communication and computation, the hardware part provides a unified memory hierarchy, an efficient quantum controller, as well as a multi-stage processing pipeline.The unified memory hierarchy functions as a communication buffer between host and quantum accelerators, with dedicated data paths and interfaces provided by the quantum controller.The multi-stage pipeline leverages hardware pipelines to fully exploit parallelism.To program hybrid quantum-classical algorithms on the hardware, our software part provides a set of instructions for data communication and computation.The instructions also enable fine-grained synchronization and efficient scheduling for quantum-host interaction.We design Qtenon as a RISC-V extended chip and implement it using Chisel.In evaluation, we achieve up to 14.9× end-to-end speedup compared to state-of-the-art work for hybrid quantum-classical algorithms.

Scheduling determines the execution order and time of operations in a program. The order is related to operation dependencies, including data and resource dependencies. Data dependency is intrinsic in a program, showing operation data flow. Resource dependency is determined by scheduling methods, resolving operation resource contention. Existing scheduling methods focus on data dependency, rather than building and exploiting operation dependency graph (ODG) with extra resource dependency. As ODG contains all dependencies determining operation execution order, it provides global program information, facilitating efficient scheduling. In this work, we propose ODGS, a dependency-aware scheduling method for high-level synthesis with graph neural network (GNN) and reinforcement learning (RL). We adopt GNN to perceive accurate relations between operations. We use the relations to guide an RL agent in building a complete ODG. We perform feedback-guided iterative scheduling with ODG to converge to a high-quality solution. Experiments show that our method reduces 16.4% latency and 26.5% resource usage on average, compared with the latest RL-based method. Moreover, we reduce an average 2.9% latency over the GNN-based method under the same resource usage. The same resource usage is obtained by improving the GNN-based method with manual resource constraint tuning. Without tuning, its basic version consumes an average 237.6% more resources than our method.

Spatial accelerators are domain-specific architectures to elevate performance and energy efficiency for deep neural networks (DNNs). They also bring a large number of schedule parameters to determine computation and data movement patterns of DNNs. Previous works formulate the schedule problem as design space exploration or integer linear programming. However, these advanced techniques face the challenge of efficiency or scalability. In this article, we propose Ceiba, which is a deep reinforcement learning-based DNN scheduler for spatial accelerators. Ceiba observes the running DNN computation as well as the spatial architecture to make schedule decisions. Then, Ceiba receives a reward to learn and produce the best-fit policy. To provide efficient and scalable scheduling, Ceiba constructs a DNN-architecture-specific action space. It is defined by upper and lower bounds to exclude invalid and sub-optimal schedule candidates. Extensive experiments demonstrate that Ceiba generally provides better performance for spatial accelerators under a fixed number of searching steps or a fixed amount of time. Specifically, Ceiba achieves an average 2.2× speedup for the Simba accelerator, compared with the state-of-the-art scheduler. When scaling the batch size and the hardware architecture up by 64×, the performance gains of Ceiba are 1.8× and 1.2× on average, respectively. Moreover, Ceiba exhibits better scalability for the Eyeriss accelerator.

Program behavior comprises operation dependency and resource requirement. They impact the performance of scheduling in high-level synthesis (HLS). Most existing scheduling methods focus on one aspect, resulting in poor performance. In this article, we propose PBS, a program behavior-aware scheduling method for HLS. We leverage a hybrid state encoding scheme to facilitate the comprehensive learning of program behaviors. Moreover, we propose bi-directional GNN and multiresolution aggregation schemes for learning complex operation dependency behavior. These schemes are integrated in an RL framework to iteratively improve scheduling solutions toward low latency and resource usage. Experiments show that PBS provides an average 32.7%, 26.3%, and 25.9% latency reductions, compared with the SDC, GNN-based, and RL-based methods, respectively.

Multi-head attention demonstrates enormous potential but incurs high costs (e.g., memory access) when deploying transformer models on spatial accelerators. Operator fusion is prevalent in conventional deep learning mappers to reduce off-chip memory access. However, designing operator-fusion mapping for multi-head attention is challenging. There exist strict data dependency between operators and hardware resource constraints of accelerators. In this paper, we propose TileMap, an operator-fusion mapping framework for multi-head attention on spatial accelerators. Central to this framework is tile-based analysis that can automatically satisfy both data dependency and resource constraints. Based on this analysis, we construct a mapping design space, which significantly prunes invalid candidates. We then propose an RL-based searching algorithm to explore the mapping space. The RL agent regards the mapping space as action space and further optimizes it to preserve all constraints. Experiments show TileMap achieves$1.8\times$to$3.1\times$speedup on different spatial accelerators, relative to state-of-the-art mapping approaches.

Spatial accelerator is a specialized hardware to provide noticeable performance speedup for tensor computations. It also brings a challenge to map tensor computations on spatial accelerators. Auto-tuning compiler is one of the most promising directions for tensor mapping. However, existing auto-tuning compilers suffer from either numerous invalid and inefficient programs or inaccurate evaluation of incomplete programs, leading to sub-optimal performance.In this paper, we propose Soter, a novel auto-tuning tensor compilation framework for spatial accelerators. The key is to perform exploration in a both valid and efficient program design space and perform optimization according to accurate evaluation of complete programs. First, we design an analytical model to generate a high-quality program design space, which excludes invalid and inefficient programs. Second, we design an automatic program tuner to efficiently explore the program space and avoid evaluating incomplete programs. Finally, we coordinate the model and the tuner to further improve the quality of program space. The program space is identified by the model and is updated during the exploration of tuner. On average, Soter achieves 2.1× to 3.5× speedup over the state-of-the-art tensor compilers. Moreover, Soter shows better scalability for larger-scale tensor computations and spatial architectures.

Scheduling and placement for deep learning (DL) jobs on GPU clusters is essential to improve quality of service and reduce operational cost. Scheduling involves determining the execution order of waiting jobs, and placement entails selecting appropriate computing nodes to execute the jobs. In this paper, we propose a RL-based scheduling and placement method for DL jobs on large-scale GPU clusters. The key idea is to employ two RL agents with adaptable policy networks. These networks are capable of reducing computational complexity and supporting a flexible action space. First, we regard the scheduling and placement as unified sequence selection processes, i.e., selecting an element from the candidate sequence. And they are tackled by two similar RL agents. Second, we develop an encoder-only Transformer-based policy network. This network can manage variable-length sequences and offer a flexible action space. Third, we propose a novel sequence filtering approach. This approach can exclude those job sequences offering limited learning value, so as to enhance the agents' training efficiency. We evaluate our method's performance using a real production-level job trace, comparing it with several heuristic and RL methods. Our method achieves an average improvement of up to 1.30 x in average job completion time and up to 1.11 x in energy consumption.

The mapping of tensor computation is a complex and important process for spatial accelerators. Today's mapping works depend on hand-tuned kernel libraries or search-based heuristics from human experts. The former is time-intensive while the latter easily leads to sub-optimal performance. In this paper, we propose TensorMap, a deep reinforcement learning (RL)-based mapping framework for tensor computations on spatial accelerators. We propose a sequential generation mode for mapping optimization and construct a coarse-grained action space to reduce the complexity of the mapping search space. An efficient policy network is devised to optimize mapping primitives in the RL-based search. We then propose a stop signal that is sampled fromBernoullidistribution to facilitate multi-level loop unrolling for spatial accelerators. Finally, a genetic algorithm is employed to further refine the optimized mappings. In the experiments, we demonstrate TensorMap's ability for different spatial accelerators with various tensor computations. On TPU, TensorMap provides 2.6$\times$, 2.7$\times$, and 2.4$\times$better energy-delay product (EDP) on average compared with FlexTensor, Ansor, and AMOS respectively. On Eyeriss, TensorMap provides 2.1$\times$, 1.8$\times$, and 1.7$\times$better EDP on average compared with FlexTensor, Ansor, and AMOS respectively.

Large language model (LLM) is a promising trend to sustain accuracy growth with billions of parameters for various application domains. Deep learning (DL) accelerators that are typically designed in spatial architecture are potential platforms to handle the substantial computational demands of LLMs. Exploiting DL accelerators for LLMs require high-performance kernels, which are manually optimized or automatically generated. While prior automatic works reduce development costs, they fail to find optimal or near-optimal kernels. This is because the kernel design space is large containing many invalid kernels, and non-convex containing many local minima. In this paper, we propose an automatic kernel generation framework for large language models on deep learning accelerators. The key idea is the reinforcement learning (RL) formulation to generate a kernel with multi-step decision-making. We first develop a high-quality action space to satisfy architectural constraints of accelerator. Then, we provide a practical RL implementation by devising a policy network with Transformer and variance reduction techniques for gradients. Experimental results show our framework achieves average 3.5× speedup on TensorCore compared with exploration-based Ansor; 2.6× speedup on Simba compared with solver-based CoSA. Also, our framework achieves better energy efficiency compared to the state-of-the-art works.

This paper proposes a locality-aware Oblivious RAM (ORAM) primitive, named Green ORAM, which exploits spatial locality of data in the physical memory for reducing ORAM overheads. The Green ORAM is novel consisting of three policies. The first is row-guided label allocation used for mapping spatial locality onto ORAM tree to reduce the number of memory commands. The second is segment-based path replacement able to improve the data locality within the path in the ORAM tree in order to remove the redundant memory accesses. The third is multi-path write-back able to improve the data locality between different paths in order to obtain theoretical best stash hit rate. Notably, the Green ORAM still maintains the security as we analyzed. Experimental results show that Green ORAM achieves a 28.72% access latency reduction, and a 19.06% memory energy consumption reduction on average, compared with the state-of-the-art String ORAM.

Routing is one of the most time-consuming stages in the FPGA design flow. Parallelization can accelerate the routing process but suffering from load imbalance, further resulting in a low scalability. In this paper, we propose a load balance-centric parallel router in a distributed computing environment. First, we explore regular and irregular region partitioning so that routing tasks are assigned to different cores for static load balance before parallel routing. Second, we explore message propagation and task migration between underloaded and overloaded cores so that load balance can be dynamically maintained at parallel routing runtime. Finally, we demonstrate the effectiveness of the parallel router using large-scale Titan designs. Experimental results show that our parallel router achieves about 17 × speedup on average using 32 cores, compared with VTR 8 router.

As a large number of emerging graph applications spread across different domains, the need for processing massive concurrent graph jobs (CGJs) is increasing. However, existing graph processing systems designed for a single job cannot efficiently tackle multiple CGJs, where they suffer from interfering memory access patterns and inefficient property management. In this paper, we introduce Krill, a compiler and runtime system for processing concurrent graph jobs. We propose an SAP model, which decouples graph structure, algorithm, and property. In the compiler, we propose leveraging the property buffer to easily write and manage property data. In the runtime system, we propose a novel technique named graph kernel fusion to reduce memory accesses, which fuses all the jobs and processes them as a whole. Experimental results show our system significantly reduces the number of memory accesses for CGJs by more than 6x compared with the baseline, and achieves up to 6.76x speedup with 3.84x shorter response latency than GraphM, the state-of-the-art concurrent graph processing system.

Routing is a very complex process in the field programmable gate array (FPGA) CAD flow. The increase of both FPGA size and design complexity leads to a long routing time hindering the productivity. In this article, we propose a more effective parallel router that combines static and dynamic load balance in parallel routing for FPGAs. First, we explore hierarchical region partitioning to assign routing tasks to different cores for static load balance. Then, we coordinate message propagation and task migration at runtime so that load balance between cores can be dynamically maintained in parallel routing. Finally, we combine static and dynamic load balance in the parallel routing for a higher degree of parallelism. Our parallel router performs on the multicore distributed-memory systems and the communication between cores is through message passing interface messages. We demonstrate the effectiveness of our parallel router using large-scale Titan designs. On average, our parallel router can scale up to 32 cores to achieve about 17× speedup with slight loss of quality, compared with the latest VTR 8 router.

It is promising to deploy CNN inference on local end-user devices for high-accuracy and time-sensitive applications. Model parallelism has the potential to provide high throughput and low latency in distributed CNN inference. However, it is non-trivial to use model parallelism as the original CNN model is inherently tightly-coupled structure. In this article, we propose DeCNN, a more effective inference approach that uses decoupled CNN structure to optimize model parallelism for distributed inference on end-user devices. DeCNN is novel consisting of three schemes. Scheme-1 is structure-level optimization. It exploits group convolution and channel shuffle to decouple the original CNN structure for model parallelism. Scheme-2 is partition-level optimization. It is based on channel group to partition the convolutional layers, and then leverages input-based method to partition the fully connected layers, further exposing high degree of parallelism. Scheme-3 is communication-level optimization. It uses inter-sample parallelism to hide communications for better performance and robustness, especially in the weak network connections. We use ImageNet classification task to evaluate the effectiveness of DeCNN on a distributed multi-ARM platform. Notably, when using the number of devices from 1 to 4, DeCNN can accelerate the inference of large-scale ResNet-50 by 3.21×, and reduce 65.3 percent memory footprint, with 1.29 percent accuracy improvement.

Routing is a very time-consuming stage in the FPGA design flow, significantly hindering the productivity. This article proposes CPRS, a coarse-grained parallel routing scheme in a distributed computing environment. First, we partition entire routing region to guide the assignment of nets for parallel processing. The partitioning is a recursive fashion, and at each recursive partitioning, the region is partitioned into two subregions forming three subsets of nets. The first subset consists of potentially dependent nets and they are distributed in different subregions. The remaining two subsets consist of potentially independent nets and they are distributed in their own subregions. Second, we route the nets of first subset in serial and process the remaining two subsets in parallel. The parallel processing is a coarse-grained fashion, which is implemented by MPI parallel programming model. Finally, we explore the optimization of both partitioning and parallel processing to further improve the overall speedup of parallel routing. In addition, we adopt MPI message to synchronize the intermediate results between different cores in parallel routing for a feasible solution. Experiments use a set of commonly used benchmarks to demonstrate the effectiveness of CPRS. Notably, CPRS achieves about 18× speedup on average using 32 processor cores with minor loss of quality, compared with the VTR 7.0 serial router. There is about 1.6× improvement over the state-of-the-art parallel router.

In this paper, we present a serial-equivalent parallel router for FPGAs on modern multi-core processors. We are based on the inherent net order of serial router to schedule all the nets into a series of stages, where the non-conflicting nets are scheduled in same stage and the conflicting nets are scheduled in different stages. We explore the parallel routing of non-conflicting nets on multi-core processors for a significant speedup. We perform the data synchronization of conflicting stages using MPI-based message queue for a feasible routing solution. Note that load balance is always used to guide the multi-core parallel routing. Experimental results show that our parallel router provides about 19.13× speedup on average using 32 processor cores comparing to the serial router. Notably, our parallel router generates exactly the same wirelength as the serial router satisfying serial equivalency.

CNN is a popular deep learning structure able to provide intelligent processing in IoT applications. Instead of deploying the resource-hungry CNN inference workloads on the cloud, it would be promising to utilize local IoT devices for the in-situ processing. Since a single IoT device has only limited resources available, distributing over multiple local devices becomes a potential solution, especially for high-accuracy and time-sensitive tasks. However, it is non-trivial to distribute the inference of existing CNN models efficiently as they are inherently tightly-coupled structure. In this paper, we propose a distributed in-situ CNN inference system with the loosely-coupled CNN structure (LCS), the synchronization-oriented partitioning (SOP), and the decentralized asynchronous communication (DAC) for IoT applications. LCS is based on two novel design ideas, the homogeneous group and the intermittent shuffle. Experiments on ImageNet classification illustrate that LCS has the leading accuracy compared with other structures, under a given computation budget. SOP and DAC target on converting the loosely-coupled feature of LCS into practical performance improvement. SOP tries to partition LCS with fewer synchronization points and DAC reduces the communication overhead by overlapping communications. When the number of IoT devices increases from 1 to 4, our system accelerates by up to 3.85 ×, and reduces the memory footprint in each device by 70%, outperforming other approaches.

High-level synthesis (HLS) is important for compiling an application design onto field-programmable gate array (FPGA) but still faces challenges of balancing scalability and quality of results in the scheduling process. In this article, we propose an entropy-directed scheduling (EDS) algorithm that efficiently generates high-quality schedules for FPGA HLS. This article is novel in three ways. First, we make the first attempt to adopt entropy in the scheduling of HLS, which is an intuitive and robust measurement with lots of good analytic properties. Second, we creatively leverage the maximum entropy principle to describe the scheduling process, which is proved equivalent to the optimal solution in some particular cases. Third, we make EDS automatically analyze the input graph structure and leverage a three-stage scheduling process to obtain high-quality results. As a result, EDS has the lowest time complexity among existing scheduling algorithms and is flexible to solve both latency- and resource-constrained problems while satisfying other constraints. The experimental results show that for latency-constrained scheduling problem, EDS reduces up to 68% resource usage and is 294× faster than the force-directed scheduling algorithm. For resource-constrained scheduling problem, EDS obtains near-optimal solutions with an average speedup of 16 410× compared with ILP. To our best knowledge, this is the first EDS algorithm for FPGA HLS.

Serial equivalency enables easier regression testing and customer support in production-grade parallel CAD tools. While existing parallel routing techniques have become sufficiently advanced to provide good speedup, support for serial equivalency still has been very limited or ignored because it was considered costly. In this paper, we present a serial-equivalent parallel router that not only provides significant speedup but also produces the same result as the serial router. This parallel router primarily leverages a dependency-aware scheduling algorithm to facilitate the serial equivalency. Moreover, regardless of how many processor cores are used, this scheduling algorithm also enables parallel router to have the same result as the serial router. In scheduling algorithm, according to the original net order of serial router, all of the nets are scheduled to a series of different stages. Specifically, the independent nets are scheduled to the same stage and they can be routed in parallel while the dependent nets are scheduled in different stages and they are processed in serial. Note that the parallel routing of independent nets can be explored in static and dynamic fashions, and the data synchronization between dependent stages is implemented in MPI-based message queue. Experimental evaluations using ten large designs from the academic VTR benchmark suite show that our parallel router can scale to 32 processor cores at least to provide an average 19.13× speedup compared to the state-of-the-art academic VPR router. And most importantly, our parallel router can maintain the serial equivalency which achieves the same results as the serial router. To the best of our knowledge, it is the first parallel router that provides significant speedup with a serial equivalency guarantee.

With the advanced communication sensors are deployed into the modern connected vehicles (CVs), large amounts of traffic information can be collected in real-time, which gives the chance to explore the various techniques to control the routing of CVs in a ground traffic network. However, the control of CVs often suffers from energy inefficiency due to the constant changes of network capacity and traffic demand. In this paper, we propose a cost-based iterative framework, named EEPC, to explore the energy-efficient parallel control of connected vehicles. EEPC enables the control of CVs to iteratively generate a feasible solution, where the control of each vehicle is guided in an energy-efficient way routing on its own trajectory. EEPC eliminates the conflicts between CVs with a limited number of iterations and in each iteration, EEPC enables each vehicle to coordinate with other vehicles for a same road resource of the traffic network, further determining which vehicle needs the resource most. Note that at each iteration, the imposed cost is updated to guide the coordination between CVs while the energy is always used to guide the control of CVs in EEPC. In addition, we also explore the parallel control of CVs to improve the real-time performance of EEPC. We provide two parallel approaches, one is fine grain and the other is coarse grain. The fine grain performs the parallel control of single-vehicle routing while the coarse grain performs the parallel control of multi-vehicle routing. Note that fine grain adopts multi-threading techniques and coarse grain adopts MPI techniques. The simulation results show that the proposed EEPC can generate a feasible control solution. Notably, we also demonstrate that the generated solution is effective in eliminating the resource conflicts between CVs and in suggesting an energy-efficient route to each vehicle. To the best of our knowledge, this is the first work to explore energy-efficient parallel control of CVs.

FPGAs are very attractive to accelerate the deep neural networks (DNNs). While single FPGA can provide good performance for small-scale DNNs, support for large-scale DNNs is limited due to higher resource demand. In this paper, we propose an efficient mapping approach for accelerating large-scale DNNs on asymmetric multi-FPGA architectures. In this approach, the neural network mapping can be formulated as a resource allocation problem. We design a dynamic programming-based partitioning to solve this problem optimally. Experimental results using the large-scale ResNet-152 demonstrate that our approach deploys sixteen FPGAs to provide an advantage of 16.4x GOPS over the state-of-the-art work.

Routing is a time-consuming step in the FPGA compilation flow. The parallelization of routing has the potential to reduce the time but imposes the dependent problem as the inherent order of nets. In this paper, we present Raparo, a resource-level angle-based parallel router. Raparo exploits angle-based region partitioning to drive the assignment of the nets for efficient parallel routing on the multi-core processor systems. Raparo parallelizes the routing at resource level rather than region level for the similar convergence as the serial router. Results show that Raparo can scale to 32 processor cores to provide about 16x speedup on average with acceptable impacts on the quality of results, comparing to the serial router.

As the most important stage in high-level synthesis (HLS), scheduling mostly relies on heuristic algorithms due to their speed, flexibility, and scalability. However, designing heuristics easily involves human bias, which makes the scheduling unpredictable in some specific cases. In this paper, we propose a deep-reinforcement-learning (Deep-RL) based scheduler for HLS. It maximumly reduces the human involvement and learns to schedule by itself. Firstly, we introduce a novel state and action representation for constrained scheduling problems, which is the foundation of the learning task. Secondly, we use a training pipeline to train the policy network. Supervised learning is used to initialize the weight of the network, and reinforcement learning is used to improve the performance, which makes the Deep-RL based scheduler practical for HLS. Finally, we compare our scheduler with the ASAP schedule and the optimal ILP schedule. Experimental results show our scheduler can reduce up to 74% resource usage compared with the original ASAP schedule, and the gap between the optimal solution is small. Notably, this is the first work leveraging reinforcement learning in HLS and has great potential to be integrated into different HLS systems.

In this paper, we propose Parrot, a more effective parallel routing approach that exploits angle-based space recursion partitioning for parallel FPGA routing. Parrot partitions entire routing region into two subregions such that all of the nets are assigned to three sets, where the first set consists of the nets that their terminal pins are distributed in two subregions and the other two sets consists of the nets that their terminal pins are located in their own respective subregions. Note that load balance is always used to guide the partitioning for a greater degree of parallelism. Moreover, all of the sets can be recursively partitioned in the same way to implement the scalable parallel routing and in each recursion, the first set is routed in serial before the other two sets are routed in parallel to generate the deterministic results. In addition, the synchronization overheads can be further reduced to improve the parallelism. Experimental results shows that Parrot can scale to 32 processor cores to provide about 16x speedup on average with acceptable impact on the quality of results. This is about 3x improvement over the state-of-the-art parallel router in terms of maximum average speedup.

As the most critical stage in FPGA HLS, scheduling depends heavily on heuristics due to their speed, flexibility, and scalability. However, designing heuristics easily involves human bias, which makes scheduling unpredictable in some specific cases. To solve the problem, we propose an efficient deep reinforcement learning (Deep-RL) based scheduler for FPGA HLS. It has the potential to reduce the human involvement maximumly and learn to schedule by itself. The proposed scheduler consists of three steps. First, we design a novel state and action representation for constrained scheduling problems, which is the foundation of the learning task. Then, we leverage a training pipeline to train the policy network. Specifically, supervised learning is used to initialize the weights of the network and reinforcement learning is used to improve the performance, both of which make the Deep-RL based scheduler practical for HLS. At last, we compare our scheduler with the ASAP schedule and the optimal ILP schedule. Experimental results show that the proposed scheduler can reduce up to 74% resource usage compared with the original ASAP schedule, and the gap between the optimal solution is very small. Notably, this is the first work leveraging reinforcement learning in HLS and has great potential to be integrated into different HLS systems.

Field Programmable Gate Arrays (FPGAs) are reconfigurable architectures able to provide a good balance between energy efficiency and flexibility with respect to CPUs and ASICs. The main drawback in using FPGAs, however, is their timing-consuming routing process, significantly hindering the designer productivity. An emerging solution to this problem is to accelerate the routing by parallelization. Existing attempts of parallelizing the FPGA routing either do not fully exploit the parallelism or suffer from an excessive quality loss. Massive parallelism using GPUs has the potential to solve this issue but faces non-trivial challenges. To cope with these challenges, this paper explores GPU-accelerated routing approach for FPGAs. We leverage the idea of problem size reduction by limiting the single-net routing in a small subgraph rather than in an entire graph, further enabling the GPU-friendly shortest path algorithm to be used in FPGA routing. We maintain the convergence after problem size reduction by using the dynamic expansion of the routing resource subgraph, where the routing region of subgraph will be progressively expanded to find a feasible solution to each net. In addition, we are based on a GPU platform to explore the fine-grained single-net parallel routing in three ways and propose a hybrid approach to combine the static and dynamic parallelization for better speedup in FPGA routing. To explore the coarse-grained multi-net parallelization, We propose a dynamic programming-based partitioning algorithm to parallelize the routing of multiple nets while generating the equivalent routing results as the original single-net routing. Experimental results show that our proposed approach can provide an average of about 21.53× speedup on a single GPU with a tolerable loss in the routing quality and maintain a scalable speedup on large-scale routing resource graphs. To our knowledge, this is the first work to demonstrate the effectiveness of GPU-accelerated routing for FPGAs.

FPGA is reconfigurable architecture able to implement a good trade-off in terms of energy, performance, and flexibility. However, the main drawback in using FPGAs is their very long routing time. Multi-core processors are now ubiquitous, making parallelism an increasingly attractive direction to accelerate the routing time. In this paper, we propose a task-level distributed parallel router that exploits conflict-aware box expansion and equal-sized grid partitioning for parallel FPGA routing. In box expansion, we adopt net bounding box to limit the search space of routing and based on current congestion state among nets, we design conflict-aware box expansion to optimize the serial routing time and provide more non-conflicting nets to obtain significant parallelism. In grid partitioning, we employ equal-sized grid to partition the overall routing region, where the nets in same grid are routed in serial and the grids are processed in parallel. Specifically, the nets distributed in multiple grids can be used to balance the workloads among processor cores. Experiments show that the parallel implementation scales to an average speedup of about 21 × using 32 processor cores compared to state-of-the-art VPR router.

Serial equivalency can provide easier regression testing and customer support in production-grade CAD software. While existing parallel routing techniques have become sufficiently advanced to accelerate the execution time, support for serial equivalency has been very limited or ignored due to it was considered costly. In this paper, we propose serial-equivalent parallel routing for FPGAs. We use an optimal dependency-aware scheduling to facilitate serial equivalency of parallel routing algorithm. This capability enables the same answer as the serial version of the parallel algorithm, regardless of how many processing cores are used. We also validate this property across different hardware platforms. Further experimental results show that we achieve a 14.27x speedup on the MPI-based distributed parallel computer and a 19.65x speedup on the GPU-based massively parallel machine. To our knowledge, it is the first parallel routing with a serial equivalency guarantee.

Placement is probably the most critical process in the FPGA design flow. The demand for high performance continues to increase, but existing placers are still faced with numerous challenges including very long runtime, poor scalability, and restricted space exploration. In this paper we propose a novel timing-driven placement algorithm called BoxPlacer, which is supported by the force directed concept. BoxPlacer firstly uses a simple policy to create the initial box for placement. Then a force-directed iterative scheme is used to reduce the box size and determine the global placement. At last, the same concept is employed to eliminate the overlaps between reduced boxes to ensure the legalization in detailed placement. Notice that timing is always used to drive the placement in BoxPlacer. We demonstrate the effectiveness of our BoxPlacer by comparing the experimental results with that produced by the academic simulated annealing-based placer. Notably, our BoxPlacer achieves on average about 8x runtime advantage with 9% smaller critical path delay and 6% shorter wirelength.

FPGAs are very attractive to accelerate the deep neural networks (DNNs). While single-FPGA can provide good performance for small-scale DNNs, support for large-scale DNNs is very limited due to they require higher resource demand. In this paper, we propose an efficient mapping approach for accelerating large-scale DNNs on an asymmetric multi-FPGA architecture. Relative to the state-of-the-art single-FPGA resource reuse for large-scale DNNs, we consider multi-FPGA fashion to strive for higher performance. In this fashion, the neural network mapping problem can be formulated as a resource allocation problem, and a dynamic programming-based partitioning is designed to solve this problem optimally. Notice that the network topology and communication bandwidth of multiple FPGAs are always used to guide the partitioning to boost the performance while satisfying the constraints of resource-performance trade-off in a single FPGA. Experimental results using the large-scale ResNet-152 demonstrate that our approach deploys sixteen FPGAs to provide an advantage of 16.4x GOPS over the state-of-the-art work.

Packing is one of the most critical stages in the FPGA physical syntheses flow. In this paper, we propose DP-Pack, a distributed parallel packing approach. DP-Pack consists of two primary steps. First, all of the minimal circuit units are assigned into several subsets where the conflicting units are located in the same subset and the non-conflicting units are distributed in different subsets. Then, the non-conflicting subsets are partitioned by round robin such that the number of subsets in each processor core is equal approximately, leading to good load balance in parallel packing. Second, the parallelization between processor cores is implemented by the MPI-based message queue in a distributed platform. Note that DP-Pack has been integrated into the VTR 7.0 tool. Experimental results show that our DP-Pack scales to 8 processor cores to provide about 1.4~3.2× runtime advantages with acceptable quality degradation, comparing to the academic state-of-the-art AAPack.

FPGAs are reconfigurable architectures that can offer large performance and energy improvements over general purpose processors. However, compiling an application design onto the underlying FPGA device takes commonly too much time to allow efficient design turnaround times, significantly hindering designer productivity. Routing is always a very timing-consuming and critical process in FPGA compilation flow. To reduce FPGA routing time, parallel techniques have become more popular in recent years. In this paper, we propose a fine-grained GPU-based parallel routing approach that enables high concurrent single-net parallel routing for large-scale FPGAs. The proposed approach is novel in three ways. The first is Scheme-1. We route a single net only on its own bounding box rather than entire routing resource graph and then selectively expand its bounding box to make sure that single-net routing has a feasible solution. The second is Scheme-2. We impose a GPU thread to each node and perform path searching in dynamic programming algorithm on all the nodes simultaneously for single-net parallel routing on a single GPU. Note that these nodes are distributed in the bounding box of single net. The third is optimized Scheme-2. We attempt to partition single-net routing box into several sub-boxes, each of which is processed in a shared memory of GPU to enable high scalability and parallelism. Our evaluation with ten large designs from the academic VTR benchmark suite shows that our approach of combining the approximation of VPR 7.0 router (Scheme-1) and its parallelization (optimized Scheme-2) provides a 1.57x speedup improvement compared to the best parallelization-only approach of the original VPR 7.0 router, though at a small quality deterioration.

Routing is probably the most time-consuming stage in the FPGA compilation flow. While parallelization has the potential to reduce the routing time, load imbalance still arises in parallel routing process, resulting in the degradations of speedup and quality of results. Furthermore, when scaling the number of processing cores, load imbalance will become more severe in parallel routing. In this paper, we explore load balance-aware parallel routing to obtain significant speedup. To study load balance problem, we implement a basic MPI-based parallel routing framework on multi-core distributed-memory platform. This framework provides two dynamic partitioning algorithms and both of them can automatically maintain the load balance of parallel routing at runtime. The first is the heuristic algorithm and it is able to assign more nets to fast MPI processes by removing an equal number of nets from slow MPI processes. The second algorithm selects the re-partitioning of the nets for all the MPI processes at each iteration, further leading to a good load balance during parallel routing. The key idea of these two algorithms is to analyze the behaviours of previous iteration to guide the parallelization of next iteration. Results show that the effectiveness and efficiency of the two algorithms in multi-core distributed-memory parallel routing framework. Notably, our parallel router can achieve about 6× speedup on average using 8 MPI processes, comparing to the serial router. This is a 1.2× improvement over a state-of-the-art multi-core parallel router.

FPGAs play a crucial role in the space of customizable accelerators over the next few years. A chief limiting factor is that FPGA CAD tools are cumbersome and time-consuming to most application developers. Routing is the most complex step in FPGA design flow and NP-complete problem. The PathFinder routing algorithm is in dominant use in FPGA CAD research. However, PathFinder is sequential in nature and lengthy in runtime. Parallelization has the potential to solve the issue but faces non-trivial challenges. In this work we introduce Megrez that uses strictly-ordered partitioning to explore the parallelism on GPU. Experimental results show that Megrez achieves an average of 15.13× speedup on GPU with negligible influence on the routing quality.

Routing is a time-consuming process in the FPGA design flow. Parallelization is a promising direction to accelerate the routing. While synchronous parallelization can converge a feasible solution, the ideal speedup is rarely achieved due to excessive communication overheads. Asynchronous parallelization can provide an almost linear speedup, but it is difficult to converge in the limited number of iterations due to net dependency. In this paper we propose SAPRoute, which coordinates synchronous and asynchronous parallelism on distributed multiprocessing environment to accelerate the routing for FPGAs. The objective is to boost the more speedup of parallel routing algorithm under the requirement of convergence. To the best of our knowledge, this is the first work to study the impact of synchronization and asynchronization during parallelization. Experimental results show that our approach have negligible explicit synchronization overhead and achieves significant speedup improvement over a set of commonly used benchmarks. Notably, SAPRoute produces the speedup of 24.27× on average compared to the default serial solution.

Quantitative effects of Moore's Law have driven qualitative changes in FPGA architecture, applications, and tools. As a consequence, the existing EDA tools takes several hours or even days to implement the applications onto FPGAs. Typically, routing is a very time-consuming process in the EDA design flow. While several attempts have accelerated this process through parallelization, they still do not provide a strong parallel scheme for FPGA routing. In this paper we introduce a dependency-aware parallel approach, named Bamboo, to accelerate the routing time for FPGAs. With the dependency detection, Bamboo partitions the nets into multiple subsets, where the nets in the same subsets are independent, and the dependency only exists among different subsets. Specifically, the independent nets in the same subset are routed in parallel, and the subsets are processed in serial according to the original routing ordering. The partitioning problem is solved optimally using dynamic programming, and the parallelization is implemented by speculative parallelism on a single GPU. Experimental results show that our approach achieves an average of 15.13x speedup with negligible influence on the routing quality. Most importantly, it effectively maintains deterministic results and always produces the same results as the serial version.

Traditional transportation systems in metropolitan areas always suffer from energy inefficiencies, evidenced by its uncoordinated behaviors such as system capacity and traffic demand change. With the advanced networked sensors are prevalent deployed into the autonomous vehicles, the information of system status and traffic demand can be collected in real-time. These information provides the potential to perform different types of coordination and control for autonomous vehicles in large-scale intelligent transportation systems. In this paper, we design a coordination-based energy-aware control method for large-scale connected vehicles, named Tiguan. Tiguan enables an iterative scheme to compute a practicable solution, which all vehicles are controlled on different trajectory paths of ground traffic network while achieving the close to the optimal performance. Safety is guaranteed by enabling vehicle to autonomously coordinate with other vehicles for a road traffic resource, and thus determine which vehicle needs the resource most. Experimental results show that Tiguan can effectively generate a feasible control solution with collision avoidance, and minimizing the energy consumption.

FPGA routing is a time-consuming step in the EDA design flow. In this paper we present a coarse-grained recursive partitioning approach to exploit parallelism. The basic idea is to partition the nets into three subsets, where the first subset and the other two subsets consist of potentially conflicting nets and potentially conflicting-free nets, respectively. The two potentially conflicting-free subsets are routed in parallel after the first subset is routed. And all subsets are recursively partitioned in the same way. Furthermore, we point out that the estimated runtime using recursive bisection is close to the optimal estimated runtime using the optimal recursive partitioning, which we can find in polynomial time. The parallel router is implemented using the Message Passing Interface (MPI). Experimental results show that our parallel router ParRoute+ achieves a 7.06× speedup compared to the VPR 7.0 router. This is a 3.36× improvement over a recent coarse-grained parallel router.