“A METHOD AND AN APPARATUS FOR STORING ON AND RETRIEVING DATA FROM ONE OR MORE EXTERNAL MEMORY DEVICES”

Field of the Invention:
The present invention relates to a method and an apparatus for storing on and retrieving data from one or more external memory devices.

Background of the Invention:
The problem of achieving high data throughput systems requires a wide DDR interface. Very wide DDR interfaces have some limitations such as they not only make the timing closure (physical design) tough but also, for a given burst length at the DDR, require a larger amount of data to be transferred per transaction thus impacting the efficiency for specific packet sizes.

The above mentioned problems can be alleviated by splitting the interface into multiple independently working interfaces. However, high data throughput can be achieved only if the transaction load is distributed across multiple controllers. Even in the case of a single controller, the maximum DDR bandwidth can be achieved when the transaction load is uniformly distributed across all the banks.

A problem that adversely affects the DDR bandwidth utilization is the ability to access multiple banks of the DDR. This is a phenomenon referred to as polarization. This phenomenon occurs most often when each new frame is started in the same bank. For example, when new frames are always started in bank A of a four bank (A, B, C, D) memory device, this tends to under use bank D because the frames are of random length and therefore can end up in any bank. This can be visualized by writing several frames each containing 48 bytes of data into the memory device having four banks (A, B, C, D) ,wherein each bank holds 16 bytes of data. If they are written into the memory according to the conventional practice, 16 bytes would be loaded sequentially into banks A, B, C and thereby leaving bank D as an unutilized bank. If there are multiple frames of the same size then the problem is further aggravated each time an additional frame is added as bank D will never be utilized. This leads to wastage of bandwidth.

Therefore, there always existed a need to develop a method and a system for uniformly distributing load across multiple controllers and/or multiple banks.

Objective of the Invention:
An object of the present invention is to provide a method and system for storing data effectively on one or more external memory devices.

Another object of the present invention is to provide a method and a system for reading data from one or more external memory devices.

Yet another object of the present invention is to provide a system for uniformly distributing load across multiple controllers and/or multiple banks.

Summary of the Invention
Accordingly, the present invention provides a method of storing data on one or more external memory devices, said method comprising the steps of receiving data to be stored on at least one external memory device, said received data comprising at least one frame and said at least one frame comprising one or more chunks, said at least one external memory device comprising one or more banks, each of the said bank comprising a plurality of memory blocks, the said at least one external memory device comprising a plurality of buffers, each of the buffer having at least one memory block and the said buffers are connected to at least one controller that enables storing of the data; determining availability of a free buffer; determining a start controller identification and/or a start bank identification at which a first of the plurality of chunks would be stored using any of- the free buffer’s identification or address; and/or the level of utilization of controllers accessing the buffer; and/or the level of utilization of banks present in the buffer; and/or a random variable; determining a sequence in which the remaining chunks would be stored in the memory blocks of the said buffer; and storing each of the plurality of chunks accordingly.

The present invention also provides an apparatus for storing data on one or more external memory devices, the said system comprising: a means for receiving data to be stored on at least one external memory device, said received data comprising at least one frame and said at least one frame comprising one or more chunks, said at least one external memory device comprising one or more banks, each of the said bank comprising a plurality of memory blocks, the said at least one external memory device comprising a plurality of buffers, each of the buffer having at least one memory block and the said buffers are connected to at least one controller that enables storing of the data; a means for determining availability of a free buffer; a means for determining a start controller identification and/or a start bank identification at which a first of the plurality of chunks would be stored using any of- the free buffer’s identification or address; and/or the level of utilization of banks present in the buffer; and/or the level of utilization of controllers accessing the buffer; and/or a random variable; a means for determining a sequence in which the remaining chunks would be stored; and a means for storing each of the plurality of chunks accordingly.

The present invention further provides a method of reading data from one or more external memory devices, the said method comprising the steps of identifying a buffer to be read; determining the start controller identification and the start bank identification from where the said buffer is to be read based on an on chip stored data; and transmitting at least one request for reading to the memory in accordance with the start controller identification and the start bank identification thus determined.

The present invention furthermore provides an apparatus for reading data from one or more external memory devices, the said system comprising: a means for identifying a buffer to be read; a means for determining the start controller identification and the start bank identification from where the said buffer is to be read based on an on chip stored data; and a means for transmitting at least one request for reading to the memory in accordance with the start controller identification and the start bank identification thus determined.

Brief Description of the Accompanying Drawings:
Figure 1 illustrates a system for distribution load across multiple controllers and/or multiple banks.

Figure 2 illustrates the flow chart for a method of storing data on one or external memory devices.

