Deep neural networks have demonstrated their great potential in recent years, exceeding the performance of human experts in a wide range of applications. Due to their large sizes, however, compression techniques such as weight quantization and pruning are usually applied before they can be accommodated on the edge. It is generally believed that quantization leads to performance degradation, and plenty of existing works have explored quantization strategies aiming at minimum accuracy loss. In this paper, we argue that quantization, which essentially imposes regularization on weight representations, can sometimes help to improve accuracy. We conduct comprehensive experiments on three widely used applications: fully connected network for biomedical image segmentation, convolutional neural network for image classification on ImageNet, and recurrent neural network for automatic speech recognition, and experimental results show that quantization can improve the accuracy by 1%, 1.95%, 4.23% on the three applications respectively with 3.5x-6.4x memory reduction.

The rapid development of Internet-of-Things is yielding a huge volume of time series data, the real-time mining of which becomes a major load for data centers. The computation bottleneck in time series data mining is distance function, which is the fundamental element of many high data mining tasks. Recently various software optimization and hardware acceleration techniques have been proposed to tackle the challenge. However, each of these techniques is only designed or optimized for a specific distance function. To address this problem, in this paper we propose MDA, a high-throughput reconfigurable memristor-based distance accelerator for real-time and energy-efficient data mining with time series in data centers. Common circuit structure is extracted for efficiency, and the circuit can be configured to any specific distance functions. Particularly, we adopt the emerging device memristor for the design of MDA. Comprehensive experiments are presented with public available datasets to evaluate the performance of the proposed MDA. Experimental results show that compared with existing works, MDA has achieved a speedup of 3.5×-376× on performance and an improvement of 1-3 orders of magnitude on energy efficiency with little accuracy loss.

With pervasive applications of medical imaging in health-care, biomedical image segmentation plays a central role in quantitative analysis, clinical diagnosis, and medical intervention. Since manual annotation suffers limited reproducibility, arduous efforts, and excessive time, automatic segmentation is desired to process increasingly larger scale histopathological data. Recently, deep neural networks (DNNs), particularly fully convolutional networks (FCNs), have been widely applied to biomedical image segmentation, attaining much improved performance. At the same time, quantization of DNNs has become an active research topic, which aims to represent weights with less memory (precision) to considerably reduce memory and computation requirements of DNNs while maintaining acceptable accuracy. In this paper, we apply quantization techniques to FCNs for accurate biomedical image segmentation. Unlike existing literatures on quantization which primarily targets memory and computation complexity reduction, we apply quantization as a method to reduce overfitting in FCNs for better accuracy. Specifically, we focus on a state-of-the-art segmentation framework, suggestive annotation [26], which judiciously extracts representative annotation samples from the original training dataset, obtaining an effective small-sized balanced training dataset. We develop two new quantization processes for this framework: (1) suggestive annotation with quantization for highly representative training samples, and (2) network training with quantization for high accuracy. Extensive experiments on the MICCAI Gland dataset show that both quantization processes can improve the segmentation performance, and our proposed method exceeds the current state-of-the-art performance by up to 1%. In addition, our method has a reduction of up to 6.4x on memory usage.

Cellular neural networks (CeNNs) have been widely adopted in image processing tasks. Recently, various hardware implementations of CeNNs have emerged in the literature, with Field Programmable Gate Array (FPGA) being one of the most popular choices due to its high flexibility and low time-to-market. However, CeNNs typically involve extensive computations in a recursive manner. As an example, to simply process an image of 1,920 × 1,080 pixels requires 4--8 Giga floating point multiplications (for 3 × 3 templates and 50–100 iterations), which needs to be done in a timely manner for real-time applications. To address this issue, in this article, we propose a compressed CeNN framework for efficient FPGA implementations. It involves various techniques, such as incremental quantization and early exit, which significantly reduces computation demands while maintaining an acceptable performance. Particularly, incremental quantization quantizes the numbers in CeNN templates to powers of two, so that complex and expensive multiplications can be converted to simple and cheap shift operations, which only require a minimum number of registers and logical elements (LEs). While a similar concept has been explored in hardware implementations of Convolutional Neural Networks (CNNs), CeNNs have completely different computation patterns, which require different quantization and implementation strategies. Experimental results on FPGAs show that incremental quantization and early exit can achieve a speedup of up to 7.8× and 8.3×, respectively, compared with the state-of-the-art implementations, while with almost no performance loss with four widely adopted applications. We also discover that different from CNNs, the optimal quantization strategies of CeNNs depend heavily on the applications. We hope that our work can serve as a pioneer in the hardware optimization of CeNNs.

The rapid development of Internet of Things is yielding a huge volume of time series data, the real-time mining of which becomes a major load for data centers. The computation bottleneck in time series mining is the distance measure, in which dynamic time warping (DTW) is one of the most widely used distance measures. Recently, various software optimization and hardware acceleration techniques have been proposed for DTW acceleration. However, the throughput and energy efficiency of DTW are still big concerns considering the ever-increasing volume of times series. In this paper, we propose a high-throughput and efficient memristor-based DTW architecture for real-time time series mining on data centers. Specifically, memristors have been adopted for both computation and configuration of the computing architecture. The computation flow in this architecture is fully presented in a continuous and asynchronous manner. To improve the computation efficiency, we propose an early lower bound algorithm by exploiting the predictability in the circuit characteristic. Experiments are performed with module evaluation and end-to-end evaluation including three popular applications: 1) similarity search; 2) classification; and 3) anomaly detection. Experimental results indicate that, compared to existing approaches, the speedup and energy efficiency improvement are 12x-43x and 51x-287x, respectively.

The rapid development of Internet-of-Things (IoT) is yielding a huge volume of time series data, the real-time mining of which becomes a major load for data centers. The computation bottleneck in time series data mining is the distance function, which has been tackled by various software optimization and hardware acceleration techniques recently. However, each of these techniques is only designed or optimized for a specific distance function. To address this problem, in this paper we propose an efficient and reconfigurable memristor-based distance accelerator for real-time and energy-efficient data mining with time series on data centers. Common circuit structure is extracted to save chip areas, and the circuit can be configured to any specific distance functions. Experimental results show that compared with existing works, our work has achieved a speedup of 3.5x-376x on performance and an improvement of 1-3 orders of magnitude on energy efficiency.

Multi-agent simulation (MAS) is a widely used paradigm for modeling and simulating real world complex system, ranging from ant colony foraging to online trading. The performance of existing MAS software, however, suffers when simulating massive-scale multi-agent systems on traditional serial processing processors. In this paper, we propose an FPGA-based framework for massive-scale grid-based MAS. Memory interleaving, parallel tasks partition, and computing pipeline are adopted to improve system throughput. A classical MAS benchmark, Conway's Game of Life, is used as a case study to illustrate how to map grid-based models to our MAS framework. We implemented it on a Xilinx Virtex-5 FPGA board and achieved a speedup of 290x with two million agents, compared to the C implementation.

SRAM-based Field Programmable Gate Arrays (FPGAs) are vulnerable to Single Event Upsets (SEUs). We show that a large portion (40%-60% for the circuits in our experiments) of the total used LUT configuration bits are don't care bits, and propose to decide the logic values of don't care bits such that soft errors are reduced. Our approaches are efficient and do not change LUT level placement and routing. Therefore, they are suitable for design closure. For the ten largest combinational MCNC benchmark circuits mapped for 6-LUTs, our approaches obtain 20% chip level Mean Time To Failure (MTTF) improvements, compared to the baseline mapped by Berkeley ABC mapper. They obtain 3× more chip level MTTF improvements and are 128× faster when compared to the existing best in-place IPD algorithm.

We present a fault-tolerant post-mapping resynthesis for FPGA-based designs that exploits the dual-output feature of modern FPGA architectures to improve the reliability of a mapped circuit against faults. Emerging FPGA architectures, such as 6-LUTs in Xilinx Virtex-5 and 8-input ALMs in Altera Stratix-III, have a secondary LUT output that allows access to non-occupied SRAM bits. We show that this architectural feature can be used to build redundancy for fault masking with limited area and performance overhead. Our algorithm improves reliability of a mapping by performing two basic operations: duplication (in which free configuration bits are used to duplicate a logic function whose value is obtained at the secondary output) and encoding (in which two copies of the same logic function are ANDed or ORed together in the fanout of the duplicated logic). The problem of fault tolerant post-mapping resynthesis is then formulated as the optimal duplication and encoding scheme that ensures the minimal circuit fault rate w.r.t. a stochastic single fault model. We present an ILP formulation of this problem and an efficient algorithm based on generalized network flow. On MCNC benchmarks, experimental results show that for combinational circuits the proposed approach improves mean-time-to-failure(MTTF) by 27% with 4% area overhead, and the proposed approach with explicit area redundancy improves MTTF by 113% with 36% area overhead, compared to the baseline mapping by ABC. This provides a viable fault tolerance solution for non-mission critical applications compared to TMR (triple modular redundancy) which has a 5x–6x area overhead.

Logic synthesis for soft error mitigation is increasingly important in a wide range of applications of FPGAs. We present R2, an algorithm for rewiring a post-layout LUT-based circuit that reduces the overall criticality of the circuit, where criticality is the fraction of primary inputs that lead to observable errors at the primary outputs if an single event upset inverts a configuration bit. Our algorithm explicitly optimizes the robustness of the interconnect, the dominant component of FPGAs. The key idea of R2 is to exploit Boolean flexibilities in the circuit implementation to replace wires with high criticality with those with lower criticality while preserving the circuit functionality. We estimate criticalities using a Monte Carlo fault simulation. We represent flexibilities using SPFDs (Set of Pairs of Functions to be Distinguished), and use criticality information to choose candidates for rewiring, assigning the maximum flexibility to high criticality wires. Compared to IPR, a recent robust logic optimization, our implementation increases MTTF (Mean Time to Failure) by 24%, showing for the first time, the advantages of exploiting Boolean flexibilities in optimizing for robustness. In addition, R2 achieves 5% and 2% more reduction on the number of wires and LUTs in an FPGA than that obtained by the existing rewiring algorithm for area minimization.

Reliability analysis for a logic circuit is one of the primary tasks in fault-tolerant logic synthesis. Given a fault model, it quantifies the impact of faults on the full-chip fault rate. We present RALF, an exact algorithm for calculating the reliability of a logic circuit. RALF is based on the compilation of a circuit to deterministic decomposable negation normal form (d-DNNF), a representation for Boolean formulas that can be more succinct than BDDs. Our algorithm can solve a large set of MCNC benchmark circuits within 5 minutes, enabling an optimality study of Monte Carlo simulation, a popular estimation method for reliability analysis, on real benchmark circuits. Our study shows that Monte Carlo simulation with a small set of random vectors generally has a high fidelity for the computation of full-chip fault rates and the criticality of single gates. While we focus on reliability analysis, RALF can also be used to efficiently locate random pattern resistant faults. This can be used to identify where methods other than random simulation should be used for accurate criticality calculations and where to enhance the testability of a circuit.

Boolean matching is one of the most important fundamental algorithms in FPGA synthesis and architecture evaluations. However, existing Boolean matchers for FPGAs, even with numerous improvements, are still not scalable to complex PLBs and large circuits. This paper aims to improve the efficiency of Boolean matching using lookup tables implemented by Bloom filters, which can store terabyte-lookup tables with a desktop PC. The key improvement is to efficiently prune a large set of non-implementable functions use the Bloom filter. Using the area-oriented re-synthesis as an application, the experiments on a broad selection of benchmark sets show that the re-synthesis with our improved Boolean matcher is 18X faster than the one with an optimized SAT-based Boolean matcher, while preserving the quality of the re-synthesizer.

This paper describes a novel and fast placement algorithm for FPGA design space (e.g., area, power or reliability) exploration. The proposed algorithm generates the placement based on the topological similarity between two configurations (netlists) in the design space. Thus, it utilizes the sharing of reusable information during the design space exploration and avoids the time-consuming placement computation like VPR. Tested on logic-level and algorithm-level design space exploration cases, our similarity-based placement accurately depicts the “shape” of a design space and pinpoints the designs which are of most interest to IC designers. Moreover, a turbo version of circuit similarity-based placement performs an average of 30x (up to 100x) faster than VPR's while still achieving comparable placement results.

