Figure 6: Figure 7:

Figure 8:

gives rise to the arc going to the write-back capture buffers node. Because several of the processing steps after a write-back has been captured is performed by the sP, cycles exists, and deadlocks are possible.

The way to solve this problem is to provide extra hardware that performs the flush. This gives rise to the dependence graph shown in Figure 9. In StarT-ng, we have chosen to implement this in the ACD hardware, but it functions in parallel to all the other functionalities of the ACD. Another potential solution is to use another microprocessor to perform the flush. This can also be used to provide some of the services currently performed by the sP but not all. Those that can be moved to the second processor are the processing of a captured Read Request and processing of Read Request to the home site. The two arrows from the Read Request Capture Buffers node and the Home Buffer for Read Requests node to the Flush Executor does not create any cycle.

3.4.3 Model Summarizing Resource Types in StarT-ng

In the design of CCDSM on StarT-ng, we used the dependence graph approach described above, and a simple but typical protocol to derive a model that summarized the different sets of hardware resources we need. Although this model is derived from the simple protocol described above, it is actually able to accomodate many variations of the protocols. The reason for this flexibility is that most protocols does not involve more than sites in three categories: the initiator site, the home site, and remote sites. The communication with this large group normally starts from the home, and either goes to the home, or the initiator site. These three groups of sites correspond to the three pieces of the model described next.

The model, as shown in Figure 10, has three main pieces, with six groups of resources. The main pieces and their resources are:

• The BI+NIU: The BI provides the Bus Interface for global memory. Blocking hardware resources include: (i) Read Request Buffers; (ii) Write-back Request buffers; (iii) Returned Figure 9: Figure 10:

Figure 11:

Data Buffer.

• The pP+NIU: The pP provides the directory management and protocol processing. Hardware blocking resources include: (i) Home Buffer for Read Requests; (ii) Home buffer for write-back requests.

• The cC+NIU: The cC performs blocking operation like flush. Resources in this part are: (i) buffer and logic for performing flush requests. (flusher)

The dependence graph of this model is exactly that in Figure 7. The grouping into the 3 main pieces are based on similarity in functionality. The BI interfaces to the snoopy bus on the requester’s end, the pP performs all home site functionality, while the cC performs remote site, blocking operations. We have not done any combining of the different groups of resources as any combination will result in static cycles and hence deadlock.

This model is mapped on StarT-ng hardware by having the sP perform most of the functionality in a non-blocking manner. Access to network always goes through the sP. All the buffers are software buffers managed by the sP, but in the six different categories to avoid out-of-buffer deadlocks. The only thing that the sP cannot do is blocking operations like flush. Thus the cC cannot be multiplexed on the sP but is instead provided by extra hardware as part of the ACD, which also include the BI. The latter cannot be provided by the sP as it’s bus interface cannot be made to behave like that of a memory.

3.4.4 Preallocation as a Means of Modifying the Dependence Graph

The dependence graph arising from a protocol can be changed by preallocation of buffer space, which has the effect of removing some dependence. For instance, Requested Data Buffer can be allocated when the Read Request is captured. This removes arcs going to the node labelled Requested Data Buffers in Figure 7, and merges that node with Read Request Capture Buffers, producing the dependence graph of Figure 11.

3.5 The Role of Network in a CCDSM System

We have so far glossed over the interconnection network. It is tempting to solve the out-of-buffer problem by assuming that the network has infinite buffering. This is unfortunately unrealistic and also does not solve all the deadlock problems either. The idea, however, raises the interesting and perhaps worrysome question of whether the network itself can introduce further deadlocks, and how should a CCDSM implementation deal with this issue. Fortunately, given our above view of buffering, all that we assume of the network is only that the switching fabric never blocks. All the source and destination buffering is managed by the CCDSM protocol.

A network that provides separate request and reply networks can easily achieve the requirement that the network fabric does not block. A protocol message is in general sent on the request network. If it is unable to obtain the type of buffering space it needs at the receiver end it is simply retried by the receiver. Since the protocol always holds on to the buffering at the sender side in the previous step of the protocol processing, the retry has the “always sinkable” property of a reply and is put on the reply network.

