On-chip communication architectures play an important role in determining the overall performance of System-on-Chip (SoC) designs. Communication architectures should be flexible so as to offer high performance over a wide range of traffic characteristics. In particular, the resource sharing mechanism of the communication architecture, which determines how the often-conflicting requirements of different components are served, is of utmost importance. Conventional SoC architectures typically employ priority or time-division multiple-access (TDMA)-based communication architectures. However, these techniques are often inadequate. In the former, low-priority components may suffer from starvation, while in the latter, depending on the request profile, high-priority traffic may be subject to large latencies. This paper presents LOTTERYBUS, a high-performance SoC communication architecture based on new randomized on-chip communication protocols that addresses the shortcomings mentioned above. LOTTERYBUS provides each SoC component with a flexible, proportional, and probabilistically guaranteed share of the on-chip communication bandwidth. We present two variants of LOTTERYBUS. In the first variant, its architectural parameters are statically configured, leading to relatively low hardware overhead and design complexity. In the second variant, these parameters are allowed to vary dynamically, enabling more sophisticated use of LOTTERYBUS, at additional hardware cost. We have performed experiments to investigate the performance of LOTTERYBUS across a range of communication traffic characteristics. We have used LOTTERYBUS in designing a 4times4 ATM switch subsystem, and have compared its performance with conventional architectures. The results show that LOTTERYBUS provides fine-grained control over bandwidth allocation, and also provides significant reduction in average transaction latencies (up to 85%) compared to conventional architectures. Hardware implementations using a commercial 0.15-mum cell-based library indicate that the advantages provided by LOTTERYBUS are accompanied by modest hardware overheads compared to conventional architectures

This paper presents a technique for exploiting input statistics for energy and performance optimization of embedded software. The proposed technique is based on the fact that the computational complexities of programs or subprograms are often highly dependent on the values assumed by input and intermediate program variables during execution. This observation is exploited in the proposed software synthesis technique by augmenting the program with optimized versions of one or more subprograms that are specialized to, and executed under, specific input subspaces. We propose a methodology for input space-adaptive software synthesis that consists of the following steps: 1) control and value profiling of the input program; 2) application of compiler transformations in a preprocessing step; 3) identification of subprograms and corresponding input subspaces that hold the highest potential for optimization; and 4) an iterative application of known compiler transformations to realize performance and energy savings. We propose novel metrics based on the entropies of program variables to characterize subprograms and input subspaces that hold significant potential for optimization. The chosen subprograms are optimized by translating the input subspaces into value constraints on their variables, and iteratively applying known compiler transformations (that were not applicable in the context of the original program). We have evaluated input space-adaptive software synthesis by compiling the resulting optimized programs to two commercial embedded systems: an embedded system based on the Fujitsu SPARClite processor, and the Compaq iPAQ personal digital assistant (PDA) [64 MB memory, 206 MHz Intel StrongARM central processing unit (CPU)]. The energy and execution-time savings were calculated using energy-aware instruction-level simulators, as well as through direct-current measurement on the iPAQ. Our results demonstrate that the proposed technique can reduce energy by up to 54.5% (average of 30.6% and 25.6% for the SPARClite-based system and the iPAQ, respectively) while simultaneously improving performance by up to 59.6% (average of 31.3% and 31.5% for the SPARClite-based system and the iPAQ, respectively). In effect, improvements in the energy-delay product of up to 81.1% (average of 51.0% and 47.7% for the SPARClite-based system and the iPAQ, respectively) were observed. The energy savings resulting from our technique are fairly processor independent, and complementary to conventional compiler optimizations.

This paper presents a memory binding algorithm for behaviors, used in application-specific integrated circuits (ASICs), that are characterized by the presence of conditionals and deeply nested loops that access memory extensively through arrays. Unlike previous works, this algorithm examines the effects of branch probabilities and allocation constraints. First, we demonstrate, through examples, the importance of incorporating branch probabilities and allocation constraint information when searching for a performance-efficient memory binding. We also show the interdependence of these two factors and how varying one without considering the other may greatly affect the performance of the behavior. Second, we introduce a memory binding algorithm that has the ability to examine numerous bindings by employing an efficient performance estimation procedure. The estimation procedure exploits locality of execution, which is an inherent characteristic of target behaviors. This enables the performance estimation technique to look at the global impact of the different bindings, given the allocation constraints. We tested our algorithm using a number of benchmarks from the parallel computing domain. A series of experiments demonstrates the algorithm's ability to produce bindings that optimize performance, meet memory allocation constraints, and adapt to different resource constraints and branch probabilities. One limitation of our algorithm is that, in its current form, it is not well suited for system-on-a-chip synthesis where there is complex communication between general-purpose microprocessors that use custom-designed arrays. Results show that the algorithm requires 41% fewer memories with a performance loss of only 0.2% when compared to a parallel memory architecture. When compared to the best of a series of random memory bindings, the algorithm improves schedule performance by 22%.

In this paper, we present a methodology for the design of high-performance system-on-chip communication architectures. The approach is based on the addition of a layer of circuitry called the communication architecture tuner (CAT) layer around an existing communication architecture topology. The added layer provides a system with the capability of adapting to runtime variability in the communication needs of its constituent components. For example, more critical data may be handled differently, leading to lower communication latencies. The CAT associated with each component monitors its internal state, analyzes the communication transactions it generates, and "predicts" the relative importance of the transactions in terms of their impact on system-level performance metrics. It then configures the protocol parameters of the underlying communication architecture (e.g., priorities, burst modes, etc.) to best suit the system's changing communication needs. We illustrate the issues and tradeoffs involved in the design of CAT-based communication architectures, and present algorithms that automate the key steps. Experiments with example systems indicate that performance metrics (e.g., number of missed deadlines, average processing time) for systems with CAT-based communication architectures are significantly (sometimes over an order of magnitude) better than those with conventional communication architectures.

