Search

When dealing with partially reconfigurable designs on field-programmable gate array, floorplanning represents a critical step that highly impacts system’s performance and reconfiguration overhead. However, current vendor design tools still require the floorplan to be manually defined by the designer. Within this paper, we provide a novel floorplanning automation framework, integrated in the Xilinx tool chain, which is based on an explicit enumeration of the possible placements of each region. Moreover, we propose a genetic algorithm (GA), enhanced with a local search strategy, to automate the floorplanning activity on the defined direct problem representation. The proposed approach has been experimentally evaluated with a synthetic benchmark suite and real case studies. We compared the designed solution against both the state-of-the-art algorithms and alternative engines based on the same direct problem representation. Experimental results demonstrated the effectiveness of the proposed direct problem representation and the superiority of the defined GA engine with respect to the other approaches in terms of exploration time and identified solution. [ABSTRACT FROM AUTHOR]

It is well known that optimizations made by traditional logic synthesis tools often correlate poorly with postlayout performance; this is largely a result of interconnect effects only being visible after layout. In this paper, a corrective methodology is proposed for timing-driven logic restructuring at the placement level. The approach focuses on a lookup table (LUT)-based field-programmable gate arrays. The approach is iterative in nature. In each iteration, using current placement information, the method induces a timing-critical fan-in tree via (temporary) replication. Such trees are then reimplemented where the degrees of freedom include functional decomposition of LUTs, "mini-LUT" tree mapping, and physical embedding. A dynamic programming algorithm optimizes over all of these freedoms simultaneously. All simple disjoint LUT decompositions (i.e., Ashenhurst style) are encoded in a "mini-LUT" tree using choice nodes similar to those in the paper by Lehman et al. At the same time, because embedding is done simultaneously, interconnect delay is directly taken into account. Over multiple iterations, the design is progressively improved. The framework has been implemented, and promising experimental results are reported. [ABSTRACT FROM AUTHOR]

The main goal of this paper is to develop deeper in- sights into viable placement-level optimization of routing. Two primary contributions are made. First, an experimental framework in which the viability of "predictive" or "probabilistic" models of routing congestion for optimization during detailed placement can be evaluated is developed. The main criterion of consideration in these experiments is how (un)reliably various models from the literature detect routing hot spots. It was concluded that such models appear to be too unreliable for detailed placement optimization. Second, motivated by the first result, a single combinatorial framework in which cell placement and "exact" routing structures are captured and optimized is presented; the framework relies on the "trunk decomposition" of global routing structures, and optimization is performed by generalization of the "optimal interleaving" algorithm. An implementation of this framework is studied in the field-programmable gate array domain. The technique can reduce the number of channels at maximum density by more than 60% on average with maximum reduction of more than 81% for optimized global routing taking only 75% of the Versatile Place and Route (VPR) placement and routing runtime combined. For the standard cell domain, routing-based interleaving, on average, reduces the maximum track count by more than two tracks with a maximum reduction of nine tracks. [ABSTRACT FROM AUTHOR]

This paper presents a set of techniques for placement-coupled timing-driven logic replication. Two components are at the core of the approach. First, is an algorithm for optimal timing-driven fanin tree embedding; the algorithm is very general in that it can easily incorporate complex objective functions (e.g., placement costs) and can perform embedding on any graph-based target. Second, the replication tree is introduced, which allows to induce large fanin trees from a given circuit, which can then be optimized by the embedder. The authors have built an optimization engine around these two ideas and report promising results for the field-programmable gate array (FPGA) domain including clock period reductions of up to 36% compared with a timing-driven placement from versatile place and route (VPR) (Marquardt et al., 2000) and almost double the average improvement of local replication (Beraudo and Lillis, 2003). These results are achieved with modest area and runtime overhead. In addition, issues that arise due to reconvergence in the circuit specification are addressed. The authors build on the replication tree idea and enhance the timing-driven fanin tree embedding algorithm to optimize subcritical paths, yielding even better delay improvements. [ABSTRACT FROM AUTHOR]

We give an overview of a buffer tree synthesis package which pays particular attention to the following issues: routing and buffer blockages, minimization of interconnect and buffer costs, congestion, exploitation of temporal locality among the sinks, and addressing sink polarity requirements. Experimental results demonstrate the effectiveness of the tool in comparison with previously proposed techniques. [ABSTRACT FROM AUTHOR]

This paper presents two primary results relevant to physical design problems in CAD/VLSI through a case study of the linear placement problem. First a local search mechanism which incorporates a sophisticated neighborhood operator based on constraint relaxation is proposed. The strategy exhibits many of the desirable features of analytical placement while retaining the flexibility and non-determinism of local search. The second and orthogonal contribution is in netlist clustering. We characterize local optima in the linear placement problem through a simple visualization tool--the displacement graph . This characterization reveals the relationship between clusters and local optima and motivates a dynamic clustering scheme designed specifically for escaping such local optima. Promising experimental results are reported. [ABSTRACT FROM AUTHOR]

Focuses on a study which examined Steiner-tree constructions for difficult instances to optimize the buffered tree resulting from the van Ginneken-style buffer insertion. Notation and problem formulation; Information on the proposed clustered tree algorithm; Experimental comparison.

Presents results in the area of timing optimization for multisource nets. Formulations presented; Description of the repeater insertion algorithm; Details on the experiments conducted; Conclusion.