Accelerating machine learning inference has been an active research area in recent years. In this context, field-programmable gate arrays (FPGAs) have demonstrated compelling performance by providing massive parallelism in deep neural networks (DNNs). Neural networks (NNs) are computationally intensive during inference, as they require massive amounts of multiplication and addition, which makes their implementations costly. Numerous studies have recently addressed this challenge to some extent using a combination of sparsity induction, quantization, and transformation of neurons or sub-networks into lookup tables (LUTs) on FPGAs. Gradient boosted decision trees (GBDTs) are a high-accuracy alternative to DNNs in a wide range of regression and classification tasks, particularly for tabular datasets. The basic building block of GBDTs is a decision tree, which resembles the structure of binary decision diagrams. FPGA design flows are heavily optimized to implement such a structure efficiently. In addition to decision trees, GBDTs perform simple operations during inference, including comparison and addition. We present TreeLUT as an open-source tool for implementing GBDTs using an efficient quantization scheme, hardware architecture, and pipelining strategy. It primarily utilizes LUTs with no BRAMs or DSPs on FPGAs, resulting in high efficiency. We show the effectiveness of TreeLUT using multiple classification datasets, commonly used to evaluate ultra-low area and latency architectures. Using these benchmarks, we compare our implementation results with existing DNN and GBDT methods, such as DWN, PolyLUT-Add, NeuraLUT, LogicNets, FINN, hls4ml, and others. Our results show that TreeLUT significantly improves hardware utilization, latency, and throughput at competitive accuracy compared to previous works. For instance, it achieves an accuracy of around 97% on the MNIST dataset while delivering around 4 to 101 times lower hardware cost in terms of area-delay product than recent LUT-based NNs.

As deep learning models grow in size to achieve state-of-the-art accuracy, there is a pressing need for compact models. To address this challenge, we introduce a novel operation called Personal Self-Attention (PSA). It is specifically designed to learn non-linear 1D functions, enhancing existing spline-based methods while remaining compatible with gradient backpropagation. By integrating these non-linear functions with linear transformations, we can achieve the accuracy of larger models but with significantly smaller hidden dimensions, which is crucial for FPGA implementations. We evaluate PSA by implementing it in a Multi-Layer Perceptron (MLP)-based vision model, ResMLP, and testing it on the CIFAR-10 classification task. MLP is gaining increasing popularity due to its widespread use in large-language models. Our results confirm that PSA achieves equivalent accuracy with a 2 \(\times\) smaller hidden size compared to conventional MLPs. Furthermore, by quantizing our non-linear function into a simple Lookup Table (LUT), we reduce the number of operations required by 45–28%, which offers significant benefits for hardware accelerators. To showcase this, we design an end-to-end unrolled streaming accelerator for ResMLP, demonstrating that our compressed model maintains an 88% accuracy while reducing LUT \(+\) DSP resource requirements by 25%, and doubling throughput to 32 kFPS. Additionally, we implement a fixed-size SIMD accelerator for the same compressed model that achieves a 62.1% improvement in throughput while only consuming 3.5% extra LUTs.

Lookup tables are widely used in hardware to store arrays of constant values. For instance, complex mathematical functions in hardware are typically implemented through table-based methods such as plain tabulation, piecewise linear approximation, and bipartite or multipartite table methods, which primarily rely on lookup tables to evaluate the functions. Storing extensive tables of constant values, however, can lead to excessive hardware costs in resource-constrained edge devices such as FPGAs. In this paper, we propose a method, called CompressedLUT, as a lossless compression scheme to compress arrays of arbitrary data, implemented as lookup tables. Our method exploits decomposition, self-similarities, higher-bit compression, and multilevel compression techniques to maximize table size savings with no accuracy loss. CompressedLUT uses addition and arithmetic right shift beside several small lookup tables to retrieve original data during the decoding phase. Using such cost-effective elements helps our method use low area and deliver high throughput. For evaluation purposes, we compressed a number of different lookup tables, either obtained by direct tabulation of 12-bit elementary functions or generated by other table-based methods for approximating functions at higher resolutions, such as multipartite table method at 24-bit, piecewise polynomial approximation method at 36-bit, and hls4ml library at 18-bit resolutions. We implemented the compressed tables on FPGAs using HLS to show the efficiency of our method in terms of hardware costs compared to previous works. Our method demonstrated 60% table size compression and achieved 2.33 times higher throughput per slice than conventional implementations on average. In comparison, previous TwoTable and LDTC works compressed the lookup tables on average by 33% and 37%, which resulted in 1.63 and 1.29 times higher throughput than the conventional implementations, respectively. CompressedLUT is available as an open source tool.

Unary computing is a relatively new method for implementing arbitrary nonlinear functions that uses unpacked thermometer number encoding, enabling much lower hardware costs. In its original form, unary computing provides no trade-off between accuracy and hardware cost. In this work, we propose a novel self-similarity-based method to optimize the previous hybrid binary-unary work and provide it with the trade-off between accuracy and hardware cost by introducing controlled levels of approximation. Looking for self-similarity between different parts of a function allows us to implement a very small subset of core unique subfunctions and derive the rest of the subfunctions from this core using simple linear transformations. We compare our method to previous works such as FloPoCo-LUT (lookup table), HBU (hybrid binary-unary) and FloPoCo-PPA (piecewise polynomial approximation) on several 8–12-bit nonlinear functions including Log, Exp, Sigmoid, GELU, Sin, and Sqr, which are frequently used in neural networks and image processing applications. The area$\times$delay hardware cost of our method is on average 32%–60% better than previous methods in both exact and approximate implementations. We also extend our method to multivariate nonlinear functions and show on average 78%–92% improvement over previous work.

Unary computing is a relatively new method for implementing non-linear functions using few hardware resources compared to binary computing. In its original form, unary computing provides no trade-off between accuracy and hardware cost. In this work, we propose a novel self-similarity-based method to optimize the previous hybrid binary-unary method and provide it with the trade-off between accuracy and hardware cost by introducing controlled levels of approximation. Given a target maximum error, our method breaks a function into sub-functions and tries to find the minimum set of unique sub-functions that can derive all the other ones through trivial bit-wise transformations. We compare our method to previous works such as HBU (hybrid binary-unary) and FloPoCo-PPA (piece-wise polynomial approximation) on a number of non-linear functions including Log, Exp, Sigmoid, GELU, Sin, and Sqr, which are used in neural networks and image processing applications. Without any loss of accuracy, our method can improve the area-delay-product hardware cost of HBU on average by 7% at 8-bit, 20% at 10-bit, and 35% at 12-bit resolutions. Given the approximation of the least significant bit, our method reduces the hardware cost of HBU on average by 21% at 8-bit, 49% at 10-bit, and 60% at 12-bit resolutions, and using the same error budget as given to FloPoCo-PPA, it reduces the hardware cost of FloPoCo-PPA on average by 79% at 8-bit, 58% at 10-bit, and 9% at 12-bit resolutions. We finally show the benefits of our method by implementing a 10-bit homomorphic filter, which is used in image processing applications. Our method can implement the filter with no quality loss at lower hardware cost than what the previous approximate and exact methods can achieve.

We propose a novel method for approximate hardware implementation of univariate math functions with significantly fewer hardware resources compared to previous approaches. Examples of such functions include exp(x) and the activation function GELU(x), both used in transformer networks, gamma(x), which is used in image processing, and other functions such as tanh(x), cosh(x), sq(x), and sqrt(x). The method builds on previous works on hybrid binary-unary computing. The novelty in our approach is that we break a function into a number of sub-functions such that implementing each sub-function becomes cheap, and converting the output of the sub-functions to binary becomes almost trivial. Our method also uses self-similarity in functions to further reduce the cost. We compare our method to the conventional binary, previous stochastic computing, and hybrid binary-unary methods on several functions at 8-, 12-, and 16-bit resolutions. While preserving high accuracy, our method outperforms previous works in terms of hardware cost, e.g., tolerating less than 0.01 mean absolute error, our method reduces the (area x latency) cost on average by 5, 7, and 2 orders of magnitude, compared to the conventional binary, stochastic computing, and hybrid binary-unary methods, respectively. Ultimately, we demonstrate the potential benefits of our method for natural language processing and image processing applications. We deploy our method to implement major blocks in an encoding layer of BERT language model, and also the Roberts Cross edge detection algorithm. Both include non-linear functions.

