From ganesh@bliss.cs.utah.edu Mon Jun 21 00:13:10 1993
Date: Sun, 20 Jun 93 17:00:31 0600
From: ganesh@bliss.cs.utah.edu (Ganesh C. Gopalakrishnan)
To: asynchronous@hohum.stanford.edu
Status: RO
ContentLength: 3983
XLines: 107
Hello,
There is a really nice article on "Symmetric Crossbar Arbiters"
in the January 1993 issue of the IEEE trans. on Parallel and
Distributed Systems by Tamir and Chi. I wonder whether we
(i.e. "asynchronous folks") could come up with interesting
asynchronous schemes, and compare them with the ones that are
proposed in the paper. (I've tried for a short while, but haven't
found any solutions that are clearly better...).
An example will illustrate the requirements of the arbiter.
Consider the crossbar switch that is fed from multiqueues. (I'll explain
the multiqueues momentarily.) The crossbar switches can connect any of the
four row wires to any of the four column wires. There is a switch at every
location "ij" where i and j are numbers between 0 and 3. If switch "ij" is
closed, the "i"th row wire is connected to the "j"th column wire. A
rowwire may only be connected to atmost one column wire. A column wire
may only be connected to atmost one row wire.
The multiqueues enqueue messages that bear an ID (a number between 0 and 3).
We shall focus only on the message IDs. A message walks in against a row
wire, and (after the appropriate switch is closed) drains thru the column
wire.
The contents of the multiqueues are "02", "001", "1" and "32", in the
example below.
"001" means that
 there is one message with ID "1" that wants to traverse
thru the column wire 1 (thus wanting switch 11 to be closed)
 the next two messages want to traverse thru column wire 0
(thus wanting switch 10 to be closed)
The idea behind multiqueues is to enhance thruput. For example, suppose
a message with ID "2" comes into the multiqueue which has currently
"001". Instead of enqueueing "2" in FIFO order (and thus preventing
message 2 to be considered until the others have drained), we essentially
create a situation where message "2" can contend for column wire 2 in
parallel with message 1 contenting for column wire 1, and in parallel also
with TWO messages with ID 0, which, in FIFO order, content for column wire "0".
(Basically the above "multiqueue" is like four separate queues...)
The question is "how do we arbitrate for the row/column wires so as to
maximize the flow".
For example, if we let the multiqueue "02" grab
the column wire 0, multiqueue "001" cannot grab column 0  so it has
to grab column wire "1" (which is the only other message that multiqueue
"001" bears). This is poor choice, however, because, the third multiqueue
cannot drain, as the only column wire which it can take is "1", which has,
alas, already been taken.
A better choice is
 let multiqueue "02" force switch 02 to be closed
 and, multiqueue "001" force switch 10 to be closed
 and, multiqueue "1" force switch 21 to be closed
 and, multiqueue "32" force switch 33 to be closed
Thus, the goal is to maximize the number of connections established,
while avoiding conflicts.
Clearly these arbitration decisions are not independent. Independent
decisions can very easily lead to circularwaits.
=================================================================
Multi 0 1 2 3
queues

    
v    
02 00010203
   
001 10111213
   
1 20212223
   
32 30313233
   
   
message comes in this way >
and drains this way 

v
=================================================================
I hope the requirements are clear. If not, I have a formal definition of
the problem which I can post.
Thanks, and hope the problem is of interest. If this problem is "well known"
and is a "piece of cake", please then bear with my ignorance.
Cheers,
Ganesh Gopalakrishnan ganesh@cs.utah.edu
Assistant Professor, Phone: (801) 5813568
Computer Science, Fax : (801) 5815843
4540 Merrill Engineering Building,
University of Utah, Salt Lake City,
UT 84112, USA