Design and Evaluation of a Switch Cache Architecture for CC-NUMA Multiprocessors.
AbstractCache coherent nonuniform memory access (CC-NUMA) multiprocessors provide a scalable design for shared memory. But, they continue to suffer from large remote memory access latencies due to comparatively slow memory technology and large data transfer latencies in the interconnection network. In this paper, we propose a novel hardware caching technique, called switch cache, to improve the remote memory access performance of CC-NUMA multiprocessors. The main idea is to implement small fast caches in crossbar switches of the interconnect medium to capture and store shared data as they flow from the memory module to the requesting processor. This stored data acts as a cache for subsequent requests, thus reducing the need for remote memory accesses tremendously. The implementation of a cache in a crossbar switch needs to be efficient and robust, yet flexible for changes in the caching protocol. The design and implementation details of a CAche Embedded Switch ARchitecture, CAESAR, using wormhole routing with virtual channels is presented. We explore the design space of switch caches by modeling CAESAR in a detailed execution driven simulator and analyze the performance benefits. Our results show that the CAESAR switch cache is capable of improving the performance of CC-NUMA multiprocessors by up to 45 percent reduction in remote memory accesses for some applications. By serving remote read requests at various stages in the interconnect, we observe improvements in execution time as high as 20 percent for these applications. We conclude that switch caches provide a cost-effective solution for designing high performance CC-NUMA multiprocessors.
Introduction
To alleviate the problem of high memory access latencies, shared memory multiprocessors employ
processors with small fast on-chip caches and additionally larger off-chip caches. Symmetric multiprocessor
(SMP) systems are usually built using a shared global bus. However the contention on
the bus and memory heavily constrains the number of processors that can be connected to the bus.
To build high performance systems that are scalable, several current systems [1, 10, 12, 13] employ
the cache coherent non-uniform memory access (CC-NUMA) architecture. In such a system, the
shared memory is distributed among all the nodes in the system to provide a closer local memory
and several remote memories. While local memory access latencies can be tolerated, the remote
memory accesses generated during the execution can bring down the performance of applications
drastically.
To reduce the impact of remote memory access latencies, researchers have proposed improved
caching strategies [14, 18, 27] within each cluster of the multiprocessor. These caching techniques
are primarily based on data sharing among multiple processors within the same cluster. Nayfeh
et al. [18] explore the use of shared L2 caches to benefit from the shared working set between the
processors within a cluster. Another alternative is the use of network caches or remote data caches
[14, 27]. Network caches reduce the remote access penalty by serving capacity misses of L2 caches
and by providing an additional layer of shared cache to processors within a cluster. The HP Exemplar
[1] implements the network cache as a configurable partition of the local memory. Sequent's
NUMA-Q [13] dedicates a 32MB DRAM memory for the network cache. The DASH multiprocessor
[12] has provision for a network cache called the remote access cache. A recent proposal by Moga et
al.[14] explores the use of small SRAM (instead of DRAM) network caches integrated with a page
cache. The use of 32KB SRAM chips reduces the access latency of network caches tremendously.
Our goal is to reduce remote memory access latencies by implementing a global shared cache abstraction
central to all processors in the CC-NUMA system. We observe that network caches
provide such an abstraction limited to the processors within a cluster. We explore the implementation
issues and performance benefits of a multi-level caching scheme that can be incorporated
into current CC-NUMA systems. By embedding a small fast SRAM cache within each switch in
the interconnection network, called switch cache, we capture shared data as it flows through the
interconnect and provide it to future accesses from processors that re-use this data. Such a scheme
can be considered as a multi-level caching scheme, but without inclusion property. Our studies on
application behavior indicate that there is enough spatial and temporal locality between requests
from processors to benefit from small switch caches. Recently, a study by Mohapatra et al. [15]
used synthetic workloads and showed that increasing the buffer size in a crossbar switch beyond a
certain value does not have much impact on network performance. Our application-based study [4]
confirms that this observation holds true for the CC-NUMA environment running several scientific
applications. Thus we think that the large amount of buffers in current switches, such as SPIDER
[7], is an overkill. A better utilization of these buffers can be accomplished by organizing them as
a switch cache.
There are several issues to be considered while designing such a caching technique. These include
cache design issues such as technology & organization, cache coherence issues, switch design issues
such as arbitration, and message flow control issues such as appropriate routing strategy, message
layout etc. The first issue is to design and analyze a cache organization that is large enough to hold
the reusable data, yet fast enough to operate during the time a request passes through the switch.
The second issue involves modifying the directory-based cache protocol to handle an additional
caching layer at the switching elements, so that all the cache blocks in the system are properly
invalidated on a write. The third issue is to design buffers and arbitration in the switch which
will guarantee certain cache actions within the switch delay period. For example, when a read
request travels through a switch cache, it must not incur additional delays. Even in the case of
a switch cache hit, the request must pass on to the home node to update the directory, but not
generate a memory read operation. The final issue deals with message header design to enable
request encoding, network routing etc.
The contribution of this paper is the detailed design and performance evaluation of a switch cache
interconnect employing CAESAR, a CAche Embedded Switch ARchitecture. The CAESAR switch
cache is made up of a small SRAM cache operating at the same speed as a wormhole routed cross-bar
switch with virtual channels. The switch design is optimized to maintain crossbar bandwidth
and throughput, while at the same time providing sufficient switch cache throughput and improved
remote access performance. The performance evaluation of the switch cache interconnect is conducted
using six scientific applications. We present several sensitivity studies to cover the entire
design space and to identify the important parameters. Our experiments show that switch caches
offer a great potential for use in future CC-NUMA interconnects for some of these applications.
The rest of the paper is organized as follows. Section 2 provides a background on the remote access
characteristics of several applications in a CC-NUMA environment and builds the motivation behind
our proposed global caching approach. The switch cache framework and the caching protocol are
presented in Section 3. Section 4 covers the design and implementation of the crossbar switch cache
architecture called CAESAR. Performance benefits of the switch cache framework are evaluated
and analyzed in great detail in Section 5. Sensitivity studies over various design parameters are
also presented in Section 5. Finally, Section 6 summarizes and concludes the paper.
Memory
Interconnection Network
Memory
Network Interface/Router
Network Interface/Router
Remote
Memory
Node X's

Figure

1: CC-NUMA system & memory hierarchy
Application Characteristics and Motivation
Several current distributed shared memory multiprocessors have adopted the CC-NUMA architecture
since it provides transparent access to data. Figure 1 shows the disparities in proximity and
access time in the CC-NUMA memory hierarchy of such systems. A load or store issued by processor
X can be served in a few cycles upon L1 or L2 cache hits, in less than a hundred cycles for
local memory access or incurs few hundreds of cycles due to a remote memory access. While the
latency for stores to the memory (write transactions) can be hidden by the use of weak consistency
models, the stall time due to loads (read transactions) to memory can severely degrade application
performance.
2.1 Global Cache Benefits: A Trace Analysis
To reduce the impact of remote read transactions, we would like to exploit the locality in sharing
patterns between the processors. Figure 2 plots the read sharing pattern for six applications with
processors using a cache line size of 32 bytes. The six applications used in this evaluation are the
Floyd-Warshall's Algorithm (FWA), Gaussian Elimination (GAUSS), Gram-Schmidt (GS), Matrix
Multiplication (MM), Successive Over Relaxation (SOR) and the Fast Fourier Transform (FFT).
The x-axis represents the number of sharing processors (X) while the y-axis denotes the number of
accesses to blocks shared by X number of processors. From the figure, we observe that for four out
of the six applications (FWA, GAUSS, GS, MM), multiple processors read the same block between
two consecutive writes to that block. These shared reads form a major portion (35 to 80%) of the
application's read misses. To take advantage of such read-sharing patterns across processors, we
(a) FWA (b) SOR (c) GAUSS
(d) GS (e) FFT (f) MM