Constant coefficient multipliers are widely used in digital signal processing and machine learning architectures. Researchers have proposed HBU-CCM (hybrid binary-unary constant coefficient multiplier), which is an approximate method that outperforms conventional binary and FloPoCo-KCM (table-based real multiplier) methods in terms of hardware cost at the expense of accuracy due to aliasing issues. SimBU (self-similarity-based hybrid binary-unary) is another method that was recently proposed to implement general nonlinear functions using self-similarities leading to few hardware resources. In this work, we use a simplified version of the SimBU algorithm to address the aliasing issues of HBU-CCM and improve accuracy. We also implement a convolution kernel for a Gaussian blurring filter to evaluate our method and compare it to previous works. Our method outperforms conventional binary and FloPoCo-KCM methods in terms of hardware cost with desired accuracy and with no aliasing error as opposed to HBU-CCM.

Multipliers are used in virtually all Digital Signal Processing (DSP) applications such as image and video processing. Multiplier efficiency has a direct impact on the overall performance of such applications, especially when real-time processing is needed, as in 4K video processing, or where hardware resources are limited, as in mobile and IoT devices. We propose a novel, low-cost, low energy, and high-speed approximate constant coefficient multiplier (CCM) using a hybrid binary-unary encoding method. The proposed method implements a CCM using simple routing networks with no logic gates in the unary domain, which results in more efficient multipliers compared to Xilinx LogiCORE IP CCMs and table-based KCM CCMs (Flopoco) on average. We evaluate the proposed multipliers on 2-D discrete cosine transform algorithm as a common DSP module. Post-routing FPGA results show that the proposed multipliers can improve the {area, area × delay, power consumption, and energy-delay product} of a 2-D discrete cosine transform on average by {30%, 33%, 30%, 31%}. Moreover, the throughput of the proposed 2-D discrete cosine transform is on average 5% more than that of the binary architecture implemented using table-based KCM CCMs. We will show that our method has fewer routability issues compared to binary implementations when implementing a DCT core.

Multipliers are used in virtually all Digital Signal Processing (DSP) applications, such as image and video processing. Multiplier efficiency has a direct impact on the overall performance of such applications, especially when real-time processing is needed, as in 4K video processing, or where hardware resources are limited, as in mobile and IoT devices. We propose a novel, low-cost, low energy and high-speed approximate constant coefficient multiplier (CCM) using a hybrid binary-unary encoding method. The proposed method implements a CCM using simple routing networks with no logic gates in the unary domain, which results in more efficient multipliers compared to Xilinx LogiCORE IP CCMs and table-based KCM CCMs on average. We evaluate the proposed multipliers on 2-D discrete cosine transform and fast Fourier transform algorithms as two common DSP modules. Post-routing FPGA results show that the proposed multipliers can improve the {area × delay cost, and energy consumption per sample} of 8-bit fixed-point 2-D discrete cosine transform on average by {33%, 36%}. The improvement for 128-point 16-bit fixed-point fast Fourier transform on these metrics is {45%, 54%}. Moreover, the throughput of the proposed 2-D discrete cosine transform and 128-point fast Fourier transform architectures are on average 1.04× and 1.76× of the throughput of the binary architectures implemented using Xilinx LogiCORE IP CCMs, respectively.

Multipliers are the basic building blocks of modern DSP systems and contribute significantly to their overall performance. In many DSP systems, using truncated multipliers instead of full precision multipliers can keep the accuracy at a desirable level while significantly reducing FPGA resources, delay, and power consumption. Truncated multipliers are widely used to accelerate DSP applications such as filtering, fast Fourier, and discrete cosine transforms. In this paper we propose a novel low-cost, low energy, and highspeed truncated multiplier using a hybrid binary-unary encoding method. We take advantage of the unary computing method to exploit two error correction mechanisms in order to reduce error without adding to the hardware cost. The proposed multipliers outperform Xilinx LogiCORE IP in terms of hardware cost, and outperform state-of-the-art FPGA-specific approximate multipliers in terms of accuracy and hardware costs. The proposed approximate multipliers result in area reductions between 12% to 48% for 7- to 15-bit multipliers on average. We assess the performance of the proposed multipliers on an FIR filter, 2-D discrete cosine transform, and fast Fourier transform as three common DSP algorithms. The evaluation results show that these applications can deliver desirable performance using the proposed multipliers.

Convolutional layers account for 90% of the total computational power of Convolutional Neural Networks (CNNs). Field programmable gate arrays (FPGAs) have shown great potential for accelerating inference tasks in CNNs. However, it is harder for FPGA platforms to deliver the best performance due to high computational power and high memory bandwidth requirements of today's CNNs. In this paper, we propose a reconfigurable parallel-pipelined Hybrid Binary-Unary CNN Accelerator (HBUCNNA) to implement low-cost, high-performance convolutional layers of a ResNet-18 architecture. We use the hybrid binary-unary method to implement banks of constant-coefficient multipliers, which are used to implement convolutional kernels. Moreover, we propose hybrid binary-unary batch normalization units to further improve the total hardware costs. These two units reduce {area, area×delay} costs by {50%, 30%} and {44%, 65%} on average compared to their conventional binary counterparts, respectively. The proposed accelerator stores control signals for reconfigurability instead of the numeric value of weights, which in turn reduces the memory footprint on average by 20%. Overall, the proposed HBUCNNA architecture reduces the {area, latency, power, energy, area×delay} costs on average by {25.5%, 40%, 15%, 40%, 47%} and {53%, 61%, 47%, 62%, 67%} compared to the constant-coefficient multiplier-based and variable size multiplier-based binary architectures, respectively. Moreover, the proposed accelerator improves the throughput by about 1.4 × compared to both of the mentioned architectures.

Near-sensor convolution engines have many applications in Internet-of-Things. Pulsed unary processing has been recently proposed for high-performance and energy-efficient processing of data using simple digital logic. In this work, we propose a low-cost, high-performance, and energy-efficient near-sensor convolution engine based on pulsed unary processing. The proposed engine removes the necessity of using costly analog-to-digital converters. Synthesis results show that the proposed pulse-based design significantly improves the hardware cost and energy consumption compared to the conventional fixed-point binary and also to the stochastic computing-based designs.

Stream-based computing such as stochastic computing has been used in recent years to create designs with significantly smaller area by harnessing unary encoding of data. However, the area saving comes at an exponential price in latency, making the area x delay cost unattractive. In this article, we present a novel method which uses a hybrid binary / unary representation to perform computations. We first divide the input range into a few sub-regions, perform unary computations on each sub-region individually, and finally pack the outputs of all sub-regions back to compact binary. Moreover, we propose a synthesis methodology and a regression model to predict an optimal or close-to-optimal design in the design space. To the best of our knowledge, we are the first to show a scalable method based on parallel bit-stream data representation that can beat conventional binary in terms of a real cost, i.e., area x delay and energy consumption in almost all functions that we tried at resolutions of 8-, 10-, and 12-bits. Our method outperforms the binary, stochastic, and fully unary methods on a number of functions, especially low-cost binary CORDIC-based functions, and on a common edge detection algorithm on FPGA and in ASIC implementation. In terms of area x delay cost, our {on FPGA, in ASIC} cost is on average only {4:72%, 24:36%} and {20:16%, 60:12%} of the parallel binary pipeline implementation at 8and 10-bit resolution, respectively. These numbers are 2-3 orders of magnitude better than the results of traditional stochastic methods. Our method is not competitive with the parallel CORDIC-based pipeline binary method for high-resolution (12-bit), highly oscillating functions such as sin (15x). However, for complex functions like gamma function, the proposed method can beat any other methods in terms of area x delay, throughput, latency, and energy per sample costs. To implement the Roberts cross edge detection algorithm, the proposed method takes 5.7 and 39.45 percent of the area x delay cost of FPGA and ASIC implementation of the binary method, respectively. In terms of energy efficiency for FPGA implementation, our method uses only 8.4, 12.7, and 27.7 percent of the energy per sample usage of serial binary implementations at 8-, 10-, and 12-bit resolutions, respectively. These numbers change to 23.9, 38.54, and 99.3 percent compared to parallel binary implementations.

