[9fans] current state of thread programming

[9fans] current state of thread programming

[andrey mirtchovski]

found this snippet today and decided to share it with the list. every
once in a while a look at how "the rest of the world" does things is
beneficial :)

"I don't know about you, but every time I have to program with threads
and shared resources, I want to remove my face incrementally with a
salad fork. Locks, mutexes, the synchronized keyword; all of these
things can strike fear into the heart of a green developer. Most
seasoned developers just fall into a rut of depression when it's time
for multi-threading. Developers like me simply talk our way out of it.
It's easier than thinking."


full article: http://www.theregister.co.uk/2008/07/28/sun_dziuba_tm/

Re: [9fans] current state of thread programming

[tlaronde]

On Mon, Jul 28, 2008 at 11:11:19AM -0600, andrey mirtchovski wrote:
> found this snippet today and decided to share it with the list. every
> once in a while a look at how "the rest of the world" does things is
> beneficial :)
>
> "I don't know about you, but every time I have to program with threads
> and shared resources, I want to remove my face incrementally with a
> salad fork. Locks, mutexes, the synchronized keyword; all of these
> things can strike fear into the heart of a green developer. Most
> seasoned developers just fall into a rut of depression when it's time
> for multi-threading. Developers like me simply talk our way out of it.
> It's easier than thinking."

On the same subject, this quote from Donald E. Knuth, Volume 4
fascicle 0 (new addition to The Art of Computer Programming, published
in may 2008)---Preface:

	"Furthermore, as in earlier volumes of this serie, I'm
	intentionnally concentrating almost entirely on _sequential_
	algorithms, even though computers are increasingly able to carry out
	activities in parallel. I'm unable to judge what ideas about
	parallelism are likely to be useful five or ten years from now, let
	alone fifty, so I happily leave such questions to others who are
	wiser than I. Sequential methods, by themselves, already test the
	limits of my own ability to discern what the artful programmers of
	tomorrow will want to know."

And as an illustration of the "fun", the ongoing discussion on NetBSD
kernel mailing list _between_ 1:1 and SA threading models (when the person
working on SA revival proposes "vel" : 1:1 or/and SA ---pickup the one
you want or need for backward compatibility), discussion with
an amount of technical arguments of 5% or less.
--
Thierry Laronde (Alceste) <tlaronde +AT+ polynum +dot+ com>
                 http://www.kergis.com/
Key fingerprint = 0FF7 E906 FBAF FE95 FD89  250D 52B1 AE95 6006 F40C

Re: [9fans] current state of thread programming

[Pietro Gagliardi]

On Jul 28, 2008, at 1:11 PM, andrey mirtchovski wrote:
> salad fork. Locks, mutexes, the synchronized keyword; all of these
> things can strike fear into the heart of a green developer. Most

That's what you get for using Java.

On Jul 28, 2008, at 1:50 PM, tlaronde@polynum.com wrote:
> I'm unable to judge what ideas about
> 	parallelism are likely to be useful five or ten years from now, let
> 	alone fifty,

By that time, $50 (not $500 or $5,000, but $50) computers will be
around that will have processors with as many cores as Blue Gene, thus
almost completely eliminating the problems of multithreaded
programming. Data synchronization will be solved by simply turning off
one of the processors until the critical code has completed.

If only I could tell him that without having to wait for the snail!

Re: [9fans] current state of thread programming

[Russ Cox]

Don Knuth:
> I'm unable to judge what ideas about parallelism are likely to
> be useful five or ten years from now, let alone fifty, so I happily
> leave such questions to others who are wiser than I.

Pietro:
> By that time, ...
> If only I could tell him that without having to wait for the snail!

I can't think of anything nice to say.

Russ

Re: [9fans] current state of thread programming

[Skip Tavakkolian]

> Don Knuth:
>> I'm unable to judge what ideas about parallelism are likely to
>> be useful five or ten years from now, let alone fifty, so I happily
>> leave such questions to others who are wiser than I.
>
> Pietro:
>> By that time, ...
>> If only I could tell him that without having to wait for the snail!
>
> I can't think of anything nice to say.
>
> Russ

Pietro has a great future in talk radio.

Re: [9fans] current state of thread programming

[Roman V. Shaposhnik]

