a pipeline with collision detection

Discussion in 'VHDL' started by skatoulas@hotmail.com, Aug 2, 2005.

  1. Guest

    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.
    , Aug 2, 2005
    #1
    1. Advertising

  2. On 2 Aug 2005 09:26:54 -0700, 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:
    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.
    Jonathan Bromley, Aug 2, 2005
    #2
    1. Advertising

  3. 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 Harrekilde-Petersen, Aug 2, 2005
    #3
  4. Guest

    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
    , Aug 2, 2005
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Stephen Wolfe

    Collision detection

    Stephen Wolfe, Feb 19, 2004, in forum: Java
    Replies:
    1
    Views:
    595
    Alex Hunsley
    Feb 20, 2004
  2. Abs
    Replies:
    4
    Views:
    8,388
    Jesper Nordenberg
    May 14, 2004
  3. Thorsten Reichelt

    collision detection and penetration depth

    Thorsten Reichelt, Oct 25, 2004, in forum: Python
    Replies:
    3
    Views:
    620
    Thorsten Reichelt
    Oct 25, 2004
  4. Collision Detection

    , Apr 16, 2008, in forum: Java
    Replies:
    3
    Views:
    350
    Jeff Higgins
    Apr 16, 2008
  5. Aaron Brady

    hashing and collision detection

    Aaron Brady, Apr 7, 2009, in forum: Python
    Replies:
    0
    Views:
    521
    Aaron Brady
    Apr 7, 2009
Loading...

Share This Page