Databases Reference
In-Depth Information
Figure 6: Object Allocation Table and References to Remote Objects
Object count balancing and locality preference enforcement can be implemented
without significant space/time overhead
12)
.
For external reference reduction, however, a simple implementation based on
“most-recently-accessed PE” is not effective
12)
. Therefore, another scheme has been
proposed which identifies the relocation candidates and the destinations more
precisely
8,
11)
.
In order to find the relocation candidate objects more precisely, four counters
are introduced for each object. If the relocation timing arrives, the following formula
selects the candidates for relocation:
where
R
to_inner
, R
from_inner
, R
to_ext
and
R
from_ext
are the references to the same PE, the
references the references from the same PE, the references to the other PEs, and
the references from the other PE, respectively.
For the problem of finding the destination PE,
n
records (
n
is a constant, possibly
smaller than the number of PEs) is introduced to count the external references
more precisely. Each record has PE ID and the reference counts from the PE. Let
the
i
-th record be record
(i)
(1
n
). The revised method selects the PE having the
largest count as the relocation destination.
The counts must be initialized to zero. The revised algorithm for updating the
counters, to be initiated each time a reference is encountered, is as follows.
1.
≤
i
≤
Look up the PE ID recorded in record(1) and increment the counter if the
PE ID matches the ID of the referrer. If not, go to Step 2.
2.
For each record
(i)
(2
n
), repeat the following operation. If the PE ID
matches the ID of the referrer, increment the counter. If the counter for
record
(i)
becomes greater than that of record(
i
-1), replace the record with
record(
i
-1). Repeat this step until the matching record is found or until
i
=
n
.
≤
i
≤
