HW0: Exchange

SERIAL CODE

#include <xmtc.h>
int main(){
int x;
for(x=0; x<n; x++){
int e= A[x];
A[x] = B[x];
B[x] = e;
}
}

PARALLEL CODE (1)
#include <xmtc.h>
int main(){
int x[n];
spawn(0,n-1){
x[$] = A[$];
A[$] = B[$];
B[$] = x[$];
}
}

PARALLEL CODE (2)
#include <xmtc.h>
int main(){
int y[n];
int x[n];
spawn(0,2*n-1){
if($<n)
        x[$] = A[$];
else
        y[$%n] = B[$%n];
}
spawn(0, 2*n-1){
if($<n)
        A[$] = y[$];
else
        B[$%n] = x[$%n];
}
}//end main

TABLE OF RUN-TIMES IN CLOCK CYCLES
-----------------------------------------------------------------
Input size                      |n=16   |n=3200 |n=16000|n=64000|
--------------------------------|-------|-------|-------|-------|
Serial Clock Cycles             |8082   |60340  |464294 |1825026|
--------------------------------|-------|-------|-------|-------|
Parallel1 Clock Cycles          |9207   |18702  |58728  |206081 |
--------------------------------|-------|-------|-------|-------|
Parallel2 Clock Cycles          |10883  |21757  |81044  |287921 |
-----------------------------------------------------------------



HW1: Matrix Multiplication

ALGORITHM AND TIME COMPLEXITY

0 spawn loops(serial)
        time = n^3
        operations = n^3
        space = 3
1 spawn loop
        time = 4
        operations= 4n^3
        space = 3n^3
2 spawn loops
        time = 3
        operations= 2n^2 + n^3
        space = 2n^2
3 spawn loops
        time = 1
        operations= n^3
        space = 0 
 
In conclusion, the more nested spawn loops, the faster the program should run. In the data table, the single spawn
loop runs slower than the spawn loop with the for loop because the former has a greater number of operations.

SERIAL CODE
#include <xmtc.h>
int main(){
int r,c,i;
for( r=0; r<n; r++){
        for( c=0; c<n; c++){
                for( i=0; i<= n; i++)
                C[r][c] += A[r][i]*B[i][c];
        }
} 
}//end main

PARALLEL CODE
#include <xmtc.h>
int main()
{
spawn(0,N*n-1)
{
int i=$%n;
int r=($/n)/n;
int c=($/n)%n;
   C[r][c] += A[r][i]*B[i][c];
}
}





PARALLEL CODE( if I could nest spawn loops)
int main(){
spawn(0,n-1){  //variable is $
spawn(0,n-1){//variable is #
spawn(0,n-1){ //variable is @
C[$][#] += A[$][@]*B[@][#];
}
}
}
}//end main

TABLE
-----------------------------------------------------
Input Size              | n=64   | n=128  |n=256    |
------------------------|--------|--------|---------|
Serial Clock Cycles     |12726565|94944564|732596001|
------------------------|--------|--------|---------|
Parallel w/ for loop    |702100  |5520356 |43922503 |
------------------------|--------|--------|---------|
Parallel w/o for loop   |1220446 |9700056 |77486861 |
-----------------------------------------------------



HW2: Matrix-Vector Multiplication
ALGORITHM

Open a for loop across the number of rows.(Lets call this variable r)
        Open another for loop from rowptr[r] to rowptr[r+1]. This tells you how many numbers are NOT zero in that row.(Lets $
        For each of these non-zero numbers, add the product values[c]*vector[c] to result[r];

Time should run in BigOh(nnz) with a minimum time of n , where nnz is the number of non-zero array elements.
Work will run in BigOh(nnz).

SERIAL CODE
#include <xmtc.h>
int main(){
        // WRITE YOUR CODE HERE
int i, j;
for( i=0; i<m; i++){
        for(j= rowptr[i]; j< rowptr[i+1]; j++){
        int k= col_ind[j]; //k represents column and i represents row
        result[i] += values[j]*vector[k];
        }
}
}//end main

PARALLEL CODE
#include <xmtc.h>
int main(){

spawn(0, m-1){
int i;
        for(i= rowptr[$]; i< rowptr[$+1] ; i++){
        int k= col_ind[i];//k represents the column
        result[$] += values[i]*vector[k];
        }
}//end spawn
}//end main

RUN-TIMES

Clock cycles for Sparse Matrix Vector Multiplication
------------------------------------------|
ALGORITHM  |SMALL|MEDIUM| LARGE  | XLARGE |
------------------------------------------|
Serial     |61055|408309|10354102|30942046|
------------------------------------------|
Parallel   |58369|377130|9264457 |27701584|
------------------------------------------|



HW3: COMPACTION

ALGORITHM
1. set a global variable as the base to 0
2. spawn n slaves, one for each element of A
        3. for each slave...
        a. if it deserves copying ( if B[$] !=0 )
                i. copy it into C, and update the base value
                ii. set D[base] to $
SERIES CODE
#include <xmtc.h>
int main(void){
int ptr=0;
int l;
for(l=0; l<n; l++){
if(B[l] != 0){
C[ptr] = A[l];
D[ptr] = l;
ptr++;
}
}//end for
}//end main

PARALLEL CODE
#include <xmtc.h>
psBaseReg base;
int main(void){
base =0;

spawn(0, n-1)
{
int step =1;
if( B[$] != 0)
{
ps( step, base);
C[step] = A[$];
D[step] = $;
}

}//end spawn
int r=0;
for(r; r<base; r++){
printINT(C[r]);
printSTR("\n");
}
}// end main

RUN-TIMES
---------------------------------------|
Input size | 50 | 4000 | 10000| 50000  |
-----------|----|------|------|--------|
Serial     |9228|100154|346005| 1949912|
-----------|----|------|------|--------|
Parallel   |9093|15067 |27898 | 125349 |
---------------------------------------|