I am not a computer scientist and not experienced in reading algorithm
books so I can only speculate.
An exclusive read and write algorithm is implementable in a distributed
memory computer without any communication maybe? That is, if you can prove
this property you may need a communication step before the algortihm to
get the data on the right node and to get it back afterwards, but you need no
communication inside the algorithm. On a shared memory architecture with
non-uniform memory access and if the access pattern agrees with the
memory distribution there would also be a (slight) performance advantage.
Unfortunately, an important measure is number of cache misses due to cache
line invalidations from remote processors, and that is much harder to
establish and is a function not only of the algorithm and its implementation,
but also of the intended computer platform.
Speculation:
If the algorithm is EREW then it is theoretically possible to implement the
algorithm without false sharing in SMPs and without communication in
distributed memeory machines. However, the implementation will need to
take the underlying hardware and memory lay-out in account. So the count
is an iportant aspect of the algorithm, poor performance can then be
blaimed on the implementor instead of the algorithm itself.
Coming from a different field of science I'd imagine that a computer
scientists doing research in algorithms publishes an algorithm and makes
statements about its properties (such as EREW, concurrent reads etc).
And you accompanies your publication with experiements where the algortihm
is implemented on different computers and you present graphs over
L2-cache misses, cache line invalidations etc measured by the performance
counters on the machines. (And the rest of the paper is spent in
panic trying to explain the differences :-). At least that is how
papers in the mechanics field traditionally are supposed to be (but they
usually are not following this ideal fully)
/Nils
|