Dryad

http://research.microsoft.com/research/sv/dryad/


Dryad

Overview
Project Members
Publications
Overview

Converting a sequential and/or single-machine program into a form in
which it can be executed in a concurrent, potentially distributed
environment is known to be hard. One long-standing technique to
address this is to decompose the program into two logical layers: a
high-level skeleton which expresses the data-flow, distribution and
concurrency properties; and a collection of subroutines each of which
is scheduled by the high-level layer, and executes locally with
restricted communications to the rest of the program.

This general approach has recently enjoyed practical success at two
very different scales: pixel shader languages deployed on many-core
graphics cards; and Google's MapReduce system deployed on a data-
center of many thousands of commodity PCs. In both cases it has been
found that large numbers of developers have been able to efficiently
develop and deploy parallelized algorithms running over hardware
resources which are not known at development time, and all without
specialized training in concurrent programming.

The Dryad project is an attempt to generalize this approach to provide
a programming model which scales from future single-machine many-core
PCs up to large-scale data-centers. We are initially focusing on a few
research questions:

* Composability: We want to decompose a program skeleton into a set of
simple operation classes (Map, Sort, etc.). We are developing a
composition language to glue them together again to support other
algorithm patterns such as joins while still hiding details like the
number of available CPUs from the programmer.
* Fault tolerance: A fundamental requirement of the Dryad system is
that it be resilient to failures of subsets of the computing
resources. Historically, parallel computing environments have
generally ignored failures. More recent systems have included
specialized mechanisms for masking faults, but we need to generalize
these to support the more varied topologies and communication patterns
we envisage.
* Applicability: Shader languages are good at describing rendering
algorithms. MapReduce has been shown to be well suited to data-mining
and transformation tasks. However, there are many other computing
tasks which are resource constrained and which do not map naturally
onto either of these existing systems. We want to understand whether
this paradigm for distributed programming can be used for example to
implement CPU-bound algorithms in computer vision, speech and machine
learning.

Project Members


* Andrew Birrell
* Mihai Budiu
* Dennis Fetterly
* Michael Isard
* Mark Manasse
* Yuan Yu

Publications

Dryad: Distributed Data-Parallel Programs from Sequential Building
Blocks
Michael Isard, Mihai Budiu, Yuan Yu, Andrew Birrell, and Dennis
Fetterly
European Conference on Computer Systems (EuroSys), Lisbon, Portugal,
March 21-23, 2007

Associated Groups


Distributed Systems - Silicon Valley
Silicon Valley

Web Search and Data Mining - Silicon Valley
Silicon Valley