CSC/ECE 506 Spring 2010/ch 12 PP - Revision history

Ppratha: /* Routing Algorithms */

2010-05-02T21:22:53Z

Routing Algorithms

← Older revision		Revision as of 21:22, 2 May 2010
Line 334:		Line 334:

	'''Number of paths:''' Algorithms can be classified according to the number of alternative paths as '''Completely Adaptive''' (or fully adaptive) or '''Partially Adaptive'''.		'''Number of paths:''' Algorithms can be classified according to the number of alternative paths as '''Completely Adaptive''' (or fully adaptive) or '''Partially Adaptive'''.

			==Deadlock==

			This is a situation where each packet waits for the other to finish, and since a waiting activity cannot finish, deadlock lasts forever. For example if each packet whose header has not yet arrived requests for buffers, and they are full, they will never get access since packet cannot be moved till the header arrives. This causes a deadlock between header requesting space but not getting it due to packet not being able to process.

			==Starvation==
			This situation arises when resources requested by the packet are always granted to other packet. This happened when incorrect resource assignment scheme is used to arbitrate in the case of conflict.

			==Livelock==
			Even if the packets are not blocked, they may not reach their destination node because the channels required to do so are occupied by other packets.

	=References=		=References=

Ppratha: /* Routing Algorithms */

2010-04-24T19:30:06Z

Routing Algorithms

← Older revision		Revision as of 19:30, 24 April 2010
Line 321:		Line 321:
	[[Image:Routing_algos.jpg]]		[[Image:Routing_algos.jpg]]

	Number of Destinations: In Unicast Routing packets have a single destination and multiple destinations in Multicast Routing.		'''Number of Destinations:''' In '''Unicast''' Routing packets have a single destination and multiple destinations in '''Multicast''' Routing.

	Routing Decisions: The path can either be established by a centralized controller ('''Centralized Routing''') at the source node prior to packet injection ('''Source Routing''') or determined in a distributed manner while the packet travels across the network ('''Distributed Routing'''). Hybrid Schemes are called '''Multiphase Routing''' in which the source node computes some destination nodes.		'''Routing Decisions:''' The path can either be established by a centralized controller ('''Centralized Routing''') at the source node prior to packet injection ('''Source Routing''') or determined in a distributed manner while the packet travels across the network ('''Distributed Routing'''). Hybrid Schemes are called '''Multiphase Routing''' in which the source node computes some destination nodes.

	Implementation: Routing algorithms can be implemented either by looking at a routing table ('''Table Lookup''') or executing a routing algorithm in software/hardware according to a '''Finite-State Machine'''.		'''Implementation:''' Routing algorithms can be implemented either by looking at a routing table ('''Table Lookup''') or executing a routing algorithm in software/hardware according to a '''Finite-State Machine'''.

	Adaptivity: '''Deterministic routing''' algorithms always supply the same path between a given source/destination pair. '''Adaptive routing''' algorithms use information abput network traffic and/or channel status to avoid congested or faulty regions of the network.		'''Adaptivity:''' '''Deterministic routing''' algorithms always supply the same path between a given source/destination pair. '''Adaptive routing''' algorithms use information abput network traffic and/or channel status to avoid congested or faulty regions of the network.

	Progressiveness: Adaptive algorithms can be progressive or backtracking. '''Progressive''' algorithms move the header forward, reserving a new channel at each routing operation. '''Backtracking''' allow the header to backtrack, releasing previously reserved channels. Backtracking algorithms are used for fault-tolerant routing.		''' Progressiveness:''' Adaptive algorithms can be progressive or backtracking. '''Progressive''' algorithms move the header forward, reserving a new channel at each routing operation. '''Backtracking''' allow the header to backtrack, releasing previously reserved channels. Backtracking algorithms are used for fault-tolerant routing.

	Minimality: '''Profitable''' routing algorithms only supply channels that bring the packet closer to its destination. '''Misrouting''' may also supply channels that send packets away from destinations.

	~~Number of paths: Algorithms can be classified according to the number of alternative paths as '''Completely Adaptive''' (or fully adaptive) or '''Partially Adaptive'''~~.

			'''Minimality:''' '''Profitable''' routing algorithms only supply channels that bring the packet closer to its destination. '''Misrouting''' may also supply channels that send packets away from destinations.

			'''Number of paths:''' Algorithms can be classified according to the number of alternative paths as '''Completely Adaptive''' (or fully adaptive) or '''Partially Adaptive'''.

	=References=		=References=

Ppratha at 19:28, 24 April 2010

2010-04-24T19:28:41Z

@@ Line 315: / Line 315: @@
 ''Figure22: Distributed Crossbar Switch Hypermesh Networks ''
-==References==
+=Routing Algorithms=
 * http://www.boardguess.com/universitiesdeemed-universities/ignou/ignou-bca/assignments-bca/sem-i/100-100.htm
-* Interconnection Networks: An Engineering Approach by Duato, Jośe. Yalamanchili, Sudhakar. Ni, Lionel M.
+* Interconnection Networks: An Engineering Approach by Duato, Jośe. Yalamanchili, Sudhakar. Ni, Lionel M. (Referencing many pictures and real implementations)
 * http://www.boardguess.com/universitiesdeemed-universities/ignou/ignou-bca/assignments-bca/sem-i/100-100.htm

Ppratha: /* Choosing the “Best” Network */

2010-04-24T19:00:02Z

Choosing the “Best” Network

← Older revision		Revision as of 19:00, 24 April 2010
Line 10:		Line 10:

	While there is no best network that would work well for all applications, it greatly depends on the given application and the parallel system at hand. The following are some of the factors that affect the choice of interconnection network.		While there is no best network that would work well for all applications, it greatly depends on the given application and the parallel system at hand. The following are some of the factors that affect the choice of interconnection network.


	1. '''Performance Requirements:''' Minimize message latency, avoid network from saturating (unable to deliver messages injected by nodes) and increase throughput of the network.		1. '''Performance Requirements:''' Minimize message latency, avoid network from saturating (unable to deliver messages injected by nodes) and increase throughput of the network.

Ppratha: /* Choosing the “Best” Network */

2010-04-24T18:59:49Z

Choosing the “Best” Network

← Older revision		Revision as of 18:59, 24 April 2010
Line 9:		Line 9:
	==Choosing the “Best” Network==		==Choosing the “Best” Network==

	While there is no best network that would work well for all applications, it greatly depends on the given application and the parallel system at hand. The following are some of the factors affect the choice of interconnection network.		While there is no best network that would work well for all applications, it greatly depends on the given application and the parallel system at hand. The following are some of the factors that affect the choice of interconnection network.


Line 31:		Line 31:

	10. '''Cost Constraints:''' The “best” network might be too expensive. Alternative design considerations are important to meet cost constraints.		10. '''Cost Constraints:''' The “best” network might be too expensive. Alternative design considerations are important to meet cost constraints.


	==Classification of Interconnection networks==		==Classification of Interconnection networks==

Ppratha at 18:58, 24 April 2010

2010-04-24T18:58:05Z

← Older revision		Revision as of 18:58, 24 April 2010
Line 1:		Line 1:
	=Interconnection Networks=		=Interconnection Networks=

			==Development of Interconnection Structures==

			Advances in multiprocessors, parallel computing & networking and parallel computer architectures demand very high performance from interconnection networks. Due to this, interconnection network structure has changed over time, trying to meet higher bandwidths and performance.

			Number of applications requiring interconnection networks are continuously growing. These include backplane buses and system area networks; telephone switches; internal networks for asynchronous transfer mode and Internet Protocol switches; processor/memory interconnects for vector supercomputers; interconnection networks for multicomputers and distributed shared-memory multiprocessors; clusters of workstations and personal computers; local area networks; wide area computer networks and networks for industrial applications. Hence, the demand for higher network bandwidth, scalability and reliability have led to new developments in network structures.

	==Choosing the “Best” Network==		==Choosing the “Best” Network==

Ppratha at 16:22, 24 April 2010

2010-04-24T16:22:30Z

Ppratha at 16:14, 24 April 2010

2010-04-24T16:14:03Z

Show changes

Ppratha: /* References */

2010-04-24T16:00:51Z

References

← Older revision		Revision as of 16:00, 24 April 2010
Line 277:		Line 277:

	==References==		==References==

			* http://www.boardguess.com/universitiesdeemed-universities/ignou/ignou-bca/assignments-bca/sem-i/100-100.htm

			* Interconnection Networks: An Engineering Approach by Duato, Jośe. Yalamanchili, Sudhakar. Ni, Lionel M.

			* http://www.boardguess.com/universitiesdeemed-universities/ignou/ignou-bca/assignments-bca/sem-i/100-100.htm

			* http://www.cse.iitk.ac.in/~dheeraj/cs425/lec08.html

			* http://www.cs.nmsu.edu/~pfeiffer/classes/573/notes/topology.html

			* http://kbs.cs.tu-berlin.de/projects/tusci_engl.htm

			* http://www.top500.org/2007_overview_recent_supercomputers/sci

			* http://www.wikipedia.org/

Ppratha at 15:56, 24 April 2010

2010-04-24T15:56:16Z

← Older revision		Revision as of 15:56, 24 April 2010
Line 260:		Line 260:
	====Hierarchical Networks====		====Hierarchical Networks====

			Different buses are interconnected by routers and bridges to transfer information. Routers/bridges filter the network traffic by checking the destination address of the message. This approach is used in bridged LAN.

	[[Image:Hybrid2.jpg]]		[[Image:Hybrid2.jpg]]

	====Cluster-Based Networks====		====Cluster-Based Networks====

			Cluster based network combine advantages of buses and point-to-point links by using buses at the lower level in the hierarchy to form clusters and a direct network topology connecting the clusters at the higher level.

	[[Image:Hybrid3.jpg]]		[[Image:Hybrid3.jpg]]

	====Other Hypergraph Topologies====		====Other Hypergraph Topologies====

			Figure __ shows a distributed crossbar switch hypermesh. Each bus is driven by a single node. Bandwidth scales with the number of nodes.

	[[Image:Hybrid4.jpg]]		[[Image:Hybrid4.jpg]]

			==References==

← Older revision		Revision as of 16:22, 24 April 2010
Line 51:		Line 51:
	'''Implementation examples:'''		'''Implementation examples:'''

	*IBM token ring: Supports bandwidth of 4 or 16 Mbps based on coaxial tube		*'''IBM token ring:''' Supports bandwidth of 4 or 16 Mbps based on coaxial tube
	*FDDI: Bandwidth of 100Mbps using fiber optics		*'''FDDI:''' Bandwidth of 100Mbps using fiber optics


Line 67:		Line 67:
	'''Implementation examples:'''		'''Implementation examples:'''

	*ARCNET: Attached Resource Computer NETwork		*'''ARCNET:''' Attached Resource Computer NETwork


Line 81:		Line 81:
	'''Implementation examples:'''		'''Implementation examples:'''

	*Gigaplane used in Sun Ultra Enterprise X000 Server (ca. 1996): 2.68 Gbyte/s peak, 256 bits data, 42 bits address, split transaction protocol, 83.8 MHz clock		*Gigaplane used in '''Sun Ultra Enterprise X000 Server''' (ca. 1996): 2.68 Gbyte/s peak, 256 bits data, 42 bits address, split transaction protocol, 83.8 MHz clock

	*DEC AlphaServer8X00, i.e. 8200 & 8400 (ca. 1995): 2.1 Gbyte/s, 256 bits data, 40 bits address, split transaction protocol, 100 MHz clock (1 foot length)		*'''DEC AlphaServer8X00''', i.e. 8200 & 8400 (ca. 1995): 2.1 Gbyte/s, 256 bits data, 40 bits address, split transaction protocol, 100 MHz clock (1 foot length)

	*SGI PowerPath -2 (ca. 1993): 1.2 Gbyte/s, 256 bits data, 40 bits address, 6 bits control, split transaction protocol, 47.5 MHz clock		*'''SGI PowerPath-2 (ca. 1993):''' 1.2 Gbyte/s, 256 bits data, 40 bits address, 6 bits control, split transaction protocol, 47.5 MHz clock

	*HP9000 Multiprocessor Memory Bus (ca. 1993): 1Gbyte/s, 128 buts data, 64 bit address, 13 inches, pipelined bus, 60 MHz clock		*'''HP9000 Multiprocessor Memory Bus (ca. 1993):''' 1Gbyte/s, 128 buts data, 64 bit address, 13 inches, pipelined bus, 60 MHz clock


