Search

As interconnects dominate circuit performance in modern FPGAs, placement becomes a crucial stage for timing closure. Traditional FPGA placers seldom consider the timing constraints, and thus may lead to illegal routing solutions. In this paper, we present an incremental timing-driven placement flow for advanced FPGAs. First, a timing-based global placement strategy is designed to guide heterogeneous blocks to desired locations with satisfied timing constraints. Then, a timing-aware packing algorithm is developed to mitigate the design complexity while improving the timing results. Finally, we propose a critical path-based optimization method to generate optimized layout without timing violations. We evaluate our algorithm based on industrial circuits using an advanced FPGA device. The experimental results show that our placer achieves an 5.1% improvement in worst slack, and produces placements that require 16.7% less time to route when compared with the leading commercial tool Xilinx Vivado.

Field programmable gate array (FPGA) packing and placement without routability consideration could lead to unroutable results for high-utilization designs. Conventional FPGA packing and placement approaches are shown to have severe difficulties to yield good routability. In this paper, we propose an FPGA packing and placement engine called UTPlaceF that simultaneously optimizes wirelength and routability. A novel physical and congestion aware packing algorithm and a hierarchical detailed placement technique are proposed. UTPlaceF outperforms state-of-the-art FPGA placers simultaneously in runtime and solution quality on International Symposium on Physical Design (ISPD) 2016 benchmark suite. Compared with the top three winners of ISPD’16 FPGA placement contest, UTPlaceF can deliver 6.2%, 11.6%, and 29.1% better routed wirelength with shorter runtime.

Irregular packing problems exist widely in industrial applications. To obtain better packing results, packing shapes are rotated freely during the packing process. However, equal angle-intervals are commonly used in the existing packing algorithms without considering the shape contour features, which may miss the best packing positions with the reduced packing quality. To solve this problem, an irregular packing algorithm is proposed based on a principal component analysis methodology in this paper. The principal components of convex features on the shapes are calculated. The rotation angles are then searched according to the first principal components. Finally, the shapes are rotated and packed based on the rotation angles. Experimental results show that the packing time is reduced and the material utilization is improved by the proposed algorithm.

An optimization procedure for the layout assessment of electrically large but finite planar arrays is presented. The synthesis takes into account the desired directivity pattern that is prescribed employing bound constraints. Moreover, the size of the radiators is taken into account, which results in a hard nonoverlapping, between the elements, constraint. The latter should not be violated if we want the attained solution not only to obey the far-field mask, but also to be physically realizable. As stated, the optimization problem is twofold. An antenna design is associated with a packing problem. In order to take the constraints on the layout into account and solve the whole problem, we propose the constraint relaxation approach, which is equipped with a packing algorithm. Our study is applied to various initial geometries, and the resulting arrays appear to comply with the desired pattern and the nonoverlapping constraint. Several examples for different cases including symmetric arrays and a study on maximally sparse arrays are presented, which show the applicability and merit of the method.

Local microscopic particle density variation stemming from packing density far below unity is one of the important aspects of digital tape recording. In this paper, we present a modeling methodology for simulating realistic particle packing in particulate tape media. The packing algorithm is able to generate randomly dispersed tape particles with packing density as high as 34%-40% and user-defined parameters such as easy axes orientation, aspect ratio variation, size distribution, etc. Micromagnetic modeling of recording characteristics have also been conducted to study the impact of various aspects of packing.