Scaling To a Million Cores and Beyond

mattaw writes "In my blog post I describe a system designed to test a route to the potential future of computing. What do we do when we have computers with 1 million cores? What about a billion? How about 100 billion? None of our current programming models or computer architecture models apply to machines of this complexity (and with their corresponding component failure rate and other scaling issues). The current model of coherent memory/identical time/everything can route to everywhere; it just can't scale to machines of this size. So the scientists at the University of Manchester (including Steve Furber, one of the ARM founders) and the University of Southampton turned to the brain for a new model. Our brains just don't work like any computers we currently make. Our brains have a lot more than 1 million processing elements (more like the 100 billion), all of which don't have any precise idea of time (vague ordering of events maybe) nor a shared memory; and not everything routes to everything else. But anyone who argues the brain isn't a pretty spiffy processing system ends up looking pretty silly. In effect, modern computing bears as much relation to biological computing as the ordered world of sudoku does to the statistical chaos of quantum mechanics.

Comments

1 billion cores

[should_be_linear]

thats about 30 forks(), and there you go.

Re:1 billion cores

[BhaKi]

Wrong. You need 999999999 forks.

Re:1 billion cores

[TheSpoom]

I'm pretty sure the poster meant to do something like this:

fork();
fork();
fork(); // etc.

which would make the number of processes increase exponentially every time the forked processes forked again. Not 1, 2, 3, but 1, 2, 4, 8, 16... and 2^30 gets you above 1 billion.

multi core design

[girlintraining]

Simply put, there are some computational problems that work well with parallelization. And there are some that no matter how you try to approach it, you come back to a serial-based model. You could have a billion core machine running at 1Ghz get stomped by a single core machine running at 1.7Ghz for certain computational processes. We have yet to find a way computationally or mathematically to make intrinsically serialized problems into parallel ones. If we did, it would probably open up a whole new field of mathematics.

Re:multi core design

[jd]

You cannot parallelize a serial task, any more than you can have 60 people dig one posthole in one second. On the other hand, there are MANY tasks that are inherently parallel but which are serialized because either the programmers aren't up to the task, the OS isn't up to the task or the CPU isn't up to the task.

(I don't know if kernel threads under Linux will be divided between CPUs in an SMP system, they certainly can't migrate across motherboards in any MOSIX-type project. That limits how parallel the bottlenecks in the program can ever become. And it's one of the best OS' out there.)

Re:multi core design

[Your.Master]

Actually, you can to some extent serialize a parallel task, with sufficiently many cores.

For instance, you could just guess at all the intermediate results of halfway through a long sequence of operations, and execute from there, but discard the information if it's wrong. With lots of cores and a good chokepoint, you might be able to gain a 2x speedup a significant percent of the time (for a lower average speedup). 2x, that is, from billions of cores.

Kind of like branch prediction, or a dynamically generated giant lookup table.

It just isn't a very efficient speedup, at all, compared to the gains of even modestly parallelizable tasks.

Re:multi core design

[Anonymous Coward]

If one is willing to use the transistors of a billion core machines to speed up a single problem anyway, some transistors could be better used to accelerate the specific problem in the form of custom circuits. There could be a similar layered structure in the system as the brain uses. The lowest, fastest and task customized levels could be build using hard-wired logic, the layer above it using slowly reconfigurable circuits with very fast switching speeds, the layers above easily reconfigurable circuits with slower switching speeds and the highest level using the normal general purpose logic. A higher level could train and use the services of a lower level just like the brains might do in a case of a phobia, trauma or some psychosomatic condition. New sub fields of computer science and computer engineering of a computer psychologist and a computer psychiatrist might be created out of necessity..

Re:multi core design

[jd]

You've got to be careful when talking about threads. There are four basic models: SISD, SIMD, MISD and MIMD. Of those, only SISD is serial, but if you've two independent SISD tasks, you can run them in parallel. Most modern supercomputers are built on the premise that SIMD is good enough. Not sure where MISD is used, MIMD fell out of favour when vector processors became too expensive but may be revived on more modest CPUs with modern interconnects like Infiniband.

