Parallel computing

From Wikipedia for FEVERv2
(Redirected from Parallel computation)
Jump to navigation Jump to search

"Parallelization" redirects here. Parallel computing_sentence_0

For parallelization of manifolds, see Parallelization (mathematics). Parallel computing_sentence_1

Parallel computing is a type of computation where many calculations or the execution of processes are carried out simultaneously. Parallel computing_sentence_2

Large problems can often be divided into smaller ones, which can then be solved at the same time. Parallel computing_sentence_3

There are several different forms of parallel computing: bit-level, instruction-level, data, and task parallelism. Parallel computing_sentence_4

Parallelism has long been employed in high-performance computing, but has gained broader interest due to the physical constraints preventing frequency scaling. Parallel computing_sentence_5

As power consumption (and consequently heat generation) by computers has become a concern in recent years, parallel computing has become the dominant paradigm in computer architecture, mainly in the form of multi-core processors. Parallel computing_sentence_6

Parallel computing is closely related to concurrent computing—they are frequently used together, and often conflated, though the two are distinct: it is possible to have parallelism without concurrency (such as bit-level parallelism), and concurrency without parallelism (such as multitasking by time-sharing on a single-core CPU). Parallel computing_sentence_7

In parallel computing, a computational task is typically broken down into several, often many, very similar sub-tasks that can be processed independently and whose results are combined afterwards, upon completion. Parallel computing_sentence_8

In contrast, in concurrent computing, the various processes often do not address related tasks; when they do, as is typical in distributed computing, the separate tasks may have a varied nature and often require some inter-process communication during execution. Parallel computing_sentence_9

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. Parallel computing_sentence_10

Specialized parallel computer architectures are sometimes used alongside traditional processors, for accelerating specific tasks. Parallel computing_sentence_11

In some cases parallelism is transparent to the programmer, such as in bit-level or instruction-level parallelism, but explicitly parallel algorithms, particularly those that use concurrency, are more difficult to write than sequential ones, because concurrency introduces several new classes of potential software bugs, of which race conditions are the most common. Parallel computing_sentence_12

Communication and synchronization between the different subtasks are typically some of the greatest obstacles to getting optimal parallel program performance. Parallel computing_sentence_13

A theoretical upper bound on the speed-up of a single program as a result of parallelization is given by Amdahl's law. Parallel computing_sentence_14

Background Parallel computing_section_0

Traditionally, computer software has been written for serial computation. Parallel computing_sentence_15

To solve a problem, an algorithm is constructed and implemented as a serial stream of instructions. Parallel computing_sentence_16

These instructions are executed on a central processing unit on one computer. Parallel computing_sentence_17

Only one instruction may execute at a time—after that instruction is finished, the next one is executed. Parallel computing_sentence_18

Parallel computing, on the other hand, uses multiple processing elements simultaneously to solve a problem. Parallel computing_sentence_19

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. Parallel computing_sentence_20

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. Parallel computing_sentence_21

Historically parallel computing was used for scientific computing and the simulation of scientific problems, particularly in the natural and engineering sciences, such as meteorology. Parallel computing_sentence_22

This led to the design of parallel hardware and software, as well as high performance computing. Parallel computing_sentence_23

Frequency scaling was the dominant reason for improvements in computer performance from the mid-1980s until 2004. Parallel computing_sentence_24

The runtime of a program is equal to the number of instructions multiplied by the average time per instruction. Parallel computing_sentence_25

Maintaining everything else constant, increasing the clock frequency decreases the average time it takes to execute an instruction. Parallel computing_sentence_26

An increase in frequency thus decreases runtime for all compute-bound programs. Parallel computing_sentence_27

However, power consumption P by a chip is given by the equation P = C × V × 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). Parallel computing_sentence_28

Increases in frequency increase the amount of power used in a processor. Parallel computing_sentence_29

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. Parallel computing_sentence_30

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. Parallel computing_sentence_31

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. Parallel computing_sentence_32

Multi-core processors have brought parallel computing to desktop computers. Parallel computing_sentence_33

Thus parallelisation of serial programmes has become a mainstream programming task. Parallel computing_sentence_34

In 2012 quad-core processors became standard for desktop computers, while servers have 10 and 12 core processors. Parallel computing_sentence_35

From Moore's law it can be predicted that the number of cores per processor will double every 18–24 months. Parallel computing_sentence_36

This could mean that after 2020 a typical processor will have dozens or hundreds of cores. Parallel computing_sentence_37

An operating system can ensure that different tasks and user programmes are run in parallel on the available cores. Parallel computing_sentence_38

However, for a serial software programme to take full advantage of the multi-core architecture the programmer needs to restructure and parallelise the code. Parallel computing_sentence_39

