The Cray-2 was the world's fastest computer from 1985 to 1989. The Cray-2 was a vector Supercomputer made by Cray Research starting in 1985.

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"). Computing is usually defined like the activity of using and developing Computer technology Computer hardware and software. In Computer science, an instruction is a single operation of a processor defined by an Instruction set architecture. In Computer science, concurrency is a properties of system in which several Computational processes are executing at the same time and potentially interacting There are several different forms of parallel computing: bit-level parallelism, instruction-level parallelism, data parallelism, and task parallelism. 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 performed simultaneously Data parallelism (also known as loop-level parallelism) is a form of Parallelization of computing across multiple processors in Parallel computing Task parallelism (also known as function parallelism and control parallelism) is a form of Parallelization of computer code across multiple processors 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. High-performance computing (HPC uses Supercomputers and Computer clusters to solve advanced computing problems Frequency scaling (also known as frequency ramping) is in Computer architecture, the technique of ramping a processor's Frequency so as to achieve Parallel computing has become the dominant paradigm in computer architecture, mainly in the form of multicore processors. In Computer engineering, computer architecture is the conceptual design and fundamental operational structure of a Computer system A multi-core processor (or chip-level multiprocessor, CMP) combines two or more independent cores into a single package composed of a single Integrated ^[2] However, in recent years, power consumption by parallel computers has become a concern. In Electrical engineering, power consumption often refers to the Electrical energy over Time supplied to operate an Electrical appliance, although ^[3]

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. A multi-core processor (or chip-level multiprocessor, CMP) combines two or more independent cores into a single package composed of a single Integrated In Computing, symmetric multiprocessing or SMP involves a Multiprocessor computer-architecture where two or more identical processors can connect to a single Massive parallel processing ( MPP) is a term used in Computer architecture to refer to a computer system with many independent Arithmetic units or entire Grid computing is a form of Distributed computing whereby a "super and virtual computer" is composed of a cluster of networked loosely-coupled

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. In Computer science, a parallel algorithm, as opposed to a traditional Sequential algorithm, is one which can be executed a piece at a time on many different processing A software bug (or just “bug” is an error flaw mistake Failure, fault or “undocumented feature” in a Computer program that prevents it A race condition or race hazard is a flaw in a System or process whereby the output and/or result of the process is unexpectedly and critically dependent Communication and synchronization between the different subtasks is typically one of the greatest barriers to getting good parallel program performance. Computer networking is the Engineering Discipline concerned with communication between Computer systems or devices Networking routers In Computer science, synchronization refers to one of two distinct but related concepts synchronization of processes, and synchronization of data The speedup of a program as a result of parallelization is given by Amdahl's law. In Parallel computing, speedup refers to how much a Parallel algorithm is faster than a corresponding sequential Algorithm. Amdahl's law, also known as Amdahl's argument, is named after computer architect Gene Amdahl, and is used to find the maximum expected improvement

Background

Traditionally, computer software has been written for serial computation. To solve a problem, an algorithm is constructed that produces a serial stream of instructions. In Mathematics, Computing, Linguistics and related subjects an algorithm is a sequence of finite instructions often used for Calculation 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]

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. 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. Frequency scaling (also known as frequency ramping) is in Computer architecture, the technique of ramping a processor's Frequency so as to achieve 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. In Computer science, CPU bound (or compute bound) is when the time for a computer to complete a task is determined principally by the speed of the central processor ^[6]

However, power consumption by a chip is given by the equation P = C × V² × 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). In Electrical engineering, power consumption often refers to the Electrical energy over Time supplied to operate an Electrical appliance, although Capacitance is a measure of the amount of Electric charge stored (or separated for a given Electric potential. Electrical tension (or voltage after its SI unit, the Volt) is the difference of electrical potential between two points of an electrical ^[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. Tejas was a code name for Intel 's Microprocessor which was to be a successor to the latest Pentium 4 with Prescott core ^[8]

Moore's Law is the empirical observation that transistor density in a microprocessor doubles every 18 to 24 months. Moore's law describes an important trend in the History of computer hardware. 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.

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) speedup the program would have experienced in the optimal case, while the purple curve indicates the actual (suboptimal) speedup. By the same token, the yellow curve indicates the runtime the program would have experienced in the optimal case (an asymptopte which approaches zero), while the red curve indicates the actual runtime (an asymptopte 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.

The potential speedup of an algorithm on a parallel computing platform is given by Amdahl's law, originally formulated by Gene Amdahl in the 1960s. Amdahl's law, also known as Amdahl's argument, is named after computer architect Gene Amdahl, and is used to find the maximum expected improvement Gene Myron Amdahl (born November 16, 1922) is a Norwegian American computer architect and hi-tech entrepreneur chiefly known for his work on ^[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:

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 speedup, 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. Gustafson's Law (also known as Gustafson-Barsis' law) is a law in Computer engineering which states that any sufficiently large problem can be efficiently parallelized It can be formulated as:

A graphical representation of Amdahl's law Assume that a task has two independent parts, A and B. Amdahl's law, also known as Amdahl's argument, is named after computer architect Gene Amdahl, and is used to find the maximum expected improvement 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 speedup, (5x versus 2x).

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.

Dependencies

Understanding data dependencies is fundamental in implementing parallel algorithms. A data dependency in computer science is a situation in which a program statement (instruction refers to the data of a preceding statement In Computer science, a parallel algorithm, as opposed to a traditional Sequential algorithm, is one which can be executed a piece at a time on many different processing No program can run more quickly than the longest chain of dependent calculations (known as the critical path), since calculations that depend upon prior calculations in the chain must be executed in order. However, most algorithms do not consist of just a long chain of dependent calculations; there are usually opportunities to execute independent calculations in parallel.

Let P_i and P_j be two program fragments. Bernstein's conditions^[12] describe when the two are independent and can be executed in parallel. Let I_i be all of the input variables to P_i and O_i the output variables, and likewise for P_j. P _i and P_j are independent if they satisfy

Violation of the first condition introduces a flow dependency, corresponding to first statement's 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. For other uses see Semaphore. A semaphore, in computer science is a protected Variable (an entity storing a value or Abstract In Parallel computing, a barrier is a type of synchronization method In Computer science, synchronization refers to one of two distinct but related concepts synchronization of processes, and synchronization of data

Race conditions, mutual exclusion, synchronization, and parallel slowdown

Subtasks in a parallel program are often called threads. A thread in Computer science is short for a thread of execution. Some parallel computer architectures use smaller, lightweight versions of threads known as fibers, while others use bigger versions known as processes. In Computer science, a fiber is a particularly lightweight Thread of execution. In computing a process is an instance of a Computer program that is being sequentially executed by a computer system that has the ability to run several computer However, "threads" is generally accepted as a generic term for subtasks. Threads will often need to update some variable that is shared between them. A variable (ˈvɛərɪəbl is an Attribute of a physical or an abstract System which may change its Value while it is under Observation. The instructions between the two programs may be interleaved in any order. Interleaving in Computer science is a way to arrange Data in a non- Contiguous way in order to increase performance For example, consider the following program:

If instruction 1B is executed between 1A and 3A, or if instruction 1A is executed between 1B and 3B, the program will produce incorrect data. This is known as a race condition. A race condition or race hazard is a flaw in a System or process whereby the output and/or result of the process is unexpectedly and critically dependent The programmer must use a lock to provide mutual exclusion. 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 Mutual exclusion (often abbreviated to mutex) Algorithms are used in Concurrent programming to avoid the simultaneous use of a common resource such as a 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. In Concurrent programming a critical section is a piece of Code that accesses a shared resource (data structure or device that must not be concurrently accessed by Therefore, to guarantee correct program execution, the above program can be rewritten to use locks:

One thread will successfully lock variable V, while the other thread will be locked out—unable to proceed until V is unlocked again. 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 This guarantees correct execution of the program. Locks, while necessary to ensure correct program execution, can greatly slow a program.

Locking multiple variables using non-atomic locks introduces the possibility of program deadlock. An atomic operation in computer science refers to a set of operations that can be combined so that they appear to the rest of the system to be a single operation with only A deadlock is a situation wherein two or more competing actions are waiting for the other to finish and thus neither ever does An atomic lock locks multiple variables all at once. If it cannot lock all of them, it does not lock any of them. If two threads each need to lock the same two variables using non-atomic locks, it is possible that one thread will lock one of them and the second thread will lock the second variable. In such a case, neither thread can complete, and deadlock results.

Many parallel programs require that their subtasks act in synchrony. In Computer science, synchronization refers to one of two distinct but related concepts synchronization of processes, and synchronization of data This requires the use of a barrier. In Parallel computing, a barrier is a type of synchronization method 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. 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 However, this approach is generally difficult to implement and requires correctly designed data structures.

Not all parallelization results in speed-up. Generally, as a task is split up into more and more threads, those threads spend an ever-increasing portion of their time communicating with each other. 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. Parallel slowdown is a phenomenon in Parallel computing where parallelization of a parallel computer program beyond a certain point causes the program to run

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. 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 Embarrassingly parallel applications are considered the easiest to parallelize.

Consistency models

Main article: Consistency model

Leslie Lamport first defined the concept of sequential consistency. In Computer science, in a Distributed system such as a Distributed shared memory system or a distributed data store such as a Database, Filesystem Dr Leslie Lamport (born February 7, 1941 in New York City) is an American computer scientist. Sequential consistency is one of the Consistency models used in the domain of the Concurrent programming (e Lamport is also well-known for his work in creating the LaTeX typesetting software. LaTeX (ˈleɪtɛ

Parallel programming languages and parallel computers must have a consistency model (also known as a memory model). In Computer science, in a Distributed system such as a Distributed shared memory system or a distributed data store such as a Database, Filesystem The consistency model defines rules for how operations on computer memory occur and how results are produced. Computer data storage, often called storage or memory, refers to Computer components devices and recording media that retain digital

One of the first consistency models was Leslie Lamport's sequential consistency model. Dr Leslie Lamport (born February 7, 1941 in New York City) is an American computer scientist. Sequential consistency is one of the Consistency models used in the domain of the Concurrent programming (e 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]

Software transactional memory is a common type of consistency model. In Computer science, software transactional memory (STM is a Concurrency control mechanism analogous to Database transactions for controlling access to Software transactional memory borrows from database theory the concept of atomic transactions and applies them to memory accesses. A database management system ( DBMS) is Computer software designed for the purpose of managing Databases DBMSes may use any of a variety of Data models In Database systems atomicity (or atomicness) is one of the ACID transaction properties

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. A Petri net (also known as a place/transition net or P/T net) is one of several Mathematical Modeling languages for the description of discrete Dataflow theory later built upon these, and Dataflow architectures were created to physically implement the ideas of dataflow theory. Dataflow architecture is a Computer architecture that directly contrasts the traditional Von Neumann architecture or Control flow architecture 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. In Computer science, the process calculi (or process algebras) are a diverse family of related approaches to formally modelling Concurrent systems Process The Calculus of Communicating Systems (CCS is a Process calculus introduced by Robin Milner in around 1980 In Computer science, Communicating Sequential Processes ( CSP) is a formal language for describing Patterns of Interaction in Concurrent More recent additions to the process calculus family, such as the π-calculus, have added the capability for reasoning about dynamic topologies. In Theoretical computer science, the \pi-calculus is a Process calculus originally developed by Robin Milner, Joachim Parrow and 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. Temporal logic of actions (TLA is 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 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. Michael J Flynn (born May 20, 1934 in New York City) is an American professor emeritus at Stanford University Flynn's taxonomy is a classification of Computer architectures proposed by Michael J 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.

The single-instruction-single-data (SISD) classification is equivalent to an entirely sequential program. Flynn's taxonomy is a classification of Computer architectures proposed by Michael J In Computing, SISD ( S ingle I nstruction S ingle D ata is a term referring to an architecture in which a single processor an uniprocessor In Computing, MISD ( M ultiple I nstruction S ingle D ata is a type of Parallel computing architecture where In Computing, SIMD ( S ingle I nstruction M ultiple D ata is a technique employed to achieve data level parallelism as in a Vector In Computing, MIMD ( M ultiple I nstruction stream M ultiple D ata stream is a technique employed to achieve parallelism 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. Signal processing is the analysis interpretation and manipulation of signals Signals of interest include sound, images, biological signals such as 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. In Computer architecture, a systolic array is a pipe network arrangement of processing units called cells Multiple-instruction-multiple-data (MIMD) programs are by far the most common type of parallel programs.

According to David A. Patterson and John L. Hennessy, "Some machines are hybrids of these categories, of course, but this classic model has survived because it is simple, easy to understand, and gives a good first approximation. David Andrew Patterson (born November 16[[ 947]] is an American computer pioneer and academic who has held the position of Professor of Computer Science For other people named John Hennessy see John Hennessy. John LeRoy Hennessy is an American computer scientist and academic It is also—perhaps because of its understandability—the most widely used scheme. "^[15]

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. Bit-level parallelism is a form of Parallel computing based on increasing processor word size. In Computing, " word " is a term for the natural unit of data used by a particular computer design ^[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. Eight-bit CPUs normally use an 8-bit data bus and a 16-bit address bus which means that their Address space is limited to 64 KBs This is not a "natural The integers (from the Latin integer, literally "untouched" hence "whole" the word entire comes from the same origin but via French In Computer processors the carry flag (usually indicated as the C flag is a single Bit in a system status (flag register used to indicate when

Historically, 4-bit microprocessors were replaced with 8-bit, then 16-bit, then 32-bit microprocessors. The Intel 4004, the world's first commercially available single- chip Microprocessor, was a 4-bit CPU. 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 (circa 2003-2004), with the advent of x86-64 architectures, have 64-bit processors become commonplace. x86-64 is a Superset of the x86 instruction set architecture. '64-bit' CPUs have existed in Supercomputers since the 1960s and in RISC -based workstations and servers since the early 1990s.

Instruction-level parallelism

Main article: 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. Instruction-level parallelism (ILP is a measure of how many of the operations in a Computer program can be performed simultaneously These instructions can be re-ordered and combined into groups which are then executed in parallel without changing the result of the program. In Computer engineering, out-of-order execution, OoOE, is a paradigm used in most high-performance Microprocessors to make use of cycles that This is known as instruction-level parallelism. Advances in instruction-level parallelism dominated computer architecture from the mid-1980s until the mid-1990s. ^[17]

Modern processors have multi-stage instruction pipelines. Pipelining redirects here For HTTP pipelining see HTTP pipelining. Each stage in the pipeline corresponds to a different action the processor performs on that instruction in that stage; in other words, a processor with N pipeline stages 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. The Pentium 4 brand refers to Intel 's line of single- core mainstream desktop and Laptop Central processing units (CPUs introduced ^[18]

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. A superscalar CPU architecture implements a form of parallelism called Instruction-level parallelism within a single processor Instructions can be grouped together only if there is no data dependency between them. A data dependency in computer science is a situation in which a program statement (instruction refers to the data of a preceding statement 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. Scoreboarding is a centralized method used in the CDC 6600, for dynamically scheduling a pipeline so that the instructions can execute out of order when The Tomasulo algorithm is a hardware Algorithm developed in 1967 by Robert Tomasulo from IBM. In Computer engineering, register renaming refers to a technique usedto avoid unnecessary serialization of program operations imposed by the reuseof registers by those

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. Data parallelism (also known as loop-level parallelism) is a form of Parallelization of computing across multiple processors in Parallel computing In Computer science control flow (or alternatively flow of control refers to the order in which the individual statements, instructions or Function "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.

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:

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. Pseudocode is a compact and informal high-level description of a Computer programming Algorithm that uses the structural conventions of some Programming language In Mathematics, the Fibonacci numbers are a Sequence of numbers named after Leonardo of Pisa, known as Fibonacci 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]

Task parallelism

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". Task parallelism (also known as function parallelism and control parallelism) is a form of Parallelization of computer code across multiple processors ^[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]

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). In Computing, shared memory is a memory that may be simultaneously accessed by multiple programs with an intent to provide communication among them or avoid redundant copies 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 In Computer science, distributed memory refers to a multiple-processor computer system in which each processor has its own private memory. ^[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. Distributed Shared Memory (DSM also known as a distributed global address space ( DGAS) is a term in Computer science that refers to a wide class of software Accesses to local memory are typically faster than accesses to non-local memory.

A logical view of a Non-Uniform Memory Access (NUMA) architecture. Non-Uniform Memory Access or Non-Uniform Memory Architecture ( NUMA) is a computer memory design used in Multiprocessors where the memory access 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 all of main memory can be accessed with equal latency and bandwidth are known as Uniform Memory Access (UMA) systems. In Computing, memory latency is the time between initiating a request for a Byte or word in memory until it is retrieved In Computer networking and Computer science, digital bandwidth or just bandwidth is the capacity for a given system to transfer data over a connection Uniform Memory Access (UMA is a Shared memory architecture used in Parallel computers All the processors in the UMA model share the physical memory uniformly Typically, only a shared memory system (where the memory is not physically distributed) can achieve these. In Computing, shared memory is a memory that may be simultaneously accessed by multiple programs with an intent to provide communication among them or avoid redundant copies A system that does not have this property is known as a Non-Uniform Memory Access (NUMA) architecture. Non-Uniform Memory Access or Non-Uniform Memory Architecture ( NUMA) is a computer memory design used in Multiprocessors where the memory access Distributed memory systems have non-uniform memory access.

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). In Computer science, a cache (kæʃ like "cash") is a collection of data duplicating original 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. In computing Cache coherency (also cache coherence) refers to the integrity of data stored in local caches of a shared resource Bus snooping is one of the most common methods for keeping track of which values are being accessed (and thus should be purged). Bus sniffing or Bus snooping is a technique used in Distributed shared memory systems and multiprocessors aimed at achieving Cache coherence. 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]

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. For multiplexing in electronics and signal processing see Multiplexer. A crossbar switch (also known as cross-point switch, crosspoint switch, or matrix switch) is a Switch connecting multiple inputs to multiple In Computer architecture, a bus is a subsystem that transfers data between computer components inside a Computer or between computers Network topology is the study of the arrangement or mapping of the elements ( links, nodes, etc Star networks are one of the most common Computer network topologies. A ring network is a Network topology in which each node connects to exactly two other nodes forming a circular pathway In Graph theory, a tree is a graph in which any two vertices are connected by exactly one path. In the mathematical field of Graph theory, the Hypercube graph Qn is a Regular graph with 2 n 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. Routing is the process of selecting paths in a network along which to send network traffic The medium used for communication between the processors is likely to be hierarchical in large multiprocessor machines.

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"). A multi-core processor (or chip-level multiprocessor, CMP) combines two or more independent cores into a single package composed of a single Integrated In Computer engineering, an execution unit is a part of a CPU that performs the operations and calculations called for by the program. 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.

Simultaneous multithreading (of which Intel's HyperThreading is the best known) was an early form of pseudo-multicoreism. Simultaneous multithreading, often abbreviated as SMT, is a technique for improving the overall efficiency of Superscalar CPUs with Hardware Hyper-threading (officially termed Hyper-Threading Technology or HTT) is an Intel-proprietary technology A processor capable of simultaneous multithreading has only one execution unit ("core"), but when that execution unit is idling (such as during a cache miss), it uses that execution unit to process a second thread. Intel's Core and Core 2 processor families are Intel's first true multicore architectures. The Core brand refers to Intel 's 32-bit mobile Dual-core X86 CPUs that derived from the Pentium M branded processors The Core 2 brand refers to a range of Intel 's consumer 64-bit dual-core and 2x2 MCM quad-core CPUs with the X86-64 instruction set IBM's Cell microprocessor, designed for use in the Sony Playstation 3, is another prominent multicore processor. International Business Machines Corporation abbreviated IBM and nicknamed "Big Blue", is a multinational Computer Technology Cell is a Microprocessor architecture jointly developed by Sony Computer Entertainment, Toshiba, and IBM, an is a multinational conglomerate corporation headquartered in Minato Tokyo, Japan, and one of the world's largest Media conglomerates with

Symmetric multiprocessing

Main article: Symmetric multiprocessing

A symmetric multiprocessor (SMP) is a computer system with multiple identical processors that share memory and connect via a bus. In Computing, symmetric multiprocessing or SMP involves a Multiprocessor computer-architecture where two or more identical processors can connect to a single ^[22] Bus contention prevents bus architectures from scaling. Bus contention, in Computer design, is an undesirable state of the bus in which more than one device on the bus attempts to place values on the bus at the same time 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]

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 computing deals with Hardware and Software Systems containing more than one processing element or Storage element concurrent Distributed computers are highly scalable.

Cluster computing

Main article: Computer cluster

A Beowulf 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. Originally referring to a specific computer built in 1994 Beowulf is a class of Computer clusters similar to the original NASA system ^[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. In Computer networking, load balancing is a technique to spread work between two or more computers network links CPUs hard drives or other resources in order to get optimal 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. Originally referring to a specific computer built in 1994 Beowulf is a class of Computer clusters similar to the original NASA system Commercial off-the-shelf ( COTS) is a term for Software or Hardware, generally technology or computer products that are ready-made and available for sale The Internet Protocol Suite (commonly TCP/IP) is the set of Communications protocols used for the Internet and other similar networks Ethernet is a family of frame -based Computer networking technologies for Local area networks (LANs ^[25] Beowulf technology was originally developed by Thomas Sterling and Donald Becker. Thomas Sterling is a colleague of Don Becker and co-author of the original Beowulf Howto Donald Becker is a notable developer well known for writing many of the Ethernet drivers for the Linux operating system The vast majority of the TOP500 supercomputers are clusters. The TOP500 project ranks and details the 500 most powerful known Computer systems in the world ^[26]

Massive parallel processing

Main article: Massive parallel processing

A massively parallel processor (MPP) is a single computer with many networked processors. Massive parallel processing ( MPP) is a term used in Computer architecture to refer to a computer system with many independent Arithmetic units or entire 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]

A cabinet from Blue Gene/L, ranked as the fastest supercomputer in the world according to the TOP500 rankings. Blue Gene is a Computer architecture project designed to produce several Supercomputers designed to reach operating speeds in the PFLOPS (petaFLOPS The TOP500 project ranks and details the 500 most powerful known Computer systems in the world Blue Gene/L is a massively parallel processor.

Blue Gene/L, the fastest supercomputer in the world according to the TOP500 ranking, is an MPP. Blue Gene is a Computer architecture project designed to produce several Supercomputers designed to reach operating speeds in the PFLOPS (petaFLOPS

Grid computing

Main article: Grid computing

Grid computing is the most distributed form of parallel computing. Grid computing is a form of Distributed computing whereby a "super and virtual computer" is composed of a cluster of networked loosely-coupled It makes use of computers communicating over the Internet to work on a given problem. The Internet is a global system of interconnected Computer networks 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 best-known examples. A list of Distributed computing projects. Berkeley Open Infrastructure for Network Computing (BOINC See also Berkeley Open Infrastructure for Network SETI@home ("SETI at home" is a Distributed computing ( Grid computing) project using Internet -connected computers hosted by the Space Folding@home (sometimes abbreviated as FAH or F@h) is a Distributed computing (DC project designed to perform computationally intensive simulations

Most grid computing applications use middleware—software that operates between the operating system and the application, which manages network resources and standardizes the software interface for grid computing applications. Middleware is computer Software that connects Software components or applications The most common grid computing middleware is the Berkeley Open Infrastructure for Network Computing (BOINC). The Berkeley Open Infrastructure for Network Computing ( BOINC) is a non-commercial Middleware system for volunteer and Grid computing. Often, grid computing software makes use of "spare cycles", performing computations at times when a computer is idling.

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. The term domain-specific language ( DSL) has become popular in recent years in Software development to indicate a Programming language or Specification

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. Reconfigurable computing is a computing paradigm combining some of the flexibility of software with the high performance of hardware by processing with very flexible high speed computing FPGAs should not be confused with the Flip-chip pin grid array, a form of integrated circuit packaging An FPGA is, in essence, a computer chip that can rewire itself for a given task.

FPGAs can be programmed with hardware description languages such as VHDL or Verilog. In Electronics, a hardware description language or HDL is any language from a class of Computer languages and/or Programming languages for formal In the Semiconductor and electronic design industry Verilog is a Hardware description language (HDL used to model electronic systems. 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. A number of vendors have attempted to create tools that convert C or C-like languages into a Hardware description language like VHDL or Verilog. tags please moot on the talk page first! --> In Computing, C is a general-purpose cross-platform block structured The best known C to HDL languages are Mitrion-C, Impulse C, DIME-C, and Handel-C. Impulse C is a subset of the C programming language combined with a C-compatible Function library supporting Parallel programming, in particular for 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 It is

AMD's decision to open its HyperTransport technology to third-party vendors has become the enabling technology for high-performance reconfigurable computing. ^[29] According to Michael R. D'Amour, CEO of DRC Computer Corporation, "when we first walked into AMD, they called us 'the socket stealers. A CPU socket or CPU slot is a connector on a computer's Motherboard that accepts a CPU and forms an electrical interface with it ' Now they call us their partners. "^[29]

GPGPU with graphics processing units

Main article: GPGPU

Nvidia's Tesla GPGPU card

General-purpose computing on graphics processing units (GPGPU) is a fairly recent trend in computer engineering research. General-purpose computing on graphics processing units (GPGPU also referred to as GPGP and to a lesser extent GP² is the technique of using a GPU, which typically handles The Tesla GPU is NVIDIA's third brand of GPUs It's based on the G80 and Quadro and is NVIDIA's first dedicated GPUs are co-processors that have been heavily optimized for computer graphics processing. Computer graphics are Graphics created by Computers and more generally the Representation and Manipulation of Pictorial Data ^[30] Computer graphics processing is a field dominated by data parallel operations—particularly linear algebra matrix operations. Linear algebra is the branch of Mathematics concerned with In Mathematics, a matrix (plural matrices) is a rectangular table of elements (or entries) which may be Numbers or more generally

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. The multinational NVIDIA Corporation ( (ɪnˈvɪdiə specializes in the manufacture of graphics-processor technologies for Workstations CUDA ( Compute Unified Device Architecture) is a Compiler and set of development tools that enable programmers to use a variation of C to Close To Metal (" CTM " in short originally called Close-to-the-Metal) is the name of a beta version of a low-level programming interface developed by Other GPU programming languages are BrookGPU, PeakStream, and RapidMind. BrookGPU is the Stanford University Graphics group's compiler and runtime implementation of the Brook stream programming language for using modern graphics hardware PeakStream is a Parallel processing software company located in San Mateo California company founded by Matthew Papakipos and Asher Waldfogel in April Stream processing is a Computer programming paradigm related to SIMD, that allows some applications to more easily exploit a limited form of parallel processing Nvidia has also released specific products for computation in their Tesla series. The Tesla GPU is NVIDIA's third brand of GPUs It's based on the G80 and Quadro and is NVIDIA's first dedicated

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. ^[31][32][33]

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. X-ray lithography is a next generation Lithography that has been developed for the Semiconductor industry This process requires a mask, which can be extremely expensive. A single mask can cost over a million US dollars. ^[34] (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. ^[29] 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. MDGRAPE-3 is an ultra-high performance Supercomputer system developed by the RIKEN research institute in Japan. Molecular dynamics ( MD) is a form of Computer simulation in which atoms and molecules are allowed to interact for a period of time by approximations of

Vector processors

Main article: Vector processor

The Cray-1 is the most famous vector processor. A vector processor, or array processor, is a CPU design where the instruction set includes operations that can perform mathematical operations on multiple data The Cray-1 was a Supercomputer designed by a team including Seymour Cray for Cray Research.

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 where A, B, and C are each 64-element vectors of 64-bit floating-point numbers. In Computing, floating point describes a system for numerical representation in which a string of digits (or Bits represents a Real number. "^[35] They are closely related to Flynn's SIMD classification. ^[35]

Cray computers became famous for their vector-processing computers in the 1970s and 1980s. Cray Inc ( is a Supercomputer manufacturer based in Seattle Washington. 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). 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, IBM and Freescale Semiconductor S treaming '''S'''IMD E xtensions ( SSE) is a SIMD (Single Instruction Multiple Data Instruction set extension to the X86

Software

Parallel programming languages

Main article: parallel programming model

Concurrent programming languages, libraries, APIs, and parallel programming models have been created for programming parallel computers. 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, a library is a collection of Subroutines used to develop Software. A parallel programming model is a set of software technologies to express Parallel algorithms and match applications with the underlying parallel systems 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. In Computer science, message passing is a form of communication used in Parallel computing, Object-oriented programming, and Interprocess communication 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. POSIX Threads is a POSIX standard for threads The standard defines an API for creating and manipulating threads The OpenMP (Open Multi-Processing is an Application programming interface (API that supports multi-platform Shared memory Multiprocessing programming Message Passing Interface ( MPI) is a specification for an API that allows many computers to communicate with one another 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. In Computer science, futures and promises are closely related constructs used for synchronization in some concurrent programming languages

Automatic parallelization

Main article: Automatic parallelization

Automatic parallelization of a sequential program by a compiler is the "holy grail" of parallel computing. Automatic parallelization, also auto parallelization, autoparallelization, parallelization, or //ization (shorthand the last two of which imply A compiler is a Computer program (or set of programs that translates text written in a computer language (the source language) into another According to Christian mythology, the Holy Grail was the dish plate or cup used by Jesus at the Last Supper, said to possess miraculous powers Despite decades of work by compiler researchers, automatic parallelization has had only limited success. ^[36]

Mainstream parallel programming languages remain either explicitly parallel or (at best) partially implicit, in which a programmer gives the compiler directives for parallelization. In Computer programming, explicit parallelism is the representationof concurrent computations by means of primitivesin 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 In Computer programming, the term directive is applied in a variety of ways that are similar to the term command, it is also used to describe some Programming 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. 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

Main article: Application checkpointing

The larger and more complex a computer, the more that can go wrong and the shorter the mean time between failures. Checkpointing is a technique for inserting Fault tolerance into Computing systems Mean time between failures (MTBF is the Mean (average time between Failures of a system and is often considered the "useful life" of the device i 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. Checkpointing is a technique for inserting Fault tolerance into Computing systems 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 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. 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). Bioinformatics is the application of information technology to the field of molecular biology Protein folding is the physical process by which a Polypeptide folds into its characteristic and functional three-dimensional structure. Mathematical finance is the branch of Applied mathematics concerned with the Financial markets. Common types of problems found in parallel computing applications are^[37]:

• Dense linear algebra
• Sparse linear algebra
• Spectral methods (such as Cooley-Tukey Fast Fourier transform)
• N-body problems (such as Barnes-Hut simulation)
• Structured grid problems (such as Lattice Boltzmann methods),
• Unstructured grid problems (such as found in finite element analysis)
• Monte Carlo simulation
• Combinational logic (such as brute-force cryptographic techniques)
• Graph traversal (such as Sorting algorithms)
• Dynamic programming
• Branch and bound methods
• Graphical models (such as detecting Hidden Markov models and constructing Bayesian networks)
• Finite State Machine simulation

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. Linear algebra is the branch of Mathematics concerned with The Cooley-Tukey Algorithm, named after JW Cooley and John Tukey, is the most common Fast Fourier transform (FFT algorithm An N -body simulation is a simulation of massive particles under the influence of physical forces usually gravity and sometimes other forces The Barnes-Hut simulation is an Algorithm for performing an N-body simulation. A regular grid is a Tessellation of the Euclidean plane by congruent rectangles or a space-filling tessellation of rectilinear Parallelepipeds Lattice Boltzmann methods (LBM is a class of Computational fluid dynamics (CFD methods for fluid simulation An unstructured grid is a Tessellation of a part of the Euclidean plane or Euclidean space by simple shapes such as Triangles or tetrahedra Monte Carlo methods are a class of Computational Algorithms that rely on repeated Random sampling to compute their results In Digital circuit theory combinational logic (also called combinatorial logic) is a type of logic circuit whose output is a Pure function of the In Cryptanalysis, a brute force attack is a method of defeating a Cryptographic scheme by trying a large number of possibilities for example possible keys 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 Branch and bound (BB is a general Algorithm for finding optimal solutions of various optimization problems especially in discrete and Combinatorial In Probability theory, Statistics, and Machine learning, a graphical model (GM is a graph that represents independencies among Random variables 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 A Bayesian network (or a belief network) is a Probabilistic graphical model that represents a set of Variables and their probabilistic independencies The history of Computing is longer than the History of computing hardware and modern computing technology and includes the history of methods intended for ILLIAC IV was one of the most infamous Supercomputers ever in a series of research machines ILLIACs, from the University of Illinois. Federico Luigi Conte Menabrea Marquis of Valdora ( September 4, 1809 &ndash May 24, 1896) was an Italian general and Statesman 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 "^[38][39] IBM introduced the 704 in 1954, through a project in which Gene Amdahl was one of the principal architects. International Business Machines Corporation abbreviated IBM and nicknamed "Big Blue", is a multinational Computer Technology Gene Myron Amdahl (born November 16, 1922) is a Norwegian American computer architect and hi-tech entrepreneur chiefly known for his work on It became the first commercially available computer to use fully automatic floating point arithmetic commands. In Computing, floating point describes a system for numerical representation in which a string of digits (or Bits represents a Real number. ^[40] In 1958, IBM researchers John Cocke and Daniel Slotnick discussed the use of parallelism in numerical calculations for the first time. John Cocke ( May 30 1925 – July 16, 2002) was an American Computer scientist recognised for his large contribution to Computer ^[41] Burroughs Corporation introduced the D825 in 1962, a four-processor computer that accessed up to 16 memory modules through a crossbar switch. The Burroughs Corporation began in 1886 as the American Arithmometer Company in St A crossbar switch (also known as cross-point switch, crosspoint switch, or matrix switch) is a Switch connecting multiple inputs to multiple ^[42] In 1967, Amdahl and Slotnick published a debate about the feasibility of parallel processing at American Federation of Information Processing Societies Conference. ^[41] It was during this debate that Amdahl's Law was coined to define the limit of speed-up due to parallelism.

In 1969, US company Honeywell introduced its first Multics system, a symmetric multiprocessor system capable of running up to eight processors in parallel. Honeywell ( is a major American multinational conglomerate company that produces a variety of consumer products engineering services and aerospace systems ^[41] C.mmp, a 1970s multi-processor project at Carnegie Mellon University, was "among the first multiprocessors with more than a few processors". The Cmmp was an early MIMD multiprocessor system developed at Carnegie Mellon University by William Wulf (1971 Carnegie Mellon University (also known as CMU) is a private Research University in Pittsburgh, Pennsylvania, United ^[39] "The first bus-connected multi-processor with snooping caches was the Synapse N+1 in 1984. "^[39]

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. Networking Propagation delay is defined as how long it takes for a certain amount of bytes to transfered over a medium A control unit in general is a central (or sometimes distributed but clearly distinguishable part of whatsoever machinery that controls its operation provided that ^[43] In 1964, Slotnick had proposed building a massively parallel computer for the Lawrence Livermore National Laboratory. The Lawrence Livermore National Laboratory ( LLNL) in Livermore California is a scientific research laboratory founded by the University of California in 1952 ^[41] His design was funded by the US Air Force, which was the earliest SIMD parallel-computing effort, ILLIAC IV. ILLIAC IV was one of the most infamous Supercomputers ever in a series of research machines ILLIACs, from the University of Illinois. ^[41] 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. A vector processor, or array processor, is a CPU design where the instruction set includes operations that can perform mathematical operations on multiple data 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. ^[44] 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. The Cray-1 was a Supercomputer designed by a team including Seymour Cray for Cray Research.

References

External links

• Parallel computing at the Open Directory Project
• Lawrence Livermore National Laboratory: Introduction to Parallel Computing
• Designing and Building Parallel Programs, by Ian Foster
• Internet Parallel Computing Archive
• Parallel processing topic area at IEEE Distributed Computing Online
• Parallel Computing Works Free On-line Book
• Frontiers of Supercomputing Free On-line Book Covering topics like algorithms and industrial applications