Article

Dryad: distributed data-parallel programs from sequential building blocks

Authors:

Andrew Birrell,

Dennis FetterlyAuthors Info & Claims

EuroSys '07: Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems 2007

Pages 59 - 72

https://doi.org/10.1145/1272996.1273005

Published: 21 March 2007 Publication History

Abstract

Dryad is a general-purpose distributed execution engine for coarse-grain data-parallel applications. A Dryad application combines computational "vertices" with communication "channels" to form a dataflow graph. Dryad runs the application by executing the vertices of this graph on a set of available computers, communicating as appropriate through flies, TCP pipes, and shared-memory FIFOs.

The vertices provided by the application developer are quite simple and are usually written as sequential programs with no thread creation or locking. Concurrency arises from Dryad scheduling vertices to run simultaneously on multiple computers, or on multiple CPU cores within a computer. The application can discover the size and placement of data at run time, and modify the graph as the computation progresses to make efficient use of the available resources.

Dryad is designed to scale from powerful multi-core single computers, through small clusters of computers, to data centers with thousands of computers. The Dryad execution engine handles all the difficult problems of creating a large distributed, concurrent application: scheduling the use of computers and their CPUs, recovering from communication or computer failures, and transporting data between vertices.

References

[1]

Global grid forum. http://www.gridforum.org/.

[2]

Intel IXP2XXX product line of network processors. http://www.intel.com/design/network/products/npfamily/ixp2xxx.htm.

[3]

Intel platform 2015. http://www.Intel.com/technology/architecture/platform2015/.

[4]

The LINQ project. http://msdn.microsoft.com/netframework/future/linq/.

[5]

Open MPI. http://www.open-mpi.org/.

[6]

SQL Server Integration Services. http://www.microsoft.com/sq1/technologies/integration/default.mspx.

[7]

Thomas E. Anderson, David E. Culler, David A. Patterson, and NOW Team. A case for networks of workstations: NOW. IEEE Micro, pages 54--64, February 1995.

Digital Library

[8]

Remzi H. Arpaci-Dusseau. Run-time adaptation in River. Transactions on Computer Systems (TOCS), 21(1):36--86, 2003.

Digital Library

[9]

Özalp Babaoǧlu, Lorenzo Alvisi, Alessandro Amoroso, Renzo Davoli, and Luigi Alberto Giachini. Paralex: an environment for parallel programming in distributed systems. pages 178--187, New York, NY, USA, 1992. ACM Press.

Digital Library

[10]

Magdalena Balazinska, Hari Balakrishnan, Samuel Madden, and Mike Stonebraker. Fault-Tolerance in the Borealis Distributed Stream Processing System. In ACM SIGMOD, Baltimore, MD, June 2005.

Digital Library

[11]

Tom Barclay, Robert Barnes, Jim Gray, and Prakash Sundaresan. Loading databases using dataflow parallelism. SIGMOD Rec., 23(4):72--83, 1994.

Digital Library

[12]

Chaitanya Baru and Gilles Fecteau. An overview of DB2 parallel edition. In SIGMOD '95: Proceedings of the 1995 ACM SIGMOD international conference on Management of data, pages 460--462, New York, NY, USA, 1995. ACM Press.

Digital Library

[13]

Guy E. Blelloch. Programming parallel algorithms. Communications of the ACM (CACM), 39(3):85--97, 1996.

Digital Library

[14]

Robert D. Blumofe, Christopher F. Joerg, Bradley Kuszmaul, Charles E. Leiserson, Keith H. Randall, and Yuli Zhou. Cilk: An efficient multithreaded runtime system. In ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), pages 207--216, Santa Barbara, California, July 19--21 1995.

Digital Library

[15]

Eylon Caspi, Michael Chu, Randy Huang, Joseph Yeh, Yury Markovskiy, André DeHon, and John Wawrzynek. Stream computations organized for reconfigurable execution (SCORE): Introduction and tutorial. In FPL, Lecture Notes in Computer Science. Springer Verlag, 2000.

Digital Library

[16]

