But as the number of cores increase, these disadvantages are outweighed by performance gains of using a more "relaxed" style of random assignment, the researchers said.
To test the effectiveness of SprayList, the researchers ran an implementation on a Fujitsu RX600 S6 server with four 10-core Intel Xeon E7-4870 (Westmere EX) processors, which supported 80 hardware threads. In effect, it mimicked an 80-core processor.
When used to juggle fewer than eight processing threads, SprayList was indeed slower than a set of more traditional algorithms. As more threads were introduced, the performance of these established algorithms leveled out, and SprayList's performance continued to increase linearly, as measured by operations per second.
SprayList does not pick tasks entirely at random, but rather works off a kind of priority queue called a skip list, which bundles tasks into different priority levels, ensuring high-priority items still get processed before low-priority ones.
"Users who specifically choose to use a priority queue require that items with the highest priority are selected before items with low priority. Our work argues that it is OK to relax this somewhat — we can process the tenth-highest priority before the first highest priority without too much problem," said MIT Graduate student Justin Kopinsky, who led the work with fellow graduate student Jerry Li. Pure randomization might lead the computer to first process tasks with very low priority. "Then you run into trouble," Kopinsky wrote by e-mail.
For the work, Kopinsky and Li received help from their advisor Nir Shavit, an MIT professor of computer science and engineering, as well as Dan Alistarh, who works at Microsoft Research and is a former student of Shavit's.
The researchers will present their work next month in San Francisco at the Association for Computing Machinery's Symposium on Principles and Practice of Parallel Programming.
Sign up for CIO Asia eNewsletters.