The binary number representation has dominated digital logic for decades due to its compact storage requirements. An alternative representation is the unary number system: We use N bits, from which the first M are 1 and the rest are 0 to represent the value M/N . One-hot representation is a variation of the unary number system where it has one 1 in the N bits, where the 1’s position represents its value. We present a novel method that first converts binary numbers to unary using thermometer (one-hot) encoders and then uses a “scaling network” followed by voting gates that we call “alternator logic,” followed by a decoder to convert the numbers back to the binary format. For monotonically increasing functions, the scaling network is all we need, which essentially uses only the routing resources and flip-flops on a typical FPGA architecture. Our method is clearly superior to the conventional binary implementation: Our area×delay cost is on average only 0.4%, 4%, and 39% of the binary method for 8-, 10-, and 12-bit resolutions, respectively, in thermometer encoding scheme, and 0.5%, 15%, and 147% in the one-hot encoding scheme. In terms of power efficiency, our one-hot method is between about 69× and 114× better compared to conventional binary.

Stochastic computing (SC) in recent years has been defined as a digital computation approach that operates on streams of random bits that represent probability values. SC can perform complex tasks with much smaller hardware footprints compared with conventional binary methods, but previous methods on SC circuits operated on serial bit streams, which leads to high-latency implementations. This article presents a significant improvement over previous work; it provides a deterministic parallel bit shuffling network that can use a simple deterministic thermometer encoding of data, resulting in zero random fluctuation and high accuracy, yet keeping the output bit-stream length constant. We use core “stochastic” logic circuits that do not employ constant coefficients, making them significantly smaller than traditional stochastic logic that use a significant amount of resources to generate such coefficients. Our experiments show that compared with previous SC methods, our method has up to 3x smaller mean absolute error, and better area x delay and power efficiency. Compared with conventional binary methods, our method is better in terms of area x delay at 8-bit resolution. It shows better power efficiency (40x, 18x, and 8x Gops/W at 8-, 10-, and 12-bit resolutions) compared with conventional binary.

Near-sensor convolution engines have many applications in Internet-of-Things. Pulsed unary processing has been recently proposed for high-performance and energy-efficient processing of data using simple digital logic. In this work, we propose a low-cost, high-performance, and energy-efficient near-sensor convolution engine based on pulsed unary processing.

Stochastic computing has been used in recent years to create designs with significantly smaller area by harnessing unary encoding of data. However, the low area advantage comes at an exponential price in latency, making the area x delay cost unattractive. In this paper, we present a novel method which uses a hybrid binary / unary representation to perform computations. We first divide the input range into a few sub-regions, perform unary computations on each sub-region individually, and finally pack the outputs of all sub-regions back to compact binary. Moreover, we propose a synthesis methodology and a regression model to predict an optimal or sub-optimal design in the design space. The proposed method is especially well-suited to FPGAs due to the abundant availability of routing and flip-flop resources. To the best of our knowledge, we are the first to show a scalable method based on the principles of stochastic computing that can beat conventional binary in terms of a real cost, i.e., area x delay. Our method outperforms the binary and fully unary methods on a number of functions and on a common edge detection algorithm. In terms of area x delay cost, our cost is on average only 2.51% and 10.2% of the binary for 8- and 10-bit resolutions, respectively. These numbers are 2--3 orders of magnitude better than the results of traditional stochastic methods. Our method is not competitive with the binary method for high-resolution oscillating functions such as sin(15x).

Stochastic computing (SC) has been used for low-cost and low power implementation of neural networks. Inherent inaccuracy and long latency of processing random bit-streams have made prior SC-based implementations inefficient compared to conventional fixed-point designs. Random or pseudo-random bitstreams often need to be processed for a very long time to produce acceptable results. This long latency leads to a significantly higher energy consumption than binary design counterparts. Low-discrepancy sequences have been recently used for fast-converging deterministic computation with stochastic constructs. In this work, we propose a low-cost, low-latency, and energy-efficient implementation of convolutional neural networks based on low-discrepancy deterministic bit-streams. Experimental results show a significant reduction in the energy consumption compared to previous random bitstream-based implementations and to the optimized fixed-point design with no quality degradation.

Most modern neural networks use the basic Multiply-Accumulate (MAC) Operation in some form or another, and as networks get larger, the computational needs for these larger networks grow rapidly. Typically neural networks implemented on FPGAs use variable multipliers so that any weight can be used in the MAC, but this also forces the accelerator designer to store the weights of the model in off-chip memory (DRAM). Moreover, because of high computational power and high memory bandwidth requirements of today's CNNs, it is harder for FPGA platforms to deliver the best performance. In this paper, we propose a fully parallel-pipeline Hybrid Binary-Unary Neural Network (HBUNN) architecture to implement a low-cost and high-performance ResNet-18 convolutional neural network. We use a hybrid binary-unary method to implement constant-coefficient multipliers and batch normalization units. These two units reduce hardware cost by 30.7% and 47.97% on average compared to the conventional binary equivalent, respectively. Moreover, we propose a novel training scheme using our hardware cost-aware regularizers that not only improves the area cost of the proposed architecture and the conventional binary architecture by 59.3% and 76.7% respectively, but also maintains the same accuracy. Finally, we have implemented three trained networks using different regularizers. The proposed HBUNN architectures reduce the area cost by 30%, and the area × delay cost by 69% on average compared to the conventional binary architectures. The error rate of the proposed work is 12.93%, while its throughput is 278 Kfps.

Stochastic Computing (SC) in recent years has been defined as a digital computation approach that operates on streams of random bits that represent probability values. In a bit-stream representing probability x, each bit has probability x of being 1. Using this simple assumption, SC can perform complex tasks with much smaller hardware footprints compared to conventional binary methods: e.g., a simple AND gate can perform multiplication between two uncorrelated bit-streams. Previous methods on SC circuits either relied on (1) randomness in the input bit streams, or (2) more recently, performing full convolution of deterministic streams to achieve exact computation results. The problem with the first method is that it introduces high random fluctuations and hence high variability in the results. The second method results in exponential increase in the length of the bit stream as circuit depth increases. Both of these methods suffer from very long latencies and neither is readily adaptable for parallel implementations. Our work presents a significant improvement over previous work: it provides a deterministic parallel bit shuffling network that can use a simple deterministic thermometer encoding of data, resulting in zero random fluctuation and high accuracy, yet keeping the output bit stream length constant. We use core “stochastic” logic circuits that do not employ constant coefficients, making them significantly smaller than traditional stochastic logic that potentially use a significant amount of resources to generate such constant coefficients. We show results on feed-forward and feedback circuits and show that our method on average has an area × delay value that is 10.6x smaller than of conventional binary and 7.9x smaller than previous stochastic work at 10-bit binary resolutions.

The binary number representation has dominated digital logic for decades due to its compact storage requirements. However, since the number system is positional, it needs to "unpack»» bits, perform computations, and repack the bits back to binary (\emphe.g., partial products in multiplication).An alternative representation is the unary number system: we use N bits, out of which the first M are 1 and the rest are 0 to represent the value $M/N$. We present a novel method which first converts binary numbers to unary using thermometer encoders, then uses a "scaling network»» followed by voting gates that we call "alternator logic»», followed by an adder tree to convert the numbers back to the binary format. For monotonically increasing functions, the scaling network is all we need, which essentially uses only the routing resources and flip-flops on the FPGA architecture. Our method is especially well-suited to FPGAs due to the abundant availability of routing and FF resources, and for the ability of FPGAs to realize high fanout gates for highly oscillating functions. We compare our method to stochastic computing and to conventional binary implementations on a number of functions, as well as on two common image processing applications. Our method is clearly superior to the conventional binary implementation: our area×delay cost is on average only 3%, 8% and 32% of the binary method for 8-, 10-, and 12-bit resolutions respectively. Compared to stochastic computing, our cost is 6%, 5%, and 8% for those resolutions. The area cost includes conversions from and to the binary format. Our method out performs the conventional binary method on an edge detection algorithm. However, it is not competitive with the binary method on the median filtering application due to the high cost of generating and saving unary representations of the input pixels.

Sorting is a common task in a wide range of applications from signal and image processing to switching systems. For applications that require high performance, sorting is often performed in hardware. Hardware cost and power consumption are the dominant concerns. The usual approach is to wire up a network of compare-and-swap units in a configuration called a Batcher (or Bitonic) network. This paper proposes a novel area-and power-efficient approach to sorting networks based on "unary processing." Data is encoded as serial bit-streams, with values represented by the fraction of 1's in a stream of 0's and 1's. (This is an evolution of prior work on stochastic logic. Unlike stochastic logic, the unary approach is deterministic and completely accurate.) Synthesis results of complete sorting networks show up to 87% area and power saving compared to the conventional binary implementations. However, the latency increases. To mitigate the increased latency, the paper uses a novel time-encoding of data. The approach is validated with implementation of an important application of sorting: median filtering. The result is a low-cost, energy-efficient implementation of median filtering with only a slight accuracy loss.

Computations based on stochastic bit streams have several advantages compared to deterministic binary radix computations, including low power consumption, low hardware cost, high fault tolerance, and skew tolerance. To take advantage of this computing technique, previous work proposed a combinational logic-based reconfigurable architecture to perform complex arithmetic operations on stochastic streams of bits. The long execution time and the cost of converting between binary and stochastic representations, however, make the stochastic architectures less energy efficient than the deterministic binary implementations. This article introduces a methodology for synthesizing a given target function stochastically using finite-state machines (FSMs), and enhances and extends the reconfigurable architecture using sequential logic. Compared to the previous approach, the proposed reconfigurable architecture can save hardware area and energy consumption by up to 30% and 40%, respectively, while achieving a higher processing speed. Both stochastic reconfigurable architectures are much more tolerant of soft errors (bit flips) than the deterministic binary radix implementations, and their fault tolerance scales gracefully to very large numbers of errors.

In the paradigm of stochastic computing, arithmetic functions are computed on randomized bit streams. The method naturally and effectively tolerates very high clock skew. Exploiting this advantage, this paper introduces polysynchronous clocking, a design strategy in which clock domains are split at a very fine level. Each domain is synchronized by an inexpensive local clock. Alternatively, the skew requirements for a global clock distribution network can be relaxed. This allows for a higher working frequency and so lower latency. The benefits of both approaches are quantified. Polysynchronous clocking results in significant latency, area, and energy savings for wide variety of applications.

Stochastic computing (SC) is a promising technique for applications that require low area overhead and fault tolerance, but can tolerate relatively high latency. In the SC paradigm, logical computation is performed on randomized bit streams. In prior work, streams were generated with linear feedback shift registers; these contributed heavily to the hardware cost and consumed a significant amount of power. This paper introduces a new approach for encoding signal values: computation is performed on analog periodic pulse signals. Exploiting pulse width modulation, time-encoded signals corresponding to specific values are generated by adjusting the frequency and duty cycles of pulse width modulated (PWM) signals. With this approach, the latency, area, and energy consumption are all greatly reduced. Experimental results on image processing applications show up to 99% performance speedup, 98% saving in energy dissipation, and 40% area reduction compared to prior stochastic approaches. Circuits synthesized with the proposed approach can work as fast and energy-efficiently as a conventional binary design while retaining the fault-tolerance and low-cost advantages of conventional stochastic designs.

Stochastic computing (SC) is a digital computation approach that operates on random bit streams to perform complex tasks with much smaller hardware footprints compared with conventional binary radix approaches. SC works based on the assumption that input bit streams are independent random sequences of 1s and 0s. Previous SC efforts have avoided implementing functions that have feedback, because doing so has the potential for creating highly correlated inputs. We propose a number of solutions to overcome the challenges of implementing feedback in stochastic logic. We use a family of dynamical system functions that are similar to the well-known logistic map x → μx(1- x) as case studies. We show that complex behaviors, such as period doubling and chaos, do indeed occur in digital logic with only a few gates operating on a few 0s and 1s. Our energy consumption is between 21% and 31% of the conventional binary approach. In order to verify our design methodology, we have measured the mean switching rate between the basins of attraction of two coexisting fixed points and the peak width of the steady-state distribution of the output using a logistic-map-like function as an example. Theoretical results match well with our numerical experiments.

Clock distribution networks (CDNs) are costly in high-performance ASICs. This paper proposes a new approach: splitting clock domains at a very fine level, down to the level of a handful of gates. Each domain is synchronized with an inexpensive clock signal, generated locally. This is possible by adopting the paradigm of stochastic computation, where signal values are encoded as random bit streams. The design method is illustrated with the synthesis of circuits for applications in signal and image processing.

Conventional Simulated Annealing (SA) based placement methods for FPGAs generate high quality results in terms of wirelength and critical path delay, but at a high runtime cost. In case of modern multi-million gate FPGAs, SA-based methods for placement take a large portion of runtime in the FPGA CAD flow. In this paper, we propose a fast and efficient timing driven open-source analytical placement engine targeted at global placement for FPGAs followed by low temperature SA for detailed placement. Our global placement engine uses quadratic programming to minimize wirelength and employs dynamic net weights based on timing criticality between the nets to minimize the critical path delay iteratively. Experimental results show, on average, a 30% runtime improvement for our proposed global placer compared to VPR placer while having approximately the same critical path delay at an expense of 3% larger overall wirelength and channel width after routing with 20 largest MCNC benchmark circuits. The runtime improvement is seen despite the fact that our global placement engine is currently implemented in MATLAB. We expect our runtime to improve notably once we port the code to C. On combining the detailed placement runtime, our proposed approach performs faster for almost all the large circuits having more than 250 blocks. The results show that this placer performs faster global placement across all benchmarks, hence it is easily scalable with modern complex FPGA designs.

We present the design of stochastic computing systems based on sequential logic to implement arbitrary polynomial functions. Stochastic computing is an emerging alternative computing paradigm that performs arithmetic operations on real-valued data represented as random bitstreams using digital logic gates. Stochastic computing systems are capable of realizing complex mathematical operations using a small number of hardware resources by expressing the computation in terms of probabilities. Moreover, the stochastic representation of data using random bitstreams is extremely robust against bit errors. We present a systematic approach to implement arbitrary polynomial functions in stochastic computing using sequential logic, and compare our approach against prior conventional and stochastic implementations.

