framing strategy for STDM

Hi everyone,

after evaluating several approaches to schedule activities on a commonly 
shared bus (see <news:cc1b52Fah05U1@mid.individual.net> and 
<news:ccbvuaF40tpU1@mid.individual.net>) 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?

On 11/21/2014 7:43 AM, alb wrote:
> 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?

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!).

> I'm pretty sure there's a mathematical formula to get this number and so

What (one) "number"?

> 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)

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

> 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 |   |   |

Or,

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

(notice 3&4 still conflict)

> 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?

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

> 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!

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 <0, you're screwed (T has
to change -- or, the Ni or t).  If 0, you can make it work *ONLY* if
you can force slaves to access the bus exactly when you PROCLAIM they
must.  Anything beyond that (> 0) is "wiggle room".

On 11/21/2014 9:43 AM, alb wrote:
> Hi everyone,
>
> after evaluating several approaches to schedule activities on a commonly
> shared bus (see <news:cc1b52Fah05U1@mid.individual.net> and
> <news:ccbvuaF40tpU1@mid.individual.net>) 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!

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

Hi Don,

Don Y <this@is.not.me.com> wrote:
[]
>> 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?
> 
> 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.

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.

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

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 |   |
 

>> I'm pretty sure there's a mathematical formula to get this number and so
> 
> What (one) "number"?

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

>> 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)
> 
> 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

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

>> 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 |   |   |
> 
> Or,
> 
> T---|---|---|---|---|---|---|---|---|---|---|---T
> | 4 |   |   | 4 |   |   | 4 |   |   | 4 |   |   |
> |   | 3 |   |   |   | 3 |   |   |   | 3 |   |   |
> |   |   | 2 |   |   |   |   |   | 2 |   |   |   |
> |   |   |   |   | 1 |   |   |   |   |   |   |   |
> 
> (notice 3&4 still conflict)

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.

>> 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?
> 
> No -- but that could be because I'm fried from washing the car out in
> the bright sun!  :<

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'.

>> 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!
> 
> Why not look at what you *need* (in terms of total bandwidth) and work
> UP from there?

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.

> 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 <0, you're screwed (T has
> to change -- or, the Ni or t).  If 0, you can make it work *ONLY* if
> you can force slaves to access the bus exactly when you PROCLAIM they
> must.  Anything beyond that (> 0) is "wiggle room".

The transaction time imposes an implementation choice for the bus width 
and the protocol stack of a transaction, and this is something I would 
like to avoid at the architectural level. At the end of the exercise I 
should be able to define what is the transaction time we have available 
and what we need to do with it (write/read ops).

Only then I can think in terms of implementation, shall it be a 16 bit 
wide bus or 32 or 64, what is the access time, 25ns, 40ns, 100ns. All 
those details do not have a concrete meaning beyond 'feasability' 
(certainly it would be difficult to implement a bus of 1024 bits and 
access time of 2ns!)

Al

Hi Rick,

rickman <gnuarm@gmail.com> wrote:
[]
> I would favor a *less* formal approach.  I don't get why you are making 
> this so hard.  

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.

> Don't you have control over when the bus masters need 
> access to the bus?

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.

> 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.

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.

> Do I not understand the problem?

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: http://en.wikipedia.org/wiki/Irritable_male_syndrome :-). 
DISCLAIMER: I'm not seconding the validity of the research, just using 
to make my point!

On 11/24/2014 5:39 AM, alb wrote:
> Hi Rick,
>
> rickman <gnuarm@gmail.com> wrote:
> []
>> I would favor a *less* formal approach.  I don't get why you are making
>> this so hard.
>
> 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.
>
>> Don't you have control over when the bus masters need
>> access to the bus?
>
> 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.
>
>> 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.
>
> 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.

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


> 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.

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


>> Do I not understand the problem?
>
> Maybe I didn't give you all the elements to see the full picture, hence
> your limited understanding of it.

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

-- 

Rick

Hi Al,

On 11/24/2014 2:57 AM, alb wrote:
>> 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.
>
> 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.

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 <whatever> 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)

>> Trivial example:  two slaves each want access at the exact same frequency
>> and can't tolerate any latency (*somebody* has got to wait!).
>>
>
> 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 |   |
>
>
>>> I'm pretty sure there's a mathematical formula to get this number and so
>>
>> What (one) "number"?
>
> Oops, funny how we consider clear what is actually completely obscure!
> Indeed the number I'm talking about is the number of slices.
>
>>> 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)
>>
>> 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
>
> Pardon me, I should have called s the 'number of slices', not 'time
> slice'.

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)

>>> 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 |   |   |
>>
>> Or,
>>
>> T---|---|---|---|---|---|---|---|---|---|---|---T
>> | 4 |   |   | 4 |   |   | 4 |   |   | 4 |   |   |
>> |   | 3 |   |   |   | 3 |   |   |   | 3 |   |   |
>> |   |   | 2 |   |   |   |   |   | 2 |   |   |   |
>> |   |   |   |   | 1 |   |   |   |   |   |   |   |
>>
>> (notice 3&4 still conflict)
>
> 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.

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

>>> 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?
>>
>> No -- but that could be because I'm fried from washing the car out in
>> the bright sun!  :<
>
> 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'.

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)

>>> 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!
>>
>> Why not look at what you *need* (in terms of total bandwidth) and work
>> UP from there?
>
> 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.

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

>> 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 <0, you're screwed (T has
>> to change -- or, the Ni or t).  If 0, you can make it work *ONLY* if
>> you can force slaves to access the bus exactly when you PROCLAIM they
>> must.  Anything beyond that (> 0) is "wiggle room".
>
> The transaction time imposes an implementation choice for the bus width
> and the protocol stack of a transaction, and this is something I would
> like to avoid at the architectural level. At the end of the exercise I
> should be able to define what is the transaction time we have available
> and what we need to do with it (write/read ops).

I look at it as requirements driven:  what do you NEED to do.  Then, figure
out how/if you can *do* it.  I.e., if you are moving X data/time unit, then
your comms system needs an aggregate bandwidth of AT LEAST X/T.  "Gee,
that rules out Bell 103 modems!"

> Only then I can think in terms of implementation, shall it be a 16 bit
> wide bus or 32 or 64, what is the access time, 25ns, 40ns, 100ns. All
> those details do not have a concrete meaning beyond 'feasability'
> (certainly it would be difficult to implement a bus of 1024 bits and
> access time of 2ns!)