tlaronde@polynum.com wrote:
> On the same subject, this quote from Donald E. Knuth, Volume 4
> fascicle 0 (new addition to The Art of Computer Programming, published
> in may 2008)---Preface:
>
> 	"Furthermore, as in earlier volumes of this serie, I'm
> 	intentionnally concentrating almost entirely on _sequential_
> 	algorithms, even though computers are increasingly able to carry out
> 	activities in parallel. I'm unable to judge what ideas about
> 	parallelism are likely to be useful five or ten years from now, let
> 	alone fifty, so I happily leave such questions to others who are
> 	wiser than I. Sequential methods, by themselves, already test the
> 	limits of my own ability to discern what the artful programmers of
> 	tomorrow will want to know."
>
I believe this is the biggest point in all of the hype around
concurrency as the
next  programming paradigm: it is very hard to approach the algorithmic
side of it. And no, I'm not talking locking-hygiene, I'm talking design and
implementation  of  basic  (and no so basic ) algorithms.

Thanks,
Roman.

Re: [9fans] current state of thread programming

[Bakul Shah]

On Tue, 29 Jul 2008 11:40:39 PDT "Roman V. Shaposhnik" <rvs@sun.com>  wrote:
> tlaronde@polynum.com wrote:
> > On the same subject, this quote from Donald E. Knuth, Volume 4
> > fascicle 0 (new addition to The Art of Computer Programming, published
> > in may 2008)---Preface:
> >
> > 	"Furthermore, as in earlier volumes of this serie, I'm
> > 	intentionnally concentrating almost entirely on _sequential_
> > 	algorithms, even though computers are increasingly able to carry out
> > 	activities in parallel. I'm unable to judge what ideas about
> > 	parallelism are likely to be useful five or ten years from now, let
> > 	alone fifty, so I happily leave such questions to others who are
> > 	wiser than I. Sequential methods, by themselves, already test the
> > 	limits of my own ability to discern what the artful programmers of
> > 	tomorrow will want to know."
> >
> I believe this is the biggest point in all of the hype around
> concurrency as the
> next  programming paradigm: it is very hard to approach the algorithmic
> side of it. And no, I'm not talking locking-hygiene, I'm talking design and
> implementation  of  basic  (and no so basic ) algorithms.

Recently I stumbled upon something that seems appropriate here:
http://www.cs.utexas.edu/users/EWD/transcriptions/EWD05xx/EWD506.html

    Bill Wulf raised the question: "If there were a Nobel prize for
    computing science, what would be the next achievement in our field
    worthy of it?"        ...

    The next achievement Bill Wulf was asking for might very well take
    the form of successfully challenging one of our common "tacit
    assumptions". Von Neumann's "instruction counter" and the notion of
    "a sequential process" seems the most likely victim: any workable
    conceptual framework in which "parallel programming" becomes as
    meaningless a term as "sequential programming" could be a worthy
    candidate for computing science's Nobel prize!

It is slightly depressing to think that the situation has not really
changed since EWD wrote this in 1975.  It will take some young
whippersnapper of a Dijkstra or Hoare or Strachey or Iverson or Backus
to find the critical insight that will make reasoning about parallel
algorithm no more difficult than sequential ones.

Re: [9fans] current state of thread programming

[tlaronde]

On Tue, Jul 29, 2008 at 12:12:05PM -0700, Bakul Shah wrote:
>
> It is slightly depressing to think that the situation has not really
> changed since EWD wrote this in 1975.  It will take some young
> whippersnapper of a Dijkstra or Hoare or Strachey or Iverson or Backus
> to find the critical insight that will make reasoning about parallel
> algorithm no more difficult than sequential ones.

Is the human thought process parallel? For _my capacities_, I have the
impression that I'm more multitask than parallel. And context switch is
expensive because there is not only explicit data, but also implicit and
I'm not able, if I'm really doing something involved, to restore the
previous state without much ado.

CSP is (for me) the best answer to problem involving blocking/waiting on
input. But this is not parallelism.

And for processing, finally threads are also called in some
implementations: LWP, that is simply something that could have been
solved with Processes, if it was not so costly.
I have the impression that LWP is just a solution to poor process
creation and to poor IPC tools (threads are the solution not for
parallelism by itself, but because there is need to share resources
between processes and that it is simplest to put them in the same
address space).