This paper proposes a novel circuit design methodology, called common-case computation (CCC)-based design, and new design automation algorithms for optimizing energy consumption and performance. The proposed techniques are applicable in conjunction with any high-level design methodology, where a structural register-transfer level (RTL) description and its corresponding scheduled behavioral (cycle-accurate functional) description are available. It is a well-known fact that in behavioral descriptions of hardware circuits (and also in software programs), a small set of computations often account for most of the computational complexity. However, in the hardware implementations (structural RTL or lower level), the common cases and the remaining computations are typically treated alike. This paper shows that identifying and exploiting common cases during the design process can lead to implementations that are much more efficient in terms of energy consumption and performance.

This paper presents a high-level design methodology, called input space adaptive design, and new design automation algorithms for optimizing energy consumption and performance. Our techniques can be applied to behaviors described in hardware description languages, predesigned register-transfer level (RTL) circuits, or in the context of traditional high-level design methodologies. An input space adaptive design exploits the well-known fact that the quality of circuits can be significantly optimized by employing algorithms and implementation architectures that adapt to input statistics. This paper shows that harnessing the principles of input space adaptive design into a structured high-level design methodology can lead to large improvements in performance and energy consumption. We illustrate the tradeoffs involved in such designs, and demonstrate the need for a systematic design methodology in order to realize the full potential for performance and energy improvements. We propose a methodology for input space adaptive design that consists of the following steps: identification of parts of the behavior that hold the highest potential for optimization, selection of input subspaces whose occurrence can lead to significant reductions in implementation complexity, and transformation of the behavior to realize performance and/or energy savings. Evaluations of performance, energy, and area characteristics of input space adaptive designs in the context of a commercial high-level design flow indicate that such designs can reduce energy consumption by up to 58.9% (average of 40.0%), and simultaneously improve performance by up to 57.5% (average of 41.8%) compared to well-optimized designs that do not employ such techniques. The energy-delay product is reduced by up to 77.9% (average of 64.8%). When the performance improvements are translated into additional energy savings through supply voltage reduction, input space adaptive designs consume up to 74.2% (average of 68.8%) less energy at the same performance. The average area overhead is only 7.4%.

The increasing complexity and software content of embedded systems has led to the frequent use of system software to help applications access hardware resources easily and efficiently. In this paper, we present a method for detailed analysis of real-time operating system (RTOS) power consumption. RTOSs form an important component of the system software layer. Despite the widespread use of, and significant role played by, RTOSs in mobile and low-power embedded systems, little is known about their power-consumption effects. This paper presents a method of producing a hierarchical energy-consumption profile for applications as they interact with an RTOS. As a proof-of-concept, we use our infrastructure to produce the power profiles for a commercial RTOS, /spl mu/C/OS-II, running several applications on an embedded system based on the Fujitsu SPARClite processor. These examples demonstrate that an RTOS can have a significant impact on power consumption. We discuss ways in which application software can be designed to use an RTOS in a power-efficient manner. We believe that this is a first step toward establishing a systematic approach to power optimization of embedded systems containing RTOSs.

Providing acceptable levels of security imposes significant computational requirements on wireless clients, servers, and network elements. These requirements are often beyond the modest processing capabilities and energy (battery) resources available on wireless clients. The relatively small sizes of wireless data transactions imply that public-key encryption algorithms dominate the security processing requirements. We propose techniques to improve the computational efficiency of public-key encryption algorithms. We focus on the modular exponentiation based encryption/decryption employed in many popular public-key algorithms. We study an extensive suite of algorithmic optimizations to the basic modular exponentiation algorithm and new advanced techniques. The proposed algorithmic optimizations lead to an "algorithm design space", across which performance varies significantly (over an order-of-magnitude). We evaluated the proposed algorithmic optimization techniques by obtaining processing times for the SSL (secure sockets layer) handshake protocol on a state-of-the-art embedded processor by using the optimal algorithm configuration and a popular conventional algorithm configuration. The results demonstrate that the optimum algorithm configuration leads to a 5.7/spl times/ improvement in SSL handshake protocol processing times. The proposed techniques are complementary to, and can be applied in conjunction with, improvements in security mechanisms and protocols, new hardware architectures, and improvements in silicon technologies.

Available register-transfer level (RTL) test generation techniques do not make a concerted effort to reduce the test application time associated with the derived tests. Chip tester memory limitations, increasing tester costs, etc., make it imperative that the issue of generating compact tests at the RTL be addressed and consolidated with the known gains of high-level testing. In this paper, the authors provide a comprehensive framework for generating compact tests for an RTL circuit. They develop a series of techniques that exploit the inherent parallelism available in symbolic test(s) derived for RTL module(s). These techniques enable them to schedule testing of multiple modules in parallel as well as perform test pipelining. In addition, the authors also present design for testability (DFT) techniques for lowering test application time. Using a maximum bipartite matching formulation, they choose a low-overhead set of test enhancements that can achieve compact tests. The authors' techniques can seamlessly plug into any generic high-level test framework. Their experimental results in the context of one such framework indicate that the proposed methodology achieves an average reduction in test application time of 54.2% for the example circuits.

