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     

Circuit performance optimization and model fitting based on simulated annealing

An efficient new method, based on the coupling between an enhanced simulated annealing algorithm and the SPICE-PAC ‘open’ circuit simulator, is proposed for minimizing objective functions describing circuit performance optimization problems or component model fitting to experimental data. To keep the number of objective function evaluations and CPU times to the lowest possible level, we focus our attention on two features: first, we build an original partitioning technique for splitting large n-dimensional problems; then we carefully study variables discretization, (which is necessary for applying the simulated annealing method to continuous problems). To illustrate the efficiency of our method, we show how to determine the 40 MOS transistor model parameters, through fitting the model to experimental data.     

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     

Simulated annealing algorithms: an overview

A brief introduction is given to the actual mechanics of simulated annealing, and a simple example from an IC layout is used to illustrate how these ideas can be applied. The complexities and tradeoffs involved in attacking a realistically complex design problem are illustrated by dissecting two very different annealing algorithms for VLSI chip floorplanning. Several current research problems aimed at determining more precisely how and why annealing algorithms work are examined. Some philosophical issues raised by the introduction of annealing are discussed     

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.     

基于神经网络的时延驱动版图规划算法

本文用离散的网格代替连续的版图规划平面,把长宽比可变的软模块对应成多个长度和宽度均确定的硬模块,给出了相应的时延驱动版图规划问题的形式化描述,并提出了基于均场退火网络的新的求解算法.算法用一个三维二值换位矩阵将问题映射为神经网络,建立包含时延约束、重叠约束和优化目标的能量函数,再用均场退火方程迭代求解.对应于同一软模块的硬模块有且只有一个能且只能放置在版图规划平面一个位置上的约束用神经元归一化的方法解决.本算法已用Visual C++编程实现,实验结果表明,这是一种有效的方法.     

基于模拟退火算法的多相序列搜索

具有良好相关特性的多相序列是许多有源传感和通信系统的组成部分。由于该序列的搜索是一个非线性多变量的优化问题,寻找高效的搜索方法至关重要。为了获得相关性好的多相序列,文章提出将具有全局优化能力的模拟退火算法引入到多相序列的搜索问题中。基本原理是为序列搜索建立适当的目标函数,调试出适当的退火和停止规则。通过大量对搜索性能和收敛参数进行的数值实验结果来看,文章显示采用模拟退火算法来设计具有良好相关性的多相序列是可行且有效的,特别是当优化问题的参数数量较大时。     

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.     

State assignment scheme for two-level logic implementation based on a simulate annealing algorithm with a fast cost estimation method

A state assignment algorithm for two-level logic implementation based on a simulated annealing algorithm is proposed. To save CPU time an efficient cost estimation method is devised without losing much estimation accuracy. The experimental results based on 40 benchmark example finite state machines show that the number of cubes and area obtained by the proposed approach is approximately 10% less than that of the two-level state assignment program NOVA within a comparable CPU time. For a large example, it could reduce the number of product terms by more than 40%.<>     

Simultaneous scheduling, allocation and binding in high levelsynthesis

The authors describe a new and efficient algorithm for concurrent scheduling, allocation and binding in high level synthesis (HLS). Globally optimum data path realisations with efficient single-level interconnect structures are rapidly obtained using a novel strategy for the generation of new synthesis solutions applied to simulated annealing. An example of a fifth-order wave digital filter is included     

Massive MIMO异构网的高能效资源分配

为满足第五代移动通信系统高频谱效率和高能量效率的需求,提出一种工作在不同频段下行两层异构网中的高能量效率资源分配方法,考虑用户数据率需求和基站最大发射功率。天线和传输带宽是影响系统能量效率的关键因素。通过研究宏基站和小基站的天线资源和带宽分配发现:当系统天线数很大时,发射功耗的影响可以忽略不计;给定带宽分配因子时,达到宏基站或微基站最大发射功率的天线分配因子几乎可以达到最高能效;给定天线分配因子时,系统平均总功耗是关于带宽分配因子的下凸函数,存在全局最优带宽分配因子使能效最高。仿真结果表明,与给定带宽和天线资源的异构网和小小区网络相比,所提出的异构网可以显著提高系统能量效率,而且在大量用户、高数据率需求时能效提升更明显。      

Fast motion estimation using modified orthogonal search algorithm for video compression

