Method and apparatus for resolving write and read conflicts between memory modules accessing blocks of a memory

• US 8,788,729 B1
• Filed: 05/17/2013
• Issued: 07/22/2014
• Est. Priority Date: 06/12/2003
• Status: Active Grant

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: Marvell International Limited (Marvell Technology Group Limited)
• Inventors: Zheng, Hongming, Gadepalli, Gangadhar
• Primary Examiner(s): Tsai, Henry
• Assistant Examiner(s): Hassan, Aurangzeb
• Application Number:
  US13/896,869
• Time in Patent Office: 431 Days
• Field of Search: None
• US Class Current: 710/52
• CPC Class Codes: G06F 3/0656 Data buffering arrangements
• CPC Class Codes: G06F 5/10 having a sequence of storage locations each being individually accessible for both enqueue and dequeue operations, e.g. using random access memory G06F5/065 takes precedence
• CPC Class Codes: G06F 5/12 Means for monitoring the fill level; Means for resolving contention, i.e. conflicts between simultaneous enqueue and dequeue operations

Abstract

A system includes a memory that stores and outputs data in a first-in-first-out order. A sequence generator generates a sequence of first values, and randomly assigns the first values to blocks of the memory. A first memory module, based on the sequence of first values, accesses a first block of the memory. A conflict module, in response to a write or read conflict existing between the first and second memory modules due to the first memory module accessing the first block, resolves the write or read conflict. The conflict module resolves the write or read conflict by reading a value from the first block, and based on the value, either (i) causing the first memory module to write to a second block of the memory instead of the first block, or (ii) preventing the first memory module from reading from the first block.

Claims

1. A system comprising:

a memory configured to store and output data in a first-in-first-out order;

a sequence generator configured to (i) generate a sequence of first values, and (ii) randomly assign the first values to blocks of the memory;

a first memory module configured to, based on the sequence of first values, access a first block of the memory; and

a conflict module configured to

based on the sequence of first values and prior to the first memory module writing to or reading from the first block of the memory, read a value from the first block of the memory,

based on the value read from the first block of the memory, determine whether a write conflict or a read conflict exists between the first memory module and a second memory module for the first block of the memory, and

in response to the write conflict or the read conflict existing between the first memory module and the second memory module, either resolve (i) the write conflict causing the first memory module to write to a second block of the memory instead of the first block of the memory, or (ii) the read conflict by preventing the first memory module from reading from the first block of the memory.

2. The system of claim 1, wherein:

the value read from the first block of the memory identifies the second memory module; and

the conflict module is configured to, based on the value read from the first block of the memory, cause the first memory module to write to the second block of the memory instead of the first block of the memory.

3. The system of claim 1, wherein the conflict module is configured to (i) determine whether the value read from the first block of the memory is a predetermined value, and (ii) based on whether the value read from the first block of the memory is the predetermined value, permit the first memory module to write to the first block of the memory.

4. The system of claim 1, wherein:

the conflict module is configured to, in response to the value identifying the first memory module, (i) permit the first memory module to read from the first block of the memory, and (ii) prevent the second memory module from reading from the first block of the memory; and

the conflict module is configured to, in response to the value identifying the second memory module, (i) permit the second memory module to read from the first block of the memory, and (ii) prevent the first memory module from reading from the first block of the memory.

5. The system of claim 1, further comprising the second memory module, wherein:

the sequence generator is configured to (i) generate a sequence of second values, and (ii) randomly assign the second values to the blocks of the memory; and

the second memory module is configured to access the first block of the memory based on the sequence of second values,

wherein the conflict module is configured to, based on the value read from the first block of the memory, permit the second memory module to one of write to or read from the first block of the memory.

6. The system of claim 5, wherein:

the first values include a same set of values as the second values; and

the sequence generator is configured to randomly assign the second values to the blocks of the memory in a different order than the first values.

7. The system of claim 1, further comprising:

a first access module configured to store a first block identifier;

a second access module configured to store a second block identifier; and

the second memory module (i) writes data to or reads data from the first block of the memory according to the first block identifier, and (ii) writes data to or reads data from a third block of the memory according to the second block identifier.

8. The system of claim 1, further comprising a verifier module configured to determine whether a block of the memory corresponding to a first block identifier is being used by the second memory module, wherein:

the sequence generator is configured to randomly generate the first block identifier; and

the conflict module is configured to, if the block of the memory corresponding to the first block identifier is not being used by the second memory module, permit the first memory module to access the block of the memory corresponding to the first block identifier.

9. The system of claim 8, wherein:

the sequence generator is configured to, if the block of the memory corresponding to the first block identifier is being used by the second memory module, randomly generate a second block identifier; and

the conflict module is configured to, if the block of the memory corresponding to the second block identifier is not being used by the second memory module, write in the block of the memory corresponding to the second block identifier (i) an identifier number of the first memory module, and (ii) a counter value of the sequence of the first values.

10. The system of claim 1, wherein:

the sequence generator is configured to generate the sequence of first values based on a Fibonacci sequence; and

the Fibonacci sequence is based on (i) a first identifier of an initial value of the sequence of first values, and (ii) a second identifier of a length of the sequence of first values.

21. The system of claim 1, wherein the first memory module is configured to minimize conflicts between the first memory module and the second memory module by accessing (i) the first block of the memory based on the sequence of values, and (ii) the second block of the memory based on the sequence of values.

22. The system of claim 1, wherein:

if the value read from the first block of the memory is a predetermined value, the conflict module is configured to (i) determine no conflict exists between the first memory module and the second memory module, and (ii) permit the first memory module access to the first block of the memory; and

if the value read from the first block of the memory is not the predetermined value, the conflict module is configured to (i) determine a conflict exists between the first memory module and the second memory module, and (ii) prevent the first memory module from accessing the first block of the memory.

11. A method comprising:

generating a sequence of first values;

randomly assigning the first values to blocks of a memory, wherein the memory is configured to store and output data in a first-in-first-out order;

based on the sequence of first values and prior to a first memory module writing to or reading from a first block of the memory, read a value from the first block of the memory via a conflict module, wherein the first memory module is configured to access the first block of the memory based on the sequence of first values;

based on the value read from the first block of the memory, determine whether a write conflict or a read conflict exists between the first memory module and a second memory module for the first block of the memory; and

in response to the write conflict or the read conflict existing between the first memory module and the second memory module, either resolving (i) the write conflict causing the first memory module to write to a second block of the memory instead of the first block of the memory, or (ii) the read conflict by preventing the first memory module from reading from the first block of the memory.

12. The method of claim 11, further comprising, based on the value read from the first block of the memory, causing the first memory module to write to the second block of the memory instead of the first block of the memory,

wherein the value read from the first block of the memory identifies the second memory module.

13. The method of claim 11, further comprising:

determining whether the value read from the first block of the memory is a predetermined value; and

based on whether the value read from the first block of the memory is the predetermined value, permitting the first memory module to write to the first block of the memory.

14. The method of claim 11, further comprising:

in response to the value identifying the first memory module, (i) permitting the first memory module to read from the first block of the memory, and (ii) preventing the second memory module from reading from the first block of the memory; and

in response to the value identifying the second memory module, (i) permitting the second memory module to read from the first block of the memory, and (ii) preventing the first memory module from reading from the first block of the memory.

15. The method of claim 11, further comprising:

generating a sequence of second values;

randomly assigning the second values to the blocks of the memory;

based on the sequence of second values, accessing the first block of the memory via the second memory module; and

based on the value read from the first block of the memory, permitting the second memory module to one of write to or read from the first block of the memory.

16. The method of claim 15, further comprising randomly assigning the second values to the blocks of the memory in a different order than the first values,

wherein the first values include a same set of values as the second values.

17. The method of claim 11, further comprising:

storing a first block identifier via a first access module;

storing a second block identifier via a second access module;

writing data to or reading data from the first block of the memory according to the first block identifier via the second memory module; and

writing data to or reading data from a third block of the memory according to the second block identifier via the second memory module.

18. The method of claim 11, further comprising:

randomly generating a first block identifier;

determining whether a block of the memory corresponding to the first block identifier is being used by the second memory module; and

if the block of the memory corresponding to the first block identifier is not being used by the second memory module, permitting the first memory module to access the block of the memory corresponding to the first block identifier.

19. The method of claim 18, further comprising:

if the block of the memory corresponding to the first block identifier is being used by the second memory module, randomly generating a second block identifier; and

if the block of the memory corresponding to the second block identifier is not being used by the second memory module, writing in the block of the memory corresponding to the second block identifier (i) an identifier number of the first memory module, and (ii) a counter value of the sequence of the first values.

20. The method of claim 11, further comprising generating the sequence of first values based on a Fibonacci sequence, wherein the Fibonacci sequence is based on (i) a first identifier of an initial value of the sequence of first values, and (ii) a second identifier of a length of the sequence of first values.