The “high-level CPU” challenge (2008)

http://yosefk.com/blog/the-high-level-cpu-challenge.html

by pw • 11 years ago

57 58 11 years ago

_chris_2• 11 years ago

2008? So... anything happen since? I assume nobody took him up on his offer!

"Alan Kay: [...] "Just as an aside [...] a benchmark from 1979 at Xerox PARC runs only 50 times faster today. Moore’s law has given us somewhere between 40,000 and 60,000 times improvement in that time. So there’s approximately a factor of 1,000 in efficiency that has been lost by bad CPU architectures.""

Is he complaining that machines today aren't a bunch of micro-coded, multi-chip computers like in the good old days, or does he have a better proposal to the modern multi-core, superscalar OoO processors coupled to GPGPU multi-threaded engines?

Because complaining about Moore's Law feels a bit meaningless if DRAM is still 100ns away.

_yosefk5• 11 years ago

In 2015 I find the claim that you could beat Intel by 1000x with a better arch much more idiotic than I did in 2008. Because apart from it being idiotic from a technical standpoint I'm now dumbfounded by the extent of its idiocy from the business angle. If you're so smart, what's stopping you from making a trillion dollars off it?

You need to be an Alan Kay to utter such bullshit repeatedly and still have crowds of worshippers taking each of your utterances as gospel while chanting that you singlehandedly invented computing as we know it.

creshal• 11 years ago

You'd think there are enough universities working on research processor architectures that a 10x would have popped up by now, if you can theoretically make a 1000x one.

I'd rather point the blame on software: If we were banging on hardware directly like in the 70s, we'd probably see a massive performance boost, too… just hope that your customers accidentally happen to have the hardware you optimized for and don't want to run anything else on it.

CyberDildonics• 11 years ago

I don't know if 1000x is something that can be backed up, but the difference between a program written with poor memory locality and one written with great locality plus 256 bit SIMD can give a performance boost of around 100x.

This isn't theoretical, I've done it personally and this is just one core.

So the claims are anything but outrageous although that is basically what GPUs are - transistors going to actual FLOPS instead of dealing with memory latency.

Intel cores however are structured like this because most code isn't written with cache locality in mind, they are written in god awful pointer chasing spaghetti styles so all the work that Intel puts in to make that go fast pays off.

Skylake almost had SIMD scatter and gather, which could have been an enormous boost to properly written software, but they had no reason to put it in when they are curb stomping AMD on one hand, and very little software takes advantage of the SIMD units they have now on the other.

sklogic7• 11 years ago

It's trivial to beat a generic CPU by 1000x with a specialised ASIC or even an FPGA in many cases (think cryptography, for example).

stevejones• 11 years ago

You'd be better off working out a way to compile smalltalk to FPGA.

mseebach• 11 years ago

What exactly is the benchmark? Is it, say, pure CPU-bound maths? Because a lot of the work between 1979 and today has been about getting the right numbers to the CPU faster, not (just) for the CPU to actually do the math on the numbers.

One of the biggest leaps in general computing performance in recent years have been the general availability of SSDs. SSDs makes you computer significantly faster, but not by changing anything about the CPU.

venomsnake• 11 years ago

I would kindly show Mr. Kay god of war 2 on the original PS2. Which is incredible tribute to what can be squeezed out of modest hardware.

We have glaring inefficiencies in every level of the software development and runtime stack. I have been writing software for 20 years. The sluggishness of the software, difficulty of writing and debugging has remained constant. Creating a modern Boostrap singlepage app is as difficult and time consuming as the old MFC 4.0 stack. Similar speed of delivery too.

Hardware is fast enough. We just don't bother using it.

kragen8• 11 years ago

I dug into the 50× claim in https://www.mail-archive.com/kragen-tol@canonical.org/msg001.... Basically Alan was saying that the all-ECL Dorado, which was never sold commercially but might have cost US$100k per computer if it had been, was 50× slower than modern (2005) embedded RISC processors that cost US$150 per computer.

Omitting the three orders of magnitude in performance due to sheer brute cost is how you get to "only 50 times faster today". There's an additional order of magnitude of overhead in Squeak's bytecode-interpretation strategy, which was a good strategy on the Dorado but not on an AMD64; you can squeeze that out with JIT, and you get to four orders of magnitude discrepancy between Kay's offhand claim and reality. If you build a 500-node cluster and use a modern JIT compiler on it, the "efficiency that has been lost by bad CPU architectures" evaporates.

As you implicitly point out, though, this is parallel performance, not serial performance.

