Themen im Seminar 32 247: "Parallelisierung sequentieller Programmcodes" 

Organisatorisches

·         Das Seminar findet in zwei Blöcken am ZIB in Dahlem (Anfahrt) statt:

·         T1: Montag, den 26.05.2008 ab 10:15 (s.t) am ZIB, Hörsaal, (Eingang Rundbau).

·         T2: Freitag, den 06.06.2008 ab 10:15 (s.t) am ZIB, Seminarraum 2006, (Eingang Rundbau, gleich neben Hörsaal).

·       Vorträge:

·       Spätestens eine Woche vor dem Vortrag sollen die fertigen Folien der Präsentation uns zugeschickt werden.

·         Die Vorträge können wahlweise auf deutsch oder auf englisch vorbereitet und durchgeführt werden. Die Länge eines Vortrages (inklusive Fragen) soll zwischen 45 und 60 Minuten betragen.

·         Die Vorträge werden gegenseitig beurteilt, und die Gewinner erwartet der erwähnte Sonderpreis. Die Bewertungen bitte spätestens eine Woche nach dem jeweiligen Termin hier eintragen (die Geheimtokens werden während der Veranstaltung ausgeteilt).

·         Bei der Vorbereitung können die Tipps für Vorträge nützlich sein.

·         Bitte die Folien (pdf oder ppt) uns direkt nach dem Vortrag zuschicken, diese werden ins Web eingebunden.

·         Die Ausarbeitung kann bis zum 1.10.2008 nachgereicht werden (mind. 8 Seiten bei einer Person, mind. 12 Seiten bei zwei Personen).

·         Hier sind die Links zu den eingereichten Folien und zu den Ausarbeitungen.

·         Ein Artikel zu diesem Thema von Economist (Mai 2008).

·         Offizielle Veranstaltungsseite: http://www.zib.de/reinefeld/HU/2008_SS_Parallelisierung_sequentieller_Programmcodes/index.html

·         Der Vortrag zum Thema „spez-1“ von Herrn Stefan Klumpp wurde in der gegenseitigen Bewertung zu dem besten Vortrag gewählt. Glückwünsch!

·         Die Tabelle mit allen Bewertungen findet man hier (comma separated values, anonymisiert): Tabelle

Referenten und Termine:

Vorname

Name

Thema

Termin

Abdulhakim

Kaya

fund-1

T1

Christoph

Waschke

fund-2

T1

Volker

Grabsch

fund-3

T1

Yves

Radunz

fund-3

T1

Robert

Maier

fund-4

T1

Michael

Berlin

fund-4

T1

Peter

Hagemann

fund-5

T1

Thomas

Schüttler

prog-1

T1

David

Menger

prog-1

T1

Thomas

Kuhlmeyer

prog-2

T1

Antoniya

Georgieva

prog-2

T1

Christoph

Jacob

prog-3

T2

Bert

Münnich

prog-3

T2

Stephan

Grund

prog-4

T2

Mathias

Körner

prog-5

T2

Erik

Neumann

prog-5

T2

Jan

Birkholz

prog-6

T2

Stefan

Klumpp

spez-1

T2

Monika

Domanska

spez-2

T2

Stefan

Curow

spez-2

T2

Frank

Bicking

spez-4

T2

Nico

Kruber

spez-4

T2

Themen

 

Motivation und Grundlagen (fund)

1. The Landscape of Parallel Computing Research: A View from Berkeley (Teil 1)

·         Als Motivation Artikel: Automatic parallelization aus Wikipedia, http://en.wikipedia.org/wiki/Automatic_parallelization

·         Dazu Kapitel 1 bis 3 und ggf. dort zitierte Literatur aus

·         Krste Asanovic et al, (Titel oben), University of California at Berkeley, Technical Report No. UCB/EECS-2006-183, http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-183.html

2. The Landscape of Parallel Computing Research: A View from Berkeley (Teil 2)

·         Kapitel 4 bis 8 und ggf. dort zitierte Literatur

·         Krste Asanovic et al, (Titel oben), University of California at Berkeley, Technical Report No. UCB/EECS-2006-183, http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-183.html

3. Amdahl’s Law und Gustafson’s Law

·         Folgende drei Artikel:

·         Wikipedia: Amdahl’s Law, http://en.wikipedia.org/wiki/Amdahl%27s_law

·         John L. Gustafson, Reevaluating Amdahl’s Law, CACM, 31(5), 1988, pp. 532-533, http://www.scl.ameslab.gov

·         Yuan Shi,  Reevaluating Amdahl’s Law and Gustafson’s Law, http://www.cis.temple.edu/~shi/docs/amdahl/amdahl.html

4. Latency Lags Bandwidth / Petascale Computational Systems

·         Folgende zwei Artikel

·         David A. Patterson, Latency Lags Bandwidth, COMMUNICATIONS OF THE ACM, October 2004/Vol. 47, No. 10

