Ordered escape routing (OER), which seeks the routing paths from some signal pins to the boundary of a pin array in a given order, is an important research topic for PCB design. Although reinforcement learning based methods for OER have been proposed, the routing capacity between two adjacent pins is assumed to be just one. In this work, we propose MCMC-Escape, a Monte-Carlo tree search (MCTS) based multi-capacity ordered escape router, which includes, in turn, the initial solving approach, the improved Monte-Carlo tree search (improved MCTS) process, and the last routing attempt approach based on wires removing and re-routing. In the improved MCTS, the prior knowledge based pruning strategies and the fine-tuning strategy are proposed to enhance the efficiency of solving multi-capacity OER (MC-OER) problems, while the weight adjusting strategy is proposed to address the path occupancy issues arising from multiple capacity. Experimental results demonstrate that MCMC-Escape can effectively solve large-scale MC-OER problems and outperform existing methods in terms of routing success rate, runtime and wire length. For a set of problems with 50×50 pin array, MCMC-Escape achieves 4X higher success rate of routing with 50% less solving time than MCMCF-Router [ 1 ], while reducing the average total wire length.

Ordered escape routing (OER), which means that the pins need to be routed to the boundary of a pin array in a given order, is an important research topic in PCB design. Although OER has been widely investigated, most works assume that the routing capacity between two adjacent pins is just 1 and the structure of the pin array is a grid pin array. In this article, we focus on multi-capacity ordered escape routing (MC-OER) both in grid pin arrays and staggered pin arrays, which means that multiple wires are allowed to pass through between two adjacent pins. We first propose a multi-capacity multi-commodity flow (MC-MCF) model for the MC-OER problem. To accelerate the routing process, MCMCF-Router is proposed. In MCMCF-Router, a wiring resources driven partition strategy is proposed to reduce the problem size, followed by the approach based on routing conflicts. These approaches largely accelerate the MC-MCF model based method and increase the routability with minimal sacrifice on wire length. Experiments on various cases (with up to 525 pins) show that the proposed method achieves 100% routability within reasonable time (<810 seconds). Compared to the state-of-the-art works for single-capacity OER problems, MCMCF-Router performs similarly well or better.

Ordered escape routing(OER) is a key problem in PCB-board level routing. In this paper, a compact model driven by linear constraints for ordered escape routing problem is proposed. The model can solve the ordered escape routing with minimized wire length. Our algorithm builds an injective map between the solution space of model and the solution space of OER. Linear contraints are added to eliminate infeasible solutions. Without loss of solution feasibility and optimality, this model can prune the integer linear programming(ILP) variables(constraints) by 79.43%(74.05%) compared to previous work. To further accelerate the speed, a partition strategy based on the routing region of each net is proposed. This can divide the problem into several sub-problems. Experimental results show that, compared to former method which considers wire length, our compact model with partition can achieve up to 100 times speed up with solutions that have almost the same cost.

Many-core chip architectures integrate tens to hundreds of processor cores on a single chip. Recent development of photonic interconnects has made Optical Networks-on-Chips (ONoCs) an attractive technology to overcome the drawbacks of electrical networks-on-chips. With ultra-high bandwidth, low latency, and great energy efficiency, ONoCs enable the designer to build scalable systems. However, photonic devices are sensitive to temperature fluctuations, and hence, require proactive management. This paper first calculates the thermal distribution from cell distribution using an approximated Green's function and proposes a post-placement algorithm to reduce the number of photonic devices in the hotspots. The paper then improves the routing algorithm considering bending loss and temperature variations. Experimental results also verify the efficiency and effectiveness of our algorithm.

Ordered escape routing is a critical issue in high-speed PCB routing. Differential pair and thermal-blockage-avoided are useful in PCB design to obtain high noise immunity and low electromagnetic interference. In this article, a Min-cost Multi-commodity Flow (MMCF) approach is proposed to solve the ordered escape routing. First, the characteristic of grid pin array and staggered pin array is analyzed and then a basic network model is used to convert ordered escape routing to MMCF model. To satisfy the constraints of ordered escape routing, three novel transformations, such as non-crossing transformation, ordering transformation, and capacity transformation, are used to convert the basic network model to the final correct MMCF model. After that, the differential pair in ordered escape routing is discussed. Finally, a method to deal with the blockage issue is proposed. Experimental results show that our method achieves 100% routability for all the test cases. The method can get both a feasible solution and an optimal solution for ordered escape routing. Compared to published approaches, our method improves in both wire length and CPU time remarkably. At the same time, the proposed method can effectively avoid the blockage and deal with the differential pair.

Power consumption has become one of the major challenges in current chip design. One effective low power technology, multiple supply voltages (MSVs), has succeeded in 2D network-on-chip (NoC) design. However, few researches considered the MSV in 3D NoC, especially application-specific 3D NoC. In this paper, a complete three-stage synthesis flow for MSV-driven application-specific 3D NoC is proposed, which involves all the issues of layer assignment, voltage level assignment, 3D NoC synthesis, floorplanning, and post-floorplanning adjustment. First, a unified model is presented considering both layer assignment and voltage level assignment, which achieves the best tradeoff between core power and communication power. After that, a 3D NoC synthesis method is proposed to assign network components (NCs) to each layer and generate interlayer connections while a two-stage floorplanning algorithm is used to determine the positions of both cores and NCs. Finally, a novel transitive closure graph-based post-floorplanning repacking algorithm is applied to further reduce the communication power without changing much of the floorplan. Experimental results show that the proposed method is very effective. Compared to traditional 3D NoC, the proposed method can reduce the core power by about 33.6%; compared to MSV-driven 2D NoC, the proposed method can reduce the communication power by about 52.6%.

Ordered Escape routing is a critical issue in high-speed PCB routing. In this paper, for the first time, a Min-cost Multi-commodity Flow (MMCF) approach is proposed to solve the ordered escape routing. The characteristic of grid pin array is analyzed and then a basic network model is used to convert ordered escape routing to MMCF model. To satisfy the constraints of ordered escape routing, three novel transformations, such as non-crossing transformation, ordering transformation and capacity transformation, are used to convert the basic network model to the final correct MMCF model. Experimental results show that our method achieves 100% routability for all the test cases. The method can get both a feasible solution and an optimal solution. Compared to published approaches, our method improves in both wire length and CPU time remarkably.

A multilayer routing system usually adopts multiple interconnect configuration with different wire sizes and thicknesses. Since thicker layers of metal lead to fatter wires with smaller resistance, the layer assignment (LA) of nets has a large impact on the interconnect delay. However, such layer-dependent characteristics have been ignored by most of the state-of-the-art academic LA methods. These characteristics also weaken the previous wire length-based antenna avoidance method, because the net length itself cannot accurately capture the antenna area under the condition of various wire sizes. To remedy this deficiency, this paper proposes a more effective three-stage LA algorithm under multitier interconnect structure, and focuses on minimizing delays, via count, and antenna violations. It first minimizes the total delay and via count simultaneously by dynamic programming and negotiation technique, and then further minimizes the maximum delay carefully while almost unchanging the via count. After that, a check-and-repair method is adopted to further fix the antenna violations. The experimental results on the International Conference on Computer-Aided Design'09 benchmarks show that the proposed algorithm can significantly reduce the total delay and maximum delay while still keeping roughly the same via count compared with the state-of-the-art via count minimization LA method negotiation-based via minimization algorithm. At the same time, the antenna violation repair method can dramatically reduce the antenna violated nets and sinks with little impact on the solution quality.

In this paper, a transitive closure graph (TCG)-based post-floorplanning repacking algorithm is proposed for power optimization of Multiple Supply Voltages (MSV)-driven application specific 2D NoC. Through a five-stage processing including floorplan representation, preconditioning, objective insertion point calculation, TCG modification and ILP-based incremental repacking, the total communication power can be optimized without changing much of the original floorplan. Experimental results show that the proposed method can reduce the communication power by 28.3%.

Escape routing has become a critical issue in high-speed PCB routing. Most of the previous work paid attention to either differential-pair escape routing or single-signal escape routing, but few considered them together. In this paper, a significant three-stage algorithm is proposed to solve the problem of escape routing of both differential pairs and single signals (mixed-pattern signals). First, differential pairs are preconditioned to reduce the complication of the problem. Then, a unified ILP model is used to formulate the problem and a novel Boolean coding-driven algorithm is proposed to avoid mixed crossings. Finally, a slice-based method is presented to prune the variables and speed up the algorithm. Experimental results show that the proposed method is very effective. For single-pattern escape routing, it can solve all the test cases in short time and reduce wire length and chip area by 16.1% and 15.5%, respectively. For mixed-pattern escape routing, it can increase the routability by 17.5% and reduce the wire length by 14.1% compared to a two-stage method. At the same time, the proposed method can effectively avoid mixed crossings with only a little increase on wire length. Furthermore, with slice-based speedup strategy, the method can reduce the solving time by 76.7%.

In this paper, a MSV-driven power optimization method is proposed for application-specific 3D NoC (MSV-3DNoC). A unified modeling method is presented for considering both layer assignment and voltage assignment, which achieves the best trade-off between core power and communication power. A 3D NoC synthesis is proposed to assign network components onto each layer and generate inter-layer interconnection. A global redistribution is applied to further reduce communication power. Experimental results show that compared to MSV-driven 2D NoC, the proposed method can improve total chip power greatly.