Jeff Dean and Sanjay Ghemawat. MapReduce: Simplified data processing on large clusters. In Proceedings of the 6th Symposium on Operating Systems Design and Implementation (OSDI), pages 137--150, December 2004.

Digital Library

[17]

D. DeWitt, S. Ghandeharizadeh, D. Schneider, H. Hsiao, A. Bricker, and R. Rasmussen. The GAMMA database machine project. IEEE Transactions on Knowledge and Data Engineering, 2(1), 1990.

Digital Library

[18]

David DeWitt and Jim Gray. Parallel database systems: The future of high performance database processing. Communications of the ACM, 36(6), 1992.

Digital Library

[19]

D. C. DiNucci and R. G. Babb II. Design and implementation of parallel programs with LGDF2. In Digest of Papers from Compcon '89, pages 102--107, 1989.

[20]

Armando Fox, Steven D. Gribble, Yatin Chawathe, Eric A. Brewer, and Paul Gauthier. Cluster-based scalable network services. In ACM Symposium on Operating Systems Principles (SOSP), pages 78--91, New York, NY, USA, 1997. ACM Press.

Digital Library

[21]

Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung. The Google file system. In SOSP '03: Proceedings of the nineteenth ACM symposium on Operating systems principles, pages 29--43, New York, NY, USA, 2003. ACM Press.

Digital Library

[22]

Goetz Graefe. Encapsulation of parallelism in the Volcano query processing system. In SIGMOD '90: Proceedings of the 1990 ACM SIGMOD international conference on Management of data, pages 102--111, New York, NY, USA, 1990. ACM Press.

Digital Library

[23]

J. Gray, A. S. Szalay, A. Thakar, P. Kunszt, C. Stoughton, D. Slutz, and J. Vandenberg. Data mining the SDSS SkyServer database. In Distributed Data and Structures 4: Records of the 4th International Meeting, pages 189--210, Paris, France, March 2002. Carleton Scientific, also as MSR-TR-2002-01.

[24]

Jim Gray and Alex Szalay. Science in an exponential world. Nature, 440(23), March 23 2006.

[25]

J.-H. Hwang, M. Balazinska, A. Rasin, U. Çetintemel, M. Stonebraker, and S. Zdonik. A comparison of stream-oriented high-availability algorithms. Technical Report TR-03-17, Computer Science Department, Brown University, September 2003.

[26]

Ujval Kapasi, William J. Dally, Scott Rixner, John D. Owens, and Brucek Khailany. The Imagine stream processor. In Proceedings 2002 IEEE International Conference on Computer Design, pages 282--288, September 2002.

Digital Library

[27]

Eddie Kohler, Robert Morris, Benjie Chen, John Jannotti, and M. Frans Kaashoek. The Click modular router. ACM Transactions on Computer Systems, 18(3):263--297, 2000.

Digital Library

[28]

James Larus and Michael Parkes. Using cohort scheduling to enhance server performance. In Usenix Annual Technical Conference, June 2002.

Digital Library

[29]

Orlando Loques, Julius Leite, and Enrique Vinicio Carrera E. P-RIO: A modular parallel-programming environment. IEEE Concurrency, 6(1):47--57, 1998.

Digital Library

[30]

William Mark, Steven Glanville, Kurt Akeley, and Mark J. Kilgard. Cg: A system for programming graphics hardware in a C-like language. ACM Transactions on Graphics, 22(3):896--907, 2003.

Digital Library

[31]

P. Newton and J. C. Browne. The CODE 2.0 graphical parallel programming language. pages 167 -- 177, Washington, D. C., United States, July 1992.

Digital Library

[32]

Ken Phillips. SenSage ESA. SC Magazine, March 1 2006.

[33]

Rob Pike, Sean Dorward, Robert Griesemer, and Sean Quinlan. Interpreting the data: Parallel analysis with Sawzall. Scientific Programming, 13(4):277--298, 2005.

Digital Library

[34]

Mehul A. Shah, Joseph M. Hellerstein, and Eric Brewer. Highly available, fault-tolerant, parallel dataflows. In SIGMOD '04: Proceedings of the 2004 ACM SIGMOD international conference on Management of data, pages 827--838, New York, NY, USA, 2004. ACM Press.

Digital Library

[35]

V. S. Sunderam. PVM: a framework for parallel distributed computing. Concurrency: Pract. Exper., 2(4):315--339, 1990.

Digital Library

[36]

David Tarditi, Sidd Puri, and Jose Oglesby. Accelerator: using data-parallelism to program GPUs for general-purpose uses. In International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), Boston, MA, October 2006. also as MSR-TR-2005-184.

Digital Library

[37]

Douglas Thain, Todd Tannenbaum, and Miron Livny. Distributed computing in practice: The Condor experience. Concurrency and Computation: Practice and Experience, 17(2-4):323--356, 2005.

Digital Library

[38]

P. W. Trinder, H-W. Loidl, and R. F. Pointon. Parallel and distributed Haskells. Journal of Functional Programming, 12(4&5):469--510, 2002.

Digital Library

Cited By

Liu YHe HHan TZhang XLiu MTian JZhang YWang JGao XZhong TPan YXu SWu ZLiu ZZhang XZhang SHu XZhang TQiang NLiu TGe B(2025)Understanding LLMs: A comprehensive overview from training to inferenceNeurocomputing10.1016/j.neucom.2024.129190620(129190)Online publication date: Mar-2025
https://doi.org/10.1016/j.neucom.2024.129190
Chlyah SGesbert NGenevès PLayaïda N(2025)Efficient Iterative Programs with Distributed Data CollectionsJournal of Logical and Algebraic Methods in Programming10.1016/j.jlamp.2025.101047(101047)Online publication date: Feb-2025
https://doi.org/10.1016/j.jlamp.2025.101047
Lin CHan ZZhang CYang YYang FChen CQiu LGavrilovska ATerry D(2024)ParrotProceedings of the 18th USENIX Conference on Operating Systems Design and Implementation10.5555/3691938.3691988(929-945)Online publication date: 10-Jul-2024
https://dl.acm.org/doi/10.5555/3691938.3691988
Show More Cited By

Index Terms

Dryad: distributed data-parallel programs from sequential building blocks
1. Computing methodologies
  1. Distributed computing methodologies
    1. Distributed programming languages
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Distributed programming languages

Recommendations

Dryad: distributed data-parallel programs from sequential building blocks
EuroSys'07 Conference Proceedings

Dryad is a general-purpose distributed execution engine for coarse-grain data-parallel applications. A Dryad application combines computational "vertices" with communication "channels" to form a dataflow graph. Dryad runs the application by executing ...
Conquering big data with spark and BDAS
SIGMETRICS '14: The 2014 ACM international conference on Measurement and modeling of computer systems

Today, big and small organizations alike collect huge amounts of data, and they do so with one goal in mind: extract "value" through sophisticated exploratory analysis, and use it as the basis to make decisions as varied as personalized treatment and ad ...
Distributed data-parallel computing using a high-level programming language
SIGMOD '09: Proceedings of the 2009 ACM SIGMOD International Conference on Management of data

The Dryad and DryadLINQ systems offer a new programming model for large scale data-parallel computing. They generalize previous execution environments such as SQL and MapReduce in three ways: by providing a general-purpose distributed execution engine ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EuroSys '07: Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems 2007

March 2007

431 pages

ISBN:9781595936363

DOI:10.1145/1272996

ACM SIGOPS Operating Systems Review Volume 41, Issue 3
EuroSys'07 Conference Proceedings
June 2007
386 pages
ISSN:0163-5980
DOI:10.1145/1272998
Issue’s Table of Contents

Copyright © 2007 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]

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 March 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

EuroSys07

Sponsor:

SIGOPS

EuroSys07: Eurosys 2007 Conference

March 21 - 23, 2007

Lisbon, Portugal

Acceptance Rates

Overall Acceptance Rate 241 of 1,308 submissions, 18%

Upcoming Conference

EuroSys '25

Sponsor:
sigops

