Phase Change Memory (PCM), one of the recently proposed non-volatile memory technologies, has been suffering from low write endurance. For example, a single-layer PCM cell could only be written approximately 10 8 . This limits the lifetime of a PCM-based memory to a few days rather than years when memory-intensive applications are running. Wear leveling techniques have been proposed to improve the write endurance of a PCM. Among those techniques, the region-based start-gap (RBSG) scheme is widely cited as achieving the highest lifetime. Based on our experiments, RBSG can achieve 97% of the ideal lifetime, but only for relatively small memory sizes (e.g., 8–32GB). As the memory size goes up, RBSG becomes less effective and its expected percentage of the ideal lifetime reduces to less than 57% for a 2TB PCM. In this article, we propose a table-based wear leveling scheme called block grouping to enhance the write endurance of a PCM with a negligible overhead. Our research results show that with a proper configuration and adoption of partial writes (writing back only 64B subblocks instead of a whole row to the PCM arrays) and internal row shift (shifting the subblocks in a row periodically so no subblock in a row will be written repeatedly), the proposed block grouping scheme could achieve 95% of the ideal lifetime on average for the Rodinia, NPB, and SPEC benchmarks with less than 1.74% performance overhead and up to 0.18% hardware overhead. Moreover, our scheme is scalable and achieves the same percentage of ideal lifetime for PCM of size from 8GB to 2TB. We also show that the proposed scheme can better tolerate memory write attacks than WoLFRaM (Wear Leveling and Fault Tolerance for Resistive Memories) and RBSG for a PCM of size 32GB or higher. Finally, we integrate an error-correcting pointer technique into our proposed block grouping scheme to make the PCM fault tolerant against hard errors.

Dynamic Information Flow Tracking has been successfully used to prevent a wide range of attacks and detect illegal access to sensitive information. Most proposed solutions only track the explicit information flow where the taint is propagated through data dependencies. However, recent evasion attacks exploit implicit flows, that use control flow in the application, to manipulate the data thus making the malicious activity undetectable. We propose NIFT - a nested implicit flow tracking mechanism that extends explicit propagation to instructions affected by a control dependency. Our technique generates taint instructions at compile time which are executed by specialized hardware to propagate taint implicitly even in cases of deeply-nested branches. In addition, we propose a restricted taint propagation for data executed in conditional branches that affects only immediate instructions instead of all instructions inside the branch scope. Our technique efficiently locates implicit flows and resolves them with negligible performance overhead. Moreover, it mitigates the over-tainting problem.

Cyber-Physical Systems (CPS) are increasingly used in a variety of transportation, healthcare, electricity grid, and other applications. Thermal stress is often a major concern for processors embedded in such systems. High operating temperatures can dramatically shorten processor life. This, in turn, can require provisioning of significant amounts of additional computational hardware to withstand more frequent failures, with obvious implications for sustainability. This paper describes a novel approach to reduce thermally-induced damage in CPS processors by targeting Dynamic Voltage and Frequency Scaling (DVFS) to high-activity task phases. That is, by preferentially slowing down high-activity task phases, significant additional savings in energy and thermal stress can be attained for a given amount of computational slowdown; this approach is shown to be superior to conventional methods that use DVFS without regard to activity levels. Also, our proposed task reassignment across cores is driven by estimates of current core reliability, which is superior to the usual approach of simply using either current temperature or temperature history. Our approach leads to a significant reliability improvement (around 20 percent) over baseline DVFS techniques.

Non-Volatile Memory (NVM) such as PCM has emerged as a potential alternative for main memory due to its high density and low leakage power. However, an NVM main-memory system faces three challenges when compared to Dynamic Random Access Memory (DRAM) - long latency, poor write endurance and data security. To address these three challenges, we propose a secure DRAM+NVM hybrid memory module. The hybrid module integrates a DRAM cache and a security unit (SU). DRAM cache can improve the performance of an NVM memory module and reduce the number of direct writes to the NVM. Our results show that a 256MB 2-way DRAM cache with a 1024B cache line performs well in an 8GB NVM main memory module. The SU is embedded in the onboard controller and includes an AES-GCM engine and an NVM vault. The AES-GCM engine implements encryption and authentication with low overhead. The NVM vault is used to store MAC tags and counter values for each DRAM cache line. According to our results, the proposed secure hybrid memory module improves the performance by 32% compared to an NVM-only memory module, and is only 6.8% slower than a DRAM only memory module.

Because most traditional homogeneous and heterogeneous processors have a fixed design that limits its runtime adaptability, they are not able to cope with the varying application behavior when one considers the axes of fault tolerance, performance, and energy consumption altogether. In this context, we propose a new dynamically adaptive processor design that is capable of delivering the best trade-off among these three axes according to the application at hand, or be tuned to optimize a specific metric. This is achieved by extending a polymorphic processor that can change its issue-width during runtime with specific mechanisms for fault tolerance, energy optimization, and performance enhancement. They are controlled by an optimization algorithm that evaluates and chooses which is the best configuration according to given requirements. Considering a metric that weighs all three axes, the proposed adaptive processor delivers a result that is 94.88% of the oracle processor on average, while a static configuration (defined at design time without runtime adaptation) only achieves 28.24% at most, which means that dynamic adaptation is required to cope with different application behaviors as there is not one specific configuration that fits all applications.

Communication and load balancing have a significant impact on the performance of parallel applications and have been the subject of extensive research in multicore architectures. Thread mapping has been one of the solutions adopted in multicore architectures to address both communication and load balancing. However, the impact of such issues on more recently introduced manycore architectures is still unknown. Most related work on manycore architectures focus on execution time and idleness information for scheduling decisions. In this paper, we improve the state of the art by performing a very detailed analysis of the impact of thread mapping on communication and load balancing in two manycore systems from Intel, namely Knights Corner and Knights Landing. We observed that the widely used metric of CPU time provides very inaccurate information for load balancing. We also evaluated the usage of thread mapping based on the communication and load information of the applications to improve the performance of manycore systems.

We present an in-depth analysis of transient faults effects on HPC applications in Intel Xeon Phi processors based on radiation experiments and high-level fault injection. Besides measuring the realistic error rates of Xeon Phi, we quantify Silent Data Corruption (SDCs) by correlating the distribution of corrupted elements in the output to the application's characteristics. We evaluate the benefits of imprecise computing for reducing the programs' error rate. For example, for HotSpot a 0.5% tolerance in the output value reduces the error rate by 85%.

Cyber-physical systems (CPS) frequently have to use massive redundancy to meet application requirements for high reliability. While such redundancy is required, it can be activated adaptively, based on the current state of the controlled plant. Most of the time, the plant is in a state that allows for a lower level of fault tolerance. Avoiding the continuous deployment of massive fault tolerance will greatly reduce the workload of the CPS, and lower the operating temperature of the cyber sub-system, thus increasing its reliability. In this article, we extend our prior research by demonstrating a software simulation framework Adaptive Fault Tolerance (AdaFT) that can automatically generate the sub-spaces within which our adaptive fault tolerance can be applied. We also show the theoretical benefits of AdaFT and its actual implementation in several real-world CPSs.

Dot-product is frequently used in many signal processing applications, and for this reason digital signal processors (DSPs) commonly include hardware units to speed up its calculation. In this paper, we propose a new circuit architecture for dot-product hardware units. This design fuses all the steps of the dot-product computation into a unit called a fused dot-product multiplier (FDPM), resulting in enhancements in performance, power and area vs. designs such as multiply-accumulate (MAC) units. We designed and implemented the FDPM in 28-nanometer and 65-nanometer technologies. Comparison of the fused unit to an implementation by an EDA design compiler showed that our architecture consumed 38% less power and 30% less area for the same clock cycle. Comparison to a previously proposed FDPM architecture showed a per-bit 1.9X - 4.7X energy reduction. Analysis of the dependence of the per-bit power consumption on vector length and word-width indicated a good match between theory and practice.

Heterogeneous architectures offer the promise of higher performance/Watt compared to symmetric multi-cores. Recent works have proposed the use of non-monotonic (NM) heterogeneous architectures with diverse core types where each core has unique power and performance characteristics. However, the power and performance benefits achieved by NM architectures is highly dependent on assignment of application to the most suitable core type for all program phases. In this paper we propose a novel online program phase detection technique that is based on the frequency of cache misses and processor stalls which correspond to core resource bottlenecks. We track performance monitors to formulate a Bottleneck Type Vector (BTV) that help direct the application to most appropriate core type for execution. We compare the proposed BTV-based core assignment method to prior online core assignment approaches and demonstrate as much as 22% improvement in average performance/Watt using Instructions per Second (IPS) as the performance metric.