·         Gordon Bell, Jim Gray and Alex Szalay, Petascale Computational Systems: Balanced CyberInfrastructure in a Data-Centric World, September 2005, http://research.microsoft.com/~gray/papers/petascale%20computational%20systems.pdf

5. KILO-INSTRUCTION PROCESSORS – OVERCOMING THE MEMORY WALL

·         Artikel und ggf. dort zitierte Literatur

·         Adrián Cristal et al, KILO-INSTRUCTION PROCESSORS – OVERCOMING THE MEMORY WALL, IEEE MICRO, MAY–JUNE 2005, pp. 48-57.

 

Programmiermodelle und Architekturen (prog)

1. Übersicht über Modelle für paralleles Programmieren

·         Vorstellung der Modelle aus dem folgenden Artikel

·         Wikipedia, Parallel programming model, http://en.wikipedia.org/wiki/Parallel_programming_model

2. Paradigmen für paralleles Programmieren

·         Artikel und ggf. dort zitierte Literatur

·         Luis Silva and Rajkumar Buyyaz, Parallel Programming Models and Paradigms, in Rajkumar Buyya (editor), High Performance Cluster Computing: Programming and Applications, Vol. 2, Prentice Hall PTR, NJ, USA, 1999, www.buyya.com/cluster/v2chap1.pdf

3. Map-Reduce Framework von Google

·         Artikel und ggf. weiterführende Literatur

·         Jeffrey Dean and Sanjay Ghemawat, MapReduce: Simplified Data Processing on Large Clusters, http://labs.google.com/papers/mapreduce.html

4. Data Parallel Algorithms

·         Artikel und ggf. dort zitierte Literatur

·         W. Daniel Hillis and Guy L. Steele, COMMUNICATIONS OF THE ACM, December 1986, Vol. 29, No. 12

5. Parallelisierung von Programmen in Fortran

·         Hier sollen die Quellen selbständig erarbeitet werden

6. Spekulatives Multithreading

·         Folgende Präsentation sowie weiterführende Artikel aus http://pages.cs.wisc.edu/~sohi/talks.html

·         Gurindar S. Sohi, Speculative Multithreading: from Multiscalar to MSSP, keynote at the MTEAC workshop, December 2001, ftp://ftp.cs.wisc.edu/sohi/talks/2001/mteac01.pdf

7. Vergleich von message passing und shared memory Modellen

·         Artikel und ggf. zusätzliche Literatur

·         Alexander C. Klaiber, Henry M. Levy, A Comparison of Message Passing and Shared Memory Architectures for Data Parallel Programs, Proceedings of the 21th International Symposium on Computer Architecture, 1994, http://citeseer.ist.psu.edu/klaiber94comparison.html

8. Speculative Multi-Threading Computer Architecture

·         Artikel aus http://suif.stanford.edu/research/speculate.html, insbesondere:

·         J. Oplinger, D. Heine and M. S. Lam, In Search of Speculative Thread-Level Parallelism, Proc. 1999 International Conference on Parallel Architectures and Compilation Techniques (PACT'99), Newport Beach, CA, October 1999,

 

Spezielle Themen (spez)

1.    Multi-core Games

·         Hier müssen die Quellen selbständig erarbeitet werden, aber auf jedem Fall Teile der folgenden Präsentation nutzen

·         Tim Sweeney (Epic Games), The Next Mainstream Programming Language: A Game Developer’s Perspective, POPL 2006, www.st.cs.uni-sb.de/edu/seminare/2005/advanced-fp/docs/sweeny.pdf

2.    Das parallele Rechnen in Matlab

·         Artikel und ggf. weiterführende Literatur

·         The MathWorks, Inc, MatLab Parallel Computing Toolbox, http://www.mathworks.com/products/distribtb/

3.    Affine Transformations for Optimizing Parallelism and Locality

·         Artikel aus http://suif.stanford.edu/research/affine.html, insbesondere

·         A. W. Lim, S.-W. Liao and M. S. Lam, Blocking and Array Contraction Across Arbitrarily Nested Loops Using Affine Partitioning, Proc. ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, June, 2001.

4.    Interpreting the Data: Parallel Analysis with Sawzall

·         Artikel und ggf. weiterführende Literatur

·         Rob Pike, Sean Dorward, Robert Griesemer, Sean Quinlan, Interpreting the Data: Parallel Analysis with Sawzall, http://labs.google.com/papers/sawzall.html

5.    Algorithms for Distributed Data Stream Mining

·         Artikel und ggf. weiterführende Literatur

·         K. Bhaduri, K. Das, K. SivaKumar, H. Kargupta, R. Wolff, R. Chen. Algorithms for Distributed Data Stream Mining. Kapitel 14 in Data Streams: Models and Algorithms, Charu Aggarwal (Editor), Springer. pp. 309-332. 2006.