ACADEMIA
Programming Languages Award Recognizes Impact of Renaming Technique in Compilers
A distinguished computer scientist at the University of California, San Diego is being hailed for her role twenty years ago in developing an efficient algorithm for a data structure commonly used in computers today. Jacobs School of Engineering associate dean and computer science professor Jeanne Ferrante and four former colleagues she worked with at IBM in the 1980s share the prestigious 2006 SIGPLAN Programming Languages Achievement Award given by the Association for Computer Machinery (ACM). ACM cites their development of Static Single Assignment (SSA) as a "significant and lasting contribution to the field of programming languages." 
The group at IBM's T.J. Watson Research Center that developed SSA included Ron Cytron, Barry Rosen, Mark Wegman, Kenneth Zadeck and Ferrante. SSA is an intermediate representation -- a data structure that is constructed by a compiler from the programmer's code -- that allows more efficient and powerful methods of transforming the user's program to machine code. Zadeck, Wegman and Ferrante accepted the award today at the ACM SIGPLAN 2006 Conference on Programming Language Design and Implementation (PLDI) in Ottawa, Canada. Ferrante received her Ph.D. in mathematics from MIT in 1974. She taught for four years at Tufts University, before joining the computer science department of IBM Watson Research Center in 1978. Ferrante remained at IBM for sixteen years, until joining UCSD's Computer Science and Engineering faculty in 1994. Ferrante traces her involvement in SSA to a 1985 sabbatical at UC Berkeley, where she worked on renaming. "Names and representations are important because if you cannot represent a concept in a language, there is nothing you can do with it," said Ferrante. "In ordinary discourse, if you don't have a word for snow, how do you refer to it? It's the same with programming languages. If you don't have a way to represent a particular operation or instruction, you cannot generate good code for it." She explored renaming for both parallelism and storage allocation. Returning to IBM Watson, she teamed with Ron Cytron on the 1987 paper titled, "What's in a Name." "In terms of programming, a name is usually associated with a piece of memory, so when you change names, you are using different memory," said Ferrante. "If you don't need to hold a value because you've put it somewhere else, you can reuse the original memory for other things." Also at IBM around the same time, Rosen, Wegman, Zadeck, and others were working to get more powerful transformations in compilers. The teams joined forces in an ad-hoc working group that developed what came to be known as Static Single Assignment form. "SSA is about names and what a name means, and it involves renaming each variable whenever it is assigned a value," she said. "It's very clean because there is only a single assignment of any variable that reaches any use of that variable in the program. SSA ensures that a variable's value can only come from one place in the program." Ferrante smiles when she remembers what happened next. "I will always remember this because it was one of my few 'Eureka!' moments," she said. "At one point I realized that an algorithm we had developed for another piece of work (on control dependence) might also work for SSA. If you go back and look at the SSA journal article from 1991, we talked about using the algorithm for both SSA and control dependence - but the latter came first!" Her earlier work formed the basis for an efficient construction algorithm, which led to its acceptance by the research community. SSA was immediately adopted for research compilers and today it is used commonly in production compilers. For her part, Ferrante has worked with colleagues at UCSD on adapting SSA to new machine architectures, including predicated architectures (where each instruction has a 'predicate' associated with it that dictates whether the instruction will be executed). Other work at UCSD centers on exploiting parallelism and optimizing data movement to improve performance, and her current research interests include program information interfaces. "Compilers are like black boxes because they don't tell you what they're doing," said Ferrante. "To make computing more effective, we need to be able to crack open compilers and get the information out." The team that developed SSA dispersed: Cytron teaches at Washington University in St. Louis; Zadeck founded a startup, NaturalBridge, to integrate SSA into a Java compiler; Barry Rosen retired after a long career at IBM; Wegman remained at IBM. All welcomed the award's recognition. Said UCSD's Ferrante: "We have fond memories of our productive team collaboration at IBM." Related Links PLDI 2006 Website
The group at IBM's T.J. Watson Research Center that developed SSA included Ron Cytron, Barry Rosen, Mark Wegman, Kenneth Zadeck and Ferrante. SSA is an intermediate representation -- a data structure that is constructed by a compiler from the programmer's code -- that allows more efficient and powerful methods of transforming the user's program to machine code. Zadeck, Wegman and Ferrante accepted the award today at the ACM SIGPLAN 2006 Conference on Programming Language Design and Implementation (PLDI) in Ottawa, Canada. Ferrante received her Ph.D. in mathematics from MIT in 1974. She taught for four years at Tufts University, before joining the computer science department of IBM Watson Research Center in 1978. Ferrante remained at IBM for sixteen years, until joining UCSD's Computer Science and Engineering faculty in 1994. Ferrante traces her involvement in SSA to a 1985 sabbatical at UC Berkeley, where she worked on renaming. "Names and representations are important because if you cannot represent a concept in a language, there is nothing you can do with it," said Ferrante. "In ordinary discourse, if you don't have a word for snow, how do you refer to it? It's the same with programming languages. If you don't have a way to represent a particular operation or instruction, you cannot generate good code for it." She explored renaming for both parallelism and storage allocation. Returning to IBM Watson, she teamed with Ron Cytron on the 1987 paper titled, "What's in a Name." "In terms of programming, a name is usually associated with a piece of memory, so when you change names, you are using different memory," said Ferrante. "If you don't need to hold a value because you've put it somewhere else, you can reuse the original memory for other things." Also at IBM around the same time, Rosen, Wegman, Zadeck, and others were working to get more powerful transformations in compilers. The teams joined forces in an ad-hoc working group that developed what came to be known as Static Single Assignment form. "SSA is about names and what a name means, and it involves renaming each variable whenever it is assigned a value," she said. "It's very clean because there is only a single assignment of any variable that reaches any use of that variable in the program. SSA ensures that a variable's value can only come from one place in the program." Ferrante smiles when she remembers what happened next. "I will always remember this because it was one of my few 'Eureka!' moments," she said. "At one point I realized that an algorithm we had developed for another piece of work (on control dependence) might also work for SSA. If you go back and look at the SSA journal article from 1991, we talked about using the algorithm for both SSA and control dependence - but the latter came first!" Her earlier work formed the basis for an efficient construction algorithm, which led to its acceptance by the research community. SSA was immediately adopted for research compilers and today it is used commonly in production compilers. For her part, Ferrante has worked with colleagues at UCSD on adapting SSA to new machine architectures, including predicated architectures (where each instruction has a 'predicate' associated with it that dictates whether the instruction will be executed). Other work at UCSD centers on exploiting parallelism and optimizing data movement to improve performance, and her current research interests include program information interfaces. "Compilers are like black boxes because they don't tell you what they're doing," said Ferrante. "To make computing more effective, we need to be able to crack open compilers and get the information out." The team that developed SSA dispersed: Cytron teaches at Washington University in St. Louis; Zadeck founded a startup, NaturalBridge, to integrate SSA into a Java compiler; Barry Rosen retired after a long career at IBM; Wegman remained at IBM. All welcomed the award's recognition. Said UCSD's Ferrante: "We have fond memories of our productive team collaboration at IBM." Related Links PLDI 2006 Website