Method and apparatus for maximizing memory throughput

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.