Moodle course web site

Assignment 4: Supporting distributed Branch & Bound

Purpose

The purpose of this programming assignment is to:

References on branch and bound

Specification

Branch & Bound Framework

Design & implement a framework for branch & bound (B&B) applications that can be applied to Tsp & 3-Sat (see below).

The Environment

Enable the application programmer to establish a computational environment accessible to all tasks:

The Input Object

The read-only object typically is used to transmit data that is common to all tasks comprising a computation, such as a distance matrix in non-Euclidean Tsp. More generally, this read-only object has a computation's input. We therefore refer to this attribute of the environment as the input object.

Shared Object

Sometimes you want all tasks to have access to a common set of data that tasks can modify during the course of the computation. In computations distributed over the Internet in which performance is a prime goal, it may be inappropriate to provide shared objects in the conventional sense. Here, we provide a weaker form of sharing that is compatible with high performance:

An Object that is shared among all of a computation's unfinished tasks, and whose value, when changed by any task, is propagated with best effort to all unfinished tasks.

This limited kind of sharing is of limited value. Branch & bound however is an important combinatorial optimization technique that benefits from this kind of sharing.

When is a proposed update to a shared object accepted? We cannot use the time that the update was proposed; there is no single clock in a distributed system. Design & implement an API for such a shared object that does not depend on any notion of global time, but which makes sense in the context of a given application.

For example, in the Tsp, the cost of the best known solution at any point in time can be shared among the tasks. Between 2 such costs, a lower cost is a newer cost. In branch and bound, this value may be used to decide if a particular subtree of the search tree can be pruned. Thus, sharing the cost of the best known solution enhances the pruning ability of concurrently executing tasks that are exploring disjoint parts of the search tree. Indeed, this improvement in pruning is essential to the efficiency of distributed B&B.

API

You are free to create the api to support the computational environment as you see fit. One possibility is to augment the Client2Space interface with the following method:

Semantics: If a Task object is sent to the Space after the setEnvironment method returns, it has access to those input and shared objects. Alternatively, you might combine put, take, and setEnvironment:

Semantics:

  1. Set the environment to the input and shared objects.
  2. Compute that task, blocking until its Result is returned.

Whatever you choose for your Client2Space interface, you need to modify the Task interface to give the body of its execute method access the input and shared objects. The api can include an abstract base TaskImpl class that implements the Task interface. Two possibilities are, among others: 

	private Computer computer;

	abstract public Result execute();
	public Object getInput() { return computer.getInput(); }
	public Object getShared() { return computer.getShared(); }
	public void   setShared( Shared shared ) { computer.setShared( shared ); }
	
	void   setComputer( Computer computer ) { this.computer = computer; }

Semantics: All tasks have access to an input object and a shared object. To propagate a newer shared object to other tasks, the task invokes it setShared method. The computer.setShared method propagates the proposed newer shared object to the Space only if the proposed shared object is newer than the computer's existing shared object. The Space similarly propagates a shared object to other computers only if it is newer than the Space's shared object.

Alternatively, but still using a base TaskImpl class, you may revise the execute method:

The setComputer is only to help the implementation of the setShared method. Task classes that extend TaskImpl do not have access to it.

Modify either Space2Computer or Computer2Space to support distributing the environment.

A possible Shared interface:

Advice: Make objects that implement Shared immutable to facilitate multithreading.

When a Task's execute method wants to convey a new value for the Shared object to other Tasks, it uses setShared to replace the existing Shared object with the new one: 

	
	setShared( new IntShared( minCost ) );

The Computer's setShared method is responsible for confirming that the proposed shared object is indeed newer, by using the isNewerThan method. For example, its implementation might be: 


	synchronized void setShared( Shared proposedShared )
	{
		if ( proposedShared.isNewerThan( shared ) )
		{
		    shared = proposedShared;
		    space.setShared( shared ); // space refers to proxy for remote space
		}		
	}

When the Space gets a proposed Shared object from a Computer, it similarly tests to see if it is indeed newer, and, if so, it sends this to all Computers, possibly excepting the Computer that sent it the proposed Shared.

Applications

Boolean Satisfiability (Sat)

We introduce another application: 3-SATISFIABILITY (3-Sat), a special form of the Boolean Satisfiability Problem, which is NP-complete. Let x be a boolean variable. The expression x and the expression !x are called literals, where !x is the negation of x. A clause is a set of literals. It evaluates to true if there is a literal in the clause that evaluates to true. The satisfiability problem (in conjunctive normal form (CNF)) is as follows:

INSTANCE

A set U of boolean vaiables and a collection C of clauses over U.

QUESTION

Is there a satisfying truth assignment for C? That is, is there an assignment to the boolean variables that makes all the clauses evaluate to true?

3-Sat is a restricted form of CNF satisfiability: Each of the clauses has exactly 3 literals.

Develop an application for 3-Sat. The representation of the set of clauses is an int[][]. There is 1 row for each clause. Each clause is an int[] with 3 values, one for each literal. For example, int[] = { 4, 7, 10 } represents the clause that evaluates to true if and only if at least one of x4, x7, and x10 is assigned true; int[] = { 4, -7, 10 } evaluates to true if and only if ( x4 or x10 are assigned true) or ( x7 is assigned false): unary minus indicates the unary negation operator.

To represent a 3-Sat problem instance, define a class Sat3Input, that has:

clauses.length is the number of clauses; clauses[i].length == 3, for 0 <= i <= clauses.length.

The class has a constructor,

Sat3Input( int n, int[][] clauses )

You may assume that the arguments to the constructor are correctly formed (including that the literals contain only values x or -x, where 1 <= |x| <= n).

Use DAC to solve 3-Sat: Tasks are initialized with a partial assignment. The root task has the empty assignment.

If a task detects that the instance is satisfiable, it sets the Boolean shared object to true. If a task accesses the shared object and it is true, then the problem already has been solved, and the execute method returns immediately with an appropriate return value.

Implement your Task class so that the set of clauses is the computation input, as described above. The Result value is:

Existing applications

If you build a distance matrix for Tsp instances, you may wish to make that the input object.

The client

Define a client that:

int[][] clauses = 
{
{   1,   2,  3},
{  -2,  -3,  4},
{  -3,  -4,  5},
{  -4,  -5,  6},
{  -5,  -6,  7},
{  -6,  -7,  8},
{  -7,  -8,  9},
{  -8,  -9, 10},
{  -9, -10, 11},
{ -10, -11, 12},
{ -11, -12, -1},
{ -12,  -1,  2},
{  -1,   2,  3}
}

Deployment

Repeat the above steps for C = 1, 2, 4, 8, and 16. Let P be a problem. Let TC be the elapsed time to complete P using C Computers. For each problem, P, using Excel, plot P's parallel efficiency: T1 / (C TC).

Paper Summary

Submit a 1-page summary, entirely in your own words, of the paper titled, "Cilk: An Efficient Multithreaded Runtime System."

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:

source

This contains the following subdirectories, reflecting the package structure:

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:

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.


 cappello@cs.ucsb.edu 2009.04.30