Click here for previous editions of SBAC-PAD and to access their conference proceedings.
The results of the 1st Open Contest of Parallel Programming are available here.
The organization of the SBAC-PAD'07 Conference, together with SUN Microsystems Brazil and the INRIA project GRID'5000 (http://www.grid5000.fr), is glad to announce the first Open Contest of Parallel Programming.
The traveling salesman problem (TSP) is a classical problem of combinatorial optimization, with many applications. The Wikipedia states it as follows: Given a number m of cities and the costs Cij of travelling from any city i to any other city j, what is the cheapest round-trip route that visits each city exactly once and then returns to the starting city? (TSP at Wikipedia).
Applications include many transportation and logistics problems, for example the definition of bus lines, the drilling of printed circuits boards, the assignment of routes for planes, the scheduling of jobs on a single machine, etc.
To win the Open Contest, you have to provide a parallel, distributed version, of a solution to the symmetric TSP problem (for all pair i,j, Cij = Cji). As input, your program must read a file in the TSPLIB format (see TSPLib 95 and some examples in National Traveling Salesman Problems) as the only argument in the command-line. As output, your program should return the lowest possible cost of a round-trip.
You will have to provide your source code, with a Makefile, as a unique tar file, through this page, before Sunday, 21st of October, 23h00 (Brazilian time, GMT-3). The tar bundle should include all the necessary source code: no pre-compiled binary code is allowed. Your Makefile should include a target called 'run', to set-up and run your parallel program (for instance by invoking 'mpirun'). A README file should give the necessary details, if any, such as environment variables to be set. The parallel programs will then be run on a Cluster, on some given input, and classified according to the following criteria:
The target cluster will be the GRELON cluster (with our special thanks to the Nancy site of Grid'5000, hosted at the LORIA), composed of bi-processor nodes, each processor being an Intel Xeon 5110 dualcore, with 2 GB of RAM. The nodes are interconnected by a Gigabit Ethernet network. The run-time of the parallel TSP will be evaluated on around 100 nodes of the cluster.
You are free to use any algorithm or heuristics that you find appropriate. A good starting point can be this site about TSP, which provides Open Source software and testbeds. The software, called Concorde, already enables the use of Threads and Sockets. Any implementation should be limited to the use of C, C++ or Fortran, Posix Threads, MPI and/or OpenMP.
The SUN Microsystems Brazil company and partners will reward the best solution with a Sun Ultra 20 Workstation.
TCCA and TCSC of
are published by
|Promoted by||Organized by|