Adaptive multiple FIFO scheme

• US 8,447,900 B1
• Filed: 06/12/2003
• Issued: 05/21/2013
• 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:
  US10/459,798
• Time in Patent Office: 3,631 Days
• Field of Search: 710/20, 710/52, 709/212, 709/215, 709/2, 370/318, 370/441
• 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 first in, first out (FIFO) buffer system includes memory with a plurality of memory blocks. A first FIFO control module generates and assigns a first random sequence to the memory blocks and stores first data in the memory blocks according to the first random sequence. A second FIFO control module generates and assigns a second random sequence to the memory blocks that is different than the first random sequence and stores second data in the memory blocks according to the second random sequence.

Claims

1. A first in, first out (FIFO) buffer system, comprising:

memory that includes a plurality of contiguous memory blocks;

a first FIFO control module that generates a first random sequence and stores first data in said memory blocks according to said first random sequence; and

a second FIFO control module that generates a second random sequence that is different than said first random sequence and stores second data in said memory blocks according to said second random sequence.

2. The FIFO buffer system of claim 1 wherein said first and second FIFO control modules are capable of storing data in all of said memory blocks.

3. The FIFO buffer system of claim 1 wherein said first FIFO control module retrieves said first data from said memory blocks using said first random sequence and said second FIFO control module retrieves said second data from said memory blocks using said second random sequence.

4. The FIFO buffer system of claim 1 further comprising:

a check block module that stores a potential write block identifier; and

a block verifier that communicates with said check block module and said memory and determines availability of a memory block corresponding to said potential write block identifier.

5. The FIFO buffer system of claim 4 wherein said block verifier determines whether said memory block corresponding to said potential write block identifier has one of a used status and a not used status and sends a status signal to said check block module.

6. The FIFO buffer system of claim 5 wherein said FIFO control module sets a current write block identifier equal to a next write block identifier and said next write block identifier equal to said potential write block identifier when said memory block corresponding to said potential write block identifier has said not used status.

7. The FIFO buffer system of claim 1 wherein said FIFO control module outputs a FIFO number and a sequence count when writing to one of said memory blocks.

8. The FIFO buffer system of claim 4 wherein said check block module stores a potential read block identifier.

9. The FIFO buffer system of claim 8 wherein said block verifier determines whether a memory block corresponding to said potential read block identifier has a FIFO number that matches said first FIFO control module.

10. The FIFO buffer system of claim 9 wherein said first FIFO control module sets a current read block identifier equal to a next read block identifier and said next read block identifier equal to said potential read block identifier when said match occurs.

11. The FIFO buffer system of claim 10 wherein said first FIFO control module includes a read counter that compares a read block count to a sequence count stored in said memory block corresponding to said current read block identifier.

12. The FIFO buffer system of claim 1 further comprising a FIFO access arbiter module that communicates with said first and second FIFO control modules and said memory, wherein said FIFO access arbiter module stores said first data and said second data to and extracts said first data and said second data from said plurality of memory blocks.

13. The FIFO buffer system of claim 1 wherein said first FIFO control module generates said first random sequence using a first Fibonacci sequence that is based on a first tap value and a first initialization value.

14. The FIFO buffer system of claim 13 wherein said second FIFO control module generates said second random sequence using a second Fibonacci sequence that is based on a second tap value and a second initialization value, which are different than said first tap value and said first initialization value.

15. The FIFO buffer system of claim 1 wherein said first FIFO control module receives said first data from a first communications channel and said second FIFO control module receives said second data from a second communications channel.

16. The FIFO buffer system of claim 1 wherein said FIFO buffer system is implemented in one of a network switch and a network router.

48. The system of claim 1 wherein said first random sequence is substantially orthogonal to said second random sequence.

49. The system of claim 1 wherein said first random sequence includes values used to assign said first data to said memory blocks and said second random sequence includes values used to assign said second data to said memory blocks.

17. A first in, first out (FIFO) buffer system, comprising:

memory means for storing data and including a plurality of contiguous memory blocks;

first FIFO control means for generating a first random sequence and for storing first data in said memory blocks according to said first random sequence; and

second FIFO control means for generating a second random sequence that is different than said first random sequence and for storing second data in said memory blocks according to said second random sequence.

18. The FIFO buffer system of claim 17 wherein said first and second FIFO control means are capable of storing data in all of said memory blocks.

19. The FIFO buffer system of claim 17 wherein said first FIFO control means retrieves said first data from said memory blocks using said first random sequence and said second FIFO control means retrieves said second data from said memory blocks using said second random sequence.

20. The FIFO buffer system of claim 17 further comprising:

check block means for storing a potential write block identifier; and

block verifying means for communicating with said check block means and said memory and for determining availability of a memory block corresponding to said potential write block identifier.

