Re: [fonc] Physics Simulation (Re: Everything You Know (about Parallel Programming) Is Wrong!: A Wild Screed about the Future)

[BGB]

On 4/3/2012 9:29 PM, Miles Fidelman wrote:

BGB wrote:


On 4/3/2012 10:47 AM, Miles Fidelman wrote:


Hah.  You've obviously never been involved in building a CGF 
simulator (Computer Generated Forces) - absolute spaghetti code when 
you have to have 4 main loops, touch 2000 objects (say 2000 tanks) 
every simulation frame.  Comparatively trivial if each tank is 
modeled as a process or actor and you run asynchronously.


I have not encountered this term before, but does it have anything to 
do with an RBDE (Rigid Body Dynamics Engine), or often called simply 
a "physics engine". this would be something like Havok or ODE or 
Bullet or similar.


There is some overlap, but only some - for example, when modeling 
objects in flight (e.g., a plane flying at constant velocity, or an 
artillery shell in flight) - but for the most part, the objects being 
modeled are active, and making decisions (e.g., a plane or tank, with 
a simulated pilot, and often with the option of putting a 
person-in-the-loop).


So it's really impossible to model these things from the outside 
(forces acting on objects), but more from the inside (run 
decision-making code for each object).




fair enough...

but, yes, very often in cases where one is using a physics engine, this 
may be combined with the use of internal logic and forces as well, 
albeit admittedly there is a split:
technically, these forces are applied directly by whatever code is using 
the physics engine, rather than by the physics engine itself.


for example: just because it is a physics engine doesn't mean that it 
necessarily has to be "realistic", or that objects can't supply their 
own forces.


I guess, however, that this would be closer to the main "server end" in 
my case, namely the part that manages the entity system and NPC AIs and 
similar (and, also, the game logic is more FPS style).


still not heard the term CGF before though.


in this case, the basic timestep update is basically to loop over all 
the entities in the scene and calls their "think" methods and similar 
(things like AI and animation and similar are generally handled via 
think methods and similar), and maybe do things like updating physics 
(if relevant), ...


this process is single threaded with a single loop though.

I guess it is arguably "event-driven" though:
handling timing is done via events ("think" being a special case);
most interactions between entities involve events as well;
...

many entities and AIs are themselves essentially finite-state-machines.


or such...


___
fonc mailing list
fonc@vpri.org
http://vpri.org/mailman/listinfo/fonc

Re: [fonc] Everything You Know (about Parallel Programming) Is Wrong!: A Wild Screed about the Future

[David Barbour]

On Tue, Apr 3, 2012 at 7:55 PM, Miles Fidelman
wrote:

>
>> You seem to be starting from the assumption that process per object is a
>> good thing.
>>
>
> absolutely - I come from a networking background - you spawn a process for
> everything - it's conceptually simpler all around - and as far as I can
> tell, most things that complex systems are inherently parallel
>
> having to serialize things that are inherently parallel (IMHO) only makes
> sense if you're forced to by constraints of the run-time environment


I agree there is a lot of latent parallelism in most systems. But
process-per-object is not necessarily the best way to express that
parallelism. It certainly won't be the most efficient way to express
parallelism, and in practice - unless you don't care about quality of your
simulator - you'll be adding complexity to regain consistency (i.e. so
tanks don't keep doing things after they should have been blown up because
a message was lost or out of order).



That's what I meant.  Each loop has to touch each object, every simulation
> cycle, to see if anything has happened that needs attention.  It's been a
> while, but as I recall it's something like
> 1. loop one, update all lines of sight
> 2. loop two, update all sensors
> 3. loop three, calculate weapons effects
> 4. loop four, update positions
> 5. loop five, update graphic display
> 6. repeat ad nauseum
>

In the pipeline model I was suggesting, all five loops run
pipeline-parallel, and we can have data-parallelism within each loop (e.g.
running 100 tanks at a time in OpenCL). So I look at that loop and see easy
potential for 500x parallelism without any loss to determinism or
consistency and with much lower overheads.


>
> If I were building one of these, in say Erlang, if a tank is doing
> nothing, it simply sits and does nothing.  If it's moving, maybe a
> heartbeat kicks off a recalculation every so often.  Everything else is a
> matter of event-driven activities.


> The sequential approach pretty much forces things down a path of touching
> everything, frequently, in a synchronous manner.


It's easy enough to just maintain different collections for different
processing. I.e. rather than one big collection of tanks, you can have five
lists - tanks that are moving, tanks that are targeting, etc. - with
pointers back to the master list. But it's often more efficient to just
keep a mode in each tank and process them all (e.g. skip targeting for
those not in firing mode) every instant.

A heartbeat every so often for motion? 20Hz is already a latency of 50ms to
begin reacting to changes in the environment, and is borderline adequate
for a combat simulator. What are you imagining, exactly?

You seem hell bent on premature optimization there; don't be surprised if
you get the hell without the optimization.


>   Asynchronous, event-driven behavior is a LOT easier to conceptualize and
> code.


Or maybe you're only conceptualizing an idealized version of the code, the
happy path...



 (Except for line-of-sight calculations.)
>

And collision-detection and a bunch of other things...


>
> By the way, as soon as you network simulators (at least military ones, not
> necessarily MMORPGs) it's very much a parallel, asynchronous world.


That really depends on the communication protocol, of course. There are
many ways it could have been achieved.


>
> It all just works.   Not all that new either - dates back to BBN's SIMNET
> stuff back in the late 1980s.
>

It works for some purposes. But I've sat in on one presentation that
expressed frustration about rewind, replay-with-variation, etc. features
and the inability to leverage simulators as testing software.