A speed-up of application software runtime will no longer be achieved through frequency scaling, instead programmers will need to parallelise their software code to take advantage of the increasing computing power of multicore architectures. Parallel computing_sentence_40

Amdahl's law and Gustafson's law Parallel computing_section_1

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. Parallel computing_sentence_41

However, very few parallel algorithms achieve optimal speedup. Parallel computing_sentence_42

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. Parallel computing_sentence_43

The potential speedup of an algorithm on a parallel computing platform is given by Amdahl's law Parallel computing_sentence_44

where Parallel computing_sentence_45

Parallel computing_unordered_list_0

  • Slatency is the potential speedup in latency of the execution of the whole task;Parallel computing_item_0_0
  • s is the speedup in latency of the execution of the parallelizable part of the task;Parallel computing_item_0_1
  • p is the percentage of the execution time of the whole task concerning the parallelizable part of the task before parallelization.Parallel computing_item_0_2

Since Slatency < 1/(1 - p), it shows that a small part of the program which cannot be parallelized will limit the overall speedup available from parallelization. Parallel computing_sentence_46

A program solving a large mathematical or engineering problem will typically consist of several parallelizable parts and several non-parallelizable (serial) parts. Parallel computing_sentence_47

If the non-parallelizable part of a program accounts for 10% of the runtime (p = 0.9), we can get no more than a 10 times speedup, regardless of how many processors are added. Parallel computing_sentence_48

This puts an upper limit on the usefulness of adding more parallel execution units. Parallel computing_sentence_49

"When a task cannot be partitioned because of sequential constraints, the application of more effort has no effect on the schedule. Parallel computing_sentence_50

The bearing of a child takes nine months, no matter how many women are assigned." Parallel computing_sentence_51

Amdahl's law only applies to cases where the problem size is fixed. Parallel computing_sentence_52

In practice, as more computing resources become available, they tend to get used on larger problems (larger datasets), and the time spent in the parallelizable part often grows much faster than the inherently serial work. Parallel computing_sentence_53

In this case, Gustafson's law gives a less pessimistic and more realistic assessment of parallel performance: Parallel computing_sentence_54

Both Amdahl's law and Gustafson's law assume that the running time of the serial part of the program is independent of the number of processors. Parallel computing_sentence_55

Amdahl's law assumes that the entire problem is of fixed size so that the total amount of work to be done in parallel is also independent of the number of processors, whereas Gustafson's law assumes that the total amount of work to be done in parallel varies linearly with the number of processors. Parallel computing_sentence_56

Dependencies Parallel computing_section_2

Understanding data dependencies is fundamental in implementing parallel algorithms. Parallel computing_sentence_57

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. Parallel computing_sentence_58

However, most algorithms do not consist of just a long chain of dependent calculations; there are usually opportunities to execute independent calculations in parallel. Parallel computing_sentence_59

Let Pi and Pj be two program segments. Parallel computing_sentence_60

Bernstein's conditions describe when the two are independent and can be executed in parallel. Parallel computing_sentence_61

For Pi, let Ii be all of the input variables and Oi the output variables, and likewise for Pj. Parallel computing_sentence_62

Pi and Pj are independent if they satisfy Parallel computing_sentence_63

Violation of the first condition introduces a flow dependency, corresponding to the first segment producing a result used by the second segment. Parallel computing_sentence_64

The second condition represents an anti-dependency, when the second segment produces a variable needed by the first segment. Parallel computing_sentence_65

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. Parallel computing_sentence_66

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

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. Parallel computing_sentence_68

It violates condition 1, and thus introduces a flow dependency. Parallel computing_sentence_69

In this example, there are no dependencies between the instructions, so they can all be run in parallel. Parallel computing_sentence_70

Bernstein's conditions do not allow memory to be shared between different processes. Parallel computing_sentence_71

For that, some means of enforcing an ordering between accesses is necessary, such as semaphores, barriers or some other synchronization method. Parallel computing_sentence_72

Race conditions, mutual exclusion, synchronization, and parallel slowdown Parallel computing_section_3

Subtasks in a parallel program are often called threads. Parallel computing_sentence_73

Some parallel computer architectures use smaller, lightweight versions of threads known as fibers, while others use bigger versions known as processes. Parallel computing_sentence_74

However, "threads" is generally accepted as a generic term for subtasks. Parallel computing_sentence_75

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. Parallel computing_sentence_76

Without synchronization, the instructions between the two threads may be interleaved in any order. Parallel computing_sentence_77

For example, consider the following program: Parallel computing_sentence_78

Parallel computing_table_general_0

Thread AParallel computing_cell_0_0_0 Thread BParallel computing_cell_0_0_1
1A: Read variable VParallel computing_cell_0_1_0 1B: Read variable VParallel computing_cell_0_1_1
2A: Add 1 to variable VParallel computing_cell_0_2_0 2B: Add 1 to variable VParallel computing_cell_0_2_1
3A: Write back to variable VParallel computing_cell_0_3_0 3B: Write back to variable VParallel computing_cell_0_3_1

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. Parallel computing_sentence_79

This is known as a race condition. Parallel computing_sentence_80

The programmer must use a lock to provide mutual exclusion. Parallel computing_sentence_81

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. Parallel computing_sentence_82

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. Parallel computing_sentence_83

Therefore, to guarantee correct program execution, the above program can be rewritten to use locks: Parallel computing_sentence_84

Parallel computing_table_general_1

Thread AParallel computing_cell_1_0_0 Thread BParallel computing_cell_1_0_1
1A: Lock variable VParallel computing_cell_1_1_0 1B: Lock variable VParallel computing_cell_1_1_1
2A: Read variable VParallel computing_cell_1_2_0 2B: Read variable VParallel computing_cell_1_2_1
3A: Add 1 to variable VParallel computing_cell_1_3_0 3B: Add 1 to variable VParallel computing_cell_1_3_1
4A: Write back to variable VParallel computing_cell_1_4_0 4B: Write back to variable VParallel computing_cell_1_4_1
5A: Unlock variable VParallel computing_cell_1_5_0 5B: Unlock variable VParallel computing_cell_1_5_1

One thread will successfully lock variable V, while the other thread will be locked out—unable to proceed until V is unlocked again. Parallel computing_sentence_85

This guarantees correct execution of the program. Parallel computing_sentence_86

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. Parallel computing_sentence_87

Locking multiple variables using non-atomic locks introduces the possibility of program deadlock. Parallel computing_sentence_88

An atomic lock locks multiple variables all at once. Parallel computing_sentence_89

If it cannot lock all of them, it does not lock any of them. Parallel computing_sentence_90

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. Parallel computing_sentence_91

In such a case, neither thread can complete, and deadlock results. Parallel computing_sentence_92

Many parallel programs require that their subtasks act in synchrony. Parallel computing_sentence_93

This requires the use of a barrier. Parallel computing_sentence_94

Barriers are typically implemented using a lock or a semaphore. Parallel computing_sentence_95

One class of algorithms, known as lock-free and wait-free algorithms, altogether avoids the use of locks and barriers. Parallel computing_sentence_96

However, this approach is generally difficult to implement and requires correctly designed data structures. Parallel computing_sentence_97

Not all parallelization results in speed-up. Parallel computing_sentence_98

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. Parallel computing_sentence_99

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. Parallel computing_sentence_100

This problem, known as parallel slowdown, can be improved in some cases by software analysis and redesign. Parallel computing_sentence_101

Fine-grained, coarse-grained, and embarrassing parallelism Parallel computing_section_4

Applications are often classified according to how often their subtasks need to synchronize or communicate with each other. Parallel computing_sentence_102

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. Parallel computing_sentence_103

Embarrassingly parallel applications are considered the easiest to parallelize. Parallel computing_sentence_104

Consistency models Parallel computing_section_5

Main article: Consistency model Parallel computing_sentence_105

Parallel programming languages and parallel computers must have a consistency model (also known as a memory model). Parallel computing_sentence_106

The consistency model defines rules for how operations on computer memory occur and how results are produced. Parallel computing_sentence_107

One of the first consistency models was Leslie Lamport's sequential consistency model. Parallel computing_sentence_108

Sequential consistency is the property of a parallel program that its parallel execution produces the same results as a sequential program. Parallel computing_sentence_109

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". Parallel computing_sentence_110

Software transactional memory is a common type of consistency model. Parallel computing_sentence_111

Software transactional memory borrows from database theory the concept of atomic transactions and applies them to memory accesses. Parallel computing_sentence_112

Mathematically, these models can be represented in several ways. Parallel computing_sentence_113

Introduced in 1962, Petri nets were an early attempt to codify the rules of consistency models. Parallel computing_sentence_114

Dataflow theory later built upon these, and Dataflow architectures were created to physically implement the ideas of dataflow theory. Parallel computing_sentence_115

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. Parallel computing_sentence_116

More recent additions to the process calculus family, such as the π-calculus, have added the capability for reasoning about dynamic topologies. Parallel computing_sentence_117

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. Parallel computing_sentence_118

See also: Relaxed sequential Parallel computing_sentence_119

Flynn's taxonomy Parallel computing_section_6

Michael J. Flynn created one of the earliest classification systems for parallel (and sequential) computers and programs, now known as Flynn's taxonomy. Parallel computing_sentence_120

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. Parallel computing_sentence_121

