Project 5
Due Dec. 5, 2014 at 11:59:59pm no late submissions will be accepted
20 Points, you may work in groups of two on this project
Turn in this assignment as a zip file using the eCompanion Dropbox.
Graduate students must complete both MPI and multi-threaded versions of this assignment and provide full I/O statistics during runtime using an interactive visualization with D3.js for an additional 30 points.

Starter code is provided at the following link
Sample input data is provided at the following link

Introduction

Write a multi-threaded or MPI C program that uses a thread/process to represent a memory manager that will provide paged data management to worker threads/processes. Note that each worker thread/process may perform different operations.  Before worker threads/processes may start processing, they must request memory from the memory manager.  Such memory must be requested for all local variables within each thread/process except for those used to allocate memory from the memory manager.  Input data for each thread must be provided through the memory manager thread/process.

Workers will perform one of three kinds of tasks: Decryption, Matrix Addition, or Dot Product. 

Your programs must take as file input the following information:

• Number of Decryption workers based upon the solution at the following site: http://www.hpcuniversity.org/students/weeklyChallenge/48/)
  
• Number of Matrix Addition workers (use the solution to project 2 to help in creating these threads)
  
• Number of Dot Product workers (this problem is very similar to the matrix addition, but uses vectors)
  
• Memory size in KB (≥ 10)
• Number of pages per segment (≥ 1)
• Frame size in KB (≥ 1 and a power of two)
  

You may assume that data will be loaded from a virtual hard drive. You may also assume that the virtual hard drive will be large enough to hold all files provided as input.

You must also provide as input within the same file:

• An id number for each thread followed by either the
  
• Name of the files to be decrypted, or
  
• Names of the pair of files containing Matrix data, or
  
• Names of the pair of files containing Dot product data
  

Both threaded and MPI programs should make use of the following data structures (or similar data structures of your own creation) within the memory manager.

struct Page
{
    int pageSize;
    Frame * frame;
    struct Page * next;
};

struct Segment
{
    int threadOwner;
    Page * pageList;
    struct Segment * next;
};

struct PhysicalRam
{
    Frame * frames;
};

struct VirtualHDD
{
    int * threadOwner;
    char ** files;
};

struct Frame
{
    char * frameData;
};

Matrix Addition Input

Assume data for matrices will be stored in files. Matrices will be stored one matrix per file. Each of the files will contain header information denoting the number of rows and columns in the matrix on the first line. Thereafter, each file will contain the data for a matrix. For example, the following matrix:

[ 1 2 3
  4 5 6
  7 8 9 ]

Would be stored as:

3 3
1
2
3
4
5
6
7
8
9

Dot Product Input

Assume data for dot products will be stored in files.  A dot product is the sum of the point to point products of values within a pair of vectors.  Vectors will be stored one matrix per file. Each of the files will contain header information denoting the number of elements in the vector on the first line. For example, the following vector:

[ 1 2 3 4 5 6 7 8 9 ]

Would be stored as:

9
1
2
3
4
5
6
7
8
9

The dot product of two vectors [ 1 2 3 ] and [ 4 5 6 ] is 1*4 + 2*5 + 3*6 = 4 + 10 + 18 = 32

Decryption Input (i.e. an encrypted file)

The encrypted file is a flat file that contains information encrypted via xor.  You may assume that the key will be provided in the first line of the file.  Notice that if we take 37 xor 23, we get the encrypted result 50.  We can decrypt the result by taking 50 xor 23 = 37.  For example, the following text:

This file will be encrypted!

If encrypted using 23 as the key, would be stored as:

23
C~d7q~{r7`~{{7ur7rytengcrs6

You can use the following code to help with your encryption and decryption:

#include <stdio.h>
#include <string.h>

int main(int argc, char ** argv)
{
  printf("%d\n", 37 ^ 23);
  printf("%d\n", 50 ^ 23);

  char * str = "This file will be encrypted!";

  int i = 0;
  for(i = 0; i < strlen(str); i++)
    printf("%c", str[i] ^ 23);
  printf("\n");
  return 0;
}

Processing

Assume each thread/process may cache (store with in its own data structures), all of its data received from the memory manager. You may also assume each thread can keep track of the size of the matrices, vectors, or file data belonging to it. Before a thread/process may add matrices a row and a column, decrypt data, or perform a a dot product, it must acquire data from the memory manager. To obtain data, you must make a function call or send a request to the memory manager requesting the data for that thread/process.  When this call is made, the memory manager must first simulate virtual memory by finding the correct segment number. Next, the memory manager must simulate the segment table by finding the appropriate page number in the segment table, and using the page number to access the corresponding frame from simulated physical memory (an array). You will need to keep track of segment sizes and frame sizes to make the appropriate conversions between offsets in virtual memory and physical memory. You may allow the memory manager to keep track of the files and matrices belonging to each worker thread.

Note that you may encounter memory page faults while performing processing (when loading a new thread/process). When a process/thread completes, you must swap matrix data out of memory and replace it with the needed memory from the virtual hard drive to continue processing and provide worker processes/threads with the data (files) they need. You may assume that all threads/processes arrive for processing at the approximately same time and are processed in a first come first serve manner. Note that you have a limited amount of main memory. If there is not enough memory for each thread/process to perform its processing, you must force those threads/processes to wait until memory is available. Provided memory is available, the memory manager should allocate enough space for all files for every active worker thread. Hint: you may wish to use a mutex and a condition variable to help with your implementation of the memory manager.

Output

Provide as output, the average worker thread runtime in milliseconds, the average number of frames used per worker thread, the total runtime, the total number of frames used, and the total number of pages used. Store the results of each matrix multiplication and decryption in an output file. Provide dot product results as output to standard out (the screen).  Note that this data must pass through main memory before it can be written to a file.

Submission

Submit your source code this program to the eCompanion dropbox for Project 5. Additionally, you must submit a README file explaining how to run and compile your program and denoting any issues with the program.