Kay's group has done a substantial amount of awesome research since he said that in 2007, dramatically exceeding Kay's expectations for performance on modern machines. To a great extent, Kay's Communication Design Group (funded by VPRI and SAP) is the closest thing we have today to the 1970s Xerox PARC, pioneering new enabling technologies and interaction paradigms.

hga2• 11 years ago

Also worth pointing out is that ECL processors were specialized hot rods, not in the main line of contemporary computer systems aside from supercomputers and the very high end of mainframes like the top of the line DEC KL10 PDP-10 CPU, Vax 8000 family, and IBM 360/91.

They were expensive to design and run (traded power dissipation for speed), and eventually CMOS caught up with ECL.

sourceless2• 11 years ago

https://www.cs.york.ac.uk/fp/reduceron/

It's still fairly young technology but there has been work on processors for HLLs. The one above (if my understanding is correct) is effectively a combinator processor, and its input language is a subset of Haskell.

(and now I notice it's already linked in the article comments, but I'll keep it here for those interested.)

_chris_2• 11 years ago

Yah, the author does a follow-up blogpost (albeit, only a few days later, and not years, hehe).

http://yosefk.com/blog/high-level-cpu-follow-up.html

sourceless2• 11 years ago

I don't 100% agree with the author that the reduceron is a "Haskell Machine" - it seems very much to be the motivation for the project, but I think it's more of a 'strongly typed functional language machine'.

I'd be inclined to think that the more general machine Yosef wishes for would come with time and more languages implemented. Heck, maybe restricting the kind of languages best supported is a necessary feature - you can't say that von Neumann doesn't best support imperative & procedural languages after all.

chetanahuja2• 11 years ago

A plausible tl;dr of the post could be: "Dreaming up high level instruction sets is useless because today's CPU's spend most of their time waiting for memory access (accept for rare applications doing lots of math on a small amount of data ... e.g. bitcoin mining)

userbinator2• 11 years ago

Dreaming up high level instruction sets is useless because today's CPU's spend most of their time waiting for memory access

...which doesn't make much sense, because the benefit of small but powerful multicycle instructions is precisely so you can spend the time decoding and executing them (and less time fetching them) while the CPU is waiting for some memory access. One factor that many people seem to forget is that instructions also need to be fetched from memory, and the less bandwidth that takes, the better.

chetanahuja2• 11 years ago

Not defending the OP's thesis but clarifying my tl;dr summary of it: Fetching instructions is not the main problem, it's the data that the instructions have to act upon (Hence the exception for the compute heavy, data-light applications.) And since most of the compute power in the world today is basically processing and moving massive amounts of data around, I can see how that thesis would make sense in the general case.

kragen8• 11 years ago

If that were true, we'd all be using desktop Tera MTAs by now.

userbinator2• 11 years ago

Suppose you want to support strings and have a string comparison instruction. You might think that "it's done in the hardware", so it's blindingly fast. It isn't, because the hardware still has to access memory, one word per cycle. A superscalar/VLIW assembly loop would run just as quickly; the only thing you'd save is a few bytes for instruction encoding.

Actually if you've actually looked at things like SSE memory copying/comparison routines, it's not "a few bytes", it's more like a factor of 100x+. REP MOVSB is 2 bytes; a SSE memcpy, highly unrolled - incidentally, also a bad idea for modern CPUs - is easily a few hundred. I've seen ones over a kilobyte(!) The former is essentially the same speed as the latter, but makes for significantly less instruction cache utilisation, which is increasingly important today.

You see, RISC happened for a reason.

When memory bandwidth was not the bottleneck, it was a good idea. Now, not so much. Even ARMs which are considered "RISC" are growing into uop-decoding decoupled OoO machines like x86, and adding more instructions with each new generation. I like to mention this article, where the "purest" RISC, MIPS, turns out to be the least power-efficient:

http://www.extremetech.com/extreme/188396-the-final-isa-show...

I'd say that CPUs are certainly getting more high-level and CISCy, but not in the same way as their original proponents imagined. If you don't think so, try beating POPCNT, CRC32, AESENC, etc. with a sequence of simpler instructions...

renox• 11 years ago

I find strange your point about ARM vs MIPS given that ARMv8 seems much more 'MIPSy' than previous ARM ISAs..

sklogic7• 11 years ago

Why? It's very intentionally not MIPSy. ARMv8 removes anything that may dictate any microarchitecture decisions, while MIPS exposes it in an ISA (delay slots and all that). Even predication had been killed for this reason (it's not good for OoO anyway).

hga2• 11 years ago

When memory bandwidth was not the bottleneck, it was a good idea.

That plus the earlier period in VLSI when there was an extreme premium on the number of gates you put on a single die. If you could fit an entire simplified CPU on a small die you could win big, and this advantage continued as FPUs, cache, and more and more cache were added.

Nowadays gates aren't exactly free, but dies are constrained by other considerations like power and size (yield) balanced against what more gates will gain you. Outside of tiny microcontrollers, I don't think any one is obsessing over the issues that limited the 1978 8086 to 29,000 transistors, or the 1979 68000 to 68,000 (https://en.wikipedia.org/wiki/Transistor_count).

Tuna-Fish• 11 years ago

There are a lot of new kind of more complicated instructions, but they very much follow the basic RISC principles. That is, instructions that do any kind of math take in a few register operands, output into a register, and do so quickly and do not touch any external state. They do not do some math, wait on memory, and do more math based on it, they do not access complex internal state, etc. The only exception to this are the x86 string instructions, and even they store all their state in registers during interrupts.

Basically, RISC at some point meant {reduced instruction set} computer, now it means {reduced instruction} set computer.

rasz_pl• 11 years ago

"Suppose you want to support strings and have a string comparison instruction. You might think that "it's done in the hardware", so it's blindingly fast. It isn't, because the hardware still has to access memory,"

well, there is this: http://www.micron.com/about/innovations/automata-processing

baq• 11 years ago

in fact lots of standard big O complexity analysis assumes a von Neumann machine – O(1) random access.

i don't see the logic here.

lsd5you2• 11 years ago

Memory lookup can be considered O(log(m)) where m is the amount of memory you are using. e.g. If the addressable memory space exceeds the word size then it would take two cycles to do a load from memory.

In practice memory lookup is O(1) but there is hard limit to the amount that can be used. Except of course this is not true - there are costs to using more memory - because of the cache hierarchy.

adrianN• 11 years ago

In practice, whether memory lookup is constant time or log time depends on your access pattern. The TLB makes random lookups more expensive. See for example

https://people.mpi-inf.mpg.de/~tojot/papers/TowardBetterComp...

kragen8• 11 years ago

If we're really going to talk about memories of over 2⁶⁴ bytes, in the limit it's O(m^⅓) if you're talking about latency, because larger memories need to be physically further away, on average.

sklogic7• 11 years ago

The future might be in an FPGA fabric tightly coupled with generic RISC cores (things like Zynq SoCs, but with a tighter integration, allowing a direct access from FPGA to the CPU internal registers, pipelines, etc.). Bigger macro cells (like entire ALUs, generic caches, etc.) might be useful too.

This way hot spots can be optimised (even in a JIT engine in runtime) into hardware circuits.

I played a bit with some crazy ideas like mixing HDLs with a low level C code (see the Mandelbrot example here: https://github.com/combinatorylogic/soc/tree/master/backends... ) - this sort of things can become practical with a tighter integration between a CPU core and FPGA fabric (in my case it was a soft core, of course).

moron4hire2• 11 years ago

All the EEs I know think 1000 lines of code is "a lot". I've never met any EEs that used source control. I've never met any that tracked issues beyond forwarding emails back and forth. Their idea of documentation is separate PDFs for electrical properties and programming APIs.

So if us software engineers don't know the hardware side well enough to design hardware, I'm not really sure electrical engineers understand the software side well enough to design hardware, either.

Not saying there aren't EEs that understand software. Just saying I've never met any.

EDIT: wait, I know one EE who uses source control. I finally got my wife to start using Git. She kept looking over my shoulder at home, asking me "what is that?" pointing at my changelog in SourceTree. "Oh, you know, it's just an annotated record of every change every member of the project has ever made, including when they did it, in such a way that we can share these changes with each other without having to have long discussions about which particular folder on which particular network drive is the 'latest' code. Oh, you think that would be helpful in your work? Who would have thought?"

sklogic7• 11 years ago

Every EE company I worked for used source control (perforce, git or svn). And a typical Verilog module is far longer than 1000 lines.

moron4hire2• 11 years ago

If it weren't a meme, it wouldn't be a meme.

cyanoacry• 11 years ago

Two things:

1) Of course, anecdotes don't prove the general case.

2) There's some conflation here between knowledge of toolchains and knowledge of software. Arguably, they are not the same--they might be orthogonal domains of knowledge. Knuth (who knows a lot about CS) does not use email, and I would be surprised if he used git for his books.

sriku3• 11 years ago

Aren't GPUs a good enough example of hardware that can be programmed to do things way faster than what is possible with CPUs of the same era?

