[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:	Mathematics at DEC

Moderator:	RUSURE::EDP

Created:	Mon Feb 03 1986
Last Modified:	Fri Jun 06 1997
Last Successful Update:	Fri Jun 06 1997
Number of topics:	2083
Total number of notes:	14613

604.0. "Stripe Set Mapping Function" by SEARAY::EAST () Mon Oct 27 1986 20: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

T.R	Title	User	Personal Name	Date	Lines
604.1		CLT::GILBERT	eager like a child	`Tue Oct 28 1986 01:48`	38
	And that's why I hate word problems. Half way through, tracks, fragments and sectors are introduced without definition. Sigh. Suppose f=3, t=10, and n=4. You want the logical blocks mapped like: unit #0 unit #1 unit #2 unit �3 group 0 0 1 2 3 4 5 6 7 8 9 10 11 group 1 12 13 14 15 16 17 18 19 20 21 22 23 group 2 24 25 26 27 28 29 30 31 32 �3 34 35 group 3 36 37 38 39 40 41 4� 43 44 45 46 47 ... Let the (input) logical block number be x. Now the unit number u(x) is simple: u(x� = (x div f) mod n. The group number g(x) is given by: g(x) = (x div f) div n, or g(x) = x div (fn), and the block nu�ber within a fragm�nt is (x mod f). 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 to the beginning of the unit -- call this b(x). Thus, b(x) mod t will always be less than (t mod f)f. In the above example, x 0 1 2 12 13 14 24 25 26 36 37 38 ... b(x) 0 1 2 3 4 5 6 7 8 10 11 12 ... (b(x) = 9 is missing) Thus, b(x) is something like g(x) f + (x mod f), except that we need to 'skip� some b�ocks -- of every t blocks, we skip (t mod f) blocks. So, b(x) = (g(x) div (t div f)) * t + (g(x) mod (t div f)) * f + (x mod f). (Eq.1) or, b(x) = ( g(x) di� (t div f) ) * (t mod f) + g(x) * f + (x mod f). (Eq.2) Eq.1 is easier to understand; eq.2 is derived fr�m it after noting that (x div k) * n + (x mod k) = (x div k) * (n-k) + x
604.2	Faster than a speeding bullet	10424::EAST		`Tue Oct 28 1986 12:52`	21
	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!
604.3		CLT::GILBERT	eager like a child	`Tue Oct 28 1986 14:47`	36
	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 - fz) + (g(x) div z) fz + (g(x) mod z) f + (x mod f) = (g(x) div z) * (t - fz) + (x mod f) + f ((g(x) div z) * z + (g(x) mod z)) b(x) = (g(x) div z) * (t - fz) + (x mod f) + f g(x) But, t - fz = 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.