Search

Diverse applications of Deep convolution neural networks (CNNs), such as image classification, semantic segmentation, video recognition, etc., in smart systems require high-throughput acceleration for real-time performance. Such CNNs when realized on edge devices of the Internet of Things, a power/energy-efficient compute platform is required, which can meet the limited power/energy budget of the devices. In this regard, an end-to-end power-optimized acceleration for the compute-intensive CNNs is proposed in this work. The proposed architecture, termed WinDConv, introduces a scheme to support both regular and energy-efficient Winograd convolutions on the same architecture through a fused datapath. Furthermore, using a thoroughly investigated data sparsity enhancement, the data reuse scheme, and a suitable memory hierarchy for power efficiency, the proposed architecture is able to exhibit a practical average power efficiency of at least 12.35 tera operations per second per Watt, which is at least $2\times $ higher than the generic $z$ -first storage baseline architecture with over $3\times $ higher energy efficiency. The proposed architecture also demonstrates the applicability of the proposed schemes in commonly occurring variants of the convolution operation.

The increasing importance of inference algorithms, such as neural networks (NNs), principle component analysis (PCA), and singular value decomposition (SVD), etc., has led to the emergence of hardware accelerators to address power-performance tradeoffs in their implementation. Their large data sets make DRAM access the bottleneck for power and performance. Private SRAM scratch-pad memory is used to mitigate the DRAM access penalty but it is a limited resource in size and bandwidth. Thus, accelerator design is not just about computation, but also how data flow is scheduled across the memory hierarchy, including DRAM, scratch-pad SRAM, and datapath registers. Current accelerator design tools automate the generation of customized datapaths to improve performance, but have limited support for reducing DRAM/SRAM accesses during the computation. In this paper, we propose a memory-driven accelerator design methodology for large-scale inference applications, to maximize data access in the datapath and SRAM. We demonstrate its efficacy using several key kernels from large-scale inference applications.

In this paper, we present an accuracy-aware design framework [called accuracy-aware high-level synthesis (Achilles)], which synthesizes a high-level description of an input application with the objective of minimizing the energy consumption of the synthesized circuit. The proposed framework includes two main parts of Achilles and light-weight predictor selection. The framework leverages light-weight error predictors (i.e., machine learning-based classifiers) to achieve more energy reduction by dynamically managing the output quality level (exact or approximate) of the synthesized circuit. To synthesize the input application, first, we exploit a heuristic algorithm to determine the quality level required for each operation in the data flow graph (DFG) representation of the input application. Next, for synthesizing the input application, we propose an effective Achilles algorithm which utilizes the flexibility of the available multiquality arithmetic units in a high-level cell library to synthesize the datapath. To improve the efficiency, the process starts by iteratively reducing the number of functional units required for synthesizing the DFG. Then, a proper light-weight error predictor satisfying the user expected quality is chosen from the available predictors in the framework. Based on the quality requirements, three different quality management modes are considered. The efficacy of the proposed framework is assessed for benchmarks from image and signal processing as well as robotics domains. The study of these benchmarks indicates that Achilles may reduce the energy consumption up to 51% (36% on average), up to 72% (51% on average), and up to 57% (33% on average) in threshold, average, and hybrid modes, respectively, for the studied cases. Moreover, the results show that relative coverage of large errors may be increased from 21% to 55% by employing synthetic minority oversampling technique method.

With technology scaling leading to reliability problems and a proliferation of hardware accelerators, there is a need for cost-effective techniques to detect errors in complex datapaths. Modulo (residue) arithmetic is useful for creating a shadow datapath to check the computation of an arithmetic datapath and involves three key steps: 1) reduction of the inputs to modulo shadow values; 2) computation with those shadow values; and 3) checking the outputs for consistency with the shadow outputs. The focus of this paper is new gate-level architectures and algorithms to reduce the cost of modulo shadow datapaths. We introduce new low-cost architectures for the functional units performing the aforementioned reduction, shadow computation, and checking operations. We compare our functional units to the previous state-of-the-art approach, observing a 12.5% reduction in area and a 47.1% reduction in delay for a 32-bit mod-3 reducer; that our reducer costs, which tend to dominate shadow datapath costs, do not increase with larger modulo bases; and that for modulo-15 and above, all of our functional units have better area and delay than their previous counterparts. To demonstrate the cost-effectiveness of our approach in computation-intensive accelerator applications, we design custom pipelined shadow datapaths for five compound functional units implementing a variety of vector and matrix operations. For a 32-bit main datapath and 2-bit shadow datapath, we observe area costs of 6%–10% and reliability improvements against single event transient errors of 3–61 $\times$ . For an 8-bit shadow datapath, we observe area costs of 15%–20% and reliability gains of 121–2477 $\times$ .

This paper makes a paradigm shift in the assumed notion of common subexpressions for complexity reduction of multiple constant multiplications implementation. Our proposed unified adder/subtractor (UAS)-based common subexpression elimination (CSE) algorithm is inspired by the recent advancement in complex arithmetic component mapping for datapath synthesis of digital systems. A dedicated UAS operator is designed at gate level to achieve arithmetic reduction for concurrent computation of the sum and difference of two input signals. To maximize computation reuse, dual subexpression is defined to enable a UAS to be shared by the otherwise incompatible odd and even common subexpressions. The three different types of common subexpression are uniquely encoded by a quadruple in the proposed data structure. Constant coefficients are represented by signed digits in Cartesian coordinate system from which nonoverlapping pairs of nonzero digits are parsed for dual, even, and odd subexpressions to maximize the reuse of all three types of arithmetic resources. The effectiveness of our proposed UAS-based CSE in overcoming the complexity reduction bottleneck are demonstrated by comparing the synthesis results obtained from six benchmark finite impulse response filters, an electroencephalogram filter bank, fast Fourier transform, and discrete cosine transform multipliers designed by ten algorithms. The results show a noteworthy 27.2% reduction in area-time complexity of our method over the baseline canonical signed digit implementation. Our solutions are also more power efficient, with average power saving of 12.0% over those designed by other algorithms in comparison.

