More Web Proxy on the site http://driver.im/

research-article

Open access

BitSAD v2: Compiler Optimization and Analysis for Bitstream Computing

Authors:

Kyle Daruwalla,

Mikko LipastiAuthors Info & Claims

ACM Transactions on Architecture and Code Optimization (TACO), Volume 16, Issue 4

Article No.: 43, Pages 1 - 25

https://doi.org/10.1145/3364999

Published: 18 November 2019 Publication History

All formats PDF

Abstract

Computer vision and machine learning algorithms operating under a strict power budget require an alternate computing paradigm. While bitstream computing (BC) satisfies these constraints, creating BC systems is difficult. To address the design challenges, we propose compiler extensions to BitSAD, a DSL for BC. Our work enables bit-level software emulation and automated generation of hierarchical hardware, discusses potential optimizations, and proposes compiler phases to implement those optimizations in a hardware-aware manner. Finally, we introduce population coding, a parallelization scheme for stochastic computing that decreases latency without sacrificing accuracy, and provide theoretical and experimental guarantees on its effectiveness.

Supplementary Material

a43-daruwalla-suppl.pdf (daruwalla.zip)

Supplemental movie, appendix, image and software files for, BitSAD v2: Compiler Optimization and Analysis for Bitstream Computing

Download
107.52 KB

References

[1]

2016. IBM Neurosynaptic System Neuron Function Library Reference Manual. Technical Report. IBM Corporation.

[2]

Armin Alaghi and John P. Hayes. 2013. Survey of stochastic computing. ACM Trans. Embed. Comput. Syst. 12, 2s (2013), 1--19.

Digital Library

[3]

A. H. Bentbib and A. Kanber. 2015. Block power method for SVD decomposition. Anal. Sti. Univ. Ovid. Const. Ser. Mat. 23, 2 (2015), 45--58.

[4]

Bradley D. Brown and Howard C. Card. 2001. Stochastic neural computation I: Computational elements. IEEE Transactions on Computers 50, 9 (2001), 891--905.

Digital Library

[5]

Taylor S. Clawson, Silvia Ferrari, Sawyer B. Fuller, and Robert J. Wood. 2016. Spiking neural network (SNN) control of a flapping insect-scale robot. In Proceedings of the IEEE Conference on Decision and Control. 3381--3388.

[6]

Kyle Daruwalla and Heng Zhuo. 2019. BitSAD: A domain-specific language for bitstream computing. In Proceedings of the 1st ISCA Workshop on Unary Computing.

[7]

Kyle Daruwalla, Heng Zhuo, Carly Schulz, and Mikko Lipasti. 2019. BitBench: A benchmark for bitstream computing. In Proceedings of the 20th ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES’19). ACM Press, New York, NY, 177--187.

Digital Library

[8]

Pierre Emile Duhamel, Judson Porter, Benjamin Finio, Geoffrey Barrows, David Brooks, Gu Yeon Wei, and Robert J. Wood. 2011. Hardware in the loop for optical flow sensing in a robotic bee. In Proceedings of the IEEE International Conference on Intelligent Robots and Systems, 1099--1106.

[9]

S. Rasoul Faraji and Kia Bazargan. 2019. Hybrid binary-unary hardware accelerator. In Proceedings of the 24th Asia and South Pacific Design Automation Conference on (ASPDAC’19). ACM Press, New York, NY, 210--215.

Digital Library

[10]

Dario Floreano and Robert J. Wood. 2015. Science, technology and the future of small autonomous drones. Nature 521, 7553 (2015), 460--466.

[11]

B. R. Gaines. 1969. Stochastic computing systems. In Advances in Information Systems Science. Springer US, Boston, MA, 37--172.

[12]

Warren J. Gross and Vincent C. Gaudet. 2019. Stochastic Computing: Techniques and Applications.

[13]

Wassily Hoeffding. 1963. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association 58, 301 (1963), 13--30.

[14]

Devon Jenson and Marc Riedel. 2016. A deterministic approach to stochastic computation. In Proceedings of the 35th International Conference on Computer-Aided Design (ICCAD’16), 1--8.

Digital Library

[15]

Mikko Lipasti and Carly Schulz. 2017. End-to-end stochastic computing. In Proceedings of the 1st Workshop on Pioneering Processor Paradigms.

[16]

Kevin Y. Ma, Pakpong Chiraratttananon, Sawyer B. Fuller, and Robert J. Wood. 2013. Controlled flight of a biologically inspired, insect-scale robot. Science 340, 6132 (May 2013), 603--607.

[17]

Ezio Malis and Manuel Vargas. 2007. Deeper understanding of the homography decomposition for vision-based control. Research Report. RR-6303, INRIA, inria-00174036v3. pp. 90.

[18]

Lifeng Miao and Chaitali Chakrabarti. 2013. A parallel stochastic computing system with improved accuracy. In Proceedings of the IEEE Workshop on Signal Processing Systems (SiPS’13). IEEE, 195--200.

[19]

Soheil Mohajer, Zhiheng Wang, and Kia Bazargan. 2018. Routing magic: Performing computations using routing networks and voting logic on unary encoded data. In Proceedings of the 2018 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays (FPGA’18), 77--86.

Digital Library

[20]

Rohit Shukla, Erik Jorgensen, and Mikko Lipasti. 2017. Evaluating hopfield-network-based linear solvers for hardware constrained neural substrates. In Proceedings of the International Joint Conference on Neural Networks, 3938--3945.

[21]

Rohit Shukla, Soroosh Khoram, Erik Jorgensen, Jing Li, Mikko Lipasti, and Stephen Wright. 2018. Computing Generalized Matrix Inverse on Spiking Neural Substrate. 115 pages.