Power and fault tolerance are deemed to be two orthogonal optimization objectives in FPGA synthesis, with independent attempts to develop algorithms and CAD tools to optimize each objective. In this paper, we study the relationship between these two optimizations and show empirically that there are strong ties between them. Specifically, we analyze the power and reliability optimization problems in FPGA physical synthesis (i.e., packing, placement, and routing), and show that the intrinsic structures of these two problems are very similar. Supported by the post routing results with detailed power and reliability analysis for a wide selection of benchmark circuits, we show that with minimal changes - fewer than one hundred lines of C code - an existing power-aware physical synthesis tool can be used to minimize the fault rate of a circuit under SEU faults. As a by-product of this study, we also show that one can improve the mean-time-to-failure by 100% with negligible area and delay overhead by performing fault-tolerant physical synthesis for FPGAs. The results from this study show a great potential to develop CAD systems co-optimized for power and fault-tolerance.

Software as a Service (SaaS) 1.0 signifcantly lowers the infrastructure and maintenance cost and increases the accessibility of the software by hosting software via the web. Compared with SaaS 1.0, SaaS 2.0 is more flexible since it leverages software tools from both server and client sides with closer interaction between them. The SaaS 2.0 paradigm provides new opportunities and challenges for EDA. In this paper, we take Boolean matching, one of the core sub algorithms in logic synthesis for field programmable gate arrays (FPGAs), as a case study. We investigate the advantages and challenges of implementing a scalable EDA algorithm under SaaS 2.0 paradigm from a technical perspective. We propose SaaS-BM, a new Boolean matching algorithm customized to take full advantage of the cloud while addressing concerns such as security and the internet bandwidth limit. Extensive experiments are performed under a networked environment with concurrent accesses. Integrated into a post-mapping re-synthesis algorithm minimizing area, the proposed SaaS-BM is 863X times faster than state-of-the-art SAT-based Boolean matching with 0.5% area overhead. Compared with a recent Bloom Filter-based Boolean matching algorithm, our proposed SaaS-BM is 53X times faster on large circuits with no area overhead.

We describe In-Place Reconfiguration (IPR) for LUT-based FPGAs, an algorithm that maximizes identical configuration bits for complementary inputs of a LUT thereby reducing the propagation of faults seen at a pair of complementary inputs. Based on IPR, we develop a fault-tolerant logic resynthesis algorithm which decreases the circuit fault rate while preserving functionality and topology of the LUT-based logic network. Since the topology is preserved, the resynthesis algorithm can be applied post-layout and without changes in physical design. Compared to the state-of-the-art academic technology mapper Berkeley ABC, IPR reduces the relative fault rate by 48% and increases MTTF by 1.94x with the same area and performance, and IPR combined with a previous fault-tolerant logic resynthesis algorithm (ROSE) reduces the relative fault rate by 49% and increases MTTF by 2.40x with 19% less area but same performance. The above improvement assumes a stochastic single fault and more improvement is expected for multi-fault models.

Small gates, such as AND2, XOR2, and MUX2, have been mixed with lookup tables (LUTs) inside programmable logic blocks (PLBs) to reduce area and power and increase performance in FPGAs. However, it is unclear whether incorporating macrogates with wide inputs inside PLBs is beneficial. In this paper, we first develop a methodology to extract a small set logic functions that are able to implement a large portion of functions for given FPGA applications, and propose a heterogeneous PLB with one LUT and one macrogate for the selected logic functions. Furthermore, we develop a synthesis flow for such heterogeneous PLBs, including a cut-based delay and area optimized technology mapping, a mixed binary integer and linear programming-based postmapping area recovery to balance the utilization of macrogates and LUTs, and a SAT-based PLB architecture-aware packing. Experiments using over 70 industrial benchmark applications show that we can extract four six-input logic functions to cover more than 50% functions of these applications, and the proposed synthesis flow reduces area by 5% compared to an alternative flow without the postmapping area recovery when both have the optimal logic depth. Compared to the PLB with mixed LUT-4 and small macrogates (XOR2 and MUX2), the PLB with mixed LUT-4 and four-input macrogate reduces logic depth by 6% (and up to 42%) for the aforementioned applications.

We propose a new resynthesis algorithm for FPGA area reduction. In contrast to existing resynthesis techniques, which consider only single-output Boolean functions and the combinational portion of a circuit, we consider multi-output functions and retiming, and develop effective algorithms that incorporate recent improvements to SAT-based Boolean matching. Our experimental results show that with the optimal logic depth, the resynthesis considering multi-output functions reduces area by up to 0.4% compared to the one considering single-output functions, and the sequential resynthesis reduces area by up to 10% compared to combinational resynthesis when both consider multi-output functions. Furthermore, our proposed resynthesis algorithm reduces area by up to 16% compared to the best existing academic technology mapper, Berkeley ABC.