The single-instruction-single-data (SISD) classification is equivalent to an entirely sequential program. Parallel computing_sentence_122

The single-instruction-multiple-data (SIMD) classification is analogous to doing the same operation repeatedly over a large data set. Parallel computing_sentence_123

This is commonly done in signal processing applications. Parallel computing_sentence_124

Multiple-instruction-single-data (MISD) is a rarely used classification. Parallel computing_sentence_125

While computer architectures to deal with this were devised (such as systolic arrays), few applications that fit this class materialized. Parallel computing_sentence_126

Multiple-instruction-multiple-data (MIMD) programs are by far the most common type of parallel programs. Parallel computing_sentence_127

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. Parallel computing_sentence_128

It is also—perhaps because of its understandability—the most widely used scheme." Parallel computing_sentence_129

Types of parallelism Parallel computing_section_7

Bit-level parallelism Parallel computing_section_8

Main article: Bit-level parallelism Parallel computing_sentence_130

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 manipulate per cycle. Parallel computing_sentence_131

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. Parallel computing_sentence_132

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. Parallel computing_sentence_133

Historically, 4-bit microprocessors were replaced with 8-bit, then 16-bit, then 32-bit microprocessors. Parallel computing_sentence_134

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. Parallel computing_sentence_135

Not until the early 2000s, with the advent of x86-64 architectures, did 64-bit processors become commonplace. Parallel computing_sentence_136

Instruction-level parallelism Parallel computing_section_9

Main article: Instruction-level parallelism Parallel computing_sentence_137

A computer program is, in essence, a stream of instructions executed by a processor. Parallel computing_sentence_138

Without instruction-level parallelism, a processor can only issue less than one instruction per clock cycle (IPC < 1). Parallel computing_sentence_139

These processors are known as subscalar processors. Parallel computing_sentence_140

These instructions can be re-ordered and combined into groups which are then executed in parallel without changing the result of the program. Parallel computing_sentence_141

This is known as instruction-level parallelism. Parallel computing_sentence_142

Advances in instruction-level parallelism dominated computer architecture from the mid-1980s until the mid-1990s. Parallel computing_sentence_143

All modern processors have multi-stage instruction pipelines. Parallel computing_sentence_144

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 and thus can issue one instruction per clock cycle (IPC = 1). Parallel computing_sentence_145

These processors are known as scalar processors. Parallel computing_sentence_146

The canonical example of a pipelined processor is a RISC processor, with five stages: instruction fetch (IF), instruction decode (ID), execute (EX), memory access (MEM), and register write back (WB). Parallel computing_sentence_147

The Pentium 4 processor had a 35-stage pipeline. Parallel computing_sentence_148

Most modern processors also have multiple execution units. Parallel computing_sentence_149

They usually combine this feature with pipelining and thus can issue more than one instruction per clock cycle (IPC > 1). Parallel computing_sentence_150

These processors are known as superscalar processors. Parallel computing_sentence_151

Instructions can be grouped together only if there is no data dependency between them. Parallel computing_sentence_152

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. Parallel computing_sentence_153

Task parallelism Parallel computing_section_10

Main article: Task parallelism Parallel computing_sentence_154

Task parallelisms is the characteristic of a parallel program that "entirely different calculations can be performed on either the same or different sets of data". Parallel computing_sentence_155

This contrasts with data parallelism, where the same calculation is performed on the same or different sets of data. Parallel computing_sentence_156

Task parallelism involves the decomposition of a task into sub-tasks and then allocating each sub-task to a processor for execution. Parallel computing_sentence_157

The processors would then execute these sub-tasks concurrently and often cooperatively. Parallel computing_sentence_158

Task parallelism does not usually scale with the size of a problem. Parallel computing_sentence_159

Superword level parallelism Parallel computing_section_11

Superword level parallelism is a vectorization technique based on loop unrolling and basic block vectorization. Parallel computing_sentence_160

It is distinct from loop vectorization algorithms in that it can exploit parallelism of inline code, such as manipulating coordinates, color channels or in loops unrolled by hand. Parallel computing_sentence_161

Hardware Parallel computing_section_12

Memory and communication Parallel computing_section_13

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). Parallel computing_sentence_162

Distributed memory refers to the fact that the memory is logically distributed, but often implies that it is physically distributed as well. Parallel computing_sentence_163

Distributed shared memory and memory virtualization combine the two approaches, where the processing element has its own local memory and access to the memory on non-local processors. Parallel computing_sentence_164

Accesses to local memory are typically faster than accesses to non-local memory. Parallel computing_sentence_165

On the supercomputers, distributed shared memory space can be implemented using the programming model such as PGAS. Parallel computing_sentence_166

This model allows processes on one compute node to transparently access the remote memory of another compute node. Parallel computing_sentence_167

