Method and apparatus for performing lane arithmetic to perform network processing

• US 6,047,304 A
• Filed: 07/29/1997
• Issued: 04/04/2000
• Est. Priority Date: 07/29/1997
• Status: Expired due to Term

• Current Assignee: Avaya Management L.P. (Avaya Incorporated)
• Original Assignee: Nortel Networks Corporation
• Inventors: Ladwig, Geoff, Harriman, Edward S.
• Primary Examiner(s): FOLLANSBEE, JOHN A
• Application Number:
  US08/902,396
• Time in Patent Office: 980 Days
• Field of Search: 370/252, 714/52, 714/56, 714/703, 714/712, 714/758, 714/776, 714/799, 714/807, 708/505, 708/603, 708/670-714, 708/530
• US Class Current: 708/530
• CPC Class Codes: G06F 2207/3828 Multigauge devices, i.e. capable of handling packed numbers without unpacking them
• CPC Class Codes: G06F 2207/3836 One's complement
• CPC Class Codes: G06F 7/505 in bit-parallel fashion, i.e. having a different digit-handling circuit for each denomination
• CPC Class Codes: G06F 9/30014 with variable precision
• CPC Class Codes: G06F 9/30032 Movement instructions, e.g. MOVE, SHIFT, ROTATE, SHUFFLE
• CPC Class Codes: G06F 9/30036 Instructions to perform operations on packed data, e.g. vector, tile or matrix operations

Abstract

A method and apparatus for processing network packets is disclosed. A Single Instruction Multiple Data (SIMD) architecture processor is disclosed. The SIMD processor includes several instructions designed specifically for the task of network packet processing. For example, SIMD add instructions for performing one'"'"'s complement additions are included to quickly calculate Internet checksums. Furthermore, the SIMD processor includes several instructions for performing lane arithmetic.

Claims

1. A method of calculating a sum in a processor, said method comprising:

storing a data set as a sequential series of data values in a memory, the data values being associated with lanes of data values of a selectable bit width;

sequentially adding a subset of said sequential series of data values to contents of a register using lane arithmetic to generate a sequence of partial sums within the register, the subset of said sequential series of data values are selected such that lanes of data values within the subset of said sequential series of data values are aligned and added within lanes of the register; and

executing bit field arithmetic operations on the contents of the resister within the lanes in order to reduce said sequence of partial sums into a final sum within a lane of the register.

2. The method of calculating a sum as claimed in claim 1, wherein sequentially adding a subset of said sequential series of data values to a register using lane arithmetic includes,

utilizing four 16 bit lanes of a 64 bit register,

organizing the subset of said sequential series by selecting four separate 16 bit data values and placing them end to end in alignment with the four 16 bit lanes of the 64 bit register, and

adding the bits in the respective aligned lanes together.

3. The method of calculating a sum as claimed in claim 1, wherein sequentially adding a subset of said sequential series of data values to a register using lane arithmetic includes adding by one'"'"'s complement lane arithmetic so that a carry bit from each most significant bit of each respective lane affects a least significant bit of the respective lane.

4. The method of calculating a sum as claimed in claim 3, wherein said one'"'"'s complement lane arithmetic further includes rotating bits within at least one lane of contents within the register prior to adding the subset of said sequential series of data values to the contents of the register using one'"'"'s complement lane arithmetic.

5. The method of calculating a sum as claimed in claim 1, wherein said data set comprises an Internet Protocol header and the final sum represents a computed checksum value for comparison with a received predetermined checksum to determine if a packet associated with the received predetermined checksum was correctly received.

6. The method of calculating a sum as claimed in claim 5, wherein the final sum represents the computed checksum value in one'"'"'s complement form and the comparison between the computed checksum value and the received predetermined checksum value is performed by adding the received predetermined checksum to the one'"'"'s complement form of the computed checksum value and determining if the result is zero.

7. The method of calculating a sum as claimed in claim 1, wherein sequentially adding a subset of said sequential series of data values to a register using lane arithmetic includes processing an add16to16in1s lane arithmetic instruction so that sixteen bit lanes of the subset of said sequential series of data values are added to sixteen bit lanes of contents of the register using one'"'"'s complement lane arithmetic addition.

8. The method of calculating a sum as claimed in claim 1, wherein sequentially adding a subset of said sequential series of data values to a register using lane arithmetic includes processing an add8to16in1s lane arithmetic instruction so that eight bit lanes of the subset of said sequential series of data values are added to sixteen bit lanes of contents of the register using one'"'"'s complement lane arithmetic addition.

9. The method of calculating a sum as claimed in claim 1, wherein sequentially adding a subset of said sequential series of data values to a register using lane arithmetic includes rotating bits within at least one lane of contents within the register prior to adding the subset of said sequential series of data values to the contents of the register using lane arithmetic.

