Directory schemes have long been used to solve the cache coherence problem for large scale shared memory multiprocessors. In addition, tree-based protocols have been employed to reduce the directory size and the invalidation latency for a large degree of data sharing in the system. However, the existing tree-based protocols involve a very high communication overhead for maintaining a balanced tree, especially when the degree of data sharing is low. This paper presents a new tree-based cache coherence protocol which is a hybrid of the limited directory and the linked list schemes. By utilizing a limited number of pointers in the directory, the proposed protocol connects the nodes caching a shared block in a tree fashion without incurring any communication overhead. In addition to the low communication overhead, the proposed scheme also possesses the advantages of the existing bit-map and tree-based linked list protocols, namely, scalable memory requirement and logarithmic invalidation latency. We evaluate the performance of our protocol by running four applications on the Proteus execution-driven simulator. Our simulation results show that the performance of the proposed protocol is very close to that of the full-map protocol.

In this brief contribution, we derive an exact expression for (n-1)-cube reliability in an n-cube using a new probability fault model and an existing random fault model. Approximate results are also obtained for m-cube reliability for values of m smaller than n-1. We show that the proposed probability model for computing subcube reliability is equally accurate, but computationally more efficient than the existing random fault model.>

We study the problem of constructing subcubes in faulty hypercubes. First a divide-and-conquer technique is used to form the set of disjoint subcubes in the faulty hypercube. The concept of irregular subcubes is then introduced to take advantage of advanced switching techniques, such as wormhole routing, to increase the sizes of the available subcubes. We present a subcube partitioning technique to form an irregular subcube of maximum size. The n-cube containing two faults is studied first because, in the worst case, two faults are sufficient to destroy all the possible regular (n-1)-cubes. It is shown that the subcube partitioning technique is able to tolerate /spl Gamma/n/2/spl Gamma/ faults while maintaining a fault-free (n-1)-cube in a faulty n-cube. In general, we show that a fault-free (n-m-1)-cube is guaranteed when there are (/spl Gamma/n-m/2/spl Gamma/+1)/spl times/2/sup m/+2/sup m-1/-1 or fewer faults. We also develop a two-phase subcube allocation strategy in order to show the average case performance of our subcube construction technique. Extensive simulation is conducted to show the effectiveness of the two-phase subcube allocation strategy.>

This paper proposes a distributed directory cache coherence protocol and compares the performance of the proposed protocol with fully mapped and single linked list protocols for the hypercube multiprocessors. The directories of shared blocks are maintained as a tree structure which is motivated by the similarity of the indirect binary n-cube to the direct binary n-cube. The proposed protocol also takes advantage of the wormhole routing technique. Compared to the fully mapped and single linked list schemes, the proposed protocol reduces the memory reference latency and the network traffic.

The subcube allocation problem in faulty hypercubes is studied in this paper. An efficient method for forming the set of regular subcubes is proposed. A concept of irregular subcubes is then introduced to take advantage of the advanced switching techniques such as wormhole routing to increase the size of available sub cubes. In this paper, a two-phase fault tolerant subcube allocation strategy is proposed. The first phase is the re configuration process based on a modified subcube parti tioning technique which finds the set of disjoint subcubes in the faulty hypercube. The second phase is to apply an existing fault-free subcube allocation strategy such as Buddy strategy to each disjoint subcube for assigning the fault-free available subcubes to the incoming tasks. The simulation results using Buddy strategy are also given.