As best as I can tell, desktop computing seems to have reached an 
impasse where the only way to increase processor performance is to add 
more cores and hope that multi-threaded applications start being 
developed "real soon now".

As far as computer programming is concerned, writing programs which 
aren't single-threaded is a "hard problem". Oh, it depends on the task 
of course. But many programs are just really awkward to write in a way 
that utilises multiple cores.

Part of that is the design of the system, of course. The design worked 
OK when there was only one processor, but having several starts to 
stress the design assumptions. Multiple cores fight over available 
memory bandwidth, unified cache, and cache coherence.

However, I'm beginning to wonder whether the whole concept of "computer" 
fundamentally revolves around sequential execution. I mean, think about 
it: Why do computers exist in the first place? Computers exist because 
humans suck at arithmetic. But why do humans suck at arithmetic?

Make no mistake, a human can do a facial recognition task in split 
seconds that would take many hours for a computer. Humans can resolve 
blurry stereoscopic images into 3D mental maps with an accuracy and 
precision that still makes computer vision experts sick with envy. Watch 
a game of snooker and you'll see humans computing things which are far 
from trivial for a computer to simulate.

In other words, the human brain has significant computational power. And 
it is of course perfectly capable of performing just about any 
arithmetic operation that a computer can perform. It's just not very 
good at it, in general.

So here we have a device, the human brain [or rather, a quite small 
subset of it], which is very good at certain mathematical operations, 
yet fairly bad at certain other mathematical operations. The interesting 
question is: why?

Hypothesis: The human brain is good at parallel operations, and less 
good at significantly serial operations.

Corollary: Computers are designed to perform significantly serial 
operations.

QED.

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> As far as computer programming is concerned, writing programs which 
> aren't single-threaded is a "hard problem". Oh, it depends on the task 
> of course. But many programs are just really awkward to write in a way 
> that utilises multiple cores.

  The problems with concurrent and parallel programming are quite fundamental
(and not all that dependent eg. on the programming language used). There are
many severe problems, mutual exclusion, deadlocks and livelocks being
just a few examples of them (and even with them, they often become a problem
in programs which are supposedly thread-aware and use all kinds of locking
and mutual exclusion mechanisms). Curiously the majority of these problems
appear even in single-core systems which run multiple threads (even though
no two threads are ever physically run at the same time in parallel). The
problems are only aggravated in situations where separate processes need to
communicate with each other through an unreliable channel (which is the
case in distributed and client/server type systems). The problems that may
arise are sometimes quite surprising and not at all evident from the program
itself, even if it's competently implemented. These problems have been known
for a really long time and there are tons and tons of entire books dedicated
to them. Also lots of theory and software has been developed in order to
try to model such parallel systems and try to find flaws in them, and to
verify that a proposed implementation works.

  I don't think that switching from current serial design CPUs to something
that is more parallel is going to solve any of those problems (if anything,
they could only aggravate them). AFAIK the problems are more fundamental
than the precise CPU design used.

-- 
                                                          - Warp

Post a reply to this message

On 18/01/2011 04:20 PM, Warp wrote:
> Invisible<voi### [at] devnull>  wrote:
>> As far as computer programming is concerned, writing programs which
>> aren't single-threaded is a "hard problem". Oh, it depends on the task
>> of course. But many programs are just really awkward to write in a way
>> that utilises multiple cores.
>
>    The problems with concurrent and parallel programming are quite fundamental
> (and not all that dependent eg. on the programming language used).

The more you look at it, the more problems you find.

> There are
> many severe problems, mutual exclusion, deadlocks and livelocks being
> just a few examples of them.

These are problems of "making the program work correctly". There are 
also grave problems of "making the program actually go faster when you 
add more computer power".

> Curiously the majority of these problems
> appear even in single-core systems which run multiple threads.

> The problems that may
> arise are sometimes quite surprising and not at all evident from the program
> itself, even if it's competently implemented. These problems have been known
> for a really long time and there are tons and tons of entire books dedicated
> to them. Also lots of theory and software has been developed in order to
> try to model such parallel systems and try to find flaws in them, and to
> verify that a proposed implementation works.

In other words, "correctness is really, really hard".

>    I don't think that switching from current serial design CPUs to something
> that is more parallel is going to solve any of those problems (if anything,
> they could only aggravate them). AFAIK the problems are more fundamental
> than the precise CPU design used.

Well, certainly writing a program is something that tends to be very 
linear. But with multiple processors, the system's actions are no longer 
linear at all. Indeed, maybe the very metaphor of a linear program is no 
longer appropriate.

There are other problems. All the processors communicate through a 
single memory link, which is a bottleneck. If your program is limited by 
RAM bandwidth, adding more cores is hardly going to help. The caches 
that were added to hide RAM latency tend to trip each other up when 
threads want to communicate.

The usual solution is something like NUMA, where the different access 
speeds of different regions of memory are explicit rather than hidden. 
Distributed computing is in a way a more severe version of NUMA, but 
with lots more protocol overhead, and usually no guarantees of message 
delivery. It all spirals into complexity.

The more I think about it, the more I think we need to look at the 
problem in some sort of totally different way.

Post a reply to this message

Warp wrote:
> appear even in single-core systems which run multiple threads (even though
> no two threads are ever physically run at the same time in parallel).

Just FYI, the general terms you're looking for are "concurrent" but not 
"simultaneous". :-)

> AFAIK the problems are more fundamental
> than the precise CPU design used.

Yep. There's no good way of making larger parts of systems automatically 
concurrent. The body of a loop that is small enough for the compiler to 
analyze? Sure. Two separately compiled procedures, or something running on 
two physically separate machines (where one might fail while the other keeps 
running)?  Not so much.  Not *impossible*, but far from trivial.

I've never seen it done well unless the whole system was broken down into 
parallel operations and then optimized back into larger components. E.g., in 
NIL and Hermes, there were no subroutine calls, just sending a message to an 
independent process (that only existed for however long it took to process) 
and then waiting for the result - easy to parallelize, pretty easy to 
recognise and turn into a subroutine if appropriate. In Erlang, you 
explicitly deal with failures and concurrency, manually making the trade-off 
of where to run a process, how many to run, and the difference between a 
process and a subroutine.

-- 
Darren New, San Diego CA, USA (PST)
   Serving Suggestion:
     "Don't serve this any more. It's awful."

Post a reply to this message

Darren New escreveu:
> I've never seen it done well unless the whole system was broken down 
> into parallel operations and then optimized back into larger components. 

I read in the early days the programmer would manually break a program 
into small chunks that could fit in the memory.  Eventually the process 
became automated.

-- 
a game sig: http://tinyurl.com/d3rxz9

Post a reply to this message

nemesis wrote:
> Darren New escreveu:
>> I've never seen it done well unless the whole system was broken down 
>> into parallel operations and then optimized back into larger components. 
> 
> I read in the early days the programmer would manually break a program 
> into small chunks that could fit in the memory.  Eventually the process 
> became automated.

Yep. That's what "overlays" were. Now we have demand-paging.  (And it wasn't 
that "early". Any machine without virtual memory (and some with it) did 
that, including Amigas, IBM machines before the 386, 68000s, etc.)

-- 
Darren New, San Diego CA, USA (PST)
   Serving Suggestion:
     "Don't serve this any more. It's awful."

Post a reply to this message

Darren New escreveu:
> nemesis wrote:
>> Darren New escreveu:
>>> I've never seen it done well unless the whole system was broken down 
>>> into parallel operations and then optimized back into larger components. 
>>
>> I read in the early days the programmer would manually break a program 
>> into small chunks that could fit in the memory.  Eventually the 
>> process became automated.
> 
> Yep. That's what "overlays" were. Now we have demand-paging.  (And it 
> wasn't that "early". Any machine without virtual memory (and some with 
> it) did that, including Amigas, IBM machines before the 386, 68000s, etc.)

really?!  What was it?  An settable option for the compiler?

-- 
a game sig: http://tinyurl.com/d3rxz9

Post a reply to this message

nemesis wrote:
> really?!  What was it?  An settable option for the compiler?

Not really.  You created basically a tree of code, where the only 
permissible movements into a branch were from the node directly above. 
(E.g., you couldn't have A as the parent of B and C, and have B call C, or C 
return to B after it had been overwritten.)

Then the linker would link multiple routines to live in the same address 
space, such that B and C might share addresses. Then it would patch the 
calls from A to B or A to C to first make sure that the appropriate branch 
of the tree was in memory (loading it if not) before branching to the actual 
routine.

So, by the time of MS-DOS, it was not dissimilar to building a makefile that 
you gave to the linker, and it would do the patching up. You just had to 
have enough knowledge of your system that you knew what pieces could be 
overlaid. (Which was *way* easier with procedural code rather than OO or 
something.)

-- 
Darren New, San Diego CA, USA (PST)
   Serving Suggestion:
     "Don't serve this any more. It's awful."

Post a reply to this message

nemesis wrote:
> really?!  What was it?  An settable option for the compiler?

So say you had a piece of code that would take input, do some calculations, 
then print the report.

"main" would be in the root, along with things like printf(), malloc(), etc. 
And anything else that was used in more than just input, calcs, or print.

Main would call your top input routine, which would cause that chunk of code 
to be read in and branched to. It would take the inputs it needs and save 
them out to a file (or memory or whatever).  Input routines would return 
with a flag that says "Yes, go run the calcs", so Main would invoke the calcs.

You'd overlay input on top of calcs, so while you're doing the math, your 
input validation routines and code to draw menus and widgets and such 
doesn't need to be around.

Your calcs would write out their results (say, in a CSV file) and return to 
main, which would invoke the print routines, including those that knew how 
to put in commas and dollar signs, paginate reports, print the appropriate 
footnotes on the proper pages, etc. All your printer drivers could be gone 
while you're doing input. All your input validation could be gone while 
you're doing printing.

-- 
Darren New, San Diego CA, USA (PST)
   Serving Suggestion:
     "Don't serve this any more. It's awful."

Post a reply to this message

Darren New escreveu:
> nemesis wrote:
>> really?!  What was it?  An settable option for the compiler?
> 
> So say you had a piece of code that would take input, do some 
> calculations, then print the report.
> 
> "main" would be in the root, along with things like printf(), malloc(), 
> etc. And anything else that was used in more than just input, calcs, or 
> print.
> 
> Main would call your top input routine, which would cause that chunk of 
> code to be read in and branched to. It would take the inputs it needs 
> and save them out to a file (or memory or whatever).  Input routines 
> would return with a flag that says "Yes, go run the calcs", so Main 
> would invoke the calcs.
> 
> You'd overlay input on top of calcs, so while you're doing the math, 
> your input validation routines and code to draw menus and widgets and 
> such doesn't need to be around.
> 
> Your calcs would write out their results (say, in a CSV file) and return 
> to main, which would invoke the print routines, including those that 
> knew how to put in commas and dollar signs, paginate reports, print the 
> appropriate footnotes on the proper pages, etc. All your printer drivers 
> could be gone while you're doing input. All your input validation could 
> be gone while you're doing printing.

you are into this for a long time, huh, dude? :)

if you didn't give up in the hard hairy days, it's certainly not today...

-- 
a game sig: http://tinyurl.com/d3rxz9

Post a reply to this message