Presents an efficient and accurate high level software energy estimation methodology using the concept of characterization-based macromodeling. In characterization-based macromodeling, a function or subroutine is characterized using an accurate lower level energy model of the target processor to construct a macromodel that relates the energy consumed in the function under consideration to various parameters that can be easily observed or calculated from a high-level programming language description. The constructed macromodels eliminate the need for significantly slower instruction-level interpretation or hardware simulation that is required in conventional approaches to software energy estimation. Two different approaches to macromodeling for embedded software offer distinct efficiency-accuracy characteristics: 1) complexity-based macromodeling, where the variables that determine the algorithmic complexity of the function under consideration are used as macromodeling parameters and 2) profiling-based macromodeling, where internal profiling statistics for the functions are used as the parameters in the energy macromodels.

This paper presents Lotterybus, a novel high-performance communication architecture for system-on-chip (SoC) designs. The Lotterybus architecture was designed to address the following limitations of current communication architectures: (i) lack of control over the allocation of communication bandwidth to different system components or data flows (e.g., in static priority based shared buses), leading to starvation of lower priority components in some situations, and (ii) significant latencies resulting from variations in the time-profile of the communication requests (e.g., in time division multiplexed access (TDMA) based architectures), sometimes leading to larger latencies for high-priority communications.

This paper presents an efficient and accurate high-level software energy estimation methodology using the concept of characterization-based macro-modeling. In characterization-based macro-modeling, a function or sub-routine is characterized using an accurate lower-level energy model of the target processor, to construct a macro-model that relates the energy consumed in the function under consideration to various parameters that can be easily observed or calculated from a high-level programming language description. The constructed macro-models eliminate the need for significantly slower instruction-level interpretation or hardware simulation that is required in conventional approaches to software energy estimation.

This paper presents a high-level design methodology, called input space adaptive design, and new design automation algorithms for optimizing energy consumption and performance. An input space adaptive design exploits the well-known fact that the quality of hardware circuits and software programs can be significantly optimized by employing algorithms and implementation architectures that adapt to the input statistics. We propose a methodology for such designs which includes identifying parts of the behavior to be optimized, selecting appropriate input sub-spaces, transforming the behavior, and verifying the equivalence of the original and optimized designs. Experimental results indicate that such designs can reduce energy consumption by up to 70.6% (average of 55.4%), and simultaneously improve performance by up to 85.1% (average of 58.1%), leading to a reduction in the energy-delay product by up to 95.6% (average of 80.7%), compared to well-optimized designs that do not employ such techniques.

The use of nanometer technologies is making it increasingly important to consider transient characteristics of a circuit's power dissipation (e.g., peak power, and power gradient or differential) in addition to its average power consumption. Current transient power analysis and reduction approaches are mostly at the transistor- and logic-levels. We argue that, as was the case with average power minimization, architectural solutions to transient power problems can complement and significantly extend the scope of lower-level techniques. In this work, we present a high-level synthesis approach to transient power management. We demonstrate how high-level synthesis can impact the cycle-by-cycle peak power and peak power differential for the synthesized implementation. Further, we demonstrate that it is necessary to consider transient power metrics judiciously in order to minimize or avoid area and performance overheads. In order to alleviate the limits on parallelism imposed by peak power constraints, we propose a novel technique based on the selective insertion of data monitor operations in the behavioral description. We present enhanced scheduling algorithms that can accept constraints on transient power characteristics (in addition to the conventional resource and performance constraints). Experimental results on several example designs obtained using a state-of-the-art commercial design flow and technology library indicate that high-level synthesis with transient power management results in significant benefits-peak power reductions of up to 32% (average of 25%), and peak power differential reductions of up to 59% (average of 42%)-with minimal performance overheads.

Available techniques for testing of core-based systems-on-a-chip (SOCs) do not provide a systematic means for synthesizing low-overhead test architectures and compact test solutions. In this paper, we provide a comprehensive framework that generates low-overhead compact test solutions for SOCs. First, we develop a common ground for addressing issues such as core test requirements, core access, and testing hardware additions. For this purpose, we introduce finite-state automata (FSA) for modeling tests, transparency modes, and testing hardware behavior. In many cases, the tests repeat a basic set of test actions for different test data that can again be modeled using FSA. While earlier work can derive a single symbolic test for a module in a register-transfer level (RTL) circuit as a finite-state automaton, this work extends the methodology to the system level and additionally contributes a satisfiability-based solution to the problem of applying a sequence of tests phased in time. This problem is known to be a bottleneck in testability analysis not only at the system level, but also at the RTL. Experimental results show that the system-level average area overhead for making SOCs testable with our method is only 4.5%, while achieving an average test application time reduction of 80% over recent approaches. At the same time, it provides 100% test coverage of the precomputed test sets/sequences of the embedded cores.

In this paper, we present testability analysis and optimization (TAO), a novel methodology for register-transfer level (RTL) testability analysis and optimization of RTL controller/data path circuits. Unlike existing high-level testing techniques that cater restrictively to certain classes of circuits or design styles, TAO exploits the algebra of regular expressions to provide a unified framework for handling a wide variety of circuits including application-specific integrated circuits (ASICs), application-specific programmable processors (ASPPs), application-specific instruction processors (ASIPs), digital signal processors (DSPs), and microprocessors. We also augment TAO with a design-for-test (DFT) framework that can provide a low-cost testability solution by examining the tradeoffs in choosing from a diverse array of testability modifications like partial scan or test multiplexer insertion in different parts of the circuit. Test generation is symbolic and, hence, independent of bit width. Experimental results on benchmark circuits show that TAO is very efficient, in addition to being comprehensive. The fault coverage obtained is above 99% in all cases. The average area and delay overheads for incorporating testability into the benchmarks are only 3.2% and 1.0%, respectively. The test generation time is two-to-four orders of magnitude smaller than that associated with gate-level sequential test generators, while the test application times are comparable.