The digital signal processing (DSP) blocks on modern field programmable gate arrays (FPGAs) are highly capable and support a variety of different datapath configurations. Unfortunately, inference in synthesis tools can fail to result in circuits that reach maximum DSP block throughput. We have developed a tool that maps graphs of add/sub/mult nodes to DSP blocks on Xilinx FPGAs, ensuring maximum throughput. This is done by delaying scheduling until after the graph has been partitioned onto DSP blocks and scheduled based on their pipeline structure, resulting in a throughput optimized implementation. Our tool prepares equivalent implementations in a variety of other methods, including high-level synthesis (HLS) for comparison. We show that the proposed approach offers an improvement in frequency of 100% over standard pipelined code, and 23% over Vivado HLS synthesis implementation, while retaining code portability, at the cost of a modest increase in logic resource usage.

Due to the necessity of handling unexpected events in execution time, e.g., to support process variations, new mechanisms for dealing with every possible behavior of the datapath must be developed. Conventional centralized controllers can only handle very few dynamic events. Distributed controllers, on the other hand, are able to support every combination of events. These controllers are composed of several finite state machines, which are interconnected via a global coordinator. The use of this type of controller obliges to check the hazards between operations in run time, which entails some penalty in the controller complexity. In this paper, a new methodology for deploying a distributed controller over a set of clusters is presented. A register binding algorithm specially suited for distributed controllers has also been developed. It combines a clustering method and a least recently used policy to reduce the number of hazards in run time. Furthermore, our methodology allows the exploration of different solutions by tuning the input parameters of the binding algorithm. Several studies evaluating the execution time and area tradeoffs are presented to support our techniques. Results show that for some cases it is possible to reduce more than 50% the expected execution time, at the expense of a slight area increase.

Nowadays, power is a primary concern in digital circuits and clock distribution networks are particularly a significant power consumer. Therefore, clock gating is an effective technique in saving dynamic power by reducing the switching activities. In this paper, we propose a centralized and fine-grained microarchitecture-level clock gating for low power hardware accelerators which are automatically designed by high-level synthesis (HLS) tool. The basic principium of our idea is not to use any extra computation for generating clock enabled signals and exploit exiting signals of finite state machine for controlling the datapath clock network. After determining the current state in finite state machine, clock sub-tree of current state is enabled and the other sub-trees are disabled with a slight increase in circuit area. Our approach is implemented within an HLS design flow for automatic low power hardware accelerator generation in application specific integrated circuit design. Experimental results are obtained on a set of representative benchmark programs. Depending on the circuit size and number of registers, it is shown that 47%–86% reduction in power dissipation is observed.

In order to keep pace with the growing complexity of integrated circuits (ICs), IC and system designers are increasingly using electronic system level (ESL) design tools. ESL tool sales were around $460 million in 2011. The value of the ICs designed using these tools is at least an order of magnitude more. Concurrently, advanced IC reverse engineering techniques are being developed and used by attackers. In response, several anti-reverse engineering techniques have been proposed for integration into the IC design flow. An important class of defenses hardens the controllers that orchestrate the functionality of designs generated by ESL tools. We demonstrate an attack to recover the controller in any ESL-generated design even if the controller has been hardened using state-of-the-art controller hardening techniques. The attack analyzes the unhardened parts of the controller (i.e., the controller output logic and datapath) and reconciles this information with the architectural, controller, and timing constraints implicit in and underlying all ESL design methodologies. We then propose a countermeasure that inserts decoy connections into an ESL tool-generated design to thwart reverse engineering. We introduce a security metric to quantify the effectiveness of the developed attacks and defenses. We demonstrate the attack and defenses on designs generated by state-of-the-art ESL tools.

High-level synthesis (HLS) tools generate register-transfer level (RTL) hardware descriptions from behavioral-level specifications through resource allocation, scheduling and binding. Traditionally, HLS tools build datapath pipelines by inserting pipeline registers to break combinational logic into single-cycle segments; accurately analyzing that the number of available cycles for signal propagation is proven to be infeasible at the RT-level. Thus, RT-level timing analyses must pessimistically assume each path has at most one cycle for signal propagation. This leads to false positives in critical-path analyses, prevents RTL synthesis tools from optimizing real critical paths, and forces HLS flows to insert pipeline registers without improving hardware quality. In this paper, we present an efficient behavioral-level multicycle path analysis (BL-MCPA) algorithm that leverages control-data flow information to reduce time complexity of multicycle path analysis from exponential to polynomial. BL-MCPA helps eliminate false positives in timing analysis, and improves the reported f max by 15% on average. With BL-MCPA, we avoid unnecessary pipeline register insertion, and reduce execution latency by 25% and register usage by 29% under a user f max constraint of 300 MHz. Using BL-MCPA, we replace large multiplexers (MUXs) by pipelined MUX-trees and reduce execution latency of hardware by up to 67% on designs whose performance is limited by the large MUXs.

An equivalence checking method of finite state machines with datapath based on value propagation over model paths is presented here for validation of code motion transformations commonly applied during the scheduling phase of high-level synthesis. Unlike many other reported techniques, the method is able to handle code motions across loop bodies. It consists in propagating the variable values over a path to the subsequent paths on discovery of mismatch in the values for some live variable, until the values match or the final path segments are accounted for without finding a match. Checking loop invariance of the values being propagated beyond the loops has been identified to play an important role. Along with uniform and nonuniform code motions, the method is capable of handling control structure modifications as well. The complexity analysis depicts identical worst case performance as that of a related earlier method of path extension which fails to handle code motion across loops. The method has been implemented and satisfactorily tested on the outputs of a basic block-based scheduler, a path-based scheduler, and the high-level synthesis tool SPARK for some benchmark examples.

In nanometer technologies, even local interconnects are believed to cause major impact on timing, power, repeaters, and routability in VLSI circuits. Although empirical studies exist, there is little comprehensive work that explores the impact of local interconnects on both timing and power in a real high performance microprocessor design in a quantitative manner. To address the void, this article presents results from the extensive study carried out on RTL-to-layout synthesized (RLS) and semi-manually designed structured data path (SDP) blocks in a 45 nm technology microprocessor core. The study shows that for synthesized blocks local interconnects contribute $1/3rd to the worst internal timing paths, on average; in case of datapath blocks, the same contribution is $1/5th. Moreover, regardless of the design style, the interconnects contribute to more than 30% to the dynamic/glitch power. This points to severity of impact due to local interconnects in today's high performance designs and implies that algorithms/approaches underlying existing synthesis/physical design tools/methodologies have limited success in mitigating the same.

Variations in timing can occur due to multiple sources on a chip such as process variations and variations in input patterns. It is desirable to have variation awareness at the register transfer level (RTL), and estimate block level delay distributions early in the design cycle, to evaluate design choices quickly and minimize postsynthesis simulation costs. In previous work, we introduced statistical high-level analysis and rigorous performance estimation (SHARPE), a rigorous, systematic methodology to verify design correctness in RTL in the presence of variations. We described SHARPE in the context of computing statistical delay invariants with respect to input variations. We treated the RTL source code as a program and used static program analysis techniques to compute probabilities. We modeled the probabilistic RTL modules as discrete time Markov chains that are then checked formally for probabilistic invariants using PRISM, a probabilistic model checker. In this paper, we extend SHARPE to perform timing verification in RTL in the context of process variations. We achieved this by obtaining a set of process variation-aware RTL delay models and correspondingly modifying the existing steps in SHARPE. We illustrate SHARPE on the RTL description of the datapath of OR1200, an open source embedded processor. We also apply SHARPE to other data-intensive RTL designs such as nontrivial components of communication systems and a few benchmark designs.

As technology scales and frequencies increase, a new hybrid design style emerges, wherein designs contain a mixture of random logic and datapath standard-cell components. This paper demonstrates that conventional half-perimeter wirelength driven placers underperform in terms of regularity and Steiner wirelength (StWL) for such hybrid designs. In addition, the quality gap between manual and automatic placement is more pronounced as the designs become more datapath oriented. To effectively handle hybrid designs, this paper proposes a new unified placement flow that simultaneously places random logic and datapath cells. This flow is built on the top of a leading academic force-directed placer and significantly improves the quality of datapath placement while leveraging the speed and flexibility of existing random-logic placement algorithms. It consists of a suite of novel global and detailed placement techniques, collectively called structure-aware placement techniques (SAPT). These techniques effectively integrate alignment constraints into placement, thereby overcoming the deficiencies of existing random-logic placers when handling designs with embedded datapaths. Compared to other state-of-the-art placers, SAPT improves total StWL by more than 28% and total routing overflow by over six times on the ISPD 2011 datapath benchmark suite. In addition, it improves total StWL by 5.8% on industrial hybrid designs.

Addition is the key arithmetic operation in most digital circuits and processors. Therefore, their performance and other parameters, such as area and power consumption, are highly dependent on the adders' features. In this paper, we present multispeculation as a way of increasing adders' performance with a low area penalty. In our proposed design, dividing an adder into several fragments and predicting the carry-in of each fragment enables computing every addition in two very short cycles at the most, with 99% or higher probability. Furthermore, based on multispeculation principles, we propose a new strategy for implementing addition chains and hiding most of the penalty cycles due to mispredictions, while keeping at the same time the resource sharing capabilities that are sought in high-level synthesis. Our results show that it is possible to build linear and logarithmic adders more than 4.7× and 1.7× faster than the nonspeculative case, respectively. Moreover, this is achieved with a low area penalty (38% for linear adders) or even an area reduction (-8% for logarithmic adders). Finally, applying multispeculation principles to signal processing benchmarks that use addition chains will result in 25% execution time reduction, with an additional 3% decrease in datapath area with respect to implementations with logarithmic fast adders.

Speculative functional units (SFUs) are arithmetic functional units that operate using a predictor for the carry signal. The carry prediction helps to shorten the critical path of the functional unit. The average case performance of these units is determined by the hit rate of the prediction. In case of mispredictions, the SFUs need to be coordinated by the datapath control mechanism to perform corrections and to maintain the datapath in the correct state. Devising a control mechanism for correcting mispredictions without adversely impacting overall performance is the most important challenge. In this paper, we present techniques for designing a datapath controller for seamless deployment of SFUs in high level synthesis. We have developed two techniques based on two main control paradigms: centralized and distributed control. The centralized approach stops the execution of the entire datapath for each misprediction and resumes execution once the correct value of the carry is known. The distributed approach decouples the functional unit suffering from the misprediction from the rest of the datapath. Hence, it allows the remainder of the functional units to carry on execution and be at different scheduling states at different times. We tested datapaths utilizing both linear structures and logarithmic structures for speculative arithmetic functional units. Our results show that it is possible to reduce execution time by as much as 38% (33% on average) for linear structures and by as much as 37.2% (25% on average) for logarithmic structures.

