Search

Although Markov Decision Process (MDP) has wide applications in autonomous systems as a core model in Reinforcement Learning, a key bottleneck is the large memory utilization of the state transition probability matrices. This is particularly problematic for computational platforms with limited memory, or for Bayesian MDP, which requires dozens of such matrices. To mitigate this difficulty, we propose a highly memory-efficient representation for probability matrices using Binary Decision Diagram (BDD) based sampling, and develop a corresponding (Bayesian/classical) MDP solver on a CPU-GPU platform. Simulation results indicate our approach reduces memory by one and two orders of magnitude for Bayesian/classical MDP, respectively.CCS CONCEPTS• Theory of computation $\rightarrow$ Data compression; Parallel algorithms; Sequential decision making; • Mathematics of computing $\rightarrow$Bayesian computation

By employing the Optimal Bayesian Robust (OBR) policy, Bayesian Markov Decision Process (BMDP) can be used to solve the Gene Regulatory Network (GRN) control problem. However, due to the "curse of dimensionality", the data storage limitation hinders the practical applicability of the BMDP. To overcome this impediment, we propose a novel Duplex Sparse Storage (DSS) scheme in this paper, and develop a BMDP solver with the DSS scheme on a heterogeneous GPU-based platform. The simulation results demonstrate that our approach achieves a 5x reduction in memory utilization with a 2.4% "decision difference" and an average speedup of 4.1x compared to the full matrix based storage scheme. Additionally, we present the tradeoff between the runtime and result accuracy for our DSS techniques versus the full matrix approach. We also compare our results with the well known Compressed Sparse Row (CSR) approach for reducing memory utilization, and discuss the benefits of DSS over CSR.