[22]

Pai Shun Ting and John Patrick Hayes. 2014. Stochastic logic realization of matrix operations. In Proceedings of the 2014 17th Euromicro Conference on Digital System Design (DSD’14), 356--364.

Digital Library

[23]

Pai Shun Ting and John Patrick Hayes. 2016. Isolation-based decorrelation of stochastic circuits. In Proceedings of the 34th IEEE International Conference on Computer Design (ICCD’16). 88--95.

[24]

Zhiheng Wang, Soheil Mohajer, and Kia Bazargan. 2018. Low latency parallel implementation of traditionally-called stochastic circuits using deterministic shuffling networks. In Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC’18), 337--342.

[25]

Di Wu and Joshua San Miguel. 2019. In-stream stochastic division and square root via correlation. In Proceedings of the 56th Annual Design Automation Conference (DAC'19). 1--6.

Digital Library

[26]

Xuan Zhang, Mario Lok, Tao Tong, Sae Kyu Lee, Brandon Reagen, Simon Chaput, Pierre-Emile J. Duhamel, Robert J. Wood, David Brooks, and Gu-Yeon Wei. 2017. A fully integrated battery-powered system-on-chip in 40-nm CMOS for closed-loop control of. IEEE J. Solid-State Circ. 52, 9 (2017), 2374--2387.

Cited By

Li ZJin HZhong KLuo GWang RQian W(2024)SCGen: A Versatile Generator Framework for Agile Design of Stochastic Circuits2024 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE58400.2024.10546649(1-6)Online publication date: 25-Mar-2024
https://doi.org/10.23919/DATE58400.2024.10546649
Khoram SDaruwalla KLipasti M(2023)Energy-Efficient Bayesian Inference Using Bitstream ComputingIEEE Computer Architecture Letters10.1109/LCA.2023.323858422:1(37-40)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1109/LCA.2023.3238584
Ilov APaler A(2023)High-Speed Compilation of Large-Scale Stochastic Circuits2023 IEEE International Conference on Rebooting Computing (ICRC)10.1109/ICRC60800.2023.10386131(1-4)Online publication date: 5-Dec-2023
https://doi.org/10.1109/ICRC60800.2023.10386131
Show More Cited By

Index Terms

BitSAD v2: Compiler Optimization and Analysis for Bitstream Computing
1. Software and its engineering
  1. Software notations and tools
    1. Context specific languages
      1. Domain specific languages
2. Theory of computation
  1. Models of computation
    1. Probabilistic computation
    2. Streaming models

Recommendations

BitBench: a benchmark for bitstream computing
LCTES 2019: Proceedings of the 20th ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems

With the recent increase in ultra-low power applications, researchers are investigating alternative architectures that can operate on streaming input data. These target use cases require complex algorithms that must be evaluated under a real-time ...
McLab: an extensible compiler toolkit for MATLAB and related languages
C3S2E '10: Proceedings of the Third C* Conference on Computer Science and Software Engineering

Matlab is a popular language for scientific computation. Effectively compiling Matlab presents many challenges due to the dynamic nature of the language. We present McLab, an extensible compiler toolkit for the Matlab and related languages. McLab aims to ...
Compiler-Based Code Compression for Hard Real-Time Systems
SCOPES '19: Proceedings of the 22nd International Workshop on Software and Compilers for Embedded Systems

Real-Time Systems often come with additional requirements apart from being functionally correct and adhering to their timing constraints. Another common additional optimization goal is to meet code size requirements. Code compression techniques might be ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Architecture and Code Optimization

ACM Transactions on Architecture and Code Optimization Volume 16, Issue 4

December 2019

572 pages

ISSN:1544-3566

EISSN:1544-3973

DOI:10.1145/3366460

Editor:
Koen De Bosschere
Ghent University, Belgium

Issue’s Table of Contents

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 November 2019

Accepted: 01 September 2019

Revised: 01 August 2019

Received: 01 June 2019

Published in TACO Volume 16, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
875
Total Downloads

Downloads (Last 12 months)146
Downloads (Last 6 weeks)18

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Li ZJin HZhong KLuo GWang RQian W(2024)SCGen: A Versatile Generator Framework for Agile Design of Stochastic Circuits2024 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE58400.2024.10546649(1-6)Online publication date: 25-Mar-2024
https://doi.org/10.23919/DATE58400.2024.10546649
Khoram SDaruwalla KLipasti M(2023)Energy-Efficient Bayesian Inference Using Bitstream ComputingIEEE Computer Architecture Letters10.1109/LCA.2023.323858422:1(37-40)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1109/LCA.2023.3238584
Ilov APaler A(2023)High-Speed Compilation of Large-Scale Stochastic Circuits2023 IEEE International Conference on Rebooting Computing (ICRC)10.1109/ICRC60800.2023.10386131(1-4)Online publication date: 5-Dec-2023
https://doi.org/10.1109/ICRC60800.2023.10386131
Wu DLi JYin RHsiao HKim YMiguel J(2021)uGEMM: Unary Computing for GEMM ApplicationsIEEE Micro10.1109/MM.2021.306536941:3(50-56)Online publication date: 1-May-2021
https://doi.org/10.1109/MM.2021.3065369
Fujieda N(2021)A Python-based evaluation framework for stochastic computing circuits on FPGA SoC2021 Ninth International Symposium on Computing and Networking Workshops (CANDARW)10.1109/CANDARW53999.2021.00021(81-86)Online publication date: Nov-2021
https://doi.org/10.1109/CANDARW53999.2021.00021

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents