Search

The power density of processors has increased greatly over time. Since elevated temperatures greatly shorten the lifetime of semiconductor devices, thermal management has emerged as a key topic in the design and control of computational platforms. In this paper, we provide a comprehensive yet compact survey of thermal management in cyber-physical systems. Such systems are constrained by the need to meet hard deadlines; this distinguishes them from general-purpose systems and motivates distinctive resource-management approaches.

We introduce a hardware-based mechanism to dynamically profile application blocks.Profiling information is used to prioritize critical memory loads during execution.Our mechanism yields better accuracy and performance gains than previous proposals.We extensively analyze how our mechanism improves performance.Results show that it alleviates prefetch inter-core interference. Most performance enhancing mechanisms in current processors, such as branch predictors or prefetchers, rely on program characteristics monitored at the granularity of single instructions. However, many of these characteristics can be obtained at the basic block-level instead. The coarser granularity allows a larger portion of the code to be examined, enabling a more accurate profiling and a detailed analysis of the different types of instructions executed within a block. Therefore, block-level analysis can be advantageous for performance enhancing mechanisms, as it allows us to look at how the instructions influence each other, and thus detect complex behavior patterns.In this paper, we present the Dynamic Block-Level Execution Profiler (DBLEP), a basic block level online mechanism that profiles micro-architectural bottlenecks, such as delinquent memory loads, hard-to-predict branches and contention for functional units. DBLEP operates at the basic block level and provides information that can be used to reduce the impact of these bottlenecks. A prefetch dropping scheme and a memory controller policy were developed to use the code profiling information provided by DBLEP. By taking advantage of the high profiling accuracy, these mechanisms are able to improve the processor's performance by up to 18.6% (5.3% on average). We show that our mechanism's performance is comparable to mechanisms that work on single instruction granularity, using less hardware.

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.

Thermal issues in the cyber part of cyber-physical systems (CPSs) has attracted considerable attention in recent years. Heat generation due to energy consumption results in accelerated thermal damage to the processing units, reducing their lifetime. Fault tolerance contributes to a large fraction of this thermal behavior in CPS since it is implemented using redundant computations. This paper studies the use of dynamic actuator derating (i.e., artificially limiting the maximum actuator output) for reducing the need to apply maximum redundancy. By targeting the use of fault-tolerance, we are able to obtain significant reductions in computer energy expenditure and thermal stress without lowering the reliability. This has beneficial effects on processor lifetime as well as the required energy storage.

