Research proves the improbable can be made possible

Microprocessors are at the heart of devices such as computers, smart phones and iPads. In the Texas Architecture and Compiler Optimization (TACO) lab at Texas A&M University, Dr. Daniel Jiménez, professor in the Department of Computer Science and Engineering, has revolutionized the way research on this technology is conducted.

Microprocessors execute programs by reading instructions written in machine language, decoding them, carrying out their objective and storing the results. Similar to an assembly line, they process instructions through a channel called a pipeline where many instructions are processed at the same time in different stages.

Some commands, such as branch instructions, cause the pipeline to temporarily stop until the instruction can complete. Branch instructions can change the source of subsequent instructions, creating the potential for a type of problem know as a control hazard; when a control hazard occurs, no other work can be performed. Jiménez works to address these hazards with microarchitectural prediction.

Some instructions load values from the computer's main memory, which is usually made from a high-capacity, but slow technology called Dynamic random-access memory (DRAM). When a load instruction has to access the main memory, it can take up to 300 times longer than an instruction that does not use the main memory.

A delay caused by the slow memory is called a data hazard and can also reduce performance. Microprocessors rely on a cache to avoid the cost of accessing the slow memory. However, most processors' caches have a limited capacity to keep the right data.

Jiménez has developed many algorithms for performing branch prediction, which allows the processor to predict whether a branch instruction will cause a change in the flow of control in a program. Most of his algorithms are based on neural learning – the same form of information processing method neural networks such as the biological nervous system use.

Jiménez's branch predictors are among the most accurate in the literature and industry and are used in a range of computing platforms such as high-performance computers, desktop and laptop, as well as mobile computing. Recent microprocessors from Advance Micro Devices (AMD), Oracle, and others feature branch predictors based on those designs. He was awarded the NSF CAREER grant for his work in this area.

Jiménez and his team in the TACO lab have developed several dead block prediction algorithms as well as improved cache replacement policies for data hazards. Dead block predictors give a prediction as to whether a block of data will be used again in the near future. With this information, the cache controller can decide whether to keep a block or remove it in favor of a block that is more likely to be used soon; this improves the storage capacity of the cache and in turn, efficiency.

"When I first started working on the idea of using neural learning in branch prediction, I didn't realize that the idea was totally impractical," Jiménez said. "Once I proposed it, I learned that the tight timing constraints in a microprocessor make neural learning almost impossible to implement for branch prediction. I spent several years as an assistant and associate professor at Rutgers turning 'totally impractical' and 'almost impossible' into reality by inventing various techniques to solve the timing problem as well as improve accuracy."

Jiménez and his students have introduced several improved dead block predictors and cache replacement policies, including their most recent paper which was presented at the 2016 HPCA conference.

That paper, "Minimal Disturbance Placement and Promotion," introduced a policy that uses very little hardware overhead to do cache replacement that results in performance competitive with state-of-the-art policies with higher overheads.

They recently submitted another paper that merges neural learning with dead block prediction to outperform all other state-of-the-art policies. Several microprocessor manufacturers have expressed interest in using these cache replacement algorithms.

Jiménez first began studying microarchitectural prediction while completing his doctorate at the University of Texas at Austin in 1999; his first neural branch prediction paper was a collaboration with graduate adviser, Dr. Calvin Lin.

Jiménez's research on branch prediction was featured in the 2009 issue of IEEE Micro's "Top Picks from Computer Architecture Conferences"; this research was conducted in collaboration with Dr. Doug Burger and Dr. Renée St. Amant from the University of Texas at Austin. He has also collaborated with Dr. Gabriel Loh of AMD Research on branch prediction and other microarchitectural prediction.