research-article

Chlorophyll: synthesis-aided compiler for low-power spatial architectures

Authors:

Phitchaya Mangpo Phothilimthana,

Rastislav BodikAuthors Info & Claims

ACM SIGPLAN Notices, Volume 49, Issue 6

Pages 396 - 407

https://doi.org/10.1145/2666356.2594339

Published: 09 June 2014 Publication History

Abstract

We developed Chlorophyll, a synthesis-aided programming model and compiler for the GreenArrays GA144, an extremely minimalist low-power spatial architecture that requires partitioning the program into fragments of no more than 256 instructions and 64 words of data. This processor is 100-times more energy efficient than its competitors, but currently can only be programmed using a low-level stack-based language.

The Chlorophyll programming model allows programmers to provide human insight by specifying partial partitioning of data and computation. The Chlorophyll compiler relies on synthesis, sidestepping the need to develop classical optimizations, which may be challenging given the unusual architecture. To scale synthesis to real problems, we decompose the compilation into smaller synthesis subproblems---partitioning, layout, and code generation. We show that the synthesized programs are no more than 65% slower than highly optimized expert-written programs and are faster than programs produced by a heuristic, non-synthesizing version of our compiler.

References

[1]

Rajeev Alur. Syntax-guided synthesis. Tutorial at FMCAD, 2013.

[2]

Arduino. Arduino playground: Avr code. http://playground.arduino.cc/Main/AVR.

[3]

Rimas Avizienis and Per Ljung. Comparing the Energy Efficiency and Performance of the Texas Instrument MSP430 and the GreenArrays GA144 processors. Technical report, 2012.

[4]

Sorav Bansal and Alex Aiken. Automatic generation of peephole superoptimizers. In ASPLOS, 2006.

Digital Library

[5]

Sorav Bansal and Alex Aiken. Binary translation using peephole superoptimizers. In OSDI, 2008.

Digital Library

[6]

Gilles Barthe, Juan Manuel Crespo, Sumit Gulwani, Cesar Kunz, and Mark Marron. From relational verification to simd loop synthesis. In PPoPP, 2013.

Digital Library

[7]

Zeki Bozkus, Alok Choudhary, Tomasz Haupt, Geoffrey Fox, and Sanjay Ranka. Compiling hpf for distributed memory mimd computers. In The Interaction of Compilation Technology and Computer Architecture. 1994.

[8]

Doug Burger, Stephen W. Keckler, Kathryn S. McKinley, Mike Dahlin, Lizy K. John, Calvin Lin, Charles R. Moore, James Burrill, Robert G. McDonald, William Yoder, and the TRIPS Team. Scaling to the end of silicon with edge architectures. Computer, July 2004.

Digital Library

[9]

William W. Carlson, Jesse M. Draper, and David E. Culler. S-246, 187 introduction to upc and language specification.

[10]

Satish Chandra, Vijay Saraswat, Vivek Sarkar, and Rastislav Bodik. Type inference for locality analysis of distributed data structures. In PPoPP, 2008.

Digital Library

[11]

David T. Connolly. An improved annealing scheme for the QAP. European Journal of Operational Research, 46(1):93--100, 1990.

[12]

Leonardo De Moura and Nikolaj Bjørner. Z3: An efficient smt solver. In TACAS, 2008.

Digital Library

[13]

Gwenaël Delaval, Alain Girault, and Marc Pouzet. A type system for the automatic distribution of higher-order synchronous dataflow programs. In LCTES, 2008.

Digital Library

[14]

Marco Dorigo and Thomas Stützle. Ant Colony Optimization. Bradford Company, Scituate, MA, USA, 2004.

Digital Library

[15]

Christopher W. Fraser, Robert R. Henry, and Todd A. Proebsting. Burg: fast optimal instruction selection and tree parsing. SIGPLAN Not., 27(4):68--76, April 1992.

Digital Library

[16]

