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

research-article

Public Access

From functional programs to pipelined dataflow circuits

Authors:

Richard Townsend,

Stephen A. EdwardsAuthors Info & Claims

CC 2017: Proceedings of the 26th International Conference on Compiler Construction

Pages 76 - 86

https://doi.org/10.1145/3033019.3033027

Published: 05 February 2017 Publication History

Abstract

We present a translation from programs expressed in a functional IR into dataflow networks as an intermediate step within a Haskell-to-Hardware compiler. Our networks exploit pipeline parallelism, particularly across multiple tail-recursive calls, via non-strict function evaluation. To handle the long-latency memory operations common to our target applications, we employ a latency-insensitive methodology that ensures arbitrary delays do not change the functionality of the circuit. We present empirical results comparing our networks against their strict counterparts, showing that non-strictness can mitigate small increases in memory latency and improve overall performance by up to 2×.

References

[1]

Arvind and R. Nikhil. Executing a program on the MIT tagged-token dataflow architecture. IEEE Trans. Comp., 39(3):300–318, Mar. 1990.

Digital Library

[2]

Arvind et al. High-level synthesis: an essential ingredient for designing complex ASICs. In Intl. Conf. Comp. Aided Design (ICCAD), pp. 775–782, San Jose, CA, Nov. 2004.

Digital Library

[3]

C. Baaij et al. Cλ ash: Structural descriptions of synchronous hardware using Haskell. In Euromicro Digital Sys. Design (DSD), pp. 714–721, Lille, France, Sept. 2010.

Digital Library

[4]

C. P. R. Baaij and J. Kuper. Using rewriting to synthesize functional languages to digital circuits. In Proc. Trends in Functional Programming (TFP), LNCS vol. 8322, pp. 17–33, Provo, Utah, 2014. Springer.

Digital Library

[5]

D. F. Bacon et al. Parallel real-time garbage collection of multiple heaps in reconfigurable hardware. In Proc. Intl. Symp. Memory Management (ISMM), pp. 117–127, Edinburgh, UK, 2014.

Digital Library

[6]

P. Bjesse, K. Claessen, M. Sheeran, and S. Singh. Lava: Hardware design in Haskell. In Proc. Intl. Conf. Functional Programming (ICFP), pp. 174–184, Baltimore, Maryland, 1998.

Digital Library

[7]

B. Cao et al. Implementing latency-insensitive dataflow blocks. In Form. Meth. Mod. Codesign (MEMOCODE), Austin, TX, Sep. 2015.

Digital Library

[8]

L. P. Carloni. The role of back-pressure in implementing latencyinsensitive systems. Elect. Notes Theo. CS, 146(2):61–80, 2006.

Digital Library

[9]

J. Carmona et al. Elastic circuits. IEEE Trans. CAD, 28(10):1437– 1455, Oct 2009.

Digital Library

[10]

S. Frankau and A. Mycroft. Stream processing hardware from functional language specifications. In Hawaii Intl. Conf. Sys. Sci., 2003.

Digital Library

[11]

P. Gammie. Synchronous digital circuits as functional programs. ACM Computing Surveys, 46(2), article 21, Nov. 2013.

Digital Library

[12]

D. R. Ghica. Function interface models for hardware compilation. In Proc. of the Intl. Conf. on Formal Methods and Models for Codesign (MEMOCODE), pp. 131–142, Cambridge, UK, July 2011.

Digital Library

[13]

A. Gill et al. Types and associated type families for hardware simulation and synthesis: The internals and externals of Kansas Lava. Higher-Order and Symbolic Computation, pp. 1–20, 2013.

Digital Library

[14]

J. W. Janneck et al. Synthesizing hardware from dataflow programs. Journal of Signal Processing Systems, 63(2):241–249, May 2011.

Digital Library

[15]

G. Kahn. The semantics of a simple language for parallel programming. In Information Processing 74: Proc. of IFIP Congress 74, pp. 471–475, Stockholm, Sweden, Aug. 1974. North-Holland.

[16]

M. Kulkarni et al. Lonestar: A suite of parallel irregular programs. In Proc. of the Intl. Symposium on Performance Analysis of Systems and Software (ISPASS), pp. 65–76, Boston, Massachusetts, Apr. 2009.

[17]

H.-W. Loidl et al. Comparing parallel functional languages. Higher-Order and Symbolic Computation, 16(3):203–251, 2003.

Digital Library

[18]

P. Mantovani et al. High-level synthesis of accelerators in embedded scalable platforms. In Proc. Asia South Pacific Design Automation Conf. (ASP-DAC), pp. 204–211. IEEE, 2016.

[19]

A. Mycroft et al. Hardware synthesis using SAFL and application to processor design. In Correct HW Design Verif. Methods (CHARME), LNCS vol. 2144, pp. 13–39, Livingston, Scot., Sept. 2001.

Digital Library

[20]

R. Nane et al. A survey and evaluation of FPGA high-level synthesis tools. IEEE Trans. CAD, 35(10):1591–1604, Oct 2016.

Digital Library

[21]

S. Peyton Jones and A. Santos. Compilation by transformation in the Glasgow Haskell Compiler. In Functional Programming, Glasgow 1994, pp. 184–204. Springer.

[22]

M. W. Roberts and P. K. Lala. Algorithm to detect reconvergent fanouts in logic circuits. IEE Proc. E—Comp. and Dig. Tech., 134(2):105–111, March 1987.

[23]

X. Saint-Mleux et al. SHard: a Scheme to hardware compiler. In Scheme and Func. Prog. (SFPW), pp. 39–49, Portland, OR, Sep. 2006.

[24]

R. Sharp and A. Mycroft. A higher-level language for hardware synthesis. In Correct Hard. Design and Verif. Methods (CHARME), pp. 228–243. Springer, 2001.

Digital Library

[25]

R. W. Sharp and A. Mycroft. The FLaSH compiler: Efficient circuits from functional specs. tr.2000.3, AT&T Labs Cambridge, 2000.

[26]

M. Sheeran. µFP, an algebraic VLSI design language. In Symp. LISP and Funct. Prog. (LFP), pp. 104–112, Austin, Texas, Aug. 1984.

Digital Library

[27]

G. Venkatesh et al. Conservation cores: Reducing the energy of mature computations. In Arch. Support for Prog. Lang. and Operating Sys. (ASPLOS), pp. 205–218, Pittsburgh, Pennsylvania, Mar. 2010.

Digital Library

[28]

D. R. White and M. Newman. Fast approximation algorithms for finding node-independent paths in networks. Technical Report 01– 07–035, Santa Fe Institute, New Mexico, 2001.

[29]

F. Winterstein et al. High-level synthesis of dynamic data structures: A case study using Vivado HLS. In Proc. of Field-Programmable Technology (FPT), pages 362–365. IEEE, 2013.

[30]

K. Zhai et al. Hardware synthesis from a recursive functional language. In Proc. Conf. Hardware/Software Codesign and System Synthesis (CODES+ISSS), Amsterdam, The Netherlands, Oct. 2015.

Digital Library

Cited By

Liu JGraczyk MGuerrieri AJosipović L(2024)Fast Switching Activity Estimation for HLS-Produced Dataflow Circuits2024 34th International Conference on Field-Programmable Logic and Applications (FPL)10.1109/FPL64840.2024.00025(118-125)Online publication date: 2-Sep-2024
https://doi.org/10.1109/FPL64840.2024.00025
Tu KTang XYu CJosipović LChu ZTu KTang XYu CJosipović LChu Z(2024)High-Level SynthesisFPGA EDA10.1007/978-981-99-7755-0_8(113-134)Online publication date: 1-Feb-2024
https://doi.org/10.1007/978-981-99-7755-0_8
Sylvestre LSérot JChailloux E(2024)Hardware Implementation of OCaml Using a Synchronous Functional LanguagePractical Aspects of Declarative Languages10.1007/978-3-031-52038-9_10(151-168)Online publication date: 15-Jan-2024
https://dl.acm.org/doi/10.1007/978-3-031-52038-9_10
Show More Cited By

Index Terms

From functional programs to pipelined dataflow circuits
1. Hardware
  1. Integrated circuits
    1. Logic circuits
2. Software and its engineering
  1. Software notations and tools
    1. Compilers

Recommendations

Lenient evaluation is neither strict nor lazy

What is a non-strict functional language? Is a non-strict language necessarily lazy? What additional expressiveness brings non-strictness, with or without laziness? This paper tries to shed some light on these questions. First, in order to characterize ...
Lenient evaluation and parallelism

In a companion paper (Tremblay G. Lenient evaluation is neither strict nor lazy. Computer languages 2000; 26:43-66.), we showed that non-strict functional languages were not necessarily lazy. More precisely, non-strict functional languages can be ...
Evaluation of Speculation in Out-of-Order Execution of Synchronous Dataflow Networks

Dataflow process networks are a convenient formalism for implementing robust concurrent systems that has been successfully used for hardware and software systems in the past. However, the strictly stream-based execution limits the performance of dataflow ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

CC 2017: Proceedings of the 26th International Conference on Compiler Construction

February 2017

141 pages

ISBN:9781450352338

DOI:10.1145/3033019

General Chair:
Peng Wu
Huawei, USA
,
Program Chair:
Sebastian Hack
Saarland University, Germany

Copyright © 2017 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: 05 February 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Conference

CC '17

CC '17: Compiler Construction

February 5 - 6, 2017

TX, Austin, USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
485
Total Downloads

Downloads (Last 12 months)91
Downloads (Last 6 weeks)22

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Liu JGraczyk MGuerrieri AJosipović L(2024)Fast Switching Activity Estimation for HLS-Produced Dataflow Circuits2024 34th International Conference on Field-Programmable Logic and Applications (FPL)10.1109/FPL64840.2024.00025(118-125)Online publication date: 2-Sep-2024
https://doi.org/10.1109/FPL64840.2024.00025
Tu KTang XYu CJosipović LChu ZTu KTang XYu CJosipović LChu Z(2024)High-Level SynthesisFPGA EDA10.1007/978-981-99-7755-0_8(113-134)Online publication date: 1-Feb-2024
https://doi.org/10.1007/978-981-99-7755-0_8
Sylvestre LSérot JChailloux E(2024)Hardware Implementation of OCaml Using a Synchronous Functional LanguagePractical Aspects of Declarative Languages10.1007/978-3-031-52038-9_10(151-168)Online publication date: 15-Jan-2024
https://dl.acm.org/doi/10.1007/978-3-031-52038-9_10
Han SJang MKang JAamodt TJerger NSwift M(2023)ShakeFlow: Functional Hardware Description with Latency-Insensitive Interface CombinatorsProceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 210.1145/3575693.3575701(702-717)Online publication date: 27-Jan-2023
https://dl.acm.org/doi/10.1145/3575693.3575701
Jurkans KFox C(2023)Python Subset to Digital Logic Dataflow Compiler for Robots and IoT2023 IEEE 22nd International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom)10.1109/TrustCom60117.2023.00257(1893-1899)Online publication date: 1-Nov-2023
https://doi.org/10.1109/TrustCom60117.2023.00257
Szafarczyk RNabi SVanderbauwhede W(2023)A High-Frequency Load-Store Queue with Speculative Allocations for High-Level Synthesis2023 International Conference on Field Programmable Technology (ICFPT)10.1109/ICFPT59805.2023.00018(115-124)Online publication date: 12-Dec-2023
https://doi.org/10.1109/ICFPT59805.2023.00018
Szafarczyk RNabi SVanderbauwhede W(2023)Compiler Discovered Dynamic Scheduling of Irregular Code in High-Level Synthesis2023 33rd International Conference on Field-Programmable Logic and Applications (FPL)10.1109/FPL60245.2023.00009(1-9)Online publication date: 4-Sep-2023
https://doi.org/10.1109/FPL60245.2023.00009
Sylvestre LChailloux ESérot J(2023)Accelerating OCaml Programs on FPGAInternational Journal of Parallel Programming10.1007/s10766-022-00748-z51:2-3(186-207)Online publication date: 24-Jan-2023
https://doi.org/10.1007/s10766-022-00748-z
Schlaak CJuang TDubach C(2022)Memory-Aware Functional IR for Higher-Level Synthesis of AcceleratorsACM Transactions on Architecture and Code Optimization10.1145/350176819:2(1-26)Online publication date: 31-Jan-2022
https://dl.acm.org/doi/10.1145/3501768
Josipovic LGuerrieri AIenne P(2022)From C/C++ Code to High-Performance Dataflow CircuitsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2021.310557441:7(2142-2155)Online publication date: Jul-2022
https://doi.org/10.1109/TCAD.2021.3105574
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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 Publication

Media

Figures

Other

Tables

View Table of Contents