10. The method of calculating a sum as claimed in claim 1, wherein sequentially adding a subset of said sequential series of data values to the register using lane arithmetic includes performing two'"'"'s complement lane arithmetic.

11. An apparatus for processing sequential instructions, said apparatus comprising:

a register for storing bits of data;

an instruction execution unit, said instruction execution unit including logic to receive lane arithmetic instructions and control the execution thereof; and

an arithmetic logic unit, said arithmetic logic unit having logic to execute lane arithmetic instructions on lanes within said register, a lane being a range of bits as specified by a lane arithmetic instruction.

12. The apparatus for processing sequential instructions as claimed in claim 11 further comprises:

bit field manipulation logic, said bit field manipulation logic to perform bit field arithmetic instructions by performing an arithmetic operation on selected fields of bits within the register as specified in a bit field arithmetic instruction.

13. The apparatus for processing sequential instructions as claimed in claim 11 wherein the logic within said arithmetic logic unit executes lane arithmetic add instructions using one'"'"'s complement lane arithmetic addition.

14. The apparatus for processing sequential instructions as claimed in claim 13 wherein,

the logic within said arithmetic logic unit may rotate bits within a lane prior to execution of a one'"'"'s complement lane arithmetic addition.

15. The apparatus for processing sequential instructions as claimed in claim 11 wherein said arithmetic logic unit processes an add16to16in1s lane arithmetic instruction causing sixteen bit lanes of data to be added to sixteen bit lanes of contents of the register using one'"'"'s complement lane arithmetic addition.

16. The apparatus for processing sequential instructions as claimed in claim 11 wherein said arithmetic logic unit processes an add8to16in1s lane arithmetic instruction causing eight bit lanes of data to be added to sixteen bit lanes of contents of the register using one'"'"'s complement lane arithmetic addition.

17. The apparatus for processing sequential instructions as claimed in claim 11 wherein, the logic within said arithmetic logic unit executes lane arithmetic add instructions with two'"'"'s complement lane arithmetic addition.

18. The apparatus for processing sequential instructions as claimed in claim 17 wherein,

the logic within said arithmetic logic unit may rotate bits within a lane prior to execution of a two'"'"'s complement lane arithmetic addition.

19. A method of verifying that a packet of data was correctly received by a network device in a network, the packet of data including a transmitted checksum and a plurality of data words each being a lane wide of a predetermined number of bits forming a plurality of lanes, the method comprising:

arranging the data words into a sequence of data words, the sequence of data words formed by placing lanes of data words end to end in alignment for addition in parallel together;

adding each parallel lane of the sequence of data words together using lane arithmetic resulting in a partial sum in each lane;

adding each partial sum together using bit field arithmetic to form a final sum representative of a calculated checksum; and

comparing the final sum with the transmitted checksum to determine if the packet was correctly received.

20. The method of claim 19, wherein the final sum represents the calculated checksum in one'"'"'s complement form and the comparison between the calculated checksum and the transmitted checksum includes adding the transmitted checksum to the one'"'"'s complement form of the calculated checksum and determining if the result is zero.

21. The method of claim 19 wherein, the adding of each parallel lane of the sequence of data words together using lane arithmetic resulting in a partial sum in each lane includes performing one'"'"'s complement lane arithmetic.

22. A network device having a single instruction multiple data (SIMD) processor, the network device using the SIMD processor and a received checksum to verify the correct receipt of data packets across the network, each data packet including a plurality of data values each data value being a lane wide and each lane being a plurality of bits wide, the network device comprising:

the SIMD processor including an arithmetic logic unit and a register having a width of N lanes, the arithmetic logic unit to perform lane arithmetic or bit field arithmetic in response to a single instruction, the register to couple to the arithmetic logic unit during execution of instructions and storing the operands and the results thereof;

a processor readable storage medium; and

a processor readable code recorded in the processor readable storage medium to

load N data values into the N respective lanes of the register as an operand,

add the next N data values in parallel to the contents within the N lanes of the register using lane arithmetic to form a partial sum in lanes of the register,

add at least one lane of contents within the register to another at least one lane of contents in the register using bit field arithmetic to reduce the partial sum in lanes of the register to a final sum in a lane of the register, the final sum representative of a calculated checksum, and

compare the final sum with the received checksum to verify that the data packet was correctly received.

23. The network device of claim 22, wherein,

the processor readable storage medium is one or more of the set of magnetic storage medium, optical storage medium, or semiconductor storage medium.

24. The network device of claim 22, wherein,

the final sum is in one'"'"'s complement form and the comparison with the received checksum is performed by the processor readable code recorded in the processor readable storage medium by adding the received checksum to the one'"'"'s complement form of the final sum and determining if the result is zero.

25. The network device of claim 22, wherein,

the arithmetic logic unit of the SIMD processor adds the next N data values in parallel to the contents within the lanes of the register using one'"'"'s complement lane arithmetic to form a partial sum in each lane of the register.