This paper proposes an automatic design flow of datapath-dominated applications which is able to deal with optimization and equivalence checking of multi-output polynomials over Z2n. This paper also gives four main contributions: 1) proposing a complete design flow for modular equivalence checking, high level synthesis, and optimization; 2) considering hidden monomials to factorize those polynomials which do not have any common monomials; 3) combining and improving our previous optimization heuristics to eliminate multi-operand common sub-expressions as much as possible; and 4) implementing all algorithms on top of the modular Horner expansion diagram package. Experimental results have shown an average saving of 9.9% and 4.5% in the number of gates and critical path delay, respectively, after applying modular reduction over Z2n, while other optimization techniques are not used. Besides, after applying our optimization techniques, experimental comparisons with the state-of-the-art techniques show an average improvement in the area by 19.5% with an average delay decrease of 16.7%. Regarding the comparison with our previous papers, the area and delay are improved by 13.3% and 15.5%, respectively.

A formal verification method of the datapath and controller generation phase of a high-level synthesis (HLS) process is described in this paper. The goal is achieved in two steps. In the first step, the datapath interconnection and the controller finite state machine description generated by a high-level synthesis process are analyzed to obtain the register transfer-operations executed in the datapath for a given control assertion pattern in each control step. In the second step, an equivalence checking method is deployed to establish equivalence between the input and the output behaviors of this phase. A rewriting method has been developed for the first step. Unlike many other reported techniques, our method is capable of validating pipelined and multicycle operations, if any, spanning over several states. The correctness and complexity of the presented method have been treated formally. The method is implemented and integrated with an existing HLS tool, called structured architecture synthesis tool. The experimental results on several HLS benchmarks indicate the effectiveness of the presented method.

While application-specific instruction-set processors (ASIPs) have allowed designers to create processors with custom instructions to target specific applications, floating-point (FP) units (FPUs) are still instantiated as noncustomizable general-purpose units, which, if underutilized, wastes area and performance. Therefore, there is a need for custom FPUs for embedded systems. To create a custom FPU, the subset of FP instructions that should be implemented in hardware has to be determined. Implementing more instructions in hardware reduces the cycle count of the application but may lead to increased latency if the critical delay of the FPU increases. Therefore, a balance between the hardware-implemented and the software-emulated instructions, which produces the best performance, must be found. In order to find this balance, a rapid design space exploration was performed to explore the tradeoffs between the area and the performance. In order to reduce the area of the custom FPU, it is desirable to merge the datapaths for each of the FP operations so that redundant hardware is minimized. However, FP datapaths are complex and contain components with varying bit widths; hence, sharing components of different bit widths is necessary. This introduces the problem of bit alignment, which involves determining how smaller resources should be aligned within larger resources when merged. A novel algorithm for solving the bit-alignment problem during datapath merging was developed. Our results show that adding more FP hardware does not necessarily equate to lower runtime if the delays associated with the additional hardware overcomes the cycle count reductions. We found that, with the Mediabench applications, datapath merging with bit alignment reduced area by an average of 22.5%, compared with an average of 14.1% without bit alignment. With the Standard Performance Evaluation Corporation (SPEC) CPU2000 FP (CFP2000) applications, datapath merging with bit alignment reduced area by an average of 7.6%, compared with an average of 3.9% without bit alignment. The less pronounced improvement with the SPEC CFP2000 benchmarks occurs because the SPEC CFP2000 applications predominantly use double-precision operations only. Therefore, there are fewer resources with different bit widths, which benefit less from bit alignment.

Test-pattern generators (TPGs), based on arithmetic operations, are becoming cost-effective built-in self-test solutions for circuits with embedded processors. Similar to pseudorandom TPGs, arithmetic TPGs use reseeding to reach high levels of fault coverage (FC). In this paper, we propose a method of searching for an effective reseeding strategy, guaranteeing a specified FC level. The proposed methodology minimizes the total test time under the constraint of the total memory resource allocated to store the seeds. The minimization is performed by a binary search that speeds up the seed selection. Experiments with benchmark circuits have shown an average reduction of 43.47% in test time compared with the three previous methodologies.

This paper addresses the equivalence verification problem of register-transfer level (RTL) descriptions that implement arithmetic computations (such as add, mult) over bit vectors with finite widths. A bit vector of size represents integer values from 0 to 2m-1, implying that the corresponding integer values are reduced modulo 2m(%2m). This suggests that bit-vector arithmetic can be efficiently modeled as algebra over finite integer rings, where the bit-vector size (m) dictates the cardinality of the ring (Z2 m). This paper models the arithmetic datapath verification problem as the equivalence testing of polynomial functions from Z2 n 1timesZ2 n 2times...timesZ2 n drarrZ2 m. We formulate the equivalence problem into that of proving whether f-gequiv0%2m. Fundamental concepts and results from ldquonumber,rdquo ldquoring,rdquo and ldquoideal theoryrdquo are subsequently employed to develop systematic complete algorithmic procedures to solve the problem. We demonstrate the application of the proposed theoretical concepts to high-level (behavioral/RTL) verification of bit-vector arithmetic within practical computer-aided design settings. Using our approach, we verify a set of arithmetic datapaths at RTL, where contemporary verification approaches prove to be infeasible.

