CSC/ECE 506 Spring 2012/1c cl - Revision history

Cli8: /* Description */

2012-02-03T02:04:19Z

Description

← Older revision		Revision as of 02:04, 3 February 2012
Line 100:		Line 100:

	====Description====		====Description====
	A systolic array is composed of matrix-like rows of data processing units called cells. Data processing units (DPUs) are similar to central processing units (CPU)s, (except for the usual lack of a program counter,~~[1]~~ since operation is transport-triggered, i.e., by the arrival of a data object). Each cell shares the information with its neighbours immediately after processing. The systolic array is often rectangular where data flows across the array between neighbour DPUs, often with different data flowing in different directions. The data streams entering and leaving the ports of the array are generated by auto-sequencing memory units, ASMs. Each ASM includes a data counter. In embedded systems a data stream may also be input from and/or output to an external source.		A systolic array is composed of matrix-like rows of data processing units called cells. Data processing units (DPUs) are similar to central processing units (CPU)s, (except for the usual lack of a program counter, since operation is transport-triggered, i.e., by the arrival of a data object). Each cell shares the information with its neighbours immediately after processing. The systolic array is often rectangular where data flows across the array between neighbour DPUs, often with different data flowing in different directions. The data streams entering and leaving the ports of the array are generated by auto-sequencing memory units, ASMs. Each ASM includes a data counter. In embedded systems a data stream may also be input from and/or output to an external source.
	An example of a systolic algorithm might be designed for matrix multiplication. One matrix is fed in a row at a time from the top of the array and is passed down the array, the other matrix is fed in a column at a time from the left hand side of the array and passes from left to right. Dummy values are then passed in until each processor has seen one whole row and one whole column. At this point, the result of the multiplication is stored in the array and can now be output a row or a column at a time, flowing down or across the array.~~[2]~~
			An example of a systolic algorithm might be designed for matrix multiplication. One matrix is fed in a row at a time from the top of the array and is passed down the array, the other matrix is fed in a column at a time from the left hand side of the array and passes from left to right. Dummy values are then passed in until each processor has seen one whole row and one whole column. At this point, the result of the multiplication is stored in the array and can now be output a row or a column at a time, flowing down or across the array.

	Systolic arrays are arrays of DPUs which are connected to a small number of nearest neighbour DPUs in a mesh-like topology. DPUs perform a sequence of operations on data that flows between them. Because the traditional systolic array synthesis methods have been practiced by algebraic algorithms, only uniform arrays with only linear pipes can be obtained, so that the architectures are the same in all DPUs. The consequence is, that only applications with regular data dependencies can be implemented on classical systolic arrays. Like SIMD machines, clocked systolic arrays compute in "lock-step" with each processor undertaking alternate compute \| communicate phases. But systolic arrays with asynchronous handshake between DPUs are called wavefront arrays. One well-known systolic array is Carnegie Mellon University's iWarp processor, which has been manufactured by Intel. An iWarp system has a linear array processor connected by data buses going in both directions.		Systolic arrays are arrays of DPUs which are connected to a small number of nearest neighbour DPUs in a mesh-like topology. DPUs perform a sequence of operations on data that flows between them. Because the traditional systolic array synthesis methods have been practiced by algebraic algorithms, only uniform arrays with only linear pipes can be obtained, so that the architectures are the same in all DPUs. The consequence is, that only applications with regular data dependencies can be implemented on classical systolic arrays. Like SIMD machines, clocked systolic arrays compute in "lock-step" with each processor undertaking alternate compute \| communicate phases. But systolic arrays with asynchronous handshake between DPUs are called wavefront arrays. One well-known systolic array is Carnegie Mellon University's iWarp processor, which has been manufactured by Intel. An iWarp system has a linear array processor connected by data buses going in both directions.

Cli8: /* MISD Architecture Application */

2012-02-03T02:02:58Z

MISD Architecture Application

