exclusive verilog task usage

Hi.

I model a cpu that receives from my chip 2 interupts signals.
Upon each interrupt the cpu performs different set of registers read
and writes.

The register_read and register_write are implemented in verilog task.

Since these are time-consuming tasks, I fear from a collision between
cpu
accesses origineted by the 2 interrupts.

I have a solution in mind, but I am not sure if it is risky:

The solution is based on verilog wait statement + a global lock signal,
and on the fact that the 2
interrupt proccesses (and the tasks) are located in the same file and
module.


initial begin
@ (negedge interrupt1_n) ;
// some code that handles interrupt 1
reg_read ( ... );
...
reg_write (...) ;
..
end


initial begin
@ (negedge interrupt2_n) ;
// some code that handles interrupt 2
reg_read ( ... );
...
reg_write (...) ;
..
end


reg lock;
initial lock = 0;

task reg_read
input ...
output ...

begin
wait (lock == 0) ;
lock = 1;
// and here goes the code

lock = 0;
end



task reg_write
input ...
output ...

begin
wait (lock == 0) ;
lock = 1;
// and here goes the code

lock = 0;
end


Do you see any risk in such code ?
Can I expand it to more processes that use these tasks safely?

ThankX,
NAHUM

 

[Jonathan Bromley]

On 8 Nov 2006 00:34:08 -0800,
nahum_barnea@yahoo.com wrote:

I have a solution in mind, but I am not sure if it is risky:

In theory it is, but in practice it is probably OK. It's certainly
better than nothing.

The solution is based on verilog wait statement + a global lock signal,

reg lock;
initial lock = 0;

task reg_read
input ...
output ...

begin
wait (lock == 0) ;

