Arbiter

I am designing a bit arbiter with following behavior:

Request(0 to 3): 0000 1010 0110 1101 0010 1001 0001 1000 1011 1011
1000 0101 1001
Reset
HHHLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLHHHHLLLLLLLLLLL LLLLLLL
Ack(0 to 3): 0000 1000 0010 0100 0010 1000 0001 1000 0000 1000
1000 0100 0001

There is a reset line that's active high and if high, it will set all
the Ack(0 to 3) to 0000. The current Request(0 to 3) compares to the
previous Request(0 to 3) to see if there were bits that were requested
earlier but were not acknowledged on Ack(0 to 3) and it gives them
priority in the current Ack(0 to 3).

I hope I explained ok here. I'm having trouble putting this behavior
into codes in VHDL. Someone has any idea?

willwestward@gmail.com

writes:
> I hope I explained ok here. I'm having trouble putting this behavior
> into codes in VHDL. Someone has any idea?

How would you design it with logic gates (and flip-flops, if required)?

Once you know that, you can just do the same thing in VHDL.

Eric Smith

On Jun 7, 3:54 pm, Eric Smith <e...@brouhaha.com> wrote:
> willwestw...@gmail.com writes:
> > I hope I explained ok here. I'm having trouble putting this behavior
> > into codes in VHDL. Someone has any idea?
>
> How would you design it with logic gates (and flip-flops, if required)?
>
> Once you know that, you can just do the same thing in VHDL.

Yes you can do it in logic gates, but I want behavior modeling. If
using FF and logic gates, it would make this totally a netlist
coding.

Here is the Requset, Reset, and Acknowledge again:

Request(0 to 3): 0000 1010 0110 1101 0010 1001 0001 1000 1011 1011
1000 0101 1001
Reset:
HHHHLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLHHHHLLLLLL LLLLLLLLLLLLLLL
Ack(0 to 3): 0000 1000 0010 0100 0010 1000 0001 1000 0000 1000
1000 0100 0001

I also plan to convert this code into Verilog, C or C++ later on, so
if you have algorithm or codes in those languages, it's fine too.

willwestward@gmail.com

Eric asked 'how' you would do it with logic gates. Once you know that, then
the question is to how to describe that behavior in VHDL, verilog, c, c++...

If you can write behavioral descriptions for your FFs and logic gates in
VHDL (etc.), you have a solution to your problem.

If you can abstract the sequence to a state machine, and code that in VHDL
(etc.), you have another solution to your problem.

If you understand what it is you really want to do, and appropriately
describe and code it, you are likely to have a better solution to your
problem. A better solution, because it will respond to other sequences the
way you intend, rather than just matching the small set of stimulus-response
vectors described. There will be many solutions that will pass the test
vectors, but will not 'do the right thing' in general.

JTW

<> wrote in message
news: ups.com...
> On Jun 7, 3:54 pm, Eric Smith <e...@brouhaha.com> wrote:
>> willwestw...@gmail.com writes:
>> > I hope I explained ok here. I'm having trouble putting this behavior
>> > into codes in VHDL. Someone has any idea?
>>
>> How would you design it with logic gates (and flip-flops, if required)?
>>
>> Once you know that, you can just do the same thing in VHDL.
>
> Yes you can do it in logic gates, but I want behavior modeling. If
> using FF and logic gates, it would make this totally a netlist
> coding.
>
> Here is the Requset, Reset, and Acknowledge again:
>
> Request(0 to 3): 0000 1010 0110 1101 0010 1001 0001 1000 1011 1011
> 1000 0101 1001
> Reset:
> HHHHLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLHHHHLLLLLL LLLLLLLLLLLLLLL
> Ack(0 to 3): 0000 1000 0010 0100 0010 1000 0001 1000 0000 1000
> 1000 0100 0001
>
> I also plan to convert this code into Verilog, C or C++ later on, so
> if you have algorithm or codes in those languages, it's fine too.
>
>

jtw