Asymmetric multi-core processors (AMPs) comprise cores with different sizes of micro-architectural resources yielding very different performance and energy characteristics. Since the computational demands of workloads vary from one task to the other, AMPs can often provide a higher power efficiency than symmetric multi-cores. Furthermore, as the computational demands of a task change during its course of execution, reassigning the task from one core to another, where it can run more efficiently, can further improve the overall power efficiency. However, too frequent re-assignments of tasks to cores may result in high overhead. To greatly reduce this overhead, we propose a morphable core architecture that can dynamically adapt its resource sizes, operating frequency and voltage to assume one of four possible core configurations. Such a morphable architecture allows more frequent task to core configuration re-assignments for a better match between the current needs of the task and the available resources. To make the online morphing decisions we have developed a runtime analysis scheme that uses hardware performance counters. Our results indicate that the proposed morphable architecture controlled by the runtime management scheme, can improve the throughput/Watt of applications by 31 percent over executing on a static out-of-order core while the previously proposed big/little morphable architecture achieves only a 17 percent improvement.

Previous studies have shown that the best way to achieve high throughput/Watt of a single threaded application is by running it on an asymmetric multicore processor (AMP). AMPs feature cores that are tuned for specific workload characteristics. To increase efficiency, the core that offers the best power-performance trade-off for the executing thread is chosen. To reduce the overhead of thread migration, we have previously proposed a morphable core that can morph into multiple core types. In this study, apart from power-performance efficiency, we also consider the reliability of the different core types as indicated by their vulnerability to soft-errors. We show that the best core type for power-efficiency may not be the best for reliability. Accordingly, we develop a multi-objective thread migration strategy to determine the best core type considering power efficiency and reliability. To support runtime decision making, we have developed online estimators for reliability and power efficiency based on performance monitoring counters. In keeping with the existing literature, we use the architectural vulnerability factor (AVF) as the metric for reliability and instructions-per-second2/Watt as the metric for power efficiency. For the multi-objective optimization we use a Cobb-Douglas production function. Our results indicate that the proposed runtime mechanism for reliability and power-efficiency improves, on the average, the throughput/Watt of applications by 24% and reduces the Soft-Error Rate (SER) by 12% compared to the best static execution.

Several studies and recent real-world designs have promoted sharing of underutilized resources between cores in a multicore processor to achieve better performance/power. It has been argued that when utilization of such resources is low, sharing has a negligible impact on performance while offering considerable area and power benefits. In this article, we investigate the performance and performance/watt implications of sharing large and underutilized resources between pairs of cores in a multicore. We first study sharing of the entire floating-point datapath (including reservation stations and execution units) by two cores, similar to AMD’s Bulldozer. We find that while this architecture results in power savings for certain workload combinations, it also results in significant performance loss of up to 28%. Next, we study an alternative sharing architecture where only the floating-point execution units are shared, while the individual cores retain their reservation stations. This reduces the highest performance loss to 14%. We then extend the study to include sharing of other large execution units that are used infrequently, namely, the integer multiply and divide units. Subsequently, we analyze the impact of sharing hardware resources in Simultaneously Multithreaded (SMT) processors where multiple threads run concurrently on the same core. We observe that sharing improves performance/watt at a negligible performance cost only if the shared units have high throughput. Sharing low-throughput units reduces both performance and performance/watt. To increase the throughput of the shared units, we propose the use of Dynamic Voltage and Frequency Boosting (DVFB) of only the shared units that can be placed on a separate voltage island. Our results indicate that the use of DVFB improves both performance and performance/watt by as much as 22% and 10%, respectively.

Asymmetric multicore processors (AMPs) consist of cores executing the same ISA, but differing in micro-architectural resources, performance, and power consumption. As the computational bottleneck of a workload shifts from one resource to the next, during its course of execution, reassigning it to the core where it runs most efficiently can improve the overall energy efficiency. Simulation studies show that the performance bottlenecks can shift frequently, often within a few thousands cycles. With frequent core hooping, the overhead of thread migration becomes significant. To mitigate this overhead, we propose a morphable core that can assume one of four possible configurations to address the dominant performance bottlenecks, while retaining the same cache and registers. This way the architectural state remains intact while the morphable core is reconfigured in resources and frequency. We then implement a runtime scheme to decide the best configuration to run on and switch configuration as necessary. Simulation results indicate that on the average, the proposed scheme results in performance/watt improvement of 41%.

Most mechanisms in current superscalar processors use instruction granularity information for speculation, such as branch predictors or prefetchers. However, many of these characteristics can be obtained at the basic block level, increasing the amount of code that can be covered while requiring less space to store the data. Furthermore, the code can be profiled more accurately and provide a higher variety of information by analyzing different instruction types inside a block. Because of these advantages, block-level analysis can offer more opportunities for mechanisms that use this information. For example, it is possible to integrate information about branch prediction and memory accesses to provide precise information for speculative mechanisms, increasing accuracy and performance. We propose a Block-Level Architecture Profiler (BLAP), an online mechanism that profiles bottlenecks at the micro architectural level, such as delinquent memory loads, hard-to-predict branches and contention for functional units. BLAP works at the basic block level, providing information that can be used to reduce the impact of these bottlenecks. A prefetch dropping mechanism and a memory controller policy were developed to use the profiled information provided by BLAP. Together, these mechanisms are able to improve performance by up to 17.39% (3.90% on average). Our technique showed average gains of 13.14% when evaluated under high memory pressure due to highly aggressive prefetch.

Clock gating is a predominant technique used for power saving. It is observed that the commonly used synthesis-based gating still leaves a large amount of redundant clock pulses. Data-driven gating aims to disable these. To reduce the hardware overhead involved, flip-flops (FFs) are grouped so that they share a common clock enabling signal. The question of what is the group size maximizing the power savings is answered in a previous paper. Here we answer the question of which FFs should be placed in a group to maximize the power reduction. We propose a practical solution based on the toggling activity correlations of FFs and their physical position proximity constraints in the layout. Our data-driven clock gating is integrated into an Electronic Design Automation (EDA) commercial backend design flow, achieving total power reduction of 15%-20% for various types of large-scale state-of-the-art industrial and academic designs in 40 and 65 manometer process technologies. These savings are achieved on top of the sClock gating is a predominant technique used for power saving. It is observed that the commonly used synthesis-based gating still leaves a large amount of redundant clock pulses. Data-driven gating aims to disable these. To reduce the hardware overhead involved, flip-flops (FFs) are grouped so that they share a common clock enabling signal. The question of what is the group size maximizing the power savings is answered in a previous paper. Here we answer the question of which FFs should be placed in a group to maximize the power reduction. We propose a practical solution based on the toggling activity correlations of FFs and their physical position proximity constraints in the layout. Our data-driven clock gating is integrated into an Electronic Design Automation (EDA) commercial backend design flow, achieving total power reduction of 15%-20% for various types of large-scale state-of-the-art industrial and academic designs in 40 and 65 manometer process technologies. These savings are achieved on top of the savings obtained by clock gating synthesis performed by commercial EDA tools, and gating manually inserted into the register transfer level design.avings obtained by clock gating synthesis performed by commercial EDA tools, and gating manually inserted into the register transfer level design.

The importance of dynamic thread scheduling is increasing with the emergence of Asymmetric Multicore Processors (AMPs). Since the computing needs of a thread often vary during its execution, a fixed thread-to-core assignment is sub-optimal. Reassigning threads to cores (thread swapping) when the threads start a new phase with different computational needs, can significantly improve the energy efficiency of AMPs. Although identifying phase changes in the threads is not difficult, determining the appropriate thread-to-core assignment is a challenge. Furthermore, the problem of thread reassignment is aggravated by the multiple power states that may be available in the cores. To this end, we propose a novel technique to dynamically assess the program phase needs and determine whether swapping threads between core-types and/or changing the voltage/frequency levels (DVFS) of the cores will result in higher throughput/Watt. This is achieved by predicting the expected throughput/Watt of the current program phase at different voltage/frequency levels on all the available core-types in the AMP. We show that the benefits from thread swapping and DVFS are orthogonal, demonstrating the potential of the proposed scheme to achieve significant benefits by seamlessly combining the two. We illustrate our approach using a dual-core High-Performance (HP)/Low-Power (LP) AMP with two power states and demonstrate significant throughput/Watt improvement over different baselines.