Stochastic Computing (SC) is a digital computation approach that operates on random bit streams to perform complex tasks with much smaller hardware footprint compared to conventional approaches that employ binary radix. For stochastic logic to work, the input random bit streams have to be independent, which is a challenge when implementing system with feedback: outputs that are generated based on input bit streams would be correlated to those streams and cannot be readily combined as inputs to stochastic logic for another iteration of the function. We propose re-randomization techniques for stochastic computing and use the Logistic Map x → r x(1-x) as a case study for dynamical systems in general. We show that complex behaviors such as period-doubling and chaos do indeed occur in digital logic with only a few gates operating on a few 0's and 1's. We employ a number of techniques such as random number generator sharing and using table-lookup pre-computations to significantly reduce the total energy of the computation. Compared to the conventional binary approach, we achieve between 8% and 25% energy consumption.

We consider the design of IIR filters operating on oversampled sigma-delta modulated bit streams using stochastic arithmetic. Conventional digital filters process multi-bit data at the Nyquist rate using multi-bit multipliers and adders. High resolution ADCs based on the sigma-delta modulation generate random bits at an oversampled rate as intermediate data. We propose to filter the sigma-delta modulated bit streams directly and present first and second order low pass IIR filters based on the stochastic integrator. Experimental results show a significant reduction in hardware area by using stochastic filters.

Stochastic computing refers to a mode of computation in which numbers are treated as probabilities implemented as 0/1 bit streams, which essentially is a unary encoding scheme. Previous work has shown significant reduction in area and increase in fault tolerance for low to medium resolution values (6-10 bits). However, this comes at very high latency cost. We propose a novel hybrid approach combining traditional binary with unary stochastic encoding, called binary stochastic. Similar to the binary representation, it is a positional number system, but instead of only 0/1 digits, the digits would be fractions. We show how simple logic such as adders and multipliers can be implemented, and then show more complex function implementations such as the gamma correction function and functions such as tanh, absolute and exponentiation using both combinational and sequential binary stochastic logic. Our experiments show significant reduction in latency compared to unary stochastic, while using significantly smaller area compared to binary implementations on FPGAs.

Most digital systems operate on a positional representation of data, such as binary radix. 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 binary radix. 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). 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 linear finite-state machines (FSMs) can implement complex functions such as exponentiation and tanh effectively. Prior work on stochastic computation has largely been validated empirically.This paper provides a rigorous mathematical treatment of stochastic implementation of complex functions such as exponentiation and tanh implemented using linear FSMs. It presents two new functions, an absolute value function and exponentiation based on an absolute value, motivated by specific applications. Experimental results show that the linear FSM-based constructs for these functions have smaller area-delay products than the corresponding deterministic constructs. They also are much more tolerant of soft errors.

Maintaining the reliability of integrated circuits as transistor sizes continue to shrink to nanoscale dimensions is a significant looming challenge for the industry. Computation on stochastic bit streams, which could replace conventional deterministic computation based on a binary radix, allows similar computation to be performed more reliably and often with less hardware area. Prior work discussed a variety of specific stochastic computational elements (SCEs) for applications such as artificial neural networks and control systems. Recently, very promising new SCEs have been developed based on finite-state machines (FSMs). In this paper, we introduce new SCEs based on FSMs for the task of digital image processing. We present five digital image processing algorithms as case studies of practical applications of the technique. We compare the error tolerance, hardware area, and latency of stochastic implementations to those of conventional deterministic implementations using binary radix encoding. We also provide a rigorous analysis of a particular function, namely the stochastic linear gain function, which had only been validated experimentally in prior work.

Stochastic computing is an alternative approach to conventional real arithmetic. A stochastic computing module is a digital system that operates on random bit streams representing real numbers. The success of stochastic computing relies on the efficient generation of random bit streams encoding real values in the unit interval. We present the design of random bit stream generators based on finite state machines (FSMs) that emulate Reversible Markov chains. We develop a general synthesis method to designs FSMs for generating arbitrary probabilities with finite resolution. We show that our method uses fewer input random sources for the constant random bit streams needed in a computation compared to the previous work. We further show that the output random bit stream quality and convergence times of our FSMs are reasonable.

Stochastic computing is a novel approach to real arithmetic, offering better error tolerance and lower hardware costs over the conventional implementations. Stochastic modules are digital systems that process random bit streams representing real values in the unit interval. Stochastic modules based on finite state machines (FSMs) have been shown to realize complicated arithmetic functions much more efficiently than combinational stochastic modules. However, a general approach to synthesize FSMs for realizing arbitrary functions has been elusive. We describe a systematic procedure to design FSMs that implement arbitrary real-valued functions in the unit interval using the Taylor series approximation.

The Stochastic Computational Element (SCE) uses streams of random bits (stochastic bits streams) to perform computation with conventional digital logic gates. It can guarantee reliable computation using unreliable devices. In stochastic computing, the linear Finite State Machine (FSM) can be used to implement some sophisticated functions, such as the exponentiation and tanh functions, more efficiently than combinational logic. However, a general approach about how to synthesize a linear FSM-based SCE for a target function has not been available. In this paper, we will introduce three properties of the linear FSM used in stochastic computing and demonstrate a general approach to synthesize a linear FSM-based SCE for a target function. Experimental results show that our approach produces circuits that are much more tolerant of soft errors than deterministic implementations, while the area-delay product of the circuits are less than that of deterministic implementations.

The paradigm of logical computation on stochastic bit streams has several key advantages compared to deterministic computation based on binary radix, including error-tolerance and low hardware area cost. Prior research has shown that sequential logic operating on stochastic bit streams can compute non-polynomial functions, such as the tanh function, with less energy than conventional implementations. However, the functions that can be computed in this way are quite limited. For example, high order polynomials and non-polynomial functions cannot be computed using prior approaches. This paper proposes a new finite-state machine (FSM) topology for complex arithmetic computation on stochastic bit streams. It describes a general methodology for synthesizing such FSMs. Experimental results show that these FSM-based implementations are more tolerant of soft errors and less costly in terms of the area-time product that conventional implementations.

Numerical integration is a widely used approach for computing an approximate result of a definite integral. Conventional digital implementations of numerical integration using binary radix encoding are costly in terms of hardware and have long computational delay. This work proposes a novel method for performing numerical integration based on the paradigm of logical computation on stochastic bit streams. In this paradigm, ordinary digital circuits are employed but they operate on stochastic bit streams instead of deterministic values; the signal value is encoded by the probability of obtaining a one versus a zero in the streams. With this type of computation, complex arithmetic operations can be implemented with very simple circuitry. However, typically, such stochastic implementations have long computational delay, since long bit streams are required to encode precise values. This paper proposes a stochastic design for numerical integration characterized by both small area and short delay -- so, in contrast to previous applications, a win on both metrics. The design is based on mathematical analysis that demonstrates that the summation of a large number of terms in the numerical integration could lead to a significant delay reduction. An architecture is proposed for this task. Experiments confirm that the stochastic implementation has smaller area and shorter delay than conventional implementations.

FPGA placement and routing are still challenging problems. Given the increased diversity of logic and routing resources on FPGA chips, it seems appropriate to tackle the placement problem as a mapping between the nodes and edges in a circuit graph to compatible resources in the architecture graph. We explore utilizing graph isomorphism algorithms to perform FPGA placement. We use a hierarchical approach in which the circuit and architecture graphs are simultaneously clustered to reduce the size of the search space, and then a novel reductive graph product method is used to solve the isomorphism problem. The graph product algorithm is called reductive as it eliminates a linear number of candidates at every step of the search process, reducing the number of candidate nodes by approximately 1/3. Compared to the annealing-based placement tool VPR 5.0, we achieve approximately 40% improvement in placement runtime, while improving the critical path delay by about 7% and wire length by 5%, while demanding 1.3% more channels on average.