We present FPGA logic synthesis algorithms for stochastic fault rate reduction in the presence of both permanent and transient defects. We develop an algorithm for fault tolerant Boolean matching (FTBM), which exploits the flexibility of the LUT configuration to maximize the stochastic yield rate for a logic function. Using FTBM, we propose a robust resynthesis algorithm (ROSE) which maximizes stochastic yield rate for an entire circuit. Finally, we show that existing PLB (programmable logic block) templates for area-aware Boolean matching and logic resynthesis are not effective for fault tolerance, and propose a new robust template with path re-convergence. Compared to the state-of-the-art academic technology mapper Berkeley ABC, ROSE using the proposed robust PLB template reduces the fault rate by 25% with 1% fewer LUTs, and increases MTBF (mean time between failures) by 31%, while preserving the optimal logic depth.

This paper presents a fast and accurate solution, namely Fashion, to routability-driven global routing problem. Fashion is based on two efficient yet effective techniques: 1) dynamic pattern routing (DPR) and 2) movable-segment-driven DPR. These two techniques enable Fashion to explore large solution space to achieve high routability with low time complexity. Compared with BoxRouter, Fashion has a shorter wire length and reduces overflow and runtime by 5 and 15 times, respectively. Compared with FastRoute, Fashion has similar runtime but 90% smaller overflow and 1.9% shorter wire length. Fashion is significantly better than Labyrinth and Fengshui in terms of overflow, wire length, and runtime.

Boolean matching is one of the enabling techniques for technology mapping and logic resynthesis of field-programmable gate arrays (FPGAs). Boolean satisfiability (SAT)-based Boolean matching (SAT-BM) has been proposed, but computational complexity prohibits its practical deployment. In this paper, we leverage symmetries present in both Boolean functions and target FPGA architectures to prune the solution space, and we also propose some techniques to reduce the replication runtime for SAT instance generation using the incremental SAT reasoning engine. Experiment shows that our SAT-BM reduces runtime by 226times compared with the original SAT-BM algorithm, making SAT-BM more practical.