An explicit ACK is not necessary if a reply from the destination back to the sender is expected. Otherwise, an ACK sent on the reply network to deallocate the buffering space at the source is needed. The overhead of ACK is expected to be low as most CCDSM protocol messages have a natural accompanying reply. Retry is also expected to be rare as the design should provide sufficient buffering so that this is not necessary most of the time, and only used to avoid potential deadlocks. It should also be noted that protocol messages that are replies, i.e. they are always sinkable, can use the reply network directly, thus avoiding firstly the need for source buffering once the message is sent out, and secondly the need for retry or ACK.

3.6 StarT-ng specific CCDSM Issues

In StarT-ng’s setting, there is a temptation to allow the sP to share cacheable, writeable data between the other processors at the site, which we call the computer processors (cPs). This could, for example, be used as a means for the cPs to communicate with the sP and vice versa.

Unfortunately, this is unsafe as the sP may now read data which is dirty in one of the cPs. As a result, an attempt by the sP to read the data will block until the cP is able to push the dirty data out with a write-back. However, the write-back may be blocked because all the write-back capture buffers resource are in used, and can only be freed up by the sP. In the dependence graph, sharing of writeable, cacheable data between the sP and the cPs introduces an arc from the sP to the write-back capture buffers resource, and results in a cycle.

Data sharing is still possible between the sP and cP, but it must be through uncached memory. It is also interesting to note that since OS data-structures on SMPs are usually cacheable and writeable by any processor, this prohibition on sharing cacheable, writeable memory between the cPs and the sP means that the sP cannot be running the same OS that is running on the other sP. For this reason, the sP will in most likelihood have to run firmware code without VM, although it is conceivable that the sP could run a simple OS of its own, that does not share any resource with the other OS.

4 A Word on StarT-ng’s Minimum Hardware CCDSM Performance

Since StarT-ng’s support for CCDSM is mostly software, a cache miss incurs a significant penalty. In this section, we will assess that penalty and analyze whether that penalty is tolerable.

Type of Miss  Penalty (cycles)
L3 Hit  157
Local Clean  199
Local Dirty Remote  692
Remote Clean  699
Remote Dirty at Home 786
Remote Dirty Remote 1219

Figure 12: Miss penalties

4.1 Penalty of a cache miss

We plan to have the sP implement an L3 cache in software. Once a cache-miss is captured by the ACD, the sP will check its local cache for the item. We expect the L3 cache to be around 32 megabytes large.

Cache miss penalty, therefore, depends on whether the desired cache-line hits in the L3 cache. Since the L3 cache is managed by software, we expect that prefetching techniques can work very well. We could instruct the sP to bring over an object at a time. Also, if prefetching is done at the correct time, much of the desired data that is being prefetched could wind up in the sP’s L1 or L2 cache, speeding up the software access time.

The penalties of cache-misses are shown in Figure ??. The times are given in processor cycles and are approximate. The penalties assume that a remote home location is 7 network hops away and that a remote dirty location is 5 network hops away.

4.2 Cache miss inpact on overall performance

StarT-ng’s CCDSM support is experimental, and thus the performance is not optimal. In this section, we will use Stanford FLASH miss ratios[?] to estimate our performance relative to the code running on a single site.

The performance numbers are found in Figure 13. The miss ratios and the breakdowns into local and remote accesses were obtained from a Flash paper[?].

The numbers in the L3 cache rows indicate the additional cost incurred by global references that do not hit in the cache to memory references. In other words, to compute the average cost of a global memory reference, figure out the cost of the reference if it hits in the cache, then add the value given. In order to get overall performance impact on the instruction stream, the average global reference cost should be multiplied by the fraction of global references there are in the instruction stream then added to the cost of the rest of the instructions.

These numbers are probably overly pessimistic. The Flash numbers were generated with a 1 megabyte cache; our cache will be 4 megabytes, though Flash’s cache has lines twice as long as ours.

It is clear that unless we get under 1% miss rates, our performance will be quite bad. We hope, however, that split-phase techniques will greatly reduce our penalties (perhaps down to the 300 to 400 cycle range for any access that requires remote communication), which would better our performance dramatically. Using 400 cycles as the cycle penalty if remote access needs to be performed to get the cache-line, we wind up with the numbers shown in Figure 14. It is interesting to note that for programs with very good hit rates, performance actually gets worse with split-phase.

Barnes  FFT  LU  MP3D  Ocean  OS  Radix
Miss Rate (1 M)  0.06%  0.64%  0.05%  6.00%  0.91%  0.09%  0.78%
Local Clean  2.40%  20.10%  1.00%  0.40%  51.70% 20.00%  2.60%
Local Dirty Remote  3.70%  0.00%  0.00%  5.90%  0.00%  2.70%  76.00%
Remote Clean  38.70% 17.70% 67.10%  3.80%  10.50% 58.60% 16.60%
Remote Dirty at Home 3.60%  62.10% 31.90%  5.90%  37.80%  2.60%  2.20%
Remote Dirty Remote 52.60%  0.10%  0.00%  84.00%  0.00%  16.10%  2.60%
Miss rate 64k  0.6%  1.1%  7.1%  2.5%  4.2%
No L3 cache  0.58223 4.179501 0.360877 68.3112 4.307813 0.616314 5.429689
50% L3 cache hit rate 0.338215 2.59215 0.219688 38.8656 2.868256 0.378807 3.327145
80% L3 cache hit rate 0.191806 1.63974 0.134975 21.19824 2.004523 0.236303 2.065618
90% L3 cache hit rate 0.143003 1.32227 0.106738 15.30912 1.716611 0.188801 1.645109

Figure 13: Performance numbers assuming blocking when cache misses

Barnes  FFT  LU  MP3D  Ocean  OS  Radix
Miss Rate (1 M)  0.06%  0.64%  0.05%  6.00%  0.91%  0.09%  0.78%
Local Clean  2.40%  20.10%  1.00%  0.40%  51.70% 20.00%  2.60%
Local Dirty Remote  3.70%  0.00%  0.00%  5.90%  0.00%  2.70%  76.00%
Remote Clean  38.70% 17.70% 67.10%  3.80%  10.50% 58.60% 16.60%
Remote Dirty at Home 3.60%  62.10% 31.90%  5.90%  37.80%  2.60%  2.20%
Remote Dirty Remote 52.60%  0.10%  0.00%  84.00%  0.00%  16.10%  2.60%
Miss rate 64k  0.6%  1.1%  7.1%  2.5%  4.2%
No L3 cache  1.239506 3.301434 1.198995 24.95176 3.694355 1.32382 4.079237
50% L3 cache hit rate 1.166853 2.653117 1.138748 17.68588 3.061528 1.23256 3.151919
80% L3 cache hit rate 1.123261 2.264127 1.102599 13.32635 2.681831 1.177804 2.595527
90% L3 cache hit rate 1.108731 2.134463 1.09055 11.97318 2.555266 1.159552 2.410064

Figure 14: Performance numbers assuming split-phase switch when cache misses

For programs with bad performance, however, the performance gets significantly better.

Using page localization? (no numbers for this)

5 Related Work

In this section, we compare StarT-ng’s CCDSM implementation to that of other similar machines, including the Stanford DASH, the MIT Alewife, and the Stanford FLASH.

5.1 Comparison with the Stanford DASH

Stanford’s DASH is very similar to StarT-ng in that it connects together a collection of SMPs. However, DASH only provides shared memory and not message passing capabilities. A network is still needed for shared memory communication, but this is not directly accessible by code executed on the processors for message passing.

The biggest difference between StarT-ng and DASH’s CCDSM implementations lies in the implementation strategy. CCDSM in DASH is provided with dedicated hardware that implements the directory and all the protocol processing in hardware. Directory memory is provided with special fast memory on a board that also houses the protocol processing hardware. The board communicates with the SMP bus on one side, and a 2D mesh routing network on the other side.

From a logical point of view, the important difference is that once a request, for example a cache line read request, is captured from the snoopy bus in DASH, the shared memory board takes care of all the processing without having to go over the local snoopy bus again until a result is returned. It may have to send a request to a remote site’s shared memory board, which then accesses memory over the remote site’s SMP bus. However, none of this requires crossing the local snoopy bus. In constrast, StarT-ng’s implementation requires crossing the local L3 bus multiple times during the processing of any bus operation to shared memory.

Another important difference is that on DASH, access to shared memory that happen to reside on the same site as the requestor can happen directly to memory, unless coherence action on remote sites are needed. In contrast, because directory information is managed in software by the sP on StarT-ng, all accesses to shared memory, even resident shared memory, has to go through the local ACD and sP. We have suggested in Section 4 that through the use of localized global pages we may be able to ameliorate this disadvantage in programs that exhibit favorable access patterns.

