Re: Larrabee delayed: anyone know what's happening?

nmm1@xxxxxxxxx wrote:
In article <4B399C3B.2050207@xxxxxxxxxxxxxxx>,
Andy \"Krazy\" Glew <ag-news@xxxxxxxxxxxxxxx> wrote:
That doesn't help significantly. For the real benefit, you need to
be able to ensure that objects that are accessed in separate threads
can be separated by the implementation to any degree that it needs.
That's a problem.
How can you do this with linked datastructures?

E.g. the flavor of sparse array that has cells (row,col,data,ptr_to_next_in_row,ptr_to_next_in_col)
with linked lists on both dimensions.
Sometimes parallelized by row, sometimes by columns;
sometimes both at the same time.

Just as for arrays. You copy in and copy back, when and as necessary.
Yes, it costs, which is why most Fortran compilers use copy-in/copy-out
for arrays only when essential.

My point is that the language must be such as to ALLOW the compiler
to do that. Fortran, Python etc. by and large do. C, C++ and Java,
by and large don't.

Copy in/out helps, but generalize:

Some funky linked data structure where you can't tell a priori what subsections there are.

Or, heck, an N-dimensional array, where you sometimes want row access, sometimes columns, sometimes any of the diagonals, sometimes sub-matrices - where, in general, you can't tell what subset of the data structure is being manipulated. And where there is not some hierarchy that is natural for locking or other mutex.

Copy in/out helps. Particularly for dense arrays - because the parallel threads are not deallocating structure nodes, but are just changing values. You may get inconsistent values when you copy back in - values that are not consistent with their surrounding values - but the dense array isn't broken.

Whereas with a subset of linked datastructure that does not have a single dominator, you can't necessarily copy back in a changed datastructure, with nodes that have been added or deleted.

Herlihy's non-blocking lock free algorithms using compare-and-swap depend on there being a single pointer that dominates the data structure you are changing.

Failing that, you need either transaction - K-way compare and swap, or full transactions.

Or you need locks.

If you are operating on something like an irregular but static mesh, okay, you may be able to copy in/out. But if the mesh is evolving as objects move.

Anyway, yes, copy in/out helps. But it is not the final answer. The real problem in so much of this is that we have memory. Data structures that are operated on in place. And, no matter what advocates of data flow, logic programming, applicative or functional languages say, I don't think that we are going to do away with them.
.

Relevant Pages

  • Re: Latest version of glossary
    ... such as XML, refer to the use of the term within that "namespace" using ... An n-dimensional data structure, S, is one where each element of S ... Whenever mathematics is applied to anything, ... associative array (while trying to do something in JavaScript, ...
    (comp.databases.theory)
  • Re: combining hashes
    ... >>> A hash is an ordered data structure indexed by a specific key. ... My mind's eye sees it differently. ... c> An array is ...
    (comp.lang.perl.misc)
  • Re: how to read dynamic data structures from the kernel (was Re: reading routing table)
    ... could give us individual entries of the data structure on each call, ... steps for any given kernel subsystem -- we have data structures, ... bumping the references and adding pointers to the array. ... the global locks, and proceed lock, externalize, unlock, and copyout each ...
    (freebsd-net)
  • Re: Looking for advise on storring a complex array
    ... hashes etc. ... The trick is that I would not like to have to read back the entire array ... but you should look into using a database with a few ... This *really* depends on your data structure. ...
    (perl.beginners)