04-05-2012, 03:27 PM
Active Correlation Tracking
10[1].1.1.24.9686.pdf (Size: 229.48 KB / Downloads: 42)
Introduction
This paper describes active correlation tracking, a mechanism
for tracking data sharing between threads, and its implementation
in CVM [1], a software distributed shared
memory (DSM) system. DSMs are software systems that
provide the abstraction of shared memory to threads of a
parallel application running on networks of workstations.
Consistency is maintained by using virtual memory techniques
to trap accesses to shared data and ensure consistency.
Information on the type and degree of data sharing is
useful to such systems because the majority of network
communication is caused by the underlying consistency
system. When a pair of threads located on distinct machines
(nodes) both access data on the same shared page,
network communication can only be avoided by moving at
least one of the threads so that they are located on the same
node.
Thread correlations and cut costs
The cut cost of a given mapping of threads to nodes is the
pairwise sum of all thread correlations, i.e. a sum with n2
terms, where n is the number of threads. This sum represents
a count of the pages shared by threads on distinct
machines.
We hypothesize that cut costs are good indicators of
data traffic for running applications. We tested this hypothesis
experimentally by measuring the correlation between
cut costs and remote misses of a series of randomly
generated thread configurations.
Variation with number of threads
The columns in Table 3 correspond to 32, 48, and 64
threads, respectively. Somewhat surprisingly, they show
that sharing characteristics can significantly vary with the
number of threads.
The overall structure of the correlation maps for SOR,
Barnes, and Water are little affected by changing the number
of threads. This could have been predicted from a cursory
examination of application structure. Threads in SOR,
for example, share only single rows of data between pairs
of adjacent threads. Hence, changing the number of threads
does not affect the structure of the map. Water and Barnes
are more complex, but still easily explained.
Active correlation tracking
Network ping-pongs can be avoided by obtaining additional
information about correlations between local threads
before any thread migration takes place. We obtain this
information through an active correlation-tracking phase,
which iteratively obtains access information for each local
thread. The correlation-tracking phase spans a single iteration
of each of the applications. The algorithm uses two
data structures on each node: per-page correlation bits, and
per-thread access bitmaps: