HW3 Sp08 Assigned 4/10/08, Due 4/17/08 and 4/24/08
HW3 - 4/10/08, Due 4/17/08 and 4/24/08

HW2 - 2/19/08, Due 3/4/08 and 4/10/08

HW1 - 1/31/08, Due 2/7/08

In 2008 send email to me at lw@ic.sunysb.edu
{What follows is from 2003)




Assignments CSE613 Fall 2003 Sun 23Nov03 v6

Please email questions to ldw@cs.sunysb.edu.

Assignments Week  12 Read Chap 4 of text. Read the documentation on perfex performance tools on SGI challenge computer.
HW 6, due Wed 3 Dec Do all parts of ex. 3.8 and 3.9. Start early.

Assignments Week  9 Read Chap 3 of text. Read the documentation on parallel coding pragmas for SGI challenge native C compiler.
HW 5, due Mon 10 Nov Make any minor corrections to make file to get your splash2 code running sequentially on challenge. Insert compile time conditionals to count all memory reads and writes in your code running sequentially. Compare your memory access counts to those in splash2 report. Explain any major differences. Compare the execution times with and without the counters.

The initialized red/black version of the sequential equation solver in Figure 2.7 has been revised, as seen in green below, in four ways:

A) Iterations cannot stop until 2*n steps are complete, enough time for values in diagonally opposite corners to influence each other (well converged solutions should run much longer than this minimum time).

B) The tolerance value has been made absolute, not relative to 1/(n*value extremes).

C) The maximum value change (maxdiff) in each iteration is calculated in addition to diff, the average value change used to stop the iterations.

D) The (1 to n) edge values AND their slopes have been used to set the ghost border values added to avoid treating iterative updates of the edge values as special cases.

Note: Consider three points with x, x+d, and x+2d. If the slope (e/d) is the same for all, then the points are (x,y), (x+d, y+e), and (x+2d,y+2e). Their coordinates individually satisfy c2-c1 = c1-c0 and c2 = 2*c1-c0. Hence the changes to the code to fill in the ghost border values.

Convert this pseudocode to native C for the challenge SGI computer (it is red/black so later parallel versions of this code can be expected to give the same exact answers). The matrix is initialized to the same minimal value at all elements except the lower right corner, which has a the maximum value. Both the upper left and lower right corners are forced before each iteration (sweep over the matrix) to the min and max values, respectively. Get your C version of this equation solver to compile and run sequentially (on challenge).

Use the following parameters for runs of this code: minval=0; maxval=419; n = 14, 42, 140, 420, 1400; tol = 0.001 for all but 140 and 420. For 140 and 420, tol = 0.1, 0.03, 0.01, 0.003, 0.001, 0.0003, 0.0001, 0.00003, and 0.00001, if they allow termination. For each combination of parameter values, print the n and tol parameters, the number of iterations before termination, the final values of diff and maxdiff, and the indices from A[0,0] to A[n+1,n+1] plus the final values of the first 4, the middle 4 and the last 4 elements on the 4 borders and the 2 diagonals - a total of 64 distinct A[i,j]=abc.de pairs. Please arrange the pairs in a print matrix corresponding to their A[I,j] locations so they can easily be understood. Include a table summarizing at least your iteration count, diff and maxdiff values versus other parameters.

 

Red Black Sequential Ocean Code with Absolute Tolerance

 
1. int n; /* size of matrix: (n+2-by-n+2) elements*/
2a. float **A, tol, diff = 0.0, maxdiff = -1.0;; /*A is global (shared) array representing the grid*/
2b. /*diff,maxdiff are global (shared) average and maximum value changes in current sweep*/
 
3. main()
4. begin
5. read(n); read(tol); /*read input matrix size and tolerance value to end this run */
5a. read(minval); read(maxval); /*read fixed elt values (0,419) for this initialization */
6. A ß malloc(a two-dimensional array of size n+2 by n+2 doubles);
7. initialize(A); /*initialize A in an unspecified way*/
8. Solve (A); /* call the routine to solve equation*/
9. end main
 
10. procedure Solve(A) /* solve the equation system*/
11. float **A; /*A is entire n+2-by-n+2 shared array */
12. begin
13. int i, j; /*local variables*/
13a. int iter = 0; /*number of iterations*/
14. float temp;
14a. for i ß 1 to n do /*initalize elements in each of my rows*/
14b. for j ß 1 to n do /* for all non-border elts of my rows, */
14c. A[i,j] = minval; /* initial value = min */
14d. endfor /* set border elts and clamp special elts, */
14e. endfor /* before start of each time step below */
 
