Unary Computing

Unary computing is a type of computing paradigm based on serial bits in streams, rather than parallel bits in conventional binary computing. The unary computing kernels are much simpler than conventional binary counterparts, but spend more cycles for a single operation.

In general, a single unary computing kernel may not outperform the binary counterpart in terms of energy efficiency. However, at the system level, there are two advantages in unary computing over binary computing with respect to the system input.

1. If the system input is analog from sensors, unary computing eliminates the process of converting the analog signals to binary format and storing it, reducing the energy consumption [1, 2].
2. If the system input is already binary, due to the higher computing density resulting from simple logic, unary computing can achieve even higher energy efficiency than binary computing when the computational intensity reaches a certain threshold [3].

UnarySim

This UnarySim is a PyTorch-based cycle-accurate simulator for large scale unary computing, compatible to both CPU and GPU with high efficiency.

The paper related to this simulator, "uGEMM: Unary Computing Architecture for GEMM Applications", is accepted to International Symposium on Computer Architecture (ISCA) 2020, and further awarded IEEE Micro Top Pick from 2020 Computer Architecture Conferences.

The components included in UnarySim belong to three categories, including

1. Stream Manipulation
2. Computing Kernel
3. Performance Metric

Among those, components in Stream Manipulation and Computing Kernel can physically exist in real hardware, while those in Performance Metric are virtually for performance analysis.

Prerequisite

1. PyTorch (Version >= 1.10)
2. Python (Version >= 3.6)
3. pylfsr
4. numpy
5. torchinfo
6. matplotlib

Environment configuration before simulation: export PYTHONPATH=<UnarySim-Parent-Dir-Absolute-Path>/

Data Representation

UnarySim has five categories of data, with each having default data type as 'torch.float' in PyTorch.

1. Source Data: The input source data in unary computing need to be ranging from 0 to 1 in unipolar format (Uni), or from -1 to 1 in bipolar format (Bi). The input source data (source) is scaled to a certain range (as in unipolar/bipolar format) from the raw data (raw) with respect to its maximum. An example scaling is source = raw / max(raw).

2. Random Number: The random numbers (rand) are to be compared with the source data in order to generate the bitstreams. To notice, source data is in unipolar/bipolar format, while random numbers are integers. To compare them, source data requires to scale up by the bitwidth of random numbers. At each cycle, if round(source * 2^bitwidth) > rand, a bit of logic 1 in the stream will be generated; otherwise, a bit of logic 0 will be generated.

3. Stream: At each cycle, the bitstreams physically flow through cascaded logic kernels, and they count for most of the memory space during simulation. The bitstream can leverage either rate coding (RC) or temporal coding (TC).

4. Buffer: Inside each logic kernel, there may exist buffers, like counters or shift registers, to compute future data by monitoring the past bitstreams.

5. Metric Variable: Those are variables to compute specially designed performance metrics.

Directory Hierarchy

This directory contains multiple subdirectories, including 'stream', 'kernel', 'metric', 'test', 'app', 'hw', covering three components mentioned above.

'stream' subdirectory

This directory contains the components for Stream Manipulation, which manipulate the bitstreams for high performance and accuracy.

Name	Date	Encoding	Polarity	Reference	Status
Bi2Uni	Mar 31, 2020	RC	Bi	[11]
BSGen	Seq 07, 2019	Both	Both	[4]
BSGenMulti	Nov 11, 2019	Both	Both	[4]
RawScale	Dec 07, 2019	Both	Both	NA
RNG	Seq 07, 2019	Both	Both	[5]
RNGMulti	Nov 11, 2019	Both	Both	[5]
SourceGen	Seq 07, 2019	Both	Both	[4]
SkewedSync	Seq 07, 2019	Both	Both	[6]
Uni2Bi	Mar 31, 2020	RC	Uni	[11]

'kernel' subdirectory

This directory contains the components for Computing Kernel, which take bitstreams as inputs and perform actual unary computation. The supported kernels are listed as follows. The components currently supported or to be implemented are listed in the table below.

1. Fully Streaming Unary (FSU) components that both consume and produce unary bitstreams.

Name	Date	Encoding	Polarity	Reference	Status
FSUAbs	Mar 25, 2020	RC	Bi	[11]
FSUAdd	Oct 10, 2019	Both	Both	[7]
FSUConv2d	Jun 02, 2021	Both	Both	NA
FSUDiv	Apr 01, 2020	RC	Both	[6]
FSUHardsigmoid	Jun 06, 2021	RC	Both	NA
FSUHardtanh	Jun 06, 2021	RC	Both	NA
FSULinear	Seq 27, 2019	Both	Both	[7]
FSUMGUCell	Jun 06, 2021	RC	Both	NA
FSUMul	Nov 05, 2019	RC	Both	[7]
FSUReLU	Nov 23, 2019	Both	Both	[7]
FSUSign	Mar 31, 2020	RC	Bi	[11]
FSUSqrt	Apr 02, 2020	RC	Both	[6]