Re:multi core design

[William Robinson]

Not sure where MISD is used

Back in 1987, when I was part of team that was designing parallel processing machine, with 4 neighboring CPUs sharing common memory (apart from their own local memory, kind of systolic array), we were designing machine suitable to simulate aerodynamics or weather forecasting using diffusion equations. We believed that it was working on MISD model, where different algorithms running in different CPUs utilized same data for analysis, using bus arbitration logic.

Re:multi core design

[smallfries]

While turning intrinsically serial problems into a parallel form would certainly open up a new field it is doubtful that it would be a "a whole new field of mathematics" or did you just like the sound of your hyperbole?

On a slightly different note; every time there is any article about parallel architecture on slashdot someone raises the problem of inherently serial tasks. Can you name any? Or more to the point can you name an inherently serial task on a realistically sized data-set that can't be tackled by a single 2Ghz core?

It would seem that we have scaled single-core performance to the point that we don't care about serial tasks any more. All of the interesting performance hogs that we do care about can be parallelised.

Re:multi core design

[WillDraven]

You cannot parallelize a serial task, any more than you can have 60 people dig one posthole in one second.

We do it all the time around here:
1 to operate the pile driver
2 holding up stop/slow signs
3 riding in the "follow me" vehicle
4 standing around supervising
5 cops writing tickets in the surrounding 8 mile work zone
10 administrators to approve the project
15 residents jumping out of bed at 6am thinking it'a a bomb going off
20 people sitting in their cars honking their horns for motivational support

Of course the whole procedure and traffic carnage can last for months or years, but the actual post being rammed in only takes a second. ;-)

Re:multi core design

[James Manning]

How would you know that the calculations were wrong?

You know later. It's similar to things like the EPIC arch where you might (for example) execute both sides of a branch in parallel, but you don't 'commit' the results until you get the results of the predicate bits, at which point you'll throw away one side's results and commit the other side's.

http://en.wikipedia.org/wiki/Explicitly_parallel_instruction_computing

Predicated execution is used to decrease the occurrence of branches and to increase the speculative execution of instructions. In this feature, branch conditions are converted to predicate registers which are used to kill results of executed instructions from the side of the branch which is not taken.

http://en.wikipedia.org/wiki/Speculative_execution

Bluudy Blogs

[jd]

• Hardware design tools
• Transactional Memory
• TERAFLUX: Exploiting Dataflow Parallelism in Teradevice Computing
• SpiNNaker - A Universal Spiking Neural Network Architecture
• The Balsa Asynchronous Synthesis System

I've left out links to some projects, by request, but everything can be found on their homepage anyway. Anyways, it is this combination that is important, NOT one component alone.

Re:Better be running OSS

[jd]

I don't know about this specific project, but Manchester is strongly Open Source. The Manchester Computer Centre developed one of the first Linux distributions (and - at the time - one of the best). The Advanced Processor Technologies group has open-sourced software for developing asynchronous microelectronics and FPGA design software.

Manchester University is highly regarded for pioneering work (they were working on parallel systems in 1971, and developed the first stored-program computer in 1948) and they have never been ashamed to share what they know and do. (Disclaimer: I studied at and worked at UMIST, which was bought by Manchester, and my late father was a senior lecturer/reader of Chemistry at Manchester. I also maintain Freshmeat pages for the BALSA projects at APT.)

Problems with this blog.

[Anonymous Coward]

The problem posed by the author is somewhat of a straw man argument: "The trouble is once you go to more than a few thousand cores the shared memory - shared time concept falls to bits."

Multiple processors in a single multicore aren't required even today to be in lockstep in time (it is actually very difficult to do this). Yes, locally within each core and privates caches they do maintain a synchronous clock, but cores can run in their own clock domains. So I don't buy the argument about scaling with "shared time".

