WarpEngine Test Programs

The following is a listing of the programs the Richard Littin wrote for the WarpEngine, version 2 of the instruction set.

Matrix multiplication	asm	C
Transitive closure	asm	C
Gauss-Jordan elimination	asm	C
Heapsort	asm	C
Quicksort (version 1)	asm	C
Quicksort (version 2)	asm	C
Naive binary tree insertion	asm	C
AVL binary tree insertion	asm	C
Recursive Fibonacci number generation	asm	C
Recursive Fibonacci number generation (data flow)	asm	C

C Code

Matrix multiplication

float A[N][N], B[N][N], C[N][N];

void Mult(void) {
    int i,j,k;
    float t;

    for (i=0;i<N;i++)
        for (j=0;j<N;j++) {
            t = 0;
            for (k=0;k<N;k++)
                t += A[i][k] * B[k][j];
            C[i][j] = t;
        }
}

Transitive closure

int a[NUM_VERT+1][NUM_VERT][NUM_VERT];

void Trans() {
    int i,j,k;
    for (k=0;k<NUM_VERT;k++)
        for (i=0;i<NUM_VERT;i++)
            for (j=0;j<NUM_VERT;j++)
                a[k+1][i][j] = (a[k][i][j] || (a[k][i][k] && a[k][k][j]));
}

Gauss-Jordan elimination

float A[N*N];

float ABS(i) {
  if (i > 0)
    return i;
  return -i;
}

void gaussj(float *a, int n) {
  float big, dum, pivinv;
  long int i, icol, irow, j, k, l, ll;
  long int indxc[N], indxr[N], ipiv[N];

  for (j=0;j<n;j++) {
    indxc[j] = 0;
    indxr[j] = 0;
    ipiv[j] = 0;
  }
  for (i=0;i<n;i++) {
    big = 0.0;
    for (j=0;j<n;j++)
      if (ipiv[j] != 1)
	for (k=0;k<n;k++)
	  if (ipiv[k] == 0) {
	    if (ABS(a[j*N+k]) >= big) {
	      big = ABS(a[j*N+k]);
	      irow = j;
	      icol = k;
	    }
	  }
	  else if (ipiv[k] > 1) {
	    printf("pause 1 in GAUSSJ - singular matrix\n");
	    getc(stdin);
	  }
    ipiv[icol] = ipiv[icol] + 1;
    if (irow != icol) {
      for (l=0;l<n;l++) {
	dum = a[irow*N+l];
	a[irow*N+l] = a[icol*N+l];
	a[icol*N+l] = dum;
      }
    }
    indxr[i] = irow;
    indxc[i] = icol;
    if (a[icol*N+icol] == 0.0) {
      printf("pause 2 in GAUSSJ - singular matrix\n");
      getc(stdin);
    }
    pivinv = 1.0 / a[icol*N+icol];
    a[icol*N+icol] = 1.0;
    for (l=0;l<n;l++) {
      a[icol*N+l] = a[icol*N+l]*pivinv;
    }
    for (ll=0;ll<n;ll++)
      if (ll != icol) {
	dum = a[ll*N+icol];
	a[ll*N+icol] = 0.0;
	for (l=0;l<n;l++) {
	  a[ll*N+l] = a[ll*N+l] - a[icol*N+l] * dum;
	}
      }
  }
  for (l=n-1;l>=0;l--)
    if (indxr[l] != indxc[l])
      for (k=0;k<n;k++) {
	dum = a[k*N+indxr[l]];
	a[k*N+indxr[l]] = a[k*N+indxc[l]];
	a[k*N+indxc[l]] = dum;
      }
}

Heapsort

int table[TABLE_SIZE];

void Swap(int *a, int *b) {
    int temp;
    temp = *a; *a = *b; *b = temp;
}

void Heapify(int i, int j) {
    if ((RC(j) >= i) && (table[RC(j)] <= table[LC(j)]) && (table[RC(j)] < table[j])) {
        Swap(&(table[j]),&(table[RC(j)]));
        Heapify(i, RC(j));
    }
    else if ((LC(j) >= i) && (table[LC(j)] < table[j])) {
        Swap(&(table[j]),&(table[LC(j)]));
        Heapify(i, LC(j));	
    }
}

void InitialiseHeap() {
    int i;
    for (i=0;i<TABLE_SIZE;i++) {
        Heapify(0,i);
    }
}

void HeapSort() {
    int i;
    InitialiseHeap();
    for (i=0;i<TABLE_SIZE-1;i++) {
        Swap(&(table[i]),&(table[TABLE_SIZE-1]));
        Heapify(i+1,TABLE_SIZE-1);
    }
}