Michael I. Gordon, William Thies, Michal Karczmarek, Jasper Lin, Ali S. Meli, Andrew A. Lamb, Chris Leger, Jeremy Wong, Henry Hoffmann, David Maze, and Saman Amarasinghe. A stream compiler for communication-exposed architectures. In ASPLOS, 2002.

Digital Library

[17]

GreenArrays. Product Brief: GreenArrays Architecture, 2010.

[18]

GreenArrays. Product Brief: GreenArrays GA144, 2010.

[19]

GreenArrays. Appplication Note AB001: An Implementation of the MD5 Hash, 2012.

[20]

Sumit Gulwani, Susmit Jha, Ashish Tiwari, and Ramarathnam Venkatesan. Synthesis of loop-free programs. In PLDI, 2011.

Digital Library

[21]

Richard Hughey. Programming systolic arrays. Technical report, Brown University, 1992.

[22]

Kurtis T. Johnson, A. R. Hurson, and Behrooz Shirazi. General-purpose systolic arrays. Computer, 26(11):20--31, November 1993.

Digital Library

[23]

Rajeev Joshi, Greg Nelson, and Keith Randall. Denali: a goal-directed superoptimizer. In PLDI, 2002.

Digital Library

[24]

Monica S. Lam. A Systolic Array Optimizing Compiler. Kluwer Academic Publishers, Norwell, MA, USA, 1989.

Digital Library

[25]

Eugene L. Lawler. The quadratic assignment problem. Manage. Sci., 9:586--599, 1963.

Digital Library

[26]

Walter Lee, Rajeev Barua, Matthew Frank, Devabhaktuni Srikrishna, Jonathan Babb, Vivek Sarkar, and Saman Amarasinghe. Space-time scheduling of instruction-level parallelism on a raw machine. In ASPLOS, 1998.

Digital Library

[27]

Ben Liblit, Alex Aiken, and Katherine Yelick. Type systems for distributed data sharing. In Radhia Cousot, editor, Static Analysis, volume 2694 of Lecture Notes in Computer Science, pages 273--294. Springer Berlin Heidelberg, 2003.

Digital Library

[28]

Per Ljung. Welcome to the dark side of computing. Presented at ParLab Summer Retreat, University of California, Berkeley, 2011.

[29]

Henry Massalin. Superoptimizer: a look at the smallest program. In ASPLOS, 1987.

[30]

John Merlin. Techniques for the automatic parallelisation of 'distributed fortran 90', 1992.

[31]

Jarek Nieplocha, Bruce Palmer, Vinod Tipparaju, Manojkumar Krishnan, Harold Trease, and Edoardo Aprà. Advances, applications and performance of the global arrays shared memory programming toolkit. Int. J. High Perform. Comput. Appl., 20(2):203--231, May 2006.

Digital Library

[32]

Tony Nowatzki, Michael Sartin-Tarm, Lorenzo De Carli, Karthikeyan Sankaralingam, Cristian Estan, and Behnam Robatmili. A general constraint-centric scheduling framework for spatial architectures. In PLDI, 2013.

Digital Library

[33]

Arch D. Robison. Impact of economics on compiler optimization. In Proceedings of the 2001 Joint ACM-ISCOPE Conference on Java Grande, JGI '01, pages 1--10, New York, NY, USA, 2001. ACM.

Digital Library

[34]

V. Sarawat, B. Bloom, I. Peshansky, O. Tardieu, and D. Grove. X10 language specification, October 2012.

[35]

Eric Schkufza, Rahul Sharma, and Alex Aiken. Stochastic superoptimization. In ASPLOS, 2013.

Digital Library

[36]

Hong Shen. Occam implementation of process-to-processor mapping on the hathi-2 transputer system. Microprocessing and Microprogramming, 33(3), 1992.

Digital Library

[37]

Jadranka Skorin-Kapov. Tabu search applied to the quadratic assignment problem. INFORMS Journal on Computing, 2(1):33--45, 1990.

[38]

