Featured Research

from universities, journals, and other organizations

Parallel programming may not be so daunting: 'Lock-free' parallel algorithms match performance with wait-free

Date:
March 24, 2014
Source:
Massachusetts Institute of Technology
Summary:
Computer chips have stopped getting faster: The regular performance improvements we've come to expect are now the result of chipmakers' adding more cores, or processing units, to their chips, rather than increasing their clock speed.

Computer chips have stopped getting faster: The regular performance improvements we've come to expect are now the result of chipmakers' adding more cores, or processing units, to their chips, rather than increasing their clock speed.

Related Articles


In theory, doubling the number of cores doubles the chip's efficiency, but splitting up computations so that they run efficiently in parallel isn't easy. On the other hand, say a trio of computer scientists from MIT, Israel's Technion, and Microsoft Research, neither is it as hard as had been feared.

Commercial software developers writing programs for multicore chips frequently use so-called "lock-free" parallel algorithms, which are relatively easy to generate from standard sequential code. In fact, in many cases the conversion can be done automatically.

Yet lock-free algorithms don't come with very satisfying theoretical guarantees: All they promise is that at least one core will make progress on its computational task in a fixed span of time. But if they don't exceed that standard, they squander all the additional computational power that multiple cores provide.

In recent years, theoretical computer scientists have demonstrated ingenious alternatives called "wait-free" algorithms, which guarantee that all cores will make progress in a fixed span of time. But deriving them from sequential code is extremely complicated, and commercial developers have largely neglected them.

In a paper to be presented at the Association for Computing Machinery's Annual Symposium on the Theory of Computing in May, Nir Shavit, a professor in MIT's Department of Electrical Engineering and Computer Science; his former student Dan Alistarh, who's now at Microsoft Research; and Keren Censor-Hillel of the Technion demonstrate a new analytic technique suggesting that, in a wide range of real-world cases, lock-free algorithms actually give wait-free performance.

"In practice, programmers program as if everything is wait-free," Shavit says. "This is a kind of mystery. What we are exposing in the paper is this little-talked-about intuition that programmers have about how [chip] schedulers work, that they are actually benevolent."

The researchers' key insight was that the chip's performance as a whole could be characterized more simply than the performance of the individual cores. That's because the allocation of different "threads," or chunks of code executed in parallel, is symmetric. "It doesn't matter whether thread 1 is in state A and thread 2 is in state B or if you just swap the states around," says Alistarh, who contributed to the work while at MIT. "What we noticed is that by coalescing symmetric states, you can simplify this a lot."

In a real chip, the allocation of threads to cores is "a complex interplay of latencies and scheduling policies," Alistarh says. In practice, however, the decisions arrived at through that complex interplay end up looking a lot like randomness. So the researchers modeled the scheduling of threads as a process that has at least a little randomness in it: At any time, there's some probability that a new thread will be initiated on any given core.

The researchers found that even with a random scheduler, a wide range of lock-free algorithms offered performance guarantees that were as good as those offered by wait-free algorithms.

That analysis held, no matter how the probability of thread assignment varied from core to core. But the researchers also performed a more specific analysis, asking what would happen when multiple cores were trying to write data to the same location in memory and one of them kept getting there ahead of the others. That's the situation that results in a lock-free algorithm's worst performance, when only one core is making progress.

For that case, they considered a particular set of probabilities, in which every core had the same chance of being assigned a thread at any given time. "This is kind of a worst-case random scheduler," Alistarh says. Even then, however, the number of cores that made progress never dipped below the square root of the number of cores assigned threads, which is still better than the minimum performance guarantee of lock-free algorithms.


Story Source:

The above story is based on materials provided by Massachusetts Institute of Technology. The original article was written by Larry Hardesty. Note: Materials may be edited for content and length.


Cite This Page:

Massachusetts Institute of Technology. "Parallel programming may not be so daunting: 'Lock-free' parallel algorithms match performance with wait-free." ScienceDaily. ScienceDaily, 24 March 2014. <www.sciencedaily.com/releases/2014/03/140324154049.htm>.
Massachusetts Institute of Technology. (2014, March 24). Parallel programming may not be so daunting: 'Lock-free' parallel algorithms match performance with wait-free. ScienceDaily. Retrieved March 6, 2015 from www.sciencedaily.com/releases/2014/03/140324154049.htm
Massachusetts Institute of Technology. "Parallel programming may not be so daunting: 'Lock-free' parallel algorithms match performance with wait-free." ScienceDaily. www.sciencedaily.com/releases/2014/03/140324154049.htm (accessed March 6, 2015).

Share This


More From ScienceDaily



More Computers & Math News

Friday, March 6, 2015

Featured Research

from universities, journals, and other organizations


Featured Videos

from AP, Reuters, AFP, and other news services

Star Wars Inspires Mobile Holograms

Star Wars Inspires Mobile Holograms

Reuters - Business Video Online (Mar. 6, 2015) 3D holograms could soon be coming to your mobile phone. Inspired by the famous Princess Leia hologram from Star Wars, a U.S. company is showcasing a prototype display at the Mobile World Congress at Barcelona and says it could be used for real-time video calls. Ivor Bennett reports Video provided by Reuters
Powered by NewsLook.com
Game Makers Lured Into Virtual Worlds

Game Makers Lured Into Virtual Worlds

AFP (Mar. 6, 2015) Some 25,000 people have descended upon San Francisco to show off the latest technologies and video games at the Game Developers Conference. Developers here discuss the future of the industry. Duration: 02:20. Video provided by AFP
Powered by NewsLook.com
Star Wars-Inspired Prototype Creates Holographic Display

Star Wars-Inspired Prototype Creates Holographic Display

Reuters - Innovations Video Online (Mar. 5, 2015) A prototype holographic display named Leia - after the Star Wars princess who appeared in holographic form asking Obi-Wan Kenobu for help - is demonstrated at the Mobile World Congress in Barcelona. Matthew Stock reports. Video provided by Reuters
Powered by NewsLook.com
IKEA and Samsung Launch Embedded Wireless Charging Range

IKEA and Samsung Launch Embedded Wireless Charging Range

Reuters - Innovations Video Online (Mar. 5, 2015) Samsung and IKEA hope their new embedded wireless charging products, launched at Barcelona&apos;s Mobile World Congress, will tempt consumers eager for plugless power. Jim Drury reports. Video provided by Reuters
Powered by NewsLook.com

Search ScienceDaily

Number of stories in archives: 140,361

Find with keyword(s):
Enter a keyword or phrase to search ScienceDaily for related topics and research stories.

Save/Print:
Share:

Breaking News:

Strange & Offbeat Stories


Space & Time

Matter & Energy

Computers & Math

In Other News

... from NewsDaily.com

Science News

Health News

Environment News

Technology News



Save/Print:
Share:

Free Subscriptions


Get the latest science news with ScienceDaily's free email newsletters, updated daily and weekly. Or view hourly updated newsfeeds in your RSS reader:

Get Social & Mobile


Keep up to date with the latest news from ScienceDaily via social networks and mobile apps:

Have Feedback?


Tell us what you think of ScienceDaily -- we welcome both positive and negative comments. Have any problems using the site? Questions?
Mobile: iPhone Android Web
Follow: Facebook Twitter Google+
Subscribe: RSS Feeds Email Newsletters
Latest Headlines Health & Medicine Mind & Brain Space & Time Matter & Energy Computers & Math Plants & Animals Earth & Climate Fossils & Ruins