Description
Z-order matrices, sometimes called Morton-order matrices, is a new matrix storage concept according to which a 2-dimensional matrix is not stored in memory row-by-row (as in C) or column-by-column (as in Fortran), but block-by-block with each block being either a scalar or 4 sub-blocks whose indices are in the order resembling a "Z". If applied to shared arrays, this concept provides 2-dimensional recursive block data distribution in UPC. The benefits are avoiding cache misses due to improved memory locality and facilitating block-recursive algorithms. For experimental purposes, we provide a small library for converting cartesian matrix indices (ordinary indices) to Z-order indices. By including this library, UPC programmers can transparently convert a 2-dimensional array into a Z-ordered array. This library is built with macros and a simple routine which can be inlined by a compiler. Thus the cost of index convertion is minimal.
References
- Phil Merkey, "Z-ordering and UPC", A TechNote. June, 2003 ( pdf )
Sourcecode
Instructions
- Put the sourcecode in the directory with your UPC program.
- Include z_order.h at the beginning of you program.
- The macro z_order(A,i,j) gives the address of element A[i][j] when array A is stored in Z-order.
- The array must be square. And its size on each dimension must be a power of 4.
- The loop indices used for traversing the array must be of 32-bit integer type and cannot exceed 65535.
Example
/* Matrix multiplication */
#include <upc.h>
#include "z_order.h"
#define N 256
#define BLK (N*N/THREADS)
#define elem_t double
#define MTYPE shared[BLK] elem_t
/* Shared arrays */
MTYPE a[N][N], b[N][N], c[N][N];
int main()
{
int i, j, k;
for (i = 0; i < N; i++)
{
forall (j = 0; j < N; j++; z_index((MTYPE *)c,i,j))
{
for (k = 0; k < N; k++)
*(z_index((MTYPE *)c,i,j)) +=
(*(z_index((MTYPE *)a,i,k))) * (*(z_index((MTYPE *)b,k,j)));
}
}
upc_barrier;
if (MYTHREAD == 0)
{
for (i = 0; i < N; i++)
{
for (j = 0; j < N; j++)
printf ("c[%d][%d]=%d\n", i, j, *(z_index((MTYPE *)c,i,j)));
}
}
return 0;
}
Last modified 12/8/4
{ Insert a counter here }