Projektanforderungen

Hier stehen die Anforderungen für unser Schleifenparallelisierungstool. Die momentane Version ist noch nicht sehr konkret, sondern nur eine Stoffsammlung, aufgeschrieben in Brainstorming-Art. Jeder Punkt ist diskussionsfähig!

Bereiche:

Input-Sprachen: wahlweise (automatisch erkennbar?)
- for endfor oder end (Systoliker-Notation I)
- <- ... -> (Systoliker-Notation II)
- do enddo oder od (Banerjee)
- Fortran-Notation
- C-Notation
- Neu: Ungleichungssysteme und Abh.Vektoren
Output-Sprachen:
- analog zu Input, wobei manchmal parfor reicht und manchmal zwischen doall und doaccross zu unterscheiden ist
- mit und ohne Synchronisation/Kommunikation
verschiedene Benutzervorgaben für Schedule:
- keine
- einfache Restriktionen, z.B. t(i+1)>t(i)-2
- Schedule ganz oder teilweise vom Benutzer
- Folge: Schedule muß überprüft werden und ggfs. ein andere, aber korrekter vorgeschlagen werden
- Schedule-Auswahl oder Heuristik bei mehreren optimalen Lösungen
verschiedene Benutzervorgaben für den Rest der Trafo-Matrix:
- keine, damit Heuristiken nötig (min. Prozessorenzahl, nur Nachbarschaftskommunikation, min. Kommunikationszahl,...)
- "ich will eine DOALL-Schleife als 2. Schleife" (nicht immer möglich, also Test)
- Distanzvektoren möglichst klein machen (was folgt daraus?)
Extras:
- Matrixoperationen als ein Tool nach außen verfügbar machen
- Neu: Fourier-Motzkin nach außen verfügbar machen--damit ist (ohne Rücksicht auf Abhängigkeiten) eine Polyedertransformation durchführbar
- Neu: Test auf Single-Assignment
- Status-Fenster aller vom Benutzer gemachten Einschränkungen und seiner getroffenen Entscheidungen
- Speicherbarkeit von jedem Stand der Transformation und von allen Restriktionen (z.B. macht derselbe Benutzer meistens "asynchr. Zielprogramme mit Nachbarschaftskommunikation")
künftige Erweiterungen, für die das Projekt gerüstet sein muß:
- not perfectly nested loops
- non-unimodular transformations
  [Xue und Pingali und Valero-Garcia]
- affine by statement scheduling, affine by variable mapping
  [A. Darte, Y. Robert]
- partitioning = tiling [Thiele + Darte + Fortes]
- multidimensional time [Feautrier, Part II]
- non convex execution spaces -- whiles [selber]

Neu: Strukturübersicht (unfertig!): Graphik

Martin Griebl