**diff options**

author | Alex Pyrgiotis <apyrgio@grnet.gr> | 2013-03-08 14:37:03 +0200 |
---|---|---|

committer | Jens Axboe <axboe@kernel.dk> | 2013-03-08 19:10:13 +0100 |

commit | d474cbc9ba33448848b50cc697622a402e91e33e (patch) | |

tree | 682e078eba1f6c27cd2fc4274ee4eb8794cb624a /lib/lfsr.h | |

parent | c3a1b740381cb19e467c8588562bac4d6cbbb199 (diff) | |

download | fio-d474cbc9ba33448848b50cc697622a402e91e33e.tar.gz fio-d474cbc9ba33448848b50cc697622a402e91e33e.tar.bz2 |

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).
Signed-off-by: Alex Pyrgiotis <apyrgio@grnet.gr>
Signed-off-by: Jens Axboe <axboe@kernel.dk>

Diffstat (limited to 'lib/lfsr.h')

-rw-r--r-- | lib/lfsr.h | 12 |

1 files changed, 8 insertions, 4 deletions

@@ -3,7 +3,7 @@ #include <inttypes.h> -#define FIO_MAX_TAPS 8 +#define FIO_MAX_TAPS 6 struct 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 |