Figure

2: Application read sharing characteristics
introduce the concept of an ideal global cache that is centrally accessible to all processors. When
the first request is served at the memory, the data sent back in the reply message is stored in a
global cache. Since the cache is accessible by all processors, subsequent requests to the data item
can be satisfied by the global cache at low latencies. There are two questions that arise here:
ffl What is the time lag between two accesses from different processors to the same block? We define this
as temporal read sharing locality between the processors, somewhat equivalent to temporal locality
in a uniprocessor system. The question raised here particularly relates to the size and organization
of the global cache. In general, it would translate to: the longer the time lag, the bigger the size of
the required global cache.
ffl Given that a block can be held in a central location, how many requests can be satisfied by this
cached block? We call this term attainable read sharing to estimate the performance improvement
by employing a global cache. Again, this metric will give an indication of the required size for the
global cache.
To answer these questions, we instrumented a simulator to generate an execution trace with
information regarding each cache miss. We then fed these traces through a trace analysis tool,
Sharing Identifier and Locality Analyzer. In order to evaluate the potential of a global
QWHU#DUULYDO#7LPH#SF\FOHV#
(a) FWA (b) GS (c) GAUSS
(d) SOR (e) FFT (f) MM

Figure

3: The temporal locality of shared accesses
cache, SILA generates two different sets of data: temporal read shared locality (Figure 3), and
attainable sharing (Figure 4). The data sets can be interpreted as follows.
Temporal Read Sharing Locality: Figure 3 depicts the temporal read sharing locality as a
function of different block sizes. A point fX,Yg from this data set indicates that Y is the probability
that two read transactions (from different processors) to the same block occur within a time distance
of X or lower. (i.e. is the average inter-arrival time between two consecutive
read requests to the same block). As seen in the figure, most applications have an inherent temporal
re-use of the cached block by other processors. The inter-arrival time between two consecutive
shared read transactions from different processors to the same block is found to be less than 500
processor cycles (pcycles) for 60-80% of the shared read transactions for all applications. Ideally,
this indicates a potential for atleast one extra request to be satisfied per globally cached block.
Attainable Read Sharing: Figure 4 explores this probability of multiple requests satisfied by
the global caching technique termed as attainable sharing degree. A point fX,Yg in this data set
indicates that if each block can be held for X cycles in the global cache, the average number of
subsequent requests per block that can be served is Y . The figure depicts the attainable read
sharing degree for each application based on the residence time for the block in the global cache.
The residence time of a cache block is defined as the amount of time the block is held in the cache
before it is replaced or invalidated. While invalidations cannot be avoided, note that the residence
time directly relates to several cache design issues such as cache size, block size and associativity.
QWHU#DUULYDO#7LPH#SF\FOHV#
(a) FWA (b) GS (c) GAUSS
(d) SOR (e) FFT (f) MM

Figure

4: The attainable sharing degree
From

Figure

2 we observed that FWA, GS and GAUSS have high read sharing degrees close to
the number of processors in the system (in this case, 16 processors). However, it is found that
the attainable sharing degree varies according to the temporal locality of each application. While
GAUSS can attain a sharing degree of 10 in the global cache with a residence time of 2000 processor
cycles, GS requires that the residence time be 5000 and FWA requires that this time be 7000. The
MM application has a sharing degree of approximately four to five, whereas the attainable sharing
degree is much lower. SOR and FFT are not of much interest since they have a very low percentage
(1-2%) of shared block accesses (see Figure 2).
2.2 The Interconnect as a Global Cache
In section 2.1, we identified the need for global caching to improve the remote access performance
of CC-NUMA systems. In this section, we explore the possible use of the interconnect medium as
a central caching location:
ffl What makes the interconnect medium a suitable candidate for central caching?
Which interconnect topology is beneficial for incorporating a central caching scheme?
Communication in a shared memory system occurs in transactions that consist of requests and
replies. The requests and replies traverse from one node to another through the network. The
Node A
Node C
Interconnect
Overlapping
Path
Caching
Potential

Figure

5: The caching potential of the interconnect medium
interconnection network becomes the only global yet distributed medium in the entire system that
can keep track of all the transactions that occur between all nodes. A global sharing framework
can efficiently employ the network elements for coherent caching of data. The potential for such
a network caching strategy is illustrated in Figure 5. The path of two read transactions to the
same memory module that emerge from different processors overlap at some point in the network.
The common elements in the network can act as small caches for replies from memory. A later
request to the recently accessed block X can potentially find the block cached in the common
routing element (illustrated by a shaded circle). The benefit of such a scheme is two-fold. From
the processor point of view, the read request gets serviced at a latency much lower than the remote
memory access latency. Secondly, the memory is relieved of servicing the requests that hit in the
global interconnect cache, thus improving the access times of other requests that are sent to the
same memory module.
From the example, we observe that incorporating such schemes in the interconnect requires a significant
amount of path overlap between processor to memory requests and that replies follow the
same path as requests in order to provide an intersection. The routing and flow of requests and
replies depends entirely upon the topology of the interconnect. The ideal topology for such a system
is the global bus. However, the global bus is not a scalable medium and bus contention severely
affects the performance when the number of processors increases beyond a certain threshold. Con-
sequently, multiple bus hierarchies and fat-tree structures have been considered effective solutions
to the scalability problem. The tree structure provides the next best alternative to hierarchical
caching schemes.
3 The Switch Cache Framework
In this section, we present a new hardware realization of the ideal global caching solution for
improving the remote access performance of shared memory multiprocessors.
3.1 The Switch Cache Interconnect
Network topology plays an important role in determining the paths from a source to a destination in
the system. Tree-based networks like the fat tree [11], the heirarchical bus network [23, 3] and the
multistage interconnection network (MIN) [17] provide hierarchical topologies suitable for global
caching. In addition, the MIN is highly scalable and it provides a bisection bandwidth that scales
linearly with the number of nodes in the system. These features of the MIN make it very attractive as
scalable high performance interconnects for commercial systems. Existing systems such as Butterfly
[2], CM-5 [11] and IBM SP2 [21] employ a bidirectional MIN. The Illinois Cedar multiprocessor [22]
employs two separate uni-directional MINs (one for requests and one for replies). In this paper, the
switch cache interconnect is a bidirectional MIN to take advantage of the inherent tree structure.
Note, however, that logical trees can also be embedded on other popular direct networks like the
mesh and the hypercube [10, 12].
The baseline topology of the 16-node bi-directional MIN (BMIN) is shown in Figure 6(a). In general,
an N-node system using a BMIN comprises of N=k switching elements (a 2k \Theta 2k crossbar) in each of
the log k N stages connected by bidirectional links. We chose wormhole routing with virtual channels
as the switching technique because it is prevalent in current systems such as the SGI Origin[10].
In a shared memory system, communication between nodes is accomplished via read/write transactions
and coherence requests/acknowledgments. The read/write requests and coherence replies
from the processor to the memory use forward links to traverse through the switches. Similarly,
read/write replies with data and coherence requests from memory to the processor traverse the
backward path, as shown in bold in Figure 6(a). Separating the paths enables separate resources
and reduces the possibility of deadlocks in the network. At the same time, routing them through
the same switches provides identical paths for requests and replies for a processor-memory pair
that is essential to develop a switch cache hierarchy. The BMIN tree structure that enables this
hierarchy is shown in Figure 6(b).
The basic idea of our caching strategy is to utilize the tree structure in the BMIN and the path
overlap of requests, replies, and coherence messages to provide coherent shared data in the intercon-
nect. By incorporating small fast caches in the switching elements of the BMIN, we can serve the
sharing processors at these switching elements. We use the term switch cache to differentiate these
caches from the processor caches. An example of a BMIN employing switch caches that can serve
Invalidation
Response
Ack, WriteBack
Request
(a) Bidirectional MIN - Structure and Routing
Processor/Cache Interface
Memory Interface
(b) Multiple Tree Structures in the BMIN
Processor/Cache Interface
Memory Interface
(c) Switch Caching in the BMIN
serviced
by memory
Switch Cache
serviced
by switch caches at
different levels

