Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

This paper presents two cache schemes for a shared-memory shared bus multiprocessor. Both schemes feature decentralized consistency control and dynamic type classification of the datum cached (i.e. read-only, local, or shared). It is shown how to exploit these features to minimize the shared bus traffic. The broadcasting ability of the shared bus is used not only to signal an event but also to distribute data. In addition, by introducing a new synchronization construct, i.e. the Test-and-Test-and-Set instruction, many of the traditional. parallell processing “hot spots” or bottlenecks are eliminated. Sketches of formal correctness proofs for the proposed schemes are also presented. It appears that moderately large parallel processors can be designed by employing the principles presented in this paper.

REFERENCES

• 1: J.D. Bell et al., "An Investigation of Alternative Cache Organizations," IEEE Transactions on Computers, Volume C-23, No. 4, April 1974.
• 2: Faye A. Briggs , Michel Dubois , Kai Hwang, Throughput analysis and configuration design of a shared-resource multiprocessor system: PUMPS, Proceedings of the 8th annual symposium on Computer Architecture, p.67-79, May 12-14, 1981, Minneapolis, Minnesota, United States
• 3: L.M. Censier and P. Feautrier, "A New Solution to Coherence Problems in Multicache Systems," IEEE Transaction on Computers, Vol., C-27, No. 12, December 1978.
• 4: Michel Dubois , Faye A. Briggs, Efficient interprocessor communication for MIMD multiprocessor systems, Proceedings of the 8th annual symposium on Computer Architecture, p.187-196, May 12-14, 1981, Minneapolis, Minnesota, United States
• 5: Michel Dubois , Fayė A. Briggs, Effects of cache coherency in multiprocessors, Proceedings of the 9th annual symposium on Computer Architecture, p.299-308, April 26-29, 1982, Austin, Texas, United States
• 6: S. J. Frank, "Tightly coupled multiprocessor system speeds memory-access times," Electronics, Vol. 57, No. 1, Jan. 1984, pp. 164.
• 7: James R. Goodman, Using cache memory to reduce processor-memory traffic, Proceedings of the 10th annual international symposium on Computer architecture, p.124-131, June 13-17, 1983, Stockholm, Sweden
• 8: A. Gottlieb, R. Grishman, C.P. Kruskal, K. P. McAuliffe, L. Rudolph, and M. Snir. "The NYU Ultracomputer - Designing an MIMD Shared Memory Parallel Computer," IEEE Transactions on Computers. Volume C-32, February 1983.
• 9: Levy Raskin, Performance evaluation of multiple processor systems., 1978
• 10: Lawrence S. Rudolph, Software structures for ultraparallel computing, 1982
• 11: L.S. Rudolph, "Executing Systolic Loops on MIMD Multiprocessors," Dept. of Computer Science, Carnegie-Mellon University, 1984. {SMI82} A.J. Smith, "Cache Memories," Computing Surveys, September 1982.
• 12: C.K. Tang, "Cache System Design in the Tightly Coupled Multiprocessor System," Proceedings of the AFIPS, 1976.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Multiple-instruction-stream, multiple-data-stream processors (MIMD)

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
          Subjects: Correctness proofs

General Terms:
Design, Performance