Through-silicon via (TSV) assignment problem is one of the key design challenges of 3-D IC which is crucial to the wire length and signal delay. In this work we formulate the 3-D IC TSV assignment as an Integer Minimum Cost Multi Commodity (IMCMC) problem on a IMCMC network, and propose a multi-level algorithm. It coarsens the IMCMC network level by level, applies a rough flow assignment on each level of coarsened graph, and generates only promising edges to reduce the IMCMC network size. Benefiting from the multi-level structure, we propose a mixed single and multi commodity flow method improve the TSV assignment solution quality. Moreover, given a TSV assignment, we propose an extended layer by layer algorithm to further optimize the TSV assignment. The experimental results demonstrate that our multi-level with mixed single and multi commodity flow algorithm achieves not only smaller wire length but also shorter runtime compared to other existing works.

© 2016 IEEE. Due to the rise of utilization wall, a large portion of silicon chips become dark or dim silicon. A NoC-sprinting method is proposed to deal with this problem for instantaneous improvement and the key design constraint of these problems is thermal design power(TDP). In this work we propose a thermalaware Modified Insert After Remove Floorplanning(MD-IARFP) algorithm for NoC-sprinting. Wire length is taken into consideration while only thermal behavior is concerned in the previous work. A thermal model is constructed to evaluate temperature, using relationship between heat transfer and electrical phenomena. Simulated Annealing(SA) based MD-IARFP algorithm is applied to optimize the distribution of active cores. In terms of perturbation of SA, Modified Insert After Remove(MD-IAR) method gives an efficient generation of new floorplan which helps to reduce iterate number and lead to less CPU time. Effective as the experimental results show, our proposal provides better solution with lower temperature and significant decrease of wire length.

Data path interconnection on VLSI chips usually consumes a significant amount of both power and area. In this paper, we focus on the port assignment problem for binary commutative operators for interconnection complexity reduction. First, the port assignment problem is formulated on a constraint graph, and a practical method is proposed to find a valid and initial solution. For solution optimization, an elementary spanning-tree-transformation-based local search algorithm is proposed. To improve the efficiency of optimization, a matrix formulation, which meets the simplex tabuleau format, is proposed and thus the simplex method is adopted for optimization. Moreover, operation pivoting and successive pivoting are discussed for algorithm speedup. The experimental results show that on the randomly generated test cases, the matrix-based algorithm shows the highest solution optimality and is five times faster than the elementary transformation method. On the real high-level synthesis benchmarks, the matrix-based method reduced 14% interconnections, while the previous greedy algorithm reduced 8% on average.

Through-silicon via (TSV) assignment problem is one of the key design challenges of 3-D IC which is crucial to the wire length and signal delay. In this work we formulate the 3-D IC TSV assignment as an Integer Minimum Cost Multi Commodity (IMCMC) problem on a IMCMC network, and propose a multi-level algorithm. It coarsens the IMCMC network level by level, applies a rough flow assignment on each level of coarsened graph, and generates only promising edges to reduce the IMCMC network size. Benefiting from the multi-level structure, we propose a mixed single and multi commodity flow method improve the TSV assignment solution quality. Moreover, given a TSV assignment, we propose an extended layer by layer algorithm to further optimize the TSV assignment. The experimental results demonstrate that our multi-level with mixed single and multi commodity flow algorithm achieves not only smaller wire length but also shorter runtime compared to other existing works.

© 2016 IEEE. Smart home scheduling, one of the most powerful technologies for electric power control from demand side, has been attracting rapidly growing interests. In this paper smart home scheduling algorithms are proposed for a single user and for multiple users to reduce total monetary cost. For a single user a game theory based method is proposed where each home appliance is regarded as a player and scheduling for appliances is iteratively optimized. For multiple users mixed strategy is adopted instead of pure strategy to reduce congestions of appliances on the current cheapest time interval. Experimental results show that both the scheduling for a single user or multiple users outperform the latest existing work both in terms of total monetary cost and execution time.

The vast majority of foreground detection methods require heavy hardware optimization to process in real-time standard definition videos. Indeed, those methods process the whole frame for the detection but also for the background modelling part which makes them resource guzzlers (time, memory, etc.) unable to be applied to Ultra High Definition (UHD) videos. This paper presents a real-time background modelling method called Mixed Block Background Modelling (MBBM). It is a spatio-temporal approach which updates the background model by carefully selecting block by a linear and pseudo-random orders and update the corresponding model's block parts. The two block selection orders make sure that every block will be updated. For foreground detection purposes, the method is combined with a foreground detection designed for UHD videos such as the Adaptive Block-Propagative Background Subtraction method. Experimental results show that the proposed MBBM can process 50 min. of 4K UHD videos in less than 6 hours. while other methods are estimated to take from 8 days to more than 21 years. Compared to 10 state-of-the-art foreground detection methods, the proposed MBBM shows the best quality results with an average global quality score of 0.597 (1 being the maximum) on a dataset of 4K UHDTV sequences containing various situation like illumination variation. Finally, the processing time per pixel of the MBBM is the lowest of all compared methods with an average of 3.18x10(-8) s.

The vast majority of foreground detection methods require heavy hardware optimization to process in real-time standard definition videos. Indeed, those methods process the whole frame for the detection but also for the background modelling part which makes them resourceguzzlers (time, memory, etc.) unable to be applied to Ultra High Definition (UHD) videos. This paper presents a real-time background modelling method called Mixed Block Background Modelling (MBBM). It is a spatio-temporal approach which updates the background model by carefully selecting block by a linear and pseudo-random orders and update the corresponding model's block parts. The two block selection orders make sure that every block will be updated. For foreground detection purposes, the method is combined with a foreground detection designed for UHD videos such as the Adaptive Block-Propagative Background Subtraction method. Experimental results show that the proposed MBBM can process 50 min. of 4K UHD videos in less than 6 hours. while other methods are estimated to take from 8 days to more than 21 years. Compared to 10 stateof-the-art foreground detection methods, the proposed MBBM shows the best quality results with an average global quality score of 0.597 (1 being the maximum) on a dataset of 4K UHDTV sequences containing various situation like illumination variation. Finally, the processing time per pixel of the MBBM is the lowest of all compared methods with an average of 3.18×10-8 s.

Sample adaptive offset (SAO) is a newly introduced in-loop filtering component in H. 265/High Efficiency Video Coding (HEVC). While SAO contributes to a notable coding efficiency improvement, the estimation of SAO parameters dominates the complexity of in-loop filtering in HEVC encoding. This paper presents an efficient VLSI design for SAO estimation. Our design features a dual-clock architecture that processes statistics collection (SC) and parameter decision (PD), the two main functional blocks of SAO estimation, at high-and lowspeed clocks, respectively. Such a strategy reduces the overall area by 56% by addressing the heterogeneous data flows of SC and PD. To further improve the area and power efficiency, algorithm-architecture co-optimizations are applied, including a coarse range selection (CRS) and an accumulator bit width reduction (ABR). CRS shrinks the range of fine processed bands for the band offset estimation. ABR further reduces the area by narrowing the accumulators of SC. They together achieve another 25% area reduction. The proposed VLSI design is capable of processing 8k at 120-frames/s encoding. It occupies 51k logic gates, only one-third of the circuit area of the state-of-the-art implementations.

