Mon, 27 Apr 2009, 02:00

A student writes:

	Dr. Patt,

	I need clarification on the vector stride register.

	Is stride used in order to define 2 dimensional arrays in memory for 
	matrix operations - or is it used to define the size of the data being 
	operated on?

I would not have worded it that way, since in your examples it actually
relates somewhat to both.  Let me try.

The stride register contains the amount that must be added to the address of
a LD instruction to form the address of the next load.  That is it pure and
simple.  Let me leave your two choices above alone for the moment, and look
at your examples.

	My study group is having a disconnect with the definition of stride.  
	Say we are starting with a vector located at x3000. The LC3b is byte
	addressable - therefore if you define the stride = 4, does that mean 
	each element in the vector is 4 bytes?

No, I would say the stride is 1.  But the contents of the stride register in 
this case is 4 because you need to add 4 to the address to get the next data
element.  If we were looking at the Cray machines as was the case in class, 
since addressability is 64 bits, the next data element is stored at the next 
location and so stride is one and contents of the stride register is 1.

	Or, is the stride register used specifically for memory accesses.

Yes, the stride register is used specifically for memory accesses, but if 
addressibility is less than the entire data element, then the contents of 
the vector stride register has to reflect both the size of the data element 
and where the next element is stored.

	Suppose you have an array as follows stored in column major format:

	1  2  3  4  5
	6  7  8  9  10
	11 12 13 14 15

Actually, this array is stored in row major format.  Row major means store 
the first row, then the second row, ...

	[piece of student question deleted since I think it will confuse,
	rather than illuminate.]

If you had the above array stored in column major format, and each element 
occupied one location, the elements would be stored in locations:

1  4  7 10 13
2  5  8 11 14
3  6  9 12 15

If you wanted to load row 1, you would access 1,4,7,10,13.  To do this,
you would want to load the stride register with 3 before starting.

If you wanted to access column 3, you would access 7,8,9.  You would first
load the stride register with 1.

Suppose you had the LC-3b augmented with 32-bit floating point and you had
an array of 32-bit floating point numbers.  Then the starting address of 
each element of the above array would be:

1 13 25 37 49
5 17 29 41 53
9 21 33 45 57

Now if you want to load row 1, you would access 1, 13, 25, 37, and 49.
Before starting you would load stride register with 3 (stride) x 4 (data size).

If you wanted to access column 3, you would access 25, 29, 33.  You would
first load the stride register with 1 (stride) x 4 (data size).

	Is it standard that the vectors are always stored in column major on 
	the Cray-1 machine?

Vectors are data, so are stored depending on who collected the data.  Programs
operating on data better know whether the data is stored in column major or
row major form.  It is not a function of the ISA.

	For row major, how would the stride register be effected?  i.e.

	1  6  11
	2  7  12
	3  8  13
	4  9  14
	5  10 15

This is column major.

	If the above was the case, wouldn't the length and stride 
	registers be reversed? Stride = 3, Length = 5?  

I would say the length of each vector and the stride are reversed.

	But then wouldn't this still be column major?

No, row major vs column major is all about whether the rows are
stored consecutively or the columns are stored consecutively.

	Just needed some clarification.


	<<name withheld to protect the student wanting to understand stride>>

Hope this helps.
Yale Patt