Flash transistors serve as the technology of choice for implementing nonvolatile memory. Current flash memory densities are increasing to meet storage demands. One of the key features that has resulted in increasing flash memory densities is the ability to program a flash transistor to have multiple threshold voltages. This feature has recently been exploited to implement ternary-valued logic. However, this implementation exhibited increased delays, due to the lowered Vgs values which result from using multiple threshold voltages. In this work, we present a circuit implementation that uses flash transistors to implement multi-valued digital circuits. The flash transistors used in our implementation only need two threshold voltages. As a result they have high Vgs values which improves delays significantly, and have higher write endurance as well. We evaluate our design methodology through circuit simulations, and compare our results to a CMOS standard cell based approach as well as the previously reported implementation of ternary-valued logic using flash transistors. Averaged over 20 designs, we report improvements in delay (23% lower), power (5% lower), energy (26% lower) and physical area (4% lower) compared to a CMOS standard cell based implementation. This is significant since it is hard for a new circuit approach to beat the established standard cell based approach in all the figures of merit (delay, area, power and energy. Compared to the ternary flash-based implementation, we operate at 3.15x faster than the ternary flash-based designs, while consuming more power and energy. The design approach presented in this paper targets high performance applications, unlike the TLC-based approach which targets low power and low speed applications. Also, the proposed approach scales elegantly to multi-valued logic using more than three values as well.

Modern microprocessors contain several Special Function Units (SFUs) such as specialized arithmetic units, cryptographic processors, etc. In recent times, applications such as cloud computing, web-based search engines, and network applications are widely used, and place new demands on the microprocessor. Hashing is a key algorithm that is extensively used in such applications. Hashing is typically performed in software. Thus, implementing a hardware-based hash unit on a modern microprocessor would potentially increase performance significantly. In this paper, we present the circuit design for a hardware hash unit (HU) for modern microprocessors, using a 45nm technology. Our proposed hardware hash unit is based on the use of a CAM to implement each bin of the hash function. We simulate the HU circuit and compare it with a traditional CAM design. We demonstrate an average power reduction of 5.48x using the HU over the traditional CAM. Also, we show that the HU can operate at a maximum frequency of 1.39 GHz (after accounting for process, voltage and temperature (PVT) variations and accounting for wiring parasitics). Furthermore, we present the delay, power and area trade-offs of the HU design with varying hash table sizes.

Traditionally, floating gate (flash) transistors have been used exclusively to implement non-volatile memory in its various forms. Recently, we showed that flash transistors can be used to implement digital circuits as well. In this paper, we present the details on the realization and characteristics of the block-level flash-based digital design. The current work describes the synthesis flow to decompose a circuit block into a network of interconnected FCs. The resulting network is characterized with respect to timing, power and energy, and the results are compared with a standard-cell based realization of the same block (obtained using commercial tools). We obtain significantly improved delay (0.59×), power (0.35×) and cell area (0.60×) compared to a traditional CMOS standard-cell based approach, when averaged over 12 standard benchmarks. It is generally rare that a circuit methodology yields results that are better than existing commercial standard-cell based flows in terms of delay, area, power and energy, and in this sense, we submit that our results are significant. Additional benefits of a flash-based digital design is that it allows for precision speed binning in the factory, and also enables in-field re-programmability (we note that our flash-based design is not an FPGA, but rather an ASIC style design) to counteract the speed degradation of a design due to aging. These benefits arise from the fact that the threshold voltage of flash devices can be controlled with precision.

Bloom filters are commonly used to test for set membership. A Bloom filter consists of a series of hash functions, whose combined signature is used to construct a composite hash. Applications are broad, and include networking, transactional memory, server load balancing etc. Several realizations, both in hardware and software, have been proposed in academia and industry, but a reliable means to empirically test the statistical behavior of Bloom filters is lacking. In this paper, we present an efficient, practical methodology to validate the statistical performance of Bloom filters. This paper does not focus on the design of a new Bloom filter. Our scheme is based on the use of the NIST test suite, which is a widely accepted means to test for randomness in the cryptography community. In particular, we first test the randomness of the hash functions that comprise the Bloom filter in isolation, and then test for randomness of the Bloom filter, which is constructed by combining the hash functions. We also prove that randomness is a sufficient condition for the uniformity of the hash function and the Bloom filter output. Finally, we test our approach using two classes of Bloom filters, and based on the results, we provide practical guidelines for designing Bloom filters.

In this paper, we present a circuit-level analysis of deep voltage-scaled FPGAs, which operate from full supply to sub-threshold voltages. The logic as well as the interconnect of the FPGA are modeled at the circuit level, and their relative contribution to the delay, power and energy of the FPGA are studied by means of circuit simulations. Three representative designs are studied to explore these design trade-offs. We conclude that the energy and delay-minimal FPGA design is one in which both the interconnect and logic are curtailed from scaling below a fixed voltage (about 550mV in our experiments). If power is a more important design factor (at the cost of delay), it is beneficial to operate both the logic and interconnect between 300mV and 800mV.

In recent years, post-silicon debugging has become a significantly difficult exercise due to the increase in the size of the electrical state of the IC being debugged, coupled with the limited fraction of this state that is visible to the debug engineer. As the number of transistors increases, the number of possible electrical states increases exponentially, while the amount of information that can be accessed grows at a much slower rate. This difficulty is compounded by the outsourcing of IP blocks, which creates more black boxes that the debug engineer must work around. As a result, when an IC fails tracking down the cause of the failure becomes a monumental task, and debugging becomes more art than science. One source of errors in a test circuit is the fluctuation of the power supplies during a single clock cycle. These supply variations can increase or decrease the speed of a circuit and lead to errors such as hold time violations and setup time violations. This paper presents a circuit that samples precisely the power supply multiple times in a clock cycle, allowing the debug engineer to quantify the variations in the supply over a clock cycle. With this information, a better understanding of the electrical state of the test chip is made possible. The circuit presented in this paper can sample the supply voltage with a quantization of 0.291mV, and the output is linear with an R2 value of 0.9987.

The FinFET device has gained much traction in recent VLSI designs. In the FinFET device, the conduction channel is vertical, unlike a traditional bulk MOSFET, in which the conduction channel is planar. This yields several benefits, and as a consequence, it is expected that most VLSI designs will utilize FinFETs from the 20nm node and beyond. Despite the fact that several research papers have reported FinFET based circuit and layout realizations for popular circuit blocks, there has been no reported work on the use of FinFETs for Field Programmable Gate Array (FPGA) designs. The key circuit in the FPGA that enables programmability is the n-input Look-up Table (LUT). An n-input LUT can implement any logic function of up to n inputs. In this paper, we present an evaluation of several FPGA LUT designs. We compare these designs from a performance (delay, power, energy) as well as an area perspective. Comparisons are conducted with respect to a bulk based LUT as well. Our results demonstrate that all the FinFET based LUTs exhibit better delays and energy than the bulk based LUT. Based on our comparisons, we have two winning candidate LUTs, one for high performance designs (3X faster than a bulk based LUT) and another for low energy, area constrained designs (83% energy and 58% area compared to a bulk based LUT).

Field programmable gate arrays (FPGAs) are the implementation platform of choice when it comes to design flexibility. However, the high power consumption of FPGAs (which arises due to their flexible structure), make them less appealing for extreme low power applications. In this paper, we present a design of an FPGA look-up table (LUT), with the goal of seamless operation over a wide band of supply voltages. The same LUT design has the ability to operate at sub-threshold voltage when low power is required, and at higher voltages whenever faster performance is required. The results show that operating the LUT in sub-threshold mode yields a (~80x) lower power and (~4x) lower energy than full supply voltage operation, for a 6-input LUT implemented in a 22nm predictive technology. The key drawback of sub-threshold operation is its susceptibility to process, temperature, and supply voltage (PVT) variations. This paper also presents the design and experimental results for a closed-loop adaptive body biasing mechanism to dynamically cancel these PVT variations. For the same 22nm technology, we demonstrate that the closed-loop adaptive body biasing circuits can allow the FPGA to operate over an operating frequency range that spans an order of magnitude (40 MHz to 1300 MHz). We also show that the closed-loop adaptive body biasing circuits can cancel delay variations due to supply voltage changes, and reduce the effect of process variations on setup and hold times by 1.8x and 2.9x respectively.

In this paper, we present a new IC-based gamma radiation detector. We report 3D simulation results for the PIN diode structure which is used in this detector, along with a discussion of the architecture of the readout electronics for this detector. Gamma detection traditionally consists of three parts -- i) a scintillator, ii) a detector unit and iii) the readout electronics. Our PIN diode based detector uses a traditional scintillator and a bialkali photocathode to convert the scintillated light into an electron current. This current is detected by the PIN diodes in the detector, which is fused to the photocathode. This structure has many advantages. Sensitivity is enhanced by placing the photocathode and detector IC on all six faces of the NaI scintillating crystal. Our detector is small, has a low-dead-time and it consumes very low power. The sensitive area of the chip is 75%, which is higher than any existing solid-state gamma detector. We have verified the operation of each component of the system by performing circuit-level simulations. The detector is implemented in a low-cost 0.5 um process. The optimal parameters for the PIN diode detector are explored through 3D device simulations. Our results show that a detector sensitivity better than 20 keV is easily achievable with a PIN diode of dimensions 2.5 um X 2.5 um.

Most existing Network-on-Chip (NoC) designs operate at the same or lower clock speed as the processing elements (PEs). Recently, a new source-synchronous ring-based NoC architecture has been proposed, which runs significantly faster than the PEs and offers a significantly higher bandwidth and lower communication latency. However, the ring-based design assumes a separate clock distribution scheme for the NoC and the PEs, and uses a standard mesh topology for the NoC. In this work, we present a source synchronous ring-based NoC, laid out in an H-tree topology, with each data link being routed parallel to a clock ring. The clock is generated and distributed by multiple standing wave oscillator (SWO) rings, which are also laid out in an H-tree topology. Our design allows the PEs to extract a low jitter clock directly from the high speed ring-based SWO clock by division. Moreover, since the PEs are synchronous with the ring clock, they do not need synchronizers while communicating with the NoC. We also show that by recursively duplicating links in the H-tree based source synchronous NoC (Hnoc), we can obtain new hybrid NoC structures. In the limit, this recursive duplication causes the H-tree based NoC to morph into the meshbased source synchronous NoC (Mnoc). The performance of each such intermediate hybrid NoC structure is quantified in terms of area, link utilization and contention free latency. We also enhance the performance of the hybrid NoCs by widening congested links, and quantify the tradeoffs. Experimental results show that the hybrid NoC designs can provide significantly lower latency (upto 5× lower) and are able to sustain a higher injection rate (upto 6.8× higher) compared to a state of the art mesh. Moreover, these hybrid NoC designs use fewer buffers (upto 19.4% less) and lower wire length (upto 19.7% lower) compared to a mesh. Based on the performance and the area tradeoffs, an NoC designer can select any hybrid NoC structure among the presented.