Ultrahigh definition television is becoming increasingly attractive and practical with the doubled compression performance delivered by High Efficiency Video Coding (H.265/HEVC). Meanwhile, implementation of real-time video codecs is challenged by not only the huge throughput and memory bandwidth requirements but also the increased complexity of new algorithms. For motion compensation (MC) that is a known bottleneck in video decoding, the enlarged and diversified prediction unit sizes impose notably higher difficulties in trading off area, power, and memory traffic. This paper presents a very large scale integration implementation of HEVC MC that supports 7680 x 4320@60 frames/s bidirectional prediction. The MC design incorporates a highly efficient cache realized by novel architecture optimizations including distance biased directing mapping, eight-bank memory structure, row-based miss information compression, and mask-based block conflict checking. As a result, the proposed design not only achieves 8x throughput enhancement but also improves hardware efficiency by at least 2.01 times, in comparison with prior arts.

8K ultra-HD is being promoted as the next-generation video specification. While the High Efficiency Video Coding (HEVC) standard greatly enhances the feasibility of 8K with a doubled compression ratio, its implementation is a challenge, owing to ultrahigh-throughput requirements and increased complexity per pixel. The latter comes from the new features of HEVC. At the system level, the most challenging of them is the enlarged and highly variable-size coding/prediction/transform units, which significantly increase the requirement for on-chip memory as pipeline buffers and the difficulty in maintaining pipeline utilization. This paper presents an HEVC decoder chip featuring a system pipeline that works at a nonunified and variable granularity. The pipeline saves on-chip memory with a novel block-in-block-out queue system and a parameter delivery network, while allowing overhead-free and fully pipelined operation of the processing components. With the system pipeline design combined with various component-level optimizations, the proposed decoder in 40 nm achieves a maximum throughput of 4 Gpixels/s or 8K 120 frames/s for the low-delay-P configuration of HEVC, 7.5-55 times faster than prior works. It supports 8K 60 frames/s for the low-delay and random-access configurations. In a normalized comparison, it also shows 3.1-3.6 times better area efficiency and 31%-55% superior energy efficiency.

Deep convolutional neural networks (CNN) have shown their good performances in many computer vision tasks. However, the high computational complexity of CNN involves a huge amount of data movements between the computational processor core and memory hierarchy which occupies the major of the power consumption. This paper presents Chain-NN, a novel energy-efficient 1D chain architecture for accelerating deep CNNs. Chain-NN consists of the dedicated dual-channel process engines (PE). In Chain-NN, convolutions are done by the 1D systolic primitives composed of a group of adjacent PEs. These systolic primitives, together with the proposed column-wise scan input pattern, can fully reuse input operand to reduce the memory bandwidth requirement for energy saving. Moreover, the 1D chain architecture allows the systolic primitives to be easily reconfigured according to specific CNN parameters with fewer design complexity. The synthesis and layout of Chain-NN is under TSMC 28nm process. It costs 3751k logic gates and 352KB on-chip memory. The results show a 576-PE Chain-NN can be scaled up to 700MHz. This achieves a peak throughput of 806.4GOPS with 567.5mW and is able to accelerate the five convolutional layers in AlexNet at a frame rate of 326.2fps. 1421.0GOPS/W power efficiency is at least 2.5 to 4.1x times better than the state-of-the-art works.

© 2016 IEEE.In this work we solve the 3D-IC TSV assignment which is formulated as an Integer Minimum Cost Multi Commodity (IMCMC) problem. We propose a multi-level algorithm including graph coarsening and un-coarsening, to greatly reduce the IMCMC problem size; benefiting from it, we transform the IMCMC problem into a mixed single and multi commodity problem and partially solved it using min-cost flow method. Further, we extend the layer by layer method for TSV assignment optimization. The experimental results shows that the our proposal generates initial solutions with 2.8% wire length reduction compared to the existing work, and our extended layer by layer method achieves another 1.7% improvement with slight time overhead.

The exponential increase in leakage power and the substantial power-saving opportunities provided by scheduling have made dual-threshold voltage (dual-V-th) an attractive choice for low-leakage-power designs. In this paper, we work under the assumption that functional units (FUs) are allocated after scheduling, and fully explore the solution space of scheduling with dual-V-th operations to optimize the leakage power of the FUs. First, a binding conflict graph (BCG)-based scheduling method is presented to minimize the number of FUs. Second, the BCG-based method is extended to allow scheduling with dual-V-th operation targeting the minimization of leakage power. In timing-constrained scheduling, each operation in the data flow is initialized with low-V-th. Then, starting from an operation schedule with the timing constraint satisfied, we scale the sets of low-V-th operations in the off-critical paths with high-V-th so as to reduce the number of low-V-th FUs without increasing the total delay. Finally, a scheduling method for minimizing the leakage power under both timing and resource constraints is presented. The results of benchmark tests show that the proposed algorithms can reduce the leakage power reported in previous works by 10.2% while maintaining high circuit performance.

© 2015 IEEE.Interconnect reduction is one of the key issues in high-level synthesis. In this paper, we propose a primal-dual based method to solve the functional unit (FU) and register binding simultaneously while minimizing the global interconnection. Specifically, the binding problem is formulated as a min-cost network flow based on splitting weighted and order compatibility graphs (SWOCGs). The interconnect sharing among registers and FUs are maximized by binding the the operations or variables on the same path to the same FUs or registers according to the flow. Experimental results show that, compared with the previous greedy method [7], our proposed algorithm achieves an average 4.8% further reduction in global interconnection for a suite of benchmarks.

© 2015 IEEE.This paper proposes a simultaneous scheduling and binding approach for resource and interconnect reduction in high-level synthesis. The scheme incorporates the operation scheduling into functional unit (FU) and register binding, targeting the reduction of both resource and interconnect reduction. A simplified weighted and ordered compatibility graph (SWOCG) based binding algorithm is also proposed and runs tens of times faster than the WOCG based binding algorithm. The experimental results show that our proposal achieves 4% to 15% reduction in resource usage and interconnect reduction, and also runs 5X faster compared to previous works.

© 2016 IEEE.8K Ultra HD is being promoted as the next-generation digital video format. From a communication channel perspective, the latest high-efficiency video coding standard (H.265/HEVC) greatly enhances the feasibility of 8K by doubling the compression ratio. Implementation of such codecs is a challenge, owing to ultra-high throughput requirements and increased complexity per pixel. The former corresponds to up to 10b/pixel, 7680×4320pixels/frame and 120fps - 80× larger than 1080p HD. The latter comes from the new features of HEVC relative to its predecessor H.264/AVC. The most challenging of them is the enlarged and highly variable-size coding/prediction/transform units (CU/PU/TU), which significantly increase: 1) the requirement for on-chip memory as pipeline buffers, 2) the difficulty in maintianing pipeline utilization, and 3) the complexity of inverse transforms (IT). This paper presents an HEVC decoder chip supporting 8K Ultra HD, featuring a 16pixel/cycle true-variable-block-size system pipeline. The pipeline: 1) saves on-chip memory with a novel block-in-block-out (BIBO) queue system and a parameter delivery network, and 2) allows high design efficiency and utilizat

Network-on-Chip (NoC) is a promising solution for System-on-Chip (SoC) challenges. In this work, we present a Decompose and Cluster generation Refinement (DCR) algorithm to find minimum power consumption simultaneously. A two-stage method is proposed for decompose and cluster generation step to generate solutions with lower power. Refinement step explores optimal positions and adjusts clusters for selected solutions to find balanced point between power consumption and CPU time. Experimental results show that the proposed method outperforms the existing work.

