Freitag, 10.11.2000, 14:30, Felix-Klein-Hörsaal HG 04-24
Max-Planck-Institut für Informatik
Saarbrücken
"Schneller Zugriff auf parallele Platten"
Abstract:
Viele Anwendungen arbeiten mit so großen Datenmengen, dass effiziente
gleichzeitige Nutzung vieler Festplatten erforderlich ist, um eine
Leistung zu erreichen, die den Erwartungen an die Möglichkeiten der
aktuellen Technologie gerecht wird. Daraus ergeben sich interessante
algorithmische Probleme, wenn unregelmäßige Zugriffsmuster auftreten.
Der Vortrag ordnet dieses Thema zunächt in die allgemeinere
Fragestellung ein, wie unregelmäßig strukturierte Berechnungen auf
parallelen Hochleistungsrechnern zu handhaben sind. Dann werden
Techniken zur effizienten Handhabung paralleler Platten vorgestellt.
Es wird erklärt, wie eine Kombination von zufälliger Datenplazierung
und redundanter Speicherung viele Probleme auf allgemeine Weise löst.
Dabei ergeben sich interessante Querverbindungen zu Graphenalgorithmen
für maximale Flüsse und bipartites Matching sowie zu
probabilistischen Problemen vom Typ 'Balls-into-Bins', die in jüngerer
Zeit intensiv studiert wurden. Als Anwendungsbeispiele werden ein
einfaches Programmiermodell für Sekundärspeicheralgorithmen,
externes Sortieren und Video-on-Demand erwähnt.