This paper presents the first in-depth study on dual-Vddbuffer insertion for power minimization under delay constraint. Compared with delay-optimal singleVddbuffer insertion, the dual-Vddbuffer insertion reduces power by 16%. Such power reduction increases when the delay specification is relaxed. Whereas the van Ginneken algorithm can be extended to handle the new problem formulation optimally, its time complexity increases from quadratic time (O(|B|n2)) to pseudopolynomial time (O(|B|n3cmax2log(ncmax)), where |B| is the size of buffer library,nis the number of buffer stations, andcmaxis proportional to the number of all possible subtrees of the net. To improve the time complexity, we propose an approximation technique by sampling subsolutions (i.e., options) and apply predictive min-delay and prebuffer slack pruning rules from a related work. Experiments show that sampling is most effective to reduce run time, whereas the two pruning rules further improve efficiency and accuracy loss due to sampling. We show that our proposed algorithm has linear time complexity with respect to the tree size. It runs over 1000 times faster at a cost of less than 2% delay and power increase over the extended van Ginneken algorithm.

Field programmable dual-Vdd interconnects are effective in reducing FPGA power. We formulate the dual-Vdd-aware slack budgeting problem as a linear program (LP) and a min-cost network flow problem, respectively. Both algorithms reduce interconnect power by 50% on average compared to single-Vdd interconnects, but the network-flow-based algorithm runs 11x faster on MCNC benchmarks. Furthermore, we develop simultaneous retiming and slack budgeting (SRSB) with flip-flop layout constraints in dual-Vdd FPGAs based on mixed integer linear programming, and speed-up the algorithm by LP relaxation and local legalization. Compared to retiming followed by slack budgeting, SRSB reduces interconnect power by up to 28.8%.

This paper presents a fast and accurate global routing algorithm, DpRouter, based on two efficient techniques: (1) dynamic pattern routing (Dpr), and (2) segment movement. These two techniques enable DpRouter to explore large solution space to achieve better routability with low time complexity. Compared with the state-of-the-arts, experimental results show that we consistently obtain better routing quality in terms of both congestion and wire length, while simultaneously achieving a more than 30x runtime speedup. We envision that this algorithm can be further leveraged in other routing applications, such as FPGA routing.

Small gates, such as AND2, XOR2 and MUX2, have been mixed with lookup tables (LUTs) inside the. programmable logic block (PLB) to reduce area and power and increase performance in FP-GAs. However, it is unclear whether incorporating macro-gates with wide inputs inside PLBs is beneficial. In this paper, we first propose a methodology to extract a small set of logic functions that are able to implement a large portion of functions for given FPGA applications. Assuming that the extracted logic functions are implemented by macro-gates in PLBs, we then develop a complete synthesis flow for such heterogeneous PLBs with mixed LUTs and macro-gates. The flow includes a cut-based delay and area optimized technology mapping, a mixed binary integer and linear programming based area recovery algorithm to balance the resource utilization of macro-gates and LUTs for area-efficient packing, and a SAT-based packing. We finally evaluate the proposed heterogeneous FPGA using the newly developed flow and show that mixing LUT and macro-gates, both with 6 inputs, improves performance by 16.5% and reduces logic area by 30% compared to using merely 6-input LUTs.

The Boolean matching problem is a key procedure in technology mapping for heterogeneous field programmable gate arrays (FPGA), and SAT-based Boolean matching (SAT-BM) provides a highly flexible solution for various FPGA architectures. However, the computational complexity of state-of-the-art SAT-BM prohibits its application practically. In this paper we propose an efficient SAT-BM algorithm by exploring function and architectural symmetries. While the most recent work obtained up to 13times speedup, we achieve up to 200times speedup, when both are compared to the original SAT-BM algorithm.

The existing temperature-aware clock embedding assumes a time-invariant temperature gradient. However, it is not solved how to find the worst-case temperature gradient leading to the worst case skew. In this paper, we develop a PErturbation based Clock Optimization (PECO) considering the timevariant temperature gradient. For a given clock topology, we minimize the worst case skew without asking for the worst case temperature map. We decide the merging point level by level based on the sensitivity of the skew with respect to the change of merging point. Such sensitivity is calculated using a parameterized model, which is compressed by a singularvalue-decomposition (SVD) and K-means based clustering considering the temperature correlation. The experimental results show that our algorithm reduces worst-case skew by up to 5X compared to the existing zero skew based ZST/DME method with small (up to 1%) wirelength overhead.

Obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) construction is an essential part of routing. Recently, IC routing and related researches have been extended from Manhattan architecture (lambda2-geometry) to Y-/X-architecture (lambda3-lambda4-geometry) to improve the chip performance. This paper presents an O(n log n) heuristic, lambda-OAT, for obstacle-avoiding Steiner minimal tree construction in the lambda-geometry plane (lambda-OASMT). In this paper, based on obstacle-avoiding constrained Delaunay triangulation, a full connected tree is constructed and then embedded into lambda-OASMT by zonal combination. To the best of our knowledge, this is the first work addressing the lambda-OASMT problem. Compared with most recent works on OARSMT problem, lambda-OAT obtains up to 30-Kx speedup with quality solution. We have tested randomly generated cases with up to 10 K terminals and 10-K rectilinear obstacles within 4 seconds on a Sun V880 workstation (755-MHz CPU and 4-GB memory). The high efficiency and accuracy of lambda-OAT make it extremely practical and useful in the routing phase.

In recent years, the X-architecture is introduced to obtain better performance for integrated circuit physical design. This paper reformulates the global routing problem in X-architecture under the liquid routing model. Then, a dynamic resource assignment (Dra) method is presented to reduce potential vias. At last, a global router called DraXRouter, is designed, in which we adopt a dynamic-tabulist-based tree construction algorithm and a stochastic optimization strategy to gain high quality routing solution. Tested on ISPD'98 benchmarks, DraXRouter achieves better routing performance compared with two recent global routers.