All compute nodes are also connected to an external shared memory system via high-speed interconnect, such as Infiniband, this external shared memory system is known as burst buffer, which is typically built from arrays of non-volatile memory physically distributed across multiple I/O nodes. Parallel computing_sentence_168

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. Parallel computing_sentence_169

Typically, that can be achieved only by a shared memory system, in which the memory is not physically distributed. Parallel computing_sentence_170

A system that does not have this property is known as a non-uniform memory access (NUMA) architecture. Parallel computing_sentence_171

Distributed memory systems have non-uniform memory access. Parallel computing_sentence_172

Computer systems make use of caches—small and fast memories located close to the processor which store temporary copies of memory values (nearby in both the physical and logical sense). Parallel computing_sentence_173

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. Parallel computing_sentence_174

These computers require a cache coherency system, which keeps track of cached values and strategically purges them, thus ensuring correct program execution. Parallel computing_sentence_175

Bus snooping is one of the most common methods for keeping track of which values are being accessed (and thus should be purged). Parallel computing_sentence_176

Designing large, high-performance cache coherence systems is a very difficult problem in computer architecture. Parallel computing_sentence_177

As a result, shared memory computer architectures do not scale as well as distributed memory systems do. Parallel computing_sentence_178

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. Parallel computing_sentence_179

Parallel computers based on interconnected networks need to have some kind of routing to enable the passing of messages between nodes that are not directly connected. Parallel computing_sentence_180

The medium used for communication between the processors is likely to be hierarchical in large multiprocessor machines. Parallel computing_sentence_181

Classes of parallel computers Parallel computing_section_14

Parallel computers can be roughly classified according to the level at which the hardware supports parallelism. Parallel computing_sentence_182

This classification is broadly analogous to the distance between basic computing nodes. Parallel computing_sentence_183

These are not mutually exclusive; for example, clusters of symmetric multiprocessors are relatively common. Parallel computing_sentence_184

Multi-core computing Parallel computing_section_15

Main article: Multi-core processor Parallel computing_sentence_185

A multi-core processor is a processor that includes multiple processing units (called "cores") on the same chip. Parallel computing_sentence_186

This processor differs from a superscalar processor, which includes multiple execution units and can issue multiple instructions per clock cycle from one instruction stream (thread); in contrast, a multi-core processor can issue multiple instructions per clock cycle from multiple instruction streams. Parallel computing_sentence_187

IBM's Cell microprocessor, designed for use in the Sony PlayStation 3, is a prominent multi-core processor. Parallel computing_sentence_188

Each core in a multi-core processor can potentially be superscalar as well—that is, on every clock cycle, each core can issue multiple instructions from one thread. Parallel computing_sentence_189

