Method and architecture for accelerating deterministic stochastic computing using residue number system
Inventors
Najafi, Mohammadhassan • Givaki, Kamyar • Hojabrossadati, Seyed Reza • Gholamrezayi, M. H. • Khonsari, Ahmad • Gorgin, Saeid • Rahmati, Dara
Assignees
Interested in licensing this patent?
MTEC can help explore whether this patent might be available for licensing for your application.
Publication Number
US-12307352-B2
Publication Date
2025-05-20
Expiration Date
Abstract
Inaccuracy of computations is an important challenge with the Stochastic Computing (SC) paradigm. Recently, deterministic approaches to SC are proposed to produce completely accurate results with SC circuits. Instead of random bit-streams, the computations are performed on structured deterministic bit-streams. However, current deterministic methods take a large number of clock cycles to produce correct result. This long processing time directly translates to very high energy consumption. This invention proposes a design methodology based on the Residue Number Systems (RNS) to mitigate the long processing time of the deterministic methods. Compared to the state-of-the-art deterministic methods of SC, the proposed approach delivers improvements in terms of processing time and energy consumption.
Core Innovation
The disclosed approach performs bit-stream processing in deterministic stochastic computing using Residue Number System format. A selected three-modulus set decomposes each operand into residues with small-bit-width representation, and this decomposition is associated with exponentially shorter deterministic structured bit-stream lengths and reduced processing cycles and energy versus conventional deterministic stochastic computing.
The disclosure further describes a hardware architecture that accelerates deterministic stochastic computing using finite state machine based bit-stream generation and RNS-to-binary handling concentrated in a final pipeline stage. A bit-stream generator is implemented with an FSM-based coding mechanism using per-residue multiplexers, and parallel AND gates are used with counters to convert output bit-streams into binary residues. An FSM-based reverse converter is used for reverse conversion and employs a precomputed look-up table for RNS-to-binary conversion limited to the final stage.
The document reports comparisons showing large area, power, energy, and latency reductions for 8–32-bit multipliers when implemented using the proposed method. It also compares a neural-network processing element implemented with the proposed method against baseline binary, RNS, and deterministic clock-division stochastic computing designs.
Claims Coverage
The provided independent claims cover an architecture and a corresponding method for deterministic bit-stream processing using RNS residues and FSM-based bit-stream generation. The inventive features are centered on an RNS three-residue input representation, FSM-driven bit-stream generator logic with per-residue multiplexers, deterministic generation of bit-streams, bit-stream multiplication using AND gates, conversion of produced bit-streams to binary representation using counters, and, in the architecture, reverse conversion using a look-up table confined to the final pipeline stage. In total, two independent claims are identified from the partial content.
Finite state machine bit-stream processing architecture with RNS three-residue conversion
An architecture for performing bit-stream processing comprising at least one finite state machine, at least one bit-stream generator, a moduli set, at least one input buffer storing at least two numbers comprising three residues, at least one counter, at least one AND gate, a controller, and at least one multiplexer unit, where the stored three residues are in Residue Number System format and the bit-stream generator has coding capable of converting one or more residues into bit-stream representation.
Deterministic bit-stream processing method with separate residue multiplexers and counter-based binary conversion
A method for performing bit-stream processing comprising storing at least two distinct numbers in an input buffer where each distinct number comprises two or more residues, inputting the distinct numbers into at least one finite state machine-based bit-stream generator, generating one or more deterministic bit-streams where each residue conversion uses a separate multiplexer unit, performing multiplication of outputs using an AND gate to produce a bit-stream, converting the produced bit-stream to binary representation using a counter, and calculating any residues.
Overall claim coverage ties deterministic bit-stream processing to an RNS residue representation with FSM-based bit-stream generation. The claims emphasize per-residue multiplexing for residue conversion, multiplication using AND gates to produce bit-streams, and counter-based conversion of produced bit-streams into binary representation, with the architecture further including reverse conversion using a look-up table in a final stage.
Stated Advantages
Exponentially shorter deterministic structured bit-stream lengths versus conventional deterministic stochastic computing.
Reduced processing cycles and energy versus conventional deterministic stochastic computing.
Large area, power, energy, and latency reductions for 8–32-bit multipliers when using the proposed method.
Improved neural-network processing element performance relative to baseline binary, RNS, and deterministic clock-division stochastic computing designs.
Documented Applications
Convolutional neural network processing element / neural network accelerator use case, where a processing element is implemented with the proposed method and compared against baseline designs.
Interested in licensing this patent?