Secondly, the author states that the "future" of computing should automatically be massively parallel. Clearly they are forgetting about Amdahl's Law (http://en.wikipedia.org/wiki/Amdahl's_law). If your application is 99.9% parallelizable, the MOST speedup I can expect to achieve is 1000X, forget about millions. High sequential performance (ala out-of-order execution, etc.) will not be going away anytime in the near future simply because they are best equipped to deal with serial regions of an application.

Finally, I was under the impression that they were talking about fitting "millions" of cores onto a single die, until I read the to the end of the post that they are connecting multiple boards via multi-gigabit links. Each chip on a board has about 20 or so cores with privates caches or local store. They talk to other cores on other boards through off-chip links...... SO isn't this just a plain old message passing computer?! What's the novelty here? Am I missing something?

Re:Problems with this blog.

[jd]

The main problem is that it's horribly hard to pass that many messages around without the overheads of the network exceeding the benefit from the parallelization. If they have found a way to reduce this problem, I'd call that a major novelty.

Re:Problems with this blog.

[GPSguy]

In weather forecasting, we find ourselves starting, stopping and waiting. Some of the tiles on which we compute will be trivially simple to complete, while others will not run to something approaching a numerically complete solution for some larger number of iterations. Ttherefore, we have to wait for the slowest computation/solution before we advect results to the surrounding tiles and begin the process all over again.

The nature of parallel problems isn't so simple that you generalize about how synchronization isn't important. I've also got examples of two parallel codes which have to stop, synchronize data and restart, which is very inefficient. The ability to scale the combination of shallow water equations and non-hydrostatic weather codes into a large, embarassingly parallel system would be a Good Thing for earth-system modeling in general, but is practically difficult, both in its core nature and because message passing isn't trivial at some point in a large MPI system. It simply becomes unwieldy and breaks down.

When you're parallizing a Monte Carlo problem, you can achieve significant speedup with little concern for asynchrony.When you submit a problem where each computation requires waiting for all of its surrounding neighbors, asynchrony, using conventional approaches becomes problemmatical.

I suspect that, while this project might not demonstrate 1megacore high performance, that they're on the right path.

If you look at today's multicore processor HPC, you see some (relatively) small number of cores on a single board, communicating at higher speeds than inter-board links, but the interboard links tend to be sorta fast, and tied to an interconnect fabric of some sort. This can be faster or slower depending on the base technology, and little things like bisectional bandwidth, and subscription. If one's not running some form of OpenMP (essentially threaded) environment, which also often equates to SM but doesn't mandate it, one can take significant advantage of the on-board higher speed interconnects. What's off the board doesn't affect your outcome.

On the other hand, if you have to subscribe to DM-parallelism, today's offerings are similar with minor tweaks in performance: MPICH, MPICH2, OpenMPI, etc., all striving to give the best multi-NODE intercommunication one can broadcast, and then gather back in. One of the key drawbacks, however, is that most times, I/O is scatter-gather, or, essentially serial. One, or some small subset of intercommunicating nodes gathers all the results, decides how to parse them, and/or commits them to results.In general, during a big I/O operation, the nodes wait.

In the original author's description, there's a bunch of relatively slow interconnects to allow a new topology of interconnect. A bunch of gigabit doesn't equal a QDR InfiniBand connection, but by not tying the interconnect to a fixed, store and forward interconnect, you just MIGHT gain a bit of efficiency.Somehow, I think 6 GBE interconnects is light, but I'll let better minds than mine optimize that over time.

This may well be a "plain old message passing computer" but it's novel in its reduced dependence on scatter-gather and store-forward technology.

Human brain != computer

[i-like-burritos]

The things we use computers for are different from the things we use humans for.

Computers are consistant and predictable. The human brain is not.

We have billions of human brains cheaply available, so let's use those when we want a human brain. And let's use computers when we want computers.

Re:Human brain != computer

[Wescotte]

but hopeless for calculating with a reasonable degree of accuracy the actual distance to that object- the margin of error for most people is on average going to be quite large.

I disagree. How can we learn to throw a basketball into a tiny hoop from far away without having very accurate estimates? Think of any sport and just how many good estimates are done VERY quickly and pretty damn accurately. How can a painter look at any scene recreate (to scale) what they see on canvas? I'd say are brains are pretty damn good at calculating with very high accuracy.

Just because I can't say the hoop is exactly 32.74578453 feet from me doesn't mean I don't know how far it is away. If I can throw the ball into the hoop then I have accurately calculated/predicted the distance.

Look at how sometimes people are mid-conversation, talking about something they know in depth and suddenly they forget what they were going to say- this is because processing in the brain has gone completely off track.

I'm having a hard time coming up with a good analogy but I suspect these situations are similar to interrupts in computers. Something more important requires the brains resources at that time. It's not like the information is forgotten it's simply not accessible at that movement in time. The information is never "lost" it's just unavailable for a time. If it was lost you wouldn't have the "oh yeah" moments when you remember it or look it up again. You recognize it because you already knew it.

While I agree the brain isn't as effective at large scale number crunching I do believe it's something the brain can be trained to do. There are plenty of people out there who can do insanely complex arithmetic in their heads. I suspect the reason we all don't have such skills is because we don't need them.

but there's a lot that current computers can do that the brain can't- serious large scale number crunching for example

There is no real reason in the survival of the fittest terms for us to be able to accomplish such tasks. So those resources in the brain were put to use on other tasks like accurately processing visual and audio data. I can hear or spot a predator very quickly and accurately in all types of environments and lighting conditions. If we use a computer to perform these tasks we realize just how much computation is required. There is no reason these resources couldn't be allocated to general number crunching. It's just evolution says they are better used for other tasks.

Re:Human brain != computer

[Xest]

"I disagree. How can we learn to throw a basketball into a tiny hoop from far away without having very accurate estimates?"

That was precisely my point, they're still estimates. The human brain can judge based on experience how to throw the ball to get it through a hoop, but can it calculate the distance well enough, and consistently enough to calculated the angle from the feet of the thrower upto the net to perform some action such as a precise manufacturing task?

These are two very different things, and are useful for two very different purposes. Being able to throw a ball right some, or even most of the time may be fine for a game of basketball, but is this ability good enough to calculate the values for some complex and precise engineering application? Absolutely not.

"The information is never "lost" it's just unavailable for a time. If it was lost you wouldn't have the "oh yeah" moments when you remember it or look it up again. You recognize it because you already knew it."

Absolutely, it's not lost, the issue is that the brain depends on emergence, and emergent systems can be quite vulnerable to minor variations in the initial conditions. In this case the initial conditions for the moment in question will often be set by the senses, but could also occur as a result of the happenings in the brain at a prior moment, or could be caused by some chemical imbalance (i.e. taking drugs). The problem is that although the information isn't lost as such, it's just hard for the brain to track it down again when it doesn't have the conditions required to get back to that information, again, hence why it can take a while to remember what you were going to say again- it's not easy for the brain to get back to the state required, or a near enough state such that it can get the information it needs. In contrast, it's quite easy in computers, because we have explicit memory addresses and so forth to work with and that can be persisted and referred to- or to put it rather simplistically (and far from perfectly) we don't need to rely on running the execution process again to find the data if we've done things right.

"While I agree the brain isn't as effective at large scale number crunching I do believe it's something the brain can be trained to do. There are plenty of people out there who can do insanely complex arithmetic in their heads. I suspect the reason we all don't have such skills is because we don't need them."

Again, absolutely I agree, but the issue is consistently, you may be able to train it but when it's so vulnerable to minor changes in the way it works, can it do it consistently?

"So those resources in the brain were put to use on other tasks like accurately processing visual and audio data. I can hear or spot a predator very quickly and accurately in all types of environments and lighting conditions. If we use a computer to perform these tasks we realize just how much computation is required."