21. The FIFO buffer system of claim 20 wherein said block verifying means determines whether said memory block corresponding to said potential write block identifier has one of a used status and a not used status and sends a status signal to said check block means.

22. The FIFO buffer system of claim 21 wherein said FIFO control means sets a current write block equal identifier to a next write block identifier and said next write block identifier equal to said potential write block identifier when said memory block corresponding to said potential write block identifier has said not used status.

23. The FIFO buffer system of claim 17 wherein said FIFO control means outputs a FIFO number and a sequence count when writing to one of said memory blocks.

24. The FIFO buffer system of claim 20 wherein said check block means stores a potential read block identifier.

25. The FIFO buffer system of claim 24 wherein said block verifying means determines whether a memory block corresponding to said potential read block identifier has a FIFO number that matches said first FIFO control means.

26. The FIFO buffer system of claim 25 wherein said first FIFO control means sets a current read block identifier equal to a next read block identifier and said next read block identifier equal to said potential read block identifier when said match occurs.

27. The FIFO buffer system of claim 26 wherein said first FIFO control means includes read counting means for comparing a read block count to a sequence count stored in said memory block corresponding to said current read block identifier.

28. The FIFO buffer system of claim 17 further comprising a FIFO access arbiter means that communicates with said first and second FIFO control means and said memory, wherein said FIFO access arbiter means stores said first data and said second data to and extracts said first data and said second data from said plurality of memory blocks.

29. The FIFO buffer system of claim 17 wherein said first FIFO control means generates said first random sequence using a first Fibonacci sequence that is based on a first tap value and a first initialization value.

30. The FIFO buffer system of claim 29 wherein said second FIFO control means generates said second random sequence using a second Fibonacci sequence that is based on a second tap value and a second initialization value, which are different that said first tap value and said first initialization value.

31. The FIFO buffer system of claim 17 wherein said first FIFO control means receives said first data from a first communications channel and said second FIFO control module receives said second data from a second communications channel.

32. The FIFO buffer system of claim 17 wherein said FIFO buffer system is implemented in one of a network switch and a network router.

38. The method of claim 27 further comprising setting a current write block identifier equal to a next write block identifier and said next write block identifier equal to said potential write block identifier when said memory block corresponding to said potential write block identifier has said not used status.

50. The system of claim 17 wherein said first random sequence is substantially orthogonal to said second random sequence.

51. The system of claim 17 wherein said first random sequence includes values used to assign said first data to said memory blocks and said second random sequence includes values used to assign said second data to said memory blocks.

33. A method for operating a first in, first out (FIFO) buffer system, comprising:

generating a first random sequence;

storing first data in contiguous memory blocks of memory according to said first random sequence;

generating a second random sequence that is different than said first random sequence; and

storing second data in said memory blocks according to said second random sequence.

34. The method of claim 33 wherein said first and second data is capable of being stored in any of said memory blocks.

35. The method of claim 33 further comprising:

retrieving said first data from said memory blocks using said first random sequence; and

retrieving said second data from said memory blocks using said second random sequence.

36. The method of claim 33 further comprising:

providing a potential write block identifier; and

determining availability of a memory block corresponding to said potential write block identifier.

37. The method of claim 36 further comprising:

determining whether said memory block corresponding to said potential write block identifier has one of a used status and a not used status; and

sending a status signal to a check block module.

39. The method of claim 33 further comprising generating a FIFO number and a sequence count when writing to one of said memory blocks.

40. The method of claim 39 further comprising providing a potential read block identifier.

41. The method of claim 40 further comprising determining whether a memory block corresponding to said potential read block identifier has a FIFO number that matches a first FIFO control module.

42. The method of claim 41 further comprising setting a current read block identifier equal to a next read block identifier and said next read block identifier equal to said potential read block identifier when said match occurs.

43. The method of claim 42 further comprising comparing a read block count to said sequence count stored in said memory block corresponding to said current read block identifier.

44. The method of claim 33 further comprising generating said first random sequence using a first Fibonacci sequence that is based on a first tap value and a first initialization value.

45. The method of claim 44 further comprising generating said second random sequence using a second Fibonacci sequence that is based on a second tap value and a second initialization value, which are different that said first tap value and said first initialization value.

46. The method of claim 33 further comprising receiving said first data from a first communications channel and said second data from a second communications channel.

47. The method of claim 33 wherein said FIFO buffer system is implemented in one of a network switch and a network router.

52. The method of claim 33 wherein said first random sequence is substantially orthogonal to said second random sequence.

53. The method of claim 33 wherein said first random sequence includes values used to assign said first data to said memory blocks and said second random sequence includes values used to assign said second data to said memory blocks.