This paper presents a theoretical framework that solves optimally and in polynomial time many open problems in time budgeting. The approach unifies a large class of existing time-management paradigms. Examples include time budgeting for maximizing total weighted delay relaxation, minimizing the maximum relaxation, and min-skew time budget distribution. The authors develop a combinatorial framework through which we prove that many of the time-management problems can be transformed into a min-cost flow problem instance. The methodology is applied to intellectual-property-based datapath synthesis targeting field-programmable gate arrays. The synthesis flow maps the input operations to parameterized library modules during which different time budgeting policies have been applied. The techniques always improve the area requirement of the implemented test benches and consistently outperform a widely used competitor. The experiments verify that combining fairness and maximization objectives improves the results further as compared with pure maximum budgeting. The combined fairness and maximization objective improves the area by 25.8% and 28.7% in slice and LUT counts, respectively

High-level synthesis (HLS) of memory-intensive applications has featured several innovations in terms of enhancements made to the basic memory organization and data layout. However, increasing performance and energy demands faced by application-specific integrated circuits (ASICs) are forcing designers to alter the fundamental architectural template of the HLS output, namely, a controller datapath associated with a memory subsystem (monolithic, partitioned, etc.). An architectural template for the HLS output that consists of a controller-datapath circuit associated with a memory subsystem into which computation units have been integrated is proposed. The enhanced memory subsystem is called computation-unit integrated memory (CIM). A CIM offers higher memory bandwidth (relative to what is offered through the system bus) to computation units present locally within it and reduces the overall communication between the memory subsystem and the controller datapath, thus providing a template highly suitable for deriving efficient implementations of memory-intensive applications. This paper addresses the challenge of providing a systematic synthesis framework for a CIM-based architecture. This framework can analyze the various tradeoffs involved in selecting suitable operations in a behavior for execution using a CIM and generate a high-performance low-overhead implementation. Efficient data reuse of register files have also been fully exploited to further improve system performance. Experiments with several behaviors indicate that an average performance improvement of 2.02times(a maximum of 2.70times) is possible with very low area overheads. The energy-delay product improves by an average of 2.5times(maximum of 3.8times)

It has been widely recognized that the dynamic-range information of an application can be exploited to reduce the datapath bitwidth of either processors or application-specific integrated circuits and, therefore, the overall circuit area, delay, and power consumption. While recent proposals of analytical dynamic-range-estimation methods have shown significant advantages over the traditional profiling-based method in terms of runtime, it is argued here that the rather simplistic treatment of input correlation and system nonlinearity may lead to significant error. In this paper, three mathematical tools, namely Karhunen-Loegraveve expansion, polynomial chaos expansion, and independent component analysis are introduced, which enable not only the orthogonal decomposition of input random processes, but also the propagation of random processes through both linear and nonlinear systems with difficult constructs such as multiplications, divisions, and conditionals. It is shown that when applied to interesting nonlinear applications such as adaptive filters, polynomial filters, and rational filters, this method can produce complete accurate statistics of each internal variable, thereby allowing the synthesis of bitwidth with the desired trade off between circuit performance and signal-to-noise ratio

A "white box" design methodology, which deals with hierarchical synthesis issues by providing a bridge between a high-level algorithm representation and lower level design tools, is presented. It illustrates tradeoffs when dealing with designs in a hierarchical and flattened manner. An enhanced Minnesota architectural synthesis scheduling algorithm is given, which gives highly efficient field programmable gate array solutions by providing access to parameterized expressions for datapath latencies and is applied to normalized lattice and delayed least mean square filter examples.

In this paper, we present a satisfiability (SAT)-based algorithm for automatically generating test sequences that target gate-level stuck-at faults in a circuit by using its register-transfer level (RTL) description. Our methodology uses a unified RTL circuit representation, called assignment-decision diagrams (ADDs), for test analysis. Test generation proceeds by abstracting the components in this unified representation using input/output propagation rules, so that any justification/propagation event can be captured as a Boolean implication. Consequently, we reduce RTL test generation to an SAT instance that has a significantly lower complexity than the equivalent problem at the gate level. Our algorithm is tailored to overcome the disadvantages of several existing RTL precomputed test-set-based approaches, such as the need for an explicit controller/datapath separation, the use of all test vectors or none from the precomputed test set for any given module, a dependence on symbolic justification (observability) paths from (to) circuit inputs (outputs) for a module, and a lack of applicability to mixed gate-level/RTL designs. Using the state-of-the-art SAT solver Zchaff, we show that our RTL test generator can outperform gate-level sequential automatic test-pattern generation (ATPG), in terms of both fault coverage and test-generation time (two-to-three orders of magnitude speedup), in comparable test-application times. Furthermore, we show that in a bilevel testing scenario, in which RTL ATPG is followed by gate-level sequential ATPG on the remaining faults, we improve the fault coverage even further, while maintaining a high speedup in test-generation time (nearly 32/spl times/) over pure gate-level sequential ATPG, at comparable test-application times.

We present a pipelining-aware router for fieldprogrammable gate arrays (FPGAs). The problem of routing pipelined signals is different from the conventional FPGA routing problem. The two-terminal N/sub D/ pipelined routing problem is to find the lowest cost route between a source and sink that goes through at least N (N/spl ges/1) distinct pipelining resources. In the case of a multiterminal pipelined signal, the problem is to find a minimum spanning tree (MST) that contains sufficient pipelining resources such that pipelining constraints at each sink are satisfied. In this paper, we first present an optimal algorithm for finding a lowest cost 1/sub D/ route. The optimal 1/sub D/ algorithm is then used as a building block for a greedy two-terminal N/sub D/ router. Next, we discuss the development of a multiterminal routing algorithm (PipeRoute) that effectively leverages both the 1/sub D/ and N/sub D/ routers. Finally, we present a preprocessing heuristic that enables the application of PipeRoute to pipelined FPGA architectures. PipeRoute's performance is evaluated by routing a set of benchmark netlists on the reconfigurable pipelined datapath (RaPiD) architecture. Our results show that the architecture overhead incurred in routing netlists on RaPiD is less than 20%. Further, the results indicate a possible trend between the architecture overhead and the percentage of pipelined signals in a netlist.

