Introduction to Parallel Computing

2012-10-09T23:04:00Z

Juliostutz: /* Project 1 */

This is the main page of a graduate-level course in parallel computing being taught in 2012/2 at the Polytechnic Institute [http://pt.wikipedia.org/wiki/IPRJ IPRJ]/UERJ. It is generally useful for programmers at the advanced level in the fields of scientific and multimedia programming.
[[Imagem:Matrix6.png|right|550px]]
== General Info ==
* Instructor: prof. [http://www.lems.brown.edu/~rfabbri Ricardo Fabbri], Ph.D. Brown University
* Meeting times: Tues 12:30pm-2pm, Thursdays 2:20pm - 4pm
* Evaluation criteria: 1 quizz at the end of the term (60%), plus practical projects (40%).
* Forum for file exchange and discussion: [http://uerj.tk uerj.tk]

=== Pre-requisites ===
* Linux - intermediate to advanced (will be reviewed as needed) - read [[Literatura recomendada pela equipe|Recommended Reading]]
* C/C++ - intermediate to advanced (will be reviewed) - read [[Literatura recomendada pela equipe|Recommended Reading]]
** [[Configuring Ubuntu for Programming]]
* Basic understanding of computer architecture - read "Computer Systems: A Programmer's perspective" listed at [[Literatura recomendada pela equipe|Recommended Reading]].

== Approximate Content ==

The course focuses on software techniques for parallel computing. We are aiming at a comprehensive treatment on different types of practical parallel programming techniques
* process-oriented parallel programming
* thread programming/thread safety
* single-core vector instructions
* multi-processor and multi-core programming
* mapreduce/hadoop
* MPI
* Cuda/OpenCL

Each of the above techniques would merit a course of their own, as done in many of the best universities. Therefore we aim at attaining a practical familiarity with each, in the first half of the course, and we will specialize in the later part of the course as to help the students' graduate research.

== Main Resources ==

* Textbooks
** 1st part of the course: [http://kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook.html "Is Parallel Programming Hard, and, if so, what can you do about it?" - Paul E. McKenney / IBM (editor)].
** For MPI: "An Introduction to Parallel Programming" , by Peter Pacheco[http://books.google.com.br/books?id=SEmfraJjvfwC&printsec=frontcover&hl=pt-BR&source=gbs_ge_summary_r&cad=0#v=onepage&q&f=false]
** For Cuda/OpenCL: Programming Massively Parallel Processors: A Hands-On Approach[http://books.google.com.br/books?id=qW1mncii_6EC&printsec=frontcover&hl=pt-BR#v=onepage&q&f=false]
** General textbook: A. Grama, A. Gupta, G. Karypis, V. Kumar, Introduction to Parallel Computing, Second Edition, Addison-Wesley, 2003.
** Algorithms-oriented textbook: Algorithms: sequential, parallel, and distributed, Kenneth A. Berman, Jerome L. Paul
*** For more theoretical info, see the chapter on parallel algorits in Cormen's classical algorithms book.
* Mapreduce, GFS, and Bigtable:
** Papers from Google
** http://code.google.com/edu/parallel/mapreduce-tutorial.html
** Wikipedia
** Hadoop documentation
* Presentations from IBM and Intel: Cilk, etc.
** http://software.intel.com/en-us/videos/channel/parallel-programming
* Wikipedia pages
** http://en.wikipedia.org/wiki/Vectorization_%28parallel_computing%29
** http://en.wikipedia.org/wiki/Mapreduce
** http://en.wikipedia.org/wiki/Hadoop
* Rice lecture notes on Parallel Computing [http://www.clear.rice.edu/comp422/lecture-notes/index.html]
* Other Resources
** http://www-users.cs.umn.edu/~karypis/parbook/
** http://www.cse.iitd.ernet.in/~subodh/courses/CSL860/
** Running Hadoop On Ubuntu Linux Multi and Single Node Cluster [http://www.michael-noll.com/tutorials/running-hadoop-on-ubuntu-linux-single-node-cluster/]

=== Lectures ===

''' NOTE: There will be no lectures from Oct 4 - Oct 19 2012'''

==== Partial listing & Tentative Outline ====
# Overview of parallel computing: https://computing.llnl.gov/tutorials/parallel_comp/
# Review of Linux:
## See the book Running Linux from the [[Literatura_recomendada_pela_equipe| Recommended Reading]]
# Review of C/C++ (finished 28/Aug)
# Fundamental programming techniques: processes and threads
## Read The Unix Programming Environment for some classic multi-process programming[http://wiki.nosdigitais.teia.org.br/Literatura_recomendada_pela_equipe]
## What is a process: http://linuxgazette.net/133/saha.html
## 30/Aug: We'll be following the McKenney Book, ch 3 at the lab.
## Up to (and including) 18/Sept: We followed McKenney's code samples for counting algorithms and his Threading API in detail
### What is variable alignment: [http://www.songho.ca/misc/alignment/dataalign.html] [http://gcc.gnu.org/onlinedocs/gcc-4.0.4/gcc/Type-Attributes.html]
### How to determine the cache line size for your machine: [http://stackoverflow.com/questions/794632/programmatically-get-the-cache-line-size]. This will give you better results for threading algorithms.
### Install some documentation useful for POSIX threading: sudo apt-get install glibc-doc manpages-posix-dev
## 20/Sept: Finished statistic counters and showed how to read assembly language generated by GCC, and how to disassemble binary objects
## 25/Sept: Finished theoretical thread content for the course: up until ch. 5 of McKenney's Book + Semaphores + Thread Safety.
### Homework 2 (see below)
# Cuda/OpenCL (02/Oct)
## Project 1 handout (see below) due Oct. 23
# Mapreduce/Hadoop
# MPI

== Homework ==
=== Homework 1 ===
Our insitute is planning on buying a supercomputer. Therefore, our first homework will consist on studying these systems in detail.

* The class shall be divided into groups of 2 people.
* Each group must pick one top 500 (http://www.top500.org) supercomputer and write on this wiki:
** Team number:
** Supercomputer:

* Each class will start with a 20min presentation from a '''random''' group (or a volunteer group).
* A handout must also be provided on Tue August 28
* Your project must not be a plain copy from wikipedia!

Contents of the presentation and report
* Overview of the system
* Glossary of terms
* '''How to program for the system'''
* Software infrastructure
* How does this differ from a conventional cluster.

'''Groups'''

* Team 1: Julio Stutz & Joel Sanchez
** Supercomputer: '''Tupã''' (Inpe/Brazil) ([http://www.lems.brown.edu/~rfabbri/stuff/parallel-computing/supercomputers/julio-sanchez/tupa4-supercomputer-report.pdf report]) ([http://www.lems.brown.edu/~rfabbri/stuff/parallel-computing/supercomputers/julio-sanchez/tupa4-supercomputer-presentation.pdf slides])
* Team 2: Claudir Oliver & Luiz Rosalba
** Supercomputer: '''Tianhe-1A''' (China) ([http://www.lems.brown.edu/~rfabbri/stuff/parallel-computing/supercomputers/claudir-luiz/tian-he-report.pdf report]) ([http://www.lems.brown.edu/~rfabbri/stuff/parallel-computing/supercomputers/claudir-luiz/tian-he-presentation.pdf slides])
* Team 3: Mateus Guida
** Supercomputer: '''Sequoia''' (Laborátório Nacional Lawrence Livermore - Califórnia - EUA) ([http://www.lems.brown.edu/~rfabbri/stuff/parallel-computing/supercomputers/mateus-guida/sequoia-supercomputer-report.pdf report]) ([http://www.lems.brown.edu/~rfabbri/stuff/parallel-computing/supercomputers/mateus-guida/sequoia-supercomputer-presentation.pdf slides])
* Team 4: Lyvia Aloquio & Stella Oggioni
** Supercomputer: '''Grifo04''' (PETROBRAS/Brazil)
* Team 5: Ricardo Dias
** Supercomputer: '''Mole-8.5''' (Institute of Process Engineering, Chinese Academy of Sciences/China) ([http://www.lems.brown.edu/~rfabbri/stuff/parallel-computing/supercomputers/ricardo/mole-supercomputer-report.pdf report]) ([http://www.lems.brown.edu/~rfabbri/stuff/parallel-computing/supercomputers/ricardo/mole-supercomputer-presentation.pdf slides])
* Team 6: Frederico Santos
** Supercomputer: '''Helios''' (International Fusion Energy Research Centre (IFERC), EU(F4E) - Japan Broader Approach collaboration) ([http://www.lems.brown.edu/~rfabbri/stuff/parallel-computing/supercomputers/frederico-santos/helios-report.pdf report])
* Team 7: Thiago
** Supercomputer: '''Pleiades''' - NASA/Ames Research Center/ NAS - United States.

=== Homework 2: limit counters ===
Describe the limit counter implementations of sec. 4.3 in McKenney's Book, answering:
# list and explain the advantages of each counter
# explain the main concepts of each method in your words
Due date: Oct 1 (was: Sept 27)

=== Project 1 ===
* The class will be divided into interest groups
* The interest groups will each pick one of the following technologies or else propose another one of their liking.
** mapreduce/hadoop
** MPI
** Cuda/OpenCL
** Hybrid technologies (Distributed + Cuda)
** Languages designed for concurrency: [http://golang.org Google Go], Erlang, etc.
** Programming for the Playstation 3 parallel architecture[http://groups.csail.mit.edu/cag/ps3/index.shtml]
** Proposta : OPENGL/GLSL
* The project will consist in a series of presentations by the group members individually.
* Grade will be asigned to each presentation individually

'''Groups to Project 1'''

* MPI: Claudir Oliveira (Apresentacao: 23/10/2012)
* Hybrid technologies (Distributed + Cuda): Ricardo Dias
* Cuda/OpenCL: Joel Sanchez
* OPENGL/GLSL : Luiz Rosalba ( se aceito )
* mapreduce/hadoop : Julio Stutz

=== Project 2 ===
* This project will consist on a practical programming problem from the student's research. The student is required to describe a problem from his research and present a parallel implementation of some aspect of it.
* This will be evaluated through actual code and acompanying monograph.

=== Class exercies ===
# In-class assignment (extra .1 in the final test): Compare 3 different implementation of statistic counters: array of per-thread variables, eventuallly consistent counter and GCC __thread variables
## Only '''Julio Stutz''' scored the extra +0.1 on the final exam.

=== Keywords ===
Portuguese: Programação Paralela, Introdução à Computação Paralela

[[Category:Lab Macambira]] [[Category:IPRJ]]

Pontão Nós Digitais - Contribuições do usuário [pt-br]

Introduction to Parallel Computing