A multilayer routing system usually adopts multiple interconnect configuration with different wire sizes and thicknesses. Since thicker layers of metal lead to fatter wires with smaller resistance, the layer assignment of nets has a large impact on the interconnect delay. However, such layer dependent characteristics have been ignored by most of the state-of-the-art academic layer assignment methods. To remedy this deficiency, this work studies a more effective layer assignment problem under such multi-tier interconnect structure, which arises during 3D global routing and focuses on minimizing both delays and via count. This work presents a two-stage algorithm to solve the problem, which first minimizes the total delay and via count simultaneously by dynamic programming and negotiation technique, and then further minimizes the maximum delay carefully while not increasing the via count. The experimental results on ICCAD09 benchmarks show that the proposed algorithm can significantly reduce the total delay and maximum delay while still keeping roughly the same via count, compared with the state-of-the-art via count minimization layer assignment method NVM.

Escape routing has become a critical issue in high-speed PCB routing. Most of previous work paid attention to either differential-pair escape routing or single-signal escape routing but few considered them together. In this paper, a unified ILP model is used to formulate the problem of escape routing of differential pairs together with single signals (mixed-pattern signals) on staggered pin array. A mixed-pattern escape routing algorithm is proposed to solve the problem and a slice-based heuristic method is presented to speed up the algorithm. Experimental results show that the proposed method is very efficient. It can solve all the test cases in short time and improve wire length and chip area by 13.8% and 13.4% respectively compared to traditional pin array. At the same time, the method can increase routability by 16.3% and reduce the wire length by 9.3% compared to a two-stage method.

We considered the one-sided single-detour untangling twisted nets problem for printed circuit board bus routing. A previous optimal dynamic programming based O(n3) algorithm was proposed in a previous work, where n is the number of nets. In this paper, we propose an optimal O(n) untangling algorithm without considering capacity, and this algorithm is further modified to consider capacity. Experimental results show that our algorithms runs much faster than the previous work due to its low time complexity.

In this paper, a voltage island aware framework is proposed for low power design of application specific NoC (LPASNoC). Through a three-phase processing including voltage island generation, VI-driven floorplanning and post-floorplan processing, the total power consumption, design cost and total wire length can be optimized. Experimental results show that compared to traditional ASNoC, the proposed method can reduce total core power by about 34.5% and chip area by about 26.8% without increasing communication power.

Task scheduling and core mapping have a significant impact on the overall performance of network on chip (NOC). In this paper, a unified task scheduling and core mapping algorithm called UNISM is proposed for different NOC architectures including regular mesh, irregular mesh and custom networks. First, a unified model combining scheduling and mapping is introduced using mixed integer linear programming (MILP). Then, a novel graph model is proposed to consider the network irregularity and estimate communication energy and latency, since the number of network hops is not accurate enough for irregular mesh and custom networks. To make the MILP-based UNISM scalable, a heuristic is employed to speed up our method. Compared with two previous state-of-the-art works, experimental results show that more than 15% and 11.5% improvement on the execution time is achieved with similar energy consumption on average for regular mesh NOC. For irregular and custom NOC, the improvement is 27.3% and 14.5% on the execution time with 24.3% and 18.5% lower energy. Moreover, our method is scalable for large benchmarks in terms of runtime.

Due to the increased power density and lower thermal conductivity, 3D is faced with heat dissipation and temperature problem seriously. Previous researches show that leakage power and delay are both relevant to temperature. The timing-power-temperature dependence will potentially negate the performance improvement of 3D designs. TSV (Through-Silicon-Vias) has been shown as an effective way to help heat removal, but they create routing congestions. Therefore, how to reach the trade-off between temperature, via number and delay is required to be solved. Different from previous works on TSV planning which ignored the effects of leakage power, in this paper, we integrate temperature-leakage-timing dependence into thermal via planning of 3D ICs. A weighted via insertion approach, considering both performance and heat dissipation with resource constraint, is proposed to achieve the best balance among delay, via number and temperature. Experiment results show that, with leakage power and resource constraint considered the temperature and via number required can be quite different, and weighted TSV insertion approach can improve thermal via number, by about 5.6%.

Low power design has become one of the most significant requirements when CMOS technology entered the nanometer era. Therefore, timing budget is often performed to slow down as many components as possible so that timing slacks can be applied to reduce the power consumption while maintaining the performance of the whole design. Retiming is a procedure that involves the relocation of flip-flops (FFs) across logic gates to achieve faster clocking speed. In this paper we show that the retiming and slack budgeting problem can be formulated to a convex cost dual network flow problem. Both the theoretical analysis and experimental results show the efficiency of our approach which can not only reduce power consumption by 8.9%, but also speedup previous work by 500 times.