With the increasing cost of on-chip global communication, high-performance designs for data-intensive applications require architectures that distribute hardware resources (computing logic, memories, interconnect, etc.) throughout the chip, while restricting computations and communications to geographic proximities. In this paper, we present a methodology for high-level synthesis (HLS) of distributed logic-memory architectures, i.e., architectures that have logic and memory distributed across several partitions in a chip. Conventional HLS tools are capable of extracting parallelism from a behavior for architectures that assume a monolithic controller/datapath communicating with a memory or memory hierarchy. This paper provides techniques to extend the synthesis frontier to more general architectures that can extract both coarse and fine-grained parallelism from data accesses and computations in a synergistic manner. Our methodology selects many possible ways of organizing data and computations, carefully examines the tradeoffs (i.e., communication overheads, synchronization costs, area overheads) in choosing one solution over another, and utilizes conventional HLS techniques for intermediate steps. We have evaluated the proposed framework on several benchmarks by generating register-transfer level (RTL) implementations using an existing commercial HLS tool with and without our enhancements, and by subjecting the resulting RTL circuits to logic synthesis and layout. The results show that circuits designed as distributed logic-memory architectures using our framework achieve significant (up to 5.3/spl times/, average of 3.5/spl times/) performance improvements over well-optimized conventional designs with small area overheads (up to 19.3%, 15.1% on average). At the same time, the reduction in the energy-delay product is by an average of 5.9/spl times/ (up to 11.0/spl times/).

Modern systems-on-a-chip depend heavily on hard intellectual properties, such as standard cell and datapath libraries. As the foundries accelerate their update of advanced processes with increasingly complex design rules, and the libraries grow in flexibility and size, the cost of library development becomes prohibitively high. Automated layout-migration techniques used today, which are based on layout compaction developed a decade ago, corrupt advanced design considerations by honoring only design rules, and cannot cope with some of the new challenges involved. In this paper, we present a new integer linear programming (ILP)-based layout-migration engine, called calligrapher, and make the following contributions. First, we extend the recently proposed minimum perturbation (MP) metric designed to retain original layout design intentions, while overcoming its shortcoming of biased treatment of layout objects. Second, we propose a new design-rule-constraint algorithm, and prove its linear complexity for the number of constraints generated. Compared with what has been achieved in the literature, the proposed algorithm can significantly reduce the ILP solver time by limiting the constraint size. Third, we propose an iterative migration framework based on the concept of soft constraint. With this framework, two-dimensional compaction quality can be achieved with a runtime comparable to one-dimensional compaction. We demonstrate the effectiveness of calligrapher by migrating the Berkeley low-power libraries, originally developed for the 1.2-/spl mu/m MOSIS process, into TSMC 0.25- and 0.18-/spl mu/m technologies. We show that even for a very compact layout, our metric and the MP metric can make a difference by as much as 20%-45%. We also show that our iterative algorithm can improve the area by 10% on average compared to the traditional technique using the MP metric, and inflates the area by merely 7.5% compared to the traditional technique using minimum-area metric.

Reconfigurable systems have been shown to achieve significant performance speedup through architectures that map the most time-consuming application kernel modules or inner loops to a reconfigurable datapath. As each portion of the application starts to execute, the system partially reconfigures the datapath so as to perform the corresponding computation. The reconfigurable datapath should have as few and simple hardware blocks and interconnections as possible, in order to reduce its cost, area, and reconfiguration overhead. To achieve that, hardware blocks and interconnections should be reused as much as possible across the application. We represent each piece of the application as a data-flow graph (DFG). The DFG merging process identifies similarities among the DFGs, and produces a single datapath that can be dynamically reconfigured and has a minimum area cost, when considering both hardware blocks and interconnections. In this paper we present a novel technique for the DFG merge problem, and we evaluate it using programs from the MediaBench benchmark. Our algorithm execution time approaches the fastest previous solution to this problem and produces datapaths with an average area reduction of 20%. When compared to the best known area solution, our approach produces datapaths with area costs equivalent to (and in many cases better than) it, while achieving impressive speedups.

In this paper, we present a novel power estimation scheme for programmable systems consisting of predesigned datapath and memory components. The proposed hybrid methodology yields highly accurate estimates within short runtimes by combining high-level simulation with analytical macromodeling of circuit characteristics. The kernel of our methodology is a simulation-free power estimation scheme for memoryless datapaths comprising several IP blocks connected in fixed topologies. The outer shell of our hybrid scheme is a functional simulation, which is performed only on the interfaces between memoryless components and memory blocks. This simulation accurately captures the control signals that affect the flow of data and, consequently, the utilization and power dissipation of hardware. Experimental results validate the accuracy and efficiency of our methodology. We applied our static power estimation kernel to signal processing and data encryption datapaths. For designs of up to 576 IP blocks, the average error of our power estimates is 7.3% in comparison with switch-level simulation results. We implemented our hybrid scheme into a power estimation tool, called HYPE, and used it to explore various architectural alternatives in the design of a 256-state Viterbi decoder and a Rijndael encryptor. For designs with about 1 million transistors, our estimator terminates within seconds. Compared with commercial state-of-the-art gate-level power estimators, our proposed methodology is up to 1000 times faster with 5.4% deviation on average.