Twentieth European Conference on Computer Systems

March 30 - April 3, 2025

Rotterdam , Netherlands

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2,052
Total Citations
View Citations
6,777
Total Downloads

Downloads (Last 12 months)214
Downloads (Last 6 weeks)15

Reflects downloads up to 13 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Liu YHe HHan TZhang XLiu MTian JZhang YWang JGao XZhong TPan YXu SWu ZLiu ZZhang XZhang SHu XZhang TQiang NLiu TGe B(2025)Understanding LLMs: A comprehensive overview from training to inferenceNeurocomputing10.1016/j.neucom.2024.129190620(129190)Online publication date: Mar-2025
https://doi.org/10.1016/j.neucom.2024.129190
Chlyah SGesbert NGenevès PLayaïda N(2025)Efficient Iterative Programs with Distributed Data CollectionsJournal of Logical and Algebraic Methods in Programming10.1016/j.jlamp.2025.101047(101047)Online publication date: Feb-2025
https://doi.org/10.1016/j.jlamp.2025.101047
Lin CHan ZZhang CYang YYang FChen CQiu LGavrilovska ATerry D(2024)ParrotProceedings of the 18th USENIX Conference on Operating Systems Design and Implementation10.5555/3691938.3691988(929-945)Online publication date: 10-Jul-2024
https://dl.acm.org/doi/10.5555/3691938.3691988
Zhang XKashaf AZou YZhang WLiao WSong HYe JLi YShi RTian YFeng WChen BChen ZZhang TTang Y(2024)ResLake: Towards Minimum Job Latency and Balanced Resource Utilization in Geo-Distributed Job SchedulingProceedings of the VLDB Endowment10.14778/3685800.368581717:12(3934-3946)Online publication date: 8-Nov-2024
https://dl.acm.org/doi/10.14778/3685800.3685817
Eizaguirre GBarcelona-Pons DArjona AVernik GGarcía-López PAlexandrov T(2024)Serverful Functions: Leveraging Servers in Complex Serverless Workflows (industry track)Proceedings of the 25th International Middleware Conference Industrial Track10.1145/3700824.3701095(15-21)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3700824.3701095
Jindal ABeedkar KSingh VMohammed JSingla TGupta AChoudhary K(2024)Reactive Dataflow for Inflight Error Handling in ML WorkflowsProceedings of the Eighth Workshop on Data Management for End-to-End Machine Learning10.1145/3650203.3663333(51-61)Online publication date: 9-Jun-2024
https://dl.acm.org/doi/10.1145/3650203.3663333
Chu DPanchapakesan RLaddad SKatahanas LLiu CShivakumar KCrooks NHellerstein JHoward H(2024)Optimizing Distributed Protocols with Query RewritesProceedings of the ACM on Management of Data10.1145/36392572:1(1-25)Online publication date: 26-Mar-2024
https://dl.acm.org/doi/10.1145/3639257
Song WEo JUm TJeon MChun B(2024)Blaze: Holistic Caching for Iterative Data ProcessingProceedings of the Nineteenth European Conference on Computer Systems10.1145/3627703.3629558(370-386)Online publication date: 22-Apr-2024
https://dl.acm.org/doi/10.1145/3627703.3629558
Song MNguyen LKim SEom HSon YMencagli GDazzi PLowenthal DBadia R(2024)ScaleDFS: Accelerating Decentralized and Private File Sharing via Scaling Directed Acyclic Graph ProcessingProceedings of the 33rd International Symposium on High-Performance Parallel and Distributed Computing10.1145/3625549.3658690(295-308)Online publication date: 3-Jun-2024
https://dl.acm.org/doi/10.1145/3625549.3658690
Adikari TAl-Lawati HLam JHu ZDraper S(2024)Exploiting Stragglers in Distributed Computing Systems with Task GroupingIEEE Transactions on Services Computing10.1109/TSC.2024.3495513(1-14)Online publication date: 2024
https://doi.org/10.1109/TSC.2024.3495513
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.

Figures

Tables

Media

View Table of Conten