Communication-avoiding algorithm - Revision history

Beland: convert special characters found by Wikipedia:Typo Team/moss (via WP:JWB)

2024-04-17T20:54:44Z

convert special characters found by Wikipedia:Typo Team/moss (via WP:JWB)

← Previous revision		Revision as of 20:54, 17 April 2024
Line 53:		Line 53:
	* Measure of computation = Time per [[FLOP]] = γ		* Measure of computation = Time per [[FLOP]] = γ
	* Measure of communication = No. of words of data moved = β		* Measure of communication = No. of words of data moved = β
	⇒ Total running time = γ~~·~~(no. of [[FLOP]]s) + β~~·~~(no. of words)		⇒ Total running time = γ·(no. of [[FLOP]]s) + β·(no. of words)

	From the fact that ''β'' >> ''γ'' as measured in time and energy, communication cost dominates computation cost. Technological trends<ref name="DARPA_2008"/> indicate that the relative cost of communication is increasing on a variety of platforms, from [[cloud computing]] to [[supercomputers]] to mobile devices. The report also predicts that gap between [[DRAM]] access time and FLOPs will increase 100× over coming decade to balance power usage between processors and DRAM.<ref name="Demmel_2012"/>		From the fact that ''β'' >> ''γ'' as measured in time and energy, communication cost dominates computation cost. Technological trends<ref name="DARPA_2008"/> indicate that the relative cost of communication is increasing on a variety of platforms, from [[cloud computing]] to [[supercomputers]] to mobile devices. The report also predicts that gap between [[DRAM]] access time and FLOPs will increase 100× over coming decade to balance power usage between processors and DRAM.<ref name="Demmel_2012"/>
Line 91:		Line 91:

	for i = 1 to n		for i = 1 to n
	{read row i of A into fast memory} - n² reads		{read row i of A into fast memory} - n<sup>2</sup> reads
	for j = 1 to n		for j = 1 to n
	{read C(i,j) into fast memory} - n² reads		{read C(i,j) into fast memory} - n<sup>2</sup> reads
	{read column j of B into fast memory} - n³ reads		{read column j of B into fast memory} - n<sup>3</sup> reads
	for k = 1 to n		for k = 1 to n
	C(i,j) = C(i,j) + A(i,k) * B(k,j)		C(i,j) = C(i,j) + A(i,k) * B(k,j)
	{write C(i,j) back to slow memory} - n² writes		{write C(i,j) back to slow memory} - n<sup>2</sup> writes

	Fast memory may be defined as the local processor memory ([[CPU cache]]) of size M and slow memory may be defined as the DRAM.		Fast memory may be defined as the local processor memory ([[CPU cache]]) of size M and slow memory may be defined as the DRAM.
Line 103:		Line 103:
	Communication cost (reads/writes): ''n''<sup>3</sup> + 3''n''<sup>2</sup> or O(''n''<sup>3</sup>)		Communication cost (reads/writes): ''n''<sup>3</sup> + 3''n''<sup>2</sup> or O(''n''<sup>3</sup>)

	Since total running time = ''γ''~~·~~O(''n''<sup>3</sup>) + ''β''~~·~~O(''n''<sup>3</sup>) and ''β'' >> ''γ'' the communication cost is dominant. The blocked (tiled) matrix multiplication algorithm<ref name="Demmel_2012"/> reduces this dominant term:		Since total running time = ''γ''·O(''n''<sup>3</sup>) + ''β''·O(''n''<sup>3</sup>) and ''β'' >> ''γ'' the communication cost is dominant. The blocked (tiled) matrix multiplication algorithm<ref name="Demmel_2012"/> reduces this dominant term:

	==== Blocked (tiled) matrix multiplication ====		==== Blocked (tiled) matrix multiplication ====
Line 111:		Line 111:
	for i = 1 to n/b		for i = 1 to n/b
	for j = 1 to n/b		for j = 1 to n/b
	{read block C(i,j) into fast memory} - b² × (n/b)² = n² reads		{read block C(i,j) into fast memory} - b<sup>2</sup> × (n/b)<sup>2</sup> = n<sup>2</sup> reads
	for k = 1 to n/b		for k = 1 to n/b
	{read block A(i,k) into fast memory} - b² × (n/b)³ = n³/b reads		{read block A(i,k) into fast memory} - b<sup>2</sup> × (n/b)<sup>3</sup> = n<sup>3</sup>/b reads
	{read block B(k,j) into fast memory} - b² × (n/b)³ = n³/b reads		{read block B(k,j) into fast memory} - b<sup>2</sup> × (n/b)<sup>3</sup> = n<sup>3</sup>/b reads
	C(i,j) = C(i,j) + A(i,k) * B(k,j) - {do a matrix multiply on blocks}		C(i,j) = C(i,j) + A(i,k) * B(k,j) - {do a matrix multiply on blocks}
	{write block C(i,j) back to slow memory} - b² × (n/b)² = n² writes		{write block C(i,j) back to slow memory} - b<sup>2</sup> × (n/b)<sup>2</sup> = n<sup>2</sup> writes

	Communication cost: 2''n''<sup>3</sup>/''b'' + 2''n''<sup>2</sup> reads/writes << 2''n''<sup>3</sup> arithmetic cost		Communication cost: 2''n''<sup>3</sup>/''b'' + 2''n''<sup>2</sup> reads/writes << 2''n''<sup>3</sup> arithmetic cost
