Map (parallel pattern): Difference between revisions

Revision as of 13:02, 3 February 2015

Latest revision as of 05:00, 12 February 2023

(14 intermediate revisions by 5 users not shown)

Line 1:

'''Map''' is aan [[designProgramming patternidiom|idiom]] in [[parallel computing]] where a simple operation is applied to all elements of a sequence, potentially in parallel.<ref>{{cite conference |last1=Samadi |first1=Mehrzad |first2=Davoud Anoushe |last2=Jamshidi |first3=Janghaeng |last3=Lee |first4=Scott |last4=Mahlke |title=Paraprox: Pattern-based approximation for data parallel applications |conference=Proc. 19th Int'l Conf. on Architectural support for programming languages and operating systems |url=http://cccp.eecs.umich.edu/papers/samadi-asplos14.pdf|doi=10.1145/2541940.2541948|year=2014}}</ref> It is used to solve '''embarrasingly[[embarrassingly parallel''']] problems: those problems that can be decomposed into independent subtasks, requiring no communication/synchronization between the subtasks except a [[Fork–join model|join]] or [[Barrier (computer science)|barrier]] at the end.

{{single source}}

'''Map''' is a [[design pattern]] in [[parallel computing]] where a simple operation is applied to all elements of a sequence, potentially in parallel. It is used to solve '''embarrasingly parallel''' problems: those problems that can be decomposed into independent subtasks, requiring no communication/synchronization between the subtasks except a [[Fork–join model|join]] or [[Barrier (computer science)|barrier]] at the end.

When applying the map pattern, one formulates an ''elemental function'' that captures the operation to be performed on a data item that represents a part of the problem, then applies this elemental function in one or more [[Thread (computing)|threads of execution]], [[hyperthread]]s, [[SIMD]] lanes]] or on [[distributed computing|multiple computers]].

Some parallel programming systems, such as [[OpenMP]] and [[Cilk]], have language support for the map pattern in the form of a '''parallel for loop''';<ref>{{cite web |title=Compilers and More: The Past, Present and Future of Parallel Loops |first=Michael |last=Wolfe |date=6 April 2015 |website=HPCwire |url=http://www.hpcwire.com/2015/04/06/compilers-and-more-the-past-present-and-future-of-parallel-loops/}}</ref> languages such as [[OpenCL]] and [[CUDA]] support elemental functions (as "[[GPGPU#KernelsCompute kernel|kernels]]") at the language level. The map pattern is typically combined with other parallel design patterns. E.g.For example, map combined with category reduction gives the [[MapReduce]] pattern.<ref name="spp">{{cite book |author1=Michael McCool |author2=James Reinders |author3=Arch Robison |title=Structured Parallel Programming: Patterns for Efficient Computation |isbn= 978-0124159938|publisher=Elsevier |year=2013}}</ref>{{rp|pp=106–107}}

==See also==

* [[Map (higher-order function)]]

* [[Functional programming]]

* [[Algorithmic skeleton]]

==References==

{{reflist}}

[[Category:Parallel computing]]

[[Category:Software design patterns]]