That's again really the key- the brain is brilliant for some things, so much so that a current style of computer just isn't really fit for the job. It's not so much that a lot of computation is required, it's just that the type of computation we do now is quite different from the type of computation a brain does and this is what TFA is getting at- to solve these sorts of problems we need a different paradigm. What I disagree with though is that we need a different paradigm in general- I don't believe we do because the paradigm being suggested isn't ideal for the things current computers are good at.

As with almost everything, I suspect it's a case of six of one, and half a dozen of the other- there isn't one perfect solution, we ultimately need both solutions for different types of problem, but shouldn't completely write one off at the expense of the other.

To cut a long story short, the fundamental difference is that current computers are largely predictable and formally provable. Brain style computing is chatotic and complex, we know it'll come up with a solution

Re:Better be running OSS

[capo_dei_capi]

This 1-million core machine better be running open source software and not proprietary software.

Yeah, especially if their software is licensed on a per-core basis.

Damaged Brains

[b4upoo]

Some folks with severely damaged brains seem to make better human computers than people with healthy brains. Rain Man leaps to mind as well as other savants. It seems that when some parts of the brain are impaired the energy of thought is diverted to narrower functions. Perhaps we need to think of delivery more energy to less cores to make machines that do tasks that normal humans are not so good at doing.

Link with IMAC ExaScience lab?

[Hedon]

Is it coincidence that earlier this month there was a press release from IMEC regarding the issues of massively scaling up computational power ("exascaling")?
Press blurb can be found here.
Killer application would be "space weather prediction".

Distributed Computing

[thomasinx]

The problems with "coherent memory/identical time/everything can route to everywhere" isnt only seen when you get up to a million cores. I've done plenty of work with MPI and pthreads, and depending on how it's organized, a significant portion of these methods start showing inefficiencies when you get into just a few hundred cores.

Since there are already plenty of clusters containing thousands upon thousands of individual processors (which dont use coherent memory..etc), the step to scale up to a million would likely follow the same logical development. There should already be one or two decent CS papers on the topic, since it's basically a problem that's been around since beowulf clusters were popularized (or even before then)

Last time I run a parallel program...

[ctrl-alt-canc]

...it seemed to me that Amdahl's law was still alive and kicking.

Re:Last time I run a parallel program...

[palegray.net]

Given you statement, why would you link to a document entitled Reevaluating Amdahl's Law? Did you even read what you linked to? Here's an excerpt:

Our work to date shows that it is not an insurmountable task to extract very high efficiency from a massively-parallel ensemble, for the reasons presented here. We feel that it is important for the computing research community to overcome the "mental block" against massive parallelism imposed by a misuse of Amdahl's speedup formula; speedup should be measured by scaling the problem to the number of processors, not fixing problem size. We expect to extend our success to a broader range of applications and even larger values for N.

Transputer, The Next Generation

[Animats]

This is very similar to the Inmos Transputer, a mid-1980s system. It's the same idea: many processors, no shared memory, message passing over fast serial links. The Transputer suffered from a slow development cycle; by the time it shipped, each new part was behind mainstream CPUs.

This new thing has more potential, though. There's enough memory per CPU to get something done. Each Cell processor, with only 256K per CPU, didn't have enough memory to do much on its own. 20 CPUs sharing 1GB gives 50MB per CPU, which has more promise. Each machine is big enough that this can be viewed as a cluster, something that's reasonably well understood. Cell CPUs are too tiny for that; they tend to be used as DSPs processing streaming data.

As usual, the problem will be to figure out how to program it. The original article talks about "neurons" too much. That hasn't historically been a really useful concept in computing.

Re:Reminds me of Hillis

[headhot]

The CM-1 has 65,536 one bit processors. The CM-5 was in Jurassic Park, and some phone companies.

Yep, its not like computers

[Anonymous Coward]

