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.

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.

Binary neural networks (BNNs), where both activations and weights are radically quantized to be {-1, +1}, can massively accelerate the run-time performance of convolution neural networks (CNNs) for edge devices, by computation complexity reduction and memory footprint saving. However, the non-differentiable binarizing function used in BNNs, makes the binarized models hard to be optimized, and introduces significant performance degradation than the full-precision models. Many previous works managed to correct the backward gradient of binarizing function with various improved versions of straight-through estimation (STE), or in a gradual approximate approach, but the gradient suppression problem was not analyzed and handled. Thus, we propose a novel gradient corrected approximation (GCA) method to match the discrepancy between binarizing function and backward gradient in a gradual and stable way. Our work has two primary contributions: The first is to approximate the backward gradient of binarizing function using a simple leaky-steep function with variable window size. The second is to correct the gradient approximation by standardizing the backward gradient propagated through binarizing function. Experiment results show that the proposed method outperforms the baseline by 1.5% Top-1 accuracy on ImageNet dataset without introducing extra computation cost.

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 test the smoothing heuristics for MCNC benchmarks, and 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.

Fully automatic reconstruction of 3D models from images is well-known to be a difficult problem. For many applications, a limited amount of human assistance is allowed and can greatly reduce the complexity of the 3D reconstruction problem. In this paper, we present an easy-to-use method for aligning a parameterized 3D CAD model to images taken from different views. The shape parameters of the 3D CAD model can be recovered accurately. Our work is composed of two parts. In the first part, we developed an interactive tool which allows the user to associate the features in the CAD model to the features in the 2D images. This interactive tool is designed to achieve efficiency and accuracy. In the second part, 3D information extracted from different stereo views are integrated together by using an optimization technique to obtain accurate shape parameters. Some experimental results have been shown to demonstrate the accuracy and usefulness of the recovered CAD model.

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

Three-dimensional integrated circuits (3-D ICs), i.e., stacked dies, can alleviate the interconnect problem coming 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-silicon 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(nntng2), where nnt is the number of nets and ng is the number of grids on one chip layer. The experimental results demonstrated the effectiveness of the method.

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 System-on-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.

Modern 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 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-Vth, and then it iteratively shortens the critical path delay by reassigning the set of operations covering all the critical paths to low-Vth 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].

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.

Dual-vdd has been proposed to optimize the power of circuits without violating the performance. In this paper, different from traditional methods which focus on making full use of slacks of non-critical gates, an efficient min-cut based voltage assignment algorithm concentrating on critical gates is proposed. And then this algorithm is integrated into a searching engine to auto-select rational voltages for dual-vdd system. Experimental results show that our search engine can always achieve good pair of dual-vdd, and our min-cut based algorithm outperformed previous works for voltage assignment both on power consumption and runtime.

Mathematical morphology is inheriently suitable for range image processing because it can deal with the shape of a function in a natural and intuitive way. In this paper, a new approach to the extraction of the corner-edge-surface structure from 3D range images is proposed. Morphological operations are utilized for segmenting range images into smooth surface regions and high-variation surface regions, where the high-variation surface regions are further segmented into regions of edge type and regions of corner type. A new 3D feature, HV-skeleton, can be extracted for each high-variation surface region. The HV-skeletons can be thought of as the skeletons of high-variation surface regions and are useful for feature matching. The 3D features extracted by our approach are invariant to 3D translations and rotations, and can be utilized for higher-level vision tasks such as registration and recognition. Experimental results show that the new 3D feature extraction method works well for both simple geometric objects and complex shaped objects such as human faces.

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 overlap-free 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.

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%.