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

research-article

Forge: generating a high performance DSL implementation from a declarative specification

Authors:

Arvind K. Sujeeth,

Austin Gibbons,

Kevin J. Brown,

HyoukJoong Lee,

Martin Odersky,

Kunle OlukotunAuthors Info & Claims

GPCE '13: Proceedings of the 12th international conference on Generative programming: concepts & experiences

Pages 145 - 154

https://doi.org/10.1145/2517208.2517220

Published: 27 October 2013 Publication History

Abstract

Domain-specific languages provide a promising path to automatically compile high-level code to parallel, heterogeneous, and distributed hardware. However, in practice high performance DSLs still require considerable software expertise to develop and force users into tool-chains that hinder prototyping and debugging. To address these problems, we present Forge, a new meta DSL for declaratively specifying high performance embedded DSLs. Forge provides DSL authors with high-level abstractions (e.g., data structures, parallel patterns, effects) for specifying their DSL in a way that permits high performance. From this high-level specification, Forge automatically generates both a naïve Scala library implementation of the DSL and a high performance version using the Delite DSL framework. Users of a Forge-generated DSL can prototype their application using the library version, and then switch to the Delite version to run on multicore CPUs, GPUs, and clusters without changing the application code. Forge-generated Delite DSLs perform within 2x of hand-optimized C++ and up to 40x better than Spark, an alternative high-level distributed programming environment. Compared to a manually implemented Delite DSL, Forge provides a factor of 3-6x reduction in lines of code and does not sacrifice any performance. Furthermore, Forge specifications can be generated from existing Scala libraries, are easy to maintain, shield DSL developers from changes in the Delite framework, and enable DSLs to be retargeted to other frameworks transparently.

References

[1]

Apache. Hadoop. http://hadoop.apache.org/.

[2]

E. Axelsson, K. Claessen, M. Sheeran, J. Svenningsson, D. Engdal, and A. Persson. The Design and Implementation of Feldspar: An Embedded Language for Digital Signal Processing. IFL'10, 2011.

Digital Library

[3]

M. Bravenboer, K. T. Kalleberg, R. Vermaas, and E. Visser. Stratego/XT 0.17. A language and toolset for program transformation. Sci. Comput. Program., 72(1-2):52--70, June 2008.

Digital Library

[4]

K. J. Brown, A. K. Sujeeth, H. Lee, T. Rompf, H. Chafi, M. Odersky, and K. Olukotun. A Heterogeneous Parallel Framework for Domain-Specific Languages. PACT, 2011.

Digital Library

[5]

K. J. Brown, A. K. Sujeeth, H. Lee, T. Rompf, C. D. Sa, M. Odersky, and K. Olukotun. Big Data Analytics with Delite. http://ppl.stanford.edu/papers/delitescaladays13.pdf, 2013.

[6]

C. Calcagno, W. Taha, L. Huang, and X. Leroy. Implementing Multistage Languages Using ASTs, Gensym, and Reflection. GPCE, 2003.

Digital Library

[7]

J. Carette, O. Kiselyov, and C. chieh Shan. Finally tagless, partially evaluated: Tagless staged interpreters for simpler typed languages. J. Funct. Program., 19(5):509--543, 2009.

Digital Library

[8]

B. Catanzaro, M. Garland, and K. Keutzer. Copperhead: compiling an embedded data parallel language. PPoPP, 2011.

Digital Library

[9]

H. Chafi, Z. DeVito, A. Moors, T. Rompf, A. K. Sujeeth, P. Hanrahan, M. Odersky, and K. Olukotun. Language Virtualization for Heterogeneous Parallel Computing. Onward!, 2010.

[10]

H. Chafi, A. K. Sujeeth, K. J. Brown, H. Lee, A. R. Atreya, and K. Olukotun. A domain-specific approach to heterogeneous parallelism. PPoPP, 2011.

Digital Library

[11]

C. Chambers, A. Raniwala, F. Perry, S. Adams, R. R. Henry, R. Bradshaw, and N. Weizenbaum. FlumeJava: easy, efficient data-parallel pipelines. PLDI, 2010.