Simultaneous multithreading (of which Intel's Hyper-Threading is the best known) was an early form of pseudo-multi-coreism. Parallel computing_sentence_190

A processor capable of concurrent multithreading includes multiple execution units in the same processing unit—that is it has a superscalar architecture—and can issue multiple instructions per clock cycle from multiple threads. Parallel computing_sentence_191

Temporal multithreading on the other hand includes a single execution unit in the same processing unit and can issue one instruction at a time from multiple threads. Parallel computing_sentence_192

Symmetric multiprocessing Parallel computing_section_16

Main article: Symmetric multiprocessing Parallel computing_sentence_193

A symmetric multiprocessor (SMP) is a computer system with multiple identical processors that share memory and connect via a bus. Parallel computing_sentence_194

Bus contention prevents bus architectures from scaling. Parallel computing_sentence_195

As a result, SMPs generally do not comprise more than 32 processors. Parallel computing_sentence_196

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. Parallel computing_sentence_197

Distributed computing Parallel computing_section_17

Main article: Distributed computing Parallel computing_sentence_198

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. Parallel computing_sentence_199

Distributed computers are highly scalable. Parallel computing_sentence_200

The terms "concurrent computing", "parallel computing", and "distributed computing" have a lot of overlap, and no clear distinction exists between them. Parallel computing_sentence_201

The same system may be characterized both as "parallel" and "distributed"; the processors in a typical distributed system run concurrently in parallel. Parallel computing_sentence_202

Cluster computing Parallel computing_section_18

Main article: Computer cluster Parallel computing_sentence_203

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. Parallel computing_sentence_204

Clusters are composed of multiple standalone machines connected by a network. Parallel computing_sentence_205

While machines in a cluster do not have to be symmetric, load balancing is more difficult if they are not. Parallel computing_sentence_206

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. Parallel computing_sentence_207

Beowulf technology was originally developed by Thomas Sterling and Donald Becker. Parallel computing_sentence_208

87% of all Top500 supercomputers are clusters. Parallel computing_sentence_209

The remaining are Massively Parallel Processors, explained below. Parallel computing_sentence_210

Because grid computing systems (described below) can easily handle embarrassingly parallel problems, modern clusters are typically designed to handle more difficult problems—problems that require nodes to share intermediate results with each other more often. Parallel computing_sentence_211

This requires a high bandwidth and, more importantly, a low-latency interconnection network. Parallel computing_sentence_212

Many historic and current supercomputers use customized high-performance network hardware specifically designed for cluster computing, such as the Cray Gemini network. Parallel computing_sentence_213

As of 2014, most current supercomputers use some off-the-shelf standard network hardware, often Myrinet, InfiniBand, or Gigabit Ethernet. Parallel computing_sentence_214

Massively parallel computing Parallel computing_section_19

Main article: Massively parallel (computing) Parallel computing_sentence_215

A massively parallel processor (MPP) is a single computer with many networked processors. Parallel computing_sentence_216

MPPs have many of the same characteristics as clusters, but MPPs have specialized interconnect networks (whereas clusters use commodity hardware for networking). Parallel computing_sentence_217

MPPs also tend to be larger than clusters, typically having "far more" than 100 processors. Parallel computing_sentence_218

In an MPP, "each CPU contains its own memory and copy of the operating system and application. Parallel computing_sentence_219

Each subsystem communicates with the others via a high-speed interconnect." Parallel computing_sentence_220

IBM's Blue Gene/L, the fifth fastest supercomputer in the world according to the June 2009 TOP500 ranking, is an MPP. Parallel computing_sentence_221

Grid computing Parallel computing_section_20

Main article: Grid computing Parallel computing_sentence_222

Grid computing is the most distributed form of parallel computing. Parallel computing_sentence_223

It makes use of computers communicating over the Internet to work on a given problem. Parallel computing_sentence_224

Because of the low bandwidth and extremely high latency available on the Internet, distributed computing typically deals only with embarrassingly parallel problems. Parallel computing_sentence_225

Many distributed computing applications have been created, of which SETI@home and Folding@home are the best-known examples. Parallel computing_sentence_226

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). Parallel computing_sentence_227

The most common distributed computing middleware is the Berkeley Open Infrastructure for Network Computing (BOINC). Parallel computing_sentence_228

Often, distributed computing software makes use of "spare cycles", performing computations at times when a computer is idling. Parallel computing_sentence_229

Specialized parallel computers Parallel computing_section_21

Within parallel computing, there are specialized parallel devices that remain niche areas of interest. Parallel computing_sentence_230

While not domain-specific, they tend to be applicable to only a few classes of parallel problems. Parallel computing_sentence_231

Reconfigurable computing with field-programmable gate arrays Parallel computing_section_22

Reconfigurable computing is the use of a field-programmable gate array (FPGA) as a co-processor to a general-purpose computer. Parallel computing_sentence_232

An FPGA is, in essence, a computer chip that can rewire itself for a given task. Parallel computing_sentence_233

FPGAs can be programmed with hardware description languages such as VHDL or Verilog. Parallel computing_sentence_234

However, programming in these languages can be tedious. Parallel computing_sentence_235

Several vendors have created C to HDL languages that attempt to emulate the syntax and semantics of the C programming language, with which most programmers are familiar. Parallel computing_sentence_236

The best known C to HDL languages are Mitrion-C, Impulse C, DIME-C, and Handel-C. Parallel computing_sentence_237

Specific subsets of SystemC based on C++ can also be used for this purpose. Parallel computing_sentence_238

AMD's decision to open its HyperTransport technology to third-party vendors has become the enabling technology for high-performance reconfigurable computing. Parallel computing_sentence_239

According to Michael R. D'Amour, Chief Operating Officer of DRC Computer Corporation, "when we first walked into AMD, they called us 'the socket stealers.' Parallel computing_sentence_240

Now they call us their partners." Parallel computing_sentence_241

General-purpose computing on graphics processing units (GPGPU) Parallel computing_section_23

Main article: GPGPU Parallel computing_sentence_242

General-purpose computing on graphics processing units (GPGPU) is a fairly recent trend in computer engineering research. Parallel computing_sentence_243

GPUs are co-processors that have been heavily optimized for computer graphics processing. Parallel computing_sentence_244

Computer graphics processing is a field dominated by data parallel operations—particularly linear algebra matrix operations. Parallel computing_sentence_245

In the early days, GPGPU programs used the normal graphics APIs for executing programs. Parallel computing_sentence_246

However, 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 Stream SDK respectively. Parallel computing_sentence_247

Other GPU programming languages include BrookGPU, PeakStream, and RapidMind. Parallel computing_sentence_248