Figure

The Switch Cache Interconnect
multiple processors is shown in Figure 6(c). An initial shared read request from processor P i
to a
block is served at the remote memory M j
. When the reply data flows through the interconnection
network, the block is captured and saved in the switch cache at each switching element along the
path. Subsequent requests to the same block from sharing processors, such as P j
and P k
, take
advantage of the data blocks in the switch cache at different stages, thus incurring reduced read
latencies.
3.2 The Caching Protocol
The incorporation of processor caches in a multiprocessor introduces the well-known cache coherence
problem. Many hardware cache-coherent systems employ a full-map directory scheme [6], In this
scheme, each node maintains a bit vector to keep track of all the sharers of each block in its local
shared memory space. On every write, an ownership request is sent to the home node, invalidations
are sent to all the sharers of the block and the ownership is granted only when all the corresponding
acknowledgments are received. At the processing node, each cache employs a three-state (MSI)
protocol to keep track of the state of each cache line. Incorporating switch caches comes with the
requirement that these caches remain coherent, and data access remain consistent with the system
consistency model.
Cannot reach these 2 states
Write Initiated
by another processor
Expected State
SHARED DIRTY UNCACHED
ReadReply*
ReadReply* InvType
INVALID
SHARED ReadReply
ReadReply
(a) Switch Cache State Diagram
Add sharer to
directory vector
Send invalidation
to requestor
Increment ack_counter
to wait for additional ack
Protocol
(b) Change in Directory Protocol
Switch Hit Read

Figure

7: Switch Cache Protocol Execution
We adopt a sequential consistency model in this paper. Our basic caching scheme can be represented
by the state diagram in Figure 7 and explained as follows: The switch cache stores only
blocks in a shared state in the system. When a block is read to the processor cache in a dirty state,
it is not cached in the switch. Effectively, the switch cache needs to employ only a 2-state protocol
where the state of a block can be either SHARED or NOT VALID. The transitions of blocks from
one state to another is shown in Figure 7a. To illustrate the difference between block invalidations
(Inv Type) and block replacements (ReadReply  ), the figure shows the NOT VALID state
conceptually separated into two states INVALID and NOT PRESENT respectively.
Read Requests: Each read request message that enters the interconnect checks the switch caches
along its path. In the event of a switch cache hit , the switch cache is responsible for providing the
data and sending the reply to the requestor. The original message is marked as switch hit and it
continues to the destination memory (ignoring subsequent switch caches along its path) with the
sole purpose of informing the home node that another sharer just read the block. Such a message is
called a marked read request. This request is necessary to maintain the full-map directory protocol.
Note that memory access is not needed for these marked requests and no reply is generated. At
the destination memory, a marked read request can find the block in only two states, SHARED, or
TRANSIENT (see Figure 7b). If the directory state is SHARED, then this request only updates the
sharing vector in the directory. However, it is possible that a write has been initiated to the same
cache line by a different processor and the invalidation for this write has not yet propagated to the
switch cache. This can only be present due to false sharing or an application that allows data race
conditions to exist. If this occurs, then the marked read request observes a TRANSIENT state at
Physical Address
Swc Hit
Dest
bits
Flits Req
Age
4bits 2bits1
Addr (contd) Src
4bits
6bits
6bits
8bits

Figure