This paper presents a novel method named as Modified Orthogonal Search Algorithm (MOSA) for the block based motion estimation. Recently fast search algorithm for video coding using Orthogonal Logarithmic Search Algorithm (OSA) has been proposed by Soongsathitanon et al. (IEEE Trans Consum Electron 51(2):552–559, 2005). We introduce the center biased search point pattern for the estimation of small motions and a half way stop technique to reduce the computational complexity in the existing OSA. This feature improves the speed performance of the algorithm by 80% as compared to the Full Search Algorithm, 50% over the Three Step Search algorithm and 2% faster than the OSA. However, the Mean Square Error and Signal to Noise Ratio did not show significant deviation from the orthogonal logarithmic search algorithm and the three step search algorithm. The experimental results based on the number of video sequences were presented to demonstrate the advantages of proposed motion estimation technique.     

Telecommunication access network design with reliability constraints

In this paper, we study the problem of the design of telecommunication access networks with reliability constraints. These networks form an important part of the telecommunications infrastructure of large organizations, such as banks. Using data patterned after an actual bank network in the U.S., we formulate an optimization model for this problem which specifically takes into account the various cost, and discount structures offered by telecommunication carriers. We then develop dedicated solution procedures for obtaining solutions. Starting from a cluster solution, we then use perturbation techniques which we developed specifically for this problem within an overall simulated annealing solution algorithm. We show how to make the solution procedure more efficient by implicitly determining the values for many variables. We then report the results of our computational testing for a variety of problems. We compare our solution to a lower bound obtained using a linear programming relaxation. We show that substantial cost savings can be realized with our model, and solution procedure. Finally, we discuss which types of annealing steps in the simulated annealing algorithm are important.     

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.     

Method for the design of diffractive optical elements through low-dimensional optimization

A method for the simulation and design of diffractive optical structures is presented. In this paper, we present a design of a finite diffractive-optic structure that has been generated by solving for the electromagnetic fields inside an optimization loop. The scalar electromagnetic fields are computed in the region of a two-dimensional diffractive-optic structure by solving the scalar Helmholtz equation, using the finite-difference method. This analysis process is inserted into a simulated annealing algorithm that designs the optimal structure by maximizing a predetermined figure of merit. Computationally efficient methods that allow for reasonable computational requirements are described, including the defining of structure parameters as relatively simple polynomial functions. This allows for changes in the structure to be made by the program while maintaining a small number of dimensions for the search by the simulated annealing algorithm.     

Multi-scale Single Image Super-Resolution with Remote-Sensing Application Using Transferred Wide Residual Network

In the integrated circuit (IC) designing floorplanning is an important phase in the process of obtaining the layout of the circuit to be designed. The floorplanning determines the performance, size, yield, and reliability of VLSI ICs. The obtained results in this step are necessary for the other consecutive process of the chip designing. VLSI floorplanning from the computational point of view is a non-polynomial hard (NP-hard problem), and hence cannot be efficiently solved by the classical optimization techniques. In this paper, we have proposed a metaheuristic approach to address the problem by using the parallel particle swarm optimization (P-PSO) technique. The P-PSO uses a new greedy operation on the sequence pair (SP) to explore the search space to find an optimal solution. Experimental results on the Microelectronic Centre of North Carolina and Gigascale Systems Research Center benchmark shows that the applied parallel PSO (P-PSO) may be used to produce an optimal solution.

     

An efficient macro-cell placement algorithm

A new approximation algorithm is presented for the efficient handling of large macro-cell placement problems. The algorithm combines simulated annealing with new features based on a hierarchical approach and a divide-and-conquer technique. Numerical results show that these features can lead to a considerable increase in efficiency of the placement algorithm without loss of effectiveness.     

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.     

Q学习算法在机会频谱接入信道选择中的应用

针对“先听后传”的机会频谱接入中认知用户的信道选择问题,本文提出了一种基于Q学习的信道选择算法。在非理想感知的条件下,通过建立认知用户的信道选择模型并设计恰当的奖励函数,使智能体能够与未知环境不断交互和学习,进而选择长期累积回报最大的信道接入。在学习过程中,本文引入了Boltzmann实验策略,运用模拟退火思想实现了资源探索与资源利用之间的折衷。仿真结果表明,所提算法能够在未知环境先验知识条件下可以快速选择性能较好的信道接入,有效提高认知用户的接入吞吐量和系统的平均容量。      

An adaptive local-search algorithm for the channel-assignmentproblem (CAP)

The channel-assignment problem (CAP) for cellular radio networks is an NP-complete problem. Previous techniques for solving this problem have used graph-coloring algorithms, neural networks, simulated annealing, and pattern-based optimization procedures. We describe an efficient two-phase adaptive local-search algorithm for the channel-assignment problem. This algorithm has been applied to several existing benchmark problems with encouraging results. In many cases it outperforms the existing algorithms in the quality of the solution obtained. When used in conjunction with structured preprocessing, the algorithm can be applied to large networks. It is thus a practical tool for the planning of cellular radio networks