Michael Isard
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.
- Global grid forum. http://www.gridforum.org/.Google Scholar
- Intel IXP2XXX product line of network processors. http://www.intel.com/design/network/products/npfamily/ixp2xxx.htm.Google Scholar
- Intel platform 2015. http://www.Intel.com/technology/architecture/platform2015/.Google Scholar
- The LINQ project. http://msdn.microsoft.com/netframework/future/linq/.Google Scholar
- Open MPI. http://www.open-mpi.org/.Google Scholar
- SQL Server Integration Services. http://www.microsoft.com/sq1/technologies/integration/default.mspx.Google Scholar
- 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. Google ScholarDigital Library
- Remzi H. Arpaci-Dusseau. Run-time adaptation in River. Transactions on Computer Systems (TOCS), 21(1):36--86, 2003. Google ScholarDigital Library
- Ö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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Tom Barclay, Robert Barnes, Jim Gray, and Prakash Sundaresan. Loading databases using dataflow parallelism. SIGMOD Rec., 23(4):72--83, 1994. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Guy E. Blelloch. Programming parallel algorithms. Communications of the ACM (CACM), 39(3):85--97, 1996. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- David DeWitt and Jim Gray. Parallel database systems: The future of high performance database processing. Communications of the ACM, 36(6), 1992. Google ScholarDigital Library
- 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.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google Scholar
- Jim Gray and Alex Szalay. Science in an exponential world. Nature, 440(23), March 23 2006.Google Scholar
- 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.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- James Larus and Michael Parkes. Using cohort scheduling to enhance server performance. In Usenix Annual Technical Conference, June 2002. Google ScholarDigital Library
- Orlando Loques, Julius Leite, and Enrique Vinicio Carrera E. P-RIO: A modular parallel-programming environment. IEEE Concurrency, 6(1):47--57, 1998. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- P. Newton and J. C. Browne. The CODE 2.0 graphical parallel programming language. pages 167 -- 177, Washington, D. C., United States, July 1992. Google ScholarDigital Library
- Ken Phillips. SenSage ESA. SC Magazine, March 1 2006.Google Scholar
- Rob Pike, Sean Dorward, Robert Griesemer, and Sean Quinlan. Interpreting the data: Parallel analysis with Sawzall. Scientific Programming, 13(4):277--298, 2005. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- V. S. Sunderam. PVM: a framework for parallel distributed computing. Concurrency: Pract. Exper., 2(4):315--339, 1990. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- P. W. Trinder, H-W. Loidl, and R. F. Pointon. Parallel and distributed Haskells. Journal of Functional Programming, 12(4&5):469--510, 2002. Google ScholarDigital Library
Index Terms
- Dryad: distributed data-parallel programs from sequential building blocks
Recommendations
Dryad: distributed data-parallel programs from sequential building blocks
EuroSys'07 Conference ProceedingsDryad 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 systemsToday, 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 dataThe 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