When a high energy particle strikes an integrated circuit, the electron-hole pairs generated in the substrate get collected at source/drain regions. The net effect on the circuit is a transient current (single event transient or SET) injected into circuit nodes. This SET can propagate and cause an error in a state register, which is called a single-event upset (SEU). We perform a detailed characterization of the impact of an SET on a logic circuit. We observe that the impact of an SET can be understood only as a two cycle phenomenon, with several possible SEU outcomes. To understand the relative probabilities of these outcomes, we perform a detailed characterization of the impact of an SET using a Monte Carlo sampling scheme which uses post-layout circuit simulations. These simulations were run in 180nm and 65nm technologies with circuits from ISCAS'85 and ITC'99 benchmarks as test cases. Based on these simulations, we observe that all the SEU outcomes are represented to a substantial extent. Further, there is a substantial fraction of outcomes in which the SET affects multiple state registers. This indicates that the traditional view of impact of an SET on a circuit as a single bit-flip and a single cycle phenomenon may not be fully justified. The impact of an SET is in reality, distributed across two cycles and across multiple state register bits.

We propose a new approach to simulation-based design optimization of multi core systems, over a large number of discrete parameters. In this approach, we embed the discrete parameter space into an extended continuous space and apply continuous space optimization techniques over the embedding to search for optimal designs. Such continuous space techniques often scale well with the number of parameters. The embedding is performed using a novel simulation-based ergodic interpolation technique, which, unlike spatial interpolation methods, can produce the interpolated value within a single simulation run irrespective of the number of parameters. In a characterization study, we find that the interpolated performance curves are continuous, piecewise smooth and have low statistical error. We use the ergodic interpolation-based approach to solve a multi-core design optimization problem with 31 design parameters. Our results indicate that continuous space optimization using ergodic interpolation-based embedding can be a viable approach for large multi-core design optimization problems.

We present a high-level synthesis flow for mapping an algorithm description (in C) to a provably equivalent register transfer level (RTL) description of hardware. This flow uses an intermediate representation which is an orthogonal factorization of the program behavior into control, data and memory aspects, and is suitable for the description of large systems. We show that optimizations such as arbiter-less resource sharing can be efficiently computed on this representation. We apply the flow to a wide range of examples ranging from stream ciphers to database and linear algebra applications. The resulting RTL is then put through a standard ASIC tool chain (synthesis followed by automatic place-and-route), and the performance and power dissipation of the resulting layout is computed. We observe that the energy consumption (per completed task) of each resulting circuit is considerably lower than that of an equivalent executable running on a low-power processor, indicating that this C-to-RTL flow offers an energy efficient alternative to the use of embedded processors in mapping algorithms to digital VLSI systems.

Interleaved address mapping has been effectively used to improve the performance of a parallely accessible memory subsystem. We propose a generalization of such mappings and study them in the framework of application specific MPSoCs. In this generalization, a section of the address bits is used to map each address to a memory bank and a row within that bank, using a look-up table(LUT). We model the problem of address mapping optimization as a Markov decision process (MDP). To solve the MDP, we propose a reinforcement learning based algorithm which learns an optimized mapping within the generalized class, for a specific application mapped to an MPSoC system. Through cycle-accurate simulations on a simulation framework specifically developed for such a study, we demonstrate that a system using an address mapping generated in this manner exhibits substantially higher performance when compared to the same system using interleaved address mappings. These results indicate that application and architecture visibility can be leveraged to obtain better mappings than generic interleaved solutions, and that an automated reinforcement learning approach can identify such mappings using only the run-time behaviour of the system.