2. Hybrid Unary Binary (HUB) components that both consume and produce binary data but compute on bitstreams.

Name	Date	Encoding	Polarity	Reference	Status
HUBConv2d	Jun 02, 2021	Both	Both	[12]
HUBLinear	Jun 02, 2021	Both	Both	[12]

3. Useful sub-components.

Name	Date	Encoding	Polarity	Reference	Status
CORDIV_kernel	Mar 08, 2020	RC	Uni	[6]
GainesAdd	Mar 02, 2020	Both	Both	[4]
GainesDiv	Mar 08, 2020	RC	Both	[4]
GainesLinear	Nov 25, 2019	RC	Both	[4]
GainesMul	Dec 06, 2019	RC	Both	[4]
GainesSqrt	Mar 24, 2020	RC	Both	[4]
JKFF	Apr 01, 2020	NA	NA	NA
ShiftReg	Dec 06, 2019	NA	NA	NA

'metric' subdirectory

This directory contains the components for Performance Metric, which take bit streams as input and calculate certain performance metrics. The components currently supported or to be implemented are listed in the table below.

Name	Date	Encoding	Polarity	Reference	Status
Correlation	Seq 07, 2019	Both	Both	[8]
NormStability	Dec 18, 2019	Both	Both	[10]
NSBuilder	Mar 31, 2020	Both	Both	[10]
ProgError	Seq 07, 2019	Both	Both	[9]
Stability	Dec 27, 2019	Both	Both	[7]

'test' subdirectory

This directory contains simple testing examples for above components.

'app' subdirectory

This directory contains several applications implemented using this UnarySim.

'hw' subdirectory

This directory includes the hardware implementation of components in Stream Manipulation and Computing Kernel, and is still in progress.

Reference

[1] V. T. Lee, A. Alaghi, J. P. Hayes, V. Sathe, and L. Ceze, "Energy-efficient hybrid stochastic-binary neural networks for near-sensor computing", in DATE 2017. [2] S. K. Khatamifard, M. H. Najafi, A. Ghoreyshi, U. R. Karpuzcu and D. J. Lilja, "On Memory System Design for Stochastic Computing", in IEEE Computer Architecture Letters 2018. [3] V. T. Lee, A. Alaghi, R. Pamula, V. S. Sathe, L. Ceze and M. Oskin, "Architecture Considerations for Stochastic Computing Accelerators", in TCAD 2018.
[4] B.R. Gaines, "Stochastic computing systems," in Advances in Information Systems Science 1969.
[5] S. Liu and J. Han, "Energy efficient stochastic computing with Sobol sequences," in DATE 2017.
[6] D. Wu and J. S. Miguel, "In-Stream Stochastic Division and Square Root via Correlation," in DAC 2019.
[7] D. Wu, J. Li, R. Yin, H. Hsiao, Y. Kim and J. San Miguel, "uGEMM: Unary Computing Architecture for GEMM Applications," in ISCA 2020.
[8] A. Alaghi and J. P. Hayes, "Exploiting correlation in stochastic circuit design," in ICCD 2013.
[9] A. Alaghi and J. P. Hayes, "Fast and accurate computation using stochastic circuits," in DATE 2014.
[10] D. Wu, R. Yin and J. San Miguel, "Normalized Stability: A Cross-Level Design Metric for Early Termination in Stochastic Computing", in ASP-DAC 2021.
[11] D. Wu, R. Yin and J. San Miguel, "In-Stream Correlation-Based Division and Bit-Inserting Square Root in Stochastic Computing", in IEEE Design & Test 2021.
[12] D. Wu and J. San Miguel, "uSystolic: Byte-Crawling Unary Systolic Array," in HPCA 2022.

Citing

If you find UnarySim is useful for your research, please use the following bibtex to cite us,

@inproceedings{diwu2020uGEMM,
  title = {{uGEMM: Unary Computing Architecture for GEMM Applications}},
  author = {Di Wu and Jingjie Li and Ruokai Yin and Hsuan Hsiao and Younghyun Kim and Joshua San Miguel},
  booktitle = {International Symposium on Computer Architecture (ISCA)},
  year = {2020},
}

Contribution

Active contributor:

1. Di Wu
2. Ruokai Yin
3. Jingjie Li
4. Zhewen Pan

Please contact me (di.wu@ece.wisc.edu) if you are interested in contributing to this project!