HYBRID ADDRESS MUTEX MECHANISM FOR MEMORY ACCESSES IN A NETWORK PROCESSOR

• US 20120023295A1
• Filed: 09/30/2011
• Published: 01/26/2012
• Est. Priority Date: 05/18/2010
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: LSI Corporation (Broadcom, Inc.)
• Inventors: Nemawarkar, Shashank
• Granted Patent: US 8,843,682 B2
• Time in Patent Office: Days
• US Class Current: 711/130
• CPC Class Codes: G06F 12/0813 with a network or matrix configuration
• CPC Class Codes: H04L 47/621 Individual queue per connection or flow, e.g. per VC
• CPC Class Codes: H04L 47/623 Weighted service order
• CPC Class Codes: H04L 49/00 Packet switching elements
• CPC Class Codes: H04L 49/101 using crossbar or matrix
• CPC Class Codes: H04L 49/109 Integrated on microchip, e.g. switch-on-chip
• CPC Class Codes: H04L 49/1546 using pipelined operation
• CPC Class Codes: H04L 49/506 Backpressure

Abstract

Described embodiments provide arbitration for a cache of a network processor. Processing modules of the network processor generate memory access requests including a requested address and an ID value corresponding to the requesting processing module. Each request is either a locked request or a simple request. An arbiter determines whether the received requests are locked requests. For each locked request, the arbiter determines whether two or more of the requests are conflicted based on the requested address of each received memory requests. If one or more of the requests are non-conflicted, the arbiter determines, for each non-conflicted request, whether the requested addresses are locked out by prior memory requests based on a lock table. If one or more of the non-conflicted memory requests are locked-out by prior memory requests, the arbiter queues the locked-out memory requests. The arbiter grants any non-conflicted memory access requests that are not locked-out.

Claims

1. A method of arbitrating access to a level one (L1) cache of a network processor having a plurality of processing modules and at least one shared memory, the method comprising:

generating, by one or more processing modules of the network processor, one or more memory access requests, each memory access request comprising a requested address and an ID value corresponding to the requesting processing module, wherein each memory access request comprises one of a locked access request and one or more simple access requests;

determining, by an address mutually exclusive (mutex) arbiter of the network processor, whether one or more received memory access requests are simple access requests or locked access requests, wherein, for each locked access request, the address mutex arbiter performs the steps of;

determining, by the address mutex arbiter, whether two or more of the memory access requests are either conflicted or non-conflicted based on the requested address of each of the one or more memory access requests;

if one or more of the memory access requests are non-conflicted, determining, by the address mutex arbiter, for each non-conflicted memory access request, whether the requested address of each non-conflicted memory access request is locked out by one or more prior memory access requests based on a lock table of the address mutex arbiter;

if one or more of the non-conflicted memory access requests are locked-out by one or more prior memory access requests;

queuing, by the address mutex arbiter, one or more locked-out memory requests;

granting one or more non-conflicted memory access requests that are not locked-out;

updating the lock table corresponding to the requested addresses associated with the one or more granted memory access requests.

2. The method of claim 1, further comprising:

if one or more of the memory access requests are conflicted, determining, by the address mutex arbiter, a priority value associated with each conflicted memory access request;

determining, by the address mutex arbiter, for a conflicted memory access request having a relative highest priority value for each given requested memory address, whether one or more of the requested addresses are locked out by one or more prior memory access requests based on a lock table of the address mutex arbiter;

if one or more of the requested addresses are locked-out by one or more prior memory access requests;

queuing, by the address mutex arbiter, one or more locked-out memory requests;

granting one or more memory access requests that are not locked-out; and

updating the lock table corresponding to the requested addresses associated with the one or more granted memory access requests.

3. The method of claim 2, further comprising:

receiving, by the address mutex arbiter, a lock release request from a requesting one of one or more processing modules of the network processor, wherein the release request comprises a memory address and the ID value corresponding to the requesting processing module;

updating the lock table corresponding to the memory address of the lock release request; and

allowing access to the memory address by one or more subsequent memory access requests.

4. The method of claim 3, further comprising:

determining whether one or more memory access requests are queued for access to the memory address of the lock release request, and if so;

determining whether the one or more queued memory access requests correspond to the same ID value as the release request, and if so;

if any of the one or more queued memory access requests correspond to a different ID value than the release request, determining a priority value of each of the one or more queued memory access requests.

5. The method of claim 4, further comprising:

granting, based on the determined priority values, access to a queued memory access request having a relative next highest priority value and corresponding to a different ID value than the release request, thereby preventing one or more consecutive access requests corresponding to a single ID value.

6. The method of claim 4, further comprising:

if all of the one or more queued memory access requests correspond to the same ID value as the release request, granting access to a next memory access in the queue.

7. The method of claim 1, further comprising:

for each simple memory access request;

providing, by the address mutex arbiter, each simple memory access request to a corresponding one of one or more simple arbiters of the network processor.

8. The method of claim 7, wherein each of the one or more simple arbiters are dedicated for arbitration of a given one of a plurality of types of memory access requests.

9. The method of claim 8, wherein the type of memory access request is one of a simple read request, a simple write request, a memory allocation request, and a level-one cache operation.