The most efficient is to have tools that match the way our brains work
(or not...). I'm not convinced our brains are "parallel" (at least mines
are not).
--
Thierry Laronde (Alceste) <tlaronde +AT+ polynum +dot+ com>
                 http://www.kergis.com/
Key fingerprint = 0FF7 E906 FBAF FE95 FD89  250D 52B1 AE95 6006 F40C

Re: [9fans] current state of thread programming

[Roman V. Shaposhnik]

On Wed, 2008-07-30 at 13:35 +0200, tlaronde@polynum.com wrote:
> On Tue, Jul 29, 2008 at 12:12:05PM -0700, Bakul Shah wrote:
> >
> > It is slightly depressing to think that the situation has not really
> > changed since EWD wrote this in 1975.  It will take some young
> > whippersnapper of a Dijkstra or Hoare or Strachey or Iverson or Backus
> > to find the critical insight that will make reasoning about parallel
> > algorithm no more difficult than sequential ones.
>
> Is the human thought process parallel?

No. But to give you an example of why that shouldn't matter I would
like to note that the human thought is, in my opinion, finite. Yet,
we have developed very nice and efficient tools for comprehending and
reasoning about infinity.

> The most efficient is to have tools that match the way our brains work
> (or not...). I'm not convinced our brains are "parallel" (at least mines
> are not).

I disagree on philosophical grounds ;-) It's been one of the major
engineering follies to always approach design from a "just follow
the nature" standpoint. No wonder that before the Wright brothers
everybody thought the best way to fly is to flap some kind of wings.

Thanks,
Roman.

P.S. I guess, we are getting way off topic here.

Re: [9fans] current state of thread programming

[Robert Raschke]

I think useful parallel programming paradigms can very probably be
abstracted from really big systems like a national health system or an
army. How parallelism is employed in those systems, would be a good
starting point for a deeper investigation.

Especially a military system must have some very concrete, well tried
and tested, ways of organising things in parallel. Government is
another one, but I'm not sure if that's a good model ;-)

Robby

Re: [9fans] current state of thread programming

[Paweł Lasek]

On Wed, Jul 30, 2008 at 13:50, Roman V. Shaposhnik <rvs@sun.com> wrote:
> On Wed, 2008-07-30 at 13:35 +0200, tlaronde@polynum.com wrote:
>> The most efficient is to have tools that match the way our brains work
>> (or not...). I'm not convinced our brains are "parallel" (at least mines
>> are not).
>
> I disagree on philosophical grounds ;-) It's been one of the major
> engineering follies to always approach design from a "just follow
> the nature" standpoint. No wonder that before the Wright brothers
> everybody thought the best way to fly is to flap some kind of wings.

I'd disagree with this example, as it is certainly not a viable one.
First, the main thing that Wright brothers have created were control
surfaces and a lighweight plane - people had been flying for few years
before them, but nobody could get a light enough engine :)

And flapping wings wasn't an error - the error was how it was
implemented. And if you take a good look at bigger birds, you'll see
that in their case, flapping is a reuse of equipment - the principles
of flight are the same.

Oh, and BTW, there's a lot of development for ornitopters. Da Vinci
simply didn't have the tools (of which one of the most important is
computer. With _lots_ of computing power...)

> P.S. I guess, we are getting way off topic here.
>
Sorry for continuing with OT.


-- 
Paweł Lasek

Re: [9fans] current state of thread programming

[David Leimbach]

[-- Attachment #1: Type: text/plain, Size: 3141 bytes --]

On Wed, Jul 30, 2008 at 4:35 AM, <tlaronde@polynum.com> wrote:

> On Tue, Jul 29, 2008 at 12:12:05PM -0700, Bakul Shah wrote:
> >
> > It is slightly depressing to think that the situation has not really
> > changed since EWD wrote this in 1975.  It will take some young
> > whippersnapper of a Dijkstra or Hoare or Strachey or Iverson or Backus
> > to find the critical insight that will make reasoning about parallel
> > algorithm no more difficult than sequential ones.
>
> Is the human thought process parallel? For _my capacities_, I have the
> impression that I'm more multitask than parallel. And context switch is
> expensive because there is not only explicit data, but also implicit and
> I'm not able, if I'm really doing something involved, to restore the
> previous state without much ado.
>
> CSP is (for me) the best answer to problem involving blocking/waiting on
> input. But this is not parallelism.


It's not pure parallelism, no, but CSP arranged tasks may execute in
parallel :-)

