CSC/ECE 506 Spring 2013/12a cm - Revision history

Cthinkel at 05:06, 25 April 2013

2013-04-25T05:06:22Z

Mchen4 at 04:23, 18 April 2013

2013-04-18T04:23:09Z

← Older revision		Revision as of 04:23, 18 April 2013
Line 184:		Line 184:
	<h2>Fat Tree</h2>		<h2>Fat Tree</h2>
	<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><span id="2body">[[#2foot\|[2]]]</span></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 an 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><span id="2body">[[#2foot\|[2]]]</span></sup>.
	<br>		<br>
	<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><span id="7body">[[#7foot\|[7]]]</span></sup>.		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><span id="7body">[[#7foot\|[7]]]</span></sup>.
	~~</p>~~
	<br>		<br>
			Mercury Computer System's RACEway, their original interconnect fabric, uses 6-way crossbar chips organized in a fat tree network. The fat tree network was particularly well suited for Fast Fourier Transforms, which was used for signal processing<sup><span id="13body">[[#13foot\|[13]]]</span>.

	<h2>Butterfly</h2>		<h2>Butterfly</h2>
Line 206:		Line 206:

	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><span id="7body">[[#7foot\|[7]]]</span></sup>.		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><span id="7body">[[#7foot\|[7]]]</span></sup>.
			Originally developed for military applications, wireless mesh networks are now being used in the consumer sector. MIT Media Lab's XO-1 laptop, also known as "OLPC" (One Laptop Per Child) uses mesh networking to create an inexpensive infrastructure. The connections made by the laptops are used to reduce the need for an external infrastructure<sup><span id="15body">[[#15foot\|[15]]]</span>.


	<h2>Hypercube</h2>		<h2>Hypercube</h2>

	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.

	The CRAY T3E, CRAY XT3, and SGI Origin 2000 ~~use~~ k-ary n-cubed topologies.		Intel produced several supercomputers using hypercube design, of which the best known was the iPSC/860. Other early supercomputers, including the first few models of the Conection Machine family from Thinking Machines Corporation, also used the hypercube design. The CRAY T3E, CRAY XT3, and SGI Origin 2000 also used k-ary n-cubed topologies.

	[[Image:Disknet_hypercube.jpg\|frame\|center\|''Hypercube structure''<sup><span id="2body">[[#2foot\|[2]]]</span></sup>]]		[[Image:Disknet_hypercube.jpg\|frame\|center\|''Hypercube structure''<sup><span id="2body">[[#2foot\|[2]]]</span></sup>]]
Line 553:		Line 555:
	<span id="12foot">[[#12body\|12.]]</span> http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.95.573&rep=rep1&type=pdf Flattened Butterfly Topology <br />		<span id="12foot">[[#12body\|12.]]</span> http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.95.573&rep=rep1&type=pdf Flattened Butterfly Topology <br />
	<span id="13foot">[[#13body\|13.]]</span> http://courses.engr.illinois.edu/cs533/sp2012/notes/InterconnectionNet.pdf <br />		<span id="13foot">[[#13body\|13.]]</span> http://courses.engr.illinois.edu/cs533/sp2012/notes/InterconnectionNet.pdf <br />
			<span id="14foot">[[#14body\|14.]]</span> http://courses.csail.mit.edu/6.896/spring04/handouts/papers/fat_trees.pdf <br />
			<span id="15foot">[[#15body\|15.]]</span> http://wiki.laptop.org/go/Mesh_Network_Details <br />
	<br />		<br />

Cthinkel at 02:05, 18 April 2013

2013-04-18T02:05:42Z

← Older revision		Revision as of 02:05, 18 April 2013
Line 223:		Line 223:
	In a 2D network, each router is very simple since it only needs to have a degree of 4. A router usually uses crossbar switches to route inputs to outputs and the cost of additional ports increase the complexity quadratically.		In a 2D network, each router is very simple since it only needs to have a degree of 4. A router usually uses crossbar switches to route inputs to outputs and the cost of additional ports increase the complexity quadratically.

	As an example, IBM's [http://en.wikipedia.org/wiki/Blue_Gene/Q Blue Gene/Q] uses a 3D mesh interconnect with auxiliary networks for global communications (broadcast and reductions), I/O, and management
	</p>		</p>
	<p>		<p>
	In comparison to a 2D mesh, a router for a hypercube is much more complex with a degree of twice the diameter. For example, for 5 dimensions, we need a router of degree 10. With other networks like a butterfly, the complexity of a router remains same at 4 but we would need a larger number of routers as the number of links is more.		In comparison to a 2D mesh, a router for a hypercube is much more complex with a degree of twice the diameter. For example, for 5 dimensions, we need a router of degree 10. With other networks like a butterfly, the complexity of a router remains same at 4 but we would need a larger number of routers as the number of links is more.
	</p>		</p>

			As an example, IBM's [http://en.wikipedia.org/wiki/Blue_Gene/Q Blue Gene/Q] uses a 3D mesh interconnect with auxiliary networks for global communications (broadcast and reductions), I/O, and management.

	<h1>Comparison of Network Topologies </h1>		<h1>Comparison of Network Topologies </h1>

Cthinkel at 02:05, 18 April 2013

2013-04-18T02:05:10Z

← Older revision		Revision as of 02:05, 18 April 2013
Line 222:		Line 222:
	<br> <br>		<br> <br>
	In a 2D network, each router is very simple since it only needs to have a degree of 4. A router usually uses crossbar switches to route inputs to outputs and the cost of additional ports increase the complexity quadratically.		In a 2D network, each router is very simple since it only needs to have a degree of 4. A router usually uses crossbar switches to route inputs to outputs and the cost of additional ports increase the complexity quadratically.

			As an example, IBM's [http://en.wikipedia.org/wiki/Blue_Gene/Q Blue Gene/Q] uses a 3D mesh interconnect with auxiliary networks for global communications (broadcast and reductions), I/O, and management
	</p>		</p>
	<p>		<p>

Cthinkel at 06:41, 17 April 2013

2013-04-17T06:41:04Z

← Older revision		Revision as of 06:41, 17 April 2013
Line 220:		Line 220:
	<p>		<p>
	From the perspective of performance and flexibility for each of the topologies, it looks like higher dimension networks are preferable compared to low dimensional networks. However, in reality, cost of building the network is also an important consideration. A mesh network is much easier to layout because all of the connections can be made in 2 dimensions. Conversely, hypercubes and butterflies contain many crossing wires which may need to be quite long to loop around the edge.		From the perspective of performance and flexibility for each of the topologies, it looks like higher dimension networks are preferable compared to low dimensional networks. However, in reality, cost of building the network is also an important consideration. A mesh network is much easier to layout because all of the connections can be made in 2 dimensions. Conversely, hypercubes and butterflies contain many crossing wires which may need to be quite long to loop around the edge.
			<br> <br>
	In a 2D network, each router is very simple since it only needs to have a degree of 4. A router usually uses crossbar switches to route inputs to outputs and the cost of additional ports increase the complexity quadratically.		In a 2D network, each router is very simple since it only needs to have a degree of 4. A router usually uses crossbar switches to route inputs to outputs and the cost of additional ports increase the complexity quadratically.
	</p>		</p>

Cthinkel at 06:36, 17 April 2013

2013-04-17T06:36:13Z

← Older revision		Revision as of 06:36, 17 April 2013
Line 217:		Line 217:
	It is worth to mention that even though there are many topologies have much better performance than 2-D mesh, the cost of these advanced topologies are also high. Since most of the chips is in 2-D space, it is very expensive to implement high dimensional topology on 2-D chip. For hypercube topology, the increases of number of node will cause higher degree for each node. For the butterfly topology, although the increases of degree is relatively slow but the required number of links and number of switches increases rapidly.		It is worth to mention that even though there are many topologies have much better performance than 2-D mesh, the cost of these advanced topologies are also high. Since most of the chips is in 2-D space, it is very expensive to implement high dimensional topology on 2-D chip. For hypercube topology, the increases of number of node will cause higher degree for each node. For the butterfly topology, although the increases of degree is relatively slow but the required number of links and number of switches increases rapidly.

	<h1> Why do 2D meshes dominate?</h1>		<h1> Why do meshes dominate?</h1>
	<p>		<p>
	From the perspective of performance and flexibility for each of the topologies, it looks like higher dimension networks are preferable compared to low dimensional networks. However, in reality, cost of building the network is also an important consideration. In a 2D network, each router is very simple since it only needs to have a degree of 4. A router usually uses crossbar switches to route inputs to outputs and the cost of additional ports increase the complexity quadratically.		From the perspective of performance and flexibility for each of the topologies, it looks like higher dimension networks are preferable compared to low dimensional networks. However, in reality, cost of building the network is also an important consideration. A mesh network is much easier to layout because all of the connections can be made in 2 dimensions. Conversely, hypercubes and butterflies contain many crossing wires which may need to be quite long to loop around the edge.

			In a 2D network, each router is very simple since it only needs to have a degree of 4. A router usually uses crossbar switches to route inputs to outputs and the cost of additional ports increase the complexity quadratically.
	</p>		</p>
	<p>		<p>

Cthinkel at 06:14, 17 April 2013

2013-04-17T06:14:08Z

← Older revision		Revision as of 06:14, 17 April 2013
Line 16:		Line 16:

	Hypercube topologies were invented in the 80s and had desirable characteristics when the number of nodes is small (~1000 maximum, often <100) and every processor must stop working to receive and forward the message <sup><span id="4body">[[#4foot\|[4]]]</span></sup>. The low-radix era began in 1985 and was defined by routers with between 4 and 8 ports using toroidal, mesh or fat-tree topologies and wormhole routing. This era lasted about 20 years until it was determined that routers with dozens of ports offered superior performance. Two topologies were developed to take advantage of the newly developed high-radix routers. These are flattened butterfly and dragonfly, which are somewhere between a mesh with each point on the mesh being a router (or virtual router in the case of dragonfly) with dozens or hundreds of nodes attached and a fat tree with sufficiently high arity as to only have two levels.		Hypercube topologies were invented in the 80s and had desirable characteristics when the number of nodes is small (~1000 maximum, often <100) and every processor must stop working to receive and forward the message <sup><span id="4body">[[#4foot\|[4]]]</span></sup>. The low-radix era began in 1985 and was defined by routers with between 4 and 8 ports using toroidal, mesh or fat-tree topologies and wormhole routing. This era lasted about 20 years until it was determined that routers with dozens of ports offered superior performance. Two topologies were developed to take advantage of the newly developed high-radix routers. These are flattened butterfly and dragonfly, which are somewhere between a mesh with each point on the mesh being a router (or virtual router in the case of dragonfly) with dozens or hundreds of nodes attached and a fat tree with sufficiently high arity as to only have two levels.

			The use of different topologies has changed over the years. The following pie charts from top500.org show the share of different network topologies over the years.

			[[Image:ob_wiki_12_2001.png ]] ''Interconnect Family Market Share for 2001''
			[[Image:ob_wiki_12_2004.png]] ''Interconnect Family Market Share for 2004''
			[[Image:ob_wiki_12_2007.png]] ''Interconnect Family Market Share for 2007''
			[[Image:ob_wiki_12_2010.png]] ''Interconnect Family Market Share for 2010''

			<h1> Performance Metrics for Interconnection Network Topologies</h1>

			<p>
			The several metrics used for evaluating characteristics of a network topology like latency, bandwidth, cost, etc. are as follows:
			*Diameter: This is the longest distance between any pair of nodes of the network. It is measured in terms of network hops (the number of links the message must travel before reaching the destination).
			*Bisection Bandwidth: This is the minimum number of links that one must cut in order to partition the network into two halves.
			*Degree: This is the total number of links in and out from a router.
			</p>
			<p>
			The Diameter and Bisection bandwidth are the measure of performance of a network while the degree along with the total number of links is the measure of cost.
			</p>

	<h2>Interconnection evolution in the Top500 List</h2>		<h2>Interconnection evolution in the Top500 List</h2>

Cthinkel at 06:06, 17 April 2013

2013-04-17T06:06:04Z

← Older revision		Revision as of 06:06, 17 April 2013
Line 154:		Line 154:

	In a research study by Andy Hospodor and Ethan Miller, several network topologies were investigated in a high-performance, high-traffic network<sup><span id="2body">[[#2foot\|[2]]]</span></sup>. Several topologies were investigated including the fat tree, butterfly, mesh, torii, and hypercube structures. Advantages and disadvantages including cost, performance, and reliability were discussed.		In a research study by Andy Hospodor and Ethan Miller, several network topologies were investigated in a high-performance, high-traffic network<sup><span id="2body">[[#2foot\|[2]]]</span></sup>. Several topologies were investigated including the fat tree, butterfly, mesh, torii, and hypercube structures. Advantages and disadvantages including cost, performance, and reliability were discussed.

			[[File:Machines.png\|frame\|center\|''Current Machine Statistics''<sup><span id="13body">[[#13foot\|[13]]]</span></sup>]]

	In this experiment, a petabyte-scale network with over 100 GB/s total aggregate bandwidth was investigated. The network consisted of 4096 disks with large servers with routers and switches in between<sup><span id="2body">[[#2foot\|[2]]]</span></sup>.		In this experiment, a petabyte-scale network with over 100 GB/s total aggregate bandwidth was investigated. The network consisted of 4096 disks with large servers with routers and switches in between<sup><span id="2body">[[#2foot\|[2]]]</span></sup>.
Line 526:		Line 528:
	<span id="11foot">[[#11body\|11.]]</span> http://www.google.com/research/pubs/pub35155.html Dragonfly Topology <br />		<span id="11foot">[[#11body\|11.]]</span> http://www.google.com/research/pubs/pub35155.html Dragonfly Topology <br />
	<span id="12foot">[[#12body\|12.]]</span> http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.95.573&rep=rep1&type=pdf Flattened Butterfly Topology <br />		<span id="12foot">[[#12body\|12.]]</span> http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.95.573&rep=rep1&type=pdf Flattened Butterfly Topology <br />
			<span id="13foot">[[#13body\|13.]]</span> http://courses.engr.illinois.edu/cs533/sp2012/notes/InterconnectionNet.pdf <br />
	<br />		<br />

Cthinkel at 04:02, 16 April 2013

2013-04-16T04:02:27Z

← Older revision		Revision as of 04:02, 16 April 2013
Line 195:		Line 195:

	It is worth to mention that even though there are many topologies have much better performance than 2-D mesh, the cost of these advanced topologies are also high. Since most of the chips is in 2-D space, it is very expensive to implement high dimensional topology on 2-D chip. For hypercube topology, the increases of number of node will cause higher degree for each node. For the butterfly topology, although the increases of degree is relatively slow but the required number of links and number of switches increases rapidly.		It is worth to mention that even though there are many topologies have much better performance than 2-D mesh, the cost of these advanced topologies are also high. Since most of the chips is in 2-D space, it is very expensive to implement high dimensional topology on 2-D chip. For hypercube topology, the increases of number of node will cause higher degree for each node. For the butterfly topology, although the increases of degree is relatively slow but the required number of links and number of switches increases rapidly.

			<h1> Why do 2D meshes dominate?</h1>
			<p>
			From the perspective of performance and flexibility for each of the topologies, it looks like higher dimension networks are preferable compared to low dimensional networks. However, in reality, cost of building the network is also an important consideration. In a 2D network, each router is very simple since it only needs to have a degree of 4. A router usually uses crossbar switches to route inputs to outputs and the cost of additional ports increase the complexity quadratically.
			</p>
			<p>
			In comparison to a 2D mesh, a router for a hypercube is much more complex with a degree of twice the diameter. For example, for 5 dimensions, we need a router of degree 10. With other networks like a butterfly, the complexity of a router remains same at 4 but we would need a larger number of routers as the number of links is more.
			</p>

	<h1>Comparison of Network Topologies </h1>		<h1>Comparison of Network Topologies </h1>

Cthinkel at 03:57, 16 April 2013

2013-04-16T03:57:46Z

← Older revision		Revision as of 03:57, 16 April 2013
Line 22:		Line 22:
	This chart shows the evolution over time of the different interconnect topologies by their dominance in the top500 list of supercomputers <sup><span id="7body">[[#7foot\|[7]]]</span></sup>. As one can see, many technologies came into vogue briefly before losing performance share and disappearing. In the early days of the list, most of the computers list that the interconnect type is not applicable. However, the trailing end of the hypercube phase is clear in burnt orange. The dark blue at the top is "other" and the dark red in the middle is "proprietary", so we can only speculate about what topologies they might employ. The toroidal mesh appears briefly at the start in a cream color, and slightly outlasts the hypercube. The two crossbar technologies (blue and olive) followed the toroidal mesh. The fully-distributed crossbar died out quickly, but the multi-stage crossbar lasted longer but wasn't ever dominant. The 3-D torus (purple) dominates much of the 90s with hypercube topologies (dark pink) enjoying a short comeback in the later part of the decade. SP Switch (light olive), an IBM interconnect technology which uses a multi-stage crossbar switch replaced the 3-D torus<sup><span id="8body">[[#8foot\|[8]]]</span></sup>. Myrinet, Quadrics, and Federation all shared the spotlight in the mid 00s each used a similar fat-tree topology<sup><span id="9body">[[#9foot\|[9]]]</span></sup><sup><span id="10body">[[#10foot\|[10]]]</span></sup>. The current class of supercomputers is dominated by nodes connected with either Infiniband or gigabit ethernet. Both can be connected in either a fat-tree or 2-D mesh topology. The primary difference between them is speed. Infiniband is considerably faster per link and allows links to be ganged into groups of 4 or 12. Gigabit ethernet is vastly less expensive, however, and some supercomputer designers have apparently chosen to save money on the interconnect technology in order to allow the use of faster nodes <sup><span id="11body">[[#11foot\|[11]]]</span></sup><sup><span id="12body">[[#12foot\|[12]]]</span></sup>.		This chart shows the evolution over time of the different interconnect topologies by their dominance in the top500 list of supercomputers <sup><span id="7body">[[#7foot\|[7]]]</span></sup>. As one can see, many technologies came into vogue briefly before losing performance share and disappearing. In the early days of the list, most of the computers list that the interconnect type is not applicable. However, the trailing end of the hypercube phase is clear in burnt orange. The dark blue at the top is "other" and the dark red in the middle is "proprietary", so we can only speculate about what topologies they might employ. The toroidal mesh appears briefly at the start in a cream color, and slightly outlasts the hypercube. The two crossbar technologies (blue and olive) followed the toroidal mesh. The fully-distributed crossbar died out quickly, but the multi-stage crossbar lasted longer but wasn't ever dominant. The 3-D torus (purple) dominates much of the 90s with hypercube topologies (dark pink) enjoying a short comeback in the later part of the decade. SP Switch (light olive), an IBM interconnect technology which uses a multi-stage crossbar switch replaced the 3-D torus<sup><span id="8body">[[#8foot\|[8]]]</span></sup>. Myrinet, Quadrics, and Federation all shared the spotlight in the mid 00s each used a similar fat-tree topology<sup><span id="9body">[[#9foot\|[9]]]</span></sup><sup><span id="10body">[[#10foot\|[10]]]</span></sup>. The current class of supercomputers is dominated by nodes connected with either Infiniband or gigabit ethernet. Both can be connected in either a fat-tree or 2-D mesh topology. The primary difference between them is speed. Infiniband is considerably faster per link and allows links to be ganged into groups of 4 or 12. Gigabit ethernet is vastly less expensive, however, and some supercomputer designers have apparently chosen to save money on the interconnect technology in order to allow the use of faster nodes <sup><span id="11body">[[#11foot\|[11]]]</span></sup><sup><span id="12body">[[#12foot\|[12]]]</span></sup>.

			<br>
	<br>		<br>
	<br>		<br>

← Older revision		Revision as of 06:06, 17 April 2013
Line 154:		Line 154:

	In a research study by Andy Hospodor and Ethan Miller, several network topologies were investigated in a high-performance, high-traffic network<sup><span id="2body">[[#2foot\|[2]]]</span></sup>. Several topologies were investigated including the fat tree, butterfly, mesh, torii, and hypercube structures. Advantages and disadvantages including cost, performance, and reliability were discussed.		In a research study by Andy Hospodor and Ethan Miller, several network topologies were investigated in a high-performance, high-traffic network<sup><span id="2body">[[#2foot\|[2]]]</span></sup>. Several topologies were investigated including the fat tree, butterfly, mesh, torii, and hypercube structures. Advantages and disadvantages including cost, performance, and reliability were discussed.

			[[File:Machines.png\|frame\|center\|''Current Machine Statistics''<sup><span id="13body">[[#13foot\|[13]]]</span></sup>]]

	In this experiment, a petabyte-scale network with over 100 GB/s total aggregate bandwidth was investigated. The network consisted of 4096 disks with large servers with routers and switches in between<sup><span id="2body">[[#2foot\|[2]]]</span></sup>.		In this experiment, a petabyte-scale network with over 100 GB/s total aggregate bandwidth was investigated. The network consisted of 4096 disks with large servers with routers and switches in between<sup><span id="2body">[[#2foot\|[2]]]</span></sup>.
Line 526:		Line 528:
	<span id="11foot">[[#11body\|11.]]</span> http://www.google.com/research/pubs/pub35155.html Dragonfly Topology <br />		<span id="11foot">[[#11body\|11.]]</span> http://www.google.com/research/pubs/pub35155.html Dragonfly Topology <br />
	<span id="12foot">[[#12body\|12.]]</span> http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.95.573&rep=rep1&type=pdf Flattened Butterfly Topology <br />		<span id="12foot">[[#12body\|12.]]</span> http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.95.573&rep=rep1&type=pdf Flattened Butterfly Topology <br />
			<span id="13foot">[[#13body\|13.]]</span> http://courses.engr.illinois.edu/cs533/sp2012/notes/InterconnectionNet.pdf <br />
	<br />		<br />