Laszlo Belady

László Antal Bélády (* 29. April 1928 in Budapest, Ungarn; † 6. November 2021 ebenda) war ein ungarisch-amerikanischer Informatiker. Er war Mitbegründer der Mitsubishi Electric Laboratories, Inc. und fungierte als deren Präsident. Er entwickelte 1966 während seiner Arbeit bei IBM Research den theoretischen Speicher-Caching-Algorithmus von Bélády’s Min. Er wies auch die Existenz einer Bélády-Anomalie nach.

Leben und Werk

Bélády erwarb einen Bachelor-Abschluss in Maschinenbau und anschließend 1950 einen Master-Abschluss in Luftfahrttechnik an der Technischen Universität Budapest. Anschließend arbeitete er bis 1953 bei der ungarischen Luftwaffe und dann bis 1956 als Konstrukteur in Ungarn. Nach der Ungarischen Revolution verließ er 1956 Ungarn. Er arbeitete von 1956 bis 1959 als Konstrukteur bei der Ford Motor Company in Köln und danach als Aerodynamik-Ingenieur bei Dassault Aviation in Paris.

1961 wanderte er in die Vereinigten Staaten aus, wo er von 1961 bis 1981 beim IBM Watson Research Center beschäftigt war. Er arbeitete zunächst in den Bereichen Betriebssysteme, Architekturen virtueller Maschinen, Programmverhaltensmodellierung, Speicherverwaltung, Computergrafik und Datensicherheit. In den 60er und 70er Jahren lebte er hauptsächlich in New York City mit Stationen in Kalifornien und England. Danach wurde er Direktor für Softwaretechnologie bei IBM und war von 1983 bis 1984 Manager bei IBM Research in Tokio.

Der ehemalige Hauptsitz der Microelectronics and Computer Technology Corporation in Austin, Texas. 2005

Anschließend war er Mitbegründer des Forschungskonsortiums Microelectronics and Computer Technology Corporation (MCC) und bis 1991 Vizepräsident. Er arbeitete danach bis 1998 sieben Jahre lang als General Manager des Mitsubishi Electric Information Technology Center in den Vereinigten Staaten. Ab 1998 war er Geschäftsführer und Vorstandsmitglied des Austin Software Council und internationaler Berater oder Vorstandsmitglied bei Startup-Unternehmen in den USA, Österreich und Ungarn.

Zusätzliche Aktivitäten

Belady forschte als Gastprofessor 1971 und 1972 an der University of California, Berkeley und 1974 am Imperial College in London. In den Jahren 1987 und 1988 war er Mitglied des USAF Science Advisory Board, von 1984 bis 1994 Chairman des Advisory Board des IT Institute of the National Computer Board of Singapore und von 1988 bis 1994 im Board of Directors der Computer Research Associates tätig. Ab 2003 war er Präsident des Unternehmens Eutecus Inc, das computerbezogene Dienstleistungen und Beratung anbietet.

Belady war Mitglied in Beiräten mehrerer Computerunternehmen in den USA, Österreich, der Slowakei und Ungarn. Er war ausländisches Mitglied der Ungarischen Akademie der Wissenschaften.

Bélády war von 1979 bis 1983 Chefredakteur der IEEE Transactions on Software Engineering.

Forschung zu Speichermanagement

Ende der 1950er Jahre war der virtuelle Atlas-Speicher das erste System, das die dynamische Zuordnung von Programmen und Daten in einer Speicherhierarchie automatisierte. Die Atlas-Designer zeigten, dass die Automatisierung der Speicherverwaltung die Produktivität der Programmierer verdoppeln oder verdreifachen könnte. Trotz der attraktiven Programmiervorteile war der virtuelle Speicher umstritten, da experimentelle Studien mit Ersatzalgorithmen zu widersprüchlichen Ergebnissen bezüglich der endgültigen Systemleistung führten. Die Kontroverse erreichte Mitte der 1960er Jahre ihren Höhepunkt, als große Computerhersteller wie RCA, Burroughs, Univac, General Electric und andere den virtuellen Speicher einführten. Sie stellten bald fest, dass mehrfach programmierte virtuelle Speichersysteme sehr anfällig für Überlastungen waren. Die Systeme verlangsamten sich plötzlich auf ein kaum wahrnehmbares Kriechverhalten und konnten nur wiederhergestellt werden, wenn einige Jobs abgebrochen wurden. Die damaligen Ingenieure nannten das Problem „Paging to Death“.

Belady begann seine Experimente zum Programmverhalten und zu Seitenersetzungsalgorithmen im Jahr 1963, als er bei IBM Research in Yorktown Heights arbeitete. Seine Arbeit über Seitenersetzungsalgorithmen aus dem Jahr 1966 lieferte eine erste Definition der Lokalität und demonstrierte nützliche mathematische Modelle von Programmen, die in Speichersystemen ausgeführt werden. Belady entwickelte einen Simulator zur Untersuchung der Leistung von Paging-Algorithmen anhand tatsächlich aufgezeichneter Adressspuren. Später führte er Experimente mit einem mehrfach programmierten virtuellen Speichersystem durch, an dessen Entwicklung er beteiligt war. Er entdeckte MIN, den optimalen (Look-Ahead-)Paging-Algorithmus, der in der Praxis weit verbreitet und in Lehrbüchern zu finden ist.