>
> FYI: It was having a number of our coders tell me that there's just too
> much context-switching to consider an asynchronous architecture, that led
> me to discover Erlang - one of the few (perhaps the only) environments that
> support massive concurrency.


There's actually quite a few languages today that support massive
concurrency. And there are languages to support massive parallelism (like
OpenCL).


>> I think there are simple, parallel approaches. I know there are
>> simplistic, parallel approaches.
>>
>

 Not to be impolite, but what point are you trying to make?
>

Your approach to parallelism strikes me as simplistic. Like saying Earth is
in center of Solar system. Sun goes around Earth. It sounds simple. It's
"easy to conceptualize". Oh, and it requires epicyclic orbits to account
for every other planet. Doesn't sound so simple anymore. Like this,
simplistic becomes a complexity multiplier in disguise.

You propose actor per object. It sounds simple to you, and "easy to
conceptualize". But now programmers have challenges to control latency,
support replay, testing, maintenance, verification, consistency. This is in
addition to problems hand-waved through like line-of-sight and collision
detection. It doesn't sound so simple anymore.

The old sequential model, or even the p

Re: [fonc] Physics Simulation (Re: Everything You Know (about Parallel Programming) Is Wrong!: A Wild Screed about the Future)

[Miles Fidelman]

BGB wrote:


On 4/3/2012 10:47 AM, Miles Fidelman wrote:


Hah.  You've obviously never been involved in building a CGF 
simulator (Computer Generated Forces) - absolute spaghetti code when 
you have to have 4 main loops, touch 2000 objects (say 2000 tanks) 
every simulation frame.  Comparatively trivial if each tank is 
modeled as a process or actor and you run asynchronously.


I have not encountered this term before, but does it have anything to 
do with an RBDE (Rigid Body Dynamics Engine), or often called simply a 
"physics engine". this would be something like Havok or ODE or Bullet 
or similar.


There is some overlap, but only some - for example, when modeling 
objects in flight (e.g., a plane flying at constant velocity, or an 
artillery shell in flight) - but for the most part, the objects being 
modeled are active, and making decisions (e.g., a plane or tank, with a 
simulated pilot, and often with the option of putting a person-in-the-loop).


So it's really impossible to model these things from the outside (forces 
acting on objects), but more from the inside (run decision-making code 
for each object).


Miles

--
In theory, there is no difference between theory and practice.
In practice, there is.    Yogi Berra


___
fonc mailing list
fonc@vpri.org
http://vpri.org/mailman/listinfo/fonc

[fonc] Physics Simulation (Re: Everything You Know (about Parallel Programming) Is Wrong!: A Wild Screed about the Future)

[BGB]

(changed subject, as this was much more about physics simulation than 
about concurrency).


yes, this is a big long "personal history dump" type thing, please 
ignore if you don't care.



On 4/3/2012 10:47 AM, Miles Fidelman wrote:

David Barbour wrote:


Control flow is a source of much implicit state and accidental 
complexity.


A step processing approach at 20Hz isn't all bad, though, since at 
least you can understand the behavior of each frame in terms of the 
current graph of objects. The only problem with it is that this 
technique doesn't scale. There are easily up to 15 orders of 
magnitude in update frequency between slow-updating and fast-updating 
data structures. Object graphs are similarly heterogeneous in many 
other dimensions - trust and security policy, for example.


Hah.  You've obviously never been involved in building a CGF simulator 
(Computer Generated Forces) - absolute spaghetti code when you have to 
have 4 main loops, touch 2000 objects (say 2000 tanks) every 
simulation frame.  Comparatively trivial if each tank is modeled as a 
process or actor and you run asynchronously.




I have not encountered this term before, but does it have anything to do 
with an RBDE (Rigid Body Dynamics Engine), or often called simply a 
"physics engine".

this would be something like Havok or ODE or Bullet or similar.

I have written such an engine before, but my effort was single-threaded 
(using a fixed-frequency virtual timer, with time-step subdivision to 
deal with fast-moving objects).


probably would turn a bit messy though if it had to be made internally 
multithreaded (it is bad enough just trying to deal with irregular 
timesteps, blarg...).


however, it was originally considered to potentially run in a separate 
thread from the main 3D engine, but I never really bothered as there 
turned out to not be much point.



granted, one could likely still parallelize it while keeping everything 
frame-locked though, like having the threads essentially just subdivide 
the scene-graph and each work on a certain part of the scene, doing the 
usual thing of all of them predicting/handling contacts within a single 
time step, and then all updating positions in-sync, and preparing for 
the next frame.


in the above scenario, the main cost would likely be how to best go 
about efficiently dividing up work among the threads (the usual strategy 
I use is work-queues, but I have doubts regarding their scalability).


side note:
in my own experience, simply naively handling/updating all objects 
in-sequence doesn't tend to work out very well when mixed with things 
like contact forces (example: check if object can make move, if so, 
update position, move on to next object, ...). although, this does work 
reasonably well for "Quake-style" physics (where objects merely update 
positions linearly, and have no actual contact forces).


better seems to be:
for all moving objects, predict where the object wants to be in the next 
frame;

determine which objects will collide with each other;
calculate contact forces and apply these to objects;
update movement predictions;
apply movement updates.

however, interpenetration is still not avoided (sufficient forces will 
still essentially push objects into each other). theoretically, one can 
disallow interpenetration (by doing like Quake-style physics and simply 
disallow any post-contact updates which would result in subsequent 
interpenetration), but in my prior attempts to enable such a feature, 
the objects would often become "stuck" and seemingly entirely unable to 
move, and were in-fact far more prone to violently explode (a pile of 
objects will seemingly become stuck-together and immovable, maybe for 
several seconds, until ultimately all of them will violently explode 
outward at high velocities).


