http://www.economist.com/node/18750706?story_id=18750706

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Orchid XP v8 <voi### [at] devnull> wrote:
> http://www.economist.com/node/18750706?story_id=18750706

  One thing I thought of:

  A programming language/compiler cannot automatically parallelize all
possible programs given to it in the most optimal way (iow. so that it
maximizes, or at least gets very close to maximizing the efficiency of
the program in a multiprocessor architecture). Some problems are more
easily parallelized in an automatic way, while others are much harder
(they can be really hard to parallelize even for an expert programmer,
not to talk about parallelizing it automatically). This is just a fact
(and I wouldn't be surprised if such an optimization problem would be
at the very least in the NP category, if not in the "impossible" category
in the general case; in fact, if you think about it, distributing code
optimally among processors sounds a lot like the knapsack problem; only
it's probably even harder than that).

  So if we have a programming language and/or compiler that automatically
parallelizes a program, in many cases it will make a pretty lousy job
compared to am expert programmer doing it.

  One would hastily think "well, better *some* speedup by distributing
the task among processors than just running it in one core in the old
fashioned way, with no speedup at all".

  That may be so if you are running that program only. However, in many
cases in many situations that will not be the only program running in the
system. The problem is that this "lousily" parallelized program will be
hogging all the cores for itself, and in a rather inefficient way at that,
and thus other processes will get a smaller share.

  It may even be that in some situation you might even want just the
program using one core if it can't use the others efficiently, so that
you can run something else on the others, than the one program hogging
everything for itself, making other programs run more slowly than they
would have to.

  This automatic parallelization may be also give the false illusion of
efficiency, when in fact it's far from it. After all, you will see the
program using 100% of all the cores. That's pretty efficient, isn't it?
Of course this is just an illusion. CPU usage percentage doesn't necessarily
directly translate to efficiency. One program using two cores at 100% each
might be running just eg. 20% faster than when running on one single core.
(And in fact, I think there are examples of programs which actually run
*slower* on multiple cores than on one core, even though they are using
100% of CPU time on each, as contradictory as that might sound.)

-- 
                                                          - Warp

Post a reply to this message

On 16/06/2011 10:40 PM, Warp wrote:

>    One thing I thought of:
>
>    A programming language/compiler cannot automatically parallelize all
> possible programs given to it in the most optimal way.

Sure. But parallelism doesn't necessarily have to be "automatic". Doing 
it manually is OK, so long as you make it really easy to specify what 
you actually want. That works.

> Some problems are more
> easily parallelized in an automatic way, while others are much harder.

Quite. GPUs have been merrily parallising a large class of important 
algorithms for decades now. It's no secret that only certain algorithms 
fit the GPU model, but when they do, boy do they go fast!

On the other hand, how do you make your word processor go faster? Hell, 
*can* you make your word processor go faster? From what I've seen, the 
thing that usually slows these down is I/O latency (possibly due to lack 
of RAM forcing you to use virtual memory). Adding more CPU power is 
going to do nothing about that.

> This is just a fact
> (and I wouldn't be surprised if such an optimization problem would be
> at the very least in the NP category

It took me a moment to think about this one. My initial reaction was 
"isn't the NP category only defined for *sequential* algorithms?" And 
then I realised that the process of transforming a program could very 
well be a sequential algorithm, and hence amenable to classification.

OOC, how many problems can you name for which there is no known optimal 
algorithm? How many problems provably cannot be solved optimally?

>    It may even be that in some situation you might even want just the
> program using one core if it can't use the others efficiently, so that
> you can run something else on the others, than the one program hogging
> everything for itself, making other programs run more slowly than they
> would have to.

Even for programs which do run faster in parallel, due to Amdahl's law, 
there's usually a point at which adding more cores does not improve 
performance. So you probably don't ever want to say "use as many cores 
as I have", because that tends to be pessimal. You probably want to 
choose the optimal number of cores for each particular program.

>    This automatic parallelization may be also give the false illusion of
> efficiency, when in fact it's far from it. After all, you will see the
> program using 100% of all the cores. That's pretty efficient, isn't it?
> Of course this is just an illusion. CPU usage percentage doesn't necessarily
> directly translate to efficiency.

Quite.

> (And in fact, I think there are examples of programs which actually run
> *slower* on multiple cores than on one core, even though they are using
> 100% of CPU time on each, as contradictory as that might sound.)

This is not a theoretical idea. This is something which commonly happens 
in the real world.

Spawn two threads. Have one thread compute the odd-numbered elements of 
an array, and the other thread compute the even-numbered elements. This 
way, the work is split in half, right?

Except now each CPU core continuously invalidates the other core's L1 
cache lines, causing constant memory traffic and hence very high 
latency. It's probably vastly slower than just doing all the work in one 
thread.

Of course, the solution here is pretty trivial; rather than interleave 
the elements, split the array in the middle and have one thread process 
each half. If the elements really are independent, you should now see a 
50% speedup.

In case this sounds like the kind of mistake only a novice would make, 
consider GHC's new parallel garbage collector. Initially they programmed 
it to use all available cores. But they quickly discovered that due to 
locality issues, performance was rubbish. It turns out to be *faster* to 
let cores sit idle rather than generate lots of cache traffic sometimes.

(The solution they eventually implemented was that each core has its own 
heap, and garbage-collects it in parallel. At least, for the first 
generation. The second generation has a shared heap, which is still 
split into "chunks" and collected in parallel.)

Post a reply to this message

On 6/17/2011 1:12, Invisible wrote:
> On the other hand, how do you make your word processor go faster?

Is your word processor really not fast enough?

> *can* you make your word processor go faster?

Spell check in one thread, layout of pages you haven't looked at in another 
thread, etc.  I think they're already making it faster, if you actually 
watch Word or Reader open a big document, for example.

> From what I've seen, the thing
> that usually slows these down is I/O latency

I find that's almost all of the slow-down, actually. Have you seen the video 
of the SSD RAID array? Where they open all four office programs with 
documents in about half a second?  Where they open every program installed 
on the computer in about 10 seconds?

>> This is just a fact
>> (and I wouldn't be surprised if such an optimization problem would be
>> at the very least in the NP category
>
> It took me a moment to think about this one. My initial reaction was "isn't
> the NP category only defined for *sequential* algorithms?"

Sort of. A NDTM isn't exactly a sequential machine.

If it's NP, it's going to be NP on any fixed number of processors. Only if 
you let the number of processors scale with the size of the problem does it 
come into question. (Granted, that's how a lot of SIMD theory is defined.)

> OOC, how many problems can you name for which there is no known optimal
> algorithm? How many problems provably cannot be solved optimally?

Certainly all the problems that can't be solved can't be solved optimally. 
Otherwise, you can always brute force all possible answers and pick out the 
optimal one, assuming you have a way of generating answers and evaluating 
their relative merits.  I think your question is too ill-specified to be 
answered clearly, tho.

> Even for programs which do run faster in parallel, due to Amdahl's law,
> there's usually a point at which adding more cores does not improve
> performance.

Certainly having more cores than the number of instructions the program 
executes is going to be pointless, so mathematically speaking, the law 
*always* applies, even if it's silly in practice to take it to that 
exaggeration.

> Except now each CPU core continuously invalidates the other core's L1 cache
> lines, causing constant memory traffic and hence very high latency. It's
> probably vastly slower than just doing all the work in one thread.

And for people who don't have a technical background:

http://blogs.msdn.com/b/ericlippert/archive/2011/06/16/atomicity-volatility-and-immutability-are-different-part-three.aspx

> (The solution they eventually implemented was that each core has its own
> heap, and garbage-collects it in parallel. At least, for the first
> generation. The second generation has a shared heap, which is still split
> into "chunks" and collected in parallel.)

GC is definitely one of the harder problems out there. :-) One of those "in 
theory it's easy, in practice getting good performance is really hard."

-- 
Darren New, San Diego CA, USA (PST)
   "Coding without comments is like
    driving without turn signals."

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> Certainly having more cores than the number of instructions the program 
> executes is going to be pointless, so mathematically speaking, the law 
> *always* applies, even if it's silly in practice to take it to that 
> exaggeration.

  I don't think it works like that. Of course each CPU runs the *same* code,
but each on different input data (or partially different, as some of the
input data may well be shared among the threads, only some parameters being
different; POV-Ray 3.7 would be a perfect example of this).

  Perhaps you meant that having more cores than the amount of generated data
would be useless (because each processor has to output at least one bit of
data to be useful). Since generated data typically has quite many bits, it's
not like you would hit this limit any time soon.

-- 
                                                          - Warp

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> Quite. GPUs have been merrily parallising a large class of important 
> algorithms for decades now.

  I wonder what gives you that impression.

  The first GPU to support programmable shaders was the GeForce 3 Series,
released in 2001. Back then support for implementing more-or-less generic
algorithms with these shaders was very limited.

  As programmable shader languages were improved, the possibilities
increased, and there were quite many "hacks" to make programmable shaders
do something else than to paint pixels, but it probably was not until CUDA
was published that there was "official" support for generic algorithm
programming on GPUs. The first GPU supporting CUDA was the GeForce 8800
Series, released in 2006.

-- 
                                                          - Warp

Post a reply to this message

On 6/18/2011 4:49, Warp wrote:
> Darren New<dne### [at] sanrrcom>  wrote:
>> Certainly having more cores than the number of instructions the program
>> executes is going to be pointless, so mathematically speaking, the law
>> *always* applies, even if it's silly in practice to take it to that
>> exaggeration.

>    Perhaps you meant that having more cores than the amount of generated data

I was speaking entirely theoretically. Amahl's law says you only get so much 
speed-up, no matter how many CPUs you throw at it. If the sequential program 
executes 100 billion instructions over the course of solving the problem, 
giving it more than 100 billion processors cannot possibly speed it up any 
farther.

Sort of like an O(n) question ignoring the constant factor sort of discussion.

> would be useless (because each processor has to output at least one bit of
> data to be useful). Since generated data typically has quite many bits, it's
> not like you would hit this limit any time soon.

Exactly. That's why I said "mathematically speaking."

When I studied SIMD algorithms in school, the assumption was that you always 
had N processors, where N was the same number you were giving to O(N) sorts 
of calculations.

-- 
Darren New, San Diego CA, USA (PST)
   "Coding without comments is like
    driving without turn signals."

Post a reply to this message

On 18/06/2011 12:55 PM, Warp wrote:
> Invisible<voi### [at] devnull>  wrote:
>> Quite. GPUs have been merrily parallising a large class of important
>> algorithms for decades now.
>
>    I wonder what gives you that impression.
>
>    The first GPU to support programmable shaders was the GeForce 3 Series,
> released in 2001.

OK. So the early ones were entirely hard-wired. They're still using 
parallel processing to solve a real-world problem. My point was that 
some kinds of algorithms are very easy to solve with parallel processing.

Post a reply to this message

>> On the other hand, how do you make your word processor go faster?
>
> Is your word processor really not fast enough?

Sometimes. (Depending on which one I'm using.)

>> *can* you make your word processor go faster?
>
> Spell check in one thread, layout of pages you haven't looked at in
> another thread, etc. I think they're already making it faster, if you
> actually watch Word or Reader open a big document, for example.

I wonder if anybody has fixed that thing where closing the CD drive 
causes the entire Windows OS to lock up for 30 seconds yet?

>> From what I've seen, the thing
>> that usually slows these down is I/O latency
>
> I find that's almost all of the slow-down, actually.

I'm just bitter because our document management system requires you to 
open a Word document that lives on a Windows share at HQ. Of course, for 
all the people at HQ, that's just a subnet away. But for everyone 
else... SMB over a WAN is not fast. 5 Mbit/sec bandwidth and 105 ms 
latency is not fun with such a chatty protocol.

> Have you seen the
> video of the SSD RAID array? Where they open all four office programs
> with documents in about half a second? Where they open every program
> installed on the computer in about 10 seconds?

I do remember configuring my Amiga 1200 to boot from a RAM disk. Jesus, 
that was fast...

>> OOC, how many problems can you name for which there is no known optimal
>> algorithm? How many problems provably cannot be solved optimally?
>
> Certainly all the problems that can't be solved can't be solved
> optimally. Otherwise, you can always brute force all possible answers
> and pick out the optimal one, assuming you have a way of generating
> answers and evaluating their relative merits. I think your question is
> too ill-specified to be answered clearly, tho.

OK, so a problem would be provably impossible to solve if the search 
space is infinite or if there's no way to enumerate all possible solutions?

>> Even for programs which do run faster in parallel, due to Amdahl's law,
>> there's usually a point at which adding more cores does not improve
>> performance.
>
> Certainly having more cores than the number of instructions the program
> executes is going to be pointless, so mathematically speaking, the law
> *always* applies, even if it's silly in practice to take it to that
> exaggeration.

Sure. My point was that for some programs, adding more cores yields more 
speed, at least until you reach ridiculous limits. For other programs, 
adding just one or two cores means you already reach that point.

> GC is definitely one of the harder problems out there. :-) One of those
> "in theory it's easy, in practice getting good performance is really hard."

I think the fundamental thing is that GC wants to traverse pointers 
backwards, but the heap structure only allows you to traverse them forwards.

Other than that, we keep getting processors with more and more cores, 
but exactly the same amount of memory bandwidth. This seems very 
unsustainable.

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> OK. So the early ones were entirely hard-wired. They're still using 
> parallel processing to solve a real-world problem. My point was that 
> some kinds of algorithms are very easy to solve with parallel processing.

  Scanline rendering is easy to parallelize because all the pixels can be
rendered independently of each other (not unlike raytracing).

-- 
                                                          - Warp

Post a reply to this message

On 6/21/2011 1:31, Invisible wrote:
> I wonder if anybody has fixed that thing where closing the CD drive causes
> the entire Windows OS to lock up for 30 seconds yet?

Yes. They call it "NT".  Your flaw is thinking the entire OS is locked up, 
when it's really just explorer waiting to read the disk.

> WAN is not fast. 5 Mbit/sec bandwidth and 105 ms latency is not fun with
> such a chatty protocol.

Yeah. Try starting up SunOS and X Windows on a 4-meg sparcstation with no 
internal disk paging over the 10Mbps ethernet.  Ninety seconds to switch 
window focus?

> I do remember configuring my Amiga 1200 to boot from a RAM disk. Jesus, that
> was fast...

Amazing how when you get rid of the moving parts and the simulation of 
moving parts it goes really fast.

>>> OOC, how many problems can you name for which there is no known optimal
>>> algorithm? How many problems provably cannot be solved optimally?
>>
>> Certainly all the problems that can't be solved can't be solved
>> optimally. Otherwise, you can always brute force all possible answers
>> and pick out the optimal one, assuming you have a way of generating
>> answers and evaluating their relative merits. I think your question is
>> too ill-specified to be answered clearly, tho.
>
> OK, so a problem would be provably impossible to solve if the search space
> is infinite or if there's no way to enumerate all possible solutions?

It would be provably impossible to solve via brute force, sure. That's 
exactly what keeps the halting problem from being solved, in at least some 
sense.

Beyond that, you'll have to say what you mean by "solving optimally". We 
know the optimal Big-O for a number of problems. Is that what you're talking 
about?

> Sure. My point was that for some programs, adding more cores yields more
> speed, at least until you reach ridiculous limits. For other programs,
> adding just one or two cores means you already reach that point.

Right. My comment was more of an aside.

I also realized yesterday, when driving past the building I tried to model 
for my game that slowed the frame rate to a crawl when I actually drew it, 
that the reason the universe doesn't have trouble keeping up with the 
frame-rate is that it really does have N processors for a problem of size N.

How do you calculate in real time exactly what it would look like to have 
light reflecting off that building built out of all those atoms?  Give each 
atom the ability to process its contribution to the reflected light in 
parallel.  How do you do the clipping and shadow casting in real time? Have 
each atom doing the clipping and shadow casting in parallel for all the 
pixels it affects. Etc.

(Yes, maybe obvious, but it kind of twinged with this conversation.)

> I think the fundamental thing is that GC wants to traverse pointers
> backwards, but the heap structure only allows you to traverse them forwards.

I don't think GC wants to traverse backwards, except perhaps in purely 
functional languages/heaps. GC works by starting at the roots and seeing 
what's still reachable, so that's all forward pointers.

> Other than that, we keep getting processors with more and more cores, but
> exactly the same amount of memory bandwidth. This seems very unsustainable.

Yep.  That's why NUMA is getting more popular and such.

-- 
Darren New, San Diego CA, USA (PST)
   "Coding without comments is like
    driving without turn signals."

Post a reply to this message

On 21/06/2011 06:41 PM, Warp wrote:
> Invisible<voi### [at] devnull>  wrote:
>> OK. So the early ones were entirely hard-wired. They're still using
>> parallel processing to solve a real-world problem. My point was that
>> some kinds of algorithms are very easy to solve with parallel processing.
>
>    Scanline rendering is easy to parallelize because all the pixels can be
> rendered independently of each other (not unlike raytracing).

Indeed, a great many graphical tasks parallise very well. For example, 
image scaling (whether bilinear or trilinear or anisotropic or 
whatever). Or DCT / inverse DCT operations [on independent pixel blocks].

Other tasks don't parallise so well.

Post a reply to this message

On 21/06/2011 06:55 PM, Darren New wrote:
> On 6/21/2011 1:31, Invisible wrote:
>> I wonder if anybody has fixed that thing where closing the CD drive
>> causes
>> the entire Windows OS to lock up for 30 seconds yet?
>
> Yes. They call it "NT". Your flaw is thinking the entire OS is locked
> up, when it's really just explorer waiting to read the disk.

Sure. It's not the whole OS. It's just the entire GUI. Subtle difference 
there.

Same thing happens if the OS is expecting to configure a NIC via DHCP 
but there's no server. It waits quite a long time - which is fine - but 
the entire GUI again locks up while it does so (which isn't fine). No 
reason, just poor design. (I think in XP it at least doesn't sit around 
waiting if there's no cable plugged in.)

>> WAN is not fast. 5 Mbit/sec bandwidth and 105 ms latency is not fun with
>> such a chatty protocol.
>
> Yeah. Try starting up SunOS and X Windows on a 4-meg sparcstation with
> no internal disk paging over the 10Mbps ethernet. Ninety seconds to
> switch window focus?

Running X Windows on an Amiga 1200 is almost as slow as that. Which is 
daft really; the native OS is trippy-fast. More responsive than some of 
the [massively more powerful] PCs I look after at work. And here I was 
thinking Linux was fast...

>> I do remember configuring my Amiga 1200 to boot from a RAM disk.
>> Jesus, that was fast...
>
> Amazing how when you get rid of the moving parts and the simulation of
> moving parts it goes really fast.

Back in those days, people were talking about PCMCIA RAM cards and how 
they were going to replace HDs. Never happened, did it?

Then again, SSDs are here now, and gradually becoming actually popular. 
I guess history repeats itself, eh?

>> OK, so a problem would be provably impossible to solve if the search
>> space
>> is infinite or if there's no way to enumerate all possible solutions?
>
> It would be provably impossible to solve via brute force, sure. That's
> exactly what keeps the halting problem from being solved, in at least
> some sense.
>
> Beyond that, you'll have to say what you mean by "solving optimally". We
> know the optimal Big-O for a number of problems. Is that what you're
> talking about?

Warp's original comment was that partitioning an arbitrary problem such 
that you gain parallel speedup is probably impossible "in practise". 
Intuitively, I was wondering how many real-world problems are 
"impossible" to solve in the real world. (Here "solve" doesn't 
necessarily mean deriving an /optimal/ solution, just a solution that's 
"useable".)

I guess that *is* way too vague to answer.

> I also realized yesterday, when driving past the building I tried to
> model for my game that slowed the frame rate to a crawl when I actually
> drew it, that the reason the universe doesn't have trouble keeping up
> with the frame-rate is that it really does have N processors for a
> problem of size N.
>
> How do you calculate in real time exactly what it would look like to
> have light reflecting off that building built out of all those atoms?
> Give each atom the ability to process its contribution to the reflected
> light in parallel. How do you do the clipping and shadow casting in real
> time? Have each atom doing the clipping and shadow casting in parallel
> for all the pixels it affects. Etc.
>
> (Yes, maybe obvious, but it kind of twinged with this conversation.)

Heheh, yeah. Didn't somebody say a few months back "we need advanced 
quantum computers *now*!", to which somebody else replied "we already 
have that; we call it 'the real world'". ;-)

>> I think the fundamental thing is that GC wants to traverse pointers
>> backwards, but the heap structure only allows you to traverse them
>> forwards.
>
> I don't think GC wants to traverse backwards, except perhaps in purely
> functional languages/heaps. GC works by starting at the roots and seeing
> what's still reachable, so that's all forward pointers.

Ideally you want to find out whether a given object is pointed to by 
anything - which is a reverse pointer traversal. But of course, that's 
impossible, so we do forward traversal to compute the same information.

Except that's not true of course. It's possible for two dead objects to 
point to each other. (Which is why reference counting will never work.) 
The other option is to put the liveliness testing into pointer 
manipulation operations (since this is the only place where the 
information can change), but that's going to heap tonnes of overhead 
onto very common operations.

The other thing I've thought about is having multiple heap areas and 
tracking pointers between them. If you could arrange it so that all the 
garbage is in one heap chunk, you can just drop the whole chunk rather 
than doing complex processing over it. However, that's not easy to 
achieve in general.

>> Other than that, we keep getting processors with more and more cores, but
>> exactly the same amount of memory bandwidth. This seems very
>> unsustainable.
>
> Yep. That's why NUMA is getting more popular and such.

Only for supercomputers.

I wonder how long it will take for desktops to catch up?

Speaking of which, take a look at this:

http://tinyurl.com/64bfdmv

The interesting bit is slides #3 and #4. I've often wondered why all the 
books about supercomputers talk a lot about parallel processing, but 
[until recently] it's never seen in normal computers. Now I know, I guess...

Post a reply to this message

On 6/22/2011 1:35, Invisible wrote:
> Sure. It's not the whole OS. It's just the entire GUI. Subtle difference there.

Not the entire GUI. One program running the file manager.

Your email client still works. Your background processes still work. 
Programs trying to open files might get stuck.

> Same thing happens if the OS is expecting to configure a NIC via DHCP but
> there's no server. It waits quite a long time - which is fine - but the
> entire GUI again locks up while it does so (which isn't fine).

Never had that problem that I remember. On the other hand, yes, since Vista 
or so, network I/O requests can be canceled, which is what you're 
experiencing there.

> No reason, just poor design.

More like "insufficient engineering time given to edge cases to make them 
efficient."

> Then again, SSDs are here now, and gradually becoming actually popular. I
> guess history repeats itself, eh?

Yeah. Sadly, it has to actually *look* like a disk, so you still get a lot 
of the overhead.

> Warp's original comment was that partitioning an arbitrary problem such that
> you gain parallel speedup is probably impossible "in practise".

I wouldn't be surprised if it was mathematically impossible in theory, either.

> I guess that *is* way too vague to answer.

For the general case, yeah.

> Heheh, yeah. Didn't somebody say a few months back "we need advanced quantum
> computers *now*!", to which somebody else replied "we already have that; we
> call it 'the real world'". ;-)

I think that was me, yes. :-)

> Ideally you want to find out whether a given object is pointed to by
> anything

Um, no, not really. You want the collection of live objects. Or the 
collection of dead objects. You don't do GC one object at a time, unless 
you're doing reference counting.

http://en.wikipedia.org/wiki/Garbage_collection_%28computer_science%29#Tri-colour_marking

> Except that's not true of course. It's possible for two dead objects to
> point to each other. (Which is why reference counting will never work.) The
> other option is to put the liveliness testing into pointer manipulation
> operations (since this is the only place where the information can change),
> but that's going to heap tonnes of overhead onto very common operations.

Yes, that's reference counting, and that's why people avoid that in GC when 
they can.

> The other thing I've thought about is having multiple heap areas and
> tracking pointers between them. If you could arrange it so that all the
> garbage is in one heap chunk, you can just drop the whole chunk rather than
> doing complex processing over it. However, that's not easy to achieve in
> general.

That's called semi-space garbage collection.

>>> Other than that, we keep getting processors with more and more cores, but
>>> exactly the same amount of memory bandwidth. This seems very
>>> unsustainable.
>>
>> Yep. That's why NUMA is getting more popular and such.
>
> Only for supercomputers.

The Opteron is a supercomputer?

> I wonder how long it will take for desktops to catch up?

You're probably already running it.

> Speaking of which, take a look at this:
>
> http://tinyurl.com/64bfdmv

Comic Saaaaaaaaaaans!


> The interesting bit is slides #3 and #4. I've often wondered why all the
> books about supercomputers talk a lot about parallel processing, but [until
> recently] it's never seen in normal computers. Now I know, I guess...

Because until recently (like, the last 10 years), putting multiple CPUs in 
something was very expensive.

-- 
Darren New, San Diego CA, USA (PST)
   "Coding without comments is like
    driving without turn signals."

Post a reply to this message

On 6/22/2011 1:07, Invisible wrote:
> Indeed, a great many graphical tasks parallise very well.

Pretty much anything computed by atoms parallelzixes well. Sound algorithms, 
video algorithms, image algorithms, mapping algorithms, etc.

-- 
Darren New, San Diego CA, USA (PST)
   "Coding without comments is like
    driving without turn signals."

Post a reply to this message

On 6/22/2011 8:44, Darren New wrote:
> Your email client still works. Your background processes still work.
> Programs trying to open files might get stuck.

Actually, I suspect what's happening is that you put the CD in, and Windows 
immediately generates a message saying "hey, your list of valid disks may 
have changed." At which point Explorer (and maybe others) goes out over the 
list of disks, but Windows is still spinning up the CD and all that, not yet 
having determined which file system it is and mounted it, so processes that 
do that hang waiting for the disk to mount.

You *could* make a separate thread to handle this one case, but it's 
probably not worth it, esp. since you're the only person in my entire career 
I've heard complain about it.

-- 
Darren New, San Diego CA, USA (PST)
   "Coding without comments is like
    driving without turn signals."

Post a reply to this message

On 22/06/2011 05:07 PM, Darren New wrote:

> You *could* make a separate thread to handle this one case, but it's
> probably not worth it, esp. since you're the only person in my entire
> career I've heard complain about it.

The other fun one is clicking on A: by mistake. It takes an absurdly 
long time to figure out that there's no disk there. (That's possibly a 
limitation of the hardware, but some sort of status indication wouldn't 
hurt.)

Still, apparently only people like me actually *care* that the design is 
flawed. Normal people just assume "it's a computer, it's not supposed to 
work properly". So why does M$ have any incentive to fix it? It's not 
like it affects their profits...

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

On 22/06/2011 04:45 PM, Darren New wrote:
> On 6/22/2011 1:07, Invisible wrote:
>> Indeed, a great many graphical tasks parallise very well.
>
> Pretty much anything computed by atoms parallelzixes well. Sound
> algorithms, video algorithms, image algorithms, mapping algorithms, etc.

Not sure what the difference between "video algorithms" and "image 
algorithms" is, but you can add "kinetic simulations" to the list...

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

On 6/22/2011 13:31, Orchid XP v8 wrote:
> Still, apparently only people like me actually *care* that the design is
> flawed.

I'd say confusing "flaw" with "intentional design trade-off" is your problem 
there.

-- 
Darren New, San Diego CA, USA (PST)
   "Coding without comments is like
    driving without turn signals."

Post a reply to this message

On 6/22/2011 13:51, Orchid XP v8 wrote:
> Not sure what the difference between "video algorithms" and "image
> algorithms" is,

If you have an image operation that convolves the entire image in a way that 
can't be para;lelized, you can still paralellize it between different frames.

 > but you can add "kinetic simulations" to the list...

Yeah, probably true.

-- 
Darren New, San Diego CA, USA (PST)
   "Coding without comments is like
    driving without turn signals."

Post a reply to this message

On 22/06/2011 04:44 PM, Darren New wrote:
> On 6/22/2011 1:35, Invisible wrote:
>> Sure. It's not the whole OS. It's just the entire GUI. Subtle
>> difference there.
>
> Not the entire GUI. One program running the file manager.
>
> Your email client still works. Your background processes still work.
> Programs trying to open files might get stuck.

The Start menu stops working, all open Explorer windows stop working, 
the task bar stops working, the system tray stops working, windows stop 
repainting, Alt+Tab stops working, and even Ctrl+Alt+Del becomes very 
slow. And for what? Because of a piffling hardware event which I might 
not even care about? Great...

>> No reason, just poor design.
>
> More like "insufficient engineering time given to edge cases to make
> them efficient."

I'm not sure "the entire PC stops working every time you touch the CD 
drive" is what I'd call an "edge case", but whatever...

>> Then again, SSDs are here now, and gradually becoming actually popular. I
>> guess history repeats itself, eh?
>
> Yeah. Sadly, it has to actually *look* like a disk, so you still get a
> lot of the overhead.

I did see a flash device that's a PCI card. It requires special device 
drivers and stuff, but apparently it goes stupidly fast.

Then again, the advantage of a vanilla SSD is that it works with 
everything. A bit like the way 30 years after the original IBM PC was 
released, almost every desktop computer on Earth still pretends to have 
a 20-bit address space until you twiddle one of the control registers on 
the keyboard controller (!?!) to enable access to all of the installed RAM.

>> Warp's original comment was that partitioning an arbitrary problem
>> such that
>> you gain parallel speedup is probably impossible "in practise".
>
> I wouldn't be surprised if it was mathematically impossible in theory,
> either.

Well, no, the search space is presumably finite (although absurdly 
vast), so theoretically it's trivial.

>> The other thing I've thought about is having multiple heap areas and
>> tracking pointers between them. If you could arrange it so that all the
>> garbage is in one heap chunk, you can just drop the whole chunk rather
>> than
>> doing complex processing over it. However, that's not easy to achieve in
>> general.
>
> That's called semi-space garbage collection.

Wikipedia's description of "semi-space GC" seems to be "2-space GC".

>>> Yep. That's why NUMA is getting more popular and such.
>>
>> Only for supercomputers.
>
> The Opteron is a supercomputer?

How many desktop PCs contain an Opteron?

>> I wonder how long it will take for desktops to catch up?
>
> You're probably already running it.

Desktop PCs have had non-uniform memory access times for decades now. 
But currently, they all *pretend* to have uniform memory. NUMA is about 
explicitly admitting that there are different pools of memory, with 
different properties.

> Comic Saaaaaaaaaaans!

Yeah, well, I didn't write it...

>> The interesting bit is slides #3 and #4. I've often wondered why all the
>> books about supercomputers talk a lot about parallel processing, but
>> [until recently] it's never seen in normal computers. Now I know, I guess...
>
> Because until recently (like, the last 10 years), putting multiple CPUs
> in something was very expensive.

Putting multiple chip in is *still* very expensive. ;-)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

On 6/22/2011 14:09, Orchid XP v8 wrote:
> windows stop repainting,

All of them? Or just explorer windows?  Because none of that stuff happens 
with me.  Maybe you have something installed that goes compute-bound or 
something when you mount a disk.

> I'm not sure "the entire PC stops working every time you touch the CD drive"
> is what I'd call an "edge case", but whatever...

Clearly it doesn't "stop working."  Try opening the task manager and 
watching the chart scroll when you put something in the CD drive.

> Then again, the advantage of a vanilla SSD is that it works with everything.

Exactly, yes.

>>> Warp's original comment was that partitioning an arbitrary problem
>>> such that
>>> you gain parallel speedup is probably impossible "in practise".
>>
>> I wouldn't be surprised if it was mathematically impossible in theory,
>> either.
>
> Well, no, the search space is presumably finite (although absurdly vast), so
> theoretically it's trivial.

Hmmm. Maybe, yeah, if you tried every possible rearrangement of opcodes sort 
of thing. But that assumes you can tell that the rearranged opcodes will 
have the same effect, which again is impossible.

I.e., the number of ways you can chop up the problem is finite, but the 
number of *wrong* ways to chop up the problem is non-zero.

>>> The other thing I've thought about is having multiple heap areas and
>>> tracking pointers between them. If you could arrange it so that all the
>>> garbage is in one heap chunk, you can just drop the whole chunk rather
>>> than
>>> doing complex processing over it. However, that's not easy to achieve in
>>> general.
>>
>> That's called semi-space garbage collection.
>
> Wikipedia's description of "semi-space GC" seems to be "2-space GC".

Well, you're either talking about generational heaps, semi-space heaps, or 
separate heaps that might have roots in other heaps, in which case it's the 
same as a generational heap technologically-speaking.

>
>>>> Yep. That's why NUMA is getting more popular and such.
>>>
>>> Only for supercomputers.
>>
>> The Opteron is a supercomputer?
>
> How many desktop PCs contain an Opteron?

http://sites.amd.com/us/business/products/desktop/Pages/hp.aspx

Come on now. That wasn't even difficult.

> Desktop PCs have had non-uniform memory access times for decades now. But
> currently, they all *pretend* to have uniform memory.

Well, except to the OS.  Applications pretend they all have contiguous 
memory addresses, too.

-- 
Darren New, San Diego CA, USA (PST)
   "Coding without comments is like
    driving without turn signals."

Post a reply to this message