CSC/ECE 506 Spring 2012/12a mt - Revision history

Mjtanner at 02:55, 26 April 2012

2012-04-26T02:55:25Z

← Older revision		Revision as of 02:55, 26 April 2012
Line 126:		Line 126:


	2) What is a more simplified way to calculate the ''cost'' of a ~~BVH~~?		2) What is a more simplified way to calculate the ''cost'' of a Balanced Varietal Hypercube?

	a) 3n		a) 3n
Line 166:		Line 166:


	6) For review, which of the following is '''NOT''' one of the three ingredients necessary for an efficient ~~SMP~~?		6) For review, which of the following is '''NOT''' one of the three ingredients necessary for an efficient shared memory multiprocessor?

	a) synchronization primitives		a) synchronization primitives
Line 199:		Line 199:


	9)		9) Why is it important for a interconnection network to have ''high'' bandwidth communication?

	a) 3n		a) It isn't important, only achieving low latency is important.

	b) ~~3n^2~~		b) It means the network is fast.

	c) ~~2n^2 + n~~		c) It means the network is correct.

	d) ~~2n^2 + 2n~~		d) It means the network is efficient.

Mjtanner at 02:38, 26 April 2012

2012-04-26T02:38:49Z

@@ Line 164: / Line 164: @@
 d) 10
 ==='''''Answer Key'''''===
-) ''d''; 2) ''b''; 3) ''b''; 4) ''c''; 5) ''a''; 6) ; 7) ; 8) ; 9) ; 10) ;
+) ''d''; 2) ''b''; 3) ''b''; 4) ''c''; 5) ''a''; 6) ''c''; 7) ''b''; 8) ''a''; 9) ''d''; 10) ''a'';

Mjtanner at 02:27, 26 April 2012

2012-04-26T02:27:02Z

← Older revision		Revision as of 02:27, 26 April 2012
Line 34:		Line 34:

	N = k^n		N = k^n
	*complexity limited by wire delay, speed limited by wire density, and majority of power consumed by drive wires.
	===The ''PROBLEM''===		===The ''PROBLEM''===

	As mentioned previously, a VLSI network is wire-limited; as a result: network complexity is limited by wire delay, the program's run speed is limited by wire density, and the majority of the power is consumed by drive wires. Therefore, in order to achieve a low latency and high bandwidth communication, network architects have make sure that their designs are "wire-efficient". To do this, the wires need to be kept as short as possible in order to limit latency and diameter. Furthermore, when architects are brainstorming ideas for their networks, they have to ensure the physical organization (the wires) matches the logical organization (function of the program) so that it produces the most efficient and optimized results.		As mentioned previously, a VLSI network is wire-limited; as a result: network complexity is limited by wire delay, the program's run speed is limited by wire density, and the majority of the power is consumed by drive wires. Therefore, in order to achieve a low latency and high bandwidth communication, network architects have make sure that their designs are "wire-efficient". To do this, the wires need to be kept as short as possible in order to limit latency and diameter. Furthermore, when architects are brainstorming ideas for their networks, they have to ensure the physical organization (the wires) matches the logical organization (function of the program) so that it produces the most efficient and optimized results.

	However, "networks have traditionally been analyzed under the assumption of constant channel bandwidth"[3]. As it so happens, constant channel bandwidth favors high-dimensional networks; unfortunately, low-dimensional networks are far more efficient than high-dimensional ones under VLSI. The reason is due to VLSI's wire-limited nature. As more processors (and subsequently more dimensions) are added to the network, the length and number of wires needed increase. Due to the number of wires increasing, the number of [ links]		However, "networks have traditionally been analyzed under the assumption of constant channel bandwidth"[3]. As it so happens, constant channel bandwidth favors high-dimensional networks; unfortunately, low-dimensional networks are far more efficient than high-dimensional ones under VLSI. The reason is due to VLSI's wire-limited nature. As more processors (and subsequently more dimensions) are added to the network, the length and number of wires needed increase. Due to the number of wires increasing, the number of [http://expertiza.csc.ncsu.edu/wiki/index.php/CSC/ECE_506_Spring_2012/12a_mt#Glossary links] necessary for messages to cross to reach their destination increase, thereby increasing the latency. Furthermore, the increase in length of the wires means that more materials are needed to build the network, thereby increasing the cost. By the early 1990s, network architects began to abandon VLSI networks like the 'k''-ary ''n''-cube, and began to research networks that would be more favorable to high-dimensional networks.

	=='''Recent Studies'''==		=='''Recent Studies'''==
Line 135:		Line 135:

	d) 2n^2 + 2n		d) 2n^2 + 2n


	3) True or False: The current FTΩ can tolerate more than one node malfunction at a time.		3) True or False: The current FTΩ can tolerate more than one node malfunction at a time.

			a) True

			b) False


			4) How many nodes are in a binary 10-node cube? (Hint: the prefix ''bi-'' in Latin means "two".

			a) 20

			b) 100

			c) 1024

			d) 2048


			5) If there are 2187 nodes in a tertiary (''k'' = 3) cube, what is the value of ''n''?

			a) 7

			b) 8

			c) 9

			d) 10

	==='''''Answer Key'''''===		==='''''Answer Key'''''===

	1) ''d''; 2) ''b'';		1) ''d''; 2) ''b''; 3) ''b''; 4) ''c''; 5) ''a''; 6) ; 7) ; 8) ; 9) ; 10) ;

