Protecting 3x16 bits with 16 bits ? (crc16)
|
Prev: Protecting 3x16 bits with 16 bits ? (Raptor codes)
Next: Protecting 3x16 bits with 16 bits ? (CRC16 on GPU ?! ;))
From: Skybuck Flying on 11 Feb 2010 15:28 Maybe this is a good solution, crc16: http://en.wikipedia.org/wiki/Cyclic_redundancy_check (math group included too, maybe it will get through ;)) Bye, Skybuck. "Skybuck Flying" <IntoTheFuture(a)hotmail.com> wrote in message news:6f76a$4b745dac$d53371df$29602(a)cache4.tilbu1.nb.home.nl... > Hello, > > Soon I will attempt some gpgpu development/shader development... I have > already done some tests and so forth the gpu and it's memory seem to be > working just fine... (and fast ;) :)) No bit errors so far. > > However the thought of bit errors creeping into it is indeed a bit > scary... The hardware is older from 2006: nvidia 7900 gtx with 512 MB of > RAM. (OpenGL will be used for it's development and cg shaders). > > It seems this gpu works with 4 floating point fields per register. Either > 16 bit or 32 bit. Maybe it's always 32 bit ? I am not sure... probably not > because 16 bit performance is twice as high. > > I plan on using: 3x16 bits so that needs a "vector" register with 4x16 > bits. > > This means only 48 bits are used for example the .x, .y, .z and this > leaves the .w to be used for something else. > > For me it could be interesting to make two modes of operations for the > final product: > > First mode which uses 3x16 bits in registers and memory. > Second mode which uses 4x16 bits in registers and memory. > > This would make the second mode slightly less memory efficient. > > I have a feeling that the gpu is very fast and has plenty of processing > power/instruction power. > > So I might get away with adding some extra "data integrity checks" to the > .x, .y, .z components and store them in .w component. > > So the idea is basically to apply a 16 bit "data integrity check" to 48 > bits of data. Using Shader Model 3.0 instructions/CG language for now... > > I wonder what is a good data integrity checking algorithm to detect bit > errors in this situation ? > > The data integrity algorithm should not use to many branches... hopefully > just one branch to compare results ?! ;) > > It shouldn't use too many memory look ups... that would be bad for > performance ?! ;)... > > The 3x16 bits could be unpacked into 6x8 bit quantities which are then > stored in 32 bit floating point registers to do further calculations on... > > If the algorithm is in floating point format and limits itself to 8 bit to > 16 bit precision than that should work just fine... algorithms can be done > with integers... I can convert it to 16 bit floating points ;) I could > even convert it to 64 bit floating point but that would require 64 bit > software math and would slow things done so better not to do that... > > The following operations are definetly available for such an algorithm: > 32 bit floating point addition, can be used as 8 bit or 16 bit integer > addition, (max 24 bit) > 32 bit floating point subtraction, can be used as 8 bit or 16 bit integer > subtraction, (max 24 bit) > 32 bit floating point multiplication, can be used as 8 bit or 16 bit > integer multiplication, (max 24 bit) > 32 bit floating point division, can be used as 8 bit or 16 bit integer > division, (max 24 bit) > > and ofcourse special graphics instructions: > dot operations > interpolation operations. (But I have never used them and don't quite > understand on the gpu at least but I am willing to learn ;) :)) > > Some idea's in my head for now: > > 1. A simply weak "checksum" where everything is summed together... seems > like a very bad algorithm, since bit flips might go undetected. > 2. A crc32 ? But the algorithm I have requires a large table and thus > memory lookups... doesn't seem to smart... and crc32 is like a large > division ? maybe overkill for just 48 bits of data ? > 3. I can vaguely remember something about parity ? Is that the same as a > checksum or different ? I think that's different... parity counts the bits > set and then stores that ? Doesn't seem so strong ? > 4. I can vaguely remember an error correcting code which could correct 1 > bit error ? by using two parities or so ? one vertical, one horizontal ? > > So I ask you software programmers/developers and hardware designers and > algorithm designers :) out there the following question: > > What kind of error detection algorithms, or maybe even error correction > algorithms are out there that you think would be suited for this special > situation ? > > Also maybe you can design something specially for this situation ? > > (The algorithm could later also be applied to slightly smaller bits like > only 16 bits, or 32 bits, or maybe even just 8 bits, but stored in 16 > bits... that would be nice.) > > Bye, > Skybuck. > |