EM emissions can be a rich source of leakage for side-channel analysis of cipher implementations. In this paper, we describe a set of novel countermeasures based on dynamic spatial relocation and dynamic mappings, and validate the protection provided by them against EM attacks. The countermeasures improve significantly the security of the circuit.

The computational needs of a program change over time. Sometimes a program exhibits low instruction level parallelism (ILP), while at other times the inherent ILP may be higher; sometimes a program stalls due to a large number of cache misses, while at other times it may exhibit high cache throughput. Asymmetric Multicore Processors (AMP) have been proposed to allow matching the computing needs of a thread to a core where it executes most efficiently. Some of the recent works focus on AMPs consisting of a monolithic large out-of-order (OOO) core and a small in-order (InO) core. Dynamic swapping of threads between these cores is then facilitated to improve energy efficiency of the threads without impacting performance too negatively. Swapping decisions are made at coarse grain instruction granularities to mitigate the impact of migration overhead. This excludes many opportunities for swap at a fine granular level. In this paper we consider a single superscalar OOO core that can morph itself dynamically into an InO core at runtime. In order to determine when to morph from OOO to InO and vice-versa, we rely on certain hardware performance monitors. Using these performance monitors we estimate the energy-delay-squared product (ED2P) for both modes of operation, which is then used to make morphing decisions. The morphing hardware support is simple and is already available in certain Intel processors to facilitate debug. The proposed scheme has low migration overhead, that enables fine-grain morphing to achieve more energy efficient computing by trading a small loss of performance for much greater energy reduction.

A digital camera sensor will incur pixel defects both in fabrication and during its lifetime. While manufacturing defects are corrected in the factory, in-field defects are prohibitively expensive to fix, and can eventually affect the picture quality. During the last 10 years, we have conducted a study of defect development in digital imagers, in which we had access to about 40 cameras and a database of past photos taken by them. The data we collected allows us to quantify characteristics of defect growth. Our investigations have shown that pixel defects are permanent, and their number grows with time. We found that the main type of defect is hot pixels, which are pixels that appear as a bright spot in the image even without any illumination. We also observed that the defects are distributed randomly over the sensor area and are not clustered. By studying past pictures of each given camera we found that the defect growth rate is constant over time. These spatial and temporal characteristics led us to the conclusion that defects are not likely related to material degradation or imperfect fabrication, but are caused by environmental stress such as cosmic rays radiation. Measuring the effect on the defect rate of sensor parameters such as sensor area, number of pixels, pixel size, and sensor technology (CCD - Charge Coupled Device vs. APS - Active Pixel Sensor) yielded a power law, implying that increasing the number of pixels by shrinking the pixel size will result in a higher defect rate and is, therefore, not recommended.

The emergence of asymmetric multicore processors(AMPs) has elevated the problem of thread scheduling in such systems. The computing needs of a thread often vary during its execution (phases) and hence, reassigning threads to cores(thread swapping) upon detection of such a change, can significantly improve the AMP's power efficiency. Even though identifying a change in the resource requirements of a workload is straightforward, determining the thread reassignment is a challenge. Traditional online learning schemes rely on sampling to determine the best thread to core in AMPs. However, as the number of cores in the multicore increases, the sampling overhead may be too large. In this paper, we propose a novel technique to dynamically assess the current thread to core assignment and determine whether swapping the threads between the cores will be beneficial and achieve a higher performance/Watt. This decision is based on estimating the expected performance and power of the current program phase on other cores. This estimation is done using the values of selected performance counters in the host core. By estimating the expected performance and power on each core type, informed thread scheduling decisions can be made while avoiding the overhead associated with sampling. We illustrate our approach using an 8-core high performance/low-power AMP and show the performance/Watt benefits of the proposed dynamic thread scheduling technique. We compare our proposed scheme against previously published schemes based on online learning and two schemes based on the use of an oracle, one static and the other dynamic. Our results show that significant performance/Watt gains can be achieved through informed thread scheduling decisions in AMPs.

Implementations of cryptographic algorithms continue to proliferate in consumer products due to the increasing demand for secure transmission of confidential information. Although the current standard cryptographic algorithms proved to withstand exhaustive attacks, their hardware and software implementations have exhibited vulnerabilities to side channel attacks, e.g., power analysis and fault injection attacks. This paper focuses on fault injection attacks that have been shown to require inexpensive equipment and a short amount of time. The paper provides a comprehensive description of these attacks on cryptographic devices and the countermeasures that have been developed against them. After a brief review of the widely used cryptographic algorithms, we classify the currently known fault injection attacks into low-cost ones (which a single attacker with a modest budget can mount) and high-cost ones (requiring highly skilled attackers with a large budget). We then list the attacks that have been developed for the important and commonly used ciphers and indicate which ones have been successfully used in practice. The known countermeasures against the previously described fault injection attacks are then presented, including intrusion detection and fault detection. We conclude the survey with a discussion on the interaction between fault injection attacks (and the corresponding countermeasures) and power analysis attacks.

Asymmetric multi-core processors (AMPs) have been shown to outperform symmetric ones in terms of performance and performance/watt. Improved performance and power efficiency are achieved when the program threads are matched to their most suitable cores. Since the computational needs of a program may change during its execution, the best thread to core assignment will likely change with time. We have, therefore, developed an online program phase classification scheme that allows the swapping of threads when the current needs of the threads justify a change in the assignment. The architectural differences among the cores in an AMP can never match the diversity that exists among different programs and even between different phases of the same program. Consider, for example, a program (or a program phase) that has a high instruction-level parallelism (ILP) and will exhibit high power efficiency if executed on a powerful core. We can not, however, include such powerful cores in the designed AMP, since they will remain underutilized most of the time, and they are not power efficient when the programs do not exhibit a high degree of ILP. Thus, we must expect to see program phases where the designed cores will be unable to support the ILP that the program can exhibit. We, therefore, propose in this article a dynamic morphing scheme. This scheme will allow a core to gain control of a functional unit that is ordinarily under the control of a neighboring core during periods of intense computation with high ILP. This way, we dynamically adjust the hardware resources to the current needs of the application. Our results show that combining online phase classification and dynamic core morphing can significantly improve the performance/watt of most multithreaded workloads.

Gating of the clock signal in VLSI chips is nowadays a mainstream design methodology for reducing switching power consumption. In this paper we develop a probabilistic model of the clock gating network that allows us to quantify the expected power savings and the implied overhead. Expressions for the power savings in a gated clock tree are presented and the optimal gater fan-out is derived, based on flip-flops toggling probabilities and process technology parameters. The resulting clock gating methodology achieves 10% savings of the total clock tree switching power. The timing implications of the proposed gating scheme are discussed. The grouping of FFs for a joint clocked gating is also discussed. The analysis and the results match the experimental data obtained for a 3-D graphics processor and a 16-bit microcontroller, both designed at 65-nanometer technology.

The trend toward multicore processors is moving the emphasis in computation from sequential to parallel processing. However, not all applications can be parallelized and benefit from multiple cores. Such applications lead to under-utilization of parallel resources, hence sub-optimal performance/watt. They may however, benefit from powerful uniprocessors. On the other hand, not all applications can take advantage of more powerful uniprocessors. To address competing requirements of diverse applications, we propose a heterogeneous multicore architecture with a Dynamic Core Morphing (DCM) capability. Depending on the computational demands of the currently executing applications, the resources of a few tightly coupled cores are morphed at runtime. We present a simple hardware-based algorithm to monitor the time-varying computational needs of the application and when deemed beneficial, trigger reconfiguration of the cores at fine-grain time scales to maximize the performance/watt of the application. The proposed dynamic scheme is then compared against a baseline static heterogeneous multicore configuration and an equivalent homogeneous configuration. Our results show that dynamic morphing of cores can provide performance/watt gains of 43% and 16% on an average, when compared to the homogeneous and baseline heterogeneous configurations, respectively.

Summary form only given. Technology scaling has led to a tremendous increase in the packing density of transistors. However, these small transistors are susceptible to certain impediments that were not present earlier. Manufacturability suffers due to trailing lithography technology which does not scale well with transistor technology. Increased leakage current has reduced effectiveness of burn-in tests. Infant mortality cannot therefore, be completely kept under check. Even during operation, reliability is affected due to CMOS wear-out mechanisms such as time-dependent dielectric breakdown (TDDB), hot carrier injection (HCI), negative bias temperature instability (NBTI), electro migration (EM), and stress induced voiding (SIV).

Simultaneous multithreading (SMT) increases processor throughput by allowing parallel execution of several threads. However, fully sharing processor resources may cause resource monopolization by a single thread or other misallocations, resulting in overall performance degradation. Static resource partitioning techniques have been suggested, but are not as effective as dynamic ones since program behavior does change over the course of its execution. In this paper, we propose an Adaptive Resource Partitioning Algorithm (ARPA) that dynamically assigns resources to threads according to changes in thread behavior. ARPA analyzes the resource usage efficiency of each thread in a given time period and assigns more resources to threads which can use them more efficiently. Its purpose is to improve the efficiency of resource utilization, thereby improving overall instruction throughput. Our simulation results on a set of 42 multiprogramming workloads show that ARPA outperforms the traditional fetch policy ICOUNT by 55.8 percent with regard to overall instruction throughput and achieves a 33.8 percent improvement over Static Partitioning. It also outperforms the current best dynamic resource allocation technique, Hill-climbing, by 5.7 percent. Considering fairness accorded to each thread, ARPA attains 43.6, 18.5, and 9.2 percent improvements over ICOUNT, Static Partitioning, and Hill-climbing, respectively, using a common fairness metric. We also explore the energy efficiency of dynamically controlling the number of powered-on reorder buffer entries for ARPA. Compared with ARPA, our energy-aware resource partitioning algorithm achieves 10.6 percent energy savings, while the performance loss is negligible.

Multicore architectures are designed so as to provide an acceptable level of performance per unit power for the majority of applications. Consequently, we must occasionally expect applications that could have benefited from a more powerful core in terms of either lower execution time and/or lower energy consumed. Fusing some of the resources of two (or more) cores to configure a more powerful core for such instances is a natural approach to deal with those few applications that have very high performance demands. However, a recent study has shown that fusing homogeneous cores is unlikely to benefit applications. In this paper we study the potential performance benefits of core morphing in a heterogeneous multicore processor that can be reconfigured at runtime. We consider as an example a dual core processor with one of the two cores being designed to target integer intensive applications while the other is better suited to floating-point intensive applications. These two cores can be fused into a single powerful core when an application that can benefit from such fusion is executing. We first discuss the design principles of the two individual cores so that the majority of the benchmarks that we consider execute in a satisfactory way. We then show that a small subset of the considered applications can greatly benefit from core morphing even in the case where two applications that could have been executed in parallel on the two cores are run, for some percentage of time, on the single morphed core. Our results indicate that a performance gain of up to 100% is achievable at a small hardware overhead of less than 1%.

Simultaneous Multithreading (SMT) increases processor throughput by allowing the parallel execution of several threads. However, fully sharing processor resources may cause resource monopolization by a single thread or other misallocations, resulting in overall performance degradation. Static resource partitioning techniques have been suggested, but are not as effective as dynamically controlling the resource usage of each thread since program behavior does change during its execution.

Branch Prediction Analysis has been recently proposed as an attack method to extract the key from software implementations of the RSA public key cryptographic algorithm. In this paper, we describe several solutions to protect against such an attack and analyze their impact on the execution time of the cryptographic algorithm. We show that the code transformations required for protection against branch target buffer attacks can be automated and impose only a negligible performance penalty.

One of the most effective ways of attacking a cryptographic device is by deliberate fault injection during computation, which allows retrieving the secret key with a small number of attempts. Several attacks on symmetric and public-key cryptosystems have been described in the literature and some dedicated error-detection techniques have been proposed to foil them. The proposed techniques are ad hoc ones and exploit specific properties of the cryptographic algorithms. In this paper, we propose a general framework for error detection in symmetric ciphers based on an operation-centered approach. We first enumerate the arithmetic and logic operations included in the cipher and analyze the efficacy and hardware complexity of several error-detecting codes for each such operation. We then recommend an error-detecting code for the cipher as a whole based on the operations it employs. We also deal with the trade-off between the frequency of checking for errors and the error coverage. We demonstrate our framework on a representative group of 11 symmetric ciphers. Our conclusions are supported by both analytical proofs and extensive simulation experiments

Emerging network technologies have complex network interfaces that have renewed concerns about network reliability. In this paper, we present an effective low-overhead fault tolerance technique to recover from network interface failures. Failure detection is based on a software watchdog timer that detects network processor hangs and a self-testing scheme that detects interface failures other than processor hangs. The proposed self-testing scheme achieves failure detection by periodically directing the control flow to go through only active software modules in order to detect errors that affect instructions in the local memory of the network interface. Our failure recovery is achieved by restoring the state of the network interface using a small backup copy containing just the right amount of information required for complete recovery. The paper shows how this technique can be made to minimize the performance impact to the host system and be completely transparent to the user.

We present a system emulator that provides a versatile environment for testing and validating a distributed system for sensing of the lower atmosphere during its development lifecycle. The emulator, along with its comprehensive RAPIDS toolbox, provide the necessary infrastructure to experiment with different parameters of the system to ensure that the system specifications are being met, while also providing the scope of experimenting with newer configurations and futuristic designs. Extensive monitoring of the system possible through RAPIDS, allows to expose bugs and performance bottlenecks. The remote experimentation feature of the system allows several users to drive/monitor the system without requiring physical access to the emulator.

Recently, various attacks have been proposed against many crypto systems, exploiting deliberate error injection during the computation process. In this paper, we add a residue-based error detection scheme to an RSA architecture to protect against such attacks. We then evaluate the error coverage and the expected area and latency overheads

Front-end instruction delivery accounts for a significant fraction of energy consumption in dynamically scheduled superscalar processors. Different front-end throttling techniques have been introduced to reduce the chip-wide energy consumption caused by redundant fetching. Hardware-based techniques, such as flow-based throttling, could reduce the energy consumption considerably, but with a high performance loss. On the other hand, compiler-based IPC-estimation-driven software fetch throttling (CFT) techniques result in relatively low performance degradation, which is desirable for high-performance processors. However, their energy savings are limited by the fact that they typically use a predefined fixed low IPC-threshold to control throttling. In this paper, we propose a compiler-based adaptive fetch throttling (CAFT) technique that allows changing the throttling threshold dynamically at runtime. Instead of using a fixed threshold, our technique uses the decode/issue difference (DID) to assist the fetch throttling decision based on the statically estimated IPC. Changing the threshold dynamically makes it possible to throttle at a higher estimated IPC, thus increasing the throttling opportunities and resulting in larger energy savings. We demonstrate that CAFT could increase the energy savings significantly compared to CFT, while preserving its benefit of low performance loss. Our simulation results show that the proposed technique doubles the energy-delay product (EDP) savings compared to the fixed threshold throttling and achieves a 6.1% average EDP saving.

1073-1074

Saturating counters are a newly defined class of generalized parallel counters that provide the exact number of inputs which are equal to 1 only if this number is below a given threshold. Such counters are useful in, for example, self-test and repair units for embedded memories. This paper defines saturating counters for arbitrary threshold values and presents several alternatives for their implementation. The delay and area of the proposed design alternatives are then estimated using a 0.25/spl mu/m cell library. Finally, we study the behavior of saturating counters when the threshold approaches the number of input bits, i.e., the special case of non-saturating parallel counters.

This paper describes an analytical delay model for transistor sizing. Two primitives are selected to be mapped for computing gate delay. These primitives model the short-channel effect and body effect in deep submicron CMOS circuits. A mapping algorithm for arbitrary serial-parallel structures is adopted. The delay of complex gates using such mappings to primitives are found to be within 10% of SPICE for most of the gates. The delay model is incorporated into a transistor sizing algorithm based on TILOS. Also presented are the experimental results for several circuits from LGSynth91 benchmark suite.

Embedded systems often have severe power and energy constraints. Dynamic voltage scaling (DVS) is a mechanism by which energy consumption may be reduced. In this paper, we implement a dynamic voltage scaling based scheduler in the eCos operating system running on Voltage Scalable Intel Xscale Board and show how energy usage can be reduced while still meeting hard real-time deadlines.

Yield is normally ignored during the floorplanning stage. Recently, it has been shown that floorplanning can affect the yield with the increased sizes of chips. With the "medium-area clustering" model, yield can be evaluated during the floorplanning stage. Therefore, it's straightforward to incorporate yield in modern floorplanners. However, conventional simulate-annealing (SA) based moves are only designed for the combination of the area and/or the wire length minimizations. In this paper, we proposed a heuristic scheme of "moves" directly targeting on the yield improvement. The experimental results show a great yield improvement with little penalty for the area and/or the total wire length.

This paper evaluates several hardware-based data prefetching techniques from an energy perspective, and explores their energy/performance tradeoffs. We present detailed simulation results and make performance and energy comparisons between different configurations. Power characterization is provided based on HSpice circuit-level simulation of state-of-the-art low-power cache designs implemented in deep-submicron process technology. This is combined with architecture-level simulation of switching activities in the memory system. The results show that while aggressive prefetching techniques often help to improve performance, they increase energy consumption in most of the cases. In designs implemented in deep-submicron 100-nm BPTM process technology, cache leakage becomes one of the dominant factors of the energy consumption. We have, however, found that if leakage is optimized with recently-proposed circuit-level techniques, most of the energy degradation is due to prefetch-hardware related costs and unnecessary L1 data cache lookups related to prefetches that hit in the L1 cache. This overhead on the memory system can be as much as 20%.

Systems that operate in extremely volatile environments, such as orbiting satellites, must be designed with a strong emphasis on fault tolerance. Rather than rely solely on the system hardware, it may be beneficial to entrust some of the fault handling to software at the application level, which can utilize semantic information and software communication channels to achieve fault tolerance with considerably less power and performance overhead. We show the implementation and evaluation of such a software-level approach, application-level fault tolerance and detection (ALFTD) into the orbital thermal imaging spectrometer (OTIS).

We define a new class of parallel counters, saturating counters, which provide the exact count of the inputs that are 1 only if this count is below a given threshold. Such counters are useful in, for example, a self-test and repair unit for embedded memories in a system-on-a-chip. We describe this application and present several alternatives for the design of the saturating counter. We then compare the delay and area of the proposed design alternatives.

Recent research has shown that fault diagnosis and possibly fault tolerance are important features when implementing cryptographic algorithms by means of hardware devices. In fact, some security attack procedures are based on the injection of faults. At the same time, hardware implementations of cryptographic algorithms, i.e. crypto-processors, are becoming widespread. There is however, only very limited research on implementing fault diagnosis and tolerance in crypto-algorithms. Fault diagnosis is studied for the RC5 crypto-algorithm, a recently proposed block-cipher algorithm that is suited for both software and hardware implementations. RC5 is based on a mix of arithmetic and logic operations, and is therefore a challenge for fault diagnosis. We study fault propagation in RC5, and propose and evaluate the cost/performance tradeoffs of several error detecting codes for RC5. Costs are estimated in terms of hardware overhead, and performances in terms of fault coverage. Our most important conclusion is that, despite its nonuniform nature, RC5 can be efficiently protected by using low-cost error detecting codes.

193-202

491-500

741-750

Power and energy consumption has recently become an important issue and consequently, power-aware techniques are being devised at all levels of system design; from the circuit and device level, to the architectural, compiler, operating system, and networking layers. In this paper, we concentrate on power-aware design techniques for real-time systems. While the main focus is on hard real-time, soft real-time systems are considered as well. We start with the motivation for focusing on these systems and provide a brief discussion on power and energy objectives. We then follow with a survey of current research on a layer-by-layer basis. We conclude with illustrative examples and open research challenges. This paper provides an overview of power-aware techniques for the real-time system engineer as well as an up-to-date reference list for the researcher.

The goal of the Advanced Encryption Standard (AES) is to achieve secure communication. The use of AES does not, however, guarantee reliable communication. Prior work has shown that even a single transient error occurring during the AES encryption (or decryption) process will very likely result in a large number of errors in the encrypted/decrypted data. Such faults must be detected before sending to avoid the transmission and use of erroneous data. Concurrent fault detection is important not only to protect the encryption/decryption process from random faults. It will also protect the encryption/decryption circuitry from an attacker who may maliciously inject faults in order to find the encryption secret key. In this paper, we first describe some studies of the effects that faults may have on a hardware implementation of AES by analyzing the propagation of such faults to the outputs. We then present two fault detection schemes: The first is a redundancy-based scheme while the second uses an error detecting code. The latter is a novel scheme which leads to very efficient and high coverage fault detection. Finally, the hardware costs and detection latencies of both schemes are estimated.

The unique characteristics of multimedia/embedded applications dictate media-sensitive architectural and compiler approaches to reduce the power consumption of the data cache. Our goal is exploring energy savings for embedded/multimedia workloads without sacrificing performance. Here, we present two complementary media-sensitive energy-saving techniques that leverage static information. While our first technique is applicable to existing architectures, in our second technique we adopt a more radical approach and propose a new tagless caching architecture by reevaluating the architecture--compiler interface.Our experiments show that substantial energy savings are possible in the data cache. Across a wide range of cache and architectural configurations, we obtain up to 77% energy savings, while the performance varies from 14% improvement to 4% degradation depending on the application.

Reliability of systems used in space, avionic, and biomedical applications is highly critical. Such systems consist of an analog front-end to collect data, an analog-to-digital converter (ADC) to convert the collected data to digital form, and a digital unit to process it. Though a considerable amount of research has been performed to increase the reliability of digital blocks, the same cannot be claimed for mixed-signal blocks. The reliability enhancement that we employ begins with fault-sensitivity analysis followed by redesign. The data obtained from the sensitivity analysis is used to grade blocks based on their sensitivity to faults. The highly sensitive blocks can then be replaced by more reliable alternatives. The improvement gained by opting for more robust implementations might be limited due to the number of possible implementations. In these cases, alternative reliability enhancement techniques such as adding redundancy may provide further improvements. The steps involved in the reliability enhancement of ADCs are illustrated in this paper by first proposing a sensitivity analysis methodology for /spl alpha/-particle induced transients and then suggesting redesign techniques to improve the reliability of the ADC. A novel concept of node weights specific to /spl alpha/-particle transients is introduced, which improves the accuracy of the sensitivity analysis. The fault simulations show that, using techniques such as alternative robust implementations, adding redundancy, pattern detection, and transistor sizing, considerable improvements in reliability can be attained.

High reliability is a desirable property of any implementation of the Advanced Encryption Standard (AES). To achieve high reliability, all possible faults must be detected to avoid the use and transmission of erroneous encrypted/decrypted data. In this paper we first study the behavior of faults which may occur during the encryption and decryption procedures of AES, and the way such faults eventually propagate to the final result. We then describe an appropriate detection technique for these faults. This work extends our preliminary results (G. Bertoni et al, MPCS 2002) by considering more general fault models (e.g., permanent and multiple transient faults), and the possibility of fault masking.

This work is based on our philosophy of providing interlayer system-level power awareness in computing systems. Here, we couple this approach with our vision of multi-partitioned memory systems, where memory accesses are separated based on their static predictability and memory footprint and managed with various compiler controlled techniques. We show that media applications are mapped more efficiently when scalar memory accesses are redirected to a mini-cache. Our results indicate that a partitioned 8K cache with the scalars being mapped to a 512 byte mini-cache can be more efficient than a 16K monolithic cache from both performance and energy point of view for most applications. In extensive experiments, we report 30% to 60% energy-delay product savings over a range of system configurations and different cache sizes.

Many real-time systems employed in defense, space, and consumer applications have power constraints and high reliability requirements. In this paper, we focus on the relationship between fault tolerance techniques and energy consumption. In particular, we establish the energy efficiency of Application Level Fault Tolerance (ALFT) over other software-based fault tolerance methods. We then develop sensible energy-aware heuristics for ALFT schemes. The heuristics yield up to 40% energy savings.

Presents an area-efficient register transfer level technique for gracefully degradable data path synthesis called phantom redundancy. In contrast to spare-based approaches, phantom redundancy is a recovery technique that does not use any standby spares. Phantom redundancy uses extra interconnect to make the resulting data path reconfigurable in the presence of any (single) functional unit failure. When phantom redundancy is combined with a concurrent error detection technique, error detection followed by reconfiguration is automatic. The authors developed a register transfer level synthesis algorithm that incorporates phantom redundancy constraints. There is a tight interdependence between reconfiguration of a (faulty) data path and scheduling and operation-to-operator binding tasks during register transfer level synthesis. They developed a genetic algorithm-based register transfer level synthesis approach to incorporate phantom redundancy constraints. The algorithm minimizes the performance degradation of the synthesized data path in the presence of any single faulty functional unit. The effectiveness of the technique and the algorithm are illustrated using high-level synthesis benchmarks.

