Cannon's algorithm - Revision history

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

2025-05-24T18:18:37Z

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

← Previous revision		Revision as of 18:18, 24 May 2025
Line 6:		Line 6:
	The main advantage of the algorithm is that its storage requirements remain constant and are independent of the number of processors.<ref name="stanfordpaper"/>		The main advantage of the algorithm is that its storage requirements remain constant and are independent of the number of processors.<ref name="stanfordpaper"/>

	The Scalable Universal Matrix Multiplication Algorithm (SUMMA)<ref>{{cite journal \|first1=Robert A. \|last1=van de Geijn \|first2=Jerrell \|last2=Watts \|title=SUMMA: scalable universal matrix multiplication algorithm \|journal=Concurrency: Practice and Experience \|volume=9 \|issue=4 \|pages=255–274 \|date=April 1997 \|doi= 10.1002/(SICI)1096-9128(199704)9:4<255::AID-CPE250>3.0.CO;2-2\|url=http://onlinelibrary.wiley.com/doi/10.1002/(SICI)1096-9128(199704)9:4%3C255::AID-CPE250%3E3.0.CO;2-2/abstract}}</ref>		The Scalable Universal Matrix Multiplication Algorithm (SUMMA)<ref>{{cite journal \|first1=Robert A. \|last1=van de Geijn \|first2=Jerrell \|last2=Watts \|title=SUMMA: scalable universal matrix multiplication algorithm \|journal=Concurrency: Practice and Experience \|volume=9 \|issue=4 \|pages=255–274 \|date=April 1997 \|doi= 10.1002/(SICI)1096-9128(199704)9:4<255::AID-CPE250>3.0.CO;2-2\|url=http://onlinelibrary.wiley.com/doi/10.1002/(SICI)1096-9128(199704)9:4%3C255::AID-CPE250%3E3.0.CO;2-2/abstract\|url-access=subscription }}</ref>
	is a more practical algorithm that requires less workspace and overcomes the need for a square 2D grid. It is used by the [[ScaLAPACK]], [[PLAPACK]], and [http://code.google.com/p/elemental/ Elemental] libraries.		is a more practical algorithm that requires less workspace and overcomes the need for a square 2D grid. It is used by the [[ScaLAPACK]], [[PLAPACK]], and [http://code.google.com/p/elemental/ Elemental] libraries.

Citation bot: Altered chapter-url. URLs might have been anonymized. Add: archive-date, archive-url. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Distributed algorithms | #UCB_Category 24/41

2025-01-18T05:02:58Z

Altered chapter-url. URLs might have been anonymized. Add: archive-date, archive-url. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Distributed algorithms | #UCB_Category 24/41

← Previous revision		Revision as of 05:02, 18 January 2025
Line 1:		Line 1:
	{{Short description\|Algorithm for matrix multiplication}}		{{Short description\|Algorithm for matrix multiplication}}
	In [[computer science]], '''Cannon's algorithm''' is a [[distributed algorithm\|distributed]] [[algorithm for matrix multiplication]] for two-dimensional [[Mesh networking\|meshes]] first described in 1969 by [[Lynn Elliot Cannon]].<ref>{{cite thesis \|first=Lynn Elliot \|last=Cannon \|title=A cellular computer to implement the Kalman Filter Algorithm \|date=14 July 1969 \|type=PhD \|publisher=Montana State University \|url=https://scholarworks.montana.edu/bitstreams/643669d9-055d-4345-a467-41ad612599c8/download}}</ref><ref name="stanfordpaper">{{cite ~~techreport~~ \|last=Gupta \|first=H. \|last2=Sadayappan \|first2=P. \|title=Communication Efficient Matrix-Multiplication on Hypercubes \|date=1994 \|publisher=Stanford Infolab \|url=http://ilpubs.stanford.edu:8090/59/}}</ref>		In [[computer science]], '''Cannon's algorithm''' is a [[distributed algorithm\|distributed]] [[algorithm for matrix multiplication]] for two-dimensional [[Mesh networking\|meshes]] first described in 1969 by [[Lynn Elliot Cannon]].<ref>{{cite thesis \|first=Lynn Elliot \|last=Cannon \|title=A cellular computer to implement the Kalman Filter Algorithm \|date=14 July 1969 \|type=PhD \|publisher=Montana State University \|url=https://scholarworks.montana.edu/bitstreams/643669d9-055d-4345-a467-41ad612599c8/download}}</ref><ref name="stanfordpaper">{{cite tech report \|last=Gupta \|first=H. \|last2=Sadayappan \|first2=P. \|title=Communication Efficient Matrix-Multiplication on Hypercubes \|date=1994 \|publisher=Stanford Infolab \|url=http://ilpubs.stanford.edu:8090/59/}}</ref>

	It is especially suitable for computers laid out in an ''N'' × ''N'' mesh.<ref name="ornl.gov">{{cite book \|chapter=4.2 Matrix Multiplication on a Distributed Memory Machine \|title=Numerical Linear Algebra \|publisher=Computational Science Education Project \|date=1991–1995 \|chapter-url=https://web.archive.org/web/20180401075129/https://www.phy.ornl.gov/csep/la/node6.html}}</ref> While Cannon's algorithm works well in homogeneous 2D grids, extending it to heterogeneous 2D grids has been shown to be difficult.<ref name="lyonfr">{{cite thesis \|first=Jean-François \|last=Pineau \|title=Communication-aware scheduling on heterogeneous master-worker platforms \|date=October 2010 \|type=PhD \|publisher=Ecole normale supérieure de lyon \|url=https://tel.archives-ouvertes.fr/tel-00530131/document \|id=tel-00530131}}</ref>		It is especially suitable for computers laid out in an ''N'' × ''N'' mesh.<ref name="ornl.gov">{{cite book \|chapter=4.2 Matrix Multiplication on a Distributed Memory Machine \|title=Numerical Linear Algebra \|publisher=Computational Science Education Project \|date=1991–1995 \|chapter-url=https://www.phy.ornl.gov/csep/la/node6.html\|archive-url=https://web.archive.org/web/20180401075129/https://www.phy.ornl.gov/csep/la/node6.html \|archive-date=1 April 2018 }}</ref> While Cannon's algorithm works well in homogeneous 2D grids, extending it to heterogeneous 2D grids has been shown to be difficult.<ref name="lyonfr">{{cite thesis \|first=Jean-François \|last=Pineau \|title=Communication-aware scheduling on heterogeneous master-worker platforms \|date=October 2010 \|type=PhD \|publisher=Ecole normale supérieure de lyon \|url=https://tel.archives-ouvertes.fr/tel-00530131/document \|id=tel-00530131}}</ref>

	The main advantage of the algorithm is that its storage requirements remain constant and are independent of the number of processors.<ref name="stanfordpaper"/>		The main advantage of the algorithm is that its storage requirements remain constant and are independent of the number of processors.<ref name="stanfordpaper"/>

RDBrown: →cite thesis, web etc | Alter: doi, url. URLs might have been anonymized. Add: archive-date, archive-url, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this tool. Report bugs. | #UCB_Gadget | Alter: chapter-url, doi, url. URLs might have been anonymized. Add: archive-date, archive-url, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this tool. [[:en:WP:DBU...

2025-01-12T04:12:37Z

→cite thesis, web etc | Alter: doi, url. URLs might have been anonymized. Add: archive-date, archive-url, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this tool. Report bugs. | #UCB_Gadget | Alter: chapter-url, doi, url. URLs might have been anonymized. Add: archive-date, archive-url, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this tool. [[:en:WP:DBU...

← Previous revision		Revision as of 04:12, 12 January 2025
Line 1:		Line 1:
	{{Short description\|Algorithm for matrix multiplication}}		{{Short description\|Algorithm for matrix multiplication}}
	In [[computer science]], '''Cannon's algorithm''' is a [[distributed algorithm\|distributed]] [[algorithm for matrix multiplication]] for two-dimensional [[Mesh networking\|meshes]] first described in 1969 by [[Lynn Elliot Cannon]].<ref>Lynn Elliot Cannon, ~~''[http://portal.acm.org/citation.cfm?coll~~=~~GUIDE&dl=GUIDE&id=905686~~ A cellular computer to implement the Kalman Filter Algorithm~~]'',~~ ~~Technical~~ ~~report,~~ ~~Ph.D.~~ ~~Thesis,~~ Montana State University, ~~14 July 1969~~.</ref><ref name="stanfordpaper">~~[http://dbpubs.stanford.edu:8090/pub/1994-25~~ Gupta, H.; Sadayappan, P.: Communication Efficient Matrix-Multiplication on Hypercubes], ~~dbpubs~~.stanford.edu</ref>		In [[computer science]], '''Cannon's algorithm''' is a [[distributed algorithm\|distributed]] [[algorithm for matrix multiplication]] for two-dimensional [[Mesh networking\|meshes]] first described in 1969 by [[Lynn Elliot Cannon]].<ref>{{cite thesis \|first=Lynn Elliot \|last=Cannon \|title=A cellular computer to implement the Kalman Filter Algorithm \|date=14 July 1969 \|type=PhD \|publisher=Montana State University \|url=https://scholarworks.montana.edu/bitstreams/643669d9-055d-4345-a467-41ad612599c8/download}}</ref><ref name="stanfordpaper">{{cite techreport \|last=Gupta \|first=H. \|last2=Sadayappan \|first2=P. \|title=Communication Efficient Matrix-Multiplication on Hypercubes \|date=1994 \|publisher=Stanford Infolab \|url=http://ilpubs.stanford.edu:8090/59/}}</ref>

	It is especially suitable for computers laid out in an ''N'' × ''N'' mesh.<ref name="ornl.gov">~~[http://www.phy.ornl.gov/csep/la/node6.html~~ 4.2 Matrix Multiplication on a Distributed Memory Machine], www.phy.ornl.gov</ref> While Cannon's algorithm works well in homogeneous 2D grids, extending it to heterogeneous 2D grids has been shown to be difficult.<ref name="lyonfr">Jean-François Pineau~~, [https://tel.archives-ouvertes.fr/tel-00530131/document~~ Communication-aware scheduling on heterogeneous master-worker platforms], PhD ~~thesis,~~ ~~October~~ ~~2010~~.</ref>		It is especially suitable for computers laid out in an ''N'' × ''N'' mesh.<ref name="ornl.gov">{{cite book \|chapter=4.2 Matrix Multiplication on a Distributed Memory Machine \|title=Numerical Linear Algebra \|publisher=Computational Science Education Project \|date=1991–1995 \|chapter-url=https://web.archive.org/web/20180401075129/https://www.phy.ornl.gov/csep/la/node6.html}}</ref> While Cannon's algorithm works well in homogeneous 2D grids, extending it to heterogeneous 2D grids has been shown to be difficult.<ref name="lyonfr">{{cite thesis \|first=Jean-François \|last=Pineau \|title=Communication-aware scheduling on heterogeneous master-worker platforms \|date=October 2010 \|type=PhD \|publisher=Ecole normale supérieure de lyon \|url=https://tel.archives-ouvertes.fr/tel-00530131/document \|id=tel-00530131}}</ref>

	The main advantage of the algorithm is that its storage requirements remain constant and are independent of the number of processors.<ref name="stanfordpaper"/>		The main advantage of the algorithm is that its storage requirements remain constant and are independent of the number of processors.<ref name="stanfordpaper"/>

	The Scalable Universal Matrix Multiplication Algorithm (SUMMA)<ref>Robert A. van de Geijn ~~and~~ Jerrell Watts, [http://onlinelibrary.wiley.com/doi/10.1002/(SICI)1096-9128(199704)9:4%3C255::AID-CPE250%3E3.0.CO;2-2/abstract ~~SUMMA: scalable universal matrix multiplication algorithm], Concurrency: Practice and Experience. Volume 9, Issue 4, pages 255–274, April 1997.~~</ref>		The Scalable Universal Matrix Multiplication Algorithm (SUMMA)<ref>{{cite journal \|first1=Robert A. \|last1=van de Geijn \|first2=Jerrell \|last2=Watts \|title=SUMMA: scalable universal matrix multiplication algorithm \|journal=Concurrency: Practice and Experience \|volume=9 \|issue=4 \|pages=255–274 \|date=April 1997 \|doi= 10.1002/(SICI)1096-9128(199704)9:4<255::AID-CPE250>3.0.CO;2-2\|url=http://onlinelibrary.wiley.com/doi/10.1002/(SICI)1096-9128(199704)9:4%3C255::AID-CPE250%3E3.0.CO;2-2/abstract}}</ref>
	is a more practical algorithm that requires less workspace and overcomes the need for a square 2D grid. It is used by the [[ScaLAPACK]], [[PLAPACK]], and [http://code.google.com/p/elemental/ Elemental] libraries.		is a more practical algorithm that requires less workspace and overcomes the need for a square 2D grid. It is used by the [[ScaLAPACK]], [[PLAPACK]], and [http://code.google.com/p/elemental/ Elemental] libraries.

Line 51:		Line 51:

	== References ==		== References ==
			{{reflist}}
	<references/>

	== External links ==		== External links ==
			{{refbegin}}
	* [http://www.cs.berkeley.edu/~demmel/cs267/lecture11/lecture11.html Lecture at Berkeley]
			*{{cite web \|first=J. \|last=Demmel \|title=Lecture 9: Parallel Matrix Multiplication \|date=1996 \|work=CS267 Applications of Parallel Computers \|publisher=U.C. Berkeley \|url=http://www.cs.berkeley.edu/~demmel/cs267/lecture11/lecture11.html}}
	* [https://web.archive.org/web/20070703035731/http://www.cs.mu.oz.au/498/notes/node30.html mu.oz.au]
			*{{cite web \|first=Aaron \|last=Harwood \|title=Matrix multiplication §Cannon's algorithm \|date=2003 \|work=433-498 Networks and Parallel Processing Complexity \|publisher=Melbourne University \|url=http://www.cs.mu.oz.au/498/notes/node30.html \|archive-url=https://web.archive.org/web/20070703035731/http://www.cs.mu.oz.au/498/notes/node30.html \|archive-date=3 July 2007 }}
			{{refend}}

	{{Numerical linear algebra}}		{{Numerical linear algebra}}

LachlanA: /* Algorithm overview */ p_ij does not initially have a_ij and b_ij

2023-11-07T10:40:11Z

Algorithm overview: p_ij does not initially have a_ij and b_ij

← Previous revision		Revision as of 10:40, 7 November 2023
Line 11:		Line 11:
	==Algorithm overview==		==Algorithm overview==

	When multiplying two ''n''×''n'' matrices A and B, we need ''n''×''n'' processing nodes p arranged in a 2D grid~~. Initially p<sub>i,j</sub> is responsible for a<sub>i,j</sub> and b<sub>i,j</sub>~~.		When multiplying two ''n''×''n'' matrices A and B, we need ''n''×''n'' processing nodes p arranged in a 2D grid.
	// PE(i , j)		// PE(i , j)
	k := (i + j) mod N;		k := (i + j) mod N;

LachlanA: No longer a stub

2023-11-07T10:37:44Z

No longer a stub

← Previous revision		Revision as of 10:37, 7 November 2023
Line 63:		Line 63:
	[[Category:Matrix multiplication algorithms]]		[[Category:Matrix multiplication algorithms]]
	[[Category:Mesh networking]]		[[Category:Mesh networking]]


	{{mathapplied-stub}}

14.139.181.225: Undid revision 1180068193 by 14.139.181.225 (talk)

2023-10-14T08:55:53Z

Undid revision 1180068193 by 14.139.181.225 (talk)

← Previous revision		Revision as of 08:55, 14 October 2023
Line 4:		Line 4:
	It is especially suitable for computers laid out in an ''N'' × ''N'' mesh.<ref name="ornl.gov">[http://www.phy.ornl.gov/csep/la/node6.html 4.2 Matrix Multiplication on a Distributed Memory Machine], www.phy.ornl.gov</ref> While Cannon's algorithm works well in homogeneous 2D grids, extending it to heterogeneous 2D grids has been shown to be difficult.<ref name="lyonfr">Jean-François Pineau, [https://tel.archives-ouvertes.fr/tel-00530131/document Communication-aware scheduling on heterogeneous master-worker platforms], PhD thesis, October 2010.</ref>		It is especially suitable for computers laid out in an ''N'' × ''N'' mesh.<ref name="ornl.gov">[http://www.phy.ornl.gov/csep/la/node6.html 4.2 Matrix Multiplication on a Distributed Memory Machine], www.phy.ornl.gov</ref> While Cannon's algorithm works well in homogeneous 2D grids, extending it to heterogeneous 2D grids has been shown to be difficult.<ref name="lyonfr">Jean-François Pineau, [https://tel.archives-ouvertes.fr/tel-00530131/document Communication-aware scheduling on heterogeneous master-worker platforms], PhD thesis, October 2010.</ref>

			The main advantage of the algorithm is that its storage requirements remain constant and are independent of the number of processors.<ref name="stanfordpaper"/>
	Poda dei

	The Scalable Universal Matrix Multiplication Algorithm (SUMMA)<ref>Robert A. van de Geijn and Jerrell Watts, [http://onlinelibrary.wiley.com/doi/10.1002/(SICI)1096-9128(199704)9:4%3C255::AID-CPE250%3E3.0.CO;2-2/abstract SUMMA: scalable universal matrix multiplication algorithm], Concurrency: Practice and Experience. Volume 9, Issue 4, pages 255–274, April 1997.</ref>		The Scalable Universal Matrix Multiplication Algorithm (SUMMA)<ref>Robert A. van de Geijn and Jerrell Watts, [http://onlinelibrary.wiley.com/doi/10.1002/(SICI)1096-9128(199704)9:4%3C255::AID-CPE250%3E3.0.CO;2-2/abstract SUMMA: scalable universal matrix multiplication algorithm], Concurrency: Practice and Experience. Volume 9, Issue 4, pages 255–274, April 1997.</ref>

14.139.181.225 at 08:54, 14 October 2023

2023-10-14T08:54:36Z

← Previous revision		Revision as of 08:54, 14 October 2023
Line 4:		Line 4:
	It is especially suitable for computers laid out in an ''N'' × ''N'' mesh.<ref name="ornl.gov">[http://www.phy.ornl.gov/csep/la/node6.html 4.2 Matrix Multiplication on a Distributed Memory Machine], www.phy.ornl.gov</ref> While Cannon's algorithm works well in homogeneous 2D grids, extending it to heterogeneous 2D grids has been shown to be difficult.<ref name="lyonfr">Jean-François Pineau, [https://tel.archives-ouvertes.fr/tel-00530131/document Communication-aware scheduling on heterogeneous master-worker platforms], PhD thesis, October 2010.</ref>		It is especially suitable for computers laid out in an ''N'' × ''N'' mesh.<ref name="ornl.gov">[http://www.phy.ornl.gov/csep/la/node6.html 4.2 Matrix Multiplication on a Distributed Memory Machine], www.phy.ornl.gov</ref> While Cannon's algorithm works well in homogeneous 2D grids, extending it to heterogeneous 2D grids has been shown to be difficult.<ref name="lyonfr">Jean-François Pineau, [https://tel.archives-ouvertes.fr/tel-00530131/document Communication-aware scheduling on heterogeneous master-worker platforms], PhD thesis, October 2010.</ref>

			Poda dei
	The main advantage of the algorithm is that its storage requirements remain constant and are independent of the number of processors.<ref name="stanfordpaper"/>

	The Scalable Universal Matrix Multiplication Algorithm (SUMMA)<ref>Robert A. van de Geijn and Jerrell Watts, [http://onlinelibrary.wiley.com/doi/10.1002/(SICI)1096-9128(199704)9:4%3C255::AID-CPE250%3E3.0.CO;2-2/abstract SUMMA: scalable universal matrix multiplication algorithm], Concurrency: Practice and Experience. Volume 9, Issue 4, pages 255–274, April 1997.</ref>		The Scalable Universal Matrix Multiplication Algorithm (SUMMA)<ref>Robert A. van de Geijn and Jerrell Watts, [http://onlinelibrary.wiley.com/doi/10.1002/(SICI)1096-9128(199704)9:4%3C255::AID-CPE250%3E3.0.CO;2-2/abstract SUMMA: scalable universal matrix multiplication algorithm], Concurrency: Practice and Experience. Volume 9, Issue 4, pages 255–274, April 1997.</ref>

Karmanka: #suggestededit-add 1.0

2022-04-30T16:06:51Z

#suggestededit-add 1.0

← Previous revision		Revision as of 16:06, 30 April 2022
Line 1:		Line 1:
			{{Short description\|Algorithm for matrix multiplication}}
	In [[computer science]], '''Cannon's algorithm''' is a [[distributed algorithm\|distributed]] [[algorithm for matrix multiplication]] for two-dimensional [[Mesh networking\|meshes]] first described in 1969 by [[Lynn Elliot Cannon]].<ref>Lynn Elliot Cannon, ''[http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=905686 A cellular computer to implement the Kalman Filter Algorithm]'', Technical report, Ph.D. Thesis, Montana State University, 14 July 1969.</ref><ref name="stanfordpaper">[http://dbpubs.stanford.edu:8090/pub/1994-25 Gupta, H.; Sadayappan, P.: Communication Efficient Matrix-Multiplication on Hypercubes], dbpubs.stanford.edu</ref>		In [[computer science]], '''Cannon's algorithm''' is a [[distributed algorithm\|distributed]] [[algorithm for matrix multiplication]] for two-dimensional [[Mesh networking\|meshes]] first described in 1969 by [[Lynn Elliot Cannon]].<ref>Lynn Elliot Cannon, ''[http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=905686 A cellular computer to implement the Kalman Filter Algorithm]'', Technical report, Ph.D. Thesis, Montana State University, 14 July 1969.</ref><ref name="stanfordpaper">[http://dbpubs.stanford.edu:8090/pub/1994-25 Gupta, H.; Sadayappan, P.: Communication Efficient Matrix-Multiplication on Hypercubes], dbpubs.stanford.edu</ref>

WeekdayWarrior: /* Generalisation */ Reverts incorrect Hadamard Product edits

2021-04-29T16:34:59Z

Generalisation: Reverts incorrect Hadamard Product edits

← Previous revision		Revision as of 16:34, 29 April 2021
Line 39:		Line 39:

	=== Generalisation ===		=== Generalisation ===
	In practice we have much fewer processors than the matrix elements. We can replace the matrix elements with submatrices, so that every processor processes more values. The scalar multiplication and addition ~~are~~ ~~replaced~~ by ~~adding the [[Hadamard product (matrices) \| Hadamard product]] of the submatrices of A~~ and ~~B to matrix C~~. The width and height of the submatrices will be <math>N=n/\sqrt {p}</math>.		In practice we have much fewer processors than the matrix elements. We can replace the matrix elements with submatrices, so that every processor processes more values. The scalar multiplication and addition become sequential matrix multiplication and addition. The width and height of the submatrices will be <math>N=n/\sqrt {p}</math>.

	The runtime of the algorithm is <math>T\mathcal{(n, p)} = T_{coll} (n/N, p) + N*T_{seq}(n/N) + 2(N - 1)(T_{start} + T_{byte}(n/ N)^2)		The runtime of the algorithm is <math>T\mathcal{(n, p)} = T_{coll} (n/N, p) + N*T_{seq}(n/N) + 2(N - 1)(T_{start} + T_{byte}(n/ N)^2)

47.215.198.231: /* Generalisation */ disambiguates Hadamard Product link

2021-04-23T04:42:31Z

Generalisation: disambiguates Hadamard Product link

← Previous revision		Revision as of 04:42, 23 April 2021
Line 39:		Line 39:

	=== Generalisation ===		=== Generalisation ===
	In practice we have much fewer processors than the matrix elements. We can replace the matrix elements with submatrices, so that every processor processes more values. The scalar multiplication and addition are replaced by adding the [[Hadamard product]] of the submatrices of A and B to matrix C. The width and height of the submatrices will be <math>N=n/\sqrt {p}</math>.		In practice we have much fewer processors than the matrix elements. We can replace the matrix elements with submatrices, so that every processor processes more values. The scalar multiplication and addition are replaced by adding the [[Hadamard product (matrices) \| Hadamard product]] of the submatrices of A and B to matrix C. The width and height of the submatrices will be <math>N=n/\sqrt {p}</math>.

	The runtime of the algorithm is <math>T\mathcal{(n, p)} = T_{coll} (n/N, p) + N*T_{seq}(n/N) + 2(N - 1)(T_{start} + T_{byte}(n/ N)^2)		The runtime of the algorithm is <math>T\mathcal{(n, p)} = T_{coll} (n/N, p) + N*T_{seq}(n/N) + 2(N - 1)(T_{start} + T_{byte}(n/ N)^2)