Mounting concerns over variability, defects, and noise motivate a new approach for digital circuitry: stochastic logic, that is to say, logic that operates on probabilistic signals and so can cope with errors and uncertainty. Techniques for probabilistic analysis of circuits and systems are well established. We advocate a strategy for synthesis. In prior work, we described a methodology for synthesizing stochastic logic, that is to say logic that operates on probabilistic bit streams. In this paper, we apply the concept of stochastic logic to a reconfigurable architecture that implements processing operations on a datapath. We analyze cost as well as the sources of error: approximation, quantization, and random fluctuations. We study the effectiveness of the architecture on a collection of benchmarks for image processing. The stochastic architecture requires less area than conventional hardware implementations. Moreover, it is much more tolerant of soft errors (bit flips) than these deterministic implementations. This fault tolerance scales gracefully to very large numbers of errors.

Circuit rewiring can be used to explore a larger solution space by modifying circuit structure to suit a given optimization problem. Among several rewiring techniques that have been proposed, SPFD-based rewiring has been shown to be more effective in terms of solution space coverage. However, its adoption in practice has been limited due to its long runtime. We propose a novel SAT-based algorithm that is much faster than the traditional BDD-based methods. Unlike BDD-based methods that completely specify all pairs of SPFD using BDDs, our algorithm uses a few SAT instances to perform rewiring for a given wire without explicitly enumerating all SPFDs. Experimental results show that our algorithm's runtime is only 13% of that of a conventional one when each wire has at most 25 candidate wires and the runtime scales well with the number of candidate wires considered. Our approach evaluates each rewiring instance independently in the order of milliseconds, rendering deployment of an SPFD-based rewiring inside the optimization loop of synthesis tools a possibility.

This paper proposes two set-of-pairs-of-functions-to-be-distinguished (SPFD)-based rewiring algorithms to be used in a multi-tier rewiring framework, which employs multiple rewiring techniques. The first algorithm has two unique features: 1) a satisfiability problem (SAT) instance was devised so that an unsuccessful rewiring can be identified very quickly, and 2) unlike binary decision diagram-based methods that require all pairs of SPFD, our algorithm uses a few SAT instances to perform rewiring for a given wire without explicitly enumerating all SPFDs. Experimental results show that the runtime of our algorithm is about three times faster than that of a conventional one under a simulated setting of such a framework and it scales well with the number of candidate wires considered. The efficacy of the framework can be further improved by the second proposed algorithm. The algorithm relies on a theory presented herein to allow adding a new wire outside of the restricted set of dominator nodes, a feature common in automatic-test-pattern-generation-based rewiring, but absent in existing SPFD-based ones. Although this algorithm may suffer from long runtimes in the same way conventional SPFD-based techniques do, experiments show that the number of wires which can be rewired increases 13% on average and the number of alternative wires also increases.

Future computing systems will feature many cores that run fast, but might show more faults compared to existing CMOS technologies. New software methodologies must be adopted to utilize communication bandwidth and the computational power of few slow, reliable cores that could be employed in such systems to verify the results of the fast, faulty cores. Employing the traditional Triple Module Redundancy (TMR) at core instruction level would not be as effective due to its blind replication of computations. We propose two software development methods that utilize what we call Smart TMR (STMR) and fingerprinting to statistically monitor the results of computations and selectively replicate computations that exhibit faults. Experimental results show significant speedup and reliability improvement over traditional TMR approaches.

Mounting concerns over variability, defects and noise motivate a new approach for integrated circuits: the design of stochastic logic, that is to say, digital circuitry that operates on probabilistic signals, and so can cope with errors and uncertainty. Techniques for probabilistic analysis are well established. We advocate a strategy for synthesis. In this paper, we present a reconfigurable architecture that implements the computation of arbitrary continuous functions with stochastic logic. We analyze the sources of error: approximation, quantization, and random fluctuations. We demonstrate the effectiveness of our method on a collection of benchmarks for image processing. Synthesis trials show that our stochastic architecture requires less area than conventional hardware implementations. It achieves a large speed up compared to software conventional implementations. Most importantly, it is much more tolerant of soft errors (bit flips) than these deterministic implementations.

As CMOS devices are scaled down into the nanometer regime, concerns about reliability are mounting. Instead of viewing nano-scale characteristics as an impediment, technologies such as PCMOS exploit them as a source of randomness. The technology generates random numbers that are used in probabilistic algorithms. With the PCMOS approach, different voltage levels are used to generate different probability values. If many different probability values are required, this approach becomes prohibitively expensive.

With ever-shrinking device geometries, process variations play an increased role in determining the delay of a digital circuit. Under such variations, a gate may lie on the critical path of a manufactured die with a certain probability, called the criticality probability. In this paper, we present a new technique to compute the statistical criticality information in a digital circuit under process variations by linearly traversing the edges in its timing graph and dividing it into ldquozones.rdquo We investigate the sources of error in using tightness probabilities for criticality computation with Clark's statistical maximum formulation. The errors are dealt with using a new clustering-based pruning algorithm which greatly reduces the size of circuit-level cutsets improving both accuracy and runtime over the current state of the art. On large benchmark circuits, our clustering algorithm gives about a 250times speedup compared with a pairwise pruning strategy with similar accuracy in results. Coupled with a localized sampling technique, errors are reduced to around 5% of Monte Carlo simulations with large speedups in runtime.

Field-programmable gate arrays (FPGAs) have gained wide acceptance among low- to medium-volume applications. However, there are gaps between FPGA and custom implementations in terms of area, performance and power consumption. In recent years, specialized blocks - memories and multipliers in particular - have been shown to help reduce this gap. However, their usefulness has not been studied formally on a broad spectrum of designs. As FPGAs are prefabricated, an FPGA family must contain members of various sizes and combinations of specialized blocks to satisfy diverse design resource requirements. We formulate the family selection process as an ldquoFPGA family compositionrdquo problem and propose an efficient algorithm to solve it. The technique was applied to an architecture similar to Xilinx Virtex FPGAs. The results show that smart composition technique can reduce the expected silicon area up to 55%. The benefit of providing multiplier blocks in FPGAs is also shown to reduce total area by 20% using the proposed algorithm.

This paper presents a new approach to active sub-threshold leakage reduction using task migration. The main idea is to replicate a hot module in a design so as to actively migrate its computation at regular intervals, reducing the on-chip temperature and thereby the sub-threshold leakage. We observe that choosing which blocks to migrate and their placement in a floorplan is a chicken-and-egg problem. To solve this, we propose a two step floorplanning methodology, wherein, given a base floorplan, we first choose the modules to replicate and then effectively utilize the deadspaces in it by exploiting the lateral conduction of heat in the floorplan to place a modulepsilas replica. With an optimized floorplan, using task migration we obtain an average savings of 29% in the active sub-threshold leakage at the expense of about 6% additional area.

With constant scaling of process technologies, chip design is becoming increasingly difficult due to process variations. The FPGA community has only recently started focusing on the effects of variations. In this work we present a statistical analysis to compare the effects of variations on designs mapped to FPGAs and ASICs. We also present CAD and architecture techniques to mitigate the impact of variations. First we present a variation-aware router that optimizes statistical criticality. We then propose a modification to the clock network to deliver programmable skews to different flip-flops. Finally, we combine the two techniques and the result is a 9x reduction in yield loss that translates to a 12% improvement in timing yield. When the desired timing yield is set to 99%, our combined statistical routing and skew assignment technique results in a delay improvement of about 10% over a purely deterministic approach.

Chip design in the nanometer regime is becoming increasingly difficult due to process variations. ASIC designers have adopted statistical optimization techniques to mitigate the effects of variations. The FPGA community on the other hand, has only recently started focussing on the effects of variations. This paper presents a comparative study of the impact of variations on designs mapped to FPGAs and ASICs to get a measure of the severity of the problem in both the FPGA and ASIC domains. We also propose a variation aware router that reduces the yield loss by 7.61X, or the circuit delay by 3.95% for the same yield for the MCNC benchmarks.

Traditionally, logic synthesis constrains the solution space of later design steps, such as physical design, because they are applied in sequence. Rewiring is a technique to restructure a circuit while maintaining its functionality. Since design properties and objectives can be considered during post-synthesis rewiring, it can help relieve constraints put forth by decisions made at earlier design steps. The extent of rewiring of a rewiring algorithm has a great impact on the success of the design flow. This paper presents a powerful rewiring technique that in addition to unifying all previously proposed Set-of-Pairs-of-Functions-to-be-Distinguished based rewiring techniques, it can perform rewiring with more than one wire which increases our ability to circumvent poorly-decided early design constraints. With this ability, the rewiring ability of using different numbers of wires is reported for the first time in this paper. Our technique can be used for runtime/quality trade-off in any given rewiring application.

This paper presents a technique to fix timing violations caused by process variations in FPGAs by adjusting the clock skews of flip-flops. This involves making the clock distribution network tunable by adding programmable delay elements to compensate for variations. We propose generic as well as chip-specific skew assignment schemes that are robust to variations. The two proposed schemes result in recovering about 80% and 82% of the failed chips respectively with conservative timing constraints. With more aggressive constraints, the corresponding numbers are 69% and 77% respectively. Our technique causes a 39% increase in the number of chips in the fast bin when speed-binning is performed. The area and power overhead associated with this technique are 3.5% and 5.6% respectively.

We present a new linear time technique to compute criticality information in a timing graph by dividing it into “zones”. Errors in using tightness probabilities for criticality computation are dealt with using a new clustering based pruning algorithm which greatly reduces the size of circuitlevel cutsets. Our clustering algorithm gives a 150X speedup compared to a pairwise pruning strategy in addition to ordering edges in a cutset to reduce errors due to Clark’s MAX formulation. The clustering based pruning strategy coupled with a localized sampling technique reduces errors to within 5% of Monte Carlo simulations with large speedups in runtime.

The nine papers in this special section are expanded versions of papers first presented at the fourteenth International Symposium on Field-Programmable Gate Arrays in 2006. Briefly summarizes the articles included in this section.

According to the ITRS predictions, controlling manufacturing yield is going to be a challenging task in future technologies. The effective yield of future FPGA architectures considering configurable logic blocks, switch boxes, connection boxes and routing segments is estimated in this paper. The results show that some degree of redundancy for logic blocks, routing and switch boxes is necessary. However, no more than one spare logic block per cluster, and at most one spare wire is required to obtain a satisfactory effective yield. The results also indicate that it is beneficial to increase logic cluster size of future FPGA architectures for better yield.

We present timing-driven partitioning and simulated-annealing (SA)-based placement algorithms together with a detailed routing tool for three-dimensional (3-D) field-programmable gate array (FPGA) integration. The circuit is first divided into layers with a limited number of interlayer vias, and then placed on individual layers, while minimizing the delay of critical paths. We use our tool as a platform to explore the potential benefits, in terms of delay and wire length (WL), that 3-D technologies can offer for FPGA fabrics. Experimental results show, on average, a total decrease of 25% in WL and 35% in delay can be achieved over traditional two-dimensional chips, when ten layers are used in 3-D integration

Modern field programmable gate array (FPGA) architectures provide ample routing resources so that designs can be routed successfully. The routing architecture is designed to handle versatile connection configurations. However, providing such a great flexibility comes at a high cost in terms of area, delay, and power. The authors propose a new FPGA routing architecture that utilizes a mixture of hardwired and traditional flexible switches. The result is an about a 30% reduction in leakage power consumption, a 5% smaller area, and 20% shorter delays, which translates to a 25% increase in the clock frequency. Despite the increase in clock speeds, the overall power consumption is reduced.

We present timing-driven partitioning and simulated annealing based placement algorithms together with a detailed routing tool for 3D FPGA integration. The circuit is first divided into layers with limited number of inter-layer vias, and then placed on individual layers, while minimizing the delay of critical paths. We use our tool as a platform to explore the potential benefits in terms of delay and wire-length that 3D technologies can offer for FPGA fabrics. Experimental results show on average a total decrease of 21% in wire-length and 24% in delay, can be achieved over traditional 2D chips, when five layers are used in 3D integration.

This paper introduces a novel 3-Dimensional (3D) vertically integrated adaptive computing system. This 3D-SoftChip is a combination of state-of-the-art processing and interconnection technology. It comprises the vertical integration of two chips (a Configurable Array Processor and an Intelligent Configurable Switch) through indium bump 3D interconnections. The Configurable Array Processor (CAP) is an array of heterogeneous processing elements (PEs) while the Intelligent Configurable Switch (ICS) comprises a switch block, 32-bit dedicated RISC processor for control, on-chip program/data memory, data frame buffer along with a Direct Memory Access (DMA) controller. This paper introduces the 3D-Softchip architecture for real-time communication and multimedia signal processing as a next gene! ration computing system. The paper further describes the up-to-date HW/SW co-design and verification methodology including high level system modeling and architecture exploration of 3D-SoftChip using SystemC in order to determine the optimum hardware specification in the early design stage.

Modern FPGA architectures provide ample routing resources so that designs can be routed successfully. The routing architecture is designed to handle versatile connection configurations. However, providing such great flexibility comes at a high cost in terms of area, delay and power. We propose a new FPGA routing architecture\footnoteThis work was supported in part by a grant from NSF under contract CAREER CCF-0347891 that utilizes a mixture of hardwired and traditional flexible switches. The result is 24% reduction in leakage power consumption, 7% smaller area and 24% shorter delays, which translates to 30% increase in clock frequency. Despite the increase in clock speeds, the overall power consumption is %, including dynamic power, reduced by 8%.

In traditional field programmable gate array (FPGA) placement methods, there is virtually no coupling between placement and routing. Performing simultaneous placement and detailed routing has been shown to generate much better placement qualities, but at the expense of significant runtime penalties (Nag and Rutenbar, 1998). We propose a routing-aware partitioning-based placement algorithm for FPGAs in which a looser but effective coupling between the placement and routing stages is used. The placement engine incorporates a more accurate FPGA delay model and employs effective heuristics that minimize circuit delay. Delay estimations are obtained from routing profiles of selected circuits that are placed and routed using the timing-driven versatile place and route (TVPR) (Betz and Rose, 1997), (Marquardt et al., 2000). As a result, the delay predictions during placement more accurately resemble those observed after detailed routing, which in turn leads to better delay optimization. An efficient terminal alignment heuristic for delay minimization is applied during placement to further optimize the delay of the circuit. These two techniques help maintain harmony between placement and routing-delay optimization stages. Simulation results show that the proposed partitioning-based placement combined with more accurate delay models and the alignment heuristic can achieve postrouting circuit delays comparable to those obtained from TVPR, while achieving a fourfold speedup in total placement runtime. In another experiment, we augmented the original TVPR algorithm with the terminal alignment heuristic, and achieved, on average, a 5% improvement in circuit delay with negligible runtime penalty.

Summary form only given. We present efficient solutions for the noncontiguous linear placement of data paths for reconfigurable fabrics. A strip-based architecture is assumed for the reconfigurable fabric. A preorder tree-expression or a general graph is placed in a strip, which can have active and/or inactive preplaced cores representing blockages and/or cores available for reuse. Two very efficient algorithms are proposed to solve the simpler problem of noncontiguous placement with blockages but without core reuse for tree graphs. The linear ordering obtained with any of the above algorithms is used as input for a third efficient algorithm to solve the problem of noncontiguous placement with both active and inactive cores. A fourth algorithm is proposed to solve the problem of noncontiguous placement with both core and connectivity reuse. Simulations results are reported.