allowing objects to interpenetrate was thus seen as the "lesser evil", 
since, even though objects were violating the basic assumption that 
"rigid bodies aren't allowed to exist in the same place at the same 
time", typically (assuming the collision-detection and force-calculation 
functions are working correctly, itself easier said than done), this 
will generally correct itself reasonably quickly (the contact forces 
will push the objects back apart, until they reach a sort of 
equilibrium), and with far less incidence of random "explosions".


sadly, the whole physics engine ended up a little "rubbery" as a result 
of all of this, but it seemed reasonable, as I have also observed 
similar behavior to some extent in Havok, and have figured out that I 
could deal with matters well enough by using a simpler (Quake-style) 
physics engine for most non-dynamic objects. IOW: things using AABBs 
(Axis-Aligned Bounding-Box) and similar, and other related "solid 
objects which can't undergo rotation", a very naive "check and update" 
strategy works fairly well for objects which can only ever undergo 
translational movement.


admittedly, I also never was able 

Re: [fonc] Everything You Know (about Parallel Programming) Is Wrong!: A Wild Screed about the Future

[Miles Fidelman]

David Barbour wrote:


On Tue, Apr 3, 2012 at 5:17 PM, Miles Fidelman 
mailto:mfidel...@meetinghouse.net>> wrote:



But there are good architectures that won't become spaghetti
code in these circumstances. If you pipelined 2000 tank data
objects through four processes each instant, for example (i.e.
so tanks 1-100 are in the last process of four while 301-400
are in the first) there would be some clear constraints on
communication, and state could be updated only at transition
from one instant to another.

You're speaking theoretically, of course.  The systems I'm
familiar with are fairly highly evolved and optimized.  They just
start from the assumption that you can't spawn a process for every
object.


I have written simulators before, though not for CGF. Pipelines work 
very well - they offer a low overheads due to batch processing, data 
parallelism within each stage, pipeline parallelism between stages, 
and can be both real-time and deterministic. Same principle as 
rendering a scene and running a bunch of vertex shaders each frame.
Even if I have a system where context switching and process-per-tank 
is free, I would be disinclined to model things that way. It is more 
valuable to reason about consistency and robustness, to have 
determinism for maintenance and regression testing, to know the 
simulation will run the same etc.


You seem to be starting from the assumption that process per object is 
a good thing.


absolutely - I come from a networking background - you spawn a process 
for everything - it's conceptually simpler all around - and as far as I 
can tell, most things that complex systems are inherently parallel


having to serialize things that are inherently parallel (IMHO) only 
makes sense if you're forced to by constraints of the run-time environment




http://blog.incubaid.com/2012/03/28/the-game-of-distributed-systems-programming-which-level-are-you/



You claim managing 2000 asynchronous processes is trivial. I
think you'll just find different things to complain about
after you have, say, 2000 actors processing 16
asynchronous messages per second (4 messages per actor * 20
Hz, minimal for your example) plus managing consistent views
and safe updates of a shared map or environment, or consistent
snapshots for persistence.


What makes you assume that every actor is doing anything all the
time.  A lot of them are simply sitting in one place, others are
moving but not interacting with anything.  The major events are
weapons fire events, which are not happening at 20hz.


I interpreted your words to assume it. You said: "you have 4 main 
loops touch 2000 objects every simulation frame". To me this sounds 
like 4 loops each touching the same 2000 objects at 20 Hz = 4 * 2000 * 
20 = 160k. I figured each loop was handling something different so as 
to avoid collisions - e.g. sensors, comms, navigation and obstacle 
avoidance, targeting. Did you mean something else? Anyhow, a touch 
likely corresponds to one or two messages. My estimate of 160k 
messages per second was, IMO, quite conservative.
That's what I meant.  Each loop has to touch each object, every 
simulation cycle, to see if anything has happened that needs attention.  
It's been a while, but as I recall it's something like

1. loop one, update all lines of sight
2. loop two, update all sensors
3. loop three, calculate weapons effects
4. loop four, update positions
5. loop five, update graphic display
6. repeat ad nauseum

If I were building one of these, in say Erlang, if a tank is doing 
nothing, it simply sits and does nothing.  If it's moving, maybe a 
heartbeat kicks off a recalculation every so often.  Everything else is 
a matter of event-driven activities.


The sequential approach pretty much forces things down a path of 
touching everything, frequently, in a synchronous manner.  Asynchronous, 
event-driven behavior is a LOT easier to conceptualize and code.  
(Except for line-of-sight calculations.)


By the way, as soon as you network simulators (at least military ones, 
not necessarily MMORPGs) it's very much a parallel, asynchronous world.  
Each simulator maintains its own world view, calculates what other 
entities are doing by dead reckoning, and the only things that travel 
across the net are deltas (aspect and velocity changes, weapons fire) - 
usually taking the form of multicast UDP packets (look up the DIS 
protocol sometime).  It all just works.   Not all that new either - 
dates back to BBN's SIMNET stuff back in the late 1980s.


FYI: It was having a number of our coders tell me that there's just too 
much context-switching to consider an asynchronous architecture, that 
led me to discover Erlang - one of the few (perhaps the only) 
environments that support massive concurrency.



But this is far afield from the basic point:  Someone suggested
th

Re: [fonc] Everything You Know (about Parallel Programming) Is Wrong!: A Wild Screed about the Future

