Parallel Algorithms | Research & Encyclopedia Articles

Parallel Algorithms

With the advent of parallel processing, the raw computing power available to solve many problems is now immense, well beyond what was available using conventional uniprocessor computing techniques. This is especially significant in solving the so-called Grand Challenge problems of computing. A Grand Challenge problem (such as accurate weather forecasting) is a fundamental problem of science or engineering, having a broad social or economic impact, whose solution requires the use of very high-end computing power.

Many problem domains are also naturally suited to parallel processing. For instance, applications such as weather prediction, biosphere modeling, population analyses, and the like are modeled by assuming a grid on the domain being modeled. The segments (squares or cubes) of the grid are analyzed for their influences on surrounding segments, and vice versa. This often requires solutions to large systems of differential equations, with the granularity of the grid chosen determining the accuracy of the model. Such a problem often cannot be solved using sequential algorithms running on a uniprocessor.

As an example of such a problem, consider the task of modeling the weather over the lower 48 states of the United States. We may say that the area being modeled is approximately 3000 miles x 3000 miles, and that the atmosphere up to a height of 10 miles is significant in determining the weather. Assume that the 3000 x 3000 x 10 cubic mile weather domain is partitioned into segments of size 0.1 x 0.1 x 0.1 cubic miles. There are thus about 10¹¹ different segments.

In a weather modeling system, time is an additional dimension in the computations, since the model has to show the changes of weather over time. Let us say that in our model we need to model the weather over a two-day (48 hour) period, and that the variables must be updated every half hour--these are very conservative assumptions, likely to be highly inaccurate in practice (practical weather forecasting models require much faster updates, often within minutes). The computation of variables (temperature, pressure, wind speed, humidity, cloud cover, etc.) in each segment may be taken to require the previous values of the variables in that segment, as well as the values from neighboring segments. Assume that this computation requires 100 instructions to be executed (again, a very conservative estimate). Thus, a single half-hourly update of the variables for the whole system requires 10¹¹ x 100, or 10¹³ instructions. As there are about 100 such updates over two days, the total number of instructions to be executed is about 10¹⁵. On a high-end serial computer capable of computing one billion instructions a second, this computation would require about 280 hours, or almost twelve days.

This illustrates one important problem with serial computing even using fast computers--a weather forecasting system that takes twelve days to forecast the weather over the next two days is obviously useless. Parallel algorithms running on many machines thus are required--by partitioning the large problem among many processors (such as by allocating large chunks of the three-dimensional segment space to them for individual processing), problems such as weather forecasting may be solved.

A basic approach to the study of parallel algorithms is to assume that the size of the input space is equal to the number of available processors that can be used in parallel. This is obviously not always accurate--it is unrealistic to grant that one could have 10¹¹ processors to solve the weather forecasting problem described above. However, the assumption is useful to the extent that it illustrates which problems are capable of being solved in parallel. In general, it is good for the size of the input space to be divisible by the number of processors available, but this too may be an over-simplistic assumption. Most processors in real life are also not dedicated to just one task such as weather modeling, and may have other variable loads that change from time to time. The number of processors available may also change periodically due to crashes or maintenance, or as new ones are added to the system. Randomization and other techniques are often applied to distribute the load among processors running in parallel.

In running a parallel algorithm, the ideal case would be where with n processors each of which takes time T to solve the problem, one would be able to solve the problem in T divided by n time. However, there are communication overheads (time and processor cycles taken for communication between processors), network delays, and the like--the problem itself may also not be easily parallelizable. For such reasons, this is usually more than the gain actually achieved with n processors. The "Principle of Unitary Speedup" says that the gain from using n each of which takes time T, is at most equal to that of using a single processor which takes time T/n.

In randomized parallel algorithms, sometimes the principle given above may not hold true, and super-linear gain may be observed occasionally due to the unpredictable performance of randomized algorithms. In deterministic algorithms, however, the principle is always true.