CS 575 Supercomputing
Vectors and Loops
(Complement Ch 8 - Loop Optimization)
22 October 03

Dr. Kris Stewart (stewart@rohan.sdsu.edu)
San Diego State University

Why so much emphasis on loops?

• Learning to recognize the programmer's coding impact on the independence needed to automatically treat each iteration of a loop in the same manner to produce vectorization - the first step toward parallel operations on distributed processors. Tasks that block vectorization of a loop:
  • Subroutine and function calls (if they aren't "inlined")
  • I/O statements (system call will halt uniform processing)
  • Arithmetic IF, computed GOTO, assignged GOTO
  • Partial word data (e.g. character data)
  • Unstructured branches
  • Data Dependencies (we'll focus here)
  • Ambiguous pointers (may lead to dependency)
• Loops can be recognized by the compiler and mapped directly onto vector hardware which we will be using later in the semester from the San Diego Supercomputer Center (SDSC).

Key Concepts:

Vector-vector add:

Y_n+1 = Y_N + h * F(x_N,Y_N)
SAXPY operation is fundamental computational in solving Ordinary Differential Equations (Y' = A Y) as well as Linear Equations (A x = b) .

Matrix-vector multiply (as a SAXPY):

b = A x = x₁ A_*1 + x₂ A_*2 + x₃ A_*3 + ... + x_n A_*N
where A_*2 refers to the Column 2 of the matrix A.

Matrix-matrix multiply: C = A B

Guiding principal is that once you have moved data from memory to the cache or the registers of the CPU, your program should be organized to accomplish as many of the operations involving the data as possible.

Fig. A-3 Vector processor registers

© O'Reilly Publishers (Used with permission)

Fig. A-4 A vector processor at work

© O'Reilly Publishers (Used with permission)

CS 575 Ch 8 Loop Opt