← Older revision		Revision as of 02:02, 3 February 2012
Line 91:		Line 91:

	Few actual examples of this class of parallel computer have ever existed. One example of this machine is the systolic array, such as the CMU iWarp[Borkaret al., 1990]. Another prominent example of MISD in computing are the Space Shuttle flight control computers. The research on MISD concentrates on some conceivable usage: Multiple frequency filters operating on a single signal stream, Multiple cryptography algorithms, and Attempting to crack a single coded message.		Few actual examples of this class of parallel computer have ever existed. One example of this machine is the systolic array, such as the CMU iWarp[Borkaret al., 1990]. Another prominent example of MISD in computing are the Space Shuttle flight control computers. The research on MISD concentrates on some conceivable usage: Multiple frequency filters operating on a single signal stream, Multiple cryptography algorithms, and Attempting to crack a single coded message.

			===Systolic Arrays<ref>http://en.wikipedia.org/wiki/Systolic_array</ref>===
			----------------------------------------------

			====Definition and History====
			In computer architecture, a systolic array is a pipe network arrangement of processing units called cells. It is a specialized form of parallel computing, where cells (i.e. processors), compute data and store it independently of each other. The systolic array paradigm, data-stream-driven by data counters, is the counterpart of the von Neumann paradigm, instruction-stream-driven by a program counter. Because a systolic array usually sends and receives multiple data streams, and multiple data counters are needed to generate these data streams, it supports data parallelism. The name derives from analogy with the regular pumping of blood by the heart.
			H. T. Kung and Charles E. Leiserson published the first paper describing systolic arrays in 1978; however, the first machine known to have used a similar technique was the Colossus Mark II in 1944.

			====Description====
			A systolic array is composed of matrix-like rows of data processing units called cells. Data processing units (DPUs) are similar to central processing units (CPU)s, (except for the usual lack of a program counter,[1] since operation is transport-triggered, i.e., by the arrival of a data object). Each cell shares the information with its neighbours immediately after processing. The systolic array is often rectangular where data flows across the array between neighbour DPUs, often with different data flowing in different directions. The data streams entering and leaving the ports of the array are generated by auto-sequencing memory units, ASMs. Each ASM includes a data counter. In embedded systems a data stream may also be input from and/or output to an external source.
			An example of a systolic algorithm might be designed for matrix multiplication. One matrix is fed in a row at a time from the top of the array and is passed down the array, the other matrix is fed in a column at a time from the left hand side of the array and passes from left to right. Dummy values are then passed in until each processor has seen one whole row and one whole column. At this point, the result of the multiplication is stored in the array and can now be output a row or a column at a time, flowing down or across the array.[2]
			Systolic arrays are arrays of DPUs which are connected to a small number of nearest neighbour DPUs in a mesh-like topology. DPUs perform a sequence of operations on data that flows between them. Because the traditional systolic array synthesis methods have been practiced by algebraic algorithms, only uniform arrays with only linear pipes can be obtained, so that the architectures are the same in all DPUs. The consequence is, that only applications with regular data dependencies can be implemented on classical systolic arrays. Like SIMD machines, clocked systolic arrays compute in "lock-step" with each processor undertaking alternate compute \| communicate phases. But systolic arrays with asynchronous handshake between DPUs are called wavefront arrays. One well-known systolic array is Carnegie Mellon University's iWarp processor, which has been manufactured by Intel. An iWarp system has a linear array processor connected by data buses going in both directions.

			====Super Systolic Array====
			The super systolic array is a generalization of the systolic array. Because the classical synthesis methods (algebraic, i. e. projection-based synthesis), yielding only uniform DPU arrays permitting only linear pipes, systolic arrays could be used only to implement applications with regular data dependencies. By using simulated annealing instead, Rainer Kress has introduced the generalized systolic array: the super systolic array. Its application is not restricted to applications with regular data dependencies.
			====applications on 2D Convolution <ref>http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=4142414</ref>====

			bit-level super-systolic array can be used for 2D convolution which needs 1-bit ports for each input or output sequence. In addition to the arrangement of delays for data flow synchrony, the super-systolic array in which the cell of systolic array is organized again as a systolic
			array is adopted to perform the bit-level data flow and operation on bit data. The derived Super-systolic array for 2D convolution is synthesized using Synopsys design compiler based on Hynix 0.35,um cell library and compared with conventional word-level systolic array for 2D convolution. The bit-level super-systolic design is very compact in that it needs only 1-bit ports for each I/O sequence instead of n-bit ports in word-level design besides the reduced area requirement without time penalty on the output.

Cli8: /* References */

2012-02-03T01:53:07Z

References