In this paper, VLSI architecture design of unified motion vector (MV) and boundary strength (BS) parameter decoder (PDec) for 8K UHDTV HEVC decoder is presented. The adoption of new coding tools in PDec, such as Advanced Motion Vector Prediction (AMVP), increases the VLSI hardware realization overhead and memory bandwidth requirement, especially for 8K UHDTV application. We propose four techniques for these challenges. Firstly, this work unifies MV and BS parameter decoders for line buffer memory sharing. Secondly, to support high throughput, we propose the top-level CU-adaptive pipeline scheme by trading off between implementation complexity and performance. Thirdly, PDec process engine with optimizations is adopted for 43.2k area reduction. Finally, PU-based coding scheme is proposed for 30% DRAM bandwidth reduction. In 90 nm process, our design costs 93.3k logic gates with 23.0 kB line buffer. The proposed architecture can support real-time decoding for 7680x4320@60fps application at 249MHz in the worst case.

In this paper, VLSI architecture design of unified motion vector (MV) and boundary strength (BS) parameter decoder (PDec) for 8K UHDTV HEVC decoder is presented. The adoption of new coding tools in PDec, such as Advanced Motion Vector Prediction (AMVP), increases the VLSI hardware realization overhead and memory bandwidth requirement, especially for 8K UHDTV application. We propose four techniques for these challenges. Firstly, this work unifies MV and BS parameter decoders for line buffer memory sharing. Secondly, to support high throughput, we propose the top-level CU-adaptive pipeline scheme by trading off between implementation complexity and performance. Thirdly, PDec process engine with optimizations is adopted for 43.2k area reduction. Finally, PU-based coding scheme is proposed for 30% DRAM bandwidth reduction. In 90 nm process, our design costs 93.3k logic gates with 23.0 kB line buffer. The proposed architecture can support real-time decoding for 7680x4320@60fps application at 249 MHz in the worst case.

8K Ultra High Definition Television (UHDTV) requires extremely high throughput for video decoding based on H.265. In H.265, intra coding could significantly enhance video compression efficiency, at the expense of an increased computational complexity compared with H.264. For intra prediction of 8K UHDTV real-time H.265 decoding, the joint complexity and throughput issue is more difficult to solve. Therefore, based on the divide-and-conquer strategy, we propose a new VLSI architecture in this paper, including two techniques, in order to achieve 8K UHDTV H.265 intra prediction decoding. The first technique is the LUT based Reference Sample Fetching Scheme (LUT-RSFS), reducing the number of reference samples in the worst case from 99 to 13. It further reduces the circuit area and enhances the performance. The second one is the Hybrid Block Reordering and Data Forwarding (HBRDF), minimizing the idle time and eliminating the dependency between TUs by creating 3 Data Forwarding paths. It achieves the hardware utilization of 94%. Our design is synthesized using Synopsys Design Compiler in 40nm process technology. It achieves an operation frequency of 260MHz, with a gate count of 217.8K fo

Scheduling is a key problem in high level synthesis, as the scheduling results affect most of the important design metrics. In this paper, we propose a novel scheduling method to simultaneously optimize the leakage power of functional units with dual-Vth techniques and the number of registers under given timing and resource constraints. The mobility overlaps between operations are removed to eliminate data dependencies, and a simulated-annealing-based method is introduced to explore the mobility overlap removal solution space. Given the overlapfree mobilities, the resource usage and register usage in each control step can be accurately estimated. Meanwhile, operations are scheduled so as to optimize the leakage power of functional units with minimal number of registers. Then, a set of operations is iteratively selected, reassigned as low-Vth, and rescheduled until the resource constraints are all satisfied. Experimental results show the efficiency of the proposed algorithm.

In this paper, we address the problem of scheduling operations into control steps with a dual threshold voltage (dual-V-th) technique, under timing and resource constraints. We present a two-stage algorithm for leakage power optimization. In the threshold voltage (V-th) assignment stage, the proposed algorithm first initializes all the operations to high-V-th, and then it iteratively shortens the critical path delay by reassigning the set of operations covering all the critical paths to low-V-th, until the timing constraint is met. In the scheduling stage, a modified force-directed scheduling is implemented to schedule operations and to adjust threshold voltage assignments with a consideration of the resource constraints. To eliminate the potential resource constraint violations, the operations' threshold voltage adjustment problem is formulated as a "weighted interval scheduling" problem. The experimental results show that our proposed method performs better in both running time and leakage power reduction compared with MWIS [3].

In this paper, we address the problem of scheduling operations into control steps with a dual threshold voltage (dual-Vth) technique, under timing and resource constraints. We present a two-stage algorithm for leakage power optimization. In the threshold voltage (Vth) assignment stage, the proposed algorithm first initializes all the operations to high-V th, and then it iteratively shortens the critical path delay by reassigning the set of operations covering all the critical paths to low-V th until the timing constraint is met. In the scheduling stage, a modified force-directed scheduling is implemented to schedule operations and to adjust threshold voltage assignments with a consideration of the resource constraints. To eliminate the potential resource constraint violations, the operations' threshold voltage adjustment problem is formulated as a "weighted interval scheduling" problem. The experimental results show that our proposed method performs better in both running time and leakage power reduction compared with MWIS [3]. Copyright © 2014 The Institute of Electronics, Information and Communication Engineers.

Scheduling is a key problem in high level synthesis, as the scheduling results affect most of the important design metrics. In this paper, we propose a novel scheduling method to simultaneously optimize the leakage power of functional units with dual-Vth techniques and the number of registers under given timing and resource constraints. The mobility overlaps between operations are removed to eliminate data dependencies, and a simulated-annealing-based method is introduced to explore the mobility overlap removal solution space. Given the overlapfree mobilities, the resource usage and register usage in each control step can be accurately estimated. Meanwhile, operations are scheduled so as to optimize the leakage power of functional units with minimal number of registers. Then, a set of operations is iteratively selected, reassigned as low-Vth, and rescheduled until the resource constraints are all satisfied. Experimental results show the efficiency of the proposed algorithm. Copyright © 2014 The Institute of Electronics, Information and Communication Engineers.

Modem field programmable gate arrays (FPGAs) with heterogeneous resources are partially reconfigurable. Existing methods of reconfiguration-aware floorplanning have limitations with regard to homogeneous resources; they solve only a part of the reconfigurable problem. In this paper, first, a precise model for partially reconfigurable FPGAs is formulated, and then, a two-phase floorplanning approach is presented. In the proposed approach, resource distribution is taken into consideration at all times. In the first step, a resource-aware insertion-after-remove perturbation is devised on the basis of the multi-layer sequence pair constraint graphs, and resource-aware slack-based moves (RASBM) are made to satisfy resource requirements. In the second step, a resource-aware fixed-outline floorplanner is used, and RASBM are applied to pack the reconfigurable regions on the FPGAs. Experimental results show that the proposed approach is resource- and reconfiguration-aware, and facilitates stable floorplanning. In addition, it reduces the wire-length by 4-28% in the first step, and by 12% on average in the second step compared to the wire-length in previous approaches.

In this work, we present a Genetic Algorithm (GA) based method for pipeline scheduling optimization. The objective is to minimize the circuit area under both data initiation interval and pipeline latency constraints. In the initialization, the scheduler generates a series of solutions between As Soon As Possible (ASAP) and As Late As Possible (ALAP) interval. Afterwards a Linear Programming (LP) algorithm is applied for transforming unfeasible solutions to feasible solutions, which are input to GA for searching the optimization result. In the experiments, our proposed algorithm achieves an average of 29.74% area improvement by comparing with ASAP and ALAP methods. © 2013 IEEE.

