A modern field-programmable gate array (FPGA) often contains an ASIC-like clocking architecture which is crucial to achieve better skew and performance. Existing conventional FPGA placement algorithms seldom consider clocking resources, and thus may lead to clock routing failures. To address the special FPGA clocking architecture, this article presents an effective clock-aware placement algorithm for large-scale heterogeneous FPGAs. Our algorithm consists of four major technologies: 1) a combinatorial clock fence region method to effectively reduce the overuse of clocking resources; 2) a smoothed heterogeneous density function to lead heterogeneous blocks to desired sites and a coordinate transformation technique to facilitate CLB cell spreading; 3) a heterogeneous force modulation algorithm to stabilize placement movement and a hierarchical contraction technique to remedy an insufficiency of the multilevel placement framework; and 4) a two-level clock-aware packing and legalization scheme to generate an optimized, clocking-violation-free placement. We evaluate our results based on the ISPD 2017 Clock-Aware Placement Contest benchmark suite. Compared with the state-of-the-art placers, the experimental results show that our algorithm achieves the best-routed wirelength.

The 2.5D FPGA is a promising technology to accommodate a large design in one FPGA chip, but the limited number of inter-die connections in a 2.5D FPGA may cause routing failures. To resolve the failures, input/output time-division multiplexing is adopted by grouping cross-die signals to go through one routing channel with a timing penalty after netlist partitioning. However, grouping signals after partitioning might lead to a suboptimal solution. Consequently, it is desirable to consider simultaneous partitioning and signal grouping although the optimization objectives of partitioning and grouping are different, and the time complexity of such simultaneous optimization is usually high. In this paper, we propose a simultaneous partitioning and grouping algorithm that can not only integrate the two objectives smoothly, but also reduce the time complexity to linear time per partitioning iteration. Experimental results show that our proposed algorithm outperforms the state-of-the-arts flow in both cross-die signal timing criticality and system-clock periods.

FPGAs have emerged as a popular style for modern circuit designs, due mainly to their non-recurring costs, in-field reprogrammability, short turn-around time, etc. A modern FPGA consists of an array of heterogeneous logic components, surrounded by routing resources and bounded by I/O cells. Compared to an ASIC, an FPGA has more limited logic and routing resources, diverse architectures, strict design constraints, etc.; as a result, FPGA placement and routing problems become much more challenging. With growing complexity, diverse design objectives, high heterogeneity, and evolving technologies, further, modern FPGA placement and routing bring up many emerging research opportunities. In this paper, we introduce basic architectures of FPGAs, describe the placement and routing problems for FPGAs, and explain key techniques to solve the problems (including three major placement paradigms: partitioning, simulated annealing, and analytical placement; two routing paradigms: sequential and concurrent routing, and simultaneous placement and routing). Finally, we provide some future research directions for FPGA placement and routing.

A modern FPGA often contains an ASIC-like clocking architecture which is crucial to achieve better skew and performance. Existing conventional FPGA placement algorithms seldom consider clocking resources, and thus may lead to clock routing failures. To address the special FPGA clocking architecture, this paper presents a novel clock-aware placement algorithm for large-scale heterogeneous FPGAs. Our algorithm consists of three major stages: (1) a nonlinear global placement framework with clock fence region construction, (2) a clock-aware packing scheme, and (3) clock-aware legalization and detailed placement. We evaluate our results based on the 2017 ISPD Clock-Aware Placement Contest benchmark suite. Compared with the top three winners, the results show that our algorithm achieves the best overall routed wirelength. On average, our algorithm outperforms the top-3 winners by 3.6%, 7.5%, and 12.9% in routed wirelength, respectively.