Digital Library

[12]

R. Chandra, L. Dagum, D. Kohr, D. Maydan, J. McDonald, and R. Menon. Parallel programming in OpenMP. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2001.

Digital Library

[13]

A. Danial. CLOC - Count Lines of Code. Open source, 2009.

[14]

Z. DeVito, N. Joubert, F. Palacios, S. Oakley, M. Medina, M. Barrientos, E. Elsen, F. Ham, A. Aiken, K. Duraisamy, E. Darve, J. Alonso, and P. Hanrahan. Liszt: A Domain Specific Language for Building Portable Mesh-based PDE Solvers. SC, 2011.

Digital Library

[15]

S. Erdweg, L. C. Kats, T. Rendel, C. Kästner, K. Ostermann, and E. Visser. SugarJ: library-based language extensibility. OOPSLA, 2011.

Digital Library

[16]

M. Eysholdt and H. Behrens. Xtext: implement your language faster than the quick and dirty way. SPLASH '10, 2010.

Digital Library

[17]

T. E. Foundation. Eclipse Modeling Framework Project (EMF). http://www.eclipse.org/modeling/emf/, 2013.

[18]

Google. Protocol Buffers Data Interchange Format. http://code.google.com/p/protobuf, 2011.

[19]

B. Hindman, A. Konwinski, M. Zaharia, A. Ghodsi, A. D. Joseph, R. Katz, S. Shenker, and I. Stoica. Mesos: A platform for fine-grained resource sharing in the data center. NSDI, 2011.

Digital Library

[20]

C. Hofer, K. Ostermann, T. Rendel, and A. Moors. Polymorphic embedding of DSLs. GPCE, 2008.

Digital Library

[21]

S. Hong, H. Chafi, E. Sedlar, and K. Olukotun. Green-Marl: A DSL for Easy and Efficient Graph Analysis. ASPLOS, 2012.

Digital Library

[22]

P. Hudak. Building domain-specific embedded languages. ACM Computing Surveys, 28, 1996.

Digital Library

[23]

M. Isard, M. Budiu, Y. Yu, A. Birrell, and D. Fetterly. Dryad: distributed data-parallel programs from sequential building blocks. EuroSys, 2007.

Digital Library

[24]

JetBrains. Meta Programming System. http://www.jetbrains.com/mps/, 2009.

[25]

S. Kandel, A. Paepcke, J. Hellerstein, and J. Heer. Wrangler: interactive visual specification of data transformation scripts. CHI '11, 2011.

Digital Library

[26]

L. C. Kats and E. Visser. The spoofax language workbench: rules for declarative specification of languages and IDEs. OOPSLA '10, 2010.

Digital Library

[27]

E. Meijer, B. Beckman, and G. Bierman. LINQ: Reconciling Object, Relations and XML in the .NET framework. SIGMOD, 2006.

Digital Library

[28]

P.-A. Muller, F. Fleurey, D. Vojtisek, Z. Drey, D. Pollet, F. Fondement, P. Studer, J.-M. Jézéquel, et al. On executable meta-languages applied to model transformations. MTiP, 2005.

[29]

NVIDIA. CUDA. http://developer.nvidia.com/object/cuda.html.

[30]

N. Nystrom, D. White, and K. Das. Firepile: run-time compilation for GPUs in scala. GPCE, 2011.

Digital Library

[31]

T. Rompf and M. Odersky. Lightweight modular staging: a pragmatic approach to runtime code generation and compiled DSLs. Commun. ACM, 55(6):121--130, 2012.

Digital Library

[32]