8: Message Header Format
the directory. In such an event, the directory sends an invalidation to the processor that requested
the read and waits for this additional acknowledgment before committing the write.
Read Replies: Read replies can originate from two different sources, namely, the memory node
or an owner's cache in dirty state. Both read replies enter the interconnect following the backward
path. The read reply originating from the memory node should check the switch cache along its
path. If the line is not present in a switch cache, the data carried by the read reply is written into
the cache. The state of the cache line is marked SHARED. For messages originating from an owner's
cache, only those replies whose home node and requester node are not identical can be allowed to
check the switch caches along the way. Those replies that find the line absent in the cache will
enter the data in the cache. If the home node and the requester are the same, the reply should
ignore the switch cache. This reply is not allowed to enter the switch cache because subsequent
modification of the block by the owner will not be visible to the interconnection network. Thus the
path from the owner to the requester is not coherent and does not overlap with the write request
or the invalidation request responsible for coherence (as explained next). In summary, only read
replies with non-identical home node and requester node should enter data into the switch cache,
if not already present.
Writes, Write-backs and Coherence Messages: These requests flow through the switches,
check the switch cache and invalidate the cache line if present in the cache. By doing so, the switch
cache coherence is maintained somewhat transparently.
Message Format: The messages are formatted at the network interface where requests, replies
and coherence messages are prepared to be sent over the network. In a wormhole-routed network,
messages are made up of flow control digits or flits. Each flit is 8 bytes as in Cavallino [5]. The
message header contains the routing information, while data flits follow the path created by the
header. The format of the message header is shown in Figure 8. To implement the caching technique,
we require that the header consists of 3 additional bits of information. Two bits (Reqtype
are encoded to denote the switch cache access type as follows:
cache line from the switch cache. If present, mark read header and generate
reply message.
4w
4w
4w
Forward
Link
Inputs
Backward
Link
Inputs
Forward
Link
Outputs
Link
Outputs
Backward
Input Block
Input Block
Input Block
Input Block
Arbiter
Crossbar
4w
Routing Tables
4w
4w
4w
4w

Figure

9: A conventional crossbar switch
line into the switch cache.
Invalidate the cache line, if present in the cache.
switch cache, no processing required.
Note from the above description and the caching protocol that read requests are encoded as sc read
requests. Read replies whose home node and requestor id are different are encoded as sc write. Coherence
messages, write ownership requests and write-back requests are encoded as sc inv requests.
All other requests can be encoded as sc ignore requests. An additional bit is required to mark
sc read requests as earlier switch cache hit. Such a request is called a marked read request. This
is used to avoid multiple caches servicing the same request. As discussed, such a marked request
only updates the directory and avoids a memory access.
4 Switch Cache Design and Implementation
Crossbar switches provide an excellent building block for scalable high performance interconnects.
Crossbar switches mainly differ in two design issues: switching technique and buffer management.
We use wormhole routing as the switching technique and input buffering with virtual channels since
these are prevalent in current commercial crossbar switches [5, 7]. We begin by presenting the
organization and design alternatives for a 4 \Theta 4 crossbar switch cache. In a later subsection, the
extensions required for incorporating a switch cache module into a larger (8 \Theta 8) crossbar switch
are presented.
4w
4w
4w
Forward
Link
Inputs
Backward
Link
Inputs
Forward
Link
Outputs
Link
Outputs
Backward
Input Block
Input Block
Input Block
Input Block
Routing Tables
Crossbar
4w
Arbiter
Input Block
Switch Cache
Module
4w
4w
4w
4w
4w
4w
4w
Forward
Link
Inputs
Backward
Link
Inputs
Forward
Link
Outputs
Link
Outputs
Backward
Input Block
Input Block
Input Block
Input Block
Crossbar
4w
Routing Tables
4w
4w
4w
4w
Switch Cache
Module
Arbiter
Input Block
(a) Arbitration-Independent (b) Arbitration-Dependent

Figure

10: Crossbar Switch Cache Organization
4.1 Switch Cache Organization
Our base bi-directional crossbar switch has four inputs and four outputs as shown in Figure 9. Each
input link in the crossbar switch has two virtual channels thus providing 8 possible input candidates
for arbitration. The arbitration process is the age technique, similar to that employed in the SGI
Spider Switch [7]. At each arbitration cycle, a maximum of 4 highest age flits are selected from 8
possible arbitration candidates. The flit size is chosen to be 8 bytes (4w) with links similar
to the Intel Cavallino [5]. Thus it takes four link cycles to transmit a flit from output of one switch
to the input of the next. Buffering in the crossbar switch is provided at the input block at each
link. The input block is organized as a fixed size FIFO buffer for each virtual channel that stores
flits belonging to a single message at a time. The virtual channels are also partitioned based on
the destination node. This avoids out-of-order arrival of messages originating from the same source
to the same destination. We also provide a bypass path for the incoming flits that can be directly
transmitted to the output if the input buffer is empty.
While organizing the switch cache, we are particularly interested in maximizing performance by
serving flits within the cycles required for the operation of the base crossbar switch. Thus the
organization depends highly on the delay experienced for link transmission and crossbar switch
processing. Here we present two different alternatives for organizing the switch cache module within
conventional crossbar switches. The arbitration-independent organization is based on a crossbar
switch operation similar to the SGI Spider [7]. The arbitration-dependent organization is based on
a crossbar switch operation similar to the Intel Cavallino [5].
Arbitration-Independent Organization: This switch cache organization is based on link and
switch processing delays similar to those experienced in the SGI Spider. The internal switch core
runs at 100 MHz, while the link transmission operates at 400MHz. The switch takes four 100MHz
clocks to move flits from the input to the link transmitter at the output. The link, on the other
hand, can transmit a 8byte flit in a single 100 MHz clock (four 400 MHz clocks). Figure 10a
shows the arbitration-independent organization of the switch cache. The organization is arbitration
independent because the switch cache performs the critical operations in parallel with the arbitration
operation. At the beginning of each arbitration cycle, a maximum of four input flits stored in
the input link registers are transmitted to the switch cache module. In order to maintain flow
control, all required switch cache processing should be performed in parallel with the arbitration
and transmission delay of the switch (4 cycles).
Arbitration-Dependent Organization: This switch cache organization is based on link and
switch processing delays similar to those experienced in the Intel Cavallino [5]. The internal switch
core and link transmission operate at 200MHz. It takes 4 cycles for the crossbar switch to pass the
flit from its input to the output transmitter and 4 cycles for the link to transmit one flit from one
switch to another. Figure 10b shows the arbitration-dependent organization of the switch cache.
The organization is arbitration dependent because it performs the critical operations at the end
of the arbitration cycle and in parallel with the output link transmission. At the end of every
arbitration cycle, a maximum of four flits passed through the crossbar from input buffers to the
output link transmitters are also transmitted to the switch cache. Since the output transmission
takes four 200MHz cycles, the switch cache needs to process a maximum of four flits within 4 cycles.
Each organization has its advantages/disadvantages. In the arbitration-independent organization,
the cache operates at the switch core frequency and remains independent of the link speed. On the
other hand, this organization lacks arbitration information which could be useful for completing
operations in an orderly manner. While this issue does not affect 4 \Theta 4 switches, the drawback will
be evident when we study the design of larger crossbar switches. The arbitration-dependent organization
benefits from the completion of the arbitration phase and can use the resultant information
for timely completion of switch cache processing. However in this organization, the cache is required
to run at link transmission frequency in order to complete critical switch cache operations. As in
the Intel Cavallino, it is possible to run the switch core, the switch cache and the link transmission
at the same speed.
Finally, note that, in both cases the reply messages from the switch cache module are stored in
another input block as shown in Figure 10. With two virtual channels per input block, the crossbar
switch size expands to 4. Also, in both cases, the maximum number of switch cache inputs are
4 requests and processing time is limited to 4 switch cache cycles.
Cache Size (in bytes)
Cache
Access
Time
(in
Direct
Cache Size (in bytes)
Cache
Access
Time
(in
Direct
(a) 32-byte cache lines (b) 64-byte cache lines

Figure

11: Cache Access Time (in FO4)
4.2 Cache Design: Area and Access Time Issues
The access time and area occupied by an SRAM cache depends on several factors such as asso-
ciativity, cache size, number of wordlines and number of bitlines[25, 16]. In this section, we study
the impact cache size and associativity on access time and area constraints. Our aim is to find the
appropriate design parameters for our crossbar switch cache.
Cache Access Time: The CACTI model [25] quantifies the relationship between cache size,
associativity and cache access time. We ran the CACTI model to measure the switch cache access
time for different cache sizes and set associativity values. In order to use the measurements in
a technology independent manner, we present the results using the delay measurement technique
known as the fan-out-of-four One FO4 is the delay of a signal passing through an inverter
driving a load capacitance that is four times larger than its input. It is known that a 8 Kbyte data
cache has a cycle time of 25 FO4 [9].

Figure

11 shows the results obtained in FO4 units. In Figure 11, the x-axis denotes the size of the
cache, and each curve represents the access time for a particular set associativity. We find that
direct mapped caches have the lowest access time since a direct indexing method is used to locate
the line. However, a direct mapped cache may exhibit poor hit ratios due to mapping conflicts in
the switch cache. Set-associative caches can provide improved cache hit ratios, but have a longer
cycle time due to a higher data array decode delay. Most current processors employ multi-ported
set associative L1 caches operating within a single processor cycle. We have chosen a 2-way set
associative design for our base crossbar switch cache to maintain a balance between access time and
hit ratio. However, we also study the effect of varied set associativity on switch cache performance.
Cache output width is also an important issue that primarily affects the data read/write delay.
As studied by Wilton et al. [25], the increase in data array width increases the number of sense
amplifiers required. The organization of the cache can also make a significant difference in terms of
(a) 32-byte cache lines (b) 64-byte cache lines

Figure

12: Cache Relative Area
chip area. Narrower caches provide data in multiple cycles, thus increasing the cache access time for
an average read request. For example, a cache with 32-byte blocks and a width of 64 bits decreases
the cache throughput to one read in four cycles. Within the range of 64 to 256 bits of data output
width, we know that 64 bits will provide the worst possible performance scenario. We designed our
switch cache using a 64-bit output width and show that the overall performance is not affected by
this parameter.
Cache Relative Area: In order to determine the impact of cache size and set associativity on
the area occupied by an on-chip cache, we use the area model proposed by Mulder et al.[16]. The
area model incorporates overhead area such as drivers, sense amplifiers, tags and control logic to
compare data buffers of different organizations in a technology independent manner using register-
bit equivalent or rbe. One rbe equals the area of a bit storage cell. We used this area model and
obtained measurements for different cache sizes and associativities.

Figure

12 shows the results obtained in relative area. The x-axis denotes the size of the cache and
each curve represents different set associativity values. For small cache sizes ranging from 512 bytes
to 4KB, we find that the amount of area occupied by the direct mapped cache is much lower than
that for an 8-way set associative cache. From the figure, we find that an increase in associativity
from 1 to 2 has a lower impact on cache area than an increase from 2 to 4. From this observation,
we think that a 2-way set associative cache design would be the most suitable organization in terms
of cache area and cache access time, as measured earlier.
4.3 CAche Embedded Switch ARchitecture (CAESAR)
In this section, we present a hardware design for our crossbar switch cache called CAESAR, (CAche
Embedded Switch ARchitecture). A block diagram of the CAESAR implementation is shown in

Figure

13. For a 4 \Theta 4 switch, a maximum of 4 flits are latched into switch cache registers at each
4w
4w
F
4w
F
4w 4w
R
Y
U
Switch Cache Module
Cache Access Control
Switch Cache
Module
Arbiter
Crossbar
Select
Source
Link/Buffer
Information
Process Incoming Flits
Flits Transmitted from Crossbar
header vector To
Input
Block
Blocking
Info
Update
Read
Header
Cache
Data
Unit
Cache
Tag
Unit
Snoop Registers
RI
Buffer
WR
Buffers

Figure

13: Implementation of CAESAR
arbitration cycle. The operation of the CAESAR switch cache can be divided into (1) process
incoming flits, (2) switch cache access, (3) switch cache reply generation, and (4) switch cache
feedback. In this section, we cover the design and implementation issues for each of these operations
in detail.
Process Incoming Flits: Incoming flits stored into the registers can belong to different request
types. The request type of the flit is identified based on the 2 bits (R 1 R 0 ) stored in the header.
Header flits of each request contain the relevant information including memory address required for
processing reads and invalidations. Subsequent flits belonging to these messages carry additional
information not essential for the switch cache processing. Write requests to the switch cache require
both the header flit for address information and the data flits to be written into the cache line.
Finally ignore requests need to be discarded since they do not require any switch cache processing.
An additional type of request that does not require processing is the marked read request. This
read request has the swc hit bit set in the header to inform switch caches that it has been served
at a previous switch cache. Having classified the types of flits entering the cache, the switch cache
processing can be broken into two basic operations.
The first operation performed by the flit processing unit is that of propagating the appropriate flits
to the switch cache. As mentioned earlier, the flits that need to enter the cache are read headers,
invalidation headers and all write flits. Thus, the processing unit masks out ignore flits, marked
read flits and the data flits of invalidation and read requests. This is done by reading the R 1 R 0 bits
from the header vector and the swc hit bit. To utilize this header information for the subsequent
data flits of the message, the switch cache maintains a register that stores these bits.
Flits requiring cache processing are passed to the request queue one in every cycle. The request
queue is organized as two buffers, the RI buffer and the set of WR buffers shown in Figure 13.
The RI buffer holds the header flits of read and invalidation requests. The WR buffers store all
write flits and are organized as num vc \Theta k=2 different buffers. Here multiple buffers are required
to associate data flits with the corresponding headers. When all data flits of a write request have
accumulated into a buffer, the request is ready to initiate the cache line fill operation.
The second operation to complete the processing of incoming flits is as follows. All unmarked read
header flits need to snoop the cache to gather hit=miss information. This information is needed
within the 4 cycles of switch delay or link transmission to be able mark the header by setting the last
bit (swc hit). To perform this snooping operation on the cache tag, the read headers are also copied
to the snoop registers (shown in Figure 13). We require two snoop registers because a maximum of
two read requests can enter the cache in a single arbitration cycle.
Switch Cache Access: Figure 14 illustrates the design of the cache subsystem. The cache module
shown in the figure is that of a 2-way set associative SRAM cache The cache operates at the same
frequency as the internal switch core. The set associative cache is organized using two sub-arrays
for tag and data. The cache output width is 64 bits, thus requiring 4 cycles of data transfer for
reading a line. The tag array is dual ported to allow two independent requests to
access the tag at the same time. We now describe the switch cache access operations and their
associated access delays. Requests to the switch cache can be broken into two types of requests:
snoop requests and regular requests.
Snoop Requests: Read requests are required to snoop the cache to determine hit or miss before
the outgoing flit is transmitted to the next switch. For the arbitration independent switch cache
organization (Figure 10a), it takes a minimum of four cycles for moving the flit from the switch
input to the output. Thus we need the snoop operation within the last cycle to mark the message
before link transmission. Similarly, for the arbitration dependent organization (Figure 10b), it takes
4 cycles to transmit a 64-bit header on a 16-bit output link after the header is loaded into the 64-bit
(4w) output register. From the message format in Figure 8, the phit containing the swc hit bit to
be marked is transmitted in the fourth cycle. Thus it is required that the cache access be completed
within a maximum of 3 cycles. From Figure 13, copying the first read to the snoop registers is
performed by the flit processing unit and is completed in one cycle. By dedicating one of the ports
of the tag array primarily for snoop requests, each snoop in the cache takes only an additional
cycle to complete. Since a maximum of 2 read headers can arrive to the switch cache in a single
arbitration cycle, we can complete the snoop operation in the cache within 3 cycles. Note from

Figure

14 that the snoop operation is done in parallel with the pending requests in the RI buffer
Qsize
Gen.
Reply
Data Buffer
Header
Bit
Directory 0
Queue Status Send ReplyREPLY UNIT
Request
Address
Address
Write
Data
Data In/Out
Data In/Out
Hit/Miss
BLOCKING INFO TO INPUT BLOCK

Figure

14: Design of the CAESAR Cache Module
and the WR buffers. When the snoop operation completes, the hit/miss information is propagated
to the output transmitter to update the read header in the output register. If the snoop operation
results in a switch cache miss, the request is also dequeued from the RI buffer.
Regular Requests: A regular request is a request chosen from either the RI buffer or the WR buffers.
Such a request is processed in a maximum of 4 cycles in the absence of contention. Requests from
the RI buffer are handled on a FCFS basis. This avoids any dependency violation between read
and invalidation requests in that buffer. However, we can have a candidate for cache operation from
the RI buffer as well as from one or more of the WR buffers. In the absence of address dependencies,
the requests from these buffers can progress in any order to the switch cache. When a dependency
exists between two requests, we need to make sure that cache state correctness is preserved. We
identify two types of dependencies between a request from the RI buffer and a request from the
WR buffer:
ffl An invalidation (from the RI buffer) to a cache line X and a write (from the the WR buffer) to the
same cache line X . To preserve consistency, the simplest method is to discard the write to the cache
line, thus avoiding incorrectness in the cache state. Thus, when invalidations enter the switch cache,
write addresses of pending write requests in the WR buffer are compared and invalidated in parallel
with the cache line invalidation.
ffl A read (from the RI buffer) to a cache line X and a write (from the WR buffer) to a cache line Y
that map on to the same cache entry. If the write occurs first, then cache line X will be replaced.
In such an event, the read request cannot be served. Since such an occurrence is rare, the remedy is
to send the read request back to the home node destined to be satisfied as a typical remote memory
read request.
Switch Cache Reply Generation: While invalidations and writes to the cache do not generate
any replies from the switch cache, read requests need to be serviced by reading the cache line from
the cache and sending the reply message to the requesting processor. The read header contains all
the information required to send out the reply to the requester. The read header and cache line data
are directly fed into the reply unit shown in Figure 14. The reply unit gathers the header at the
beginning of the cache access and modifies the source/destination and request/reply information in
the header in parallel with the cache access. When the entire cache line has been read, the reply
packet is generated and sent to switch cache output block. The reply message from the switch
cache now acts as any other message entering a switch in the form of flits and gets arbitrated to
the appropriate output link and progresses using the backward path to the requesting processor.
Switch Cache Feedback: Another design issue for the CAESAR switch is the selection of queue
sizes. In this section, we identify methods to preserve crossbar switch throughput by blocking only
those requests that violate correctness. As shown in Figure 13 and 14, finite size queues exist at
the input of the switch cache (RI buffer and WR buffer) and at the reply unit (virtual channel
queues in the switch cache output block). When any limited size buffer gets full, we have two
options for the processing of read/write requests. The first option is to block the requests until a
space is available in the buffer. The second option, probably the wiser one, is to allow the request
to continue on its path to memory. The performance of the switch cache will be dependent on the
chosen scheme only when buffer sizes are extremely limited. Finally, invalidate messages have to be
processed through the switch cache since they are required to maintain coherence. These messages
need to be blocked only when the RI buffer gets full. The modification required to the arbiter to
make this possible is quite simple. To implement the blocking of flits at the input, the switch cache
needs to inform the arbiter of the status of all its queues. At the end of each cycle, the switch
cache informs the crossbar about the status of its queues in the form of free space available in each
queue. The modification to the arbiter to perform the required blocking is minor. Depending on
the free space of each queue, appropriate requests (based on R 1 R 0 ) will be blocked while others
will traverse through the switch in a normal fashion.
4.4 Design of a 8 \Theta 8 Crossbar Switch Cache
In the previous sections, we presented the design and implementation of a 4 \Theta 4 cache embedded
crossbar switch. Current commercial switches such as SGI Spider and Intel Cavallino have six
Hit/Miss
Way
BankBank Select
Addr/Data
Pair
(1)
Way
Way
Way
BankBankBankQsize
Gen.
Reply
REPLY UNIT
Queue
Status
Reply
Addr/Data
Pair
Address
(1)
Address

Figure

15: Design of the CAESAR
bidirectional inputs, while the IBM SP2 switch has 8 inputs and 8 outputs. In this section, we
present extensions to the earlier design to incorporate a switch cache module in a 8 \Theta 8 switch. We
maintain the same base parameters for switch core frequency, core delay, link speed, link width and
flit size.
The main issue when expanding the switch is that the number of inputs to the switch cache module
doubles from 4 to 8. Thus, in each arbitration cycle, a maximum of four read requests can come
into the switch. They require snoop operation on the switch cache within 4 cycles of switch core
delay or link transmission depending on the switch cache organization shown in Figure 10. As
shown in Figure 13, it takes one cycle to move the flits to the snoop registers. Thus we require to
complete the snoop operation for 4 requests within 2 cycles and mark the header flit in the last
cycle depending on the snoop result.
In order to perform four snoops in two cycles, we propose to use a multiported CAESAR cache
module. Multiporting can be implemented either by duplicating the caches or interleaving it into
two independent banks. Since duplicating the cache consumes tremendous amount of on-chip area,
we propose to use a 2-way interleaved CAESAR (CAESAR as shown in Figure 15.
Interleaving splits the cache organization into two independent banks. Current processors such as
MIPS R10000 [26] use even and odd addressed banked caches. However, the problem remains that
four even addressed or four odd addressed requests will still require four cycles for snooping due
to bank conflicts. We propose to interleave the banks based on the destination memory by using
the outgoing link ids. In a 8 \Theta 8 switch there are four outgoing links that transmit flits from the
switch towards the destination memory and vice-versa. Each cache bank will serve requests flowing
through two of these links, thus partitioning the requests based on the destination memory. In an
arbitration-independent organization (Figure 10a), it is possible that four incoming read requests
are directed to the same memory module and result in bank conflicts. However, in the arbitration-
dependent organization (Figure 10b), the conflict gets resolved during the arbitration phase. This
guarantees that the arbitrated flits flow through different links. For 8 \Theta 8 switches, it would be
more advantageous to use an arbitration dependent organization, thus assuring a maximum of 2
requests per bank in each arbitration cycle. As a result, the snoop operation of four requests can
be completed in the required two cycles. Finally, note that only a few bits from the routing tag are
needed to identify the bank in the cache.
Such an interleaved organization changes the aspect ratio of the cache [25], and may affect the cycle
time of the cache. Wilson et al.[24] showed that the increase in cycle time measured using the
fan-out-of-four banked or interleaved caches over single ported caches was minimal.
The 2-way interleaved implementation also doubles the cache throughput. Since two requests can
simultaneously access the switch cache, the reply unit needs to provide twice the buffer space for
storing the data from the cache. Similarly the header flit of the two read requests also need to be
stored. As shown in Figure 15, the buffers are connected to outputs from different banks to gather
the cache line data.
Performance Evaluation
In this section, we present a detailed performance evaluation of the switch cache multiprocessor
based on execution-driven simulation.
5.1 Simulation Methodology
To evaluate the performance impact of switch caches on the application performance of CC-NUMA
multiprocessors, we use a modified version of the Rice Simulator for ILP Multiprocessors (RSIM)
[19]. RSIM is an execution driven simulator for shared memory multiprocessors with accurate
models of current processors that exploit instruction-level parallelism. In this section, we present
the various system configurations and the corresponding modifications to RSIM for conducting
simulation runs.
The base system configuration consists of 16 nodes. Each node consists of a 200MHz processor
Multiprocessor System - processors
Processor Memory
Speed 200MHz Access time 40
Issue 4-way Interleaving 4
Cache Network
L1 Cache 16KB Switch Size 8x8
line size 32bytes Core delay 4
set size 2 Core Freq 200MHz
access time 1 Link width 16 bits
L2 Cache 128KB Xfer Freq 200MHz
line 32bytes Flit length 8bytes
set size 4 Virtual Chs. 2
access time 8 Buf. Length 4 flits
Switch/Network Caches
Switch Cache 128bytes-8KB Network Cache 4KB
Application Workload
FWA 128x128 GE 128x128
GS 96x128 MM 128x128

Table

1: Simulation parameters
capable of issuing 4 instructions per cycle, a 16KB L1 cache a 128KB L2 cache, a portion of the
local memory, directory storage and a local bus interconnecting these components. The L1 cache
is 2-way set associative and an access time of a single cycle. The L2 cache is 4-way set associative
and has an access time of 8 cycles. The raw memory access time is 40 cycles, but it takes more
than 50 cycles to submit the request to the memory subsystem and read the data over the memory
bus. The system employs the full-map three-state directory protocol [6] and the MSI cache protocol
to maintain cache coherence. The system uses a release consistency model. We modified RSIM to
employ a wormhole routed bidirectional MIN using 8 \Theta 8 switches organized in 2 stages as shown
earlier in Figure 6. Virtual channels were also added to the switching elements to simulate the
behavior of commercial switches like Cavallino and Spider. Each input link to the switch is provided
with 2 virtual channel buffers capable of storing a maximum of 4 flits from a single message. The
crossbar switch operation is similar to the description in Section 4.1. A detailed list of simulation
parameters is also shown in Table 1.

Figure

Percentage Reduction in Memory Reads
To evaluate switch caches, we further modified the simulator to incorporate switch caches into each
switching element in the IN. The switch cache system improves on the base system in the following
respects. Each switching element of the bidirectional MIN employs a variable size cache that models
the functionality of the CAESAR switch cache presented in Section 4. Several parameters such as
cache size and set associativity are varied for evaluating the design space of the switch cache.
We have selected some numerical applications to investigate the potential performance benefits
of the switch cache interconnect. These applications are Floyd-Warshall's all-pair-shortest-path
algorithm, Gaussian elimination (GE), QR factorization using the Gram-Schmidt Algorithm (GS)
and the multiplication of 2D matrices (MM), successive over-relaxation of a grid (SOR) and the
six-step 1D fast fourier transform (FFT) from SPLASH [20]. The input data sizes are shown in

Table

1 and the sharing characteristics were discussed in Section 2.1.
5.2 Base Simulation Results
In this subsection, we present and analyze the results obtained through extensive simulation runs to
compare three systems: the base system (Base), network cache (NC) and switch cache (SC). The
Base system does not employ any caching technique beyond the L1 and L2 caches. We simulate
a system with NC by enabling 4KB switch caches in all the switching elements of stage 0 in the
MIN. Note that stage 0 is the stage close to the processor, while stage 1 is the stage close to the
remote memory as shown in Figure 6. The SC system employs switch caches in all the switching
elements of the MIN.
The main purpose of switch caches in the interconnect is to serve read requests as they traverse
to memory. This enhances the performance by reducing the number of read misses served at the
remote memory. Figure 16 presents the reduction in the number of read misses to memory by
Appl Hit Distribution Sharing
GS 69.02 30.98 1.94 2.37
GE 59.55 40.45 1.58 2.66

Table

2: Distribution of switch cache accesses
employing network caches (NC) and switch caches (SC) over the base system (Base). In order to
perform a fair comparison, here we compare a SC system with 2KB switch caches at both stages
(overall 4KB cache space) to a NC system with 4KB network caches. Figure 16 shows that network
caches reduce remote read misses by 6-20% for all the applications, except FFT. The multiple layers
of switch caches are capable of reducing the number of memory reads requests by upto 45% for
FWA, GS and GE applications.

Table

2 shows the distribution of switch cache hits across the two stages (St0 and St1) of the
network. From the table, we note that a high percentage of requests get satisfied in the switch
caches present at the lowest stage in the interconnect. Note however, that for three of the six
applications, roughly 30-40% of the requests are switch cache hits in the stage close to the memory
(St1). It is also interesting to note the number of requests satisfied by storing each block in the
switch cache. Table 2 presents this data as sharing, which is defined as the number of different
processor requests served after a block is encached in the switch cache. We find that this sharing
degree ranges from 1.0 to 2.7 across all applications. For applications with high overall read sharing
degrees (FWA, GS and GE), we find that the the degree of sharing is approximately 1:7 in the stage
closer to the processor. With only 4 of 16 processors connected to each switch, many read requests
do not find the block in the first stage but get satisfied in the subsequent stage. Thus we find a
higher (approximately 2:5) read sharing degree for the stage closer to the remote memory for these
applications. The MM application has an overall sharing degree of approximately 4 (see Figure 2).
The data is typically shared by four processors physically connected to the same switch in the first
stage of the network. Thus most of the requests (88:2%) get satisfied in the first stage and attain
a read sharing degree of 1:8. Finally, the SOR and FFT applications have very few read shared
requests, most of which are satisfied in the first stage of the network.

Figure

17: Impact on average read latency

Figure

Application execution time improvements

Figure

17 shows the improvement in average memory access latency for reads for each application
by using switch caching in the interconnect. For each application, the figure consists of three bars
corresponding to the Base, NC and SC systems. The average read latency comprises of processor
cache delay, bus delay, network data transfer delay, memory service time and queueing delays at
the network and memory module. As shown in the figure, by employing network caches, we can
improve the average read latency by atmost 15% for most of the applications. With switch caches
in multiple stages of the interconnect, we find that the average read latency can be improved by
as high as 35% for FWA, GS and GE applications. The read latency reduces by about 7% for the
MATMUL application. Again, SOR and FFT are unaffected by network caches or switch caches
due to negligible read sharing.
The ultimate parameter for performance is execution time. Figure 18 shows the execution time
improvement. Each bar in the figure is divided into computation and synchronization time, read
stall time and write stall time. In a release consistent system, we find that the write stall time is
negligible. However, the read stall time in the base system comprises as high as 50% of the overall

Figure

19: Impact of cache size on the number of memory reads

Figure

20: Impact of cache size on execution time
execution time. Using network caches, we find that the read stall time reduces by a maximum of 20%
(for the FWA, GS and GE applications) and thus translates to an improvement in execution time
by up to 10%. Using switch caches over multiple stages in the interconnect, we observe execution
time improvements as high as 20% in the same three applications. The execution time of the MM
application is comparable to that with network caches. SOR and FFT are unaffected by switch
caches.
5.3 Sensitivity Studies
Sensitivity to Cache Size
In order to determine the effect of cache size on performance, we varied the switch cache size from
a mere 128 bytes to a large 8KB. Figures 19 & 20 show the impact of switch cache size on the
number of memory reads and the overall execution time. As the cache size is increased, we find that
a switch cache size of 512 bytes provides the maximum performance improvement (up to 45% reads
5HSO ,QY

Figure

21: Effect of cache size on the eviction rate

Figure

22: Effect of cache size on switch cache hits across stages
and 20% execution time) for three of the six applications. The MM and SOR applications require
larger caches for additional improvement. The MM application attains a performance improvement
of 7% in execution time at a switch cache size of 2KB. Increasing the cache size further has negligible
impact on performance. For SOR, we found some reduction in the number of memory reads, contrary
to the negligible amount of sharing in the application (shown in Figure 2). Upon investigation, we
found that the switch cache hits come from replacements in the L2 caches. In other words, blocks
in the switch cache are accessed highly by the same processor whose initial request entered the
block into the switch cache. The switch cache acts as a victim cache for this application. The use
of switch caches does not affect the performance of the FFT application.

Figure

21 investigates the impact of cache size on the eviction rate and type in the switch cache for
the FWA application. The x-axis in the figure represents the size of the cache in bytes. A block in
the switch cache can be evicted either due to replacement or due to invalidation. Each bar in the
figure is divided into two portions to represent the amount of replacements versus invalidations in
the switch cache. The figures are normalized to the number of evictions for a system with 128 byte

Figure

23: Effect of line size on the number of memory reads
switch caches. The first observation from the figure is the reduction in the number of evictions as
the cache size increases. Note that the number of evictions remains constant beyond a cache size
of 1KB. With small caches, we also observe that roughly 10-20% of the blocks in the switch cache
are invalidated while all others are replaced. In other words, for most blocks, invalidations are not
processed through the switch cache since they have already been evicted through replacements due
to small capacity. As the cache size increases, we find the fraction of invalidations increase, since
fewer replacements occur in larger caches. For the 8KB switch cache, we find that roughly 50% of
the blocks are invalidated from the cache.
We next look at the impact of cache size on the amount of sharing across stages. Figure 22 shows
the amount of hits obtained in each stage of the network for the FWA application. Each bar is
divided into two segments, representing each stage of switch caches, denoted by the stage number.
Note that Stage0 is the stage closest to the processor interface. From the figure, it is interesting to
note that for small caches, an equal amount of hits are obtained from each stage in the network.
On the other hand, as the cache size increases, we find that a higher fraction of the hits are due to
switch caches closer to the processor interface (60-70% from St0). This is beneficial, because fewer
hops are required in the network to access the data, thereby reducing the read latency considerably.
Sensitivity to Cache Line Size
In the earlier sections, we analyzed data with lines. In this section, we vary the cache
line size to study its impact on switch cache performance. Figures 23 & 24 show the impact of
a larger cache line (64 bytes) on the switch cache performance for three applications
and GE). We vary the cache size from 256 bytes to 16KB and compare the performance to the
base system with lines and 64 byte cache lines. Note that the results are normalized
to the base system with 64 byte cache lines. We found that the number of memory reads were

Figure

24: Effect of line size on execution time

Figure

25: Effect of associativity on switch cache hits
reduced by 37 to 45% when we increase the cache line size in the base system. However, the use
of switch caches still has significant impact on application performance. With 1KB switch caches,
we can reduce the number of read requests served at the remote memory by as high as 45% and
the execution time by as high as 20%. In summary, the switch cache performance does not depend
highly on cache line size for highly read shared applications with good spatial locality.
Sensitivity to Set Associativity
In this section, we study the impact of cache set associativity on application performance. Figure 25
shows the percentage of switch cache hits as the cache size and associativity are varied. We find that
set associativity has no impact on switch cache performance. We believe that frequently accessed
blocks need to reside in the switch cache only for a short amount of time, as we observed earlier
from our trace analysis. A higher degree of associativity tries to prolong the residence time by
reducing cache conflicts. Since we do not require a higher residence time in the switch cache, the
performance is neither improved nor hindered.

Figure

26: Effect of application size on execution time
Sensitivity to Application Size
Another concern for the performance of switch caches is the relatively small data set that we have
used for faster simulation. In order to verify that the switch cache performance does not change
drastically for larger data sets, we used the FWA application and increased the number of vertices
from 128 to 192 and 256. Note that the data set size increases by a square of the number of vertices.
The base system execution time increases by a factor of 2.3 and 4.6 respectively. With 512 byte
switch caches, the execution time reduces by 17% for 128 vertices, 13% for 192 vertices and 10%
for 256 vertices. In summary, we believe that switch caches require small cache capacity and can
provide sufficient performance improvements for large applications with frequently accessed read
shared data.
6 Conclusions
In this paper, we presented a novel hardware caching technique, called switch cache, to improve
the remote memory access performance of CC-NUMA multiprocessors. A detailed trace analysis of
several applications showed that accesses to shared blocks have a great deal of temporal locality.
Thus remote memory access performance can be greatly improved by caching shared data in a global
cache. To make the global cache accessible to all the processors in the system, the interconnect
seems to be the best location since it has the ability to monitor all inter-node transactions in the
system in an efficient, yet distributed fashion.
By incorporating small caches within each switching element of the MIN, shared data was captured
as they flowed from the memory to the processor. In designing such a switch caching framework,
several issues were dealt with. The main hindrance to global caching techniques is that of maintaining
cache coherence. We organized the caching technique in a hierarchical fashion by utilizing
the inherent tree structure of the BMIN. By doing so, caches were kept coherent in a transparent
fashion by the regular processor invalidations sent by the home node and other such control infor-
mation. To maintain full-map directory information, read requests that hit in the switch cache were
marked and allowed to continue on their path to the memory for the sole purpose of updating the
directory. The caching technique was also kept non-inclusive and thus devoid of the size problem
in a multi-level inclusion property.
The most important issue while designing switch caches was that of incorporating a cache within
typical crossbar switches (such as SPIDER and CAVALLINO) in a manner such that requests are
not delayed at the switching elements. A detailed design of a cache embedded switch architecture
(CAESAR) was presented and analyzed. The size and organization of the cache depends heavily
on the switch transmission latency. We presented a dual-ported 2-way set associative SRAM cache
organization for a 4 \Theta 4 crossbar switch cache. We also proposed a link-based interleaved cache
organization to scale the size of the CAESAR module for 8 \Theta 8 crossbar switches. Our simulation
results indicate that a small cache of size 1 KB bytes is sufficient to provide up to 45% reduction in
memory service and thus a 20% improvement in execution time for some applications. This relates
to the fact that applications have a lot of temporal locality in their shared accesses. Current switches
such as SPIDER maintain large buffers that are under-utilized in shared memory multiprocessors.
It seems that by organizing these buffers as a switch cache, the improvement in performance can
be realized.
In this paper, we studied the use of switch caches to store recently accessed data in the shared state
to be re-used by subsequent requests from any processor in the system. In addition to these requests,
applications also have a significant amount of accesses to blocks in the dirty state. To improve the
performance of such requests, directories have to be embedded within the switching elements. By
providing shared data through switch caches and ownership information through switch directories,
the performance of the CC-NUMA multiprocessor can be significantly improved. Latency hiding
techniques such as data prefetching or forwarding can also utilize the switch cache and reduce
the risk of processor cache pollution. The use of switch caches along with the above latency
hiding techniques can further improve the application performance on CC-NUMA multiprocessors
tremendously.



--R

"An Overview of the HP/Convex Exemplar Hardware,"
"Butterfly Parallel Processor Overview, version 1,"
"Performance of the Multistage Bus Networks for a Distributed Shared Memory Multiprocessor,"
"The Impact of Switch Design on the Application Performance of Shared Memory Multiprocessors,"
"Cavallino: The Teraflops Router and NIC,"
"A New Solution to Coherence Problems in Multicache Sys- tems,"
"Scalable Pipelined Interconnect for Distributed Endpoint Routing: The SGI SPIDER Chip,"
"Tutorial on Recent Trends in Processor Design: Reclimbing the Complexity Curve,"
"High Frequency Clock Distribution,"
"The SGI Origin: A ccNUMA Highly Scalable Server,"
"The Network Architecture of the Connection Machine CM-5,"
"The Stanford DASH Multiprocessor,"
"STiNG: A CC-NUMA Computer System for the Commercial Mar- ketplace.,"
"The Effectiveness of SRAM Network Caches on Clustered DSMs,"
"A Performance Model for Finite-Buffered Multistage Interconnection Networks,"
"An Area Model for On-Chip Memories and its Applica- tion,"
"Design and Analysis of Cache Coherent Multistage Interconnection Networks,"
"The Impact of Shared-Cache Clustering in Small-Scale Shared-Memory Mul- tiprocessors,"
"RSIM Reference Manual. Version 1.0,"
"SPLASH: Stanford Parallel Applications for Shared- Memory,"
"The SP2 High Performance Switch,"
"The Performance of the Cedar Multistage Switching Network,"
"Hierarchical cache/bus architecture for shared memory multiprocessors,"
"Designing High Bandwidth On-Chip Caches,"
"An Enhanced Access and Cycle Time Model for On-Chip Caches,"
"The MIPS R10000 Superscalar Microprocessor,"
"Reducing Remote Conflict Misses: NUMA with Remote Cache versus COMA,"
--TR

--CTR
Takashi Midorikawa , Daisuke Shiraishi , Masayoshi Shigeno , Yasuki Tanabe , Toshihiro Hanawa , Hideharu Amano, The performance of SNAIL-2 (a SSS-MIN connected multiprocessor with cache coherent mechanism), Parallel Computing, v.31 n.3+4, p.352-370, March/April 2005
shared memory multiprocessors;wormhole routing;crossbar switches;scalable interconnects;cache architectures;execution-driven simulation