[David Barbour]

On Tue, Apr 3, 2012 at 5:17 PM, Miles Fidelman 
 wrote:

>
>> But there are good architectures that won't become spaghetti code in
>> these circumstances. If you pipelined 2000 tank data objects through four
>> processes each instant, for example (i.e. so tanks 1-100 are in the last
>> process of four while 301-400 are in the first) there would be some clear
>> constraints on communication, and state could be updated only at transition
>> from one instant to another.
>>
> You're speaking theoretically, of course.  The systems I'm familiar with
> are fairly highly evolved and optimized.  They just start from the
> assumption that you can't spawn a process for every object.


I have written simulators before, though not for CGF. Pipelines work very
well - they offer a low overheads due to batch processing, data parallelism
within each stage, pipeline parallelism between stages, and can be both
real-time and deterministic. Same principle as rendering a scene and
running a bunch of vertex shaders each frame.

Even if I have a system where context switching and process-per-tank is
free, I would be disinclined to model things that way. It is more valuable
to reason about consistency and robustness, to have determinism for
maintenance and regression testing, to know the simulation will run the
same etc.

You seem to be starting from the assumption that process per object is a
good thing.

http://blog.incubaid.com/2012/03/28/the-game-of-distributed-systems-programming-which-level-are-you/


>
>> You claim managing 2000 asynchronous processes is trivial. I think you'll
>> just find different things to complain about after you have, say, 2000
>> actors processing 16 asynchronous messages per second (4 messages per
>> actor * 20 Hz, minimal for your example) plus managing consistent views and
>> safe updates of a shared map or environment, or consistent snapshots for
>> persistence.
>>
>
> What makes you assume that every actor is doing anything all the time.  A
> lot of them are simply sitting in one place, others are moving but not
> interacting with anything.  The major events are weapons fire events, which
> are not happening at 20hz.


I interpreted your words to assume it. You said: "you have 4 main loops
touch 2000 objects every simulation frame". To me this sounds like 4 loops
each touching the same 2000 objects at 20 Hz = 4 * 2000 * 20 = 160k. I
figured each loop was handling something different so as to avoid
collisions - e.g. sensors, comms, navigation and obstacle avoidance,
targeting. Did you mean something else? Anyhow, a touch likely corresponds
to one or two messages. My estimate of 160k messages per second was, IMO,
quite conservative.

I grant we could optimize cases when a tank is doesn't need certain
processing. But let's not start assuming that most active objects in our
simulation are just sitting still - that assumption often fails in practice.


>
> The difficult part of the job, and the one that causes a shared-nothing
> approach problematic, is line-of-sight calculations - who can see whom.
>  Ultimately that has to be solved.
>

Navigation, obstacle avoidance, convoying and formations, and a number of
other problems are also non-trivial.


>
> But this is far afield from the basic point:  Someone suggested that
> people thing sequentially, or that parallelism is more complicated than
> sequential architectures.  This is a very real case where that simply is
> not the case - sequential approaches to this problem space are inherently
> more complicated than parallel ones.


I think there are simple, parallel approaches. I know there are simplistic,
parallel approaches.

Regards,

Dave

-- 
bringing s-words to a pen fight
___
fonc mailing list
fonc@vpri.org
http://vpri.org/mailman/listinfo/fonc

Re: [fonc] Everything You Know (about Parallel Programming) Is Wrong!: A Wild Screed about the Future

[BGB]

On 4/3/2012 9:46 AM, Miles Fidelman wrote:

David Barbour wrote:


On Tue, Apr 3, 2012 at 8:25 AM, Eugen Leitl > wrote:


It's not just imperative programming. The superficial mode of human
cognition is sequential. This is the problem with all of mathematics
and computer science as well.


Perhaps human attention is basically sequential, as we're only able 
to focus our eyes on one point and use two hands.  But I think humans 
understand parallel behavior well enough - maintaining multiple 
relationships, for example, and predicting the behaviors of multiple 
people.


And for that matter, driving a car, playing a sport, walking and 
chewing gum at the same time :-)




yes, but people have built-in machinery for this, in the form of the 
cerebellum.
relatively little conscious activity is generally involved in these 
sorts of tasks.


if people had to depend on their higher reasoning powers for basic 
movement tasks, people would likely be largely unable to operate 
effectively in basic day-to-day tasks.





If you look at MPI debuggers, it puts people into a whole other
universe of pain that just multithreading.


I can think of a lot of single-threaded interfaces that put people in 
a universe of pain. It isn't clear to me that distribution is at 
fault there. ;)




Come to think of it, tracing flow-of-control through an 
object-oriented system REALLY is a universe of pain (consider the 
difference between a simulation - say a massively multiplayer game - 
where each entity is modeled as an object, with one or two threads 
winding their way through every object, 20 times a second; vs. 
modeling each entity as a process/actor).




FWIW, in general I don't think much about global control-flow.

however, there is a problem with the differences between:
global behavior (the program as a whole);
local behavior (a local collection of functions and statements).

a person may tend to use general fuzzy / "intuitive" behavior for 
reasoning about "the system as a whole", but will typically use fairly 
rigid sequential logic for thinking about the behavior of a given piece 
of code.


there is a problem if the individual pieces of code are no longer 
readily subject to analysis.



the problem I think with multithreading isn't so much that things are 
parallel or asynchronous, but rather that things are very often 
inconsistent.


if two threads try to operate on the same piece of data at the same 
time, often this will create states which are impossible had either been 
operating on the data individually (and, very often, changes made in one 
thread will not be immediately visible to others, say, because the 
compiler had not actually thought to write the change to memory, or the 
other thread to reload the variable).