editorial Free Access Share on Editorial: Special issue on dynamically adaptable embedded systems Editors: John Lach University of Virginia, Charlottesville, VA University of Virginia, Charlottesville, VAView Profile , Kia Bazargan University of Minnesota, Minneapolis, MN University of Minnesota, Minneapolis, MNView Profile Authors Info & Claims ACM Transactions on Embedded Computing SystemsVolume 3Issue 2pp 233–236https://doi.org/10.1145/993396.993397Published:01 May 2004Publication History 1citation926DownloadsMetricsTotal Citations1Total Downloads926Last 12 Months9Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Publisher SiteeReaderPDF

In this paper we propose a partitioning-based placement algorithm for FPGAs. The method incorporates simple, but effective heuristics that target delay minimization. The placement engine incorporates delay estimations obtained from previously placed and routed circuits using VPR [6]. As a result, the delay predictions during placement more accurately resemble those observed after detailed routing, which in turn leads to better delay optimization. An efficient terminal alignment heuristic for delay minimization is employed to further optimize the delay of the circuit in the routing phase. Simulation results show that the proposed technique can achieve comparable circuit delays (after routing) to those obtained with VPR while achieving a 7-fold speedup in placement runtime.

We present an algorithm based on dynamic programming to perform the HW/SW partitioning and scheduling of a given task graph for minimum latency subject to resource constraint. The major contribution of this paper is to consider the edge communication delays in the dynamic programming solution of the problem. The algorithm has a polynomial run time complexity on trees. We also introduce a pruning technique to reduce the runtime of the worst-case scenario of directed acyclic graphs (DAGs). The algorithm has been implemented and the results are reported. A very fast quality heuristic is also proposed and implemented to provide good solutions in negligible run time.

Placement of functional units on an FPGA fabric is a challenging problem for runtime reconfigurable computing systems. We introduce the concept of physical contexts to greatly reduce the complexity of the placement and routing problems. We have implemented static and dynamic linear placement methods for expression trees placed in physical contexts. Our placement algorithms are implemented in the JBits environment, creating a layer of a hardware operating system for future reconfigurable computing systems.

A hard disk readback signal generator designed to provide noise-corrupted signals to a channel simulator has been implemented on a Xilinx Virtex textrmTME FPGA device. The generator simulates pulses sensed by read heads in hard drives. All major distortion and noise processes, such as intersymbol interference, transition noise, electronics noise, head and media nonlinearity, intertrack interference, and write timing error, can be generated according to the statistics and parameters defined by the user. Reconfigurable implementation enables an update of the signal characteristics in runtime. The user also has the flexibility to choose from a set of bitstreams to simulate particular combinations of noise and distortion. Such customized restructuring helps reduce the area consumption and hence virtually increase the capacity of the FPGA device. The time to generate the readback signals has been reduced by four orders compared to its software counterpart.

Presents statistical-timing driven partitioning for performance optimization. We show that by using the concept of node criticality we can enhance the Fiduccia-Mattheyses (FM) partitioning algorithm to achieve, on average, around 20% improvements in terms of timing, among partitions with the same cut size. By incorporating mechanisms for timing optimization at the partitioning level, we facilitate wire-planning at high levels of the design process.

In this paper we present multi-objective hMetis partitioning for simultaneous cutsize and circuit delay minimization. We change the partitioning process itself by introducing a new objective function that incorporates a truly path-based delay component for the most critical paths. To avoid semi-critical paths from becoming critical, the traditional slack based delay component is also included in the cost function. The proposed timing driven partitioning algorithm is built on top of the hMetis algorithm, which is very efficient. Simulations results show that 14% average delay improvement can be obtained. Smooth trade-off between cutsize and delay is possible in our algorithm.

Floorplanning is a crucial phase in VLSI physical design. The subsequent placement and routing of the cells/modules are coupled very closely with the quality of the floorplan. A widely used technique for floorplanning is simulated annealing. It gives very good floorplanning results but has major limitation in terms of run time. For circuit sizes exceeding tens of modules simulated annealing is not practical. Floorplanning forms the core of many synthesis applications. Designers need faster prediction of system metrics to quickly evaluate the effects of design changes. Early prediction of metrics is imperative for estimating timing and routability. In this work we propose a constructive technique for predicting floorplan metrics. We show how to modify the existing top-down partitioning-based floorplanning to obtain a fast and accurate floorplan prediction. The prediction gets better as the number of modules and flexibility in the shapes increase. We also explore applicability of the traditional sizing theorem when combining two modules based on their sizes and interconnecting wirelength. Experimental results show that our prediction algorithm can predict the area/length cost function normally within 5-10% of the results obtained by simulated annealing and is, on average, 1000 times faster.

Improvements in FPGA technology have resulted in the introduction of reconfigurable computing machines, where the hardware adapts itself to the running application to gain speedup. We present a top-down compilation method, under development, for such systems. We compile a C program into hierarchical VHDL source files, and annotate them with the placement information of the hardware modules to be configured on the FPGA. Static scheduling combined with a fast, two-stage placement core reduces the compilation time of large programs to minutes.

In many applications such as high-level synthesis (HLS) and logic synthesis and possibly engineering change order (ECO) we would like to get fast and accurate estimations of different performance measures of the chip, namely area, delay and power consumption. These measures cannot be estimated with high accuracy unless a fairly detailed layout of the chip, including the floorplan and routing is available, which in turn are very costly processes in terms of running time. As we have entered the deep sub-micron era, we have to deal with designs which contain million gates and up. Not only we should consider the area occupied by the modules, but we also have to consider the wiring congestion. In this paper we propose a cost function that is, in addition to other parameters, a function of the wiring area. We also propose a method, to avoid running the floorplanning process after every change in the design, by considering the possible changes in advance and generating a floorplan which is tolerant to these modifications, i.e., the changes in the netlist does not dramatically change the performance measures of the chip. Experiments are done in the high-level synthesis domain, but the method can be applied to logic synthesis and ECO as well. We gain speedups of 184% on the average over the traditional estimation methods used in HLS.

We propose fresher looks into already existing hierarchical partitioning based floorplan design methods and their relevance in providing faster alternatives to conventional approaches. We modify the existing partitioning based floor-planner to handle congestion and timing. We also explore the applicability of traditional sizing theorem for combining two modules based on their sizes and interconnecting wirelength. The results show that our floorplanning approach can produce floorplans hundred times faster and at the same time achieving better quality (on average 20% better wirelength, better congestion and better timing optimization) than that of pure simulated annealing based floorplanner.

Floorplanning is an early phase in chip planning. It provides information on approximate area, delay, power, and other performance measures. Careful floorplanning is, thus, of extreme importance. In many applications, while a good floorplan is needed, the information about all modules is not available, or even worse, part of the provided information is inaccurate. Examples of such applications are designing a huge system where the floorplan is needed early in the design process, but not all the modules have been designed. Another example is the field of reconfigurable computing where it is not known what modules will be needed on the reconfigurable chip as the program is being executed. Floorplanning with uncertainty is the problem of obtaining a good floorplan when the information about module dimensions is not complete. In this paper, the floorplanning problem with uncertainty is formulated. Correlation between input characteristics and output characteristics is studied. Also, it is established that traditional floorplanners are incapable of efficiently handling uncertainty. An effective method for dealing with uncertain data is proposed. Experiments show that, for example, with up to 30% input uncertainty an area estimate with less than 7% error can be obtained.

Floorplanning is an early phase in chip planning. It provides information on approximate area, delay, power, and other performance measures. Careful floorplanning is thus of extreme importance. In many applications while a good floorplan is needed, not all modules' information are available, or even w orse, part of the pro vided information is inaccurate. Floorplanning with uncertainty is the problem of obtaining a good floorplan under uncertainty. In this paper, the floorplanning problem with uncertainty is form ulated. It is established that traditional floorplanners are incapable of handling uncertainty. An effective method for dealing with uncertain data is proposed. Experiments sho w that, for example, with up to 30% input uncertainty an area estimate with less than 7% error can be obtained.