Memory management free pointer pool

[0001] 1. Field of the Invention

[0002] The present invention relates generally to the field of high speed data transfer, and more specifically to managing data memory, such as synchronous dynamic random access memory (SDRAM), divided into relatively small linked partitions.

[0003] 2. Description of the Related Art

[0004] Data communication networks receive and transmit ever increasing amounts of data. Data is transmitted from an originator or requester through a network to a destination, such as a router, switching platform, other network, or application. Along this path may be multiple transfer points, such as hardware routers, that receive data typically in the form of packets or data frames. At each transfer point data must be routed to the next point in the network in a rapid and efficient manner.

[0005] High speed networking systems typically employ a memory, connected via a memory data bus or interface to other hardware networking components. The memory holds data in a set of partitions, and positions and retrieves this data using a series of pointers to indicate the beginning of each partition. High speed networking applications are currently in the range of ten times faster than previous implementations, but memory technologies have not provided increased efficiency in the presence of larger and larger memories.

[0006] Double Data Rate (DDR) SDRAM data memory is one example of a large memory having a large number of partitions and a significant number of pointers. The number of pointers in newer systems is too large to store on the DDR SDRAM chip, so available pointers are typically stored off chip. Pointers are managed by a communications memory manager, which obtains a pointer every time a new cell or packet fragment is established, and returns a pointer every time a partition is dequeued. Storage of pointers off chip requires that the communications memory manager fetch the pointers and replace the pointers to the off chip location, which tends to adversely effect speed, throughput and overall memory efficiency. Further, SDRAM memory typically exhibits significant latency. A DDR SDRAM pointer management design that minimizes the adverse effects associated with off chip pointer storage would improve over previously available implementations.

[0007] The present invention is illustrated by way of example, and not by way of limitation, in the figures of the accompanying drawings in which:

[0008] FIG. 1A is a conceptual illustration of a packet switching system;

[0009] FIG. 1B is a block diagram illustrating an example of a prior art partitioning of a physical memory;

[0010] FIG. 2A is a block diagram illustrating an example of a memory;

[0011] FIG. 2B presents a block diagram illustrating another example of a memory;

[0012] FIG. 2C is a block diagram illustrating an example of a partition;

[0013] FIG. 2D illustrates an example of a FIFO buffer including more than one partition;

[0014] FIG. 3 shows the construction of a prior art memory manager;

[0015] FIG. 4 illustrates a memory management configuration employing an on chip free pointer pool FIFO;

[0016] FIG. 5 shows partitioning of a memory such as DDR SDRAM having a free pointer pool included in certain partitions;

[0017] FIG. 6A shows a 64 bit wide arrangement of 20 pointers in memory;

[0018] FIG. 6B is a 128 bit wide arrangement of 20 pointers in memory; and

[0019] FIG. 7 illustrates a 64 byte, eight word partition.

[0020] Digital communication systems typically employ packet-switching systems that transmit blocks of data called packets. Typically, data to be sent in a message is longer than the size of a packet and must be broken into a series of packets. Each packet consists of a portion of the data being transmitted and control information in a header used to route the packet through the network to its destination.

[0021] A typical packet switching system 100A is shown in FIG. 1A. In the system 10A, a transmitting server 110A is connected through a communication pathway 115A to a packet switching network 120A. Packet switching network 120A is connected through a communication pathway 125A to a destination server 130A. The transmitting server 110A sends a message as a series of packets to the destination server 130A through the packet switching network 120A. In the packet switching network 120A, packets typically pass through a series of servers. As each packet arrives at a server, the server stores the packet briefly before transmitting the packet to the next server. The packets proceed through the network until they arrive at the destination server 130A. The destination server 130A contains memory partitions on one or more processing chips 135 and on one or more memory chips 140A. The memory chips 140A may use various memory technologies, including SDRAM.