15. while (!done) do /*outer loop over all elements*/
16. diff = 0.0; maxdiff = -1.0
16a. A[1,1] = minval; /* clamp upper left corner = min */
16b. A[n,n] = maxval; /* clamp lower right corner = max */

16c. A[0,0] = 2* A[1,1] - A[2,2]; /* extend diagonal values and slopes */

16d. A[0,n+1] = 2* A[1,n] - A[2,n-1]; /* to corner elts unused by solver */

16e. A[n+1,0] = 2* A[n,1] - A[n-1,2]; /* so final display is complete. */

16f. A[n+1,n+1] = 2* A[n,n] - A[n-1,n-1];
16g. for j ß 1 to n do /* each top or bottom mid-border elt, */
16h. A[0,j] = 2*A[1,j]- A[2,j]; /* set to: 2*nearest edge elt */
16i. A[n+1,j] = 2*A[n,j] - A[n-1,j]; /* – next inner elt */
16j. endfor
 
17. for i ß 1 to n do /*for each BLACK nonborder elt of my rows*/
17a. A[i,0] = 2*A[i,1]- A[i,2]; /* each side border elt set to: */

17b. A[i,n+1] = 2*A[i,n] - A[i,n-1]; /* 2*nearest edge elt – next inner elt*/

18. for j ß 2 - i%2 to n by 2 do /*for all black elts */
19. temp = A[i,j];
20. A[i,j] = 0.2 * (A[i,j] + A[i,j-1] + A[i-1,j] +
21. A[i,j+1] + A[i+1,j]);
22. diff += abs(A[i,j] - temp);