hence, people need things like the "volatile" modifier, use of atomic 
operations, things like "mutexes" or "synchronized" regions, ...



this leaves several possible options:
systems go further in this direction, with little expectation of global 
synchronization unless some specific mechanism is used (two threads 
working on a piece of memory may temporarily each see their own local copy);
or, languages/compilers go the other direction, so that one thread 
changing a variable is mandated to be immediately visible to other threads.


one option is more costly than the other.

as-is, the situation seems to be that compilers lean on one side (only 
locally consistent), whereas the HW tries to be globally consistent.


a question then, is assuming HW is not kept strictly consistent, how to 
best handle this (regarding both language design and performance).



however, personally I think abandoning local sequential logic and 
consistency, as being a bad move.


I am personally more in-favor of message passing, and either the ability 
to access objects synchronously, or "pass messages to the object", which 
may be in-turn synchronous.


consider, for example:
class Foo
{
sync function methodA() { ... }//synchronous (only one such 
method executes at a time)

sync function methodB() { ... }//synchronous
async function methodC() { ... }//asynchronous / concurrent 
(calls will not block)
sync async function methodD() { ... } //synchronous, but calls will 
not block

}

...
var obj=new Foo();

//thread A
obj.methodA();
//thread B
obj.methodB();

the VM could enforce that the object only executes a single such method 
at a time (but does not globally lock the object, unlike "synchronized").


similarly:
//thread A
async obj.methodA();
//thread B
async obj.methodB();

which works similarly, except neither thread blocks (in this case, "obj" 
functions as a virtual process, and the method call serves more as a 
message pass). note that, if methods are not "sync", then they may 
execute concurrently.


note that "obj.methodC();" will behave as if the async keyword were 
given (it may be called concurrently). "obj.methodD();" will beha

Re: [fonc] Everything You Know (about Parallel Programming) Is Wrong!: A Wild Screed about the Future

[Miles Fidelman]

David Barbour wrote:



On Tue, Apr 3, 2012 at 10:47 AM, Miles Fidelman 
mailto:mfidel...@meetinghouse.net>> wrote:


Hah.  You've obviously never been involved in building a CGF
simulator (Computer Generated Forces) - absolute spaghetti code
when you have to have 4 main loops, touch 2000 objects (say 2000
tanks) every simulation frame.  Comparatively trivial if each tank
is modeled as a process or actor and you run asynchronously.


I haven't used CGF. It does sound like a mess, the way you describe it.


No... the question was whether you've ever built one, not used one.  I 
haven't either, but engineers I've worked with have - and there are good 
reasons for designing things they way they are.  At least if you're 
using a language where context switching is expensive.




But there are good architectures that won't become spaghetti code in 
these circumstances. If you pipelined 2000 tank data objects through 
four processes each instant, for example (i.e. so tanks 1-100 are in 
the last process of four while 301-400 are in the first) there would 
be some clear constraints on communication, and state could be updated 
only at transition from one instant to another.
You're speaking theoretically, of course.  The systems I'm familiar with 
are fairly highly evolved and optimized.  They just start from the 
assumption that you can't spawn a process for every object.


You claim managing 2000 asynchronous processes is trivial. I think 
you'll just find different things to complain about after you have, 
say, 2000 actors processing 16 asynchronous messages per second (4 
messages per actor * 20 Hz, minimal for your example) plus managing 
consistent views and safe updates of a shared map or environment, or 
consistent snapshots for persistence.


What makes you assume that every actor is doing anything all the time.  
A lot of them are simply sitting in one place, others are moving but not 
interacting with anything.  The major events are weapons fire events, 
which are not happening at 20hz.


The difficult part of the job, and the one that causes a shared-nothing 
approach problematic, is line-of-sight calculations - who can see whom.  
Ultimately that has to be solved.


But this is far afield from the basic point:  Someone suggested that 
people thing sequentially, or that parallelism is more complicated than 
sequential architectures.  This is a very real case where that simply is 
not the case - sequential approaches to this problem space are 
inherently more complicated than parallel ones.


Miles Fidelman

--
In theory, there is no difference between theory and practice.
In practice, there is.    Yogi Berra


___
fonc mailing list
fonc@vpri.org
http://vpri.org/mailman/listinfo/fonc

Re: [fonc] Everything You Know (about Parallel Programming) Is Wrong!: A Wild Screed about the Future

[David Barbour]

On Tue, Apr 3, 2012 at 10:47 AM, Miles Fidelman
wrote:

> Hah.  You've obviously never been involved in building a CGF simulator
> (Computer Generated Forces) - absolute spaghetti code when you have to have
> 4 main loops, touch 2000 objects (say 2000 tanks) every simulation frame.
>  Comparatively trivial if each tank is modeled as a process or actor and
> you run asynchronously.
>

I haven't used CGF. It does sound like a mess, the way you describe it.

But there are good architectures that won't become spaghetti code in these
circumstances. If you pipelined 2000 tank data objects through four
processes each instant, for example (i.e. so tanks 1-100 are in the last
process of four while 301-400 are in the first) there would be some clear
constraints on communication, and state could be updated only at transition
from one instant to another.

You claim managing 2000 asynchronous processes is trivial. I think you'll
just find different things to complain about after you have, say, 2000
actors processing 16 asynchronous messages per second (4 messages per
actor * 20 Hz, minimal for your example) plus managing consistent views and
safe updates of a shared map or environment, or consistent snapshots for
persistence.

Regards,

Dave

