Browsing by Subject "Stochastic computing"
Now showing 1 - 5 of 5
Results Per Page
Sort Options
Item Analysis, design, and logic synthesis of finite-state machine-based Stochastic computing(2013-06) Li, PengMost digital systems operate on a positional representation of data, such as binary encoding. An alternative is to operate on random bit streams where the signal value is encoded by the probability of obtaining a one versus a zero. This representation is much less compact than the binary encoding. However, complex operations can be performed with very simple logic. Furthermore, since the representation is uniform, with all bits weighted equally, it is highly tolerant of soft errors (i.e., bit flips). Complex algorithms, such as artificial neural networks (ANN), low-density parity-check (LPDC) error-correcting coding, and kernel density estimation (KDE)-based image segmentation, can be implemented using stochastic encoding with much lower hardware cost and higher fault-tolerance. For example, the hardware area of the stochastic implementation of the KDE-based image segmentation is only 1.2% of the corresponding deterministic implementation, and it can tolerate more than 30% soft errors. Compared to conventional fault-tolerant techniques, such as triple-module redundance (TMR), the stochastic implementations of the complex algorithms normally consumes equivalent or less energy and have better fault-tolerance. For example, the TMR implementation of the KDE-based implementation can only tolerate up to 10% soft errors, but consumes the same energy as the stochastic implementation. In addition, thanks to the simple construction of the stochastic computing elements, it makes the rounting much easier, which is a big issue for very large scale integrated circuit (VLSI) deterministic implementations of these complex algorithms. Both combinational and sequential constructs have been proposed for operating on stochastic bit streams. Prior work has shown that combinational logic can implement multiplication and scaled addition effectively while finite-state machines (FSMs) can implement complex functions such as exponentiation and tanh effectively. Although the combinational logic-based stochastic computing elements had been well studied, they are inefficient for complex operations. The FSM-based stochastic computing elements are very efficient for complex operations. However, only three FSM-based stochastic computing elements were proposed by prior work, which limits the applications of stochastic computing. To implement more applications and functions stochastically, this dissertation focuses on the FSM-based stochastic computing. We first analyze the FSM-based stochastic computing elements proposed by prior work, which had largely been validated empirically. In this dissertation, we provide a rigorous mathematical treatment of the FSM-based stochastic computing elements. This gives us intuition about how to construct arbitrary functions stochastically using the FSM. Then, based on the existing stochastic computing elements, we implement five digital image processing algorithms as case studies. So far as we know, this is the first time these digital image processing algorithms are implemented stochastically. For all the five algorithms, the stochastic implementation has much less hardware cost and better fault-tolerance than the corresponding deterministic implementation. Last but not the least, we present a general method to synthesize a given target function stochastically using FSMs. We proposed three FSM topologies and discuss how to use these FSMs to synthesize the given target functions. The trade-offs among these different FSM topologies are introduced. Based on this synthesis method, more applications can be implemented stochastically to achieve lower hardware cost and better fault-tolerance.Item The Design of Spintronic-based Circuitry for Memory and Logic Units in Computer Systems(2018-10) Ma, CongAs CMOS technology starts to face serious scaling and power consumption issues, emerging beyond-CMOS technologies draw substantial attention in recent years. Spintronic device, one of the most promising CMOS alternatives, with smaller size and low standby power consumption, fits the needs of the trending mobile and IoT devices. Spin-Transfer Torque-MRAM (STT-MRAM) with comparable read latency with SRAM and All-spin logic (ASL) capable of implementing pure spin-based circuit are the potential candidates to replace CMOS memory and logic devices. However, spintronic memory continues to require higher write energy, presenting a challenge to memory hierarchy design when energy consumption is a concern. This motivates the use of STT-MRAM for the first level caches of a multicore processor to reduce energy consumption without significantly degrading the performance. The large STT-MRAM first-level cache implementation saves leakage power. And the use of small level-0 cache regains the performance drop due to the long write latency of STT-MRAM. This combination reduces the energy-delay product by 65% on average compared to CMOS baseline. All-spin logic suffers from random bit flips that significantly impacts the Boolean logic reliability. Stochastic computing, using random bit streams for computations, has shown low hardware cost and high fault-tolerance compared to the conventional binary encoding. It motivates the use of ASL in stochastic computing to take advantage of its simplicity and fault tolerance. Finite-state machine (FSM), a sequential stochastic computing element, can compute complex functions including the exponentiation and hyperbolic tangent functions more efficiently, but it suffers from long calculation latency and autocorrelation issues. A parallel implementation scheme of FSM is proposed to use an estimator and a dispatcher to directly initialize the FSM to the steady state. It shows equivalent or better results than the serial implementation with some hardware overhead. A re-randomizer that uses an up/down counter is also proposed to solve the autocorrelation issue.Item Distributed Edge Computing Infrastructure with Low Hardware Cost, Performance Evaluation and Reliability(2018-08) Li, BingzheEdge computing is one method of pushing the applications, data and computation components away from the centralized system. Each edge computing component has its own computation ability and storage capacity. And they also can communicate with the center server through the cloud and Internet to send the pre-computed data to the center. With increasing the interests of Internet of Things (IoT), more and more edge computing nodes will be attached to the cloud and will build a distributed edge computing infrastructure. In the infrastructure, the center server with storage systems is capable of managing the data and storing the captured data into its storage systems. Moreover, tens or hundreds of edge computing nodes are attached to the infrastructure cloud. Each edge computing node has the computation ability to pre-compute some data captured by the back-end sensors and sends the processed data to the center server via the infrastructure cloud. In this thesis, three aspects of the distributed edge computing infrastructure are investigated, the low hardware cost design for edge computing node, performance evaluation for the central server and the reliability of the central server. First, for each edge computing component, the hardware cost is an extremely important factor due to the limited power supply and computation ability. Stochastic computing is a promising technology to achieve the low power and area designs. Taking neural networks as the applications at edge computing nodes, we proposed different arithmetic operations in stochastic domain for neural networks to achieve the low hardware cost design for those edge computing components. Second, with adding more and more edge computing nodes, the network and storage traffic will be increased tremendously in the central server side. Therefore, it is significant to know how much workloads (number of edge computing nodes) the central server can tolerate for system designers. In our work, we proposed replayer tools which are capable of replaying traces to the target system in order to measure the performance of the target system. By doing so, it will be clear to know the ability of the system whether it can tolerate the workload or not and guide the system designer to add more resource to the cenral server such as more storage devices and changing higher frequency CPUs. Finally, the central server in the infrastructure receives the data sent from each edge computing node and stores them into its storage system. Therefore, it is important to protect the data and to achieve the high performance. In this thesis, we proposed new RAID-6 codes to improve the write and degraded read performance while keeping the reliability of the central server.Item Low complexity MIMO detection algorithms and implementations(2014-12) Huai, LianMIMO techniques use multiple antennas at both the transmitter and receiver sides to achieve diversity gain, multiplexing gain, or both. One of the key challenges in exploiting the potential of MIMO systems is to design high-throughput, low-complexity detection algorithms while achieving near-optimal performance. In this thesis, we design and optimize algorithms for MIMO detection and investigate the associated performance and FPGA implementation aspects.First, we study and optimize a detection algorithm developed by Shabany and Gulak for a K-Best based high throughput and low energy hard output MIMO detection and expand it to the complex domain. The new method uses simple lookup tables, and it is fully scalable for a wide range of K-values and constellation sizes. This technique reduces the computational complexity, without sacrificing performance and the complexity scales only sub-linearly with the constellation size. Second, we apply the bidirectional technique to trellis search and propose a high performance soft output bidirectional path preserving trellis search (PPTS) detector for MIMO systems. The comparative error analysis between single direction and bidirectional PPTS detectors is given. We demonstrate that the bidirectional PPTS detector can minimize the detection error. Next, we design a novel bidirectional processing algorithm for soft-output MIMO systems. It combines features from several types of fixed complexity tree search procedures. The proposed approach achieves a higher performance than previously proposed algorithms and has a comparable computational cost. Moreover, its parallel nature and fixed throughput characteristics make it attractive for very large scale integration (VLSI) implementation.Following that, we present a novel low-complexity hard output MIMO detection algorithm for LTE and WiFi applications. We provide a well-defined tradeoff between computational complexity and performance. The proposed algorithm uses a much smaller number of Euclidean distance (ED) calculations while attaining only a 0.5dB loss compared to maximum likelihood detection (MLD). A 3x3 MIMO system with a 16QAM detector architecture is designed, and the latency and hardware costs are estimated.Finally, we present a stochastic computing implementation of trigonometric and hyperbolic functions which can be used for QR decomposition and other wireless communications and signal processing applications.Item Magnetic Tunnel Junctions For Next Generation Of Conventional And Unconventional Computing Schemes(2022-09) Zink, BrandonMagnetic tunnel junctions (MTJs) have several novel features that make them promising devices for next generation memory and computing technologies. These features include multifunctionality, tunable stochasticity, and capability of being tuned by multiple forces. In this dissertation, I demonstrate how these properties make MTJs promising solutions in conventional memory and logic applications as well as unconventional computing applications such as probabilistic bits with increased information capacity and stochastic computing units. Devices that generate random asynchronous, or telegraphic, switching signals have been proposed as probabilistic bits (p-bits) in new paradigms of probabilistic computing schemes for advanced computation. For the first part of my dissertation, I demonstrate that tunable telegraphic switching signals can be generated from MTJs through the combination of an external magnetic field and a DC bias voltage. Previous studies show that tunable telegraphic signals can be generated on MTJs with low thermal stability using only a single bias current or bias voltage. However, my results show that this ‘dual-biasing’ method has a unique capability called two-degrees of tunability, which gives this method two key advantages over the single biased method. One is that it can overcome the challenges imposed by the effects of device variations in large-scale networks and the second is that the signals generated have two times more information capacity than those generated by single-biased MTJs. In the next part of my dissertation, I explore the interplay between the effects of the voltage-controlled exchange coupling (VCEC) and spin-orbit torque (SOT) switching mechanisms. Previous experimental work from our group has demonstrated that VCEC switching can be achieved in perpendicularly magnetized MTJs (p-MTJs) at switching current densities nearly one order of magnitude lower than those for spin transfer torque (STT) and SOT switching. In this dissertation, I show that by combining the SOT and VCEC effects, the VCEC switching current density can be reduced even further, thus providing a pathway to optimize the performance of future magnetoresistive random access memory (MRAM) technologies based on VCEC switching. In the next chapter, I describe a method that was invented by our research group that performs stochastic computing within the hardware for computational random-access memory (CRAM), which is called SC-CRAM. Stochastic computing has several attractive capabilities such as performing complex arithmetic functions with a small number of logic gates, noise resilience, and error tolerance. However, there are significant costs in circuit area and energy consumption for the hardware required to generate stochastic bit-streams. The method described in my dissertation overcomes these costs by embedding the bit-stream generation and computation steps within the same CRAM cells. Furthermore, SC-CRAM shows significant reductions in circuit area for certain neuromorphic computing tasks when compared to conventional computing methods in CRAM. Finally, I study the prospects of MTJs for future applications involving high radiation environments, such as space exploration. Ionizing radiation levels beyond 10 krad have detrimental effects on modern CMOS technology. However, my results demonstrate that MTJs can be exposed to ionizing radiation levels as high as 1 Mrad without significantly influencing the properties key to their performance in MRAM cells. This resilience to ionizing radiation makes MTJs strong candidates for future ‘rad-hard’ devices.