Content deleted Content added
mNo edit summary |
Citation bot (talk | contribs) Removed URL that duplicated identifier. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox | #UCB_webform_linked 17/967 |
||
| (642 intermediate revisions by more than 100 users not shown) | |||
Line 1:
{{redirect|Parallelization|parallelization of manifolds|Parallelization (mathematics)}}
{{short description|Programming paradigm in which many processes are executed simultaneously}}
[[File:IBM Blue Gene P supercomputer.jpg|thumb|300px|Large [[Supercomputer|supercomputers]] such as IBM's [[Blue Gene|Blue Gene/P]] are designed to heavily exploit parallelism. ]]
'''Parallel computing''' is a type of [[computing|computation]] in which many calculations or [[Process (computing)|process]]es are carried out simultaneously.<ref>{{cite book |last=Gottlieb |first=Allan |url=http://dl.acm.org/citation.cfm?id=160438 |title=Highly parallel computing |author2=Almasi, George S. |publisher=Benjamin/Cummings |year=1989 |isbn=978-0-8053-0177-9 |___location=Redwood City, Calif. |language=en-US}}</ref> Large problems can often be divided into smaller ones, which can then be solved at the same time. There are several different forms of parallel computing: [[Bit-level parallelism|bit-level]], [[Instruction-level parallelism|instruction-level]], [[Data parallelism|data]], and [[task parallelism]]. Parallelism has long been employed in [[high-performance computing]], but has gained broader interest due to the physical constraints preventing [[frequency scaling]].<ref name=":0">S.V. Adve ''et al.'' (November 2008). [https://graphics.cs.illinois.edu/sites/default/files/upcrc-wp.pdf "Parallel Computing Research at Illinois: The UPCRC Agenda"] {{webarchive|url=https://web.archive.org/web/20180111165735/https://graphics.cs.illinois.edu/sites/default/files/upcrc-wp.pdf |date=2018-01-11 }} (PDF). Parallel@Illinois, University of Illinois at Urbana-Champaign. "The main techniques for these performance benefits—increased clock frequency and smarter but increasingly complex architectures—are now hitting the so-called power wall. The [[computer industry]] has accepted that future performance increases must largely come from increasing the number of processors (or cores) on a die, rather than making a single core go faster."</ref> As power consumption (and consequently heat generation) by computers has become a concern in recent years,<ref>[[Krste Asanović|Asanovic]] ''et al.'' Old [conventional wisdom]: Power is free, but [[transistor]]s are expensive. New [conventional wisdom] is [that] power is expensive, but transistors are "free".</ref> parallel computing has become the dominant paradigm in [[computer architecture]], mainly in the form of [[multi-core processor]]s.<ref name="View-Power">[[Asanovic, Krste]] ''et al.'' (December 18, 2006). [http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-183.pdf "The Landscape of Parallel Computing Research: A View from Berkeley"] (PDF). University of California, Berkeley. Technical Report No. UCB/EECS-2006-183. "Old [conventional wisdom]: Increasing clock frequency is the primary method of improving processor performance. New [conventional wisdom]: Increasing parallelism is the primary method of improving processor performance… Even representatives from Intel, a company generally associated with the 'higher clock-speed is better' position, warned that traditional approaches to maximizing performance through maximizing clock speed have been pushed to their limits."</ref>
[[File:Parallelism_vs_concurrency.png|thumb|Parallelism vs concurrency]]
In [[computer science]], '''parallelism''' and concurrency are two different things: a parallel program uses [[Multi-core processor|multiple CPU cores]], each core performing a task independently. On the other hand, concurrency enables a program to deal with multiple tasks even on a single CPU core; the core switches between tasks (i.e. [[Thread (computing)|threads]]) without necessarily completing each one. A program can have both, neither or a combination of parallelism and concurrency characteristics.<ref>{{Cite book |title=Parallel and Concurrent Programming in Haskell |publisher=O'Reilly Media |year=2013 |isbn=9781449335922}}</ref>
Parallel computers can be roughly classified according to the level at which the hardware supports parallelism, with multi-core and [[Symmetric multiprocessing|multi-processor]] computers having multiple [[processing element]]s within a single machine, while [[Computer cluster|clusters]], [[Massively parallel (computing)|MPPs]], and [[Grid computing|grids]] use multiple computers to work on the same task. Specialized parallel computer architectures are sometimes used alongside traditional processors, for accelerating specific tasks.
In some cases parallelism is transparent to the programmer, such as in bit-level or instruction-level parallelism, but explicitly [[parallel algorithm]]s, particularly those that use concurrency, are more difficult to write than [[sequential algorithm|sequential]] ones,<ref>{{cite book|last=Hennessy|first=John L.|author-link=John L. Hennessy|title=Computer organization and design: the hardware/software interface|year=1999|publisher=Kaufmann|___location=San Francisco|isbn=978-1-55860-428-5|edition=2. ed., 3rd print.|author2=Patterson, David A.|author-link2=David Patterson (computer scientist)|author3=Larus, James R.|author-link3=James Larus|url=https://archive.org/details/computerorganiz000henn}}</ref> because concurrency introduces several new classes of potential [[software bug]]s, of which [[race condition]]s are the most common. [[Computer networking|Communication]] and [[Synchronization (computer science)|synchronization]] between the different subtasks are typically some of the greatest obstacles to getting optimal parallel program performance.
A theoretical [[upper bound]] on the [[Speedup|speed-up]] of a single program as a result of parallelization is given by [[Amdahl's law]], which states that it is limited by the fraction of time for which the parallelization can be utilised.
{{TOC limit|limit=4}}
==Background==
Traditionally, [[computer software]] has been written for [[serial computation]]. To solve a problem, an [[algorithm]] is constructed and implemented as a serial stream of instructions. These instructions are executed on a [[central processing unit]] on one computer. Only one instruction may execute at a time—after that instruction is finished, the next one is executed.<ref name="llnltut">{{cite web |author=Barney, Blaise |title=Introduction to Parallel Computing |url=http://www.llnl.gov/computing/tutorials/parallel_comp/ |access-date=2007-11-09 |publisher=Lawrence Livermore National Laboratory |language=en-US}}</ref>
Parallel computing, on the other hand, uses multiple processing elements simultaneously to solve a problem. This is accomplished by breaking the problem into independent parts so that each processing element can execute its part of the algorithm simultaneously with the others. The processing elements can be diverse and include resources such as a single computer with multiple processors, several networked computers, specialized hardware, or any combination of the above.<ref name="llnltut" /> Historically parallel computing was used for scientific computing and the simulation of scientific problems, particularly in the natural and [[engineering sciences]], such as [[meteorology]]. This led to the design of parallel hardware and software, as well as [[high performance computing]].<ref>{{Cite book|title=Parallel Programming: for Multicore and Cluster Systems|author=Thomas Rauber |author2=Gudula Rünger|publisher=Springer Science & Business Media|year=2013|isbn=9783642378010|page=1}}</ref>
[[Frequency scaling]] was the dominant reason for improvements in [[computer performance]] from the mid-1980s until 2004. The [[Run time (program lifecycle phase)|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 [[CPU bound|compute-bound]] programs.<ref>{{cite book|last=Hennessy|first=John L.|title=Computer architecture / a quantitative approach.|year=2002|publisher=International Thomson|___location=San Francisco, Calif.|isbn=978-1-55860-724-8|edition=3rd|author2=Patterson, David A.|page=43}}</ref> However, power consumption ''P'' by a chip is given by the equation ''P'' = ''C'' × ''V'' <sup>2</sup> × ''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).<ref>{{cite book|last=Rabaey|first=Jan M.|title=Digital integrated circuits : a design perspective|year=1996|publisher=Prentice-Hall|___location=Upper Saddle River, N.J.|isbn=978-0-13-178609-7|page=235}}</ref> Increases in frequency increase the amount of power used in a processor. Increasing processor power consumption led ultimately to [[Intel]]'s May 8, 2004 cancellation of its [[Tejas and Jayhawk]] processors, which is generally cited as the end of frequency scaling as the dominant computer architecture paradigm.<ref>{{cite news|last=Flynn|first=Laurie J.|title=Intel Halts Development Of 2 New Microprocessors|url=https://www.nytimes.com/2004/05/08/business/08chip.html?ex=1399348800&en=98cc44ca97b1a562&ei=5007|access-date=5 June 2012|newspaper=New York Times|date=8 May 2004}}</ref>
To deal with the problem of power consumption and overheating the major [[central processing unit]] (CPU or processor) manufacturers started to produce power efficient processors with multiple cores. The core is the computing unit of the processor and in multi-core processors each core is independent and can access the same memory concurrently. [[Multi-core processor]]s have brought parallel computing to [[desktop computers]]. Thus parallelization of serial programs has become a mainstream programming task. In 2012 quad-core processors became standard for [[desktop computers]], while [[Server (computing)|servers]] had 10+ core processors. By 2023 some processors had over hundred cores. Some designs having a mix of performance and efficiency cores (such as [[ARM big.LITTLE|ARM's big.LITTLE]] design) due to thermal and design constraints.<ref>{{Cite book|title=Parallel Programming: for Multicore and Cluster Systems|author=Thomas Rauber |author2=Gudula Rünger|publisher=Springer Science & Business Media|year=2013|isbn=9783642378010|page=2}}</ref>{{Citation needed|date=March 2023}} From [[Moore's law]] it can be predicted that the number of cores per processor will double every 18–24 months.
An [[operating system]] can ensure that different tasks and user programs are run in parallel on the available cores. However, for a serial software program to take full advantage of the multi-core architecture the programmer needs to restructure and parallelize the code. A speed-up of application software runtime will no longer be achieved through frequency scaling, instead programmers will need to parallelize their software code to take advantage of the increasing computing power of multicore architectures.<ref>{{Cite book|title=Parallel Programming: for Multicore and Cluster Systems|author=Thomas Rauber |author2=Gudula Rünger|publisher=Springer Science & Business Media|year=2013|isbn=9783642378010|page=3}}</ref>
=== Relevant laws ===
[[File:AmdahlsLaw.svg|right|thumbnail|300px|A graphical representation of [[Amdahl's law]]. The law demonstrates the theoretical maximum [[speedup]] of an overall system and the concept of diminishing returns. If exactly 50% of the work can be parallelized, the best possible speedup is 2 times. If 95% of the work can be parallelized, the best possible speedup is 20 times. According to the law, even with an infinite number of processors, the speedup is constrained by the unparallelizable portion.]]
[[File:Optimizing-different-parts.svg|thumb|300px|Assume that a task has two independent parts, ''A'' and ''B''. Part ''B'' takes roughly 25% of the time of the whole computation. By working very hard, one may be able to make this part 5 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 part ''B'''s speedup is greater by ratio, (5 times versus 2 times).]]
Main article: [[Amdahl's law]]
Optimally, the [[speedup]] from parallelization would be linear—doubling the number of processing elements should halve the runtime, and doubling it a second time should again halve the runtime. However, very few parallel algorithms achieve optimal speedup. Most of them have a near-linear speedup for small numbers of processing elements, which flattens out into a constant value for large numbers of processing elements.
The maximum potential speedup of an overall system can be calculated by [[Amdahl's law]].<ref name=":02">{{Citation |last=Bakos |first=Jason D. |title=Chapter 2 - Multicore and data-level optimization: OpenMP and SIMD |date=2016-01-01 |work=Embedded Systems |pages=49–103 |editor-last=Bakos |editor-first=Jason D. |url=https://linkinghub.elsevier.com/retrieve/pii/B978012800342800002X |access-date=2024-11-18 |place=Boston |publisher=Morgan Kaufmann |doi=10.1016/b978-0-12-800342-8.00002-x |isbn=978-0-12-800342-8|url-access=subscription }}</ref> Amdahl's Law indicates that optimal performance improvement is achieved by balancing enhancements to both parallelizable and non-parallelizable components of a task. Furthermore, it reveals that increasing the number of processors yields diminishing returns, with negligible speedup gains beyond a certain point. <ref>{{Cite book |title=The Art of Multiprocessor Programming, Revised Reprint |date=22 May 2012 |publisher=Morgan Kaufmann |isbn=9780123973375}}</ref><ref>{{Cite book |title=Programming Many-Core Chips |isbn=9781441997395 |last1=Vajda |first1=András |date=10 June 2011 |publisher=Springer}}</ref>
Amdahl's Law has limitations, including assumptions of fixed workload, neglecting [[inter-process communication]] and [[Synchronization (computer science)|synchronization]] overheads, primarily focusing on computational aspect and ignoring extrinsic factors such as data persistence, I/O operations, and memory access overheads.<ref>{{Cite book |last=Amdahl |first=Gene M. |chapter=Validity of the single processor approach to achieving large scale computing capabilities |date=1967-04-18 |title=Proceedings of the April 18-20, 1967, spring joint computer conference on - AFIPS '67 (Spring) |chapter-url=https://dl.acm.org/doi/10.1145/1465482.1465560 |___location=New York, NY, USA |publisher=Association for Computing Machinery |pages=483–485 |doi=10.1145/1465482.1465560 |isbn=978-1-4503-7895-6}}</ref><ref name=":1">{{Cite book |title=Computer Architecture: A Quantitative Approach |date=2003 |publisher=Morgan Kaufmann |isbn=978-8178672663}}</ref><ref>{{Cite book |title=Parallel Computer Architecture A Hardware/Software Approach |date=1999 |publisher=Elsevier Science |isbn=9781558603431}}</ref>
[[Gustafson's law]] and [[Neil J. Gunther#Universal Scalability Law|Universal Scalability Law]] give a more realistic assessment of the parallel performance.<ref>{{cite book |last1=McCool |first1=Michael |title=Structured Parallel Programming: Patterns for Efficient Computation |last2=Reinders |first2=James |last3=Robison |first3=Arch |publisher=Elsevier |year=2013 |isbn=978-0-12-415993-8 |pages=61}}</ref><ref>{{Cite book |last=Gunther |first=Neil |title=Guerrilla Capacity Planning: A Tactical Approach to Planning for Highly Scalable Applications and Services |year=2007 |isbn=978-3540261384}}</ref>[[File:Gustafson.png|thumb|right|300px|A graphical representation of [[Gustafson's law]]]]
===Dependencies===
Understanding [[data dependency|data dependencies]] is fundamental in implementing [[parallel algorithm]]s. No program can run more quickly than the longest chain of dependent calculations (known as the [[Critical path method|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''<sub>''i''</sub> and ''P''<sub>''j''</sub> be two program segments. Bernstein's conditions<ref>{{cite journal|last=Bernstein|first=Arthur J.|title=Analysis of Programs for Parallel Processing|journal=IEEE Transactions on Electronic Computers|date=1 October 1966|volume=EC-15|issue=5|pages=757–763|doi=10.1109/PGEC.1966.264565}}</ref> describe when the two are independent and can be executed in parallel. For ''P''<sub>''i''</sub>, let ''I''<sub>''i''</sub> be all of the input variables and ''O''<sub>''i''</sub> the output variables, and likewise for ''P''<sub>''j''</sub>. ''P''<sub>''i''</sub> and ''P''<sub>''j''</sub> are independent if they satisfy
: <math>O_i \cap O_j = \varnothing.</math>
Violation of the first condition introduces a flow dependency, corresponding to the first
Consider the following functions, which demonstrate several kinds of dependencies:
1: function Dep(a, b)
2:
3:
4: end function
1: function NoDep(a, b)
2:
3:
4:
5: end function
In this example, there are no dependencies between the instructions, so they can all be run in parallel.
===Race conditions, mutual exclusion, synchronization, and parallel slowdown===
Subtasks in a parallel program are often called [[Thread (computing)|threads]]. Some parallel computer architectures use smaller, lightweight versions of threads known as [[Fiber (computer science)|fibers]], while others use bigger versions known as [[Process (computing)|processes]]. However, "threads" is generally accepted as a generic term for subtasks.<ref>{{cite web
| url = https://msdn.microsoft.com/en-us/library/windows/desktop/ms684841(v=vs.85).aspx
| title = Processes and Threads
| date = 2018
| website = Microsoft Developer Network
| publisher = Microsoft Corp.
| access-date = 2018-05-10
}}</ref> Threads will often need [[Synchronization (computer science)|synchronized]] access to an [[Object (computer science)|object]] or other [[Resource management (computing)|resource]], for example when they must update a [[Variable (programming)|variable]] that is shared between them. Without synchronization, the instructions between the two threads may be interleaved in any order. For example, consider the following program:
{| class="wikitable"
|-
|-
|1A: Read variable V
Line 84 ⟶ 91:
|2B: Add 1 to variable V
|-
|3A: Write back to variable V
|3B: Write back to variable V
|}
If instruction 1B is executed between 1A and 3A, or if instruction 1A is executed between 1B and 3B, the program will produce incorrect data. This is known as a [[race condition]]. The programmer must use a [[Lock (computer science)|lock]] to provide [[mutual exclusion]]. A lock is a programming language construct that allows one thread to take control of a variable and prevent other threads from reading or writing it, until that variable is unlocked. The thread holding the lock is free to execute its [[critical section]] (the section of a program that requires exclusive access to some variable), and to unlock the data when it is finished. Therefore, to guarantee correct program execution, the above program can be rewritten to use locks:
{| class="wikitable"
|-
|-
|1A: Lock variable V
Line 104 ⟶ 111:
|3B: Add 1 to variable V
|-
|4A: Write back to variable V
|4B: Write back to variable V
|-
|5A: Unlock variable V
Line 111 ⟶ 118:
|}
One thread will successfully lock variable V, while the other thread will be [[Software lockout|locked out]]—unable to proceed until V is unlocked again. This guarantees correct execution of the program. Locks
| url = http://www.developforperformance.com/ThreadSafetyForPerformance.html
| title = Thread Safety for Performance
| last = Krauss
| first = Kirk J
| date = 2018
| website = Develop for Performance
| access-date = 2018-05-10
| archive-date = 2018-05-13
| archive-url = https://web.archive.org/web/20180513081315/http://www.developforperformance.com/ThreadSafetyForPerformance.html
| url-status = dead
}}</ref>
Locking multiple variables using [[Atomic operation|non-atomic]] locks introduces the possibility of program [[Deadlock (computer science)|deadlock]]. An [[atomic lock]] locks multiple variables all at once. If it cannot lock all of them, it does not lock any of them. If two threads each need to lock the same two variables using non-atomic locks, it is possible that one thread will lock one of them and the second thread will lock the second variable. In such a case, neither thread can complete, and deadlock results.<ref>{{cite book
| url = http://www.informit.com/articles/article.aspx?p=25193
| title = Introduction to Operating System Deadlocks
| last = Tanenbaum
| first = Andrew S.
| date = 2002-02-01
| website = Informit
| publisher = Pearson Education, Informit
| access-date = 2018-05-10
}}</ref>
Many parallel programs require that their subtasks [[Synchronization (computer science)|act in synchrony]]. This requires the use of a [[barrier (computer science)|barrier]]. Barriers are typically implemented using a
| url = https://www.embedded.com/design/operating-systems/4440752/Synchronization-internals----the-semaphore
| title = Synchronization internals – the semaphore
| last = Cecil
| first = David
| date = 2015-11-03
| website = Embedded
| publisher = AspenCore
| access-date = 2018-05-10
}}</ref> One class of algorithms, known as [[lock-free and wait-free algorithms]], altogether avoids the use of locks and barriers. However, this approach is generally difficult to implement and requires correctly designed data structures.<ref>{{cite web
| url = http://preshing.com/20120612/an-introduction-to-lock-free-programming/
| title = An Introduction to Lock-Free Programming
| last = Preshing
| first = Jeff
| date = 2012-06-08
| website = Preshing on Programming
| access-date = 2018-05-10
}}</ref>
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
| url = https://stackoverflow.com/questions/806569/whats-the-opposite-of-embarrassingly-parallel
| title = What's the opposite of "embarrassingly parallel"?
| website = StackOverflow
| access-date = 2018-05-10
}}</ref><ref>{{cite web
| url = https://stackoverflow.com/questions/1970345/what-is-thread-contention
| title = What is thread contention?
| last = Schwartz
| first = David
| date = 2011-08-15
| website = StackOverflow
| access-date = 2018-05-10
}}</ref> Once the overhead from resource contention or communication dominates the time spent on other computation, further parallelization (that is, splitting the workload over even more threads) increases rather than decreases the amount of time required to finish. This problem, known as [[parallel slowdown]],<ref>{{cite web
| url = https://software.intel.com/en-us/blogs/2008/03/04/why-a-simple-test-can-get-parallel-slowdown
| title = Why a simple test can get parallel slowdown
| last = Kukanov
| first = Alexey
| date = 2008-03-04
| access-date = 2015-02-15
}}</ref> can be improved in some cases by software analysis and redesign.<ref>{{cite web
| url = http://www.developforperformance.com/ThreadingForPerformance.html
| title = Threading for Performance
| last = Krauss
| first = Kirk J
| date = 2018
| website = Develop for Performance
| access-date = 2018-05-10
| archive-date = 2018-05-13
| archive-url = https://web.archive.org/web/20180513081501/http://www.developforperformance.com/ThreadingForPerformance.html
| url-status = dead
}}</ref>
===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
===Flynn's taxonomy===
{{Main|Flynn's taxonomy}}
[[Michael J. Flynn]] created one of the earliest classification systems for parallel (and sequential) computers and programs, now known as [[Flynn's taxonomy]]. Flynn classified programs and computers by whether they were operating using a single set or multiple sets of instructions, and whether or not those instructions were using a single set or multiple sets of data.
{{Flynn's taxonomy}}
The single-instruction-single-data (SISD) classification is equivalent to an entirely sequential program. The single-instruction-multiple-data (SIMD) classification is analogous to doing the same operation repeatedly over a large data set. This is commonly done in [[signal processing]] applications. Multiple-instruction-single-data (MISD) is a rarely used classification. While computer architectures to deal with this were devised (such as [[systolic array]]s), few applications that fit this class materialized. Multiple-instruction-multiple-data (MIMD) programs are by far the most common type of parallel programs.
Line 143 ⟶ 207:
According to [[David A. Patterson (scientist)|David A. Patterson]] and [[John L. Hennessy]], "Some machines are hybrids of these categories, of course, but this classic model has survived because it is simple, easy to understand, and gives a good first approximation. It is also—perhaps because of its understandability—the most widely used scheme."<ref>Patterson and Hennessy, p. 748.</ref>
== Disadvantages ==
Parallel computing can incur significant overhead in practice, primarily due to the costs associated with merging data from multiple processes. Specifically, inter-process communication and synchronization can lead to overheads that are substantially higher—often by two or more orders of magnitude—compared to processing the same data on a single thread. <ref>{{Cite book |title=Operating System Concepts |isbn=978-0470128725 |last1=Silberschatz |first1=Abraham |last2=Galvin |first2=Peter B. |last3=Gagne |first3=Greg |date=29 July 2008 |publisher=Wiley }}</ref><ref>{{Cite book |title=Computer Organization and Design MIPS Edition: The Hardware/Software Interface (The Morgan Kaufmann Series in Computer Architecture and Design) |date=2013 |publisher=Morgan Kaufmann |isbn=978-0124077263}}</ref><ref>{{Cite book |title=Parallel Programming: Techniques and Applications Using Networked Workstations and Parallel Computers |date=2005 |publisher=Pearson |isbn=978-0131405639}}</ref> Therefore, the overall improvement should be carefully evaluated.
==Granularity==
===Bit-level parallelism===
{{main|Bit-level parallelism}}
[[File:Taiwania 3 Supercomputer.jpg|thumb|Taiwania 3 of [[Taiwan]], a parallel supercomputing device that joined [[COVID-19]] research]]
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 [[Word (data type)|computer word size]]—the amount of information the processor can manipulate per cycle.<ref>{{cite book|last=Singh|first=David Culler; J.P.|title=Parallel computer architecture|year=1997|publisher=Morgan Kaufmann Publ.|___location=San Francisco|isbn=978-1-55860-343-1|page=15|edition=[Nachdr.]}}</ref> 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 computing|8-bit]] processor must add two [[16-bit computing|16-bit]] [[integer]]s, 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.
Historically, [[4-bit computing|4-bit]] microprocessors were replaced with 8-bit, then 16-bit, then 32-bit microprocessors. This trend generally came to an end with the introduction of 32-bit processors, which has been a standard in general-purpose computing for two decades. Not until
===Instruction-level parallelism===
{{main|Instruction
[[File:Nopipeline.png|thumb|300px|A canonical processor without [[Instruction pipelining|pipeline]]. It takes five clock cycles to complete one instruction and thus the processor can issue subscalar performance ({{nobreak|1=IPC = 0.2 < 1}}).]]
A computer program is, in essence, a stream of instructions executed by a processor. Without instruction-level parallelism, a processor can only issue less than one [[Instructions per cycle|instruction per clock cycle]] ({{nobreak|IPC < 1}}). These processors are known as ''subscalar'' processors. These instructions can be [[Out-of-order execution|re-ordered]] and combined into groups which are then executed in parallel without changing the result of the program. This is known as instruction-level parallelism. Advances in instruction-level parallelism dominated computer architecture from the mid-1980s until the mid-1990s.<ref>Culler et al. p. 15.</ref>
[[File:Fivestagespipeline.png|thumb|300px|A canonical five-stage [[Instruction pipelining|pipelined]] processor. In the best case scenario, it takes one clock cycle to complete one instruction and thus the processor can issue scalar performance ({{nobreak|1=IPC = 1}}).]]
All modern processors have multi-stage [[Instruction pipelining|instruction pipelines]]. Each stage in the pipeline corresponds to a different action the processor performs on that instruction in that stage; a processor with an ''N''-stage pipeline can have up to ''N'' different instructions at different stages of completion and thus can issue one instruction per clock cycle ({{nobreak|1=IPC = 1}}). These processors are known as ''scalar'' processors. 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). The [[Pentium 4]] processor had a 35-stage pipeline.<ref>[[Yale Patt|Patt, Yale]] (April 2004). "[http://users.ece.utexas.edu/~patt/Videos/talk_videos/cmu_04-29-04.wmv The Microprocessor Ten Years From Now: What Are The Challenges, How Do We Meet Them?] {{webarchive|url=https://web.archive.org/web/20080414141000/http://users.ece.utexas.edu/~patt/Videos/talk_videos/cmu_04-29-04.wmv |date=2008-04-14 }} (wmv). Distinguished Lecturer talk at [[Carnegie Mellon University]]. Retrieved on November 7, 2007.</ref>
[[File:Superscalarpipeline.svg|thumb|300px|A canonical five-stage [[Instruction pipelining|pipelined]] processor with two execution units. In the best case scenario, it takes one clock cycle to complete two instructions and thus the processor can issue superscalar performance ({{nobreak|1=IPC = 2 > 1}}).]]
Most modern processors also have multiple [[execution unit]]s. They usually combine this feature with pipelining and thus can issue more than one instruction per clock cycle ({{nobreak|IPC > 1}}). These processors are known as ''[[superscalar]]'' processors. Superscalar processors differ from [[multi-core processor]]s in that the several execution units are not entire processors (i.e. processing units). Instructions can be grouped together only if there is no [[data dependency]] between them. [[Scoreboarding]] and the [[Tomasulo algorithm]] (which is similar to scoreboarding but makes use of [[register renaming]]) are two of the most common techniques for implementing out-of-order execution and instruction-level parallelism.
===Task parallelism===
{{main|Task parallelism}}
Task
===Superword level parallelism===
Superword level parallelism is a [[Automatic vectorization|vectorization]] technique based on [[loop unwinding|loop unrolling]] and basic block vectorization. It is distinct from loop vectorization algorithms in that it can exploit [[Parallelism (computing)|parallelism]] of [[inline code]], such as manipulating coordinates, color channels or in loops unrolled by hand.<ref>{{cite web|title=Exploiting Superword Level Parallelism with Multimedia Instruction Sets|url=http://groups.csail.mit.edu/cag/slp/SLP-PLDI-2000.pdf|author=Samuel Larsen|author2=Saman Amarasinghe }}</ref>
==Hardware==
===Memory and communication===
Main memory in a parallel computer is either [[Shared memory (interprocess communication)|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).<ref name=PH713>Patterson and Hennessy, p. 713.</ref> 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]] 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. Accesses to local memory are typically faster than accesses to non-local memory. On the [[supercomputers]], distributed shared memory space can be implemented using the programming model such as [[Partitioned global address space|PGAS]]. This model allows processes on one compute node to transparently access the remote memory of another compute node. 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.
[[
Computer architectures in which each element of main memory can be accessed with equal [[Memory latency|latency]] and [[Bandwidth (computing)|bandwidth]] are known as [[
Computer systems make use of [[CPU cache|cache]]s—small
Processor–processor and processor–memory communication can be implemented in hardware in several ways, including via shared (either multiported or [[Multiplexing|multiplexed]]) memory, a [[crossbar switch]], a shared [[Bus (computing)|bus]] or an interconnect network of a myriad of [[
Parallel computers based on
===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.
====
{{main|Multi-core
A
[[Simultaneous multithreading]] (of which Intel's [[
====Symmetric multiprocessing====
{{main|Symmetric multiprocessing}}
A symmetric multiprocessor (SMP) is a computer system with multiple identical processors that share memory and connect via a [[bus (computing)|bus]].<ref name=HP549>Hennessy and Patterson, p. 549.</ref> [[Bus contention]] prevents bus architectures from scaling. As a result, SMPs generally do not comprise more than 32 processors.<ref>Patterson and Hennessy, p. 714.</ref>
====Distributed computing====
{{main|Distributed computing}}
A distributed computer (also known as a distributed memory multiprocessor) is a distributed memory computer system in which the processing elements are connected by a network. Distributed computers are highly scalable. The terms "[[concurrent computing]]", "parallel computing", and "distributed computing" have a lot of overlap, and no clear distinction exists between them.<ref>[[Distributed computing#CITEREFGhosh2007|Ghosh (2007)]], p. 10. [[Distributed computing#CITEREFKeidar2008|Keidar (2008)]].</ref> The same system may be characterized both as "parallel" and "distributed"; the processors in a typical distributed system run concurrently in parallel.<ref>[[Distributed computing#CITEREFLynch1996|Lynch (1996)]], p. xix, 1–2. [[Distributed computing#CITEREFPeleg2000|Peleg (2000)]], p. 1.</ref>
=====Cluster computing=====
{{main|Computer cluster}}
[[File:Beowulf.jpg|right|thumbnail|upright|A [[Beowulf (computing)|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.<ref>[http://www.webopedia.com/TERM/c/clustering.html What is clustering?] Webopedia computer dictionary. Retrieved on November 7, 2007.</ref> Clusters are composed of multiple standalone machines connected by a network. While machines in a cluster do not have to be symmetric, [[Load balancing (computing)|load balancing]] is more difficult if they are not. The most common type of cluster is the [[Beowulf (computing)|Beowulf cluster]], which is a cluster implemented on multiple identical [[commercial off-the-shelf]] computers connected with a [[TCP/IP]] [[Ethernet]] [[local area network]].<ref>[https://www.pcmag.com/encyclopedia_term/0,2542,t=Beowulf&i=38548,00.asp Beowulf definition.] {{Webarchive|url=https://web.archive.org/web/20121010215231/https://www.pcmag.com/encyclopedia_term/0%2C2542%2Ct%3DBeowulf%26i%3D38548%2C00.asp |date=2012-10-10 }} ''PC Magazine''. Retrieved on November 7, 2007.</ref> Beowulf technology was originally developed by [[Thomas Sterling (computing)|Thomas Sterling]] and [[Donald Becker]]. 87% of all [[TOP500|Top500]] supercomputers are clusters.<ref>{{Cite web|url=https://www.top500.org/statistics/list/|title=List Statistics {{!}} TOP500 Supercomputer Sites|website=www.top500.org|language=en|access-date=2018-08-05}}</ref> The remaining are Massively Parallel Processors, explained below.
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. This requires a high bandwidth and, more importantly, a low-[[latency (engineering)|latency]] interconnection network. Many historic and current supercomputers use customized high-performance network hardware specifically designed for cluster computing, such as the Cray Gemini network.<ref>[https://www.nersc.gov/users/computational-systems/hopper/configuration/interconnect/ "Interconnect"] {{webarchive|url=https://web.archive.org/web/20150128133120/https://www.nersc.gov/users/computational-systems/hopper/configuration/interconnect/ |date=2015-01-28 }}.</ref> As of 2014, most current supercomputers use some off-the-shelf standard network hardware, often [[Myrinet]], [[InfiniBand]], or [[Gigabit Ethernet]].
=====Massively parallel computing=====
{{main|Massively parallel (computing)}}
[[File:BlueGeneL cabinet.jpg|right|thumbnail|upright|A cabinet from [[IBM]]'s [[Blue Gene|Blue Gene/L]] massively parallel [[supercomputer]]]]
A massively parallel processor (MPP) is a single computer with many networked processors. MPPs have many of the same characteristics as clusters, but MPPs have specialized interconnect networks (whereas clusters use commodity hardware for networking). MPPs also tend to be larger than clusters, typically having "far more" than 100 processors.<ref>Hennessy and Patterson, p. 537.</ref> 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."<ref>[https://www.pcmag.com/encyclopedia_term/0,,t=mpp&i=47310,00.asp MPP Definition.] {{Webarchive|url=https://web.archive.org/web/20130511084523/https://www.pcmag.com/encyclopedia_term/0%2C%2Ct%3Dmpp%26i%3D47310%2C00.asp |date=2013-05-11 }} ''PC Magazine''. Retrieved on November 7, 2007.</ref>
[[IBM]]'s [[Blue Gene|Blue Gene/L]], the fifth fastest [[supercomputer]] in the world according to the June 2009 [[TOP500]] ranking, is an MPP.
=====Grid computing=====
{{main|Grid computing}}
Grid computing is the most distributed form of parallel computing. It makes use of computers communicating over the [[Internet]] to work on a given problem. Because of the low bandwidth and extremely high latency available on the Internet,
Most grid computing applications use [[middleware]] (software that sits between the operating system and the application to manage network resources and standardize the software interface). The most common grid computing middleware is the [[Berkeley Open Infrastructure for Network Computing]] (BOINC). Often [[volunteer computing]] software makes use of "spare cycles", performing computations at times when a computer is idling.<ref>{{cite journal|last=Kirkpatrick|first=Scott|title=COMPUTER SCIENCE: Rough Times Ahead|journal=Science|volume=299|issue=5607|pages=668–669|doi=10.1126/science.1081623|year=2003|pmid=12560537|s2cid=60622095}}</ref>
=====Cloud computing=====
{{main|Cloud computing}}
The ubiquity of Internet brought the possibility of large-scale cloud computing.
====Specialized parallel computers====
Within parallel computing, there are specialized parallel devices that remain niche areas of interest. While not [[Domain-specific programming language|___domain-specific]], they tend to be applicable to only a few classes of parallel problems.
[[Reconfigurable computing]] is the use of a [[field-programmable gate array]] (FPGA) as a co-processor to a general-purpose computer. An FPGA is, in essence, a computer chip that can rewire itself for a given task.
FPGAs can be programmed with [[hardware description language]]s such as [[VHDL]]<ref>{{Cite journal|last1=Valueva|first1=Maria|last2=Valuev|first2=Georgii|last3=Semyonova|first3=Nataliya|last4=Lyakhov|first4=Pavel|last5=Chervyakov|first5=Nikolay|last6=Kaplun|first6=Dmitry|last7=Bogaevskiy|first7=Danil|date=2019-06-20|title=Construction of Residue Number System Using Hardware Efficient Diagonal Function|journal=Electronics|language=en|volume=8|issue=6|pages=694|doi=10.3390/electronics8060694|issn=2079-9292|quote=All simulated circuits were described in very high speed integrated circuit (VHSIC) hardware description language (VHDL). Hardware modeling was performed on Xilinx FPGA Artix 7 xc7a200tfbg484-2.|doi-access=free}}</ref> or [[Verilog]].<ref>{{Cite
AMD's decision to open its [[HyperTransport]] technology to third-party vendors has become the enabling technology for high-performance reconfigurable computing.<ref name="DAmour">D'Amour, Michael R., Chief Operating Officer,
{{main|GPGPU}}
[[
General-purpose computing on [[graphics processing unit]]s (GPGPU) is a fairly recent trend in computer engineering research. GPUs are co-processors that have been heavily optimized for [[computer graphics]] processing.<ref>Boggan, Sha'Kia and Daniel M. Pressel (August 2007). [
In the early days, GPGPU programs used the normal graphics APIs for executing programs. However,
{{main|Application-specific integrated circuit}}
Several [[application-specific integrated circuit]] (ASIC) approaches have been devised for dealing with parallel applications.<ref>Maslennikov, Oleg (2002). [
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 [[
{{main|Vector processor}}
[[File:Cray 1 IMG 9126.jpg|right|thumbnail|The [[Cray-1]] is a vector processor.]]
A vector processor is a CPU or computer system that can execute the same instruction on large sets of data. Vector processors have high-level operations that work on linear arrays of numbers or vectors. An example vector operation is ''A'' = ''B'' × ''C'', where ''A'', ''B'', and ''C'' are each 64-element vectors of 64-bit [[floating-point]] numbers.<ref name=PH751>Patterson and Hennessy, p. 751.</ref> They are closely related to Flynn's SIMD classification.<ref name=PH751/>
[[Cray]] computers became famous for their vector-processing computers in the 1970s and 1980s. However, vector processors—both as CPUs and as full computer systems—have generally disappeared. Modern [[Instruction set|processor instruction sets]] do include some vector processing instructions, such as with [[Freescale Semiconductor]]'s [[AltiVec]] and [[Intel]]'s [[Streaming SIMD Extensions]] (SSE).
==Software==
===Parallel programming languages===
{{main|List of concurrent and parallel programming
[[
Efforts to standardize parallel programming include an open standard called [[OpenHMPP]] for hybrid multi-core parallel programming. 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 using [[remote procedure call]]s.
The rise of consumer GPUs has led to support for [[compute kernel]]s, either in graphics APIs (referred to as [[compute shader]]s), in dedicated APIs (such as [[OpenCL]]), or in other language extensions.
===Automatic parallelization===
{{main|Automatic parallelization}}
[[Automatic parallelization]] of a sequential program by a [[compiler]] is the
Mainstream parallel programming languages remain either [[Explicit parallelism|explicitly parallel]] or (at best) [[Implicit parallelism|partially implicit]], in which a programmer gives the compiler [[Directive (programming)|directives]] for parallelization. A few fully implicit parallel programming languages exist—[[SISAL]], Parallel [[Haskell]],
===Application checkpointing===
{{main|Application checkpointing}}
==Algorithmic methods==
As parallel computers become larger and faster,
<!--Note: do not add to or remove from this list. It is copied from the above source-->
* Dense [[linear algebra]]
* Sparse linear algebra
* Spectral methods (such as [[Cooley–Tukey FFT algorithm|Cooley–Tukey fast Fourier transform]])
* [[
* [[Regular grid|Structured grid]] problems (such as [[Lattice Boltzmann methods]])
* [[Unstructured grid]] problems (such as found in [[finite element analysis]])
* [[Monte Carlo method
* [[Combinational logic]] (such as [[Brute force attack|brute-force cryptographic techniques]])
* [[Graph traversal]] (such as [[sorting algorithm]]s)
* [[Dynamic programming]]
* [[Branch and bound]] methods
* [[Graphical model]]s (such as detecting [[hidden Markov model]]s and constructing [[Bayesian network]]s)
* [[HBJ model]], a concise message-passing model<ref>{{cite journal |last1=David R. |first1=Helman |last2=David A. |first2=Bader |last3=JaJa |first3=Joseph |year=1998 |title=A Randomized Parallel Sorting Algorithm with an Experimental Study |journal=Journal of Parallel and Distributed Computing |volume=52 |pages=1–23 |doi=10.1006/jpdc.1998.1462 |hdl=1903/835 |url=http://www.cc.gatech.edu/~bader/papers/JPDC-981462.pdf |access-date=26 October 2012 |archive-date=19 November 2012 |archive-url=https://web.archive.org/web/20121119012835/http://www.cc.gatech.edu/~bader/papers/JPDC-981462.pdf |url-status=dead }}</ref>
* [[Finite-state machine]] simulation
==Fault tolerance==
{{further|Fault-tolerant computer system}}
Parallel computing can also be applied to the design of [[fault-tolerant computer system]]s, particularly via [[Lockstep (computing)|lockstep]] systems performing the same operation in parallel. This provides [[Redundancy (engineering)|redundancy]] in case one component fails, and also allows automatic [[error detection]] and [[error correction]] if the results differ. These methods can be used to help prevent single-event upsets caused by transient errors.<ref>Dobel, B., Hartig, H., & Engel, M. (2012) "Operating system support for redundant multithreading". ''Proceedings of the Tenth ACM International Conference on Embedded Software'', 83–92. {{doi|10.1145/2380356.2380375}}</ref> 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.
==History==
{{
[[
The origins of true (MIMD) parallelism go back to [[Luigi Federico Menabrea]] and his ''Sketch of the [[Analytic Engine]] Invented by [[Charles Babbage]]''.<ref>[[Luigi Federico Menabrea|Menabrea, L. F.]] (1842). [http://www.fourmilab.ch/babbage/sketch.html ''Sketch of the Analytic Engine Invented by Charles Babbage'']. Bibliothèque Universelle de Genève. Retrieved on November 7, 2007.
quote: "when a long series of identical computations is to be performed, such as those required for the formation of numerical tables, the machine can be brought into play so as to give several results at the same time, which will greatly abridge the whole amount of the processes."
</ref><ref name=PH753>Patterson and Hennessy, p. 753.</ref><ref>
R.W. Hockney, C.R. Jesshope. [https://books.google.com/books?id=6HcBQ67-Fb4C ''Parallel Computers 2: Architecture, Programming and Algorithms, Volume 2'']. 1988. p. 8 quote: "The earliest reference to parallelism in computer design is thought to be in General L. F. Menabrea's publication in… 1842, entitled ''Sketch of the Analytical Engine Invented by Charles Babbage''".
</ref>
In 1957, [[Compagnie des Machines Bull]] announced the first computer architecture specifically designed for parallelism, the [[Bull Gamma 60|Gamma 60]].<ref>{{Cite journal |last=Bataille |first=M. |date=1972-04-01 |title=Something old: the Gamma 60 the computer that was ahead of its time |url=https://dl.acm.org/doi/10.1145/641276.641278 |journal=ACM SIGARCH Computer Architecture News |volume=1 |issue=2 |pages=10–15 |doi=10.1145/641276.641278 |s2cid=34642285 |issn=0163-5964|url-access=subscription }}</ref> It utilized a [[Fork–join model|fork-join model]] and a "Program Distributor" to dispatch and collect data to and from independent processing units connected to a central memory.<ref>{{Cite web |title=Architecture Sketch of Bull Gamma 60 -- Mark Smotherman |url=http://www.feb-patrimoine.com/projet/gamma60/architecture_sketch_of_bull_gamma_60_jbourb_--_mark_smotherman.htm |access-date=2023-08-14 |website=www.feb-patrimoine.com}}</ref><ref>{{Cite web |last=Tumlin, Smotherman |date=2023-08-14 |title=An Evaluation of the Design of the Gamma 60 |url=https://db.aconit.org/dbaconit/medias.view.php?media=../dbmedia_0/pdf_10/10174.pdf&cotemedia=An%20Evaluation%20of%20the%20Design%20of%20the%20Gamma%2060.pdf&format=pdf |access-date=2023-08-14 |website=ACONIT Computer History Museum |publisher=Department of Computer Science, Clemson University}}</ref>
In April 1958, Stanley Gill (Ferranti) discussed parallel programming and the need for branching and waiting.<ref>"Parallel Programming", S. Gill, ''The Computer Journal'' Vol. 1 #1, pp2-10, British Computer Society, April 1958.</ref> Also in 1958, IBM researchers [[John Cocke (computer scientist)|John Cocke]] and [[Daniel Slotnick]] discussed the use of parallelism in numerical calculations for the first time.<ref name=G_Wilson>{{cite web | url = http://ei.cs.vt.edu/~history/Parallel.html | title = The History of the Development of Parallel Computing | access-date = 2008-01-08 | first = Gregory V. | last = Wilson | year = 1994|publisher=Virginia Tech/Norfolk State University, Interactive Learning with a Digital Library in Computer Science}}</ref> [[Burroughs Corporation]] introduced the D825 in 1962, a four-processor computer that accessed up to 16 memory modules through a [[crossbar switch]].<ref>{{cite web | url = http://www.computerworld.com/action/article.do?command=viewArticleBasic&articleId=65878 | title = The Power of Parallelism | author = Anthes, Gry | access-date = 2008-01-08 | date = November 19, 2001 | work = [[Computerworld]] | url-status = dead | archive-url = https://web.archive.org/web/20080131205427/http://www.computerworld.com/action/article.do?command=viewArticleBasic&articleId=65878 | archive-date = January 31, 2008 }}</ref> In 1967, Amdahl and Slotnick published a debate about the feasibility of parallel processing at American Federation of Information Processing Societies Conference.<ref name=G_Wilson/> It was during this debate that [[Amdahl's law]] was coined to define the limit of speed-up due to parallelism.
In 1969, [[Honeywell]] introduced its first [[Multics]] system, a symmetric multiprocessor system capable of running up to eight processors in parallel.<ref name=G_Wilson/> [[C.mmp]], a multi-processor project at [[Carnegie Mellon University]] in the 1970s, was among the first multiprocessors with more than a few processors. The first bus-connected multiprocessor with snooping caches was the Synapse N+1 in 1984.<ref name=PH753/>
SIMD parallel computers can be traced back to the 1970s. The motivation behind early SIMD computers was to amortize the [[Propagation delay|gate delay]] of the processor's [[control unit]] over multiple instructions.<ref>Patterson and Hennessy, p. 749.</ref> In 1964, Slotnick had proposed building a massively parallel computer for the [[Lawrence Livermore National Laboratory]].<ref name=G_Wilson/> His design was funded by the [[US Air Force]], which was the earliest SIMD parallel-computing effort, [[ILLIAC IV]].<ref name=G_Wilson/> 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 processor|vector processing]]. However, ILLIAC IV was called "the most infamous of supercomputers", because the project was only one-fourth completed, but took 11 years and cost almost four times the original estimate.<ref name="infamous">Patterson and Hennessy, pp. 749–50: "Although successful in pushing several technologies useful in later projects, the ILLIAC IV failed as a computer. Costs escalated from the $8 million estimated in 1966 to $31 million by 1972, despite the construction of only a quarter of the planned machine . It was perhaps the most infamous of supercomputers. The project started in 1965 and ran its first real application in 1976."</ref> 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]].
==Biological brain as massively parallel computer==
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|massively parallel computer]]. In 1986, Minsky published ''The Society of Mind'', which claims that "mind is formed from many little agents, each mindless by itself".<ref>{{cite book|last=Minsky|first=Marvin|title=The Society of Mind|date=1986|publisher=Simon & Schuster|___location=New York|isbn=978-0-671-60740-1|pages=[https://archive.org/details/societyofmind00marv/page/17 17]|url=https://archive.org/details/societyofmind00marv/page/17}}</ref> The theory attempts to explain how what we call intelligence could be a product of the interaction of non-intelligent parts. 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.<ref>{{cite book|last=Minsky|first=Marvin|title=The Society of Mind|date=1986|publisher=Simon & Schuster|___location=New York|isbn=978-0-671-60740-1|pages=[https://archive.org/details/societyofmind00marv/page/29 29]|url=https://archive.org/details/societyofmind00marv/page/29}}</ref>
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:
* Thomas R. Blakeslee,<ref>{{cite book |last=Blakeslee |first=Thomas |date=1996 |title=Beyond the Conscious Mind. Unlocking the Secrets of the Self |url=https://archive.org/details/beyondconsciousm00blak |url-access=registration |pages=[https://archive.org/details/beyondconsciousm00blak/page/6 6–7]|publisher=Springer |isbn=9780306452628 }}</ref>
* [[Michael Gazzaniga|Michael S. Gazzaniga]],<ref>{{cite book |last1=Gazzaniga |first1=Michael |author-link1=Michael S. Gazzaniga |last2=LeDoux |first2=Joseph |author-link2=Joseph E. LeDoux |date=1978 |title=The Integrated Mind |pages=132–161}}</ref><ref>{{cite book |last=Gazzaniga |first=Michael |author-link=Michael S. Gazzaniga |date=1985 |title=The Social Brain. Discovering the Networks of the Mind |url=https://archive.org/details/socialbraindisco0000gazz |url-access=registration |pages=[https://archive.org/details/socialbraindisco0000gazz/page/77 77–79]|publisher=Basic Books |isbn=9780465078509 }}</ref>
* [[Robert E. Ornstein]],<ref>{{cite book |last= Ornstein |first= Robert |author-link= Robert Ornstein |date=1992 |title=Evolution of Consciousness: The Origins of the Way We Think |url= https://archive.org/details/evolutionofconsc0000orns |url-access= registration |pages=[https://archive.org/details/evolutionofconsc0000orns/page/2 2]}}</ref>
* [[Ernest Hilgard]],<ref>{{cite book|last=Hilgard|first=Ernest|title=Divided consciousness: multiple controls in human thought and action.|author-link=Ernest Hilgard|date=1977|publisher= Wiley|___location=New York|isbn=978-0-471-39602-4}}</ref><ref>{{cite book|last=Hilgard|first=Ernest|title=Divided consciousness: multiple controls in human thought and action (expanded edition).|author-link=Ernest Hilgard|date=1986|publisher= Wiley|___location=New York|isbn=978-0-471-80572-4}}</ref>
* [[Michio Kaku]],<ref>{{cite book |last=Kaku |first=Michio |author-link=Michio Kaku |date=2014 |title=The Future of the Mind|title-link=The Future of the Mind }}</ref>
* [[George Gurdjieff|George Ivanovich Gurdjieff]],<ref>{{cite book |last=Ouspenskii |first= Pyotr |author-link=Pyotr Demianovich Ouspenskii |date=1992 |title=In Search of the Miraculous. Fragments of an Unknown Teaching |pages=72–83 |chapter=Chapter 3}}</ref>
* Neurocluster Brain Model.<ref>{{cite web |url=http://neuroclusterbrain.com |title=Official Neurocluster Brain Model site |access-date=July 22, 2017}}</ref>
==See also==
{{div col|colwidth=25em}}
* [[Computer multitasking]]
* [[Concurrency (computer science)]]
* [[Content Addressable Parallel Processor]]
* [[List of distributed computing conferences]]
* [[Loop-level parallelism]]
* [[Dataflow architecture|Manchester dataflow machine]]
* [[Manycore processor|Manycore]]
* [[Parallel programming model]]
* [[Parallelization contract]]
* [[Serializability]]
* [[Synchronous programming]]
* [[Transputer]]
* [[Vector processing]]
{{div col end}}
==References==
{{reflist|
==Further reading==
* {{cite book|last1=Rodriguez|first1=C.|last2=Villagra|first2=M.|last3=Baran|first3=B. |title=2007 2nd Bio-Inspired Models of Network, Information and Computing Systems |chapter=Asynchronous team algorithms for Boolean Satisfiability |date=29 August 2008|pages=66–69|doi=10.1109/BIMNICS.2007.4610083|s2cid=15185219}}
* Sechin, A.; Parallel Computing in Photogrammetry. GIM International. #1, 2016, pp. 21–23.
==External links==
{{Spoken Wikipedia|En-Parallel_computing.ogg|date=2013-08-21}}
{{wikibooks|Distributed Systems}}
* [http://www.llnl.gov/computing/tutorials/parallel_comp/ Lawrence Livermore National Laboratory: Introduction to Parallel Computing]
* [http://www-unix.mcs.anl.gov/dbpp/ Designing and Building Parallel Programs, by Ian Foster]
* [https://web.archive.org/web/20021012122919/http://wotug.ukc.ac.uk/parallel/ Internet Parallel Computing Archive]
{{Parallel Computing|state=collapsed}}
{{Programming paradigms navbox}}
{{featured article}}
{{Authority control}}
[[Category:Parallel computing| ]]
[[Category:Concurrent computing]]
[[Category:Distributed computing]]
| |||