The Artima Developer Community
Articles | News | Weblogs | Books | Forums
Artima Forums | Articles | Weblogs | Java Answers | News
Sponsored Link •

Artima Developer Spotlight Forum
Unwelcome Advice: Programming to Thousands of Cores

26 replies on 2 pages. Most recent reply: Aug 2, 2008 10:11 AM by Tim Nash

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 26 replies on 2 pages [ « | 1 2 ]
Mark Thornton

Posts: 275
Nickname: mthornton
Registered: Oct, 2005

Re: Unwelcome Advice: Programming to Thousands of Cores Posted: Jul 7, 2008 6:39 AM
Reply to this message Reply
Advertisement
> Additionally, there are quite a few algorithms that are
> highly resistant to parallelization. I cannot really
> imagine a parallel implementation for the Fibonacci
> sequence for instance.

I seem to remember that the n'th Fibonacci number can be computed using the n'th power of a simple two by two matrix. Some parallel computation should be possible.

Maarten Hazewinkel

Posts: 32
Nickname: terkans
Registered: Jan, 2005

Re: Unwelcome Advice: Programming to Thousands of Cores Posted: Jul 7, 2008 7:40 AM
Reply to this message Reply
> > Additionally, there are quite a few algorithms that are
> > highly resistant to parallelization. I cannot really
> > imagine a parallel implementation for the Fibonacci
> > sequence for instance.
>
> I seem to remember that the n'th Fibonacci number can be
> computed using the n'th power of a simple two by two
> matrix. Some parallel computation should be possible.

(Checking wikipedia)
You're right, there is a direct calculation of any Fibonacci number. However, this is more a case of makeing parallelism unncecessary rarther than an oportunity to apply it.

(Back on topic)
Applying that formula would allow increased parallelism in an application by eliminating the need to maintain a central cache of calculated Fibonacci numbers to avoid long calculations. Such a cache would represent a shared resource and could result in one thread blocking others.

Max Lybbert

Posts: 314
Nickname: mlybbert
Registered: Apr, 2005

Re: Unwelcome Advice: Programming to Thousands of Cores Posted: Jul 7, 2008 11:41 AM
Reply to this message Reply
> > If I had a single system with
> > multiple cores, I'd want to run distributed grep on the
> > linux filesystem.
>
> I realize it's just an example, but its just a really bad
> one.
> The result would just be to have 4-8 threads waiting for
> the disk to serve up the file, instead of just one.

Additionally, each thread would be seeking to a different part of the file system, making your cache basically useless.

Then again, that assumes one hard drive. Once you have multiple drives (or a striped RAID), it would make sense to run one thread per physical drive. Then they aren't sharing information coming from the disk, but are potentially sharing access to the computer monitor or internal data structures (say, the list that records found matches).

I've had multiple hard drives on my desktop computer for years. Linux is smart enough to run fsck simultaneously on each physical drive to take advantage of this.

Mark Thornton

Posts: 275
Nickname: mthornton
Registered: Oct, 2005

Re: Unwelcome Advice: Programming to Thousands of Cores Posted: Jul 7, 2008 11:47 AM
Reply to this message Reply
> (Checking wikipedia)
> You're right, there is a direct calculation of any
> Fibonacci number. However, this is more a case of makeing
> parallelism unncecessary rarther than an oportunity to
> apply it.

For calculating very large (e.g. thousand digit) Fibonacci numbers there is still some opportunity for parallelism even with a direct calculation.

Michael Feathers

Posts: 448
Nickname: mfeathers
Registered: Jul, 2003

Re: Unwelcome Advice: Programming to Thousands of Cores Posted: Jul 7, 2008 3:32 PM
Reply to this message Reply
One thing that is unmentioned but important is that with an insane number of cores there really is very little cost to doing computation on speculation: if you think you might need the result of some call later, just send it off to a core to compute. If you need it, it's there, if not so what? Not sure what they arguments should be? Map the state space of the arguments to a set of cores.

Working that way be a real shift.

Tim Nash

Posts: 6
Nickname: tim08
Registered: May, 2008

Re: Unwelcome Advice: Programming to Thousands of Cores Posted: Jul 7, 2008 4:32 PM
Reply to this message Reply
The grep example is not as bad as you might think.
Take an unlikely but most obvious example. Let's say you had a google sized "copy of the internet on your filesystem". You could run many of the same applications that google already runs. Some of them are very grep-ish.
So then you may think..."Well see map-reduce is only for large datasets"
But we could begin to adopt a map-reduce library, and get developers to use it. It will rarely cause a performance problem and it will frequently bring performance benefits. What is more, the developers will start thinking of new ways to use it.

(from the out-on-a-limb department)
Map-reduce will one day be as important outside of google as it is inside google today. The cache problem mentioned seems solvable.

But it is a long wait for these kinds of changes. I'm just going to move to erlang which makes map-reduce and distributed computing easier. (see the couchDB for example)

Cameron Zemek

Posts: 17
Nickname: grom358
Registered: Dec, 2006

Re: Unwelcome Advice: Programming to Thousands of Cores Posted: Jul 8, 2008 1:49 AM
Reply to this message Reply
I think talk of hundreds of cores is a bit hyped. A lot of algorithms are I/O bound. I/O is still the slowest part of a computer.

Yesterday I found an interview with Alan Kay where he had this to say (extract from http://www.acmqueue.com/modules.php?name=Content&pa=showpage&pid=273&page=3)
> Neither Intel nor Motorola nor any other chip company understands the first thing about why that architecture was a good idea.

> Just as an aside, to give you an interesting benchmark—on roughly the same system, roughly optimized the same way, 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.

So a modern day PC is only running 50 times faster for this particular benchmark then a 29 year old machine.

Max Lybbert

Posts: 314
Nickname: mlybbert
Registered: Apr, 2005

Re: Unwelcome Advice: Programming to Thousands of Cores Posted: Jul 8, 2008 9:53 AM
Reply to this message Reply
> I think talk of hundreds of cores is a bit hyped.

I was looking over my copy of Design & Evolution of C++ where Stroustrup mentions that at the time (early '90s) he kept getting proposals to make C++ more multi-core friendly, and that as far as he could tell people had been expecting multi-cores to take off "any minute now" for twenty years.

We obviously have finally reached a case where multiple cores are actually available on the desktop. And only about 35 years since it was the accepted wisdom. But, yeah, I don't think we'll see hundreds of cores on the desktop in the near future. We probably won't see hundreds of cores in most servers for ten years or more. In fact, most of the servers I've worked with are I/O bound.

robert young

Posts: 361
Nickname: funbunny
Registered: Sep, 2003

Re: Unwelcome Advice: Programming to Thousands of Cores Posted: Jul 8, 2008 10:38 AM
Reply to this message Reply
> > I think talk of hundreds of cores is a bit hyped.
> We probably won't see
> hundreds of cores in most servers for ten years or more.
> In fact, most of the servers I've worked with are I/O
> O bound.

Don't look now, but the Thinking Machines approach (op cit) is closer than it appears in the mirror. See, for example, Texas Memory Systems. See also DB2 and Oracle, both putting more/much effort into memory based databases (through acquisition, of course). Relational databases are inherently parallel algorithmically (think: set theory), and take to such machines as ducks to water. The only difference is that now such machines will be available to smaller organizations.

The multi-core/processor solid state machine will be a disruptive event in the business/database side; less so in desktop.

Max Lybbert

Posts: 314
Nickname: mlybbert
Registered: Apr, 2005

Re: Unwelcome Advice: Programming to Thousands of Cores Posted: Jul 9, 2008 9:01 AM
Reply to this message Reply
> See also DB2 and Oracle, both putting more/much effort into memory based databases

That's a possible solution to the "disk access is inherently not parallel" problem. And it's something I hadn't heard of. Thanks.

Ivo Wever

Posts: 3
Nickname: confusion
Registered: Apr, 2008

Re: Unwelcome Advice: Programming to Thousands of Cores Posted: Jul 21, 2008 11:41 AM
Reply to this message Reply
But we could begin to adopt a map-reduce library, and get developers to use it. It will rarely cause a performance problem and it will frequently bring performance benefits.

The bottleneck of almost all of the code I have written so far is I/O: database and remote method calls. Let'I doubt that even 10% of all the time is spent waiting for the CPU to complete some task. For simplicity, we assume that all of that is parallelizable and that we have an infinite number of available processors. Amdahl's law then tells you that you can only speed up your code by that 10% and it costs you the trouble of parallelizing quite a bit of code.

To answer the original question:
To what extent do you consider your application's scalability on many CPU cores?
Hardly. As Maarten Hazewinkel already pointed out, most of the code that can benefit from multiple cores is already written in such a way that it can use multiple cores. Mainly, this is done by handling seperate requests from seperate users in seperate threads.

Tim Nash

Posts: 6
Nickname: tim08
Registered: May, 2008

Re: Unwelcome Advice: Programming to Thousands of Cores Posted: Aug 2, 2008 10:11 AM
Reply to this message Reply
Much of the existing code you (and many others) currently write may be I/O bound but there are many places where the I/O problem is being managed.

map-reduce on a workstation with many many cores may require associated changes to the operating systems, such as new file systems. If Intel is going to spend the many millions it will take to invest in this strategy they have probably already begun to address the I/O problem.

It will be a lot harder to change the minds of seasoned programmers. Google is loaded with smarties but they didn't anticipate how much code could be written on top of map-reduce. Computing needs to scale efficiently to earn it's carbon footprint. The I/O problem is just another opportunity.

Flat View: This topic has 26 replies on 2 pages [ « | 1  2 ]
Topic: JetBrains Releases First Beta of IDEA 8 Previous Topic   Next Topic Topic: Origin of BDFL
Sponsored Links


Google
  Web Artima.com   

Copyright © 1996-2019 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use