Imagine if you had a CSP-style process that grabs data in chunks from a
network, and then passes a message to another helper which does some
filtering.  The filtering process could be scheduled on another core/CPU,
while the other task it getting I/O from the network and massaging it in
other ways.

It's not exactly CSP, but I wrote a prime sieve using communication channels
in Haskell (typed STM based channels) and I got a pretty good boost by
telling the scheduler there was more than one CPU.

http://hpaste.org/7766
(was my first try with this kind of haskell, so it's probably not that
pretty).


>
>
> And for processing, finally threads are also called in some
> implementations: LWP, that is simply something that could have been
> solved with Processes, if it was not so costly.
> I have the impression that LWP is just a solution to poor process
> creation and to poor IPC tools (threads are the solution not for
> parallelism by itself, but because there is need to share resources
> between processes and that it is simplest to put them in the same
> address space).
>
> The most efficient is to have tools that match the way our brains work
> (or not...). I'm not convinced our brains are "parallel" (at least mines
> are not).


What Joe Armstrong (of Erlang) would tell you (I think) is that we operate
concurrently, and we communicate with each other via message passing, and
that we manage to get work done in parallel this way, so why not manage
parallel applications in this same system model?


If you have lots of cores, and you wrote your application in a concurrent
manner, in theory, many of them *could* run in parallel, but obviously this
makes it sound more like art than science :-)  One must know when a given
process depends on the results of others to show where things are really not
in parallel but just compositions of serial operations.



>
> --
> Thierry Laronde (Alceste) <tlaronde +AT+ polynum +dot+ com>
>                 http://www.kergis.com/
> Key fingerprint = 0FF7 E906 FBAF FE95 FD89  250D 52B1 AE95 6006 F40C
>
>

[-- Attachment #2: Type: text/html, Size: 4175 bytes --]

Re: [9fans] current state of thread programming

[andrey mirtchovski]

> Is the human thought process parallel? For _my capacities_, I have the
> impression that I'm more multitask than parallel. And context switch is
> expensive because there is not only explicit data, but also implicit and
> I'm not able, if I'm really doing something involved, to restore the
> previous state without much ado.

I, for one, think that this analogy is incorrect. It is your
perception of what the brain is doing (higher order functions) that
appears to be sequential, however, underneath it all, the brain is
being highly parallel at doing all the functions that keep us alive:
basic motor functions such as breathing, eyesight (which in itself is
a highly parallel endeavour), hunger, circadian rhythms if you will.
Even the neocortex is parallel: you can easily talk while, say,
navigating the corridors of a building.

The fact that most tasks that require extreme concentration (and using
several of our neocortex functions in a coordinated fashion to solve a
single problem) appear, to us, to be dealt with by 'multitasking', may
simply be an evolutionary shortcoming to be fixed in later
generations. Something like being able to SMS at 40 words per minute
while headbanging at a concert :)

So, in essence, I think the brain may be exactly what Dijkstra had in
mind in the earlier quote: its workings are so implicitly parallel
that the word 'parallel' carries no meaning when describing it.

Re: [9fans] current state of thread programming

[Roman V. Shaposhnik]

[I promise this to be my last off-topic message, but I just can't resit]

On Wed, 2008-07-30 at 08:00 -0600, andrey mirtchovski wrote:
> So, in essence, I think the brain may be exactly what Dijkstra had in
> mind in the earlier quote: its workings are so implicitly parallel
> that the word 'parallel' carries no meaning when describing it.

I believe I've already bored everyone to death with this joke (I usually
tell it during my Multicore and Transactional Memory presentations),
but here it goes again. If we were to oversimplify things than brain
is, at its core, limited by a very fundamental biological constraint:
speed at which cells can communicate. A sort of "propagation delay"
if we were to use electronics as an analogy. It seems to be agreed
upon(*) that we can safely assume this constraint to limit our brain
to about couple of hundred of processing steps per second. This is
known as a "100 steps rule". Something is really, really wrong with
the computing model we base our technology on, if even the slowest
of the computers we can consider useful required a clock rate
of KHz.