Interconnects (wires, buffers, clock distribution networks, multiplexers, and busses) consume a significant fraction of total circuit power. In this paper, we demonstrate the importance of optimizing on-chip interconnects for power during high-level synthesis. We present a methodology to integrate interconnect power optimization into high-level synthesis. It not only reduces datapath unit power consumption in the resultant register-transfer level architecture, but also optimizes interconnects for power. We take into account physical design information and coupling capacitance to estimate interconnect power consumption accurately for deep submicron technologies. We show that there is significant spurious (i.e., unnecessary) switching activity in the interconnects and propose techniques to reduce it. Compared with interconnect-unaware power-optimized circuits, interconnect power can be reduced by 53.1% on average, while overall power is reduced by an average of 26.8%, with negligible area overhead. Compared with area-optimized circuits, the interconnect power reduction is 72.9% and overall power reduction is 56.0%, with 44.4% area overhead. The power reductions are obtained solely through switched capacitance reduction (no voltage scaling is assumed).

Microprocessor datapath architectures operate on signed numbers usually represented in two's-complement or sign-magnitude formats. The multiplication operation is performed by optimized array multipliers of various architectures which are often produced by automatic module generators. Array multipliers have either a standard, nonrecoded signed (or unsigned) architecture or a recoded (modified Booth's algorithm) architecture. High-quality testing of array multipliers based on a comprehensive sequential fault model and not affecting their well-optimized structure has not been proposed in the past. In this paper, we present a built-in self-testing (BIST) architecture for signed and unsigned array multipliers with respect to a comprehensive sequential fault model. The BIST architecture does not alter the well-optimized multiplier structure. The proposed test sets can be applied externally but their regular nature makes them very suitable for embedded, self-test application by simple specialized hardware which imposes small overheads. Two different implementations of the BIST architecture are proposed. The first implementation focuses on the test invalidation problem and targets robust sequential fault testing, while the second one focuses on test cost reduction (test time and hardware overhead).

A fault-secure datapath either generates a correct result or signals an error. This paper presents a register transfer level concurrent error detection (CED) technique that uses hybrid time and hardware redundancy to optimize the time and area overhead associated with fault security. The proposed technique combines the idle computation cycles in a datapath with selective breaking of data dependences of the normal computation. Designers can tradeoff time and hardware overhead by varying these design parameters. We present an algorithm to synthesize fault secure designs and validate it using Synopsys' behavioral compiler.

This work examines the inherent self-checking (SC) property of latch-free dynamic asynchronous datapath (LFDAD) using differential cascode voltage switch logic. Consequently, a highly efficient SC dynamic asynchronous datapath architecture is presented. In this architecture, no hardware needs to be added to the datapath to achieve SC. The presented implementation is efficient in terms of speed and area and represents a new approach to fault-tolerant design.

This paper addresses the problem of layout automation of datapath cells. It presents an analytical approach to transistor placement under full custom design style and demonstrates that it can be applied to practical datapath designs. The presented approach is based on a mathematical model which employs a mixed integer linear programming technique. The placement algorithm adopts the custom design techniques commonly used by datapath layout designers in generating hand-crafted designs. An important aspect of the presented method is the efficient management of the complexity of the underlying mathematical model which makes it applicable to real designs. The authors implemented the presented datapath design technique as an experimental software tool running in the industrial environment. The generated layout results are competitive with manual designs provided by experienced layout designers.

We present a new approach to checking assertion properties for register-transfer level (RTL) design verification. Our approach combines structural word-level automatic test pattern generation (ATPG) and modular arithmetic constraint-solving techniques to solve the constraints imposed by the target assertion property. Our word-level ATPG and implication technique not only solves the constraints on the control logic, but also propagates the logic implications to the datapath. A novel arithmetic constraint solver based on modular number system is then employed to solve the remaining constraints in datapath. The advantages of the new method are threefold. First, the decision-making process of the word-lever ATPG is confined to the selected control signals only. Therefore, the enumeration of enormous number of choices at the datapath signals is completely avoided. Second, our new implication translation techniques allow word-level logic implication being performed across the boundary of datapath and control logic and, therefore, efficiently cut down the ATPG search space. Third, our arithmetic constraint solver is based on modular instead of integral number systems. It can thus avoid the false-negative effect resulting from the bit-vector value modulation. A prototype system has been built that consists of an industrial front-end hardware description language (HDL) parser, a property-to-constraint converter, and the ATPG/arithmetic constraint-solving engine. The experimental results on some public benchmark and industrial circuits demonstrate the efficiency of our approach and its applicability to large industrial designs.

Test issues in application-specific digital filter datapaths are investigated. It is found that such designs can contain hundreds of redundant faults, making it difficult to accurately determine fault coverage. Since these redundant faults tend to appear in the same general location as test-resistant faults, the presence of many redundant faults can hide significant untested faults despite high overall test coverage. Classes of redundant faults that arise in digital filter datapaths are described, and we propose a suite of techniques for identifying and eliminating the most common redundancies based on arithmetic optimization. The approach is suitable as a front-end to more accurate fault simulation, or can be used in the design process to eliminate redundant logic. The approach is validated as a tool for developing very high-coverage built-in self-test circuits, showing that 100% fault coverage can be achieved in 24k-gate filters with as little as 1% area overhead. When used as a datapath optimization technique, the average area reduction over 15 designs was 8.9%, compared with moderately optimized designs. As a front-end to fault simulation, the approach yielded a 97.9% average reduction in the number of undetected faults across the 15 designs.

