Inclusion monitors

• US 10,133,512 B1
• Filed: 04/27/2017
• Issued: 11/20/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,773
• Publication Number:
  US 20180314460A1
• Time in Patent Office: 572 Days
• CPC Class Codes: G06F 15/76 Architectures of general purpose stored program computers with program plugboard G06F15/08; multicomputers G06F15/16
• 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

Abstract

Systems, devices, and techniques for processor synchronization are described. A described system includes sending, from first processors, release requests to an inclusion monitor, the release requests including an identifier tag; sending, from a second processor, an acquire request to the inclusion monitor circuitry, the acquire request including a weight value and the identifier tag; creating a content addressable memory (CAM) entry based on a receipt of at least one of the release or acquire requests; maintaining a count of the release requests that correspond to the identifier tag by using the entry'"'"'s arrival counter; causing the first processors to stall if the entry'"'"'s arrival counter does not satisfy a threshold criterion specified by the entry'"'"'s weight value or if the acquire request has not been received; storing the acquire request'"'"'s weight value as the entry'"'"'s weight value; and releasing the first processors if the entry'"'"'s arrival counter satisfies the criterion.

Claims

1. An apparatus comprising:

inclusion monitor circuitry;

a content addressable memory (CAM) coupled with the inclusion monitor circuitry;

a first processor configured to send a first release request to the inclusion monitor circuitry, wherein the first release request comprises an identifier tag;

a second processor configured to send a second release request to the inclusion monitor circuitry, wherein the second release request comprises the identifier tag; and

a third processor configured to send an acquire request to the inclusion monitor circuitry, wherein the acquire request comprises the identifier tag and a weight value,

wherein the inclusion monitor circuitry is configured to create a CAM entry in the CAM based on receiving the first release request, the second release request, or the acquire request, and use the identifier tag as a tag of the CAM entry,

wherein the inclusion monitor circuitry, in response to receiving the first release request, is configured to perform a first lookup in the CAM based on the identifier tag of the first release request, increment an arrival counter of the CAM entry, and cause the first processor to enter a stalled state based on (i) a first determination that the arrival counter of the CAM entry does not satisfy a threshold criterion specified by a weight value of the CAM entry or (ii) a first determination that the acquire request has not yet been received by the inclusion monitor circuitry, and

wherein the inclusion monitor circuitry, in response to receiving the second release request, is configured to perform a second lookup in the CAM based on the identifier tag of the second release request, increment the arrival counter of the CAM entry, and cause the second processor to enter the stalled state based on (i) a second determination that the arrival counter of the CAM entry does not satisfy the threshold criterion specified by the weight value of the CAM entry or (ii) a second determination that the acquire request has not yet been received by the inclusion monitor circuitry, and

wherein the inclusion monitor circuitry, in response to receiving the acquire request, is configured to perform a third lookup in the CAM based on the identifier tag of the acquire request, store the weight value of the acquire request as the weight value of the CAM entry, and release the first processor and the second processor from the stalled state based on a determination that the arrival counter of the CAM entry does satisfy the threshold criterion.

2. The apparatus of claim 1, wherein the inclusion monitor circuitry is configured to invalidate the CAM entry based on the determination that the arrival counter of the CAM entry does satisfy the threshold criterion.

3. The apparatus of claim 2, wherein the third processor is configured to send an additional acquire request to the inclusion monitor circuitry, the additional acquire request comprising the identifier tag, and wherein the inclusion monitor circuitry is configured to perform an additional lookup in the CAM based on a receipt of the additional acquire request and create a new CAM entry in the CAM based on the additional lookup missing in the CAM.

4. The apparatus of claim 1, wherein the first determination that the arrival counter of the CAM entry does not satisfy the threshold criterion specified by the weight value of the CAM entry comprises (i) a determination that the weight value of the CAM entry is greater than zero, and (ii) a determination that the arrival counter is less than the weight value of the CAM entry.

5. The apparatus of claim 1, wherein the inclusion monitor circuitry is configured to store a processor identifier of the first processor in a register of the CAM entry, wherein the inclusion monitor circuitry is configured to release the first processor from the stalled state by sending a command to the first processor, wherein the command is addressed based on the processor identifier stored in the register in the CAM entry.

6. The apparatus of claim 1, wherein the inclusion monitor circuitry, the CAM, and the processors are formed within a system-on-a-chip.

7. The apparatus of claim 1, wherein the first processor comprises the third processor.

8. A method comprising:

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

sending, from a second processor, a second release request to the inclusion monitor circuitry, wherein the second release request comprises the identifier tag;

sending, from a third processor, an acquire request to the inclusion monitor circuitry, wherein the acquire request comprises a weight value and the identifier tag;