Also what about FPGAs? If compiling a specific program down to an FPGA is possible, what kinds of optimizations can we bring in? (I am indeed waving my hands here, but we already have had genetic-proframming optimized FPGAs for over 15 years in research.)

_yosefk5• 11 years ago

Isn't it obvious after all these years that gpus or fpgas give hlls nothing?? Nobody actually runs hlls there, even! And everyone had years and years to try! On these machines in reality hll performance blows much much harder than on cpus and at what point does it become obvious that nobody doing something must be due to reasons that can be learned and understood instead of ignored?

I wrote tfa to explain some of those reasons and nobody seems to read it, they just keep saying what they always do.

Someone is wrong on the Internet!!

sklogic7• 11 years ago

Matlab is quite a HLL, and it benefits a lot from GPUs. LabView is a HLL too, obviously.

Not to mention numerous DSLs (also pretty high level) running on GPUs (e.g., I'm running a derivative of the OpenSCAD language on a GPU, for a fast and precise slicing). As HLL as it gets.

sriku3• 11 years ago

I didn't state my point clearly. My point was not that GPUs give some new capability to HLLs, but that GLSL itself is higher level for a restricted domain than what is afforded by a general purpose processor ... and, owing to their specialization, GPUs are faster than normal CPUs.

FPGAs blur what it means to "run a HLL", since you can optimize the circuitry to a point where there is no explicit representation of the "code" or "microcode" anywhere so the question becomes pointless. Heck even what part of physics is used is blurred! [1,2]

[1] https://en.wikipedia.org/wiki/Evolvable_hardware (Ref: Adrian Thompson's work)

[2] http://www.damninteresting.com/on-the-origin-of-circuits/

Bognar• 11 years ago

I don't think a GPU is significantly faster than a CPU, it's just highly parallelized. Many FPGAs are similar, but it's hard to generalize that space. FPGAs and ASICs are also usually designed with a specific task in mind and are not suitable for general computing.

sriku3• 11 years ago

That line of reasoning would take the shape of a "no true scotsman".

As long as we're talking about alternative hardware architectures that can enable computation speeds otherwise not possible, we ought to include parallel computers, GPUs, FPGAs in the mix. The connection machine doesn't count?

Why exclude FPGAs? As long as I can have a program that will reprogram an auxiliary FPGA to do what I want more efficiently, it counts as an alternative processor with a potentially odd architecture where a gate acts as a switch in one program and works as a memory bit in another. They are named "programmable" for a reason.

Symmetry3• 11 years ago

Well, the obvious place to start is via using separate memory channels. If you have separate load/store queues for the stack and heap you can have substantially higher max performance for the same area/power since the cost of that structure scales super-linearly. But that means you can't have arrays with a mix of pointers to heap and stack allocated objects.

That's one of the things the Reduceron (mentioned elsewhere) does.

_yosefk5• 11 years ago

I plan to write about it; the thing is, the Reduceron is not a more performant machine when all is said and done. Memory costs you a lot in area and power and throwing channels at the problem needlessly and saying youve solved the von neumann bottleneck is a worse idea than trying to avoid banging at the memory needlessly; using C is a part of a working strategy to acheive the latter.

Symmetry3• 11 years ago

Breaking up the load/store queue would basically just be a way of increasing parallelism at the core level for free. You wouldn't be changing the amount of memory in caches, just increasing the rate at which you can issue loads or stores and the number of outstanding accesses the core could support. Well, you might consider a split L1D but there are lots of tradeoffs with that and you'd have to simulate to figure out if that'd be a good idea.

JoeAltmaier• 11 years ago

Further, separate the call stack from the 'display' or local variable stack. Conflating them causes bugs, is appropriate only for some code models, and makes it harder on tools. Computers didn't used to work this way; some paper got published about combining them and everybody after went the one-stack direction by default. It doesn't make a lot of sense today.

Symmetry3• 11 years ago

I should also say that if you're designing a core for a specific workload there are always ways you can optimize it but that doesn't have anything to do with high or low level languages. See the presentation on the M6 at Hot Chips for the way they tuned their cache hierarchy to work with their database.

The talk is on the Day 2 track here: http://www.hotchips.org/archives/2010s/hc26/

rthomas6• 11 years ago

Surely there is some improvement to be made by automatically parallelizing map and filter functions, and for side-effect free languages, automatically parallelizing functions that do not share state? Maybe this is more on the compiler side than the hardware side, but wouldn't this potentially provide a significant speedup if you have a lot of cores to take advantage of? A speedup that you can't get from procedural programming languages?

The “high-level CPU” challenge (2008)

Related Stories