FACTOID # 30: If Alaska were its own country, it would be the 26th largest in total area, slightly larger than Iran.

 Home Encyclopedia Statistics States A-Z Flags Maps FAQ About

 WHAT'S NEW

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

(* = Graphable)

Encyclopedia > Parallel computing
The Cray-2 was the world's fastest computer from 1985 to 1989.

Parallel computing is a form of computation in which many instructions are carried out simultaneously,[1] operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently ("in parallel"). There are several different forms of parallel computing: bit-level parallelism, instruction-level parallelism, data parallelism, and task parallelism. It has been used for many years, mainly in high-performance computing, but interest in it has grown in recent years due to the physical constraints preventing frequency scaling. Parallel computing has become the dominant paradigm in computer architecture, mainly in the form of multicore processors.[2] However, in recent years, power consumption by parallel computers has become a concern.[3] ImageMetadata File history File links Download high resolution version (2592x1944, 2110 KB) File links The following pages link to this file: Supercomputer Cray-2 ... ImageMetadata File history File links Download high resolution version (2592x1944, 2110 KB) File links The following pages link to this file: Supercomputer Cray-2 ... The Cray-2 is in the left foreground. ... For the formal concept of computation, see computation. ... In computer science, an instruction typically refers to a single operation of a processor within a computer architecture. ... The Dining Philosophers, a classic problem involving concurrency and shared resources In computer science, concurrency is a property of systems in which several computational processes are executing at the same time, and potentially interacting with each other. ... Bit-level parallelism is a form of parallel computing based on increasing processor word size. ... Instruction-level parallelism (ILP) is a measure of how many of the operations in a computer program can be dealt with at once. ... Data parallelism (also known as loop-level parallelism) is a form of parallelization of computing across multiple processors in parallel computing environments. ... Task Parallelism is a form of parallelization of computer code. ... The field of high performance computing (HPC) comprises computing applications on (parallel) supercomputers and computer clusters. ... For the power conservation technique, see dynamic frequency scaling. ... A typical vision of a computer architecture as a series of abstraction layers: hardware, firmware, assembler, kernel, operating system and applications (see also Tanenbaum 79). ... Diagram of an Intel Core 2 dual core processor, with CPU-local Level 1 caches, and a shared, on-die Level 2 cache. ... In electrical engineering, power consumption refers to the electrical energy over time that must be supplied to an electrical device to maintain its operation. ...

Parallel computers can be roughly classified according to the level at which the hardware supports parallelism—with multi-core and multi-processor computers having multiple processing elements within a single machine, while clusters, MPPs, and grids use multiple computers to work on the same task. Diagram of a generic dual core processor, with CPU-local Level 1 caches, and a shared, on-die Level 2 cache. ... Symmetric multiprocessing, or SMP, is a multiprocessor computer architecture where two or more identical processors are connected to a single shared main memory. ... An example of a Computer cluster A computer cluster is a group of tightly coupled computers that work together closely so that in many respects they can be viewed as though they are a single computer. ... Massive parallel processing (MPP) is a term used in computer architecture to refer to a computer system with many independent arithmetic units or entire microprocessors, that run in parallel. ... Grid computing is a phrase in distributed computing which can have several meanings: Multiple independent computing clusters which act like a grid because they are composed of resource nodes not located within a single administrative domain. ...

Parallel computer programs are more difficult to write than sequential ones,[4] because concurrency introduces several new classes of potential software bugs, of which race conditions are the most common. Communication and synchronization between the different subtasks is typically one of the greatest barriers to getting good parallel program performance. The speed-up of a program as a result of parallelization is given by Amdahl's law. In computer science, a parallel algorithm, as opposed to a traditional serial algorithm, is one which can be executed a piece at a time in many different processing devices, and then put back together again at the end to get the correct result. ... A software bug is an error, flaw, mistake, failure, or fault in a computer program that prevents it from behaving as intended (e. ... A race condition or race hazard is a flaw in a system or process whereby the output of the process is unexpectedly and critically dependent on the sequence or timing of other events. ... This article or section is in need of attention from an expert on the subject. ... In computer science, especially parallel computing, synchronization means the coordination of simultaneous threads or processes to complete a task in order to get correct runtime order and avoid unexpected race conditions. ... In parallel computing, speedup refers to how much a parallel algorithm is faster than a corresponding sequential algorithm. ... The speedup of a program using multiple processors in parallel computing is limited by the sequential fraction of the program. ...

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 is executed.[5] Flowcharts are often used to graphically represent algorithms. ... CPU redirects here. ...

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.[5]

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 computation-bounded programs.[6] For the power conservation technique, see dynamic frequency scaling. ... CPU bound refers to a condition where the time to complete a computation is determined principally by the speed of the central processor and main memory. ...

However, power consumption by a chip is given by the equation P = C × V2 × F, where P is power, 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).[7] Increases in frequency increase the amount of power used in a processor. Increasing processor power consumption led ultimately to Intel's May 2004 cancellation of its Tejas and Jayhawk processors, which is generally cited as the end of frequency scaling as the dominant computer architecture paradigm.[8] In electrical engineering, power consumption refers to the electrical energy over time that must be supplied to an electrical device to maintain its operation. ... Capacitance is a measure of the amount of electric charge stored (or separated) for a given electric potential. ... International safety symbol Caution, risk of electric shock (ISO 3864), colloquially known as high voltage symbol. ... Intel Corporation (NASDAQ: INTC, SEHK: 4335), founded in 1968 as Integrated Electronics Corporation, is an American multinational corporation that is best known for designing and manufacturing microprocessors and specialized integrated circuits. ... Tejas was a code name for Intels microprocessor which was to be a successor to the latest Pentium 4 with Prescott core. ...

Moore's Law is the empirical observation that transistor density in a microprocessor doubles every 18 to 24 months. Despite power consumption issues, and repeated predictions of its end, Moore's law is still in effect. With the end of frequency scaling, these additional transistors (which are no longer used for frequency scaling) can be used to add extra hardware for parallel computing. Gordon Moores original graph from 1965 Growth of transistor counts for Intel processors (dots) and Moores Law (upper line=18 months; lower line=24 months) For the observation regarding information retrieval, see Mooers Law. ...

### Amdahl's law and Gustafson's law

The program runtime and speed-up of a program with suboptimal parallelization. The blue curve illustrates the (linear) speed-up the program would have experienced in the optimal case, while the purple curve indicates the actual (suboptimal) speed-up. By the same token, the yellow curve indicates the runtime the program would have experienced in the optimal case (an asymptote which approaches zero), while the red curve indicates the actual runtime (an asymptote which approaches a value greater-than-zero)

Theoretically, the speed-up from parallelization should 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 speed-up. Most of them have a near-linear speed-up for small numbers of processing elements, which flattens out into a constant value for large numbers of processing elements. Image File history File links No higher resolution available. ... Image File history File links No higher resolution available. ... For other uses, see Asymptote (disambiguation). ...

The potential speed-up of an algorithm on a parallel computing platform is given by Amdahl's law, originally formulated by Gene Amdahl in the 1960s.[9] It states that a small portion of the program which cannot be parallelized will limit the overall speed-up available from parallelization. Any large mathematical or engineering problem will typically consist of several parallelizable parts and several non-parallelizable (sequential) parts. This relationship is given by the equation: The speedup of a program using multiple processors in parallel computing is limited by the sequential fraction of the program. ... Gene Amdahl addressing a UW-Madison Alumni gathering, March 13 2008. ...

$S = frac{1}{(1 - P)}$

where S is the speed-up of the program (as a factor of its original sequential runtime), and P is the fraction that is parallelizable. If the sequential portion of a program is 10% of the runtime, we can get no more than a 10x speed-up, regardless of how many processors are added. This puts an upper limit on the usefulness of adding more parallel execution units. "When a task cannot be partitioned because of sequential constraints, the application of more effort has no effect on the schedule. The bearing of a child takes nine months, no matter how many women are assigned."[10]

Gustafson's law is another law in computer engineering, closely related to Amdahl's law. It can be formulated as: Gustafsons Law (also known as Gustafson-Barsis law) is a law in computer engineering which states that any sufficiently large problem can be efficiently parallelized. ...

A graphical representation of Amdahl's law Assume that a task has two independent parts, A and B. B takes roughly 25% of the time of the whole computation. With effort, a programmer may be able to make this part five times faster, but this only reduces the time for the whole computation by a little. In contrast, one may need to perform less work to make part A twice as fast. This will make the computation much faster than by optimizing part B, even though B got a greater speed-up, (5x versus 2x).
$displaystyle S(P) = P - alpha(P-1)$

