Profiling - Revision history

GethinWilliams: /* Don't thrash the cache */

2013-09-24T10:32:27Z

Don't thrash the cache

GethinWilliams: /* Don't thrash the cache */

2013-09-24T10:24:28Z

Don't thrash the cache

GethinWilliams: /* Don't thrash the cache */

2013-09-24T10:21:35Z

Don't thrash the cache

GethinWilliams: /* Don't thrash the cache */

2013-09-24T10:09:34Z

Don't thrash the cache

GethinWilliams: /* Don't thrash the cache */

2013-09-24T10:07:32Z

Don't thrash the cache

GethinWilliams: /* Suggested Exercises */

2013-09-20T10:38:58Z

Suggested Exercises

GethinWilliams: /* Heed the Memory Hierarchy */

2013-09-20T10:36:08Z

Heed the Memory Hierarchy

GethinWilliams: /* Don't thrash the cache */

2013-09-20T10:25:45Z

Don't thrash the cache

GethinWilliams: /* Only then Consider Parallel Programming */

2013-09-20T10:10:30Z

Only then Consider Parallel Programming

GethinWilliams: /* Don't thrash the cache */

2013-09-20T10:00:34Z

Don't thrash the cache

@@ Line 499: / Line 499: @@
 How can we ensure that we make best use of the memory hierarchy?  In order to devise a good strategy, we must appreciate some of the hidden details of the inner workings of a computer:  Let's say a program requests to ''read'' a single item from memory.  First, the computer will look for the item in cache.  If the data is not found in cache, it will be fetched from main memory, so as to create a more readily accessible copy.  Single items are not fetched, however.  Instead chunks of data are copied into cache.  The size of this chunk matches the size of an element of storage in cache known as a ''cache line'' (often 64 bytes in today's machines).  The situation is a little more complex when ''writing'', as we have to ensure that both cache and main memory are synchronised, but--in the interests of brevity--we'll skip over this just now.
-[[Image:Cache-reuse.jpg|650px|thumbnail|centre|Try your best to re-use the data already in cache.]]
+[[Image:Cache-reuse.jpg|650px|thumbnail|left|Try your best to re-use the data already in cache.]]
-<gallery widths=300px heights=300px perrow=2>
+<gallery widths=250px heights=250px perrow=2>
 File:five-point-stencil.jpg|Stencil for a 2D finite difference approximation to the 2nd differential
 File:4x4-2D-laplacian-grid.jpg|Grid for 2D heat equation
 </gallery>
-Access patterns with the above 'stencil'--such as that required to solve the 2D heat equation are also prone to thrash the cache, when the size of the arrays are large:
+Access patterns with the above 'stencil'--such as that required to solve the 2D heat equation are also prone to thrash the cache, when the size of the arrays are large (800x800 doubles, run on my desktop machine):
 <pre>

@@ Line 503: / Line 503: @@
 <gallery widths=300px heights=300px perrow=2>
 File:five-point-stencil.jpg|Stencil for a 2D finite difference approximation to the 2nd differential
 </gallery>

@@ Line 503: / Line 503: @@
 <gallery widths=300px heights=300px perrow=2>
 File:five-point-stencil.jpg|Stencil for a 2D finite difference approximation to the 2nd differential
 </gallery>

@@ Line 501: / Line 501: @@
 [[Image:Cache-reuse.jpg|650px|thumbnail|centre|Try your best to re-use the data already in cache.]]
-[[Image:five-point-stencil.jpg|200px|thumbnail|centre|Stencil for a 2D finite difference approximation to the 2nd differential]]
+<gallery widths=300px heights=300px perrow=2>
 Access patterns with the above 'stencil'--such as that required to solve the 2D heat equation are also prone to thrash the cache, when the size of the arrays are large:

@@ Line 501: / Line 501: @@
 [[Image:Cache-reuse.jpg|650px|thumbnail|centre|Try your best to re-use the data already in cache.]]
-The pay-off for this chunked approach is that if the program now requests to read another item from memory, and that item was part of the previous fetch, then it will already be in cache and a slow journey to main memory will be avoided.  Thus we can see that '''re-use of data already in cache''' will be a key factor in program performance.
+[[Image:five-point-stencil.jpg|200px|thumbnail|centre|Stencil for a 2D finite difference approximation to the 2nd differential]]
-A good example of this would be a looping situation.  A loop order which predominately cycles over items already in cache will run much faster than one which demands that cache is constantly refreshed.  Another point to note is that cache size is limited, so a loop cannot access many large arrays with impunity.  Using too many arrays in a single loop will exhaust cache capacity and force evictions and subsequent re-reads of essential items.
+Access patterns with the above 'stencil'--such as that required to solve the 2D heat equation are also prone to thrash the cache, when the size of the arrays are large:
 As as example of adhering to the principle of spatial locality, consider two almost identical programs ('''loopingA.f90''' and '''loopingB.f90''').  You will see that inside each program a 2-dimensional array is declared and two nested loops are used to visit each of the cells of the array in turn (and an arithmetic value is dropped in).  The only way in which the two programs differ is the order in which the cycle through the contents of the arrays.  In '''loopingA.f90''', the outer loop is over the rows of the array and the inner loop is over the columns (i.e. for a given value of '''ii''', all values of '''jj''' and cycled over):

@@ Line 855: / Line 855: @@
 * Write a short program (in, e.g. C or Fortran) which highlights the benefits of using compiler flags, such as gcc's -O3, -ffast-math, etc.  (Hint a for loop containing some arithmetic will do.)
 * Write a short program in the language of your choice which accesses makes a file access during every iteration of a loop.  Time it.  Now re-write your program to read or write the information from/to memory instead and time it again.
 * Write a MATLAB, Python or R script which demonstrates the benefits of vectorisation in one of those languages.
 * Write a simple C or Fortran program, using OpenMP, which demonstrates the benefits of work-sharing across a loop.

← Older revision		Revision as of 10:36, 20 September 2013
Line 557:		Line 557:

	To run some equivalent C code examples, where you'll see that an optimising C compiler will spot this mistake and rearrange your loops for you!		To run some equivalent C code examples, where you'll see that an optimising C compiler will spot this mistake and rearrange your loops for you!
		+
		+	===Be parsimonious in your data structures===
		+
		+	For example:
		+
		+	<source lang="c">
		+	#define N 1024*1024
		+
		+	struct datum
		+	{
		+	int a;
		+	int b;
		+	int c; /* Note: unused in loop */
		+	int d; /* Note: unused in loop */
		+	};
		+
		+	struct datum mydata[N];
		+
		+	for (i=0;i<N;i++)
		+	{
		+	mydata[i].a = mydata[i].b;
		+	}
		+	</source>
		+
		+	will take longer to run than:
		+
		+	<source lang="c">
		+	#define N 1024*1024
		+
		+	struct datum
		+	{
		+	int a;
		+	int b;
		+	};
		+
		+	struct datum mydata[N];
		+
		+	for (i=0;i<N;i++)
		+	{
		+	mydata[i].a = mydata[i].b;
		+	}
		+	</source>
		+
		+	simply because the second program refreshes cache fewer times.

	==Avoid Expensive Operations==		==Avoid Expensive Operations==

@@ Line 543: / Line 543: @@
 Dude!  '''loopingA.exe''' takes more than twice the time of '''loopingB.exe'''.  What's the reason?
-Well, Fortran stores it's 2-dimensional arrays in '''column-major order'''.  Our 2-dimension array is actually stored in the computer memory as a 1-dimension array, where the cells in a given column are next to each other.  For example, the array:
+Well, Fortran stores it's 2-dimensional arrays in '''column-major order'''.  Our 2-dimension array is actually stored in the computer memory as a 1-dimension array, where the cells in a given column are next to each other.  For example:
-:<math> \begin{bmatrix}
+[[Image:Column-major-order.jpg|400px|thumbnail|centre|Stepping through the cells of a 2-d array in Fortran.]]
-<pre>
+That means is that our outer loop should be over the columns, and our inner loop over the rows.  Otherwise we would end up hopping all around the memory, potentially thrashing the cache if the array is large, and using unnecessary time, which explains why loopingA takes longer.
 The opposite situation is true for the C programming language, which stores its 2-dimensional arrays in '''row-major order'''.  You can type:

@@ Line 808: / Line 808: @@
 * http://chryswoods.com/beginning_openmp, or
 * https://source.ggy.bris.ac.uk/wiki/Parallel
 =Suggested Exercises=