19th International Symposium on Computer Architecture
and High Performance Computing

Open Contest Sponsor:

Sun Grid5000

Open Contest Award for the best solution:

Open Contest Award

Featured Photo:

12

Previous Editions:

Click here for previous editions of SBAC-PAD and to access their conference proceedings.

1st Open Contest of Parallel Programming

Results

The results of the 1st Open Contest of Parallel Programming are available here.

Introduction

The deadline has been extended to Wed., 24th of October, 13h00 (Brazilian time, GMT-3).


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 cost of the smallest round-trip should be correct,
  • the smaller the run-time, the better.

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.

More Information

  • Nicolas Maillard (UFRGS) - nicolas@inf.ufrgs.br
  • Benhur Stein (UFSM) - benhur@inf.ufsm.br
Co-sponsored by
TCCA and TCSC of		 and Conference Proceedings
are published by		 Promoted by Organized by
IEEE IFIP IEEE2 SBC UFRGS   UFF
Sponsors