POWER, Itanium, Niagara: Superscalar vs. VLIW vs. Simple Multicore

The recent near-simultaneous announcements of IBM's POWER7 and Intel's Itanium 9300 ("Tukwila") invites some background on how those differ in essential architecture, why VLIW (Itaniam's architecture) never was a good idea in the first place, and how they compare to the alternative simple multicore systems such as Sun's (now Oracle's) Niagara. 

Why do this when this blog is about parallel stuff, and they're all, except Sun, devoted to single-stream performance? This isn't "The Perils of Serial," and won't become that, but it nevertheless is wise to know thy enemy. Besides, it will explain what "small simple core" really means compared with the alternatives.

So: POWER is Superscalar, Itanium is VLIW (Very Long Instruction Word; Intel calls its version EPIC for Explicitly Parallel Instruction Computer), and Niagara is composed of many simple cores.

Everything clear now?

I hope not, since I've written a pile of stuff here that gives my understanding of how those architectures differ. The explanations will deliberately leave out a whole lot of detail in an attempt to render them approachable, but I'll give some hints about what I've left out. I'd appreciate any feedback indicating that I got things wrong, or left out issues that I mistakenly thought weren't key.

Finally, before I forget: The real killer tech among the announcements is none of this architecture stuff. It's some silicon technology in POWER7. IBM's fabs have managed to put DRAM on the same silicon as the POWER7 logic, something known as embedded DRAM, or eDRAM. This is a real feat, since the fab process to make DRAM and the process to make logic are very dissimilar; SRAM, in contrast, uses the same process as logic, which is one reason it's often seen in caches (another is that it's faster than DRAM). eDRAM lets POWER7 have a huge cache (32MB) that eats far less chip area because it is dense DRAM instead of more sprawling SRAM; uses less power than equivalent-size SRAM; and puts that cache right on the same silicon as the processors, reducing its access latency by 6 times compared with off-chip cache (they say). Hats off!

Starting Point: A Very Simple Processor

In its guts, a CPU has functional blocks of logic that are connected roughly like this (very simplified):

There's a unit that gets the next instruction (Fetch), another that figures out what that instruction says to do (Decode), and then another that finally does what it says (Execute). Execution, however, itself uses different hardware units for the different kinds of things that an instruction could say to do. So it's actually split up like this (for example, and deliberately leaving out memory access and writeback for simplicity):

The Integer unit is designed to do integer operations, like adding, masking, rotating bits, etc. The Float unit is similarly designed to do only floating-point operations, like add, multiply-add, and so on. The branch unit decides whether to specify where the next instruction fetched should come from. The three share just about nothing; they're completely different logic functions.

In what we have so far, only one instruction is being worked on at a time: One instruction is fetched, then that same instruction is passed to decode, then that same instruction goes to one of the execution units, and only then, after the current instruction is over, does the next instruction get fetched. If we have one clock tick for each of those operations, it does one instruction every three clock ticks, at best.

Once upon a time computers actually did just that: they did one instruction, period, at a time. Then someone introduced the joys of pipelining:

Now we can be doing three instructions simultaneously. Starting from the right:

• We are executing instruction N, actually doing what it said to do – an integer add, for example.
  
• At the same time, we're decoding the next instruction to be done, instruction N+1.
  
• And at the same time as that, we're getting hold of (Fetching) the instruction to be done before that one, namely instruction N+2.
  

"Fetch" now becomes free-running; it just keeps getting the next instruction. This, however, produces a problem: Branches. If instruction N is a branch whose execution says the next instruction performed should be at N+2289 (for example), you do not want to fetching and decoding N+1 and N+2. So you dump them out, replacing them with null operations while the instruction at N+2289 is fetched. The time wasted doing those nulled-out operations constitutes the infamous pipeline stall. There are good heuristics for avoiding this kind of pipeline stall; they basically involve making an educated guess about what the next instruction is going to be. For example, some processors keep a branch history table, a cache of where recent branches went. Then, as soon as a branch is fetched, the next fetch done is from the location that followed the branch last time. This works really well for every iteration of a loop but the last, for example. (And the first.)

We are now running quite a bit faster. Except for pipeline stalls, we finish an instruction every clock cycle, rather than every three. This is good. But there's an opportunity to do even better staring us in the face, if we know where to look.

The Road to Superscalar

Look at those three execution units on the right: Integer, Float, and Branch. Two out of three of them are sitting idle all the time, since no one instruction ever uses them all at once. But it's easy to think of cases where they could be running simultaneously.

For example, suppose X, Y, and Z are floats; and A, B, and C are integers. Then you could do these two instructions at the same time:

X = Y + Z /* fadd (fregY, fregX, fregZ)

A = B + C /* add (iregB, iregC, iregA)

These two use different logic – one the integer execution unit, the other the float execution unit. And they use different registers – one reads and writes integer registers, the other just uses float registers. This kind of thing happens all the time in computational loops, with the integer operation counting an index or something. Nothing intrinsically says you can't do them at the same time, so why not do that?

Well, because not every pair of instructions, or trio, or whatever, is independent the way those two are. Suppose we had these two successive instructions:

A=A+1

B=A+1

Were these done at the same time, B won't see the updated value of A. Crash!

We have to pick out the independent sets of instructions. How can we pull that off?

Superscalar

Like this:

First, we have to fetch faster than one instruction per cycle. No problem there; the units of storage in instruction caches, cache lines, hold well more than one instruction each.

And we have to be able to decode more than one instruction per cycle. Just replicate the decoding logic (not illustrated).

Finally, we have to hold all those instructions at the same time in a queue, the instruction queue. If we don't have them all at the same time, it's rather difficult to do them at the same time. (The queue's length we'll talk about later, but generally it's pretty short, like four.)

That queue isn't just a passive queue; it has to have some special logic winding among its storage elements:

• It has to compare each instruction to all others in the queue (logic not shown), and flag dependencies: This instruction uses a register that one uses – no good, we must do them in order. Or: these two are independent in the data they work on, but need the same execution unit – no good, must do them in order.
  
• Whenever it finds some that are independent, it shoves that whole group, simultaneously, at their appropriate execution units. Wham! All done at once. The need to send all at once is why there are so many paths to the execution unit.
  

That's superscalar. It's "super" because, under the right conditions, it can execute more than one instruction per cycle. It's "scalar" because, well, it's not vector. That's another way, and the only other way at the time this was invented, to do more than one operation per cycle. For example, specify two sets of N operands each, have one instruction that says "add them all," and have a pile of adders available to apply to the job.

Superscalar can get even more super than the previous diagram indicates. What if instructions are independent, but they both use the integer unit, or both use the float unit? Simple: Add more units.

Multiple float units have obvious uses (see vector case above). However, multiple integer units are more often useful, since lots of address calculations go on independent of program-explicit integer operations. Also, integer units are a lot smaller and less complicated that float units. Most superscalar designs have at least two integer units, and often more.

Superscalar designs like the whole IBM POWER series can do very well. What you get out of them is, of course, heavily dependent on the instruction stream – how independent the instructions are from each other. Lots of compiler technology has been applied to this, with the result that aggressive superscalar designs can perform pure computational floating-point loops pretty much at their limit, cranking out multiple results per cycle, until other system aspects intervene (like memory bandwidth). But they can't turn a pig's ear into a silk purse. Operating system code – test a bit and branch, test another bit and branch, etc. – is really hard to get down to even one instruction per cycle; usually it's more than that.

Superscalar Woes

Despite being rather good, the superscalar approach has one glaring problem: That magical queue in the middle. It has to compare every instruction with every other instruction to test independence; and it has to have paths to every execution unit.

Every-to-every checking that must complete in a single cycle (otherwise there's no point) and all those paths, add up to a lot of logic and wires. In fact, the queue and its associated logic grows in size roughly as the square of the queue length. What that means is that a queue eight long is hard but can be accomplished – POWER7 and earlier designs can issue 8 instructions per cycle – but a queue 16 long would be fairly exorbitant.

Question: How do you get past this?

Answer: Punt to software.

Very Large Instruction Word (VLIW)

That's what VLIW does. (Intel calls their version EPIC.) It looks roughly like this:

Seem familiar? Almost all I did is replace the words "instruction queue" with the word "parcels." That's because the prior diagram didn't show all the comparison logic among the instructions; VLIW has none. (I also dropped a few of the paths to the execution units; more on that later.)

So how does it get away with not checking dependencies among instructions? The compiler does it. The "parcels" correspond to more-or-less normal instructions, and a single instruction is now a whole queue-load of those parcels.

That's why it's called "Very Long Instruction Word." The whole collection of parcels is one "instruction," always fetched as a unit, and executed as a unit. All in parallel.

So what does the compiler do when there aren't enough independent parcels to fill up a whole Very Long Instruction? It just pads out the instruction with null operation parcels. And use intensely clever compiler techniques to try to avoid that as much as possible.

There are, additionally, some fun issues concerning executing a number of loop iterations that isn't evenly divisible by the number of parcels, but it can be done. For example, you can have several loop exit paths of different widths; or you can use masking techniques to disable execution of particular parcels according to a vector-like test.

In addition to ditching the n² comparison logic, VLIW designs can also cut down on the number of paths to execution units by simply mandating that only certain parcels can have certain operations.

In the diagram above, for example, only the first parcel can be a branch. There's no loss of generality or performance in doing that, because all parcels are done at once, so you can always move a branch to the first position; and you don't need more than one, since it's a bit hard to do two branches, to two different locations, simultaneously. Superscalar can't do that reduction because a branch could be in any position in the queue, and there can be multiple branches; they just have to be done sequentially (or punted with a pipeline stall).

My other data path changes are pretty arbitrary, but fairly representative; I've allowed for only two floats at the same time, but three integer ops.

With that quadratic factor out of the way, the sky's the limit in terms of the parallelism you can incorporate. Sixteen-way, 32-way, go for it. You'll need a lot of execution units, but what the heck, that's what the customer is paying for.

Sounds good, right? Nah.

Why VLIW Always Was a Bad Idea

There are two reasons why I've always thought VLIW is a bad idea. The first one below is by far the lesser, but it's still significant. The second is, for me, the killer.

Problem 1: Compile is specific to implementation. In particular, what if you have a compiled binary you bought off the shelf. It was compiled several years ago. Now you go out and buy a shiny new VLIW system that executes a new, different number of parcels in parallel. What happens to your binaries? Two cases, but either way you're screwed:

• If the new number is smaller – say, your binary is compiled for 4, but but your hardware does 2 – at least the code works. But your code is full of those null operations needed to pad things out to 4, so you waste time doing those. Your OS in particular (test a bit and branch) will probably run twice as slow as it needs to.
  
• If the new number is larger – say, your binary is compiled for 4, but your hardware does 8 – the program doesn't work. The hardware tries to do 8 at a time, but only groups of 4 are independent. As a result, dependent instructions run at the same time and clobber each other's data. Intel does have a fix for this: A bit that says "independence stops here!" The compiler sets the bit at the boundaries it compiled for, and the hardware respects it. So the program works. But it only runs as fast as the old hardware. Your new wider hardware doesn't help; you got nothing for that purchase.
  

Problem 2: Not enough parallelism. So you can do all this parallelism. Is it present in a single thread of execution to exploit in the first place? Um, no. It's certainly not there in operating systems (test a bit and branch), databases, and other commercial software. Most technical codes find it hard to average over four in a single thread. Parallelism for multiple threads is there, but it doesn't translate down to single threads very well at all.

Now, before all the graphics guys go ballistic on me over Problem 2, consider: Yes, there's a ton of single-thread parallelism in graphics. But it's well-handled by SIMD (vector) techniques. Those are far cheaper to implement in hardware, and furthermore don't have Problem 1, since it's relatively simple to parameterize the code to the length of the SIMD (vector) registers. Also, with SIMD, you can double down and do more smaller-data operations at once, with the same hardware; VLIW can't do that.

Problem 2 has been known for a very long time, even from the inception of VLIW. I remember being in an IBM Research seminar by Josh Fisher of Yale, back when he originally proposed it in the early 1980s. I recall asking "But is there enough single-thread parallelism?" (in so many words). Response: "It gets rid of the quadratic-size logic!" (in so many words). Me again: "But is the parallelism there to exploit?" Respose: "But it's such a neat idea, it gets rid of the quadratic-size logic!" And so on. (To be fair, I don't recall whether I was talking to Fisher at the time, or to someone who invited him. Probably an inviter.)

As to the experimental truth of this, well, there's probably a lot of experimentation and compiler jockeying swirling around the fact that Itanium 2 issues eight parcels per cycle, the same as POWER7.

I think Intel was sold a bill of good on this; some folks from HP were the prime movers in its joint inception.

But it hardly matters. Itanium, incorporating the new magic of VLIW and moving on from the X86 instruction set, was originally going to be Intel's path to 64-bit computing. If anybody remembers that. Then AMD did a successful, upward-compatible, X86-compatible 64-bit architecture. The die was cast, and Itanium became a long-term dead end. (Just like IBM and the PS/2's microchannel vs. the ISA I/O bus.)

Can it be made to work adequately? Sure. Intel's Itanium is far from a pig; it's established a small place in the big-iron category. Additionally, there are still people doing research on VLIW, and more power to them. Just because something is unpalatable initially doesn't mean that gnawing on it some more won't uncover something quite worthwhile.

By the Way, I Left Out Some Hard Stuff

Like, a lot of hard stuff. In particular, once you start initiating integer and FP ops at the same time, in Superscalar or otherwise, they probably don't finish in the same order they were started.

Oops. Or OoO (Out-of-Order) execution.

This produces significant additional complexity in the dependence analysis needed to tell when instructions in the queue (or whole parcel groups) can start executing. And it just gets worse when you include memory operations, which I've left out for simplicity, just because memory operations take a long time.

Furthermore, with all those instructions running at the same time in different units, which one(s) do you punt when a branch comes along?

And in addition, doing multiple instructions per cycle is not very useful unless you can store back multiple results per cycle into your register file. (For example, POWER 7 can retire 5 results per cycle.) There's also the other end: You have to be able to read multiple registers simultaneously, too.

All this can be, and has been, handled. But it's hardly trivial. It requires lots of transistors to squeeze a single instruction stream to be as parallel as it can, which isn't very.

Enter Simple Multicore

So pity the poor core designer/architect, trying to make systems go ever faster, pounding his head against this rock of an obstacle, being more clever than anybody thought possible, but still getting ever-decreasing returns from tsunamis of transistors thrown against the problem.

Is it any wonder that they punted to software again?

But that's not what is said. I suspect many don't realize that's what they did.

What I'm referring to is, of course, the use of many simple cores, immortalized in thousands of presentations of near-meaningless diagrams like this one:

This is so common it's now part of the standard canon. Everybody knows it. It's accepted fact. Don't believe it, and you've branded yourself a Neanderthal. Right?

Basically, it claims that four (always seems to be four…) small, simple cores, the kind described earlier as just pipelined, give more performance than you get with one of those old-fashioned, big, bad, hot, complicated cores.

Well, sure. They can. But let's all understand that this is punting to software big time: Instead of finding parallelism in one instruction stream, programs must be explicitly split up into multiple instruction streams.

And, of course, the kinds of performance measures always quoted for lots of simple cores always assume perfect scaling – splitting into four actually achieves four times the performance. This doesn't happen. You don't get perfect performance out of OoO, Superscalar or VLIW, either, and the comparison does take those well-known limitations into account. So it's the known (to hardware guys) imperfect compared with the unknown (to hardware guys) perfect, an inherently unfair comparison.

Fortunately, there actually is very good scaling possible on a lot of commercial processing; think many individual accesses to a web site. Many, not all, technical / HPC programs scale rather well, too.

Unfortunately, none of those is the client-side volume market needed for any killer app which might support the industry. It may work, with additional hardware support, for power reduction (see my prior post about Parallel PowerPoint), but so far that's a road not taken.

Parallel PowerPoint: Why the Power Law is Important

The notion of "parallel PowerPoint" is a poster child for the uselessness of multicore on client computers. Rendering a slide two, four, eight times faster is a joke. Nobody needs it.

Running PowerPoint 4, 16, 64 times longer on my laptop battery, though, that's useful. I am purely sick of carrying around a 3 lb. power supply with my expensively light, carbide case, 3 lb. laptop.

This is why the Parallel Power Law – if the hardware is designed right, the processor power can drop with the square of the number of processors – is important. I'd like to suggest that it is a, possibly the, killer app for parallelism.

There are two keys here, the source of both I discussed in the previous post, the Parallel Power Law. One key is reduced power, of course: Double the processors and halve the clock rate, with associated reduced voltage, and the power drops by 4X (see that post). That decrease doesn't happen, though, unless the other key is present: You don't increase performance, as parallel mavens have been attempting for eons; instead, you keep it constant. Many systems, particularly laptops and graphics units, now reduce clock speed under heat or power constraints; but they don't maintain performance.

The issue is this: All the important everyday programs out there run with perfectly adequate performance today, and have done so for nigh unto a decade. Email, browsers, spreadsheets, word processors, and yes, PowerPoint, all those simply don't have a performance issue; they're fast enough now. Multicore in those systems is a pure waste: It's not needed, and they don't use it. Yes, multiple cores get exercised by the multitasking transparently provided by operating systems, but it really doesn't do anything useful; with a few exceptions, primarily games, programs are nearly always performance-gated by disk or network or other functions than by processing speed. One can point to exceptions – spreadsheets in financial circles where you press F5 (recalculate) and go get coffee, or lunch, or a night's sleep – but they scarcely are used in volume.

And volume is what defines a killer app: It must be something used widely enough to soak up the output of fabs. Client applications are the only ones with that characteristic.

What I'm trying to point to here appears to be a new paradigm for the use of parallelism: Use it not to achieve more performance, but to drastically lower power consumption without reducing performance. It applies to both traditional clients, and to the entire new class of mobile apps running on smart phones / iPads / iGoggles that is now the fastest-expanding frontier.

For sure, the pure quadratic gains (or more; see the comments on that post) won't be realized, because there are many other uses of power this does not affect, like displays, memory, disks, etc. But a substantial fraction of the power used is still in the processor, so dropping its contribution by a lot will certainly help.

Can this become a new killer-app bandwagon? It's physically possible. But I doubt it, because the people with the expertise to do it, the parallel establishment, is too heavily invested in the paradigm of parallel for higher performance, busily working out how to get to exascale computation, with conjoined petascale department systems, etc.

Some areas definitely need that level of computation; weather and climate simulation, for example. But cases like that, while useful and even laudable, are increasingly remote from the volumes needed to keep the industry running as it has in the past. Parallelism for lower power is the only case I've seen that truly addresses that necessarily broad market.

The Parallel Power Law

Do a job with 2X the parallelism and use 4X less power -- if the hardware is designed right. Yes, it's a square law. And that "right" hardware design has nothing to do with simplifying the processor design.

No, nobody's going to achieve that in practice, for reasons I'll get into below; it's a limit. But it's very hard to argue with a quadratic in the long run.

That's why I would have thought this would be in the forefront of everybody's mind these days. After all, it affects both software and hardware design of parallel systems. While it seems particularly to affect low-power applications, in reality everything's a low-power issue these days. Instead, I finally tracked it down, not anywhere on the Interwebs, but in physical university library stacks, down in the basement, buried on page 504 of a 1000-page CMOS circuit design text.

This is an issue that has been bugging me for about five months, ever since my post Japan Inc., vs. Intel – Not Really. Something odd was going on there. When they used more processors, reducing per-processor performance to keep aggregate performance constant, they appeared to noticeably reduce the aggregate power consumption of the whole chip. For example, see this graph of the energy needed to execute tomcatv in a fixed amount of time (meeting a deadline); it's Figure 12 from this paper:

In particular, note the dark bars, the energy with power saving on. They decrease as the number of processors increases. The effect is most noticeable in the 1% case I've marked in red above, where nearly all the energy is spent on actively switching the logic (the dynamic power). (Tomcatv is a short mesh-generation program from the SPEC92 benchmark suite.)

More processors, less power. What's going on here?

One thing definitely not going on is a change in the micro-architecture of the processors. In particular, the approach is not one of using simpler processors – casting aside superscalar, VLIW, out-of-order execution – and thereby cramming more of them onto the same silicon area. The simplification route is a popular direction taken by Oracle (Sun) Niagara, IBM's Blue Genes, Intel's Larrabee, and others, and people kept pointing me to it when I brought up this issue; it's a modern slightly milder variation of what legions of I'm-an-engineer-I-don't-write-software guys have been saying for decades: armies of ants outperform a few strong horses. They always have, they always will, but on the things ants can do. Nevertheless, that's not what's happening here, since the same silicon is used in all the cases.

Instead, what's happening appears to have to do with the power supply voltage (V_DD) and clock frequency. That leaves me at a disadvantage, since I'm definitely not a circuits guy. Once upon a time I was EE, but that was more decades ago than I want to admit. But my digging did come up with something, so even if you don't know an inductor from a capacitor (or don't know why EE types call sqrt(-1) "j", not "I"), just hang in there and I'll walk you through it.

The standard formula for the power used by a circuit is P = CV²f, where:

C is the capacitance being driven. This is basically the size of the bucket you're trying to fill up with electrons; a longer, fatter wire is a bigger bucket, for example, and it's more work to fill up a bigger bucket. However, this doesn't change per circuit when you add more processors of the same kind, so the source of the effect can't be here.

f is the clock frequency. Lowering this does reduce power, but only linearly: Halve the speed, you only halve the power, so two processors each half the speed use the same amount of power as one running full speed. You stay in the same place. No help here.

V is the power supply voltage, more properly called V_DD to distinguish it from other voltages hanging around circuits. (No, I don't know why it's a sagging double-D.) This has promise, since it is related to the power by a quadratic term: Halve the voltage and the power goes down 4X.

Unfortunately, V doesn't have an obvious numerical relationship to processor speed. Clearly it does have some relationship: If you have less oomph, it takes longer to fill up that bucket, so you can't run as fast a frequency when you lower the supply voltage. But how much lower does f go as you reduce V? I heard several answers to that which boiled down to "I don't know, but it's probably complicated." One circuit design text just completely punted and recommended using a feedback circuit – test the clock rate, and lower/raise the voltage if the clock is too fast/slow.

But we can ignore that for a little bit, and just look at the power used by an N-way parallel implementation. Kang and Leblibici, the text referenced above, do just that. They consider what happens to power when you parallelize any circuit, reducing the clock to 1/Nth of the original, and combine the results in one final register of capacitance Creg that runs at the original speed, (f_CLK is that original clock speed):

 If the original circuit is really big, like a whole core, its capacitance Ctotal overwhelms the place where you deposit the result, Creg, so that "1+" term at the front is essentially 1. So, OK, that means the power ratio is proportional to the square of the voltage ratio. What does that have to do with the clock speed?

They suggest you solve the equations giving the propagation time through an inverter to figure that out. Here they are, purely for your amusement:

Solve them? No thank you. I'll rely on Kang and Leblibici's analysis, which states, after verbally staring at a graph of those equations for a half a page: "The net result is that the dependence of switching power dissipation on the power supply voltage becomes stronger than a simple quadratic relationship,…" (emphasis added).

So, there you go. More parallel means less power. By a lot. Actually stronger than quadratic. And it doesn't depend on micro-architecture: It will work just as well on full-tilt single-thread-optimized out-of-order super scalar or whatever cores – so you can get through serial portions with those cores faster, then spread out and cool down on nicely parallel parts.

You can't get that full quadratic effect in practice, of course, as I mentioned earlier. Some things this does not count:

• Less than perfect software scaling.
  
• Domination by static, not switching, power dissipation: The power that's expended just sitting there doing nothing, not even running the clock. This can be an issue, since leakage current is a significant concern nowadays.
  
• Hardware that doesn't participate in this, like memory, communications, and other IO gear. (Update: Bjoern Knafia pointed out on Twitter that caches need this treatment, too. I've no clue how SRAM works in this regard, but it is pretty power-hungry. eDRAM, not so much.)
  
• Power supply overheads
  
• And… a lack of hardware that actually lets you do this.
  

The latter kind of makes this all irrelevant in practice, today. Nobody I could find, except for the "super CPU" discussed in that earlier post, allows software control of voltage/frequency settings. Embedded systems today, like IBM/Frescale PowerPC and ARM licensees, typically just provide on and off, with several variants of "off" using less power the longer it takes to turn on again. Starting with Nehalem (Core i7) Intel has Turbo Boost, which changes the frequency but not the voltage (as far as I can tell), thereby missing the crucial ingredient to make this work. And there were hints that Larraabee will (can?) automatically reduce frequency if its internal temperature monitoring indicates things are getting too hot.

But the right stuff just isn't there to exploit this circuit-design law of physics. It should be.


And, clearly, software should be coding to exploit it when it becomes available. Nah. Never happen.


Ultimately, though, it's hard to ignore Mother Nature when she's beating you over the head with a square law. It'll happen when people realize what they have to gain.

The Problem with Larrabee

Memory bandwidth. And, most likely, software cost. Now that I've given you the punch lines, here's the rest of the story.

Larrabee, Intel's venture into high-performance graphics (and accelerated HPC), the root of months of trash talk between Intel and Nvidia, is well-known to have been delayed sin die: The pre-announced 2010 product won't happen, although some number will be available for software development, and no new date has been given for a product. It's also well-known for being an architecture that's clearly programmable with standard thinking and tools, as opposed to other GPGPUs (Nvidia, ATI/AMD), which look like something from another planet to anybody but a graphics wizard. In that context, a talk at Stanford earlier this month by Tom Forsyth, one of the Larrabee architects at Intel, is an interesting event.

Tom's topic was The Challenges of Larrabee as a GPU, and it began with Tom carefully stating the official word on Larrabee (delay) and then interpreting it: "Essentially, the first one isn't as cool as we hoped, and so there's no point in trying to sell it, because no one would buy it." Fair enough. He promised they'd get it right on the 2^nd, 3^rd, 4^th, or whatever try. Everybody's doing what they were doing before the announcement; they'll just keeping on truckin'.

But, among many other interesting things, he also said the target memory bandwidth – presumably required for adequate performance on the software renderer being written (and rewritten, and rewritten…) was to be able to read 2 bytes / thread / cycle.

He said this explicitly, vehemently, and quite repeatedly, further asserting that they were going to try to maintain that number in the future. And he's clearly designing code to that assertion. Here's a quote I copied: "Every 10 instructions, dual-issue means 5 clocks, that's 10 bytes. That's it. Starve." And most good code will be memory-limited.

The thing is: 2 bytes / cycle / thread is a lot. It's so big that a mere whiff of it would get HPC people, die-hard old-school HPC people, salivating. Let's do some math:

Let's say there are 100 processors (high end of numbers I've heard). 4 threads / processor. 2 GHz (he said the clock was measured in GHz).

That's 100 cores x 4 treads x 2 GHz x 2 bytes = 1600 GB/s.

Let's put that number in perspective:

• It's moving more than the entire contents of a 1.5 TB disk drive every second.
  
• It's more than 100 times the bandwidth of Intel's shiny new QuickPath system interconnect (12.8 GB/s per direction).
  
• It would soak up the output of 33 banks of DDR3-SDRAM, all three channels, 192 bits per channel, 48 GB/s aggregate per bank.
  

In other words, it's impossible. Today. It might be that Intel is pausing Larrabee to wait for product shipment of some futuristic memory technology, like the 3D stacked chips with direct vias (vertical wires) passing all the way through the RAM chip to the processor stacked on it (Exascale Ambitions talk at Salishan 20 by Bill Camp, Intel’s Chief Architect/CTO of HPC, p. 21). Tom referred to the memory system designers as wizards beyond his comprehension; but even so, such exotica seems a flaky assumption to me.

What are the levers we have to reduce it? Processor count, clock rate, and that seems to be it. They need those 4 threads / processor (it's at the low end of really keeping their 4-stage pipe busy). He said the clock rate was "measured in GHz," so 1 GHz is a floor there. That's still 800 GB/s. Down to 25 processors we go; I don't know about you, but much lower than 24 cores starts moving out of the realm I was lead to expect. But 25 processors still gives 200 GB/s. This is still probably impossible, but starting to get in the realm of feasibility. Nvidia's Fermi, for example, is estimated as having in excess of 96 GB/s.

So maybe I'm being a dummy: He's not talking about main memory bandwidth, he's talking about bandwidth to cache memory. But then the number is too low. Take his 5 instructions, dual issue, 10 bytes example: You can get a whole lot more than 10 bytes out of an L1 cache in 5 instructions, not even counting the fact that it's probably multi-ported (able to do multiple accesses in a single cycle).

So why don't other GPU vendors have the same problem? I suspect it's at least partly because they have several separate, specialized memories, all explicitly controlled. The OpenCL memory model, for example, includes four separate memory spaces: private, local, constant, and global (cached). These are all explicitly managed, and if you align your stars correctly can all be running simultaneously. (See OpenCL Fundamentals, Episode 2). In contrast, Larrabee has to chokes it all through one general-purpose memory.

Now, switching gears:

Tom also said that the good news is that they can do 20 different rendering pipelines, all on the same hardware, since it's a software renderer; and the bad news is that they have to. He spoke of shipping a new renderer optimized to a new hot game six months after the game shipped.

Doesn't this imply that they expect their software rendering pipeline to be fairly marginal – so they are forced to make that massive continuing investment? When asked why others didn't do that, he indicated that they didn't have a choice; the pipeline's in hardware, so that one size fits all. Well, in the first place that's far less true with newer architectures; both Nvidia and ATI (AMD) are fairly programmable these days (they'd say "very programmable," I'm sure). In the second place, if it works adequately, who cares if you don't have a choice? In the third place, there's a feedback loop between applications and the hardware: Application developers work to match what they do to the hardware that's most generally available. This is the case in general, but is particularly true with fancy graphics. So the games will be designed to what the hardware does well, anyway.

And I don't know about you, but in principle I wouldn't be really excited about having to wait 6 months to play the latest and greatest game at adequate performance. (In practice, I'm never the first one out of the blocks for a new game.)

I have to confess that I've really got a certain amount of fondness for Larrabee. Its architecture seems so much more sane and programmable than the Nvidia/ATI gradual mutation away from fixed-function units. But these bandwidth and programming issues really bother me, and shake out some uncomfortable memories: The last I recall Intel attempting, as in Larrabee, to build whatever hardware the software wanted (or appeared to want on the surface), what came out was the ill-fated and nearly forgotten iAPX 432, renowned for hardware support of multitasking, object-oriented programming, and even garbage collection – and for being 4x slower than an 80286 of the same frequency.

Different situation, different era, different kind of hardware design, I know. But it still makes me worry.


(Acknowledgement: The graphic comparison to 1.5 TB disk transfer, was suggested by my still-wishing-to-remain-anonymous colleague, who also pointed me to the referenced video. This post generally benefited from email discussion with him.)

Intel’s Single-Chip Clus… (sorry) Cloud

Intel's recent announcement of a 48-core "single-chip cloud" (SCC) is now rattling around several news sources, with varying degrees of boneheaded-ness and/or willful suspension of disbelief in the hype. Gotta set this record straight, and also raise a few questions I didn't find answered in the sources now available (the presentation, the software paper, the developers' video).

Let me emphasize from the start that I do not think this is a bad idea. In fact, it's an idea good enough that I've lead or been associated with rather similar architectures twice, although not on a single chip (RP3, POWER 4 (no, not the POWER4 chip; this one was four original POWER processors in one box, apparently lost on the internet) (but I've still got a button…)). Neither was, in hindsight, a good idea at their times.

So, some facts:

SCC is not a product. It's an experimental implementation of which about a hundred will be made, given to various labs for software research. It is not like Larrabee, which will be shipped in full-bore product-scale quantities Some Day Real Soon Now. Think concept car. That software research will surely be necessary, since:

SCC is neither a multiprocessor nor a multicore system in the usual sense. They call it a "single chip cloud" because the term "cluster" is déclassé. Those 48 cores have caches (two levels), but cache coherence is not implemented in hardware. So, it's best thought of as a 48-node cluster of uniprocessors on a single chip. Except that those 48 cluster nodes all access the same memory. And if one processor changes what's in memory, the others… don't find out. Until the cache at random happens to kick the changed line out. Sometime. Who knows when. (Unless something else is done; but what? See below.)

Doing this certainly does save hardware complexity, but one might note that quite adequately scalable cache coherence does exist. It's sold today by Rackable (the part that was SGI); Fujitsu made big cache-coherent multi-x86 systems for quite a while; and there are ex-Sequent folks out there who remember it well. There's even an IEEE standard for it (SCI, Scalable Coherent Interface). So let's not pretend the idea is impossible and assume your audience will be ignorant. Mostly they will be, but that just makes misleading them more reprehensible.

To leave cache coherence out of an experimental chip like this is quite reasonable; I've no objection there. I do object to things like the presentation's calling this "New Data-Sharing Options." That's some serious lipstick being applied.

It also leads to several questions that are so far unanswered:

How do you keep the processors out of each others' pants? Ungodly uncontrolled race-like uglies must happen unless… what? Someone says "software," but what hardware does that software exercise? Do they, perhaps, keep the 48 separate from one another by virtualization techniques? (Among other things, virtualization hardware has to keep virtual machine A out of virtual machine B's memory.) That would actually be kind of cool, in my opinion, but I doubt it; hypervisor implementations require cache coherence, among other issues. Do you just rely on instructions that push individual cache lines out to memory? Ugh. Is there a way to decree whole swaths of memory to be non-cacheable? Sounds kind of inefficient, but whatever. There must be something, since they have demoed some real applications and so this problem must have been solved somehow. How?

What's going on with the operating system? Is there a separate kernel for each core? My guess: Yes. That's part of being a clus… sorry, a cloud. One news article said it ran "Rock Creek Linux." Never heard of it? Hint: The chip was called Rock Creek prior to PR.

One iteration of non-coherent hardware I dealt with used cluster single system image to make it look like one machine for management and some other purposes. I'll bet that becomes one of the software experiments. (If you don't know what SSI is, I've got five posts for you to read, starting here.)

Appropriately, there's mention of message-passing as the means of communicating among the cores. That's potentially fast message passing, since you're using memory-to-memory transfers in the same machine. (Until you saturate the memory interface – only four ports shared by all 48.) (Or until you start counting usual software layers. Not everybody loves MPI.) Is there any hardware included to support that, like DMA engines? Or protocol offload engines?

Finally, why does every Intel announcement of gee-whiz hardware always imply it will solve the same set of problems? I'm really tired of those flying cars. No, I don't expect to ever see an answer to that one.

I'll end by mentioning something in Intel's SCC (née Rock Creek) that I think is really good and useful: multiple separate power regions. Voltage and frequency can be varied separately in different areas of the chip, so if you aren't using a bunch of cores, they can go slower and/or draw less power. That's something that will be "jacks or better" in future multicore designs, and spending the effort to figure out how to build and use it is very worthwhile.

Heck, the whole thing is worthwhile, as an experiment. On its own. Without inflated hype about solving all the world's problems.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - -

(This has been an unusually topical post, brought to you courtesy of the author's head-banging-wall level of annoyance at boneheaded news stories. Soon we will resume our more usual programming. Not instantly. First I have to close on and move into a house. In Holiday and snow season.)

Oh, for the Good Old Days to Come

I recently had a glorious flashback to 2004.

Remember how, back then, when you got a new computer you would be just slightly grinning for a few weeks because all your programs were suddenly so crisp and responsive? You hadn't realized your old machine had a rubbery-feeling delay responding to your clicks and key-presses until zip! You booted the new machine for the first time, and wow. It just felt good.

I hadn't realized how much I'd missed that. My last couple of upgrades have been OK. I've gotten a brighter screen, better graphics, lighter weight, and so on. They were worth it, intellectually at least. But the new system zip, the new system crispness of response – it just wasn't there.

I have to say I hadn't consciously noticed that lack because, basically, I mostly didn't need it. How much faster do you want a word processor to be, anyway? So I muddled along like everyone else, all our lives just a tad more drab than they used to be.

Of course, the culprit denying us this small pleasure has been the flattening of single-thread performance wrought by the half-death of Moore's Law. Used to be, after a couple of years delay you would naturally get a system that ran 150% or 200% faster, so everything just went faster. All your programs were rejuvenated, and you noticed, instantly. A few weeks or so later you were of course used to it. But for a while, life was just a little bit better.

That hasn't happened for nigh unto five years now. Sure, we have more cores. I personally didn't get much use out of them. All my regular programs don't perk up. But as I said, I really didn't notice, consciously.

So what happened to make me realize how deprived I – and everybody else – has been? The Second Life client.

I'd always been less than totally satisfied with how well SL ran on my system. It was usable. But it was rubbery. Click to walk or turn and it took just a little … time before responding. It wasn't enough to make things truly unpleasant (except when lots of folks were together, but that's another issue). But it was enough to be noticeably less than great. I just told myself, what the heck, it's not Quake but who cares, that's not what SL is about.

Then for reasons I'll explain in another post, I was motivated to reanimate my SL avatar. It hadn't seen any use for at least six months, so I was not at all surprised to find a new SL client required when I connected. I downloaded, installed, and cranked it up.

Ho. Ly. Crap.

The rubber was gone.

There were immediate, direct responses to everything I told it to do. I proceeded to spend much more time in SL than I originally intended, wandering around and visiting old haunts just because it was so pleasant. It was a major difference, on the order of the difference I used to encounter when using a brand-new system. It was like those good old days of CPU clock-cranking madness. The grin was back.

So was this "just" a new, better, software release? Well, of course it was that. But I wouldn't have bothered writing this post if I hadn't noticed two other things:

First, my CPU utilization meter was often pegged. Pegged, as in 100% utilization, where flooring only one of my two CPUs only reads 50%. When I looked a little deeper, I saw the one, single SL process was regularly over 50%. I've not looked at any of the SL documentation on this, but from that data I can pretty confidently say that this release of the SL client can make effective use of both cores simultaneously. It's the only program I've got with that property.

Second, my thighs started burning. Not literally. But that heat tells me when my discrete GPU gets cranking. So, this client was also exercising the GPU, to good effect.

Apparently, this SL client actually does exploit the theoretical performance improvements from graphics units and multiple cores that had been laying around unused in my system. I was, in effect, pole-vaulted about two system generations down the road – that's how long it's been since there was a discernible difference. The SL client is my first post-Moore client program.

All of this resonates for me with the recent SC09 (Supercomputing Conference 2009) keynote of Intel's Justin Rattner. Unfortunately it wasn't recorded by conference rules (boo!), but reports are that he told the crowd they were in a stagnant, let us not say decaying, business unless they got their butts behind pushing the 3D web. (UPDATE: Intel has posted video of Rattner's talk.)

Say What? No. For me, particularly following the SL experience above, this is not a "Say What?" moment. It makes perfect sense. Without a killer application, the chip volumes won't be there to keep down the costs of the higher-end chips used in non-boutique supercomputers. Asking that audience for a killer app, though, is like asking an industrial assembly-line designer for next year's toy fashion trends. Killer apps have to be client-side and used by the masses, or the volumes aren't there.

Hence, the 3D Web. This would take the kind of processing in the SL client, which can take advantage of multicore and great graphics processing, and put it in something that everybody uses every day: the browser. Get a new system, crank up the browser, and bang! you feel the difference immediately.

Only problem: Why does anybody need the web to be 3D? This is the same basic problem with virtual worlds: OK, here's a virtual world. You can run around and bump into people. What, exactly, do you do there? Chat? Bogus. That's more easily done, with more easily achieved breadth of interaction, on regular (2D) social networking sites. (Hence Google's virtual world failure.)

There are things that virtual worlds and a "3D web" can, potentially, excel at; but that's a topic for a later post.

In the meantime, I'll note that in a great crawl-first development, there are real plans to use graphics accelerators to speed up the regular old 2D web, by speeding up page rendering. Both Microsoft and Mozilla (IE & Firefox) are saying they'll bring accelerator-based speedups to browsers (see CNET and Bas Schouten's Mozilla blog) using Direct2D and DirectWrite to exploit specialized graphics hardware.

One could ask what good it is to render a Twitter page twice as fast. (That really was one of the quoted results.) What's the point? Asking that, however, would only prove that One doesn't Get It. You boot your new system, crank up the browser and bam! Everything you do there, and you do more and more there, has more zip. The web itself – the plain, old 2D web – feels more directly connected to your inputs, to your wishes; it feels more alive. Result?

The grin will be back. That's the point.

Multicore vs. Cloud Computing

Multicore is the wave of the future. Cloud Computing is the wave of the future. Do they get along? My take: Eh. Sorta. There are the usual problems with parallel programming support, despite hubbub about parallel languages and runtimes and ever bigger multicores.

Multicore announcements in particular have been rampant recently. Not just the usual drumbeat from Intel and AMD; that continues, out to 8-way, 12-way, and onward to the future. Now more extreme systems are showing their heads, such as ScaleMP announcing vSMP for the Cloud, (and also for SMB), a way of gluing together X86 multicore systems into even larger shared-memory (NUMA) systems. 3Leaf is doing also doing essentially the same thing. Tilera just announced a 100-core chip product, beating Intel and others to the punch. Windows 7 has replaced the locking in XP, allowing it to "scale to 256 processors" – a statement that tells me (a) they probably did fix a bunch of stuff; and (b) they reserved one whole byte for the processor/thread ID. (Hope that's not cast in concrete for the future, or you'll have problems with your friendly neighborhood ScaleMP'd Tilera.)

So there's a collection of folks outside the Big Two processor vendors who see a whole lot of cores as good. Non-"commodity" systems – by the likes of IBM, Sun, and Fujitsu – have of course been seeing that for a long time, but the low-priced spread is arguably as the most important in the market, and certainly is the only hardware basis I've seen for clouds.

What's in the clouds for multicore?

Amazon's instance types and pricing do take muticore into account: at the low end small Linux is $0.085/hour for 1 core, nominally 1 GHz; and at the high end, still Linux, you can get "Extra-large High CPU" Linux is $0.68/hour for 8 cores, 2.5GHz each. So, assuming perfect parallel scaling, that's about 20X performance for 8X the price, a good deal. (I simplified 1 Amazon compute unit to 1 GHz. Amazon says it's 1.0-1.2 GHz 2007 Opteron or Xeon.)

Google App Engine (GAE) just charges per equivalent 1.2 GHz single CPU. What happens when you create a new thread in your Java code (now supported) is… well, you can't. Starting a new thread isn't supported. So GAE basically takes the same approach as Microsoft Azure, which treats multicore as an opportunity to exercise virtualization (not necessarily hardware-level virtualization, by my read), dividing multicores down into single core systems.

The difference between AWS, on the one hand, and GAE or Azure on the other, of course makes quite a bit of sense.

GAE and Azure are both PaaS (Platform as a Service) systems, providing an entire application platform, and the application is web serving, and the dominant computing models for web-serving are all based on throughput, not multicore turnaround.

AWS, in contrast, is IaaS (Infrastructure as a Service): You got the code? It's got the hardware. Just run it. That's any code you can fit into a virtual machine, including shared-memory parallel code, all the way up to big hulking database systems.

Do all God's chillum have to be writing their web code in Erlang or Haskell or Clojure (which turns into Java at runtime) or Ct or whatever before PaaS clouds start supporting shared-memory parallelism? But if PaaS is significant, doesn't it have to support E/H/C/Ct/etc. before those chillums will use them? Do we have a chicken-and-egg problem here? I think this just adds to the already long list of good reasons why parallel languages haven't taken off: PaaS clouds won't support them.

And in the meantime, there are of course a formidable barrier to others hosting their own specialty code on PaaS, like databases and at least some HPC codes. Hence the huge number of Amazon Solution Providers, including large-way SMP users such as of Oracle, IBM DB2, and Pervasive, while Google has just a few third-party Python libraries so far.

PaaS is a good thing, but I think that sooner or later it will be forced, like everyone else, to stop ignoring the other wave of the future.

------------------------------------------------------------------

Postscript / Addendum / Meta-note: My apologies for the lack up blog updates recently; I've been busy on things that make money or get me housed. I've something like six posts stacked up to be written, so you can expect more soon.