In this work, we focus on the problem of latency-constrained scheduling with consideration of multiple voltage technologies in High-level synthesis. Without the resource concern, we propose an Integer Linear Programming (ILP) formulation and further relax it to a piecewise Linear Programming (LP) problem, which is optimally solved using the efficient piecewise-linear extended network simplex method(PLNSM). The experimental results showed 80X+ speedup compared to the general LP formulation. Considering the resource usage, we propose a two-stage heuristic Network Simplex Method based Power-efficient Multiple Voltage Scheduling(NPMVS) method. Firstly, the above relaxed LP formulation is modified to perform mobility allocation and delay assignment for the operations so as to minimize the power and the differences between the allocated operation mobilities and the predefined target mobilities. The modified formulation is solved using the PLNSM and iteratively performed to minimize power and resource density variation in control steps by gradually updating the predefined target mobilities. Secondly, with the allocated operation mobilities, we apply dependencyfree operation scheduling with the objective of minimizing the resource usage. Experimental results show that the proposed method can produce optimum solutions for all 6 benchmarks with 14 groups of data in a maximum time of 0.25 second.

Floorplanning has played a crucial role in the VLSI physical design process, while a lot of focus has been put on the representation methodologies for the floorplan optimization in the recent researches. In this work, we propose an efficient Padmissible representation, called random contour corner (RCC), for non-slicing floorplans. It depends on a two-section random code, representing the sequence and location of the blocks respectively. The objective is to improve both area and wire length. For the optimization procedure, we apply a simulated annealing (SA) algorithm. The method is quite simple and time efficient for implementation even on large-scale integration floorplans, and the run time complexity for the algorithm is O(nlogn). The experimental results show that our proposed method achieves promising results by comparing with some other representations (O-tree, B*-tree and TCG) on basic MCNC benchmark circuits.

In this work, we focus on the problem of latency-constrained scheduling with consideration of multiple voltage technologies in High-level synthesis. Without the resource concern, we propose an Integer Linear Programming (ILP) formulation and further relax it to a piecewise Linear Programming (LP) problem, which is optimally solved using the efficient piecewise-linear extended network simplex method(PLNSM). The experimental results showed 80X+ speedup compared to the general LP formulation. Considering the resource usage, we propose a two-stage heuristic Network Simplex Method based Power-efficient Multiple Voltage Scheduling(NPMVS) method. Firstly, the above relaxed LP formulation is modified to perform mobility allocation and delay assignment for the operations so as to minimize the power and the differences between the allocated operation mobilities and the predefined target mobilities. The modified formulation is solved using the PLNSM and iteratively performed to minimize power and resource density variation in control steps by gradually updating the predefined target mobilities. Secondly, with the allocated operation mobilities, we apply dependencyfree operation scheduling with the objective of minimizing the resource usage. Experimental results show that the proposed method can produce optimum solutions for all 6 benchmarks with 14 groups of data in a maximum time of 0.25 second.

Application-Specific Network-on-Chips (ASNoCs) have been proposed as a more promising solution than regular NoCs to the global communication challenges for particular applications in nanoscale Systemon- Chip (SoC) designs. In ASNoC Design, one of the key challenges is to generate the most suitable and power efficient NoC topology under the constraints of the application specification. In this work, we present a two-step floorplanning (TSF) algorithm, integrating topology synthesis into floorplanning phase, to automate the synthesis of such ASNoC topologies. At the first-step floorplanning, during the simulated annealing, we explore the optimal positions and clustering of cores and implement an incremental path allocation algorithm to predictively evaluate the power consumption of the generated NoC topology. At the second-step floorplanning, we explore the optimal positions of switches and network interfaces on the floorplan. A power and timing aware path allocation algorithm is also integrated into this step to determine the connectivity across different switches. Experimental results on a variety of benchmarks show that our algorithm can produce greatly improved solutions over the latest works. Copyright © 2013 The Institute of Electronics, Information and Communication Engineers.

In this paper, we address the problem of scheduling operations into control steps with dual threshold voltage (dual-Vth) technique under timing and resource constraints. We present a min-cut based algorithm for leakage power optimization. The proposed algorithm first initializes all the operations to high-Vth, then iteratively shorten the critical path delay by reassigning the set of operations covering all the critical paths to low-Vth until the timing constraints are met. A modified force-directed scheduling is implemented to schedule operations and to adjust threshold voltage assignments with consideration of resource constraints. During this procedure, mobility overlap graph (MOG) is constructed based on the mobilities of high-Vth operations. To guarantee the resource constraints are satisfied, operations' threshold voltages are adjusted by computing the min-cut of MOG. Experimental results show that our method performs better both in running time and leakage power reduction compared with MWIS-heuristic [3]. © 2013 IEEE.

Data path connection elements usually consume a significant amount of both power and area on a VLSI chip. In this paper, we focus on the port assignment problem for multiplexer (MUX) and interconnection optimization in High-Level Synthesis. Given a binding solution of operations and variables, the port assignment problem connects the registers to the operator ports through MUXes, to minimize the interconnections between MUXes and operator ports, as well as the MUX power and area. We formulate the port assignment problem for binary commutative operators as a vertex partition problem on a graph, and propose a local search based heuristic algorithm that iteratively performs the elementary spanning tree transformation on the graph to solve it. We also propose a method to estimate the result of the tree transformation and filter a considerable amount of bad solutions in advance which greatly accelerate the algorithm. The experimental results show that our proposed algorithm is able to achieve 48% execution time reduction and 8.3% power reduction compared with the previous work, and the power reduction can be obtained for 37% test benches. © 2013 IEEE.

Floorplanning has played a crucial role in the VLSI physical design process, while a lot of focus has been put on the representation methodologies for the floorplan optimization in the recent researches. In this work, we propose an efficient Padmissible representation, called random contour corner (RCC), for non-slicing floorplans. It depends on a two-section random code, representing the sequence and location of the blocks respectively. The objective is to improve both area and wire length. For the optimization procedure, we apply a simulated annealing (SA) algorithm. The method is quite simple and time efficient for implementation even on large-scale integration floorplans, and the run time complexity for the algorithm is O(nlogn). The experimental results show that our proposed method achieves promising results by comparing with some other representations (O-tree, B*-tree and TCG) on basic MCNC benchmark circuits.

As technology scaling, three-dimensional integrated circuits (3D-ICs) are emerging as a promising solution to address the challenges in system on chips (SoCs). Moreover, it's a necessity to design an efficient Network-on-Chip (NoC) topology for the interconnection issues of 3D SoCs. In this paper, we propose a topology-aware floorplanning method to determine the power-performance efficient 3D NoC topology. Unlike the previous works which explore the path allocation of the NoC components and Through-Silicon Vias (TSVs) assignment after the floorplan of cores is fixed, we integrate these steps (the clustering of cores + the placement of cores and switches + the path allocation + the TSV-aware topology evaluation) within the 3D floorplanning procedure. Experimental results show the effectiveness of our method. © 2013 IEEE.

In this paper, we address the problem of scheduling operations into control steps with dual threshold voltage (dual-Vth) technique under timing and resource constraints. Recently, some scheduling methods are proposed based on the mobility overlap removal, and it is a hard problem to remove the mobility overlap optimally. There might be no feasible solution with an improper mobility overlap removal. In this work, we implement the mobility overlap removal together with dual threshold voltage technique to minimize the total leakage power. A simulated-annealing based method is introduced to explore the optimal solution. For each mobility overlap removal, a probability-based method is proposed to schedule operations at appropriate control steps, and to assign them with proper threshold voltages. The experimental results show the effectiveness of the proposed method. © 2013 IEEE.

