How to write SystemVerilog-like semaphore in Verilog?
sasha....@gmail.com
Thank you.
Jonathan Bromley
>Is it possible to do that?
Yes and no.
SV semaphores are dynamically created - they have
a "new" function - and there is no way to get that
effect in regular Verilog. But you could almost
certainly work around it by creating a static
pool of semaphores and handing out one of them
whenever their "new" method was called,
or simply by statically creating each semaphore
that you know you will need.
More important, though, is the question of
the mutual exclusion behaviour of a semaphore.
It's quite tricky to get that right in Verilog
because the language allows arbitrary interleaving
of execution of concurrent threads, but you can find
plenty of rigorous solutions by consulting any standard
text on concurrent programming (I like Ben-Ari,
Principles of Concurrent and Distributed Programming,
but it's quite old and may be out of print by now).
Googling for "mutual exclusion" and "bakery algorithm"
will probably be useful too.
For some real, practical problems you can get away
with a much simpler implementation that is not
rigorously reliable and not truly general. As an
example, consider a static task that must be
executed by no more than one process at a time:
task T(...); // static task
reg mutex; // static variable
begin
if (mutex) // Someone else has the lock.
wait (mutex === 1'b0); // Wait for my turn.
mutex = 1'b1; // Claim the lock.
<<< do the real work of the task >>>
mutex = 1'b0; // Release the lock.
end
endtask
It is an interesting and instructive exercise to work out
(a) how this works,
(b) how it can go wrong (it can, in many different ways!)
Once you've done (b) to your own satisfaction, you will be
ready to read the academic texts on how to do it properly!
good luck
--
Jonathan Bromley, Consultant
DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services
Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
jonathan...@MYCOMPANY.com
http://www.MYCOMPANY.com
The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.
sasha....@gmail.com
wrote:
>
> The contents of this message may contain personal views which
> are not the views of Doulos Ltd., unless specifically stated.
Thank you for a good example.
Probably, the solution of this puzzle is to replace static task with
automatic one?
Jonathan Bromley
>Probably, the solution of this puzzle is to replace static task with
>automatic one?
That is usually a good idea, but it does not help if you need
to get exclusive access to a shared resource. Like I say -
read the standard texts on concurrent programming!
--
Jonathan Bromley, Consultant
DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services
Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
jonathan...@MYCOMPANY.com
Marcus Harnisch
> Is it possible to do that?
I suppose something like that could be whipped up using a wire as
semaphore and $countdrivers().
1. create signal driver.
2. enable driver.
3. check whether we are the only one driving the signal.
4. We are: move on.
There are other drivers:
4a. disable driver.
4b. wait for some amount of time.
4c. go back to 2.
5. process critical section.
6. disable driver.
This is completely untested. I don't have the time to actually try
this out.
Regards
Marcus
--
note that "property" can also be used as syntaxtic sugar to reference
a property, breaking the clean design of verilog; [...]
testbench
I wrote this when I was a kid in verification. Have a look @
http://testbench.in/tTB_27_VERILOG_SEMAPHORE.html
Jonathan Bromley
OK, so now you're not a kid perhaps you
could be kind enough to document the various
ways in which that example is flawed?
As has been pointed out several times in this thread,
it's easy to make something in Verilog that works
as a mutex/semaphore *almost* all the time. Getting
it completely bulletproof is MUCH harder.
Andreas Ehliar
> That is usually a good idea, but it does not help if you need
> to get exclusive access to a shared resource. Like I say -
> read the standard texts on concurrent programming!
It seems as if my newsreader ate my reply here. Anyway, I thought this
was an interesting challenge, so how about the following attempt:
module lock;
// I haven't checked the Verilog standard, but I assume that reads/writes
// to an integer is atomic.
integer new_id = 0;
integer final_id = 0;
reg pulse_lock = 0;
task automatic lock;
input integer ID;
begin
while(final_id != ID) begin
new_id = ID;
@(pulse_lock); // Wait for serialization
end
end
endtask
// This procedure serializes access to the lock
reg locked = 0;
always @(new_id) begin
if(!locked) begin
locked = 1;
final_id = new_id; // This ID acquired the lock
pulse_lock = !pulse_lock; // Wake up all all threads that may be
// listening
end
end
task unlock;
begin
final_id = 0;
locked = 0;
pulse_lock = !pulse_lock; // Wake up anyone else who is trying to
// access the lock.
end
endtask
endmodule
Unfortunately a unique ID is required for every place in the code that the
lock is acquired. Is there a nice way to get this? I was thinking about using
%m in $sprintf, but that is not fool proof if the lock should be acquired in
a task.
Also, I'm not totally sure about the scheduling semantics of Verilog here.
The always block will be triggered by the change in new_id. Is it guaranteed
that @(pulse_lock) will be reached before the always block is activated?
This could be a really nasty interview question by the way... (although it
would make for a very nice discussion on race conditions in Verilog).
/Andreas
Andreas Ehliar
Hmm, after thinking a bit more about this I believe that there are some
race conditions in this version as well. I still believe that the locking
is fairly solid, but there seems to be some race possibilities when
unlocking the lock.
This was even trickier than I thought in the beginning...
/Andreas
sasha....@gmail.com
> Hmm, after thinking a bit more about this I believe that there are some
> race conditions in this version as well. I still believe that the locking
> is fairly solid, but there seems to be some race possibilities when
> unlocking the lock.
>
> This was even trickier than I thought in the beginning...
>
I cannot find the solution for now. Does it exists in Verilog 2001
Standard?
Andreas Ehliar
> This was even trickier than I thought in the beginning...
I have thought a bit more about how to synchronize tasks in Verilog and
I have come up with the following attempt. Comments from more knowledgable
Verilog wizards are invited (Hi Jonathan?). The change from the previous attempt
is basically that I'm using non-blocking assignments when assigning to the
pulse_lock signal.
module lock;
integer new_id;
integer final_id = 0;
reg pulse_lock = 0;
// Acquire the lock. A unique ID must be used at every place where the
// lock is acquired. (Well, not really, it is just necessary to guarantee
// that the same ID will never be used to acquire the lock simultaneously.
// It is perfectly allright to have the following code since the same ID
// will not be used simultaneously:
// lock l();
// initial fork
// begin l.lock(1);l.unlock();l.lock(1);l.unlock(); end
// begin l.lock(2);l.unlock();l.lock(2);l.unlock(); end
// join
//
// On the other hand, the following is not allowed:
// fork
// begin l.lock(1);l.unlock(); end
// begin l.lock(1);l.unlock(); end
// join
//
// Modifying the source code to avoid the use of unique IDs is left
// as an exercise for the reader :)
task automatic lock;
input integer ID;
begin
while(final_id != ID) begin
new_id = ID;
@(pulse_lock); // Wait for serialization
end
end
endtask
reg locked = 0;
always @(new_id) begin : LOCK_ARBITER
if(!locked) begin
locked = 1; // Flag the lock as acquired
final_id = new_id; // This ID acquired the lock
// The following assignment will trigger all tasks that are
// trying to acquire the lock. It is important that a
// non-blocking assignment is used here to guarantee that no
// active task is present in the lock task
// above. (i.e. having assigned new_id but haven't yet
// reached @(pulse_lock).
pulse_lock <= !pulse_lock;
end
end
// Not surprisingly, unlock() will unlock the lock.
task unlock;
begin
final_id = 0;
locked = 0;
// This will wake up all tasks that are trying to acquire the lock.
// A non-blocking assignment is used here for the same reason as
// a non-blocking assignment is used in LOCK_ARBITER above.
pulse_lock <= !pulse_lock;
end
endtask
endmodule
// And this is an example of how the lock can be used:
module foo;
lock l();
initial begin
fork
begin l.lock(1); $display("Acquired 1!"); $display("Released 1!"); l.unlock(); end
begin l.lock(2); $display("Acquired 2!"); $display("Released 2!"); l.unlock(); end
begin l.lock(3); $display("Acquired 3!"); $display("Released 3!"); l.unlock(); end
begin l.lock(4); $display("Acquired 4!"); $display("Released 4!"); l.unlock(); end
begin l.lock(5); $display("Acquired 5!"); $display("Released 5!"); l.unlock(); end
begin l.lock(6); $display("Acquired 6!"); $display("Released 6!"); l.unlock(); end
begin l.lock(7); $display("Acquired 7!"); $display("Released 7!"); l.unlock(); end
begin l.lock(8); $display("Acquired 8!"); $display("Released 8!"); l.unlock(); end
begin l.lock(9); $display("Acquired 9!"); $display("Released 9!"); l.unlock(); end
begin l.lock(10); $display("Acquired 10!"); $display("Released 10!"); l.unlock(); end
begin l.lock(11); $display("Acquired 11!"); $display("Released 11!"); l.unlock(); end
begin l.lock(12); $display("Acquired 12!"); $display("Released 12!"); l.unlock(); end
begin l.lock(13); $display("Acquired 13!"); $display("Released 13!"); l.unlock(); end
begin l.lock(14); $display("Acquired 14!"); $display("Released 14!"); l.unlock(); end
begin l.lock(15); $display("Acquired 15!"); $display("Released 15!"); l.unlock(); end
begin l.lock(16); $display("Acquired 16!"); $display("Released 16!"); l.unlock(); end
begin l.lock(17); $display("Acquired 17!"); $display("Released 17!"); l.unlock(); end
begin l.lock(18); $display("Acquired 18!"); $display("Released 18!"); l.unlock(); end
begin l.lock(19); $display("Acquired 19!"); $display("Released 19!"); l.unlock(); end
begin l.lock(20); $display("Acquired 20!"); $display("Released 20!"); l.unlock(); end
join
end
endmodule
/Andreas
Jonathan Bromley
>I have thought a bit more about how to synchronize tasks in Verilog and
>I have come up with the following attempt.
[snip]
It looks right to me, but I'm ashamed to say I lack
the discrete-math skills to prove or disprove it.
It seems a little troublesome that you are obliged
to wait for a trip around the scheduling algorithm
(waiting for the NBA to take effect) for each
arbitration. That's equivalent to a full
delta-cycle delay in VHDL. I believe that there
are algorithms that arbitrate in zero simulated
time, but (with apologies) I don't have time right
now to do the necessary homework.
Thanks for the interesting post.
Bill Warner
swap. This could be easily done in a PLI. The PLI C routine will
almost certainly execute atomically with respect to other PLI C routines
(i.e., they are not reentrant.)
-- Bill
Alex
----------------- Code start -----------------------------------
module test ();
parameter num_senders = 4;
sender #0 SND0 ();
sender #1 SND1 ();
sender #2 SND2 ();
sender #3 SND3 ();
arbiter #4 ARB();
integer i1, i2, i3, i4;
//--------------------------------------------------------------------------
initial begin
fork
for (i1=0; i1<1; i1=i1+1) SND0.send_message();
for (i2=0; i2<3; i2=i2+1) SND1.send_message();
for (i3=0; i3<5; i3=i3+1) SND2.send_message();
for (i4=0; i4<7; i4=i4+1) SND3.send_message();
join
#10
fork
for (i1=0; i1<3; i1=i1+1) SND0.send_message();
for (i2=0; i2<3; i2=i2+1) SND1.send_message();
join
end
endmodule
//--------------------------------------------------------------------------
module sender #( parameter ID = 0)();
task send_message ();
begin
test.ARB.req[ID] = 1'b1; wait (test.ARB.ID == ID);
test.ARB.show_message(ID); // run the task
test.ARB.req[ID] = 1'b0; wait (test.ARB.ID != ID);
end
endtask
endmodule
//--------------------------------------------------------------------------
module arbiter #(parameter num_senders = 3) ( );
reg [num_senders-1:0] req = 0;
reg [7:0] ID;
integer i;
always @(posedge |req)
while (|req) for (i=0; i<num_senders; i=i+1)
if (req[i]) begin ID = i; wait (req[i]==1'b0); ID = num_senders;
end
// common task
task show_message (input [15:0] ID);
$display ("my ID = %0d",ID);
endtask
endmodule
----------------- Code End -----------------------------------
Few notes:
1. Arbiter must know maximum number of requestors.
2. Arbiter checks all requestor's requests using "for" loop - any time
any request is asserted. In this case, it is, in fact, independent on
the simulator thread ordering.
3. There is double handshake between requestor and arbiter: first,
requestor waits for arbiter's acknowledgement, and, at the end,
requestor wait for arbiter to "release" it's ID.
Regards,
-Alex