Calendar  |  Centennial Gift Shop  |  Donate to Campaign   Give to Regis
Facebook LinkedIn Twitter Vimeo
 
1914 | 2014       The Centennial Celebration       1914 | 2014
 
Multimedia Gallery
The Tomasulo Algorithm
Robert Tomasulo '52
 
Robert Tomasulo's photo in the 1952 Regis yearbook.
If you are reading this news story, chances are you are doing so on an electronic device that operates with a high performance processor—a processor which may not have been developed had it not been for the diligent work of Robert Tomasulo ’52.

Robert Tomasulo ’52 was a computer scientist and inventor of the Tomasulo Algorithm, an algorithm he formally defined in 1967. The algorithm "allows sequential instructions that would normally be stalled due to certain dependencies to execute non-sequentially" (also known as out of order execution).

In layperson's terms, the algorithm permits a cook in a kitchen who is supposed to blend milk with a stick of butter, add beaten eggs and then flour—to add the flour to the butter, even if the eggs and milk are not yet available. More succinctly, it permits elements of code to be written non-sequentially.

A March 2011 article from Engineering & Technology Magazine titled "Big Blue at 100: what IBM has done for us" highlighted the significance of the algorithm Tomasulo produced:

Computer architects realised one of the snags with performance was that compilers did not have enough information to deliver instructions in the right order—they could not know when data would be available for a following instruction. Only the runtime environment could provide that information. Step forward out-of-order execution.

Working on the Model 91, Robert Tomasulo came up with an answer: use that runtime information to reschedule instructions and execute them out of order. The CDC 6600 could finish instructions in the wrong order, thanks to a technique called scoreboarding, so that a very long operation such as a floating-point divide would not hold up simpler operations. Tomasulo's algorithm greatly extended the ability of a computer to re-sequence instructions and it became the template for microprocessor architectures such as IBM's POWER processors and the Intel Pentium Pro and AMD K5.

In those processors, out-of-order execution was used more extensively than in the Model 91, where it was restricted to the floating-point unit, much like scoreboarding in the CDC machine. It was not until the microprocessor wars that Tomasulo's approach was used widely: faster memory provided a cheaper speed boost for mainframes that followed the Model 91. Tomasulo received the Eckert-Mauchly Award a couple of years after out-of-order microprocessors were launched.

Excerpt from Big Blue at 100: what IBM has done for us, Engineering & Technology Magazine
March 14, 2011


As referenced, Tomasulo received the Eckert-Mauchly Award for his algorithm in 1997, an award which is presented jointly by the Association for Computing Machinery (ACM) and the IEEE Computer Society. The award represents the computer architecture community’s most prestigious citation.

In January 2008, just a little over two months before his passing, Tomasulo spoke at the University of Michigan College of Engineering about his career and the history and development of out-of-order execution (View video of the seminar). Still a critical principal of the programming universe today, a Google search for the Tomasulo Algorithm yields over 12,000 links.

Tomasulo's 1952 Regis yearbook photo is accompanied by a few descriptions of his life as a Regis student including, "Finds keen enjoyment in a game of chess," and "A charter member of The Square Circle, the Regis Math Club". After Regis, Tomasulo graduated from Manhattan College and went on to receive an electrical engineering degree from Syracuse University. He spent the bulk of his computer programming career with IBM, a stint that began in 1956.

Following many years as a loyal donor to Regis, Tomasulo became a member of the St. John Francis Regis Legacy Society later in life. Following his passing in South Lyon, Michigan in 2008, he left the bulk of his estate—a bequest totaling over $2 million—to Regis. The final installment of his estate gift was received this year, a fitting tribute to the Centennial celebration from a man whose life work played an important role in ushering in the digital revolution of the 21st Century.

Has the Centennial celebration inspired you to consider establishing the legacy you will leave at Regis? If you are considering designating Regis as a beneficiary in your estate planning, contact Paul Atkinson at legacy@regis.org for more information or visit regis.org/legacy.