[lcr95.abs]

Dinda, P., and O'Hallaron, D. "The Performance Impact of Address
Relation Caching". In Proc. of the Third Workshop on Languages,
Compilers, and Run-Time Environments for Scalable Computers. Troy, NY,
May 1995.

Abstract: An important portion of end--to--end latency in data
transfer is spent in address computation, determining a relation
between sender and receiver addresses.  In deposit model
communication, this computation happens only on the sender and some of
its results are embedded in the message.  Conventionally, address
computation takes place on--line, as the message is assembled.  If the
amount of address computation is significant, and the communication is
repeated, it may make sense to remove address computation from the
critical path by caching its results.  However, assembling a message
using the cache uses additional memory bandwidth.

We present a fine grain analytic model for simple address relation
caching in deposit model communication.  The model predicts how many
times a communication must be repeated in order for the average
end--to--end latency of an implementation which caches to break even
with that of an implementation which doesn't cache.  The model also
predicts speedup and those regimes where a caching implementation
never breaks even.  The model shows that the effectiveness of caching
depends on CPU speed, memory bandwidth and the complexity of the
address computation.  We verify the model on the iWarp and the Paragon
and find that, for both machines, caching can improve performance even
when address computation is quite simple (one instruction per data
word on the iWarp and 16 instructions per data word on the Paragon.)

To show the practical benefit of address relation caching, we examine
the performance of an HPF distributed array communication library that
can be configured to use caching.  In some cases, caching can double
the performance of the library.  Finally, we discuss other benefits to
caching and several open issues.