Routing of nets is one of the most time-consuming steps in the FPGA design flow. Existing works have described ways of accelerating the process through parallelization. However, only some of them are deterministic, and determinism is often achieved at the cost of speedup. In this paper, we propose ParaDRo, a parallel FPGA router based on spatial partitioning that achieves deterministic results while maintaining reasonable speedup. Existing spatial partitioning based routers do not scale well because the number of nets that can fully utilize all processors reduces as the number of processors increases. In addition, they route nets that are within a spatial partition sequentially. ParaDRo mitigates this problem by scheduling nets within a spatial partition to be routed in parallel if they do not have overlapping bounding boxes. Further parallelism is extracted by decomposing multi-sink nets into single-sink nets to minimize the amount of bounding box overlaps and increase the number of nets that can be routed in parallel. These improvements enable ParaDRo to achieve an average speedup of 5.4X with 8 threads with minimal impact on the quality of results.

The increase in speed and capacity of FPGAs is faster than the development of effective design tools to fully utilize it, and routing of nets remains as one of the most time-consuming stages of the FPGA design flow. While existing works have proposed methods of accelerating routing through parallelization, they are limited by the memory architecture of the system that they target. In this paper, we propose a distributed memory parallel FPGA router called ParaDiMe to address the limitations of existing works. ParaDiMe speculatively routes net in parallel and dynamically detects the need to reduce the number of active processes in order to achieve convergence. In addition, the synchronization overhead in ParaDiMe is significantly reduced through a careful design of the messaging protocol where paths to sinks are encoded in a space-efficient manner. Moreover, the frequency of synchronization is tuned to ensure convergence while minimizing the communication overhead. Compared to VTR, ParaDiMe achieves an average speedup of 19.8X with 32 processes while producing similar quality of results.

Routing of nets is one of the most time-consuming steps in the FPGA design flow. While existing works have described ways of accelerating the process through parallelization, they are not scalable. In this paper, we propose ParaFRo, a two-phase hybrid parallel FPGA router using fine-grained synchronization and partitioning. The first phase of the router aims to exploit the maximum parallelism available by routing nets while minimizing load imbalance. Instead of resolving contention with expensive software transactional memory, synchronization among threads is realized using lightweight spin mutexes. In the case where the algorithm detects that convergence is not possible in phase one, it transitions into phase two where convergence is prioritized over maximum parallelism. To achieve convergence, each thread in phase two routes only congested nets that have been assigned to it by a partitioner. The partitioner aims to reduce the contention among threads at the cost of an unbalanced load. In addition, periodic rip up of the entire route tree is employed to break the algorithm out from a local minimum. When only congested nets are rerouted, ParaFRo with 8 threads achieves an average speedup of 26.2× relative to VTR. In contrast, existing works managed to obtain an average speedup of up to 9.42× with 8 threads. Besides, ParaFRo is able to maintain the high speedups while producing similar quality of result as VTR in terms of critical path delay. Finally, the quality of result is relatively independent of the number of the threads.

Routing of nets is one of the most time consuming steps in the FPGA design flow. While existing works have described ways of accelerating the process through parallelization, they are not scalable. In this paper, we propose a scalable way of parallelizing the routing algorithm through Lagrangian relaxation. The FPGA routing problem is formulated as a linear programming problem, and the channel width constraints, which limit the amount of parallelism, are relaxed by incorporating them into the objective function. The result of the relaxation yields independent sub-problems that we solve using minimum Steiner tree algorithms. Our approach outperforms the state-of-the-art FPGA parallel router by producing an average self-relative speedup of 7.05X with 8 threads, reduces the total wire length by 22.4% on average and has similar channel width requirements as VPR, albeit at the cost of 7.5% longer critical path. Another advantage of our algorithm is that the number of threads and the order in which the nets are routed has totally no impact on the quality of result.

Leakage power has become an important component of the total power consumption in FPGAs as process technology shrinks. In addition, a significant amount of leakage power in FPGAs is consumed by the routing resources. Therefore, leakage power reduction in FPGAs should begin with the routing resources. In this paper, we propose a novel directional coarse-grained power gating architecture for switch boxes. In addition, the existing VPR routing algorithm has been adapted with a new cost function to support the new power gating architecture. Results have shown that the new cost function yields an average improvement of 22% as compared to the existing VPR cost function in terms of the number of power gating regions that can be turned off.

High functional yield is one of the key challenges for subthreshold standard cell designs. Device upsizing is a commonly used but suboptimal method due to its overheads in energy and area. In this paper, we propose a robustness-driven intra-cell mixed-Vtdesign methodology (MVT-ULV) for the robust ultra-low voltage operation. It uses low threshold voltage transistors in the weak pulling network of logic gates to enhance the robustness. It guarantees the high functional yield with the minimum energy/area overheads. We demonstrate on a commercial 65nm CMOS process that, our proposed design methodology shows up to 60mV and 110mV robustness improvement at 300mV power supply voltage over the commercial library cells and the cells built with previous Leakage-Minimization mixed-Vtmethods (MVT-LM) under the same cell area constraints, respectively. In addition, the proposed MVT-ULV library enables ITC'99 benchmark circuits to show on average 30.1% and 78.1% energy-efficiency improvement when compared to the libraries built with the device-upsizing methods and the previous MVT-LM methods under the same yield constraints, respectively.

With the increasing number of processors in Multiprocessor System-on-Chips (MPSoCs), Network-on-Chips (NoCs) are replacing conventional buses as the interprocessor communication architecture. Since different use cases might be running on MPSoCs, there is a need for dynamically reconfigurable NoC. However, most dynamically reconfigurable NoCs have a large area overhead due to the additional reconfiguration logic. While recently some dynamically reconfigurable NoCs have been proposed based on partial reconfiguration (PR), they have high reconfiguration delay and require off-line bitstream generation for all possible scenarios. The problem lies with the design of the crossbar switch, which is the fundamental component of a NoC. In this paper, a novel partially reconfigurable crossbar switch design with low area requirement, low reconfiguration delay and runtime bitstream generation is presented. The crossbar switch is built from lookup tables (LUTs), and reconfiguration is done by modifying the LUTs' content through PR. Reconfiguration delay is minimized by constraining the placement of the LUTs into the least number of configurable logic block columns and identifying the configuration frames that are responsible for LUTs' content. The novel crossbar switch design achieves an area saving of up to 84% and reconfiguration delay minimization of up to 78%. It can be used to realize any network topology, and Clos, Benes and single stage crossbar topologies are evaluated in the paper.