The brain isn't like computers at all. The brain is compartmentalized. There are dozens of separate pieces each with its specialty. Its wired to other pieces in specific ways. There is no "Total Information Awareness"(tm) bullshit going on (what 1 million cores would give you). The problem with TIA is that there is too much crap to wade through. Too big a haystack to find the needle you need. What they found when analyzing Berger-Liaw speech recognition systems against other systems is that the Berger-Liaw system kept temporal (time-based) subtleties, in contrast to other speech recognition systems that were simply digital (with the clock/oscillator sampling in a Nyquist format, destroying or failing to capture temporal information). The Berger-Liaw system can best the best human listeners (which is why the US navy got it instead of it becoming an available commercial product). It could act as a 'sonic input device' using only a tiny neural network (20 to 30 nodes) for superhuman input, instead of the digital ones, giving crappy results with 2048 or 4096 nodes. The brain is wired with a lot of 'specialty components' which use a spare number of components to get the job done. Some of the excess appears to be redundant (although I am not a neural-scientist and could be wrong).

Where to start? software

[CBravo]

My opinion is that you should not require software to be parallelized from the start. You parallelize it during runtime or at compile time.

This makes sense because parallelization does not add anything in functionality (the outcome should not change). My point is: program functionality and configure/compile parallelization afterwards (possibly by power-users). There could be a unique selling point for open source: parallel performance because you can recompile.

Re:Dangerous idea

[ProfessionalCookie]

From a science perspective I'm pretty sure that either computer are already "sentient" or (IMHO, more likely) that we don't really understand what sentience is. At all.

The Internet

[pmontra]

The Internet is at least in the 1 billion cores range. The way to use many of them for a parallel computation has been demonstrated by Seti@home, Folding@home and even by botnets. They might not be the most efficient implementations when you have full control of the cores but they show the way to go when the availability of the cores and the communication between them is unreliable, when they have different times and different clocks and when they might be preempted to do different tasks.

Re:Reminds me of Hillis

[teazen]

Exactly! New is the new old. A million processors? Pah! Old hat. There has been done lots of interesting research into parallel processing in the past. Read the Connection Machine book It's a great read.

Feynman was also involved with the machine at a certain point. There's a great writeup on him and it for a quick introduction: '.. It was a complicated device; by comparison, the processors themselves were simple. Connecting a separate communication wire between each pair of processors was impractical since a million processors would require $10^{12]$ wires. Instead, we planned to connect the processors in a 20-dimensional hypercube so that each processor would only need to talk to 20 others directly. ..'

The C-5 looked awesome as well. And I'll just keep quiet about all the cool Lisp stuff they did on it.

The brain isn't a spiffy processing system.

[master_p]

The brain does not do arithmetic, it only does pattern matching. That's what most people don't get and that's the obstacle to understanding and realizing AI.

If you ask how can humans can then do math in their brain, the answer is simple: they can't, but a pattern matching system can be trained to do math by learning all the relevant patterns.

If you further ask how humans can do logical inference in their brain, the answer is again simple: they can't, and that's the reason people believe in illogical things. Their answers are the result of pattern matching, just like Google returning the wrong results.

Re:Reminds me of Hillis

[pieterh]

You don't even need Erland, you can use a lightweight message-passing library like ZeroMQ that lets you build fast concurrent applications in 20 or so languages. It looks like sockets but implements Actors that connect in various patterns (pubsub, request-reply, butterfly), and works with Ruby, Python, C, C++, Java, Ada, C++, CLisp, Go, Haskell, Perl, and even Erlang. You can even mix components in any language.

You get concurrent apps with no shared state, no shared clock, and components that can come and go at any time, and communicate only by sending each other messages.

In hardware terms it lets you run one thread per core, at full efficiency, with no wait states. In software terms it lets you build at any scale, even to the scale of the human brain, which is basically a message-passing concurrent architecture.

Re:Dangerous idea

[perryizgr8]

on the contrary, i can't wait for sentient machines. at last we will be free of shoddy human programming. no vendor lockins and other such stuff. just tell your computer to write a specific program you desire for a specific purpose, and he will write it for you.

Re: "steal"

[TaoPhoenix]

No no - you had the golden chance and missed it!

You *license* the baby!