ASPLOS Best Paper Award Spurs on Research to Redesign, Speed-up Address Translation

6/9/2020 Aaron Seidlitz, Illinois CS

CS researchers earn prestigious distinction, seek a commercial outlet for address translation work.

Written by Aaron Seidlitz, Illinois CS

About a year and a half ago, Illinois Computer Science PhD student Dimitrios Skarlatos started to consider an idea stemming from his internship with VMware.

Returning to campus, he wanted to rethink the virtual memory translation system of processors. He believed that current implementations inhibit processors from conducting address translations at a faster rate.

As with all good ideas, it took time and maturation to execute. Through the combination of his knowledge and expertise from Illinois CS faculty, it blossomed.

The work group included Skarlatos, fellow CS student Apostolos Kokolis and CS faculty Josep Torrellas and Tianyin Xu. Their research proved a new method to conduct address translations at a faster rate.

The research paper then earned Best Paper distinction at ASPLOS – the leading conference for interdisciplinary research combining computer architecture and operating systems.

Dimitrios Skarlatos
Dimitrios Skarlatos

"I was on the academic job market this year, and I remember that the email about the Best Paper award arrived in the morning a few hours before an interview,” Skarlatos said. “It was a fun morning, and I am tremendously honored to receive this recognition because ASPLOS is a premier forum dedicated to interdisciplinary research combining computer architecture, programming languages, and operating systems.

“It's produced some of the most exciting papers in this field.”

From the moment Skarlatos came back to campus with the germ of an idea, Torrellas and Xu supported it and helped push the work forward.

Torrellas’ expertise in computer hardware and Xu’s in operating systems helped the students delve further into the concept. Armed with the knowledge that the virtual address translation system contributes to substantial application slowdown, an attempt to redesign the system intrigued the professors.

Xu said that the industry has long decided to trade off the overhead for a standard benefit. Virtual memory is a fundamental operating system abstraction, which makes programs easy to write and be able to run on machines with different memory capacity or configuration – no matter how many other programs are running.

The current implementation has encountered further issues as it’s become outdated. Rather than continuing to add to the current approach, this group wanted to start anew.

Professor Josep Torrellas
Professor Josep Torrellas

“This design replaces radix page tables – the industry standard – with hashed page tables,” Torrellas said. “And to avoid the problems of collisions, we then designed Elastic Cuckoo Hashing. Together, this meant we could resize page tables on the fly while the program ran."

“The bottom line is that this offers an opportunity to streamline the current multiple step translation process, and translation time goes down.”

Their research showed that the resulting design “harvests, for the first time, the benefits of memory-level parallelism for address translation.”

It also proved that elastic cuckoo page tables “reduce the address translation overhead by an average of 40 percent over conventional radix page tables. The result is a 3-18% speed-up in application execution.”

Thinking back on the process, it’s clear that the team enjoyed the process as much as the results.

Professor Tianyin Xu
Tianyin Xu

A strong sense of camaraderie developed, as the group formed solutions around this pertinent problem.

“Working together with a fellow student and the faculty is what makes Illinois Computer Science a unique department and serves, in my opinion, as the university’s greatest strength,” Skarlatos said. “This project would not have been possible without this particular team, and each member’s expertise in multiple areas.

“At UIUC, finding collaborators in any area is as simple as knocking at their door. Everyone, both students and faculty, welcomes collaboration on exciting projects.”

Their work remains unfinished at this point.

Next, Xu and Torrellas said, they will attempt to see the idea through to commercialization. This has included discussions with Intel.

“Receiving the Best Paper recognition at ASPLOS, encouraged our entire research group to continue this work,” Xu said. “To make something like this, and see it through to commercial, is an ongoing process and it’s not going to be easy.

“Our goal is to press on until there is a practical use of this technology.”

Share this story

This story was published June 9, 2020.