Tardis Directory System May Change How Multicore Chips Overwrite Data

MIT engineers use “time travel” to allot memory space.

MIT engineers have developed a new technique for programming memory allotment in multicore chips, which they are likening to time travel.

By The original uploader was Zir at English Wikipedia (Transferred from en.wikipedia to Commons.) [CC BY 2.5 (http://creativecommons.org/licenses/by/2.5), GFDL (www.gnu.org/copyleft/fdl.html) or CC-BY-SA-3.0 (http://creativecommons.org/licenses/by-sa/3.0/)], via Wikimedia Commons

By The original uploader was Zir at English Wikipedia (Transferred from en.wikipedia to Commons.) [CC BY 2.5 (http://creativecommons.org/licenses/by/2.5), GFDL (www.gnu.org/copyleft/fdl.html) or CC-BY-SA-3.0 (http://creativecommons.org/licenses/by-sa/3.0/)], via Wikimedia Commons

They’ve even gone so far as to name the system “Tardis” after the time-travelling spaceship piloted by the iconic sci-fi character Dr. Who.

Multicore chips store data in memory caches personal to each core, plus an additional and larger cache, which all cores can access. This shared cache keeps a directory of which cores are operating on which copies of data.

This means the directory takes up a bit of memory itself. As the core count would increase, so too would the amount of memory the directory takes up.

The Tardis directory system however, uses a new technique which increases memory allotment according to the logarithm of the number of cores instead, therefore using only one-third as much memory. Hypothetically, a 1,000-core chip could have space savings of 96 percent, an article by MIT News states.

The coolest part, however, is how the cores share data.

The Tardis directory system allows multiple cores to edit the same set of data simultaneously and organizes overwrites according to logical-time ordering, rather than physical-time as used by previous systems.

“Directories guarantee that when a write happens, no stale copies of the data exist,” said Xiangyao Yu, an electrical engineering and computer science graduate from MIT and first author of the paper. “After this write happens, no read to the previous version should happen. So this write is ordered after all the previous reads in physical-time order.”

With Srini Devadas, a professor in MIT’s Department of Electrical Engineering and Computer Science, the pair established that physical-time order didn’t matter as long as logical-time order was preserved.

“What we do is we just assign time stamps to each operation and we make sure that all the operations follow that time stamp order,” Yu said.

Larry Hardesty, with MIT News, lays out a clear example of this in his article:

“Say, for instance, that cores A through D have all read the same data, setting their internal counters to 1 and incrementing the data’s counter to 10. Core E needs to overwrite the data, so it takes ownership of it and sets its internal counter to 11. Its internal counter now designates it as operating at a later logical time than the other cores: They’re way back at 1, and it’s ahead at 11.

“Now, if core A tries to take out a new lease on the data, it will find it owned by core E, to which it sends a message. Core E writes the data back to the shared cache and core A reads it, incrementing its internal counter to 11 or higher.”

Christopher Hughes, a principal engineer at Intel Labs points out that chip designers may be apprehensive about adopting such a new technique.

“Almost all mass-produced commercial systems are based on directory-based protocols,” he says. “We don’t mess with them because it’s so easy to make a mistake when changing the implementation.”

Should chip designers move on from physical-time order systems? Are their apprehensions well founded? Could the Tardis directory system revolutionize processing power for multicore chips?

The MIT team will let us know when they introduce the Tardis at the International Conference on Parallel Architecures and Compilation Techniques Oct. 19.

To read their report, visit http://people.csail.mit.edu/devadas/pubs/tardis.pdf.