固定边框的多电压布图规划算法

多电压设计是应对SoC功耗挑战的一种有效方法,但会带来线长、面积等的开销。为减少线长、芯片的空白面积及提高速度,提出了一种改进的固定边框多电压布图方法.对基于NPE（Normalized Polish Expression）表示的布图解,采用形状曲线相加算法来计算其最优的布图实现,并通过增量计算方法来减少计算NPE及多电压分配的时间.为使所得布图解满足给定的边框约束,提出了一个考虑固定边框约束的目标函数,并采用删除后插入（Insertion after Delete,IAD）算子对SA求得布图解进行后优化.实验结果表明,和已有方法相比,所提出方法在线长和空白面积率方面有较明显优势,且所有电路在不同高宽比、不同电压岛数下均实现了极低的空白面积率（< <1%）.     

面向软模块的稳定固定边框布图规划算法

该文提出一种稳定的面向软模块的固定边框布图规划算法。该算法基于正则波兰表达式(Normalized Polish Expression, NPE)表示,提出一种基于形状曲线相加和插值技术的计算NPE最优布图的方法,并运用模拟退火(Simulation Annealing, SA)算法搜索最优解。为了求得满足固定边框的布图解,提出一种基于删除后插入(Insertion After Delete, IAD)算子的后布图优化方法。对8个GSRC和MCNC电路的实验结果表明,所提出算法在1%空白面积率的边框约束下的布图成功率接近100%,在总线长上较已有文献有较大改进,且在求解速度上较同类基于SA的算法有较大优势。     

Fixed-outline floorplanning: enabling hierarchical design

Classical floorplanning minimizes a linear combination of area and wirelength. When simulated annealing is used, e.g., with the sequence pair representation, the typical choice of moves is fairly straightforward. In this paper, we study the fixed-outline floorplan formulation that is more relevant to hierarchical design style and is justified for very large ASICs and SoCs. We empirically show that instances of the fixed-outline floorplan problem are significantly harder than related instances of classical floorplan problems. We suggest new objective functions to drive simulated annealing and new types of moves that better guide local search in the new context. Wirelength improvements and optimization of aspect ratios of soft blocks are explicitly addressed by these techniques. Our proposed moves are based on the notion of floorplan slack. The proposed slack computation can be implemented with all existing algorithms to evaluate sequence pairs, of which we use the simplest, yet semantically indistinguishable from the fastest reported . A similar slack computation is possible with many other floorplan representations. In all cases the computation time approximately doubles. Our empirical evaluation is based on a new floorplanner implementation Parquet-1 that can operate in both outline-free and fixed-outline modes. We use Parquet-1 to floorplan a design, with approximately 32000 cells, in 37 min using a top-down, hierarchical paradigm.     

An exact algorithm for wirelength optimal placements in VLSI design

We present a new algorithm designed to solve floorplanning problems optimally. More precisely, the algorithm finds solutions to rectangle packing problems which globally minimize wirelength and avoid given sets of blocked regions. We present the first optimal floorplans for 3 of the 5 intensely studied MCNC block packing instances and a significantly larger industrial instance with 27 rectangles and thousands of nets. Moreover, we show how to use the algorithm to place larger instances that cannot be solved optimally in reasonable runtime.     

An adaptive hybrid memetic algorithm for thermal-aware non-slicing VLSI floorplanning

Floorplanning is a crucial step in very large scale integration design flow. It provides valuable insights into the hardware decisions and estimates a floorplan with different cost metrics. In this paper, to handle a multi-objective thermal-aware non-slicing floorplanning optimization problem efficiently, an adaptive hybrid memetic algorithm is presented to optimize the area, the total wirelength, the maximum temperature and the average temperature of a chip. In the proposed algorithm, a genetic search algorithm is used as a global search method to explore the search space as much as possible, and a modified simulated annealing search algorithm is used as a local search method to exploit information in the search region. The global exploration and local exploitation are balanced by a death probability strategy. In this strategy, according to the natural mechanisms, each individual in the population is endowed with an actual age and a dynamic survival age. Experimental results on the standard tested benchmarks show that the proposed algorithm is efficient to obtain floorplans, with decreasing the average and the peak temperature.     

Block flipping and white space distribution for wirelength minimization

Floorplanning plays an important role in the physical design of very large scale integration (VLSI) circuits. Traditional floorplanners use heuristics to optimize a floorplan based on multiple objectives. Besides traditional floorplanning approaches, some post-floorplanning steps can be applied to consider block flipping, pin assignment and white space distribution to optimize the performance. If we can consider the above three optimizations simultaneously as a post-floorplanning step, the total wirelength can be further reduced without modifying the original floorplan topology. Experimental results show that our approach can handle these issues simultaneously and wirelength can be further improved with a small penalty in runtime. Thus, this approach is highly desirable to be incorporated into a floorplanner as a post-processing step for wirelength optimization.     

APWL-Y: An accurate and efficient wirelength estimation technique for hexagon/triangle placement

The Y architecture has recently received much attention due to its many potential advantages, such as substantially reduced wirelength, power consumption and significantly improved throughput. To fully utilize the virtues of Y architecture, several hexagon/triangle placement (HTP) algorithms suitable for the Y architecture were presented, however the wirelength optimization is not included in the algorithms. Wirelength estimation is fundamental to guide the wirelength optimization process in early design stages. In this paper, we present an accurate and efficient wirelength estimation technique called APWL-Y appropriate for the Y architecture, and especially for HTP floorplanner and placer. The average error of APWL-Y is 4.41% for 1.57 million nets from industrial circuits. When developing APWL-Y, we find out that 3-SMT wirelength is a power function of aspect ratio of bounding box of the given n-pin nets. The time complexity of APWL-Y is O(n). APWL-Y is very effective to guide the wirelength optimization in a HTP placer. Moreover, we develop an efficient HTP algorithm with wirelength optimization driven by APWL-Y estimator. The placement results by our placer subject to different optimization objectives are presented. Compared to the HTP placer with only area optimization, our placer can reduce the wirelength by 54.3% with a small area overhead of 9.07% on average. In addition, we explore the HPWL technique in the Y architecture. To the best of our knowledge, this paper is the first in-depth study on wirelength estimation technique in Y architecture and HTP floorplanning optimization with consideration of interconnects.     

Regularity-constrained floorplanning for multi-core processors

Multi-core technology becomes a new engine that drives performance growth for both microprocessors and embedded computing. This trend requires chip floorplanners to consider regularity constraint since identical processing/memory cores are preferred to form an array in layout. In general, regularity facilitates modularity and therefore makes chip design planning easier. As chip core count keeps growing, pure manual floorplanning will be inefficient on the solution space exploration while conventional floorplanning algorithms do not address the regularity constraint for multi-core processors. In this work, we investigate how to enforce regularity constraint in a simulated annealing based floorplanner. We propose a simple and effective technique for encoding the regularity constraint in sequence-pairs. To the best of our knowledge, this is the first work on regularity-constrained floorplanning in the context of multi-core processor designs. Experimental comparisons with a semi-automatic method show that our approach yields an average of 12% less wirelength and mostly smaller area.     

Fast floorplanning for effective prediction and construction

Floorplanning is a crucial phase in VLSI physical design. The subsequent placement and routing of the cells/modules are coupled very closely with the quality of the floorplan. A widely used technique for floorplanning is simulated annealing. It gives very good floorplanning results but has major limitation in terms of run time. For circuit sizes exceeding tens of modules simulated annealing is not practical. Floorplanning forms the core of many synthesis applications. Designers need faster prediction of system metrics to quickly evaluate the effects of design changes. Early prediction of metrics is imperative for estimating timing and routability. In this work we propose a constructive technique for predicting floorplan metrics. We show how to modify the existing top-down partitioning-based floorplanning to obtain a fast and accurate floorplan prediction. The prediction gets better as the number of modules and flexibility in the shapes increase. We also explore applicability of the traditional sizing theorem when combining two modules based on their sizes and interconnecting wirelength. Experimental results show that our prediction algorithm can predict the area/length cost function normally within 5-10% of the results obtained by simulated annealing and is, on average, 1000 times faster     

Multi-bend bus driven floorplanning

In this paper, the problem of bus-driven floorplanning is addressed. Given a set of blocks and bus specifications (the width of each bus and the blocks that the bus need to go through), we will generate a floorplan solution such that all the buses go through their blocks, with the area of the floorplan and the total area of the buses minimized. The approach proposed is based on a simulated annealing framework. Using the sequence pair representation, we derived and proved some necessary conditions for feasible buses, for which we allow 0-bend, one-bend, or two-bend. A checking will be performed to identify those buses that cannot be placed simultaneously. Finally, a solution will be generated giving the coordinates of the modules and the buses. Comparing with the results of the most updated work on this problem by Xiang et al. [Bus-driven floorplanning, in: Proceedings of IEEE International Conference on Computer-Aided Design, 2003, pp. 66-73], our algorithm can handle buses going through many blocks and the dead space of the floorplan obtained is also reduced. For example, if the buses have to go through more than 10 blocks, the approach in Xiang et al. [Bus-driven floorplanning, in: Proceedings of IEEE International Conference on Computer-Aided Design, 2003, pp. 66-73] is not able to generate any solution while our algorithm can still give solutions of good quality.     

