Wed, 13 May 2009, 06:21

```

A student writes, and although my connection here in Northwest Africa
is not the greatest right now, this did get through and I am able to
respond.

Dr. Patt,

The buzzwords list defines Omega network as:
an interconnection network that is a "half-way house" in
some sense between a bus which has maximum contention and
minimum cost and a full crossbar which has minimum contention
and maximum cost. The omega network consists of an array of
k by k crossbar switches. cost is proportional to the number of
switch connections. Ergo, a k by k crossbar has a cost = k^2.
To implement an n by n omega network with k by k crossbars,
the array has n/k rows of log-base-k(n) columns. Each column
decodes a single bit of the address, and forward the access
request to the next column of k by k crossbars.

I think the last sentence should be:
Each column decodes log-base-2(k) bits of the address, and
forwards the access request to the next column of k by k crossbars.

Right?

Exactly!  Thank you for pointing it out.  And I apologize for disengaging
my brain while my fingers were still typing.

In class you presented a bunch of processors on one side
of the Omega network and memories on the other side of the network.
The processors can only talk to the memories - they can't talk to
other processors.  What would you do if you wanted to allow the
processors to talk to each other using an Omega network?
Would the processors be connected to either side of the network?

<<name withheld to protect ...>>

Yes, they would be connected to both sides of the network.  That is, all
sources would be connected at the left, all destinations would be connected
at the right, anything that can be both source and destination would be
connected to both.

Thanks for pointing these out.  Good luck on the exam.

Yale Patt

```