Multiprocessor system utilizing a directory memory and including grouped processing elements each having cache

• US 5,537,569 A
• Filed: 03/02/1994
• Issued: 07/16/1996
• Est. Priority Date: 03/02/1993
• Status: Expired due to Fees

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Masubuchi, Yoshio
• Primary Examiner(s): Kim, Matthew M.
• Application Number:
  US08/204,499
• Time in Patent Office: 867 Days
• Field of Search: 364/200 MS, 364/900 MS, 395/425, 395/403, 395/448, 395/471, 395/200.08, 395/472, 395/421.11
• US Class Current: 711/121
• CPC Class Codes: G06F 12/0826 Limited pointers directories; State-only directories without pointers

Abstract

In a shared memory type multiprocessing system, when data stored in each processing element is managed in a directory method, a plurality of processing elements are grouped in advance. A directory memory is provided along with a data memory mounted in a shared memory. Directory information held in the directory memory indicates which one of the groups holds a copy of a data block. In response to a request from the processing element, the shared memory executes a process of finding the processing element from the processing group, or a process of finding the processing group from the processing element.

Claims

1. A multiprocessor system having a data memory for storing data in a plurality of divided block areas, and a plurality of processing elements each having a cache memory for holding a copy of part of said data stored in said divided block areas of said data memory in units of a data block stored in each of said divided block areas, said multiprocessor system comprising:

a directory memory for classifying said plurality of processing elements into processing groups each comprising a plurality of said processing elements, and for holding directory information indicating which one of said processing group holds a copy of the data stored in said data memory in units of said data block; and

control means for referring to said directory memory in response to a request from one of said processing elements, for identifying the processing group holding said copy of data, and for delivering a predetermined message to processing elements belonging to the identified processing group.

2. The multiprocessor system according to claim 1, wherein said control means delivers successively said predetermined message to the processing elements belonging to said identified processing group.

3. The multiprocessor system according to claim 1, wherein said control means broadcasts said predetermined message to the processing elements belonging to said identified processing group.

4. The multiprocessor system according to claim 1, wherein said directory information includes a shared bit indicating that the data is held in at least two of said processing groups.

5. The multiprocessor system according to claim 1, wherein each of said processing elements includes a plurality of CPUs (Central Processing Unit).

6. The multiprocessor system according to claim 1, wherein said control means refers to said directory memory in response to a write request from one of said processing elements, identifies the processing group holding said copy of data, and delivers a data invalidation message to the processing elements belonging to the identified processing group, excluding the one processing element making the write request.

7. The multiprocessor system according to claim 6, wherein said control means includes directory information control means and group information control means, wherein

said group information control means finds, from a group address assigned to the processing group sent from said directory information control means, an end address assigned to the processing elements belong to said processing group, and delivers the end address to said directory information control means, and

said directory information control includes:

means for referring to said directory memory, in response to said write request, for identifying the processing group holding said copy of data, and for delivering the group address corresponding to said processing group to said group information control means, and

means for delivering the data invalidation message to the processing elements belonging to said identified processing group based on the end address sent from said group information control means.

8. The multiprocessor system according to claim 1, wherein said control means writes new directory information in said directory memory in response to a read request from a given one of said processing elements, and delivers a desired data block to the one processing element making the read request.

9. The multiprocessor system according to claim 8, wherein said control means includes directory information control means and group information control means,

said group information control means includes:

means for identifying, from an end address sent from said directory information control means, the processing group to which the one processing element making the read request belongs; and

means for decoding a group address assigned to said identified processing group, for obtaining first directory information, and for delivering said first directory information to said directory information control means, and

said directory information control means includes;

means for delivering said end address of the origin of the request to said group information control means in response to said read request;

means for referring to said directory memory in response to said read request and for reading out second directory information corresponding to desired data; and

means for calculating logical OR of said first directory information and said second directory information, and for changing said second directory information in said directory information memory to a result of the calculated logical OR.

10. The multiprocessor system according to claim 1, wherein a group address (m-bits) assigned to said processing group is determined to satisfy the condition:

space="preserve" listing-type="equation">k≦

2.sup.m, and n≧

m,

when an end address assigned to said processing element is n-bits and one entry of the directory information is k-bits.

11. A directory management method applicable to a multiprocessing system having a data memory for storing data in a plurality of divided block areas, a plurality of processing elements each having a cache memory for holding a copy of part of said data stored in said divided block areas of said data memory in units of a data block stored in each of said divided block areas, and a directory memory for storing information relating to a copy of the data stored in said data memory, said directory management method comprising the steps of:

a) classifying said plurality of processing elements into processing groups each comprising a plurality of said processing elements, and holding directory information indicating which of said processing groups hold the copy of the data stored in said data memory, said directory information being held in said directory memory in units corresponding to said data block; and

b) referring to said directory memory in response to a request for data from one of said processing elements, identifying the processing group holding the requested data, and delivering a predetermined message to the processing elements belonging to the identified processing group.

12. The method according to claim 11, wherein said step b) includes a step of delivering successively said predetermined message to the processing elements belonging to said identified processing group.

13. The method according to claim 11, wherein said step b) includes a step of broadcasting said predetermined message to the processing elements belonging to said identified processing group.

14. The method according to claim 11, wherein said step a) includes a step of storing, in said directory memory, shared information indicating that the copy of the data is held in at least two of said processing groups.

15. The method according to claim 11, wherein each of said processing elements includes a plurality of CPUs (Central Processing Unit).

16. The method according to claim 11, wherein said step b) includes the steps of:

referring to said directory memory in response to a write request for data from a given one of said processing elements, and identifying the processing group holding the requested data,

identifying an end address assigned to the processing elements within said processing group based on a group address assigned to said processing group, and

delivering a data invalidation message to the processing elements within said identified processing group based on the end address.

17. The method according to claim 11, wherein said step b) includes the additional steps of:

identifying, in response to a read request from one of the processing elements, the processing group to which said processing element making the read request belongs, the identification being made based on an end address of the processing element making the read request, and

decoding a group address assigned to said identified processing group and obtaining first directory information, and wherein the steps recited by claim 11 include;

referring to said directory memory in response to said read request and reading out second directory information corresponding to desired data, calculating logical OR of said first directory information and said second directory information, and changing said second directory information in said directory information memory to a result of the calculated logical OR, and

delivering a desired data block to the processing element making the read request.