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

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

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

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

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     

An orthogonal simulated annealing algorithm for large floorplanning problems

The conventional simulated annealing with some random generation mechanism using the sequence-pair topological representation in block placement and floorplanning is effective for a very small number of modules (40-50). This paper proposes an orthogonal simulated annealing algorithm (OSA) with an efficient generation mechanism (EGM) for solving large floorplanning problems. EGM samples a small number of representative floorplans and then efficiently derives a high-performance floorplan by using a systematic reasoning method for the next move of OSA based on orthogonal experimental design. Furthermore, an improved swap operation is proposed which cooperates with EGM to make OSA efficient. Excellent experimental results using the Microelectronics Center of North Carolina and the Gigascale Systems Research Center benchmarks show that OSA performs better than existing methods for large floorplanning problems.     

Corner block list representation and its application to floorplan optimization

We propose to use a corner block list (CBL) representation for mosaic floorplans. In a mosaic floorplan, each room has only one block assigned to it. Thus, there is a unique corner room on the top right corner of the chip. Corner block deletion and corner block insertion keep the floorplan mosaic. Through a recursive deletion process, a mosaic floorplan can be converted to a representation that is named as CBL. Given a CBL, it takes only linear time to construct the floorplan. The CBL is used for the application to very large-scale integration floorplan and building block placement. We adopt a simulated annealing process for the optimization. Soft blocks and the aspect ratio of the chip are taken into account in the optimization process. The experimental results demonstrate that the algorithm is quite promising.     

基于数据通路结构的FPGA编译系统策略

在基于FPGA的电路设计流程中,对电路规整性的利用将层致系统性能和布图效率的提高。针对现有的FPGA设计软件对电路属性,尤其是规整性和层次性,考虑不够,导致在实现数据通路（datapath)电路时性能欠佳的事实,文章提出了一种适合具有大量规整单元的电路的FPGA编译系统构架架。此CAD系统结构将充分考虑具有规整结构的电路单元的特殊性,从编译系统的输入部分入手,尽可能区分并区别对待普通逻辑与规整单元,以便优化规单元,以至整个电路系统的性能,最后,利用模拟退火的布图规划策略完成布图的迭代优化。     

填充启发式算法的二维矩形排样问题

针对小矩形切割的二维排样问题,尤其是对玻璃或厚钢板等材料,在切割时定向一次性切割到头的排布.结合综合蚂蚁算法和模拟退火算法思想,提出了一种最低水平线与填充式算法相结合的启发式排样算法.通过对计算机上随机产生的实验数据进行模拟,实现了自动排样.实验表明,该算法提高了单次切割的材料利用率,得到较好的排样效果.     

Net-based force-directed macrocell placement for wirelength optimization

We propose a net-based hierarchical macrocell placement such that "net placement" dictates the cell placement. The proposed approach has four phases. 1) Net clustering and net-level floorplanning phase: a weighted net dependency graph is built from the input register-transfer-level netlist. Clusters of nets are then formed by clique partitioning and a net-cluster level floorplan is obtained by simulated annealing. The floorplan defines the regions where the nets in each cluster must be routed. 2) Force-directed net placement phase: a force-directed net placement is performed which yields a coarse net-level placement without consideration for the cell placement. 3) Iterative net terminal and cell placement phase: a force-directed net and cell placement is performed iteratively. The terminals of a net are free to move under the influence of forces in the quest for optimal wire length. The cells with high net length cost may "jump" out of local minima by ignoring the rejection forces. The overlaps are reduced by employing electrostatic rejection forces. 4) Overlap removal and input/output (I/O) pin assignment phase: Overlap removal is performed by a grid-based heuristic. I/O pin assignment is performed by minimum-weight bipartite matching. Placements generated by the proposed approach are compared with those generated by Cadence Silicon Ensemble and the O-tree floorplanning algorithm. On average, the proposed approach improves both the total wire length and longest wire length by 18.9% and 28.3%, respectively, with an average penalty of 5.6% area overhead.     

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.     

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.     

A fast force-directed simulated annealing for 3D IC partitioning

With the advent of three dimensional (3D) IC designs, new partitioning techniques that can take into account the 3D nature of designs are required. In this paper, a new force-directed simulated annealing (FSA) is introduced and used for 3D partitioning. The proposed force-directed simulated annealing introduces force as a new factor during the annealing process and replaces the random moves by probabilistic force-directed moves. Experimental results show that the force-directed move strategy speeds up the convergence and significantly improves the execution time of SA maintaining the quality of solution. FSA algorithm is effective for 3D IC partitioning and can be applied in other optimization problems.     

Hierarchical 3-D Floorplanning Algorithm for Wirelength Optimization

