Title A Grid Approach to Divide-and-Conquer
Proposer joxan
Category HYP
Project Areas Software Systems
Description
The starting point is an abstract algorithm/framework to solve
divide-and-conquer problems on a network of heteogenrous computers
(grid). The algorithm, based on message passing, is highly dynamic and
adaptive, enjoys full utilization of available computing resources,
and features fault detection/recovery. The algorithm makes no
assumption on the stability of the workers on the network. A large
area of application of this abstract algorithm is combinatorial
search. In this project, you are expected to refine the communication
protocol among the computers, and benchmark this algorithm on the
Tembusu cluster against well know combinatorial optimization problems
such as Traveling Salesman Problem and Job Shop Scheduling.
Requirement Access to several unix machines
Skill Programming in C/C++, knowledge of client/server
programming
Benefit Adaptive parallelism for intractable problems
Reviewer 1's Comments teoym has reviewed this proposal. His comment is:
An interesting grid application.
Reviewer 2's Comments yuenck has reviewed this proposal. His comment is:
sounds hard, especially the fault recovery part; does the algorithm
involve process migration (either to dynamically balance the workload,
or to re-start jobs from crashed processors)?