Fast key generation algorithms which can generate random sequences of varying atomic lengths and throughput are important for secure data communication. In this paper, we present a non-linear congruential method for generating high quality random numbers at flexible throughput rates of upto 66 Gbps, on a GPU platform. Each random number can have up to 4096 key bits. The method can be easily extended for implementation on hardware platforms like FPGAs and ASICs as well. Our key generator is comprised of N Linear Congruential Generators (LCGs) running in parallel; we have chosen N=4096 for the GPU implementation. The outputs of the LCGs are combined using N encoded majority functions. The encoded majority function used for any bit is changed in every generation iteration. In our GPU implementation of the Non-Linear Congruential Generator (GPU-NLCG), it is possible to alter the LCG functions on the fly by changing the primes periodically without interrupting the generation. Our GPU-NLCG can be used for high speed cryptographic key generation for rates up to 66 Gbps and can be easily integrated into multi-threaded applications in cryptography and Monte Carlo methods. The GPU-NLCG passes the NIST, Diehard and Dieharder battery of tests of randomness, which ensure the quality of our ciphers.

In the quest to understand and cure genetic diseases such as cancer, the fundamental approach being taken is undergoing a gradual change. It is becoming more acceptable to view these diseases as an engineering problem, and systems engineering approaches are becoming more accepted as a means to tackle genetic diseases. In this light, we believe that logic synthesis techniques can play a very important role. Several techniques from the field of logic synthesis can be adapted to assist in the arguably huge effort of modeling and controlling such diseases. The set of genes that control a particular genetic disease can be modeled as a Finite State Machine (FSM) called the Gene Regulatory Network (GRN). Important problems include (i) inferring the GRN from observed gene expression data from patients and (ii) assuming that such a GRN exists, determining the "best" set of drugs so that the disease is "maximally" cured. In this paper, we report initial results on the application of logic synthesis techniques that we have developed to address both these problems. In the first technique, we present Boolean Satisfiability (SAT) based approaches to infer the logical support of each gene that regulates melanoma, using gene expression data from patients of the disease. From the output of such a tool, biologists can construct targeted experiments to understand the logic functions that regulate a particular gene. The second technique assumes that the GRN is known, and uses a weighted partial Max-SAT formulation to find the set of drugs with the least side-effects, that steer the GRN state towards one that is closest to that of a healthy individual, in the context of colon cancer. Our group is currently exploring the application of several other logic techniques to a variety of related problems in this domain.

Negative Bias Temperature Instability (NBTI) causes the threshold voltage of PMOS devices to degrade with time, resulting in a reduced lifetime of a CMOS IC. In this paper, we present an approach to mitigate the degradation due to NBTI for off-chip output drivers. Our approach is based on forcibly inducing relaxation in the individual fingers of the output driver (which is typically implemented in a multi-fingered fashion). The individual fingers are relaxed in a round-robin manner, such that at any given time, k out of n fingers of the driver are being relaxed. Our results show that the proposed approach significantly extends the lifetime of the output driver.

For secure high data-rate communications, fast key generation algorithms are crucial. In this paper, we present a VLSI implementation of a Non-Linear Feedback Shift Register (NLFSR) for cryptography applications. Unlike existing cryptographic key generation techniques, our NLFSR generates multiple (64 in our implementation) key bits in each clock cycle. This enables its use in secure, high speed communications. Our NLFSR is implemented using a plurality (3 in our implementation) of LFSRs. The outputs of 64 bits from each LFSR are combined using 64 encoded majority functions, where the majority function used for any bit is changed at every clock cycle. We demonstrate that our NLFSR can generate keys which may be used for OC-768 optical fiber communication, which operates at 40 Gbps. The keys from our NLFSR pass all the tests in the NIST suite, which is a defacto benchmark used in industry to evaluate the quality of ciphers.

Boolean Satisfiability (SAT) is a core NP-complete problem. Several heuristic software and hardware approaches have been proposed to solve this problem. In this paper we present a Boolean satisfiablity approach with a new GPU-enhanced variable ordering heuristic. Our results demonstrate that over several satisfiable and unsatisfiable benchmarks, our technique (MESP) performs better than MiniSAT. We show a 2.35× speedup on average, over 68 from the SAT Race (2008) competition.

Advances in GPU technology have propelled the GPU into arenas far afield from the traditional, isolated roles they have previously played. With hundreds of processing units in a single GPU, substantial speedups can be achieved by harnessing their power to augment the performance of the traditional single- or multi-core CPU on certain compute-intensive applications. However, utilizing the GPU requires both a change in the programmer's traditional algorithmic model as well as a judicious selection of algorithm being used for the problem. This paper reviews the GPU architecture and the tools available to utilize this valuable resource. It also provides insight into the type of problem best suited for the GPU as well as programming styles required to fully harness the power of the GPU. We present examples of specific EDA algorithms that can benefit from GPU acceleration, using both the CUDA and OpenCL environments.

Leakage power consumption is a large fraction of the total power consumption in contemporary VLSI designs. Since memories occupy a large portion of the total area of many high-performance ICs, it is crucial to reduce the leakage energy of memories. This problem is particularly aggravated for memories implemented in the 45nm technology node, since these processes exhibit significantly higher leakage power. For these memories, leakage is a significant problem not only from a power point of view, but also from a performance degradation standpoint. In this paper, we quantify this problem and provide a solution, using a 512KByte SRAM implemented in a 45nm bulk process as a design example. We show that implementing the SRAM as a monolithic memory results in increased delay as well as power. We illustrate a methodology to optimally reduce leakage power and improve performance in memories by splitting the memory array into word line groups (WLGs) which are selectively forward body biased when accessed. We present a derivation of optimal number of WLGs and the forward body bias voltage value, and show that our approach results in a 9:2% access time reduction, and a 53:4% reduction in power during a read operation. Our approach also achieves an 18% reduction in power during a write operation and a 69% leakage power improvement. The area overhead of our scheme is 7:2% compared to a monolithic memory.

Multi-node optimization using Boolean relations is a powerful approach for network minimization. In this paper, we present an algorithm to perform Boolean relation-based multi-node optimization using a robust, fast and memory efficient algorithm. In particular, we simultaneously optimize two nodes at a time. The robustness of our approach arises from the use of a window-based technique for computing these Boolean relations. Secondly, we perform early quantification during the computation, keeping memory utilization low. Finally, we employ smart heuristics for selecting the node pair to be optimized simultaneously.These features allow the approach to scale well and provide good results for large designs. We perform experiments on a set of large benchmarks and compare our algorithm's performance to a recent SAT-based network optimization technique using complete don't cares. On average, we achieve a 15% reduction in literal count across all the large designs, compared to the complete don't care-based method while maintaining small runtimes and low memory usage.

In recent times, the contribution of leakage power to the total power consumption of a chip has been increasing at an alarming rate. Leakage power is expected to exceed dynamic power in newer process technologies. Since leakage exhibits an exponential increase with temperature, it is possible that the high leakage of an IC causes a temperature increase, which in turn causes an increase in leakage, and so on, until the IC fails due to overheating. At the very least, this may cause the temperature and power consumption of the IC to be poorly estimated by traditional thermal or power modeling techniques. We developed a framework to model this situation in an FPGA context. Our CAD framework accurately models the total power consumption of the design at a given temperature, finds the thermal profile of the IC under this power consumption, and then uses this new thermal information to update the power consumption. This is iterated until the temperature of the IC converges, or until the temperatures on the die exceed a safe value. The iterations are very fast, due to the use of accurate and compact mathematical macromodels for leakage and temperature computation in the inner loop. We have exhaustively verified the fidelity of all our leakage macromodels. They estimate the leakage, at any temperature, to within 3% of the values generated by SPICE, while providing greater than four orders of magnitude speedup over explicit SPICE runs. Our experiments show that this model helps avoid an incorrect estimation of chip temperature and total power consumption, and also helps detect the increase in device temperature beyond a safe value. The average (maximum) error of our temperature estimates has been found to be within 1% (2.5%) compared to a full-chip 3D temperature modeling tool.

Single event upsets (SEUs) are becoming increasingly problematic for both combinational and sequential circuits with device scaling, lower supply voltages and higher operating frequencies. To design radiation tolerant circuits efficiently, techniques are required to analyze the effects of a particle strike on a circuit early in the design flow and also to evaluate the circuit's resilience to SEU events. In this paper, we present an analytical model for SEU induced transients in combinational circuits. The pulse width of the voltage glitch due to an SEU event is a good measure of SEU robustness and our model efficiently computes it for any combinational gate. The experimental results demonstrate that our model is very accurate with a very low pulse width estimation error of 4% compared to SPICE. Our model gains its accuracy by using a non-linear transistor current model, and by considering the effect of tauB of the radiation induced current pulse. Our analytical model is very fast and accurate, and can therefore be easily incorporated in a design flow to implement SEU tolerant circuits.

In this paper, we explore the implementation of fault simulation on a graphics processing unit (GPU). In particular, we implement a fault simulator that exploits thread level parallelism. Fault simulation is inherently parallelizable, and the large number of threads that can be computed in parallel on a GPU results in a natural fit for the problem of fault simulation. Our implementation fault- simulates all the gates in a particular level of a circuit, including good and faulty circuit simulations, for all patterns, in parallel. Since GPUs have an extremely large memory bandwidth, we implement each of our fault simulation threads (which execute in parallel with no data dependencies) using memory lookup. Fault injection is also done along with gate evaluation, with each thread using a different fault injection mask. All threads compute identical instructions, but on different data, as required by the Single Instruction Multiple Data (SIMD) programming semantics of the GPU. Our results, implemented on a NVIDIA GeForce GTX 8800 GPU card, indicate that our approach is on average 35 x faster when compared to a commercial fault simulation engine. With the recently announced Tesla GPU servers housing up to eight GPUs, our approach would be potentially 238 times faster. The correctness of the GPU based fault simulator has been verified by comparing its result with a CPU based fault simulator.

In this work, we present a CODEC design for the forbidden transition free crosstalk avoidance code. Our mapping and coding scheme is based on the Fibonacci numeral system and the mathematical analysis shows that all numbers can be represented by FTF vectors in the Fibonacci numeral system (FNS). The proposed CODEC design is highly efficient, modular and can be easily combined with a bus partitioning technique. We also investigate the implementation issues and our experimental results show that the proposed CODEC complexity is orders of magnitude better compared to the brute force implementation. Compared to the best existing approaches, we achieve a 17% improvement in logic complexity. A high speed design can be achieved through pipelining.

In this paper, we present a pipelined Network of PLA based circuit design approach. Our approach can be used to realize an arbitrary logic circuit with an extremely high throughput and low latency. Using logic synthesis tools to decompose a logic circuit into this framework, and appropriately inserting "stutter" blocks to balance the logical depth of all paths in the decomposed circuit, we come up with a pipelined network of PLA netlist. We have demonstrated the effectiveness of the approach via SPICE simulations and layout generation experiments. Throughput, latency, and area are compared with competing approaches, demonstrating the power of this design style. We show that our approach has a 75% better throughput than the asynchronous micropipelining based technique, and a latency which is 63% that of the asynchronous scheme. Both techniques were implemented in a super-threshold fashion. We have also conducted Monte Carlo experiments to validate the approach under variations.

With current technology trends, FPGA routing is an important problem, since routing in FPGAs contributes significantly to delay and resource utilization, as compared to the logic portion of FPGAs. In this paper we improve the FPGA routing characteristics by applying the technique of network coding.This relatively new technique was developed in the context of communication networks, and proven to improve network throughput, reliability, etc. To the best of our knowledge, this paper is the first to apply network coding to improve FPGA routing. Our preliminary results are implemented in the VPR 4.30 tool suite. We demonstrate (on average) a 14% reduction in worst case delay, a 3% reduction in wirelength and a healthy reduction in the routing track count on several MCNC benchmark circuits, over the current best known results. By using carefully generated cost models for applying the technique of network coding, we show that this routability improvement is accompanied by a zero percent CLB utilization overhead and

High Speed VLSI design utilizes heavy pipelining, resulting in a large number of flip-flops in the circuit. Hence there is a strong motivation to design fast, low power and area efficient flip-flops. In this paper, we present a pulsed flip-flop design based on a novel pulse generator circuit. Our design achieves significantly improved speed when compared to recent pulsed flip-flop design, as well as a traditional master-slave D flip-flop. Monte Carlo simulations demonstrate that our design is significantly more robust to variations than the other flip-flops. Our design consumes low power as well. Also we have performed the layout of our design and shown that our layout area is smaller than a traditional D flip-flop.