Nachdem er seine Forschungen im Bereich Speichermanagement im Jahr 1968 abgeschlossen hatte, gründete und leitete Belady ein IBM-Forschungsteam mit dem Schwerpunkt Computergrafik. Auf diesem Gebiet erhielt er US-Patente.

Weitere Forschungen

• 1963 entwickelte Belady ein Tool zur Erfassung der Speicherreferenzmuster realer Anwendungsprogramme durch Modifizierung eines Software-Interpreters. Diese Arbeit führte zu einer Reihe wichtiger theoretischer Fortschritte, die in seiner Veröffentlichung aus dem Jahr 1966 A Study of Page Replacement Algorithms for Virtual Storage Computers beschrieben werden. Dieser Artikel über Virtual Memory Management wurde 1983 zum Citation Index Classic und war die am häufigsten zitierte Veröffentlichung im Bereich Computersoftware.
• Er leitete mathematische Ausdrücke für die Leistung des RAND (Zufallsersatzalgorithmus) ab und validierte sie mit empirischen Daten.
• Er erfand den MIN-Algorithmus, der die Anzahl der Seitenfehler für jede Seitenreferenzspur minimierte. Später meldete er ein Patent für ein Gerät an, das die Adressverfolgung einer CPU überwachte und die Seitenfehlerfunktion ausgab, die MIN gehabt hätte, und zeigte damit, dass die optimale Paging-Rate in Echtzeit berechnet werden kann. Auch als Belady-Algorithmus bezeichnet, hat er wichtige Anwendungen in anderen Bereichen, einschließlich der Registerzuweisungsphase des Compilerbetriebs.
• Beladys Studien zu Seitenersetzungsalgorithmen hatten großen Einfluss auf das Design des M44-Computers, eines modifizierter IBM-7044-Computers, der mehrfach programmierten virtuellen Speicher unterstützte. Als der M44 1965 in Betrieb ging, führte er „Live“-Experimente mit diesem neuen System durch, um zusätzliche Einblicke in das Verhalten von Berechnungen bei dynamischer Speicherpartitionierung zu gewinnen.
• Auf dem M44 entdeckte Belady die FIFO-Anomalie, auch Belady-Anomalie genannt. Dies ist die Beobachtung, dass eine Erhöhung des einem bestimmten Programm zugewiesenen Speicherplatzes tatsächlich die Anzahl der Seitenfehler beim FIFO-Ersatz erhöhen kann.
• Auf dem M44 führte Belady die Lebensdauerfunktion als Maß für die Güte von Paging-Algorithmen ein. Er bewies, dass diese Funktion eine nichtlineare Form hat, die als „konkave Aufwärts“-Kurve beginnt und dann in eine „konkave Abwärts“-Kurve übergeht.
• Auf dem M44 beobachtete er, dass eine unterschiedliche Partitionsgröße die Gesamtlebensdauerfunktion verbesserte. Er erklärte dieses Ergebnis mathematisch, indem er die konkave Aufwärtseigenschaft einzelner Programmlebensdauerfunktionen nutzte.
• Im Jahr 1970 begann Belady die Zusammenarbeit mit Manny Lehman zum Thema Programmierproduktivität und -qualität. Ihre Untersuchungen führten zu einem Verständnis darüber, wie sich die Programmqualität im Laufe der Zeit aufgrund aufeinanderfolgender Entwicklungs- und Wartungsrunden verschlechtert.
• In den späten 1970er Jahren leitete Belady ein Team bei IBM, das eine Hauptkomponente des Betriebssystems OS/360 neu gestaltete.

Ehrungen

• 1969 und 1973: IBM Outstanding Contribution Award
• 1983: Citation Index Classic for the most-referenced paper in the field of software
• 1988: Fellow IEEE
• 1990: JD Warnier-Award
• 2003: Award der John von Neumann Computer Society

Veröffentlichungen (Auswahl)

• A Study of Replacement Algorithms for a Virtual Storage Computer, IBM Systems Journal, Bd. 5, Nr. 2, Juni 1966, S. 78–10.
• mit Meir L. Lehman: Program Evolution, Processes of Software Change. Academic Press, London, 1985.
• mit R. A. Nelson, G. S. Shedler: An Anomaly in Space-time Characteristics of Certain Programs Running in a Paging Machine. In: Commun. ACM. Band 12, Nr. 6, 1. Juni 1969, ISSN 0001-0782, S. 349–353, doi:10.1145/363011.363155.

Weblinks

• Vorschlag zur Verleihung der Ehrendoktorwürde László Bélády ungarisch/englisch (PDF)
• Biografie bei IEEE Computer Society
• Youtube-Video: Bélády László portré
• Lazlo Belady bei dblp