T. Rompf, N. Amin, A. Moors, P. Haller, and M. Odersky. Scala-Virtualized: Linguistic Reuse for Deep Embeddings. Higher-Order and Symbolic Computation (Special issue for PEPM'12, to appear).

[33]

T. Rompf, A. K. Sujeeth, N. Amin, K. Brown, V. Jovanovic, H. Lee, M. Jonnalagedda, K. Olukotun, and M. Odersky. Optimizing Data Structures in High-Level Programs. POPL, 2013.

Digital Library

[34]

A. K. Sujeeth, H. Lee, K. J. Brown, T. Rompf, M. Wu, A. R. Atreya, M. Odersky, and K. Olukotun. OptiML: an Implicitly Parallel Domain-Specific Language for Machine Learning. ICML, 2011.

[35]

A. K. Sujeeth, T. Rompf, K. J. Brown, H. Lee, H. Chafi, V. Popic, M. Wu, A. Prokopec, V. Jovanovic, M. Odersky, and K. Olukotun. Composition and Reuse with Compiled Domain-Specific Languages. ECOOP, 2013.

Digital Library

[36]

H. Sutter. The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software. Dr. Dobb's Journal, 30(3):202--210, 2005.

[37]

W. Taha and T. Sheard. MetaML and multi-stage programming with explicit annotations. Theor. Comput. Sci., 248(1-2):211--242, 2000.

Digital Library

[38]

The Khronos Group. OpenCL 1.0. http://www.khronos.org/opencl/.

[39]

S. Tobin-Hochstadt, V. St-Amour, R. Culpepper, M. Flatt, and M. Felleisen. Languages as libraries. PLDI '11, 2011.

Digital Library

[40]

Typesafe. Simple Build Tool. http://www.scalasbt.org.

[41]

M. Zaharia, M. Chowdhury, T. Das, A. Dave, J. Ma, M. McCauley, M. Franklin, S. Shenker, and I. Stoica. Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing. NSDI, 2011.

Digital Library

Cited By

Shaikhha AChiba SThüm T(2024)Restaging Domain-Specific Languages: A Flexible Design Pattern for Rapid Development of Optimizing CompilersProceedings of the 23rd ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences10.1145/3689484.3690739(80-93)Online publication date: 21-Oct-2024
https://dl.acm.org/doi/10.1145/3689484.3690739
Tian ZDe Roover CRumpe BShaikhha A(2023)Multi-Stage Vertex-Centric Programming for Agent-Based SimulationsProceedings of the 22nd ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences10.1145/3624007.3624057(100-112)Online publication date: 22-Oct-2023
https://dl.acm.org/doi/10.1145/3624007.3624057
Fehr MNiu JRiddle RAmini MSu ZGrosser TJhala RDillig I(2022)IRDL: an IR definition language for SSA compilersProceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3519939.3523700(199-212)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519939.3523700
Show More Cited By

Index Terms

Forge: generating a high performance DSL implementation from a declarative specification
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
      1. Runtime environments
      2. Source code generation
    2. General programming languages
      1. Language types
        Concurrent programming languages
        Distributed programming languages
        Extensible languages
        Parallel programming languages

Recommendations

Delite: A Compiler Architecture for Performance-Oriented Embedded Domain-Specific Languages
Special Issue on Real-Time and Embedded Technology and Applications, Domain-Specific Multicore Computing, Cross-Layer Dependable Embedded Systems, and Application of Concurrency to System Design (ACSD'13)

Developing high-performance software is a difficult task that requires the use of low-level, architecture-specific programming models (e.g., OpenMP for CMPs, CUDA for GPUs, MPI for clusters). It is typically not possible to write a single application ...
Lightweight modular staging: a pragmatic approach to runtime code generation and compiled DSLs
GPCE '10: Proceedings of the ninth international conference on Generative programming and component engineering

Software engineering demands generality and abstraction, performance demands specialization and concretization. Generative programming can provide both, but the effort required to develop high-quality program generators likely offsets their benefits, ...
Forge: generating a high performance DSL implementation from a declarative specification
GPCE '13

Domain-specific languages provide a promising path to automatically compile high-level code to parallel, heterogeneous, and distributed hardware. However, in practice high performance DSLs still require considerable software expertise to develop and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GPCE '13: Proceedings of the 12th international conference on Generative programming: concepts & experiences

October 2013

198 pages

ISBN:9781450323734

DOI:10.1145/2517208

General Chair:
Jaakko Järvi
Texas A&M University, USA
,
Program Chair:
Christian Kästner
Carnegie Mellon University, USA

ACM SIGPLAN Notices Volume 49, Issue 3
GPCE '13
March 2014
181 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/2637365
Editors:
Mark W. Bailey
Hamilton College, Clinton, NY
,
Jaakko Järvi
Texas A&M University, USA
,
Christian Kästner
Carnegie Mellon University, USA
Issue’s Table of Contents

Copyright © 2013 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].

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 October 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GPCE'13

Sponsor:

SIGPLAN

GPCE'13: Generative Programming: Concepts and Experiences

October 27 - 28, 2013

Indiana, Indianapolis, USA

Acceptance Rates

GPCE '13 Paper Acceptance Rate 20 of 59 submissions, 34%;

Overall Acceptance Rate 56 of 180 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

37
Total Citations
View Citations
438
Total Downloads

Downloads (Last 12 months)16
Downloads (Last 6 weeks)2

Reflects downloads up to 16 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Shaikhha AChiba SThüm T(2024)Restaging Domain-Specific Languages: A Flexible Design Pattern for Rapid Development of Optimizing CompilersProceedings of the 23rd ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences10.1145/3689484.3690739(80-93)Online publication date: 21-Oct-2024
https://dl.acm.org/doi/10.1145/3689484.3690739
Tian ZDe Roover CRumpe BShaikhha A(2023)Multi-Stage Vertex-Centric Programming for Agent-Based SimulationsProceedings of the 22nd ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences10.1145/3624007.3624057(100-112)Online publication date: 22-Oct-2023
https://dl.acm.org/doi/10.1145/3624007.3624057
Fehr MNiu JRiddle RAmini MSu ZGrosser TJhala RDillig I(2022)IRDL: an IR definition language for SSA compilersProceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3519939.3523700(199-212)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519939.3523700
Brahmakshatriya AAmarasinghe SLee J(2022)GraphIt to CUDA compiler in 2021 LOCProceedings of the 20th IEEE/ACM International Symposium on Code Generation and Optimization10.1109/CGO53902.2022.9741280(53-65)Online publication date: 2-Apr-2022
https://dl.acm.org/doi/10.1109/CGO53902.2022.9741280
Young DGrebe MGill A(2021)On Adding Pattern Matching to Haskell-Based Deeply Embedded Domain Specific LanguagesPractical Aspects of Declarative Languages10.1007/978-3-030-67438-0_2(20-36)Online publication date: 13-Jan-2021
https://doi.org/10.1007/978-3-030-67438-0_2
Chelini LZinenko OGrosser TCorporaal H(2019)Declarative Loop Tactics for Domain-specific OptimizationACM Transactions on Architecture and Code Optimization10.1145/337226616:4(1-25)Online publication date: 26-Dec-2019
https://dl.acm.org/doi/10.1145/3372266
Kokologiannakis MRaad AVafeiadis V(2019)Effective lock handling in stateless model checkingProceedings of the ACM on Programming Languages10.1145/33605993:OOPSLA(1-26)Online publication date: 10-Oct-2019
https://dl.acm.org/doi/10.1145/3360599
Near JDarais DAbuah CStevens TGaddamadugu PWang LSomani NZhang MSharma NShan ASong D(2019)Duet: an expressive higher-order language and linear type system for statically enforcing differential privacyProceedings of the ACM on Programming Languages10.1145/33605983:OOPSLA(1-30)Online publication date: 10-Oct-2019
https://dl.acm.org/doi/10.1145/3360598
Wang SCao QMohan AHobor A(2019)Certifying graph-manipulating C programs via localizations within data structuresProceedings of the ACM on Programming Languages10.1145/33605973:OOPSLA(1-30)Online publication date: 10-Oct-2019
https://dl.acm.org/doi/10.1145/3360597
Huang MFu HChatterjee KGoharshady A(2019)Modular verification for almost-sure termination of probabilistic programsProceedings of the ACM on Programming Languages10.1145/33605553:OOPSLA(1-29)Online publication date: 10-Oct-2019
https://dl.acm.org/doi/10.1145/3360555
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 Table of Contents