Suppose that V = {v/sub 1/, v/sub 2/, ...v/sub n/} is a set of nodes randomly (uniformly) distributed in the d dimensional cube [0, x/sub 0/]/sup d/, and W = {w(i, j) > 0 : 1 /spl les/ i, j /spl les/ n} is a set of numbers chosen so that w(i, j) = w(j, i) = w(j, i). Construct a graph G/sub n,d,W/ whose vertex set is V, and whose edge set consists of all pairs {u/sub i/, u/sub j/} with /spl par/ u/sub i/ - u/sub j/ /spl par/ /spl les/ w(i, j). In the wireless network context, the set V is a set of labeled nodes in the network and W represents the maximum distances between the node pairs for them to be connected. We essentially address the following question: "if G is a graph with vertex set V, what is the probability that G appears as a subgraph in G/sub n,d,W/?" Our main contribution is a closed form expression for this probability under the l/sub /spl infin// norm for any dimension d and a suitably defined probability density function. As a corollary to the above answer, we also answer the question, "what is the probability that Q/sub n,d,W/ is connected?".

Internet protocol (IP) address lookup is one of the major performance bottlenecks in high-end routers. This paper presents an architecture for an IP address lookup engine based on programmable finite-state machines (FSMs). The IP address lookup problem can be translated into the implementation of a large FSM. Our hardware engine is then used to implement this FSM using a structured approach, in which the large FSM is broken down into a set of smaller FSMs which are then mapped into reconfigurable hardware blocks. The design of our hardware engine is based on a regular and well structured architecture, which is easy to scale. Our simulation results demonstrate that the FSM based architecture can easily scale to wire speed performance at OC-192 rates. Unlike previous approaches, the performance of our architecture is not constrained by memory bandwidth and is, therefore, in principle scalable with very large scale integration technology.

We consider the state assignment problem as that of the decomposition of finite stare machines and transform this decomposition problem into an orthogonal partitioning problem with a certain cost function. We justify this cost function in two ways, first by using an idealized model of multi-level logic implementation, and second by empirical studies of a particular benchmark circuit. We describe a greedy algorithm to minimize this cost function. We present results obtained by running the algorithm on a set of 16 MCNC benchmarks. We compare these results with other state assignment techniques such as JEDI and NOVA. For multilevel implementations of the benchmark state machines, we find that the implementations obtained after using JEDI were, on average, 8.52% larger in area and 81.87% slower in delay than the implementations obtained using our approach. The implementations obtained after using NOVA were, on average, 4.40% larger in area and 104.96% slower in delay when compared with implementations obtained using our approach. Our scheme has the potential to serve as an alternative to conventional state assignment tools since we observe that it produces good results for larger finite state machines.

In this paper we introduce a method for computing the Elmore delay of MOS circuits which relies on a model of the capacitance of MOS devices and a model of the Elmore delay of individual MOS devices. The resistance of a device is not explicitly modelled. The Elmore models are used to compute the Elmore delay and the 50% point delay of CMOS circuits in a static timing verifier. Elmore delays computed with these models fall within 10% of SPICE and can be computed thousands of times faster than if computed using SPICE. These models were used to verify critical paths during the design of a 600MHz microprocessor.

In a high performance microprocessor such as Digital's 30O MHz Alpha 21164, the distribution of a high quality clock signal to all regions of the device is achieved using a complex grid with multiple drivers. The large capacitance of this distribution grid together with the high clock frequency results in substantial power dissipation in the chip. In this paper, we describe techniques to size the interconnect segments (thus reducing their capacitance) of the distribution network while meeting certain design goals. These techniques place no restrictions on the topology of the network being sized, and have been successfully used on very large examples.

A static timing verifier is an important tool in the design of a complex high performance VLSI chip such as an Alpha CPU. A timing verifier uses a simple and pessimistic delay model to identify critical failing paths in the design, which then need to be fixed. However, the pessimistic delay model results in a large number of correct paths being identified as failing paths, possibly leading to wasted design resources. Therefore, each critical path identified by the timing verifier needs to be analyzed using a circuit simulator such as SPICE in order to confirm that it is a real failure. Setting up such a simulation is complex, especially when the critical path consists of structures appearing in a datapath of the CPU. In this paper, we present algorithms for the construction of a model for simulating the maximum delay through a critical path. This technique has been used to analyze several critical paths during the design of a 300 MHz Alpha CPU.