Traditionally,
computer software has been written for
serial computation. To solve a problem, an
algorithm is constructed and implemented as a serial stream of instructions. These instructions are executed on a
central processing unit on one computer. Only one instruction may execute at a time—after that instruction is finished, the next one is executed. Parallel computing, on the other hand, uses multiple processing elements simultaneously to solve a problem. This is accomplished by breaking the problem into independent parts so that each processing element can execute its part of the algorithm simultaneously with the others. The processing elements can be diverse and include resources such as a single computer with multiple processors, several networked computers, specialized hardware, or any combination of the above.
Frequency scaling was the dominant reason for improvements in
computer performance from the mid-1980s until 2004. The
runtime of a program is equal to the number of instructions multiplied by the average time per instruction. Maintaining everything else constant, increasing the clock frequency decreases the average time it takes to execute an instruction. An increase in frequency thus decreases runtime for all
compute-bound programs. However, power consumption
P by a chip is given by the equation
P =
C ×
V 2 ×
F, where
C is the
capacitance being switched per clock cycle (proportional to the number of transistors whose inputs change),
V is
voltage, and
F is the processor frequency (cycles per second). Increases in frequency increase the amount of power used in a processor. Increasing processor power consumption led ultimately to
Intel's May 8, 2004 cancellation of its
Tejas and Jayhawk processors, which is generally cited as the end of frequency scaling as the dominant computer architecture paradigm. To deal with the problem of power consumption and overheating the major
central processing unit (CPU or processor) manufacturers started to produce power efficient processors with multiple cores. The core is the computing unit of the processor and in multi-core processors each core is independent and can access the same memory concurrently.
Multi-core processors have brought parallel computing to
desktop computers. Thus parallelization of serial programs has become a mainstream programming task. In 2012 quad-core processors became standard for
desktop computers, while
servers had 10+ core processors.
Moore's law predicted that the number of cores per processor would double every 18–24 months. By 2023 some processors had over hundred cores. Some designs having a mix of performance and efficiency cores (such as
ARM's big.LITTLE design) due to thermal and design constraints. An
operating system can ensure that different tasks and user programs are run in parallel on the available cores. However, for a serial software program to take full advantage of the multi-core architecture the programmer needs to restructure and parallelize the code. A speed-up of application software runtime will no longer be achieved through frequency scaling, instead programmers will need to parallelize their software code to take advantage of the increasing computing power of multicore architectures.
Relevant laws . The law demonstrates the theoretical maximum
speedup of an overall system and the concept of diminishing returns. If exactly 50% of the work can be parallelized, the best possible speedup is 2 times. If 95% of the work can be parallelized, the best possible speedup is 20 times. According to the law, even with an infinite number of processors, the speedup is constrained by the unparallelizable portion. Optimally, the
speedup from parallelization would be linear—doubling the number of processing elements should halve the runtime, and doubling it a second time should again halve the runtime. However, very few parallel algorithms achieve optimal speedup. Most of them have a near-linear speedup for small numbers of processing elements, which flattens out into a constant value for large numbers of processing elements. The maximum potential speedup of an overall system can be calculated by
Amdahl's law. Amdahl's Law indicates that optimal performance improvement is achieved by balancing enhancements to both parallelizable and non-parallelizable components of a task. Furthermore, it reveals that increasing the number of processors yields diminishing returns, with negligible speedup gains beyond a certain point. Amdahl's Law has limitations, including assumptions of fixed workload, neglecting
inter-process communication and
synchronization overheads, primarily focusing on computational aspect and ignoring extrinsic factors such as data persistence, I/O operations, and memory access overheads.
Gustafson's law and
Universal Scalability Law give a more realistic assessment of the parallel performance.
Dependencies Understanding
data dependencies is fundamental in implementing
parallel algorithms. No program can run more quickly than the longest chain of dependent calculations (known as the
critical path), since calculations that depend upon prior calculations in the chain must be executed in order. However, most algorithms do not consist of just a long chain of dependent calculations; there are usually opportunities to execute independent calculations in parallel. Let
Pi and
Pj be two program segments. Bernstein's conditions describe when the two are independent and can be executed in parallel. For
Pi, let
Ii be all of the input variables and
Oi the output variables, and likewise for
Pj.
Pi and
Pj are independent if they satisfy : I_j \cap O_i = \varnothing, : I_i \cap O_j = \varnothing, : O_i \cap O_j = \varnothing. Violation of the first condition introduces a flow dependency, corresponding to the first segment producing a result used by the second segment. The second condition represents an anti-dependency, when the second segment produces a variable needed by the first segment. The third and final condition represents an output dependency: when two segments write to the same location, the result comes from the logically last executed segment. Consider the following functions, which demonstrate several kinds of dependencies: 1: function Dep(a, b) 2: c := a * b 3: d := 3 * c 4: end function In this example, instruction 3 cannot be executed before (or even in parallel with) instruction 2, because instruction 3 uses a result from instruction 2. It violates condition 1, and thus introduces a flow dependency. 1: function NoDep(a, b) 2: c := a * b 3: d := 3 * b 4: e := a + b 5: end function In this example, there are no dependencies between the instructions, so they can all be run in parallel. Bernstein's conditions do not allow memory to be shared between different processes. For that, some means of enforcing an ordering between accesses is necessary, such as
semaphores,
barriers or some other
synchronization method.
Race conditions, mutual exclusion, synchronization, and parallel slowdown Subtasks in a parallel program are often called
threads. Some parallel computer architectures use smaller, lightweight versions of threads known as
fibers, while others use bigger versions known as
processes. However, "threads" is generally accepted as a generic term for subtasks. Threads will often need
synchronized access to an
object or other
resource, for example when they must update a
variable that is shared between them. Without synchronization, the instructions between the two threads may be interleaved in any order. For example, consider the following program: If instruction 1B is executed between 1A and 3A, or if instruction 1A is executed between 1B and 3B, the program will produce incorrect data. This is known as a
race condition. The programmer must use a
lock to provide
mutual exclusion. A lock is a programming language construct that allows one thread to take control of a variable and prevent other threads from reading or writing it, until that variable is unlocked. The thread holding the lock is free to execute its
critical section (the section of a program that requires exclusive access to some variable), and to unlock the data when it is finished. Therefore, to guarantee correct program execution, the above program can be rewritten to use locks: One thread will successfully lock variable V, while the other thread will be
locked out—unable to proceed until V is unlocked again. This guarantees correct execution of the program. Locks may be necessary to ensure correct program execution when threads must serialize access to resources, but their use can greatly slow a program and may affect its
reliability. Locking multiple variables using
non-atomic locks introduces the possibility of program
deadlock. An
atomic lock locks multiple variables all at once. If it cannot lock all of them, it does not lock any of them. If two threads each need to lock the same two variables using non-atomic locks, it is possible that one thread will lock one of them and the second thread will lock the second variable. In such a case, neither thread can complete, and deadlock results. Many parallel programs require that their subtasks
act in synchrony. This requires the use of a
barrier. Barriers are typically implemented using a lock or a
semaphore. One class of algorithms, known as
lock-free and wait-free algorithms, altogether avoids the use of locks and barriers. However, this approach is generally difficult to implement and requires correctly designed data structures. Not all parallelization results in speed-up. Generally, as a task is split up into more and more threads, those threads spend an ever-increasing portion of their time communicating with each other or waiting on each other for access to resources. Once the overhead from resource contention or communication dominates the time spent on other computation, further parallelization (that is, splitting the workload over even more threads) increases rather than decreases the amount of time required to finish. This problem, known as
parallel slowdown, can be improved in some cases by software analysis and redesign.
Fine-grained, coarse-grained, and embarrassing parallelism Applications are often classified according to how often their subtasks need to synchronize or communicate with each other. An application exhibits fine-grained parallelism if its subtasks must communicate many times per second; it exhibits coarse-grained parallelism if they do not communicate many times per second, and it exhibits
embarrassing parallelism if they rarely or never have to communicate. Embarrassingly parallel applications are considered the easiest to parallelize.
Flynn's taxonomy Michael J. Flynn created one of the earliest classification systems for parallel (and sequential) computers and programs, now known as
Flynn's taxonomy. Flynn classified programs and computers by whether they were operating using a single set or multiple sets of instructions, and whether or not those instructions were using a single set or multiple sets of data. The single-instruction-single-data (SISD) classification is equivalent to an entirely sequential program. The single-instruction-multiple-data (SIMD) classification is analogous to doing the same operation repeatedly over a large data set. This is commonly done in
signal processing applications. Multiple-instruction-single-data (MISD) is a rarely used classification. While computer architectures to deal with this were devised (such as
systolic arrays), few applications that fit this class materialized. Multiple-instruction-multiple-data (MIMD) programs are by far the most common type of parallel programs. According to
David A. Patterson and
John L. Hennessy, "Some machines are hybrids of these categories, of course, but this classic model has survived because it is simple, easy to understand, and gives a good first approximation. It is also—perhaps because of its understandability—the most widely used scheme." == Disadvantages ==