Method and apparatus for maximizing memory throughput

• US 6,487,202 B1
• Filed: 06/30/1997
• Issued: 11/26/2002
• Est. Priority Date: 06/30/1997
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Wong, Kevin, Klausmeier, Daniel E.
• Primary Examiner(s): Cheng, Joe H.
• Assistant Examiner(s): Nguyen, Kim T.
• Application Number:
  US08/884,999
• Time in Patent Office: 1,975 Days
• Field of Search: 370/233, 370/235, 370/395, 370/397, 370/399, 370/398, 370/409, 370/412, 370/465, 370/468
• US Class Current: 370/395.1
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 2012/5681 Buffer or queue management
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS
• CPC Class Codes: H04L 49/108 using shared central buffer
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/901 using storage descriptor, e.g. read or write pointers
• CPC Class Codes: H04L 49/9089 replacing packets in a storage arrangement, e.g. pushout
• CPC Class Codes: H04L 49/9094 Arrangements for simultaneous transmit and receive, e.g. simultaneous reading/writing from/to the storage element

Abstract

A method of executing a sequence of multiple dependent operations, each operation including a memory read and a memory write involves overlapping memory accesses of the operations by grouping together memory reads and memory writes of multiple operations and preserving a desired sequence of the operations using a circuit external to a memory through which the memory accesses are performed. The operations may be updates to one or more linked lists. In one embodiment, the step of overlapping memory accesses may be performed by grouping together memory accesses according to ATM cell arrivals or departures. In this embodiment, the operations are associated with ATM cell arrivals or departures and may be gets or puts. Each get and put operation may be characterized by a number of atomic memory operations to update one or more linked lists. To perform the operations a circuit a having an address processor, a data processor coupled to the address processor and to the external memory, and a prefetch buffer coupled to the external memory, the address processor and to the data processor is provided. The address processor generates memory addresses for the operations according to the step of overlapping memory accesses. The atomic memory operations are grouped so that all of the memory read operations associated with the dependent operations are performed before all of the memory write operations associated with the dependent operations are performed.

Claims

1. A method comprising:

mapping together in a predetermined order a number of memory accesses including memory reads and memory writes of multiple cell operations within a network switch so as to implement a desired sequence of the cell operations, which sequence accounts for data dependencies among the cell operations, the memory accesses being associated with cell move, cell arrival and cell departure operations, each having one or more memory get and/or put operations associated therewith; and

performing said desired sequence of the cell operations.

2. A method as in claim 1 wherein the cell operations comprise updates to one or more linked lists that indicate cell storage locations.

3. A method as in claim 1 wherein each get and put operation includes a number of memory operations to update one or more linked lists that indicate cell storage locations.

4. A method as in claim 3 wherein the memory operations of the gets and puts comprise memory reads and memory writes and such memory operations are grouped so that all memory read operations associated with dependent ones of the operations are performed before all memory write operations associated with the dependent ones of the operations are performed.

5. A method comprising:

performing one or more update operations on a plurality of linked list pointers to produce a set of updated linked list pointers, the update operations being performed in response to update requests and comprising a series of dequeuing operations followed by a series of enqueuing operations, all of the dequeuing operations being performed prior to any of the enqueuing operations being performed; and

storing said updated linked list pointers in a memory.

6. A method as in claim 5 wherein the update requests are associated with one or more Asynchronous Transfer Mode (ATM) connections and the linked list pointers are associated with ATM queues for the ATM connections.

7. A method as in claim 6 wherein the update operations are performed by:

reading a plurality of head pointers, tail pointers and intermediate pointers from the memory;

storing the plurality of head pointers, tail pointers and intermediate pointers in a cache circuit; and

updating the plurality of head pointers, tail pointers and intermediate pointers to reflect the results of the cell operations specified by the update requests.

8. A digital switch, comprising:

a memory;

one or more linked lists of pointers stored in the memory, the pointers corresponding to memory locations of associated data; and

a caching circuit coupled to the memory and configured to (a) receive one or more of the linked lists of pointers in response to a linked list update request, the linked list update request indicating an operation involving the data, (b) to generate updated linked lists of pointers according to the update request, and (c) to generate the updated linked lists of pointers by performing out-of-order update operations wherein all dequeuing operations are performed before any enqueuing operations are performed.

9. A digital switch as in claim 8 wherein the caching circuit is further configured to write the updated linked lists of pointers to the memory upon completion of the operation.

10. A digital switch as in claim 9 wherein the caching circuit comprises:

a buffer adapted to receive the linked lists of pointers from the memory;

an address processor coupled to the buffer and adapted to receive the update request, the address processor configured to generate read and write addresses for accessing the memory according to the update request; and

a data processor coupled to the buffer and configured to perform the out-of-order update operations according to the update request.

11. A digital switch as in claim 10 wherein the data processor stores intermediate results of the update operations in the buffer.

12. A digital switch comprising:

means for mapping together in a predetermined order a number of memory accesses including memory reads and memory writes of multiple cell operations so as to implement a desired sequence of the cell operations, which sequence accounts for data dependencies among the cell operations, the memory accesses being associated with cell move, cell arrival and cell departure operations, each having one or more memory get and/or put operations associated therewith; and