Mjtanner at 02:14, 26 April 2012

2012-04-26T02:14:00Z

← Older revision		Revision as of 02:14, 26 April 2012
Line 39:		Line 39:
	As mentioned previously, a VLSI network is wire-limited; as a result: network complexity is limited by wire delay, the program's run speed is limited by wire density, and the majority of the power is consumed by drive wires. Therefore, in order to achieve a low latency and high bandwidth communication, network architects have make sure that their designs are "wire-efficient". To do this, the wires need to be kept as short as possible in order to limit latency and diameter. Furthermore, when architects are brainstorming ideas for their networks, they have to ensure the physical organization (the wires) matches the logical organization (function of the program) so that it produces the most efficient and optimized results.		As mentioned previously, a VLSI network is wire-limited; as a result: network complexity is limited by wire delay, the program's run speed is limited by wire density, and the majority of the power is consumed by drive wires. Therefore, in order to achieve a low latency and high bandwidth communication, network architects have make sure that their designs are "wire-efficient". To do this, the wires need to be kept as short as possible in order to limit latency and diameter. Furthermore, when architects are brainstorming ideas for their networks, they have to ensure the physical organization (the wires) matches the logical organization (function of the program) so that it produces the most efficient and optimized results.

	However, "networks have traditionally been analyzed under the assumption of constant channel bandwidth"[3].		However, "networks have traditionally been analyzed under the assumption of constant channel bandwidth"[3]. As it so happens, constant channel bandwidth favors high-dimensional networks; unfortunately, low-dimensional networks are far more efficient than high-dimensional ones under VLSI. The reason is due to VLSI's wire-limited nature. As more processors (and subsequently more dimensions) are added to the network, the length and number of wires needed increase. Due to the number of wires increasing, the number of [ links]

	=='''Recent Studies'''==		=='''Recent Studies'''==

Mjtanner at 02:08, 26 April 2012

2012-04-26T02:08:47Z