I really wish Jeff Hawkins (http://www.onintelligence.org/) the best
of luck. I doubt his institution is going to unlock the mystery
of the brain any time soon, but the feedback for our industry
can be pretty groundbreaking. If they get lucky, of course.

Thanks,
Roman.

(*) Rumelhart, E., & McClelland, J. L. (Eds.). (1986).
    Parallel Distributed Processing. (Vol. 1, 2).
    Cambridge, MA: MIT Press.
    --------------------------------------------------
    Feldman, J. and Ballard, D. (1982),
    Connectionist Models and Their Properties
    in Cognitive Science, 6, pp. 205-254.

Re: [9fans] current state of thread programming

[Bakul Shah]

> > Is the human thought process parallel? For _my capacities_, I have the
> > impression that I'm more multitask than parallel. And context switch is
> > expensive because there is not only explicit data, but also implicit and
> > I'm not able, if I'm really doing something involved, to restore the
> > previous state without much ado.
>
> I, for one, think that this analogy is incorrect. It is your
> perception of what the brain is doing (higher order functions) that
> appears to be sequential, however, underneath it all, the brain is
> being highly parallel at doing all the functions that keep us alive:
> basic motor functions such as breathing, eyesight (which in itself is
> a highly parallel endeavour), hunger, circadian rhythms if you will.
> Even the neocortex is parallel: you can easily talk while, say,
> navigating the corridors of a building.

Besides, parallel programming is not about modelling human
brain or thought processes (though you can use it for that).
The other point to make is that *reasoning* about parallel
programming need not to be parallel and one should be able to
do that even with a "sequential" brain!

>              Something like being able to SMS at 40 words per minute
> while headbanging at a concert :)

I never thought of ADHD as parallel programming!

> So, in essence, I think the brain may be exactly what Dijkstra had in
> mind in the earlier quote: its workings are so implicitly parallel
> that the word 'parallel' carries no meaning when describing it.

His papers like "A new elephant built from mosquitoes humming
in harmony" etc. make me think perhaps he was talking about a
new way of looking at parallel programming and not at how our
brains work as such.  May be CSP is it but I don't really know.

Re: [9fans] current state of thread programming

[tlaronde]

On Wed, Jul 30, 2008 at 04:50:39AM -0700, Roman V. Shaposhnik wrote:
> 
> No. But to give you an example of why that shouldn't matter I would
> like to note that the human thought is, in my opinion, finite. Yet,
> we have developed very nice and efficient tools for comprehending and
> reasoning about infinity. 
> 

Like the antinomies that shaked the foundations of Mathematics at the
beginning of the 20th century :-^

And as a side note, I'm always happy when I read papers about AI where
somebody explains that a computer will probably be able (using huge
parallelism perhaps!) to solve problems that a humain being can not
solve.

I.e., that a program, that is instructions; this means, finally, integer
numbers (sequence of bits); that is a projection on arithmetic, will be
able to decide undecidable propositions... (I seem to remember something
about Gödel...)

> P.S. I guess, we are getting way off topic here.
 
Yes, and I will stop there.

Cheers,
-- 
Thierry Laronde (Alceste) <tlaronde +AT+ polynum +dot+ com>
                 http://www.kergis.com/
Key fingerprint = 0FF7 E906 FBAF FE95 FD89  250D 52B1 AE95 6006 F40C

Re: [9fans] current state of thread programming

[tlaronde]

On Wed, Jul 30, 2008 at 04:50:39AM -0700, Roman V. Shaposhnik wrote:
> On Wed, 2008-07-30 at 13:35 +0200, tlaronde@polynum.com wrote:
>
> > The most efficient is to have tools that match the way our brains work
> > (or not...). I'm not convinced our brains are "parallel" (at least mines
> > are not).
>
> I disagree on philosophical grounds ;-) It's been one of the major
> engineering follies to always approach design from a "just follow
> the nature" standpoint. No wonder that before the Wright brothers
> everybody thought the best way to fly is to flap some kind of wings.

When I spoke about "tools", I meant "programming tools". Computers are
already parallel, multi-task. There are already "collaborative" between
devices that have their own processing capabilities distinct from the
CPU(s); between users, or between tasks (real processes) of a same user.