Better to say
wait (lock === 1'b0);
to avoid any confusion about what happens when there's an X on "lock".

lock = 1;
// and here goes the code

lock = 0;
end

Do you see any risk in such code ?

The problem is this.
Consider TWO processes both competing for the lock
at exactly the same time. Both processes execute

wait (lock === 1'b0);

Then the lock variable goes to 1, and both processes
are free to run. Suppose BOTH are promoted to the
run queue (the Active region of Verilog's scheduling model)
and then one of them executes

lock = 1;

Of course, the other one will also execute the lock as well,
because both processes think they have the lock!

This can happen only if two or more processes attempt
to get the lock whilst a third process has it; when the
owner process releases the lock, it may promote all
waiters to the run queue.

Can I expand it to more processes that use these tasks safely?

As suggested above, it becomes more fragile if you have >2 processes
competing for the same lock. One possible approach is this:
when a process discovers it cannot have the lock yet, it waits
for a random time interval before trying again. Once again this
is not bomb-proof, but it's easy to implement and it's better
than nothing.

Take a look at any standard text on concurrent programming or
operating systems (e.g. Ben-Ari Principles of Concurrent and
Distributed Systems) for some more sophisticated approaches
to this problem. Unfortunately, many of the standard mutual
exclusion algorithms require each process to have an identity,
which is not possible in standard Verilog.

If you have a SystemVerilog licence, consider using its
semaphore construct instead.
--
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.

 

Might wanna give priority to your interrupt so that both happens, you
process priority interrupt (if your design permits).

 

[Alex]

That's really good and useful explanation !

The only thing I don't agree is:

"Unfortunately, many of the standard mutual
exclusion algorithms require each process to have an identity,
which is not possible in standard Verilog."

It is possible in Verilog with the only limitation: the task cannot
"compete" with itself. In other words, all competing tasks have to be
different.

Let's say there are tasks t1, t2, t3, and t4. In the same scope we can
instantiate an arbiter with req_t1, req_t2, req_t3, req_t4 inputs and
gnt_t1, gnt_t2, gnt_t3, gnt_t4 outputs.

Each task will containt the following code:

task t1;
...
req_t1 = 1;
wait (gnt_t1);
<execute task>
.....
req_t1 = 0;
endtask

The arbiter generates 1-hot grants for the incoming requests. When
process is finished, corresponding arbiter request input goes down,
"releasing" the arbiter for the next arbitration. Round-robin arbiter
design will remove starvation issues. Also, the arbiter can be
parametrized and highly reused.

Regards,
-Alex


Jonathan Bromley wrote:

On 8 Nov 2006 00:34:08 -0800,
nahum_barnea@yahoo.com wrote:

I have a solution in mind, but I am not sure if it is risky:

In theory it is, but in practice it is probably OK. It's certainly
better than nothing.

The solution is based on verilog wait statement + a global lock signal,

reg lock;
initial lock = 0;

task reg_read
input ...
output ...

begin
wait (lock == 0) ;

Better to say
wait (lock === 1'b0);
to avoid any confusion about what happens when there's an X on "lock".

lock = 1;
// and here goes the code

lock = 0;
end

Do you see any risk in such code ?

The problem is this.
Consider TWO processes both competing for the lock
at exactly the same time. Both processes execute

wait (lock === 1'b0);

Then the lock variable goes to 1, and both processes
are free to run. Suppose BOTH are promoted to the
run queue (the Active region of Verilog's scheduling model)
and then one of them executes

lock = 1;

Of course, the other one will also execute the lock as well,
because both processes think they have the lock!

This can happen only if two or more processes attempt
to get the lock whilst a third process has it; when the
owner process releases the lock, it may promote all
waiters to the run queue.

Can I expand it to more processes that use these tasks safely?

As suggested above, it becomes more fragile if you have >2 processes
competing for the same lock. One possible approach is this:
when a process discovers it cannot have the lock yet, it waits
for a random time interval before trying again. Once again this
is not bomb-proof, but it's easy to implement and it's better
than nothing.

Take a look at any standard text on concurrent programming or
operating systems (e.g. Ben-Ari Principles of Concurrent and
Distributed Systems) for some more sophisticated approaches
to this problem. Unfortunately, many of the standard mutual
exclusion algorithms require each process to have an identity,
which is not possible in standard Verilog.

If you have a SystemVerilog licence, consider using its
semaphore construct instead.
--
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.

 

[Jonathan Bromley]

On 8 Nov 2006 08:41:32 -0800, "Alex"
<agnusin@gmail.com> wrote:

The only thing I don't agree is:

"Unfortunately, many of the standard mutual
exclusion algorithms require each process to have an identity,
which is not possible in standard Verilog."

It is possible in Verilog [...]

Perhaps I didn't express it very well. Your approach gives each
thread of execution an identity by getting each thread to use
a distinct variable instance. My point was that there is no way
in Verilog to get a unique process-ID from a process itself.
By contrast, SystemVerilog provides the self() function in a
process, which returns a handle to the process descriptor of
that process; armed with this, you have access to a wide
range of standard mutual-exclusion and scheduling algorithms.

Your approach can certainly be made to work, but it's not
bullet-proof: a malicious or ignorant user could easily
subvert it by making use of the wrong variable from
some process.
--
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.

 

[Alex]

Jonathan Bromley wrote:
....

By contrast, SystemVerilog provides the self() function in a
process, which returns a handle to the process descriptor of
that process; armed with this, you have access to a wide
range of standard mutual-exclusion and scheduling algorithms.

Your approach can certainly be made to work, but it's not
bullet-proof: a malicious or ignorant user could easily
subvert it by making use of the wrong variable from
some process.

Well, in language itself, there is no defense from "malicious or
ignorant users" and SV is not a "magic bullet"
What is important, however, is the ease of debug. This is where most of
development time is spent.
Debugging/observing arbitration in verilog is easy: you just observe
arbiter's requests and grants. I am not sure that SV provides the same
convenience for debug with dynamically allocated self() pointers.

Regards,
-Alex

 

[Utku Özcan]

ankitks@yahoo.com schrieb:

Might wanna give priority to your interrupt so that both happens, you
process priority interrupt (if your design permits).

Same opinion.

Operating Systems have Interrupt Handler routines which require a
priority implemented either in Interrupt Queue or nested-if-checks in
the handler routines.

Another funny thing is, I have never seen a commercial implementation
where the product has more than one interrupt pin. Please correct me if
I am wrong here.

[Jonathan Bromley]

My point was that there is no way in Verilog to get a unique process-ID from a process itself.

I don't think so. You can name any block in Verilog. Even not named,
simulator names it (defblockxxyyy labels in NC-Sim for example). In
that case you can access any named object with acc_handle_scope() for
example, which mimics unique Process-ID mechanism.

Utku.

 

Utku Özcan wrote:

Another funny thing is, I have never seen a commercial implementation
where the product has more than one interrupt pin. Please correct me if
I am wrong here.

Well the funny thing is that you have seen it.
Every PC utilize a PCI bus.
and PCI bus has 4 interrupt pins.

 

Thanks for the detailed response.

Do you think that the situation can improve if instead of seperate
"initial" processes,
I will use one initial proces with verilog fork-join statements?



Jonathan Bromley wrote:

On 8 Nov 2006 00:34:08 -0800,
nahum_barnea@yahoo.com wrote:

I have a solution in mind, but I am not sure if it is risky:

In theory it is, but in practice it is probably OK. It's certainly
better than nothing.

The solution is based on verilog wait statement + a global lock signal,

reg lock;
initial lock = 0;

task reg_read
input ...
output ...

begin
wait (lock == 0) ;

Better to say
wait (lock === 1'b0);
to avoid any confusion about what happens when there's an X on "lock".

lock = 1;
// and here goes the code

lock = 0;
end

Do you see any risk in such code ?

The problem is this.
Consider TWO processes both competing for the lock
at exactly the same time. Both processes execute

wait (lock === 1'b0);

Then the lock variable goes to 1, and both processes
are free to run. Suppose BOTH are promoted to the
run queue (the Active region of Verilog's scheduling model)
and then one of them executes

lock = 1;

Of course, the other one will also execute the lock as well,
because both processes think they have the lock!

This can happen only if two or more processes attempt
to get the lock whilst a third process has it; when the
owner process releases the lock, it may promote all
waiters to the run queue.

Can I expand it to more processes that use these tasks safely?

As suggested above, it becomes more fragile if you have >2 processes
competing for the same lock. One possible approach is this:
when a process discovers it cannot have the lock yet, it waits
for a random time interval before trying again. Once again this
is not bomb-proof, but it's easy to implement and it's better
than nothing.

Take a look at any standard text on concurrent programming or
operating systems (e.g. Ben-Ari Principles of Concurrent and
Distributed Systems) for some more sophisticated approaches
to this problem. Unfortunately, many of the standard mutual
exclusion algorithms require each process to have an identity,
which is not possible in standard Verilog.

If you have a SystemVerilog licence, consider using its
semaphore construct instead.
--
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.

 

[Utku Özcan]

Utku Özcan wrote:
Another funny thing is, I have never seen a commercial implementation
where the product has more than one interrupt pin. Please correct me if
I am wrong here.



Well the funny thing is that you have seen it.
Every PC utilize a PCI bus and PCI bus has 4 interrupt pins.

PCI Bus is not a product, but it is a standard. 4 interrupts form a bus
but each of them comes from a unique device.

I wanted to say that I have never seen an application that a device has
a more than one interrupt pin *output*, towards a computer architecture
bus or CPU (sorry it was incomplete in my previous email what I wanted
to say). It is technically possible to have more than one interrupt
pin, I did it in the past such custom chips for a commercial product,
but in the market I have never met such a thing.

Utku.

 

[Jonathan Bromley]

On 9 Nov 2006 00:04:25 -0800, nahum_barnea@yahoo.com wrote:

Thanks for the detailed response.

Do you think that the situation can improve if instead of seperate
"initial" processes,
I will use one initial proces with verilog fork-join statements?

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

 

Jonathan Bromley wrote:

Perhaps I didn't express it very well. Your approach gives each
thread of execution an identity by getting each thread to use
a distinct variable instance. My point was that there is no way
in Verilog to get a unique process-ID from a process itself.

Nor is there a need to do so. There are other ways to assign unique
IDs to the processes without having to access the internals of
processes.

The most obvious that comes to mind is the "now serving number N"
mechanism used in delicatessens to give first-come-first-served
arbitration. Set up a "ticket dispenser" with a counter to assign an
increasing number to each waiter as it arrives (an automatic variable
in the task can store the assigned ticket number independently for each
caller). Set up another "now serving" counter that keeps track of
whose turn it is next. Each caller waits for the lock to come free AND
the "now serving" counter to match their ticket number. When they are
done, they increment the "now serving" counter and clear the lock.
This can all be encapsulated in the task.

The only thing this relies on is the ability to increment and assign
the ticket counter value as an atomic operation, without being
preempted by another process in the middle. And while the Verilog LRM
does not actually guarantee that, most Verilog designs would fail to
work correctly if simulators actually preempted processes at arbitrary
points. So if you can't trust that, you might as well give up writing
reasonable code in Verilog. If you are really paranoid, you could
probably use Dekker's algorithm to avoid the need for the atomic
operation.

 

[ramnarayan]

Hi,
use the automatic tasks instead of static tasks.
i think it may resolve ur problem.
sharp@cadence.com wrote:

Jonathan Bromley wrote:

Perhaps I didn't express it very well. Your approach gives each
thread of execution an identity by getting each thread to use
a distinct variable instance. My point was that there is no way
in Verilog to get a unique process-ID from a process itself.

Nor is there a need to do so. There are other ways to assign unique
IDs to the processes without having to access the internals of
processes.

The most obvious that comes to mind is the "now serving number N"
mechanism used in delicatessens to give first-come-first-served
arbitration. Set up a "ticket dispenser" with a counter to assign an
increasing number to each waiter as it arrives (an automatic variable
in the task can store the assigned ticket number independently for each
caller). Set up another "now serving" counter that keeps track of
whose turn it is next. Each caller waits for the lock to come free AND
the "now serving" counter to match their ticket number. When they are
done, they increment the "now serving" counter and clear the lock.
This can all be encapsulated in the task.

The only thing this relies on is the ability to increment and assign
the ticket counter value as an atomic operation, without being
preempted by another process in the middle. And while the Verilog LRM
does not actually guarantee that, most Verilog designs would fail to
work correctly if simulators actually preempted processes at arbitrary
points. So if you can't trust that, you might as well give up writing
reasonable code in Verilog. If you are really paranoid, you could
probably use Dekker's algorithm to avoid the need for the atomic
operation.

 

[Jonathan Bromley]

On 9 Nov 2006 11:26:45 -0800, sharp@cadence.com wrote:

There are other ways to assign unique
IDs to the processes [...] Set up a "ticket dispenser" [...]

Folk scanning for references on that will probably want to
look for the "bakery algorithm", no?

(an automatic variable
in the task can store the assigned ticket
number independently for each caller).

Thank you. To my shame, I had not thought of using
automatic tasks in this way.
--
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.