Talk:Parallel algorithm - Revision history

Qwerfjkl (bot): Implementing WP:PIQA (Task 26)

2024-02-02T22:58:10Z

← Previous revision		Revision as of 22:58, 2 February 2024
Line 1:		Line 1:
	{{WikiProject ~~Computing~~\|class=Start\|~~importance=}}~~		{{WikiProject banner shell\|class=Start\|
	{{WikiProject ~~Computer science\|class=Start~~\|importance=~~mid~~}}		{{WikiProject Computing\|importance=}}
			{{WikiProject Computer science\|importance=mid}}
			}}

	== Parallel programming ==		== Parallel programming ==

Billwoo2011 at 23:49, 22 January 2021

2021-01-22T23:49:56Z

← Previous revision		Revision as of 23:49, 22 January 2021
Line 48:		Line 48:

	:Indeed, removed it from the page. A parallel version can be found [https://www.cs.cmu.edu/~scandal/nesl/alg-numerical.html#primes here]. [[User:Qwertyus\|Q<small>VVERTYVS</small>]] <small>([[User talk:Qwertyus\|hm?]])</small> 20:42, 15 May 2015 (UTC)		:Indeed, removed it from the page. A parallel version can be found [https://www.cs.cmu.edu/~scandal/nesl/alg-numerical.html#primes here]. [[User:Qwertyus\|Q<small>VVERTYVS</small>]] <small>([[User talk:Qwertyus\|hm?]])</small> 20:42, 15 May 2015 (UTC)

			== Confusing Lead ==
			"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.".
			Can't all algorithms can do multiple operations in a "given time"? Parallel algorithms are defined by allowing operations to be performed at the same time are they not? From the reference: "... it is usually necessary to design an algorithm that specifies multiple operations on each step, i.e., a parallel algorithm." Single step is not synonymous with "given time", I think "simultaneously"/"same time" would be more explicit [[User:Billwoo2011\|Billwoo2011]] ([[User talk:Billwoo2011\|talk]]) 23:49, 22 January 2021 (UTC)

Qwertyus: /* The sieve of Eratosthenes parallelisation */

2015-05-15T20:42:56Z

The sieve of Eratosthenes parallelisation

← Previous revision		Revision as of 20:42, 15 May 2015
Line 46:		Line 46:
	* the outer loop iterates over already found prime numbers - this loop is serial, because it uses knowledge of composite numbers from previous iterations to save work;		* the outer loop iterates over already found prime numbers - this loop is serial, because it uses knowledge of composite numbers from previous iterations to save work;
	* the inner loop iterates over the whole prescribed number set to mark multiples of a given prime number (from the outer loop) as composite - this can be done in parallel. <small class="autosigned">— Preceding [[Wikipedia:Signatures\|unsigned]] comment added by [[Special:Contributions/83.25.127.16\|83.25.127.16]] ([[User talk:83.25.127.16\|talk]]) 08:24, 18 April 2015 (UTC)</small><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->		* the inner loop iterates over the whole prescribed number set to mark multiples of a given prime number (from the outer loop) as composite - this can be done in parallel. <small class="autosigned">— Preceding [[Wikipedia:Signatures\|unsigned]] comment added by [[Special:Contributions/83.25.127.16\|83.25.127.16]] ([[User talk:83.25.127.16\|talk]]) 08:24, 18 April 2015 (UTC)</small><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->

			:Indeed, removed it from the page. A parallel version can be found [https://www.cs.cmu.edu/~scandal/nesl/alg-numerical.html#primes here]. [[User:Qwertyus\|Q<small>VVERTYVS</small>]] <small>([[User talk:Qwertyus\|hm?]])</small> 20:42, 15 May 2015 (UTC)

SineBot: Signing comment by 83.25.127.16 - "/* The sieve of Eratosthenes parallelisation */ new section"

2015-04-18T08:25:14Z

Signing comment by 83.25.127.16 - "The sieve of Eratosthenes parallelisation: new section"

← Previous revision		Revision as of 08:25, 18 April 2015
Line 45:		Line 45:
	This article states that the sieve of Eratosthenes is inherently serial. That is not true. The sieve of Eratosthenes consists of two loops:		This article states that the sieve of Eratosthenes is inherently serial. That is not true. The sieve of Eratosthenes consists of two loops:
	* the outer loop iterates over already found prime numbers - this loop is serial, because it uses knowledge of composite numbers from previous iterations to save work;		* the outer loop iterates over already found prime numbers - this loop is serial, because it uses knowledge of composite numbers from previous iterations to save work;
	* the inner loop iterates over the whole prescribed number set to mark multiples of a given prime number (from the outer loop) as composite - this can be done in parallel.		* the inner loop iterates over the whole prescribed number set to mark multiples of a given prime number (from the outer loop) as composite - this can be done in parallel. <small class="autosigned">— Preceding [[Wikipedia:Signatures\|unsigned]] comment added by [[Special:Contributions/83.25.127.16\|83.25.127.16]] ([[User talk:83.25.127.16\|talk]]) 08:24, 18 April 2015 (UTC)</small><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->

83.25.127.16: /* The sieve of Eratosthenes parallelisation */ new section

2015-04-18T08:24:06Z

The sieve of Eratosthenes parallelisation: new section

← Previous revision		Revision as of 08:24, 18 April 2015
Line 40:		Line 40:

	I think that is meant to be inherently sequential. <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures\|unsigned]] comment added by [[Special:Contributions/119.224.35.68\|119.224.35.68]] ([[User talk:119.224.35.68\|talk]]) 22:40, 31 December 2009 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->		I think that is meant to be inherently sequential. <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures\|unsigned]] comment added by [[Special:Contributions/119.224.35.68\|119.224.35.68]] ([[User talk:119.224.35.68\|talk]]) 22:40, 31 December 2009 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->

			== The sieve of Eratosthenes parallelisation ==

			This article states that the sieve of Eratosthenes is inherently serial. That is not true. The sieve of Eratosthenes consists of two loops:
			* the outer loop iterates over already found prime numbers - this loop is serial, because it uses knowledge of composite numbers from previous iterations to save work;
			* the inner loop iterates over the whole prescribed number set to mark multiples of a given prime number (from the outer loop) as composite - this can be done in parallel.

