Parallel algorithm - Revision history

OlliverWithDoubleL: Added short description

2025-01-17T08:29:40Z

Added short description

← Previous revision		Revision as of 08:29, 17 January 2025
Line 1:		Line 1:
			{{Short description\|Algorithm which can do multiple operations in a given time}}
	{{More citations needed\|date=November 2012}}		{{More citations needed\|date=November 2012}}
	In [[computer science]], a '''parallel algorithm''', as opposed to a traditional [[serial algorithm]], is an [[algorithm]] which can do multiple operations in a given time. It has been a tradition of [[computer science]] to describe serial algorithms in [[abstract machine]] models, often the one known as [[random-access machine]]. Similarly, many computer science researchers have used a so-called [[parallel random-access machine]] (PRAM) as a parallel abstract machine (shared-memory).<ref>{{cite web \|title=Parallel Algorithms \|first1=Guy E. \|last1=Blelloch \|first2=Bruce M. \|last2=Maggs \|publisher=School of Computer Science, [[Carnegie Mellon University]] \|location=USA \|access-date=2015-07-27 \|url=https://www.cs.cmu.edu/~guyb/papers/BM04.pdf}}</ref><ref>{{cite web \|title=Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques, 104 pages \|first=Uzi \|last=Vishkin \|publisher=Class notes of courses on parallel algorithms taught since 1992 at the University of Maryland, College Park, Tel Aviv University and the Technion \|date=2009 \|url=http://users.umiacs.umd.edu/~vishkin/PUBLICATIONS/classnotes.pdf}}</ref>		In [[computer science]], a '''parallel algorithm''', as opposed to a traditional [[serial algorithm]], is an [[algorithm]] which can do multiple operations in a given time. It has been a tradition of [[computer science]] to describe serial algorithms in [[abstract machine]] models, often the one known as [[random-access machine]]. Similarly, many computer science researchers have used a so-called [[parallel random-access machine]] (PRAM) as a parallel abstract machine (shared-memory).<ref>{{cite web \|title=Parallel Algorithms \|first1=Guy E. \|last1=Blelloch \|first2=Bruce M. \|last2=Maggs \|publisher=School of Computer Science, [[Carnegie Mellon University]] \|location=USA \|access-date=2015-07-27 \|url=https://www.cs.cmu.edu/~guyb/papers/BM04.pdf}}</ref><ref>{{cite web \|title=Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques, 104 pages \|first=Uzi \|last=Vishkin \|publisher=Class notes of courses on parallel algorithms taught since 1992 at the University of Maryland, College Park, Tel Aviv University and the Technion \|date=2009 \|url=http://users.umiacs.umd.edu/~vishkin/PUBLICATIONS/classnotes.pdf}}</ref>

Worldec478: added information about developing an effective parallel algorithm for solution in "parallelizability" section and citation to book

2024-07-25T17:16:10Z

added information about developing an effective parallel algorithm for solution in "parallelizability" section and citation to book

← Previous revision		Revision as of 17:16, 25 July 2024
Line 11:		Line 11:

	Some problems cannot be split up into parallel portions, as they require the results from a preceding step to effectively carry on with the next step – these are called '''{{visible anchor\|inherently serial problem}}s'''. Examples include iterative [[numerical analysis\|numerical methods]], such as [[Newton's method]], iterative solutions to the [[three-body problem]], and most of the available algorithms to compute [[pi]] (π).{{citation needed\|date=August 2019}} Some sequential algorithms can be converted into parallel algorithms using [[automatic parallelization]].<ref name="MXian1997">{{cite book \|author1=Megson G M\|author2=Chen Xian\|title=Automatic Parallelization For A Class Of Regular Computations\|url=https://books.google.com/books?id=1wHtCgAAQBAJ&q=%22parallel+algorithm%22\|date=4 January 1997\|publisher=World Scientific\|isbn=978-981-4498-41-8}}</ref>		Some problems cannot be split up into parallel portions, as they require the results from a preceding step to effectively carry on with the next step – these are called '''{{visible anchor\|inherently serial problem}}s'''. Examples include iterative [[numerical analysis\|numerical methods]], such as [[Newton's method]], iterative solutions to the [[three-body problem]], and most of the available algorithms to compute [[pi]] (π).{{citation needed\|date=August 2019}} Some sequential algorithms can be converted into parallel algorithms using [[automatic parallelization]].<ref name="MXian1997">{{cite book \|author1=Megson G M\|author2=Chen Xian\|title=Automatic Parallelization For A Class Of Regular Computations\|url=https://books.google.com/books?id=1wHtCgAAQBAJ&q=%22parallel+algorithm%22\|date=4 January 1997\|publisher=World Scientific\|isbn=978-981-4498-41-8}}</ref>

			In many cases developing an effective parallel algorithm for solution of some task requires attraction of new ideas and methods comparing to creating a sequential algorithm version. These are, for instance, practically important problems of searching a target element in data structures, evaluation of an algebraic expression, etc.<ref>{{Cite book \|last=Kurgalin \|first=Sergei \|title=The discrete math workbook: a companion manual using Python \|last2=Borzunov \|first2=Sergei \|date=2020 \|publisher=Springer Naturel \|isbn=978-3-030-42220-2 \|edition=2nd \|series=Texts in Computer Science \|location=Cham, Switzerland}}</ref>

	==Motivation==		==Motivation==

JayBeeEll: Reverted 1 edit by 2A03:D000:1400:93EE:7D68:23BD:8EA6:9648 (talk): Rv refspam

2024-04-03T17:55:52Z

Reverted 1 edit by 2A03:D000:1400:93EE:7D68:23BD:8EA6:9648 (talk): Rv refspam

← Previous revision		Revision as of 17:55, 3 April 2024
Line 11:		Line 11:

	Some problems cannot be split up into parallel portions, as they require the results from a preceding step to effectively carry on with the next step – these are called '''{{visible anchor\|inherently serial problem}}s'''. Examples include iterative [[numerical analysis\|numerical methods]], such as [[Newton's method]], iterative solutions to the [[three-body problem]], and most of the available algorithms to compute [[pi]] (π).{{citation needed\|date=August 2019}} Some sequential algorithms can be converted into parallel algorithms using [[automatic parallelization]].<ref name="MXian1997">{{cite book \|author1=Megson G M\|author2=Chen Xian\|title=Automatic Parallelization For A Class Of Regular Computations\|url=https://books.google.com/books?id=1wHtCgAAQBAJ&q=%22parallel+algorithm%22\|date=4 January 1997\|publisher=World Scientific\|isbn=978-981-4498-41-8}}</ref>		Some problems cannot be split up into parallel portions, as they require the results from a preceding step to effectively carry on with the next step – these are called '''{{visible anchor\|inherently serial problem}}s'''. Examples include iterative [[numerical analysis\|numerical methods]], such as [[Newton's method]], iterative solutions to the [[three-body problem]], and most of the available algorithms to compute [[pi]] (π).{{citation needed\|date=August 2019}} Some sequential algorithms can be converted into parallel algorithms using [[automatic parallelization]].<ref name="MXian1997">{{cite book \|author1=Megson G M\|author2=Chen Xian\|title=Automatic Parallelization For A Class Of Regular Computations\|url=https://books.google.com/books?id=1wHtCgAAQBAJ&q=%22parallel+algorithm%22\|date=4 January 1997\|publisher=World Scientific\|isbn=978-981-4498-41-8}}</ref>

	In many cases developing an effective parallel algorithm for solution of some task requires attraction of new ideas and methods comparing to creating a sequential algorithm version. These are, for instance, practically important problems of searching a target element in data structures,
	evaluation of an algebraic expression, etc. <ref>Kurgalin, Sergei; Borzunov, Sergei (2020). "The Discrete Math Workbook: A Companion Manual Using Python". 2nd ed. Springer. ISBN 978-3-030-42220-2, 978-3-030-42221-9. https://doi.org/10.1007/978-3-030-42221-9 </ref>

	==Motivation==		==Motivation==

2A03:D000:1400:93EE:7D68:23BD:8EA6:9648: /* Parallelizability */

2024-04-03T13:29:32Z

Parallelizability

← Previous revision		Revision as of 13:29, 3 April 2024
Line 11:		Line 11:

	Some problems cannot be split up into parallel portions, as they require the results from a preceding step to effectively carry on with the next step – these are called '''{{visible anchor\|inherently serial problem}}s'''. Examples include iterative [[numerical analysis\|numerical methods]], such as [[Newton's method]], iterative solutions to the [[three-body problem]], and most of the available algorithms to compute [[pi]] (π).{{citation needed\|date=August 2019}} Some sequential algorithms can be converted into parallel algorithms using [[automatic parallelization]].<ref name="MXian1997">{{cite book \|author1=Megson G M\|author2=Chen Xian\|title=Automatic Parallelization For A Class Of Regular Computations\|url=https://books.google.com/books?id=1wHtCgAAQBAJ&q=%22parallel+algorithm%22\|date=4 January 1997\|publisher=World Scientific\|isbn=978-981-4498-41-8}}</ref>		Some problems cannot be split up into parallel portions, as they require the results from a preceding step to effectively carry on with the next step – these are called '''{{visible anchor\|inherently serial problem}}s'''. Examples include iterative [[numerical analysis\|numerical methods]], such as [[Newton's method]], iterative solutions to the [[three-body problem]], and most of the available algorithms to compute [[pi]] (π).{{citation needed\|date=August 2019}} Some sequential algorithms can be converted into parallel algorithms using [[automatic parallelization]].<ref name="MXian1997">{{cite book \|author1=Megson G M\|author2=Chen Xian\|title=Automatic Parallelization For A Class Of Regular Computations\|url=https://books.google.com/books?id=1wHtCgAAQBAJ&q=%22parallel+algorithm%22\|date=4 January 1997\|publisher=World Scientific\|isbn=978-981-4498-41-8}}</ref>

			In many cases developing an effective parallel algorithm for solution of some task requires attraction of new ideas and methods comparing to creating a sequential algorithm version. These are, for instance, practically important problems of searching a target element in data structures,
			evaluation of an algebraic expression, etc. <ref>Kurgalin, Sergei; Borzunov, Sergei (2020). "The Discrete Math Workbook: A Companion Manual Using Python". 2nd ed. Springer. ISBN 978-3-030-42220-2, 978-3-030-42221-9. https://doi.org/10.1007/978-3-030-42221-9 </ref>

	==Motivation==		==Motivation==

Tom.Reding: +{{Authority control}} (1 ID from Wikidata); WP:GenFixes & cleanup on

2023-10-22T22:41:06Z

+{{Authority control}} (1 ID from Wikidata); WP:GenFixes & cleanup on

← Previous revision		Revision as of 22:41, 22 October 2023
Line 49:		Line 49:

	{{Parallel computing}}		{{Parallel computing}}
			{{Authority control}}

	[[Category:Parallel computing]]		[[Category:Parallel computing]]

A876: +link. +comma. fixed 2 ref errors. checked links.

2021-07-27T22:36:16Z

+link. +comma. fixed 2 ref errors. checked links.

← Previous revision		Revision as of 22:36, 27 July 2021
Line 1:		Line 1:
	{{~~refimprove~~\|date=November 2012}}		{{More citations needed\|date=November 2012}}
	In [[computer science]], a '''parallel algorithm''', as opposed to a traditional [[serial algorithm]], is an [[algorithm]] which can do multiple operations in a given time. It has been a tradition of [[computer science]] to describe serial algorithms in abstract machine models, often the one known as [[random-access machine]]. Similarly, many computer science researchers have used a so-called [[parallel random-access machine]] (PRAM) as a parallel abstract machine (shared-memory).<ref>{{cite ~~document\|~~ title=Parallel Algorithms \| first1=Guy E. \| last1=Blelloch \| first2=Bruce M. \| last2=Maggs \| publisher=School of Computer Science, [[Carnegie Mellon University]] \| location=USA \| access-date=2015-07-27 \| url= https://www.cs.cmu.edu/~guyb/papers/BM04.pdf }}</ref><ref>{{cite ~~document~~\| title = Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques, 104 pages \| first = Uzi \| last = Vishkin \| publisher = Class notes of courses on parallel algorithms taught since 1992 at the University of Maryland, College Park, Tel Aviv University and the Technion \| date = 2009 \| url=http://~~www~~.umiacs.umd.edu/~~users/~~vishkin/PUBLICATIONS/classnotes.pdf }}</ref>		In [[computer science]], a '''parallel algorithm''', as opposed to a traditional [[serial algorithm]], is an [[algorithm]] which can do multiple operations in a given time. It has been a tradition of [[computer science]] to describe serial algorithms in [[abstract machine]] models, often the one known as [[random-access machine]]. Similarly, many computer science researchers have used a so-called [[parallel random-access machine]] (PRAM) as a parallel abstract machine (shared-memory).<ref>{{cite web \|title=Parallel Algorithms \|first1=Guy E. \|last1=Blelloch \|first2=Bruce M. \|last2=Maggs \|publisher=School of Computer Science, [[Carnegie Mellon University]] \|location=USA \|access-date=2015-07-27 \|url=https://www.cs.cmu.edu/~guyb/papers/BM04.pdf}}</ref><ref>{{cite web \|title=Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques, 104 pages \|first=Uzi \|last=Vishkin \|publisher=Class notes of courses on parallel algorithms taught since 1992 at the University of Maryland, College Park, Tel Aviv University and the Technion \|date=2009 \|url=http://users.umiacs.umd.edu/~vishkin/PUBLICATIONS/classnotes.pdf}}</ref>

	Many parallel algorithms are executed [[concurrent computing\|concurrently]] – though in general [[concurrent algorithm]]s are a distinct concept – and thus these concepts are often conflated, with which aspect of an algorithm is parallel and which is concurrent not being clearly distinguished. Further, non-parallel, non-concurrent algorithms are often referred to as "[[sequential algorithm]]s", by contrast with concurrent algorithms.		Many parallel algorithms are executed [[concurrent computing\|concurrently]] – though in general [[concurrent algorithm]]s are a distinct concept – and thus these concepts are often conflated, with which aspect of an algorithm is parallel and which is concurrent not being clearly distinguished. Further, non-parallel, non-concurrent algorithms are often referred to as "[[sequential algorithm]]s", by contrast with concurrent algorithms.
Line 8:		Line 8:
	Algorithms vary significantly in how parallelizable they are, ranging from easily parallelizable to completely unparallelizable. Further, a given problem may accommodate different algorithms, which may be more or less parallelizable.		Algorithms vary significantly in how parallelizable they are, ranging from easily parallelizable to completely unparallelizable. Further, a given problem may accommodate different algorithms, which may be more or less parallelizable.

	Some problems are easy to divide up into pieces in this way – these are called ''[[embarrassingly parallel ~~problem~~]]s.'' Examples include many algorithms to solve [[Rubik's Cube]]s and find values which result in a given [[~~Associative~~ array\|hash]].{{~~Citation~~ needed\|date=December 2019}}		Some problems are easy to divide up into pieces in this way – these are called ''[[embarrassingly parallel]] problems.'' Examples include many algorithms to solve [[Rubik's Cube]]s and find values which result in a given [[associative array\|hash]].{{citation needed\|date=December 2019}}

	Some problems cannot be split up into parallel portions, as they require the results from a preceding step to effectively carry on with the next step – these are called '''{{visible anchor\|inherently serial problem}}s'''. Examples include iterative [[~~Numerical~~ analysis\|numerical methods]], such as [[Newton's method]], iterative solutions to the [[three-body problem]], and most of the available algorithms to compute [[pi]] (π).{{citation needed\|date=August 2019}} Some sequential algorithms can be converted into parallel algorithms using [[automatic parallelization]].<ref name="MXian1997">{{cite book\|author1=Megson G M\|author2=Chen Xian\|title=Automatic Parallelization For A Class Of Regular Computations\|url=https://books.google.com/books?id=1wHtCgAAQBAJ&q=%22parallel+algorithm%22\|date=4 January 1997\|publisher=World Scientific\|isbn=978-981-4498-41-8}}</ref>		Some problems cannot be split up into parallel portions, as they require the results from a preceding step to effectively carry on with the next step – these are called '''{{visible anchor\|inherently serial problem}}s'''. Examples include iterative [[numerical analysis\|numerical methods]], such as [[Newton's method]], iterative solutions to the [[three-body problem]], and most of the available algorithms to compute [[pi]] (π).{{citation needed\|date=August 2019}} Some sequential algorithms can be converted into parallel algorithms using [[automatic parallelization]].<ref name="MXian1997">{{cite book \|author1=Megson G M\|author2=Chen Xian\|title=Automatic Parallelization For A Class Of Regular Computations\|url=https://books.google.com/books?id=1wHtCgAAQBAJ&q=%22parallel+algorithm%22\|date=4 January 1997\|publisher=World Scientific\|isbn=978-981-4498-41-8}}</ref>

	==Motivation==		==Motivation==
Line 20:		Line 20:
	The cost or complexity of serial algorithms is estimated in terms of the space (memory) and time (processor cycles) that they take. Parallel algorithms need to optimize one more resource, the communication between different processors. There are two ways parallel processors communicate, shared memory or message passing.		The cost or complexity of serial algorithms is estimated in terms of the space (memory) and time (processor cycles) that they take. Parallel algorithms need to optimize one more resource, the communication between different processors. There are two ways parallel processors communicate, shared memory or message passing.

	[[~~Shared memory (interprocess communication)\|~~Shared memory]] processing needs additional [[~~Lock~~ (computer science)\|locking]] for the data, imposes the overhead of additional processor and bus cycles, and also serializes some portion of the algorithm.		[[Shared memory]] processing needs additional [[lock (computer science)\|locking]] for the data, imposes the overhead of additional processor and bus cycles, and also serializes some portion of the algorithm.

	[[Message passing]] processing uses channels and message boxes but this communication adds transfer overhead on the bus, additional memory need for queues and message boxes and latency in the messages. Designs of parallel processors use special [[~~Bus~~ (computing)\|buses]] like [[~~Crossbar~~ switch\|crossbar]] so that the communication overhead will be small but it is the parallel algorithm that decides the volume of the traffic.		[[Message passing]] processing uses channels and message boxes but this communication adds transfer overhead on the bus, additional memory need for queues and message boxes and latency in the messages. Designs of parallel processors use special [[bus (computing)\|buses]] like [[crossbar switch\|crossbar]] so that the communication overhead will be small but it is the parallel algorithm that decides the volume of the traffic.

	If the communication overhead of additional processors outweighs the benefit of adding another processor, one encounters [[parallel slowdown]].		If the communication overhead of additional processors outweighs the benefit of adding another processor, one encounters [[parallel slowdown]].
Line 28:		Line 28:
	===Load balancing===		===Load balancing===
	{{main\|Load balancing (computing)}}		{{main\|Load balancing (computing)}}
	Another problem with parallel algorithms is ensuring that they are suitably [[~~Load~~ balancing (computing)\|load balanced]], by ensuring that ''load'' (overall work) is balanced, rather than input size being balanced. For example, checking all numbers from one to a hundred thousand for primality is easy to split ~~amongst~~ processors; however, if the numbers are simply divided out evenly (1–1,000, 1,001–2,000, etc.), the amount of work will be unbalanced, as smaller numbers are easier to process by this algorithm (easier to test for primality), and thus some processors will get more work to do than the others, which will sit idle until the loaded processors complete.		Another problem with parallel algorithms is ensuring that they are suitably [[load balancing (computing)\|load balanced]], by ensuring that ''load'' (overall work) is balanced, rather than input size being balanced. For example, checking all numbers from one to a hundred thousand for primality is easy to split among processors; however, if the numbers are simply divided out evenly (1–1,000, 1,001–2,000, etc.), the amount of work will be unbalanced, as smaller numbers are easier to process by this algorithm (easier to test for primality), and thus some processors will get more work to do than the others, which will sit idle until the loaded processors complete.

	==Distributed algorithms==		==Distributed algorithms==
	{{main\|Distributed algorithm}}		{{main\|Distributed algorithm}}
	{{expand section\|date=February 2014}}		{{expand section\|date=February 2014}}
	A subtype of parallel algorithms, ''[[distributed algorithm]]s'' are algorithms designed to work in [[cluster computing]] and [[distributed computing]] environments, where additional concerns beyond the scope of "classical" parallel algorithms need to be addressed.		A subtype of parallel algorithms, ''[[distributed algorithm]]s'', are algorithms designed to work in [[cluster computing]] and [[distributed computing]] environments, where additional concerns beyond the scope of "classical" parallel algorithms need to be addressed.

	==See also==		==See also==
Line 43:		Line 43:

	==References==		==References==
	{{~~reflist~~}}		{{Reflist}}

	==External links==		==External links==
	*[~~http~~://www.mcs.anl.gov/~itf/dbpp/ Designing and Building Parallel Programs ~~page at the~~ US Argonne National ~~Laboratories]~~		*[https://www.mcs.anl.gov/~itf/dbpp/ Designing and Building Parallel Programs], US Argonne National Laboratory

	{{Parallel ~~Computing~~}}		{{Parallel computing}}

	[[Category:Parallel computing]]		[[Category:Parallel computing]]

Haeinous at 06:44, 22 April 2021

2021-04-22T06:44:27Z

← Previous revision		Revision as of 06:44, 22 April 2021
Line 1:		Line 1:
	{{refimprove\|date=November 2012}}		{{refimprove\|date=November 2012}}
	In [[computer science]], a '''parallel algorithm''', as opposed to a traditional [[serial algorithm]], is an [[algorithm]] which can do multiple operations in a given time. It has been a tradition of [[computer science]] to describe serial algorithms in abstract machine models, often the one known as [[~~Random~~-access machine]]. Similarly, many computer science researchers have used a so-called [[parallel random-access machine]] (PRAM) as a parallel abstract machine (shared-memory).<ref>{{cite document\| title=Parallel Algorithms \| first1=Guy E. \| last1=Blelloch \| first2=Bruce M. \| last2=Maggs \| publisher=School of Computer Science, [[Carnegie Mellon University]] \| location=USA \| access-date=2015-07-27 \| url= https://www.cs.cmu.edu/~guyb/papers/BM04.pdf }}</ref><ref>{{cite document\| title = Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques, 104 pages \| first = Uzi \| last = Vishkin \| publisher = Class notes of courses on parallel algorithms taught since 1992 at the University of Maryland, College Park, Tel Aviv University and the Technion \| date = 2009 \| url=http://www.umiacs.umd.edu/users/vishkin/PUBLICATIONS/classnotes.pdf }}</ref>		In [[computer science]], a '''parallel algorithm''', as opposed to a traditional [[serial algorithm]], is an [[algorithm]] which can do multiple operations in a given time. It has been a tradition of [[computer science]] to describe serial algorithms in abstract machine models, often the one known as [[random-access machine]]. Similarly, many computer science researchers have used a so-called [[parallel random-access machine]] (PRAM) as a parallel abstract machine (shared-memory).<ref>{{cite document\| title=Parallel Algorithms \| first1=Guy E. \| last1=Blelloch \| first2=Bruce M. \| last2=Maggs \| publisher=School of Computer Science, [[Carnegie Mellon University]] \| location=USA \| access-date=2015-07-27 \| url= https://www.cs.cmu.edu/~guyb/papers/BM04.pdf }}</ref><ref>{{cite document\| title = Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques, 104 pages \| first = Uzi \| last = Vishkin \| publisher = Class notes of courses on parallel algorithms taught since 1992 at the University of Maryland, College Park, Tel Aviv University and the Technion \| date = 2009 \| url=http://www.umiacs.umd.edu/users/vishkin/PUBLICATIONS/classnotes.pdf }}</ref>

	Many parallel algorithms are executed [[concurrent computing\|concurrently]] – though in general [[concurrent algorithm]]s are a distinct concept – and thus these concepts are often conflated, with which aspect of an algorithm is parallel and which is concurrent not being clearly distinguished. Further, non-parallel, non-concurrent algorithms are often referred to as "[[sequential algorithm]]s", by contrast with concurrent algorithms.		Many parallel algorithms are executed [[concurrent computing\|concurrently]] – though in general [[concurrent algorithm]]s are a distinct concept – and thus these concepts are often conflated, with which aspect of an algorithm is parallel and which is concurrent not being clearly distinguished. Further, non-parallel, non-concurrent algorithms are often referred to as "[[sequential algorithm]]s", by contrast with concurrent algorithms.
Line 22:		Line 22:
	[[Shared memory (interprocess communication)\|Shared memory]] processing needs additional [[Lock (computer science)\|locking]] for the data, imposes the overhead of additional processor and bus cycles, and also serializes some portion of the algorithm.		[[Shared memory (interprocess communication)\|Shared memory]] processing needs additional [[Lock (computer science)\|locking]] for the data, imposes the overhead of additional processor and bus cycles, and also serializes some portion of the algorithm.

	[[Message passing]] processing uses channels and message boxes but this communication adds transfer overhead on the bus, additional memory need for queues and message boxes and latency in the messages. Designs of parallel processors use special buses like [[Crossbar switch\|crossbar]] so that the communication overhead will be small but it is the parallel algorithm that decides the volume of the traffic.		[[Message passing]] processing uses channels and message boxes but this communication adds transfer overhead on the bus, additional memory need for queues and message boxes and latency in the messages. Designs of parallel processors use special [[Bus (computing)\|buses]] like [[Crossbar switch\|crossbar]] so that the communication overhead will be small but it is the parallel algorithm that decides the volume of the traffic.

	If the communication overhead of additional processors outweighs the benefit of adding another processor, one encounters [[parallel slowdown]].		If the communication overhead of additional processors outweighs the benefit of adding another processor, one encounters [[parallel slowdown]].

Monkbot: Task 18 (cosmetic): eval 3 templates: hyphenate params (1×);

2020-12-28T04:50:45Z

Task 18 (cosmetic): eval 3 templates: hyphenate params (1×);

← Previous revision		Revision as of 04:50, 28 December 2020
Line 1:		Line 1:
	{{refimprove\|date=November 2012}}		{{refimprove\|date=November 2012}}
	In [[computer science]], a '''parallel algorithm''', as opposed to a traditional [[serial algorithm]], is an [[algorithm]] which can do multiple operations in a given time. It has been a tradition of [[computer science]] to describe serial algorithms in abstract machine models, often the one known as [[Random-access machine]]. Similarly, many computer science researchers have used a so-called [[parallel random-access machine]] (PRAM) as a parallel abstract machine (shared-memory).<ref>{{cite document\| title=Parallel Algorithms \| first1=Guy E. \| last1=Blelloch \| first2=Bruce M. \| last2=Maggs \| publisher=School of Computer Science, [[Carnegie Mellon University]] \| location=USA \| ~~accessdate~~=2015-07-27 \| url= https://www.cs.cmu.edu/~guyb/papers/BM04.pdf }}</ref><ref>{{cite document\| title = Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques, 104 pages \| first = Uzi \| last = Vishkin \| publisher = Class notes of courses on parallel algorithms taught since 1992 at the University of Maryland, College Park, Tel Aviv University and the Technion \| date = 2009 \| url=http://www.umiacs.umd.edu/users/vishkin/PUBLICATIONS/classnotes.pdf }}</ref>		In [[computer science]], a '''parallel algorithm''', as opposed to a traditional [[serial algorithm]], is an [[algorithm]] which can do multiple operations in a given time. It has been a tradition of [[computer science]] to describe serial algorithms in abstract machine models, often the one known as [[Random-access machine]]. Similarly, many computer science researchers have used a so-called [[parallel random-access machine]] (PRAM) as a parallel abstract machine (shared-memory).<ref>{{cite document\| title=Parallel Algorithms \| first1=Guy E. \| last1=Blelloch \| first2=Bruce M. \| last2=Maggs \| publisher=School of Computer Science, [[Carnegie Mellon University]] \| location=USA \| access-date=2015-07-27 \| url= https://www.cs.cmu.edu/~guyb/papers/BM04.pdf }}</ref><ref>{{cite document\| title = Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques, 104 pages \| first = Uzi \| last = Vishkin \| publisher = Class notes of courses on parallel algorithms taught since 1992 at the University of Maryland, College Park, Tel Aviv University and the Technion \| date = 2009 \| url=http://www.umiacs.umd.edu/users/vishkin/PUBLICATIONS/classnotes.pdf }}</ref>

	Many parallel algorithms are executed [[concurrent computing\|concurrently]] – though in general [[concurrent algorithm]]s are a distinct concept – and thus these concepts are often conflated, with which aspect of an algorithm is parallel and which is concurrent not being clearly distinguished. Further, non-parallel, non-concurrent algorithms are often referred to as "[[sequential algorithm]]s", by contrast with concurrent algorithms.		Many parallel algorithms are executed [[concurrent computing\|concurrently]] – though in general [[concurrent algorithm]]s are a distinct concept – and thus these concepts are often conflated, with which aspect of an algorithm is parallel and which is concurrent not being clearly distinguished. Further, non-parallel, non-concurrent algorithms are often referred to as "[[sequential algorithm]]s", by contrast with concurrent algorithms.

Citation bot: Alter: template type, url. URLs might have been internationalized/anonymized. | You can use this bot yourself. Report bugs here. | Suggested by AManWithNoPlan | All pages linked from cached copy of User:AManWithNoPlan/sandbox2 | via #UCB_webform_linked 1368/3977

2020-11-07T02:14:07Z

Alter: template type, url. URLs might have been internationalized/anonymized. | You can use this bot yourself. Report bugs here. | Suggested by AManWithNoPlan | All pages linked from cached copy of User:AManWithNoPlan/sandbox2 | via #UCB_webform_linked 1368/3977

← Previous revision		Revision as of 02:14, 7 November 2020
Line 1:		Line 1:
	{{refimprove\|date=November 2012}}		{{refimprove\|date=November 2012}}
	In [[computer science]], a '''parallel algorithm''', as opposed to a traditional [[serial algorithm]], is an [[algorithm]] which can do multiple operations in a given time. It has been a tradition of [[computer science]] to describe serial algorithms in abstract machine models, often the one known as [[Random-access machine]]. Similarly, many computer science researchers have used a so-called [[parallel random-access machine]] (PRAM) as a parallel abstract machine (shared-memory).<ref>{{cite ~~paper~~\| title=Parallel Algorithms \| first1=Guy E. \| last1=Blelloch \| first2=Bruce M. \| last2=Maggs \| publisher=School of Computer Science, [[Carnegie Mellon University]] \| location=USA \| accessdate=2015-07-27 \| url= https://www.cs.cmu.edu/~guyb/papers/BM04.pdf }}</ref><ref>{{cite ~~paper~~\| title = Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques, 104 pages \| first = Uzi \| last = Vishkin \| publisher = Class notes of courses on parallel algorithms taught since 1992 at the University of Maryland, College Park, Tel Aviv University and the Technion \| date = 2009 \| url=http://www.umiacs.umd.edu/users/vishkin/PUBLICATIONS/classnotes.pdf }}</ref>		In [[computer science]], a '''parallel algorithm''', as opposed to a traditional [[serial algorithm]], is an [[algorithm]] which can do multiple operations in a given time. It has been a tradition of [[computer science]] to describe serial algorithms in abstract machine models, often the one known as [[Random-access machine]]. Similarly, many computer science researchers have used a so-called [[parallel random-access machine]] (PRAM) as a parallel abstract machine (shared-memory).<ref>{{cite document\| title=Parallel Algorithms \| first1=Guy E. \| last1=Blelloch \| first2=Bruce M. \| last2=Maggs \| publisher=School of Computer Science, [[Carnegie Mellon University]] \| location=USA \| accessdate=2015-07-27 \| url= https://www.cs.cmu.edu/~guyb/papers/BM04.pdf }}</ref><ref>{{cite document\| title = Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques, 104 pages \| first = Uzi \| last = Vishkin \| publisher = Class notes of courses on parallel algorithms taught since 1992 at the University of Maryland, College Park, Tel Aviv University and the Technion \| date = 2009 \| url=http://www.umiacs.umd.edu/users/vishkin/PUBLICATIONS/classnotes.pdf }}</ref>

	Many parallel algorithms are executed [[concurrent computing\|concurrently]] – though in general [[concurrent algorithm]]s are a distinct concept – and thus these concepts are often conflated, with which aspect of an algorithm is parallel and which is concurrent not being clearly distinguished. Further, non-parallel, non-concurrent algorithms are often referred to as "[[sequential algorithm]]s", by contrast with concurrent algorithms.		Many parallel algorithms are executed [[concurrent computing\|concurrently]] – though in general [[concurrent algorithm]]s are a distinct concept – and thus these concepts are often conflated, with which aspect of an algorithm is parallel and which is concurrent not being clearly distinguished. Further, non-parallel, non-concurrent algorithms are often referred to as "[[sequential algorithm]]s", by contrast with concurrent algorithms.
Line 10:		Line 10:
	Some problems are easy to divide up into pieces in this way – these are called ''[[embarrassingly parallel problem]]s.'' Examples include many algorithms to solve [[Rubik's Cube]]s and find values which result in a given [[Associative array\|hash]].{{Citation needed\|date=December 2019}}		Some problems are easy to divide up into pieces in this way – these are called ''[[embarrassingly parallel problem]]s.'' Examples include many algorithms to solve [[Rubik's Cube]]s and find values which result in a given [[Associative array\|hash]].{{Citation needed\|date=December 2019}}

	Some problems cannot be split up into parallel portions, as they require the results from a preceding step to effectively carry on with the next step – these are called '''{{visible anchor\|inherently serial problem}}s'''. Examples include iterative [[Numerical analysis\|numerical methods]], such as [[Newton's method]], iterative solutions to the [[three-body problem]], and most of the available algorithms to compute [[pi]] (π).{{citation needed\|date=August 2019}} Some sequential algorithms can be converted into parallel algorithms using [[automatic parallelization]].<ref name="MXian1997">{{cite book\|author1=Megson G M\|author2=Chen Xian\|title=Automatic Parallelization For A Class Of Regular Computations\|url=https://books.google.com/books?id=1wHtCgAAQBAJ~~&printsec=frontcover#v=onepage~~&q=%22parallel~~%20algorithm~~%22~~&f=false~~\|date=4 January 1997\|publisher=World Scientific\|isbn=978-981-4498-41-8}}</ref>		Some problems cannot be split up into parallel portions, as they require the results from a preceding step to effectively carry on with the next step – these are called '''{{visible anchor\|inherently serial problem}}s'''. Examples include iterative [[Numerical analysis\|numerical methods]], such as [[Newton's method]], iterative solutions to the [[three-body problem]], and most of the available algorithms to compute [[pi]] (π).{{citation needed\|date=August 2019}} Some sequential algorithms can be converted into parallel algorithms using [[automatic parallelization]].<ref name="MXian1997">{{cite book\|author1=Megson G M\|author2=Chen Xian\|title=Automatic Parallelization For A Class Of Regular Computations\|url=https://books.google.com/books?id=1wHtCgAAQBAJ&q=%22parallel+algorithm%22\|date=4 January 1997\|publisher=World Scientific\|isbn=978-981-4498-41-8}}</ref>

	==Motivation==		==Motivation==

Freeknowledgecreator: formatting

2020-04-24T09:03:38Z

formatting

← Previous revision		Revision as of 09:03, 24 April 2020
Line 1:		Line 1:
	{{refimprove\|date=November 2012}}		{{refimprove\|date=November 2012}}
	In [[computer science]], a '''parallel algorithm''', as opposed to a traditional [[serial algorithm]], is an [[algorithm]] which can do multiple operations in a given time. It has been a tradition of [[computer science]] to describe serial algorithms in abstract machine models, often the one known as [[Random-access machine]]. Similarly, many computer science researchers have used a so-called [[parallel random-access machine]] (PRAM) as a parallel abstract machine (shared-memory).		In [[computer science]], a '''parallel algorithm''', as opposed to a traditional [[serial algorithm]], is an [[algorithm]] which can do multiple operations in a given time. It has been a tradition of [[computer science]] to describe serial algorithms in abstract machine models, often the one known as [[Random-access machine]]. Similarly, many computer science researchers have used a so-called [[parallel random-access machine]] (PRAM) as a parallel abstract machine (shared-memory).<ref>{{cite paper\| title=Parallel Algorithms \| first1=Guy E. \| last1=Blelloch \| first2=Bruce M. \| last2=Maggs \| publisher=School of Computer Science, [[Carnegie Mellon University]] \| location=USA \| accessdate=2015-07-27 \| url= https://www.cs.cmu.edu/~guyb/papers/BM04.pdf }}</ref><ref>{{cite paper\| title = Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques, 104 pages \| first = Uzi \| last = Vishkin \| publisher = Class notes of courses on parallel algorithms taught since 1992 at the University of Maryland, College Park, Tel Aviv University and the Technion \| date = 2009 \| url=http://www.umiacs.umd.edu/users/vishkin/PUBLICATIONS/classnotes.pdf }}</ref>
	<ref>{{cite paper\| title=Parallel Algorithms \| first1=Guy E. \| last1=Blelloch \| first2=Bruce M. \| last2=Maggs \| publisher=School of Computer Science, [[Carnegie Mellon University]] \| location=USA \| accessdate=2015-07-27 \| url= https://www.cs.cmu.edu/~guyb/papers/BM04.pdf }}</ref>
	<ref>{{cite paper\| title = Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques, 104 pages \| first = Uzi \| last = Vishkin \| publisher = Class notes of courses on parallel algorithms taught since 1992 at the University of Maryland, College Park, Tel Aviv University and the Technion \| date = 2009 \| url=http://www.umiacs.umd.edu/users/vishkin/PUBLICATIONS/classnotes.pdf }}</ref>

	Many parallel algorithms are executed [[concurrent computing\|concurrently]] – though in general [[concurrent algorithm]]s are a distinct concept – and thus these concepts are often conflated, with which aspect of an algorithm is parallel and which is concurrent not being clearly distinguished. Further, non-parallel, non-concurrent algorithms are often referred to as "[[sequential algorithm]]s", by contrast with concurrent algorithms.		Many parallel algorithms are executed [[concurrent computing\|concurrently]] – though in general [[concurrent algorithm]]s are a distinct concept – and thus these concepts are often conflated, with which aspect of an algorithm is parallel and which is concurrent not being clearly distinguished. Further, non-parallel, non-concurrent algorithms are often referred to as "[[sequential algorithm]]s", by contrast with concurrent algorithms.

← Previous revision		Revision as of 08:29, 17 January 2025
Line 1:		Line 1:
			{{Short description\|Algorithm which can do multiple operations in a given time}}
	{{More citations needed\|date=November 2012}}		{{More citations needed\|date=November 2012}}
	In [[computer science]], a '''parallel algorithm''', as opposed to a traditional [[serial algorithm]], is an [[algorithm]] which can do multiple operations in a given time. It has been a tradition of [[computer science]] to describe serial algorithms in [[abstract machine]] models, often the one known as [[random-access machine]]. Similarly, many computer science researchers have used a so-called [[parallel random-access machine]] (PRAM) as a parallel abstract machine (shared-memory).<ref>{{cite web \|title=Parallel Algorithms \|first1=Guy E. \|last1=Blelloch \|first2=Bruce M. \|last2=Maggs \|publisher=School of Computer Science, [[Carnegie Mellon University]] \|location=USA \|access-date=2015-07-27 \|url=https://www.cs.cmu.edu/~guyb/papers/BM04.pdf}}</ref><ref>{{cite web \|title=Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques, 104 pages \|first=Uzi \|last=Vishkin \|publisher=Class notes of courses on parallel algorithms taught since 1992 at the University of Maryland, College Park, Tel Aviv University and the Technion \|date=2009 \|url=http://users.umiacs.umd.edu/~vishkin/PUBLICATIONS/classnotes.pdf}}</ref>		In [[computer science]], a '''parallel algorithm''', as opposed to a traditional [[serial algorithm]], is an [[algorithm]] which can do multiple operations in a given time. It has been a tradition of [[computer science]] to describe serial algorithms in [[abstract machine]] models, often the one known as [[random-access machine]]. Similarly, many computer science researchers have used a so-called [[parallel random-access machine]] (PRAM) as a parallel abstract machine (shared-memory).<ref>{{cite web \|title=Parallel Algorithms \|first1=Guy E. \|last1=Blelloch \|first2=Bruce M. \|last2=Maggs \|publisher=School of Computer Science, [[Carnegie Mellon University]] \|location=USA \|access-date=2015-07-27 \|url=https://www.cs.cmu.edu/~guyb/papers/BM04.pdf}}</ref><ref>{{cite web \|title=Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques, 104 pages \|first=Uzi \|last=Vishkin \|publisher=Class notes of courses on parallel algorithms taught since 1992 at the University of Maryland, College Park, Tel Aviv University and the Technion \|date=2009 \|url=http://users.umiacs.umd.edu/~vishkin/PUBLICATIONS/classnotes.pdf}}</ref>

← Previous revision		Revision as of 06:44, 22 April 2021
Line 1:		Line 1:
	{{refimprove\|date=November 2012}}		{{refimprove\|date=November 2012}}
	In [[computer science]], a '''parallel algorithm''', as opposed to a traditional [[serial algorithm]], is an [[algorithm]] which can do multiple operations in a given time. It has been a tradition of [[computer science]] to describe serial algorithms in abstract machine models, often the one known as [[~~Random~~-access machine]]. Similarly, many computer science researchers have used a so-called [[parallel random-access machine]] (PRAM) as a parallel abstract machine (shared-memory).<ref>{{cite document\| title=Parallel Algorithms \| first1=Guy E. \| last1=Blelloch \| first2=Bruce M. \| last2=Maggs \| publisher=School of Computer Science, [[Carnegie Mellon University]] \| location=USA \| access-date=2015-07-27 \| url= https://www.cs.cmu.edu/~guyb/papers/BM04.pdf }}</ref><ref>{{cite document\| title = Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques, 104 pages \| first = Uzi \| last = Vishkin \| publisher = Class notes of courses on parallel algorithms taught since 1992 at the University of Maryland, College Park, Tel Aviv University and the Technion \| date = 2009 \| url=http://www.umiacs.umd.edu/users/vishkin/PUBLICATIONS/classnotes.pdf }}</ref>		In [[computer science]], a '''parallel algorithm''', as opposed to a traditional [[serial algorithm]], is an [[algorithm]] which can do multiple operations in a given time. It has been a tradition of [[computer science]] to describe serial algorithms in abstract machine models, often the one known as [[random-access machine]]. Similarly, many computer science researchers have used a so-called [[parallel random-access machine]] (PRAM) as a parallel abstract machine (shared-memory).<ref>{{cite document\| title=Parallel Algorithms \| first1=Guy E. \| last1=Blelloch \| first2=Bruce M. \| last2=Maggs \| publisher=School of Computer Science, [[Carnegie Mellon University]] \| location=USA \| access-date=2015-07-27 \| url= https://www.cs.cmu.edu/~guyb/papers/BM04.pdf }}</ref><ref>{{cite document\| title = Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques, 104 pages \| first = Uzi \| last = Vishkin \| publisher = Class notes of courses on parallel algorithms taught since 1992 at the University of Maryland, College Park, Tel Aviv University and the Technion \| date = 2009 \| url=http://www.umiacs.umd.edu/users/vishkin/PUBLICATIONS/classnotes.pdf }}</ref>

	Many parallel algorithms are executed [[concurrent computing\|concurrently]] – though in general [[concurrent algorithm]]s are a distinct concept – and thus these concepts are often conflated, with which aspect of an algorithm is parallel and which is concurrent not being clearly distinguished. Further, non-parallel, non-concurrent algorithms are often referred to as "[[sequential algorithm]]s", by contrast with concurrent algorithms.		Many parallel algorithms are executed [[concurrent computing\|concurrently]] – though in general [[concurrent algorithm]]s are a distinct concept – and thus these concepts are often conflated, with which aspect of an algorithm is parallel and which is concurrent not being clearly distinguished. Further, non-parallel, non-concurrent algorithms are often referred to as "[[sequential algorithm]]s", by contrast with concurrent algorithms.
Line 22:		Line 22:
	[[Shared memory (interprocess communication)\|Shared memory]] processing needs additional [[Lock (computer science)\|locking]] for the data, imposes the overhead of additional processor and bus cycles, and also serializes some portion of the algorithm.		[[Shared memory (interprocess communication)\|Shared memory]] processing needs additional [[Lock (computer science)\|locking]] for the data, imposes the overhead of additional processor and bus cycles, and also serializes some portion of the algorithm.

	[[Message passing]] processing uses channels and message boxes but this communication adds transfer overhead on the bus, additional memory need for queues and message boxes and latency in the messages. Designs of parallel processors use special buses like [[Crossbar switch\|crossbar]] so that the communication overhead will be small but it is the parallel algorithm that decides the volume of the traffic.		[[Message passing]] processing uses channels and message boxes but this communication adds transfer overhead on the bus, additional memory need for queues and message boxes and latency in the messages. Designs of parallel processors use special [[Bus (computing)\|buses]] like [[Crossbar switch\|crossbar]] so that the communication overhead will be small but it is the parallel algorithm that decides the volume of the traffic.

	If the communication overhead of additional processors outweighs the benefit of adding another processor, one encounters [[parallel slowdown]].		If the communication overhead of additional processors outweighs the benefit of adding another processor, one encounters [[parallel slowdown]].

← Previous revision		Revision as of 04:50, 28 December 2020
Line 1:		Line 1:
	{{refimprove\|date=November 2012}}		{{refimprove\|date=November 2012}}
	In [[computer science]], a '''parallel algorithm''', as opposed to a traditional [[serial algorithm]], is an [[algorithm]] which can do multiple operations in a given time. It has been a tradition of [[computer science]] to describe serial algorithms in abstract machine models, often the one known as [[Random-access machine]]. Similarly, many computer science researchers have used a so-called [[parallel random-access machine]] (PRAM) as a parallel abstract machine (shared-memory).<ref>{{cite document\| title=Parallel Algorithms \| first1=Guy E. \| last1=Blelloch \| first2=Bruce M. \| last2=Maggs \| publisher=School of Computer Science, [[Carnegie Mellon University]] \| location=USA \| ~~accessdate~~=2015-07-27 \| url= https://www.cs.cmu.edu/~guyb/papers/BM04.pdf }}</ref><ref>{{cite document\| title = Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques, 104 pages \| first = Uzi \| last = Vishkin \| publisher = Class notes of courses on parallel algorithms taught since 1992 at the University of Maryland, College Park, Tel Aviv University and the Technion \| date = 2009 \| url=http://www.umiacs.umd.edu/users/vishkin/PUBLICATIONS/classnotes.pdf }}</ref>		In [[computer science]], a '''parallel algorithm''', as opposed to a traditional [[serial algorithm]], is an [[algorithm]] which can do multiple operations in a given time. It has been a tradition of [[computer science]] to describe serial algorithms in abstract machine models, often the one known as [[Random-access machine]]. Similarly, many computer science researchers have used a so-called [[parallel random-access machine]] (PRAM) as a parallel abstract machine (shared-memory).<ref>{{cite document\| title=Parallel Algorithms \| first1=Guy E. \| last1=Blelloch \| first2=Bruce M. \| last2=Maggs \| publisher=School of Computer Science, [[Carnegie Mellon University]] \| location=USA \| access-date=2015-07-27 \| url= https://www.cs.cmu.edu/~guyb/papers/BM04.pdf }}</ref><ref>{{cite document\| title = Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques, 104 pages \| first = Uzi \| last = Vishkin \| publisher = Class notes of courses on parallel algorithms taught since 1992 at the University of Maryland, College Park, Tel Aviv University and the Technion \| date = 2009 \| url=http://www.umiacs.umd.edu/users/vishkin/PUBLICATIONS/classnotes.pdf }}</ref>

	Many parallel algorithms are executed [[concurrent computing\|concurrently]] – though in general [[concurrent algorithm]]s are a distinct concept – and thus these concepts are often conflated, with which aspect of an algorithm is parallel and which is concurrent not being clearly distinguished. Further, non-parallel, non-concurrent algorithms are often referred to as "[[sequential algorithm]]s", by contrast with concurrent algorithms.		Many parallel algorithms are executed [[concurrent computing\|concurrently]] – though in general [[concurrent algorithm]]s are a distinct concept – and thus these concepts are often conflated, with which aspect of an algorithm is parallel and which is concurrent not being clearly distinguished. Further, non-parallel, non-concurrent algorithms are often referred to as "[[sequential algorithm]]s", by contrast with concurrent algorithms.

← Previous revision		Revision as of 02:14, 7 November 2020
Line 1:		Line 1:
	{{refimprove\|date=November 2012}}		{{refimprove\|date=November 2012}}
	In [[computer science]], a '''parallel algorithm''', as opposed to a traditional [[serial algorithm]], is an [[algorithm]] which can do multiple operations in a given time. It has been a tradition of [[computer science]] to describe serial algorithms in abstract machine models, often the one known as [[Random-access machine]]. Similarly, many computer science researchers have used a so-called [[parallel random-access machine]] (PRAM) as a parallel abstract machine (shared-memory).<ref>{{cite ~~paper~~\| title=Parallel Algorithms \| first1=Guy E. \| last1=Blelloch \| first2=Bruce M. \| last2=Maggs \| publisher=School of Computer Science, [[Carnegie Mellon University]] \| location=USA \| accessdate=2015-07-27 \| url= https://www.cs.cmu.edu/~guyb/papers/BM04.pdf }}</ref><ref>{{cite ~~paper~~\| title = Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques, 104 pages \| first = Uzi \| last = Vishkin \| publisher = Class notes of courses on parallel algorithms taught since 1992 at the University of Maryland, College Park, Tel Aviv University and the Technion \| date = 2009 \| url=http://www.umiacs.umd.edu/users/vishkin/PUBLICATIONS/classnotes.pdf }}</ref>		In [[computer science]], a '''parallel algorithm''', as opposed to a traditional [[serial algorithm]], is an [[algorithm]] which can do multiple operations in a given time. It has been a tradition of [[computer science]] to describe serial algorithms in abstract machine models, often the one known as [[Random-access machine]]. Similarly, many computer science researchers have used a so-called [[parallel random-access machine]] (PRAM) as a parallel abstract machine (shared-memory).<ref>{{cite document\| title=Parallel Algorithms \| first1=Guy E. \| last1=Blelloch \| first2=Bruce M. \| last2=Maggs \| publisher=School of Computer Science, [[Carnegie Mellon University]] \| location=USA \| accessdate=2015-07-27 \| url= https://www.cs.cmu.edu/~guyb/papers/BM04.pdf }}</ref><ref>{{cite document\| title = Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques, 104 pages \| first = Uzi \| last = Vishkin \| publisher = Class notes of courses on parallel algorithms taught since 1992 at the University of Maryland, College Park, Tel Aviv University and the Technion \| date = 2009 \| url=http://www.umiacs.umd.edu/users/vishkin/PUBLICATIONS/classnotes.pdf }}</ref>

	Many parallel algorithms are executed [[concurrent computing\|concurrently]] – though in general [[concurrent algorithm]]s are a distinct concept – and thus these concepts are often conflated, with which aspect of an algorithm is parallel and which is concurrent not being clearly distinguished. Further, non-parallel, non-concurrent algorithms are often referred to as "[[sequential algorithm]]s", by contrast with concurrent algorithms.		Many parallel algorithms are executed [[concurrent computing\|concurrently]] – though in general [[concurrent algorithm]]s are a distinct concept – and thus these concepts are often conflated, with which aspect of an algorithm is parallel and which is concurrent not being clearly distinguished. Further, non-parallel, non-concurrent algorithms are often referred to as "[[sequential algorithm]]s", by contrast with concurrent algorithms.
Line 10:		Line 10:
	Some problems are easy to divide up into pieces in this way – these are called ''[[embarrassingly parallel problem]]s.'' Examples include many algorithms to solve [[Rubik's Cube]]s and find values which result in a given [[Associative array\|hash]].{{Citation needed\|date=December 2019}}		Some problems are easy to divide up into pieces in this way – these are called ''[[embarrassingly parallel problem]]s.'' Examples include many algorithms to solve [[Rubik's Cube]]s and find values which result in a given [[Associative array\|hash]].{{Citation needed\|date=December 2019}}

	Some problems cannot be split up into parallel portions, as they require the results from a preceding step to effectively carry on with the next step – these are called '''{{visible anchor\|inherently serial problem}}s'''. Examples include iterative [[Numerical analysis\|numerical methods]], such as [[Newton's method]], iterative solutions to the [[three-body problem]], and most of the available algorithms to compute [[pi]] (π).{{citation needed\|date=August 2019}} Some sequential algorithms can be converted into parallel algorithms using [[automatic parallelization]].<ref name="MXian1997">{{cite book\|author1=Megson G M\|author2=Chen Xian\|title=Automatic Parallelization For A Class Of Regular Computations\|url=https://books.google.com/books?id=1wHtCgAAQBAJ~~&printsec=frontcover#v=onepage~~&q=%22parallel~~%20algorithm~~%22~~&f=false~~\|date=4 January 1997\|publisher=World Scientific\|isbn=978-981-4498-41-8}}</ref>		Some problems cannot be split up into parallel portions, as they require the results from a preceding step to effectively carry on with the next step – these are called '''{{visible anchor\|inherently serial problem}}s'''. Examples include iterative [[Numerical analysis\|numerical methods]], such as [[Newton's method]], iterative solutions to the [[three-body problem]], and most of the available algorithms to compute [[pi]] (π).{{citation needed\|date=August 2019}} Some sequential algorithms can be converted into parallel algorithms using [[automatic parallelization]].<ref name="MXian1997">{{cite book\|author1=Megson G M\|author2=Chen Xian\|title=Automatic Parallelization For A Class Of Regular Computations\|url=https://books.google.com/books?id=1wHtCgAAQBAJ&q=%22parallel+algorithm%22\|date=4 January 1997\|publisher=World Scientific\|isbn=978-981-4498-41-8}}</ref>

	==Motivation==		==Motivation==

← Previous revision		Revision as of 09:03, 24 April 2020
Line 1:		Line 1:
	{{refimprove\|date=November 2012}}		{{refimprove\|date=November 2012}}
	In [[computer science]], a '''parallel algorithm''', as opposed to a traditional [[serial algorithm]], is an [[algorithm]] which can do multiple operations in a given time. It has been a tradition of [[computer science]] to describe serial algorithms in abstract machine models, often the one known as [[Random-access machine]]. Similarly, many computer science researchers have used a so-called [[parallel random-access machine]] (PRAM) as a parallel abstract machine (shared-memory).		In [[computer science]], a '''parallel algorithm''', as opposed to a traditional [[serial algorithm]], is an [[algorithm]] which can do multiple operations in a given time. It has been a tradition of [[computer science]] to describe serial algorithms in abstract machine models, often the one known as [[Random-access machine]]. Similarly, many computer science researchers have used a so-called [[parallel random-access machine]] (PRAM) as a parallel abstract machine (shared-memory).<ref>{{cite paper\| title=Parallel Algorithms \| first1=Guy E. \| last1=Blelloch \| first2=Bruce M. \| last2=Maggs \| publisher=School of Computer Science, [[Carnegie Mellon University]] \| location=USA \| accessdate=2015-07-27 \| url= https://www.cs.cmu.edu/~guyb/papers/BM04.pdf }}</ref><ref>{{cite paper\| title = Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques, 104 pages \| first = Uzi \| last = Vishkin \| publisher = Class notes of courses on parallel algorithms taught since 1992 at the University of Maryland, College Park, Tel Aviv University and the Technion \| date = 2009 \| url=http://www.umiacs.umd.edu/users/vishkin/PUBLICATIONS/classnotes.pdf }}</ref>
	<ref>{{cite paper\| title=Parallel Algorithms \| first1=Guy E. \| last1=Blelloch \| first2=Bruce M. \| last2=Maggs \| publisher=School of Computer Science, [[Carnegie Mellon University]] \| location=USA \| accessdate=2015-07-27 \| url= https://www.cs.cmu.edu/~guyb/papers/BM04.pdf }}</ref>
	<ref>{{cite paper\| title = Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques, 104 pages \| first = Uzi \| last = Vishkin \| publisher = Class notes of courses on parallel algorithms taught since 1992 at the University of Maryland, College Park, Tel Aviv University and the Technion \| date = 2009 \| url=http://www.umiacs.umd.edu/users/vishkin/PUBLICATIONS/classnotes.pdf }}</ref>

	Many parallel algorithms are executed [[concurrent computing\|concurrently]] – though in general [[concurrent algorithm]]s are a distinct concept – and thus these concepts are often conflated, with which aspect of an algorithm is parallel and which is concurrent not being clearly distinguished. Further, non-parallel, non-concurrent algorithms are often referred to as "[[sequential algorithm]]s", by contrast with concurrent algorithms.		Many parallel algorithms are executed [[concurrent computing\|concurrently]] – though in general [[concurrent algorithm]]s are a distinct concept – and thus these concepts are often conflated, with which aspect of an algorithm is parallel and which is concurrent not being clearly distinguished. Further, non-parallel, non-concurrent algorithms are often referred to as "[[sequential algorithm]]s", by contrast with concurrent algorithms.