Microprocessors use devices called branch predictors to predict the near-term behavior of a program so that work on future instructions may begin early, reducing the amount of time the program takes to run. Branch predictors must be highly accurate, and a small improvement in accuracy can give a large benefit for performance. This project is a principled approach to continuing the study of branch prediction. Several new ways to understand and improve branch prediction will be explored:
1) Exploring the limits of the potential of branch prediction to improve performance by developing a model of an idealistic branch predictor given reasonable assumptions;
2) Improving technologies for running computer programs on real computer systems so that these programs will have better branch prediction accuracy;
3) Discovering ways of improving the communication between computer programs and computer systems such that information available to a computer program can be used to improve the accuracy of branch prediction in a computer system; and
4) Working on new branch predictor designs for future computer systems, incorporating techniques from other disciplines such as machine learning, i.e., the study of how computer systems can learn by observing data.
In each of these areas, technological constraints on branch prediction will be taken into account. In particular, a branch predictor must act very quickly to deliver its prediction in time to improve performance, and it should do so in an energy-efficient way. This research will be brought to the classroom with a special seminar class on the interaction of research into computer systems and research on machine learning.
The objective of this project was to study, understand, and improve branch prediction techniques. A branch predictor is a part of a microprocessor that enables it to process instructions quickly by predicting how a program will behave. A "branch" is an instruction a computer program uses to make a decision. For instance, a program might have a sequence of instructions that mean "if a value is greater than another value, then swap them." The instruction that decides whether the swap should be performed is a branch. By intelligently guessing the outcome of a branch with high accuracy, the following instructions can be anticipated, saving the time and energy the processor would otherwise have wasted waiting for the result. Modern microprocessors achieved roughly 95% accuracy on many programs, but increasing this percentage can yield significant improvements in performance, as each incorrectly predicted branch has a large negative impact on performance. Branch prediction has been a heavily studied topic in computer architecture because of its ability to improve performance and its relative isolation from the rest of the microprocessor, i.e., a new predictor can basically be "dropped in" without affecting the design of the rest of the processor. The project developed a number of branch prediction techniques primarily based on neural learning. Neural learning attempts to emulate the way biological nervous systems learn. We developed a number of enhancements to existing algorithms proposed previously by the PI. For instance, we learned that some of the inputs to the neural learning system have a higher impact on correctness than other, so we developed an algorithm to give those inputs higher priority. The implementation of this technique was enabled by combining analog computation with digital computation. While researching branch prediction techniques, we realized that the same principles used in our research could be applied to other similar problems. For instance, we successfully applied branch prediction ideas to the problem of determining whether data from the computer's memory was likely to be used soon, and use this information to drive a cache management policy. The results of the research were published in a variety of journals, conferences, and workshops. In computer architecture research, conference presentations are accompanied by printed proceedings of papers up to 12 pages detailing the research. Journals, conferences, and sometimes workshops are peer-reviewed to ensure quality of the research. The research from this project has had significant broader impacts. In 2011, we learned that predictors invented by the PI had been used in the design of branch predictors in products offered by AMD and Oracle. Several students have participated in the project. Four women students have participated in the project. Two of them have earned their doctorates in computer science while a third has recently defended her dissertation and will graduate in Summer 2014. The research has been presented at a number of mentoring events designed to encourage under-represented groups to enter graduate education in computer science.