As technology advances, 3-D stacking of silicon layers that promises a solution to significantly alleviate the interconnect problem faced by current System-on-Chips (SoCs). In 3-D SoCs, judicious assignment of the pin locations and related vertical Through-Silicon Vias (TSVs) can improve the routing area and interconnection delay by reducing wire length and wire congestion. In this paper, we propose a significant algorithm to locate pin and TSV positions simultaneously for the two-pin net list in 3-D SoCs. Given a floorplan result, we formulate the pin assignment and TSV planning problem as a min-cost multi-commodity flow model and solve it based on lagrangian relaxation. By relaxing the capacity constraints in pin and TSV locations, we transform the min-cost multi-commodity flow problem to several min-cost max-flow problems that can be solved independently. A heuristic algorithm is also proposed to improve the result of lagrangian relaxation to guarantee the feasible solution. Experimental results show the effectiveness of the proposed algorithm. © 2013 IEEE.

Application-Specific Network-on-Chip (ASNoC) architecture is more promising than regular network-on-Chip(NoC) for some particular applications. In ASNoC Design, one of the key challenges is to generate the most suitable and power efficient NoC topology. In previous works, the placement of the cores and network components, and the path allocation are explored separately. However, the path allocation strongly depends on the placement of cores and network components. In this paper, we integrate these steps together through the floorplanning with the cluster reconstruction and path allocation (FCRPA). Several SoC benchmarks have been tested and the results showed improvements over the latest works. copy;2012 IEEE.

Network-on-Chips (NoCs) have been proposed as a solution for addressing the global communication challenges in System-on-Chip (SoC) architectures that are implemented in nanoscale technologies. For the use of NoCs to be feasible in today's industrial designs, a custom-tailored, power- efficient NoC topology that satisfies the application characteristics is required. In this work, we present a design methodology that automates the synthesis of such application-specific NoC topologies. We present a method which integrates partitioning into floorplanning phase to explore optimal clustering of cores during floorplanning with minimized link and switch power consumption. Based on the size of applications, we also present an Integer Linear Programming and a heuristic method to place switches and network interfaces on the floorplan. Then, a power and timing aware path allocation algorithm is carried out to determine the connectivity across different switches. We perform experiments on several SoC benchmarks and present a comparison with the latest work. For small applications, the NoC topologies synthesized by our method show large improvements in power consumption (27,54%), hop-count (4%) and running time (66%) on average. And for large applications, the synthesized topologies result in large power (31.77%), hop-count (29%) and running time (94.18%) on average.

Heterogeneous resources such as configurable logic blocks (CLBs), multiplier blocks (MULs) and RAM blocks (RAMs) where millions of logic gates are included have been added to field programmable gate arrays (FPGAs). The fixed-outline floorplanning used by the existing methods always has a big penalty item in the objective function to ensure all the modules are placed in the specified chip region, which maybe greatly degrade the wirelength. This paper presents a three-phase floorplanning method for heterogeneous FPGAs. First, a non-slicing free-outline floorplanning method is used to optimize the wirelength, however, in this phase, the satisfaction of resource requirements from functional modules might fail. Second, a min-cost-max-flow algorithm is used to tune the assignment of CLBs to functional modules, and assign contiguous regions to each module so that all the functional modules satisfy CLB requirements. Finally, the MULs and RAMs are allocated to modules by a network flow model. CLBs hold the maximum quantity among all the resources. Therefore, making a high utilization of them means an enhancement of the FPGA densities. The proposed method can improve the utilization of CLBs, hence, much larger circuits could be mapped to the same FPGA chip. The results show that about 7-85% wirelength reduction is obtained, and CLB utilization is improved by about 25%. Copyright © 2012 The Institute of Electronics, Information and Communication Engineers.

In this paper, we propose a method of floorplanning with voltage island generation for system-on-chips (SoC) designs, which is deeply coupled with voltage island partitioning and voltage assignment, and has a good scalability. Floorplans with voltage islands are represented using nested Sequence Pairs, where the cores involved in the same voltage island consecutively appear in the sequences. Starting from a randomly generated initial floorplan, where each non chip-level core occupies an individual voltage island, we iteratively improve the solution by removing a core from the floorplan, then, inserting back the core by trying all the possible O(n 2) block positions, which are defined as the combinations of insertion points and voltage islands. An almost linear algorithm is devised to roughly but quickly filter many worse block positions, in each iteration, considering fixed-outline constraints, wirelength, power, power/ground routing resources, and level shifters. Compared with the latest work, the proposed method shows 9.74% and 21.04% improvements respectively on the wirelength and power when all the blocks are hard. When soft blocks are involved, the proposed method shows 12.38% wirelength reduction and 3.10% more power saving with a penalty of 7.5% whitespace. Moreover, more than 20X speedups can be obtained for the large test cases. © 2012 ACM.

Flip-chip package provides the highest chip density because I/O buffers in it could be placed anywhere inside a chip. The assignment of bump pads, I/O buffers and I/O pins will affect the satisfaction of timing requirement inside die core. In this paper, we proposed an effective three-step hierarchical approach to satisfy the timing-constrained I/O buffer placement in an area-I/O flip-chip design, meanwhile, wirelength could be optimized. First of all, I/O buffers are inserted to the floorplan plane greedily, and then, the wirelength between I/O buffers and I/O pins are optimized by a fixed-outline floorplanning algorithm. Secondly, a network flow model is conducted, and a min-cost-max-flow algorithm is used to assign I/O pins, I/O buffers and bump pads. Finally, the timing constraints are translated to length constraints, the results that satisfy timing constraints are selected. The experimental results show that, under the given timing constraints, higher timing-constrained satisfaction ratio (TCSR) is obtained, and the reduction of total wirelength is 14% on average.

Flip-chip package provides the highest chip density because I/O buffers in it could be placed anywhere inside a chip. The assignment of bump pads, I/O buffers and I/O pins will affect the satisfaction of timing requirement inside die core. In this paper, we proposed an effective three-step hierarchical approach to satisfy the timing-constrained I/O buffer placement in an area-I/O flip-chip design, meanwhile, wirelength could be optimized. First of all, I/O buffers are inserted to the floorplan plane greedily, and then, the wirelength between I/O buffers and I/O pins are optimized by a fixed-outline floorplanning algorithm. Secondly, a network flow model is conducted, and a min-cost-max-flow algorithm is used to assign I/O pins, I/O buffers and bump pads. Finally, the timing constraints are translated to length constraints, the results that satisfy timing constraints are selected. The experimental results show that, under the given timing constraints, higher timing-constrained satisfaction ratio (TCSR) is obtained, and the reduction of total wirelength is 14% on average.

As technology advances, 3-D stacking of silicon layers is emerging as a promising approach to address the integration challenges faced by current System-on-Chips (SoCs). Designing efficient Network-on-Chips (NoCs) is necessary to handle the 3-D interconnect complexity. In this paper, we present a four-stage synthesis approach to determine the power-performance efficient 3-D NoC topology for the application. First, we propose an algorithm to explore optimal clustering of cores during 3-D floorplanning. Then, an Integer Linear Programming (ILP) algorithm is proposed to place switches and network interfaces on the 3-D floorplan. Thirdly, a power and timing aware path allocation algorithm is carried out to determine the connectivity across different switches. Last, a min-cost max-flow based algorithm is proposed for Through-Silicon Via (TSV) assignment to minimize the link power consumption. Experimental results show the effectiveness of the proposed algorithm.