← Older revision		Revision as of 02:08, 26 April 2012
Line 39:		Line 39:
	As mentioned previously, a VLSI network is wire-limited; as a result: network complexity is limited by wire delay, the program's run speed is limited by wire density, and the majority of the power is consumed by drive wires. Therefore, in order to achieve a low latency and high bandwidth communication, network architects have make sure that their designs are "wire-efficient". To do this, the wires need to be kept as short as possible in order to limit latency and diameter. Furthermore, when architects are brainstorming ideas for their networks, they have to ensure the physical organization (the wires) matches the logical organization (function of the program) so that it produces the most efficient and optimized results.		As mentioned previously, a VLSI network is wire-limited; as a result: network complexity is limited by wire delay, the program's run speed is limited by wire density, and the majority of the power is consumed by drive wires. Therefore, in order to achieve a low latency and high bandwidth communication, network architects have make sure that their designs are "wire-efficient". To do this, the wires need to be kept as short as possible in order to limit latency and diameter. Furthermore, when architects are brainstorming ideas for their networks, they have to ensure the physical organization (the wires) matches the logical organization (function of the program) so that it produces the most efficient and optimized results.

	However, "networks have traditionally been analyzed under the assumption of constant channel bandwidth"<ref>Dally, William J. "Performance Analysis of k-ary n-cube Interconnection Networks." ''IEEE Transactions On Computers''. 39.6: (1990), 775-785. http://www.ai.mit.edu/projects/aries/papers/networks/k-ary_n-cube.pdf</ref>.		However, "networks have traditionally been analyzed under the assumption of constant channel bandwidth"[3].

	=='''Recent Studies'''==		=='''Recent Studies'''==

Mjtanner at 02:08, 26 April 2012

2012-04-26T02:08:03Z

← Older revision		Revision as of 02:08, 26 April 2012
Line 34:		Line 34:

	N = k^n		N = k^n
			*complexity limited by wire delay, speed limited by wire density, and majority of power consumed by drive wires.
			===The ''PROBLEM''===

	~~===The~~ '~~'PROBLEM''===~~		As mentioned previously, a VLSI network is wire-limited; as a result: network complexity is limited by wire delay, the program's run speed is limited by wire density, and the majority of the power is consumed by drive wires. Therefore, in order to achieve a low latency and high bandwidth communication, network architects have make sure that their designs are "wire-efficient". To do this, the wires need to be kept as short as possible in order to limit latency and diameter. Furthermore, when architects are brainstorming ideas for their networks, they have to ensure the physical organization (the wires) matches the logical organization (function of the program) so that it produces the most efficient and optimized results.

	~~In a VLSI network~~,		However, "networks have traditionally been analyzed under the assumption of constant channel bandwidth"<ref>Dally, William J. "Performance Analysis of k-ary n-cube Interconnection Networks." ''IEEE Transactions On Computers''. 39.6: (1990), 775-785. http://www.ai.mit.edu/projects/aries/papers/networks/k-ary_n-cube.pdf</ref>.

	=='''Recent Studies'''==		=='''Recent Studies'''==

Mjtanner at 01:54, 26 April 2012

2012-04-26T01:54:54Z

← Older revision		Revision as of 01:54, 26 April 2012
Line 105:		Line 105:

	<references></references>		<references></references>

			===See Also===

			http://expertiza.csc.ncsu.edu/wiki/index.php/CSC/ECE_506_Spring_2011/ch12

Mjtanner at 01:52, 26 April 2012

2012-04-26T01:52:47Z

← Older revision		Revision as of 01:52, 26 April 2012
Line 33:		Line 33:
	Also, many topologies were created and suggested to be used during this time, but the one used most frequently was the ''k''-ary ''n''-cube, where there were ''n'' dimensions and ''k'' nodes in each dimension. In fact, most parallel (or concurrent) computers at the time utilized either the ''k''-ary ''n''-cube topology or those similar to it (i.e. mesh, ring, omega network, etc.). The following is the formula that shows the relationship between ''k'', ''n'', and the number of nodes in the network (N):		Also, many topologies were created and suggested to be used during this time, but the one used most frequently was the ''k''-ary ''n''-cube, where there were ''n'' dimensions and ''k'' nodes in each dimension. In fact, most parallel (or concurrent) computers at the time utilized either the ''k''-ary ''n''-cube topology or those similar to it (i.e. mesh, ring, omega network, etc.). The following is the formula that shows the relationship between ''k'', ''n'', and the number of nodes in the network (N):

	N = k^n		N = k^n

	===The ''PROBLEM''===		===The ''PROBLEM''===

Mjtanner at 01:52, 26 April 2012

2012-04-26T01:52:28Z