Synthesizing networks that satisfy multiple requirements, such as high reliability, low diameter, good embeddability, etc., is a difficult problem to which there has been no completely satisfactory solution. We present a simple, yet very effective, approach to this problem. The crux of our approach is a filtration process that takes as input a large set of randomly generated graphs and filters out those that do not meet the specified requirements. Our experimental results show that this approach is both practical and powerful. The use of random regular networks as the raw material for the filtration process was motivated by their surprisingly good performance with regard to almost all properties that characterize a good interconnection network. We provide results related to the generation of networks that have low diameter, high fault tolerance, and good embeddability. Through this, we show that the generated networks are serious competitors to several traditional well-known networks. We also explore how random networks can be used in a packaging hierarchy and comment on the scope of application of these networks.

We claim that the unique characteristics of multimedia applications dictate media-sensitive architectural and compiler approaches to reduce the power consumption of the data cache. Our motivation is exploring energy savings for real-time multimedia workloads without sacrificing performance. In this paper, we present two complementary media-sensitive energy-saving techniques that leverage static information. While our first technique is applicable to existing architectures, in our second technique we adopt a more radical approach and propose a new caching architecture by re-evaluating the architecture-compiler interface. Our experiments show that substantial energy savings are possible in the data cache. Across a wide range of cache and architectural configurations we obtain up to 77% energy savings, while the performance varies from 14% improvement to 4% degradation depending on the application.

It is well-known that constant-time addition, in which the execution delay is independent of operand lengths, is feasible only if the output is expressed in a redundant representation. There are many ways of introducing redundancy and the specifics of the redundant format employed can have a major impact on the performance of constant-time addition and digit set conversion. This paper presents a comprehensive analysis of constant-time addition and simultaneous format conversion. We consider full as well as partially redundant representations, where not all digit positions are redundant. The number of redundant digits and their positions can be arbitrary, yielding many possible redundant representations. Format conversion refers to changing the number and/or position of redundant digits in a representation. It is shown that such a format conversion is feasible during (ie, simultaneous with) constant time addition, even if all three operands (the two inputs and single output) are represented in distinct redundant formats. We exploit "equal-weight grouping" (EWG), wherein bits having the same weight are grouped together to achieve the constant-time addition and possible simultaneous format conversion. The analysis and data show that EWG leads to efficient implementations. We compare VLSI implementations of various constant-time addition cells and demonstrate that the conventional 4:2 compressor is the most efficient way to execute constant time-addition. We show interesting connections to prior results and indicate possible directions for further extensions.

The traditional goals of the floorplanning process for a new integrated circuit have been minimizing the total chip area and reducing the routing cost, i.e., the total length of the interconnecting wires. Recently, it has been shown that, for certain types of chips, the floorplan can affect the yield of the chip as well. Consequently, it becomes desirable to consider the expected yield, in addition to the cost of routing, when selecting a floorplan. The goal of this paper is to investigate the two seemingly unrelated, and often conflicting, objectives of yield enhancement and routing complexity minimization. We analyze the possible trade-offs between the two and then present a constructive algorithm for incorporating yield enhancement as a secondary objective into the floorplanning process, with the main objective still being the minimization of the overall routing costs.

625-627

In two operand addition, bit-wise intermediate variables such as the "propagate" and "generate" terms are defined/evaluated first. Basic carry propagation recursion is then expressed in terms of these variables and is "unrolled" to obtain a tree structure for fast execution. In CMOS VLSI technology, multiplexors are fast and efficient to implement. Hence, we investigate in this paper all possible two-bit encodings for the intermediate variables and identify the ones that enable multiplexor-based implementations. Some of these encodings enable further simplification of the multiplexor-based realizations. Our analysis also shows that adopting an intermediate signed-digit representation simply amounts to selecting one of the possible encodings. Thus, there is no inherent advantage to the use of intermediate signed-digit representations in a two operand addition. Finally, we extend our analysis to the generalized look-ahead-recursions proposed by R.W. Doran (1988).

As microprocessor-based systems grow in complexity, and the processor-memory speed gap widens further, more emphasis needs to be placed on early design space exploration in order to produce the highest performance systems with minimal schedule impact. We discuss the critical issues associated with architectural evaluation of complex microprocessor-based systems, and present a methodology for the comprehensive and semiautomatic evaluation of processor, cache hierarchy, system interconnect, and main memory architectural and technological alternatives. We discuss the implementation of the methodology, and describe how it can be used in early design space exploration. The unique aspects of the methodology are further illustrated through two architectural investigations performed using the toolset.

Current very-large-scale-integration (VLSI) technology allows the manufacture of large-area integrated circuits with submicrometer feature sizes, enabling designs with several millions of devices. However, imperfections in the fabrication process result in yield-reducing manufacturing defects, whose severity grows proportionally with the size and density of the chip. Consequently, the development and use of yield-enhancement techniques at the design stage, to complement existing efforts at the manufacturing stage, is economically justifiable. Design-stage yield-enhancement techniques are aimed at making the integrated circuit "defect tolerant", i.e., less sensitive to manufacturing defects. They include incorporating redundancy into the design, modifying the circuit floorplan, and modifying its layout. Successful designs of defect-tolerant chips must rely on accurate yield projections. This paper reviews the currently used statistical yield-prediction models and their application to defect-tolerant designs. We then provide a detailed survey of various yield-enhancement techniques and illustrate their use by describing the design of several representative defect-tolerant VLSI circuits.

Until recently, VLSI designers rarely considered yield issues when selecting a floorplan for a newly designed chip. This paper demonstrates that for large area VLSI chips, especially those that incorporate some fault tolerance, changes in the floorplan can affect the projected yield. We study several general floorplan structures, make some specific recommendations, and apply them to actual VLSI chips. We conclude that the floorplan of a chip can affect its projected yield in a nonnegligible way, for chips with or without fault-tolerance.

For VLSI application-specific arrays and other regular VLSI circuits, two techniques are available for yield enhancement, namely defect-tolerance and layout modifications. In this paper, we compare these two yield enhancement approaches by using adders as an example. Our yield projections indicate that the layout modification technique is more efficient when the defect density is low, while reconfiguration is more efficient for a high defect density. However, from the point of the view of effective yield, the layout modification is superior to defect tolerance in the practical range of defect density.

Phantom redundancy, an area-efficient technique for fabrication-time reconfigurability is presented. Phantom redundancy adds extra interconnect so as to render the resulting microarchitecture reconfigurable in the presence of any (single) functional unit failure. The proposed technique yields partially good chips in addition to perfect chips. A genetic algorithm is used to incorporate phantom redundancy constraints into microarchitecture synthesis. The algorithm minimizes tire performance degradation due to any faulty functional unit of the resulting microarchitecture. The effectiveness of the technique is illustrated on benchmark examples.

A method is proposed to estimate the fault tolerance (FT) of feedforward artificial neural nets (ANNs) and synthesize robust nets. The fault model abstracts a variety of failure modes for permanent stuck-at type faults. A procedure is developed to build FT ANNs by replicating the hidden units. It exploits the intrinsic weighted summation operation performed by the processing units to overcome faults. Metrics are devised to quantify the FT as a function of redundancy. A lower bound on the redundancy required to tolerate all possible single faults is analytically derived. Less than triple modular redundancy (TMR) cannot provide complete FT for all possible single faults. The actual redundancy needed to synthesize a completely FT net is specific to the problem at hand and is usually much higher than that dictated by the general lower bound. The conventional TMR scheme of triplication and majority voting is the best way to achieve complete FT in most ANNs. Although the redundancy needed for complete FT is substantial, the ANNs exhibit good partial FT to begin with and degrade gracefully. The first replication yields maximum enhancement in partial FT compared with later successive replications. For large nets, exhaustive testing of all possible single faults is prohibitive, so the strategy of randomly testing a small fraction of the total number of links is adopted. It yields partial FT estimates that are very close to those obtained by exhaustive testing. When the fraction of links tested is held fixed, the accuracy of the estimate generated by random testing is seen to improve as the net size grows.

This paper summarizes a practical experiment in designing a defect tolerant microprocessor and presents the underlying principles. Unlike memory integrated circuits, microprocessors have an irregular structure which complicates both the task of incorporating redundancy for defect tolerance in the design and the task of analyzing the resulting yield increase. The main goal of this paper is to present the detailed yield analysis of a defect tolerant microprocessor with an irregular structure which has been successfully fabricated. The approaches employed for achieving the goal of yield enhancement in the data path and the control part of the microprocessor are described first. Then, the yield enhancement due to the incorporated redundancy is analyzed. Finally, some practical and theoretical conclusions are drawn.>

A novel hybrid number representation is proposed. It includes the two's complement representation and the signed-digit representation as special cases. The hybrid number representations proposed are capable of bounding the maximum length of carry propagation chains during addition to any desired value between 1 and the entire word length. The framework reveals a continuum of number representations between the two extremes of two's complement and signed-digit number systems and allows a unified performance analysis of the entire spectrum of implementations of adders, multipliers and alike. We present several static CMOS implementations of a two-operand adder which employ the proposed representations. We then derive quantitative estimates of area (in terms of the required number of transistors) and the maximum carry propagation delay for such an adder. The analysis clearly illustrates the trade-offs between area and execution time associated with each of the possible representations. We also discuss adder trees for parallel multipliers and show that the proposed representations lead to compact adder trees with fast execution times. In practice, the area available to a designer is often limited. In such cases, the designer can select the particular hybrid representation that yields the most suitable implementation (fastest, lowest power consumption, etc.) while satisfying the area constraint. Similarly, if the worst case delay is predetermined, the designer can select a hybrid representation that minimizes area or power under the delay constraint.>

The cascade correlation is a very flexible, efficient and fast algorithm for supervised learning. It incrementally builds the network by adding hidden units one at a time, until the desired input/output mapping is achieved. It connects all the previously installed units to the new unit being added. Consequently, each new unit in effect adds a new layer and the fan-in of the hidden and output units keeps on increasing as more units get added. The resulting structure could be hard to implement in VLSI, because the connections are irregular and the fan-in is unbounded. Moreover, the depth or the propagation delay through the resulting network is directly proportional to the number of units and can be excessive. We have modified the algorithm to generate networks with restricted fan-in and small depth (propagation delay) by controlling the connectivity. Our results reveal that there is a tradeoff between connectivity and other performance attributes like depth, total number of independent parameters, and learning time.

Defect maps of 57 wafers containing large area VLSI IC's were analyzed in order to find a good match between the empirical distribution of defects and a theoretical model. Our main result is that the commonly employed models, most notably, the large area clustering negative binomial distribution, do not provide a sufficiently good match for these large area IC's. Only the recently proposed medium size clustering model is close enough to the empirical distribution. An even better match can be obtained either by combining two theoretical distributions or by a "censoring" procedure in which the worst chips are ignored. Another goal of the study was to find out whether certain portions of either the chip or the wafer had more defects than the others.>

The highlights of the design of an integer multiplier/divider unit for a 64-b processor are presented. The final design is the result of a compromise between performance, complexity, and transistor count. It is optimized for two specific operations with the same hardware being shared by the remaining operations. Thus, for example, the multiplier can be configured for the execution of several different multiply operations and its hardware is also heavily utilized in division. The divider design is optimized for repetitive division by small numbers, since this is a characteristic of several important applications planned for the processor. For such small divisors, the reciprocal is calculated and stored in a content-addressable memory. The stored reciprocals can then be used to generate quotients through fast multiplication. Simulations of the planned applications show a 20% to 30% performance increase over alternative designs.>

Data-driven arrays provide high levels of parallelism and pipelining for algorithms with no internal regularity. Most of the methods previously developed for mapping algorithms onto processor arrays assumed an unbounded array (i.e., one in which there will always be a sufficient number of processing elements (PEs) for the mapping). Implementing such an array is not practical. A more practical approach would be to assign the PEs to chips and map the given algorithm onto the new array of chips. The authors describe a way to directly map algorithms onto a multiple-chip data-driven array, where each chip contains a limited number of PEs. There are two optimization steps in the mapping. The first is to produce an efficient mapping by minimizing the area (i.e., the number of PEs used) as well as optimizing the performance (pipeline period and latency) for the given algorithm, or finding a trade-off between area and performance. The second is to divide the unbounded array among several chips each containing a bounded number of PEs.>

A novel, hybrid number representation is proposed. It includes the two's complement representation and the signed-digit representation as special cases. Such a hybrid representation is capable of bounding the maximum length of carry propagation chains during addition. Thus, one can select a specific hybrid number representation that limits the maximum length of all the carry propagation chains to any desired value between one and the entire word length. The framework reveals a continuum of number representations between the two extremes of two's complement and signed-digit number systems and allows a unified performance analysis of the entire spectrum of adders based on the representation selected.>

The encoding problem (Rumelhart and McClelland 1986) is an important canonical problem. It has been widely used as a benchmark. Here, we have analytically derived minimal-sized nets necessary and sufficient to solve encoding problems of arbitrary size. The proofs are constructive: we construct n-2-n encoders and show that two hidden units are also necessary for n > 2. Moreover, the geometric approach employed is general and has much wider applications. For example, this method has also helped us derive lower bounds on the redundancy necessary for achieving complete fault tolerance (Phatak and Koren 1992a,b).

It has been recognized that the yield of fault-tolerant VLSI circuits depends on the size of the fault clusters. Consequently, models for yield analysis have been proposed for large-area clustering and small-area clustering, based on the two-parameter negative-binomial distribution. The addition of a new parameter, the block size, to the two existing parameters of the fault distribution is proposed. This parameter allows the unification of the existing models and, at the same time, adds a whole range of medium-size clustering models. Thus, the flexibility in choosing the appropriate yield model is increased. Methods for estimating the newly defined block size are presented and the approach is validated through simulation and empirical data.>

The authors analyze the performance of multiprocessor systems with a multistage interconnection network in the presence of faulty components. Models for estimating the system performance, as measured by its bandwidth and processing power, are developed for two different modes of operation. In the first mode, the operation of the system is fully synchronized and all processors which require memory access issue their requests simultaneously. In the second, each processor is allowed to issue its request at any time instant. For each of the two modes of operation, two models are presented providing lower and upper estimates for the bandwidth of multistage systems and an upper estimate for their processing power. The operation of 16*16 synchronous and asynchronous reconfigurable systems has been simulated and the bandwidth and processing power have been calculated.>

A different approach to hardware evaluation of elementary functions for high-precision floating-point numbers (in particular, the extended double precision format of the IEEE standard P754) is examined. The evaluation is based on rational approximations of the elementary functions, a method which is commonly used in scientific software packages. A hardware model is presented of a floating-point numeric coprocessor consisting of a fast adder and a fast multiplier, and the minimum hardware required for evaluation of the elementary functions is added to it. Next, rational approximations for evaluating the elementary functions and testing the accuracy of the results are derived. The calculation time of these approximations in the proposed numeric processor is then estimated. It is concluded that rational approximations can successfully complete with previously used methods when execution time and silicon area are considered.>

The building blocks in a given floorplan have several possible physical implementations yielding different layouts. A discussion is presented of the problem of selecting an optimal implementation for each building block so that the area of the final layout is minimized. A polynomial algorithm that solves this problem for slicing floorplans was presented elsewhere, and it has been proved that for general (nonslicing) floorplans the problem is NP-complete. The authors suggest a branch-and-bound algorithm which proves to be very efficient and can handle successfully large general nonslicing floorplans. The high efficiency of the algorithm stems from the branching strategy and the bounding function used in the search procedure. The branch-and-bound algorithm is supplemented by a heuristic minimization procedure which further prunes the search, is computationally efficient, and does not prevent achieving a global minimum. Finally, the authors show how the nonslicing and the slicing algorithms can be combined to handle efficiently very large general floorplans.>

The authors analyze the performance (over time) of multistage multiprocessors in the presence of faults. A commonly used measure for the performance of an interconnection network is the bandwidth, BW(t), defined as the expected number, at time, t, of requests for the shared memory which are accepted per cycle. They present two models for calculating the bandwidth of the multistage network. These models generalize previously suggested models to allow the presence of faulty links, faulty processors, and faulty memories. The first model is computationally simple but too pessimistic, since it assumes that a memory request blocked by the network is lost. The second model assumes that when a processor's memory request is blocked, it reissues its request in the consecutive network cycle. This model which is computationally more complex, provides an upper estimate for the network bandwidth. The second model allows the calculation of other measures for the system's performance.>

The problem of general block placement in VLSI is considered, using the constructive approach in which blocks are selected and located one at a time. Some well-known strategies are presented for the selection of the next block to be located, novel ones are proposed, and a methodology to evaluate them is established. It is then shown that the optimization problem arising in constructive placement can be reduced to several much simpler sub problems. Objective functions for locating the selected block to achieve a good layout are presented for three different metrics: the squared Euclidean, rectilinear, and Euclidean. Appropriate optimization problems are obtained and solved analytically, using efficient computation schemes. These solutions have been implemented and are used in a real VLSI chip design environment. It is shown that the squared Euclidean and the rectilinear metrics are preferable to the Euclidean one.>

The objective of fault-tolerant computing systems is to provide an error-free operation in the presence of faults. The system has to recover from the effects of a fault by employing certain recovery procedures like program rollback, reload, and restart, etc. However, these recovery procedures, result in interruptions in the system's operation, thus reducing the availability of the system for user applications. Fault-tolerant systems for critical applications include, therefore, standby spares that are ready to replace active modules which fail to recover from the effects of a fault. A standby spare may also be used to replace a module suffering from frequent fault occurrences resulting in too many repetitions of the recovery process, in order to increase the availability of the system for user applications. In this case a module switching policy is needed indicating upon a fault occurrence, whether to retry a failing module or switch it out and replace it by a spare, considering the remaining mission time and the probability of a system crash. A module switching policy for dynamic redundancy systems is presented in this paper and the improvement in application-oriented availability due to the use of this policy is illustrated.

The effect of incorporating a priority scheme into a data flow computer is studied in this paper. Specifically, we deal with the scheduling of instructions in a data flow program, and the mechanisms by which such scheduling may be implemented within a data flow computer. We show that the assignment of priorities to data flow operations is a special case of a problem in scheduling theory, and also belongs to the NP-complete class of problems. Therefore, we develop a heuristic approach, based on the well-known Critical Path algorithm, as a basis for determining instruction priorities. Our conclusions, based on the simulation of programs executed in a modified data flow computer, show that adding a priority mechanism is not justifiable in the general case. This is due mostly to the inability to reach the potential improvement offered by scheduling operations, because of implementation restrictions. Nevertheless, certain algorithms (e. g., DFT) can still benefit from the proposed scheme, mainly because of their highly regular, static structure.

The incorporation of different forms of redundancy has been recently proposed for various VLSI and WSI designs. These include regular architectures, built by interconnecting a large number of a few types of system elements on a single chip or wafer. The motivation for introducing fault-tolerance (redundancy) into these architectures is two-fold: yield enhancement and performance (like computational availability) improvement.

New challenges have been brought to fault-tolerant computing and processor architecture research because of developments in IC technology. One emerging area is development of architectures, built by interconnecting a large number of processing elements on a single chip or wafer. Two important areas, related to such VLSI processor arrays, are the focus of this paper; they are fault-tolerance and yield improvement techniques. Fault tolerance in these VLSI processor arrays is of real practical significance; it provides for much-needed reliability improvement. Therefore, we first describe the underlying concepts of fault tolerance at work in these multiprocessor systems. These precepts are useful to then present certain techniques that will incorporate fault tolerance integrally into the design. In the second part of the paper we discuss models that evaluate how yield enhancement and reliability improvement may be achieved by certain fault-tolerant techniques.

The above paper1presents an approach to the design of fault- tolerant processor arrays. In Section IV of this paper (related work on fault-tolerant networks) the author criticizes a previously published approach presented by Koren [1] and by Gordon, Koren and Silberman [2]. In [1], an algorithm for structuring a linear array on a rectangular grid of processing elements (PE's), some of which may be faulty, is presented. Since similar structuring algorithms for other structures like square arrays and binary trees (in the presence of faulty PE's) are more complicated, a different strategy has been suggested in [1]. According to it, all PE's in the same row or column of the faulty processor will turn into connecting elements (CE's) and will not participate in any future processing task. The remaining PE's still constitute a rectangular grid with one less row and one less column. Consequently, the same structuring algorithms (for fault- free arrays) can be used and in many cases the grid will admit the same size of a binary tree as before [1]. If the communication link between two neighboring processors fails, only the processors within the corresponding single row or column will be declared CE's. In [2], a similar strategy has been applied to hexagonal arrays.

Recovery procedures involving time redundancy in the form of instruction retries and program rollbacks have proved to be very effective against transient failures in computer systems. A class of such recovery procedures is presented and analyzed here, and the parameters of each procedure are determined so that the system's operation is optimized. These procedures are then compared in order to select the most appropriate one for given system parameters.

Tree structures have been proposed for special-purpose and general-purpose multiprocessors due to their desirable property of logarithmic path from the root to any leaf element. Since only local communication among processors is needed in tree structures, they are well suited for the VLSI technology. Such an implementation requires an area-economical mapping of a tree on a plane. Novel mapping schemes for trees onto hexagonal arrays (or grids) and appropriate algorithms are proposed here and shown to be superior over known mappings on square arrays (or grids).

Fault-tolerance is undoubtedly a desirable property of any processor array. However, increased design and implementation costs should be expected when fault-tolerance is being introduced into the architecture of a processor array. When the processor array is implemented within a single VLSI chip, these cost increases are directly related to the chip silicon area. Thus, the increase in area should be weighed against the improved performance of the gracefully degrading fault-tolerant processor array. In addition, a larger chip area might reduce the wafer yield to an unaceptable level making the use of fault-tolerant VLSI processor arrays impractical. The objective of this paper is to devise performance measures for the evaluation of the effectiveness and area utilization of various fault-tolerant techniques. Another goal is to analyze the reduction in wafer yield and investigate the possibility of yield enhancement through redundancy.

A unified approach to a broad class of finite number representation systems is proposed. This class contains aDl positive and negative radix systems and other well-known number systems. In addition, it can be extended to include imaginary radix number systems. The proposed approach enables us to develop a single set of algoritims for arithmetic operations.

Signal reliability, as a measure of digital systems' reliability, has not been used until recently due to lack of efficient evaluation methods. A new approach to the evaluation of signal reliability is presented in this work. A reliability transfer function of digital systems is defined and a method for its evaluation is presented. This approach provides a new insight into the problem of digital system reliability. Furthermore, it simplifies signal reliability calculations and can easily be mechanized.

The classical reliability measure of digital circuits, known as functional reliability, assumes that the circuit fails whenever a fault is present in it. It has long been known that this reliability measure is overly pessimistic since digital circuits may produce correct output signals even when some faults are present in them. A different reliability measure, known as signal reliability, is the probability that the circuit output is correct. This reliability measure is analyzed first and compared to the functional reliability measure. Next, a new procedure for the evaluation of the signal reliability measure is presented.

In this note we investigate the conditions under which the paths which propagate a fault in a combinational network to the network output are not necessarily entirely sensitized.

It is well known that static redundancy techniques are very efficient against intermittent (transient) faults which constitute a large portion of logic faults in digital systems. However, very little theoretical work has been done in evaluating the reliability of modular redundancy systems which are subject to intermittent malfunction occurrences. In this paper we present a statistical model for intermittent faults and use it to analyze the reliability of NMR systems in mixed intermittent and permanent fault environments.

A unified approach to a broad class of number systems is proposed in this paper. This class contains all positive and negative radix systems and other well-known number systems. The proposed approach enables us to develop a single set of algorithms for arithmetic operations and conversion methods between number systems.

A continuous-parameter Markov model for intermittent faults in digital systems is presented. This continuous model is more realistic than discrete-parameter models previously presented by other authors. The results obtained using the proposed model can be reduced to those obtained from the previous models, by using appropriate approximations.

The problem considered in this paper is that of generating sequential decision trees (SDT's) for fault diagnosis in digital combinational networks. Since in most applications of the decision tree the final conclusion will be that the network is failure-free, we are interested mainly in decision trees containing minimal fault detection paths. Such a procedure will reduce the cost of verifying the proper operation of the network.

Detection of intermittent faults was considered in a number of publications [1],[2]. Recently, Kamal [3] presented an approach to the diagnosis of intermittent faults in combinational networks. The methods developed so far, however, do not yield a minimal diagnosis experiment. Moreover, complete diagnosis is not obtained even in cases where it is possible.