← Older revision		Revision as of 01:53, 3 February 2012
Line 125:		Line 125:

	<references />		<references />
	~~http://en.wikipedia.org/wiki/Multiprocessing~~

	~~http://www.itswtech.org/Lec/Manal%28system%20programming%29/simeners_A/Multiprocessing_System_Cimenar.pdf~~

	~~http://en.wikipedia.org/wiki/Parallel_computing~~

	~~http://en.wikipedia.org/wiki/Flynn%27s_taxonomy~~

	~~http://www.cse.unsw.edu.au/~cs4211/04s1/seminars/rompo.ppt~~

	~~http://www.cs.ucf.edu/courses/cot4810/fall04/presentations/Parallel_Computing.ppt~~

	~~http://www.codeproject.com/Articles/146414/Basics-of-Single-Instruction-Multiple-Data-SIMD~~

	~~https://computing.llnl.gov/tutorials/parallel_comp/~~

	~~http://wiki.cs.unm.edu/ssl/lib/exe/fetch.php/papers:bridges11exploiting.pdf~~

	~~http://www.cs.cmu.edu/~iwarp/~~

Cli8: /* Flynn's taxonomy for Instruction and Data Streamshttp://en.wikipedia.org/wiki/Flynn%27s_taxonomy */

2012-02-03T01:52:46Z

Flynn's taxonomy for Instruction and Data Streamshttp://en.wikipedia.org/wiki/Flynn%27s_taxonomy

← Older revision		Revision as of 01:52, 3 February 2012
Line 73:		Line 73:

	Multiple Instruction, Single Data stream (MISD)		Multiple Instruction, Single Data stream (MISD)
	Multiple instructions operate on a single data stream. Uncommon architecture which is generally used for fault tolerance. Heterogeneous systems operate on the same data stream and must agree on the result. Examples include the Space Shuttle flight control computer.		Multiple instructions operate on a single data stream. Uncommon architecture which is generally used for fault tolerance. Heterogeneous systems operate on the same data stream and must agree on the result. Examples include the Space Shuttle flight control computer.<ref>http://www.itswtech.org/Lec/Manal%28system%20programming%29/simeners_A/Multiprocessing_System_Cimenar.pdf</ref>

	Multiple Instruction, Multiple Data streams (MIMD)		Multiple Instruction, Multiple Data streams (MIMD)

Cli8: /* Processor coupling */

2012-02-03T01:51:36Z

Processor coupling

