How to write SystemVerilog-like semaphore in Verilog?

Is it possible to do that?

Thank you.

 

[Jonathan Bromley]

On Sat, 31 Jan 2009 12:16:33 -0800 (PST), wrote:

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

 

On Feb 1, 6:01 pm, Jonathan Bromley <jonathan.brom...@MYCOMPANY.com>
wrote:

On Sat, 31 Jan 2009 12:16:33 -0800 (PST), wrote:

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.brom...@MYCOMPANY.comhttp://www.MYCOMPANY.com

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]

On Sun, 1 Feb 2009 20:07:38 -0800 (PST), sasha.kanata@gmail.com wrote:

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

 

[Marcus Harnisch]

sasha.kanata@gmail.com writes:

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; [...]

(seen on http://www.veripool.com/verilog-mode_news.html)

 

[testbench]

On Feb 1, 1:16 am, sasha.kan...@gmail.com wrote:

Is it possible to do that?

Thank you.

I wrote this when I was a kid in verification. Have a look @
http://testbench.in/tTB_27_VERILOG_SEMAPHORE.html

 

[Jonathan Bromley]

On Tue, 3 Feb 2009 19:28:09 -0800 (PST), testbench
<k.gopi.krish@gmail.com> wrote:

On Feb 1, 1:16 am, sasha.kan...@gmail.com wrote:
Is it possible to do that?

Thank you.

I wrote this when I was a kid in verification. Have a look @
http://testbench.in/tTB_27_VERILOG_SEMAPHORE.html

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

 

[Andreas Ehliar]

On 2009-02-02, Jonathan Bromley <jonathan.bromley@MYCOMPANY.com> wrote:

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]

On 2009-02-04, Andreas Ehliar <ehliar-nospam@isy.liu.se> wrote:

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

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

 

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- Hide quoted text -

I cannot find the solution for now. Does it exists in Verilog 2001
Standard?

 

[Andreas Ehliar]

On 2009-02-06, Andreas Ehliar <ehliar-nospam@isy.liu.se> wrote:

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]

On Thu, 12 Feb 2009 05:09:26 +0000 (UTC), Andreas Ehliar wrote:

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

 

[Bill Warner]

Fundamentally, you need an atomic operation such as test-and-set or
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]

This solution is the working one:

----------------- 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) begin ID = i; wait (req==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