The complexity of current day embedded systems is steadily on the rise due to innovative content consumption applications. Embedded systems have to be adaptable and scalable to meet the unique resource demands of such applications to deliver satisfactory performance. Effective sharing of system resources by content consumption applications is imperative for user satisfaction. In this paper, we address the challenge of coming up with a design for an efficient scheduler for Multiple Application and Multi-threaded polymorphic embedded system with user satisfaction as its objective function. Randomly generated application graphs serve as benchmarks to evaluate the performance of the proposed polymorphic scheduler framework. We also discuss the impact of our scheduler on the user satisfaction of a multimedia application as a real world case study. The performance enhancements obtained using the proposed greedy polymorphic thread scheduling algorithm are demonstrated by comparison against classical approaches such as First Come First Serve(FCFS) and priority scheduling schemes.

Partial reconfiguration technology of programmable devices, such as FPGA, enables the virtualization of hardware circuit by temporal multiplexing of active parts (logic slices). An immediate consequence of virtualization is the increase in cardinality of the don't care set associated with a logic slice. In this paper, we present a logic slicing methodology that exploits the enhanced don't care set to optimize the hardware circuit for reduction in area. We show that reduced area dynamic reconfigurable slices can be generated for combinational circuits with minimal effect on the critical path. The results reported for MCNC logic synthesis benchmark circuits show an average 40% reduction in area for logic slices.

Power consumption has become a critical design criterion for integrated circuits given the growing importance of portable battery-operated devices. A typical CMOS gate driven by power supply (VDD), draws energy equal to CLVDD2during every cycle of operation. We propose a new approach to recycle the charge with an adiabatic charge pump that moves the slower adiabatic components away from the critical path of logic. The critical path of the system, and hence the delay, do not change. This is achieved by overlapping the adiabatic charge pump delays with the computing path logic delays. Many embedded high performance applications such as digital signal processing (DSP), which exhibit datapath parallelism, are ideal candidates for this scheme. The proposed method has been implemented in DSP computations. SPICE simulations-based results indicate that the proposed scheme reduces energy consumption in these DSP circuits by as much as 18% (on average 9.94%) with no perceptible loss in performance. The area penalty for these energy savings are in the 1%-2% range, The leakage energy reduction in 45-nm BPTM averages 46%.

Many embedded systems exhibit temporally and behaviorally disjoint behavior slices. When such behaviors are captured by state machines, the current design flow will capture it as a union of all the behavior slices, and map it using traditional state assignment followed by logic synthesis. Such implementations costs are proportional to the union of all the behavior slices (in area, energy and delay). We propose to use self-modifying finite automata (SMFA), that have been studied from complexity-theoretic perspective, for expressing and implementing such adaptive behaviors in embedded systems. Towards this end, we present an implementation architecture for SMFAs. We compare the area, time and energy costs of SMFA implementations with the classical logic space (FSM) implementations for four adaptive behaviors.

Software obfuscation is defined as a transformation of a program P into T(P) such that the whitebox and blackbox behaviors of T(P) are computationally indistinguishable. However, robust obfuscation is impossible to achieve with the existing software only solutions. This results from the power of the adversary model in digital rights management systems, which is significantly more than in the traditional security scenarios. The adversary has complete control of the computing node - supervisory privileges along with the full physical as well as architectural object observational capabilities. In essence, this makes the operating system (or any other layer around the architecture) untrustworthy. Thus, the trust has to be provided by the underlying architecture. In this paper, we develop an architecture to support 3D obfuscation through the use of well-known cryptographic methods and show how it provides copy-protection, IP-protection, and tamper-resistance.

A software obfuscator is a program O to transform a source program P for protection against malicious reverse engineering. O should be correct (O(P) has same functionality with P), resilient (O(P) is resilient against attacks), and effective (O(P) is not too much slower than P). In this paper we describe the design of an obfuscator which consists of two parts. The first part extracts the control flow information from the program and saves it in another process named Monitor-process. The second part protects Monitor-process converting it into an Aucsmith like self-modifying version. We prove the correctness of the obfuscation scheme. We assess its resilience and efficiency to show that both are This supports the claim that our approach is practical.

Existing schemes for cache energy optimization incorporate a limited degree of dynamic associativity: either direct mapped or full available associativity (say 4-way). In this paper, we explore a more general design space for dynamic associativity (for a 4-way associative cache, consider 1-way, 2-way, and 4-way associative accesses). The other major departure is in the associativity control mechanism. We use the actual instruction level parallelism exhibited by the instructions surrounding a given load to classify it as an IPC k load (for 1/spl les/k/spl les/IW with an issue width of IW) in a superscalar architecture. The lookup schedule is fixed in advance for each IPC classifier 1/spl les/k/spl les/IW. The schedules are as way-disjoint as possible for load/stores with different IPC classifications. The energy savings over SPEC2000 CPU benchmarks average 28.6% for a 32 kB, 4-way, L-1 data cache. The resulting performance (IPC) degradation from the dynamic way schedule is restricted to less than 2.25%, mainly because IPC based placement ends up being an excellent classifier.

