Logic for initializing the depth of the queue pointer memory

Details Logic for initializing the depth of the queue pointer memory Logic for initializing the depth of the queue pointer memory

2000-09-29

2003-10-07

Verbrugge, Kevin (Department: 2188)

Electrical computers and digital processing systems: memory

Storage accessing and control

Memory configuring

C711S154000

Reexamination Certificate

active

06631455

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to a method and/or architecture for implementing multiqueue First In First Out (FIFO) memories generally and, more particularly, to a method and/or architecture for implementing a virtual multiqueue FIFO.
BACKGROUND OF THE INVENTION
Referring to
FIG. 1
, a conventional system
10
for implementing multiqueue FIFOs is shown. The system
10
generally comprises a selector section
12
, a selector section
14
and a number of memory sections
16
a
-
16
n
. The memory sections
16
a
-
16
n
are implemented as FIFOs. The conventional system
10
implements each of the FIFOs
16
a
-
16
n
as an independent physical memory.
The selector section
12
receives data from a write interface and presents the data to one of the memory sections
16
a
-
16
n
in response to a write select signal WR_SEL. The selector section
12
selects one of the FIFOs
16
a
-
16
n
based on the signal WR_SEL. The incoming data is then stored into the appropriate FIFO
16
a
-
16
n
. Similarly, the selector section
14
presents data to a read interface from one of the memory sections
16
a
-
16
n
in response to a read select signal RD_SEL. The selector section
14
selects one of the FIFOs
16
a
-
16
n
based on the signal RD_SEL and reads the data from the appropriate FIFO
16
a
-
16
n.
Independently implementing each FIFO
16
a
-
16
n
as a separate memory element is inefficient. Additionally, the conventional system
10
does not provide flexibility for implementing variable sized FIFOs, since an increase of each FIFO in depth can only be achieved by cascading two or more of the FIFOs
16
a
-
16
n
. Such conventional depth expansion of the FIFOs
16
a
-
16
n
occurs in large quantities and can be inefficient (i.e., depth is only increased by implementing an additional FIFO). Additionally, increasing the size of the FIFOs
16
a
-
16
n
reduces the number of FIFOs that can be implemented. Moreover, the conventional system
10
is not scalable for a large number of FIFOs.
One implementation of the conventional system
10
stores multicast port information into one of the FIFOs
16
a
-
16
n
in response to the incoming data. However, with such an approach, one particular FIFO
16
a
-
16
n
of the system
10
can become significantly large, based on memory density and packet size of incoming data. For example, to implement twice a minimum size packet, half of a port information memory will be wasted. For even larger size packets, port information memory utilization is significantly reduced.
If the memory size is 64K times the data width and the minimum packet size is 8 times the data width, the number of minimum size packets is 8K (memory size/minimum packet size). For each multicast packet, port information is stored. Assuming all of the 8K packets are multicast, a 8K×32 memory is required to store all the port information for the 8K multicast packets (i.e., x32 for a 32 port configuration or x16 for a 16 port configuration). Maximum memory utilization occurs when all 8K are multicast packets and each is of minimum packet size. If packet size is increased, assuming all are multicast packets, the memory utilization will very as follows:
Packet size (words)
% mem utilization
8
100% 
 
16
50
32
25
64
12.5
128
6.25
If packet size is minimum, and multicast packets are 10% of the total number of packets, then memory utilization will be 10%. Similary, for a 64 word packet size, if 10% of the total number of packets are multicast, then the memory utilization is 10% of 12.5=1.25%.
Another implementation of the conventional system
10
implements separate logic structures to utilize unicast and multicast address generator logic. However, such an approach requires significant additional logic and has a limited amount of logic reuse. Furthermore, such an implementation can have high power consumption.
To change the depth of the FIFOs
16
a
-
16
n
of the conventional system
10
, a queue pointer memory data can be stored in a storage element (not shown). However, a default value for each depth field of the FIFOs
16
a
-
16
n
needs to be stored. During power up of the conventional system
10
, the default value is stored in the depth field for each of the FIFOs
16
a
-
16
n.
With such an approach, the dual port memory is configured to store the queue pointer memory value and is written on power up even when the default values are to be used. Such writing during power up requires extra cycles during initialization. Additionally, for a large number of FIFOs
16
a
-
16
n
, a large number of initialization cycles is required.
Conventional multiqueue memories use a forward pointer memory to store a link-list for creating virtual queues in the main memory. The forward pointer memory implements pointers to the queues in the main memory. During power up the forward pointer memory is required to be initialized in order to ensure that the entire memory is linked and is available for use. In such a conventional method, during configuration, all the locations of the forward pointer memory are initialized.
Furthermore, the forward pointer memory has to be written to on power up to initialize the link-list, which requires a significant configuration time. Additionally, the configuration time of the forward pointer memory is dependent on the size of the forward pointer memory and increases linearly as the size of the forward pointer memory increases.
SUMMARY OF THE INVENTION
One aspect of the present invention concerns a circuit configured to provide a storage device comprising one or more virtual multiqueue FIFOs. The circuit is generally configured to operate at a preferred clock speed of a plurality of clock speeds.
Another aspect of the present invention concerns a method for writing and reading in-band information to and from a single storage element, comprising the steps of (A) receiving the in-band information, (B) storing data in either (i) a port information register when in a first state or (ii) a memory element when in a second state and (C) storing subsequent data in the memory element. The first state and the second state may be dependent upon a block position of the in-band information.
Another aspect of the present invention concerns an apparatus configured to extract in-band information or skip extraction of the in-band information and perform a look ahead operation. The apparatus may be configured to switch between the extraction and the skipping of the extraction.
Another aspect of the present invention concerns an apparatus for initializing a default value of a queue. The apparatus may comprise a memory section having a first storage element and a second storage element. The apparatus may be configured to pass the default value of the queue and initialize the default value of the queue without writing to the memory section.
Another aspect of the present invention concerns an apparatus for implementing memory initialization comprising a logic circuit configured to present an address to a memory. The memory initialization may occur as a background process.
Another aspect of the present invention concerns an apparatus for providing arbitration for a dual-port memory. The apparatus may be configured to prevent a write cycle extension during contention between simultaneous read and write operations.
The objects, features and advantages of the present invention include providing a method and/or architecture for implementing a virtual multiqueue FIFO that may (i) be implemented with efficient use of memory storage, (ii) implement a single memory device or package, (iii) allow flexibility for implementing variable sized FIFOs, (iv) allow increments/decrements (e.g., changing) of maximum depth of the individual FIFOs, (v) allow depth increments/decrements in small quantities, (vi) allow scalability for a number of FIFOs, (vii) provide a virtual multiqueue FIFO in a single device, (viii) minimize initialization or configuration time of a system before packet transfer can be started, (ix) allow multiplexing without any overhead and/or (x) implement

Affiliated with

Also associated with

Rating

Logic for initializing the depth of the queue pointer memory does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Logic for initializing the depth of the queue pointer memory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Logic for initializing the depth of the queue pointer memory will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3126004