CSC/ECE 506 Spring 2015/3b az - Revision history

Zctaylor: /* Map Reduce on Graphics Processors */

2015-02-17T04:01:55Z

Map Reduce on Graphics Processors

← Older revision		Revision as of 04:01, 17 February 2015
Line 271:		Line 271:
	# The core tasks of MapReduce programs, including string processing, file manipulation and concurrent reads and writes, are unconventional to GPUs and must be handled efficiently.		# The core tasks of MapReduce programs, including string processing, file manipulation and concurrent reads and writes, are unconventional to GPUs and must be handled efficiently.

	'''''Mars''''', MapReduce framework on the GPU was designed and implemented with these challenges in mind.<ref>http://www.cse.ust.hk/~~gpuqp~~/~~Mars~~.~~html~~ Mars: A MapReduce Framework on ~~Graphic~~ Processors</ref>		'''''Mars''''', MapReduce framework on the GPU was designed and implemented with these challenges in mind.<ref>Bingsheng He, Wenbin Fang, Qiong Luo, Naga K. Govindaraju, and Tuyong Wang. [http://www.cse.ust.hk/catalac/papers/mars_pact08.pdf Mars: A MapReduce Framework on Graphics Processors.] PACT 2008.</ref>

	=== Current MapReduce Implementations for GPU ===		=== Current MapReduce Implementations for GPU ===