means for performing said desired sequence of the cell operations.

13. The digital switch according to claim 12, wherein the cell operations comprise updates to one or more linked lists that indicate cell storage locations.

14. The digital switch according to claim 12, wherein each get and put operation includes a number of memory operations to update one or more linked lists that indicate cell storage locations.

15. The digital switch according to claim 14, wherein the memory operations of the gets and puts comprise memory reads and memory writes and such memory operations are grouped so that all memory read operations associated with dependent ones of the operations are performed before all memory write operations associated with the dependent ones of the operations are performed.

16. A digital switch comprising:

means for performing one or more update operations on a plurality of linked list pointers to produce a set of updated linked list pointers, the update operations being performed in response to update requests and comprising a series of dequeuing operations followed by a series of enqueuing operations, all of the dequeuing operations being performed prior to any of the enqueuing operations being performed; and

means for storing said updated linked list pointers in a memory.

17. The digital switch according to claim 16, wherein the update requests are associated with one or more Asynchronous Transfer Mode (ATM) connections and the linked list pointers are associated with ATM queues for the ATM connections.

18. The digital switch according to claim 17, further comprising:

means for reading a plurality of head pointers, tail pointers and intermediate pointers from the memory;

means for storing the plurality of head pointers, tail pointers and intermediate pointers in a cache circuit; and

means for updating the plurality of head pointers, tail pointers and intermediate pointers to reflect the results of the cell operations specified by the update requests.

19. A computer readable medium containing executable instructions which, when executed in a processing system, cause the system to perform a method comprising:

mapping together in a predetermined order a number of memory accesses including memory reads and memory writes of multiple cell operations within a network switch so as to implement a desired sequence of the cell operations, which sequence accounts for data dependencies among the cell operations, the memory accesses being associated with cell move, cell arrival and cell departure operations, each having one or more memory get and/or put operations associated therewith; and

performing said desired sequence of the cell operations.

20. The computer readable medium according to claim 19, wherein the cell operations comprise updates to one or more linked lists that indicate cell storage locations.

21. The computer readable medium according to claim 19, wherein each get and put operation includes a number of memory operations to update one or more linked lists that indicate cell storage locations.

22. The computer readable medium according to claim 21, wherein the memory operations of the gets and puts comprise memory reads and memory writes and such memory operations are grouped so that all memory read operations associated with dependent ones of the operations are performed before all memory write operations associated with the dependent ones of the operations are performed.

23. A computer readable medium containing executable instructions which, when executed in a processing system, cause the system to perform a method comprising:

performing one or more update operations on a plurality of linked list pointers to produce a set of updated linked list pointers, the update operations being performed in response to update requests and comprising a series of dequeuing operations followed by a series of enqueuing operations, all of the dequeuing operations being performed prior to any of the enqueuing operations being performed; and

storing said updated linked list pointers in a memory.

24. The computer readable medium according to claim 23, wherein the update requests are associated with one or more Asynchronous Transfer Mode (ATM) connections and the linked list pointers are associated with ATM queues for the ATM connections.

25. The computer readable medium according to claim 24, wherein said performing further comprises:

reading a plurality of head pointers, tail pointers and intermediate pointers from the memory;

storing the plurality of head pointers, tail pointers and intermediate pointers in a cache circuit; and

updating the plurality of head pointers, tail pointers and intermediate pointers to reflect the results of the cell operations specified by the update requests.

26. A digital switch comprising:

a memory; and

a processor coupled to the memory and configured to map together in a predetermined order a number of memory accesses including memory reads and memory writes of multiple cell operations so as to implement a desired sequence of the cell operations, which sequence accounts for data dependencies among the cell operations, the memory accesses being associated with cell move, cell arrival and cell departure operations, each having one or more memory get and/or put operations associated therewith, and to perform said desired sequence of the cell operations.

27. The digital switch according to claim 26, wherein the cell operations comprise updates to one or more linked lists that indicate cell storage locations.

28. The digital switch according to claim 26, wherein each get and put operation includes a number of memory operations to update one or more linked lists that indicate cell storage locations.

29. The digital switch according to claim 28, wherein the memory operations of the gets and puts comprise memory reads and memory writes and such memory operations are grouped so that all memory read operations associated with dependent ones of the operations are performed before all memory write operations associated with the dependent ones of the operations are performed.

30. A digital switch comprising:

a memory; and

a processor coupled to the memory and configured to perform one or more update operations on a plurality of linked list pointers to produce a set of updated linked list pointers, the update operations being performed in response to update requests and comprising a series of dequeuing operations followed by a series of enqueuing operations, all of the dequeuing operations being performed prior to any of the enqueuing operations being performed, and to store said updated linked list pointers in a memory.

31. The digital switch according to claim 30, wherein the update requests are associated with one or more Asynchronous Transfer Mode (ATM) connections and the linked list pointers are associated with ATM queues for the ATM connections.

32. The digital switch according to claim 31, wherein said processor is further configured to:

read a plurality of head pointers, tail pointers and intermediate pointers from the memory;

store the plurality of head pointers, tail pointers and intermediate pointers in a cache circuit; and

update the plurality of head pointers, tail pointers and intermediate pointers to reflect the results of the cell operations specified by the update requests.