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

	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.


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