1.. _Agglomeration:
2
3Agglomeration
4=============
5
6
7.. container:: section
8
9
10   .. rubric:: Problem
11      :class: sectiontitle
12
13   Parallelism is so fine grained that overhead of parallel scheduling
14   or communication swamps the useful work.
15
16
17.. container:: section
18
19
20   .. rubric:: Context
21      :class: sectiontitle
22
23   Many algorithms permit parallelism at a very fine grain, on the order
24   of a few instructions per task. But synchronization between threads
25   usually requires orders of magnitude more cycles. For example,
26   elementwise addition of two arrays can be done fully in parallel, but
27   if each scalar addition is scheduled as a separate task, most of the
28   time will be spent doing synchronization instead of useful addition.
29
30
31.. container:: section
32
33
34   .. rubric:: Forces
35      :class: sectiontitle
36
37   -  Individual computations can be done in parallel, but are small.
38      For practical use of |full_name|,
39      "small" here means less than 10,000 clock cycles.
40
41
42   -  The parallelism is for sake of performance and not required for
43      semantic reasons.
44
45
46.. container:: section
47
48
49   .. rubric:: Solution
50      :class: sectiontitle
51
52   Group the computations into blocks. Evaluate computations within a
53   block serially.
54
55
56   The block size should be chosen to be large enough to amortize
57   parallel overhead. Too large a block size may limit parallelism or
58   load balancing because the number of blocks becomes too small to
59   distribute work evenly across processors.
60
61
62   The choice of block topology is typically driven by two concerns:
63
64
65   -  Minimizing synchronization between blocks.
66
67
68   -  Minimizing cache traffic between blocks.
69
70
71   If the computations are completely independent, then the blocks will
72   be independent too, and then only cache traffic issues must be
73   considered.
74
75
76   If the loop is "small", on the order of less than 10,000 clock
77   cycles, then it may be impractical to parallelize at all, because the
78   optimal agglomeration might be a single block,
79
80
81.. container:: section
82
83
84   .. rubric:: Examples
85      :class: sectiontitle
86
87   TBB loop templates such as ``oneapi::tbb::parallel_for`` that take a *range*
88   argument support automatic agglomeration.
89
90
91   When agglomerating, think about cache effects. Avoid having cache
92   lines cross between groups if possible.
93
94
95   There may be boundary to interior ratio effects. For example, if the
96   computations form a 2D grid, and communicate only with nearest
97   neighbors, then the computation per block grows quadratically (with
98   the block's area), but the cross-block communication grows with
99   linearly (with the block's perimeter). The following figure shows
100   four different ways to agglomerate an 8×8 grid. If doing such
101   analysis, be careful to consider that information is transferred in
102   cache line units. For a given area, the perimeter may be minimized
103   when the block is square with respect to the underlying grid of cache
104   lines, not square with respect to the logical grid.
105
106
107   .. container:: fignone
108      :name: fig1
109
110
111      Four different agglomerations of an 8×8 grid. |image0|
112
113
114   Also consider vectorization. Blocks that contain long contiguous
115   subsets of data may better enable vectorization.
116
117
118   For recursive computations, most of the work is towards the leaves,
119   so the solution is to treat subtrees as a groups as shown in the
120   following figure.
121
122
123   .. container:: fignone
124      :name: fig2
125
126
127      Agglomeration of a recursive computation |image1|
128
129
130   Often such an agglomeration is achieved by recursing serially once
131   some threshold is reached. For example, a recursive sort might solve
132   sub-problems in parallel only if they are above a certain threshold
133   size.
134
135
136.. container:: section
137
138
139   .. rubric:: Reference
140      :class: sectiontitle
141
142   Ian Foster introduced the term "agglomeration" in his book Designing
143   and Building Parallel Programs http://www.mcs.anl.gov/~itf/dbpp.
144   There agglomeration is part of a four step **PCAM** design method:
145
146
147   #. **P**\ artitioning - break the program into the smallest tasks
148      possible.
149
150
151   #. **C**\ ommunication – figure out what communication is required
152      between tasks. When using oneTBB, communication is usually cache
153      line transfers. Though they are automatic, understanding which
154      ones happen between tasks helps guide the agglomeration step.
155
156
157   #. **A**\ gglomeration – combine tasks into larger tasks. His book
158      has an extensive list of considerations that is worth reading.
159
160
161   #. **M**\ apping – map tasks onto processors. The oneTBB task
162      scheduler does this step for you.
163
164
165.. |image0| image:: Images/image002a.jpg
166   :width: 301px
167   :height: 293px
168.. |image1| image:: Images/image003a.jpg
169   :width: 291px
170   :height: 150px
171
172