US5535361A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Cache block replacement scheme based on directory control bit set/reset and hit/miss basis in a multiheading multiprocessor environment
Assignee: Panasonic Holdings Corp
•
Filing: 1993-05-24
•
Granted: 1996-07-09
•
Expires: 2013-05-24
Abstract
Abstract A cache controller for a multithreading multiprocessor system which starts an execution of another thread by suspending an ongoing execution of a thread when a cache miss happens. The cache controller comprises a cache directory unit for storing cache managing data including a footprint bit to indicate a mapping relation between at least one cache block in a main memory block, an access control unit for searching the directory unit based on an access requesting message inputted thereto through its input/output port connected to a processor to return one of a cache hit notice and a cache miss notice, as well as transferring messages with the main memory through its input/output port connected to a network, and a footprint bit changing device for setting the footprint bit in the cache managing data corresponding to a cache block at a cache hit, while resetting the footprint bit upon input of a positive responding message through the input/output port connected to the network to a fetch requesting message which has been sent therethrough at a cache miss.
Inventors
- 👤 Hiroaki Hirata
- 👤 Kozo Kimura
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 19:11
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0806; G06F12/084; G06F12/12; G06F12/121; G06F12/126; G06F12/127; G06F12/0813; G06F12/0815
Claims Analysis
Total Claims: 9
Claim 1
Independent Claim
251 words
A cache controller for a multithreading multiprocessor which suspends an ongoing execution of a thread and starts an execution of another thread when a cache miss happens, the cache controller comprising: a directory unit for storing management information indicating data blocks which are loaded from a main memory into a cache, the management information including a thread number field for storing thread reference numbers of threads which use the data blocks in the cache; a data block replacing means for determining a data block having a highest replacing priority among the data blocks in the cache and replacing the data block having the highest replacing priority with a data block in the main memory; an access control unit including a first input/output port and a second input/output port, the first input/output port transmitting and receiving an access requesting message which is one of a write requesting message and a read requesting message to and from said multithreading multiprocessor, and the second input/output port transmitting and receiving the access requesting message to and from the main memory and another cache controller, said access control unit for, on receiving the access requesting message from said multithreading multiprocessor, comparing a received thread reference number included in the received access requesting message with a thread reference number stored in said thread number field, and starting said data block replacing means by lowering a replacing priority of the data block indicated by the received thread reference number in a case where the thread reference numbers match.
Claim 2
Dependent Claim
251 words
A cache controller for a multithreading multiprocessor which suspends an ongoing execution of a thread and starts an execution of another thread when a cache miss happens, the cache controller comprising: a directory unit for storing management information indicating data blocks which are loaded from a main memory into a cache, the management information including a thread number field for storing thread reference numbers of threads which use the data blocks in the cache; a data block replacing means for determining a data block having a highest replacing priority among the data blocks in the cache and replacing the data block having the highest replacing priority with a data block in the main memory; an access control unit including a first input/output port and a second input/output port, the first input/output port transmitting and receiving an access requesting message which is one of a write requesting message and a read requesting message to and from said multithreading multiprocessor, and the second input/output port transmitting and receiving the access requesting message to and from the main memory and another cache controller, said access control unit for, on receiving the access requesting message from said multithreading multiprocessor, comparing a received thread reference number included in the received access requesting message with a thread reference number stored in said thread number field, and starting said data block replacing means by lowering a replacing priority of the data block indicated by the received thread reference number in a case where the thread reference numbers match.
Claim 3
Dependent Claim
104 words
The cache controller of claim 1, wherein said management information further includes footprint bits, each footprint bit being relevant to a corresponding data block in the cache; and said access control unit includes a footprint bit changing means for, on detecting a cache hit, of a specific data block setting a specific footprint bit corresponding to the specific data block, whereas, on detecting a cache miss of the specific data block, starting said data block replacing means by raising the replacing priority of the specific data block and resetting the specific footprint bit when a replacement of the specific data block has been completed.
Claim 4
Dependent Claim
134 words
The cache controller of claim 1, wherein said management information further includes sharing bits, each sharing bit being relevant to a corresponding data block in the cache; and said access control unit further includes a sharing bit changing means for, on detecting a cache hit of a specific data block, comparing a thread reference number stored in said thread number field with the received thread reference number included in the received access requesting message, and resetting the sharing bit in a case where the thread reference numbers do not match, and on detecting a cache miss of a specific data block, starting said data block replacing means by raising a replacing priority of the specific data block, and resetting the specific sharing bit when a replacement of the specific data block has been completed.
Claim 5
Dependent Claim
128 words
The cache controller of claim 1, wherein said management information further includes reservation bits, each reservation bit being relevant to a corresponding data block in the cache; and said access control unit further includes a reservation bit changing means for, on receiving the write requesting message from the processor for a specific data block, setting a specific reservation bit corresponding to the specific data block in a case where a cache hit of the specific data block is detected by retrieving said directory unit, and on detecting a cache miss of the specific data block, starting said data block replacing means by raising a replacing priority of the specific data block and resetting the specific reservation bit when a replacement of the specific data block has been completed.
Claim 6
Dependent Claim
65 words
The cache controller of claim 4, wherein said access control unit further includes a responding message generation unit for outputting a positive responding message upon receipt of the access requesting message from another cache controller through the second input/output port when the specific reservation bit is set, and outputting a negative responding message to the other cache controller when the specific reservation bit is reset.
Claim 7
Dependent Claim
102 words
The cache controller of claim 5, wherein said management information further includes negative bits, each negative bit being relevant to a corresponding data block in the cache; said access control unit further including a negative bit change means for setting a specific negative bit when said responding message generation unit has outputted the negative responding message; and said responding message generation unit outputs an access completion message to the other cache controller which is a sender of the negative responding message if the specific negative bit is set when the reservation bit is transformed from a reset state to a set state.
Claim 8
Dependent Claim
106 words
The cache controller of claim 6, further comprising: a rejection record storage unit for storing information of rejection history by referring data outputted from the access controlling unit; on receiving the negative responding message in response to the access requesting message to the other cache controller, said access control unit stores the negative responding message to said negative history storage unit, and on receiving the access completion message from the other cache controller, retrieves said rejection history storage unit and reoutputs the access requesting message to the other cache controller when said rejection history storage unit has rejection history information corresponding to the access completion message.
Claim 9
Dependent Claim
132 words
The cache controller of claim 1, wherein said management information further includes preservation bits, each preservation bit being relevant to a corresponding data block in the cache; and said access control unit further includes a preservation bit changing means for, on receiving a synchronization requesting message from said multiheading multiprocessor, setting a specific reservation bit in a case where a cache hit of a corresponding specific data block is detected by retrieving said directory unit, and on detecting a cache miss, starting said data block replacing means by raising a replacing priority of the corresponding specific data block, resetting the preservation bit when a replacement of the corresponding specific data block has been completed, and not changing the preservation bit even if an access requesting message is received from said multiheading multiprocessor.
References Cited (Backward Citations)
US4484267A
Cited
US4807110A
Cited
US4885680A
Cited
US4843542A
Cited
US4882642A
Cited
US4928225A
Cited
JPH0289145A
Cited
US5185875A
Cited
JPH0363851A
Cited
US5179702A
Cited
US5297269A
Cited
JPH04288647A
Cited
JPH04315235A
Cited
US5313609A
Cited
US5430850A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-07-09 | 2000-01-08 | 2000-07-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-07-09 | 2004-01-08 | 2004-07-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-07-09 | 2008-01-08 | 2008-07-09 | $7700.00 | Window Closed / Lapsed |