CSC/ECE 506 Spring 2011/ch2 dm - Revision history

Dmcarmon: Edited due to feedback

2011-04-11T22:04:41Z

Edited due to feedback

Dmcarmon: /* Connection Machines */

2011-04-02T03:42:17Z

Connection Machines

← Older revision		Revision as of 03:42, 2 April 2011
Line 136:		Line 136:
	==Connection Machines==		==Connection Machines==

	[http://longnow.org/essays/richard-feynman-connection-machine/ The connection machine] was data parallel ~~machines~~ built in the 1980s. A connection machine had on the order of 64,000 processors. Each processor computed one bit of data and was connected to others via hyper-cube wiring. [http://www.mission-base.com/tamiko/cm/index.html Tamiko Thiel] describes the machine as being modeled after a human brain. The second connection machine (CM-2) which had more RAM and included floating point adders [http://en.wikipedia.org/wiki/Connection_Machine] came out in 1987, and two smaller editions, the CM-2a and the CM-200, were developed later.		[http://longnow.org/essays/richard-feynman-connection-machine/ The connection machine] was a data parallel machine built in the 1980s. A connection machine had on the order of 64,000 processors. Each processor computed one bit of data and was connected to others via hyper-cube wiring. [http://www.mission-base.com/tamiko/cm/index.html Tamiko Thiel] describes the machine as being modeled after a human brain. The second connection machine (CM-2) which had more RAM and included floating point adders [http://en.wikipedia.org/wiki/Connection_Machine] came out in 1987, and two smaller editions, the CM-2a and the CM-200, were developed later.

	==Distributed Memory and Message Passing==		==Distributed Memory and Message Passing==

Dmcarmon: Added connection machines section

2011-04-02T03:41:21Z

Added connection machines section

← Older revision		Revision as of 03:41, 2 April 2011
Line 133:		Line 133:

	Many of these early machines were shared memory machines. This is likely because memory was very expensive and message passing requires multiple copies of data.		Many of these early machines were shared memory machines. This is likely because memory was very expensive and message passing requires multiple copies of data.

			==Connection Machines==

			[http://longnow.org/essays/richard-feynman-connection-machine/ The connection machine] was data parallel machines built in the 1980s. A connection machine had on the order of 64,000 processors. Each processor computed one bit of data and was connected to others via hyper-cube wiring. [http://www.mission-base.com/tamiko/cm/index.html Tamiko Thiel] describes the machine as being modeled after a human brain. The second connection machine (CM-2) which had more RAM and included floating point adders [http://en.wikipedia.org/wiki/Connection_Machine] came out in 1987, and two smaller editions, the CM-2a and the CM-200, were developed later.

	==Distributed Memory and Message Passing==		==Distributed Memory and Message Passing==
Line 146:		Line 150:
	=Summary=		=Summary=

	Through the history of parallel computing we may observe the tradeoffs between the shared memory and message passing models. In the beginning, due to parallel programming being done for the most part exclusively on expensive and custom-made super computers, shared memory systems made sense. Later on, the invention of the personal computer and wider availability of smaller and less expensive computers led more people to a message passing approach. ~~Since cluster computers rely on message passing between separate processors~~, ~~cluster computing~~ has ~~supported the move toward the~~ message passing ~~model. Although the~~ models may be combined into hybrid approaches, the two models are fundamentally different ways of addressing the same problem (of access control to common data). In contrast, the data parallel model is concerned with a fundamentally different problem (how to divide work into parallel tasks). As such, the data parallel model may be used in conjunction with either the shared memory or the message passing model without conflict. In fact, [[#References \| Klaiber (1994)]] compares the performance of a number of data parallel programs implemented with both shared memory and message passing models.		Through the history of parallel computing we may observe the tradeoffs between the shared memory and message passing models. In the beginning, due to parallel programming being done for the most part exclusively on expensive and custom-made super computers, shared memory systems made sense. Later on, the invention of the personal computer and wider availability of smaller and less expensive computers led more people to a message passing approach. Most recently, data parallelism has been done with GPUs. Although shared-memory and message-passing models may be combined into hybrid approaches, the two models are fundamentally different ways of addressing the same problem (of access control to common data). In contrast, the data parallel model is concerned with a fundamentally different problem (how to divide work into parallel tasks). As such, the data parallel model may be used in conjunction with either the shared memory or the message passing model without conflict. In fact, [[#References \| Klaiber (1994)]] compares the performance of a number of data parallel programs implemented with both shared memory and message passing models.

	One of the major advantages of combining the data parallel and message passing models is a reduction in the amount and complexity of communication required relative to a task parallel approach. Similarly, combining the data parallel and shared memory models tends to simplify and reduce the amount of synchronization required. If the task parallel code given in the appendix were modified from a message passing model to a shared memory model, the two threads would require 8 signals be sent between the threads (instead of 8 messages). In contrast, the data parallel code would require a single barrier before the local sums are added to compute the full sum.		One of the major advantages of combining the data parallel and message passing models is a reduction in the amount and complexity of communication required relative to a task parallel approach. Similarly, combining the data parallel and shared memory models tends to simplify and reduce the amount of synchronization required. If the task parallel code given in the appendix were modified from a message passing model to a shared memory model, the two threads would require 8 signals be sent between the threads (instead of 8 messages). In contrast, the data parallel code would require a single barrier before the local sums are added to compute the full sum.

Dmcarmon: /* Vector Machines */ updated cray computers

2011-04-02T02:47:33Z

Vector Machines: updated cray computers

← Older revision		Revision as of 02:47, 2 April 2011
Line 127:		Line 127:
	Solomon was unsuccessful and was cancelled, eventually to be reborn as the [http://research.microsoft.com/en-us/um/people/gbell/computer_structures__readings_and_examples/00000340.htm ILLIAC IV] at the University of Illinois. The ILLIAC IV showed great success at solving data-intensive problems, peaking at 150 MFLOPS under the right conditions.		Solomon was unsuccessful and was cancelled, eventually to be reborn as the [http://research.microsoft.com/en-us/um/people/gbell/computer_structures__readings_and_examples/00000340.htm ILLIAC IV] at the University of Illinois. The ILLIAC IV showed great success at solving data-intensive problems, peaking at 150 MFLOPS under the right conditions.

	Also, [http://research.microsoft.com/en-us/um/people/gbell/CGB%20Files/Cmmp%20Multi-Mini-Processor%20ComConference%201972%20c.pdf C.mmp] came out in 1971 and was actually a multiple instruction multiple data values (MIMD) archetecture. It was composed of 16 PDP-11 minicomputers and had a 16x16 crossbar switch between the processors and 16 banks of shared memory.		An innovation came with the [http://en.wikipedia.org/w/index.php?title=Cray-1&oldid=409177730 Cray-1] supercomputer in 1976. The innovation stemmed from the fact that the large data sets are often manipulated by several instructions back-to-back, such as an addition followed by a multiplication. The instruction pipeline of the Cray-1 was tweaked to take advantage of this. In the ILLIAC, up to 64 data points were loaded from memory with every instruction, but had to be stored back to manipulate the rest of the vector. The Cray computer was only able to load 12 data points, but by completing multiple instructions before continuing the total number of memory accesses decreased.
			In addition, the Cray-1 could perform at 240 MFLOPS. There continued to be new editions of Cray computers, the[http://en.wikipedia.org/wiki/Cray-2, Cray-2], [http://en.wikipedia.org/wiki/Cray-3 Cray-3] etc. One of the most recent versions, [http://en.wikipedia.org/wiki/Cray-YMP Cray Y-MP], was sold from 1988 and used a MIMD architecture.
	An innovation came with the [http://en.wikipedia.org/w/index.php?title=Cray-1&oldid=409177730 Cray-1] supercomputer in 1976. ~~It was realized~~ that the large data sets are often manipulated by several instructions back-to-back, such as an addition followed by a multiplication. In the ILLIAC, up to 64 data points were loaded from memory with every instruction, but had to be stored back to manipulate the rest of the vector. The Cray computer was only able to load 12 data points, but by completing multiple instructions before continuing the total number of memory accesses decreased.
	~~The~~ Cray-1 could perform at 240 MFLOPS.

	One of the later vector machines was the [http://www.museumwaalsdorp.nl/computer/en/comp891E.html ETA10]. It had shared memory 4M words and common memory 8M words, where each word was 64 bits. It was clocked at 24ns, but had a theorectical peak speed of 146 Mflops.		One of the later vector machines was the [http://www.museumwaalsdorp.nl/computer/en/comp891E.html ETA10]. It had shared memory 4M words and common memory 8M words, where each word was 64 bits. It was clocked at 24ns, but had a theorectical peak speed of 146 Mflops.

	Many of these early machines were shared memory machines. This is likely because memory was very expensive and message passing requires multiple copies of data~~. However, in the eighties cluster computing began to emerge, and popularized the message passing model~~.		Many of these early machines were shared memory machines. This is likely because memory was very expensive and message passing requires multiple copies of data.

	==Distributed Memory and Message Passing==		==Distributed Memory and Message Passing==

Dmcarmon: edited references

2011-04-02T01:53:35Z

edited references

← Older revision		Revision as of 01:53, 2 April 2011
Line 135:		Line 135:

	Many of these early machines were shared memory machines. This is likely because memory was very expensive and message passing requires multiple copies of data. However, in the eighties cluster computing began to emerge, and popularized the message passing model.		Many of these early machines were shared memory machines. This is likely because memory was very expensive and message passing requires multiple copies of data. However, in the eighties cluster computing began to emerge, and popularized the message passing model.

	~~==Recent Data Parallel Computing==~~

	Today most commonly data parallelism is done in GPUs, due to the nature of graphics computation. Because GPUs often share memory with the main computer processor and other elements, these most commonly have a [http://en.wikipedia.org/wiki/Shared_Memory_Architecture shared memory architecture]. The supplement for [http://pg-server.csc.ncsu.edu/mediawiki/index.php/CSC/ECE_506_Spring_2011/ch2a_mc chapter 2a] discusses GPUs in depth.

	==Distributed Memory and Message Passing==		==Distributed Memory and Message Passing==
Line 145:		Line 141:

	Each transputer processor could communicate with up to four other processors at up to 20 Mbps. Any number of processors could be combined into a massive processing farm. Of course, in large nets, the delay would be too great for any significant message passing.		Each transputer processor could communicate with up to four other processors at up to 20 Mbps. Any number of processors could be combined into a massive processing farm. Of course, in large nets, the delay would be too great for any significant message passing.

			==Recent Data Parallel Computing==

			Today data parallelism is most commonly done in GPUs, due to the nature of graphics computation. Because GPUs often share memory with the main computer processor and other elements, they most commonly have a [http://en.wikipedia.org/wiki/Shared_Memory_Architecture shared memory architecture]. The supplement for [http://pg-server.csc.ncsu.edu/mediawiki/index.php/CSC/ECE_506_Spring_2011/ch2a_mc chapter 2a] discusses GPUs in depth.

	=Summary=		=Summary=
Line 195:		Line 195:

	* ''C.mmp - A multi-mini-processor'', W. A. Wulf and C. G. Bell, C-MU 1972 http://research.microsoft.com/en-us/um/people/gbell/CGB%20Files/Cmmp%20Multi-Mini-Processor%20ComConference%201972%20c.pdf		* ''C.mmp - A multi-mini-processor'', W. A. Wulf and C. G. Bell, C-MU 1972 http://research.microsoft.com/en-us/um/people/gbell/CGB%20Files/Cmmp%20Multi-Mini-Processor%20ComConference%201972%20c.pdf

			* [http://pg-server.csc.ncsu.edu/mediawiki/index.php/CSC/ECE_506_Spring_2011/ch2a_mc CSC/ECE_506_Spring_2011/ch2a_mc]

	* David E. Culler, Jaswinder Pal Singh, and Anoop Gupta, ''Parallel Computer Architecture: A Hardware/Software Approach'', Gulf Professional Publishing, August 1998.		* David E. Culler, Jaswinder Pal Singh, and Anoop Gupta, ''Parallel Computer Architecture: A Hardware/Software Approach'', Gulf Professional Publishing, August 1998.
Line 230:		Line 232:

	* Wikipedia, MIMD [http://en.wikipedia.org/wiki/MIMD http://en.wikipedia.org/wiki/MIMD].		* Wikipedia, MIMD [http://en.wikipedia.org/wiki/MIMD http://en.wikipedia.org/wiki/MIMD].

			* Wikipedia, Shared Memory Architecture [http://en.wikipedia.org/wiki/Shared_Memory_Architecture]

	* Wikipedia, SIMD [http://en.wikipedia.org/wiki/SIMD http://en.wikipedia.org/wiki/SIMD].		* Wikipedia, SIMD [http://en.wikipedia.org/wiki/SIMD http://en.wikipedia.org/wiki/SIMD].

Dmcarmon: created subsection "Recent Data Parallel Computing"

2011-04-02T01:48:47Z

created subsection "Recent Data Parallel Computing"

← Older revision		Revision as of 01:48, 2 April 2011
Line 136:		Line 136:
	Many of these early machines were shared memory machines. This is likely because memory was very expensive and message passing requires multiple copies of data. However, in the eighties cluster computing began to emerge, and popularized the message passing model.		Many of these early machines were shared memory machines. This is likely because memory was very expensive and message passing requires multiple copies of data. However, in the eighties cluster computing began to emerge, and popularized the message passing model.

	==~~Cluster~~ Computing==		==Recent Data Parallel Computing==

	~~The introduction~~ of the ~~personal~~ computer ~~in 1981 by IBM made smaller, cheaper computers were more available~~ and ~~fueled the cluster computing growth. For companies that couldn't afford to purchase a supercomputer~~, ~~connecting many small computers to create~~ a [http://en.wikipedia.org/wiki/~~Computer_cluster computer cluster~~] ~~may have been a more feasible solution when they needed more computing power~~. ~~This setup uses the message passing model.~~		Today most commonly data parallelism is done in GPUs, due to the nature of graphics computation. Because GPUs often share memory with the main computer processor and other elements, these most commonly have a [http://en.wikipedia.org/wiki/Shared_Memory_Architecture shared memory architecture]. The supplement for [http://pg-server.csc.ncsu.edu/mediawiki/index.php/CSC/ECE_506_Spring_2011/ch2a_mc chapter 2a] discusses GPUs in depth.

	~~Furthermore, the internet was being developed and the one of the first cluster systems,~~ [http://en.~~wikipedia~~.~~org~~/~~wiki~~/~~VMScluster VMScluster~~] ~~(then known as VACcluster), was released in 1983. Pivotal~~ in ~~the development of cluster computing was the Parallel Virtual Machine (PVM). PVM allowed you to create a computer cluster with any machine that implementedf TCP/IP communication~~.

	==Distributed Memory and Message Passing==		==Distributed Memory and Message Passing==

Dmcarmon at 01:35, 2 April 2011

2011-04-02T01:35:13Z

← Older revision		Revision as of 01:35, 2 April 2011
Line 121:		Line 121:
	==Vector Machines==		==Vector Machines==

	First appearing in the late 1960s ~~[http://research.microsoft.com/en-us/um/people/gbell/computer_structures__readings_and_examples/00000340.htm (for example the ILLIAC IV)]~~, [http://en.wikipedia.org/wiki/Vector_processor vector machines] were able to apply a single instruction to multiple data values. This type of operation is used frequently in scientific fields or in multimedia.		First appearing in the late 1960s, [http://en.wikipedia.org/wiki/Vector_processor vector machines] were able to apply a single instruction to multiple data values. This type of operation is used frequently in scientific fields or in multimedia.

	The Solomon project at Westinghouse was one of the first machines to use vector operations.		The Solomon project at Westinghouse was one of the first machines to use vector operations.
	It's CPU had a large number of ALUs that would each be fed different data each cycle.		It's CPU had a large number of ALUs that would each be fed different data each cycle.
	Solomon was unsuccessful and was cancelled, eventually to be reborn as the ILLIAC IV at the University of Illinois. The ILLIAC IV showed great success at solving data-intensive problems, peaking at 150 MFLOPS under the right conditions.		Solomon was unsuccessful and was cancelled, eventually to be reborn as the [http://research.microsoft.com/en-us/um/people/gbell/computer_structures__readings_and_examples/00000340.htm ILLIAC IV] at the University of Illinois. The ILLIAC IV showed great success at solving data-intensive problems, peaking at 150 MFLOPS under the right conditions.

	Also, [http://research.microsoft.com/en-us/um/people/gbell/CGB%20Files/Cmmp%20Multi-Mini-Processor%20ComConference%201972%20c.pdf C.mmp] came out in 1971 and was actually a multiple instruction multiple data values (MIMD) archetecture. It was composed of 16 PDP-11 minicomputers and had a 16x16 crossbar switch between the processors and 16 banks of shared memory.		Also, [http://research.microsoft.com/en-us/um/people/gbell/CGB%20Files/Cmmp%20Multi-Mini-Processor%20ComConference%201972%20c.pdf C.mmp] came out in 1971 and was actually a multiple instruction multiple data values (MIMD) archetecture. It was composed of 16 PDP-11 minicomputers and had a 16x16 crossbar switch between the processors and 16 banks of shared memory.

Dmcarmon: ILLIAC IV paper from 1968

2011-04-02T01:32:50Z

ILLIAC IV paper from 1968

← Older revision		Revision as of 01:32, 2 April 2011
Line 121:		Line 121:
	==Vector Machines==		==Vector Machines==

	First appearing in the ~~1970s~~, [http://en.wikipedia.org/wiki/Vector_processor vector machines] were able to apply a single instruction to multiple data values. This type of operation is used frequently in scientific fields or in multimedia.		First appearing in the late 1960s [http://research.microsoft.com/en-us/um/people/gbell/computer_structures__readings_and_examples/00000340.htm (for example the ILLIAC IV)], [http://en.wikipedia.org/wiki/Vector_processor vector machines] were able to apply a single instruction to multiple data values. This type of operation is used frequently in scientific fields or in multimedia.

	The Solomon project at Westinghouse was one of the first machines to use vector operations.		The Solomon project at Westinghouse was one of the first machines to use vector operations.
Line 191:		Line 191:
	* Alexander C. Klaiber and Henry M. Levy, [http://portal.acm.org/citation.cfm?id=192020 "A comparison of message passing and shared memory architectures for data parallel programs,"] in ''Proceedings of the 21st Annual International Symposium on Computer Architecture,'' April 1994, pp. 94-105.		* Alexander C. Klaiber and Henry M. Levy, [http://portal.acm.org/citation.cfm?id=192020 "A comparison of message passing and shared memory architectures for data parallel programs,"] in ''Proceedings of the 21st Annual International Symposium on Computer Architecture,'' April 1994, pp. 94-105.

			* Barnes et al., [http://research.microsoft.com/en-us/um/people/gbell/computer_structures__readings_and_examples/00000340.htm The ILLIAC IV Computer]
	* Björn Lisper, ''Data parallelism and functional programming'', Lecture Notes in Computer Science, Volume 1132/1996, pp. 220-251, Springer Berlin, 1996.		* Björn Lisper, ''Data parallelism and functional programming'', Lecture Notes in Computer Science, Volume 1132/1996, pp. 220-251, Springer Berlin, 1996.

Dmcarmon: Copied content from prev. page

2011-04-02T01:14:09Z

Copied content from prev. page

Show changes

Dmcarmon at 01:06, 2 April 2011

2011-04-02T01:06:30Z

New page

Under construction