Quicksort (version 1)

int v[ARRAY_SIZE];

void QSort(int left,int right) {
    int i,piv,temp,cmp;
    
    if (left >= right)
        return;
    cmp = v[left];
    piv = left;
    for (i=left+1;i<=right;i++)
        if (v[i] < cmp) {
            piv++;
            temp = v[piv]; v[piv] = v[i]; v[i] = temp;      
        }
    temp = v[piv]; v[piv] = v[left]; v[left] = temp;
    QSort(left,piv-1);
    QSort(piv+1,right);
}

Quicksort (version 2)

int v[ARRAY_SIZE];

void QSort(int left,int right)
{
    int temp = v[left];
    int i = left, j = right;

    if (j > i) {
        while (j>i) {
            while ((j >= i) && (temp < v[j]))
                j--;
            if (j<=i)
                v[i] = temp;
            else {
                v[i] = v[j];
                i++;
                while ((i <= j) && (v[i] < temp))
                    i++;
                if (j>i) {
                    v[j] = v[i];
                    j--;
                }
                if (j<=i)
                    v[j] = temp;
            }
        }
        QSort(left,j-1);
        QSort(j+1,right);
    }
}

Naive binary tree insertion

typedef struct node node;

struct node {
    int key;
    node *left, *right;
};

node *New(int key) {
    node *new_node = (node *)malloc(sizeof(node));

    new_node->key = key;
    new_node->left = NULL;
    new_node->right = NULL;
    return new_node;
}

void Insert(node **root, int key) {
    if ((*root) == NULL)
        *root = New(key);
    else if (key < (*root)->key)
        Insert(&((*root)->left),key);
    else if (key > (*root)->key)
        Insert(&((*root)->right),key);
}

AVL binary tree insertion

struct node {
    int key;
    int bal;
    node *left, *right;
};

node *New(int key) {
  node *n = (node *)malloc(sizeof(node));

  n->key = key;
  n->bal = 0;
  n->left = NULL;
  n->right = NULL;
  return n;
}

void ShiftNode(int *d,node **c,int key,node **p) {
  if (key == (*p)->key) {
    *d = 0;
    *c = *p;
  }
  else if (key < (*p)->key) {
    *d = -1;
    *c = (*p)->left;
  }
  else {
    *d = 1;
    *c = (*p)->right;
  }
}

void Rotate(node **p, int d,node **par, int cd,node **root) {
  node *P = *p;

  if (d == -1) {
    *p = (*p)->right;
    P->right = (*p)->left;
    (*p)->left = P;
  }
  else {
    *p = (*p)->left;
    P->left = (*p)->right;
    (*p)->right = P;
  }

  if (cd == -1)
    (*par)->left = *p;
  else if (cd == 1)
    (*par)->right = *p;
  else 
    *root = *p;
}

void AVLInsert(node **root,int key) {
  int d1, d2, d3, critnodefound = 0, critdir, dir = 0;
  node *n, *a, *b, *c, *cp, *p, *r;

  p = n = *root;

  while ((n != NULL) && (n->key != key)) {
    if (n->bal != 0) {
      c = n;
      cp = p;
      critnodefound = 1;
      critdir = dir;
    }
    if (key < n->key) {
      p = n;
      n = n->left;
      dir = -1;
    }
    else {
      p = n;
      n = n->right;
      dir = 1;
    }
  }

  if (n == NULL) {
    if (p == NULL)
      *root = New(key);
    else if (dir == -1)
      p->left = New(key);
    else
      p->right = New(key);

    if (!critnodefound)
      r = *root;
    else {
      ShiftNode(&d1,&a,key,&c);
      if (c->bal != d1) {
	c->bal = 0;
	r = a;
      }
      else {
	ShiftNode(&d2,&b,key,&a);
	if (d2 == d1) {
	  c->bal = 0;
	  r = b;
	  Rotate(&c,-d1,&cp,critdir,root);
	}
	else {
	  ShiftNode(&d3,&r,key,&b);
	  if (d3 == d2) {
	    c->bal = 0;
	    a->bal = d1;
	  }
	  else if (d3 == -d2)
	    c->bal = d2;
	  else
	    c->bal = 0;
	  Rotate(&a,-d2,&c,d1,root);
	  Rotate(&c,-d1,&cp,critdir,root);
	}
      }
    }
    while (r->key != key) {
      ShiftNode(&(r->bal),&r,key,&r);
    }
  }
}

Recursive Fibonacci number generation

int Fib(int n) {
    if (n == 0)
        return 0;
    else if (n == 1)
        return 1;
    else
        return Fib(n-1) + Fib(n-2);
}