improve programmability and performance.
Each chunk executes on the processor atomically and in isolation.
Atomic execution means that none of
the chunk’s actions are made visible
to the rest of the system (processors or
main memory) until the chunk completes and commits. Execution in isolation means that if the chunk reads a
location and (before it commits) a second chunk in another processor that
has written to the location commits,
then the local chunk is squashed and
To execute chunks atomically and
in isolation inexpensively, the Bulk
Multicore introduces hardware address signatures.
3 A signature is a
register of ≈ 1,024 bits that accumulates hash-encoded addresses. Figure
1 outlines a simple way to generate a
signature (see the sidebar “Signatures
and Signature Operations in Hardware” for a deeper discussion). A signature, therefore, represents a set of
Figure 1 in the main text shows a simple implementation of a signature. the bits of an
incoming address go through a fixed permutation to reduce collisions and are then
separated in bit-fields Ci. each field is decoded and accumulated into a bit-field Vj in the
signature. Much more sophisticated implementations are also possible.
A module called the Bulk Disambiguation Module contains several signature
registers and simple functional units that operate efficiently on signatures. these
functional units are invisible to the instruction-set architecture. note that, given a
signature, we can recover only a superset of the addresses originally encoded into the
signature. Consequently, the operations on signatures produce conservative results.
the figure here outlines five signature functional units: intersection, union, test
for null signature, test for address membership, and decoding (δ). intersection finds
the addresses common to two signatures by performing a bit-wise AnD of the two
signatures. the resulting signature is empty if, as shown in the figure, any of its bit-
fields contains all zeros. union finds all addresses present in at least one signature
through a bit-wise or of the two signatures. testing whether an address a is present
(conservatively) in a signature involves encoding a into a signature, intersecting the
latter with the original signature and then testing the result for a null signature.
Decoding (δ) a signature determines which cache sets can contain addresses
belonging to the signature. the set bitmask produced by this operation is then passed
to a finite-state machine that successively reads individual lines from the sets in the
bitmask and checks for membership to the signature. this process is used to identify
and invalidate all the addresses in a signature that are present in the cache.
overall, the support described here enables low-overhead operations on sets of
Signatures and Signature
Operations in Hardware
operations on signatures.
S1 Ç S2
S1 È S2
S = Ø
a Î S
In the Bulk Multicore, the hardware automatically accumulates the
addresses read and written by a chunk
into a read (R) and a write (W) signature, respectively. These signatures
are kept in a module in the cache hierarchy. This module also includes
simple functional units that operate
on signatures, performing such operations as signature intersection (to
find the addresses common to two
signatures) and address membership
test (to find out whether an address
belongs to a signature), as detailed in
Atomic chunk execution is supported by buffering the state generated by the chunk in the L1 cache.
No update is propagated outside the
cache while the chunk is executing.
When the chunk completes or when a
dirty cache line with address in the W
signature must be displaced from the
cache, the hardware proceeds to commit the chunk. A successful commit
involves sending the chunk’s W signature to the subset of sharer processors indicated by the directory2 and
clearing the local R and W signatures.
The latter operation erases any record
of the updates made by the chunk,
though the written lines remain dirty
in the cache.
The W signature carries enough
information to both invalidate stale
lines from the other coherent caches
(using the δ signature operation on W,
as discussed in the sidebar) and enforce that all other processors execute
their chunks in isolation. Specifically,
to enforce that a processor executes a
chunk in isolation when the processor
receives an incoming signature Winc,
its hardware intersects Winc against
the local Rloc and Wloc signatures. If any
of the two intersections is not null, it
means (conservatively) that the local
chunk has accessed a data element
written by the committing chunk.
Consequently, the local chunk is
squashed and then restarted.
Figure 2 outlines atomic and isolated execution. Thread 0 executes
a chunk that writes variables B and
C, and no invalidations are sent out.
Signature W0 receives the hashed addresses of B and C. At the same time,
1 issues reads for B and C,
which (by construction) load the non-