Three-dimensional (3-D) IC physical design problems are usually of higher complexity, with a greatly enlarged solution space due to multiple device structure. In this paper, a new 3-D floorplanning algorithm is proposed for wirelength optimization. Our main contributions and results can be summarized as follows. First, a new hierarchical flow of 3-D floorplanning with a new inter-layer partitioning method. The blocks are partitioned into different layers before floorplanning. A simulated annealing (SA) engine is used to partition blocks with the objective of minimizing the statistical wirelength estimation results. The solution quality is not degraded by the hierarchical flow. Second, floorplans of all the layers are generated in a SA process. Original 3-D floorplanning problem is transformed into solving several 2-D floorplanning problems simultaneously. The solution space is scaled down to maintain a low design complexity. Finally, Experimental results show that our algorithm improves wirelength by 14%-51% compared with previous 3-D floorplanning algorithms. The hierarchical approach is proven to be very efficient and offers a potential way for high-performance 3-D design     

Reconfigurable topology synthesis for application-specific NoC on partially dynamically reconfigurable systems

In this paper, a four-stage method for synthesizing reconfigurable ASNoC topology is proposed for partially dynamically reconfigurable systems, where the topology is reconfigured dynamically at run-time along with the application's execution. Firstly, a simulated annealing based topology-aware integrated optimization framework is proposed to generate the proper schedule and floorplan of task modules. Secondly, based on the schedule and floorplan of task modules, an Integer Linear Programming (ILP)-based method and a heuristic method, are proposed to partition the communication requirements of the application into $T$ time intervals. Thirdly, we explore the proper positions of switches in the floorplan for global communications. Finally, considering the reconfiguration costs between adjacent time intervals, the routing path allocation problem is solved for time intervals in an iterative procedure to generate fine-grained dynamically reconfigurable ASNoC topologies. Experimental results show that, compared to the random partition of communication requirements, the proposed heuristic method and ILP-based method can achieve 5.4% and 10.0% power consumption improvement, respectively. And, the reconfigurable ASNoC can achieve 31.6% power consumption improvement when compared with static ASNoC.     

Discrete frequency-coded radar signal design

A modified simulated annealing algorithm (MSAA) is proposed as combinatorial multivariable optimisation technique to design discrete frequency-coding (DFC) sequence sets with good auto- and cross-correlation properties. The proposed algorithm is a combination of simulated annealing and Hamming scan algorithm. MSAA has global minimum estimation capability of simulated annealing and fast convergence rate of Hamming scan algorithm. Some of the synthesised results are presented, the properties of the sequence sets are shown to be better than the other sequence sets known in the literature. Synthesised DFC sequence sets have properties far better than polyphase sequence sets. The synthesised DFC sequence sets are promising for practical application to netted radar/multiple radar systems.     

基于SA-ANN的认知机制建模与识别优化算法

人脑认知过程机制建模是人工智能研究领域的重要方向,当前基于统计模板分析与反向传播神经网络（BP-ANN）的认知方法在聚类计算与知识理解方面存在不足.针对上述问题,提出了一种基于模拟退火神经网络（SA-ANN）的认知过程机制建模方法.对人脑认知物理过程及其基本特征进行了分析,建立了面向认知过程的SA-ANN推理模型.提出了一种改进的模拟退火神经网络（ISA-ANN）识别优化算法,对认知过程信息特征提取、知识学习训练等关键环节进行了模拟研究.设计了认知过程机制算例,开发了相应的原型软件系统,对理论结果进行了验证.结果证明,该方法具有较好的聚类性能,可以针对具体测试对象进行准确识别,能够得到相对精确的认知演化规律.     

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.     

线长驱动的层次式FPGA布局算法

针对层次式FPGA结构的特点,提出了以线长为目标的层次式FPGA布局算法.该算法基于模拟退火优化策略,针对层次式FPGA实际芯片结构的特点,提出了线长计算方法和搜索范围确定方法;同时,给出了提高算法速度的快速布局方法.实验结果表明,该方法不仅能够减小时间代价,也能够得到比较好的布局质量.     

Individual wire-length prediction with application to timing-driven placement

In this paper, we address the problem of individual wire-length prediction and demonstrate its usefulness in timing-driven placement. Many researchers have observed that different placement algorithms produce different individual wire lengths. We postulate that to obtain accurate results, individual wire-length prediction should be coupled with the placement flow. We embed the wire-length prediction into the clustering step of our fast placer implementation (FPI) framework . The predicted wire lengths act as constraints for the simulated annealing refinement stage, which guides the placement toward a solution fulfilling them. Experimental results show that our prediction process yields accurate results without loss of quality and incurs only a small cost in placement effort. We successfully apply the wire-length prediction technique to timing-driven placement. Our new slack assignment algorithm with predicted wire lengths (p-SLA) gives on average an 8% improvement in timing performance compared with the conventional modified zero-slack algorithm (m-ZSA).     

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.     

快速buffer添加算法

在深亚微米设计中,连线延迟时间已经超过器件延迟时间,成为影响性能的瓶颈之一。在线网中插入缓冲器（buffer）是改善线延迟的一种有效方法,但是目前基于缓冲器块（bufferblock）的方法一般因其计算量比较大,算法比较慢,并且也增加布局（floorplan）的复杂性。为此本文提出并实现了一种新的快速算法来解决芯片顶层互连中缓冲器添加问题。