Network-on-chip (NoC) architectures have been proposed as a promising alternative to classical bus-based communication architectures. In this paper, we propose a two phases framework to solve application-specific NoCs topology generation problem. At floorplanning phase, we carry out partition driven floorplanning. At post-floorplanning phase, a heuristic method and a min-cost max-flow algorithm is used to insert switches and network interfaces. Finally, we allocate paths to minimize power consumption. The experimental results show our algorithm is effective for power saving.

As a global interconnection, bus is critical for chip performance in deep submicron technology. Reducing bus routing vias will facilitate the lithography and give bus routing a higher yield and also a higher performance. In this paper, we present a floorplan revising method to minimize the number of reducible routing vias with a controllable loss on the chip area and wirelength. Therefore, it is easy to make a proper tradeoff between via reduction and revising loss. Experiments show that our method reaches a 96.2% and 93.5% reduction of routing vias, which is close to 100% and runs fast. Besides, our revising is friendly to all third-party floorplanners, which can be applied to any existing floorplans to reduce vias. It is also scalable to larger benchmarks.

We revisit voltage partitioning problem when the mapped voltages of functional units are predetermined. If energy consumption is estimated by formulation E=CV2,a published work claimed this problem was NP-hard. We clarify that it is polynomial solvable, then propose an optimal algorithm, its time complexity is O(nk+k2d) which is best so far, where n, k, and d are respectively the numbers of functional units, available supply voltages, and voltages employed in the final design. In reality, considering leakage power the energy-voltage curve is not simply monotonically increasing and there is still no optimal polynomal polynomial time algorithm. However, under the assumption that energy-voltage curve is quasiconvex, which is also a good approximation to actual situation, the optimal solution can be got in time O(nk2). Experimental results show that our algorithms are more efficient than previous works.

In this paper, a wirelength-driven force-directed three-dimension (3-D) Field Programmable Gate Arrays (FPGA) placement algorithm (3D-WFP) is presented. The algorithm is composed of three stages: Overlap permitted force-directed 2-D placement, legalization and 3-D layer partition. Different from traditional partition-based 3-D placers, we adjust the layer partition process after the 2-D global placement, which effectively provides the global interconnection and timing information for the next two sub-steps. To legalize the position of the logic block, a 3-D space filling curve is adopted. A low temperature simulated annealing (SA) is used to determine the blocks final layer. Only blocks with the same horizontal coordinate are permitted to interchange, the speed of the SA is very fast. Compared to recently publish 3-D FPGA placement work, this algorithm improves the half perimeter wire-length (HPWL) by 8.57%, almost at the same time cost and keeps the same timing performance.

Power optimization has become a significant issue when the CMOS technology entered the nanometer era. Multiple-Supply Voltage (MSV) is a popular and effective method for power reduction. Level shifters may cause area and Interconnect Length Overhead(ILO), and should be considered during floorplanning and post-floorplanning stages. In this paper, we propose a two phases framework VLSAF to solve voltage and level shifter assignment problem. At floorplanning phase, we use: a convex cost network flow algorithm to assign voltage; a minimum cost flow algorithm to assign level shifter. At post-floorplanning phase, a heuristic method is adopted to redistribute white spaces and calculate the positions and shapes of level shifters. Experimental results show VLSAF is effective.

With recent advance of VLSI design, interconnect delay plays dominant role in the chip performance. 3D integration, which stacks multiple device layers, greatly reduces interconnect delay. Buffer insertion, as another approach to reduce wire delay, is still necessary to further optimize interconnects. In this paper, a buffer planning algorithm at floorplanning stage for 3D ICs is proposed. Firstly, we reduce buffer insertion to a dynamic programming path problem. Then we show its potential to handle the 3D buffer insertion problem. At the same time, vertical interlayer vias are also planned. At last, buffer planning is integrated with floorplanning to optimize the packing so that not only area and wire length reach a satisfying value, timing performance is also optimized.

Thermal issue is a critical challenge in 3D IC circuit design. Incorporating thermal vias into 3D IC is a promising way to mitigate thermal issues by lowering down the thermal resistances between device layers. However, it is usually difficult to get enough space at target regions to insert thermal vias. In this paper, we propose a novel analytical algorithm to re-allocate white space for 3D ICs to facilitate via insertion. Experimental results show that after reallocating whitespaces, thermal vias and total wirelength could be reduced by 14% and by 2%, respectively. It also shows that whitespace distribution with via planning alone will degrade performance by 9% while performance-aware via planning method can reduce thermal via number by 60% and the performance is kept nearly unchanged.

