1. Home
  2. Embedded Programming
  3. framing strategy for STDM

framing strategy for STDM

Hi everyone,

after evaluating several approaches to schedule activities on a commonly shared bus (see and ) I finally landed in a comfortably deterministic solution, i.e. Synchronous Time Division Multiplexing.

Each access to the bus (transaction) is scheduled by a bus master, I have N slaves with a specific number of transactions with a certain periodicity over a fixed period T. How do I slice T in order not to have transactions overlapping?

I'm pretty sure there's a mathematical formula to get this number and so far I've only came to something like the following:

s = sum(T*n_i) / T = sum(n_i)

where:

s = time slice T = period sum() = summation operator n_i = periodicity over T for slave i (n_i is a rationale number)

Unfortunately in the above formula there's no trace of the need to have non-overlapping transactions. In the following example it seems the amount of transactions are sufficient, but 'periodicity' information has been somehow smeared due to the absence of non-overlapping requirement in the formula:

n_i = 1, 2, 3, 4 => s = 10

T---|---|---|---|---|---|---|---|---|---T | 1 | 2 | 3 | 4 | 2 | 4 | 3 | 4 | 3 | 4 |

Ideally, in order to maintain the periodicity information I'd need to do the following:

T---|---|---|---|---|---|---|---|---|---|---|---T | 1 | | | | | | | | | | | | | 2 | | | | | | 2 | | | | | | | 3 | | | | 3 | | | | 3 | | | | | 4 | | | 4 | | | 4 | | | 4 | | | Meaining that I need to have as many slots as to accommodate the maximum amount of slaves at the same time, so the above formula becomes:

s = N * sum(n_i)

where: N = maximum value for i (i.e. number of slaves)

Main drawback of this approach is the amount of 'empty slots'. But actually you can see that the amount of divisions has increased and indeed in order to keep the periodicity I should change the summation operatore with the LCD (least common divisor), hence:

s = N * LCD(n_i)

Does this all make sense?

Any idea or direction for a more formal approach? I'm sure there must be a ton of info out there, but I'm incapable to correctly formulate the right query to my favourite friend!

Al

--
A: Because it messes up the order in which people normally read text. 
Q: Why is top-posting such a bad thing? 
A: Top-posting. 
Q: What is the most annoying thing on usenet and in e-mail?
Reply to
alb
Loading thread data ...

Unless (until) you can constrain the frequencies of the requests or specify limits on tolerable skew/latency for each, you can't ever "solve" this problem in the general sense.

Trivial example: two slaves each want access at the exact same frequency and can't tolerate any latency (*somebody* has got to wait!).

What (one) "number"?

I presume you mean:

t = T / sum(Ni)

where:

Ni = number of times slave i needs access to the medium in period T t = time slice (including media acquisition/release) per EQUAL SIZED slices

Or,

T---|---|---|---|---|---|---|---|---|---|---|---T | 4 | | | 4 | | | 4 | | | 4 | | | | | 3 | | | | 3 | | | | 3 | | | | | | 2 | | | | | | 2 | | | | | | | | | 1 | | | | | | | |

(notice 3&4 still conflict)

No -- but that could be because I'm fried from washing the car out in the bright sun! :<

Why not look at what you *need* (in terms of total bandwidth) and work UP from there?

I.e., the time it takes PER TRANSACTION (assuming it is fixed for all slaves/transactions) defines the maximum number of slots you can have in a period, T. (Conversely, defines the smallest period T for a given number of slots)

See what sort of slop you have *first*. If

Reply to
Don Y

I would favor a *less* formal approach. I don't get why you are making this so hard. Don't you have control over when the bus masters need access to the bus? And I believe you have said their rates are all multiples of some base rate. So the timing doesn't wander around relatively. Just schedule them so they never ask for the bus at the same time. Do I not understand the problem?

--

Rick
Reply to
rickman

Hi Don,

Don Y wrote: []

You are absolutely right, but I have no idea how to formalize this tolerance to latency in my formula and I keep thinking that the problem has a mathematical solution. For the sake of the discussion I'm limiting the amount of slaves to 4, but in reality there are 16 if not more and potentially more to come. And I hate doing the exercise a million times.

IIRC Tim has talked about the brittleness of such a solution, maybe I'm not in the correct course of thought and there's no clear algorithm to define those slots.

But that is not related to latency, rather to phase w.r.t. T. See the following:

T---|---|---|---|---|---|---|---|---|---|---|---T | 4 | | | 4 | | | 4 | | | 4 | | | | | 4 | | | 4 | | | 4 | | | 4 | |

Oops, funny how we consider clear what is actually completely obscure! Indeed the number I'm talking about is the number of slices.

Pardon me, I should have called s the 'number of slices', not 'time slice'.

But if we introduce 'latency' we can accommodate that conflict in the following way:

0 1 2 3 4 5 6 7 8 9 10 11 T---|---|---|---|---|---|---|---|---|---|---|---T | 4 | | | 4 | | | 4 | | | 4 | | | | | 3 | | | | 3 | | | | | 3 | | | | | 2 | | | | | | 2 | | | | | | | | | 1 | | | | | | | |

We could even swap the last allocated slots for 4 and 3 alternatively on slots 9 and 10 each period.

Ok, I should have said Least Common Multiple of those periods:

s = N * LCM(n1, n2, nN).

Playing with the phases should allow me to minimize the amount of empty slots and meet all periodicity requirements. I'm not sure if the formula has some limitation or can be optimized, it seems to me there are cases where is far from being optimal (4 slaves with 1, 2, 3, 4 can fit in 12 slots as shown, but the formula would give 4*12=48 slots!), maybe because it does not take into account what we defined as 'latency'.

The problem, as formulated, specifies the number of slaves with their periodicity of transactions requirement, where a transaction can be multiple write/read operations on the bus.

I'd rather stay high level at this stage and constraint each function with a defined amount of time (time slice) to meet its throughput. The bus should be *then* dimensioned to meet the requirements.

Reply to
alb

Hi Rick,

rickman wrote: []

There are some cases where you can allow yourself to just go on heads down and if you screw up you'll just go back and reiterate. If you screw up your implementation does not really matter, if the definition is solid you can reimplement from scratch at your leisure and at the expenses of your margins.

But if definition is shaky and your architecture is vulnerable, then you're in for a painful journey that I'm not willing to deal with. I've been there, I've done that...no thanks.

Never talked about *masters*, there's only one master and several slaves. The master does not need access to the bus (or very seldom), it actually grants access to the bus to the slaves. Think about a 1553 bus, the BC rarely needs access, it only provides the necessary transactions for RTs to communicate, either between eachother or with the BC itself.

Now imagine the amount of slaves are > 10 or maybe > 20, each of them with their periods and latencies. Imagine your customer wants to change both the periodicity and the latency because she changed her mind. In order to have something that holds in place without *me* reassigning the accesses each and every time she has her periods [1], I want to get it straight from day 1 and move on on more essential things to do.

Maybe I didn't give you all the elements to see the full picture, hence your limited understanding of it.

Al

[1] it's also applicable if your customer is a man! Men do have periods as well:
formatting link
:-). DISCLAIMER: I'm not seconding the validity of the research, just using to make my point!
Reply to
alb

Cha-Ching! I love it when customers change their minds. :)

Get what straight from day 1? If the problem changes the solution changes.

I think I understand. I think it is a lot more simple than you are making it out to be.

--

Rick
Reply to
rickman

For the moment, ignore *when* the slots (will) occur. Instead, consider them as "scheduling opportunities" -- i.e., at the start of each timeslot, the "scheduler" can decide WHO gets access to that resource for that timeslot.

The difference between this and, e.g., a multitasking executive is the timeslots are non-preemptible (once you have a timeslot, it is yours for the duration!) *and* nonextensible (once the timeslot ends, so too does your dominion over it!).

[Of course, the scheduler *could* decide that you should have the next timeslot, as well...]

The other difference is that you are doing your scheduling "a priori"... deciding who WILL get each (future) timeslot instead of *immediately* (who will get *this* timeslot). Presumably, this is because you know the nature of your "consumers" and their needs are static... don't change over time.

[Contrast this with a general purpose system where new needs can arise at any given time *and* their constraints can vary -- hence the need for a scheduler "on the spot"]

With this abstraction in mind, any time you have two or more consumers vying for a timeslot, use scheduling criteria is most pertinent for your application. E.g., should the consumer with the nearest deadline go first? the consumer with the least amount of slack time? the consumer who can finish up quickest? the consumer who has the highest "abstract" importance? etc.

This, then, leaves the sole issue being one of "how big should each timeslot be". (from this, it is trivial to determine *when* each timeslot will occur relative to T=0)

Simple: if each SLAVEi requires some specific Ni number of accesses to the resource in an interval T, then sum all of the Ni and you know how many slices there must be in time T. Each slice will be T/sum units "wide" (but, this width will also include the time to acquire and release the resource).

Add any "overhead" slices you might want to accommodate. E.g., if you want to ensure the "MASTER" can obtain the resource X times in each T interval, then add X to the "sum".

The acid test is then ensuring that T/slices is "big enough" for the sorts of transactions you want to take with that resource. E.g., if T/slice=t is 10 ms and you discover that it takes *11* ms to do what you want to do in that interval, then you either increase the width of the timeslice t (by increasing T or by decreasing the total number of slots

*in* each T) or change the protocol so you can accomplish the same amount of "work" in the shorter time available (higher data rate, shorter packet, less overhead, distributing transactions over multiple accesses/timeslots)

Yes. But this manifests as "frequency jitter" (if you are thinking in the frequency domain)

Again, without constraining "acceptable latency", you can't come up with a general solution.

Instead, look at it as "how many slots do you *need*" (i.e., sum(Ni)+X). Or, how many slots can you *get* (i.e., T/minimum transaction width). Then, assign them based on *A* scheduling criteria and leave whatever is leftover as "empty" -- that's what you have available for "future changes" (i.e., when you decide you need to give SLAVE3 a bit more access to the resource BECAUSE the latency that it is incurring causes it to screw up from time to time... or, whatever)

ToMAYto, toMAHto. It's a fixed resource. Define and the rest will assume new constraints based on that first definition.

Reply to
Don Y

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.