Proposed LFSR implementation
Subsystems (2)
cover Proposed LFSR implementation
Hi Jens and list,
Due to the open-source nature of fio, I figured I'd share with you something I've created while working on Archipelago[1], a storage backend for synnefo[2] VMs.
We wanted to have an entity that can do random permutations fast, so we've created an XNOR Galois LFSR (more details about the implementation in the following patches) that should perform "better" than the generic one for I/O related tasks.
By "better", I don't mean only in terms of speed - since by definition LFSRs are insanely fast - but also in terms of their properties as PRNGs. The main issue with LFSRs that can't make them a serious candidate for I/O tasks is that due to their shifting nature, they cannot produce a sequence of numbers that differs widely from one to the next. This implementation should tackle this problem and should make LFSRs promising candidates at least for randrepeat jobs.
I actually went one step further and tested this implementation against the TESTU01 suite. A generic LFSR fails all the tests as expected, but this LFSR passes 3 to 5 out the 10 entry level tests of the suite. This shows that they are far from suitable as stand-alone PRNGs for cryptography, but should be pretty decent for I/O tasks.
Anyways, hopefully you will find this patch set interesting for inclusion in your code. If you have any questions, feel free to ask.
Thanks,
Alex
[1] http://synnefo-software.blogspot.gr/2013/02/we-are-happy-to-announce-that-synnefo_11.html
[2] http://www.synnefo.org/
[3] http://www.iro.umontreal.ca/~simardr/testu01/tu01.html
Alex Pyrgiotis (2):
Improve LFSR implementation
Add a simple test for LFSR generator
Makefile | 9 ++ filesetup.c | 2 +- lib/lfsr.c | 421 ++++++++++++++++++++++++++-------------------------------- lib/lfsr.h | 12 +- t/axmap.c | 2 +- t/lfsr-test.c | 127 ++++++++++++++++++ 6 files changed, 334 insertions(+), 239 deletions(-) create mode 100644 t/lfsr-test.c
Signature · 1 line
1.8.1.4
PATCH 1/2 Improve LFSR implementation
Changes:
1. Use Galois LFSR instead of Fibonacci LFSR.
2. Use XNOR gates instead of XOR gates.
3. Add tap sizes for LFSRs ranging from 3-bits to 15-bits.
4. Add spin parameter.
Rationale:
1. Fibonacci LFSRs have the following drawbacks:
a. Their next state can not be computed in one cycle, since the input
bit must be propagated serially through the XOR gates. Galois
LFSRs however, can be computed instantly with XOR-masks.
b. Their state changes cannot be considered "irregular", even by I/O
standards. Actually, if the current state of an n-bit LFSR is x,
then the next will either be (x >> 1) or (2^n + (x >> 1)). Galois LFSRs have instead their XOR gates interleaved with their bits, which means that the inner bits are changed as well, besides of the shifting. If the number of taps is z, this means that the different outcomes are 2^(z + 1).
2. An LFSR with XOR gates has the all-zeroes state as illegal. Since zero is valid for most I/O operations, it would be more intuitive to use XNOR gates, that have as the all-ones state as illegal.
3. Allow smaller I/O benchmarks to use LFSRs.
4. The spin parameter follows the same rationale as in 1b. To make the LFSR outcome "appear" less predictable, we can spin internally the LFSR state and produce the i-th number. To understand the spin parameter, consider the following state sequence of a 3-bit LFSR:
0, 2, 3, 5, 6, 1, 4
Same LFSR, spin value 2: 0, 3, 6, 4, 2, 5, 1
But what is the benefit from using spin? Well, the benefits are two-fold:
a. For the same I/O size, we can create a different I/O sequences.
b. Following the rationale of 1b, we can have more variable outcomes.
If the spin value is "i" and the taps are "z", the number of
different outcomes become i * 2^(z + 1).
filesetup.c +1 -1
@@ -966,7 +966,7 @@ int init_random_map(struct thread_data *td) seed = td->rand_seeds[FIO_RAND_BLOCK_OFF ]; -if (!lfsr_init (&f->lfsr, blocks, seed)) +if (!lfsr_init (&f->lfsr, blocks, seed, seed &0xF ))continue ; }else if (!td->o.norandommap) { f->io_axmap =axmap_new (blocks);
lib/lfsr.c +188 -233
466 lines not on this page · raw message
lib/lfsr.h +8 -4
@@ -3,7 +3,7 @@#include <inttypes.h> -#define FIO_MAX_TAPS 8 +#define FIO_MAX_TAPS 6struct lfsr_taps {unsigned int length;
@@ -12,14 +12,18 @@ struct lfsr_taps {struct fio_lfsr { +uint64_t xormask;uint64_t last_val; +uint64_t cached_bit;uint64_t max_val;uint64_t num_vals; -struct lfsr_taps taps; +uint64_t cycle_length; +unsigned int spin; };int lfsr_next (struct fio_lfsr *fl,uint64_t *off,uint64_t ); -int lfsr_init (struct fio_lfsr *fl,uint64_t size,unsigned long seed); -void lfsr_reset (struct fio_lfsr *fl,unsigned long seed); +int lfsr_init (struct fio_lfsr *fl,uint64_t size, +unsigned long seed,unsigned int spin); +int lfsr_reset (struct fio_lfsr *fl,unsigned long seed);#endif
t/axmap.c +1 -1
@@ -34,7 +34,7 @@ int main(int argc, char *argv[])printf ("Using %llu entries\n" , (unsigned long long ) size); -lfsr_init (&lfsr, size, seed); +lfsr_init (&lfsr, size, seed, seed &0xF ); map =axmap_new (size); osize = size;
Signature · 1 line
1.8.1.4
PATCH 2/2 Add a simple test for LFSR generator
In reply to Alex PyrgiotisAdds a simple test suite to check the speed of the LFSR generator and verify its results. Just run:
make t/lfsr-test
./t/lfsr-testto compile the test suite and print its usage
create mode 100644 t/lfsr-test.c
Makefile +9 -0
@@ -141,15 +141,21 @@ T_AXMAP_OBJS = t/axmap.o T_AXMAP_OBJS += lib/lfsr.o lib/axmap.o T_AXMAP_PROGS = t/axmap +T_LFSR_TEST_OBJS = t/lfsr-test.o +T_LFSR_TEST_OBJS += lib/lfsr.o +T_LFSR_TEST_PROGS = t/lfsr-test + T_OBJS = $(T_SMALLOC_OBJS) T_OBJS += $(T_IEEE_OBJS) T_OBJS += $(T_ZIPF_OBJS) T_OBJS += $(T_AXMAP_OBJS) +T_OBJS += $(T_LFSR_TEST_OBJS) T_PROGS = $(T_SMALLOC_PROGS) T_PROGS += $(T_IEEE_PROGS) T_PROGS += $(T_ZIPF_PROGS) T_PROGS += $(T_AXMAP_PROGS) +T_PROGS += $(T_LFSR_TEST_PROGS) ifneq ($(findstring $(MAKEFLAGS),s),s) ifndef V
@@ -204,6 +210,9 @@ t/genzipf: $(T_ZIPF_OBJS) t/axmap: $(T_AXMAP_OBJS) $(QUIET_LINK)$(CC) $(LDFLAGS) $(CFLAGS) -o $@ $(T_AXMAP_OBJS) $(LIBS) $(LDFLAGS) +t/lfsr-test: $(T_LFSR_TEST_OBJS) + $(QUIET_LINK)$(CC) $(LDFLAGS) $(CFLAGS) -o $@ $(T_LFSR_TEST_OBJS) $(LIBS) $(LDFLAGS) + fio: $(OBJS) $(QUIET_LINK)$(CC) $(LDFLAGS) $(CFLAGS) -o $@ $(OBJS) $(LIBS) $(LDFLAGS)
t/lfsr-test.c new file +127 -0
127 lines not on this page · raw message
Signature · 1 line
1.8.1.4