Line 137:		Line 137:
	<ref name="DARPA_2008">Bergman, Keren, et al. "[http://staff.kfupm.edu.sa/ics/ahkhan/Resources/Articles/ExaScale%20Computing/TR-2008-13.pdf Exascale computing study: Technology challenges in exascale computing systems]." [[Defense Advanced Research Projects Agency]] [[Information Processing Techniques Office]] (DARPA IPTO), Tech. Rep 15 (2008).</ref>		<ref name="DARPA_2008">Bergman, Keren, et al. "[http://staff.kfupm.edu.sa/ics/ahkhan/Resources/Articles/ExaScale%20Computing/TR-2008-13.pdf Exascale computing study: Technology challenges in exascale computing systems]." [[Defense Advanced Research Projects Agency]] [[Information Processing Techniques Office]] (DARPA IPTO), Tech. Rep 15 (2008).</ref>
	<ref name="Shalf_2010">Shalf, John, Sudip Dosanjh, and John Morrison. "Exascale computing technology challenges". High Performance Computing for Computational Science–VECPAR 2010. Springer Berlin Heidelberg, 2011. 1–25.</ref>		<ref name="Shalf_2010">Shalf, John, Sudip Dosanjh, and John Morrison. "Exascale computing technology challenges". High Performance Computing for Computational Science–VECPAR 2010. Springer Berlin Heidelberg, 2011. 1–25.</ref>
	<ref name="Frigo_1999">M. Frigo, C. E. Leiserson, H. Prokop, and S. Ramachandran, ~~“Cacheoblivious~~ ~~algorithms”~~, In FOCS ~~’99~~: Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999. IEEE Computer Society.</ref>		<ref name="Frigo_1999">M. Frigo, C. E. Leiserson, H. Prokop, and S. Ramachandran, "Cacheoblivious algorithms", In FOCS '99: Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999. IEEE Computer Society.</ref>
	<ref name="Toledo_1997">S. Toledo, “[https://web.archive.org/web/20180102191420/https://pdfs.semanticscholar.org/d198/43912d46f6a25de815eadb1fb43d5ca6f61c.pdf Locality of reference in LU Decomposition with partial pivoting],” SIAM J. Matrix Anal. Appl., vol. 18, no. 4, 1997.</ref>		<ref name="Toledo_1997">S. Toledo, "[https://web.archive.org/web/20180102191420/https://pdfs.semanticscholar.org/d198/43912d46f6a25de815eadb1fb43d5ca6f61c.pdf Locality of reference in LU Decomposition with partial pivoting]," SIAM J. Matrix Anal. Appl., vol. 18, no. 4, 1997.</ref>
	<ref name="Gustavson_1997">F. Gustavson, ~~“Recursion~~ Leads to Automatic Variable Blocking for Dense Linear-Algebra Algorithms,” IBM Journal of Research and Development, vol. 41, no. 6, pp. 737–755, 1997.</ref>		<ref name="Gustavson_1997">F. Gustavson, "Recursion Leads to Automatic Variable Blocking for Dense Linear-Algebra Algorithms," IBM Journal of Research and Development, vol. 41, no. 6, pp. 737–755, 1997.</ref>
	<ref name="Elmroth_2004">E. Elmroth, F. Gustavson, I. Jonsson, and B. Kagstrom, “[http://www.csc.kth.se/utbildning/kth/kurser/2D1253/matalg06/SIR000003.pdf Recursive blocked algorithms and hybrid data structures for dense matrix library software],” SIAM Review, vol. 46, no. 1, pp. 3–45, 2004.</ref>		<ref name="Elmroth_2004">E. Elmroth, F. Gustavson, I. Jonsson, and B. Kagstrom, "[http://www.csc.kth.se/utbildning/kth/kurser/2D1253/matalg06/SIR000003.pdf Recursive blocked algorithms and hybrid data structures for dense matrix library software]," SIAM Review, vol. 46, no. 1, pp. 3–45, 2004.</ref>
	<ref name="Grigori_2014">[[Laura Grigori\|Grigori, Laura]]. "[http://www.lifl.fr/jncf2014/files/lecture-notes/grigori.pdf Introduction to communication avoiding linear algebra algorithms in high performance computing].</ref>		<ref name="Grigori_2014">[[Laura Grigori\|Grigori, Laura]]. "[http://www.lifl.fr/jncf2014/files/lecture-notes/grigori.pdf Introduction to communication avoiding linear algebra algorithms in high performance computing].</ref>
	}}		}}

Citation bot: Alter: title, template type. Add: chapter-url, pages, chapter. Removed or converted URL. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox3 | #UCB_webform_linked 371/2306

2023-08-06T12:39:39Z

Alter: title, template type. Add: chapter-url, pages, chapter. Removed or converted URL. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox3 | #UCB_webform_linked 371/2306

← Previous revision		Revision as of 12:39, 6 August 2023
Line 14:		Line 14:

	=== Matrix multiplication ===		=== Matrix multiplication ===
	<ref>{{Cite ~~journal~~ \|last1=Jia-Wei \|first1=Hong \|last2=Kung \|first2=H. T. \|~~date~~=~~1981~~ \|~~title~~=I/O complexity: ~~The~~ ~~red-blue pebble game~~ \|url=http://dx.doi.org/10.1145/800076.802486 ~~\|journal=Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computing - STOC '81~~ \|location=New York, New York, USA \|publisher=ACM Press \|doi=10.1145/800076.802486\|s2cid=8410593 }}</ref> Corollary 6.2:		<ref>{{Cite book \|last1=Jia-Wei \|first1=Hong \|last2=Kung \|first2=H. T. \|title=Proceedings of the thirteenth annual ACM symposium on Theory of computing - STOC '81 \|chapter=I/O complexity \|date=1981 \|pages=326–333 \|chapter-url=http://dx.doi.org/10.1145/800076.802486 \|location=New York, New York, USA \|publisher=ACM Press \|doi=10.1145/800076.802486\|s2cid=8410593 }}</ref> Corollary 6.2:

	{{Math theorem		{{Math theorem

Citation bot: Alter: journal, template type. Add: eprint, class, s2cid, authors 1-1. Removed proxy/dead URL that duplicated identifier. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | #UCB_toolbar

2023-04-08T02:58:19Z

Alter: journal, template type. Add: eprint, class, s2cid, authors 1-1. Removed proxy/dead URL that duplicated identifier. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | #UCB_toolbar

← Previous revision		Revision as of 02:58, 8 April 2023
Line 14:		Line 14:

	=== Matrix multiplication ===		=== Matrix multiplication ===
	<ref>{{Cite journal \|~~last~~=Jia-Wei \|~~first~~=Hong \|last2=Kung \|first2=H. T. \|date=1981 \|title=I/O complexity: The red-blue pebble game \|url=http://dx.doi.org/10.1145/800076.802486 \|journal=Proceedings of the ~~thirteenth~~ ~~annual~~ ACM ~~symposium~~ on Theory of ~~computing~~ - STOC '81 \|location=New York, New York, USA \|publisher=ACM Press \|doi=10.1145/800076.802486}}</ref> Corollary 6.2:		<ref>{{Cite journal \|last1=Jia-Wei \|first1=Hong \|last2=Kung \|first2=H. T. \|date=1981 \|title=I/O complexity: The red-blue pebble game \|url=http://dx.doi.org/10.1145/800076.802486 \|journal=Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computing - STOC '81 \|location=New York, New York, USA \|publisher=ACM Press \|doi=10.1145/800076.802486\|s2cid=8410593 }}</ref> Corollary 6.2:

	{{Math theorem		{{Math theorem
Line 24:		Line 24:
	}}		}}

	More general results for other numerical linear algebra operations can be found in.<ref>{{Cite journal \|~~last~~=Ballard \|~~first~~=G. \|last2=Carson \|first2=E. \|last3=Demmel \|first3=J. \|last4=Hoemmen \|first4=M. \|last5=Knight \|first5=N. \|last6=Schwartz \|first6=O. \|date=May 2014 \|title=Communication lower bounds and optimal algorithms for numerical linear algebra \|url=http://dx.doi.org/10.1017/s0962492914000038 \|journal=Acta Numerica \|volume=23 \|pages=1–155 \|doi=10.1017/s0962492914000038 \|issn=0962-4929}}</ref> The following proof is from.<ref>{{Cite ~~journal~~ \|~~last~~=Demmel \|~~first~~=James \|last2=Dinh \|first2=Grace \|date=2018-04-24 \|title=Communication-Optimal Convolutional Neural Nets \|~~url~~=~~http://arxiv~~.~~org/abs/1802.06905~~ \|~~journal~~=~~arXiv:~~1802.06905 ~~[cs]~~}}</ref>		More general results for other numerical linear algebra operations can be found in.<ref>{{Cite journal \|last1=Ballard \|first1=G. \|last2=Carson \|first2=E. \|last3=Demmel \|first3=J. \|last4=Hoemmen \|first4=M. \|last5=Knight \|first5=N. \|last6=Schwartz \|first6=O. \|date=May 2014 \|title=Communication lower bounds and optimal algorithms for numerical linear algebra \|url=http://dx.doi.org/10.1017/s0962492914000038 \|journal=Acta Numerica \|volume=23 \|pages=1–155 \|doi=10.1017/s0962492914000038 \|s2cid=122513943 \|issn=0962-4929}}</ref> The following proof is from.<ref>{{Cite arXiv \|last1=Demmel \|first1=James \|last2=Dinh \|first2=Grace \|date=2018-04-24 \|title=Communication-Optimal Convolutional Neural Nets \|class=cs.DS \|eprint=1802.06905 }}</ref>

	{{Math proof\|title=Proof\|proof=		{{Math proof\|title=Proof\|proof=

Keith D: Fix cite date error

2023-03-16T00:56:41Z

Fix cite date error

Cosmia Nebula: /* Matrix multiplication */

2023-03-15T23:55:29Z

Matrix multiplication

← Previous revision		Revision as of 23:55, 15 March 2023
Line 36:		Line 36:
	During each segment, the processor has access to at most <math>2M</math> different points from <math>A, B, C</math>.		During each segment, the processor has access to at most <math>2M</math> different points from <math>A, B, C</math>.

	Let <math>E</math> be the set of lattice points covered during this segment. Then by [[Loomis–Whitney inequality]],		Let <math>E</math> be the set of lattice points covered during this segment. Then by the [[Loomis–Whitney inequality]],

	<math display="block">\|E\| \leq \sqrt{\|\pi_1(E)\|\|\pi_2(E)\|\|\pi_3(E)\|}</math>		<math display="block">\|E\| \leq \sqrt{\|\pi_1(E)\|\|\pi_2(E)\|\|\pi_3(E)\|}</math>
	with constraint <math>\sum_i \|\pi_i(E)\| \leq 2M.</math>.		with constraint <math>\sum_i \|\pi_i(E)\| \leq 2M</math>.

	By [[inequality of arithmetic and geometric means]], we have <math>\|E\| \leq \left(\frac 23 M\right)^{3/2}</math>, with extremum reached when <math>\pi_i(E) = \frac 23 M</math>.		By the [[inequality of arithmetic and geometric means]], we have <math>\|E\| \leq \left(\frac 23 M\right)^{3/2}</math>, with extremum reached when <math>\pi_i(E) = \frac 23 M</math>.

	Thus the arithmetic intensity is bounded above by <math>CM^{1/2}</math> where <math>C = (2/3)^{3/2}</math>, and so the communication is bounded below by <math>\frac{nmk}{CM^{1/2}}</math>.		Thus the arithmetic intensity is bounded above by <math>CM^{1/2}</math> where <math>C = (2/3)^{3/2}</math>, and so the communication is bounded below by <math>\frac{nmk}{CM^{1/2}}</math>.
Line 47:		Line 47:
	Direct computation verifies that the tiling matrix multiplication algorithm reaches the lower bound.		Direct computation verifies that the tiling matrix multiplication algorithm reaches the lower bound.
	}}		}}


	== Motivation ==		== Motivation ==

Cosmia Nebula: /* Matrix multiplication */ fix links

2023-03-15T23:49:50Z

Matrix multiplication: fix links

← Previous revision		Revision as of 23:49, 15 March 2023
Line 21:		Line 21:
	\| math_statement = Given matrices <math>A, B, C</math> of sizes <math>n\times m, m \times k, n\times k</math>, then <math>AB + C</math> has communication complexity <math>\Omega(\max(mkn/M^{1/2}, mk+kn+mk))</math>.		\| math_statement = Given matrices <math>A, B, C</math> of sizes <math>n\times m, m \times k, n\times k</math>, then <math>AB + C</math> has communication complexity <math>\Omega(\max(mkn/M^{1/2}, mk+kn+mk))</math>.

	This lower bound is achievable by [[tiling matrix multiplication]].		This lower bound is achievable by [[Communication-avoiding_algorithm#Matrix_multiplication_example\|tiling matrix multiplication]].
	}}		}}

Line 39:		Line 39:

	<math display="block">\|E\| \leq \sqrt{\|\pi_1(E)\|\|\pi_2(E)\|\|\pi_3(E)\|}</math>		<math display="block">\|E\| \leq \sqrt{\|\pi_1(E)\|\|\pi_2(E)\|\|\pi_3(E)\|}</math>
	with constraint		with constraint <math>\sum_i \|\pi_i(E)\| \leq 2M.</math>.

			By [[inequality of arithmetic and geometric means]], we have <math>\|E\| \leq \left(\frac 23 M\right)^{3/2}</math>, with extremum reached when <math>\pi_i(E) = \frac 23 M</math>.
	<math display="block">\sum_i \|\pi_i(E)\| \leq 2M.</math>
	.

	By [[inequality of arithmetic and geometric means]], we have

	<math display="block">\|E\| \leq \left(\frac 23 M\right)^{3/2}</math>
	with extremum reached when <math>\pi_i(E) = \frac 23 M</math>.

	Thus the arithmetic intensity is bounded above by <math>CM^{1/2}</math> where <math>C = (2/3)^{3/2}</math>, and so the communication is bounded below by <math>\frac{nmk}{CM^{1/2}}</math>.		Thus the arithmetic intensity is bounded above by <math>CM^{1/2}</math> where <math>C = (2/3)^{3/2}</math>, and so the communication is bounded below by <math>\frac{nmk}{CM^{1/2}}</math>.
Line 53:		Line 47:
	Direct computation verifies that the tiling matrix multiplication algorithm reaches the lower bound.		Direct computation verifies that the tiling matrix multiplication algorithm reaches the lower bound.
	}}		}}


	== Motivation ==		== Motivation ==

Cosmia Nebula: /* Matrix multiplication */ citation for proof

2023-03-15T23:47:56Z

Matrix multiplication: citation for proof

← Previous revision		Revision as of 23:47, 15 March 2023
Line 16:		Line 16:
	<ref>{{Cite journal \|last=Jia-Wei \|first=Hong \|last2=Kung \|first2=H. T. \|date=1981 \|title=I/O complexity: The red-blue pebble game \|url=http://dx.doi.org/10.1145/800076.802486 \|journal=Proceedings of the thirteenth annual ACM symposium on Theory of computing - STOC '81 \|location=New York, New York, USA \|publisher=ACM Press \|doi=10.1145/800076.802486}}</ref> Corollary 6.2:		<ref>{{Cite journal \|last=Jia-Wei \|first=Hong \|last2=Kung \|first2=H. T. \|date=1981 \|title=I/O complexity: The red-blue pebble game \|url=http://dx.doi.org/10.1145/800076.802486 \|journal=Proceedings of the thirteenth annual ACM symposium on Theory of computing - STOC '81 \|location=New York, New York, USA \|publisher=ACM Press \|doi=10.1145/800076.802486}}</ref> Corollary 6.2:

	{{Math theorem\|name=Theorem\|note~~=\|math_statement~~=		{{Math theorem
			\| name = Theorem
			\| note =
	Given matrices <math>A, B, C</math> of sizes <math>n\times m, m \times k, n\times k</math>, then <math>AB + C</math> has communication complexity <math>\Omega(mkn/M^{1/2})</math>.}}		\| math_statement = Given matrices <math>A, B, C</math> of sizes <math>n\times m, m \times k, n\times k</math>, then <math>AB + C</math> has communication complexity <math>\Omega(\max(mkn/M^{1/2}, mk+kn+mk))</math>.

			This lower bound is achievable by [[tiling matrix multiplication]].
⚫	More general results for other numerical linear algebra operations can be found in <ref>{{Cite journal \|last=Ballard \|first=G. \|last2=Carson \|first2=E. \|last3=Demmel \|first3=J. \|last4=Hoemmen \|first4=M. \|last5=Knight \|first5=N. \|last6=Schwartz \|first6=O. \|date=2014-05 \|title=Communication lower bounds and optimal algorithms for numerical linear algebra \|url=http://dx.doi.org/10.1017/s0962492914000038 \|journal=Acta Numerica \|volume=23 \|pages=1–155 \|doi=10.1017/s0962492914000038 \|issn=0962-4929}}</ref>.
			}}

		⚫	More general results for other numerical linear algebra operations can be found in <ref>{{Cite journal \|last=Ballard \|first=G. \|last2=Carson \|first2=E. \|last3=Demmel \|first3=J. \|last4=Hoemmen \|first4=M. \|last5=Knight \|first5=N. \|last6=Schwartz \|first6=O. \|date=2014-05 \|title=Communication lower bounds and optimal algorithms for numerical linear algebra \|url=http://dx.doi.org/10.1017/s0962492914000038 \|journal=Acta Numerica \|volume=23 \|pages=1–155 \|doi=10.1017/s0962492914000038 \|issn=0962-4929}}</ref>. The following proof is from <ref>{{Cite journal \|last=Demmel \|first=James \|last2=Dinh \|first2=Grace \|date=2018-04-24 \|title=Communication-Optimal Convolutional Neural Nets \|url=http://arxiv.org/abs/1802.06905 \|journal=arXiv:1802.06905 [cs]}}</ref>.

	{{Math proof\|title=Proof\|proof=		{{Math proof\|title=Proof\|proof=
Line 45:		Line 50:

	Thus the arithmetic intensity is bounded above by <math>CM^{1/2}</math> where <math>C = (2/3)^{3/2}</math>, and so the communication is bounded below by <math>\frac{nmk}{CM^{1/2}}</math>.		Thus the arithmetic intensity is bounded above by <math>CM^{1/2}</math> where <math>C = (2/3)^{3/2}</math>, and so the communication is bounded below by <math>\frac{nmk}{CM^{1/2}}</math>.

			Direct computation verifies that the tiling matrix multiplication algorithm reaches the lower bound.
	}}		}}

Cosmia Nebula: /* Matrix multiplication */ links to theorem

2023-03-15T23:42:33Z

Matrix multiplication: links to theorem

← Previous revision		Revision as of 23:42, 15 March 2023
Line 23:		Line 23:
	{{Math proof\|title=Proof\|proof=		{{Math proof\|title=Proof\|proof=

	We can draw the computation graph of <math>AB + C</math> as a cube. ~~Computing~~ <math>AB+C</math> requires the processor to have access to each point within the cube at least once. So the problem becomes covering the <math>mnk</math> ~~grid~~ points with a minimal amount of communication.		We can draw the computation graph of <math>D = AB + C</math> as a cube of lattice points, each point is of form <math>(i,j,k)</math>. Since <math>D[i,k] = \sum_j A[i,j]B[j,k] + C[i,k]</math>, computing <math>AB+C</math> requires the processor to have access to each point within the cube at least once. So the problem becomes covering the <math>mnk</math> lattice points with a minimal amount of communication.

	If <math>M</math> is large, then we can simply load all <math>mn+nk+mk</math> entries then write <math>nk</math> entries. This is uninteresting.		If <math>M</math> is large, then we can simply load all <math>mn+nk+mk</math> entries then write <math>nk</math> entries. This is uninteresting.
Line 31:		Line 31:
	During each segment, the processor has access to at most <math>2M</math> different points from <math>A, B, C</math>.		During each segment, the processor has access to at most <math>2M</math> different points from <math>A, B, C</math>.

	Let <math>E</math> be the set of lattice points covered during this segment. Then by Loomis–Whitney inequality,		Let <math>E</math> be the set of lattice points covered during this segment. Then by [[Loomis–Whitney inequality]],

	<math display="block">\|E\| \leq \sqrt{\|\pi_1(E)\|\|\pi_2(E)\|\|\pi_3(E)\|}</math>		<math display="block">\|E\| \leq \sqrt{\|\pi_1(E)\|\|\pi_2(E)\|\|\pi_3(E)\|}</math>
	with constraint		with constraint

	<math display="block">\sum_i \|\pi_i(E)\| \leq 2M</math>		<math display="block">\sum_i \|\pi_i(E)\| \leq 2M.</math>
	.		.

	By arithmetic~~-geometric~~ ~~mean~~ ~~inequality~~, we have		By [[inequality of arithmetic and geometric means]], we have

	<math display="block">\|E\| \leq \left(\frac 23 M\right)^{3/2}</math>		<math display="block">\|E\| \leq \left(\frac 23 M\right)^{3/2}</math>

Cosmia Nebula: /* Matrix multiplication */ proof of claim

2023-03-15T23:39:47Z

Matrix multiplication: proof of claim

← Previous revision		Revision as of 23:39, 15 March 2023
Line 20:		Line 20:

	More general results for other numerical linear algebra operations can be found in <ref>{{Cite journal \|last=Ballard \|first=G. \|last2=Carson \|first2=E. \|last3=Demmel \|first3=J. \|last4=Hoemmen \|first4=M. \|last5=Knight \|first5=N. \|last6=Schwartz \|first6=O. \|date=2014-05 \|title=Communication lower bounds and optimal algorithms for numerical linear algebra \|url=http://dx.doi.org/10.1017/s0962492914000038 \|journal=Acta Numerica \|volume=23 \|pages=1–155 \|doi=10.1017/s0962492914000038 \|issn=0962-4929}}</ref>.		More general results for other numerical linear algebra operations can be found in <ref>{{Cite journal \|last=Ballard \|first=G. \|last2=Carson \|first2=E. \|last3=Demmel \|first3=J. \|last4=Hoemmen \|first4=M. \|last5=Knight \|first5=N. \|last6=Schwartz \|first6=O. \|date=2014-05 \|title=Communication lower bounds and optimal algorithms for numerical linear algebra \|url=http://dx.doi.org/10.1017/s0962492914000038 \|journal=Acta Numerica \|volume=23 \|pages=1–155 \|doi=10.1017/s0962492914000038 \|issn=0962-4929}}</ref>.

			{{Math proof\|title=Proof\|proof=

			We can draw the computation graph of <math>AB + C</math> as a cube. Computing <math>AB+C</math> requires the processor to have access to each point within the cube at least once. So the problem becomes covering the <math>mnk</math> grid points with a minimal amount of communication.

			If <math>M</math> is large, then we can simply load all <math>mn+nk+mk</math> entries then write <math>nk</math> entries. This is uninteresting.

			If <math>M</math> is small, then we can divide the minimal-communication algorithm into separate segments. During each segment, it performs exactly <math>M</math> reads to cache, and any number of writes from cache.

			During each segment, the processor has access to at most <math>2M</math> different points from <math>A, B, C</math>.

			Let <math>E</math> be the set of lattice points covered during this segment. Then by Loomis–Whitney inequality,

			<math display="block">\|E\| \leq \sqrt{\|\pi_1(E)\|\|\pi_2(E)\|\|\pi_3(E)\|}</math>
			with constraint

			<math display="block">\sum_i \|\pi_i(E)\| \leq 2M</math>
			.

			By arithmetic-geometric mean inequality, we have

			<math display="block">\|E\| \leq \left(\frac 23 M\right)^{3/2}</math>
			with extremum reached when <math>\pi_i(E) = \frac 23 M</math>.

			Thus the arithmetic intensity is bounded above by <math>CM^{1/2}</math> where <math>C = (2/3)^{3/2}</math>, and so the communication is bounded below by <math>\frac{nmk}{CM^{1/2}}</math>.
			}}

	== Motivation ==		== Motivation ==

Cosmia Nebula: /* Two-level memory model */

2023-03-15T23:01:32Z

Two-level memory model

← Previous revision		Revision as of 23:01, 15 March 2023
Line 8:		Line 8:

	* There is one processor and two levels of memory.		* There is one processor and two levels of memory.
	* Level 1 memory is infinitely large. Level 0 memory ("cache") has size $M$.		* Level 1 memory is infinitely large. Level 0 memory ("cache") has size <math>M</math>.
	* In the beginning, input resides in level 1. In the end, the output resides in level 1.		* In the beginning, input resides in level 1. In the end, the output resides in level 1.
	* Processor can only operate on data in cache.		* Processor can only operate on data in cache.

← Previous revision		Revision as of 00:56, 16 March 2023
Line 19:		Line 19:
	\| name = Theorem		\| name = Theorem
	\| note =		\| note =
	\| math_statement = Given matrices <math>A, B, C</math> of sizes <math>n\times m, m \times k, n\times k</math>, then <math>AB + C</math> has communication complexity <math>\Omega(\max(mkn/M^{1/2}, mk+kn+mk))</math>.		\| math_statement = Given matrices <math>A, B, C</math> of sizes <math>n\times m, m \times k, n\times k</math>, then <math>AB + C</math> has communication complexity <math>\Omega(\max(mkn/M^{1/2}, mk+kn+mk))</math>.

	This lower bound is achievable by [[Communication-~~avoiding_algorithm~~#~~Matrix_multiplication_example~~\|tiling matrix multiplication]].		This lower bound is achievable by [[Communication-avoiding algorithm#Matrix multiplication example\|tiling matrix multiplication]].
	}}		}}

	More general results for other numerical linear algebra operations can be found in <ref>{{Cite journal \|last=Ballard \|first=G. \|last2=Carson \|first2=E. \|last3=Demmel \|first3=J. \|last4=Hoemmen \|first4=M. \|last5=Knight \|first5=N. \|last6=Schwartz \|first6=O. \|date=2014~~-05~~ \|title=Communication lower bounds and optimal algorithms for numerical linear algebra \|url=http://dx.doi.org/10.1017/s0962492914000038 \|journal=Acta Numerica \|volume=23 \|pages=1–155 \|doi=10.1017/s0962492914000038 \|issn=0962-4929}}</ref>. The following proof is from <ref>{{Cite journal \|last=Demmel \|first=James \|last2=Dinh \|first2=Grace \|date=2018-04-24 \|title=Communication-Optimal Convolutional Neural Nets \|url=http://arxiv.org/abs/1802.06905 \|journal=arXiv:1802.06905 [cs]}}</ref>.		More general results for other numerical linear algebra operations can be found in.<ref>{{Cite journal \|last=Ballard \|first=G. \|last2=Carson \|first2=E. \|last3=Demmel \|first3=J. \|last4=Hoemmen \|first4=M. \|last5=Knight \|first5=N. \|last6=Schwartz \|first6=O. \|date=May 2014 \|title=Communication lower bounds and optimal algorithms for numerical linear algebra \|url=http://dx.doi.org/10.1017/s0962492914000038 \|journal=Acta Numerica \|volume=23 \|pages=1–155 \|doi=10.1017/s0962492914000038 \|issn=0962-4929}}</ref> The following proof is from.<ref>{{Cite journal \|last=Demmel \|first=James \|last2=Dinh \|first2=Grace \|date=2018-04-24 \|title=Communication-Optimal Convolutional Neural Nets \|url=http://arxiv.org/abs/1802.06905 \|journal=arXiv:1802.06905 [cs]}}</ref>

	{{Math proof\|title=Proof\|proof=		{{Math proof\|title=Proof\|proof=

	We can draw the computation graph of <math>D = AB + C</math> as a cube of lattice points, each point is of form <math>(i,j,k)</math>. Since <math>D[i,k] = \sum_j A[i,j]B[j,k] + C[i,k]</math>, computing <math>AB+C</math> requires the processor to have access to each point within the cube at least once. So the problem becomes covering the <math>mnk</math> lattice points with a minimal amount of communication.		We can draw the computation graph of <math>D = AB + C</math> as a cube of lattice points, each point is of form <math>(i,j,k)</math>. Since <math>D[i,k] = \sum_j A[i,j]B[j,k] + C[i,k]</math>, computing <math>AB+C</math> requires the processor to have access to each point within the cube at least once. So the problem becomes covering the <math>mnk</math> lattice points with a minimal amount of communication.
Line 39:		Line 39:

	<math display="block">\|E\| \leq \sqrt{\|\pi_1(E)\|\|\pi_2(E)\|\|\pi_3(E)\|}</math>		<math display="block">\|E\| \leq \sqrt{\|\pi_1(E)\|\|\pi_2(E)\|\|\pi_3(E)\|}</math>
	with constraint <math>\sum_i \|\pi_i(E)\| \leq 2M</math>.		with constraint <math>\sum_i \|\pi_i(E)\| \leq 2M</math>.

	By the [[inequality of arithmetic and geometric means]], we have <math>\|E\| \leq \left(\frac 23 M\right)^{3/2}</math>, with extremum reached when <math>\pi_i(E) = \frac 23 M</math>.		By the [[inequality of arithmetic and geometric means]], we have <math>\|E\| \leq \left(\frac 23 M\right)^{3/2}</math>, with extremum reached when <math>\pi_i(E) = \frac 23 M</math>.

	Thus the arithmetic intensity is bounded above by <math>CM^{1/2}</math> where <math>C = (2/3)^{3/2}</math>, and so the communication is bounded below by <math>\frac{nmk}{CM^{1/2}}</math>.		Thus the arithmetic intensity is bounded above by <math>CM^{1/2}</math> where <math>C = (2/3)^{3/2}</math>, and so the communication is bounded below by <math>\frac{nmk}{CM^{1/2}}</math>.
Line 67:		Line 67:
	Energy consumption increases by orders of magnitude as we go higher in the memory hierarchy.<ref name="Shalf_2010"/>		Energy consumption increases by orders of magnitude as we go higher in the memory hierarchy.<ref name="Shalf_2010"/>

	United States president Barack Obama cited communication-avoiding algorithms in the FY 2012 Department of Energy budget request to Congress:<ref name="Demmel_2012" /> {{~~quote~~\|New Algorithm Improves Performance and Accuracy on Extreme-Scale Computing Systems. On modern computer architectures, communication between processors takes longer than the performance of a [[floating-point arithmetic]] operation by a given processor. ASCR researchers have developed a new method, derived from commonly used linear algebra methods, to minimize communications between processors and the memory hierarchy, by reformulating the communication patterns specified within the algorithm. This method has been implemented in the TRILINOS framework, a highly-regarded suite of software, which provides functionality for researchers around the world to solve large scale, complex multi-physics problems.}}		United States president Barack Obama cited communication-avoiding algorithms in the FY 2012 Department of Energy budget request to Congress:<ref name="Demmel_2012" /> {{blockquote\|New Algorithm Improves Performance and Accuracy on Extreme-Scale Computing Systems. On modern computer architectures, communication between processors takes longer than the performance of a [[floating-point arithmetic]] operation by a given processor. ASCR researchers have developed a new method, derived from commonly used linear algebra methods, to minimize communications between processors and the memory hierarchy, by reformulating the communication patterns specified within the algorithm. This method has been implemented in the TRILINOS framework, a highly-regarded suite of software, which provides functionality for researchers around the world to solve large scale, complex multi-physics problems.}}

	== Objectives ==		== Objectives ==