Assignment 5:
Ameliorate communication latency & exploit multi-core hosts

Purpose

The purpose of this programming assignment is to:

• Improve your lower bound for the Tsp.
• Exploit multi-core processors when used as compute servers.
• Amerliorate communication latency.

Specification

Branch & Bound

Tsp

Implement a lower bound for the Tsp that is stronger than just the cost of a partial tour. For example, implement the lower bound that uses the 2 shortest edges incident on each city. Implement your lower bound so that, as the partial tour increases, the lower bound is strengthened (increases).

Sat

Using the shared object, "cancel" outstanding Sat tasks after a satisfying assignment is found. That is, this is accomplished via the api, not via the system infrastructure.

Ameliorate communication latency

Instrument your system so that each of the following enhancements can be turned on or off.

Space-runnable tasks

Provide an api and infrastructure enhancement that enables selected tasks to be run on the Space. Apply the api so that the composition tasks for each application, and only those types of tasks, are executed on the Space.

Task caching

Provide an api and/or infrastructure enhancement that enables tasks to be cached on compute servers.

Task prefetching

Provide an api and/or infrastructure enhancement that enables tasks to be prefetched to compute servers: A task is, or tasks are, requested while Computer[s] run task[s].

Exploit multi-core processors when used as compute servers

JVMs increasingly exploit multiple processors by mapping different threads to different processors. The java.lang.Runtime method public int availableProcessors() returns the number of processors available to the Java virtual machine. On each compute server, start that number of Threads, each of which runs tasks.

Instrument your system so that this enhancement can be turned on or off.

Applications

• Tsp
• Fibonacci
• Sat

The client

Define a client that:

• gets the domain name of a Space's machine from the command line;
• gets a remote reference to the Client2Space service from the rmiregistry.
• for each application, it:
• instantiates a large problem instance;
• EuclideanTsp problem instance: use the following list of cities as a problem instance: Each line that follows has the x and y coordinates of a city, starting with city 0:
  
  1 1
  11 1
  11 11
  1 11
  2 2
  10 2
  10 10
  2 10
  3 3
  9 3
  9 9
  3 9
  4 4
  8 4
  8 8
  4 8
  5 5
  7 5
  7 7
  5 7
  
  

  If you plot these cities, then (I think) a minimal tour is: 0, 4, 8, 12, 16, 17, 13, 9, 5, 1, 2, 6, 10, 14, 18, 19, 15, 11, 7, 3. (I arrived at this solution by inspection.) The cost of this tour is 24 + 16 sqrt(2).

• 3-Sat problem instance: Use the SATLIB probem instance whose url I sent out previously.
• Fibonacci problem instance: Compute F(26).
• suitably display the arguments.
• constructs a "root" task for the problem instance
• uses your api to arrange for its execution; 
• gets the result
• displays it suitably.

Deployment

The deployment specification is the same as the previous homework, with 2 differences:

• Run with the number of computers, C = 1 and 16.
• For each value of C, run 4 experiments:
  1. communication latency amelioration turned off; single compute thread
  2. communication latency amelioration turned off; multiple compute threads
  3. communication latency amelioration turned on; single compute thread
  4. communication latency amelioration turned on; multiple compute threads

For each application, give a bar graph of the completion times for these 4 experiments.

Paper Summary

Submit a 1-page summary, entirely in your own words, of the paper titled, A Development & Deployment Framework for Distributed Branch & Bound

Deliverables

Mail <cappello@cs.ucsb.edu> a jar file, named <name>.jar, where <name> is the CS computer account username of 1 member of the pair. It should include the following directories and files:

Directories

documents

This has an index.html file that contains links to the following:

• readme.html: explains how to build and run your client, Space, and computers. Explain how to turn on/off communication latency amelioration & multiple compute threads.
• javadoc, a directory that contains your javadoc (which explains how to use these classes/interfaces):
• api
• Task classes: constructor parameters & run method return values.
• design document: Present your design. If your code is the trees, describe your forest: Identify the essential design issues, and how your approach to them is manifested in your object-oriented design. Figures are welcome. This should be no more than a page or 2.
• experimental results: an Excel spreadsheet with graphs. Explain your results. Document how many compute threads each compute server is using, when the multiple compute thread feature is on.

  It may be instructive to turn on/off each communication latency amelioration technique individually. But, you are not required to report that data.

• your paper summary, in either html or pdf.

source

This contains the following subdirectories, reflecting the package structure:

• tasks, containing your Task classes (each Task subtype may be in a subpackage, if you prefer)
• client, containing your client class[es]
• system, containing your infrastructure.
• api, containing the api (actually, classes and interfaces).

test

This has your Java unit test source files. Each test class is in the same package as the class it tests.

library

This has executables, typically jar files, that are not written by your team, but are needed to run your project.

policy

This has your policy file[s].

Files

build.xml

This has targets to:

• build: builds your system.
• Creates a computer.jar, a space.jar, and a client.jar, which constitute their respective classpaths.
• Creates a tasks.jar, which constitutes the client's codebase.
• runSpace: starts a Space.
• runComputer: starts a Computer.
• runClient: starts a client. Alternatively, you may have runMandelbrot, runTsp, etc.

Your build.xml also may have targets to start and stop sets of computers. Although it may be inelegant to have a start target for each specific number of computers, making such targets is a simple matter of copy & paste.