-- 
bringing s-words to a pen fight
___
fonc mailing list
fonc@vpri.org
http://vpri.org/mailman/listinfo/fonc

Re: [fonc] Everything You Know (about Parallel Programming) Is Wrong!: A Wild Screed about the Future

[Miles Fidelman]

David Barbour wrote:



On Tue, Apr 3, 2012 at 9:46 AM, Miles Fidelman 
mailto:mfidel...@meetinghouse.net>> wrote:



And for that matter, driving a car, playing a sport, walking and
chewing gum at the same time :-)


Would this be a Flintstones racecar?



I can think of a lot of single-threaded interfaces that put
people in a universe of pain. It isn't clear to me that
distribution is at fault there. ;)


Come to think of it, tracing flow-of-control through an
object-oriented system REALLY is a universe of pain (consider the
difference between a simulation - say a massively multiplayer game
- where each entity is modeled as an object, with one or two
threads winding their way through every object, 20 times a second;
vs. modeling each entity as a process/actor).


Control flow is a source of much implicit state and accidental 
complexity.


A step processing approach at 20Hz isn't all bad, though, since at 
least you can understand the behavior of each frame in terms of the 
current graph of objects. The only problem with it is that this 
technique doesn't scale. There are easily up to 15 orders of magnitude 
in update frequency between slow-updating and fast-updating data 
structures. Object graphs are similarly heterogeneous in many other 
dimensions - trust and security policy, for example.


Hah.  You've obviously never been involved in building a CGF simulator 
(Computer Generated Forces) - absolute spaghetti code when you have to 
have 4 main loops, touch 2000 objects (say 2000 tanks) every simulation 
frame.  Comparatively trivial if each tank is modeled as a process or 
actor and you run asynchronously.




--
In theory, there is no difference between theory and practice.
In practice, there is.    Yogi Berra


___
fonc mailing list
fonc@vpri.org
http://vpri.org/mailman/listinfo/fonc

Re: [fonc] Everything You Know (about Parallel Programming) Is Wrong!: A Wild Screed about the Future

[David Barbour]

On Tue, Apr 3, 2012 at 10:22 AM, David Barbour  wrote:

> I think the parallel programming models of the future will look more like
> Dedalus, Bloom, synchronous reactive, or concurrent constraint programming.
> Or my reactive demand programming. Dataflows, with lots of isolation for
> modularity and security. We can still model control flow where essential,
> but it isn't often essential.
>

I should add that I think these `dataflows` will mostly represent automated
relationship management according to policies. Instead of smart nodes with
dumb message-passing, we'll have dumb nodes with smart, declarative edges.

Regards,

Dave

-- 
bringing s-words to a pen fight
___
fonc mailing list
fonc@vpri.org
http://vpri.org/mailman/listinfo/fonc

Re: [fonc] Everything You Know (about Parallel Programming) Is Wrong!: A Wild Screed about the Future

[David Barbour]

On Tue, Apr 3, 2012 at 9:46 AM, Miles Fidelman
wrote:

>
> And for that matter, driving a car, playing a sport, walking and chewing
> gum at the same time :-)


Would this be a Flintstones racecar?


>
>
>> I can think of a lot of single-threaded interfaces that put people in a
>> universe of pain. It isn't clear to me that distribution is at fault there.
>> ;)
>>
>>
> Come to think of it, tracing flow-of-control through an object-oriented
> system REALLY is a universe of pain (consider the difference between a
> simulation - say a massively multiplayer game - where each entity is
> modeled as an object, with one or two threads winding their way through
> every object, 20 times a second; vs. modeling each entity as a
> process/actor).
>

Control flow is a source of much implicit state and accidental complexity.

A step processing approach at 20Hz isn't all bad, though, since at least
you can understand the behavior of each frame in terms of the current graph
of objects. The only problem with it is that this technique doesn't scale.
There are easily up to 15 orders of magnitude in update frequency between
slow-updating and fast-updating data structures. Object graphs are
similarly heterogeneous in many other dimensions - trust and security
policy, for example.

I think the parallel programming models of the future will look more like
Dedalus, Bloom, synchronous reactive, or concurrent constraint programming.
Or my reactive demand programming. Dataflows, with lots of isolation for
modularity and security. We can still model control flow where essential,
but it isn't often essential.

Regards,

Dave

-- 
bringing s-words to a pen fight
___
fonc mailing list
fonc@vpri.org
http://vpri.org/mailman/listinfo/fonc

Re: [fonc] Everything You Know (about Parallel Programming) Is Wrong!: A Wild Screed about the Future

[Miles Fidelman]

David Barbour wrote:


On Tue, Apr 3, 2012 at 8:25 AM, Eugen Leitl > wrote:


It's not just imperative programming. The superficial mode of human
cognition is sequential. This is the problem with all of mathematics
and computer science as well.


Perhaps human attention is basically sequential, as we're only able to 
focus our eyes on one point and use two hands.  But I think humans 
understand parallel behavior well enough - maintaining multiple 
relationships, for example, and predicting the behaviors of multiple 
people.


And for that matter, driving a car, playing a sport, walking and chewing 
gum at the same time :-)




If you look at MPI debuggers, it puts people into a whole other
universe of pain that just multithreading.


I can think of a lot of single-threaded interfaces that put people in 
a universe of pain. It isn't clear to me that distribution is at fault 
there. ;)




Come to think of it, tracing flow-of-control through an object-oriented 
system REALLY is a universe of pain (consider the difference between a 
simulation - say a massively multiplayer game - where each entity is 
modeled as an object, with one or two threads winding their way through 
every object, 20 times a second; vs. modeling each entity as a 
process/actor).


