Electrical computers and digital processing systems: memory – Storage accessing and control
Reexamination Certificate
1999-12-21
2004-06-22
An, Meng-Al T. (Department: 2127)
Electrical computers and digital processing systems: memory
Storage accessing and control
C711S001000, C711S152000, C711S200000, C712S001000, C712S220000, C718S100000, C718S102000, C718S104000
Reexamination Certificate
active
06754764
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the field of data processing and data communication. More specifically, the present invention relates to the techniques for maintaining order in a pipelined process in a data processing or data communication device, where the pipelined processes may be completed out-of-order.
2. Background Information
The performance of some processes can be greatly increase by pipelining techniques in which the process simultaneously handles multiple tasks in various stages of completion. [The term “process”, as used herein, includes hardware and/or software.]
FIG. 1
illustrates an example look up process that can benefit from such pipelining approaches. The example look up is of a kind that looks for matches between a presented query number
102
and a threaded list of entries
104
. Each entry
106
consists of comparand
108
, payload
110
and pointer
112
. Each pointer
112
points to the location of the next entry, except for the last entry
106
, whose “pointer”
112
is set to null. The query number
102
is mapped to an initial pointer
114
that points to the beginning of the list. At each entry, the comparand
108
is matched against the query number
102
. If they agree, the look up is successful, and the associated payload
110
is reported as the look up result. If they disagree, and the associated pointer
112
is non-zero, the look up process continues with the next entry
116
. The process continues until either a match is found, or the last entry
106
is encountered, where the associated pointer is null (or zero). In such case, the look up process reports failure.
In practical implementations, the threaded lists are typically stored in RAM that takes several clock cycles to access. Thus, overall system performance can be improved if the look up process can be performed for multiples of these queries at the same time. The nature of the look up process, however, is such that some queries take longer to resolve than others, giving rise to the possibility that results can become available out of order.
A specific application where such situations occur is in networking switch and router applications. Network switches/routers receive continuous streams of packets, and the included IP or MAC addresses are queued and examined to determine where the packets should be switched or routed. The determination typically involves data look ups. For performance reasons, it is desirable to be able to perform the look up for multiple of these IP/MAC addresses concurrently in a pipelined multi-stage fashion. However, as alluded to earlier, by virtue of the nature of the look up, data may be found out of order for the various IP/MAC addresses.
Thus, an efficient approach to maintaining order in a pipelined process, without squandering the efficiency gained from pipelining, is desired.
SUMMARY OF THE INVENTION
The method of the present invention includes sequentially reserving a number of memory locations of a result memory for a number of processes as the processes are sequentially dispatched for execution. As an integral part of the sequential reservation, validity determination facilitators to be subsequently employed to correspondingly facilitate determining whether valid processing results of the processes have been stored into corresponding ones of the reserved memory locations are pre-determined. The method further includes sequentially reading the reserved memory locations to sequentially accept the processing results in order. Each value read from a reserved memory location is accepted only if the corresponding validity determination facilitator exhibits a predetermined relationship with a corresponding validity determination reference value. The validity determination reference values are complementarily maintained and integrally obtained through the sequential read process.
REFERENCES:
patent: 5805854 (1998-09-01), Shigeeda
patent: 5914953 (1999-06-01), Krause et al.
patent: 6125430 (2000-09-01), Noel et al.
patent: 6233702 (2001-05-01), Horst et al.
patent: 6237079 (2001-05-01), Stoney
patent: 6256347 (2001-07-01), Yu et al.
patent: 6336180 (2002-01-01), Long et al.
An Meng-Al T.
Intel Corporation
Tom Lisa
Vo Lilian
LandOfFree
Method and apparatus for maintaining order in a pipelined... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for maintaining order in a pipelined..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for maintaining order in a pipelined... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3302381