The increasing complexity and software content of embedded systems has led to the frequent use of system software that helps applications access underlying hardware resources easily and efficiently. In this paper, we analyze the power consumption of real-time operating systems (RTOSs), which form an important component of the system software layer. Despite the widespread use of, and significant role played by, RTOSs in mobile and low-power embedded systems, little is known about their power consumption characteristics. This work presents the power profiles for a commercial RTOS, μC/OS, running several applications on an embedded system based on the Fujitsu SPARClite processor. Our work demonstrates that the RTOS can consume a significant fraction of the system power and, in addition, impact the power consumed by other software components. We illustrate the ways in which application software can be designed to use the RTOS in a power-efficient manner. We believe that this work is a first step towards establishing a systematic approach to RTOS power modeling and optimization.

In this chapter, we present a general methodology for the design of custom system-on-chip communication architectures. Our technique is based on the addition of a layer of circuitry, called the Communication Architecture Tuner (CAT), around any existing communication architecture topology. The added layer enhances the ability of the system to adapt to changing communication needs of its constituent components. For example, more critical data may be handled differently, leading to lower communication latencies. The CAT monitors the internal state and communication transactions of each component, and “predicts” the relative importance of each communication transaction in terms of its potential impact on different system-level performance metrics. It then configures the protocol parameters of the underlying communication architecture (e.g., priorities, DMA modes,etc.) to best suit the system's changing communication needs.

Available register-transfer level (RTL) test generation techniques do not make a concerted effort to reduce the test application time associated with the derived tests. Chip tester memory limitations, increasing tester costs, etc., make it imperative that the issue of generating compact tests at the RTL be addressed and consolidated with the known gains of high-level testing. In this paper, we provide a comprehensive framework for generating compact tests for an RTL circuit. We develop a series of techniques that exploit the inherent parallelism available in symbolic test(s) derived for RTL module(s). These techniques enable us to schedule testing of multiple modules in parallel as well as perform test pipelining. In addition, we also present design for testability (DFT) techniques for lowering test application time. Using a maximum bipartite matching formulation, we choose a low-overhead set of test enhancements that can achieve compact tests. Our techniques can seamlessly plug into any generic high-level test framework. Our experimental results in the context of one such framework indicate that the proposed methodology achieves an average reduction in test application time of 61.1% for the example circuits.

This paper addresses the problem of synthesizing fault-secure controller/data path circuits from behavioral specifications. These circuits are guaranteed to either produce the correct output, or to flag an error. We use an iterative improvement-based behavioral synthesis framework that performs functional unit selection, clock selection, scheduling, and resource sharing with the aim of minimizing the area of the synthesized circuit, while allowing multicycling, chaining, and functional unit pipelining. We present a dynamic comparison selection algorithm that can be used during behavioral synthesis to determine which intermediate results in the computation need to be secured in order to enable maximal resource sharing. Previous work on synthesizing fault-secure data paths has focused on ensuring that aliasing (a condition when the circuit produces an incorrect output and does not flag an error) cannot occur in any part of the design. We demonstrate that such an approach can lead to unnecessarily large overheads. In order to alleviate the overheads incurred for fault security, our behavioral synthesis framework uses ALiasing Probability analysiS (ALPS) in order to identify resource sharing configurations that reduce area while introducing a very low probability of aliasing (of the order of 10/sup -10/ for a bit-width of 32) in the resultant data path. Experimental results performed for several behavioral descriptions demonstrate that our techniques synthesize more compact circuits than techniques available in the literature, e.g., double modular redundancy or zero-aliasing techniques.

Speculative execution refers to the execution of parts of a computation before the execution of the conditional operations that decide whether they need to be executed. It has been shown to be a promising technique for eliminating performance bottlenecks imposed by control flow in hardware and software implementations alike. In this paper, we present techniques to incorporate speculative execution in a fine-grained manner into scheduling of control-flow-intensive behavioral descriptions. We demonstrate that failing to take into account information such as resource constraints and branch probabilities can lead to significantly suboptimal performance. We also demonstrate that it may be necessary to speculate simultaneously along multiple paths, subject to resource constraints, in order to minimize the delay overheads incurred when prediction errors occur. Experimental results on several benchmarks show that our speculative scheduling algorithm can result in significant (up to seven-fold) improvements in performance (measured in terms of the average number of clock cycles) as compared to scheduling without speculative execution. Also, the best and worst case execution times for the speculatively performed schedules are the same as or better than the corresponding values for the schedules obtained without speculative execution.