The implementors of DASH are well aware of the potential for deadlocks. As reported in [4], the approach taken is to fit the protocol messages into the two categories, request and reply, and to use two networks. It was not stated very clearly in the paper, but buffering space seems to be associated with the network, giving rise to 4 categories of buffer space for protocol processing:

(1) request send; (2) request receive; (3) reply send; and (4) reply receive. Unfortunately, the presence of flush results in request messages giving rise to request messages. The approach taken in DASH is to use time-out when a request that is being forwarded cannot be sent out after a certain amount of time, and retry the original request. While this approach breaks the deadlock, there is no guarantee that livelock does not results. The approach that we described in this paper, of using more categories of buffering, and multiplexing of different types of requests over one request network through the use of retry, will not have such problems.

5.2 Comparison with the MIT Alewife and the Stanford FLASH

The MIT Alewife and the Stanford FLASH machines are very similar in terms of the placement of hardware to support CCDSM. In both cases, this is placed in the memory controller sits at the cross-road between the processor, main memory, and network. Figure ?? shows the block diagram of an Alewife node, while Figure ?? shows that of Flash. In the case of Alewife, the memory controller, which they called CMMU, also controls the off chip L1 cache. For FLASH, the chip is called MAGIC, and controls access to the PCI peripheral bus too. The CCDSM support on Alewife and FLASH differs in that in the case of Alewife, most of the support is provided in hardware, although it is possible to interrupt the processor to provide further processing. In FLASH, MAGIC includes an augmented RISC core and all processing is under software control.

Interesting features of this placement of the CCDSM support include:

• Accesses from remote sites comes into the CMMU/MAGIC chip from the network, and has direct access to the main memory. In certain cases, coherency action has to be done to the local processor’s cache, but this is not always needed.

• All accesses to memory has to go through the CMMU/MAGIC chip. Thus this path has to be very fast when no coherence action is needed since there is no notion of local memory.

In general, this approach provides a more integrated way for supporting CCDSM, and will probably yield better performance. However, it requires extensive development effort. Development of the CMMU chip took four to five years, while the MAGIC chip is currently under development. It will have about 6 million transistor chip, about as big as the processor that it supports. Machines built this way also have to be built from scratch. In StarT-ng, we would like to build our system with entire SMP as the building block. This design point is therefore not available to us.

Like all other CCDSM implementations, deadlock, particularly from lack of buffer space, is possible for both machines. Alewife assumes infinite buffer space in the network[1]. They “implemented” this by timing out and interrupting the processor when the a network (NIU) send queue has been full for a while. The processor then uses main memory to provide more buffer space. However, any such extension will only provide a finite amount of buffer space, particularly since Alewife does not support virtual memory. While it may be the case the deadlock does not arise very often, there is no guarantee that it will not happen.

The description of FLASH in [3] talks about deadlock problems in some detail. It is based on the approach in DASH but with a fair amount of extensions. Separate request and reply networks are used, as in DASH. In addition, they attempt to have request messages indicate the resources it needs so that MAGIC can selectively service those messages whose resource requirements can be met. However, this choice is only limited to those messages that have already been accepted into the message receive buffer space in MAGIC. MAGIC can also backed theses schemes up with software buffers. They can use the scheme suggested in this paper of maintaining different categories of software buffer, but this was not mentioned in [3]. They did talk about using negative acknowledgement, but without keeping different categories of buffer space, it is not clear that the system is guranteed to be free of lack-of-buffer deadlock.

6 Conclusion

Why do we choose to implement CCDSM on StarT-ng this way?

CCDSM is provided on StarT-ng as an experimental feature. We are interested in finding the cheapest way of providing CCDSM on StarT-ng kind of setting, where the commercial building block imposes strict constraint on what can be done. For a very low cost, this experimental implementation will allow us to learn much about CCDSM in general. As this paper shows, the work is already yielded better understanding. We are also interested in exploring the virtual memory management (VMM) aspects of CCDSM. Unlike traditional shared memory machines, where the entire machine runs one copy of OS, we would like each site of StarT-ng to run its own copy of OS. There are many reasons for doing this, including better fault tolerant behavior. Coordination of VMM across multiple sites, and scheduling of work across multiple sites will be done as a layer on top of the per-site OS. StarT-ng will provide the platform for pursueing this research work.

It will also be interesting to see what sort of performance we can get out this extremely lowcost implementation. We have given some expected performance numbers in Section 4 and have suggested some ways of improving performance. Even if the performance turns out to be lack lustre, we will learn what are the important sources of overhead, and provide better implementations in the future.

A sP steps to service a memory access

In order to check if a desired cache-line is in the L3 cache, we need to do the following steps. We are assuming that the L3 cache is implemented using a direct-mapped scheme. We assume that the ACD has already captured the transaction.

1. ACD raises the line to the NIU. This should happen almost instantanously.

2. sP reads NIU (15 cycles) and jumps to the handler (3 cycles).

3. sP reads ACD (30 cycles) to get address (including operation).

4. sP extracts offset into direct mapped cache by performing one shift and one and operation (2 cycles.)

5. sP adds base of cache to offset (1 cycle) and reads the stored tag and presence bits (3, 15 or 30 cycles depending on hit in L1 or L2.) sP computes tag (simply a mask) and computes the address of the cache-line itself during the latency to read the stored tag.

6. sP compares tag to stored tag (1 cycle)

7. if tags compare, sP reads cache-line (3, 15 or 30 cycles depending on hit in L1 or L2.) This may be pipelined by speculatively reading when the tag is read. Reading the other words in the cache take another 7 cycles.

8. write cache-line to the ACD. Assume write-through (32 cycles + 15 cycle latency for 8 words).

9. write bus tag to ACD. Assume uncached write (15 cycle latency.)

Assuming that everything hits in the L2 cache and there is no pipelining of reading the L3 cache, the total time is 15 + 3 + 30 + 2 + 1 + 15 + 1 + 15 + 7 + 32 + 15 + 15 = 157 cycles. This time is approximately 5 times longer than a normal local access.

Let us assume that the desired cache-line is not available in the L3 cache. If the home is the current site, then the sP needs to do the following actions after the tag for the L3 is compared.

1. check to see if home is this site, mask, compare and branch (2 cycles).

2. compute directory address by adding offset to another base (1 cycle) and read directory (3, 15 or 30 cycles depending on L1 or L2 cache hits.)

3. discover that cache-line is at home, read data (30 cycles + 7 cycles for other reads.)

4. write cache-line to the ACD. Assume write-through (32 cycles + 15 cycle latency for 8 words).

5. write bus tag to ACD. Assume uncached write (15 cycle latency.)

Thus, a miss in the L3 that results in reading the cache-line from local memory takes 15 + 3 + 30 + 2 + 1 + 15 + 1 + 2 + 1 + 30 + 30 + 7 + 32 + 15 + 15 = 199 cycles.

If the cache-line is a local cache-line, but it is dirty in a remote location, the sP needs to perform an invalidation. The steps to do so are listed below. The steps follow checking the directory.

1. sP_{home} finds that cache-line is not clean at home and sends and invalidation message (35 cycles)

2. message propogates through NIU (12 cycles)

3. request goes through Arctic network (18 cycles per stage, assume 5 stages 90 cycles)

4. sP_{remote} receives message (20 cycles)

5. sP_{remote} writes flush to cC (20 cycles)

6. sP_{remote} cC flushes (30 cycles)

7. sP_{remote} reads that flush has completed (30 cycles to do first read, 30 cycles to read cache-line first word, 7 cycles to finish reading)

8. sP_{remote} sends back cache-line (60 cycles) to home

9. request goes through Arctic network (18 cycles per stage, assume 5 stages 90 cycles)

10. message enters NIU (54 cycles + 12 cycles)

11. sP_{home} receives cache-line (60 cycles)

12. write cache-line to the ACD. Assume write-through (32 cycles + 15 cycle latency for 8 words).

13. write bus tag to ACD. Assume uncached write (15 cycle latency.)

The total time to read a cache-line whose home is local but is dirty on another site is 15 + 3 + 30 + 2 + 1 + 15 + 1 + 2 + 1 + 30 + 35 + 12 + 90 + 20 + 20 + 30 + 30 + 7 + 60 + 90 + 54 + 12 + 60 + 32 + 15 + 15 = 692 cycles.

If the home is on another site, the sP then has to send a message to the home location. Assume that no invalidations need to be performed, that the requested cache-line is available from the home location. Assume that sending a request takes 35 cycles, sending a full cache-line and address takes 60 cycles, receiving a simple request takes 20 cycles and receiving a full cache-line and address takes 55 cycles.

