A low-overhead coherence solution for multiprocessors with private cache memories

ABSTRACT

This paper presents a cache coherence solution for multiprocessors organized around a single time-shared bus. The solution aims at reducing bus traffic and hence bus wait time. This in turn increases the overall processor utilization. Unlike most traditional high-performance coherence solutions, this solution does not use any global tables. Furthermore, this coherence scheme is modular and easily extensible, requiring no modification of cache modules to add more processors to a system. The performance of this scheme is evaluated by using an approximate analysis method. It is shown that the performance of this scheme is closely tied with the miss ratio and the amount of sharing between processors.

References

1. 1.J. Archibald and J. L. Baer, "An Economical Solution to the Cache Coherence Solution," University of Washington Technical Report 83-10-07, October, 1983.
2. 2.B. M. Bean, K. Langston, R. Partridge, and K. K. Sy, "Bias Filter Memory for Filtering out Unnecessary Interrogations of Cache Directories In a Multiprocessor System," United States Patent 4,142,234, February 27, 1979.
3. 3.L. M. Censier and P. Feautrier, "A New Solution to Coherence Problems in Multicache Systems," IEEE Trans. Comput., Vol. C-27, December 1978, pp. 1112-1118.
4. 4.C. J. Conti, "Concepts for Buffer Storage," IEEE Comput. Group News, vol. 2, March 1969, pp. 9-13.
5. 5.M. Dubois and F. A. Briggs, "Effects of Cache Coherency in Multiprocessors," IEEE Trans. Comput., vol. C-31, November 1982, pp. 1083-1099.
6. 6.J. R. Goodman, "Using Cache Memory to reduce Processor-Memory Traffic," Proc. 10th Annual Symp. on Computer Architecture, June 1983, pp. 124-131.
7. 7.K. R. Kaplan and R. O. Winder, "Cache-Based Computer Systems," Computer, March 1973, PP. 30-36.
8. 8.R. M. Meade, "On Memory System Design," AFIPS Proc. FJCC, vol. 37, 1970, pp. 33-43.
9. 9.R. L. Norton and J. A. Abraham, "Using Write Back Cache to Improve Performance of Multiuser Multiprocessors," Proc. 1982 Int. Conf. on Parallel Processing, August 1982, pp. 326-331.
10. 10.J. H. Patel, "Analysis of Multiprocessors with Private Cache Memories," IEEE Trans. Comput., vol. C-31, April 1982, pp. 296-304.
11. 11.G. S. Rao, "Performance Analysis of Cache Memories," J. ACM, vol. 25, No. 3, July 1978, pp. 378-395.
12. 12.A. J. Smith, "Cache Memories," Computing Surveys, vol. 14, No. 3, September 1982, pp. 473-530.
13. 13.W. D. Strecker, "Cache Memories for PDP-11 Family Computers". Proc. 3rd Annual Symp. on Computer Architecture, January 1976, PP. 155-158.
14. 14.C. K. Tang, "Cache System Design in the Tightly Coupled Multiprocessor System," AFIPS Proc. NCC, vol. 45, 1976, PP. 749-753.
15. 15.P. C. C. Yeh, J. H. Patel, and E. S. Davidson, "Shared Cache for Multiple-Stream Computer Systems," IEEE Trans. Comput., vol. C-32, January 1983, pp. 38-47.
16. 16.W. C. Yen and K. S. Fu, "Coherence Problem in a Multicache System," Proc. 1982 Int. Conf. on Parallel Processing, 1982, pp. 332-339.

Index Terms

• Computer systems organization

  • Architectures

    • Parallel architectures

      • Interconnection architectures

      • Multiple instruction, multiple data

• Hardware

  • Integrated circuits

    • Semiconductor memory

      • Dynamic memory