The notes from the previous lecture have been corrected and clarified regarding the analysis of the communication costs of the parallel implementation of Floyd's Algorithm.
The evolution of the Internet has led to a number of approaches to make use of networked computing resources for parallel computation.
A number of projects have worked to make use of internet-connected computing resoruces.
Many of these approaches fall under the category of grid computing, sometimes also called metacomputing.
The name "grid computing" can be misleading - it does not refer to a collection of processors connected by a grid-like network. The name comes from an analogy with the power grid. You "plug in" to the Internet and get your computational needs satisfied from available resources.
One view of the goal of grid computing is that users should see one integrated, dependable, global computing resource.
Some of the issues to consider:
Both producers and consumers of grid resources join in for economic reasons:
Example application: visualization of the output of an electron microscope:
NSF is supporting a project called the Distributed Teragrid Facility (DTF) which intends to build the TeraGrid, capable of 11.6 trillion calculations per second, with components located at NCSA, SDSC, ANL, Caltech.
Some projects:
This project (http://setiathome.ssl.berkeley.edu) uses otherwise idle personal computers to analyze the massive volume of data produced by the Search for Extraterrestrial Intelligence (SETI) telescope.
Their idea was to break up the data into chunks to be farmed out to computers that are volunteered for use by their owners.
The program runs as a screen saver, so it is only taking up the volunteer's computing resources when they're not otherwise in use.
The computation is a good candidate for this approach, since it is embarassingly parallel. The data is broken into chunks of about 250K which are sent off to participating computers. One of these "work units" takes several hours to a few days of computing time, involving a few trillion mathematical operations.
Some concerns here:
The project addresses these concerns by:
One estimate is that 500,000 computers participate, providing 1000 CPU-years per day!
A similar approach was used by the Twin Primes project: http://www.cs.rpi.edu/research/twinp
This project was an effort to break the record for the largest known pair of "twin primes" - a pair of prime numbers whose difference is 2.
Concerns are similar to those of SETI@Home, where compute nodes can come and go. The computer running a server could also crash, and the work lost needs to be minimized.
A worker process gets a range of 10 billion numbers to check for the existence of twin primes, and report back.
In addition to volunteers who run the process on their own systems, this project included the use of a large number of workstations at RPI. However, the only way to get permission to run on these systems was to promise not to interfere with their normal work. A system was developed called "SCATTERS" (Simple Cool Admin Tool To Everywhere Run Something) that starts up a worker when the system is idle, but kills it when other activity is detected. This allowed the use of 247 systems.
Actual computation uses Sieve of Eratosthenes.
The project continued for 2 years, and broke the record for the largest pair of twin primes which were over 1016.
Both SETI@Home and the Twin Primes use a client-server model. The server farms out chunks of work to willing clients. It is up to the client to decide when to request work. We can think of this as a more distributed bag of tasks idea.
Condor (http://www.cs.wisc.edu/condor) has been developed since the late 1980's as a way to make use of available CPU cycles on idle workstations.
Target: high-throughput computing.
The system is intended to run general Unix processes on available resourced by "scavenging" cycles.
It has been expanded to be able to run parallel (MPI, PVM) jobs as well.
Services needed:
Condor is intended to use bother dedicated and non-dedicated resources.
Condor runs jobs even if some machines:
Mechanisms:
A key feature of this system is the ability to do process migration, using the checkpointing feature.
To stop a job running on one system and start it up on another from where it left off, it neeeds to remember everything about the current state of the process, remove itself from that system, then move to another system, start up, and restore its state.
Condor's checkpointing feature:
Saving the state of a process:
The rest of the details here.
How to go about scheduling process in a Condor "flock"?
Given the ability to migrate processes, we can do opportunistic scheduling - assign a process to a node even if we're pretty sure it will not have a chance to execute to completion before the node will become unavailable.
But for things like MPI processes, we do not want to allow processes to migrate, and we don't want one of our processes to stop while others are allowed to continue (since they will not continue for long), so Condor also allows for dedicated scheduling on nodes that advertise that capability. Checkpointing parallel jobs is hard.
Most dedicated schedulers require a maximum amount of time to allow backfilling with shorter/smaller jobs. Condor can fill in any "holes" in the schedule with the regular (preemptable) jobs without delaying dedicated jobs, since those preemptable jobs can just be preempted..
The Globus Toolkit (http://www.globus.org/) is part of the Globus project that is working to support grid computing.