22a. if ((abs(A[i,j] - temp) > maxdiff) maxdiff = abs(A[i,j] - temp);
23. endfor
23a. endfor
23b. for i ß 1 to n do /*for each RED nonborder elt of my rows*/
23c. for j ß 1 + i%2 to n by 2 do /*for all red elts */
23d. temp = A[i,j];
23e. A[i,j] = 0.2 * (A[i,j] + A[i,j-1] + A[i-1,j] +
23f. A[i,j+1] + A[i+1,j]);
23g. diff += abs(A[i,j] - temp);
22h. if ((abs(A[i,j] - temp) > maxdiff) maxdiff = abs(A[i,j] - temp);
23i. endfor
24. endfor

24a. iter++;
25. if (diff/(n*n) < tol) then if iter > 2*n then if done = 1;
26. endwhile
27. end procedure

 

Copy the local file: SolverAbsSeqRedBlk.rtf to get a formatted copy of this code.

 

Assignments Week  7  Read Chap 3 of text.
HW 4, due Wed 22 Oct Convert the pseudocode of the following initialized red/black version of the sequential equation solver in Figure 2.7 to C for the native C compiler on challenge SGI computer (it is red/black so later parallel versions of this code can be expected to give the same exact answers). The matrix is initialized to the same minimal value at all elements except the lower right corner, which has a the maximum value. Both the upper left and lower right corners are forced before each iteration (sweep over the matrix) to the min and max values, respectively. Get your C version of this equation solver to compile and run sequentially (on challenge).

Use the following parameters for runs of this code: minval=0; maxval=419; n = 14, 42, 140, 420, 1400; tolfract = 0.05 for all but 420. For 420, tolfract = 0.2, 0.1, 0.05, 0.025, 0.01, 0.001, and 0.0001, if it allows termination. For each combination of parameter values, print the n and tolfract parameters, the number of iterations before termination and the indices from A[0,0] to A[n+1,n+1] plus the final values of the first 4, the middle 4 and the last 4 elements on the 4 borders and the 2 diagonals - a total of 64 distinct A[i,j]=abc.de pairs. Please arrange the pairs in a print matrix corresponding to their A[I,j] locations so they can easily be understood.

 

Red Black Sequential Ocean Code

 
1. int n; /* size of matrix: (n+2-by-n+2) elements*/
2a. float **A, tol, tolfract, diff = 0; /*A is global (shared) array representing the grid*/
/*diff is global (shared) maximum difference in current sweep*/
 
3. main()
4. begin
5. read(n); read(tolfract); /*read input matrix size and tolerance to end as fraction of expected grid delta */
5a. read(minval); read(maxval); /*read fixed elt values (0,419) for this initialization */
5b. tol = tolfract*(maxval- minval+1)/n; /* tolerance value to end this run */
6. A ß malloc(a two-dimensional array of size n+2 by n+2 doubles);
7. initialize(A); /*initialize A in an unspecified way*/
8. Solve (A); /* call the routine to solve equation*/
9. end main
 
10. procedure Solve(A) /* solve the equation system*/
11. float **A; /*A is entire n+2-by-n+2 shared array */
12. begin
13. int i, j; /*local variables*/
14. float temp;
14a. for i ß 1 to n do /*initalize elements in each of my rows*/
14b. for j ß 1 to n do /* for all non-border elts of my rows, */
14c. A[i,j] = minval; /* initial value = min */
14d. endfor /* set border elts and clamp special elts, */
14e. endfor /* before start of each time step below */
 
15. while (!done) do /*outer loop over all elements*/
16. diff = 0;
16a. A[0,0] = A[1,0] = A[1,1] = minval; /* clamp upper left corner = min */
16b. A[n+1,n+1] = A[n,n+1] = A[n,n] = maxval; /* clamp lower right corner = max */
16c. for j ß 1 to n do /* for each top or bottom mid-border elt, */
16d. A[0,j] = A[1,j]; /* copy first nonborder row elt */
16e. A[n+1,j] = A[n,j]; /* copy last nonborder row elt */
16f. endfor
 
17. for i ß 1 to n do /*for each BLACK/RED nonborder elt of my rows*/
17a. A[i,0] = A[i,1]; /* inite side border elts equal nearest nonborder elts*/
17b. A[i,n+1] = A[i,n];
18. for j ß 2 - i%2 to n by 2 do /*for all black elts */
19. temp = A[i,j];
20. A[i,j] = 0.2 * (A[i,j] + A[i,j-1] + A[i-1,j] +
21. A[i,j+1] + A[i+1,j]);
22. diff += abs(A[i,j] - temp);
23. endfor
23a. for j ß 1 + i%2 to n by 2 do /*for all red elts */
23b. temp = A[i,j];
23c. A[i,j] = 0.2 * (A[i,j] + A[i,j-1] + A[i-1,j] +
23d. A[i,j+1] + A[i+1,j]);
23e. diff += abs(A[i,j] - temp);
23f. endfor
24. endfor
25. if (diff/(n*n) < tol) then done = 1;
26. endwhile
27. end procedure

 

Copy the local file: SolveOceanSeqRedBlk.rtf to get a formatted copy of this code.

Assignments Week  5  Read Chap 2 of text.
HW 3, due Mon 13 Oct Do ex. 2.6 and add back substitution final part of Gaussian Elimination to pseudocode in Fig 2.18 on page 119. Convert the pseudocode to C for the native C compiler on challenge SGI computer. Get your C version of Gaussian elimination to compile and run sequentially (on challenge). Use your code to find the roots of a equation family that I have supplied as a numeric matrix, teddyFace96x95HW3eqns.txt in this website directory (and on challenge in /home/u26/cse613).

Here is an example of Gaussian elimination:

a0 a1 a2 a3 a4 a5 a6 a7 a8 a9

b0 b1 b2 b3 b4 b5 b6 b7 b8 b9

c0 c1 c2 c3 c4 c5 c6 c7 c8 c9

d0 d1 d2 d3 d4 d5 d6 d7 d8 d9

e0 e1 e2 e3 e4 e5 e6 e7 e8 e9

f0 f1 f2 f3 f4 f5 f6 f7 f8 f9

g0 g1 g2 g3 g4 g5 g6 g7 g8 g9

h0 h1 h2 h3 h4 h5 h6 h7 h8 h9

i0 i1 i2 i3 i4 i5 i6 i7 i8 i9

a0*x0 + ... + a8*x8 = a9

 

Triangular Fig 2.18 makes this

1 k1 k2 k3 k4 k5 k6 k7 k8 k9

0 1 m2 m3 m4 m5 m6 m7 m8 m9

0 0 1 n3 n4 n5 n6 n7 n8 n9

…

0 0 0 0 0 0 0 1 r8 r9

0 0 0 0 0 0 0 0 1 s9

 

Back substitution =>

x8 = s9 x7 = r9 — r8*x8

Solution to family of equations

1 0 0 0 0 0 0 0 0 Qx0

0 1 0 0 0 0 0 0 0 Qx1

…

0 0 0 0 0 0 0 0 1 Qx8

Assignments Week  3  Read Chaps 1 and 2 of text.
HW 2, due Wed 24 Sep Do ex. 1.7, 1.12, and 1.14

Assignments Week 2 Read Chapter 1 (2 is next) of text
HW 1 due Wed 17 Sep Do exercise 1.4

Assignments Half-Week 1 Read Appendix A and Chapter 1 (2 is next) of text
Homework 0: Send email to ldw @cs.sunysb.edu with the following info:
Your name, student number, and dept.
Names of all courses that you took in fall 2002 & your grades in each.
Are you registered for this course? UG or Grad status (e.g., G1, G4)?
Name & text title for earlier computer organization/architecture course(s);
School where you took the course(s), when, and your grade (of max).
Your other computer architecture experience, if any - such as a job.
Anything else I should know about you.