Line 281:		Line 281:
	# [https://code.google.com/p/mapcg/source/browse/trunk/README MapCG]		# [https://code.google.com/p/mapcg/source/browse/trunk/README MapCG]

	=== Mars API ===		==== Mars API ====

	Mars provides a small set of [http://en.wikipedia.org/wiki/API/ API]s that are similar to those of CPU-based MapReduce. Run-time system utilizes a large number of GPU threads for Map or Reduce tasks, and automatically assigns each thread a small number of key/value pairs to work on. As a result, the massive thread parallelism on the GPU is well utilized. To avoid any conflict between concurrent writes, Mars has a lock-free scheme with low runtime overhead on the massive thread parallelism of the GPU. This scheme guarantees the correctness of parallel execution with little synchronization overhead.		Mars provides a small set of [http://en.wikipedia.org/wiki/API/ API]s that are similar to those of CPU-based MapReduce. Run-time system utilizes a large number of GPU threads for Map or Reduce tasks, and automatically assigns each thread a small number of key/value pairs to work on. As a result, the massive thread parallelism on the GPU is well utilized. To avoid any conflict between concurrent writes, Mars has a lock-free scheme with low runtime overhead on the massive thread parallelism of the GPU. This scheme guarantees the correctness of parallel execution with little synchronization overhead.

Zctaylor: /* MapReduce-MPI */

2015-02-17T03:56:34Z

MapReduce-MPI

← Older revision		Revision as of 03:56, 17 February 2015
Line 238:		Line 238:
	====MapReduce-MPI====		====MapReduce-MPI====

	MapReduce-MPI is an implementation of MapReduce on top of standardized MPI. <ref>http://en.wikipedia.org/wiki/Message_Passing_Interface</ref> Unlike other implementations of MapReduce which are mostly in Java, MapReduce-MPI is implemented in C++. The major downfall of this implementation is a lack of fault tolerance. The implementations MPI library does not detect machines that are no longer part of the cluster very well.<ref>http://mapreduce.sandia.gov/doc/Background.html</ref>		MapReduce-MPI is an implementation of MapReduce on top of standardized MPI<ref>Message Passing Interface wiki (2015). In Wikipedia. Retrieved February 16, 2015, from http://en.wikipedia.org/wiki/Message_Passing_Interface</ref>. Unlike other implementations of MapReduce which are mostly in Java, MapReduce-MPI is implemented in C++. The major downfall of this implementation is a lack of fault tolerance. The implementations MPI library does not detect machines that are no longer part of the cluster very well.<ref>MapReduce-MPI Documentation Background. Retrieved from http://mapreduce.sandia.gov/doc/Background.html</ref>

	'''Example MR-MPI code''' <ref>http://mapreduce.sandia.gov/doc/Program.html</ref>		'''Example MR-MPI code''' <ref>MapReduce-MPI Documentation Program. Retrieved from http://mapreduce.sandia.gov/doc/Program.html</ref>
	<pre>		<pre>
	MapReduce *mr = new MapReduce(MPI_COMM_WORLD); // instantiate an MR object		MapReduce *mr = new MapReduce(MPI_COMM_WORLD); // instantiate an MR object

Zctaylor: /* Pros and Cons */

2015-02-17T03:51:16Z

Pros and Cons

← Older revision		Revision as of 03:51, 17 February 2015
Line 217:		Line 217:
	# On clusters of machines, the combiner function reduces the number of key-value pairs that must be exchanged between machines. These combiners contribute to better data locality and lower memory allocation pressure, resulting in substantial number of applications being scalable.		# On clusters of machines, the combiner function reduces the number of key-value pairs that must be exchanged between machines. These combiners contribute to better data locality and lower memory allocation pressure, resulting in substantial number of applications being scalable.

	* '''Disadvantages'''<ref>http://csl.stanford.edu/~christos/publications/2011.phoenixplus.mapreduce.pdf ~~Phoenix++: Modular MapReduce for Shared Memory Systems~~</ref>		* '''Disadvantages'''<ref>Justin Talbot, Richard M. Yoo, Christos Kozyrakis (2011). Phoenix++: Modular MapReduce for
			Shared-Memory Systems. Retrieved from http://csl.stanford.edu/~christos/publications/2011.phoenixplus.mapreduce.pdf</ref>

	# Due to shared memory there is an inefficient key-Value storage since containers must provide fast lookup and retrieval over potentially large data-set, all the while coordinating accesses across multiple threads		# Due to shared memory there is an inefficient key-Value storage since containers must provide fast lookup and retrieval over potentially large data-set, all the while coordinating accesses across multiple threads

Zctaylor: /* Map Reduce for Shared Memory Systems */

2015-02-17T03:49:39Z

Map Reduce for Shared Memory Systems

← Older revision		Revision as of 03:49, 17 February 2015
Line 180:		Line 180:
	# [http://csl.stanford.edu/~christos/sw/phoenix/ Phoenix++]		# [http://csl.stanford.edu/~christos/sw/phoenix/ Phoenix++]

	=== Metis ===		==== Metis ====

	Designed by MIT to achieve better performance than Phoenix by "using better data structures for grouping the key/value pairs generated by Map and consumed by Reduce"<ref name="metis">Yandong Mao, Robert Morris, and Frans Kaashoek. [http://pdos.csail.mit.edu/papers/metis:mittr10.pdf Optimizing MapReduce for Multicore Architectures]. Technical Report MIT-CSAIL-TR-2010-020, MIT, 2010.</ref>. The Metis library uses a hash table with a b+tree as each entry. The common case can uses a hash lookup for an O(1) operation cost. For unexpected key workloads, the performance would fall back on to the b+tree to achieve O(log N) operation costs. The performance of Metis greatly surpasses Phoenix in almost every area except in the case where the programs spend the majority of their time in application code. For more performance benchmarks please see the reference <ref name="metis"/>.		Designed by MIT to achieve better performance than Phoenix by "using better data structures for grouping the key/value pairs generated by Map and consumed by Reduce"<ref name="metis">Yandong Mao, Robert Morris, and Frans Kaashoek. [http://pdos.csail.mit.edu/papers/metis:mittr10.pdf Optimizing MapReduce for Multicore Architectures]. Technical Report MIT-CSAIL-TR-2010-020, MIT, 2010.</ref>. The Metis library uses a hash table with a b+tree as each entry. The common case can uses a hash lookup for an O(1) operation cost. For unexpected key workloads, the performance would fall back on to the b+tree to achieve O(log N) operation costs. The performance of Metis greatly surpasses Phoenix in almost every area except in the case where the programs spend the majority of their time in application code. For more performance benchmarks please see the reference <ref name="metis"/>.

	=== Phoenix API ===		==== Phoenix API ====
	Phoenix <ref>Colby Ranger, Ramanan Raghuraman, Arun Penmetsa, Gary Bradski, Christos Kozyrakis (2007). Evaluating MapReduce for Multi-core and Multiprocessor Systems. Retrieved from http://csl.stanford.edu/~christos/publications/2007.cmp_mapreduce.hpca.pdf</ref>implements MapReduce for shared-memory systems. Its goal is to support efficient execution on multiple cores without burdening the programmer with concurrency management. Phoenix consists of a simple API that is visible to application programmers and an efficient runtime that handles parallelization, resource management, and fault recovery.		Phoenix <ref>Colby Ranger, Ramanan Raghuraman, Arun Penmetsa, Gary Bradski, Christos Kozyrakis (2007). Evaluating MapReduce for Multi-core and Multiprocessor Systems. Retrieved from http://csl.stanford.edu/~christos/publications/2007.cmp_mapreduce.hpca.pdf</ref>implements MapReduce for shared-memory systems. Its goal is to support efficient execution on multiple cores without burdening the programmer with concurrency management. Phoenix consists of a simple API that is visible to application programmers and an efficient runtime that handles parallelization, resource management, and fault recovery.

Line 208:		Line 208:
	'''Reduce''' tasks are also assigned to workers dynamically, similar to Map tasks. The one difference is that, while with Map tasks there is complete freedom in distributing pairs across tasks, with Reduce all values for the same key must be processed in one task. Hence, the Reduce stage may exhibit higher imbalance across workers and dynamic scheduling is more important. The output of each Reduce task is already sorted by key. As the last step, the final output from all tasks is merged into a single buffer, sorted by keys.		'''Reduce''' tasks are also assigned to workers dynamically, similar to Map tasks. The one difference is that, while with Map tasks there is complete freedom in distributing pairs across tasks, with Reduce all values for the same key must be processed in one task. Hence, the Reduce stage may exhibit higher imbalance across workers and dynamic scheduling is more important. The output of each Reduce task is already sorted by key. As the last step, the final output from all tasks is merged into a single buffer, sorted by keys.

	==== Buffer Management ====		===== Buffer Management =====
	Two types of temporary buffers are necessary to store data between the various stages. All buffers are allocated in shared memory but are accessed in a well specified way by a few functions. To re-arrange buffers (e.g., split across tasks), pointer manipulation is done instead of the actual pairs, which may be large in size. The intermediate buffers are not directly visible to user code. Map-Reduce buffers are used to store the intermediate output pairs. Each worker has its own set of buffers. The buffers are initially sized to a default value and then resized dynamically as needed. At this stage, there may be multiple pairs with the same key. To accelerate the Partition function, the Emit intermediate function stores all values for the same key in the same buffer. At the end of the Map task, each buffer is sorted by key order. Reduce- Merge buffers are used to store the outputs of Reduce tasks before they are sorted. At this stage, each key has only one value associated with it. After sorting, the final output is available in the user allocated Output data buffer.		Two types of temporary buffers are necessary to store data between the various stages. All buffers are allocated in shared memory but are accessed in a well specified way by a few functions. To re-arrange buffers (e.g., split across tasks), pointer manipulation is done instead of the actual pairs, which may be large in size. The intermediate buffers are not directly visible to user code. Map-Reduce buffers are used to store the intermediate output pairs. Each worker has its own set of buffers. The buffers are initially sized to a default value and then resized dynamically as needed. At this stage, there may be multiple pairs with the same key. To accelerate the Partition function, the Emit intermediate function stores all values for the same key in the same buffer. At the end of the Map task, each buffer is sorted by key order. Reduce- Merge buffers are used to store the outputs of Reduce tasks before they are sorted. At this stage, each key has only one value associated with it. After sorting, the final output is available in the user allocated Output data buffer.

	==== Pros and Cons ====		===== Pros and Cons =====
	* '''Advantages'''		* '''Advantages'''

Zctaylor: /* Map Reduce for Shared Memory Systems */

2015-02-17T03:48:08Z

Map Reduce for Shared Memory Systems

← Older revision		Revision as of 03:48, 17 February 2015
Line 169:		Line 169:
	=== Challenges ===		=== Challenges ===

	Running MapReduce on a Shared Memory System can show a significant increase in speed over the cluster/disk based systems due to little to no overhead IO overhead. However a few challenges present themselves in the shared memory environment <ref>http://www4.ncsu.edu/~dtiwari2/Papers/2012_IPDPS_Devesh_MapReduce.pdf</ref>.		Running MapReduce on a Shared Memory System can show a significant increase in speed over the cluster/disk based systems due to little to no overhead IO overhead. However a few challenges present themselves in the shared memory environment <ref>Devesh Tiwari, Yan Solihin (2012). Modeling and Analyzing Key Performance Factors of Shared Memory MapReduce. Retrieved from http://www4.ncsu.edu/~dtiwari2/Papers/2012_IPDPS_Devesh_MapReduce.pdf</ref>.

	* Immediate output is stored in memory, requiring a lot for large problem sets.		* Immediate output is stored in memory, requiring a lot for large problem sets.
Line 185:		Line 185:

	=== Phoenix API ===		=== Phoenix API ===
	Phoenix <ref>http://csl.stanford.edu/~christos/publications/2007.cmp_mapreduce.hpca.pdf ~~Evaluating MapReduce for Multi-core and Multiprocessor Systems~~</ref>implements MapReduce for shared-memory systems. Its goal is to support efficient execution on multiple cores without burdening the programmer with concurrency management. Phoenix consists of a simple API that is visible to application programmers and an efficient runtime that handles parallelization, resource management, and fault recovery.		Phoenix <ref>Colby Ranger, Ramanan Raghuraman, Arun Penmetsa, Gary Bradski, Christos Kozyrakis (2007). Evaluating MapReduce for Multi-core and Multiprocessor Systems. Retrieved from http://csl.stanford.edu/~christos/publications/2007.cmp_mapreduce.hpca.pdf</ref>implements MapReduce for shared-memory systems. Its goal is to support efficient execution on multiple cores without burdening the programmer with concurrency management. Phoenix consists of a simple API that is visible to application programmers and an efficient runtime that handles parallelization, resource management, and fault recovery.

	The current Phoenix implementation provides an API for C and C++. <br>		The current Phoenix implementation provides an API for C and C++. <br>

Zctaylor: /* Metis */

2015-02-17T03:45:04Z

Metis

← Older revision		Revision as of 03:45, 17 February 2015
Line 182:		Line 182:
	=== Metis ===		=== Metis ===

	Designed by MIT to achieve better performance than Phoenix by "using better data structures for grouping the key/value pairs generated by Map and consumed by Reduce"<ref name="metis">Yandong Mao, Robert Morris, and Frans Kaashoek. [http://pdos.csail.mit.edu/papers/metis:mittr10.pdf Optimizing MapReduce for Multicore Architectures]. Technical Report MIT-CSAIL-TR-2010-020, MIT, 2010.</ref>. The Metis library uses a hash table with a b+tree as each entry. The common case can ~~use just~~ a hash lookup for an O(1) operation cost. For unexpected key workloads, the performance would fall back on to the b+tree to achieve O(log N) operation costs. The performance of Metis greatly surpasses Phoenix in almost every area except in the case where the programs spend the majority of their time in application code. For more performance benchmarks please see the reference <ref name="metis"/>.		Designed by MIT to achieve better performance than Phoenix by "using better data structures for grouping the key/value pairs generated by Map and consumed by Reduce"<ref name="metis">Yandong Mao, Robert Morris, and Frans Kaashoek. [http://pdos.csail.mit.edu/papers/metis:mittr10.pdf Optimizing MapReduce for Multicore Architectures]. Technical Report MIT-CSAIL-TR-2010-020, MIT, 2010.</ref>. The Metis library uses a hash table with a b+tree as each entry. The common case can uses a hash lookup for an O(1) operation cost. For unexpected key workloads, the performance would fall back on to the b+tree to achieve O(log N) operation costs. The performance of Metis greatly surpasses Phoenix in almost every area except in the case where the programs spend the majority of their time in application code. For more performance benchmarks please see the reference <ref name="metis"/>.

	=== Phoenix API ===		=== Phoenix API ===

Zctaylor: /* Metis */

2015-02-17T03:44:35Z

Metis

← Older revision		Revision as of 03:44, 17 February 2015
Line 182:		Line 182:
	=== Metis ===		=== Metis ===

	Designed by MIT to achieve better performance than Phoenix by "using better data structures for grouping the key/value pairs generated by Map and consumed by Reduce"<ref name="metis">Yandong Mao, Robert Morris, and Frans Kaashoek. [http://pdos.csail.mit.edu/papers/metis:mittr10.pdf Optimizing MapReduce for Multicore Architectures]. Technical Report MIT-CSAIL-TR-2010-020, MIT, 2010.</ref> The Metis library uses a hash table with a b+tree as each entry. The common case can use just a hash lookup for an O(1) operation cost. For unexpected key workloads, the performance would fall back on to the b+tree to achieve O(log N) operation costs. The performance of Metis greatly surpasses Phoenix in almost every area except in the case where the programs spend the majority of their time in application code. For more performance benchmarks please see the reference <ref name="metis"/>.		Designed by MIT to achieve better performance than Phoenix by "using better data structures for grouping the key/value pairs generated by Map and consumed by Reduce"<ref name="metis">Yandong Mao, Robert Morris, and Frans Kaashoek. [http://pdos.csail.mit.edu/papers/metis:mittr10.pdf Optimizing MapReduce for Multicore Architectures]. Technical Report MIT-CSAIL-TR-2010-020, MIT, 2010.</ref>. The Metis library uses a hash table with a b+tree as each entry. The common case can use just a hash lookup for an O(1) operation cost. For unexpected key workloads, the performance would fall back on to the b+tree to achieve O(log N) operation costs. The performance of Metis greatly surpasses Phoenix in almost every area except in the case where the programs spend the majority of their time in application code. For more performance benchmarks please see the reference <ref name="metis"/>.

	=== Phoenix API ===		=== Phoenix API ===

Zctaylor: /* Map Reduce for Shared Memory Systems */

2015-02-17T03:44:12Z

Map Reduce for Shared Memory Systems

← Older revision		Revision as of 03:44, 17 February 2015
Line 179:		Line 179:
	# [http://pdos.csail.mit.edu/metis/ Metis]		# [http://pdos.csail.mit.edu/metis/ Metis]
	# [http://csl.stanford.edu/~christos/sw/phoenix/ Phoenix++]		# [http://csl.stanford.edu/~christos/sw/phoenix/ Phoenix++]

			=== Metis ===

			Designed by MIT to achieve better performance than Phoenix by "using better data structures for grouping the key/value pairs generated by Map and consumed by Reduce"<ref name="metis">Yandong Mao, Robert Morris, and Frans Kaashoek. [http://pdos.csail.mit.edu/papers/metis:mittr10.pdf Optimizing MapReduce for Multicore Architectures]. Technical Report MIT-CSAIL-TR-2010-020, MIT, 2010.</ref> The Metis library uses a hash table with a b+tree as each entry. The common case can use just a hash lookup for an O(1) operation cost. For unexpected key workloads, the performance would fall back on to the b+tree to achieve O(log N) operation costs. The performance of Metis greatly surpasses Phoenix in almost every area except in the case where the programs spend the majority of their time in application code. For more performance benchmarks please see the reference <ref name="metis"/>.

	=== Phoenix API ===		=== Phoenix API ===

Zctaylor: /* Basic MapReduce Patterns */

2015-02-17T03:25:31Z

Basic MapReduce Patterns

← Older revision		Revision as of 03:25, 17 February 2015
Line 318:		Line 318:
	== Basic MapReduce Patterns ==		== Basic MapReduce Patterns ==

	=== Counting and Summing ===		=== Counting and Summing<ref name=katsov2012>Ilya Katsov (2012). Retrieved from MapReduce Patterns, Algorithms, and Use Cases https://highlyscalable.wordpress.com/2012/02/01/mapreduce-patterns/</ref> ===

	Suppose you wanted to count the number of occurrences for each word in a set of documents~~<ref name=katsov2012>Ilya Katsov (2012). Retrieved from MapReduce Patterns, Algorithms, and Use Cases https://highlyscalable.wordpress.com/2012/02/01/mapreduce-patterns/</ref>~~. The documents could be anything; a log file or an http page.		Suppose you wanted to count the number of occurrences for each word in a set of documents. The documents could be anything; a log file or an http page.

	The simpliest approach is just to simply emit "1" for each term that a document possesses and then have the reducer add them up.		The simpliest approach is just to simply emit "1" for each term that a document possesses and then have the reducer add them up.
Line 373:		Line 373:
	</pre>		</pre>

	=== Distributed Task Execution ===		=== Distributed Task Execution<ref name=katsov2012/> ===

	A large computational problem that can be divided into equal parts and then combined together for a final result is a standard Map-Reduce problem~~<ref name=katsov2012/>~~. The problem is split into a set of specifications and specifications are stored as input data for the mappers. Each mapper takes a specification, executes the computation and then emits the results.		A large computational problem that can be divided into equal parts and then combined together for a final result is a standard Map-Reduce problem. The problem is split into a set of specifications and specifications are stored as input data for the mappers. Each mapper takes a specification, executes the computation and then emits the results.

	<pre>		<pre>

Zctaylor: /* Advanced MapReduce Patterns https://highlyscalable.wordpress.com/2012/02/01/mapreduce-patterns/ */

2015-02-17T03:25:06Z

Advanced MapReduce Patterns https://highlyscalable.wordpress.com/2012/02/01/mapreduce-patterns/

← Older revision		Revision as of 03:25, 17 February 2015
Line 392:		Line 392:
	</pre>		</pre>

	==Advanced MapReduce Patterns ~~<ref>https://highlyscalable.wordpress.com/2012/02/01/mapreduce-patterns/</ref>~~==		==Advanced MapReduce Patterns ==

	=== Graph Processing ===		=== Graph Processing<ref name=katsov2012/> ===

	In a network of entities, relationships exist between all nodes. The problem is calculating a state for each node using the properties of its neighbors. This state can be the distance between nodes, characteristics of density and so on. Conceptually MapReduce jobs are performed in an iterative way. On each iteration, a node sends a message to its neighbors. Each neighbor will then update its state based on the message it received. The iteration is terminated based on some condition like a fixed number of iterations or minor changes in state. The Mapper is responsibly for emitting messages with for each node using the adjacent node ID as a key. The Reducer is responsible for recomputing state and rewriting the node with the new state based on the the messages from the incoming node.		In a network of entities, relationships exist between all nodes. The problem is calculating a state for each node using the properties of its neighbors. This state can be the distance between nodes, characteristics of density and so on. Conceptually MapReduce jobs are performed in an iterative way. On each iteration, a node sends a message to its neighbors. Each neighbor will then update its state based on the message it received. The iteration is terminated based on some condition like a fixed number of iterations or minor changes in state. The Mapper is responsibly for emitting messages with for each node using the adjacent node ID as a key. The Reducer is responsible for recomputing state and rewriting the node with the new state based on the the messages from the incoming node.