![](/i/fill.gif) |
![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Invisible <voi### [at] dev null> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
On 18/01/2011 04:20 PM, Warp wrote:
> Invisible<voi### [at] dev null> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |