Improving Performance: Maximizing Computational Efficiency
By: Jenny Maloney
Improving Performance Ever sit in front of a computer, click on a program you want to use, and then...wait? It's frustrating enough when these glitches are on a home computer and a user is checking e-mail or working on a document. In some cases, however, the stakes become much higher. Situations where patterns shift quickly - like when meteorologists are trying to predict hurricane and tornado behavior - mean that a computer lag can cost time, money, and possibly lives.
Dr. Qing Yi, Associate Professor in the Department of Computer Science at UCCS, is discovering new ways to speed up the process. "I work on compiler optimizations. Basically, I like to make programming easier for people and at the same time automatically make their programs run fast."
Compilers are computer programs that take a high level programming language like C++ or Java and change it into a language the machine can actually use. "I look at compilers as a tool that bridges the computer, which everyone uses nowadays, with what people want the computer to do. It's a communication channel." The biggest problems that can pop up with compilers are errors and inefficiencies created in the translation, a breakdown in the bridge Yi describes.
As the amount of information to be processed increases, programming languages have become increasingly complex, and the compilers struggle to keep up with the translations necessary for the computer to perform. "If you need to solve large simulation problems, like with weather forecasting, you have to look at a large amount of data and the efficiency there is very important," says Yi. The intention of the programmer has to be translated accurately by the compiler. At the same time, the translated machine code needs to be efficient enough so that the complex task at hand can be completed in a reasonable amount of time. Computers have become so fast, and the programming languages have become so diversified, that the compilers have a hard time understanding what the program is telling them. If you want high performance, you basically have to do the compiler's work yourself. Yi's research is geared to help with that.
"Two of my actively funded NSF projects are focused on making the compiler an open box of tools that help people optimize their programs," says Yi. She is working toward developing that tool box. "Basically, you have your program, and assuming it's correct, the compiler would analyze your program and let you know what it has found out and suggest potential optimizations." The compiler Yi describes would be interactive, showing flaws in the programming and troubleshooting areas to improve performance.
"It is mostly focused on scientific computing applications but this methodology itself does not have to be limited to scientific computing," says Yi.
For another grant, also funded by the National Science Foundation, Yi is partnering with Dr. Damian Dechev at the University of Central Florida. They are collaboratively developing a data structure library designed to address a key challenge in multi-threaded applications: synchronizing data shared among the threads without damaging performance.
They're aiming at creating lock-free data structures for parallel applications. Parallelization is a way of breaking down computer programs into multiple threads that can progress simultaneously. However, more than one thread could try to modify data at the same time, which creates a problem called race conditions. At present, locks are the answer, which basically make the competing threads queue up and wait for one another. This means the system slows down as the threads are handled singly at certain points - which tie up the threads and slow down processing, a stumbling block for parallelization.
"All computers nowadays have multicores, no matter what computer you use, even in the car. So parallelization is something that is unavoidable," says Yi.
So, how to fix the bottleneck?
With Dr. Dechev, Yi is building a library of data structures - containers like stacks, lists, queues, graphs - that support lock-free synchronization of data, even if the threads are all trying to write to the same place. This avoids locks all together. "Different threads - many, many threads - can synchronize, even if they're all trying to write to the same place. They help each other out instead of using locks."
One of the goals of Yi's research is that the combination of the container library and the programming work will lead to immense productivity and performance boosts for developers of high-end scientific and systems applications. Yi and Dechev are also aiming to develop programming techniques and tools that enable the transformation of those applications into software that is substantially more reliable and efficient and than the current state of the art.
These are some of the challenging elements of current computer science research, but Yi is up for the test. "I like to think about problems. I like to dig and understand things," says Yi. She's realistic about her approach to these challenges as well. "In general, when you branch out into any new area, there's a learning curve. It takes sometimes a year or two to really understand: What are the real challenges?"
She has the training to tackle these challenges as well, thanks to her very capable mentors. One of her mentors was Dr. Ken Kennedy. Kennedy, her Ph.D advisor at Rice University, was a pioneer in the computer science field who, according to the New York Times "spearheaded early work on software programs known as parallelizing compilers, systems that can automatically spread workloads among a large number of processors, vastly speeding calculations." Dr. Kennedy passed away in 2007, leaving behind the determined grad students he mentored to discover the computer functions of the future.
According to Yi, Kennedy told her, "Research is about spreading the ideas. It is about generating the right ideas and trying to convince people these are the right ways to do things." She tries to do both: generate ideas and communicate the importance of those ideas. Her first paper was presented at the PLDI conference (A top conference in the field of Programming Languages and Compiler Implementations) in 2000, so she started strong and continued to do well with the National Science Foundation's Career Award - always inspired by her advisor.
Yi has now sat at both ends of the table: mentor and protégé. She hopes she is as encouraging as Dr. Kennedy, but admits it's more difficult than it looks. "I try," she says.
One of the points she tries to get across to her students is that research is more than copying what has gone before. Students, teachers, all researchers, must tackle new challenges and develop new processes, otherwise you are just imitating and nothing original or groundbreaking is getting accomplished.
"Research, I tell my students, is more about ideas than implementing things. If you have implemented something that is already published by people, and you did not generate any new ideas, it's not publishable."
Yi believes that her work is a reward in and of itself, and it doesn't stop in the laboratory or the classroom. The skills she has gained from actively pursuing her scientific work - the ability to think objectively, to observe a situation - she applies to all aspects of her life.
"The ability to learn, to extract things from the information you have, the situation, and to think about it and tackle it, it's a process. You not only do it in your research, you do it in your everyday life."
Learn more about Yi at her website.