Exclusion monitors

• US 10,120,732 B1
• Filed: 04/27/2017
• Issued: 11/06/2018
• Est. Priority Date: 04/27/2017
• Status: Active Grant

• Current Assignee: Friday Harbor LLC
• Original Assignee: Friday Harbor LLC
• Inventors: Lopez, Ricardo Jorge, Hilton, Robert N.
• Primary Examiner(s): Bragdon, Reginald G
• Assistant Examiner(s): Wang, Edward
• Application Number:
  US15/499,796
• Publication Number:
  US 20180314567A1
• Time in Patent Office: 558 Days
• CPC Class Codes: G06F 15/7807 System on chip, i.e. computer system on a single chip; System in package, i.e. computer system on one or more chips in a single package
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0653 Monitoring storage devices or systems
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

Systems, devices, and techniques for processor synchronization are described. A described system includes exclusion monitor circuitry, a content addressable memory (CAM) coupled with the exclusion monitor circuitry, and processors coupled with the exclusion monitor circuitry. The processors can perform synchronization via the exclusion monitor circuitry using an identifier tag. The exclusion monitor circuitry can utilize the CAM to store information for handling one or more named mutual exclusions. The exclusion monitor circuitry and the CAM can be configured to concurrently handle multiple identifier tags that correspond to different mutual exclusions.

Claims

1. An apparatus comprising:

exclusion monitor circuitry;

a content addressable memory (CAM) coupled with the exclusion monitor circuitry, wherein the CAM is configured to store CAM entries, wherein a CAM entry of the CAM entries comprises a CAM tag and a release register; and

processors coupled with the exclusion monitor circuitry, wherein the processors perform synchronization via the exclusion monitor circuitry using an identifier tag,

wherein a first processor of the processors is configured to send a release request to the exclusion monitor circuitry, the release request comprising the identifier tag,

wherein, in response to receiving the release request, the exclusion monitor circuitry is configured to perform a first lookup in the CAM based on the identifier tag of the release request,

wherein the exclusion monitor circuitry is configured to, based on the first lookup missing in the CAM, write the identifier tag of the release request as the CAM tag in the CAM entry, mark the CAM entry as valid, write a processor identifier of the first processor in the release register of the CAM entry, and cause the first processor to enter a stalled state,

wherein a second processor of the processors is configured to send an acquire request to the exclusion monitor circuitry, the acquire request comprising the identifier tag,

wherein, in response to receiving the acquire request, the exclusion monitor circuitry is configured to perform a second lookup in the CAM based on the identifier tag of the acquire request, and

wherein the exclusion monitor circuitry is configured to, based on the second lookup hitting in the CAM, issue a grant to the second processor and release the first processor from the stalled state using the processor identifier stored in the release register of the CAM entry.

2. The apparatus of claim 1, wherein the exclusion monitor circuitry is configured to release the first processor from the stalled state by sending a retry command to the first processor, wherein the first processor sends an additional release request comprising the identifier tag in response to the retry command that causes the exclusion monitor circuitry to invalidate the CAM entry.

3. The apparatus of claim 1, wherein the stalled state causes the first processor to sleep such that a program counter associated with the second processor does not advance.

4. The apparatus of claim 1, wherein the exclusion monitor circuitry is configured to cause the second processor to enter the stalled state based on the i) second processor sending an additional acquire request comprising the identifier tag and ii) the identifier tag of the additional acquire request matching the CAM tag in the CAM entry.

5. The apparatus of claim 4, wherein the first processor sends an additional release request comprising the identifier tag, wherein the additional release request causes the exclusion monitor circuitry to release the second processor from the stalled state.

6. A method for performing synchronization between processors, comprising:

sending, by a first processor, a release request to exclusion monitor circuitry, wherein the release request comprises an identifier tag;

performing, by the exclusion monitor circuitry in response to receiving the release request, a first lookup in a content addressable memory (CAM) based on the identifier tag of the release request;

operating the exclusion monitor circuitry, based on the first lookup missing in the CAM, to write the identifier tag of the release request as a CAM tag in a CAM entry of the CAM, mark the CAM entry as valid, write a processor identifier of the first processor in a release register of the CAM entry, and cause the first processor to enter a stalled state;

sending, by a second processor, an acquire request to the exclusion monitor circuitry, wherein the acquire request comprises the identifier tag;

performing, by the exclusion monitor circuitry, a second lookup in the CAM based on the identifier tag of the acquire request; and

operating the exclusion monitor circuitry, based on the second lookup hitting in the CAM, to issue a grant to the second processor, and to release the first processor from the stalled state using the processor identifier stored in the release register of the CAM entry.

7. The method of claim 6, wherein operating the exclusion monitor circuitry to release the first processor from the stalled state comprises sending a retry command to the first processor, the method further comprising:

operating the first processor to send an additional release request comprising the identifier tag in response to the retry command that causes the exclusion monitor circuitry to invalidate the CAM entry.

8. The method of claim 6, wherein the stalled state causes the first processor to sleep such that a program counter associated with the second processor does not advance.

9. The method of claim 6, comprising:

operating the second processor to send an additional acquire request comprising the identifier tag; and

operating the exclusion monitor circuitry to cause the second processor to enter the stalled state based on i) a receipt of the additional acquire request and ii) the identifier tag of the additional acquire request matching the CAM tag in the CAM entry.

10. The method of claim 9, comprising:

operating the first processor to send an additional release request comprising the identifier tag; and

operating the exclusion monitor circuitry to release the second processor from the stalled state in response to a receipt of the additional release request.