Aaron Smith, Jon Gibson, Bertrand Maher, Nick Nethercote, Bill Yoder, Doug Burger, Kathryn S. McKinle, and Jim Burrill. Compiling for edge architectures. In CGO, 2006.

Digital Library

[39]

Armando Solar-Lezama, Liviu Tancau, Rastislav Bodik, Sanjit Seshia, and Vijay Saraswat. Combinatorial sketching for finite programs. In ASPLOS, 2006.

Digital Library

[40]

Trefis Team. Can Intel Challenge ARM's Mobile Dominance?, 2012.

[41]

Emina Torlak and Rastislav Bodik. Growing solver-aided languages with Rosette. In Onward!, 2013.

Digital Library

[42]

Xilinx. Vivado design suite. http://www.xilinx.com/products/design-tools/vivado/.

[43]

Kathy Yelick, Luigi Semenzato, Geoff Pike, Carleton Miyamoto, Ben Liblit, Arvind Krishnamurthy, Paul Hilfinger, Susan Graham, David Gay, Phil Colella, and Alex Aiken. Titanium: A high-performance java dialect. In Concurrency: Pract. Exper., 1998.

[44]

Mingxuan Yuan, Zonghua Gu, Xiuqiang He, Xue Liu, and Lei Jiang. Hardware/software partitioning and pipelined scheduling on runtime reconfigurable fpgas. ACM Trans. Des. Autom. Electron. Syst., 15(2), March 2010.

Digital Library

Cited By

Smith GKushigian BCanumalla VCheung ALyubomirsky SPorncharoenwase SJust RBernstein GTatlock ZTsafrir DMusuvathi MGupta RAbu-Ghazaleh N(2024)FPGA Technology Mapping Using Sketch-Guided Program SynthesisProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 210.1145/3620665.3640387(416-432)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3620665.3640387
Mankowitz DMichi AZhernov AGelmi MSelvi MPaduraru CLeurent EIqbal SLespiau JAhern AKöppe TMillikin KGaffney SElster SBroshear JGamble CMilan KTung RHwang MCemgil TBarekatain MLi YMandhane AHubert TSchrittwieser JHassabis DKohli PRiedmiller MVinyals OSilver D(2023)Faster sorting algorithms discovered using deep reinforcement learningNature10.1038/s41586-023-06004-9618:7964(257-263)Online publication date: 7-Jun-2023
https://doi.org/10.1038/s41586-023-06004-9
Akhunov KYildirim K(2022)AdaMICAProceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies10.1145/35503046:3(1-30)Online publication date: 7-Sep-2022
https://dl.acm.org/doi/10.1145/3550304
Show More Cited By

Chlorophyll: synthesis-aided compiler for low-power spatial architectures
1. Software and its engineering
  1. Software notations and tools

Recommendations

Chlorophyll: synthesis-aided compiler for low-power spatial architectures
PLDI '14: Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation

We developed Chlorophyll, a synthesis-aided programming model and compiler for the GreenArrays GA144, an extremely minimalist low-power spatial architecture that requires partitioning the program into fragments of no more than 256 instructions and 64 ...
Validating the MERIS Terrestrial Chlorophyll Index (MTCI) with ground chlorophyll content data at MERIS spatial resolution

The Medium Resolution Imaging Spectrometer (MERIS) Terrestrial Chlorophyll Index (MTCI), a standard level 2 European Space Agency (ESA) product, provides information on the chlorophyll content of vegetation (amount of chlorophyll per unit area of ground)...
Phenology of vegetation in Southern England from Envisat MERIS terrestrial chlorophyll index MTCI data

Given the close association between climate change and vegetation response, there is a pressing requirement to monitor the phenology of vegetation and understand further how its metrics vary over space and time. This article explores the use of the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 49, Issue 6

PLDI '14

June 2014

598 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/2666356

Editor:
Andy Gill
University of Kansas, Lawrence, KS

Issue’s Table of Contents

