imported>Citation bot: Add: arxiv, bibcode. | Use this bot. Report bugs. | Suggested by Abductive | #UCB_toolbar

2025-12-31T08:41:56Z

Add: arxiv, bibcode. | Use this bot. Report bugs. | Suggested by Abductive | #UCB_toolbar

imported>DrKay: CS1 errors: website ignored

2025-10-25T11:57:58Z

CS1 errors: website ignored

← Previous revision		Revision as of 11:57, 25 October 2025
Line 35:		Line 35:
	Optimally, the [[speedup]] from parallelization would be linear—doubling the number of processing elements should halve the runtime, and doubling it a second time should again halve the runtime. However, very few parallel algorithms achieve optimal speedup. Most of them have a near-linear speedup for small numbers of processing elements, which flattens out into a constant value for large numbers of processing elements.		Optimally, the [[speedup]] from parallelization would be linear—doubling the number of processing elements should halve the runtime, and doubling it a second time should again halve the runtime. However, very few parallel algorithms achieve optimal speedup. Most of them have a near-linear speedup for small numbers of processing elements, which flattens out into a constant value for large numbers of processing elements.

	The maximum potential speedup of an overall system can be calculated by [[Amdahl's law]].<ref name=":02">{{Citation \|last=Bakos \|first=Jason D. \|title=Chapter 2 - Multicore and data-level optimization: OpenMP and SIMD \|date=2016-01-01 \|work=Embedded Systems \|pages=49–103 \|editor-last=Bakos \|editor-first=Jason D. \|url=https://linkinghub.elsevier.com/retrieve/pii/B978012800342800002X \|access-date=2024-11-18 \|place=Boston \|publisher=Morgan Kaufmann \|doi=10.1016/b978-0-12-800342-8.00002-x \|isbn=978-0-12-800342-8\|url-access=subscription }}</ref> Amdahl's Law indicates that optimal performance improvement is achieved by balancing enhancements to both parallelizable and non-parallelizable components of a task. Furthermore, it reveals that increasing the number of processors yields diminishing returns, with negligible speedup gains beyond a certain point. <ref>{{Cite book \|title=The Art of Multiprocessor Programming, Revised Reprint \|date=22 May 2012 \|publisher=Morgan Kaufmann \|isbn=9780123973375}}</ref><ref>{{Cite book \|title=Programming Many-Core Chips \|isbn=9781441997395 \|last1=Vajda \|first1=András \|date=10 June 2011 \|publisher=Springer}}</ref>		The maximum potential speedup of an overall system can be calculated by [[Amdahl's law]].<ref name=":02">{{Citation \|last=Bakos \|first=Jason D. \|title=Chapter 2 - Multicore and data-level optimization: OpenMP and SIMD \|date=2016-01-01 \|work=Embedded Systems \|pages=49–103 \|editor-last=Bakos \|editor-first=Jason D. \|url=https://linkinghub.elsevier.com/retrieve/pii/B978012800342800002X \|access-date=2024-11-18 \|place=Boston \|publisher=Morgan Kaufmann \|doi=10.1016/b978-0-12-800342-8.00002-x \|isbn=978-0-12-800342-8\|url-access=subscription }}</ref> Amdahl's Law indicates that optimal performance improvement is achieved by balancing enhancements to both parallelizable and non-parallelizable components of a task. Furthermore, it reveals that increasing the number of processors yields diminishing returns, with negligible speedup gains beyond a certain point.<ref>{{Cite book \|title=The Art of Multiprocessor Programming, Revised Reprint \|date=22 May 2012 \|publisher=Morgan Kaufmann \|isbn=9780123973375}}</ref><ref>{{Cite book \|title=Programming Many-Core Chips \|isbn=9781441997395 \|last1=Vajda \|first1=András \|date=10 June 2011 \|publisher=Springer}}</ref>

	Amdahl's Law has limitations, including assumptions of fixed workload, neglecting [[inter-process communication]] and [[Synchronization (computer science)\|synchronization]] overheads, primarily focusing on computational aspect and ignoring extrinsic factors such as data persistence, I/O operations, and memory access overheads.<ref>{{Cite book \|last=Amdahl \|first=Gene M. \|chapter=Validity of the single processor approach to achieving large scale computing capabilities \|date=1967-04-18 \|title=Proceedings of the April 18-20, 1967, spring joint computer conference on - AFIPS '67 (Spring) \|chapter-url=https://dl.acm.org/doi/10.1145/1465482.1465560 \|location=New York, NY, USA \|publisher=Association for Computing Machinery \|pages=483–485 \|doi=10.1145/1465482.1465560 \|isbn=978-1-4503-7895-6}}</ref><ref name=":1">{{Cite book \|title=Computer Architecture: A Quantitative Approach \|date=2003 \|publisher=Morgan Kaufmann \|isbn=978-8178672663}}</ref><ref>{{Cite book \|title=Parallel Computer Architecture A Hardware/Software Approach \|date=1999 \|publisher=Elsevier Science \|isbn=9781558603431}}</ref>		Amdahl's Law has limitations, including assumptions of fixed workload, neglecting [[inter-process communication]] and [[Synchronization (computer science)\|synchronization]] overheads, primarily focusing on computational aspect and ignoring extrinsic factors such as data persistence, I/O operations, and memory access overheads.<ref>{{Cite book \|last=Amdahl \|first=Gene M. \|chapter=Validity of the single processor approach to achieving large scale computing capabilities \|date=1967-04-18 \|title=Proceedings of the April 18-20, 1967, spring joint computer conference on - AFIPS '67 (Spring) \|chapter-url=https://dl.acm.org/doi/10.1145/1465482.1465560 \|location=New York, NY, USA \|publisher=Association for Computing Machinery \|pages=483–485 \|doi=10.1145/1465482.1465560 \|isbn=978-1-4503-7895-6}}</ref><ref name=":1">{{Cite book \|title=Computer Architecture: A Quantitative Approach \|date=2003 \|publisher=Morgan Kaufmann \|isbn=978-8178672663}}</ref><ref>{{Cite book \|title=Parallel Computer Architecture A Hardware/Software Approach \|date=1999 \|publisher=Elsevier Science \|isbn=9781558603431}}</ref>
Line 137:		Line 137:
	\| first = Andrew S.		\| first = Andrew S.
	\| date = 2002-02-01		\| date = 2002-02-01
	~~\| website = Informit~~
	\| publisher = Pearson Education, Informit		\| publisher = Pearson Education, Informit
	\| access-date = 2018-05-10		\| access-date = 2018-05-10
Line 208:		Line 207:

	== Disadvantages ==		== Disadvantages ==
	Parallel computing can incur significant overhead in practice, primarily due to the costs associated with merging data from multiple processes. Specifically, inter-process communication and synchronization can lead to overheads that are substantially higher—often by two or more orders of magnitude—compared to processing the same data on a single thread. <ref>{{Cite book \|title=Operating System Concepts \|isbn=978-0470128725 \|last1=Silberschatz \|first1=Abraham \|last2=Galvin \|first2=Peter B. \|last3=Gagne \|first3=Greg \|date=29 July 2008 \|publisher=Wiley }}</ref><ref>{{Cite book \|title=Computer Organization and Design MIPS Edition: The Hardware/Software Interface (The Morgan Kaufmann Series in Computer Architecture and Design) \|date=2013 \|publisher=Morgan Kaufmann \|isbn=978-0124077263}}</ref><ref>{{Cite book \|title=Parallel Programming: Techniques and Applications Using Networked Workstations and Parallel Computers \|date=2005 \|publisher=Pearson \|isbn=978-0131405639}}</ref> Therefore, the overall improvement should be carefully evaluated.		Parallel computing can incur significant overhead in practice, primarily due to the costs associated with merging data from multiple processes. Specifically, inter-process communication and synchronization can lead to overheads that are substantially higher—often by two or more orders of magnitude—compared to processing the same data on a single thread.<ref>{{Cite book \|title=Operating System Concepts \|isbn=978-0470128725 \|last1=Silberschatz \|first1=Abraham \|last2=Galvin \|first2=Peter B. \|last3=Gagne \|first3=Greg \|date=29 July 2008 \|publisher=Wiley }}</ref><ref>{{Cite book \|title=Computer Organization and Design MIPS Edition: The Hardware/Software Interface (The Morgan Kaufmann Series in Computer Architecture and Design) \|date=2013 \|publisher=Morgan Kaufmann \|isbn=978-0124077263}}</ref><ref>{{Cite book \|title=Parallel Programming: Techniques and Applications Using Networked Workstations and Parallel Computers \|date=2005 \|publisher=Pearson \|isbn=978-0131405639}}</ref> Therefore, the overall improvement should be carefully evaluated.

	==Granularity==		==Granularity==
Line 270:		Line 269:
	====Distributed computing====		====Distributed computing====
	{{main\|Distributed computing}}		{{main\|Distributed computing}}
	A distributed computer (also known as a distributed memory multiprocessor) is a distributed memory computer system in which the processing elements are connected by a network. Distributed computers are highly scalable. The terms "[[concurrent computing]]", "parallel computing", and "distributed computing" have a lot of overlap, and no clear distinction exists between them.<ref>[[Distributed ~~computing#CITEREFGhosh2007~~\|~~Ghosh (~~2007~~)]], p~~. 10. [[Distributed computing~~#CITEREFKeidar2008~~\|~~Keidar (2008)~~]].</ref> The same system may be characterized both as "parallel" and "distributed"; the processors in a typical distributed system run concurrently in parallel.<ref>[[~~Distributed computing#CITEREFLynch1996~~\|~~Lynch (~~1996~~)]], p~~. ~~xix,~~ 1–2~~. [[Distributed computing#CITEREFPeleg2000~~\|Peleg (~~2000~~)]]~~, p~~. 1.</ref>		A distributed computer (also known as a distributed memory multiprocessor) is a distributed memory computer system in which the processing elements are connected by a network. Distributed computers are highly scalable. The terms "[[concurrent computing]]", "parallel computing", and "distributed computing" have a lot of overlap, and no clear distinction exists between them.<ref>{{cite book \|last=Ghosh \|first=Sukumar \|title=Distributed Systems – An Algorithmic Approach \|publisher=Chapman & Hall/CRC \|year=2007 \|isbn=978-1-58488-564-1 \|page=10}}</ref><ref>{{cite journal \|doi=10.1145/1466390.1466402 \|last1=Keidar \|first1=Idit \|author1-link=Idit Keidar \|title=Distributed computing column 32 – The year in review \|journal=[[ACM SIGACT News]] \|volume=39 \|issue=4 \|year=2008 \|pages=53–54 \|url=http://webee.technion.ac.il/~idish/sigactNews/#column%2032 \|citeseerx=10.1.1.116.1285 \|s2cid=7607391 \|access-date=2009-08-20 \|archive-date=2014-01-16 \|archive-url=https://web.archive.org/web/20140116123634/http://webee.technion.ac.il/~idish/sigactNews/#column%2032 \|url-status=dead}}</ref> The same system may be characterized both as "parallel" and "distributed"; the processors in a typical distributed system run concurrently in parallel.<ref>{{citation \|last=Lynch \|first=Nancy A. \|author-link=Nancy Lynch \|title=Distributed Algorithms \|publisher=[[Morgan Kaufmann]] \|year=1996 \|isbn=978-1-55860-348-6 \|url-access=registration \|url=https://archive.org/details/distributedalgor0000lync \|page=1–2}}</ref><ref>{{cite book \|last=Peleg \|first=David \|author-link=David Peleg (scientist) \|title=Distributed Computing: A Locality-Sensitive Approach \|publisher=[[SIAM]] \|year=2000 \|isbn=978-0-89871-464-7 \|url=http://www.ec-securehost.com/SIAM/DT05.html \|access-date=2009-07-16 \|archive-url=https://web.archive.org/web/20090806070332/http://www.ec-securehost.com/SIAM/DT05.html \|archive-date=2009-08-06 \|url-status=dead \|page=1}}</ref>

	=====Cluster computing=====		=====Cluster computing=====
Line 306:		Line 305:
	[[Reconfigurable computing]] is the use of a [[field-programmable gate array]] (FPGA) as a co-processor to a general-purpose computer. An FPGA is, in essence, a computer chip that can rewire itself for a given task.		[[Reconfigurable computing]] is the use of a [[field-programmable gate array]] (FPGA) as a co-processor to a general-purpose computer. An FPGA is, in essence, a computer chip that can rewire itself for a given task.

	FPGAs can be programmed with [[hardware description language]]s such as [[VHDL]]<ref>{{Cite journal\|last1=Valueva\|first1=Maria\|last2=Valuev\|first2=Georgii\|last3=Semyonova\|first3=Nataliya\|last4=Lyakhov\|first4=Pavel\|last5=Chervyakov\|first5=Nikolay\|last6=Kaplun\|first6=Dmitry\|last7=Bogaevskiy\|first7=Danil\|date=2019-06-20\|title=Construction of Residue Number System Using Hardware Efficient Diagonal Function\|journal=Electronics\|language=en\|volume=8\|issue=6\|pages=694\|doi=10.3390/electronics8060694\|issn=2079-9292\|quote=All simulated circuits were described in very high speed integrated circuit (VHSIC) hardware description language (VHDL). Hardware modeling was performed on Xilinx FPGA Artix 7 xc7a200tfbg484-2.\|doi-access=free}}</ref> or [[Verilog]].<ref>{{Cite book\|last1=Gupta\|first1=Ankit\|last2=Suneja\|first2=Kriti\|title=2020 4th International Conference on Intelligent Computing and Control Systems (ICICCS) \|chapter=Hardware Design of Approximate Matrix Multiplier based on FPGA in Verilog \|date=May 2020~~\|chapter-url=https://ieeexplore.ieee.org/document/9121004~~\|location=Madurai, India\|publisher=IEEE\|pages=496–498\|doi=10.1109/ICICCS48265.2020.9121004\|isbn=978-1-7281-4876-2\|s2cid=219990653}}</ref> Several vendors have created [[C to HDL]] languages that attempt to emulate the syntax and semantics of the [[C programming language]], with which most programmers are familiar. The best known C to HDL languages are [[Mitrionics\|Mitrion-C]], [[Impulse C]], and [[Handel-C]]. Specific subsets of [[SystemC]] based on C++ can also be used for this purpose.		FPGAs can be programmed with [[hardware description language]]s such as [[VHDL]]<ref>{{Cite journal\|last1=Valueva\|first1=Maria\|last2=Valuev\|first2=Georgii\|last3=Semyonova\|first3=Nataliya\|last4=Lyakhov\|first4=Pavel\|last5=Chervyakov\|first5=Nikolay\|last6=Kaplun\|first6=Dmitry\|last7=Bogaevskiy\|first7=Danil\|date=2019-06-20\|title=Construction of Residue Number System Using Hardware Efficient Diagonal Function\|journal=Electronics\|language=en\|volume=8\|issue=6\|pages=694\|doi=10.3390/electronics8060694\|issn=2079-9292\|quote=All simulated circuits were described in very high speed integrated circuit (VHSIC) hardware description language (VHDL). Hardware modeling was performed on Xilinx FPGA Artix 7 xc7a200tfbg484-2.\|doi-access=free}}</ref> or [[Verilog]].<ref>{{Cite book\|last1=Gupta\|first1=Ankit\|last2=Suneja\|first2=Kriti\|title=2020 4th International Conference on Intelligent Computing and Control Systems (ICICCS) \|chapter=Hardware Design of Approximate Matrix Multiplier based on FPGA in Verilog \|date=May 2020\|location=Madurai, India\|publisher=IEEE\|pages=496–498\|doi=10.1109/ICICCS48265.2020.9121004\|isbn=978-1-7281-4876-2\|s2cid=219990653}}</ref> Several vendors have created [[C to HDL]] languages that attempt to emulate the syntax and semantics of the [[C programming language]], with which most programmers are familiar. The best known C to HDL languages are [[Mitrionics\|Mitrion-C]], [[Impulse C]], and [[Handel-C]]. Specific subsets of [[SystemC]] based on C++ can also be used for this purpose.

	AMD's decision to open its [[HyperTransport]] technology to third-party vendors has become the enabling technology for high-performance reconfigurable computing.<ref name="DAmour">D'Amour, Michael R., Chief Operating Officer, DRC Computer Corporation. "Standard Reconfigurable Computing". Invited speaker at the University of Delaware, February 28, 2007.</ref> According to Michael R. D'Amour, Chief Operating Officer of DRC Computer Corporation, "when we first walked into AMD, they called us 'the [[CPU socket\|socket]] stealers.' Now they call us their partners."<ref name="DAmour"/>		AMD's decision to open its [[HyperTransport]] technology to third-party vendors has become the enabling technology for high-performance reconfigurable computing.<ref name="DAmour">D'Amour, Michael R., Chief Operating Officer, DRC Computer Corporation. "Standard Reconfigurable Computing". Invited speaker at the University of Delaware, February 28, 2007.</ref> According to Michael R. D'Amour, Chief Operating Officer of DRC Computer Corporation, "when we first walked into AMD, they called us 'the [[CPU socket\|socket]] stealers.' Now they call us their partners."<ref name="DAmour"/>

imported>Headbomb: Altered template type. Add: chapter, title. | Use this tool. Report bugs. | #UCB_Gadget

2025-06-04T19:27:03Z

Altered template type. Add: chapter, title. | Use this tool. Report bugs. | #UCB_Gadget

← Previous revision		Revision as of 19:27, 4 June 2025
Line 429:		Line 429:

	==Further reading==		==Further reading==
	* {{cite ~~journal~~\|last1=Rodriguez\|first1=C.\|last2=Villagra\|first2=M.\|last3=Baran\|first3=B.\|title=~~Asynchronous team algorithms for Boolean Satisfiability\|journal=~~Bio-Inspired Models of Network, Information and Computing Systems~~, 2007. Bionetics 2007. 2nd~~\|date=29 August 2008\|pages=66–69\|doi=10.1109/BIMNICS.2007.4610083\|s2cid=15185219}}		* {{cite book\|last1=Rodriguez\|first1=C.\|last2=Villagra\|first2=M.\|last3=Baran\|first3=B. \|title=2007 2nd Bio-Inspired Models of Network, Information and Computing Systems \|chapter=Asynchronous team algorithms for Boolean Satisfiability \|date=29 August 2008\|pages=66–69\|doi=10.1109/BIMNICS.2007.4610083\|s2cid=15185219}}
	* Sechin, A.; Parallel Computing in Photogrammetry. GIM International. #1, 2016, pp. 21–23.		* Sechin, A.; Parallel Computing in Photogrammetry. GIM International. #1, 2016, pp. 21–23.

imported>OAbot: Open access bot: url-access updated in citation with #oabot.

2025-05-26T15:29:44Z

Open access bot: url-access updated in citation with #oabot.

Show changes

Parallel computing - Revision history

imported>Citation bot: Add: arxiv, bibcode. | Use this bot. Report bugs. | Suggested by Abductive | #UCB_toolbar

imported>DrKay: CS1 errors: website ignored

imported>Headbomb: Altered template type. Add: chapter, title. | Use this tool. Report bugs. | #UCB_Gadget

imported>OAbot: Open access bot: url-access updated in citation with #oabot.