Components used as building blocks (e.g., functional units) in conventional HLS techniques are assumed to have fixed latency values. Variable-latency units exhibit the property that the number of cycles taken to compute their outputs varies depending on the input values. While variable-latency units offer potential for performance improvement, we demonstrate that realization of this potential requires that HLS be adapted suitably (sub-optimal use of variable-latency units can lead to performance degradation, or unnecessarily high area overheads). Our techniques to incorporate variable-latency units into HLS ensure that the performance improvement is maximized, while minimizing area overheads or satisfying resource constraints. These techniques are not restricted to specific HLS tools/algorithms, and can be plugged in to any generic HLS system. Since area overheads may still be incurred due to the use of variable-latency units, we present a novel technique, based on the concept of reduced variable-latency units, to further reduce area overheads. Reduced variable-latency units only implement the low-latency case behavior of complete variable-latency units. We demonstrate that the use of reduced variable-latency units significantly reduces area overheads, and sometimes results in improvements in performance while simultaneously reducing the area of the register transfer level implementation. Experimental results show that the proposed variable-latency-unit-based synthesis techniques achieve a performance improvement of up to 1.6/spl times/ (average of 1.4/spl times/) over a state-of-the-art HLS tool, with minimal area overheads (average of 5.3%). The use of reduced variable-latency units leads to a performance improvement of up to 1.6/spl times/ (average of 1.3/spl times/), with a simultaneous area reduction of up to 17.9% (10.6% on the average).

In this paper, we present TAO-BIST, a framework for testing register-transfer level (RTL) controller-datapath circuits using built-in self-test (BIST). Conventional BIST techniques at the RTL generally introduce more testability hardware than is necessary thereby causing unnecessary area, delay and power overheads. They have typically been applied to only application-specific integrated circuits (ASICs). TAO-BIST adopts a three-phased approach to provide an efficient BIST framework at the RTL. In the first phase, we identify and add an initial set of test enhancements to the given circuit. In the second phase, we use regular-expression based high-level symbolic testability analysis of a BIST model of the circuit to completely encapsulate justification/propagation information for the modules under test. The regular expressions so obtained are then used to construct a Boolean function in the final phase for determining a test enhancement solution that meets delay constraints with minimal area overheads. Our method is applicable to a wide spectrum of circuits including ASICs, application-specific programmable processors (ASPPs), application-specific instruction processors (ASIPs), digital signal processors (DSPs), and microprocessors. Experimental results on a number of benchmark circuits show that high fault coverage (>99%) can be obtained with our scheme. The average area and delay overheads due to TAO-BIST are only 6.0% and 1.5%, respectively, for a bit-width of 16. These overheads decrease further with an increase in bit-width. The test application time to achieve the high fault coverage for the whole controller-datapath circuit is also quite low.

This paper presents a design methodology, called common-case computation (CCC), and new design automation algorithms for optimizing power consumption or performance. The proposed techniques are applicable in conjunction with any high-level design methodology where a structural register-transfer level (RTL) description and its corresponding scheduled behavioral (cycle-accurate functional RTL) description are available. It is a well-known fact that in behavioral descriptions of hardware (also in software), a small set of computations (CCCs) often accounts for most of the computational complexity. However, in hardware implementations (structural RTL or lower level), CCCs and the remaining computations a typically treated alike. This paper shows that identifying and exploiting CCCs during the design process can lead to implementations that are much more efficient in terms of power consumption or performance. We propose a CCC-based high-level design methodology with the following steps: extraction of common-case behaviors and execution conditions from the scheduled description, simplification of the common-case behaviors in a stand-alone manner, synthesis of common-case detection and execution circuits from the common-case behaviors, and composing the original design with the common-case circuits, resulting in a CCC-optimized design. We demonstrate that CCC-optimized designs reduce power consumption by up to 91.5%, or improve performance by up to 76.6% compared to designs derived without special regard for CCCs.

The paper presents a memory binding algorithm for behaviors that are characterized by the presence of conditionals and deeply-nested loops that access memory extensively through arrays. Unlike previous works, this algorithm examines the effects of branch probabilities and allocation constraints. First, we demonstrate through examples, the importance of incorporating branch probabilities and allocation constraint information when searching for a performance-efficient memory binding. We also show the interdependence of these two factors and how varying one without considering the other may greatly affect the performance of the behavior. Second, we introduce a memory binding algorithm that has the ability to examine numerous bindings by employing an efficient performance estimation procedure. The estimation procedure exploits locality of execution, which is an inherent characteristic of target behaviors. This enables the performance estimation technique to look at the global impact of the different bindings, given the allocation constraints. We tested our algorithm using a number of benchmarks from the parallel computing domain. A series of experiments demonstrates the algorithm's ability to produce bindings that optimize performance, meet memory allocation constraints, and adapt to different resource constraints and branch probabilities. Results show that the algorithm requires 37% fewer memories with a performance loss of only 0.3% when compared to a parallel memory architecture. When compared to the best of a series of random memory bindings, the algorithm improves schedule performance by 21%.

Available techniques for testing core-based systems-on-a-chip (SOCs) do not provide a systematic means for synthesising low-overhead test architectures and compact test solutions. In this paper, we provide a comprehensive framework that generates low-overhead compact test solutions for SOCs. First, we develop a common ground for addressing issues such as core test requirements, core access and test hardware additions. For this purpose, we introduce finite-state automata for modeling tests, transparency modes and test hardware behavior. In many cases, the tests repeat a basic set of test actions for different test data which can again be modeled using finite-state automata. While earlier work can derive a single symbolic test for a module in a register-transfer level (RTL) circuit as a finite-state automaton, this work extends the methodology to the system level, and, additionally contributes a satisfiability-based solution to the problem of applying a sequence of tests phased in time. This problem is known to be a bottleneck in testability analysis not only at the system level, but also at the RTL. Experimental results show that the system-level average area overhead for making SOCs testable with our method is only 4.4%, while achieving an average test application time reduction of 78.5% over recent approaches. At the same time, it provides 100% test coverage of the precomputed test sets/sequences of the embedded cores.

In this paper, we present TAO-BIST, a framework for testing register-transfer level (RTL) controller-datapath circuits using built-in self-test (BIST). Conventional BIST techniques at the RTL generally introduce more testability hardware than is necessary, thereby causing unnecessary area, delay and power overheads. They have typically been applied to only application-specific integrated circuits (ASICs). TAO-BIST adopts a three-phased approach to provide an efficient BIST framework at the RTL. In the first phase, we identify and add an initial set of test enhancements to the given circuit. In the second phase, we use regular-expression based high-level symbolic testability analysis of a BIST model of the circuit to completely encapsulate justification/propagation information for the modules under test. The regular expressions so obtained are then used to construct a Boolean function in the final phase for determining a test enhancement solution that meets delay constraints with minimal area overheads. Our method is applicable to a wide spectrum of circuits including ASICs, application-specific programmable processors (ASPPs), application-specific instruction processors (ASIPs), digital signal processors (DSPs) and microprocessors. Experimental results on a number of benchmark circuits show that high fault coverage (>99%) can be obtained with our scheme. The average area and delay overheads due to TAO-BIST are only 6.0%, and 1.5%, respectively. The test application time to achieve the high fault coverage for the whole controller-datapath circuit is also quite low.

In this paper, we present a comprehensive high-level synthesis system that is geared toward reducing power consumption in control-flow intensive as well as data-dominated circuits. An iterative improvement framework allows the system to search the design space by examining the interaction between the different high-level synthesis tasks. In addition to incorporating traditional high-level synthesis tasks such as scheduling, module selection and resource sharing, we introduce a new optimization that performs power-conscious structuring of multiplexer networks, which are predominant in control-flow intensive circuits. The scheduler employed is capable of loop optimizations within and across loop boundaries. We also introduce a fast power estimation technique, based on switching activity matrices, to drive the synthesis process. Experimental results for a number of control-flow intensive and data-dominated benchmarks demonstrate power reduction of up to 62% (58%) when compared to V/sub dd/-scaled area-optimized (delay-optimized) designs. The area overheads over area-optimized designs are less than 39%, whereas the area savings over delay-optimized designs are up to 40%.