The conventional tools for mismatch elimination such as geometric symmetry and common centroid technology can only eliminate systematic mismatch, but can do little to reduce random mismatch and thermal-induced mismatch. As the development of VLSI technology, the random mismatch is becoming more and more serious. And in the context of Silicon on Insulator (SOI), the self-heating effect leads to unbearable thermal-induced mismatch. Therefore, in this paper, we first propose a new model which can estimate the combination effect of both random mismatch and thermal-induced mismatch by mismatch analysis and SPICE simulation. And in order to meet the different sensitivities of different symmetry pairs, an automatic classification tool and a configurable optimization process are also introduced. All of these are embedded in the floorplanning process. The final experimental results prove the effectiveness of our method.

To reduce the miss rate of the instruction cache, a hardware-assisted loop optimization method is proposed in this paper. This method utilizes the hardware/software co-design strategy on the behavior level. Especially, this method is equipped with the specific instruction set to limit the cache misses, which can be viewed as a set of hardware for special purposes. Then based on the specific instruction set, a scheduling process is integrated which reduces the cache miss rate through the code transformation. Finally, a set of benchmarks from MediaBench1.0 are tested on the SimpleScalar platform to assist the proposed method. The final experiments indicate that 26% enhancement can be obtained for the cache miss reduction, where the specific instruction generation and the scheduling processes contribute about 23% and 3% respectively.

This paper presents an efficient hybrid memory access optimization system called HyMacs, which integrates the hardware and software optimization strategies in the embedded system design. First, HyMacs features a pre-configuration stage which is equipped with a memory configuration algorithm to satisfy area constraints. Then a custom instruction generation process is integrated in the system via a seed-growth algorithm under the intelligent guide functions. The custom instruction benefits to the reduction of the whole memory access latency and thus relieves the burden of system through hardware mode. Finally, a data-dependency-driven scheduling algorithm is also integrated to compress the whole latency through access mode conversion. We have tested the system on a set of commonly used benchmarks, and compared the results with the previous memory access system MACCESS-opt proposed in DAC'05. The experimental results indicate 20% enhancement obtained for the total memory access latency reduction compared with MACCESS-opt, where the custom instruction generation and scheduling contribute about 15% and 5% respectively.

Fixed-outline floorplanning, which enables hierarchical design, is considered more and more important nowadays. In this paper, a novel SA-based Fixed-outline Floorplanner with the Optimal Area utilization named SAFFOA is introduced to improve the total wirelength. The basic idea is to build and solve a group of four quadratic equations in four variables iteratively, which can handle the fixed-outline constraint of any aspect ratio. A new topological representation called Ordered Quadtree is then custom-made for this basic idea to facilitate its integration into SA iterations. After the fixed-outline constraint with 100% area utilization is achieved, we will solve the tradeoff between the chip area and wirelength and thus concentrate on the latter in SA process. Experimental results show that the chip wirelength is decreased by about 16.8% and 8.6% on average, compared with two previous fixed-outline floorplanners on soft modules, which are both proved to be better than Parquet. Besides, our method is still competitive on the wirelength, even if compared with some leading-edge outline-free floorplanners. At last, Local Refinement is also adopted to guide the SA process and reshape soft modules to meet the constraint on their aspect ratios (ARs). With its help, SAFFOA can still generate feasible floorplans with no deadspace under a strict AR constraint such as [0.5,2].

In the context of SOI, thermal constraint is more serious for analog devices. Besides the hot-spot effect, the temperature gradient on symmetrical devices may cause errors and even failures in the function. In order to handle these problems, this paper introduces an accurate thermal model into the placement process. Based on the geometric symmetry which is achieved with corner block list (CBL) for the first time, the thermal model helps to find the thermal-optimal placement. And the experimental results show this method is promising.

For modern processor designs in nanometer technologies, both block and interconnect pipelining are needed to achieve multi-gigahertz clock frequency, but previous approaches consider block pipelining and interconnect pipelining separately. For example, all recent works on wire pipelining assume pre-pipelined components and consider only inserting pipeline stages on point-to-point wire or bus connections. To the best of our knowledge, this paper is the first that considers block pipelining and interconnect pipelining simultaneously. We optimize multiple critical paths or loops in the micro-architecture and insert the pipelines stages optimally in the blocks and wires of these loops to meet the clock frequency requirement. We propose two approaches to this problem. The first approach is based on mixed integer linear programming (MILP) which is theoretically guaranteed to produce the optimal solution, and the second one is an efficient graph-based algorithm that produces near-optimal solutions. Experimental results show that simultaneous block and interconnect pipelining leads to more than 20% improvement over wire-pipelining alone on the overall processor performance. Moreover, the graph-based approach gives solutions very close to the MILP results ( 2% more than MILP results on average) but in a much shorter runtime.

