Zbr's days.
←June→
Sun Mon Tue Wed Thu Fri Sat
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
←2007→
Months
Jan Feb Mar
Apr May Jun
Jul Aug Sep
Oct Nov Dec

About :: TODO :: Blog :: RSS :: Old blog :: Projects :: GIT :: Gallery :: Notes

Tue, 19 Jun 2007

CRC performance depending on the word size.

To select perfect CRC coding technique which will be used for distributed storage I'm about to start designing, I've ran set of tests to determine how CRC speed depends on size of the word used in calculation. I use simple XOR CRC which just performs XOR operation over provided data block several times and then shows its performance (i.e. number of operations per timeframe).

Here is CRC performance for the same blocksize and number of iterations (i.e. number of CRC sums performed over the same block):

size: 4096, num: 100000, bits: 64, speed: 459.630646 kop/sec.
size: 4096, num: 100000, bits: 32, speed: 348.913483 kop/sec.
size: 4096, num: 100000, bits: 16, speed: 176.067184 kop/sec.
As expected, CRC speed was improved with increasing size of the word, unfortunately for galois field multiplication speed increase is not enough.
Let's discuss Reed-Solomon coding, which requires galois-field multiplication of checksummed (or raw) data words.
For 16 bit CRC sum galois filed multiplication can be performed using 2^16 table (2 lookups per multiplication or division operation) lookup, but for 32 bit CRC galois field multiplication in GF(2^32) can not be performed using table, since it will be too big. To perform galois field multiplication essentially one needs to solve a system of equations, number of equations is equal to size of the values being multiplied, i.e. 32 in our case. Even the fastest method of solving system of equations will be much much slower than 16 bit CRC plus its 2 lookups. Even using Cauchy matrixes for Reed-Solomon encoding with galois multiplication instead of Vandermonde one results in much slower code than table lookup.

So, for the maximum performance we either need to limit Reed-Solomon system to 16 bit CRC (galois field multiplication is used in RAID coding for example), or to use different coding method.
I'm studing WEAVER codes which are faster by design (and use only XOR operations without complex galois field multiplications), but they have own limits, so I'm trying to understand how distributed system with such erasure coding will suffer from using it.

/devel/math/codes :: Link / Comments (0)

Please solve this captcha to be allowed to post (need to reload in a minute): 82 - 40

Comments are closed for this story.