a pipeline with collision detection

Hello all,

I'm stuck with the following. I am centralising the arithmetic in my
design as the way things are now, there is a lot of idle time and
resources spent on all of the distributed units. To be exact, a bunch
of things, which i call nodes, count instances of specific entries in
memory (each node has its own memory - call this count X), then the
log10(X!) is computed for each node and the whole bunch is added
together. The log10(X!) is done by means of a look-up. So say for 10
nodes, 10 X's are produced, one for each node, 10 look-ups are used and
then 9 adders are used in a row for the total addition. Now since the
X's for each node are (more often than not) produced at different
times, I simply want to throw them inside a single look-up then use an
accumulator for the complete result. However in the rare case that 2 or
more X's are produced at the same time I'd like to be able to do
something about it. What I'd like to implement is some sort of serving
system where each node basically raises its hand shouting Me! Me! and
according to some priority, nodes are served then dismissed to go fetch
the next X. The obvious solution is to go around node by node and check
if they want to be served but that introduces unnecessary waiting. I'd
appreciate any help if anyone knows a particular technique or
literature on what i want to do. Thank you.

 

[Jonathan Bromley]

On 2 Aug 2005 09:26:54 -0700, skatoulas@hotmail.com wrote:

[...]

What I'd like to implement is some sort of serving
system where each node basically raises its hand shouting Me! Me! and
according to some priority, nodes are served then dismissed to go fetch
the next X. The obvious solution is to go around node by node and check
if they want to be served but that introduces unnecessary waiting.

Since you say the requests only very rarely collide, it seems
reasonable to assume that the frequency of requests from each
node is quite low and the total frequency of requests is
significantly less than the clock frequency. In such a
situation, I suspect that an arbitrary fixed priority will
do the job, and it's fairly simple.

Fixed priority won't work well if there's a significant chance
of a single node issuing a request again within N cycles,
where N is the number of nodes. If that's the case, you may
wish to consider rotating priority. Take your N requests and
pass them through rotator logic that can rotate right by any number
of positions from 0 to N-1. At each cycle, locate the leftmost
request (this is just simple priority logic). Suppose the current
value of the rotate count is R, and the leftmost requester's
position in the rotated vector is P; both R and P are of course
in the range 0 to N-1. Then the original source of the request
is (P+R) modulo N. Service this request and dismiss it, then
set the new rotate count to the same value ((P+R) modulo N) -
this will demote that requester to the rightmost, lowest-priority
position in the requests vector.

As you can see, the rotating priority logic is exactly the
same as fixed-priority with the addition of a rotate count
register, a modulo-N adder, and the rotator logic.

Googling for "priority arbitration logic" will probably turn
up a huge pile more stuff. But with your scenario of sparse
requests, something simple will probably do the job. Consider
simulating, or doing the statistics, before committing to
a hardware design so that you can be sure you won't get
mystery deadlocks, priority inversion and all the other
nightmarish stuff that can plague arbitration schemes.
--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL, Verilog, SystemC, Perl, Tcl/Tk, Verification, Project Services

Doulos Ltd. Church Hatch, 22 Market Place, Ringwood, BH24 1AW, UK
Tel: +44 (0)1425 471223 mail:jonathan.bromley@doulos.com
Fax: +44 (0)1425 471573 Web: http://www.doulos.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.

 

[Kai Harrekilde-Petersen]

skatoulas@hotmail.com writes:

Hello all,

I'm stuck with the following.
[snip]

What I'd like to implement is some sort of serving
system where each node basically raises its hand shouting Me! Me! and
according to some priority, nodes are served then dismissed to go fetch
the next X. The obvious solution is to go around node by node and check
if they want to be served but that introduces unnecessary waiting. I'd
appreciate any help if anyone knows a particular technique or
literature on what i want to do. Thank you.

What you want is a priority encoder - it'll skip the inactive nodes.
Ideally, you'll want a rotating priority encoder, but if the events
are as fair as you indicate, you can probably get away without it.

Cheers,


Kai
--
Kai Harrekilde-Petersen <khp(at)harrekilde(dot)dk>

 

Kai and Jonathan,

Thank you both, your help is very much appreciated. In fact, whether a
single node will issue a new request within N cycles depends on the
size of each memory and the number of nodes, all of which are generic
inputs. Hence it is probably safer to go for rotating priority. Anyway,
it's all clear to me now, thanks again.

Regards