To improve the computation efficiency of application specific instruction-set processor (ASIP), a strategy of hardware/software collaborative design is usually utilized. In this process, the auto-customization of instruction set has always been a key part to support the automated design of ASIP. The key issue of this problem is how to effectively reduce the huge exponential exploration space in the instruction identification process. To address this issue, we first formulate it as a sub-graph enumeration problem under multi-constraints, and then propose a fast instruction identification algorithm based on basic convex pattern (BCP) model. The kernel technique in this algorithm is the transformation from the graph exploration to the formula-based computations. Experimental results have indicated that the proposed algorithm has a distinct reduction on the execution time.

More and more IP cores are used in modern SOC designing. In order to place IP cores effectively, hierarchical design has been introduced and better supported by fixed-outline floorplanning than outline-free [1]. In this paper, we also consider buffer insertion issue in fixed-outline floorplanning with the help of the Less Flexibility First (LFF) algorithm, which runs in a fixed-outline area and places IP cores as hard modules one after another with no backtracks. Unlike Simulated Annealing (SA), LFF is a deterministic packing algorithm and runs without topological representations. Therefore, it is able to tell the difference among geometric floorplans with the same topological structure, which is helpful to get a better result for buffer planning since buffer insertions are quite sensitive to a geometric change. Moreover, a 2-staged packing and a post greedy method after packing are also introduced based on a net-classing strategy and finally help to achieve great success rate improvement of buffer insertion (about +40.7% in 0.18um and +37.1% in 0.07μm). Meanwhile, our buffer planning method runs much faster than SA, since it is deterministic and has no backtracks. Besides, it is also useful to provide an initial solution for SA for further optimization.

3D packing is a fundamental problem for VLSI design. It arises from 3D-ICs floorplan design and task schedule in reconfigurable FPGA design. In this paper, we present a novel 3D floorplan representation by improving the 3D bounded slice-surface grid (3D-BSG) structure in two aspects: (1) optimize the evaluation time complexity from O(n3) to O(n2) by using three block relation graphs; (2) handle the infeasible assignment problem of 3D-BSG in linear time by giving the rule of null relation rooms. The effectiveness and efficiency of the fast 3D-BSG are shown by both theoretical analysis and experimental results. The average speedup compared to the original 3D-BSG is 44times high.

This paper advances a new methodology based on signal-path information to resolve the problem of device-level placement for analog layout.This methodology is mainly based on three observations: thinking of hierarchical design for analog, structural feature of circuit based on signal-path, requirements of matching/symmetry constraint and the reduction of parasitics.The thinking of hierarchical design makes the whole analog circuit divided into core-circuit and bias-circuit.So, the algorithm is designed as two independent steps: core-circuit is placed firstly, and then bias-circuit.The structural feature of circuit based on signal-path and the requirement of matching/symmetry constraint decide the placement pattern of core-circuit.The reduction of parasitics requires the algorithm to select the optimal variants to realize the placement.Experimental results demonstrate that this algorithm can generate the compact layout with high performance and it is universal and effective.

This paper studies the buffer planning problem for interconnect-driven floorplanning. With development of deep submicron technology, interconnect plays dominant role and buffer-insertion is a most flexible and efficient way to resolve this problem. However, buffer-planning on a fixed topology which only optimizes area or total wire-length is not reasonable and at the same time, trying to generate a topology which optimizes timing is much too time-consuming. We develop an algorithm which exchanges blocks of similar size to optimize timing constraint. With this algorithm applied, based on a topology which has already optimized area, we generate a packing that doesn't increase total area but exchanges block's position so that interconnect performance could be optimized in reasonable time.

2.5-D integration is a promising technique to significantly reduce the interconnection delay and thus bring advancement to VLSI technology. New CAD tools and approaches are desired by 2.5-D IC circuit design. This paper designed a novel representation multi-layer-BSG and proposed an effective algorithm based on this structure. Quick strategy for solution evaluation and phrase-based strategy for simulated annealing engine are used to reduce the runtime complexity and to improve the performance. Compared with other representations, our algorithm are experimentally proved to be a better choice for 2.5-D floorplanning problem.

In this paper, we propose an efficient approach on handling the fixed-outline constraints with the objectives of both improving the success rate and minimizing the wire length. Our approach uses the less flexibility first principles (Sheqin Dong, 2001) which are derived from human's experience in solving rectangle packing problem in the daily life. In this construction based approach, success rate is guaranteed by using effective heuristics to guide the placement process. For the wire length objective, we use a wire length minimized solution gained by circuit partitioning and multilevel simulated annealing as a reference, where the topological relations derived from it are tried to be kept. We also apply a local grouping strategy and the minimal local wire length objective as supplements of wire length optimization. Experiment results show that our approach can achieve high success rates under tight outlines and comparable wire length with various aspect ratios

The Corner Block List representation (CBL) introduced in 2000 is an efficient and effective model for floorplanning and placement while still having some limitations such as redundancy and incompleteness. In this paper, we present an auxiliary 3-Route Model to eliminate the redundancy and insert empty rooms to resolve the incompleteness. Finally we attain a P-admissible representation ECBL(2) which has higher performances than the original CBL and the count of its solution space is O((2n)!26n/n!n4).

With increasing of FPGA densities and greater demand for performance, a hierarchical approach is often used in FPGA design. Floorplanning is a key ingredient of the hierarchical approaches. However, heterogeneous resources across FPGA fabric have made FPGA floorplanning quite different from traditional floorplanning for ASICs. Enlightened by human's accumulated experience in "packing" problem, we propose a "less flexibility first" (LFF) algorithm. Experiment results based on Xilinx's XC3S5000 show that our algorithm can work better for heterogeneous FPGA floorplanning problem.

In this paper, we present an efficient and effective algorithm addressed to fixed-outline floorplanning. Unlike simulated annealing based algorithms, the proposed algorithm starts with sub-instances of the given instance. When feasible solution of a sub-instance is found, it augments this instance and tries to find a feasible solution of the augmented instance. This process continues until feasible solution of the given instance is found, or some stopping criteria met. Local search without hill-climbing is adopted to search for feasible solution of each instance. To optimize wirelength, once feasible solution of current instance is found, instead of augments it immediately, the proposed algorithm performs another local search for this instance. Experiments on MCNC and GSRC benchmarks show that in most cases the proposed algorithm can obtain feasible floorplans in quite short time, even with tight outlines or outlines with large aspect ratios imposed, and the results of wirelength optimization are also quite promising.

In this paper, an efficient algorithm addressed to fixed-outline floorplanning is presented. The proposed algorithm takes sequence pair as representation and has following main features: (1) it uses common subsequence and penalty function to bound the variations of the widths of the floorplans to a quite small range; (2) a simple cost function which has no items about the heights of the floorplans is presented; (3) two-stage simulated annealing is adopted to minimize the wirelength. Experimental results show that the proposed algorithm is superior to other state-of-the-art fixed-outline floorplanning approaches in the following aspects: (1) it can achieve high successful probabilities, even with tight outlines and large aspect ratios given; (2) the feasibility of the given outline will be evaluated at the beginning of the floorplanning, which can save much time when infeasible outline is given. Besides, the experimental results on wirelength optimization are also promising.

The dominating contribution of interconnect to system performance has made it critical to plan the resources of the buffers and routes in the early stage of the layout. In this paper, we integrate floorplanning with buffer insertion for performance-driven design processes. We devise a two-step method to evaluate the feasible buffer insertion sites, which can improve the efficiency of the buffer-planning algorithm. By partitioning all empty spaces into blocks in the packing process, the buffer allocation is handled as an integral part of the floorplanning. Our buffer-planning algorithm maps the buffers into tiles with consideration of routing congestion. In this approach, we construct a distribution graph to model the possible routes. The buffer allocation method is performed on the updated distribution graph to find the buffer locations with their respective congestion costs. The method is based on a simulated annealing approach, which is composed of multiple phases to speed up the optimization. Since there is more freedom with floorplan optimization, the empirical results demonstrate better performance.

Corner Block List (CBL) was recently proposed as an efficient representation for MOSAIC packing of rectangles. Although the original method is really innovative, there still remains room for improvement for our purpose. This article proposes a compact algorithm for placement based on corner block list. By introducing the dummy blocks in CBL, our algorithm can intellectively employ dummy blocks in the packing to represent the placement including empty rooms, which corner block list cannot represent. Our algorithm can obtain the fast convergence to an optimal solution. Based on the compact approach, we propose a new way to handle arbitrary shaped rectilinear modules. The experimental results are demonstrated by some benchmark data and the performance shows effectiveness of the proposed method.

This paper studies the buffer planning problem for interconnect-centric floorplanning for nanometer technologies. The dead-spaces are the spaces within a placement that are not held by any circuit block. In this paper, we proposed a buffer planning algorithm based on dead space redistribution to make good use of dead-spaces for buffer insertion. Associated with circuit blocks under topological representations, the dead space can be redistributed by freely moving some circuit blocks within their rooms in the placement. The total area and the topology of the placement keep unchanged while doing the dead space redistribution. The number of nets satisfying the delay constraint can be increased by redistributing the dead space all over the placement, which has been demonstrated by the experimental results. The increment of the number of nets that satisfy delay constraints is 9% on an average.

