Arbiter design problem?

Hi all,

I have two problem when reading the paper from
[url]http://www.siliconlogic.com/pdf/Arbiters_MattWeber_SLE.pdf [/url]

[1] Is Arbiter pure comb logic? If yes, shall its comb logic delay be
constrained to within one clock cycle?
[2] Shall one request and one grant both hold only one clock cycle?

Best regards, 
Davy

Thanks for interestign link.

> [1] Is Arbiter pure comb logic? If yes, shall its comb logic delay be
> constrained to within one clock cycle?

In general no. Only trivial static priority arbiter can be a simple
combinational logic. In practice the aribters need to store
a prior state (or states) information to modify the priority
and this requires sequential logic/memory etc.

The priority is made dynamic to achieve some particular goals:
for example to prevent starvation of low priority requesters while
still give low latency to high priority ones.
It all very much depends on application.
Network devices have really elaborate arbiter algorithms.

> [2] Shall one request and one grant both hold only one clock cycle?

Obviously request will be active for several clock cycles.
This is beacuse some waiting time for acknowledge is necessary.
(If not then why would we need arbiter?)

Acknowledge is one clock cycle but this is because there is
no beneft in making it any longer.
One cycle acknowledge is "atomic"

BTW Paper specifies many more advanced schemes where
acknowledge is delayed and a pointers are used in requester
to figure out how many requests have been acknowledged.

Cheers,
Przemek


Davy wrote:
> Hi all,
>
> I have two problem when reading the paper from
> [url]http://www.siliconlogic.com/pdf/Arbiters_MattWeber_SLE.pdf [/url]
>
> [1] Is Arbiter pure comb logic? If yes, shall its comb logic delay be
> constrained to within one clock cycle?
> [2] Shall one request and one grant both hold only one clock cycle?
> 
> Best regards, 
> Davy

[1] Is Arbiter pure comb logic?

Definitely not except for the case when a registered reqest signal is
given by the resourse requesting entity.

>> If yes, shall its comb logic delay be constrained to within one clock cycle?

In case the request signals are registered (in the requesting entity )
before usage in the Arbiter the above statement could hold true . The
protocol may be that the requesting entity holds its request line high
untill the grant signal is received by it.

Usually the arbiter implementation is using an fsm opeating on the bus
clock and reset signal (eg an AHB arbiter which operates on HCLK and
Hresetn)

>>[2] Shall one request and one grant both hold only one clock cycle?

Request needs to be registered either in the requesting entity or the
arbiter fsm untill it is processed (ie held valid untill the previous
resource assignment is completed). The grant may be of one cycle
duration informing the requesting of the resource allocation.

An exception may be in the case of DMA when a burst of transfers is
required between it and a requesting peripheral/memory.

[2] Shall one request and one grant both hold only one clock cycle?
bazarnik@hotmail.com wrote:
> Thanks for interestign link.
>
> > [1] Is Arbiter pure comb logic? If yes, shall its comb logic delay be
> > constrained to within one clock cycle?
>
> In general no. Only trivial static priority arbiter can be a simple
> combinational logic. In practice the aribters need to store
> a prior state (or states) information to modify the priority
> and this requires sequential logic/memory etc.
>
> The priority is made dynamic to achieve some particular goals:
> for example to prevent starvation of low priority requesters while
> still give low latency to high priority ones.
> It all very much depends on application.
> Network devices hve really elaborate arbiter algorithms.
>
> > [2] Shall one request and one grant both hold only one clock cycle?
>
> Obviously request will be active for several clock cycles.
> This is beacuse some waiting time for acknowledge is necessary.
> (If not then why would we need arbiter?)
>
> Acknowledge is one clock cycle but this is because there is
> no beneft in making it any longer.
> One cycle acknowledge is "atomic"
>
> BTW Paper specifies many more advanced schemes where
> acknowledge is delayed and a pointers are used in requester
> to figure out how many requests have been acknowledged.
>
> Cheers,
> Przemek
>
>
> Davy wrote:
> > Hi all,
> >
> > I have two problem when reading the paper from
> > [url]http://www.siliconlogic.com/pdf/Arbiters_MattWeber_SLE.pdf [/url]
> >
> > [1] Is Arbiter pure comb logic? If yes, shall its comb logic delay be
> > constrained to within one clock cycle?
> > [2] Shall one request and one grant both hold only one clock cycle?
> > 
> > Best regards, 
> > Davy

bazarnik@hotmail.com wrote:
> <snip>
>
> Obviously request will be active for several clock cycles.
> This is beacuse some waiting time for acknowledge is necessary.
> (If not then why would we need arbiter?)
>
> <snip>
>
> Cheers,
> Przemek

Not so obvious.  Some arbiters contain logic to queue incoming requests
and (for example) will interpret 4 continuous cycles of request
assertion as 4 separate requests.

This can be useful if your arbitration logic requires multiple cycles
while being expected to handle a new request every cycle.

Thanks! I stand corrected.

In the paper there are several arbiter implementations with varying
request, grant protocols.
I was assuming the simples protocol being used: Figure 1 and 2, 3
(also valid for Fig 6 logic)

So the answer is in fact yes (req and grant exactly one cycle)
for protocols used in cases shown on Figures 7-9

(answer is no for Fig 1-6)

Cheers,
Przemek



Doug MacKay wrote:
> bazarnik@hotmail.com wrote:
> > <snip>
> >
> > Obviously request will be active for several clock cycles.
> > This is beacuse some waiting time for acknowledge is necessary.
> > (If not then why would we need arbiter?)
> >
> > <snip>
> >
> > Cheers,
> > Przemek
>
> Not so obvious.  Some arbiters contain logic to queue incoming requests
> and (for example) will interpret 4 continuous cycles of request
> assertion as 4 separate requests.
>
> This can be useful if your arbitration logic requires multiple cycles
> while being expected to handle a new request every cycle.

bazarnik@hotmail.com wrote:
> Thanks! I stand corrected.
>
> In the paper there are several arbiter implementations with varying
> request, grant protocols.
> I was assuming the simples protocol being used: Figure 1 and 2, 3
> (also valid for Fig 6 logic)
>
> So the answer is in fact yes (req and grant exactly one cycle)
> for protocols used in cases shown on Figures 7-9
>
[snip]
I think the ideal arbiter is pure comb logic. But some arbiter is so
large that we have to split with FF.  When use FF, the grant will wait
a cycle and the request will send again. So the solution is add queue
(FIFO) to arbiter and pull-down the request when queue get the request.


Any comment are welcome!

Thanks!
Davy

> (answer is no for Fig 1-6)
>
> Cheers,
> Przemek
>
>
>
> Doug MacKay wrote:
> > bazarnik@hotmail.com wrote:
> > > <snip>
> > >
> > > Obviously request will be active for several clock cycles.
> > > This is beacuse some waiting time for acknowledge is necessary.
> > > (If not then why would we need arbiter?)
> > >
> > > <snip>
> > >
> > > Cheers,
> > > Przemek
> >
> > Not so obvious.  Some arbiters contain logic to queue incoming requests
> > and (for example) will interpret 4 continuous cycles of request
> > assertion as 4 separate requests.
> >
> > This can be useful if your arbitration logic requires multiple cycles
> > while being expected to handle a new request every cycle.