Network-on-Chips (NoCs) have emerged as a paradigm for designing scalable communication architecture for System-on-Chips (SoCs). In NoC, one of the key challenges is to design the most power-performance efficient NoC topology that satisfies the application characteristics. In this paper, we present a three-stage synthesis approach to solve this problem. First, we propose an algorithm [floorplanning integrated with cluster generation (FCG)] to explore optimal clustering of cores during floorplanning with minimized link and switch power consumption. Then, based on the size of applications, an Integer Linear Programming (ILP) and a heuristic method (H) are also proposed to place switches and network interfaces on the floorplan. Finally, a power and timing aware path allocation algorithm (PA) is carried out to determine the connectivity across different switches. Experimental results show that, for small applications, the NoC topology synthesized by FIP (FCG+ILP+PA) method can save 27.54% of power, 4% of hop-count and 66% of running time on average. And for large applications, FHP (FCG+H+PA) synthesis method can even save 31.77% of power, 29% of hop-count and 94.18% of running time on average.

1 As technology advances, 3-D stacking of silicon layers is emerging as a promising approach to address the integration challenges faced by current System-on-Chips (SoCs). Designing efficient Network-on-Chips (NoCs) is necessary to handle the 3-D interconnect complexity. In this paper, we present a four-stage synthesis approach to determine the power-performance efficient 3-D NoC topology for the application. First, we propose an algorithm to explore optimal clustering of cores during 3-D floorplanning. Then, an Integer Linear Programming (ILP) algorithm is proposed to place switches and network interfaces on the 3-D floorplan. Thirdly, a power and timing aware path allocation algorithm is carried out to determine the connectivity across different switches. Last, a min-cost max-flow based algorithm is proposed for Through-Silicon Via (TSV) assignment to minimize the link power consumption. Experimental results show the effectiveness of the proposed algorithm. © 2011 IEEE.

In the High-Level Synthesis (HLS), the scheduling is a key problem. Recently, the max-flow scheduling method is proposed for resource-constrained scheduling based on the mobility overlap removal. In the max-flow scheduling method, it is a hard problem how to remove the overlaps optimally. With an improper mobility overlap removal, there might be no feasible solutions with resource constraints. In this work, the mobility overlap removal-based method is extended to deal with timing-constrained scheduling problem, where the timing constraint is given as an input and the resource usage should be minimized. A simulated-annealing based method is used to explore the optimal mobility overlap removal. And, given the overlap-free mobilities, a convex-cost flow based algorithm is proposed to schedule single-cycle operations optimally. At the same time, greedy algorithms are devised to schedule multi-cycle operations. The experimental results show the effectiveness of the proposed method. © 2011 IEEE.

The occurrence of via defects Increases due to the shrinking size in integrated circuit manufacturing Redundant via insertion is an effective and recommended method to reduce the yield loss caused by via failures In this paper we introduce the redundant via allocation problem for layer partition based redundant via insertion methods [1] and solve it using the genetic algorithm At the same time we use a convex cost flow model to equilibrate the via density which is good for the via density rules The results of layer partition based model depend on the partition and processing order of metal layers Furthermore even we try all of partitions and processing orders we might miss the optimal solutions By introducing the redundant via allocation problem on partitioning boundaries we can avoid the sub optimality of the original layer partition based method The experimental results show that the proposed method got 12 more redundant vias inserted on average and the via density balance can be greatly Improved

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. (C) 2010 Elsevier B.V. All rights reserved.

As technology advances, 3-D ICs can significantly alleviate the interconnect problem coming with the decreasing of feature size and are promising for heterogeneous integration. In 3-D ICs, one of the key challenges is the vertical technology, using through-silicon via (TSV) for different device layers connection. In this paper, by noticing the TSV assignment comes under the influence of the whitespace distribution in a given 3-D floorplan, we proposed an algorithm called whitespace insertion (WSI) based on the floorplan-representation Sequence Pair to make the whitespace distribution in the given floorplan more reasonable for TSV insertion. When given 3-D circuit placement or floorplan results, we also proposed a minimum spanning tree based algorithm for TSV assignment to minimize the total wire length, assuming each net may have at most one TSV on each device layer. Experimental results show that, in the given 3-D floorplans there is a huge gap about 45.54% of the wire length increase between the ideal and the practice. And based on our method, the total wire length can be reduced by 13% on average without changing the chip area.

As technology advances, 3-D ICs can significantly alleviate the interconnect problem coming with the decreasing of feature size and are promising for heterogeneous integration. In 3-D ICs, one of the key challenges is the vertical technology, using through-silicon via (TSV) for different device layers connection. In this paper, by noticing the TSV assignment comes under the influence of the whitespace distribution in a given 3-D floorplan, we proposed an algorithm called whitespace insertion (WSI) based on the floorplan-representation Sequence Pair to make the whitespace distribution in the given floorplan more reasonable for TSV insertion. When given 3-D circuit placement or floorplan results, we also proposed a minimum spanning tree based algorithm for TSV assignment to minimize the total wire length, assuming each net may have at most one TSV on each device layer. Experimental results show that, in the given 3-D floorplans there is a huge gap about 45.54% of the wire length increase between the ideal and the practice. And based on our method, the total wire length can be reduced by 13% on average without changing the chip area.

The occurrence of via defects increases due to the shrinking size in integrated circuit manufacturing. Double-via insertion is an effective and recommended method for improving chip yield and reliability and reducing the yield loss caused by via failures. In this paper we present a genetic algorithm based method to do the double-via insertion for layouts with grid-less or grid-based routing. Design rule violation between redundant via can be represented by a conflict graph whose vertices are redundant vias and edges represent design rule violations. We propose a genetic algorithm based method exploring the optimal removal of some redundant vias to get a conflict-free redundant via set for double via insertion. To reduce the problem size, we will first merge into one vertex (one redundant via) all the connected components that are cliques of the conflict graph. Experiment results show that the effectiveness of the proposed method. ©2010 IEEE.

The technique of multiple supply voltages and dynamic frequency has been explored as a possible energy-efficient strategy in CMOS circuits. In this paper, we consider the technique in the scheduling process which is the keys of high level synthesis. Given a schedule, a novel method is presented for the frequency assignment. The objective is to decrease the energy consumption as much as possible without violating the timing constraints. Initially, an approach based on the convex cost integer network flow is proposed to generate a feasible initial frequency assignment solution. Secondly, a branch and bound method is used to improve the initial solution. Finally, due to the frequency assignment result, we perform the assignment of voltage to each function operation in the control steps. The experimental results show the effectiveness of the proposed method. It is observed that using three supply voltage levels (5V; 3.3V; 2.4V), an average energy savings of 25% to 40% (with the time constraint of 1.5 to 2.0 times the critical path) is obtained as compared to using a single-frequency clocking scheme with a single supply voltage.

Scaling frequency and voltage in a coordinated manner is a promising way to reduce energy and power. we explore the use of dynamic frequency clocking within the datapath and datapath scheduling algorithms that can be incorporated into a datapath synthesis tool. Given a schedule, we propose a practical optimal frequency assignment algorithm based on dynamic programming. The algorithm run very fast in practice. Though the algorithm theoretically run in a pseudo polynomial time O(ncTex2), nc is the number of control steps and Tex is the difference between the timing constraint and the critical path delay. ©2010 IEEE.

The technique of multiple supply voltages and dynamic frequency has been explored as a possible energy-efficient strategy in CMOS circuits. In this paper, we consider the technique in the scheduling process which is the keys of high level synthesis. Given a schedule, a novel method is presented for the frequency assignment. The objective is to decrease the energy consumption as much as possible without violating the timing constraints. Initially, an approach based on the convex cost integer network flow is proposed to generate a feasible initial frequency assignment solution. Secondly, a branch and bound method is used to improve the initial solution. Finally, due to the frequency assignment result, we perform the assignment of voltage to each function operation in the control steps. The experimental results show the effectiveness of the proposed method. It is observed that using three supply voltage levels (5V; 3.3V; 2.4V), an average energy savings of 25% to 40% (with the time constraint of 1.5 to 2.0 times the critical path) is obtained as compared to using a single-frequency clocking scheme with a single supply voltage.

Three-dimensional integrated circuits (3-D ICs), i.e., stacked dies, can alleviate the interconnect problem coining with the decreasing feature size and increasing integration density, and promise a solution to heterogenous integration. The vertical connection, which is generally implemented by the through-the-si I icon via, is a key technology for 3-D ICs. In this paper, given 3-D circuit placement or floorplan results with white space reserved between blocks for inter-layer interconnections, we proposed methods for assigning inter-layer signal via locations. Introducing a grid structure on the chip, the inter-layer via assignment of two-layer chips can be optimally solved by a convex-cost max-flow formulation with signal via congestion optimized. As for 3-D ICs with three or more layers, the inter-layer signal via assignment is modeled as an integral min-cost multi-commodity flow problem, which is solved by a heuristic method based on the lagrangian relaxation. Relaxing the capacity constraints in the grids, we transfer the min-cost multi-commodity flow problem to a sequence of lagrangian sub-problems, which are solved by finding a sequence of shortest paths. The complexity of solving a lagrangian sub-problem is O(n(nt)n(g)(2)), where n(nt) is the number of nets and n(g) is the number of grids on one chip layer. The experimental results demonstrated the effectiveness of the method.

Scheduling, an important step in high-level synthesis, is essentially a searching process in the solution space. Due to the vastness of the solution space and the complexity of the imposed constraints, it is usually difficult to explore the solution space efficiently. In this paper, we present a random walk based perturbation method to explore the schedule space. The method works by limiting the search within a specifically defined sub-solution space (SSS), where schedules in the SSS can be found in polynomial time. Then, the SSS is repeatedly perturbed by using an N-dimension random walk so that better schedules can be searched in the new SSS. To improve the search efficiency, a guided perturbation strategy is presented that leads the random walk toward promising directions. Experiments on well-known benchmarks show that by controlling the number of perturbations, our method conveniently makes tradeoff between schedule quality and runtime. In reasonable runtime, the proposed method finds schedules of better quality than existing methods. © 2009 Information Processing Society of Japan.

In this paper, we propose a generalized V-shaped multilevel floorplanning method with consideration of fixed-outline constraint. The Sequence Pair is used as the floorplan representation. The proposed multilevel method (ML-IARFP) adopts a two-stage structure: top-down partitioning and floorplanning followed by bottom-up merging and refinement. At the first stage, we recursively partition and floorplan the circuits until there are limited number blocks in each sub-circuit. Since we use a multi-partitioning instead of bi-partitioning, general non-slicing floorplan structures are explored in each level, which potentially lead to more effective exploration of the solution space. At the second stage, using a multilevel sequence pair structure, we recursively merge the sub-circuits into bigger circuits and do the refinement. Compared with IMF, Capo 10.2 and IARFP, ML-IARFP obtained the best results under fixed-outline constraints, and compared with IARFP, it achieved 9% wirelength reduction on average and showed a better scalability.

In this paper a heuristic method for module sizing is proposed as a post-processing of the fixed-outline floorplanning. The heuristic method is based on horizontal and vertical slacks of blocks in the floorplan. By evaluating the distances of each block to the chip boundaries, x-slack and y-slack can be calculated. On the one hand, the heuristic focuses on the blocks has non-zero x-slack or non-zero y-slack but not both. These blocks will be first sorted by the amount of x/y-slack. The block having the most slack will be selected and reshaped, it has a potential to reduce the fixed-outline violation. On the other hand, the heuristic makes Use of a marked flag for each block. After reshaping the block, the marked flag of the block will be set to 1. The slack of all the blocks will be recomputed and the focused blocks with marked flag 0 are reselected and sorted. If the set of focused blocks with marked flag 0 is empty, the marked flag of all the blocks will be reset to 0 and repeat the previous steps. If the fixed-outline constraint is not satisfied, we will repeat the procedure with defined maximum iteration number Experimental results show that, the proposed heuristic could efficient achieve highly success rate without sacrificing much wire-length.

As VLSI design complexity continues to increase, the yield loss due to via failure becomes more and more significant Redundant via insertion is highly recommended for improving chip yield and reliability. In this paper, we study the redundant via insertion problem in a post-routing stage, where a single via can have at most one redundant via inserted next to it. The goal is to insert as many redundant vias as possible and, at the same time, try to equilibrate the via density, which is good for the via density rules. We propose a convex-cost flow based approach to solve the problem within up to three routing layers. The experimental results show that, the proposed method can produce optimal solutions on defined density grid structure with maximum redundant via insertion, and achieve an at least 32.61% improvement of via density equalization(1).

Since many embedded applications involve intensive mathematic operations, floating-point arithmetic units (FPU) have paramount importance in embedded systems. However, previous implementations of FPU either require much manual work or only support special functions (e.g. reciprocal, square root, logarithm, etc.). In this paper, we present an automatic method to synthesize general FPU by aligned partition. Based on the novel partition algorithm and the concept of grouping floating-point numbers into zones, our method supports general functions of wide, irreducible domain. The synthesized FPU achieves smaller area, higher frequency, and greater accuracy. Experimental results show that our method achieves 1) on average 90% smaller and 50% faster indexer than the conventional automatic method
2) on the hyperbolic functions, 20 k times smaller error rate and 50% use of LUTs and flip-flops than the conventional manual design. © 2008 Information Processing Society of Japan.

Scheduling, an essential step in high-level synthesis, is an intractable process. Traditional heuristic scheduling methods usually search schedules directly in the entire solution space. In this paper, we propose the idea of searching within an intermediate solution space (ISS). We put forward a max-flow scheduling method that heuristically prunes the solution space into a specific ISS and finds the optimum of ISS in polynomial time. The proposed scheduling algorithm has some unique features, such as the correction of previous scheduling decisions in a later stage, the simultaneous scheduling of all the operations, and the optimization of more complicated objectives. Aided by the max-flow scheduling method, we implement the optimization of the IC power-ground integrity problem at the behavior level conveniently. Experiments on well-known benchmarks show that without requiring additional resources or prolonging schedule latency, the proposed scheduling method can find a schedule that draws current more stably from a supply, which mitigates the voltage fluctuation in the on-chip power distribution network.

In this paper, we propose a stable fixed-outline floorplanning method(IARFP). An elaborated method for perturbing solutions, Insertion after Remove(IAR), is devised for the simulated annealing. The IAR operation uses the technique of enumerating positions in Sequence Pair and greatly accelerates the searching. Moreover, based on the analysis of diverse objective functions used in the existing researches, we suggest a new objective function, which is still effective when combined with other objectives, for the fixed-outline floorplanning. Compared with the previous fixed-outline floorplanners, the proposed method is effective and efficient. Experiments showed that the proposed fixed-outline floorplanner achieved 100% success rate efficiently when optimizing area and wire-length simultaneously, while getting much smaller wirelength. On the other hand, we validated once more by experiments that aspect ratio close to one is beneficial to wire-length.