Solution space smoothing allows a local search heuristic to escape from a poor, local minimum. In this paper, we propose a technique that can smooth the rugged terrain surface of the solution space of a placement problem. We design the solution space smoothing algorithms for VLSI placement with pre-placed modules and placement with consideration of congestion. Experiment results demonstrated that solution space smoothing is very efficient for VLSI module placement, and it can be applied to all floorplanning representations proposed so far.

By dividing the packing area into routing tiles, we can give the budget of the buffer insertion. And the detail locating of the blocks in their rooms can be implemented for each iterations during the annealing process to favor the later buffer planning. The buffer insertion will affect the possible routes as well the congestion of the packing. The congestion estimation in this paper takes the buffer insertion into account. So we devise a buffer planning algorithm to allocate the buffer into tiles with congestion information considered. The buffer allocation problem is formulated into a net flow problem and the buffer allocation can be handled as an integral part in the floorplanning process. Since there is more freedom for floorplan optimization, the floorplanning algorithm integrated with buffer planning can result in better performance and chip area.

Previous works on buffer planning are mainly based on fixed die placement. It is necessary to reduce the complexity of computing the feasible buffer insertion sites to integrate the buffer planning with the floorplanning process. In this paper, we give an efficient buffer planning algorithm with linear complexity by computing all the feasible buffer insertion sites in a 2-step method. By partitioning all the dead spaces into blocks while doing the packing, the buffer allocation can be handled as an integral part in the floorplanning process. Our method is based on a simulated annealing approach which is divided into two phases: timing optimization phase and buffer insertion phase. Since there is more freedom for floorplan optimization, the floorplanning algorithm integrated with buffer planning can result in better time performance and chip area.

A deterministic algorithm for VLSI block placement was developed in this paper through human's accumulated experience in solving "packing" problem. Rectangle packing problem is just a simplified case of the polygon-shape stone plate packing problem that the ancient masons needed to face. Several "packing" principles derived from the so-called "less flexibility first" experience of the masons. A k-d tree data structure is used for manipulating the packed rectangles under the derived packing principles. Experiment results demonstrate that the algorithm is effective and promising in building block layout application.

In floorplanning of typical VLSI design, some modules are required to satisfy some placement constraints in the final packing. Boudary Constraint is one kind of those placement constraints to pack some modules along one of the four sides: on the left, on the right, at the bottom or at the top of the final floorplan. We implement the boundary constraint algorithm for general floorplan by extending the Corner Block List (CBL) - a new efficient topology representation for non-slicing floorplan. Our contribution is to find the necessary and sufficient characterization of the modules along the boundary represented by Corner Block List. So that we can check the boundary constraints by scanning the intermediate solutions in the linear time during the simulated annealing process and fix the corner block list in case the constraints are violated. The experiment results are demonstrated by several examples of MCNC benchmarks and the performance is remarkable.

The abutment constraint problem is one of the common constraints in practice to favor the transmission of data between blocks. Based on Corner Block List(CBL), a new algorithm to deal with abutment constraints is developed in this paper. We can obtain the abutment information by scanning the intermediate solutions represented by CBL in linear time during the simulated annealing process and fix the CBL in case the constraints are violated. Based on this algorithm, a new method to deal with L-shaped/T-shaped blocks is proposed. The shape flexibility of the soft blocks and the rotation and reflection of L-shaped/T-shaped blocks are exploited to obtain a tight packing. The experiment results are demonstrated by some benchmark data and the performance shows effectiveness of the proposed method.

A Non-Slicing floorplanning algorithm based on CBL[1], corner block list, was presented recently. It can represent non-slicing floorplans without empty rooms. In this paper, we propose an extended corner block list structure, ECBLl, to represent general non-slicing floorplans, which may include empty rooms. By setting l×[1..3], where l is the extending ratio, our algorithm can translate a topological floorplan to its corresponding placement in O(n) time, where n is the number of blocks. Also, based on the optimum solution theorem of bounded-sliceline grid in [2], we proved that the solution space of ECBLn contains the optimum block placement, which has the minimum area. Experimental results on MCNC benchmarks show promising performance with 7% improvement in wire length and 2% decrease in dead space over algorithms based on CBL. Meanwhile, compared with other algorithms, our algorithm can get better results with less runtime.

In this paper, a corner block list-a new efficient topological representation for non-slicing floorplan is proposed with applications to VLSI floorplan and building block placement. Given a corner block list, it takes only linear time to construct the floorplan. Unlike the O-tree structure, which determines the exact floorplan based on given block sizes, corner block list defines the floorplan independent of the block sizes. Thus, the structure is better suited for floorplan optimization with various size configurations of each block. Based on this new structure and the simulated annealing technique, an efficient floorplan algorithm is given. Soft blocks and the aspect ratio of the chip are taken into account in the simulated annealing process. The experimental results demonstrate the algorithm is quite promising.