CSC2002S-Assignment 3 Solved

There is a branch of Botany that is concerned with simulating vegetation patterns using computerized models. This has implications for anticipating the effect that climate change will have on vegetation. These models scale in computational complexity with the size of the input terrain, which in some cases can span entire continents. They are therefore prime candidates for acceleration using parallel programming.

 

One of the most important factors affecting a tree’s growth is its exposure to sunlight. In this assignment you will efficiently calculate the average sunlight received by trees in a forest (and also record the sunlight exposure of individual trees).

 

For the purposes of this assignment the landscape is represented by a regular matrix of floating point values. Each value represents the average hours of sunlight per day falling on a 1m x 1m area of the terrain. Not all areas receive the same amount of sunlight because of folds in the landscape (see below).

 

 

 

Figure 1: Average sun exposure during March for a 3km x 3km section of terrain in California. North facing slopes receive less sunlight (and are represented by a darker red in the colour map). South facing slopes tend to receive more sunlight (a bright red or orange in the colour map). 

 

Tree canopies are represented (rather unrealistically) as a square coverage area on the terrain. For the forest you will be provided with the top left (x, y) terrain coordinate of a tree’s canopy indexed from (0,0) and the extent in meters (e).

 

Your task is to calculate both the total sunlight exposure for each tree canopy (the sum of the sunlight values within its canopy area) and the mean sunlight exposure for all trees.

 

The file input format is as follows:  

<terrain x size – INT <terrain y size – INT

<avg. hours sunlight at (0,0) – FLOAT <avg. hours sunlight at (0, 1) – FLOAT … <avg.

hours sunlight at (xsize-1, ysize-1) – FLOAT

<number of trees – INT

<x corner of tree 0 – INT <y corner of tree 0 – INT <canopy extent of tree 0 – INT

…

<x corner of tree (numtrees-1) – INT <y corner of tree (numtrees-1) – INT <canopy extent of tree (numtrees-1) – INT

 

For example, a very small 5m x 5m section of terrain, with 2 trees would be encoded in the input file as:

5 5

4.5 5.5 4 3.5 4 4.5 5 4.5 4 4 5 5 5.5 4.5 5 4 4.5 5 5 4 4 4 4.5 4 3.5

2

1  1 3

2  3 4

 

Visually this corresponds to:

 

 

 

 

 

Note that some trees may extend beyond the edge of the terrain (as is the case above for the light green tree) and these parts of the canopy should be ignored. Trees may also overlap, but for the purposes of this simulation they do not occlude each other.

 

The file output format is as follows:

<avg. sunlight per tree – FLOAT

<number of trees – INT

<total sunlight tree 0 – FLOAT

…

<total sunlight tree (numtrees-1) – FLOAT

 

For the example above this would mean an output of:

34.5

2

43

26

 

 

 

 

 

In this assignment you will attempt to parallelize the problem in order to speed it up.  You will be required to:

 

•       Use the Java Fork/Join framework to parallelize the sunlight exposure calculations using a divide-and-conquer algorithm.

 

•       Evaluate your program experimentally:

 

o   Using high-precision timing to evaluate the run times of your serial and your parallel method, across a range of input sizes, and  

 

o   Experimenting with different parameters to establish the limits at which sequential processing should begin.

 

•       Write a report that lists and explains your findings.  

 

Note that parallel programs need to be both correct and faster than the serial versions.

Therefore, you need to demonstrate both correctness and speedup for your assignment.  

 

 

Assignment details and requirements
Your program will calculate the sunlight exposure of individual trees in parallel as well as the average sunlight exposure of all trees in the forest.

1.1 Input    and    Output         
 

Your program must take the following command-line parameters:   

<data file name <output file name

The format of these files must follow the specification provided above.

 

We will provide you with a sample input file (on Vula), though you may also create your own using random data.

1.2      Benchmarking     
You must time the execution of your parallel sorts across a range of data sizes and number of threads (sequential cutoffs) and report the speedup relative to a serial implementation. The code should be tested on at least two different machine architectures (at least one of which must be a multi-CPU/multi-core machine).  

Timing should be done at least 5 times. Use the System.currentTimeMillis method to do the measurements. Timing must be restricted to the sunlight exposure code and must exclude the time to read in the files and other unnecessary operations, as discussed in class. Call System.gc()to minimize the likelihood that the garbage collector will run during your execution (but do not call this within your timing block!).