# Background

In our constantly-evolving, many-core world, the task of load-balancing is taking on more and more importance, as is the algorithmic load balancing of computational resources done within the parallel codes computational scientists have written to implement their mathematical models. This problem offers students the opportunity to develop their algorithm for making load-balancing decisions in the universe of hybrid computing, by deciding which tasks will be run together in shared memory mode, communicating between groups using message passing.

# Required/Recommended Knowledge

Ability to program in the language of your choice.

# Problem Description

Eric Shook, a PhD student at the University of Illinois at Urbana-Champaign, has graciously suggested the kernel of a problem loosely based on his dissertation work. You will be given a simplified execution model of a linear boundary problem. An integer value is associated with each processing node representing computational workload. The value on the line connecting nodes represents the additional communication cost from using message passing instead of shared memory exchange of boundary values. For instance, in the example below, if we have three processors, we are then looking to make two cuts in the linear chain, which accomplishes the load balancing of the two pieces to the two processors.

Suppose we made a cut at 6 and 496, which might seem perfect at first glance. However the compute time for the first piece is 19+(6), for the second is (6)+42+28+7+496, and 496+2 for the third, i.e. 25, 579, and 498. Since we have to wait till all are done, the overall time is max(25, 579, 498) or 579. This is actually not the best place to do the two cuts. The best is the min(of the cost of all possible combinations of two cuts).

It turns out a better cut is at 17 and 13, max(19+42+(17), (17)+28+(13), (13)+7+2), which is max(78, 58, 22), which is 78.

The best cut is at 6 and 17, max(19+(6), (6)+42+(17), (17)+28+7+2), which is max(25, 65, 54), which is 65.

You are given three files (see below), which you must run against the same code. In all three cases you are looking for the best solution. A less desirable, but possibly more practical solution is to write a code that yields a pretty good solution. You will of course need to describe your algorithm and why it is either the best solution or a pretty good solution.

The first line of the file gives the number of processors.

Subsequent lines contain two numbers:

1. The execution time of the task.
2. The cost to add to the task group on the left and the right, if a cut is made at this spot.

The last line corresponds to the last task and thus does not have a second number.

## Analysis

Your report should include a description of the steps taken by the team in working to obtain your program. You will need to supply your program and the three outputs which includes where the cuts were made, as well as a description/proof why your solution is either the correct solution or a reasonable approximation of the correct solution.