creating, in a content addressable memory (CAM) by the inclusion monitor circuitry, a CAM entry based on a receipt of the first release request, the second release request, or the acquire request, wherein creating the CAM entry comprises using the identifier tag as a tag of the CAM entry;

incrementing, in response to receiving the first release request, an arrival counter of the CAM entry;

causing the first processor to enter a stalled state based on (i) a first determination that the arrival counter of the CAM entry does not satisfy a threshold criterion specified by a weight value of the CAM entry or (ii) a first determination that the acquire request has not yet been received by the inclusion monitor circuitry;

incrementing, in response to receiving the second release request, the arrival counter of the CAM entry;

causing the second processor to enter the stalled state based on (i) a second determination that the arrival counter of the CAM entry does not satisfy the threshold criterion specified by the weight value of the CAM entry or (ii) a second determination that the acquire request has not yet been received by the inclusion monitor circuitry;

storing, in response to receiving the acquire request, the weight value of the acquire request as the weight value of the CAM entry; and

releasing the first processor and the second processor from the stalled state based on a determination that the arrival counter of the CAM entry does satisfy the threshold criterion.

9. The method of claim 8, comprising:

operating the inclusion monitor circuitry to invalidate the CAM entry based on the determination that the arrival counter of the CAM entry does satisfy the threshold criterion.

10. The method of claim 9, comprising:

operating the third processor to send an additional acquire request to the inclusion monitor circuitry, the additional acquire request comprising the identifier tag;

performing an additional lookup in the CAM based on a receipt of the additional acquire request by the inclusion monitor circuitry; and

creating a new CAM entry in the CAM based on the additional lookup missing in the CAM.

11. The method of claim 8, wherein the first determination that the arrival counter of the CAM entry does not satisfy the threshold criterion specified by the weight value of the CAM entry comprises (i) a determination that the weight value of the CAM entry is greater than zero, and (ii) a determination that the arrival counter is less than the weight value of the CAM entry.

12. The method of claim 8, comprising:

storing a processor identifier of the first processor in a register of the CAM entry,

wherein the releasing comprises sending a command to the first processor, and wherein the command is addressed based on the processor identifier stored in the register.

13. The method of claim 8, wherein the first processor comprises the third processor.

14. A system comprising:

inclusion monitor circuitry comprising a controller and a content addressable memory (CAM) configured to store a plurality of CAM entries; and

processors to perform synchronization via the inclusion monitor circuitry using an identifier tag, wherein first processors of the processors are configured to respectively send release requests to the controller, the release requests comprising the identifier tag, wherein a second processor of the processors is configured to send an acquire request to the controller, the acquire request comprising a weight value and the identifier tag,

wherein the controller is configured to mark a CAM entry of the CAM entries as valid based on receiving at least one of the release requests or the acquire request, and write the identifier tag of the at least one of the release requests or the acquire request as a tag of the CAM entry,

wherein the controller is configured to perform first lookups in the CAM based on the identifier tag of the release requests, maintain a count of the release requests that correspond to the identifier tag by using an arrival counter of the CAM entry, and cause the first processors to enter a stalled state based on a determination that the arrival counter of the CAM entry does not satisfy a threshold criterion specified by a weight value of the CAM entry or a determination that the acquire request has not yet been received by the controller, and

wherein the controller is configured to perform a second lookup in the CAM based on the identifier tag of the acquire request, store the weight value of the acquire request as the weight value of the CAM entry, and release the first processors from the stalled state based on a determination that the arrival counter of the CAM entry does satisfy the threshold criterion.

15. The system of claim 14, wherein the determination that the arrival counter of the CAM entry does not satisfy the threshold criterion specified by the weight value of the CAM entry comprises (i) a determination that the weight value of the CAM entry is greater than zero, and (ii) a determination that the arrival counter is less than the weight value of the CAM entry.

16. The system of claim 14, wherein the controller is configured to invalidate the CAM entry based on the determination that the arrival counter of the CAM entry does satisfy the threshold criterion.

17. The system of claim 16, wherein the second processor is configured to send an additional acquire request to the controller, the additional acquire request comprising the identifier tag, and wherein the controller is configured to perform an additional lookup in the CAM based on a receipt of the additional acquire request and create a new CAM entry in the CAM based on the additional lookup missing in the CAM.

18. The system of claim 14, wherein the controller is configured to store processor identifiers of the first processors in a register of the CAM entry, and wherein the controller is configured to release the first processors from the stalled state by sending commands to the first processors, wherein the commands are addressed based on the processor identifiers stored in the register in the CAM entry.

19. The system of claim 14, wherein the first processors comprise the second processor.

20. The system of claim 14, wherein the inclusion monitor circuitry and the processors are formed within a system-on-a-chip.