Method for efficient generation of a Fletcher checksum using a single SIMD pipeline
The generation of Fletcher/Alder partial checksums are transformed from a space that requires integer multiplications and additions to a space that requires only integer additions and shifts on a single SIMD pipeline capable processor. This transformation permits the use of Fletcher/Alder checksums on processors where the performance of SIMD instructions are sub-optimal, on CMT processors that support a single SIMD pipeline as well as other processors that can be configured by executing software to implement SIMD operations for a single SIMD pipeline. The implementation of the process with this transformation on a general-purpose computer system transforms that general-purpose computer system into a special-purpose computer system that uses a single SIMD pipeline to generate a Fletcher/Alder checksum. The elimination of integer multiplications in the generation of the partial checksums results in a significant improvement in performance.
1. A computer-based method comprising:
using a single SIMD pipeline in a processor to perform a process for generating a Fletcher/Alder checksum for a data string, said process comprising:
accumulating a plurality of first sub-partial checksums S 1 [ 0 ], S 1 [ 1 ], . . . , S 1 [N−1],
where N is an integer;
N is a degree of SIMD processing; and
said plurality of first sub-partial checksums S 1 [ 0 ], S 1 [ 1 ], . . . , S 1 [N−1] are stored in integer registers of said processor;
accumulating a plurality of second sub-partial checksums S 2 [ 0 ], S 2 [ 1 ], . . . , S 2 [N−1] wherein said plurality of second sub-partial checksums S 2 [ 0 ], S 2 [ 1 ], . . . , S 2 [N−1] are stored in integer registers of said processor;
accumulating said plurality of second sub-partial checksums S 2 [ 0 ], S 2 [ 1 ], . . . , S 2 [N−1] to generate a SIMD second partial checksum;
scaling said SIMD second partial checksum, using a shift operation, by N to obtain a scaled SIMD second partial checksum;
correcting said scaled SIMD second partial checksum to generate a second partial checksum S 2 ;
accumulating said plurality of first sub-partial checksums S 1 [ 0 ], S 1 [ 1 ], . . . , S 1 [N−1] to generate a first partial checksum S 1 ;
combining said first and second partial checksums S 1 , S 2 to generate a Fletcher/Alder checksum for said data string; and
storing said Fletcher/Alder checksum in a memory wherein said Fletcher/Alder checksum is for use in determining integrity of said data string.
2. The process of claim 1 further comprising:
loading N-data units of said data string into an input register.
3. The process of claim 2 wherein said accumulating said plurality of second sub-partial checksums S 2 [ 0 ], S 2 [ 1 ], . . . , S 2 [N−1] includes accumulating said plurality of second sub-partial checksums S 2 [ 0 ], S 2 [ 1 ], . . . , S 2 [N−1] for said N-data units in said input register.
4. The process of claim 3 wherein said accumulating a plurality of first sub-partial checksums S 1 [ 0 ], S 1 [ 1 ], . . . , S 1 [N−1] includes accumulating said plurality of first sub-partial checksums S 1 [ 0 ], S 1 [ 1 ], . . . , S 1 [N−1] for said N-data units in said input register.
5. The process of claim 4 further comprising:
repeating said loading and accumulatings for said N-data units for each set of N-data units in said data string.
6. The process of claim 1 further comprising:
detecting an overflow condition;
performing said repeating after said detecting said overflow condition.
7. The process of claim 1 further comprising:
virtually partitioning at least one integer register to include at least two of said first sub-partial checksums in said plurality of first sub-partial checksums S 1 [ 0 ], S 1 [ 1 ], . . . , S 1 [N−1].
8. The process of claim 1 further comprising:
virtually partitioning at least one integer register to store at least two of said second sub-partial checksums in said plurality of second sub-partial checksums S 1 [ 0 ], S 1 [ 1 ], . . . , S 1 [N−1].
9. A computer-based method comprising:
using a single SIMD pipeline in a processor to perform a process for generating a Fletcher/Alder checksum for a data string, said process comprising:
virtually partitioning integer registers for storage of a plurality of first sub-partial checksums S 1 [ 0 ], S 1 [ 1 ], . . . , S 1 [N−1],
where N is an integer; and
N is a degree of SIMD processing;
virtually partitioning integer registers for storage of a plurality of second sub-partial checksums S 2 [ 0 ], S 2 [ 1 ], . . . , S 2 [N−1];
loading N-data units of a data string into an input register;
accumulating, in parallel, said plurality of first sub-partial checksums S 1 [ 0 ], S 1 [ 1 ], . . . , S 1 [N−1] for said N-data units;
accumulating, in parallel, said plurality of second sub-partial checksums S 2 [ 0 ], S 2 [ 1 ], . . . , S 2 [N−1] for said N-data units;
repeating said load operation and said accumulating operations for each set of N-data units in said data string;
accumulating said plurality of second sub-partial checksums to generate a SIMD second partial checksum;
scaling said SIMD second partial checksum, using a shift operation, by N to obtain a scaled SIMD second partial checksum;
correcting said scaled SIMD second partial checksum to generate a second partial checksum S 2 ;
accumulating said plurality of first sub-partial checksums to generate a first partial checksum S 1 ;
combining said first and second partial checksums S 1 , S 2 to generate a checksum for said data string; and
storing said checksum in a memory.
10. The process of claim 9 further comprising:
detecting an overflow condition;
performing said repeating after said detecting said overflow condition.
11. A computer program product comprising a non-transitory computer readable storage media having embodied therein instructions for a method comprising:
using a single SIMD pipeline in a processor to perform a process for generating a Fletcher/Alder checksum for a data string, said process comprising:
accumulating a plurality of first sub-partial checksums S 1 [ 0 ], S 1 [ 1 ], . . . , S 1 [N−1],
where N is an integer;
N is a degree of SIMD processing; and
said plurality of first sub-partial checksums S 1 [ 0 ], S 1 [ 1 ], . . . , S 1 [N−1] are
stored in integer registers of said processor;
accumulating a plurality of second sub-partial checksums S 2 [ 0 ], S 2 [ 1 ], . . . , S 2 [N−1] wherein said plurality of second sub-partial checksums S 2 [ 0 ], S 2 [ 1 ], . . . , S 2 [N−1] are stored in integer registers of said processor;
accumulating said plurality of second sub-partial checksums S 2 [ 0 ], S 2 [ 1 ], . . . , S 2 [N−1] to generate a SIMD second partial checksum;
scaling said SIMD second partial checksum, using a shift operation, by N to obtain a scaled SIMD second partial checksum;
correcting said scaled SIMD second partial checksum to generate a second partial checksum S 2 ;
accumulating said plurality of first sub-partial checksums S 1 [ 0 ], S 1 [ 1 ], . . . , S 1 [N−1] to generate a first partial checksum S 1 ;
combining said first and second partial checksums S 1 , S 2 to generate a Fletcher/Alder checksum for said data string; and
storing said Fletcher/Alder checksum in a memory wherein said Fletcher/Alder checksum is for use in determining integrity of said data string.