Figure 3 illustrates the flow chart for a method of reading data from one or external memory devices.

Detailed description of the Invention:
Accordingly, the present invention provides a method of storing data on one or more external memory devices, said method comprising the steps of receiving data to be stored on at least one external memory device, said received data comprising at least one frame and said at least one frame comprising one or more chunks, said at least one external memory device comprising one or more banks, each of the said bank comprising a plurality of memory blocks, the said at least one external memory device comprising a plurality of buffers, each of the buffer having at least one memory block and the said buffers are connected to at least one controller that enables storing of the data; determining availability of a free buffer; determining a start controller identification and/or a start bank identification at which a first of the plurality of chunks would be stored using any of- the free buffer’s identification or address; and/or the level of utilization of controllers accessing the buffer; and/or the level of utilization of banks present in the buffer; and/or a random variable; determining a sequence in which the remaining chunks would be stored in the memory blocks of the said buffer; and storing each of the plurality of chunks accordingly.

According to another aspect of the present invention, wherein each of the said at least one
external memory device is connected to a respective controller.

According to yet another aspect of the present invention, wherein the said buffer includes
one or more memory blocks belonging to one or more banks.

According to yet another aspect of the present invention, wherein the said buffer includes
one or memory blocks belonging to multiple banks belonging to an external memory
device or one or more banks belonging to a plurality of external memory devices.

According to yet another aspect of the present invention, wherein each of the said at least
one controller is identified by an unique controller identification and each of said one or
more banks in an external memory device is identified by an unique bank identification.

According to yet another aspect of the present invention, wherein the controller identified
by the said start controller identification is configured to receive the first of the plurality
of chunks as input and enable the storing of said first of the plurality of chunks in the
bank identified by the said start bank identification.

According to yet another aspect of the present invention, wherein determining the start
controller identification and/or the start bank identification based on the free buffer’s
identification or address comprises analyzing a predetermined number of bits starting
from the LSB and/or MSB position of the said free buffer’s identification or address and
based on the said analysis determining the controller that would be used for storing the
first of the plurality of chunks and/or the bank in the external memory device where the
said first of the plurality of chunks would be stored.

According to yet another aspect of the present invention, wherein the said level of
utilization of the controllers and/or the level of utilization of the banks in the external
memory device is determined based on monitoring the utilization of the controllers and/or
the banks of the external memory device in one or more previous transactions.
According to yet another aspect of the present invention, wherein the controller that is
under utilized in the said one or more previous transactions is selected as the start
controller and the bank accessed by the said start controller thus selected which is under
utilized in the said one or more previous transactions is selected as the start bank.

According to yet another aspect of the present invention, wherein determining the start
controller identification and/or the start bank identification based on the random variable
comprises the steps of determining a first random variable, based on the first random
variable selecting a controller to act as the start controller, determining a second random
variable and based on the second random variable selecting a bank accessed by the said
start controller thus selected, as the start bank.

According to yet another aspect of the present invention, wherein the sequence in which
the remaining chunks would be stored in the memory blocks of the said buffer includes
the controller identification and the bank identification at which each of the remaining of
the plurality of chunks are stored.

According to yet another aspect of the present invention, wherein the controller
identification and the bank identification at which each of the remaining of the plurality
of chunks are stored is obtained by adding fixed offset value to the start controller
identification and the start bank identification at least once.

According to yet another aspect of the present invention, wherein the controller
identification and the bank identification at which each of the remaining of the plurality
of chunks are stored is obtained by adding a variable offset value to the start controller
identification and the start bank identification at least once.

According to yet another aspect of the present invention, the method further comprises storing metadata indicative of the start controller identification and the start bank identification.

According to yet another aspect of the present invention, wherein the said metadata
indicative of the start controller identification and the start bank identification is stored as
on chip data.

According to yet another aspect of the present invention, wherein the metadata is stored
as on chip data in respect of a data frame which is independent.

According to yet another aspect of the present invention, the method further comprises
storing metadata indicative of the sequence of storing of the remaining chunks as an on
chip data.

According to yet another aspect of the present invention, the method further comprises
storing metadata indicative of the sequence of storing of the remaining chunks in the
memory blocks of the said buffer.

Accordingly the present invention also provides an apparatus for storing data on one or more external memory devices, the said system comprising: a means for receiving data to be stored on at least one external memory device, said received data comprising at least one frame and said at least one frame comprising one or more chunks, said at least one external memory device comprising one or more banks, each of the said bank comprising a plurality of memory blocks, the said at least one external memory device comprising a plurality of buffers, each of the buffer having at least one memory block and the said buffers are connected to at least one controller that enables storing of the data; a means for determining availability of a free buffer; a means for determining a start controller identification and/or a start bank identification at which a first of the plurality of chunks would be stored using any of- the free buffer’s identification or address; and/or the level of utilization of banks present in the buffer; and/or the level of utilization of controllers accessing the buffer; and/or a random variable; a means for determining a sequence in which the remaining chunks would be stored; and a means for storing each of the plurality of chunks accordingly.