Field programmable dual-Vdd interconnects are effective to reduce FPGA power.Assuming uniform length interconnects,existing work has developed time slack budgeting to minimize power based on estimating the lower bound of power reduction using dual-Vdd for given time slack.In this paper,we show that such lower bound estimation cannot be extended to mixed length interconnects that are used in modern FPGAs.We develop a technique to estimate power reduction using dual-Vdd for mixed length interconnects, and apply linear programming (LP)to solve slack budgeting to minimize power for mixed length interconnects.Experiments show 53%power reduction on average compared to single-Vdd interconnects.Furthermore,this paper presents a simultaneous retiming and slack budgeting algorithm to reduce power in dual-Vdd FPGAs considering placement and.ip-.op binding constraints.The algorithm is based on mixed integer and linear programming (MILP)and achieves up to 20%power reduction compared to retiming followed by slack budgeting.We propose a runtime e fficient flow to apply simultaneous retiming and slack budgeting only when it is necessary.To the best of our knowledge,this paper is the first in-depth study of simultaneous retiming and slack budgeting for dual-Vdd programmable FPGA power reduction while considering layout constraints.

To reduce FPGA power, a linear programming (LP) based time slack allocation algorithm, EdTLC-LP, has been proposed recently for Vdd-programmable interconnects without using Vdd-level converters for mixed wire lengths. However, it takes a long time to solve the LP problem for time slack allocation. In this paper, we develop EdTLC-NW, a slack allocation algorithm based on min-cost network flow to reduce runtime. Compared to single Vdd FPGA with power-gating, EdTLC-LP and EdTLC-NW reduce interconnect power by 52.71% and 52.52%, respectively. EdTLC-NW achieves as good results as EdTLC-LP but runs 8X faster on average. Furthermore, the speedup increases for larger circuits and EdTLC-NW is 20X faster for the largest circuit.

Routing is one of the important phases in VLSI/ULSI physical design. The obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) construction is an essential part of routing since macro cells, IP blocks, and pre-routed nets are often regarded as obstacles in the routing phase. Efficient OARSMT algorithms can be employed in practical routers iteratively. Recently, IC routing and related researches have been extended from Manhattan architecture (λ2-geometry) to Y- / X-architecture (λ3- / λ4-geometry) to improve the chip performance. This paper presents an O(nlogn) heuristic, λ-OASMT, for obstacle-avoiding Steiner minimal tree construction in the λ-geometry plane. Based on obstacle-avoiding constrained Delaunay triangulation, a full connected tree is constructed and then embedded into λ-OASMT by a novel method called zonal combination. To the best of our knowledge, this is the first work addressing the λ-OASMT problem. Compared with two most recent works on OARSMT problem, λ-OASMT obtains up to 30Kx speedup with an even better quality solution. We have tested randomly generated cases with up to 1K terminals and 10K rectilinear obstacles within 3 seconds on a Sun V880 workstation (755MHz CPU and 4GB memory). The high efficiency and accuracy of λ-OASMT make it extremely practical and useful in the routing phase, as well as interconnect estimation in the process of floorplanning and placement.

CAD tools have become more and more important for integrated circuit (IC) design since a complicated system can be designed into a single chip, called system-on-a-chip (SOC), in which physical design tool is an essential and critical part. We try to consider the via minimization problem as early as possible in physical design. We propose a routing method focusing on minimizing vias while considering mutability and wire-length constraint. That is, in the global routing phase, we minimize the number of bends, which is closely related to the number of vias. Previous work only dealt with very small nets, but our algorithm is general for the nets with any size. Experimental results show that our algorithm can greatly reduce the count of bends for various sizes of nets while meeting the constraints of congestion and wire-length.

Routing is one of the important steps in VLSI/ULSI physical design. The rectilinear Steiner minimum tree (RSMT) construction is an essential part of routing. Since macro cells, IP blocks, and pre-routed nets are often regarded as obstacles in the routing phase, obstacle-avoiding RSMT (OARSMT) algorithms are useful for practical routing applications. This paper focuses on the OARSMT problem and presents an algorithm, named An-OARSMan, based on ant colony optimization. A greedy obstacle penalty distance (OP-distance) local heuristic is used in the algorithm and performed on the track graph. The algorithm has been implemented and tested on different kinds of obstacles. Experimental results show that An-OARSMan can handle complex obstacle cases including both convex and concave polygon obstacles with good length performance. It can always achieve the optimal solution in the cases with no more than 7 terminals.