CSC/ECE 506 Spring 2012/4b rs - Revision history

Rchakar: /* Parallel Search http://stackoverflow.com/questions/4332967/where-does-super-linear-speedup-come-from */

2012-02-21T04:38:29Z

Parallel Search http://stackoverflow.com/questions/4332967/where-does-super-linear-speedup-come-from

← Older revision		Revision as of 04:38, 21 February 2012
Line 98:		Line 98:
	Let us look at the reasons for super-linear speedup. The data set of a given problem could be much larger than the cache size when the problem is executed serially. In [http://en.wikipedia.org/wiki/Parallel_computing parallel computation], however, the data set has enough space in each cache that is available. In problems that involve searching a data structure, multiple searches can be executed at the same time. This reduces the termination time. Another reason is the efficient utilization of resources by [http://en.wikipedia.org/wiki/Multiprocessing multiprocessors].		Let us look at the reasons for super-linear speedup. The data set of a given problem could be much larger than the cache size when the problem is executed serially. In [http://en.wikipedia.org/wiki/Parallel_computing parallel computation], however, the data set has enough space in each cache that is available. In problems that involve searching a data structure, multiple searches can be executed at the same time. This reduces the termination time. Another reason is the efficient utilization of resources by [http://en.wikipedia.org/wiki/Multiprocessing multiprocessors].

	===Parallel Search <ref>http://stackoverflow.com/questions/4332967/where-does-super-linear-speedup-come-from</ref>===		===Reasons for the discrepancy in the 'Parallel Search' <ref>http://stackoverflow.com/questions/4332967/where-does-super-linear-speedup-come-from</ref>===
	When search is being performed in parallel on multiple processors, the amount of work being done is lesser than the amount of work being done serially. Let us see why this is so:		When search is being performed in parallel on multiple processors, the amount of work being done is lesser than the amount of work being done serially. Let us see why this is so:

Rchakar: /* External links */

2012-02-21T04:12:22Z

External links

← Older revision		Revision as of 04:12, 21 February 2012
Line 157:		Line 157:

	8. [http://www.xbitlabs.com/articles/cpu/display/kentsfield-preview.html Intel "Kentsfield" processor]		8. [http://www.xbitlabs.com/articles/cpu/display/kentsfield-preview.html Intel "Kentsfield" processor]

			9. [http://www.netlib.org/benchmark/karp-challenge "Karp Challenge"]

	==References==		==References==
	<references/>		<references/>

Rchakar: /* Gordon Bell prize http://techresearch.intel.com/ResearcherDetails.aspx?Id=182 http://en.wikipedia.org/wiki/Gordon_Bell_Prize */

2012-02-21T04:11:46Z

Gordon Bell prize http://techresearch.intel.com/ResearcherDetails.aspx?Id=182 http://en.wikipedia.org/wiki/Gordon_Bell_Prize

← Older revision		Revision as of 04:11, 21 February 2012
Line 83:		Line 83:
	The Prizes were preceded by a similar much smaller prize (nominal: $100) by Alan Karp, a numerical analyst (then of IBM; won by Gustafson and Montry) challenging claims of MIMD performance improvements proposed in the Letters to the Editor section of the [http://en.wikipedia.org/wiki/Communications_of_the_ACM Communications of the ACM] who went on to be one of the first Bell Prize judges. Cash prizes accompany these recognitions and are funded by the award founder, [http://en.wikipedia.org/wiki/Gordon_Bell Gordon Bell], a pioneer in high-performance and parallel computing.		The Prizes were preceded by a similar much smaller prize (nominal: $100) by Alan Karp, a numerical analyst (then of IBM; won by Gustafson and Montry) challenging claims of MIMD performance improvements proposed in the Letters to the Editor section of the [http://en.wikipedia.org/wiki/Communications_of_the_ACM Communications of the ACM] who went on to be one of the first Bell Prize judges. Cash prizes accompany these recognitions and are funded by the award founder, [http://en.wikipedia.org/wiki/Gordon_Bell Gordon Bell], a pioneer in high-performance and parallel computing.

	[http://en.wikipedia.org/wiki/John_L._Gustafson Dr. John L. Gustafson] introduced the first commercial cluster system in 1985 and having first demonstrated 1000x, scalable parallel performance on real applications in 1988, for which he won the inaugural Gordon Bell Award. That demonstration broke the “Karp Challenge” that claimed speedup of more than 200x was a practical impossibility; it created a watershed that led to the widespread manufacture and use of highly parallel computers.		[http://en.wikipedia.org/wiki/John_L._Gustafson Dr. John L. Gustafson] introduced the first commercial cluster system in 1985 and having first demonstrated 1000x, scalable parallel performance on real applications in 1988, for which he won the inaugural Gordon Bell Award. That demonstration broke the [http://www.netlib.org/benchmark/karp-challenge “Karp Challenge”] that claimed speedup of more than 200x was a practical impossibility; it created a watershed that led to the widespread manufacture and use of highly parallel computers.


	==Superlinear speedup <ref>http://www.ccs.neu.edu/course/com3620/projects/scalable/jshan/final1.pdf</ref>==		==Superlinear speedup <ref>http://www.ccs.neu.edu/course/com3620/projects/scalable/jshan/final1.pdf</ref>==

Sshanbh: /* Superlinear speedup */

2012-02-14T04:27:18Z

Superlinear speedup

← Older revision		Revision as of 04:27, 14 February 2012
Line 138:		Line 138:
	Conclusion drawn from Gustafson’s law is that it should be possible to get high speedup if we scale up the problem size.		Conclusion drawn from Gustafson’s law is that it should be possible to get high speedup if we scale up the problem size.

	===~~Superlinear~~ speedup===		===Super-linear speedup===

			Even though in theory the maximum possible speedup is equal to the number of parallel processors, in practice we do see speedups higher than the number of processors, or in other words, super-linear speedup. It is considered controversial by purists because of the skepticism regarding the means of achieving this high speedup. If super-linear speedup is achievable, it gives an extremely high degree of parallelism and also provides maximum utilization of resources.

	== External links ==		== External links ==

Rchakar: /* Scaled speedup http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&sqi=2&ved=0CCkQFjAB&url=http%3A%2F%2Fcoitweb.uncc.edu%2F~abw%2FITCS4145F10%2Fslides1a.ppt&ei=rq05T_zOOpKutwe635jRAg&usg=AFQjCNFMNTKEQ2P9G4zV3fGWyaMbmYtsMQhttp://spartan.

2012-02-14T03:37:43Z

/* Scaled speedup http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&sqi=2&ved=0CCkQFjAB&url=http%3A%2F%2Fcoitweb.uncc.edu%2F~abw%2FITCS4145F10%2Fslides1a.ppt&ei=rq05T_zOOpKutwe635jRAg&usg=AFQjCNFMNTKEQ2P9G4zV3fGWyaMbmYtsMQhttp://spartan.

← Older revision		Revision as of 03:37, 14 February 2012
Line 134:		Line 134:
	Gustafson's formulation gives an illusion that as if ''number of processors'' can increase indefinitely. A closer look finds that the increase in serial parts of a program is affecting speedup negatively. The rate of speedup decrease as ''number of processors'' approaches infinity, if we translate the scaled-percentage to a non-scaled percentage. We cannot observe the speedup impact by ''number of processors'' using Gustafson's formulation directly since it contains a ''number of processors'' dependent variable serial parts of a program.		Gustafson's formulation gives an illusion that as if ''number of processors'' can increase indefinitely. A closer look finds that the increase in serial parts of a program is affecting speedup negatively. The rate of speedup decrease as ''number of processors'' approaches infinity, if we translate the scaled-percentage to a non-scaled percentage. We cannot observe the speedup impact by ''number of processors'' using Gustafson's formulation directly since it contains a ''number of processors'' dependent variable serial parts of a program.

	Even though ~~[http://en.wikipedia.org/wiki/Gustafson%27s_law#Derivation_of_Gustafson.27s_Law~~ Amdahl's law] is theoretically correct, the serial percentage is not practically obtainable. For example, if the serial percentage is to be derived from computational experiments, i.e. recording the total parallel elapsed time and the parallel-only elapsed time, then it can contain all overheads, such as communication, synchronization, input/output and memory access. The law offers no help to separate these factors. On the other hand, if we obtain the serial percentage by counting the number of total serial and parallel instructions in a program, then all other overheads are excluded. However, in this case the predicted speedup may never agree with the experiments.		Even though Amdahl's law is theoretically correct, the serial percentage is not practically obtainable. For example, if the serial percentage is to be derived from computational experiments, i.e. recording the total parallel elapsed time and the parallel-only elapsed time, then it can contain all overheads, such as communication, synchronization, input/output and memory access. The law offers no help to separate these factors. On the other hand, if we obtain the serial percentage by counting the number of total serial and parallel instructions in a program, then all other overheads are excluded. However, in this case the predicted speedup may never agree with the experiments.

	Conclusion drawn from Gustafson’s law is that it should be possible to get high speedup if we scale up the problem size.		Conclusion drawn from Gustafson’s law is that it should be possible to get high speedup if we scale up the problem size.

Rchakar: /* Scaled speedup http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&sqi=2&ved=0CCkQFjAB&url=http%3A%2F%2Fcoitweb.uncc.edu%2F~abw%2FITCS4145F10%2Fslides1a.ppt&ei=rq05T_zOOpKutwe635jRAg&usg=AFQjCNFMNTKEQ2P9G4zV3fGWyaMbmYtsMQhttp://spartan.

2012-02-14T02:31:46Z

← Older revision		Revision as of 02:31, 14 February 2012
Line 134:		Line 134:
	Gustafson's formulation gives an illusion that as if ''number of processors'' can increase indefinitely. A closer look finds that the increase in serial parts of a program is affecting speedup negatively. The rate of speedup decrease as ''number of processors'' approaches infinity, if we translate the scaled-percentage to a non-scaled percentage. We cannot observe the speedup impact by ''number of processors'' using Gustafson's formulation directly since it contains a ''number of processors'' dependent variable serial parts of a program.		Gustafson's formulation gives an illusion that as if ''number of processors'' can increase indefinitely. A closer look finds that the increase in serial parts of a program is affecting speedup negatively. The rate of speedup decrease as ''number of processors'' approaches infinity, if we translate the scaled-percentage to a non-scaled percentage. We cannot observe the speedup impact by ''number of processors'' using Gustafson's formulation directly since it contains a ''number of processors'' dependent variable serial parts of a program.

	Even though Amdahl's ~~Law~~ is theoretically correct, the serial percentage is not practically obtainable. For example, if the serial percentage is to be derived from computational experiments, i.e. recording the total parallel elapsed time and the parallel-only elapsed time, then it can contain all overheads, such as communication, synchronization, input/output and memory access. The law offers no help to separate these factors. On the other hand, if we obtain the serial percentage by counting the number of total serial and parallel instructions in a program, then all other overheads are excluded. However, in this case the predicted speedup may never agree with the experiments.		Even though [http://en.wikipedia.org/wiki/Gustafson%27s_law#Derivation_of_Gustafson.27s_Law Amdahl's law] is theoretically correct, the serial percentage is not practically obtainable. For example, if the serial percentage is to be derived from computational experiments, i.e. recording the total parallel elapsed time and the parallel-only elapsed time, then it can contain all overheads, such as communication, synchronization, input/output and memory access. The law offers no help to separate these factors. On the other hand, if we obtain the serial percentage by counting the number of total serial and parallel instructions in a program, then all other overheads are excluded. However, in this case the predicted speedup may never agree with the experiments.

	Conclusion drawn from Gustafson’s law is that it should be possible to get high speedup if we scale up the problem size.		Conclusion drawn from Gustafson’s law is that it should be possible to get high speedup if we scale up the problem size.

Rchakar: /* Scaled speedup http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&sqi=2&ved=0CCkQFjAB&url=http%3A%2F%2Fcoitweb.uncc.edu%2F~abw%2FITCS4145F10%2Fslides1a.ppt&ei=rq05T_zOOpKutwe635jRAg&usg=AFQjCNFMNTKEQ2P9G4zV3fGWyaMbmYtsMQhttp://spartan.

2012-02-14T01:36:17Z

← Older revision		Revision as of 01:36, 14 February 2012
Line 132:		Line 132:
	Using Amdahl's Law as an argument against massively parallel processing is not valid. This is because ''serial parts'' of a program can be very close to zero for many practical applications. Thus very high speedups are possible using massively many processors. Gustafson's experiments are just examples of these applications.		Using Amdahl's Law as an argument against massively parallel processing is not valid. This is because ''serial parts'' of a program can be very close to zero for many practical applications. Thus very high speedups are possible using massively many processors. Gustafson's experiments are just examples of these applications.

	Gustafson's formulation gives an illusion that as if ''number of processors'' can increase indefinitely. A closer look finds that the increase in serial parts of a program is affecting speedup negatively. The rate of speedup decrease as ~~"p"~~ approaches infinity, if we translate the scaled-percentage to a non-scaled percentage. We cannot observe the speedup impact by ''number of processors'' using Gustafson's formulation directly since it contains a ''number of processors'' dependent variable serial parts of a program.		Gustafson's formulation gives an illusion that as if ''number of processors'' can increase indefinitely. A closer look finds that the increase in serial parts of a program is affecting speedup negatively. The rate of speedup decrease as ''number of processors'' approaches infinity, if we translate the scaled-percentage to a non-scaled percentage. We cannot observe the speedup impact by ''number of processors'' using Gustafson's formulation directly since it contains a ''number of processors'' dependent variable serial parts of a program.

	Even though Amdahl's Law is theoretically correct, the serial percentage is not practically obtainable. For example, if the serial percentage is to be derived from computational experiments, i.e. recording the total parallel elapsed time and the parallel-only elapsed time, then it can contain all overheads, such as communication, synchronization, input/output and memory access. The law offers no help to separate these factors. On the other hand, if we obtain the serial percentage by counting the number of total serial and parallel instructions in a program, then all other overheads are excluded. However, in this case the predicted speedup may never agree with the experiments.		Even though Amdahl's Law is theoretically correct, the serial percentage is not practically obtainable. For example, if the serial percentage is to be derived from computational experiments, i.e. recording the total parallel elapsed time and the parallel-only elapsed time, then it can contain all overheads, such as communication, synchronization, input/output and memory access. The law offers no help to separate these factors. On the other hand, if we obtain the serial percentage by counting the number of total serial and parallel instructions in a program, then all other overheads are excluded. However, in this case the predicted speedup may never agree with the experiments.

Rchakar: /* Conclusion */

2012-02-14T01:35:38Z

Conclusion

← Older revision		Revision as of 01:35, 14 February 2012
Line 138:		Line 138:
	Conclusion drawn from Gustafson’s law is that it should be possible to get high speedup if we scale up the problem size.		Conclusion drawn from Gustafson’s law is that it should be possible to get high speedup if we scale up the problem size.

	===~~Super-linear~~ speedup===		===Superlinear speedup===

	== External links ==		== External links ==

Rchakar: /* Scaled speedup http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&sqi=2&ved=0CCkQFjAB&url=http%3A%2F%2Fcoitweb.uncc.edu%2F~abw%2FITCS4145F10%2Fslides1a.ppt&ei=rq05T_zOOpKutwe635jRAg&usg=AFQjCNFMNTKEQ2P9G4zV3fGWyaMbmYtsMQhttp://spartan.

2012-02-14T01:34:59Z

← Older revision		Revision as of 01:34, 14 February 2012
Line 130:		Line 130:
	===Scaled speedup <ref>http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&sqi=2&ved=0CCkQFjAB&url=http%3A%2F%2Fcoitweb.uncc.edu%2F~abw%2FITCS4145F10%2Fslides1a.ppt&ei=rq05T_zOOpKutwe635jRAg&usg=AFQjCNFMNTKEQ2P9G4zV3fGWyaMbmYtsMQ</ref><ref>http://spartan.cis.temple.edu/shi/public_html/docs/amdahl/amdahl.html</ref>===		===Scaled speedup <ref>http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&sqi=2&ved=0CCkQFjAB&url=http%3A%2F%2Fcoitweb.uncc.edu%2F~abw%2FITCS4145F10%2Fslides1a.ppt&ei=rq05T_zOOpKutwe635jRAg&usg=AFQjCNFMNTKEQ2P9G4zV3fGWyaMbmYtsMQ</ref><ref>http://spartan.cis.temple.edu/shi/public_html/docs/amdahl/amdahl.html</ref>===

	Using Amdahl's Law as an argument against massively parallel processing is not valid. This is because serial parts of a program can be very close to zero for many practical applications. Thus very high speedups are possible using massively many processors. Gustafson's experiments are just examples of these applications.		Using Amdahl's Law as an argument against massively parallel processing is not valid. This is because ''serial parts'' of a program can be very close to zero for many practical applications. Thus very high speedups are possible using massively many processors. Gustafson's experiments are just examples of these applications.

	Gustafson's formulation gives an illusion that as if ~~"p"~~ can increase indefinitely. A closer look finds that the increase in serial parts of a program is affecting speedup negatively. The rate of speedup decrease as "p" approaches infinity, if we translate the scaled-percentage to a non-scaled percentage. We cannot observe the speedup impact by ~~"p"~~ using Gustafson's formulation directly since it contains a ~~"p"~~ dependent variable serial parts of a program.		Gustafson's formulation gives an illusion that as if ''number of processors'' can increase indefinitely. A closer look finds that the increase in serial parts of a program is affecting speedup negatively. The rate of speedup decrease as "p" approaches infinity, if we translate the scaled-percentage to a non-scaled percentage. We cannot observe the speedup impact by ''number of processors'' using Gustafson's formulation directly since it contains a ''number of processors'' dependent variable serial parts of a program.

	Even though Amdahl's Law is theoretically correct, the serial percentage is not practically obtainable. For example, if the serial percentage is to be derived from computational experiments, i.e. recording the total parallel elapsed time and the parallel-only elapsed time, then it can contain all overheads, such as communication, synchronization, input/output and memory access. The law offers no help to separate these factors. On the other hand, if we obtain the serial percentage by counting the number of total serial and parallel instructions in a program, then all other overheads are excluded. However, in this case the predicted speedup may never agree with the experiments.		Even though Amdahl's Law is theoretically correct, the serial percentage is not practically obtainable. For example, if the serial percentage is to be derived from computational experiments, i.e. recording the total parallel elapsed time and the parallel-only elapsed time, then it can contain all overheads, such as communication, synchronization, input/output and memory access. The law offers no help to separate these factors. On the other hand, if we obtain the serial percentage by counting the number of total serial and parallel instructions in a program, then all other overheads are excluded. However, in this case the predicted speedup may never agree with the experiments.

Rchakar: /* Scaled speedup http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&sqi=2&ved=0CCkQFjAB&url=http%3A%2F%2Fcoitweb.uncc.edu%2F~abw%2FITCS4145F10%2Fslides1a.ppt&ei=rq05T_zOOpKutwe635jRAg&usg=AFQjCNFMNTKEQ2P9G4zV3fGWyaMbmYtsMQhttp://spartan.

2012-02-14T01:23:42Z

← Older revision		Revision as of 01:23, 14 February 2012
Line 133:		Line 133:

	Gustafson's formulation gives an illusion that as if "p" can increase indefinitely. A closer look finds that the increase in serial parts of a program is affecting speedup negatively. The rate of speedup decrease as "p" approaches infinity, if we translate the scaled-percentage to a non-scaled percentage. We cannot observe the speedup impact by "p" using Gustafson's formulation directly since it contains a "p" dependent variable serial parts of a program.		Gustafson's formulation gives an illusion that as if "p" can increase indefinitely. A closer look finds that the increase in serial parts of a program is affecting speedup negatively. The rate of speedup decrease as "p" approaches infinity, if we translate the scaled-percentage to a non-scaled percentage. We cannot observe the speedup impact by "p" using Gustafson's formulation directly since it contains a "p" dependent variable serial parts of a program.

			Even though Amdahl's Law is theoretically correct, the serial percentage is not practically obtainable. For example, if the serial percentage is to be derived from computational experiments, i.e. recording the total parallel elapsed time and the parallel-only elapsed time, then it can contain all overheads, such as communication, synchronization, input/output and memory access. The law offers no help to separate these factors. On the other hand, if we obtain the serial percentage by counting the number of total serial and parallel instructions in a program, then all other overheads are excluded. However, in this case the predicted speedup may never agree with the experiments.

	Conclusion drawn from Gustafson’s law is that it should be possible to get high speedup if we scale up the problem size.		Conclusion drawn from Gustafson’s law is that it should be possible to get high speedup if we scale up the problem size.