MMIX Programmieren für Fortgeschrittene: Sommer 2012

Ort und Zeit

Vorträge:
Mittwoch, 13:30-15:00, Raum R 0.009

Praktikum:
Mittwoch, 13:30-15:00, Raum R 1.009
Mittwoch, 15:15-16:45, Raum R 1.009

Course Management

Dieser Kurs verwendet redmine für die Verwaltung des Kurses.

Inhalt

Der Prozessor MMIX wurde von Donald E. Knuth entworfen um in seinem mehrbändigen Werk "The Art of Computer Programming" (TAOCP), dort wo dies nötig ist, Algorithmen auf dem Niveau von einzelnen Maschineninstruktionen darstellen und diskutieren zu können. TAOCP ist das Standardwerk der Informatik, das man konsultiert, wenn man für ein gegebenes Problem einen optimalen Algorithmus sucht. Hier werden alle Alternativen dargestellt, diskutiert, evaluiert und mathematisch analysiert. Die theoretische Abhandlung ist vollständig und die praktische Implementierung kommt nicht zu kurz. Eine Beschäftigung mit TAOCP ist also nicht nur unterhaltsam und spannend sondern auch lehrreich.

In den ersten drei Bänden von TAOCP verwendete Donald Knuth den Prozessor MIX, der aber inzwischen durch die Entwicklung völlig überholt ist. Nach der Fertigstellung von MMIX, kam zum ersten mal im Jahr 2011, ein neuer Band, Volume 4A, von TAOCP heraus, der den Prozessor MMIX verwendet. Es bleibt die Aufgabe in den vorhandenen Bänden 1 bis 3, die MIX Programme durch äquivalente MMIX Programme zu ersetzen. Für diese Aufgabe wurde von Donald E. Knuth und Vladimir G. Ivanovic die Gruppe der MMIXmasters ins Leben gerufen. Nach einem guten Start fiel die Gruppe in einen Dornröschenschlaf. Seit September 2011 ist nun die MMIXmasters Website zusammen mit der MMIX Home Page an die Hochschule München umgezogen und ich habe mir das Ziel gesetzt diese doch überschaubare Aufgabe in 2012 abzuschließen. Einen ersten Anlauf dazu werden wir gemeinsam in diesem FWP Fach unternehmen.

Die Liste der noch zu schreibenden Programme findet man auf der MMIXmasters Seite. Davon wollen wir im diesem Kurs einen (oder je nach Teilnehmerzahl zwei) der folgenden Themenblöcken bearbeiten:

  • Datenstrukturen
    • Doubly Linked Lists: Elevator Simulation
      TAOCP, Vol. 1, Section 2.2.5 einschließlich Exercises 8 und 9,
      ca. 300 lines of MIX Code.
    • Sparse Matrices: Pivot Step
      TAOCP, Vol. 1, Section 2.2.6 und Exercise 15,
      ca. 100 lines of MIX Code.
    • Binary Trees: Symbolische Ableitungen
      TAOCP, Vol. 1, Section 2.3.2 Programm D und Exercise 13,
      ca. 400 lines of MIX Code.
    • Dynamic Allocation and Garbage Collection
      TAOCP, Vol. 1, Section 2.5 und Exercises 13, 15, 16, 27, 28 und 34,
      ca. 200 lines of MIX Code.
  • Seminumerical Algorithms
    • Floating Point Arithmetic: Add, Subtract, Normalize, Multiply, Divide, Mod, Conversion, Compare
      TAOCP, Vol. 2, Section 4.2.1 Programms A, M und Exercises 14, 15 und 17,
      ca. 200 lines of MIX Code.
    • Multiple Precission Integer Arithmetic: Add, Subtract, Multiply, Divide
      TAOCP, Vol. 2, Section 4.2.1 Programms A, S, M, D und Exercises 3, 8, 13, 25 und 26,
      ca. 200 lines of MIX Code.
  • Sorting
    • Quicksort (partition exchange sort)
      TAOCP, Vol. 3, Section 5.2.2 Programm Q und Exercise 55,
      ca. 100 lines of MIX Code.
    • Radix Exchange Sort (partition exchange sort)
      TAOCP, Vol. 3, Section 5.2.2 Programm R,
      ca. 100 lines of MIX Code.
    • Straight Selection Sort
      TAOCP, Vol. 3, Section 5.2.3 Programm S und Exercise 8,
      ca. 50 lines of MIX Code.
    • Heap Sort
      TAOCP, Vol. 3, Section 5.2.3 Programm H,
      ca. 30 lines of MIX Code.
    • List Merge Sort
      TAOCP, Vol. 3, Section 5.2.4 Programm L,
      ca. 50 lines of MIX Code.
    • Radix List Sort
      TAOCP, Vol. 3, Section 5.2.5 Programm R,
      ca. 50 lines of MIX Code.
  • Searching
    • Sequential Search
      TAOCP, Vol. 3, Section 6.1 Programm S, Q, Q' und Exercise 3,
      ca. 50 lines of MIX Code.
    • Binary Search
      TAOCP, Vol. 3, Section 6.2.1 Programm B,
      ca. 20 lines of MIX Code.
    • Trie Search
      TAOCP, Vol. 3, Section 6.3 Programm T,
      ca. 10 lines of MIX Code.
    • Chained Hashing
      TAOCP, Vol. 3, Section 6.6 Programm C and Exercise 12,
      ca. 40 lines of MIX Code.
    • Open Hashing
      TAOCP, Vol. 3, Section 6.6 Programm L and D,
      ca. 50 lines of MIX Code.
Bei der Auswahl spielt natürlich die Interessenlage der Teilnehmer eine Rolle.

Veranstaltungsformat

Die Veranstaltung fokussiert sich auf ein gemeinsames Projekt, wie oben beschrieben. Wir setzen das Projektmanagement-Tool Redmine ein. Als Ergebnis erwarte ich eine Reihe von MMIX Programmen zu den in TAOCP gegebenen Algorithmen zusammen mit einer guten Dokumentation.

Im Rahmen des Projekts werden kleine Gruppen die Verantwortung für einzelne Algorithmen übernehmen. Der Algorithmus und seine Besonderheiten soll in einem kurzen Vortrag vorgestellt werden. Es werden Testcases erstellt und anschließend wird der Algorithmus implementiert. Nach der Implementierung erfolgt eine Analyse, die die Möglichkeiten zur Optimierung ausleuchten soll.

Die einzelnen Arbeitsschritte und Ergebnisse werden jeweils in Kurzvorträgen präsentiert. Für jeden Algorithmus wird auch eine Abschlussdokumentation erstellt, die - zunächst nur im WWW - veröffentlicht wird.

Die Benotung erfolgt auf der Basis der Vorträge (40%) und der Dokumentation (60%).