Freitag, 10.11.2000, 14:30, Felix-Klein-Hörsaal HG 04-24

Dr. rer. nat. Peter Sanders

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.