Let G be any directed graph and S be nonnegative and non-decreasing integer sequence(s). The prescribed degree sequence problem is a problem to determine whether there is a graph G with S as the prescribed sequence(s) of outdegrees of the vertices. Let G be the property satisfying the following (1) and (2):
(1) G has two disjoint vertex sets A and B.
(2) For every vertex pair u, v epsilon G (u not equal v), G satisfies
[GRAPHICS]
where uv (vu, respectively) means a directed edges from u to v (from v to u).
Then G is called an (r(11),r(12),r(22))-tournament ("tournament", for short). When G is a "tournament," the prescribed degree sequence problem is called the score sequence pair problem of a "tournament", and S is called a score sequence pair of a "tournament "(or S is realizable) if the answer is "yes."
We proposed the characterizations of a "tournament" and an algorithm for determining in linear time whether a pair of two integer sequences is realizable or not [5]. In this paper, we propose an algorithm for constructing a "tournament" from such a score sequence pair.

This paper presents a novel power estimation method for large and complex LSIs. The proposed method is based on simulation and is used for analyzing the ways in chip-scale gate-level circuits including processors and memory are affected by gated-clock power reduction and the voltage drop due to electrical resistance. The chip-scale power estimation based on simulation patterns generally takes enormous time. In order to reduce the time to obtain accurate estimation results based on simulation patterns, we introduce three approaches: "partitioning of target LSIs and simulation pattern," "memory modeling," and "processor modeling." After placing and routing, the target LSIs are partitioned into hierarchical blocks, memory, and processors. The power consumption of each hierarchical block is calculated by using the partitioned patterns generated from chip-scale simulation patterns. The power consumption of the processor and memory blocks is estimated by a method considering the static power consumption and the rate of LSI activity ratio. Experimental results for a commercial 0.18 mu m-technology media processing chip show that the proposed method is 23 times faster than the conventional method without partitioning and that both the results are almost the same.

This paper describes a novel engineering change order (ECO) design method for large-scale, high performance LSIs, based on a patchwork-like partitioning technique. In conventional design methods, even when only small changes are made to the design after the placement and routing process, a whole re-layout must be done, and this is very time consuming. Using the proposed method, we can partition the design into several parts after logic synthesis. When design changes occur in HDL, only the parts related to the changes need to be redesigned. The netlist for the changed design remains almost the same as the original, except for the small changed parts. For partitioning, we used multiple-fan-out-points as partition borders. An experimental evaluation of our method showed that when a small change was made in the RTL description, the revised circuit part had only about 87 gates on average. This greatly reduces the re-layout time required for implementing an ECO. In actual commercial designs in which several design changes are required, it takes only one day to redesign.

This paper presents a novel power estimation method for large and complex LSIs. The proposed method is based on simulation and is used for analyzing the ways in chip-scale gate-level circuits including processors and memory are affected by gated-clock power reduction and the voltage drop due to electrical resistance (IR-Drop). The chip-scale power estimation based on simulation patterns generally takes a long time. To obtain accurate estimation results based on simulation patterns in a short time, we introduce three approaches: (1) hierarchical circuit and simulation pattern partitioning, (2) memory modeling, and (3) the processor modeling. First, the target LSI design after placing and routing is partitioned into hierarchical blocks, memory, and processors. The power consumption of each hierarchical block is calculated by using the partitioned patterns generated from chip-scale simulation patterns. The power consumption of the processor and memory blocks is estimated by a method considering the static power consumption and the rate of LSI activity. The experimental results for the commercial 0.18um-technology digital TV chip show that our proposed method can get almost the same results obtained by the conventional method without partitioning and can do it 25 times faster.

This paper describes a new hardware/software co-verification method for System-On-a-Chip, based on the integration of a C/C++ simulator and an inexpensive FPGA emulator. Communication between the simulator and emulator occurs via a flexible interface based on shared communication registers. This method enables easy debugging, rich portability, and high verification speed, at a low cost. We describe the application of this environment to the verification of three different complex commercial SoCs, supporting concurrent hardware and embedded software development. In these projects, our verification methodology was used to perform complete system verification at 0.2-1.1 MHz, while supporting full graphical interface functions such as "waveform" or "signal dump" viewers, and debugging functions such as "step" or "break".

Latch circuits have advantage for timing and are widely used for high-speed custom circuits. However, ASIC design flows are based on the circuits with flip-flops. Then, ASIC designers don't use latches. This paper describes a new timing optimization algorithm for ASIC by replacing flip-flops to latches without changing the functionality of the circuits. After latch replacement, restricted retiming called fixed-phase retiming is carried out for timing optimization by minimizing the impact of clock skew and jitter. The experimental results show that 17% delay improvement of the benchmark circuits is achieved by proposed algorithms.

We present an ordered tree (O tree) structure to represent nonslicing floorplans, The O tree uses only n(2 + inverted right perpendicular lg n inverted left perpendicular) bits for a floorplan of n, rectangular blocks. We define an admissible placement as a compacted placement in both a: and y directions. For each admissible placement, we can find an O-tree representation. We show that the number of possible O-tree combinations is O(n!2(2n-2)/n(1.5)). This is very concise compared to a sequence pair representation that has O((n!)(2)) combinations. The approximate ratio of sequence pair and O-tree combinations is O(n(2)(n/4e)(n)), The complexity of O tree is even smaller than a binary tree structure for slicing floorplan that has O(n!2(5n-3)/n(1.5)) combinations, Given an O tree, it takes only linear time to construct the placement and its constraint graph, We have developed a deterministic floorplanning algorithm utilizing the structure of O tree. Empirical results on MCNC (www.mcnc.org) benchmarks show promising performance with average 16% improvement in wire length and 1% less dead space over previous central processing unit (CPU) intensive cluster refinement method.

This paper presents a novel implication-based method for logic minimization in large-scale, multi-level networks. It significantly reduces network size through repeated addition and removal of redundant subnetworks, utilizing multisignal implications and relationships among these implications. These are handled on a transitive implication graph, proposed ill this paper, which offers the practical use of implications for logic minimization. The proposed method holds great promise for the achievement of an interactive logic design environment for large-scale networks.

This paper presents a new design method for custom LSI layouts. This method is based on layout compaction with automatic jog (wiring bend) generation in the layout. A dense chip design can be realized by this technique. Experimental results show that the chip size designed by using the proposed layout method is only 1.2–1.4 times larger than that resulting from manual layouts. Therefore, this comkpaction-based custom LSI layout design method is very effective for achieving a minimal chip layout design. © 1987 by The Institute of Electrical and Electronics Engineers, Inc.

In the layout design of LSI chips, channel routing is one of the key problems. The problem is to route a specified net list between two rows of terminals across a two-layer channel. Nets are routed with horizontal segments on one layer and vertical segments on the other. Connections between two layers are made through via holes. Two new algorithms are proposed. These algorithms merge nets instead of assigning horizontal tracks to individual nets. The algorithms were coded in Fortran and implemented on a VAX 11/780 computer. Experimental results are quite encouraging. Both programs generated optimal solutions in 6 out of 8 cases, using examples in previously published papers. The computation times of the algorithms for a typical channel (300 terminals, 70 nets) are 1.0 and 2.1 s, respectively. © 1982 IEEE