[0022] For illustrative purposes, a particular implementation of a packet switching system is described. For ease of description, a particular implementation in which a message may be any length, a packet may vary from 1 to 64K bytes, and the memory partition size is 64 bytes is used. Many implementations may employ variable length packets having maximum packet sizes and memory partition sizes larger than 64 bytes. For example, maximum packet sizes of two kilobytes or four kilobytes may be used.

[0023] Packet switching systems may manage data traffic by maintaining a linked list of the packets. A linked list may include a series of packets stored in partitions in external memory, such that the data stored in one partition points to the partition that stores the next data in the linked list. As the data are stored in external memory, memory space may be wasted by using only a portion of a memory partition.

[0024] The present design is directed toward efficient memory operation within such a packet switching system, either internal or external, and may also apply to computer, networking, or other hardware memories including, but not limited to, SDRAM memories. One typical hardware application employing SDRAM is a network switch that temporarily stores packet data. Network switches are frequently used on Ethernet networks to connect multiple sub-networks. A switch receives packet data from one sub-network and passes that packet data onto another sub-network. Upon receiving a packet, a network switch may divide the packet data into multiple sub-packets or cells. Each of the cells includes additional header data. As is well known in the art, Ethernet packet data has a maximum size of approximately 1.5 Kbytes. With the additional header data associated with the cells, a packet of data has a maximum size in the range of under 2 Kbytes.

[0025] After dividing the packet data into cells, the network switch may temporarily allocate a memory buffer in the SDRAM to store the packet before retransmission. The address and packet data are translated to the SDRAM, which may operate at a different clock rate than other hardware within the switch. The packet data is then stored in the memory buffer. For retransmission, the switch again accesses the SDRAM to retrieve the packet data. Both the storage and retrieval of data from the SDRAM introduce access delays.

[0026] In the present design, the memory employed may be partitioned into a variety of memory partitions for ease of storage and retrieval of the packet data.

[0027] Memory Partitioning

[0028] FIG. 1B is a block diagram illustrating an example of physical memory partitioning. Typically, memory 100 is divided into equal fixed-size partitions with each of the partitions used as a FIFO buffer and assigned to a flow. Each flow may be associated with a device, such as an asynchronous transfer mode (ATM) device. The size of the memory 100 may be 1 Gbyte, for example, and the memory 100 may be divided into 256K partitions. Each of the 256K partitions may be statically assigned to a flow (e.g., the partition 1 is assigned to the flow 1, etc.) such that every flow is associated with at most one partition. No free partition exists. In this example, each partition is 4 Kbytes long. This partitioning technique is referred to as complete partitioning.

[0029] FIG. 2 is a block diagram illustrating another example of a memory and its partitions, where memory 200 may be partitioned into multiple partitions. The number of partitions may be at least equal to the number of supported flows, and the partitions may be of the same size. For example, the size of the memory 200 may be 1 Gb, and the memory 200 may be partitioned into 16M (1610241024) equally sized partitions, even though there may only be 256K flows.

[0030] In this design, partitions may be grouped into two virtual or logical groups, a dedicated group and a shared group. For example, referring to the example illustrated in FIG. 2A, there may be 4M partitions in the dedicated group 201 and 12M partitions in the shared group 202. The grouping of partitions described here relates to the number of partitions in each group. The partitions 1-16M in the current example may not all be at contiguous addresses.

[0031] Each flow may be associated with a FIFO buffer. Each FIFO buffer may span multiple partitions assigned to that flow. The multiple partitions may or may not be contiguous. The size of the FIFO buffer may be dynamic. For example, the size of a FIFO buffer may increase when more partitions are assigned to the flow. Similarly, the size of the FIFO buffer may decrease when the flow no longer needs the assigned partitions. The function of the FIFO buffer is to transfer data to the partitioned memory in a first in, first out manner.

[0032] FIG. 2B is a block diagram illustrating another example of a memory and its partitions. In this example, there are three flows 1, 3 and 8, each assigned at least one partition from the dedicated group 201. These may be considered active ports because each has assigned partitions, and unread data may exist in these partitions. One or more inactive ports may exist, and no partitions are typically assigned to inactive ports.

[0033] FIG. 2C is a block diagram illustrating an example of a partition. A partition may include a data section to store user data and a control section to store control information. For example, partition 290 may include a data section 225 that includes user data. Unit zero (0) of the partition 290 may also include a control section 220. The control information about the data may include, for example, start of packet, end of packet, error condition, etc.

[0034] Each partition may include a pointer that points to a next partition (referred to as a next partition pointer) in the FIFO buffer. For example, the first data unit 225 of the partition 290 may include a next partition pointer. The next partition pointer may be used to link one partition to another partition when the FIFO buffer includes more than one partition. When a partition is a last or only partition in the FIFO buffer, the next partition pointer of that partition may have a null value. For one embodiment, the next partition pointer may be stored in a separate memory leaving more memory space in the partition 290 for storing data.

[0035] Unit 0 is the only unit in the foregoing example configuration containing control information or a pointer. As illustrated in FIG. 2C, Units 1 through 7 are dedicated to 8 bytes of data each.

[0036] FIG. 2D is a block diagram illustrating an example of a FIFO buffer that includes more than one partition. FIFO buffer 260 in this example includes three partitions, partition 290, partition 290n, and partition 290m. These partitions may or may not be contiguous and may be in any physical order. The partition 290 is linked to the partition 290n using the next partition pointer 225. The partition 290n is linked to the partition 290m using the next partition pointer 245. The next partition pointer of the partition 290m may have a null value to indicate that there is no other partition in the FIFO buffer 260.

[0037] The FIFO buffer 260 may be associated with a head pointer 250 and a tail pointer 255. The head pointer 250 may point to the beginning of the data, which in this example may be in the first partition 290 of the FIFO buffer 260. The tail pointer 255 may point to the end of the data, which in this example may be in the last partition 290m of the FIFO buffer 260. As the data is read from the FIFO buffer 260, the head pointer 250 may be updated accordingly. When the data is completely read from the partition 290, the head pointer 250 may then be updated to point to the beginning of the data in the partition 290n. This may be done using the next partition pointer 225 to locate the partition 290n. The partition 290 may then be returned.

[0038] From FIG. 2B, partitions in the dedicated group 201 and/or in the shared group 202 may not have been assigned to any flow. These partitions are considered free or available partitions and may logically be grouped together in a free pool. For example, when a flow returns a partition to either the shared group 202 or the dedicated group 201, it may be logically be viewed as being returned to the free pool.

[0039] Memory Management

[0040] One example of a previous memory management system used to manage memory, either partitioned or not partitioned, is illustrated in FIG. 3. For the system shown in FIG. 3, memory management entails obtaining a pointer to a free partition every time a new cell or fragment of a packet is enqueued to a data buffer. The memory manager also returns a pointer to memory every time a partition is dequeued. As shown in FIG. 3, chip 301 includes enqueuer 302, dequeuer 303, DDR SDRAM interface 304, and DDR SDRAM 305. External memory 306 resides off chip and holds free pointers, as the size of the DDR SDRAM 305 dictates that pointers cannot be held within DDR SDRAM 305. The memory manager 307, which has typically been on chip but may be off chip, receives an indication that a new cell has been received, obtains a pointer from external memory 306, and provides the pointer to the enqueuer 302 which enqueues the pointer and new cell and places them in DDR SDRAM 305 in one partition. When dequeued, the dequeuer 303 obtains the pointer and the cell in the partition, provides the pointer to the external memory for recycling, and passes the cell for processing, which may include assembly into a packet. Thus external memory is accessed every time that a cell is dequeued or enqueued, and the required reading and writing of pointers significantly decreases memory access efficiency because of the requisite access time to the external memory 305.