VLSI designs are typically data-independent and as such, they must produce the correct result even for the worst-case inputs. Adders in particular assume that addition must be completed within prescribed number of clock cycles, independently of the operands. While the longest carry propagation of an n-bit adder is n bits, its expected length is only O(log"2n) bits. We present a novel dual-mode adder architecture that reduces the average energy consumption in up to 50%. In normal mode the adder targets the O(log"2n)-bit average worst-case carry propagation chains, while in extended mode it accommodates the less frequent O(n)-bit chain. We prove that minimum energy is achieved when the adder is designed for O(log"2n) carry propagation, and present a circuit implementation. Dual-mode adders enable voltage scaling of the entire system, potentially supporting further overall energy reduction. The energy-time tradeoff obtained when incorporating such adders in ordinary microprocessor's pipeline and other architectures is discussed.

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.

We present a study on estimating the dynamic power consumption of a processor based on performance counters. Today's processors feature a large number of such counters to monitor various CPU and memory parameters, such as utilization, occupancy, bandwidth, page, cache, and branch buffer hit rates. The use of various sets of performance counters to estimate the power consumed by the processor has been demonstrated in the past. Our goal is to find out whether there exists a subset of counters that can be used to estimate, with sufficient accuracy, the dynamic power consumption of processors with varying microarchitecture. To this end, we consider two recent processor configurations representing two extremes of the performance spectrum, one targeting low power and the other high performance. Our results indicate that only three counters measuring 1) the number of fetched instructions, 2) level-1 cache hits, and 3) dispatch stalls are sufficient to achieve adequate precision. These counters are shown to be effective in predicting the dynamic power consumption across processors of varying resource sizes achieving a prediction accuracy of 95%.

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.

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.

Temperature-aware techniques have established themselves as crucial steps during the design and operation of new complex ICs (e.g. dual-core microprocessors) in order to protect the ICs against high temperatures that may drastically reduce their lifetime or even render them inoperable. These techniques have been developed after it became clear that power-aware techniques and low-power design are insufficient since they still allowed hotspots to develop in the chip with temperatures considerably higher than the average temperature. The goal of this paper is to provide an overview of the state-of-the-art of temperature-aware computing. After a brief introduction, we present the current approaches to measuring the temperature of a circuit during its operation and to estimating, during the design phase, the maximum temperature that the circuit will experience. We then survey the known techniques for designing a chip with lower maximum temperature. This is followed by reviewing the currently employed run-time temperature management techniques. This paper presents a thorough review of the research done in the past decade or so in the field of thermal-aware computing and lists most of the relevant journal and conference papers on this topic.

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.

International audience; 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

Active pixel sensor (APS) CMOS technology reduces the cost and power consumption of digital imaging applications. We present a highly reliable system for the production of high-quality images in harsh environments. The system is based on a fault-tolerant architecture that effectively combines hardware redundancy in the APS cells and software correction techniques.

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.

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.

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 reliability of ADCs used in highly critical systems can be increased by applying a two-step procedure starting with sensitivity analysis followed by redesign. The sensitivity analysis is used to identify the most sensitive blocks which could then be redesigned for better reliability by incorporating fault tolerance. This paper illustrates the steps involved in incorporating fault tolerance in an ADC. Two redesign techniques to improve the reliability of a circuit are presented. Novel selective node resizing algorithms for increased tolerance against α-particle induced transients are discussed.

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.

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.

In this paper, I wish to challenge the predominant view in scholarship that the main element distinguishing Buber's Daniel (1913)' from his later book I and Thou (1923)2 is his approach to mysticism and, on a broader level, that it is that which distinguishes his earlier thought from his dialogic thought. I will claim that the approach identifying Daniel with mysticism and I and Thou with its rejection is based primarily upon a semantic distinction between the relevant passages in Daniel and those in I and Thou, rather than on a phenomenological examination thereof.3 A phenomenological examination of the so-called mystical principles considered in Daniel will reveal that Buber already rejected the possibility of unio mystica in Daniel, so that the transition to his dialogical work may not be understood as one from a position assuming the possibility of unio mystica to one that negates such a possibility. A phenomenological analysis of the descriptions of unity in Daniel and comparison to the relevant passages in I and Thou will disclose, in my opinion, that the main difference between the two books-and between the two periods in Buber's work generally-is restricted to the fact that in Daniel the dialogical principle had not yet been sufficiently articulated.

Real-time distributed computers are often used in life- critical applications. However, the complexity of such systems calls for extensive simulation studies to validate their performance and reliability before a design can be accepted and a prototype constructed. A simulator testbed has been built to model a variety of such systems quickly from a few basic building blocks. Life-critical applications require reliability levels so high that brute-force simula tion to validate these levels would take weeks of computer time. In this paper, we present studies we have conducted into the use of importance sampling in simulating real- time systems. This paper presents a interesting case- study of the use of importance sampling in an increas ingly important branch of computer engineering. Impor tance sampling may not work for all cases and over all parameter ranges. In this paper, we are interested in finding out whether (and how well) this scheme works for the case of distributed real-time systems and also the range of failure bias values for which it works well. Specifically, we look at the implementation of two heuris tics called 'forcing' and failure biasing' in the testbed. This was validated by comparing the reliability estimates with that of normal (very long) simulation. The effect of the failure bias on the dynamics of the scheme is also investigated to provide readers with some guidance on choosing appropriate bias values.

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.

As multiprocessor systems become more complex, their reliability will need to increase as well. In this paper we propose a novel technique which is applicable to a wide variety of distributed real-time systems, especially those exhibiting data parallelism. System-level fault tolerance involves reliability techniques incorporated within the system hardware and software whereas application-level fault tolerance involves reliability techniques incorporated within the application software. We assert that, for high reliability, a combination of system-level fault tolerance and application-level fault tolerance works best. In many systems, application-level fault tolerance can be used to bridge the gap when system-level fault tolerance alone does not provide the required reliability. We exemplify this with the RTHT target tracking benchmark and the ABF beamforming benchmark.

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.

Several yield-enhancement techniques are proposed for the last two stages of VLSI design, i.e., topological/symbolic and physical layout synthesis. Our approach is based on modifications of the symbolic/physical layout to reduce the sensitivity of the design to random point defects without increasing the area, rather than fault tolerance techniques. A layout compaction algorithm is presented and the yield improvement results of some industrial layout examples are shown. This algorithm has been implemented in a commercial CAD framework. Some routing techniques for wire length and via minimization are presented, and the results of wire length reduction in benchmark routing examples are shown. We demonstrate through topological optimization for PLA-based designs that yield enhancement can be applied even at a higher level of design abstraction. Experimental results show that it is possible to achieve significant yield improvements without increasing the layout area by applying the proposed techniques during layout synthesis. >

The yield of a VLSI chip depends on the sensitivity of the chip to defects occurring during the fabrication process, among other factors. To predict this sensitivity, one usually needs to compute the so-called critical area (A/sub c/), which reflects how many and how large the defects must be in order to result in a circuit failure. The main computational problem in yield estimation is to calculate A/sub c/ efficiently for complicated, irregular layouts. A novel approach is suggested for this problem that results in an algorithm that will solve it efficiently. This paper provides an interactive, accurate, and fast method for the evaluation of critical area as a design tool; the tool utilizes good visual feedback to allow layout improvement for higher yield. The algorithm is compared to other yield-prediction methods, which use either the Monte Carlo approach (VLASIC) or a deterministic approach (SCA); the algorithm is shown to be faster. It also has the advantage that it can graphically show a detailed 'defect sensitivity map' that can assist a chip designer in improving the yield of his/her layout. >

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. >

Most available models for multistate coherent systems (MCS) assume that the state sets of the system and its components are totally ordered-an assumption that greatly limits the application of the usual MCS models. This paper presents a new MCS model-a generalized multistate coherent system (GMCS) model-which assumes, more generally, that the state sets of the system and its components are partially ordered. Since the structure of a partially ordered set is very flexible, the model applies to the reliability analysis of various multistate coherent systems. As a result, the GMCS model generalizes the coherent system theory from the binary-state case to the multistate case. The authors investigate some of the properties of this generalized model. Then, system reliability is redefined and bounds for its evaluation are derived. >

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. >

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 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. >

Regular arrays of processing elements in VLSI have proved to be suitable for high-speed execution of many matrix operations. To execute an arbitrary computational algorithm on such processing arrays, it has been suggested mapping the given algorithm directly onto a regular array. The computational algorithm is represented by a data-flow graph whose nodes are to be mapped onto processors in the VLSI array. This study examines the complexity of mapping data-flow graphs onto square and hexagonal arrays of processors. We specifically consider the problem of routing data from processors in a given (source) sequence to another (target) sequence. We show that under certain conditions, the above problem is equivalent to the one of finding a minimum-diameter cyclic arrangement. The complexity of the latter problem is analyzed and upper and lower bounds on the number of intermediate rows of processors (between the source and target rows) are derived.

The topics discussed are minimization of the area occupied by a layout and related results concerning networks flow and rectilinear representation of planar graphs, based on a graph model of floorplans and layouts. Arbitrary floorplans are allowed. Given an arbitrary floorplan and the areas of the embedded building blocks, the existence and uniqueness of a zero wasted area layout are proved, and characterized by a necessary and sufficient condition. Based on this condition, a scheme is described to generate zero-wasted-area layouts. Given a family of dual network pairs for which the product of dual arc lengths are invariant, it is proved that the minimal product of their longest paths is not smaller than the maximal product of their shortest paths. It is also shown that the maximal product of the flows in such a family of dual network pairs is given by the total sum of the arc length product of each individual pair of dual arcs. An efficient procedure to derive a rectilinear representation for any planar graph is presented. >

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.

Exact expressions for the yield of an interconnection bus as a function of its physical dimensions and the parameters and distribution of the possible open-circuit and short-circuit defects are derived. The effect of introducing redundancy into the bus is examined and the optimal layout of a given bus (with and without redundancy) is obtained. Any change in the layout of a bus may affect the propagation delay of the bus and, as a consequence, the performance of the VLSI chip. Hence, the delay of the designed bus in addition to its yield must be taken into account when determining the final layout of the bus. Both yield and delay are discussed through several numerical examples. >

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. >