In order to achieve higher degrees of parallelism than feasible in shared-memory systems, work must be distributed among independent processors that don't contend for shared resources like memory. Instead of sharing memory, processes in a distributed system run on separate computers that each have their own memory. The processes communicate with each other by passing messages over a network. Message passing is not as easy to program or as fast as shared memory, but it does allow for much greater numbers of cores to be used by cooperating processes in many cases. In other words, it scales better than shared-memory parallelism.

In distributed parallel computing, a job consists of multiple processes running on the same or different computers in order to solve a single problem.

Creating a distributed parallel job could be as simple as writing a script containing several remote execution commands using a tool like ssh. However, multiple users running such jobs without some sort of traffic control could quickly lead to chaos. The solution to this problem, scheduling software, is discussed in the section called “Scheduler Basics”.

Distributed parallel computing environments are generally divided into clusters and grids, which are covered in the following sections.

In both grids and clusters, the various computers are referred to as nodes. A user logs into one of the nodes, known as a head node or submit node, and starts a job that dispatches processes on some of the other nodes, which are known as compute nodes.

A cluster is a group of commodity computers with a dedicated high-speed network and high-speed disk storage that is directly accessible to all the computers in the cluster. The dedicated network and shared disk allow processes on a cluster to communicate heavily with each other without overloading the office or campus network. The computers within a cluster are usually located in the same room, and often mounted together in a refrigerator-sized racks.

Peregrine, A Small Educational Cluster

Mortimer, A 2000-core Research Cluster

If it's possible to decompose a large computational job into somewhat independent sub-tasks, a cluster can provide a huge speed-up by deploying the work to hundreds or even thousands of cores at the same time. This type of computing is often referred to as high performance computing (HPC).

Most clusters also offer shared disk space, so that the same files are directly accessible to all nodes in the cluster. The shared space is a more or less typical file server shared by all the nodes, although on large clusters, it may be implemented using a special parallel file system designed specifically for HPC.

As stated earlier, clusters are suitable for problems that can be decomposed into a large number of relatively independent tasks that can be distributed among multiple computers to run in parallel. If decomposing a problem results in tasks that must share extremely large volumes of data, then a shared memory architecture may provide better performance. Fortunately, there are many large computational problems that adapt well to the distributed computing model offered by clusters.

There are several types of nodes in a typical cluster:

A grid made up of loosely coupled computers which may be in multiple distant locations. Grids often utilize spare CPU time on existing office or lab PCs. No additional hardware is generally required to form a grid from existing PCs on a network.

A Small Grid

A grid is similar to a cluster, but without the high-speed communication network and high-speed shared storage typically seen on clusters. Grids often utilize hardware that was not designed and built primarily for parallel computing. Instead, grids are commonly implemented to take advantage of already existing hardware that may not otherwise be well utilized, such as PCs in college computer labs. Lab PCs tend to be heavily utilized occasionally (during classes) but idle most other times.

Grids are often implemented with no improvements to the existing hardware infrastructure. Since the computers are already installed and connected by a network, a grid can be often implemented simply by installing and configuring grid management software such as LPJS (https://github.com/outpaddling/LPJS/), or HTCondor ( http://research.cs.wisc.edu/htcondor/). It is not even necessary for all the computers to run the same operating system, although standardizing will make the grid easier to use. The standardization of PC configurations can be rendered unnecessary using virtual machines to serve as compute hosts. Virtual Machine software such as VirtualBox can run the same standard guest operating system on a wide variety of host platforms. Using a virtual machine also alleviates security concerns for the host machine, since the computational jobs are contained in an isolated environment.

Since machines on a grid communicate over a standard, non-dedicated campus or office network, extensive message-passing between parallel processes or high-volume shared file servers would be likely to overload the network. Therefore, some of the programs that we typically run on clusters are not suitable for grids.

Grids are only suitable for algorithms that can be decomposed into highly independent processes that require little or no communication with each other while running, i.e. embarrassingly parallel computing. Grid users often simply run many instances of serial programs at the same time. In other words, grid users often do parallel computing without parallel programming.

Grid computing is often referred to as High Throughput Computing, or HTC, since the lack of communication between processes eliminates potential bottlenecks that might slow the progress of the computations and reduce throughput.

Many campuses are implementing grids to provide an inexpensive parallel computation resource for students and researchers. One of the leaders in this area is Purdue University, where every computer on the entire campus is part of a massive grid.