Cheers,

Miles

--
In theory, there is no difference between theory and practice.
In practice, there is.    Yogi Berra


___
fonc mailing list
fonc@vpri.org
http://vpri.org/mailman/listinfo/fonc

Re: [fonc] Everything You Know (about Parallel Programming) Is Wrong!: A Wild Screed about the Future

[David Barbour]

On Tue, Apr 3, 2012 at 8:25 AM, Eugen Leitl  wrote:

> It's not just imperative programming. The superficial mode of human
> cognition is sequential. This is the problem with all of mathematics
> and computer science as well.
>

Perhaps human attention is basically sequential, as we're only able to
focus our eyes on one point and use two hands.  But I think humans
understand parallel behavior well enough - maintaining multiple
relationships, for example, and predicting the behaviors of multiple people.


>
> If you look at MPI debuggers, it puts people into a whole other
> universe of pain that just multithreading.
>

I can think of a lot of single-threaded interfaces that put people in a
universe of pain. It isn't clear to me that distribution is at fault there.
;)

In any case, message passing and event models are still clinging tightly to
their imperative heritage.


>
> > Dataflows and pipelines can be parallelized without issue and remain
> > deterministic. If we push more of the parallelism to the code, the
> hardware
> > can also be less complex - i.e. less architecture to hide latency for
> > memory access.
>
> Global memory doesn't scale in a relativistic universe. Ditto cache
> coherence for already reasonable small number of caches.
>
> So, we don't really have a choice other to stop worrying, and learn
> to love parallelism.
>

True, but we can also make it a lot less complex.

Regards,

Dave

-- 
bringing s-words to a pen fight
___
fonc mailing list
fonc@vpri.org
http://vpri.org/mailman/listinfo/fonc

Re: [fonc] Everything You Know (about Parallel Programming) Is Wrong!: A Wild Screed about the Future

[Miles Fidelman]

Eugen Leitl wrote:

On Tue, Apr 03, 2012 at 08:19:53AM -0700, David Barbour wrote:


That said, I also disagree with Tom, there: design complexity doesn't need
to increase with parallelism. The tradeoff between complexity vs.
parallelism is more an artifact of sticking with imperative programming.

It's not just imperative programming. The superficial mode of human
cognition is sequential. This is the problem with all of mathematics
and computer science as well.

If you look at MPI debuggers, it puts people into a whole other
universe of pain that just multithreading.


Sort of depends on how you architect things.  Email is one huge parallel 
system.  Nobody even thinks of debugging the global flow of email.  It's 
a probabilistic approach.



Dataflows and pipelines can be parallelized without issue and remain
deterministic. If we push more of the parallelism to the code, the hardware
can also be less complex - i.e. less architecture to hide latency for
memory access.

Global memory doesn't scale in a relativistic universe. Ditto cache
coherence for already reasonable small number of caches.

So, we don't really have a choice other to stop worrying, and learn
to love parallelism.


True that. :-)

--
In theory, there is no difference between theory and practice.
In practice, there is.    Yogi Berra


___
fonc mailing list
fonc@vpri.org
http://vpri.org/mailman/listinfo/fonc

Re: [fonc] Everything You Know (about Parallel Programming) Is Wrong!: A Wild Screed about the Future

[Eugen Leitl]

On Tue, Apr 03, 2012 at 08:19:53AM -0700, David Barbour wrote:

> That said, I also disagree with Tom, there: design complexity doesn't need
> to increase with parallelism. The tradeoff between complexity vs.
> parallelism is more an artifact of sticking with imperative programming.

It's not just imperative programming. The superficial mode of human 
cognition is sequential. This is the problem with all of mathematics 
and computer science as well. 

If you look at MPI debuggers, it puts people into a whole other
universe of pain that just multithreading.

> Dataflows and pipelines can be parallelized without issue and remain
> deterministic. If we push more of the parallelism to the code, the hardware
> can also be less complex - i.e. less architecture to hide latency for
> memory access.

Global memory doesn't scale in a relativistic universe. Ditto cache
coherence for already reasonable small number of caches.

So, we don't really have a choice other to stop worrying, and learn
to love parallelism.
___
fonc mailing list
fonc@vpri.org
http://vpri.org/mailman/listinfo/fonc

Re: [fonc] Everything You Know (about Parallel Programming) Is Wrong!: A Wild Screed about the Future

[David Barbour]

On Tue, Apr 3, 2012 at 8:02 AM, Miles Fidelman
wrote:

> On Tue, Apr 3, 2012 at 7:23 AM, Tom Novelli  wrote:
>
>> Even if there does turn out to be a simple and general way to do parallel
>>
>>> programming, there'll always be tradeoffs weighing against it - energy
>> usage
>> and design complexity, to name two obvious ones.
>>
> To design complexity: you have to be kidding.  For huge classes of
> problems - anything that's remotely transactional or event driven,
> simulation, gaming come to mind immediately - it's far easier to
> conceptualize as spawning a process than trying to serialize things.  The
> stumbling block has always been context switching overhead.  That problem
> goes away as your hardware becomes massively parallel.
>
>
Important complexity issues of traditional approaches to parallel code
include verification, maintenance, regression testing, deadlock,
starvation, priority inversion. A good complexity metric is the number of
observably distinct failure modes.

Context switching overhead is a moderate performance concern, not a
complexity concern.

Conceptualizing task parallelism isn't enough. You need a way to
effectively control the resulting program.

