CSC/ECE 506 Spring 2010/12 EC - Revision history

Admin at 03:28, 9 April 2011

2011-04-09T03:28:18Z

← Older revision		Revision as of 03:28, 9 April 2011
Line 145:		Line 145:
	<br>		<br>

	<h2>Meshes and ~~Torii~~</h2>		<h2>Meshes and Tori</h2>
	<p>		<p>
	The mesh and torus structure used in this application would require a large number of links and total aggregate of several thousands of ports. However, since there are so many links, the mesh and torus structures provide alternates paths in case of failures<sup>2</sup>.		The mesh and torus structure used in this application would require a large number of links and total aggregate of several thousands of ports. However, since there are so many links, the mesh and torus structures provide alternates paths in case of failures<sup>2</sup>.

Jechen at 19:18, 30 April 2010

2010-04-30T19:18:49Z

← Older revision		Revision as of 19:18, 30 April 2010
Line 167:		Line 167:
	<p>		<p>
	Similar to the torii structures, the hypercube requires larger number of links. However, the bandwidth scales better than mesh and torii structures.		Similar to the torii structures, the hypercube requires larger number of links. However, the bandwidth scales better than mesh and torii structures.
			<br>
			<br>
			The CRAY T3E, CRAY XT3, and SGI Origin 2000 use k-ary n-cubed topologies.
	<br>		<br>
	<br>		<br>

Jechen at 19:12, 30 April 2010

2010-04-30T19:12:09Z

← Older revision		Revision as of 19:12, 30 April 2010
Line 129:		Line 129:
	<p>		<p>
	In large scale, high performance applications, fat tree can be a choice. However, in order to "fatten" up the links, redundant connections must be used. Instead of using one link between switching nodes, several must be used. The problem with this is that with more input and output links, one would need routers with more input and output ports. Router with excess of 100 ports are difficult to build and expensive, so multiple routers would have to be stacked together. Still, the routers would be expensive and would require several of them<sup>2</sup>.		In large scale, high performance applications, fat tree can be a choice. However, in order to "fatten" up the links, redundant connections must be used. Instead of using one link between switching nodes, several must be used. The problem with this is that with more input and output links, one would need routers with more input and output ports. Router with excess of 100 ports are difficult to build and expensive, so multiple routers would have to be stacked together. Still, the routers would be expensive and would require several of them<sup>2</sup>.
			<br>
			<br>
			The Japan Agency for Marine-Earth Science and Technology supercomputing system uses the fat tree topology. The system connects 1280 processors using NEC processors<sup>7</sup>.
	</p>		</p>
	<br>		<br>
Line 145:		Line 148:
	<p>		<p>
	The mesh and torus structure used in this application would require a large number of links and total aggregate of several thousands of ports. However, since there are so many links, the mesh and torus structures provide alternates paths in case of failures<sup>2</sup>.		The mesh and torus structure used in this application would require a large number of links and total aggregate of several thousands of ports. However, since there are so many links, the mesh and torus structures provide alternates paths in case of failures<sup>2</sup>.
			<br>
			<br>
			Some examples of current use of torus structure include the QPACE SFB TR Cluster in Germany using the PowerXCell 8i processors. The systems uses 3-D torus topology with 4608 processors<sup>7</sup>.
	<br>		<br>
	<br>		<br>
Line 490:		Line 496:
	<br>		<br>
	6 [http://web.ebscohost.com.www.lib.ncsu.edu:2048/ehost/pdfviewer/pdfviewer?vid=2&hid=15&sid=72e3828d-3cb1-42b9-8198-5c1e974ea53f@sessionmgr4 Adaptive Fault Tolerant Routing Algorithm for Tree-Hypercube Multicomputer, Qatawneh Mohammad]		6 [http://web.ebscohost.com.www.lib.ncsu.edu:2048/ehost/pdfviewer/pdfviewer?vid=2&hid=15&sid=72e3828d-3cb1-42b9-8198-5c1e974ea53f@sessionmgr4 Adaptive Fault Tolerant Routing Algorithm for Tree-Hypercube Multicomputer, Qatawneh Mohammad]
			<br>
			7 [http://www.top500.org TOP500 Supercomputing Sites]
	</p>		</p>

Prsave at 22:10, 25 April 2010

2010-04-25T22:10:15Z

← Older revision		Revision as of 22:10, 25 April 2010
Line 430:		Line 430:
	<br>		<br>

	<h1>Fault ~~Tolerance~~ Routing</h1>		<h1>Fault Tolerant Routing</h1>
	<p>		<p>
	Fault-tolerant routing means the successful routing of messages between any pair of non faulty nodes in the presence of faulty components<sup>6</sup>. With increased number of processors in a multiprocessor system and high data rates reliable transmission of data in event of network fault is of great concern and hence fault tolerant routing algorithms are important.		Fault-tolerant routing means the successful routing of messages between any pair of non faulty nodes in the presence of faulty components<sup>6</sup>. With increased number of processors in a multiprocessor system and high data rates reliable transmission of data in event of network fault is of great concern and hence fault tolerant routing algorithms are important.

Jechen at 21:47, 25 April 2010

2010-04-25T21:47:15Z

@@ Line 427: / Line 427: @@
 With high-performance routers, complex topologies are possible. As the router technology improves, more complex, high-dimensionality topologies are possible.
 </p>
 <br>
@@ Line 440: / Line 486: @@
 <br>
 [http://www.csm.ornl.gov/workshops/IAA-IC-Workshop-08/documents/wiki/dally_iaa_workshop_0708.pdf Interconnection Topologies:(Historical Trends and Comparisons)]
 </p>

Jechen at 20:31, 22 April 2010

2010-04-22T20:31:37Z

Show changes

Jechen at 19:58, 22 April 2010

2010-04-22T19:58:27Z

← Older revision		Revision as of 19:58, 22 April 2010
Line 252:		Line 252:

	To avoid circular patterns of routing, some routing patterns are disallowed. These are called '''turn restrictions''', where some turns are not allowed in order to avoid making a circular routing pattern. Some of these turn restrictions are mentioned below.		To avoid circular patterns of routing, some routing patterns are disallowed. These are called '''turn restrictions''', where some turns are not allowed in order to avoid making a circular routing pattern. Some of these turn restrictions are mentioned below.
			</p>

			<br>
			<h2>Dimensional ordered (X-Y) routing</h2>
			<p>
			Turns from the y-dimension to the x-dimension are not allowed.
			</p>

			<h2>West First</h2>
			<p>
			Turns to the west are not allowed.
			</p>

			<h2>North Last</h2>
			<p>
			Turns after a north direction are not allowed.
			</p>

			<h2>Negative First</h2>
			<p>
			Turns in the negative direction (-x or -y) are not allowed, except on the first turn.
			</p>

			<h2>Odd-Even Turn Model</h2>

			<p>
			Unfortunately, the above turn-restriction models reduce the degree of adaptiveness and are partially adaptive. The models cause some packets to take different routes, and not necessarily the minimal paths. This may cause unfairness but reduces the ability of the system to reduce congestion. Overall performance could suffer<sup>3</sup>.
			</p>

			<br>

			<p>
			Ge-Ming Chiu introduces the Odd-Even turn model as an adaptive turn restriction, deadlock-free model that has better performance than the previously mentioned models<sup>3</sup>. The model is designed primarily for 2-D meshes.
			</p>

			<p>
			Turns from the east to north direction from any node on an even column are not allowed.
			<br>
			Turns from the north to west direction from any node on an odd column are not allowed.
			<br>
			<br>
			Turns from the east to south direction from any node on an even column are not allowed.
			<br>
			Turns from the south to west direction from any node on an odd column are not allowed.
			<br>
			<br>
			The illustration below shows allowed routing for different source and destination nodes. Depending on which column the packet is in, only certain directions are allowed.
			<br>
			<br>
			[[Image:Routing_odd_even.jpg]]
			<br>
			''Odd-Even turn restriction model proposed by Ge-Ming Chiu''<sup>3</sup>
			<br>

Jechen at 19:46, 22 April 2010

2010-04-22T19:46:43Z

Show changes

Jechen at 19:18, 22 April 2010

2010-04-22T19:18:34Z

@@ Line 51: / Line 51: @@
 '''2-D Torus'''
 <p>
-[[Image:Top_2DTorus.jpg]]
+[[Image:Top_2Dtorus.jpg]]
 <br>
 <br>
@@ Line 158: / Line 158: @@
 </p>
 <br>

Jechen at 19:07, 22 April 2010

2010-04-22T19:07:24Z

← Older revision		Revision as of 19:07, 22 April 2010
Line 24:		Line 24:
	'''Linear Array'''		'''Linear Array'''
	<p>		<p>
	<~~pic top_linear~~>		[[Image:Top_linear.jpg]]
			<br>
			<br>
	The nodes are connected linearly as in an array. This type of topology is simple, however, it does not scale well. The longest distance between two nodes, or the '''diameter''', is equivalent to the number of nodes.		The nodes are connected linearly as in an array. This type of topology is simple, however, it does not scale well. The longest distance between two nodes, or the '''diameter''', is equivalent to the number of nodes.
	</p>		</p>
Line 31:		Line 33:
	'''Ring'''		'''Ring'''
	<p>		<p>
	<~~pic top_ring~~>		[[Image:Top_ring.jpg]]
			<br>
			<br>
	Similar structure as the linear array, except, the ending nodes connect to each other, establishing a circular structure. The longest distance between two nodes is cut in half.		Similar structure as the linear array, except, the ending nodes connect to each other, establishing a circular structure. The longest distance between two nodes is cut in half.
	</p>		</p>
Line 38:		Line 42:
	'''2-D Mesh'''		'''2-D Mesh'''
	<p>		<p>
	<~~pic top_2Dmesh~~>		[[Image:Top_2Dmesh.jpg]]
			<br>
			<br>
	The 2-D mesh can be thought of as several linear arrays put together to form a 2-dimensional structure. Nodes that are not on the edge have 4 input or output links, or a '''degree''' of 4.		The 2-D mesh can be thought of as several linear arrays put together to form a 2-dimensional structure. Nodes that are not on the edge have 4 input or output links, or a '''degree''' of 4.
	</p>		</p>
Line 45:		Line 51:
	'''2-D Torus'''		'''2-D Torus'''
	<p>		<p>
	<~~pic top_2Dtorus~~>		[[Image:Top_2DTorus.jpg]]
			<br>
			<br>
	The 2-D torus takes the structure of the 2-D mesh and connects the nodes on the edges. This decreases the diameter, but the number of links is higher.		The 2-D torus takes the structure of the 2-D mesh and connects the nodes on the edges. This decreases the diameter, but the number of links is higher.
	</p>		</p>
Line 52:		Line 60:
	'''Cube'''		'''Cube'''
	<p>		<p>
	<~~pic top_cube~~>		[[Image:Top_cube.jpg]]
			<br>
			<br>
	The cube can be thought of as a three-dimensional mesh.		The cube can be thought of as a three-dimensional mesh.
	</p>		</p>
Line 59:		Line 69:
	'''Hypercube'''		'''Hypercube'''
	<p>		<p>
	<~~pic top_hypercube~~>		[[Image:Top_hypercube.jpg]]
			<br>
			<br>
	The hypercube is essentially multiple cubes put together.		The hypercube is essentially multiple cubes put together.
	</p>		</p>
Line 66:		Line 78:
	'''Tree'''		'''Tree'''
	<p>		<p>
	<~~pic top_tree~~>		[[Image:Top_tree.jpg]]
			<br>
			<br>
	The tree is a hierarchical structure nodes on the bottom and switching nodes at the upper levels. The tree experiences high traffic at the upper levels.		The tree is a hierarchical structure nodes on the bottom and switching nodes at the upper levels. The tree experiences high traffic at the upper levels.
	</p>		</p>
Line 73:		Line 87:
	'''Fat Tree'''		'''Fat Tree'''
	<p>		<p>
	<~~pic top_fat_tree~~>		[[Image:Top_fat_tree.jpg]]
			<br>
			<br>
	The fat tree alleviates the traffic at upper levels by "fattening" up the links at the upper levels.		The fat tree alleviates the traffic at upper levels by "fattening" up the links at the upper levels.
	</p>		</p>
Line 80:		Line 96:
	'''Butterfly'''		'''Butterfly'''
	<p>		<p>
	<~~pic top_butterfly~~>		[[Image:Top_butterfly.jpg]]
			<br>
			<br>
	The butterfly structure is similar to the tree structure, but it replicates the switching node structure of the tree topology and connects them together so that there are equal links and routers at all levels.		The butterfly structure is similar to the tree structure, but it replicates the switching node structure of the tree topology and connects them together so that there are equal links and routers at all levels.
	</p>		</p>
Line 102:		Line 120:
	<p>		<p>
	The overall structure of the network is shown below. Note that this structure is very susceptible to failure and congestion.		The overall structure of the network is shown below. Note that this structure is very susceptible to failure and congestion.
			<br>
	<~~pic disknet_network~~>		[[Image:Disknet_network.jpg]]
			<br>
	</p>		</p>

Line 117:		Line 136:
	<p>		<p>
	In high performance applications, the butterfly structure is a good choice. The butterfly topology uses fewer links than other topologies, however, each link carries traffic from the entire layer. Fault tolerance is poor. There exists only a single path between pairs of nodes. Should the link break, data cannot be re-routed, and communication is broken<sup>2</sup>.		In high performance applications, the butterfly structure is a good choice. The butterfly topology uses fewer links than other topologies, however, each link carries traffic from the entire layer. Fault tolerance is poor. There exists only a single path between pairs of nodes. Should the link break, data cannot be re-routed, and communication is broken<sup>2</sup>.
			<br>
	<~~pic disknet_butterfly~~>		[[Image:Disknet_butterfly.jpg]]
	</p>		</p>
	<br>		<br>
Line 125:		Line 144:
	<p>		<p>
	The mesh and torus structure used in this application would require a large number of links and total aggregate of several thousands of ports. However, since there are so many links, the mesh and torus structures provide alternates paths in case of failures<sup>2</sup>.		The mesh and torus structure used in this application would require a large number of links and total aggregate of several thousands of ports. However, since there are so many links, the mesh and torus structures provide alternates paths in case of failures<sup>2</sup>.
			<br>
	<~~pic disknet_mesh~~>		[[Image:Disknet_mesh.jpg]]
	<~~pic disknet_torus~~>		<br>
			[[Image:Disknet_torus.jpg]]
	</p>		</p>
	<br>		<br>
Line 134:		Line 154:
	<p>		<p>
	Similar to the torii structures, the hypercube requires larger number of links. However, the bandwidth scales better than mesh and torii structures.		Similar to the torii structures, the hypercube requires larger number of links. However, the bandwidth scales better than mesh and torii structures.
			<br>
	<~~pic disknet_hypercube~~>		[[Image:Disknet_hypercube.jpg]]
	</p>		</p>
	<br>		<br>