But I do not believe that a programming tool could transform magically
the dumping of a programmer's brains (called a program source) and find
magically parallelism if the programmer has not thought of the thing
(primarily from the data structure point of view), since, at least for
my limited capacities, I may organize task in parallel, but I find
sequential solutions (an algorithm is defined for me as a kind of
elementary, atomic process; the organization, articulation of the
program is engineering, not algorithmics).
--
Thierry Laronde (Alceste) <tlaronde +AT+ polynum +dot+ com>
                 http://www.kergis.com/
Key fingerprint = 0FF7 E906 FBAF FE95 FD89  250D 52B1 AE95 6006 F40C

Re: [9fans] current state of thread programming

[andrey mirtchovski]

> I disagree on philosophical grounds ;-) It's been one of the major
> engineering follies to always approach design from a "just follow
> the nature" standpoint. No wonder that before the Wright brothers
> everybody thought the best way to fly is to flap some kind of wings.

off topic, but to note: biomimetics are making a comeback
http://ngm.nationalgeographic.com/2008/04/biomimetics/tom-mueller-text/1

Re: [9fans] current state of thread programming

[Eris Discordia]

> Either that or (like some brain scientists say) something is
> really, really wrong or suboptimal about the human brain.

Despite prospects of brain uptime--that's LE--being around 77.71 years for
each individual of the USAmerican population and the "entire history" of
computers being shorter than that.

I see where your "brain scientists" are driving at. Let them have a
P9-on-x86  transplant for those mouldy clumps in their crania. I'll be
happy to have all their "clumps."

--On Tuesday, August 05, 2008 3:34 AM -0700 Richard Maxwell Underwood
<ru@river.org> wrote:

> Roman V. Shaposhnik writes:
>>               If we were to oversimplify things [then the] brain
>> is, at its core, limited by a very fundamental biological constraint:
>> speed at which cells can communicate. A sort of "propagation delay"
>> if we were to use electronics as an analogy. It seems to be agreed
>> upon(*) that we can safely assume this constraint to limit our brain
>> to about couple of hundred of processing steps per second. This is
>> known as a "100 steps rule".
>
>>                             Something is really, really wrong with
>> the computing model we base our technology on, if even the slowest
>> of the computers we can consider useful required a clock rate
>> of KHz.
>
> Either that or (like some brain scientists say) something is
> really, really wrong or suboptimal about the human brain.
>

Re: [9fans] current state of thread programming

[Richard Maxwell Underwood]

Roman V. Shaposhnik writes:
>               If we were to oversimplify things [then the] brain
>is, at its core, limited by a very fundamental biological constraint:
>speed at which cells can communicate. A sort of "propagation delay"
>if we were to use electronics as an analogy. It seems to be agreed
>upon(*) that we can safely assume this constraint to limit our brain
>to about couple of hundred of processing steps per second. This is
>known as a "100 steps rule".

>                             Something is really, really wrong with
>the computing model we base our technology on, if even the slowest
>of the computers we can consider useful required a clock rate
>of KHz.

Either that or (like some brain scientists say) something is
really, really wrong or suboptimal about the human brain.

Re: [9fans] current state of thread programming

[tlaronde]

On Wed, Jul 30, 2008 at 02:58:48PM -0400, Sape Mullender wrote:
> >
> > It's a kind of parallelism, of course. But since it makes sense, it is
> > not "parallelism" as the trend is today ;)
>
> I don't know what the trend is today.  If the trend is defined by what
> Linux does then I'm not very curious.

Since my pseudo-english is only what it is, I hope that "kind of
parallelism" is not interpreted pejoratively. I mean a "form of
parallelism", a "way of using parallelism", etc.

>
> I think of parallel programming as a technique for finishing some algorithm faster.
>

I do agree with what you wrote and emphasize particularily this
sentence : parallelism doesn't _solve_ a problem; it delivers
the solution sooner. That's why I'm saying that an algorithm (that is
the expression of a solution) is sequential. But organization can be
parallel.

But indeed CSP is also a solution (above concurrency/"parallelism") to
solve a kind of problems. It is not mere parallelism, it is a way of
using/dealing with concurrency (a form of parallelism).


Real world example (about "parallelism", not CSP): geometrical
application, vectorial data, transforming "spaghettis" into
topologically correct data (connected edges). I had debugged an
existing program. It was finally giving an acceptable result, but
it was not scalable.

The "trend" today would be: convert to "threads" to go faster.

