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: 13 students
Recommended: experience with Java or C++; Parallel Programming Concepts Lecture
The everincreasing 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 interrequest level parallelism wall and the memory wall. Networksonachip, dynamic memory hierachies, massive dataparallel execution, ... are currently hot research topics and will influence the future of servers and enduser computers, as well as embedded and mobile systems.
With the advent of multicore 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)
 Parallel Computing for Complex Domains  I: Concurrency and Multiagent 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.unipotsdam.de/cyclesofwar)
 Multiagent based strategy for dominating the universe :). Game programing using concurrent agents, and perhaps some winning strategies developed in Game Theory.
 A concurrent Multiagent based framework that makes it possible to implement players using Multiagent 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!)
 Multiagent based Simulation (MABS)
 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
 FastFourierTransformations
 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
 AntiVirus 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
 Optimization / Mathematical Programing
 Genetic Algorithms
 Genetic Programing
 Artificial Neural Networks
 GPU Computing