10. The method of claim 7, wherein the one or more simple arbiters perform one of strict priority and round robin arbitration.

11. The method of claim A, wherein each locked access request is one of a locked read request and a locked write request.

12. The method of claim A, further comprising:

loading, from the at least one shared memory to the L1 cache, data corresponding to the memory access request.

13. A non-transitory machine-readable medium, having encoded thereon program code, wherein, when the program code is executed by a machine, the machine implements a method of arbitrating access to a level one (L1) cache of a network processor having a plurality of processing modules and at least one shared memory, the method comprising:

generating, by one or more processing modules of the network processor, one or more memory access requests, each memory access request comprising a requested address and an ID value corresponding to the requesting processing module, wherein each memory access request comprises one of a locked access request and one or more simple access requests;

determining, by an address mutually exclusive (mutex) arbiter of the network processor, whether one or more received memory access requests are simple access requests or locked access requests, wherein, for each locked access request, the address mutex arbiter performs the steps of;

determining, by the address mutex arbiter, whether two or more of the memory access requests are either conflicted or non-conflicted based on the requested address of each of the one or more memory access requests;

if one or more of the memory access requests are non-conflicted, determining, by the address mutex arbiter, for each non-conflicted memory access request, whether the requested address of each non-conflicted memory access request is locked out by one or more prior memory access requests based on a lock table of the address mutex arbiter;

if one or more of the non-conflicted memory access requests are locked-out by one or more prior memory access requests;

queuing, by the address mutex arbiter, one or more locked-out memory requests;

granting one or more non-conflicted memory access requests that are not locked-out;

updating the lock table corresponding to the requested addresses associated with the one or more granted memory access requests.

14. The non-transitory machine-readable medium of claim 13, further comprising:

if one or more of the memory access requests are conflicted, determining, by the address mutex arbiter, a priority value associated with each conflicted memory access request;

determining, by the address mutex arbiter, for a conflicted memory access request having a relative highest priority value for each given requested memory address, whether one or more of the requested addresses are locked out by one or more prior memory access requests based on a lock table of the address mutex arbiter;

if one or more of the requested addresses are locked-out by one or more prior memory access requests;

queuing, by the address mutex arbiter, one or more locked-out memory requests;

granting one or more memory access requests that are not locked-out; and

updating the lock table corresponding to the requested addresses associated with the one or more granted memory access requests.

15. The non-transitory machine-readable medium of claim 14, further comprising:

receiving, by the address mutex arbiter, a lock release request from a requesting one of one or more processing modules of the network processor, wherein the release request comprises a memory address and the ID value corresponding to the requesting processing module;

updating the lock table corresponding to the memory address of the lock release request; and

allowing access to the memory address by one or more subsequent memory access requests.

16. The non-transitory machine-readable medium of claim 15, further comprising:

determining whether one or more memory access requests are queued for access to the memory address of the lock release request, and if so;

determining whether the one or more queued memory access requests correspond to the same ID value as the release request, and if so;

if any of the one or more queued memory access requests correspond to a different ID value than the release request, determining a priority value of each of the one or more queued memory access requests.

17. The non-transitory machine-readable medium of claim 16, further comprising:

granting, based on the determined priority values, access to a queued memory access request having a relative next highest priority value and corresponding to a different ID value than the release request, thereby preventing one or more consecutive access requests corresponding to a single ID value.

18. The non-transitory machine-readable medium of claim 17, further comprising:

if all of the one or more queued memory access requests correspond to the same ID value as the release request, granting access to a next memory access in the queue.

19. A network processor comprising:

a plurality of processing modules, at least one level one (L1) cache, and at least one shared memory, wherein one or more of the plurality of processing modules are configured to generate one or more memory access requests, each memory access request comprising a requested address and an ID value corresponding to the requesting processing module, wherein each memory access request comprises one of a locked access request and one or more simple access requests;

an address mutually exclusive (mutex) arbiter configured to arbitrate access to the L1 cache, wherein the address mutex arbiter is further configured to;

determine whether one or more received memory access requests are simple access requests or locked access requests, wherein, for each locked access request, the address mutex arbiter is configured to;

determine whether two or more of the memory access requests are either conflicted or non-conflicted based on the requested address of each of the one or more memory access requests;

if one or more of the memory access requests are non-conflicted;

determine, for each non-conflicted memory access request, whether the requested address of each non-conflicted memory access request is locked out by one or more prior memory access requests based on a lock table of the address mutex arbiter;

if one or more of the non-conflicted memory access requests are locked-out by one or more prior memory access requests;

queue the one or more locked-out memory requests;

grant one or more non-conflicted memory access requests that are not locked-out; and

update the lock table corresponding to the requested addresses associated with the one or more granted memory access requests.

20. The network processor of claim 19, wherein the one or more one or more processing modules comprise at least one of:

control processors comprising Reduced Instruction Set Computing (RISC) central processing units (CPUs) and hardware accelerators and wherein the at least one shared memory comprises at least one of an embedded DRAM and a double data rate (DDR) DRAM coupled to the network processor and wherein the network processor is implemented as an integrated circuit chip.