[0041] FIG. 4 illustrates an on-chip implementation enabling improved access times to free pointers. FIG. 4 presents a chip 401 having an enqueuer 402, a dequeuer 403, a DDR SDRAM interface 404, and a DDR SDRAM 405. The chip 401 further includes a free pointer pool FIFO 406 located between the dequeuer 403 and the enqueuer 404.

[0042] The memory manager 407 receives an indication that a new cell has been received, obtains a pointer from the free pointer pool FIFO 406, and provides the pointer to the enqueuer 402 which enqueues the pointer and new cell and places them in DDR SDRAM 405 in one partition. When dequeued, the dequeuer 403 obtains the pointer and the cell in the partition within the DDR SDRAM, provides the pointer to the free pointer pool FIFO 406, and passes the cell for processing, which may include assembly into a packet. Thus the free pointer pool FIFO 406 acts as a balancing mechanism that operates to continuously recycle unused pointers located on the DDR SDRAM 405. A certain quantity of unused pointers is located in the DDR SDRAM 405, and those pointers may be freely transferred to and from free pointer pool FIFO 406.

[0043] FIG. 5 illustrates the composition of a sample DDR SDRAM 405 having N partitions, of any size but for purposes of this example having a size of 64 bytes. The free pointer pool 501 within the DDR SDRAM 405 occupies a certain subsection of the DDR SDRAM 405, and various sizes may be employed depending on circumstances, such as the pointer size and DDR SDRAM or other memory size, such as 5 per cent of the entire memory. In this example, the free pointer pool 501 occupies N/20 partitions and may store as many as N pointers. Pointer size in this example is 25 bits. Thus as shown in FIG. 3, the DDR SDRAM 405 is divided into multiple partitions of 64 bytes each in this example. A subsection of the DDR SDRAM 405 includes the free pointer pool 501, such as 5 per cent of the DDR SDRAM 405, and the other 95 per cent is used to store data partitions used to build data buffers. The DDR SDRAM 405 memory segment including the free pointer pool 501 is also divided into partitions, such as 64 byte partitions, and in this example can store twenty 25 bit pointers to free data partitions. The 64 byte partitions can be accessed as a circular buffer.

[0044] As may be appreciated by one skilled in the art, virtually all variables or elements described in connection with this example may be altered, namely increased in size or quantity or decreased in size or quantity, including but not limited to pointer size, partition number and size, free pointer pool size, and percentage of memory taken up by the free pointer pool. The example is meant by way of illustration and not limitation on the concepts disclosed herein.

[0045] In one particular implementation in accordance with the foregoing example, 20 free partition pointers may be stored in the 64 byte partitions occupying 5 per cent of the DDR SDRAM 405, as shown in FIG. 6A. If 128 bits memory data bus width is employed, the pointers may be stored as shown in FIG. 6B. The memory manager may communicate with the DDR SDRAM using a 128 bit bus interface as DDR SDRAM interface 404.

[0046] The 64 byte data partitions, such as each of the individual partitions illustrated in FIGS. 6A and 6B, may be organized as eight words having eight bytes each. As shown in FIG. 7, the first word of the data partition includes control information, including a 25 bit pointer to the next partition, and certain control bits, including but not limited to start of packet, end of packet, and so forth. The remaining seven words or 56 bytes include data. Data cells or packets can be stored in different ways, typically depending on the type of data flow or the manner in which data is received. For a packet-to-packet flow, each partition may store the 56 bytes, a small segment of the data packet. The last partition may contain less than 56 bytes, and thus the number of bytes stored in the last partition of a packet is provided in the information stored in the control word. This control word makes up the first portion of the packet. In the event the memory operates with ATM (asynchronous transfer mode) cells, either in cell-to-cell, packet-to-cell, or cell-to-packet transfers from the input flows, each partition stores one complete ATM cell, typically having a 52 byte data width. In the event the packet is received as cells and converted to packets, one ATM cell received makes up the partition, and the cells can be assembled into packets.