Nvidia has also released specific products for computation in their Tesla series. Parallel computing_sentence_249

The technology consortium Khronos Group has released the OpenCL specification, which is a framework for writing programs that execute across platforms consisting of CPUs and GPUs. Parallel computing_sentence_250

AMD, Apple, Intel, Nvidia and others are supporting OpenCL. Parallel computing_sentence_251

Application-specific integrated circuits Parallel computing_section_24

Main article: Application-specific integrated circuit Parallel computing_sentence_252

Several application-specific integrated circuit (ASIC) approaches have been devised for dealing with parallel applications. Parallel computing_sentence_253

Because an ASIC is (by definition) specific to a given application, it can be fully optimized for that application. Parallel computing_sentence_254

As a result, for a given application, an ASIC tends to outperform a general-purpose computer. Parallel computing_sentence_255

However, ASICs are created by UV photolithography. Parallel computing_sentence_256

This process requires a mask set, which can be extremely expensive. Parallel computing_sentence_257

A mask set can cost over a million US dollars. Parallel computing_sentence_258

(The smaller the transistors required for the chip, the more expensive the mask will be.) Parallel computing_sentence_259

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. Parallel computing_sentence_260

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. Parallel computing_sentence_261

However, some have been built. Parallel computing_sentence_262

One example is the PFLOPS RIKEN MDGRAPE-3 machine which uses custom ASICs for molecular dynamics simulation. Parallel computing_sentence_263

Vector processors Parallel computing_section_25

Main article: Vector processor Parallel computing_sentence_264

A vector processor is a CPU or computer system that can execute the same instruction on large sets of data. Parallel computing_sentence_265

Vector processors have high-level operations that work on linear arrays of numbers or vectors. Parallel computing_sentence_266

An example vector operation is A = B × C, where A, B, and C are each 64-element vectors of 64-bit floating-point numbers. Parallel computing_sentence_267

They are closely related to Flynn's SIMD classification. Parallel computing_sentence_268

Cray computers became famous for their vector-processing computers in the 1970s and 1980s. Parallel computing_sentence_269

However, vector processors—both as CPUs and as full computer systems—have generally disappeared. Parallel computing_sentence_270

Modern processor instruction sets do include some vector processing instructions, such as with Freescale Semiconductor's AltiVec and Intel's Streaming SIMD Extensions (SSE). Parallel computing_sentence_271

Software Parallel computing_section_26

Parallel programming languages Parallel computing_section_27

Main article: List of concurrent and parallel programming languages Parallel computing_sentence_272

Concurrent programming languages, libraries, APIs, and parallel programming models (such as algorithmic skeletons) have been created for programming parallel computers. Parallel computing_sentence_273

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. Parallel computing_sentence_274

Shared memory programming languages communicate by manipulating shared memory variables. Parallel computing_sentence_275

Distributed memory uses message passing. Parallel computing_sentence_276

POSIX Threads and OpenMP are two of the most widely used shared memory APIs, whereas Message Passing Interface (MPI) is the most widely used message-passing system API. Parallel computing_sentence_277

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. Parallel computing_sentence_278

CAPS entreprise and Pathscale are also coordinating their effort to make hybrid multi-core parallel programming (HMPP) directives an open standard called OpenHMPP. Parallel computing_sentence_279

The OpenHMPP directive-based programming model offers a syntax to efficiently offload computations on hardware accelerators and to optimize data movement to/from the hardware memory. Parallel computing_sentence_280

OpenHMPP directives describe remote procedure call (RPC) on an accelerator device (e.g. GPU) or more generally a set of cores. Parallel computing_sentence_281

The directives annotate C or Fortran codes to describe two sets of functionalities: the offloading of procedures (denoted codelets) onto a remote device and the optimization of data transfers between the CPU main memory and the accelerator memory. Parallel computing_sentence_282

The rise of consumer GPUs has led to support for compute kernels, either in graphics APIs (referred to as compute shaders), in dedicated APIs (such as OpenCL), or in other language extensions. Parallel computing_sentence_283

Automatic parallelization Parallel computing_section_28

Main article: Automatic parallelization Parallel computing_sentence_284

Automatic parallelization of a sequential program by a compiler is the "holy grail" of parallel computing, especially with the aforementioned limit of processor frequency. Parallel computing_sentence_285

Despite decades of work by compiler researchers, automatic parallelization has had only limited success. Parallel computing_sentence_286

Mainstream parallel programming languages remain either explicitly parallel or (at best) partially implicit, in which a programmer gives the compiler directives for parallelization. Parallel computing_sentence_287

A few fully implicit parallel programming languages exist—SISAL, Parallel Haskell, SequenceL, System C (for FPGAs), Mitrion-C, VHDL, and Verilog. Parallel computing_sentence_288