121.45.201.75: set to mid importance for computer science

2012-03-10T22:54:48Z

set to mid importance for computer science

← Previous revision		Revision as of 22:54, 10 March 2012
Line 1:		Line 1:
	{{WikiProject Computing\|class=Start\|importance=}}		{{WikiProject Computing\|class=Start\|importance=}}
	{{WikiProject Computer science\|class=Start\|importance=~~low~~}}		{{WikiProject Computer science\|class=Start\|importance=mid}}

	== Parallel programming ==		== Parallel programming ==

SineBot: Signing comment by 119.224.35.68 - "/* inherently serial? */ new section"

2009-12-31T22:42:03Z

Signing comment by 119.224.35.68 - "inherently serial?: new section"

← Previous revision		Revision as of 22:42, 31 December 2009
Line 39:		Line 39:
	== inherently serial? ==		== inherently serial? ==

			I think that is meant to be inherently sequential. <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures\|unsigned]] comment added by [[Special:Contributions/119.224.35.68\|119.224.35.68]] ([[User talk:119.224.35.68\|talk]]) 22:40, 31 December 2009 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->
	I think that is meant to be inherently sequential.

119.224.35.68: /* inherently serial? */ new section

2009-12-31T22:40:58Z

inherently serial?: new section

← Previous revision		Revision as of 22:40, 31 December 2009
Line 36:		Line 36:

	I'd made it a footnote to the end of the paragraph, because it wasn't immediately obvious to me how to make it flow well with the rest of the article. If someone finds it useful (and accurate, I hope!), feel free to add it back in. ~ [[User:Jeffq\|Jeff Q]] [[User talk:Jeffq\|(talk)]] 12:26, 29 August 2009 (UTC)		I'd made it a footnote to the end of the paragraph, because it wasn't immediately obvious to me how to make it flow well with the rest of the article. If someone finds it useful (and accurate, I hope!), feel free to add it back in. ~ [[User:Jeffq\|Jeff Q]] [[User talk:Jeffq\|(talk)]] 12:26, 29 August 2009 (UTC)

			== inherently serial? ==

			I think that is meant to be inherently sequential.

Jeffq: /* Parallel algorithms are valuable */ new section

2009-08-29T12:26:24Z

Parallel algorithms are valuable: new section

← Previous revision		Revision as of 12:26, 29 August 2009
Line 11:		Line 11:
	There are entirely ("embarrassingly") parallel algorithms for computing digits of <math>\pi</math>. For example, see D. H. Bailey, P. B. Borwein and S. Plouffe, "On The Rapid Computation of Various Polylogarithmic Constants", manuscript, 1996, which is [http://citeseer.ist.psu.edu/bailey96rapid.html		There are entirely ("embarrassingly") parallel algorithms for computing digits of <math>\pi</math>. For example, see D. H. Bailey, P. B. Borwein and S. Plouffe, "On The Rapid Computation of Various Polylogarithmic Constants", manuscript, 1996, which is [http://citeseer.ist.psu.edu/bailey96rapid.html
	available via Citeseer]. Also, just because an algorithm appears to have linear data dependencies doesn't mean that it can't be effectively parallelized. For details, see G. Blelloch, "Vector Models for Data-Parallel Computing." <small>—Preceding [[Wikipedia:Signatures\|unsigned]] comment added by [[User:Hilbertastronaut\|Hilbertastronaut]] ([[User talk:Hilbertastronaut\|talk]] • [[Special:Contributions/Hilbertastronaut\|contribs]]) 16:53, 12 October 2007 (UTC)</small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->		available via Citeseer]. Also, just because an algorithm appears to have linear data dependencies doesn't mean that it can't be effectively parallelized. For details, see G. Blelloch, "Vector Models for Data-Parallel Computing." <small>—Preceding [[Wikipedia:Signatures\|unsigned]] comment added by [[User:Hilbertastronaut\|Hilbertastronaut]] ([[User talk:Hilbertastronaut\|talk]] • [[Special:Contributions/Hilbertastronaut\|contribs]]) 16:53, 12 October 2007 (UTC)</small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->

			== Parallel algorithms are valuable ==

			I completely rewrote the "Parallel algorithms are valuable" paragraph because it seemed a bit confused. Here's what it had said:

			: ''Parallel algorithms are valuable because it is faster to perform large computing tasks via a parallel algorithm than it is via a serial (non-parallel) algorithm, because of the way modern processors work. It is far more difficult to construct a computer with a single fast processor than one with many slow processors with the same throughput. There are also certain theoretical limits to the potential speed of serial processors. Every parallel algorithm has a serial part and so parallel algorithms have a saturation point (see [[Amdahl's law]]). After that point adding more processors does not yield any more throughput but only increases the overhead and cost.''

			I'd already rewritten the first sentence to be more specific:

			: ''Parallel algorithms are valuable because of substantial improvements in [[multiprocessing]] systems and the rise of [[multi-core]] processors.''

			Then I realized that the rest of the material had two serious problemms. First, without the appropriate context, the second sentence is exactly backwards. It's typically more difficult to build a ''multiprocessor'' system than a ''uniprocessor'' system with a given throughput – unless, of course, the uniprocessor itself can't be built. Second, the rest of the paragraph conflated several ideas:

			* Theoretical limits to "serial" processor (actually uniprocessor) speed
			* Amdahl's law (relationship between serial & parallel components and potential speedup)
			* An undefined "saturation point" (presumably the maximum speedup, but no such term is in the article)
			* Discussion of overhead (something not included in Amdahl's law, but part of the [[Karp-Flatt metric]])

			The result is that it starts out talking about the limitations of serial processing, and winds up using a theory of the limitations of ''parallel'' processing to make its point.

			After I'd pointlessly tried to straighten out the discussions of parallel processing limitations, I finally just cleaned up the original point: ''parallel algorithms are valuable''. But here's the parallel-problems material I wrote:

			: ''However, parallel algorithms have similar limitations because they always contain some sequential components. Furthermore, overhead in parallel decomposition and collection invokes the law of [[diminishing returns]], putting practical limits on the degree of parallelism for a given algorithm and implementation environment. [[Amdahl's law]], [[Gustafson's law]], and the [[Karp-Flatt metric]] attempt to describe the relationships between the components of parallel algorithms and their potential and/or realized benefits.''

			I'd made it a footnote to the end of the paragraph, because it wasn't immediately obvious to me how to make it flow well with the rest of the article. If someone finds it useful (and accurate, I hope!), feel free to add it back in. ~ [[User:Jeffq\|Jeff Q]] [[User talk:Jeffq\|(talk)]] 12:26, 29 August 2009 (UTC)

Jeffq: added headings to 2 earlier posts; deleted nonsensical post from 70.19.84.16 on 3 October 2006

2009-08-29T11:46:15Z

added headings to 2 earlier posts; deleted nonsensical post from 70.19.84.16 on 3 October 2006

← Previous revision		Revision as of 11:46, 29 August 2009
Line 1:		Line 1:
	{{WikiProject Computing\|class=Start\|importance=}}		{{WikiProject Computing\|class=Start\|importance=}}
	{{WikiProject Computer science\|class=Start\|importance=low}}		{{WikiProject Computer science\|class=Start\|importance=low}}

			== Parallel programming ==

	I typed in '/wiki/Parallel_programming' and got 'Parallel computing', but this is the page I wanted.		I typed in '/wiki/Parallel_programming' and got 'Parallel computing', but this is the page I wanted.
			<span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures\|unsigned]] comment added by [[User:72.148.222.140\|72.148.222.140]] ([[User talk:72.148.222.140\|talk]] • [[Special:Contributions/72.148.222.140\|contribs]]) 05:30, 14 March 2006</span><!-- Template:Unsigned2 -->
	[[Category:[[Category:[[Category:[[Category:[[Category:]]]]]]]]]]#REDIRECT[[]]

			== Embarrassingly parallel π algorithms ==

	There are entirely ("embarrassingly") parallel algorithms for computing digits of <math>\pi</math>. For example, see D. H. Bailey, P. B. Borwein and S. Plouffe, "On The Rapid Computation of Various Polylogarithmic Constants", manuscript, 1996, which is [http://citeseer.ist.psu.edu/bailey96rapid.html		There are entirely ("embarrassingly") parallel algorithms for computing digits of <math>\pi</math>. For example, see D. H. Bailey, P. B. Borwein and S. Plouffe, "On The Rapid Computation of Various Polylogarithmic Constants", manuscript, 1996, which is [http://citeseer.ist.psu.edu/bailey96rapid.html