Energy/Area/Delay Tradeoffs in the Physical Design of On-Chip Segmented Bus Architecture

The increasing gap between design productivity and chip complexity and the emerging systems-on-chip (SoCs) architectural template have led to the wide utilization of reusable hard intellectual property (IP) cores. Macro block-based physical design implementation needs to find a well-balanced solution among chip area, on-chip communication energy, and critical communication path delay. We present in this paper an automated way to implement an energy optimal netlist interconnecting the hard macro blocks using a heavily segmented communication architecture. We explore the entire tradeoff curve among the network energy, chip area, and critical communication path delay at the floorplanning stage based on two real-life application drivers. Large energy gains with small area overheads are illustrated during the floorplanning stage. This tradeoff profile is a good guideline for the SOC designers to choose the optimal solution for their specific systems.     

Multi-layer floorplanning for stacked ICs: Configuration number and fixed-outline constraints

3-D (stacked device layers) ICs can significantly alleviate the interconnect problem coming with the decreasing feature size and is promising for heterogeneous integration. In this paper, we concentrate on the configuration number and fixed-outline constraints in the floorplanning for 3-D ICs. Extended sequence pair, named partitioned sequence pair (in short, P-SP), is used to represent 3-D IC floorplans. We prove that the number of configuration of 3-D IC floorplans represented by P-SP is less than that of planar floorplans represented by sequence pair (SP) and decreases as the device layer number increases. Moreover, we applied the technique of block position enumeration, which have been successfully used in planar fixed-outline floorplanning, to fixed-outline multi-layer floorplanning. The experimental results demonstrate the efficiency and effectiveness of the proposed method.     

On the superiority of modularity-based clustering for determining placement-relevant clusters

In advanced technology nodes, IC implementation faces increasing design complexity as well as ever-more demanding design schedule requirements. This raises the need for new decomposition approaches that can help reduce problem complexity, in conjunction with new predictive methodologies that can help avoid bottlenecks and loops in the physical implementation flow. Notably, with modern design methodologies it would be very valuable to better predict final placement of the gate-level netlist: this would enable more accurate early assessment of performance, congestion and floorplan viability in the SOC floorplanning/RTL planning stages of design. In this work, we study a new criterion for the classic challenge of VLSI netlist clustering: how well netlist clusters “stay together” through final implementation. We propose the use of several evaluators of this criterion. We also explore the use of modularity-driven clustering to identify natural clusters in a given graph without the tuning of parameters and size balance constraints typically required by VLSI CAD partitioning methods. We find that the netlist hypergraph-to-graph mapping can significantly affect quality of results, and we experimentally identify an effective recipe for weighting that also comprehends topological proximity to I/Os. Further, we empirically demonstrate that modularity-based clustering achieves better correlation to actual netlist placements than traditional VLSI CAD methods (our method is also 2× faster than use of hMetis for our largest testcases). Finally, we propose a flow with fast “blob placement” of clusters. The “blob placement” is used as a seed for a global placement tool that performs placement of the flat netlist. With this flow we achieve 20% speedup on the placement of a netlist with 4.9 M instances with less than 3% difference in routed wirelength.     

A fast temperature-aware fixed-outline floorplanning framework using convex optimization

With aggressive scaling of CMOS technology, it is essential to consider chip temperature in all design levels of digital systems to improve chip reliability and leakage power consumption. In this paper, we present a two phase fixed-outline floorplanning framework that attempts to reduce the peak-temperature of the chip. The first phase distributes evenly the available dead space between the floorplan blocks of a chip, so as to reduce the peak-temperature. The second phase employs a two-stage convex optimization formulation to perform fixed-outline floorplanning such that minimizes the peak-temperature while satisfying physical constraints. To mitigate the time and computational complexity of capturing the temperature behavior, we present a less computational expensive analogous formulation that approximates the temperature of a block by its corresponding power density. Although, the corresponding power density formulation exhibits lower complexity the experimental results demonstrate its high degree of accuracy. Moreover, this formulation manages to achieve significant improvements in terms of peak-temperature and runtime for almost all of the test cases. We investigate the trade-off between peak-temperature and area as well and provide conditions that result in a reasonable reduction of peak-temperature with minimum increase of the dead space.     

Fast thermal analysis for fixed-outline 3D floorplanning

