Exotic Methods in Parallel Computing
Summer term 2012Dr. 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 |
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.
- Multi-agent based strategy for dominating the universe :-).
Game programing using concurrent agents, and perhaps some
winning strategies developed in Game Theory.
- 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!)
- Use Genetic Algorithms to figure out interesting
configurations (e.g. for the Game of Life)
- 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
- Benchmarks
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
- Ted Ralphs. Introduction to Mathematical Programing (lecture slides)
- Genetic Algorithms
- Marek Obitko. Introduction to Genetic Algorithms (online tutorial)
- Luke, S. Essentials of Metaheuristics. 2011 (book)
- Genetic Programing
- John R. Koza. Introduction to Genetic Programming (tutorial)
- Artificial Neural Networks
- Kröse, B.J.A. and Smagt, P.P. van der. An Introduction to Neural Networks (lecture book)
- Christos Stergiou and Dimitrios Siganos. Neural Networks (report)
- GPU Computing