We present a technique for synthesizing power- as well as area-optimized circuits from hierarchical data flow graphs under throughput constraints. We allow for the use of complex register-transfer level (RTL) modules, such as fast Fourier transforms (FFT's) and filters, as building blocks for the RTL circuit, in addition to simple RTL modules such as adders and multipliers. Unlike past techniques in the area, we also customize the complex RTL modules to match the environment in which they find themselves. We present a fast and efficient algorithm for mapping multiple behaviors onto the same RTL module during the course of synthesis, thus allowing our synthesis system to explore previously unexplored regions of the design space. These techniques are at the core of an iterative improvement based approach which can accept temporary degradation in solution quality in its quest for a globally optimal solution. The moves in our iterative improvement procedure explore optimizations along different dimensions such as functional unit selection, resource allocation, resource sharing, resource splitting, and selection and resynthesis of complex RTL modules. These interrelated optimizations are dynamically traded off with each other during the course of synthesis, thus exploiting the benefits that arise from their interaction. The synthesis framework also tackles other related high-level synthesis tasks such as scheduling, clock selection, and V/sub dd/ selection. Experimental results demonstrate that our algorithm produces circuits whose area and power consumption are comparable to or better than those produced using flattened synthesis, within much shorter CPU times.

In this paper, we present an algorithm for the application of a general class of transformations to control-flow intensive behavioral descriptions. Our algorithm is based on the observation that incorporation of scheduling information can help guide the selection and application of candidate transformations, and significantly enhance the quality of the synthesized solution. The efficacy of the selected throughput and power optimizing transformations is enhanced by the ability of our algorithm to transcend basic blocks in the behavioral description. This ability is imparted to our algorithm by a general technique we have devised. Our system currently supports associativity, commutativity, distributility, constant propagation, code motion, and loop unrolling. It is integrated with a scheduler which performs implicit loop unrolling and functional pipelining, and has the ability to parallelize the execution of independent iterative constructs, whose bodies can share resources. Other transformations can easily be incorporated within the framework. We demonstrate the efficacy of our algorithm by applying it to several commonly available benchmarks. Upon synthesis, behaviors transformed by the application of our algorithm showed, on an average, a 2.5-fold improvement in throughput over an existing transformation algorithm, and a 57.6% improvement in power over designs produced without the benefit of our algorithm.

In this paper, we present a novel scheduling algorithm targeted toward minimizing the average execution time of control-flow intensive behavioral descriptions. Our algorithm uses a control/data flow graph model, which preserves the parallelism inherent in the application. It explores previously unexplored regions of the solution space by its ability to overlap the schedules of independent iterative constructs, whose bodies share resources. It also incorporates well known optimization techniques like loop unrolling in a natural fashion. This is made possible by a general loop-handling technique, which we have devised. Application of the algorithm to several common benchmarks demonstrates up to 4.8-fold improvement in expected schedule length over existing scheduling algorithms, without paying a price in terms of the best and worst case schedule lengths required to execute the behavioral description (in fact, frequently, the best/worst case schedule lengths are also better for our algorithm).

Hardware-software co-synthesis starts with an embedded-system specification and results in an architecture consisting of hardware and software modules to meet performance, power, and cost goals. Embedded systems are generally specified in terms of a set of acyclic task graphs. In this paper, we present a co-synthesis algorithm COSYN, which starts with periodic task graphs with real-time constraints and produces a low-cost heterogeneous distributed embedded-system architecture meeting these constraints. It supports both concurrent and sequential modes of communication and computation. It employs a combination of preemptive and nonpreemptive static scheduling. It allows task graphs in which different tasks have different deadlines. It introduces the concept of an association array to tackle the problem of multirate systems. It uses a new task-clustering technique, which takes the changing nature of the critical path in the task graph into account. It supports pipelining of task graphs and a mix of various technologies to meet embedded-system constraints and minimize power dissipation. In general, embedded-system tasks are reused across multiple functions. COSYN uses the concept of architectural hints and reuse to exploit this fact. Finally, if desired, it also optimizes the architecture for power consumption. COSYN produces optimal results for the examples from the literature while providing several orders of magnitude advantage in central processing unit time over an existing optimal algorithm. The efficacy of COSYN and its low-power extension COSYN-LP is also established through their application to very large task graphs (with over 1000 tasks).

In this paper, we present a power-management methodology targeted toward high-level synthesis of data-dominated behavioral descriptions. It is founded on the observation that variable assignment can significantly affect power-management opportunities in the synthesized architecture, i.e., variable assignment determines whether or not spurious operations get executed by functional units in the architecture. We introduce perfectly power managed architectures, whose functional units do not execute any spurious operations. We present a variable assignment technique which, when used in high-level synthesis, produces architectures which are perfectly power-managed. Unlike many previously proposed power-management techniques, our method does not add latches or any other circuitry in front of functional units or registers and is, therefore, free of the attendant performance penalty. Experimental results indicate savings of up to 52.5% (average 23.0%) in power consumption over already power-optimized architectures. The area overheads due to our technique are also low and averaged 2.5% for our examples.

In this paper, we present an algorithm for the application of a general class of transformations to control-flow intensive behavioral descriptions. Our algorithm is based on the observation that incorporation of scheduling information can help guide the selection and application of candidate transformations, and significantly enhance the quality of the synthesized solution. The efficacy of the selected throughput and power optimizing transformations is enhanced by the ability of our algorithm to transcend basic blocks in the behavioral description. This ability is imparted to our algorithm by a general technique we have devised. Our system currently supports associativity, commutativity, distributivity, constant propagation, code motion, and loop unrolling. It is integrated with a scheduler which performs implicit loop unrolling and functional pipelining, and has the ability to parallelize the execution of independent iterative constructs whose bodies can share resources. Other transformations can easily be incorporated within the framework. We demonstrate the efficacy of our algorithm by applying it to several commonly available benchmarks. Upon synthesis, behaviors transformed by the application of our algorithm showed up to 6-fold improvement in throughput over an existing transformation algorithm, and up to 4.5-fold improvement in power over designs produced without the benefit of our algorithm.

We present a technique for synthesizing power- as well as area-optimized circuits from hierarchical data flow graphs under throughput constraints. We allow for the use of complex RTL modules, such as FFTs and filters, as building blocks for the RTL circuit, in addition to simple RTL modules such as adders and multipliers. Unlike past techniques in the area, we also customize the complex RTL modules to match the environment in which they find themselves. We present a fast and efficient algorithm for mapping multiple behaviors onto the same RTL module during the course of synthesis, thus allowing our synthesis system to explore previously unexplored regions of the design space. These techniques are at the core of an iterative improvement based approach which can accept temporary degradation in solution quality in its quest for a globally optimal solution. The moves in our iterative improvement procedure explore optimizations along different dimensions such as functional unit selection, resource allocation, resource sharing, resource splitting, and selection and resynthesis of complex RTL modules. These inter-related optimizations are dynamically traded off with each other during the course of synthesis, thus exploiting the benefits that arise from their interaction. The synthesis framework also tackles other related high-level synthesis tasks such as scheduling, clock selection, and Vdd selection. Experimental results demonstrate that our algorithm produces circuits whose area and power consumption are comparable to or better than those produced using flattened synthesis, within much shorter CPU times. The efficacy of our algorithm in the power-optimization mode is illustrated by the fact that it produces circuits that consume upto 6.7 times less power than area-optimized circuits working at 5 Volts at area overheads not exceeding 50%.

Speculative execution refers to the execution of parts of a computation before the execution of the conditional operations that decide whether it needs to be executed. It has been shown to be a promising technique for eliminating performance bottlenecks imposed by control flow in hardware and software implementations alike. In this paper, we present techniques to incorporate speculative execution in a fine-grained manner into scheduling of control-flow intensive behavioral descriptions. We demonstrate that failing to take into account information such as resource constraints and branch probabilities can lead to significantly sub-optimal performance. We also demonstrate that it may be necessary to speculate simultaneously along multiple paths, subject to resource constraints, in order to minimize the delay overheads incurred when prediction errors occur. Experimental results on several benchmarks show that our speculative scheduling algorithm can result in significant (upto seven-fold) improvements in performance (measured in terms of the average number of clock cycles) as compared to scheduling without speculative execution. Also, the best and worst case execution times for the speculatively performed schedules are the same as or better than the corresponding values for the schedules obtained without speculative execution.

In this paper, we present a comprehensive high-level synthesis system that is geared towards reducing power consumption in control-flow intensive circuits. An iterative improvement algorithm is at the heart of the system. The algorithm searches the design space by handling scheduling, module selection, resource sharing and multiplexer network restructuring simultaneously. The scheduler performs concurrent loop optimization and implicit loop unrolling. It minimizes the expected number of cycles of the schedule without compromising on the minimum and maximum schedule lengths. A fast simulation technique based on trace manipulation aids power estimation in driving synthesis in the right direction. Experimental results demonstrate power reduction of up to 85% with minimal overhead in area over area-optimized designs operating at 5 V.

We present techniques to transform scheduled descriptions of control-flow intensive designs to facilitate power management. We investigate the factors that inhibit the application of power management in synthesized RTL implementations. Based on these insights, we present transformation techniques based on the concepts of variable protection, variable re-naming and re-assignment, and limited controller state memory insertion that result in inherently powermanaged architectures. Our transformation techniques can be easily used in conjunction with any existing resource sharing algorithm or in the framework of existing high-level synthesis tools. Experimental results on control-flow intensive designs indicated reductions of upto 76.6% (35.6% on average) in power consumption at area overheads not exceeding 10.1% (1.1% on average) over already poweroptimized designs.

Application domains like signal and image processing, mul-timedia and networking protocols involve processing of huge amounts of data stored in memory modules. The behavioral de-scriptions of these applications may contain a large number of array references for data accesses. Dependencies between array accesses cause bottlenecks in the derivation of high-performance schedules. In this paper, we introduce a scheduling-integrated technique to identify and remove these bottlenecks. We first demonstrate that there is a significant loss in the quality of a schedule if these bottlenecks are not taken into account by the scheduler. We then propose a technique to overcome these bottle-necks by introducing new operations in the schedule called veri-fication operations. Experimental results on several benchmarks show that a scheduler powered by our technique demonstrates a two-fold improvement in performance (measured in terms of the average number of clock cycles) over a recently-introduced sched-uler for control-flow intensive behavioral descriptions, called Wavesched. Wavesched itself has a two-fold performance advan-tage over traditional methods such as path-based scheduling and loop-directed scheduling. Also, the best- and worst-case execution times for the enhanced schedules obtained by our method are usu-ally equal to or much less than the corresponding values for the execution times obtained by previous schedulers. 1

In this paper, we present a power estimation technique for control-flow intensive designs that is tailored towards driving iterative high-level synthesis systems, where hundreds of architectural trade-offs are explored and compared. Our method is fast and relatively accurate. The algorithm utilizes the behavioral information to extract branch probabilities, and uses these in conjunction with switching activity and circuit capacitance information, to estimate the power consumption of a given architecture.

In this paper, we present TAO, a novel methodology for high-level testability analysis and optimization of register-transfer level controller/data path circuits. Unlike existing high-level testing techniques that cater restrictively to certain classes of circuits or design styles, TAO exploits the algebra of regular expressions to provide a unified framework for handling a wide variety of circuits including application-specific integrated circuits, application-specific programmable processors, application-specific instruction processors, digital signal processors and microprocessors. We also augment TAO with a design-for-test framework that can provide a low-cost testability solution by examining the trade-offs in choosing from a diverse array of testability modifications like partial scan or test multiplexer insertion in different parts of the circuit. Test generation is symbolic and, hence, independent of bit-width. Experimental results on benchmark circuits show that TAO is very efficient, in addition to being comprehensive. The fault coverage obtained is above 99% in all cases. The average area and delay overheads for incorporating testability into the benchmarks are only 3.3% and 1.1%, respectively. The test application time is comparable to that associated with gate-level sequential test generators.

Hardware-software co-synthesis is the process ofpartitioning an embedded system specification into hardware andsoftware modules to meet performance, power and cost goals. Inthis paper, we present a co-synthesis algorithm which starts withperiodic task graphs with real-time constraints and produces a low-costheterogeneous distributed embedded system architecturemeeting the constraints. The algorithm has the following features:1) it allows the use of multiple types of processing elements (PEs)and inter-PE communication links, where the links can take variousforms (point-to-point, bus, local area network (LAN), etc.), 2) itsupports both concurrent and sequential modes of communicationand computation, 3) it allows both preemptive and non-preemptivescheduling, 4) it employs the concept of an association array totackle the problem of multi-rate systems (which are commonlyfound in multimedia applications), 5) it uses a scheduler based ondynamic deadline-based priority levels for accurate performanceestimation of a co-synthesis solution, 6) it uses a new taskclustering technique which takes the dynamic nature of the criticalpath, and the existence of multiple critical paths in the task graphinto account, and 7) if desired, it also optimizes the architecture forpower consumption (we are not aware of any other co-synthesisalgorithm that optimizes power). Application of the proposedalgorithm to examples from the literature and real-life telecomtransport systems shows its efficacy.

Presents a novel scheduling algorithm targeted towards minimizing the average execution time of control-flow intensive behavioral descriptions. Our algorithm uses a control-data flow graph (CDFG) model, which preserves the parallelism inherent in the application. It explores previously unexplored regions of the solution space through its ability to overlap the schedules of independent iterative constructs whose bodies share resources. It also incorporates well-known optimization techniques like loop unrolling in a natural fashion. This is made possible by a general loop-handling technique which we have devised. Application of the algorithm to several common benchmarks demonstrates up to 4.8-fold improvement in expected schedule length over existing scheduling algorithms, without paying a price in terms of the best- and worst-case schedule lengths required to execute the behavioral description (in fact, frequently, the best/worst-case schedule lengths are also better for our algorithm).