Conference rusure::math

604.0. "Stripe Set Mapping Function" by SEARAY::EAST () Mon Oct 27 1986 23:43

    I'm looking for a set of functions that will map a logical block number
    from a large virtual stripe set to a block on one of the units in the
    stripe set. I've fiddled around some, trying to come up with one, and
    somebody suggested that this might be THE PLACE to get the answer. 
    
    Here are the specifics.  Any suggestions, pointers, or functions
    (!) will be appreciated.
    
    Define a virtual unit to consist of n homogeneous physical units.
    Each unit has k blocks on it, numbered from 0 to k-1.  The logical
    block numbering space for the  virtual unit is then 0..n*k-1. 
    
    The mapping function from the virtual LBN to a specific unit's LBN
    maps the first f blocks on unit 0, LBNs 0..f-1; the next f blocks
    on unit 1, LBNs 0..f-1, the next f on unit 2, LBNs 0..f-1, and so
    on, until LBN n*f.  LBNs n*f..n*(f+1)-1 map onto unit 0, LBNs f..2*f-1.
    LBNs n*(f+1)..n*(f+2)-1 map onto unit 1, LBNs f..2*f-1, and so on.
    
    The number "f" is the fragment size -- that is, it is the number
    of contiguous LBNs that are mapped to contiguous LBNs on the same
    unit.
    
    Such a function is:
    
    	unit = (lbn DIV f) MOD n
    	LBN = ((lbn DIV f) DIV n) * f + lbn MOD f
    
    Now to complicate matters.  Suppose we introduce the following rule:
    
    	Given that each unit has a track size, t, never split a fragment
    	across a track.  In other words, allocate a whole number of
    	fragments to a track, and simply never map those sectors at
    	the end of the track that don't constitute an entire fragment.
    
    For example, given a track size of 10 and a fragment size of 3,
    it follows that the last sector on each track will never be mapped.
    
    Question:  what function will follow this rule, and map a source
    	       LBN to a unit and LBN on that unit?
    
    Remember:  we never want to map any LBN twice (this is a function,
    	       after all!)
    
    Any assistance in finding such a mapping will be a big help.
    
    Thanks,
    Jeff East

    Talk about quick response!  Thank you very much for the solution. There
    is a small typo  that I'll bring up, just in case anyone is interested: 
    
    >>>But now for the complication.  Each unit has only (t mod f)*f useable
    >>>blocks per track, and we want to find the block number of x, relative

    Actually, each unit has only (t div f)*f useable blocks.  
    
    Also, I'm totally unable to fathom where (eq. 2) came from.  Feeding
    it into the simulation doesn't yield the same answers as (eq. 1),
    which yields a correct solution.
    
    However, thank you again.  Your help was very timely, and I sure
    appreciate it.
    
    Jeff
    
    p.s.  I couldn't resist the word problem.  The other choice was
          to describe the series in terms of ordered pairs...but I
          hadn't figured out a way to do so that would reflect the general
    	  problem. Fourth grade strikes again!

Thanks for pointing out the problems.  Equation 1 is:

	b(x) = (g(x) div (t div f)) * t
	     + (g(x) mod (t div f)) * f + (x mod f).

Letting z = (t div f), this is:

	b(x) = (g(x) div z) * t + (g(x) mod z) * f + (x mod f)

	     = (g(x) div z) * (t - f*z) + (g(x) div z) * f*z
	     + (g(x) mod z) * f + (x mod f)

	     = (g(x) div z) * (t - f*z) + (x mod f)
	     + f * ((g(x) div z) * z + (g(x) mod z))

	b(x) = (g(x) div z) * (t - f*z) + (x mod f) + f * g(x)

But,
	t - f*z = t - f*(t div f) = t mod f

So substituting the definition of z back into b(x) gives:

	b(x) = (g(x) div (t div f)) * (t mod f) + (x mod f) + f * g(x)

This is the same as before.



Note that when evaluating these expressions in your program,

	(x div a) div b = x div (a*b)

This will reduce the number of divisions.


P.S.  The funny characters in .1 are due to some nasty line noise.