← Older revision		Revision as of 01:52, 26 April 2012
Line 8:		Line 8:
	=='''Unpopular Topologies'''==		=='''Unpopular Topologies'''==

	Today, many in the parallel computer programming world have come to realize that depending on the type of task needed to be accomplished, certain interconnection networks are more useful than others. Furthermore, the networks that are most in favor today: use hundreds (if not thousands) of [http://expertiza.csc.ncsu.edu/wiki/index.php/CSC/ECE_506_Spring_2011/ch12#Types_of_Network_Topologies nodes], utilize [http://en.wikipedia.org/wiki/Crossbar_switch crossbar switches] and sub-switch buffers, adapting routing that avoids [http://expertiza.csc.ncsu.edu/wiki/index.php/CSC/ECE_506_Spring_2011/ch12#Deadlock deadlocks], etc. However, from the 1980s to the early 1990s, the mindset and the views on interconnection networks of programmers were different.		Today, many in the parallel computer programming world have come to realize that depending on the type of task needed to be accomplished, certain interconnection networks are more useful than others. Furthermore, the networks that are most in favor today: use hundreds (if not thousands) of [http://expertiza.csc.ncsu.edu/wiki/index.php/CSC/ECE_506_Spring_2011/ch12#Types_of_Network_Topologies nodes], utilize [http://en.wikipedia.org/wiki/Crossbar_switch crossbar switches] and sub-switch buffers, adapting routing that avoids [http://expertiza.csc.ncsu.edu/wiki/index.php/CSC/ECE_506_Spring_2011/ch12#Deadlock deadlocks], etc<ref>http://www.csm.ornl.gov/workshops/IAA-IC-Workshop-08/documents/wiki/dally_iaa_workshop_0708.pdf</ref>. However, from the 1980s to the early 1990s, the mindset and the views on interconnection networks of programmers were different.

	===Introduction to Interconnection Network Architecture===		===Introduction to Interconnection Network Architecture===
Line 29:		Line 29:
	===Brief History===		===Brief History===

	Ever since inter-processor interconnection technologies were first introduced in the 1960s, many interconnection topologies fads have come and gone. By the 1980s, the topologies that were in high favor were [http://en.wikipedia.org/wiki/VLSI VLSI] ('''V'''ery-'''L'''arge-'''S'''cale '''I'''ntegration) communication networks. VLSI systems are considered to be "wire-limited". "		Ever since inter-processor interconnection technologies were first introduced in the 1960s, many interconnection topologies fads have come and gone. By the 1980s, the topologies that were in high favor were [http://en.wikipedia.org/wiki/VLSI VLSI] ('''V'''ery-'''L'''arge-'''S'''cale '''I'''ntegration) communication networks. VLSI systems are considered to be "wire-limited". "The cost of these systems is predominately that of connecting devices, and the performance is limited by the delay of these interconnections. Thus...the network must make efficient use of the available wire"<ref>Dally, William J. "Performance Analysis of k-ary n-cube Interconnection Networks." ''IEEE Transactions On Computers''. 39.6: (1990), 775-785. http://www.ai.mit.edu/projects/aries/papers/networks/k-ary_n-cube.pdf</ref>.

			Also, many topologies were created and suggested to be used during this time, but the one used most frequently was the ''k''-ary ''n''-cube, where there were ''n'' dimensions and ''k'' nodes in each dimension. In fact, most parallel (or concurrent) computers at the time utilized either the ''k''-ary ''n''-cube topology or those similar to it (i.e. mesh, ring, omega network, etc.). The following is the formula that shows the relationship between ''k'', ''n'', and the number of nodes in the network (N):

			N = k^n

	===The ''PROBLEM''===		===The ''PROBLEM''===

			In a VLSI network,

	=='''Recent Studies'''==		=='''Recent Studies'''==
Line 42:		Line 47:
	====Background====		====Background====

	Among the recent developments of various multicomputing networks, the Hypercube (HC) has enjoyed the highest popularity due to many of its attractive properties: regularity, symmetry, small diameter, strong connectivity, recursive construction, ~~partitionability~~ and relatively small link complexity. Additionally, there have been several variations of the Hypercube, including (but not limited to) the Varietal Hypercube (VH) and Balanced Hypercube (BH). The VH has a lower degree, average distance, and cost when compared to several other versions of Hypercube like the Folded Hypercube, Twisted Hypercube, Crossed Hypercube, etc. On the other hand, the BH has proven to be better in terms of fault tolerance (which improves system reliability as the number of processors increase) compared to the regular Hypercube.		Among the recent developments of various multicomputing networks, the Hypercube (HC) has enjoyed the highest popularity due to many of its attractive properties: regularity, symmetry, small diameter, strong connectivity, recursive construction, partition ability, and relatively small link complexity. Additionally, there have been several variations of the Hypercube, including (but not limited to) the Varietal Hypercube (VH) and Balanced Hypercube (BH). The VH has a lower degree, average distance, and cost when compared to several other versions of Hypercube like the Folded Hypercube, Twisted Hypercube, Crossed Hypercube, etc. On the other hand, the BH has proven to be better in terms of fault tolerance (which improves system reliability as the number of processors increase) compared to the regular Hypercube.

	In interconnection network design, some of the most important performance parameters to consider are: communication efficiency, reliability, fault tolerance, and cost effectiveness. Thus, in order to meet the demands for such a network with a large number of processors, a new design that combined the basic structures of the VH and BH was designed known simply as the Balanced Varietal Hypercube (BVH). It "has got a reduced diameter, optimal average distance with less cost", and the inherited merits of fault tolerance from the BH. The following exhibits the BVH's topological properties for an n-dimensional BVH:		In interconnection network design, some of the most important performance parameters to consider are: communication efficiency, reliability, fault tolerance, and cost effectiveness. Thus, in order to meet the demands for such a network with a large number of processors, a new design that combined the basic structures of the VH and BH was designed known simply as the Balanced Varietal Hypercube (BVH). It "has got a reduced diameter, optimal average distance with less cost", and the inherited merits of fault tolerance from the BH. The following exhibits the BVH's topological properties for an n-dimensional BVH:
Line 63:		Line 68:
	===Omega Network===		===Omega Network===

	A crucial design attribute of a large network system is its reliability. When the system size grows, the probability of having all system nodes fault free during a given operation period falls quickly and could reach an unacceptable low point. It is, thus, necessary to incorporate redundancy into the system design to guarantee proper continuous operation even after the failure of some nodes.<ref>Bataineh, Sameer, and Ghassan E. Quanzu'a. "Reliable Omega Interconnected Network for Large-Scale Multiprocessor Systems." The Computer Journal. 46.5 (2003): 467-475. Print. http://comjnl.oxfordjournals.org/content/46/5/467.abstract</ref>		A crucial design attribute of a large network system is its reliability. When the system size grows, the probability of having all system nodes fault free during a given operation period falls quickly and could reach an unacceptable low point. It is, thus, necessary to "incorporate redundancy into the system design to guarantee proper continuous operation even after the failure of some nodes"<ref>Bataineh, Sameer, and Ghassan E. Quanzu'a. "Reliable Omega Interconnected Network for Large-Scale Multiprocessor Systems." The Computer Journal. 46.5 (2003): 467-475. Print. http://comjnl.oxfordjournals.org/content/46/5/467.abstract</ref>.

	====Background====		====Background====

Mjtanner at 01:29, 26 April 2012

2012-04-26T01:29:59Z

← Older revision		Revision as of 01:29, 26 April 2012
Line 29:		Line 29:
	===Brief History===		===Brief History===

	Ever since inter-processor interconnection technologies were first introduced in the 1960s, many interconnection topologies fads have come and gone. By the 1980s, the topologies that were in high favor were [http://en.wikipedia.org/wiki/VLSI VLSI] ('''V'''ery-'''L'''arge-'''S'''cale '''I'''ntegration)		Ever since inter-processor interconnection technologies were first introduced in the 1960s, many interconnection topologies fads have come and gone. By the 1980s, the topologies that were in high favor were [http://en.wikipedia.org/wiki/VLSI VLSI] ('''V'''ery-'''L'''arge-'''S'''cale '''I'''ntegration) communication networks. VLSI systems are considered to be "wire-limited". "


	===The ''PROBLEM''===		===The ''PROBLEM''===