Application checkpointing Parallel computing_section_29

Main article: Application checkpointing Parallel computing_sentence_289

As a computer system grows in complexity, the mean time between failures usually decreases. Parallel computing_sentence_290

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. Parallel computing_sentence_291

Application checkpointing means that the program has to restart from only its last checkpoint rather than the beginning. Parallel computing_sentence_292

While checkpointing provides benefits in a variety of situations, it is especially useful in highly parallel systems with a large number of processors used in high performance computing. Parallel computing_sentence_293

Algorithmic methods Parallel computing_section_30

As parallel computers become larger and faster, we are now able to solve problems that had previously taken too long to run. Parallel computing_sentence_294

Fields as varied as bioinformatics (for protein folding and sequence analysis) and economics (for mathematical finance) have taken advantage of parallel computing. Parallel computing_sentence_295

Common types of problems in parallel computing applications include: Parallel computing_sentence_296

Parallel computing_unordered_list_1

Fault tolerance Parallel computing_section_31

Further information: Fault-tolerant computer system Parallel computing_sentence_297

Parallel computing can also be applied to the design of fault-tolerant computer systems, particularly via lockstep systems performing the same operation in parallel. Parallel computing_sentence_298

This provides redundancy in case one component fails, and also allows automatic error detection and error correction if the results differ. Parallel computing_sentence_299

These methods can be used to help prevent single-event upsets caused by transient errors. Parallel computing_sentence_300

Although additional measures may be required in embedded or specialized systems, this method can provide a cost-effective approach to achieve n-modular redundancy in commercial off-the-shelf systems. Parallel computing_sentence_301

History Parallel computing_section_32

Main article: History of computing Parallel computing_sentence_302

The origins of true (MIMD) parallelism go back to Luigi Federico Menabrea and his Sketch of the Analytic Engine Invented by Charles Babbage. Parallel computing_sentence_303

In April 1958, Stanley Gill (Ferranti) discussed parallel programming and the need for branching and waiting. Parallel computing_sentence_304

Also in 1958, IBM researchers John Cocke and Daniel Slotnick discussed the use of parallelism in numerical calculations for the first time. Parallel computing_sentence_305

Burroughs Corporation introduced the D825 in 1962, a four-processor computer that accessed up to 16 memory modules through a crossbar switch. Parallel computing_sentence_306

In 1967, Amdahl and Slotnick published a debate about the feasibility of parallel processing at American Federation of Information Processing Societies Conference. Parallel computing_sentence_307

It was during this debate that Amdahl's law was coined to define the limit of speed-up due to parallelism. Parallel computing_sentence_308

In 1969, Honeywell introduced its first Multics system, a symmetric multiprocessor system capable of running up to eight processors in parallel. Parallel computing_sentence_309

C.mmp, a multi-processor project at Carnegie Mellon University in the 1970s, was among the first multiprocessors with more than a few processors. Parallel computing_sentence_310

The first bus-connected multiprocessor with snooping caches was the Synapse N+1 in 1984. Parallel computing_sentence_311

SIMD parallel computers can be traced back to the 1970s. Parallel computing_sentence_312

The motivation behind early SIMD computers was to amortize the gate delay of the processor's control unit over multiple instructions. Parallel computing_sentence_313

In 1964, Slotnick had proposed building a massively parallel computer for the Lawrence Livermore National Laboratory. Parallel computing_sentence_314

His design was funded by the US Air Force, which was the earliest SIMD parallel-computing effort, ILLIAC IV. Parallel computing_sentence_315

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. Parallel computing_sentence_316

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. Parallel computing_sentence_317

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. Parallel computing_sentence_318

Biological brain as massively parallel computer Parallel computing_section_33

In the early 1970s, at the MIT Computer Science and Artificial Intelligence Laboratory, Marvin Minsky and Seymour Papert started developing the Society of Mind theory, which views the biological brain as massively parallel computer. Parallel computing_sentence_319

In 1986, Minsky published The Society of Mind, which claims that “mind is formed from many little agents, each mindless by itself”. Parallel computing_sentence_320

The theory attempts to explain how what we call intelligence could be a product of the interaction of non-intelligent parts. Parallel computing_sentence_321

Minsky says that the biggest source of ideas about the theory came from his work in trying to create a machine that uses a robotic arm, a video camera, and a computer to build with children's blocks. Parallel computing_sentence_322

Similar models (which also view the biological brain as a massively parallel computer, i.e., the brain is made up of a constellation of independent or semi-independent agents) were also described by: Parallel computing_sentence_323

Parallel computing_unordered_list_2

See also Parallel computing_section_34

Parallel computing_unordered_list_3

Credits to the contents of this page go to the authors of the corresponding Wikipedia page: computing.