Map is an
idiom
An idiom is a phrase or expression that typically presents a figurative, non-literal meaning attached to the phrase; but some phrases become figurative idioms while retaining the literal meaning of the phrase. Categorized as formulaic language, ...
in
parallel computing
Parallel computing is a type of computation in which many calculations or processes are carried out simultaneously. Large problems can often be divided into smaller ones, which can then be solved at the same time. There are several different fo ...
where a simple operation is applied to all elements of a sequence, potentially in parallel. It is used to solve
embarrassingly parallel problems: those problems that can be decomposed into independent subtasks, requiring no communication/synchronization between the subtasks except a
join or
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
threads of execution,
hyperthread
Hyper-threading (officially called Hyper-Threading Technology or HT Technology and abbreviated as HTT or HT) is Intel's proprietary simultaneous multithreading (SMT) implementation used to improve parallelization of computations (doing multip ...
s,
SIMD lanes
Single instruction, multiple data (SIMD) is a type of parallel processing in Flynn's taxonomy. SIMD can be internal (part of the hardware design) and it can be directly accessible through an instruction set architecture (ISA), but it should ...
or on
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;
languages such as
OpenCL and
CUDA support elemental functions (as "
kernels") at the language level. The map pattern is typically combined with other parallel design patterns. For example, map combined with category reduction gives the
MapReduce pattern.
See also
*
Map (higher-order function)
*
Functional programming
*
Algorithmic skeleton
References
{{reflist
Parallel computing
Software design patterns