On Jun 7, 11:07 pm, "jtw" <wrightjt @hotmail.invalid> wrote:
> Eric asked 'how' you would do it with logic gates. Once you know that, then
> the question is to how to describe that behavior in VHDL, verilog, c, c++...
>
> If you can write behavioral descriptions for your FFs and logic gates in
> VHDL (etc.), you have a solution to your problem.
>
> If you can abstract the sequence to a state machine, and code that in VHDL
> (etc.), you have another solution to your problem.
>
> If you understand what it is you really want to do, and appropriately
> describe and code it, you are likely to have a better solution to your
> problem. A better solution, because it will respond to other sequences the
> way you intend, rather than just matching the small set of stimulus-response
> vectors described. There will be many solutions that will pass the test
> vectors, but will not 'do the right thing' in general.
>
> JTW
>
> <willwestw...@gmail.com> wrote in message
>
> news: ups.com...
>
>
>
> > On Jun 7, 3:54 pm, Eric Smith <e...@brouhaha.com> wrote:
> >> willwestw...@gmail.com writes:
> >> > I hope I explained ok here. I'm having trouble putting this behavior
> >> > into codes in VHDL. Someone has any idea?
>
> >> How would you design it with logic gates (and flip-flops, if required)?
>
> >> Once you know that, you can just do the same thing in VHDL.
>
> > Yes you can do it in logic gates, but I want behavior modeling. If
> > using FF and logic gates, it would make this totally a netlist
> > coding.
>
> > Here is the Requset, Reset, and Acknowledge again:
>
> > Request(0 to 3): 0000 1010 0110 1101 0010 1001 0001 1000 1011 1011
> > 1000 0101 1001
> > Reset:
> > HHHHLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLHHHHLLLLLL LLLLLLLLLLLLLLL
> > Ack(0 to 3): 0000 1000 0010 0100 0010 1000 0001 1000 0000 1000
> > 1000 0100 0001
>
> > I also plan to convert this code into Verilog, C or C++ later on, so
> > if you have algorithm or codes in those languages, it's fine too.- Hide quoted text -
>
> - Show quoted text -


I will describle the behavior again and hopefully someone can help.

The arbiter is 4 bits input and output but it can only allow 1 bit to
go high at a time on the ouput (i.e. 0010). It compares the input,
current request (C_R) with previous request (P_R) in memory to
generate output, acknowledge (ACK). If a bit on P_R is also on the
C_R, the acknowledge is not changed because it thinks the P_R is
requested on C_R again. If the C_R bit was also in the P_R and that
bit didn't get the acknowledge bit last time, it will get it this
time. There's also a reset line which sets all the output to 0000 when
it's high.

Here is a sample input and output when reset is low.

C_R(0 to 3): 0000 1010 0110 1101 0010 1001 0001 1000 1011 1011
ACK(0 to 3): 0000 1000 0010 0100 0010 1000 0001 1000 0000 1000

I understand the behavior but just can't seem to figure out the coding
style.

willwestward@gmail.com

In article < .com>,
<> wrote:
>I will describle the behavior again and hopefully someone can help.

>The arbiter is 4 bits input and output but it can only allow 1 bit to
>go high at a time on the ouput (i.e. 0010). It compares the input,
>current request (C_R) with previous request (P_R) in memory to
>generate output, acknowledge (ACK). If a bit on P_R is also on the
>C_R, the acknowledge is not changed because it thinks the P_R is
>requested on C_R again. If the C_R bit was also in the P_R and that
>bit didn't get the acknowledge bit last time, it will get it this
>time.

There's a problem in that specification. If there are three simultaneous
requests, one of them will be granted the first time, leaving two
bits in P_R that are still present in the next cycle's C_R.
The first sentance allowed only one output to go high (be acknowledged),
but the last sentance I quoted above, about "and that bit didn't
get the acknowledge bit last time", requires that -both- of the two
old requests be acknowledged in the current cycle.

To resolve this, the spec would have to be rewritten to something
similar to,
"If there are C_R bits that were also in the P_R and those bits
did not get the acknowledge bit last time, one of them will get
it this time."

But even this has problems, because it allows for indefinite
postponement. Suppose A, B, C have simultaneous requests. One
of them is granted, say A. Suppose A re-requests before the next
sampling, so at the time of the next sampling A is active because
of the re-request and B and C are still active because they have
not been acknowledged. This time, A will not be the one serviced
because of the "and that bit didn't get the acknowledge bit last time"
clause (which imparts some fairness), so one of B or C will be served,
say B, leaving A and C active. The next cycle, A and C (at least)
are still waiting from and were waiting in the previous cycle, and
neither were granted in the previous cycle, so by the clause above,
both of them are eligable for service this time. Which one will be
chosen? The specs don't say, so although serving C would be fairest
because it has been waiting longest, it could be A that is served
this time. If B had re-requested as well during the same cycle,
then again the next cycle around you have two requests that
hadn't been served the previous time, and again it might not be C
that you choose to serve. Repeat indefinitely and you can see that
C might never be served if the ACKs toggle between A and B.
--
If you lie to the compiler, it will get its revenge. -- Henry Spencer

Walter Roberson

On Jun 7, 5:16 pm, willwestw...@gmail.com wrote:
> On Jun 7, 3:54 pm, Eric Smith <e...@brouhaha.com> wrote:
>
> > willwestw...@gmail.com writes:
> > > I hope I explained ok here. I'm having trouble putting this behavior
> > > into codes in VHDL. Someone has any idea?
>
> > How would you design it with logic gates (and flip-flops, if required)?
>
> > Once you know that, you can just do the same thing in VHDL.
>
> Yes you can do it in logic gates, but I want behavior modeling. If
> using FF and logic gates, it would make this totally a netlist
> coding.
>
> Here is the Requset, Reset, and Acknowledge again:
>
> Request(0 to 3): 0000 1010 0110 1101 0010 1001 0001 1000 1011 1011
> 1000 0101 1001
> Reset:
> HHHHLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLHHHHLLLLLL LLLLLLLLLLLLLLL
> Ack(0 to 3): 0000 1000 0010 0100 0010 1000 0001 1000 0000 1000
> 1000 0100 0001
>
> I also plan to convert this code into Verilog, C or C++ later on, so
> if you have algorithm or codes in those languages, it's fine too.

Here is my code. There's a problem, the acknowledge only changes on
reset='1' and request='1111'. How can I fix this so it will give the
right output like the behavior given earlier?

LIBRARY IEEE;
USE IEEE.std_logic_1164.ALL;

entity rrarbiter is
port ( request : in std_logic_vector(0 to 3);
reset : in std_logic;
acknowledge : inout std_logic_vector(0 to 3)
);
end entity rrarbiter;

architecture rrobin_behave of rrarbiter is

signal reg_ack: std_logic_vector(0 to 3); --:=
std_logic_vector'(B"0000");

begin
behavior: process(reset, request)
begin
if reset = '1' then
acknowledge <= std_logic_vector'("0000");

------IF BIT IN ACKNOWLEDGE IS NOT IN REQUEST THEN
acknowledge<=MSB SET OF acknowledge----

elsif NOT(request(0)=reg_ack(0) or
request(1)=reg_ack(1) or request(2)=reg_ack(2) or
request(3)=reg_ack(3)) then
if request(0)='1' then
acknowledge<= std_logic_vector'("1000");

elsif request(1)='1' then
acknowledge<= std_logic_vector'("0100");

elsif request(2)='1' then
acknowledge<= std_logic_vector'("0010");

elsif request(3)='1' then
acknowledge<= std_logic_vector'("0001");

end if;

-----A BIT IN REQUEST IS ALSO IN acknowledge THEN
acknowledge<=REG_ACK----
elsif (request(0)=reg_ack(0) or
request(1)=reg_ack(1) or request(2)=reg_ack(2) or
request(3)=reg_ack(3)) then

if request(0)='1' and reg_ack(0)='1'then
acknowledge <=
std_logic_vector'("1000");

elsif request(1)='1' and reg_ack(1)='1' then
acknowledge<= std_logic_vector'("0100");

elsif request(2)='1' and reg_ack(2)='1' then
acknowledge<= std_logic_vector'("0010");

elsif request(3)='1' and reg_ack(3)='1' then
acknowledge<= std_logic_vector'("0001");

end if;

end if;

end process;

reg_ack <= acknowledge;

end rrobin_behave;

willwestward@gmail.com