Email	Print Reprint
	add to:
	Del.icio.us Digg Google Spurl	Slashdot Y! MyWeb Blink Furl
	TABLE OF CONTENTS Going Superlinear Parallel Search: Exploiting Nonuniformity A Word About Sequential Efficiency versus Complexity

We spend most of our scalability lives inside a triangular box, shown in Figure 1. It reminds me of the early days of flight: We try to lift ourselves away from the rough ground of zero scalability and fly as close as possible to the cloud ceiling of linear speedup. Normally, the Holy Grail of parallel scalability is to linearly use P processors or cores to complete some work almost P times faster, up to some hopefully high number of cores before our code becomes bound on memory or I/O or something else that means diminishing returns for adding more cores. As Figure 1 illustrates, the traditional shape of our "success" curve lies inside the triangle.

Sometimes, however, we can equip our performance plane with extra tools and safely break through the linear ceiling into the superlinear stratosphere. So the question is: "Under what circumstances can we use P cores to do work more than P times faster?" There are two main ways to enter that rarefied realm:

• Do disproportionately less work.
• Harness disproportionately more resources.

This month and next, we'll consider situations and techniques that fall into one or both of these categories.

Figure 1: Parallel scalability.

1 Going Superlinear | 2 Parallel Search: Exploiting Nonuniformity | 3 A Word About Sequential Efficiency versus Complexity Next Page

RELATED ARTICLES Climate Researchers Get New 76-Teraflop Supercomputer Game Solves Puzzles for Science MySpace Opens up Profile Data Winners of the 18th Jolt Product Excellence Awards & Recipients of the Jolt Productivity Awards Performance Portable C++		TOP 5 ARTICLES Performance Portable C++ Scaling Scrum CUDA, Supercomputing for the Masses: Part 2 There Must be Contest CUDA, Supercomputing for the Masses: Part 1