[0047] Thus in this example, the on chip free pointer the on chip free pointer pool FIFO 406 is a 125 bit by 32 word memory. Each 125-bit entry in the free pointer pool FIFO 406 is a free pointer: the memory address of an available (or free) 64-byte partition located in the external SDRAM. The free pointer pool FIFO 406 may take various forms, but typically it must offer functionality of providing for reading and writing, thus including two ports, and must be able to store an adequate quantity of pointer partitions. One implementation of the free pointer pool FIFO 406 that can accommodate the foregoing example is a two port RAM having the ability to store four pointer partitions, or 80 pointers.

[0048] Operation of the on-chip free pointer pool FIFO 406 is as follows. When a cell or packet segment is enqueued, or stored in the DDR SDRAM 405, the enqueuer 402 may obtain a pointer, the pointer indicating an unused data partition within DDR SDRAM 405. The pointer is read from the on chip free pointer pool FIFO 406. When a cell or packet segment is dequeued, or read from the DDR SDRAM 405, the dequeuer 403 returns or stores the pointer associated with the dequeued partition for future reuse. The pointer is written to the on chip free pointer pool FIFO 406. When the contents of the on chip free pointer pool FIFO 406 is above a specified threshold, such as above 75 per cent of capacity, or above 60 pointers, the enqueuer 402 returns a block of 20 pointers, one 64 byte partition, to the free pointer pool in the DDR SDRAM 405. When the contents of the on chip free pointer pool FIFO 406 is below a specified threshold, such as below 25 per cent of capacity, or below 20 pointers, the dequeuer 403 reads a block of 20 pointers, one 64 byte partition, from the free pointer pool in the DDR SDRAM 405.

[0049] At initiation, a certain quantity of pointer may be loaded from DDR SDRAM 405 into the free pointer pool FIFO 406. For the aforementioned example, 40 pointers may be loaded into the free pointer pool. Data received is enqueued using the enqueuer 402, while data transmitted is dequeued from DDR SDRAM using the dequeuer 403. In a balanced environment, a similar number of pointers will be needed and returned over a given period of time, and thus the free pointer pool FIFO 406 may not require refilling or offloading to the DDR SDRAM 405. The free pointer pool FIFO 406 contents may exceed a threshold when certain WRITE cell cycles are not used to enqueue data partitions. One WRITE cell cycle is then used by the free pointer pool FIFO 406 to write a certain number of pointers to the DDR SDRAM 405 external free pointer pool. The free pointer pool FIFO 406 contents may fall below a threshold when certain READ cell cycles are not used to dequeue data partitions. One READ cell cycle is then used by the free pointer pool FIFO 406 to read a certain number of pointers from the DDR SDRAM 405 external free pointer pool. In this manner, access to DDR SDRAM for the purpose of reading or writing pointers operates at a very low rate, such as only once every 20 cycles or more.

[0050] The present design can be used by memory controllers supporting bank interleaving. For example, a memory controller implementing four bank interleaving may employ four on chip free pointer pool FIFOs 406. This design may be employed on memories other than DDR SDRAM, including but not limited to SDR SDRAM, and RDRAM, or generally any memory having the ability to change partition size and FIFO size.

[0051] The present system may be implemented using alternate hardware, software, and/or firmware having the capability to function as described herein. One implementation is a processor having available queueing, parsing, and assembly capability, data memory, and possibly on chip storage, but other hardware, software, and/or firmware may be employed.

[0052] It will be appreciated to those of skill in the art that the present design may be applied to other memory management systems that perform enqueueing and/or dequeueing, and is not restricted to the memory or memory management structures and processes described herein. Further, while specific hardware elements, memory types, partitioning, control fields, flows, and related elements have been discussed herein, it is to be understood that more or less of each may be employed while still within the scope of the present invention. Accordingly, any and all modifications, variations, or equivalent arrangements which may occur to those skilled in the art, should be considered to be within the scope of the present invention as defined in the appended claims.