The rename map table (RMT) access and the dependence check logic (DCL) delays scale unfavorably "with the dispatch width (DW) of a superscalar processor. It is a well-known program property that the results of most instructions are consumed within the following 4-6 instruction window. This program behavior can be exploited to reduce the rename delay by reducing the number of read/write ports in the RMT to significantly below the current 3 * DW. We propose an algorithm to dynamically allocate reduced number of RMT ports to instructions in the current dispatch window, matching dispatch resources to average needs rather than peak needs. This results in shorter RMT access delays as well as in lower energy in the dispatch stage. The IPC reduction due to rename map table read/write port contention in the proposed scheme stays within 2-4%. The cycle time saved can also be leveraged to support wider dispatch in the same cycle time in order to offset this degradation.

The task of an Internet router is to scan the IP headers for the destination address and make a routing decision based on the information. If the processing capability of a router is enhanced to support computation on a datagram, some of the host computation may be delegated to the intermediate routers. The instructions about how to do the processing may be provided by the end hosts. We propose a reliable transport layer protocol, Intermediate Processing Protocol (IPP) for processing within the Internet. The protocol design makes provisions for connection set up handshake, router reservation, intermediate processing, data acknowledgement, buffering and retransmission, flow and congestion control, ordered delivery and security issues.

A general-purpose computing processor performs a wide range of functions. Although the performance of general-purpose processors has been steadily increasing, certain software technologies like multimedia and digital signal processing applications demand ever more computing power. If the computing resources are variable to the needs of an application, a better performance can be achieved. Adaptive Balanced Computing (ABC) performs a dynamic resource configuration of on-chip cache memory by converting the cache into a specialized computing unit. With a small amount of additional logic and slightly modified microarchitecture, a part of the cache memory can be configured to perform specialized computations in a conventional processor. In this paper, we evaluate the ABC using RFCs in various cache organizations to see the impact of resource reconfiguration. The simulations with multimedia and DSP applications show that the resource configuration speedups ranging from 1.04X to 3.94X in overall applications and from 2.61X to 27.4X in the core computations.

In a superscalar pipeline, the dispatch stage performs register renaming, which involves map table lookup logic and dependence check logic. Both subtasks do not scale well with the dispatch width of the processor. The number of comparators necessary for the dependence check logic grows quadratically with the dispatch width of the processor. The rename map table's word line capacitance scales linearly with the dispatch width. This paper proposes and evaluates schemes to alleviate both these problems. By performing the dependence check hierarchically in two stages, the number of comparators required in the dependence check logic is reduced from quadratic to linear in the dispatch width. This scheme is also scalable with the dispatch width by allowing a dispatch of DW/sup 2/ instructions in the same processor cycle time that the current microprocessors use to dispatch DW instructions. Simple scalar based simulations indicate a performance penalty of less than 10% over Spec95 CPU benchmarks due to the extra cycle introduced. The second scheme started with an objective of utilizing speculation in rename and dependence information. The only beneficial subspace of this speculation appears to be the reuse of rename information of those instructions whose source operands are produced either in their own basic block or in the immediately preceding basic block. By storing rename information of such instructions in a rename cache, these instructions can be dispatched directly to the reservation stations if the program takes the same path again. The performance improvement due to the rename cache is approximately 7% for SPEC95 integer benchmarks.

A considerable portion of a microprocessor chip is dedicated to cache memory. However, not all applications need all the cache storage all the time, especially the computing bandwidth-limited applications. In addition, some applications have large embedded computations with a regular structure. Such applications may be able to use additional computing resources. If the unused portion of the cache could serve these computation needs, the on-chip resources would be utilized more efficiently. This presents an opportunity to explore the reconfiguration of a part of the cache memory for computing. Thus, we propose adaptive balanced computing (ABC)-dynamic resource configuration on demand from application-between memory and computing resources. In this paper, we present a cache architecture to convert a cache into a computing unit for either of the following two structured computations: finite impulse response and discrete/inverse discrete cosine transform. In order to convert a cache memory to a function unit, we include additional logic to embed multibit output lookup tables into the cache structure. The experimental results show that the reconfigurable module improves the execution time of applications with a large number of data elements by a factor as high as 50 and 60.