Three dimensional integrated circuits (3D ICs) can alleviate the problem of interconnection, a critical problem in the nanoscale era, and are also promising for heterogeneous integration. However, the thermal challenge in industry is one of key obstacles to adopt the 3D ICs technology. Various thermal analysis models for 3D IC have been proposed in literature. However, the long simulation cycle makes runtime of thermal management inefficient during floorplanning phase. In this paper, we propose a fast thermal analysis method for fixed-outline 3D floorplanning. Before floorplanning, we simulate the thermal distribution of each block placed on different positions. Based on the simulated thermal profiles, bilinear interpolation is adopted to quickly estimate temperature during floorplanning. After the block planning, a heuristic method, which combines the shortest path and min-cost-max-flow, is presented for TSV allocation with minimization of chip temperature and wirelength. Compared with the superposition of thermal profiles method, the proposed thermal analysis method can reduce the peak temperature by 6.7% on average with short runtime for 3D fixed-outline floorplanning, which demonstrates the efficiency and effectiveness of the proposed thermal analysis method.     

FPCS——一种适用于积木块方式的布局及平面规划系统

本文简述了一种分级式的自下而上结群和自上而下分划定位相结合的全定制方式的积木块(building block)布局及平面规划(floorplanning)系统.本方法基于积木块的尺寸、形状、连接状况、引线位置以及芯片引线端等的要求逐级优化组合若干种积木块组,并且根据工艺条件进行了布线区面积估计,以便得到较好的布局结果.如果积木块的尺寸或其长宽比可以改变,则本系统可改变其尺寸及形状从而优化布局结果.由于采用了多种有效的实用方法,并把它们有机地统一在系统中,因此使布局能在基本满足用户要求的条件下,做到和布线结果基本匹配.实验结果表明,这种方法是令人满意的.     

3D IC floorplanning: Automating optimization settings and exploring new thermal-aware management techniques

The introduction of 3D chip architectures is an increasingly attractive integration solution due to the potential performance improvement, power consumption reduction and heterogeneous integration. Nevertheless, thermal distribution, evacuation and limitation constitute some of the key issues that can hinder widespread adoption of 3D integration technology. Efficient 3D floorplan algorithms have to be developed to address such complexity. In this paper we first discuss the implementation of such an algorithm and identify parameters that play a role in the solution quality. We then propose the use of a genetic algorithm to discover sets of parameters that guarantee good ?oorplan quality. Then, we present an improved thermal-aware ?oorplanner based on a new formulation of the cost function that minimizes not only peak temperature, but also thermal gradients. The temperature minimization goal is reinforced using a smart heuristic that guides 3D moves in the direction of placing power hungry blocks next to the heat sink. Experimental results show the ability of the method to reduce the temperature peak and gradient signi?cantly, while maintaining area, wirelength and computation time.     

Solving modern mixed-size placement instances

Physical design of modern systems-on-chip is extremely challenging. Such digital integrated circuits often contain tens of millions of logic gates, intellectual property blocks, embedded memories and custom register-transfer level (RTL) blocks. At current and future technology nodes, their power and performance are impacted, more than ever, by the placement of their modules. However, our experiments show that traditional techniques for placement and floorplanning, and existing academic tools cannot reliably solve the placement task.To study this problem, we identify particularly difficult industrial instances and reproduce the failures of existing tools by modifying pre-existing benchmark instances. Furthermore, we propose algorithms that facilitate placement of these difficult instances. Empirically, our techniques consistently produce legal placements, and on instances where comparison is possible, reduce wirelength by 13% over Capo 9.4 and 31% over PATOMA 1.0—the pre-existing tools that most frequently produce legal placements in our experiments.     

A fast matrix iterative technique for the WLS design of 2-D quadrantally symmetic FIR filters

High computational complexity is a major problem encountered in the optimal design of two-dimensional (2-D) finite impulse response (FIR) filters. In this paper, we present an iterative matrix solution with very low complexity to the weighted least square (WLS) design of 2-D quadrantally symmetric FIR filters with two-valued weighting functions. Firstly, a necessary and sufficient condition for the WLS design of 2-D quadrantally symmetric filters with general nonnegative weighting functions is obtained. Then, based on this optimality condition, a novel iterative algorithm is derived for the WLS design problem with a two-valued weighting function. Because the filter parameters are arranged in their natural 2-D form and the transition band is not sampled, the computation amount of the proposed algorithm is reduced significantly, especially for high-order filters. The exponential convergence of the algorithm is established, and its computational complexity is estimated. Design examples demonstrating the convergence rate and solution accuracy of the algorithm, as well as the relation between the iteration number of the algorithm and the size and transition-band width of the filter are given.     

New directions in semicustom arrays

The CMOS Gate Forest is such a semicustom array which offers an integration level comparable to that of a full-custom VLSI environment. A hierarchical design approach has become essential in order to be able to handle the complexity of such an implementation environment. Although the Gate Forest is representative of second-generation gate arrays, it also incorporates a number of unique features. The Gate Forest is used to describe the major features of a current semicustom design environment. Partitioning, floorplanning, and mapping operation characteristics are described. Current status of the different parts of the Gate Forest design environment are described