CMSC751/ENEE759K Programming Homework 2 
Due: May 10, 2004.

The objective of this homework is to use the XMT paradigm in order to
implement the Breadth-First Search algorithm in Exercise 34 on page 79
of the class notes.

The project requires writing both a serial and a parallel version,
run both on the XMT simulator and compare running times and the total number
of operations.

Before starting programming outline an iterative variant of the BFS
algorithm in a text form.
The number of iterations should be O(h), where h is the number of layers.
The amount of (XMT) work should be linear.
The parallel time should be O(h log n).

Derive two implementations (programs) from the iterative variant:
- a parallel one.
- a serial one.

Provide the results on an input of size n=10000

AYDIN: PLEASE WORK ON THE LINES BELOW UNTILL "TILL HERE"
GIVE 2 INPUT GRAPHS IN THE ADJACENCY LIST INPUT FORM.
THE LARGER INPUT SHOULD HAVE 1000 VERTICES AND 5000 EDGES AND h 
(THE NUMBER OF LAYERS IN THE GRAPH) SHOULD BE 4-5.
The SMALLER GRAPH SHOULD HAVE SAY 10 VERTICES AND 30 EDGES.


The following files are provided:
http://www.glue.umd.edu/~balkanay/mem_map.h                                     
http://www.glue.umd.edu/~balkanay/mem_map.bin 

Please examine the mem_map.h for the global variables that you can
use. The mem_map.bin file contains the portion of the memory, where
these global variables reside. Please do not change these files. The
variables are initialized to the following values:
                                                                                
int gen_array[10000];          // an array of 10000 elements
int gen_array_length;          // 10000
int gen_aux_array[10000];      // all elements are 0
int gen_aux_array_length;      // 10000
int gen_temp_array[10000];     // all elements are 0
int gen_temp_array_length;     // 10000
int gen_pointer;               // 0
int gen_randomNumbers[500];    // an array of random numbers
int gen_randomNumbers_length;  // 500
                                                                                
Your input array is "gen_array". You have an auxiliary array
"gen_aux_array" and a temporary array "gen_temp_array" of the same
length at your disposal. You also have an array of randomly generated
numbers in "gen_randomNumbers". You can use the "gen_pointer" to keep
track of the last random number you picked from the list.

You may need to rename the binary files, in order to make them
compatible to the simulator.

For trying your program, you can use smaller input arrays. A smaller
input set (8-element input array) for trying your algorithm is
available here:
                                                                                
http://www.glue.umd.edu/~balkanay/mem_map_8.h                                   
http://www.glue.umd.edu/~balkanay/mem_map_8.bin  

AYDIN: END TILL HERE


Issues:

- Please try to write your program within the main() function only. Do
  not use any other functions.

- Print out the following information about the given graph:
  * the layer number for each node.

- Print out the number of simulated cycles.

- In addition to the code and information about its execution, your
  submitted homework should include the text variant and an explanation
  (not proof) of its complexity analysis.

REMARKS ABOUT PROGRAMMING

1. Use spawn(reg1,reg2) instead of spawn reg1,reg2 (ANSI C style).

2. Use ps(reg1,reg2) instead of ps reg1,reg2

3. Use

spawn(.)
{
.
.
.
}

instead of

spawn(.)
{
.
.
.
}
join

join is implied. It is not written explicitly anymore.


4. Do NOT use the reserved words spawn,spawni,ps,psm & fork as part of your
variables names.