That said, I also disagree with Tom, there: design complexity doesn't need
to increase with parallelism. The tradeoff between complexity vs.
parallelism is more an artifact of sticking with imperative programming.
Dataflows and pipelines can be parallelized without issue and remain
deterministic. If we push more of the parallelism to the code, the hardware
can also be less complex - i.e. less architecture to hide latency for
memory access.

Regards,

Dave

-- 
bringing s-words to a pen fight
___
fonc mailing list
fonc@vpri.org
http://vpri.org/mailman/listinfo/fonc

Re: [fonc] Everything You Know (about Parallel Programming) Is Wrong!: A Wild Screed about the Future

[Miles Fidelman]

Steven Robertson wrote:

On Tue, Apr 3, 2012 at 7:23 AM, Tom Novelli  wrote:

Even if there does turn out to be a simple and general way to do parallel
programming, there'll always be tradeoffs weighing against it - energy usage
and design complexity, to name two obvious ones.

To design complexity: you have to be kidding.  For huge classes of problems - 
anything that's remotely transactional or event driven, simulation, gaming come 
to mind immediately - it's far easier to conceptualize as spawning a process 
than trying to serialize things.  The stumbling block has always been context 
switching overhead.  That problem goes away as your hardware becomes massively 
parallel.

Miles Fidelman



--
In theory, there is no difference between theory and practice.
In practice, there is.    Yogi Berra


___
fonc mailing list
fonc@vpri.org
http://vpri.org/mailman/listinfo/fonc

Re: [fonc] Everything You Know (about Parallel Programming) Is Wrong!: A Wild Screed about the Future

[Steven Robertson]

On Tue, Apr 3, 2012 at 7:23 AM, Tom Novelli  wrote:
> Even if there does turn out to be a simple and general way to do parallel
> programming, there'll always be tradeoffs weighing against it - energy usage
> and design complexity, to name two obvious ones.

Not necessarily.

As to the former, not every FLOP is equally efficient, since silicon
transistor power draw doesn't scale linearly with clock speed.
Parallel designs tend to be more efficient for the same effective
speed as single-core clockspeed ramping. This trend may continue to
scale for a while, such that hundred-core designs (with the right
approaches to concurrency) are so much more efficient than quad-core
chips that, say, phone manufacturers will be compelled to embrace that
approach.

For design complexity, at the hardware level this is something of a
business advantage, since processor companies need to keep selling new
chips somehow. With enough effort in developing software concepts and
tools to handle concurrency, there's no reason that concurrent
programming of the future need be more challenging than serial
programming is today. This doesn't mean that design complexity isn't a
factor, but I think it does mean that it won't always be a very big
one.

Steve
___
fonc mailing list
fonc@vpri.org
http://vpri.org/mailman/listinfo/fonc

Re: [fonc] Everything You Know (about Parallel Programming) Is Wrong!: A Wild Screed about the Future

[Tom Novelli]

Is Ungar focusing on general-purpose computing or just high-performance
computing?

Unless he's strictly talking about HPC, he could be way off the mark.  For
the past 5-10 years there's been a general assumption that massive
parallelism will be necessary as CPU speeds max out.  But then there's talk
that something like graphene could take us into the terahertz range.  And
isn't 4 ghz enough?  My first computer was 4 mhz.  Bloatware still pushes
hardware's limits, but in my own code, performance just isn't a big
obstacle anymore.

Even if there does turn out to be a simple and general way to do parallel
programming, there'll always be tradeoffs weighing against it - energy
usage and design complexity, to name two obvious ones.

BTW, good point about the problem of hyper-specialization in CS academia.

-Tom


On Thu, Mar 29, 2012 at 10:12 PM, David Barbour  wrote:

>
>
> On Thu, Mar 29, 2012 at 12:29 PM, Max Orhai  wrote:
>
>> Probability is highly applicable to (bounded) nondeterminism, but I get
>> the impression that most CS theorists don't tend to learn much about it,
>> and I know for sure that it gets extremely short shrift in the applied CS
>> curriculum at my school.
>>
>
> How would you suggest applying probability to non-determinism? What
> benefit would it provide?
>
> I've seen some cases where probability is applied to non-determinism, e.g.
> concurrent-constraint probability models. But the benefits it offers seem
> marginal.
>
>
>
>>
>> Dave Ungar loves being deliberately provocative, but I really don't
>> understand why he's so attached to the (obviously unscalable) shared memory
>> imperative programming model... except, perhaps, he thinks that's the only
>> model the great unwashed masses of industry coders can handle. If so, I
>> sure hope he's wrong.
>>
>
> I also hope he's wrong. After all, the unwashed masses barely handle even
> that. Even if we exclude concurrency, most bugs and complexity involve
> state.
>
>
>>
>> But, lets face it, after decades of real-world deployment, Erlang is
>> still considered an exotic language, and hardly anybody outside the ivory
>> towers has even heard of Kahn nets, FRP, CALM, etc. These don't get taught
>> in the undergrad CS curriculum either.
>>
>
> Most professors don't know them either. Doctorates in CS are generally for
> a specialized contribution, not broad knowledge. It's unfortunate.
>
>
>>
>> Programmers, like everybody else, only get to choose their problems
>> inasmuch as they are aware of the choices.
>>
>
> And the only way to make them aware is to provide a killer app to extend...
>
> Regards,
>
> Dave
>
> --
> bringing s-words to a pen fight
>
> ___
> fonc mailing list
> fonc@vpri.org
> http://vpri.org/mailman/listinfo/fonc
>
>
___
fonc mailing list
fonc@vpri.org
http://vpri.org/mailman/listinfo/fonc