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

Sourcecode

Instructions

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 }