These steps take place after the tag comparision completes.

1. sP sends request (35 cycles)

2. message propogates through NIU (12 cycles)

3. request goes through Arctic network (18 cycles per stage, assume 7 stages, 126 cycles)

4. sP receives message (20 cycles)

5. sP computes offset for directory state by performing a shift and an and operation. (2 cycles)

6. sP adds base to offset (1 cycle) and reads directory word (3, 15 or 30 cycles.)

7. sP checks to see that it cache-line is home (2 cycles)

8. sP reads cache-line (3, 15 or 30 cycles + 7 cycles.)

9. sP sends cache-line + address back (60 cycles)

10. message travels through Arctic (18 cycles per stage, assume 7 stages, 126 cycles.)

11. message enters NIU (54 cycles + 12 cycles)

12. sP reads message from NIU (60 cycles)

13. write cache-line to the ACD. Assume write-through (32 cycles + 15 cycle latency for 8 words).

14. write bus tag to ACD. Assume uncached write (15 cycle latency.)

Again, some pipeline may be possible here. The total time is 15 + 3 + 30 + 2 + 1 + 15 + 1 from the first sequence subtotalling to 67 cycles. Then we add 35 + 12 + 126 + 20 + 2 + 1 + 30 + 2 + 30 + 60 + 126 + 54 + 12 + 60 + 32 + 15 + 15 = 699 cycles. This is approximately a factor of 5 more than a hit in the L3 cache.

If a local invalidation needs to be performed before the value can be returned, the following steps occur after the check to see if the cache-line is home.

1. sP_{home} writes flush to cC (20 cycles)

2. sP_{home} cC flushes (30 cycles)

3. sP_{home} reads that flush has completed (30 cycles to do first read, 30 cycles to read cache-line first word, 7 cycles to finish reading)

4. sP_{home} sends cache-line + address back to requester (60 cycles)

5. message travels through Arctic (18 cycles per stage, assume 7 stages, 126 cycles.)

6. message enters NIU (54 cycles + 12 cycles)

7. sP reads message from NIU (60 cycles)

8. write cache-line to the ACD. Assume write-through (32 cycles + 15 cycle latency for 8 words).

9. write bus tag to ACD. Assume uncached write (15 cycle latency.) Thus, the total time to perform a memory access to a cache-line from a remote site and the line

is dirty at that site is 67 + 35 + 12 + 126 + 20 + 2 + 1 + 30 + 2 + 20 + 30 + 30 + 30 + 7 + 60 + 126 + 54 + 12 + 60 + 32 + 15 + 15 = 786.

If a non-local invalidation needs to be performed before the value can be returned, the following steps need to be performed. These steps occur after the tag comparision takes place.

1. sP sends request (35 cycles)

2. message propogates through NIU (12 cycles)

3. request goes through Arctic network (18 cycles per stage, assume 7 stages, 126 cycles)

4. sP_{home} receives message (20 cycles)

5. sP_{home} computes offset for directory state by performing a shift and an and operation. (2 cycles)

6. sP_{home} adds base to offset (1 cycle) and reads directory word (3, 15 or 30 cycles.)

7. sP_{home} checks to see that it cache-line is home (2 cycles)

8. sP_{home} finds that cache-line is not clean at home and sends and invalidation message (35 cycles)

9. message propogates through NIU (12 cycles)

10. request goes through Arctic network (18 cycles per stage, assume 5 stages 90 cycles)

11. sP_{remote} receives message (20 cycles)

12. sP_{remote} writes flush to cC (20 cycles)

13. sP_{remote} cC flushes (30 cycles)

14. sP_{remote} reads that flush has completed (30 cycles to do first read, 30 cycles to read cache-line first word, 7 cycles to finish reading)

15. sP_{remote} sends back cache-line (60 cycles) to home

16. request goes through Arctic network (18 cycles per stage, assume 5 stages 90 cycles)

17. message enters NIU (54 cycles + 12 cycles)

18. sP_{home} receives cache-line (60 cycles)

19. sP_{home} sends cache-line + address back to requester (60 cycles)

20. message travels through Arctic (18 cycles per stage, assume 7 stages, 126 cycles.)

21. message enters NIU (54 cycles + 12 cycles)

22. sP reads message from NIU (60 cycles)

23. write cache-line to the ACD. Assume write-through (32 cycles + 15 cycle latency for 8 words).

24. write bus tag to ACD. Assume uncached write (15 cycle latency.)

Thus the total for reads is 67 cycles + 35 + 12 + 126 + 20 + 2 + 1 + 30 + 2 + 35 + 12 + 90 + 20 + 20 + 30 + 30 + 30 + 7 + 60 + 90 + 54 + 12 + 60 + 60 + 126 + 54 + 12 + 60 + 32 + 15 + 15 = 1219 cycles.

It is possible that some of these numbers could be optimized down or could go up. It is important to note that StarT-ng will be configured in a Fat tree topology, which allows locality to be exploited. Thus, network numbers could be smaller.

References

[1] A. Agarwal, D. Chaiken, G. D’Souza, K. Johnson, D. Kranz, J. Kubiatowicz, K. Kurihara, B. H. Lim, G. Maa, D. Nussbaum, M. Parkin, and D. Yeung. The MIT Alewife Machine: A Large-Scale Distributed-Memory Multiprocessor. In Proceedings of Workshop on Scalable Shared Memory Multiprocesors. Kluwer Academic Publishers, 1991.

[2] G. A. Boughton. Arctic routing chip. In Proceedings of Hot Interconnects II, Stanford, CA, pages 164 – 173, Aug 1994.

[3] J. Kuskin, D. Ofelt, M. Heinrich, J. Heinlein, R. Simoni, K. Gharachorloo, J. Chapin, D. Nakahira, J. Baxter, M. Horowitz, A. Gupta, M. Rosenblum, and J. Hennessy. The Stanford FLASH Multiprocessor. In Proceedings of the 21st Annual International Symposium on Computer Architecture, Chicago, Il, pages 302–313, April 1994.

[4] D. Lenoski, J. Laudon, K. Charachorloo, A. Gupta, and J. Hennessy. The Directory-Based Cache Coherence Protocol for the DASH Multiprocesor. In Proceedings of The 17th Annual International Symposium on Computer Architecture, Seattle, WA, pages 148–159, 1990.

[5] X. W. Shen. Global Cache Coherence Schemes for StarT-ng. CSG Memo 361, MIT Lab. for Comp. Sci., Cambridge MA, Dec 1994.

Contents

1 Introduction 1

2 The Design of StarT-ng 4 2.1 Network and network interface unit . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 ACD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.3 Supporting CCDSM with the ACD and sP . . . . . . . . . . . . . . . . . . . . . . . 7

2.3.1 Partitioning Memory Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.3.2 Further experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

3 Issues in Designing CCDSM on StarT-ng 9 3.1 Constraints Imposed by the SMP Snoopy Bus Protocol . . . . . . . . . . . . . . . . 9 3.2 Issues arising from the Parallel, Distributed Nature of CCDSM . . . . . . . . . . . . 10 3.3 Logical Correctness of CCDSM Protocol . . . . . . . . . . . . . . . . . . . . . . . . 10 3.4 Implementation of a CCDSM Protocol without Introducing Deadlocks . . . . . . . . 12

3.4.1 Dependence Graph: A Tool for Checking Safe Sharing of Blocking Hardware 12 3.4.2 Presence of Non-buffer Blocking Hardware . . . . . . . . . . . . . . . . . . . . 14 3.4.3 Model Summarizing Resource Types in StarT-ng . . . . . . . . . . . . . . . 16 3.4.4 Preallocation as a Means of Modifying the Dependence Graph . . . . . . . . 18

3.5 The Role of Network in a CCDSM System . . . . . . . . . . . . . . . . . . . . . . . 19 3.6 StarT-ng specific CCDSM Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

4 A Word on StarT-ng’s Minimum Hardware CCDSM Performance 19 4.1 Penalty of a cache miss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4.2 Cache miss inpact on overall performance . . . . . . . . . . . . . . . . . . . . . . . . 20

5 Related Work 21 5.1 Comparison with the Stanford DASH . . . . . . . . . . . . . . . . . . . . . . . . . . 21 5.2 Comparison with the MIT Alewife and the Stanford FLASH . . . . . . . . . . . . . 22

6 Conclusion 23

A sP steps to service a memory access 24