LOST IN THE TRANSLATION: Professor Gets the Bugs Out of Software

• Not all language translation is done in the foreign language departments; in fact, a lot of translation goes on inside your computer.
• Software developers write their programs in high-level programming languages such as Basic, Fortran, C or C++. The high level program is then translated to machine language; each statement in the program is translated into a number of machine code instructions, specific to the type of computer. The computer then executes these instructions during the program's execution. Java is a little different in that the Java statements are translated to a language called Java Byte code that is not at machine level. The translated Java program would thus need to be interpreted by software for its execution. None of these program languages, however, are recognizable to the computer user as he or she uses software to send an e-mail, write a report, or tries to top their previous high score in Tetris.
• "Redundancy is built into programming languages to help make them easier to program and understand, but should be eliminated when a program executes because they rob a computer of time and memory," said Mary Lou Soffa, Professor of Computer Science at the University of Pittsburgh. "Another problem today is that the size of programs are growing, making it more difficult to translate programs into efficient machine code."
• Finding ways to eliminate the redundancies and developing techniques that scale to large programs are the projects Soffa has been focusing on in her work on compiler technology.
• Code optimization is a compiler technique that takes the translated code and improves on its execution time performance by removing the redundancies.
• Her current research is directed toward developing path- and resources- sensitive optimizations and scalable compiler techniques.
• "The traditional approach is to analyze and apply code optimization uniformly over all parts of a program, the assumption being that all paths through the program are equally important," Soffa said. "But it's usually the case that a small number of paths through a program are executed frequently, while large numbers of other paths are seldom, if ever, executed."
• Determining which paths execute most frequently and ensuring that those paths are optimized is more productive and produces higher quality code than the traditional approach, Soffa said. However, optimizing frequently executed paths may require other paths to execute more slowly. Path- and resource-sensitive analysis is needed to identify the paths and to determine if it is worthwhile to apply an optimization on a path at the detriment of another path.
• "One way to optimize is to identify which redundances to target for elimination by identifying and optimizing the most frequently executed paths. If some statements on a path are executed 1000 times in a program, and you can eliminate one statement from this path, but you add another statement on a path that is executed 10 times, then you have saved time by not executing 990 instructions."
• Frequently, optimizers don't take into account the amount of machine resources or characteristics. Large programs, too, can present problems for optimizing techniques designed for smaller programs.
• "When you're dealing with hundreds of procedures, and hundreds of thousands of lines of code as found in large applications, many of today's optimization techniques are either too costly to apply or are ineffective," Soffa said.
• Her goals are to develop optimizers that are not only effective, but that are applicable across a variety of programming languages and architectures.
• One current project is to develop Scalop, a scalable optimizing compiler that will have demand-driven and path-sensitive optimization algorithms.
• "Based on execution profiles, we are trying to develop and verify a scalable approach to compiler optimizations," she said. "Our approach will be to employ demand-driven techniques that limit the scope of the optimizations. Instead of simultaneously considering the optimization opportunities across the whole program, we are using program paths as the scope of the optimization application."
• The paths selected will be based on execution and resource-demand profiles to ensure that the most frequently executed paths are optimized.
• Soffa's work has been funded by grants from the NSF and Hewlett Packard Laboratories.
• In addition to her research activities, Soffa is committed to nurturing the next generation of scientists, and promoting careers in academia, especially for women and minority students. In December, she was one of 10 individuals nationally to be honored with the White House's Presidential Award for Excellence in Science, Mathematics and Engineering Mentoring, administered by the National Science Foundation.