This paper describes a pseudo-polynomial time algorithm for timing analysis of a class of choice-free asynchronous systems, called tightly coupled systems, with both min- and max-type timing constraints and bounded component delays. The algorithm consists of two phases: (1) long-term behavior analysis, that computes bounds on the time separation of events after the system has run for a sufficiently long period of time, and (2) startup behavior analysis, that computes time separations between events during an initial startup period after the system is powered up. The results of the analysis are conservative in the worst case; nevertheless, they are found to be exact in our experiments. To demonstrate the practical utility of the approach, an asynchronous differential equation solver chip has been modeled and analyzed using the proposed algorithm. We report results of datapath timing verification, intercontroller protocol timing verification and performance analysis of the chip using the proposed technique.

Historically, hardware acceleration technologies have either been application-specific, therefore lacking in flexibility, or fully programmable, thereby suffering from notable inefficiencies on an application-by-application basis. To address the growing need for domain-specific acceleration technologies, this paper describes a design methodology (i) to automatically generate a domain-specific coarse-grained array from a set of representative applications and (ii) to introduce limited forms of architectural generality to increase the likelihood that additional applications can be successfully mapped onto it. In particular, coarse-grained arrays generated using our approach are intended to be integrated into customizable processors that use application-specific instruction set extensions to accelerate performance and reduce energy; rather than implementing these extensions using application-specific integrated circuit (ASIC) logic, which lacks flexibility, they can be synthesized onto our reconfigurable array instead, allowing the processor to be used for a variety of applications in related domains. Results show that our array is around $2\times$ slower and $15\times$ larger than an ultimately efficient ASIC implementation, and thus far more efficient than field-programmable gate arrays (FPGAs), which are known to be 3–4 $\times$ slower and 20–40 $\times$ larger. Additionally, we estimate that our array is usually around $2\times$ larger and $2\times$ slower than an accelerator synthesized using traditional datapath merging, which has, if any, very limited flexibility beyond the design set of DFGs.

Prompted by demands for portability and low-cost packaging, the electronics industry has begun to view power consumption as a critical design criterion. As such there is a growing need for tools that can accurately predict power consumption early in the design process, many high-level power analysis models do not adequately model activity, however, leading to inaccurate results. This paper describes an activity-sensitive power analysis strategy for datapath, memory, control path, and interconnect elements. Since datapath and memory modeling has been described in a previous publication, this paper focuses mainly on a new Activity-Based Control (ABC) model and on a hierarchical interconnect analysis strategy that enables estimates of chip area as well as power consumption. Architecture-level estimates are compared to switch-level measurements based on net lists extracted from the layouts of three chips: a digital filter, a global controller, and a microprocessor. The average power estimation error is about 9% with a standard deviation of 10%, and the area estimates err on average by 14% with a standard deviation of 6%.

This paper introduces a new approach to performance-driven template mapping for high-level synthesis. Template mapping, the process of mapping high-level algorithmic descriptions to specialized hardware libraries or instruction sets, involves template matching, template selection, and clock selection. Efficient algorithms for each are presented, and novel issues such as partial matching are addressed. The paper focuses on datapath-intensive ASIC design, though the concepts are also highly applicable to compiler development. Experimental results on examples from real applications show significant improvements in throughput with limited area overhead.

The increasing demand for portable computing has elevated power consumption to be one of the most critical design parameters. A high-level synthesis system, HYPER-LP, is presented for minimizing power consumption in application specific datapath intensive CMOS circuits using a variety of architectural and computational transformations. The synthesis environment consists of high-level estimation of power consumption, a library of transformation primitives, and heuristic/probabilistic optimization search mechanisms for fast and efficient scanning of the design space. Examples with varying degree of computational complexity and structures are optimized and synthesized using the HYPER-LP system. The results indicate that more than an order of magnitude reduction in power can be achieved over current-day design methodologies while maintaining the system throughput; in some cases this can be accomplished while preserving or reducing the implementation area. >

This paper presents a new approach to datapath synthesis based on a problem-space genetic algorithm (PSGA). The proposed technique performs concurrent scheduling and allocation of functional units, registers, and multiplexers with the objective of finding both a schedule and an allocation which minimizes the cost function of the hardware resources and the total time of execution. The problem-space genetic algorithm based datapath synthesis system (PSGA-Synth) combines a standard genetic algorithm with a known heuristic to search the large design space in an intelligent manner. PSGA-Synth handles multicycle functional units, structural pipelining, conditional code and loops, and provides a mechanism to specify lower and upper bounds on the number of control steps. The PSGA-Synth was tested on a set of problems selected from the literature, as well as larger problems created by us, with promising results. PSGA-Synth not only finds the best known results for all the test problems examined in a relatively small amount of CPU time, but also has the ability to efficiently handle large problems. >

This paper describes the design and implementation of a high-level hardware compiler called Flamel. Ordinary Pascal programs are used to define the behavior required of the hardware. Flamel undertakes to find parallelism in the program, so it can produce a fast-running implementation that meets a user-specified cost bound. A number of program transformations create sections of code with more parallel computations than the original program has. A novel feature of Flamel is a method for organizing the search for the transformations that best satisfy the goal. Another new algorithm is one for "expression height reduction": rewriting an ensemble of expressions using algebraic properties in order to compute the expressions faster. An implementation of Flamel has been completed. The output is a description of a datapath and a controller, and at a sufficient level of detail so that good area and execution time figures can be estimated. On a series of tests, Flamel produces implementations of programs that would run 22 to 200 times faster than an MC68000 running the same programs, if the clock cycles were the same. The tests also show that a wide range of time-area tradeoffs are produced by varying the area constraint.