Hasso-Plattner-Institut Potsdam Operating Systems and Middleware Group at HPI University of Potsdam, Germany
Operating Systems and Middleware Group at HPI

Exotic Methods in Parallel Computing

Summer term 2012

Frank Feinbube, Fahad Khalid

Dr. Peter Tröger

Start thinking about your projects now!

Next meeting: 14.05.2012 17:00 H-2.57
Parallelization for Complex Domains II: Optimization and Learning

Lecture type: Project seminar Team size: 1-3 students Recommended: experience with Java or C++; Parallel Programming Concepts Lecture

The ever-increasing transistor count according to Moore's law is currently used for adding more computational cores in each new processor generation. Hardware vendors try to integrate the increasing amount of cores in new ways to overcome the three big hinderances to scalable performance: The power wall, the inter-request level parallelism wall and the memory wall. Networks-on-a-chip, dynamic memory hierachies, massive data-parallel execution, ... are currently hot research topics and will influence the future of servers and end-user computers, as well as embedded and mobile systems.

With the advent of multi-core processor architectures, the necessity of programming concurrent systems has become important for mainstream application development. Performance penalties for not applying parallelism are so huge on modern hardware architectures that they cannot be ignored anymore. This is due to the fact that the only way to take advantage of new processors is to be able to take advantage of the increase in number of cores for each new processor version.

In this course, we want to discuss the most promising programming models for parallel software that are currently in the focus of reasearch. In order to get practical experience with these models, we provide a number of programming models and appropriate small projects to chose from. Each project is worked on by a small team of students.

Vertiefungsgebiete (SO2004): Systems Architecture, Information Systems, Network & Service Computing, Mobile & Embedded Systems, Enterprise Systems Technology
Vertiefungsgebiete (SO2010): ITSE, OSIS

Seminar Outline

Block 1: Introduction

Introduction to the topics. Foundations for working on the projects.
  • Seminar Outline (Slides)
  • Parallel Programming Concepts Overview (lecture page)
  • Multi-Agent Systems and Concurrency(Slides)
  • GPU Computing

Block 2: Project Phase

Time for the teams to work on the projects. Three presentations per team:
  • Startup presentation (problem domain, problem, possible approaches)
  • Progress presentation (selected approaches, achievements and challenges)
  • Final presentation (solution, evaluation)

Important Dates

25.04.2012offical (=debatable) enrolment due date
23.05.2012Project Proposal*
25.05.2012Project Approval
04.06.2012Inital Presentation
18.06.2012Progress Presentations
09.07.2012Final Presentations
01.08.2012Hand over Project and Report
* please include the names of the team members, a title, a short outline about what you plan to do and how success is be defined.

Possible Projects

Multi-Agent Systems

  • Cycles of War (SVN:svn://svn.hpi.uni-potsdam.de/cyclesofwar)
    • Multi-agent based strategy for dominating the universe :)
    • Game programing using concurrent agents, and perhaps some winning strategies developed in Game Theory
  • Multi-agent based Simulation (MABS)
    • Mathematical models can get too complicated at times
    • MABS gives us the possibility to utilize emergence to find possible solutions
  • Agent evolution
    • Using Genetic Algorithms/Genetic Programming to simulate an agent's DNA, and let the agent colony evolve to achieve some objective
    • The objective does not have to be reproduction ... it can be any useful objective function

GPU Computing

  • Algorithms
    • Linear Algebra
    • Fast-Fourier-Transformations
    • Nqueens, Sudoku, Wator, ...
    • Sorting Algorithms
    • Compression
    • Encryption, XML Parsing, Regular Expression Parsing
    • Monte Carlo, Ray Tracing, NBody
    • Fractals
    • Fluids, Molecular Modeling
    • Statistics (PCA)
    • Logic Simulation
    • Anti-Virus Engine
    • Image Processing
    • Speech recognition
    • Hidden Markov Models
    • Graphs
  • Project Idea Mines
    • Benchmarks
      • NAS Parallel Benchmarks
      • SHOC, Rodinia
      • PARSEC, PLASMA
      • HPC Challenge
      • Paraboil Benchmark suite
      • Alpbench, Biobench, Parkbench, Mediabench, Minebench, Bioparallel
      • Pjbench
    • CUDA Showcase

Multi-Agent Systems and GPU Computing

  • Artificial Neural Networks (ANN), Genetic Algorithms (GA) and GPUs
    • Metric-based learning in ANNs
    • Machine Learning meets evolution :)
Further ideas are welcome.

Rules

The final grade will be calculated by the performance of each student in the projects (40%), a final report (25%) and the presentations (5% startup, 10% progress, 20% final).

Checklists for students

  • All presentations
    • stay in time! this is one of the most crucial criterias in the academic sector, as well as in the industry. ;)
    • be able to reason for your decisions. we will ask questions.
  • Startup presentation
    • important:conway the message: what project did you chose? what is the problem?
    • introduce the problem domain
    • describe / understand the problem. why is this a problem?
    • identify possible approaches to solve the problem
    • list your success criterias
  • Progress presentation
    • important:demonstrate some progress. demonstrate that you have a resonable plan for the rest of the seminar
    • describe the infrastructure you evaluated / chose: Programming Language, Tools, Libraries, ...
    • discuss the approach you chose: related work, papers, algorithms you base your work on, ...
    • present what you achieved so far
    • list the struggles that you had and further challenges that you identified
    • you may refine the problem description and the success criterias in this talk
  • Final presentation
    • important:demonstrate what you did
    • demonstrate your solution
    • present evaluation results
    • review the project phase: your plan, the steps you took, ...
    • identify the contributions of each group member. they should be able to answer questions related to their contributions
    • provide a conclusion for yourselves. what did you expect / learn in the seminar? what did surprise you? what was the biggest struggle? ...
    • feedback of the seminar would be nice
  • Report
    • important:report what you did in the seminar.
    • distingushed chapters for every project team member. identify the contributions of each one
    • instructions to set up and run your code
    • problem domain, problem description, possible approaches, chosen approach, steps towards the solution, implementation (programming language, libraries, tools), evaluation, conclusion. discuss each descision.
  • Project
    • important:give us all the code
    • assume that we install and run it
    • it should be as understandable as possible: "good quality", elegant, ...