PLDI '14: Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation
June 2014
619 pages
ISBN:9781450327848
DOI:10.1145/2594291
General Chair:
Michael O'Boyle
University of Edinburgh
,
Program Chair:
Keshav Pingali
University of Texas, Austin

Copyright © 2014 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 the author(s) 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: 09 June 2014

Published in SIGPLAN Volume 49, Issue 6

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

65
Total Citations
View Citations
634
Total Downloads

Downloads (Last 12 months)70
Downloads (Last 6 weeks)9

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Smith GKushigian BCanumalla VCheung ALyubomirsky SPorncharoenwase SJust RBernstein GTatlock ZTsafrir DMusuvathi MGupta RAbu-Ghazaleh N(2024)FPGA Technology Mapping Using Sketch-Guided Program SynthesisProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 210.1145/3620665.3640387(416-432)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3620665.3640387
Mankowitz DMichi AZhernov AGelmi MSelvi MPaduraru CLeurent EIqbal SLespiau JAhern AKöppe TMillikin KGaffney SElster SBroshear JGamble CMilan KTung RHwang MCemgil TBarekatain MLi YMandhane AHubert TSchrittwieser JHassabis DKohli PRiedmiller MVinyals OSilver D(2023)Faster sorting algorithms discovered using deep reinforcement learningNature10.1038/s41586-023-06004-9618:7964(257-263)Online publication date: 7-Jun-2023
https://doi.org/10.1038/s41586-023-06004-9
Akhunov KYildirim K(2022)AdaMICAProceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies10.1145/35503046:3(1-30)Online publication date: 7-Sep-2022
https://dl.acm.org/doi/10.1145/3550304
Gobieski GGhosh SHeule MMowry TNowatzki TBeckmann NLucia BHardavellas NCampanoni SGrot BKarpuzcu U(2022)RipTide: A Programmable, Energy-Minimal Dataflow Compiler and ArchitectureProceedings of the 55th Annual IEEE/ACM International Symposium on Microarchitecture10.1109/MICRO56248.2022.00046(546-564)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1109/MICRO56248.2022.00046
Vega LMcMahan JSampson AGrossman DCeze LFreund SYahav E(2021)Reticle: a virtual machine for programming modern FPGAsProceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3453483.3454075(756-771)Online publication date: 19-Jun-2021
https://dl.acm.org/doi/10.1145/3453483.3454075
Sovetov P(2021)Development of DSL Compilers for Specialized ProcessorsProgramming and Computer Software10.1134/S036176882107008247:7(541-554)Online publication date: 3-Dec-2021
https://doi.org/10.1134/S0361768821070082
Huang QKang MDinh GNorell TKalaiah ADemmel JWawrzynek JShao YMartínez JDuato JJohn L(2021)CoSAProceedings of the 48th Annual International Symposium on Computer Architecture10.1109/ISCA52012.2021.00050(554-566)Online publication date: 14-Jun-2021
https://dl.acm.org/doi/10.1109/ISCA52012.2021.00050
Kamp MPhilippsen M(2021)Approximate Bit Dependency Analysis to Identify Program Synthesis Problems as InfeasibleVerification, Model Checking, and Abstract Interpretation10.1007/978-3-030-67067-2_16(353-375)Online publication date: 17-Jan-2021
https://dl.acm.org/doi/10.1007/978-3-030-67067-2_16
Weng JLiu SDadu VWang ZShah PNowatzki TMartínez JDuato JEeckhout L(2020)DSAGENProceedings of the ACM/IEEE 47th Annual International Symposium on Computer Architecture10.1109/ISCA45697.2020.00032(268-281)Online publication date: 30-May-2020
https://dl.acm.org/doi/10.1109/ISCA45697.2020.00032
Fedyukovich GKaufman SBodík R(2020)Learning inductive invariants by sampling from frequency distributionsFormal Methods in System Design10.1007/s10703-020-00349-x56:1-3(154-177)Online publication date: 16-Nov-2020
https://doi.org/10.1007/s10703-020-00349-x
Show More Cited By

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents