Teaching

Multi-Core Programming Lab on Swarm Algorithms (WS 2011/12)

Lecturer:

Tobias Friedrich and Timo Kötzing

Tutors:

Jan Balzer and Claudio Magni

Time:

Wednesday 10:00-11:30 (be on time!)

First meeting:

19.10.2011

Contact:

Jan Balzer (technical issues): janbal@mpi-inf.mpg.de
Claudio Magni (reading material): get email address

Room:

024 in the MPI building (E1 4)

Prerequisites:

Basic knowledge of algorithms and data structures. Proficiency in coding on your own.

Registration:

Please register here for the course. In case the course is heavily oversubscribed, we will use the registration time as tie braker and prefer students who registered early. If you want to unregister, please do not send an email, but do so here. Within a few weeks after the semester starts, you will of course also have to subcribe in the HISPOS system of the university.

Content:

Swarm-based randomized search heuristics like ant colonies or particle swarm optimizers have been successful applied in various domains in the last few years. A particular advantage of such algorithms is that they can easily be parallelized in order to efficiently exploit a computer with a multi-core architecture. In this seminar the students are asked to invent and implement problem-specific algorithms, using an evolutionary or swarm based meta-heuristic.

Available Hardware:

This lab asks you to implement parallel algorithms and to exploit a multi-core architecture. For running your implementations, we give you access to a high-end server with eight 8-core Intel Xeon X7550 (and hence a total of 64 cores and 128 threads) spread on 2 motherboards and one Terabyte RAM.

Frameworks:

C/C++: POSIX Threads, MPI (Message passing interface), Boost, LLVM, OpenMP
Other: Java 1.7, Scala, Haskell (some notes on how to get performance in JAVA)

Assignments:

For the first about five weeks of the lab we will ask you to implement two small classical parellelized algorithms and a small swarm algorithm. After that, for the main part of the course, we ask you to implement an efficient optimization procedure for an NP-complete problem; we will rank your solutions with respect to their performance.
Furthermore, we will ask you to read some material at the side and will write mini tests on that material. You can find details regarding the reading assignments and their test dates in the table below and here. If you access this page from within the university network, then you will find links to all reading assignments at the bottom of this page.

Credits:

You earn the usual 7 LPs for a seminar if you complete the stated assignments.

Competition:

We have our competition hosted at SPOJ.

Schedule:

Date	Topic	Reading test on	Programming Assigment (PA)

Papers: