Exotic Methods in Parallel Computing

Summer term 2012
Frank Feinbube, Fahad Khalid
Dr. Peter Tröger

Your Final Presentations (15 minutes) are at:
26th of July, 01:00 pm
26th of July, 03:45 pm
27th of July, 01:00 pm
Details about our expectations can be found below in the Checklists section.

Mind the report deadline as well!

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 hindrances to scalable performance: The power wall, the inter-request level parallelism wall and the memory wall. Networks-on-a-chip, dynamic memory hierarchies, 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 research. 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)
  • Parallel Computing for Complex Domains - I: Concurrency and Multi-agent Systems(Slides)
  • Parallel Computing for Complex Domains - II: Optimization and Learning (Slides)
  • GPU Computing (Slides)

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.2012 offical (=debatable) enrolment due date
23.05.2012 Project Proposal*
25.05.2012 Project Approval
04.06.2012 Inital Presentation
18.06.2012 Progress Presentations
tba. Final Presentations (see doodle)
08.08.2012 Hand 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

Complex Domains

  • 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.
      • A concurrent Multi-agent based framework that makes it possible to implement players using Multi-agent strategies.
      • A parallel algorithm for optimizing a player's combat strategy. Genetic Algorithms, Particle Swarm Optimization, Ant Colony Optimization etc. can be used for optimization. Other suitable algorithms can be used as well.
  • Artificial Neural Networks
    • A parallel Artificial Neural Network Implementation
  • Optimization
    • Parallel Genetic Algorithm
    • Parallel version of any other optimization algorithm (e.g. Particle Swarm Optimization, Ant Colony Optimization etc.)
  • Cellular Automata
    • Use Genetic Algorithms to figure out interesting configurations (e.g. for the Game of Life)
      • 'n' most stable configurations that maximize life expectancy
      • Configurations that create interesting graphical patterns
    • Use Genetic Algorithms to solve "Majority On" and "Majority Off" problem for 2D Cellular Automata. Design a parallel framework for Genetic Algorithms over 2D Cellular Automata.
      • If the initial configuration has majority cells in the ON state, all cells should change state to ON
      • If the initial configuration has majority cells in the OFF state, all cells should change state to OFF
      • A decentralized algorithm for determining the global state of the system. No central decision making (emergence!)
  • Multi-agent based Simulation (MABS)
    • A MABS of your choice
  • 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
  • Artificial Neural Networks (ANN), Genetic Algorithms (GA) and GPUs
    • Optimize the weights for ANN using GA
    • Machine Learning meets evolution :-)

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
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, ...

Literature