A considerable portion of a chip is dedicated to a cache memory in a modern microprocessor chip. However, some applications may not actively need all the cache storage, especially the computing bandwidth limited applications. Instead, such applications may be able to use some additional computing resources. If the unused portion of the cache could serve these computation needs, the on-chip resources would be utilized more efficiently. This presents an opportunity to explore the reconfiguration of a part of the cache memory for computing. In this paper, we present a cache architecture to convert a cache into a computing unit for either of the following two structured computations, FIR and DCT/IDCT. In order to convert a cache memory to a function unit, we include additional logic to embed multi-bit output LUTs into the cache structure. Therefore, the cache can perform computations when it is reconfigured as a function unit. The experimental results show that the reconfigurable module improves the execution time of applications with a large number of data elements by a large factor (as high as 50 and 60). In addition, the area overhead of the reconfigurable cache module for FIR and DCT/IDCT is less than the core area of those functions. Our simulations indicate that a reconfigurable cache does not take a significant delay penalty compared with a dedicated cache memory. The concept of reconfigurable cache modules can be applied at Level-2 caches instead of Level-1 caches to provide an active-Level-2 cache similar to active memories.

Branches are one of the main impediments to achieving maximum instruction-level parallelism. Branch prediction along with speculative execution is the main, incumbent methodology to hide branch stalls. Branch decoupled architectures offer an alternate way of reducing branch penalty. This paper presents a combination of the two methodologies, to show that they can coexist and may provide better performance than processors with conventional branch prediction techniques, but equivalent hardware resources. A trace based evaluation is presented, and with three different branch prediction techniques, it is shown that over twelve of the SPEC'95 CPU benchmarks, speculative branch decoupling performs significantly better than branch prediction with speculative execution, in all the cases. Since a trace based approach has its limitations, the study is a limited one, but makes a strong case for further research in this area.

Most custom computing machine (CCM) design has centered around field-programmable gate array (FPGA) technology and rapid prototyping applications. FPGAs are reconfigured to map parts of the application. The performance of an FPGA when used as a virtual hardware engine depends on its reconfiguration granularity. We study the striped FPGA and propose a hybrid mechanism to process a large amount of data using a combination of data and configuration caching.

The number of transistors on chip has dramatically increased within the last decade. A considerable portion of a chip is dedicated to a cache memory in a modern microprocessor chip. However, some applications may not need all the caches for storage. In addition, some applications have embedded computations with a regular structure. The behavior of the applications is static, which implies that a specialized function unit could be beneficial for the application. This presents an opportunity to explore the use of a part of a cache for performing these regular computations. In this paper, we show one such design to convert a cache into a function unit to improve the performance of an application. A reconfigurable cache takes less area than the area of a cache and a function unit together and imposes no time overhead. In order to convert a cache memory to a function unit, we mapped multi-bit output look-up tables (LUTs) into the cache structure. Therefore, the cache can perform computations When it is reconfigured as a function unit.

Striped FPGA [1], or pipeline-reconfigurable FPGA provides hardware virtualization by supporting fast run-time reconfiguration. In this paper we show that the performance of striped FPGA depends on the reconfiguration pattern, the run time scheduling of configurations through the FPGA. We study two main configuration scheduling approaches: Configuration Caching and Data Caching. We present the quantitative analysis of these scheduling techniques to compute their total execution cycles taking into account the overhead caused by the IO with the external memory. Based on the analysis we can determine which scheduling technique works better for the given application and for the given hardware parameters.

We propose an alternative approach to branch resolution based on the earlier work on decoupled memory architectures. Branch decoupling is a technique for decoupling a single instruction stream program into two streams. One stream is solely dedicated to resolving branches as early as possible (both the branch condition and the branch target). The resolved branch targets are consumed by the other computing stream through a queue. We have proposed a compiler based static branch decoupling methodology earlier. In this paper, we propose a dynamic branch decoupled (DBD) architecture. Simulations show a speedup of 25.6% for SPEC95 integer benchmarks and 6.1% for SPEC95 FP benchmarks over a 2-level adaptive branch predictor. The average number of branch penalty cycles per instruction for DBD reduces to .0475 compared to .0835 for the 2-level branch predictor.

In the last three decades, device feature size has been reduced from ten's of microns to sub-0.5 /spl mu/m, shaping what is commonly called the ultra large scale integration (ULSI) era. At the same time, there has also been an appreciable decrease in the defect density over these years. While some of the defects have been completely eliminated, many still remain in modem fab lines. In view of the continuing trend of feature size reduction, the three-dimensional (3-D) nature of these defects is likely to have an impact on the functionality of integrated circuit (IC) structures. An open circuit is conventionally modeled as a break in a conductor due to an insulating defect. For 3-D defects and conductors, this physical interpretation of open circuits may not be the most appropriate one. In this paper, we present a parametrized modeling of open circuits for 3-D defects in ULSI processing. In the proposed approach, the maximum allowable increase in a conductor's resistance due to a partially or completely embedded insulating defect is suggested as the criterion for an open circuit. Analytical expressions for ULSI defect sensitivity are then obtained.

