Coded data generation or conversion – Digital code to digital code converters – To or from packed format
Reexamination Certificate
2002-06-20
2003-11-11
Tokar, Michael (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from packed format
C341S065000, C341S070000, C341S168000, C709S247000, C709S238000, C709S217000, C711S202000, C711S003000
Reexamination Certificate
active
06646576
ABSTRACT:
FIELD OF THE INVENTION
The present invention generally relates to data processing with microprocessors. More specifically, the invention relates to processing data located in an array of storage elements.
BACKGROUND OF THE INVENTION
Packet-based switching has been the focus of many telecommunication providers and manufacturers for some years now (ATM is a form of packet switching as used herein). At each network point in a packet-switched network, the communicated data may be processed for several reasons, such as error handling, traffic management, routing, etc. Generally, each packet, or Protocol Data Unit (PDU), may include some overhead, typically present in header and trailer fields, along with the relevant communicated data in a payload. The header of the PDU may include the appropriate information that a network point may need to perform the various functions listed above.
As the quest for speed continues to drive the networking and telecommunication industries, the equipment at the network points is expected to perform at faster speeds. For these reasons, hardware vendors are turning to network processors (also called communications processors) to support increasingly complex tasks at wire speeds. Programmable network processors can provide system flexibility while delivering the high-performance hardware functions required to process the PDUs at wire speed.
Generally, network processors perform four general tasks: parse, search, resolve, and modify. Network-specific processors strive to optimize each of these tasks to boost the processing performance.
FIG. 1
illustrates a method
10
for processing data at a network point, such as at a packet switch, that is generally well known in the art. The first step
1
is to receive the data at the physical layer. Generally, this step may require the data to be converted from analog to digital, if necessary. Next, the digital data may be buffered into a temporary storage location (step
2
). Typically, the buffer will be a Random Access Memory (RAM), or a register . In general, though, the buffer may be some type of fast memory location. Once buffered, the network processor can begin working on the data.
The first step generally performed by the network processor is to parse the PDU (step
3
). In essence, parsing involves analyzing and classifying the contents of the PDU and its fields. Once parsed, appropriate fields of the PDU may be used to search tables for matches (step
4
). The tables may be routing tables that dictate the next destination for the packet. Just prior to, or just after searching, error handling may be performed, commonly with a cyclic redundancy check (CRC), to verify if the PDU is valid. The next step is to resolve the destination and Quality of Service (QoS) requirements (step
5
). Certain packets may be given certain priority, re-routing information may need to be determined and communicated, etc. When necessary, the PDU may be modified and/or updated with the appropriate routing information (step
6
). Once the PDU has been updated, the packet may be sent to its next destination through the network (step
7
).
In terms of speed, processors are typically measured by the number of clock cycles necessary to perform a particular task combined with their clock frequency. For embedded applications, the energy efficiency is also an important performance parameter. Several algorithms are known in the art that perform the parsing and modifying of the PDU's. Each algorithm varies in complexity as well as performance, e.g. required clock cycles. For example, a relatively straightforward approach to parsing can be performed in software with a higher level programming language such as C. A simple record structure that is made up of several fields may be used to represent a PDU. Each field of the PDU record may be directly addressed which allows for easy access and manipulation of the fields. Unfortunately, while not complex, the programmer can not model the method in which the data is accessed in memory. Quite often, many wasteful clock cycles are used when a software approach is utilized, which leads to poor performance.
Other software solutions can utilize manual bit-level operations. A well known scheme that is often utilized by general purpose processors is a shift and mask operation. In general, to access a field located in a PDU, the field may need to be shifted so that the least-significant-bit (Isb) of the field is the lsb of the current register. The other remaining, unimportant bits in the register, can then be masked out. This, although typically more efficient than the previous solution, can still be quite cumbersome.
Hardware solutions have also been created to parse and modify a given PDU. Most of these solutions simply mirror the software implementations above. Other solutions simply consist of hardwired state machines.
Therefore, there exists a need for improved systems and methods for processing data that is stored in a packed structure, such as a PDU. It would be desirable for this solution to require as little clock cycles as necessary, but still allow for flexibility in design and implementation.
SUMMARY OF THE INVENTION
The present invention relates to methods and systems for processing data, particularly data of a packed data structure, such as a PDU. In this regard, an embodiment of a system for parsing data stored in an array of storage elements includes a decoder configured to receive a desired register format from a plurality of register formats and further configured to activate an enable signal from a set of enable signals based on the desired register format. The system also includes operational logic configured to derive an array of output data bits related to the desired register format. The operational logic receives as inputs the set of enable signals and selectively connected storage elements of the array of storage elements.
In another embodiment, a system for writing data to an array of storage elements includes a decoder configured to receive a desired register format from a plurality of register formats and further configured to activate an enable signal from a set of enable signals based on the desired register format. The system also includes an array of bit-selector blocks configured to write the data to the array of storage elements in the desired register format. Each bit-selector block receives as inputs various selected bits of the data and selected enable signals of the set of enable signals, such that activation of one of the selected enable signals dictates which bit of the various input bits is to be written to a particular storage element.
Another embodiment may be construed as a system for parsing and modifying data stored in an array of storage elements. This system includes a read decoder configured to receive a desired register format from a plurality of register formats and further configured to activate a read-enable signal from a set of read-enable signals based on the desired register format. The system also includes operational logic configured to derive an array of output data bits related to the desired register format, wherein the operational logic receives as inputs the set of read-enable signals and selectively connected storage elements of the array of storage elements. The system further includes a write decoder configured to receive a desired register format from the plurality of register formats and further configured to activate a write-enable signal from a set of write-enable signals based on the desired register format and an array of bit-selector blocks configured to write the data to the array of storage elements in the desired register format. Each bit-selector block receives as inputs various selected bits of the data and selected write-enable signals of the set of write-enable signals, such that activation of one of the selected write-enable signals dictates which bit of the various input bits is to be written to a particular storage element.
Another embodiment may be construed as a system for parsing data stored in an array of st
Delvaux Marc
Habot Ronen
Globespanvirata, Inc.
Mai Lam T
Thomas Kayden Horstemeyer & Risley
Tokar Michael
LandOfFree
System and method for processing data does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for processing data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for processing data will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3184841