Algorithm Engineering - Grafikprozessoren

Links

Sommersemester 2010

Algorithm Engineering - Graphikprozessoren

 

Allgemeines

  • Betreuer: Dennis Luxen, Vitaly Osipov, Dennis Schieferdecker
  • Anmeldung & Vorbesprechung: Dienstag, 13. April 2010, 09:45 in SR 211, Informatikgebäude am Fasanengarten (50.34)
  • Vorbesprechung Projektphase: Mittwoch, 09. Juni 2010, 09:45 in SR 211, Informatikgebäude am Fasanengarten (50.34)
  • Teilnahme: Die Teilnehmerzahl ist voraussichtlich auf zwölf Personen beschränkt.

 

Aktuelles

  • 31. Mai 2010: Termin für Projektvorbesprechung wegen Krankheit verschoben auf Mittwoch, 09. Juni 2010
  • 28. Mai 2010: Abgabe von Übungsblatt 5 und 6 auf Freitag, 04. Juni 2010 verschoben
  • 25. Mai 2010: Übungsblatt 6 online gestellt
  • 18. Mai 2010: Übungsblatt 5 online gestellt
  • 14. Mai 2010: Termin und Ort für die Vorbesprechung der Projektphase festgelegt
  • 14. Mai 2010: Korrektur an Übungsblatt 4 (Definition von Delta in Aufgabe 2b geändert)
  • 11. Mai 2010: Übungsblatt 4 online gestellt
  • 04. Mai 2010: Übungsblatt 3 online gestellt
  • 22. April 2010: Bitte alle in der Mailingliste anmelden.
  • 20. April 2010: Vitaly Osipov ist diese Woche doch nicht auf Dienstreise.
  • 20. April 2010: Die Abgabefrist für Übungsblatt 1 ist bis Sonntag, den 25. April und für Übungsblatt 2 bis Montag, den 3. Mai verlängert worden. Das dritte Übungsblatt gibt es entsprechend erst am 4. Mai.
  • 20. April 2010: Übungsblatt 2 online gestellt
  • 19. April 2010: Korrektur an Übungsblatt 1 (obere Grenze für n in Aufgabe 3 herabgesetzt)
  • 16. April 2010: Bereich Übungsblätter, Literatur erweitert. Bereiche Projekte und Hinweise eingeführt.
  • 14. April 2010:  Wegen einer Konferenzreise wird das erste Treffen der Gruppe von Vitaly Osipov auf Anfang Mai verschoben.
  • 14. April 2010: Die vollständigen Domainnamen unserer Rechner lauten i10pc*.iti.kit.edu für das Anmelden von außerhalb
  • 13. April 2010: Übungsblatt 1 online gestellt
  • 23. Februar 2010: Praktikumseite online gestellt

 

Hinweise

  • Wer eine eigene interessante Idee für ein Projekt hat, kann sich damit gerne an uns wenden.
  • Der zweite Rechner mit GPGPU Karte verzögert sich wegen Lieferproblemen voraussichtlich bis Mitte nächster Woche.
  • Die Betreuung der Gruppe von Vitaly Osipov wird meistens in Englisch geführt. Die Studenten, die dieser Gruppe zugeteilt sind aber kein Englisch sprechen, sollen sich an ihn wenden, um einer anderen Gruppe zugeteilt zu werden.

 

Inhalt

Seit ein paar Jahren sind Graphikprozessoren (GPUs) flexibel genug und es existieren vor allem Programmierschnittstellen, um ihre beachtliche Rechenleistung für allgemeinere Aufgaben als 3D-Graphik zu verwenden. Im allgemeinen handelt es sich bei GPUs um SIMT (Single Instruction Multiple Threads) Prozessoren mit weit über 100 parallelen Recheneinheiten. Meist werden sie für einfach zu parallelisierende Aufgaben wie das Berechnen von Matrizen in Simulationen oder das Bestimmen von Schlüsseln benutzt. Aber
man kann auch klassische Fragestellungen aus der Algorithmik wie Sortieren effizient auf dieser Art Prozessor umsetzen. Grafikkarten erlauben je nach Problemstellung
sehr hohe Beschleunigungen. Faktoren um die 10 bis 20 sind dabei nicht unüblich.
In diesem Praktikum wird Hardware von Nvidia und damit CUDA als API verwendet. In der ersten Phase werden CUDA und die algorithmischen Besonderheiten bei der Programmierung von SIMT-Maschinen durch wöchentlichen Übungsblättern (ca. 6 Wochen) erarbeitet. Im zweiten Teil folgt eine Projektphase mit Fragestellungen aus der aktuellen Forschung (z.B. Multiplikation großer dünn besetzter Matrizen, Graphpartitionierung, ...).

 

Voraussetzungen

Voraussetzung für die Teilnahme an diesem Praktikum sind Grundkenntnisse aus den Bereichen Theoretische Informatik und Algorithmentechnik, Interesse am Einarbeiten in neue Themengebiete und Erfahrung im Umgang mit C oder C++. Da die Dokumentation zu CUDA auf englisch vorliegt, sollten entsprechende Englischkenntnisse vorhanden sein. 

 

