Laszlo A. Belady

Born April 29, 1928, Budapest, Hungary; Proponent and implementer of virtual machine architectures and the "Belady" algorithm.

Education: BS, mechanical engineering, MS, aeronautical engineering, 1950, Technical Univ. Budapest.

Professional Experience: IBM Corp.: T.J. Watson Research Center, 1961-1981, program manager for software technology, IBM Headquarters, 1981-1983; manager of software engineering, Japan Science Institute (now Tokyo Research Laboratories), 1983-1984; vice president and director of the software technology and advanced computer technology programs, Microelectronics and Computer Technology Corp. (MCC), 1984-1991; chairman, Mitsubishi Electric Research Laboratories, Cambridge, Mass., 1991-present.

Honors and Awards: IBM Outstanding Contribution Awards, 1969 and 1973; J. D. Warnier Prize for Excellence in Information, 1990; fellow, IEEE "for contributions to the design of large software systems," 1988.

Belady did early work in operating systems, virtual machine architectures, program behavior modeling, memory management strategies, computer graphics, and data security. He co-designed and built the experimental M44/44X machine, the first computer with multiple virtual machine organization, and later participated in the design of the TSS-67, one of the earliest commercial time-sharing systems. In academic circles, Belady is best known for the OPT (or MIN) Page Replacement Algorithm, also known as the "Belady Algorithm": Given the ordered string of memory references which an executing program generates, and a given memory which is subdivided into equal-sized pages, the memory being smaller than necessary to contain the entire program material, the algorithm calculates the minimum number of page loads necessary to complete the program execution. The number is useful in order to (a) estimate system performance, and (b) compare "feasible" page replacement algorithms.

His own memories were expressed at a meeting where he was honored for his early work in 1991:

"It is really unusual for me to look back; I spend too little time reminiscing. I am now, however, forced to recall for you what I consider the most memorable aspects of my life.

"I grew up in a small town in Hungary, where my father was employed by the government as a civil engineer, designing and supervising the construction of roads and bridges. He worked often at home with compass and slide rule, tools that fascinated me. Often, he took me to the site and even today, I have the irresistible urge everyday to go to a neighboring office from which I can view the progress of a new four-level intersection being built next to our company.

"At school my favorite subjects were mathematics, the history of arts, and philosophy. I hated Latin and the study of languages in general but loved physical activity: running and biking with friends, fencing, boxing, gymnastics, skiing, skating. For years, my fondest memory was when during a school break I went out skiing, in bright sunshine, alone. It was indeed beautiful-not another soul around.

"In the meantime, WWII came to a finish. Towards its end I was once so hungry--and undernourished, weighing only about 110 pounds--that I dug up the potatoes in the field which were sown for the next crop and ate them raw. During this period, I finished my last year in high school by working first as an automobile mechanic apprentice and then (because it paid more), during the winter of 1945/46, at the salvaging of the bridges on the Danube which were blasted by the retreating Germans. We went to work by walking on ice floes, sometimes dipping in the icy waters, but we got special rations of sugar and lard. Otherwise, these items were only available on the black market. In the summer of 1946, I took my high school exams. I passed but not with honors!

"I was barely accepted to the Technical University of Budapest, because children of the intelligentsia were not favored by the then rising Communist regime. I started in mechanical engineering. The first year was tough because I cut classes and went to swim instead, as I thought that I already knew all the mathematics that was needed (we learned calculus in the last two grades in high school in Hungary). But by my final year, which was in my chosen field, aeronautical engineering, I was at the top of the class. Upon graduation, almost all aeronautics graduates were drafted and became officers of the Air Force technical staff. After three years, I finally escaped military service, but even my civilian employment was the design of special equipment for MIG-15 fighter planes. It was during this time that I received my first patents.

"The 1956 revolution interrupted my new adventure--working towards an M.S. in electronics engineering. During the revolution, my friends and I planned for the new Hungarian aircraft industry and made serious attempts to contact Western firms. As the Russians returned, I and exactly one-third of my fellow aeronautics graduates left Hungary. They are still living in the US (including myself) and Western Europe.

"I spoke German, and a peculiar 'one-way' English; I understood and could read almost everything, but had difficulty speaking the language. My reading skill was due to the fact that, during college years, I supported myself by translating English technical literature into Hungarian. After having escaped Hungary by walking 30 miles through the swamps to the Austrian border, I settled in Cologne, Germany where I became a draftsman at Ford Motor Company, the only position for which they thought a Hungarian engineer was qualified. After a few months, they "discovered" me, and for the next two years, I was designing front-end suspension systems. I became restless, as I liked airplanes better than automobiles! A friend introduced me to Theodor van Karman, the world-famous father of supersonic aerodynamics from Cal Tech (he was originally from Hungary) who helped me to find a job at Dassault in Paris as an aerodynamics engineer.

"I married an Hungarian and she has been my wife for more than 30 years. We had not known each other in Hungary, but met on our first day of freedom in Austria. At the Dassault job, I did more programming on the IBM 650, 1620, and 704 to solve equations than anything else, although I still used my beloved slide rule extensively. I was satisfied with the company and the job, but it was clear that we would never be accepted by French society even though my son was born there in 1961. We applied for immigration to the US and arrived in New York in the same year.

"From friends, I learned that you need a white shirt and dark suit for job interviews. I bought the clothing and, after distributing about 100 resumes and getting only four or five unsuccessful interviews, I gave up presenting myself as an engineer and applied as a programmer. This worked and IBM hired me into their brand-new, but empty, Yorktown research facility as a "building filler."

"I was lucky to land among an incredibly smart group, John Backus' people, who just finished their work on Fortran and its compilers. Memory management was identified as the next problem. Then, over the next few years, we designed and built IBM's first experimental virtual machine, the M44/44X, software first. The project was headed by Bob Nelson, who later became one of the first IBM fellows. Unfortunately, he died of his fourth heart attack around his 60th birthday in 1990. This man, while unknown to the non-IBM world, was a deep thinker and a very broadly read intellectual, but was of a rather shy nature. We became close friends, and to him I owe everything I learned about computers and programming.

"This work on virtual machines and paging paid off well. My paper written in 1965 became the Citation Index most-referenced paper in the field of software over a 15-year period. But by 1968, I was in computer graphics, as I was tremendously motivated by visualizing software, as other engineering artifacts are visual. Unfortunately, two years later IBM gave up on interactive graphics. After placing my fifteen people in other research groups, I went to Berkeley for a year and taught graduate courses in computer structures and memory management. Upon returning to Yorktown, I found IBM very interested in data security, and my friend, Manny Lehman, was interested in analyzing the unpredictability of operating system development. So, I managed a group in data security which produced a few interesting results among them a signature verification system, a virtual machine penetration study and a cryptographic effort which later led to a US government standard.

"The Program Evolution Dynamics work with Manny Lehman was even more interesting. For the following several years, we produced many papers, and organized conferences and workshops. Much of the material produced at this time was later published in a joint book (1985). Indeed, we were quite often criticized by our peers for this unusual effort as we were prophets trying to make some sense out of the large system complexity phenomenon and maintenance--it was heresy. I spent 1974 at Imperial College/London University with Manny Lehman, who is still there. I became more interested, however, in not only studying the phenomenon but also in doing design better. In the mid 1970s, I organized a group to utilize on practical systems the concept of data abstraction (today called object-oriented design). IBM, again, was not sufficiently enthusiastic, and I left for more administrative duties in IBM World Headquarters in Armonk. I was responsible for software technology, reporting to B.O. Evans, IBM vice president for Engineering, Programming and Technology. He was one of the greatest guys for whom I have ever worked.

"By the 1980s Japan emerged as a fascinating technical culture, and I became strongly interested in what makes them tick. The best way to find out was to live there for a while. When Hisashi Kobayashi, now Dean of Engineering at Princeton, invited me to join him at the new IBM research facility in Tokyo, I went gladly in early 1983. The next year and a half was terrific.

"For a while, I had been flirting with the idea of retiring from IBM and teaching. I finally made a deal with Georgia Tech to start teaching in the fall of 1984. But Admiral Bobby Inman intercepted me and offered me the job of software chief of the new MCC. During that summer, my wife and I sat around our kitchen table in Tokyo discussing our future, while Inman was calling weekly. Finally, I accepted his offer and joined MCC in September 1984.

"I am happy with what we have been doing in the Software Technology Program (STP) in spite of the obvious difficulties being experienced by the country, the computer industry and, thus, MCC. On balance, I am a lucky guy--as are you--to have the chance of living in such incredibly rich and interesting times."

Since that time, Belady has left MCC and is now with the Mitsubishi Electric Research Lab in Cambridge, Mass.

BIBLIOGRAPHY

Significant Publications

Belady, Laszlo A., "A Study of Replacement Algorithms for a Virtual Storage Computer," IBM Systems Journal, Vol. 5, No.2 June 1966, pp. 78-10. [This paper on Virtual Memory Management became the Citation Index Classic in 1983 as the most referenced publication in computer software.]

Belady, Laszlo A., and Meir L. Lehman, Program Evolution, Processes of Software Change, Academic Press, London, 1985.

UPDATES

Portrait inserted, MRW, 2012.

PDF version

Original content Copyright © 1995 by the Institute of Electrical and Electronics Engineers Inc.
New content Copyright © 2013-2015 by the IEEE Computer Society and the Institute of Electrical and Electronics Engineers Inc.
All rights reserved. This material may not be reproduced or redistributed without the express written permission of the copyright holder.