HA5 for cmpe110

matmul.c

#include <string.h>
#include <stdio.h>
#include <unistd.h>
#include <time.h>
#include <stdlib.h>

#define SIZE 1024

 volatile __uint64_t A[SIZE][SIZE];
 volatile __uint64_t B[SIZE][SIZE];
 volatile __uint64_t C[SIZE][SIZE];
 volatile __uint64_t D[SIZE][SIZE];

 // X is the transpose of B
 volatile __uint64_t X[SIZE][SIZE];
 volatile __uint64_t Y[SIZE][SIZE];

void transpose(volatile __uint64_t T[][SIZE])
{
	int r, c;
	int offset = 0;
	volatile __uint64_t temp = 0;

	for(r = 0; r < SIZE; r++) {
		for (c = 1 + offset; c < SIZE; c++) {
			temp = T[r][c];
			T[r][c] = T[c][r];
			T[c][r] = temp; 
		}
		offset += 1;
	}
}

void init(volatile __uint64_t A[][SIZE], volatile __uint64_t B[][SIZE], volatile __uint64_t X[][SIZE])
{
	int r, c;
	 volatile __uint64_t val = 0;

	for (c = 0; c < SIZE; c++) {
		for (r = 0; r < SIZE; r++) {
			val = rand();
			A[r][c] = rand();
			X[c][r] = val;
			B[r][c] = val;
		}
	}
}

int verify(volatile __uint64_t C[][SIZE], volatile __uint64_t D[][SIZE])
{
	int r, c;

	for (c = 0; c < SIZE; c++) {
		for (r = 0; r < SIZE; r++) {
			if (C[r][c] != D [r][c]) {
				printf("error!\n");
				goto out;
			}
			
		}
	}
	return 0;

out:
	return -1;
}

void matmul(volatile __uint64_t A[][SIZE], volatile __uint64_t B[][SIZE])
{
	int rowA, colB, idx;

	for (rowA = 0; rowA < SIZE; rowA++) {
		for (colB = 0; colB < SIZE; colB++) {
			for (idx = 0; idx < SIZE; idx++) {
				C[rowA][colB] += A[rowA][idx] * B[idx][colB];
			}
		}
	}
}

void tmatmul(volatile __uint64_t A[][SIZE], volatile __uint64_t X[][SIZE])
{
	int rowA, rowB, idx;

	for (rowA = 0; rowA < SIZE; rowA++) {
		for (rowB = 0; rowB < SIZE; rowB++) {
			for (idx = 0; idx < SIZE; idx++) {
				D[rowA][rowB] += A[rowA][idx] * X[rowB][idx];
			}
		}	
	}
}

void tilingmatmul(volatile __uint64_t A[][SIZE], volatile __uint64_t X[][SIZE], int blocksize)
{
	int rowA, colB, idx;

	int aLeftBound = 0;
	int aRightBound = blocksize;

	int bLeftBound = 0;
	int bRightBound = blocksize;

	int idxLeftBound = 0;
	int idxRightBound = blocksize;

	while (aRightBound <= SIZE) {

		while (bRightBound <= SIZE) {

			while (idxRightBound <= SIZE) {

				// Computing the Index in the block size
				for (rowA = aLeftBound; rowA < aRightBound; rowA++) {
					for (colB = bLeftBound; colB < bRightBound; colB++) {
						for (idx = idxLeftBound; idx < idxRightBound; idx++) {
							Y[rowA][colB] += A[rowA][idx] * X[idx][colB];
						}
					}
				}

				// moving the block window right, by the block size
				idxLeftBound += blocksize;
				idxRightBound += blocksize;
			}

			// reset index bounds
			idxLeftBound = 0;
			idxRightBound = blocksize;

			// increase B Matrix bounds
			bLeftBound += blocksize;
			bRightBound += blocksize;
		}

		// reset index bounds
		idxLeftBound = 0;
		idxRightBound = blocksize;

		// reset B Matrix bounds
		bLeftBound = 0;
		bRightBound = blocksize;

		// increase A Matrix bounds
		aLeftBound += blocksize;
		aRightBound += blocksize;
	}
}

int main(int argc, char **argv)
{
	clock_t t;
	double time_taken;

	init(A, B, X);
	transpose(X);

	if (!verify(B, X)) {
		printf("%s\n", "B and X are the same! Transpose Function Works!");
	}

	transpose(X);

	memset(( volatile __uint64_t**)C, 0, sizeof( volatile __uint64_t) * SIZE * SIZE);
	memset(( volatile __uint64_t**)D, 0, sizeof( volatile __uint64_t) * SIZE * SIZE);
	memset(( volatile __uint64_t**)Y, 0, sizeof( volatile __uint64_t) * SIZE * SIZE);

	t = clock();
	// saves results on to Y Matrix
	matmul(A, B);
	t = clock() - t;

	time_taken = ((double)t)/CLOCKS_PER_SEC; // in seconds	
	printf("matmul took %f seconds to execute.\n", time_taken);

	t = clock();
	// saves results on to Y Matrix
	tmatmul(A, X);
	t = clock() - t;

	time_taken = ((double)t)/CLOCKS_PER_SEC; // in seconds	
	printf("transpose matmul took %f seconds to execute.\n", time_taken);

	t = clock();
	// saves results on to Y Matrix
	tilingmatmul(A, B, 4);
	t = clock() - t;

	time_taken = ((double)t)/CLOCKS_PER_SEC; // in seconds	
	printf("tilingmatmul (tiling) with %d blocksize took %f seconds to execute.\n", 4, time_taken);

	if (!verify(C, D)) {
		printf("%s\n", "C and D are the same!");
	} else {
		printf("They're not the same\n");
	}

	if (!verify(C, Y)) {
		printf("%s\n", "C and Y are the same!");
	} else {
		printf("They're not the same\n");
	}
}