where P is the number of processors, S is the speed-up, and α the non-parallelizable part of the process.[11] Amdahl's law assumes a fixed-problem size and that the size of the sequential section is independent of the number of processors, whereas Gustafson's law does not make these assumptions. Image File history File links Optimizing-different-parts. ... Image File history File links Optimizing-different-parts. ... The speedup of a program using multiple processors in parallel computing is limited by the sequential fraction of the program. ...

### 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. A data dependency in computer science is a situation whereby computer instructions refer to the results of preceding instructions that have not yet been completed. ... In computer science, a parallel algorithm, as opposed to a traditional serial algorithm, is one which can be executed a piece at a time in many different processing devices, and then put back together again at the end to get the correct result. ... In project management, a critical path is the sequence of project network terminal elements with the longest overall duration, determining the shortest time to complete the project. ...

Let Pi and Pj be two program fragments. Bernstein's conditions[12] describe when the two are independent and can be executed in parallel. Let Ii be all of the input variables to Pi and Oi the output variables, and likewise for Pj. P i and Pj are independent if they satisfy

• $I_j cap O_i = emptyset$
• $I_i cap O_j = emptyset$
• $O_i cap O_j = emptyset$

Violation of the first condition introduces a flow dependency, corresponding to the first statement producing a result used by the second statement. The second condition represents an anti-dependency, when the first statement overwrites a variable needed by the second expression. The third and final condition, q, is an output dependency. When two variables write to the same location, the final output must have arisen from the second statement.[13]

Consider the following functions, which demonstrate several kinds of dependencies:

` 1: function Dep(a, b) 2: c := a·b 3: d := 2·c 4: end function `

Operation 3 in Dep(a, b) cannot be executed before (or even in parallel with) operation 2, because operation 3 uses a result from operation 2. It violates condition 1, and thus introduces a flow dependency.

` 1: function NoDep(a, b) 2: c := a·b 3: d := 2·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. This article is about the computer science application of mutual exclusion. ... In parallel computing, a barrier is a type of synchronization method. ... In computer science, especially parallel computing, synchronization means the coordination of simultaneous threads or processes to complete a task in order to get correct runtime order and avoid unexpected race conditions. ...

### 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 to update some variable that is shared between them. The instructions between the two programs may be interleaved in any order. For example, consider the following program: For the form of code consisting entirely of subroutine calls, see Threaded code. ... A fiber in computer science is a term for a particularly lightweight thread of execution. ... In computing, a process is an instance of a computer program that is being executed. ... In computer science and mathematics, a variable (pronounced ) (sometimes called an object or identifier in computer science) is a symbolic representation used to denote a quantity or expression. ... Interleaving in computer science is a way to arrange data in a noncontiguous way in order to increase performance. ...

 Thread A Thread B 1A: Read variable V 1B: Read variable V 2A: Add 1 to variable V 2B: Add 1 to variable V 3A Write back to variable V 3B: Write back to variable V

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: A race condition or race hazard is a flaw in a system or process whereby the output of the process is unexpectedly and critically dependent on the sequence or timing of other events. ... In computer science, a lock is a synchronization mechanism for enforcing limits on access to a resource in an environment where there are many threads of execution. ... Mutual exclusion (often abbreviated to mutex) algorithms are used in concurrent programming to avoid the simultaneous use of un-shareable resources by pieces of computer code called critical sections. ... In computer programming a critical section is a piece of code that can only be executed by one process or thread at a time. ...

 Thread A Thread B 1A: Lock variable V 1B: Lock variable V 2A: Read variable V 2B: Read variable V 3A: Add 1 to variable V 3B: Add 1 to variable V 4A Write back to variable V 4B: Write back to variable V 5A: Unlock variable V 5B: Unlock variable V

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, while necessary to ensure correct program execution, can greatly slow a program. In multiprocessor computer systems, software lockout is the issue of performance degradation due to the idle wait times spent by the CPUs in kernel-level critical sections. ...

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. In computer science, an atomic operation is an operation during which a processor can simultaneously read a location and write it in the same bus operation. ... This article is about deadlock in computing. ...

Many parallel programs require that their subtasks act in synchrony. This requires the use of a barrier. Barriers are typically implemented using a software lock. 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. In computer science, especially parallel computing, synchronization means the coordination of simultaneous threads or processes to complete a task in order to get correct runtime order and avoid unexpected race conditions. ... In parallel computing, a barrier is a type of synchronization method. ... In contrast to algorithms that protect access to shared data with locks, lock-free and wait-free algorithms are specially designed to allow multiple threads to read and write shared data concurrently without corrupting it. ...

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. Eventually, the overhead from communication dominates the time spent solving the problem, and further parallelization (that is, splitting the workload over even more threads) increases rather than decreases the amount of time required to finish. This is known as parallel slowdown. A diagram of the program runtime (shown in blue) and program speed-up (shown in red) of a real-world program with sub-optimal parallelization. ...

### 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 is embarrassingly parallel if they rarely or never have to communicate. Embarrassingly parallel applications are considered the easiest to parallelize. In the jargon of parallel computing, an embarrassingly parallel workload (or embarrassingly parallel problem) is one for which no particular effort is needed to segment the problem into a very large number of parallel tasks, and there is no essential dependency (or communication) between those parallel tasks. ...

### Consistency models

Main article: Consistency model
Leslie Lamport first defined the concept of sequential consistency. Lamport is also well-known for his work in creating the LaTeX typesetting software.

Parallel programming languages and parallel computers must have a consistency model (also known as a memory model). The consistency model defines rules for how operations on computer memory occur and how results are produced. In computer science, in a distributed system such as a distributed shared memory system or a distributed data store such as a database, filesystem, or web caching system, there are a number of possible data consistency models. ... Leslie Lamport Source: http://lamport. ... Leslie Lamport Source: http://lamport. ... Leslie Lamport Dr. Leslie Lamport (born 1941) is an American computer scientist. ... Sequential consistency is one of the consistency models used in the domain of the concurrent programming (e. ... This article is about the typesetting system. ... In computer science, in a distributed system such as a distributed shared memory system or a distributed data store such as a database, filesystem, or web caching system, there are a number of possible data consistency models. ... 1 GiB of SDRAM mounted in a personal computer. ...

One of the first consistency models was Leslie Lamport's sequential consistency model. Sequential consistency is the property of a parallel program that its parallel execution produces the same results as a sequential program. Specifically, a program is sequentially consistent if "... the results of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program".[14] Leslie Lamport Dr. Leslie Lamport (born 1941) is an American computer scientist. ... Sequential consistency is one of the consistency models used in the domain of the concurrent programming (e. ...

Software transactional memory is a common type of consistency model. Software transactional memory borrows from database theory the concept of atomic transactions and applies them to memory accesses. In computer science, software transactional memory (STM) is a concurrency control mechanism analogous to database transactions for controlling access to shared memory in concurrent computing. ... A database management system (DBMS) is computer software designed for the purpose of managing databases based on a variety of data models. ... For other uses, see Atomicity (disambiguation). ...

Mathematically, these models can be represented in several ways. Petri nets, which were introduced in Carl Adam Petri's 1962 doctoral thesis, were an early attempt to codify the rules of consistency models. Dataflow theory later built upon these, and Dataflow architectures were created to physically implement the ideas of dataflow theory. Beginning in the late 1970s, process calculi such as calculus of communicating systems and communicating sequential processes were developed to permit algebraic reasoning about systems composed of interacting components. More recent additions to the process calculus family, such as the π-calculus, have added the capability for reasoning about dynamic topologies. Logics such as Lamport's TLA+, and mathematical models such as traces and Actor event diagrams, have also been developed to describe the behavior of concurrent systems. A Petri net is a mathematical representation of discrete distributed systems. ... Dataflow architecture is a computer architecture that directly contrasts the traditional von Neuman or control flow architecture. ... The process calculi (or process algebras) are a diverse family of related approaches to formally modelling concurrent systems. ... The Calculus of Communicating Systems (or CCS) (one of the first process calculi) was developed by Robin Milner. ... In computer science, Communicating Sequential Processes (CSP) is a formal language for describing patterns of interaction in concurrent systems. ... In theoretical computer science, the Ï€-calculus is a notation originally developed by Robin Milner, Joachim Parrow and David Walker as an advance over Calculus of Communicating Systems in order to provide mobility in modeling concurrency. ... A logic developed by Leslie Lamport, which combines Temporal Logic with a logic of actions. ... In mathematics and computer science, trace theory aims to provide a concrete mathematical underpinning for the study of concurrent computation and process calculi. ... In theoretical computer science, Actor model theory concerns theoretical issues for the Actor model. ...

### 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, whether or not those instructions were using a single or multiple sets of data. Michael J. Flynn (born May 20, 1934 in New York City)[1] is an American professor emeritus at Stanford University. ... Flynns taxonomy is a classification of computer architectures, proposed by Michael J. Flynn in 1972. ...

Flynn's taxonomy
Single
Instruction
Multiple
Instruction
Single
Data
SISD MISD
Multiple
Data
SIMD MIMD
This box: view  talk  edit

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. Flynns taxonomy is a classification of computer architectures, proposed by Michael J. Flynn in 1972. ... SISD is an acronym for Single Instruction stream over a Single Data stream. ... Multiple Instruction Single Data (MISD) is a type of parallel computing architecture where many functional units perform different operations on the same data. ... -1... Multiple Instruction Multiple Data (MIMD) is a type of parallel computing architecture where many functional units perform different operations on different data. ... Signal processing is the processing, amplification and interpretation of signals, and deals with the analysis and manipulation of signals. ... In computer architecture, a systolic array is a pipe network arrangement of data processing units (DPUs (see figure, for instance, with 32 bit wide DPUs). ...

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."[15] David A. Patterson This article is about the American computer scientist. ... John LeRoy Hennessy, the founder of MIPS Computer Systems Inc. ...

## Types of parallelism

### Bit-level parallelism

Main article: Bit-level parallelism

From the advent of very-large-scale integration (VLSI) computer-chip fabrication technology in the 1970s until about 1986, speed-up in computer architecture was driven by doubling computer word size—the amount of information the processor can execute per cycle.[16] Increasing the word size reduces the number of instructions the processor must execute to perform an operation on variables whose sizes are greater than the length of the word. For example, where an 8-bit processor must add two 16-bit integers, the processor must first add the 8 lower-order bits from each integer using the standard addition instruction, then add the 8 higher-order bits using an add-with-carry instruction and the carry bit from the lower order addition; thus, an 8-bit processor requires two instructions to complete a single operation, where a 16-bit processor would be able to complete the operation with a single instruction. Bit-level parallelism is a form of parallel computing based on increasing processor word size. ... It has been suggested that VHSIC be merged into this article or section. ... In computing, word is a term for the natural unit of data used by a particular computer design. ... 8-bit refers to the number of bits used in the data bus of a computer. ... In computer science, 16-bit is an adjective used to describe integers that are at most two bytes wide, or to describe CPU architectures based on registers, address buses, or data buses of that size. ... Not to be confused with Natural number. ... In computer processors the carry flag (sometimes indicated as C flag) is a single bit in a system status (flag) register used to indicate when an arithmetic carry or borrow has been generated out of the most significant ALU bit position. ...

Historically, 4-bit microprocessors were replaced with 8-bit, then 16-bit, then 32-bit microprocessors. This trend generally came to an end with the introduction of 32-bit processors, which has been a standard in general-purpose computing for two decades. Not until recently (c. 2003–2004), with the advent of x86-64 architectures, have 64-bit processors become commonplace. In computer science, 4-bit is an adjective used to describe integers, memory addresses or other data units that are at most 4 bits wide, or to describe CPU and ALU architectures based on registers, address buses, or data buses of that size. ... The AMD64 or x86-64 is a 64-bit processor architecture invented by AMD. It is a superset of the x86 architecture, which it natively supports. ... In computing, a 64-bit component is one in which data are processed or stored in 64-bit units (words). ...

### Instruction-level parallelism

A canonical five-stage pipeline in a RISC machine (IF = Instruction Fetch, ID = Instruction Decode, EX = Execute, MEM = Memory access, WB = Register write back)

A computer program is, in essence, a stream of instructions executed by a processor. These instructions can be re-ordered and combined into groups which are then executed in parallel without changing the result of the program. This is known as instruction-level parallelism. Advances in instruction-level parallelism dominated computer architecture from the mid-1980s until the mid-1990s.[17] Instruction-level parallelism (ILP) is a measure of how many of the operations in a computer program can be dealt with at once. ... Image File history File links Download high resolution version (972x282, 7 KB) Title : Instruction scheduling using a 5 stages pipeline. ... Image File history File links Download high resolution version (972x282, 7 KB) Title : Instruction scheduling using a 5 stages pipeline. ... Reduced Instruction Set Computer (RISC), is a microprocessor CPU design philosophy that favors a smaller and simpler set of instructions that all take about the same amount of time to execute. ... In computer engineering, out-of-order execution, OoOE, is a paradigm used in most high-performance microprocessors in order to make use of cycles that would otherwise be wasted by a certain type of costly delay. ...

Modern processors have multi-stage instruction pipelines. Each stage in the pipeline corresponds to a different action the processor performs on that instruction in that stage; a processor with an N-stage pipeline can have up to N different instructions at different stages of completion. The canonical example of a pipelined processor is a RISC processor, with five stages: instruction fetch, decode, execute, memory access, and write back. The Pentium 4 processor had a 35-stage pipeline.[18] Basic five-stage pipeline in a RISC machine (IF = Instruction Fetch, ID = Instruction Decode, EX = Execute, MEM = Memory access, WB = Register write back) An instruction pipeline is a technique used in the design of computers and other digital electronic devices to increase their instruction throughput (the number of instructions that... The Pentium 4[1] brand refers to Intels single-core mainstream desktop and laptop CPUs introduced on November 20, 2000[2] (August 8, 2008 is the date of last shipments of Pentium 4s[3]). They had the 7th-generation architecture - called NetBurst - which was the companys first all...

A five-stage pipelined superscalar processor, capable of issuing two instructions per cycle. It can have two instructions in each stage of the pipeline, for a total of up to 10 instructions (shown in green) being simultaneously executed.

In addition to instruction-level parallelism from pipelining, some processors can issue more than one instruction at a time. These are known as superscalar processors. Instructions can be grouped together only if there is no data dependency between them. Scoreboarding and the Tomasulo algorithm (which is similar to scoreboarding but makes use of register renaming) are two of the most common techniques for implementing out-of-order execution and instruction-level parallelism. Image File history File links Download high resolution version (971x561, 11 KB) Title : Instruction scheduling on a 5 stages pipeline super scalar CPU (degree = 2). ... Image File history File links Download high resolution version (971x561, 11 KB) Title : Instruction scheduling on a 5 stages pipeline super scalar CPU (degree = 2). ... Simple superscalar pipeline. ... A data dependency in computer science is a situation whereby computer instructions refer to the results of preceding instructions that have not yet been completed. ... Scoreboarding is a centralized method of dynamically scheduling a pipeline so that the instructions can execute out of order when there are no conflicts and the hardware is available. ... The Tomasulo algorithm is an algorithm developed by Robert Tomasulo from IBM to execute instructions out of order. ... In computer engineering, register renaming refers to a technique used to avoid unnecessary serialization of program operations imposed by the reuse of registers by those operations. ...

### Data parallelism

Main article: Data parallelism

Data parallelism is parallelism inherent in program loops, which focuses on distributing the data across different computing nodes to be processed in parallel. "Parallelizing loops often leads to similar (not necessarily identical) operation sequences or functions being performed on elements of a large data structure."[19] Many scientific and engineering applications exhibit data parallelism. Data parallelism (also known as loop-level parallelism) is a form of parallelization of computing across multiple processors in parallel computing environments. ... In computer science control flow (or alternatively, flow of control) refers to the order in which the individual statements, instructions or function calls of an imperative or functional program are executed or evaluated. ...

A loop-carried dependency is the dependence of a loop iteration on the output of one or more previous iterations. Loop-carried dependencies prevent the parallelization of loops. For example, consider the following pseudocode that computes the first few Fibonacci numbers: Pseudocode (derived from pseudo and code) is a compact and informal high-level description of a computer programming algorithm that uses the structural conventions of some programming language, but typically omits details that are not essential for the understanding of the algorithm, such as subroutines, variable declarations and system-specific... A tiling with squares whose sides are successive Fibonacci numbers in length In mathematics, the Fibonacci numbers are a sequence of numbers named after Leonardo of Pisa, known as Fibonacci. ...

` 1: PREV2 := 0 2: PREV1 := 1 3: CUR := 1 4: do: 5: CUR := PREV1 + PREV2 6: PREV2 := PREV1 7: PREV1 := CUR 8: while (CUR < 10) `

This loop cannot be parallelized because CUR depends on itself (PREV1) and PREV2, which are computed in each loop iteration. Since each iteration depends on the result of the previous one, they cannot be performed in parallel. As the size of a problem gets bigger, the amount of data-parallelism available usually does as well.[20]

Main article: Task parallelism

Task parallelism is the characteristic of a parallel program that "entirely different calculations can be performed on either the same or different sets of data".[19] This contrasts with data parallelism, where the same calculation is performed on the same or different sets of data. Task parallelism does not usually scale with the size of a problem.[20] Task Parallelism is a form of parallelization of computer code. ...

## Hardware

### Memory and communication

Main memory in a parallel computer is either shared memory (shared between all processing elements in a single address space), or distributed memory (in which each processing element has its own local address space).[21] Distributed memory refers to the fact that the memory is logically distributed, but often implies that it is physically distributed as well. Distributed shared memory is a combination of the two approaches, where the processing element has its own local memory and access to the memory on non-local processors. Accesses to local memory are typically faster than accesses to non-local memory. // Diagram of a typical Shared memory system. ... In computing, an address space defines a range of discrete addresses, each of which may correspond to a physical or virtual memory register, a network host, peripheral device, disk sector or other logical or physical entity. ... Distributed memory is a concept used in parallel computing. ... Distributed Shared Memory (DSM), in computer science, refers to a wide class of software and hardware implementations, in which each node of a cluster has access to a large shared memory in addition to each nodes limited non-shared private memory. ...

A logical view of a Non-Uniform Memory Access (NUMA) architecture. Processors in one directory can access that directory's memory with less latency than they can access memory in the other directory's memory.

Computer architectures in which each element of main memory can be accessed with equal latency and bandwidth are known as Uniform Memory Access (UMA) systems. Typically, that can be achieved only by a shared memory system, in which the memory is not physically distributed. A system that does not have this property is known as a Non-Uniform Memory Access (NUMA) architecture. Distributed memory systems have non-uniform memory access. Image File history File links Numa. ... Image File history File links Numa. ... Non-Uniform Memory Access or Non-Uniform Memory Architecture (NUMA) is a computer memory design used in multiprocessors, where the memory access time depends on the memory location relative to a processor. ... In computing, memory latency is the time between initiating a request for a byte or word in memory until it is retrieved. ... For other uses, see Bandwidth. ... Uniform Memory Access is a computer memory architecture used in parallel computers having multiple processors and probably multiple memory chips. ... // Diagram of a typical Shared memory system. ... Non-Uniform Memory Access or Non-Uniform Memory Architecture (NUMA) is a computer memory design used in multiprocessors, where the memory access time depends on the memory location relative to a processor. ...

Computer systems make use of caches—small, fast memories located close to the processor which store temporary copies of memory values (nearby in both the physical and logical sense). Parallel computer systems have difficulties with caches that may store the same value in more than one location, with the possibility of incorrect program execution. These computers require a cache coherency system, which keeps track of cached values and strategically purges them, thus ensuring correct program execution. Bus snooping is one of the most common methods for keeping track of which values are being accessed (and thus should be purged). Designing large, high-performance cache coherence systems is a very difficult problem in computer architecture. As a result, shared-memory computer architectures do not scale as well as distributed memory systems do.[21] For other uses, see cache (disambiguation). ... Cache coherence refers to the integrity of data stored in local caches of a shared resource. ... Bus sniffing or Bus snooping is a technique used in distributed shared memory systems and multiprocessors aimed at achieving cache coherence. ...

Processor–processor and processor–memory communication can be implemented in hardware in several ways, including via shared (either multiported or multiplexed) memory, a crossbar switch, a shared bus or an interconnect network of a myriad of topologies including star, ring, tree, hypercube, fat hypercube (a hypercube with more than one processor at a node), or n-dimensional mesh. In telecommunications, multiplexing (also muxing or MUXing) is the combining of two or more information channels onto a common transmission medium using hardware called a multiplexer or (MUX). ... A crossbar switch is one of the principal architectures used to construct switches of many types. ... PCI Express bus card slots (from top to bottom: x4, x16, x1 and x16), compared to a traditional 32-bit PCI bus card slot (bottom). ... For other uses of topology, see topology (disambiguation). ... Bold text Star network layout Star networks are one of the most common computer network topologies. ... Image showing ring network layout A ring network is a network topology in which each node connects to exactly two other nodes, forming a circular pathway for signals: a ring. ... A labeled tree with 6 vertices and 5 edges In graph theory, a tree is a graph in which any two vertices are connected by exactly one path. ... The hypercube graph Q4. ... Image showing mesh network layout Mesh networking is a way to route data, voice and instructions between nodes. ...

Parallel computers based on interconnect networks need to have some kind of routing to enable the passing of messages between nodes that are not directly connected. The medium used for communication between the processors is likely to be hierarchical in large multiprocessor machines. This article is about routing in computer networks. ...

### Classes of parallel computers

Parallel computers can be roughly classified according to the level at which the hardware supports parallelism. This classification is broadly analogous to the distance between basic computing nodes. These are not mutually exclusive; for example, clusters of symmetric multiprocessors are relatively common.

#### Multicore computing

Main article: Multi-core (computing)

A multicore processor is a processor that includes multiple execution units ("cores"). These processors differ from superscalar processors, which can issue multiple instructions per cycle from one instruction stream (thread); by contrast, a multicore processor can issue multiple instructions per cycle from multiple instruction streams. Each core in a multicore processor can potentially be superscalar as well—that is, on every cycle, each core can issue multiple instructions from one instruction stream. Diagram of an Intel Core 2 dual core processor, with CPU-local Level 1 caches, and a shared, on-die Level 2 cache. ... In computer engineering, an execution unit is a part of a CPU that performs the operations and calculations called for by the program. ...

#### Symmetric multiprocessing

A symmetric multiprocessor (SMP) is a computer system with multiple identical processors that share memory and connect via a bus.[22] Bus contention prevents bus architectures from scaling. As a result, SMPs generally do not comprise more than 32 processors.[23] "Because of the small size of the processors and the significant reduction in the requirements for bus bandwidth achieved by large caches, such symmetric multiprocessors are extremely cost-effective, provided that a sufficient amount of memory bandwidth exists."[22] Symmetric multiprocessing, or SMP, is a multiprocessor computer architecture where two or more identical processors are connected to a single shared main memory. ... Bus contention is an undesirable state of the bus of a computer, in which more than one memory mapped device or the CPU is attempting to place output values onto the bus at once. ...

#### Distributed computing

Main article: Distributed computing

A distributed computer (also known as a distributed memory multiprocessor) is a distributed memory computer system in which the processing elements are connected by a network. Distributed computers are highly scalable. Distributed computing is a method of computer processing in which different parts of a program are run simultaneously on two or more computers that are communicating with each other over a network. ...

##### Cluster computing
Main article: Computer cluster

A cluster is a group of loosely coupled computers that work together closely, so that in some respects they can be regarded as a single computer.[24] Clusters are composed of multiple standalone machines connected by a network. While machines in a cluster do not have to be symmetric, load balancing is more difficult if they are not. The most common type of cluster is the Beowulf cluster, which is a cluster implemented on multiple identical commercial off-the-shelf computers connected with a TCP/IP Ethernet local area network.[25] Beowulf technology was originally developed by Thomas Sterling and Donald Becker. The vast majority of the TOP500 supercomputers are clusters.[26] An example of a Computer cluster A computer cluster is a group of tightly coupled computers that work together closely so that in many respects they can be viewed as though they are a single computer. ... Download high resolution version (500x667, 249 KB)Picture of a Beowulf Cluster. ... Download high resolution version (500x667, 249 KB)Picture of a Beowulf Cluster. ... The Borg, a 52-node Beowulf cluster used by the McGill University pulsar group to search for pulsations from binary pulsars. ... In computer networking, load balancing is a technique (usually performed by load balancers) to spread work between many computers, processes, hard disks or other resources in order to get optimal resource utilization and decrease computing time. ... The Borg, a 52-node Beowulf cluster used by the McGill University pulsar group to search for pulsations from binary pulsars. ... Commercial off-the-shelf (COTS) is a term for software or hardware products that are ready-made and available for sale to the general public. ... The Internet protocol suite is the set of communications protocols that implement the protocol stack on which the Internet runs. ... Ethernet is a large, diverse family of frame-based computer networking technologies that operate at many speeds for local area networks (LANs). ... LAN redirects here. ... Thomas Sterling is an internationally recognized supercomputing expert who is considered the father of Beowulf Clusters along with Donald Becker. ... Donald Becker is a notable developer well known for writing many of the Ethernet drivers for the Linux operating system. ... The TOP500 project ranks and details the 500 most powerful publicly-known computer systems in the world. ...

##### Massive parallel processing
Main article: Massive parallel processing

A massively parallel processor (MPP) is a single computer with many networked processors. MPPs have many of the same characteristics as clusters, but they are usually larger, typically having "far more" than 100 processors.[27] In an MPP, "each CPU contains its own memory and copy of the operating system and application. Each subsystem communicates with the others via a high-speed interconnect."[28] Massive parallel processing (MPP) is a term used in computer architecture to refer to a computer system with many independent arithmetic units or entire microprocessors, that run in parallel. ...

A cabinet from Blue Gene/L, ranked as the second fastest supercomputer in the world according to the 6/2008 TOP500 rankings. Blue Gene/L is a massively parallel processor.

Blue Gene/L, the second fastest supercomputer in the world according to the TOP500 ranking, is an MPP. Image File history File linksMetadata Download high-resolution version (1244x1906, 1804 KB) A BlueGene/L rack. ... Image File history File linksMetadata Download high-resolution version (1244x1906, 1804 KB) A BlueGene/L rack. ... This article is about the supercomputer. ... The TOP500 project ranks and details the 500 most powerful publicly-known computer systems in the world. ... Blue Gene/L Blue Gene is computer architecture project designed to produce several next generation super computers, operating in the PFLOPS range. ...

##### Grid computing
Main article: Grid computing

Grid computing is the most distributed form of parallel computing. It makes use of computers communicating over the Internet to work on a given problem. Because of the low bandwidth and extremely high latency available on the Internet, grid computing typically deals only with embarrassingly parallel problems. Many grid computing applications have been created, of which SETI@home and Folding@Home are the best-known examples.[29] Grid computing is a phrase in distributed computing which can have several meanings: Multiple independent computing clusters which act like a grid because they are composed of resource nodes not located within a single administrative domain. ... A list of distributed computing projects. ... SETI@home logo SETI@home (SETI at home) is a distributed computing project using Internet-connected computers, hosted by the Space Sciences Laboratory, at the University of California, Berkeley, in the United States. ... Folding@Home (also known as FAH or F@H) is a distributed computing project designed to perform computationally intensive simulations of protein folding and other molecular dynamics. ...

Most grid computing applications use middleware, software that sits between the operating system and the application to manage network resources and standardize the software interface. The most common grid computing middleware is the Berkeley Open Infrastructure for Network Computing (BOINC). Often, grid computing software makes use of "spare cycles", performing computations at times when a computer is idling. This article is about integration software. ... The Berkeley Open Infrastructure for Network Computing (BOINC) is a non-commercial middleware system for volunteer computing, originally developed to support the SETI@home project, but intended to be useful for other applications in areas as diverse as mathematics, medicine, molecular biology, climatology, and astrophysics. ...

#### Specialized parallel computers

Within parallel computing, there are specialized parallel devices that remain niche areas of interest. While not domain-specific, they tend to be applicable to only a few classes of parallel problems. A domain-specific programming language (domain-specific language, DSL) is a programming language designed to be useful for a specific set of tasks. ...

Reconfigurable computing with field-programmable gate arrays

Reconfigurable computing is the use of a field-programmable gate array (FPGA) as a co-processor to a general-purpose computer. An FPGA is, in essence, a computer chip that can rewire itself for a given task. Reconfigurable computing is computer processing with highly flexible computing fabrics. ... An Altera Stratix II GX FPGA. A field-programmable gate array is a semiconductor device containing programmable logic components called logic blocks, and programmable interconnects. ...

FPGAs can be programmed with hardware description languages such as VHDL or Verilog. However, programming in these languages can be tedious. Several vendors have created C to HDL languages that attempt to emulate the syntax and/or semantics of the C programming language, with which most programmers are familiar. The best known C to HDL languages are Mitrion-C, Impulse C, DIME-C, and Handel-C. In electronics, a hardware description language or HDL is any language from a class of computer languages for formal description of electronic circuits. ... VHDL, or VHSIC Hardware Description Language, is commonly used as a design-entry language for field-programmable gate arrays and application-specific integrated circuits in electronic design automation of digital circuits. ... Verilog is a hardware description language (HDL) used to model electronic systems. ... This page is to describe tools and methods that convert C or C like languages into hardware description languages like VHDL or Verilog. ... Wikibooks has a book on the topic of C Programming The C programming language (often, just C) is a general-purpose, procedural, imperative computer programming language developed in the early 1970s by Dennis Ritchie for use on the Unix operating system. ... Impulse C is a subset of the C language combined with a C-compatible function library supporting parallel programming, in particular for programming of applications targeting FPGA devices. ... DIME-C is a C to HDL tool developed by Nallatech it is part of their DIMEtalk Design Tools suite. ... Handel-C is a programming language and Hardware Description Language (HDL) for compiling programs into hardware images of FPGAs or ASICs. ...

AMD's decision to open its HyperTransport technology to third-party vendors has become the enabling technology for high-performance reconfigurable computing.[30] According to Michael R. D'Amour, CEO of DRC Computer Corporation, "when we first walked into AMD, they called us 'the socket stealers.' Now they call us their partners."[30] HyperTransport logo HyperTransport (HT), formerly known as Lightning Data Transport (LDT), is a bidirectional serial/parallel high-bandwidth, low-latency point to point link that was introduced on April 2, 2001. ... The Socket 370 processor socket, a ZIF type PGA socket A CPU socket or CPU slot is a connector on a computers motherboard that accepts a CPU and forms an electrical interface with it. ...

GPGPU with graphics processing units
Main article: GPGPU

General-purpose computing on graphics processing units (GPGPU) is a fairly recent trend in computer engineering research. GPUs are co-processors that have been heavily optimized for computer graphics processing.[31] Computer graphics processing is a field dominated by data parallel operations—particularly linear algebra matrix operations. General-purpose computing on graphics processing units (GPGPU, also referred to as GPGP and to a lesser extent GPÂ²) is a recent trend focused on using GPUs to perform computations rather than the CPU. The addition of programmable stages and higher precision arithmetic to the rendering pipelines allowed software developers... Image File history File links Metadata Size of this preview: 800 Ã— 274 pixelsFull resolutionâ€Ž (1,948 Ã— 666 pixels, file size: 904 KB, MIME type: image/jpeg) File historyClick on a date/time to view the file as it appeared at that time. ... Image File history File links Metadata Size of this preview: 800 Ã— 274 pixelsFull resolutionâ€Ž (1,948 Ã— 666 pixels, file size: 904 KB, MIME type: image/jpeg) File historyClick on a date/time to view the file as it appeared at that time. ... The Tesla GPU is NVIDIAs third brand of GPUs. ... GPU redirects here. ... This article is about the scientific discipline of computer graphics. ... Linear algebra is the branch of mathematics concerned with the study of vectors, vector spaces (also called linear spaces), linear maps (also called linear transformations), and systems of linear equations. ... In mathematics, a matrix (plural matrices) is a rectangular table of elements (or entries), which may be numbers or, more generally, any abstract quantities that can be added and multiplied. ...

In the early days, GPGPU programs used the normal graphics APIs for executing programs. However, recently several new programming languages and platforms have been built to do general purpose computation on GPUs with both Nvidia and AMD releasing programming environments with CUDA and CTM respectively. Other GPU programming languages are BrookGPU, PeakStream, and RapidMind. Nvidia has also released specific products for computation in their Tesla series. The American multinational Nvidia Corporation (NASDAQ: NVDA) (pronounced ) specializes in the manufacture of graphics-processor technologies for workstations, desktop computers, and handheld devices. ... Advanced Micro Devices, Inc. ... This article does not cite any references or sources. ... This articles Limitations section does not cite any references or sources. ... BrookGPU is the Stanford University Graphics groups compiler and runtime implementation of the Brook stream programming language for using modern graphics hardware for non-graphical, or general purpose computations. ... It has been suggested that this article or section be merged with stream processing. ... It has been suggested that this article or section be merged with stream processing. ... The Tesla GPU is NVIDIAs third brand of GPUs. ...

Application-specific integrated circuits
Main article: Application-specific integrated circuit

Several Application-specific integrated circuit (ASIC) approaches have been devised for dealing with parallel applications.[32][33][34] This article does not cite any references or sources. ... This article does not cite any references or sources. ...

Because an ASIC is (by definition) specific to a given application, it can be fully optimized for that application. As a result, for a given application, an ASIC tends to outperform a general-purpose computer. However, ASICs are created by X-ray lithography. This process requires a mask, which can be extremely expensive. A single mask can cost over a million US dollars.[35] (The smaller the transistors required for the chip, the more expensive the mask will be.) Meanwhile, performance increases in general-purpose computing over time (as described by Moore's Law) tend to wipe out these gains in only one or two chip generations.[30] High initial cost, and the tendency to be overtaken by Moore's-law-driven general-purpose computing, has rendered ASICs unfeasible for most parallel computing applications. However, some have been built. One example is the peta-flop RIKEN MDGRAPE-3 machine which uses custom ASICs for molecular dynamics simulation. This article does not cite its references or sources. ... The RIKEN MDGRAPE-3 supercomputer For the astronomical supercomputer also known as GRAPE, see Gravity Pipe. ... Molecular dynamics (MD) is a form of computer simulation wherein atoms and molecules are allowed to interact for a period of time under known laws of physics, giving a view of the motion of the atoms. ...

Vector processors
Main article: Vector processor
The Cray-1 is the most famous vector processor.

A vector processor is a CPU or computer system that can execute the same instruction on large sets of data. "Vector processors have high-level operations that work on linear arrays of numbers or vectors. An example vector operation is $A = B times C$ where A, B, and C are each 64-element vectors of 64-bit floating-point numbers."[36] They are closely related to Flynn's SIMD classification.[36] Processor board of a CRAY YMP vector computer A vector processor, or array processor, is a CPU design that is able to run mathematical operations on multiple data elements simultaneously. ... Image File history File links Download high resolution version (2560x1920, 862 KB) CRAY-1 Work by Rama File links The following pages link to this file: Cray-1 ... Image File history File links Download high resolution version (2560x1920, 862 KB) CRAY-1 Work by Rama File links The following pages link to this file: Cray-1 ... CRAY-1 at the EPFL in Switzerland. ... A floating-point number is a digital representation for a number in a certain subset of the rational numbers, and is often used to approximate an arbitrary real number on a computer. ...

Cray computers became famous for their vector-processing computers in the 1970s and 1980s. However, vector processors—both as CPUs and as full computer systems—have generally disappeared. Modern processor instruction sets do include some vector processing instructions, such as with AltiVec and Streaming SIMD Extensions (SSE). For other uses, see Cray (disambiguation). ... An instruction set is [a list of] all the instructions, and all their variations, that a processor can execute. ... AltiVec is a floating point and integer SIMD instruction set designed and owned by Apple Computer, IBM and Motorola (the AIM alliance), and implemented on versions of the PowerPC including Motorolas G4 and IBMs G5 processors. ... SSE (Streaming SIMD Extensions, originally called ISSE, Internet Streaming SIMD Extensions) is a SIMD (Single Instruction, Multiple Data) instruction set designed by Intel and introduced in 1999 in their Pentium III series processors as a reply to AMDs 3DNow! (which had debuted a year earlier). ...

## Software

### Parallel programming languages

Concurrent programming languages, libraries, APIs, and parallel programming models have been created for programming parallel computers. These can generally be divided into classes based on the assumptions they make about the underlying memory architecture—shared memory, distributed memory, or shared distributed memory. Shared memory programming languages communicate by manipulating shared memory variables. Distributed memory uses message passing. POSIX Threads and OpenMP are two of most widely used shared memory APIs, whereas Message Passing Interface (MPI) is the most widely used message-passing system API. One concept used in programming parallel programs is the future concept, where one part of a program promises to deliver a required datum to another part of a program at some future time. A parallel programming model is a set of software technologies to express parallel algorithms and match applications with the underlying parallel systems. ... Illustration of an application which may use libvorbisfile. ... API redirects here. ... A parallel programming model is a set of software technologies to express parallel algorithms and match applications with the underlying parallel systems. ... In computer science, message passing is a form of communication used in concurrent programming, parallel programming, object-oriented programming, and interprocess communication. ... POSIX Threads is a POSIX standard for threads. ... OpenMP logo The OpenMP (Open Multi-Processing) is an application programming interface (API) that supports multi-platform shared memory multiprocessing programming in C/C++ and Fortran on many architectures, including Unix and Microsoft Windows platforms. ... Message Passing Interface (MPI) is both a computer specification and is an implementation that allows many computers to communicate with one another. ... In computer science, futures and promises are closely related constructs used for synchronization in some concurrent programming languages. ...

### Automatic parallelization

Automatic parallelization of a sequential program by a compiler is the "holy grail" of parallel computing. Despite decades of work by compiler researchers, automatic parallelization has had only limited success.[37] Automatic parallelization (also known as auto parallelization or Autoparallelization), refers to the use of a modern optimizing parallelizing compiler to convert sequential code into multi-threaded or vectorized (or even both) code in order to utilize multiple processors simultaneously in a shared-memory multiprocessor (SMP) machine. ... This article is about the computing term. ... For other uses, see Holy Grail (disambiguation). ...

Mainstream parallel programming languages remain either explicitly parallel or (at best) partially implicit, in which a programmer gives the compiler directives for parallelization. A few fully implicit parallel programming languages exist—SISAL, Parallel Haskell, and (for FPGAs) Mitrion-C—but these are niche languages that are not widely used.[citation needed] In computer programming, explicit parallelism is the representation of concurrent computations by means of primitives in the form of special-purpose directives or function calls. ... In computer science, implicit parallelism is a characteristic of a programming language that allows a compiler to automatically exploit the parallelism inherent to the computations expressed by some of the languages constructs. ... A directive is an instruction to a programming language compiler about how to compile a program. ... Binomial name Agave sisalana Perrine Sisal or sisal hemp is an agave Agave sisalana that yields a stiff fiber used in making rope. ... Haskell is a standardized purely functional programming language with non-strict semantics, named after the logician Haskell Curry. ...

### Application checkpointing

The larger and more complex a computer, the more that can go wrong and the shorter the mean time between failures. Application checkpointing is a technique whereby the computer system takes a "snapshot" of the application—a record of all current resource allocations and variable states, akin to a core dump; this information can be used to restore the program if the computer should fail. Application checkpointing means that the program has to restart from only its last checkpoint rather than the beginning. For an application that may run for months, that is critical. Application checkpointing may be used to facilitate process migration. To quote Matt Dillon (of DragonFly BSD), Checkpointing allows you to freeze a copy of an application so that, in theory, you can restore the program to that running state at a later point in time. ... Mean time between failures (MTBF) is the mean (average) time between failures of a system, the reciprocal of the failure rate in the special case when the failure rate is constant. ... To quote Matt Dillon (of DragonFly BSD), Checkpointing allows you to freeze a copy of an application so that, in theory, you can restore the program to that running state at a later point in time. ... A core dump is the recorded state of the working memory of a computer program at a specific time, generally when the program has terminated abnormally (crashed). ... Process migration is when processes in computer clusters are able to move from machine to machine. ...

## Applications

As parallel computers become larger and faster, it becomes feasible to solve problems that previously took too long to run. Parallel computing is used in a wide range of fields, from bioinformatics (to do protein folding) to economics (to do simulation in mathematical finance). Common types of problems found in parallel computing applications are[38]: Map of the human X chromosome (from the NCBI website). ... Protein before and after folding. ... Mathematical finance is the branch of applied mathematics concerned with the financial markets. ...

Linear algebra is the branch of mathematics concerned with the study of vectors, vector spaces (also called linear spaces), linear maps (also called linear transformations), and systems of linear equations. ... The Cooley-Tukey algorithm, named after J.W. Cooley and John Tukey, is the most common fast Fourier transform (FFT) algorithm. ... The n-body problem is the problem of finding, given the initial positions, masses, and velocities of n bodies, their subsequent motions as determined by classical mechanics, i. ... The Barnes-Hut simulation is an algorithm for performing an N-body simulation. ... Example of regular grid. ... Lattice Boltzmann methods or LBM are CFD methods for fluid simulation. ... Example of unstructured grid for a finite element analysis mesh. ... Visualization of how a car deforms in an asymmetrical crash using finite element analysis. ... The Monte Carlo method can be illustrated as a game of battleship. ... This article is not about combinatory logic, a topic in mathematical logic. ... The EFFs US\$250,000 DES cracking machine contained over 1,800 custom chips and could brute force a DES key in a matter of days â€” the photograph shows a DES Cracker circuit board fitted with several Deep Crack chips. ... Graph traversal refers to the problem of visiting all the nodes in a graph in a particular manner. ... In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. ... In mathematics and computer science, dynamic programming is a method of solving problems exhibiting the properties of overlapping subproblems and optimal substructure (described below) that takes much less time than naive methods. ... Branch and bound is a general algorithmic method for finding optimal solutions of various optimization problems, especially in discrete and combinatorial optimization. ... In probability theory and statistics, a graphical model (GM) represents dependencies among random variables by a graph in which each random variable is a node. ... State transitions in a hidden Markov model (example) x â€” hidden states y â€” observable outputs a â€” transition probabilities b â€” output probabilities A hidden Markov model (HMM) is a statistical model in which the system being modeled is assumed to be a Markov process with unknown parameters, and the challenge is to... A Bayesian network (or a belief network) is a probabilistic graphical model that represents a set of variables and their probabilistic independencies. ... State machine redirects here. ...

## History

Main article: History of computing
ILLIAC IV, "perhaps the most infamous of Supercomputers"

The origins of true (MIMD) parallelism go back to Federico Luigi, Conte Menabrea and his "Sketch of the Analytic Engine Invented by Charles Babbage."[39][40] IBM introduced the 704 in 1954, through a project in which Gene Amdahl was one of the principal architects. It became the first commercially available computer to use fully automatic floating point arithmetic commands.[41] In 1958, IBM researchers John Cocke and Daniel Slotnick discussed the use of parallelism in numerical calculations for the first time.[42] Burroughs Corporation introduced the D825 in 1962, a four-processor computer that accessed up to 16 memory modules through a crossbar switch.[43] In 1967, Amdahl and Slotnick published a debate about the feasibility of parallel processing at American Federation of Information Processing Societies Conference.[42] It was during this debate that Amdahl's Law was coined to define the limit of speed-up due to parallelism. The history of computing is longer than the history of computing hardware and modern computing technology and includes the history of methods intended for pen and paper or for chalk and slate, with or without the aid of tables. ... Image File history File links Metadata Size of this preview: 747 Ã— 599 pixelsFull resolutionâ€Ž (2,393 Ã— 1,920 pixels, file size: 2. ... Image File history File links Metadata Size of this preview: 747 Ã— 599 pixelsFull resolutionâ€Ž (2,393 Ã— 1,920 pixels, file size: 2. ... The ILLIAC IV was one of the most infamous supercomputers ever, destined to be the last in a series of research machines from the University of Illinois. ... Federico Luigi, Conte Menabrea, Marquis of Valdora (September 4, 1809 - May 24, 1896), Italian general and statesman, was born at Chambry. ... The analytical engine, an important step in the history of computers, was the design of a mechanical general-purpose computer by the British mathematician Charles Babbage. ... Babbage redirects here. ... For other uses, see IBM (disambiguation) and Big Blue. ... Gene Amdahl addressing a UW-Madison Alumni gathering, March 13 2008. ... A floating-point number is a digital representation for a number in a certain subset of the rational numbers, and is often used to approximate an arbitrary real number on a computer. ... John Cocke (May 30, 1925 - July 16, 2002) was an American computer scientist recognised for his large contribution to computer architecture and optimizing compiler design. ... William Seward Burroughs (1857-1898), US inventor William S. Burroughs (1914-1997), author and grandson of William Seward Burroughs Edgar Rice Burroughs (1875-1950), American author of Tarzan fame The Burroughs Corporation began in 1886 as the American Arithmometer Company in St. ... A crossbar switch is one of the principal architectures used to construct switches of many types. ...

In 1969, US company Honeywell introduced its first Multics system, a symmetric multiprocessor system capable of running up to eight processors in parallel.[42] C.mmp, a 1970s multi-processor project at Carnegie Mellon University, was "among the first multiprocessors with more than a few processors".[40] "The first bus-connected multi-processor with snooping caches was the Synapse N+1 in 1984."[40] Honeywell Heating Specialties Company Stock Certificate dated 1924 signed by Mark C. Honeywell - courtesy of Scripophily. ... The C.mmp was an early multiprocessor system developed at Carnegie_Mellon_University by W.A.Wulf (1971). ... Carnegie Mellon University (also known as CMU) is a private research university in Pittsburgh, Pennsylvania, United States. ...

SIMD parallel computers can be traced back to the 1970s. The motivation behind early SIMD computers was to amortize the gate delay of the processor's control unit over multiple instructions.[44] In 1964, Slotnick had proposed building a massively parallel computer for the Lawrence Livermore National Laboratory.[42] His design was funded by the US Air Force, which was the earliest SIMD parallel-computing effort, ILLIAC IV.[42] The key to its design was a fairly high parallelism, with up to 256 processors, which allowed the machine to work on large datasets in what would later be known as vector processing. However, ILLIAC IV was called "the most infamous of Supercomputers", because the project was only one fourth completed, but took 11 years and cost almost four times the original estimate.[45] When it was finally ready to run its first real application in 1976, it was outperformed by existing commercial supercomputers such as the Cray-1. In computer science, the propogation delay is the amount of time starting from when the input to a logic gate becomes stable and valid to the time that the output of that logic gate is stable and valid. ... A control unit is the part of a CPU or other device that directs its operation. ... Aerial view of the lab and surrounding area, facing NW. The Lawrence Livermore National Laboratory (LLNL) in Livermore, California is a United States Department of Energy (DOE) national laboratory, managed and operated by Lawrence Livermore National Security, LLC (LLNS), a limited liability consortium comprised of Bechtel National, the University of... Seal of the Air Force. ... The ILLIAC IV was one of the most infamous supercomputers ever, destined to be the last in a series of research machines from the University of Illinois. ... Processor board of a CRAY YMP vector computer A vector processor, or array processor, is a CPU design that is able to run mathematical operations on multiple data elements simultaneously. ... CRAY-1 at the EPFL in Switzerland. ...

## References

1. ^ G.S. Almasi and A. Gottlieb. Highly Parallel Computing. Benjamin-Cummings publishers, Redwood city, CA, 1989.
2. ^ Krste Asanovic et al. The Landscape of Parallel Computing Research: A View from Berkeley (PDF). University of California, Berkeley. Technical Report No. UCB/EECS-2006-183. December 18, 2006: "Old [conventional wisdom]: Increasing clock frequency is the primary method of improving processor performance. New [conventional wisdom]: Increasing parallelism is the primary method of improving processor performance ... Even representatives from Intel, a company generally associated with the 'higher clock-speed is better' position, warned that traditional approaches to maximizing performance through maximizing clock speed have been pushed to their limit."
3. ^ Asanovic et al. Old [conventional wisdom]: Power is free, but transistors are expensive. New [conventional wisdom] is [that] power is expensive, but transistors are "free".
4. ^ David A. Patterson and John L. Hennessy. Computer Organization and Design (Second Edition) Morgan Kaufmann Publishers, 1998. ISBN 1558604286, p. 715.
5. ^ a b Blaise Barney. "Introduction to Parallel Computing". Lawrence Livermore National Laboratory. Retrieved on 2007-11-09.
6. ^ John L. Hennessy and David A. Patterson. Computer Architecture: A Quantitative Approach. 3rd edition, 2002. Morgan Kaufmann, ISBN 1558607242, p. 43.
7. ^ J.M. Rabaey. Digital Integrated Circuits. Prentice Hall, 1996. ISBN 0131786091, p. 235.
8. ^ Laurie J. Flynn. Intel Halts Development of 2 New Microprocessors. The New York Times, May 8, 2004. Retrieved on April 22, 2008.
9. ^ G. Amdahl. The validity of the single processor approach to achieving large-scale computing capabilities. In Proceedings of AFIPS Spring Joint Computer Conference, pp. 483–85, Atlantic City, N.J., April 1967. AFIPS Press.
10. ^ The Mythical Man-Month: Essays on Software Engineering. Frederick P. Brooks Jr.. Chapter 2 - The Mythical Man Month. ISBN 0201835959
11. ^ Reevaluating Amdahl's Law Communications of the ACM 31(5), 1988. pp. 532–33.
12. ^ A.J. Bernstein, "Program Analysis for Parallel Processing,' IEEE Trans. on Electronic Computers, EC-15, October 1966, pp. 757–62.
13. ^ Roosta, Seyed H. Parallel processing and parallel algorithms: theory and computation. 2000. Springer, ISBN 0387987169, p. 114.
14. ^ Leslie Lamport. "How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs", IEEE Transactions on Computers, C-28,9 (September 1979), pp. 690–91.
15. ^ Patterson and Hennessy, p. 748.
16. ^ David E. Culler, Jaswinder Pal Singh, Anoop Gupta. Parallel Computer Architecture - A Hardware/Software Approach. Morgan Kaufmann Publishers, 1999. ISBN 1558603433, p. 15.
17. ^ Culler et al. p. 15.
18. ^ Yale Patt. "The Microprocessor Ten Years From Now: What Are The Challenges, How Do We Meet Them? (wmv). Distinguished Lecturer talk at Carnegie Mellon University, April 2004. Retrieved on November 7, 2007.
19. ^ a b Culler et al. p. 124.
20. ^ a b Culler et al. p. 125.
21. ^ a b Patterson and Hennessy, p. 713.
22. ^ a b Hennessy and Patterson, p. 549.
23. ^ Patterson and Hennessy, p. 714.
24. ^ What is clustering? Webopedia computer dictionary. Retrieved on November 7, 2007.
25. ^ Beowulf definition. PC Magazine. Retrieved on November 7, 2007.
26. ^ Architecture share for 06/2007. TOP500 Supercomputing Sites. Clusters make up 74.60% of the machines on the list. Retrieved on November 7, 2007.
27. ^ Hennessy and Patterson, p. 537.
28. ^ MPP Definition. PC Magazine. Retrieved on November 7, 2007.
29. ^ Computer Science: Rough Times Ahead. Scott Kirkpatrick, January 31, 2003. Science, Vol. 299. no. 5607, pp. 668 - 669. DOI: 10.1126/science.1081623
30. ^ a b c Michael R. D'Amour, CEO DRC Computer Corporation. "Standard Reconfigurable Computing". Invited speaker at the University of Delaware, February 28, 2007.
31. ^ Sha'Kia Boggan and Daniel M. Pressel. GPUs: An Emerging Platform for General-Purpose Computation (PDF). ARL-SR-154, U.S. Army Research Lab. August 2007. Retrieved on November 7, 2007.
32. ^ Oleg Maslennikov (2002). Systematic Generation of Executing Programs for Processor Elements in Parallel ASIC or FPGA-Based Systems and Their Transformation into VHDL-Descriptions of Processor Element Control Units. Lecture Notes in Computer Science, 2328/2002: p. 272.
33. ^ Y. Shimokawa, Y. Fuwa, N. Aramaki. A parallel ASIC VLSI neurocomputer for a large number of neurons and billion connections per second speed. IEEE International Joint Conference on Neural Networks, 18–21 November 1991. 3: pp. 2162–67.
34. ^ K.P. Acken, M.J. Irwin, R.M. Owens. A Parallel ASIC Architecture for Efficient Fractal Image Coding. The Journal of VLSI Signal Processing, July 1998, 19(2):97–113(17)
35. ^ Andrew B. Kahng. "Scoping the Problem of DFM in the Semiconductor Industry." University of California, San Diego. June 21, 2004: "Future design for manufacturing (DFM) technology must reduce design [non-recoverable expenditure] cost and directly address manufacturing [non-recoverable expenditures] – the cost of a mask set and probe card – which is well over \$1 million at the 90 nm technology node and creates a significant damper on semiconductor-based innovation."
36. ^ a b Patterson and Hennessy, p. 751.
37. ^ Modern Processor Design: Fundamentals of Superscalar Processors. John Paul Shen, Mikko H. Lipasti. McGraw-Hill Professional, 2005. ISBN 0070570647. pp. 561: "However, the holy grail of such research - automated parallelization of serial programs - has yet to materialize. While automated parallelization of certain classes of algorithms has been demonstrated, such success has largely been limited to scientific and numeric applications with predictable flow control (e.g., nested loop structures with statically determined iteration counts) and statically analyzable memory access patterns. (e.g., walks over large multidimensional arrays of float-point data)."
38. ^ Krste Asanovic et al. The Landscape of Parallel Computing Research: A View from Berkeley (PDF). University of California, Berkeley. Technical Report No. UCB/EECS-2006-183. December 18, 2006. See table on pages 17-19
39. ^ L.F. Menabrea, Sketch of the Analytic Engine Invented by Charles Babbage. Bibliothèque Universelle de Genève, 1842. Retrieved on November 7, 2007.
40. ^ a b c Patterson and Hennessy, p. 753.
41. ^ Frank da Cruz (2003). "Columbia University Computing History: The IBM 704". Columbia University. Retrieved on 2008-01-08.
42. ^ a b c d e Wilson, Gregory V. (1994). "The History of the Development of Parallel Computing". Virginia Tech/Norfolk State University, Interactive Learning with a Digital Library in Computer Science. Retrieved on 2008-01-08.
43. ^ Gary Anthes (2001-11-19). "The Power of Parallelism". Computerworld. Retrieved on 2008-01-08.
44. ^ Patterson and Hennessy, p. 749.
45. ^ Patterson and Hennessy, pp. 749–50: "Although successful in pushing several technologies useful in later projects, the ILLIAC IV failed as a computer. Costs escalated from the \$8 million estimated in 1966 to \$31 million by 1972, despite the construction of only a quarter of the planned machine ... It was perhaps the most infamous of supercomputers. The project started in 1965 and ran its first real application in 1976."

is the 352nd day of the year (353rd in leap years) in the Gregorian calendar. ... Year 2006 (MMVI) was a common year starting on Sunday of the Gregorian calendar. ... David A. Patterson This article is about the American computer scientist. ... John LeRoy Hennessy, the founder of MIPS Computer Systems Inc. ... Year 2007 (MMVII) was a common year starting on Monday of the Gregorian calendar in the 21st century. ... is the 313th day of the year (314th in leap years) in the Gregorian calendar. ... John LeRoy Hennessy, the founder of MIPS Computer Systems Inc. ... David A. Patterson This article is about the American computer scientist. ... is the 128th day of the year (129th in leap years) in the Gregorian calendar. ... Year 2004 (MMIV) was a leap year starting on Thursday of the Gregorian calendar. ... is the 112th day of the year (113th in leap years) in the Gregorian calendar. ... 2008 (MMVIII) is the current year, a leap year that started on Tuesday of the Common Era (or Anno Domini), in accordance with the Gregorian calendar. ... Book cover The Mythical Man-Month: Essays on Software Engineering is a book on software project management by Fred Brooks, whose central theme is that Adding manpower to a late software project makes it later. ... Frederick Phillips Brooks, Jr. ... Communications of the ACM (CACM) is the flagship monthly magazine of the Association for Computing Machinery. ... Yale N. Patt is an American professor of electrical and computer engineering at The University of Texas at Austin. ... Carnegie Mellon University (also known as CMU) is a private research university in Pittsburgh, Pennsylvania, United States. ... November 7 is the 311th day of the year (312th in leap years) in the Gregorian calendar. ... Year 2007 (MMVII) was a common year starting on Monday of the Gregorian calendar in the 21st century. ... November 7 is the 311th day of the year (312th in leap years) in the Gregorian calendar. ... Year 2007 (MMVII) was a common year starting on Monday of the Gregorian calendar in the 21st century. ... November 7 is the 311th day of the year (312th in leap years) in the Gregorian calendar. ... Year 2007 (MMVII) was a common year starting on Monday of the Gregorian calendar in the 21st century. ... November 7 is the 311th day of the year (312th in leap years) in the Gregorian calendar. ... Year 2007 (MMVII) was a common year starting on Monday of the Gregorian calendar in the 21st century. ... November 7 is the 311th day of the year (312th in leap years) in the Gregorian calendar. ... Year 2007 (MMVII) was a common year starting on Monday of the Gregorian calendar in the 21st century. ... is the 59th day of the year in the Gregorian calendar. ... Year 2007 (MMVII) was a common year starting on Monday of the Gregorian calendar in the 21st century. ... November 7 is the 311th day of the year (312th in leap years) in the Gregorian calendar. ... Year 2007 (MMVII) was a common year starting on Monday of the Gregorian calendar in the 21st century. ... is the 172nd day of the year (173rd in leap years) in the Gregorian calendar. ... Year 2004 (MMIV) was a leap year starting on Thursday of the Gregorian calendar. ... is the 352nd day of the year (353rd in leap years) in the Gregorian calendar. ... Year 2006 (MMVI) was a common year starting on Sunday of the Gregorian calendar. ... Federico Luigi, Conte Menabrea, Marquis of Valdora (September 4, 1809 - May 24, 1896), Italian general and statesman, was born at Chambry. ... November 7 is the 311th day of the year (312th in leap years) in the Gregorian calendar. ... Year 2007 (MMVII) was a common year starting on Monday of the Gregorian calendar in the 21st century. ... 2008 (MMVIII) is the current year, a leap year that started on Tuesday of the Common Era (or Anno Domini), in accordance with the Gregorian calendar. ... is the 8th day of the year in the Gregorian calendar. ... 2008 (MMVIII) is the current year, a leap year that started on Tuesday of the Common Era (or Anno Domini), in accordance with the Gregorian calendar. ... is the 8th day of the year in the Gregorian calendar. ... This article is about the year. ... is the 323rd day of the year (324th in leap years) in the Gregorian calendar. ... Computerworld is an IT magazine that provides information to technology managers. ... 2008 (MMVIII) is the current year, a leap year that started on Tuesday of the Common Era (or Anno Domini), in accordance with the Gregorian calendar. ... is the 8th day of the year in the Gregorian calendar. ...

Results from FactBites:

 Parallel computing - Wikipedia, the free encyclopedia (1086 words) Parallel computing is the simultaneous execution of the same task (split up and specially adapted) on multiple processors in order to obtain results faster. Parallel processor machines are also divided into symmetric and asymmetric multiprocessors, depending on whether all the processors are capable of running all the operating system code and, say, accessing I/O devices or if some processors are more or less privileged. Such mechanisms may provide either implicit parallelism -- the system (the compiler or some other program) partitions the problem and allocates tasks to processors automatically (also called automatic parallelizing compilers) -- or explicit parallelism where the programmer must annotate his program to show how it is to be partitioned.
More results at FactBites »

Share your thoughts, questions and commentary here