Assignment 3: A Divide-and-Conquer API
Purpose
Specification
The DAC API
Design a DAC API. For ideas about this, review the Cilk paper, the CX paper, and the JICOS API, illustrated in the Tutorial section of the JICOS web site. Cilk allows any acyclic directed graph of threads. Your api needs to support only "fully strict" (i.e., purely DAC) programs. You may require that a task either:
- produces a single result object as its output
- constructs subtasks and a "compose" task that takes the single output from each of the subtasks as its "arguments," and computes some function of these as its output.
The implementation of this API involves the cooperation of the Task, the Computer, and the Space. Look at the specification of a Closure in the Cilk paper. Relate this to the infomation requirements of a Task in your system. The Space needs to distinguish between tasks that have all their arguments (and thus are ready to be executed by Computers) from those that do not. The scheduling algorithm you use to distribute ready tasks to Computers is unspecified: You can do whatever you want.
If task t produces output o (as opposed to subtasks), it needs to communicate o to its successor task s, which is waiting for o, as an input argument: When t produces o, the Space needs to know which task is s. Thus, you may need some form of task identifier. The Space also needs to know which of s's arguments o is, so the Space can set the appropriate argument of s.
Your system does not need to be robust in the presence of faulty application programs.
Application development
- Define the nth Fibonacci number, F(n), recursively:
- For n < 2, F(n) = 1.
- For n =>2, F(n) = F(n - 1) + F(n - 2).
- Refactor Mandelbrot Set visualization and TSP to use your DAC api.
The clients
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 problem instance;
- F(16)
- Mandelbrot problem instance parameter values:
- Real: -0.7510975859375, imaginary: 0.1315680625. Here is what the image should look like, modulo your color scheme. With respect to rendering, handle the y coordinate properly, otherwise your image will be inverted.
- edge length: 0.01611
- 1024
- 4096 = 2^{3 X 4}
- EuclideanTsp problem instance: use the following list of
16 cities as a problem instance:
Each line that follows has the x
and y coordinates of a city, starting with city 0 and ending with city 15:
1 1
8 1
8 8
1 8
2 2
7 2
7 7
2 7
3 3
6 3
6 6
3 6
4 4
5 4
5 5
4 5
If you plot these cities, then (I think) a minimal tour is: 0, 4, 8, 12, 13, 9, 5, 1, 2, 6, 10, 14, 15, 11, 7, 3. (Since I have arrived at this solution by inspection, this may not be optimal.) The cost of this tour is 16 + 12 sqrt(2), which is approximately 32.97.
- suitably display the arguments.
- sends each root task to the Space via the put method;
- retrieves the results from the Space via take, which then are displayed suitably.
Deployment
- Start a Space
- Start c Computers on c different machines.
- Start your client
- Record the elapsed time for each of the client's problems.
- Record the average Task run time for each problem.
Repeat the above steps for C = 1, 2, 4, 8, and 16. Let P be a problem instance (e.g., an instance of the TSP). Let TC be the elapsed time to complete P using C Computers. For each problem, P, using Excel, plot P's the parallel efficiency: T1 / (C TC).
For the case of C = 1:
- Run the client with the client, server, and 1 computer all instantiated in the same JVM. Call the elaped time TS.
- Plot TS/ T1. What is this data saying?
Analysis
- What do you see as the advantages/disadvantages of your task scheduler?
- How might you change the infrastructure to improve your parallel efficiencies?
- What issues are involved in generalizing your infrastructure to a network of Spaces?
Paper Summary
Submit a 1-page summary, entirely in your own words, of the paper titled, "CX: A Scalable, Robust Network for Parallel Computing."
Deliverable
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 - has an index.html file that contains links to:
- readme.html: provides any explanation needed to build your system, and and run each component.
- javadoc, a directory that contains the javadoc of your
- api interfaces
- Task classes: constructor parameters and execute method return values.
- experimental results: a spreadsheet.
- your analysis, in either html or pdf.
- your paper summary, in either html or pdf.
- source - a directory containing the following subdirectories, reflecting the package structure:
- api, which contains interfaces and classes needed to develop applications that use your system.
- client, which contains your client class[es]
- system, which contains interfaces & classes that comprise your cluster infrastructure (minus api stuff).
- tasks, which contains Task & Result classes (each Task/Result class pair may be in a subpackage)
- test - your Java unit test source files. Each test class is in the same package as the class it tests.
- library - has executables, typically jar files, that are not written by your team, but are needed to run your project.
- policy - has policy file[s].
Files
-
build.xml
file with targets to:
- build: builds your system: Creates a computer.jar, space.jar, and client.jar, and tasks-dl.jar.
- runSpace: starts a Space.
- runComputer: starts a Computer.
- runClient: starts a client.
Your build.xml also may have targets to start and stop sets of computers. Although it may be inelegant to have one start target for each specific number of computers, making such targets is a simple matter of copy & paste.