Design and performance of a coherent cache for parallel logic programming architectures

ABSTRACT

This paper describes the design and performance of a tightly-coupled shared-memory coherent cache optimized for the execution of parallel logic programming architectures. The cache utilizes a copy-back write-allocation protocol having five states and a hardware lock mechanism. Optimizations for logic programming are introduced in four software-controlled memory access commands: direct-write, exclusive-read, read-purge, and read-invalidate. In this paper we describe these operations and present simulated measurements showing their performance advantage for an architecture of the committed-choice language KL1. The cache optimizations also improve the performance of non-committed-choice languages, such as OR-parallel Prolog. A version of the cache design described here is currently being implemented for ICOT's Parallel Inference Machine (PIM).

REFERENCES

• 1: James Archibald , Jean-Loup Baer, Cache coherence protocols: evaluation using a multiprocessor simulation model, ACM Transactions on Computer Systems (TOCS), v.4 n.4, p.273-298, Nov. 1986 [doi>10.1145/6513.6514]
• 2: P. Bitar , A. M. Despain, Multiprocessor cache synchronization: issues, innovations, evolution, Proceedings of the 13th annual international symposium on Computer architecture, p.424-433, June 02-05, 1986, Tokyo, Japan
• 3: T. Chikayama et. al. Overview of the Parallel Inference Machine Operating System PIMOS. In Znt. Conf. on 5th Gen. Camp. Sys., Tokyo, November 1988.
• 4: S. J. Eggers , R. H. Katz, A characterization of sharing in parallel programs and its application to coherency protocol evaluation, Proceedings of the 15th Annual International Symposium on Computer architecture, p.373-382, May 30-June 02, 1988, Honolulu, Hawaii, United States
• 5: 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
• 6: A. Goto et. al. Overview of the Parallel Inference Machine Architecture PIM. In Int. Conf. on 5th Gen. Comp. Sys., Tokyo, November 1988.
• 7: R. H. Katz , S. J. Eggers , D. A. Wood , C. L. Perkins , R. G. Sheldon, Implementing a cache consistency protocol, Proceedings of the 12th annual international symposium on Computer architecture, p.276-283, June 17-19, 1985, Boston, Massachusetts, United States
• 8: Y. Kimura and T. Chikayama. An Abstract KLl Machine and its Instruction Set. In ht. Symp. on Logic Pmg., pages 468-477, August 1987.
• 9: E. Lusk et. al. The Aurora Or-Parallel Prolog System. In ht. Conf. on 5th Gen. Comp. Sys., Tokyo, November 1988.
• 10: A. Matsumoto et. al. Locally Parallel Cache Design Based on KLl Memory Access Characteristics. Technical Report 327, ICOT, 1987.
• 11: H. Nakashima and K. Nakajima. Hardware Architecture of the Sequential Inference Machine: PSI-II. In Int. Symp. on Logic Prog., pages 104-113, August 1987.
• 12: K. Nishida et. al. Evaluation of the Effect of Incremental Garbage Collection by MRB on FGHC Parallel Execution Performance. Technical Report 394, ICOT, 1988.
• 13: Mark S. Papamarcos , Janak H. Patel, A low-overhead coherence solution for multiprocessors with private cache memories, Proceedings of the 11th annual international symposium on Computer architecture, p.348-354, January 1984
• 14: M. Sato et al. KLl Execution Model for PIM Cluster with Shared Memory. In 4th Int. Conf. on Logic Pmg., pages 338-355. MIT Press, May 1987.
• 15: Sequent Computer Systems, Inc. Sequent Guide to Parallel Pmgmmming, 1987.
• 16: Alan Jay Smith, Cache Memories, ACM Computing Surveys (CSUR), v.14 n.3, p.473-530, Sept. 1982 [doi>10.1145/356887.356892]
• 17: Charles P. Thacker , Lawrence C. Stewart , Edwin H. Satterthwaite, Jr., Firefly: A Multiprocessor Workstation, IEEE Transactions on Computers, v.37 n.8, p.909-920, August 1988 [doi>10.1109/12.2243]
• 18: P. Sweazey , A. J. Smith, A class of compatible cache consistency protocols and their support by the IEEE futurebus, Proceedings of the 13th annual international symposium on Computer architecture, p.414-423, June 02-05, 1986, Tokyo, Japan
• 19: E. Tick, Data buffer performance for sequential Prolog architectures, Proceedings of the 15th Annual International Symposium on Computer architecture, p.434-442, May 30-June 02, 1988, Honolulu, Hawaii, United States
• 20: E. Tick. Performance of Parallel Logic Programming Architectures. Technical Report TR.-421, ICOT, September 1988.
• 21: K. Ueda, Guarded horn clauses, Concurrent Prolog, MIT Press, Cambridge, MA, 1988
• 22: D. H. D. Warren. .4n Abstract Prolog Instruction Set. Technical Report 309, SRI International, 1983.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Logic and constraint programming

General Terms:
Languages