Line 120:		Line 120:
	'''Implementation Examples:'''		'''Implementation Examples:'''

	* Intel Paragon: 16 rows and 16 columns of nodes, with a 2D mesh connecting them, 130 MB/sec for 1 MB messages, with a latency of around 100 usecs.		* '''Intel Paragon:''' 16 rows and 16 columns of nodes, with a 2D mesh connecting them, 130 MB/sec for 1 MB messages, with a latency of around 100 usecs.

	* MIT Reliable Router: 2-D Mesh, 23-bit links (16- bit data), 200 MHz, 400 M bytes/s per link per direction, bidirectional signaling, reliable transmission.		* '''MIT Reliable Router:''' 2-D Mesh, 23-bit links (16- bit data), 200 MHz, 400 M bytes/s per link per direction, bidirectional signaling, reliable transmission.

	* MIT M-Machine: 3-D Mesh, 800 M bytes/s for each network channel.		* '''MIT M-Machine:''' 3-D Mesh, 800 M bytes/s for each network channel.


Line 138:		Line 138:
	'''Implementation Examples:'''		'''Implementation Examples:'''

	*Chaos Router: 2-D torus topology, bidirectional 8-bit links, 180 MHz, 260 Mbytes/s in each direction.		*'''Chaos Router:''' 2-D torus topology, bidirectional 8-bit links, 180 MHz, 260 Mbytes/s in each direction.

	*Cray T3E: Bidirectional 3-D torus, 14-bit data in each direction, 375 MHz link speed, 600 Mbytes/s in each direction.		*'''Cray T3E:''' Bidirectional 3-D torus, 14-bit data in each direction, 375 MHz link speed, 600 Mbytes/s in each direction.

	*Cray T3D: Bidirectional 3-D torus, up to 1024 nodes (8 x 16 x 8), 24-bit links (16-bit data, 8-bit control), 150 MHz, 300 Mbytes/s per link.		*'''Cray T3D:''' Bidirectional 3-D torus, up to 1024 nodes (8 x 16 x 8), 24-bit links (16-bit data, 8-bit control), 150 MHz, 300 Mbytes/s per link.


Line 153:		Line 153:
	'''Implementation Examples:'''		'''Implementation Examples:'''

	* Intel iPSC-2 Hypercube: Binary hypercube topology, bit-serial channels at 2.8 Mbytes/s.		* '''Intel iPSC-2 Hypercube:''' Binary hypercube topology, bit-serial channels at 2.8 Mbytes/s.


Line 261:		Line 261:
	'''Implementation examples of Indirect Networks:'''		'''Implementation examples of Indirect Networks:'''

	* Myricom Myrinet: Supports regular and irregular topologies, 8 x 8 crossbar switch, 9-bit channels, full-duplex, 160 Mbytes/s per link.		* '''Myricom Myrinet:''' Supports regular and irregular topologies, 8 x 8 crossbar switch, 9-bit channels, full-duplex, 160 Mbytes/s per link.

	*Thinking Machines CM-5: Fat tree topology, 4-bit bidirectional channels at 40 MHz, aggregate bandwidth in each direction of 20 Mbytes/s.		*'''Thinking Machines CM-5:''' Fat tree topology, 4-bit bidirectional channels at 40 MHz, aggregate bandwidth in each direction of 20 Mbytes/s.

	*Inmos C104: Supports regular and irregular topologies, 32 x 32 crossbar switch, serial links, 100 Mbits/s per link.		*'''Inmos C104:''' Supports regular and irregular topologies, 32 x 32 crossbar switch, serial links, 100 Mbits/s per link.

	*IBM SP2: Crossbar switches supporting Omega network topologies with bidirectional, 16-bit channels at 150 MHz, 300 Mbytes/s in each direction.		*'''IBM SP2:''' Crossbar switches supporting Omega network topologies with bidirectional, 16-bit channels at 150 MHz, 300 Mbytes/s in each direction.

	*SGI SPIDER: Router with 20-bit bidirectional channels operating on both edges, 200 MHz clock aggregate row data rate of 1Gbyte/s. Offers support for configurations as nonblocking multistage network topologies as well as irregular topologies.		*'''SGI SPIDER:''' Router with 20-bit bidirectional channels operating on both edges, 200 MHz clock aggregate row data rate of 1Gbyte/s. Offers support for configurations as nonblocking multistage network topologies as well as irregular topologies.

	*Tandem ServerNet: Irregular topologies, 8-bit bidirectional channels at 50 MHz, 50 Mbytes/s link		*'''Tandem ServerNet:''' Irregular topologies, 8-bit bidirectional channels at 50 MHz, 50 Mbytes/s link