Traditional low power combinational logic synthesis methods solely attempt to minimize the node power consumption of the resulting netlist, and ignore the potential ramifications and benefits that their decisions have on the interconnect energy of the final circuit.This paper presents a more integrated approach that incrementally develops a companion placement during the logic synthesis process.This placement provides interconnect information to the suite of power optimization tools currently proposed by researchers, which allows for logic transformations that should be more effective at the layout level.It also creates opportunities for novel transformations such as clustering which reduce interconnect (and cumulative) energy by replicating portions of logic.This integrated system resulted in a 23% reduction in interconnect energy over area minimizing procedures, and a 13% reduction over current power optimizing tools on a set of MCNC PLA benchmarks. 1.Permission to make dighlhnrd copies of nil or part of this mnterinl for personnl or classroom use is granted without fee provided chat the copies ore uot made or distributed for profit or commercirl ndvautay, the copyright uotice, the title of the publication nud its date appear.nud notice is given thnt copyright is by permissiou of the ACM.Inc.To copy otherwise.to republish, lo post ou servers or to redislribule to lists, requires specific permission nndlor

Several state assignment algorithms have attempted to minimize the average Hamming distance per transition in the hopes of generating low power assignments. There has not been a reasonable theoretical lower bound on the average Hamming distance per transition that is applicable to every state assignment for a given FSM. Such a lower bound serves many roles-a target for algorithm designers, provides clues about what types of FSM structures ore likely to have low average switching per transition, could be incorporated into a high-level power model. We provide two such lower bounds which were also found to be achievable empirically within 17% for MCNC benchmarks. An interesting by product of one of these 'theoretical' lower bounds was a greedy state assignment algorithm which is amenable to a very distributed (parallel) implementation. This algorithm also outperforms JEDI by 2.5% for area and by 21% for power over MCNC benchmarks.

This paper reports our experiences with incorporating energy (or switched capacitance) based algorithms into an automated layout synthesis system based on standard cells. Our experimental results show an average savings of 18.5% in interconnect energy at a cost of about 6.2% area increase relative to area-minimized layouts on MCNC Logic Synthesis '93 benchmarks. The basic premise is that the wires with high switching should be made short even if it involves stretching several low switching wires. We modified an existing layout system, VPNR, to include these techniques during the placement and global routing phases. Attempts to include switching probabilities into channel routing did not produce appreciable results. Our experiments also lend insight into the composition of the solution space for VLSI energy minimization problems.

The carry-select or conditional-sum adders require carry-chain evaluations for each block for both the values of block-carry-in, 0 and 1. The author introduces a scheme to generate carry bits with block-carry-in 1 from the carries of a block with block-carry-in 0. This scheme is then applied to carry-select and parallel-prefix adders to derive a more area-efficient implementation for both the cases. The proposed carry-select scheme is assessed relative to carry-ripple, classical carry-select, and carry-skip adders. The analytic evaluation is done with respect to the gate-count model for area and gate-delay units for time.>

The feasibility and efficiency of design parsing are discussed. Design parsing refers to the process of parsing a flat netlist or logic description into a behaviorally equivalent flow graph where the nodes correspond to higher-level primitives such as arithmetic functions and a prespecified set of functions. It is useful in verification, resynthesis and computer-aided design documentation. A spatial-entropy-based dynamic signature that helps determine the boundaries and types of function blocks is presented.>

Module generators for adders and shifts that work at the netlist-level due to complexity of design space exploration are discussed. The module generators deal only with the netlists composed of standard macros. The objective is to use the VPNR standard-cell-based placement and route system for the layout synthesis from the generated netlist. The netlist level generation also provides the additional benefit of technology independence. It is feasible to build an accurate model for area and RC-delay of the physical layouts generated by a layout synthesis system. VPNR does an extremely good job of retaining the analytically derived area form, to within 3-8%. This well-behaved aspect of the layout synthesis systems can be used to free the module generators from working at the layout level. The module generators can instead focus their activities at the netlist level, which give them better design space exploration capabilities.>

For a medium-speed addition application, a carry-skip adder is usually preferred over a carry-select adder, due to its smaller area. A reduced-area carry-select adder scheme in which the second copy of the carry-chain is substituted by an OR gate per bit position is proposed. This alternative implementation for a carry-select adder reduces the relative area advantage of a carry-skip adder to roughly 35%. Replacing the ripple-carry blocks with parallel-prefix blocks results in a select-prefix adder with a slightly better area and time than a parallel-prefix adder.>