According to another aspect of the present invention, wherein each of the said means are
implemented as a standalone means.

According to yet another aspect of the present invention, wherein all of the said means
are implemented as a single means.

Accordingly the present invention further provides, a method of reading data from one or more external memory devices, the said method comprising the steps of identifying a buffer to be read; determining the start controller identification and the start bank identification from where the said buffer is to be read based on an on chip stored data; and transmitting at least one request for reading to the memory in accordance with the start controller identification and the start bank identification thus determined.

According to another aspect of the present invention, wherein the said start controller
identification and start bank identification indicates the controller and the bank from
where the first of the plurality of chunks would be read.

According to yet another aspect of the present invention, the method further comprises
accessing metadata indicative of the sequence in which the remaining chunks are stored.

According to yet another aspect of the present invention, wherein determining the
sequence in which the remaining of the chunks are stored and reading each of the
plurality of chunks in accordance with the sequence thus determined.

Accordingly the present invention furthermore provides an apparatus for reading data from one or more external memory devices, the said system comprising: a means for identifying a buffer to be read; a means for determining the start controller identification and the start bank identification from where the said buffer is to be read based on an on chip stored data; and a means for transmitting at least one request for reading to the memory in accordance with the start controller identification and the start bank identification thus determined.
According to another aspect of the present invention, the apparatus further comprises a
means for accessing the metadata and determining the sequence in which the remaining
chunks are stored and a means for reading the remaining of the chunks in accordance
with the sequence thus determined.

According to yet another aspect of the present invention, wherein each of the said means
are implemented as a standalone means.

According to yet another aspect of the present invention, wherein all of the said means
are implemented as a single means.

Accordingly the present invention also provides a system for uniformly distributing load
across multiple controllers and/or multiple banks, the said system comprising: at least one external memory device for storing data, the data comprising at least one frame and said at least one frame comprising one or more chunks and the said at least one external memory device comprising one or more banks, each of the said bank comprising a plurality of memory blocks, the said at least one external memory device comprising a plurality of buffers, each of the buffer having at least one memory block and the said buffers are connected to at least one controller that enables storing of the data; and an apparatus for storing data, being connected to said at least one external memory device.

According to another aspect of the present invention, the system further comprises an
apparatus for reading data.

According to yet another aspect of the present invention, wherein the apparatus for
storing data and the apparatus for reading data together form part of a load distribution
controller.

The method and system described here provides a generalized 2-dimensional stripping mechanism over banks and controllers. The load distribution essential makes use of a random variable that identifies the start bank/controller where a block of data are to be written, followed by a defined traffic pattern. The random variable can be chosen to be from the LSB’s of the buffer ID- due to the random traffic pattern and scheduling of the output queues, the sequence in which the buffers are allocated and freed up is randomized. Even in the specific case that the sequence followed is a predictable pattern, the method and the system rotates banks and controllers to avoid any lock up conditions. As a further generalization the start bank/controller state can be derived from a global state maintained in the device. This information is then embedded in the data written to the DDR, so that that order of the data can be recovered when a packet is dequeued.

Dated this 31st day of March 2009.
G.DEEPAK SRINIWAS
OF K & S PARTNERS
ATTORNEY FOR THE APPLICANT

ABSTRACT

“A METHOD AND AN APPARATUS FOR STORING ON AND RETRIEVING DATA FROM ONE OR MORE EXTERNAL MEMORY DEVICES”

The present invention relates to a method of storing data on one or more external memory devices, said method comprising the steps of receiving data to be stored on at least one external memory device, said received data comprising at least one frame and said at least one frame comprising one or more chunks, said at least one external memory device comprising one or more banks, each of the said bank comprising a plurality of memory blocks, the said at least one external memory device comprising a plurality of buffers, each of the buffer having at least one memory block and the said buffers are connected to at least one controller that enables storing of the data; determining availability of a free buffer; determining a start controller identification and/or a start bank identification at which a first of the plurality of chunks would be stored using any of- the free buffer’s identification or address; and/or the level of utilization of controllers accessing the buffer; and/or the level of utilization of banks present in the buffer; and/or a random variable; determining a sequence in which the remaining chunks would be stored in the memory blocks of the said buffer; and storing each of the plurality of chunks accordingly.