Integrated circuit manufacturing costs are increasing with decreasing device feature sizes, due to significant increases in mask costs. At the same time, systematic processing variations due to optical proximity effects are also increasing, making it harder to predict the circuit behavior with fidelity. Therefore, there is a need to implement designs using regular circuit structures. In this paper, we present a new structured ASIC approach which utilizes an array of 2-input NAND gates. Our NAND2 array based circuit implementation reduces manufacturing costs, and design turn-around times because different designs can share the same masks up to the poly layer. The regular layout structure of our NAND2 array also helps in reducing systematic variations. We compared the performance of our NAND2 array with the ASIC approach by implementing several benchmark circuits using both methods. The experimental results demonstrate that on average, our approach has a delay penalty of 40%, an area penalty of 12%, and a power increase of 7%, compared to an ASIC design approach. This is better than the previously reported structured ASIC approaches. We also performed lithographical simulations of the poly and metal masks of the designs implemented using our approach as well as the ASIC design approach. These lithographical simulation results demonstrate that our approach has lower errors on the poly and the Metal1 layers by 7% and 24% respectively, compared to the ASIC approach.

When a signal traverses on-chip voltage domains, a level shifter is required. Inverters can handle a high to low voltage shift with minimal leakage. For a low to high voltage level translation, inverters tend to consume a large amount of leakage power, and hence special circuits have been proposed for this type of translation. This paper reports a novel single-supply "true" (in the sense that it can handle a low to high, or high to low voltage level conversion) voltage level shifter, which can handle low-to-high and high-to-low voltage translation. Such a requirement arises in many modern ICs or systems-on-chip (SoCs). The use of single supply voltage reduces circuit complexity by eliminating the need for routing both supply voltages. The proposed circuit was extensively simulated in a 90 nm technology using SPICE. Simulation results demonstrate that the level shifter is able to perform voltage level shifting with low leakage for both low to high, as well as high to low voltage level translation. We have validated the correct operation of the proposed level shifter under process and temperature variations as well.

In this paper, we present a radiation-hardened digital design approach. This approach is based on the use of code word state preserving (CWSP) elements at each flip-flop of the design, and leaving the rest of the design unaltered. The CWSP element provides 100% SET protection for glitch widths up to min{Dmin/2, (Dmax - Delta)/2}, where Dmin and Dmax are the minimum and maximum circuit delay respectively and Delta is an extra delay associated with our SET protection circuit. The CWSP circuit has two inputs - the latch output signal and the same signal delayed by a quantity delta. In case an SET error is detected, then the current computation is repeated, using the correct output, which is generated later in the same clock period by the CWSP element. Unlike previous approaches, we use the CWSP element in a secondary path and the CWSP logic is designed to minimally impact the critical delay path of the design. The delay penalty of our approach (averaged over several designs) is less than 1%. Thus our technique is applicable for high-speed designs, where the additional delay associated with SET protection must be kept at a minimum.

The current work describes a new standing wave oscillator scheme aimed for clock propagation on coplanar transmission lines on a silicon die. The design is aimed for clock signaling in the gigahertz range (we are able to achieve clock rates of 8 GHz and above). The clock is transported as an oscillatory wave on a pair of conductors. An oscillatory standing wave is formed across a transmission line loop, which is connected beginning-to-end through a Mobius configuration. A single cross coupled inverter pair is required to maintain oscillation across the ring. The design is aimed to achieve low skew, low power and extreme high frequency global clock situations. The energy recycling nature of a standing wave along a transmission line allows us to keep very high frequencies oscillations along a conductor with almost no power consumption at all. A special wide input range driver was designed to convert the differential signals on the coplanar transmission lines into a square clock pulse for standard clock sinks. The design uses CMOS 90 nm BSim3v model cards for all simulations, with the transmission lines implemented on Metal8.

The determination of metal wire dimensions and inter-layer dielectric thicknesses has become increasingly important in recent times, as wire delays have begun to dominate transistor delays. In this paper, we propose metrics to guide the determination of these dimensions, along with results which describe the efficacy of these metrics. The first metric, which we refer to as cross-bar bandwidth(CBB), compares different wiring configurations in terms ofthe resulting bandwidth they can support in a square of unitsize. The second metric, called power-adjusted cross-bar bandwidth (PCBB), measures the bandwidth of a square, while accounting for the power consumed by the interconnect in the square. The application of these metrics suggests that the traditional approach (of fabricating interconnect of the finest pitch possible) may be sub-optimal with respect to either metric that we present. We have conducted our experiments for layers METAL1 through METAL4, although the approach is general and can be applied to the problem of determining interconnect dimensions for any layer. Without considering driver resistance, our approach yields up to 16% improvement in CBB and 19% improvement in PCBB. When drivers are modeled, the improvements are even greater.