But the problem was not to parallelize a poor algorithm. The problem was
to find the correct data structure and "sequential" algorithm for this
data and its manipulations.

It happens that once these are found (or at least better ones),
the program could be naturally parallelized (even simply by splitting
the data into chunks; running distinct processes on the distinct
chunks; and concatenating the results). Parallelism is a by-product. It
was not a goal. And it simply can transform a program taking n *
some_unit_of_time, in a program taking something near 1 some_unit_of_time
given n cores. But the main gain was the big O of the sequential
algorithm.

A better algorithm improves the solution or the delivery of the solution
on a single CPU. Parallelization doesn't improve the solution or the
delivery of a solution on a single CPU (it may even worsen the times).

Cheers,
--
Thierry Laronde (Alceste) <tlaronde +AT+ polynum +dot+ com>
                 http://www.kergis.com/
Key fingerprint = 0FF7 E906 FBAF FE95 FD89  250D 52B1 AE95 6006 F40C

Re: [9fans] current state of thread programming

[Sape Mullender]

>> i don't see how csp is *not* parallel processing.  as soon
>> as you have more than 1 work process per client, i would call
>> that parallel processing.
>
> It's a kind of parallelism, of course. But since it makes sense, it is
> not "parallelism" as the trend is today ;)

I don't know what the trend is today.  If the trend is defined by what
Linux does then I'm not very curious.


The point of the Plan 9 thread library was — and still is, as far
as I'm concerned — to be a tool that aids in concurrent programming.
I'm explicitly not saying parallel programming.  I think of
parallel programming as a technique for finishing some algorithm faster.
I think of concurrent programming as a way of keeping indeterminism
under control.  A file server serves many customers simultaneously,
and must expect requests, disk events, etc. to happen in any order.

Managing this is what Plan 9 threaded programs are good at.
And our model of using channels for interthread and interprocess
communication, while using a thread pool (all in one proc) for managing
shared data without needing locks, is the best programming model for
these kinds of programs I've ever come across.

You can write parallel programs using the thread library but that's not
what its primary purpose was and it's probably not going to help you
much.

	Sape

Re: [9fans] current state of thread programming

[tlaronde]

On Wed, Jul 30, 2008 at 08:50:28AM -0400, erik quanstrom wrote:
>
> i don't see how csp is *not* parallel processing.  as soon
> as you have more than 1 work process per client, i would call
> that parallel processing.

It's a kind of parallelism, of course. But since it makes sense, it is
not "parallelism" as the trend is today ;)

> [..]
> one could argue that isn't *really* parallel because the
> requests for the n blocks are made sequentially.
> but since drives, operating on the timescale of tens of
> milliseconds are competing with a processor working on
> a nanosecond timescale.  that's effectively "all at once".

This is precisely the point:

1) It is not "pure parallelism" or "parallelism du jour". But it is parallelism
too.

2) Developers have not waited for the trend to make or use parallelism.

3) An algorithm is, for me, intrinsically sequential (the elementary
unit is sequential). Parallelism is more at a higher level: methodology,
engineering, the same level as, say, structural programming.
--
Thierry Laronde (Alceste) <tlaronde +AT+ polynum +dot+ com>
                 http://www.kergis.com/
Key fingerprint = 0FF7 E906 FBAF FE95 FD89  250D 52B1 AE95 6006 F40C

Re: [9fans] current state of thread programming

[erik quanstrom]

>
> CSP is (for me) the best answer to problem involving blocking/waiting on
> input. But this is not parallelism.
>

i don't see how csp is *not* parallel processing.  as soon
as you have more than 1 work process per client, i would call
that parallel processing.

for example, the way ken's fs worked** with the worm is that
n readahead messages read from the rahqueue.  this meant
that they would block on input until there was something
to do.  since there were many cache drives and (i believe)
multiple optical drives, a request loop requesting n
blocks from the rah device could potentially get all the
physical drives going in parallel.

while ken's implementation might not fit the textbook
description of csp, it's pretty close in spirit.

one could argue that isn't *really* parallel because the
requests for the n blocks are made sequentially.
but since drives, operating on the timescale of tens of
milliseconds are competing with a processor working on
a nanosecond timescale.  that's effectively "all at once".

- erik

** the version in extra only starts one rah process and
uses an elevator algorithim on worm addresses.  this
works best on a single-disk system.