Organisatorisches

Die Anmeldung für das Praktikum und die Vorbesprechung findet am Dienstag, den 13. April 2010, um 09:45 Uhr in Raum 211 im Informatikgebäude am Fasanengarten (50.34) statt. Projektgruppen können sich bis zu Beginn der Projektphase zusammenfinden. Die Aufteilung der Projekte findet zu Beginn der Projektphase statt. Die Vorbesprechung für die Projektphase findet am 09. Juni 2010, um 09:45 Uhr in Raum 211 im Informatikgebäude am Fasanengarten (50.34) statt. Für weitere Informationen könnt Ihr euch gerne an Dennis Luxen, Vitaly Osipov oder Dennis Schieferdecker wenden.

 

Geplanter Ablauf:

  • Vorbesprechung: 13.04.2010
  • Übungsphase: 13.04.2010 - 01.06.2010
    • wöchentliche Übungsblätter
    • Anfertigung eines Protokolls (ca. 2-4 Seiten)
  • Projektphase: 09.06.2010 - 13.07.2010
    • Vorstellung der Ergebnisse in einem Vortrag am letzten Termin
    • ca. 20 Minuten pro Vortrag + 10 Minuten Diskussion
  • Abgabe der Ausarbeitung: bis 31.07.2010
    • ca. 10 Seiten

 

Ablauf

In der ersten Phase werden wöchentlich Übungsblätter ausgegeben, die einzeln zu bearbeiten sind. Die Bearbeitung kann im Poolraum der Lehrstuhls oder zu Hause erfolgen. Das Ergebnis ist dem jeweiligen Betreuer in Form eines Praktikumsprotokolls abzugeben. Für die zweite Phase werden Gruppen zu je 3 Studenten gebildet, die eines der Projektthemen gemeinsam bearbeiten. Am letzten Termin ist ein Vortrag über die Ergebnisse des Projekts von ca. 20min Länge zu halten. Außerdem ist eine schriftliche Ausarbeitung abzugeben, die das Projekt zusammenfassend beschreibt.
Für die Programmieraufgaben ist C/C++ vorgesehen, für das Anfertigen der Protokolle und der Ausarbeitung LaTeX und für die Präsentation eine frei wählbare Software ( z.B. LaTeX, Powerpoint, ... ).

 

Übungsblätter

Die Übungsblätter werden dienstags ausgegeben und sind bis zum folgenden Montag um 23:59 in Form eines Protokolls abzugeben. Die Abgabe erfolgt durch Einchecken der PDF in das svn-Repository.

  • 13.04.10: Übungsblatt 1 (PDF): Zusatzmaterial (ZIP)  -  korrigiert (19.04.2010)
  • 20.04.10: Übungsblatt 2 (PDF): Zusatzmaterial (ZIP)
  • 04.05.10: Übungsblatt 3 (PDF): Zusatzmaterial (-)
  • 11.05.10: Übungsblatt 4 (PDF): Zusatzmaterial (ZIP)  -  korrigiert (14.05.2010)
  • 18.05.10: Übungsblatt 5 (PDF): Zusatzmaterial (-)
  • 25.05.10: Übungsblatt 6 (PDF): Zusatzmaterial (-)

 

Projekte

Die Vorbesprechung für die Projektphase findet am 01. Juni 2010, um 09:45 Uhr in Raum 201 im Informatikgebäude am Fasanengarten (50.34) statt. Es werden die Projekte vorgestellt, der weitere Ablauf des Praktikums besprochen und Gruppen zu je drei Studenten gebildet. Jede Gruppe erhält ein Projekt, das bis zum Vorlesungsende bearbeitet wird.

  • Projekt 1: Sortierverfahren
    (Betreuer: Vitaloy Osipov)
  • Projekt 2: Volltextsuche
    (Betreuer: Dennis Luxen, Dennis Schieferdecker)

    Hinweis: Testdaten für Projekt 2 sind unter /global_data/cuda_praktikum zu finden, insgesamt ca. 800 MB. Für eine sinnvolle Volltextsuche sollten die Tags aus den HTML Dokumente vor der Verarbeitung entfernt werden.

 

Literatur

[1]: http://developer.nvidia.com/object/cuda\_3\_0\_downloads.html/
Nvidia Dokumentation zu CUDA.

[2]: http://llpanorama.wordpress.com/cuda-tutorial/
Sammlung von Tutorial Links.

 

Material & Links

Vorlagen

[1]: LaTeX Folienvorlage (Stand: 29.10.09)
Vorlage für das LaTeX-beamer Paket im KIT-Stil.

[2]: Powerpoint Folienvorlage
Vorlage für Powerpoint-Folien im KIT-Stil.

[3]: Projektausarbeitungsvorlage
Vorlage für die Ausarbeitung der Projekte im LNCS-Stil.

freie Software

[1]: ipe
Freies Vektorgrafikprogramm unter Linux.

[2]: Microsoft Visio (MSDN AA an der Universität Karlsruhe)
Für Studenten über MSDN-AA frei verfügbares Zeichenprogramm.