Matrix multiplication is a fundamental building block for many applications including image processing, coding, and digital signal processing. This paper presents a delay and resource efficient methodology for implementing integer and floating point matrix multiplication using FPGAs. We present a scalable architecture that provides a significant reduction in total computation time and resource utilization over previous solutions. The improvements of our method are attributed to a new method to compute partial products in parallel, utilizing the new features of modern FPGAs. The implementation of our algorithm for various matrix dimensions using Xilinx FPGAs is also described. When compared with the best reported previous method, our approach achieves an improvement in the parallelization of 60% for 64-bit floating point computations.

This paper presents a design flow that optimizes a standard cell based circuit for performance by implementing critical paths in a Programmable Logic Array (PLA). Given a standard-cell based circuit as input, our approach iteratively extracts critical paths from this circuit, which are then implemented using a PLA circuit. PLAs are a good candidate for such an approach, since they exhibit a gradual increase in delay as additional vectors are added. In subsequent iterations, these critical paths are treated as don't cares, allowing the standard cell based design to be simplified after each iteration. The final design consists of a portion which is implemented using a PLA, and another portion which is implemented using standard cells. We demonstrate that on average, our approach can achieve about 22.5% improvement in the SPICE based delay of a design, along with a placed-and-routed area improvement of 11%.

To compensate for the growing effect of process, temperature and voltage variations in digital ICs, several dynamic approaches have been proposed. These approaches require the use of capacitors to offset the effects of variations. Although MOSFET based capacitors are a natural choice, such capacitances vary significantly depending on the applied voltage. In this paper, we propose techniques to make the capacitance of MOSFET based capacitors relatively constant over the applied voltage. We study approaches that are based on gate as well as diffusion capacitors. We study the trade-off (in terms of capacitance variation, requirement of a bias voltage and area efficiency) of all the proposed schemes. Simulation results are presented for two process technologies. We show that by using our techniques the capacitance variation across applied voltage can be reduced from 75% down to 3% for a 70nm process technology.

Compatible Observability Don't Cares (CODCs) are a powerful means to express the flexibility present at a node in a multi-level logic network. Despite their elegance, the applicability of CODCs has been hampered by their computational complexity. The CODC computation for a network involves several image computations, which require the construction of global BDDs of the circuit nodes. The size of BDDs of circuit nodes is unpredictable, and as a result, the CODC computation is not robust. In practice, CODCs cannot be computed for large circuits due to this limitation.In this paper, we present an algorithm to compute approximate CODCs (ACODCs). This algorithm allows us to compute compatible don't cares for significantly larger designs. Our ACODC algorithm is scalable in the sense that the user may trade off time and memory against the accuracy of the ACODCs computed. The ACODC is computed by considering a subnetwork rooted at the node of interest, up to a certain topological depth, and performing its don't care computation. We prove that the ACODC is an approximation of its CODC.We have proved the soundness of the approach, and performed extensive experiments to explore the trade-off between memory utilization, speed and accuracy. We show that even for small topological depths, the ACODC computation gives very good results. Our experiments demonstrate that our algorithm can compute ACODCs for circuits whose CODC computation has not been demonstrated to date. Also, for a set of benchmark circuits whose CODC computation yields an average 28% reduction in literals after optimization, our ACODC computation yields an average 22% literal reduction. Our algorithm has runtimes which are about 25x and memory utilization which is 33x better that of the CODC computation of SIS.

Proposes a new VLSI layout methodology which addresses the main problems faced in deep sub-micron (DSM) integrated circuit design. Our layout "fabric" scheme eliminates the conventional notion of power and ground routing on the integrated circuit die. Instead, power and ground are essentially "pre-routed" all over the die. By a clever arrangement of power/ground and signal pins, we almost completely eliminate the capacitive effects between signal wires. Additionally. We get a power and ground distribution network with a very low resistance at any point on the die. Another advantage of our scheme is that the arrangement of conductors ensures that on-chip inductances are uniformly negligible. Finally, characterization of the circuit delays, capacitances and resistances becomes extremely simple in our scheme, and needs to be done only once for a design. We show how the uniform parasitics of our fabric give rise to a reliable and predictable design. We have implemented our scheme using public domain layout software. Preliminary results show that it holds much promise as the layout methodology of choice in DSM integrated circuit design.