← Older revision		Revision as of 01:51, 3 February 2012
Line 48:		Line 48:
	Systems that treat all CPUs equally are called symmetric multiprocessing)SMP (systems .In systems where all CPUs are not equal, system resources may be divided in a number of ways, including asymmetric multiprocessing )ASMP(, non-uniform memory access)NUMA(multiprocessing, and clustered multiprocessing.		Systems that treat all CPUs equally are called symmetric multiprocessing)SMP (systems .In systems where all CPUs are not equal, system resources may be divided in a number of ways, including asymmetric multiprocessing )ASMP(, non-uniform memory access)NUMA(multiprocessing, and clustered multiprocessing.

	====Processor coupling====		====Processor coupling<ref>https://computing.llnl.gov/tutorials/parallel_comp/</ref>====
	-------------------------------------------		-------------------------------------------
	Tightly-coupled multiprocessor systems contain multiple CPUs that are connected at the bus level .These CPUs may have access to a central shared memory )SMP or UMA(, or may participate in a memory hierarchy with both local and shared memory )NUMA.(		Tightly-coupled multiprocessor systems contain multiple CPUs that are connected at the bus level .These CPUs may have access to a central shared memory )SMP or UMA(, or may participate in a memory hierarchy with both local and shared memory )NUMA.(

Cli8: /* Iwarp project by CMU */

2012-02-03T01:50:38Z

Iwarp project by CMU

← Older revision		Revision as of 01:50, 3 February 2012
Line 109:		Line 109:
	[[File:Cl5.jpg]]		[[File:Cl5.jpg]]

	===Iwarp project by CMU===		===Iwarp project by CMU<ref>http://www.cs.cmu.edu/~iwarp/</ref>===
	-------------------------------------------		-------------------------------------------
	The iWarp project was started in 1988 to investigate issues involved in building and using high performance computer systems with powerful communication support. The project lead to the construction of the iWarp machines, jointly developed by Carnegie Mellon University and Intel Corporation.		The iWarp project was started in 1988 to investigate issues involved in building and using high performance computer systems with powerful communication support. The project lead to the construction of the iWarp machines, jointly developed by Carnegie Mellon University and Intel Corporation.

Cli8: /* MISD multiprocessing */

2012-02-03T01:49:53Z

MISD multiprocessing

← Older revision		Revision as of 01:49, 3 February 2012
Line 78:		Line 78:
	Multiple autonomous processors simultaneously executing different instructions on different data. Distributed systems are generally recognized to be MIMD architectures; either exploiting a single shared memory space or a distributed memory space.		Multiple autonomous processors simultaneously executing different instructions on different data. Distributed systems are generally recognized to be MIMD architectures; either exploiting a single shared memory space or a distributed memory space.

	====MISD multiprocessing ====		====MISD multiprocessing <ref>http://en.wikipedia.org/wiki/MISD</ref>====
	-------------------------------------------		-------------------------------------------
	[[File:Cl51.jpg]]		[[File:Cl51.jpg]]

Cli8: /* Processor couplinghttp://en.wikipedia.org/wiki/Multiprocessing */

2012-02-03T01:49:19Z

Processor couplinghttp://en.wikipedia.org/wiki/Multiprocessing

← Older revision		Revision as of 01:49, 3 February 2012
Line 48:		Line 48:
	Systems that treat all CPUs equally are called symmetric multiprocessing)SMP (systems .In systems where all CPUs are not equal, system resources may be divided in a number of ways, including asymmetric multiprocessing )ASMP(, non-uniform memory access)NUMA(multiprocessing, and clustered multiprocessing.		Systems that treat all CPUs equally are called symmetric multiprocessing)SMP (systems .In systems where all CPUs are not equal, system resources may be divided in a number of ways, including asymmetric multiprocessing )ASMP(, non-uniform memory access)NUMA(multiprocessing, and clustered multiprocessing.

	====Processor coupling~~<ref>http://en.wikipedia.org/wiki/Multiprocessing</ref>~~====		====Processor coupling====
	-------------------------------------------		-------------------------------------------
	Tightly-coupled multiprocessor systems contain multiple CPUs that are connected at the bus level .These CPUs may have access to a central shared memory )SMP or UMA(, or may participate in a memory hierarchy with both local and shared memory )NUMA.(		Tightly-coupled multiprocessor systems contain multiple CPUs that are connected at the bus level .These CPUs may have access to a central shared memory )SMP or UMA(, or may participate in a memory hierarchy with both local and shared memory )NUMA.(

Cli8: /* References */

2012-02-03T01:48:14Z

References

← Older revision		Revision as of 01:48, 3 February 2012
Line 123:		Line 123:

	==References==		==References==

			<references />
	http://en.wikipedia.org/wiki/Multiprocessing		http://en.wikipedia.org/wiki/Multiprocessing

Cli8: /* Introduction to MISD */

2012-02-03T01:46:10Z

Introduction to MISD

← Older revision		Revision as of 01:46, 3 February 2012
Line 1:		Line 1:
	==Introduction to MISD==		==Introduction to MISD==

	In computing, MISD (multiple instruction, single data) is a type of parallel computing architecture in which multiple processing elements execute from different instruction streams, and data is passed from one processing element to the next. The requirement that data is passed from one processing element to the next means that it is restricted to a certain type of computations, but is hard to apply in general. There are some bottle neck of MISD architecture<ref>http://www.cse.unsw.edu.au/~cs4211/04s1/seminars/rompo.ppt<\ref>:		In computing, MISD (multiple instruction, single data) is a type of parallel computing architecture in which multiple processing elements execute from different instruction streams, and data is passed from one processing element to the next. The requirement that data is passed from one processing element to the next means that it is restricted to a certain type of computations, but is hard to apply in general. There are some bottle neck of MISD architecture<ref>http://www.cse.unsw.edu.au/~cs4211/04s1/seminars/rompo.ppt</ref>:

	1, Low level of parallelism ; 2, High synchronizations; 3, High bandwidth required ; 4, CISC bottleneck ; 5, High complexity		1, Low level of parallelism ; 2, High synchronizations; 3, High bandwidth required ; 4, CISC bottleneck ; 5, High complexity