Would it be more efficient to have a specialized implementation instead of combining existing collectives ?
Let the size of each $x_{i,j}$ be $n/p$ bytes.
MPI_Reduce acts on the concatenation $x_{:,j}$ which has length $n$ bytes hence the complexity is $\log_2(p)(\alpha + \beta n + \gamma n)$
MPI_Scatter has the same complexity as MPI_Gather (since it's the same but backwards in time) : $\log_2(p) \alpha + \beta n$
In total, we have the complexity $\log_2(p) (\alpha + \beta n + \gamma n)$. Can we do better ?
Start exchanging between 1 and 2 and simultaneously exchanging between 3 and 4. The complexity is $\alpha + 2(\beta + \gamma) n/4$.
procid | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| $x_{1,1} + x_{1,2}$ | $x_{1,3} + x_{1,4}$ | |||
| $x_{2,1} + x_{2,2}$ | $x_{2,3} + x_{2,4}$ | |||
| $x_{3,1} + x_{3,2}$ | $x_{3,3} + x_{3,4}$ | |||
| $x_{4,1} + x_{4,2}$ | $x_{4,3} + x_{4,4}$ |
Next, we exchange between 1 and 3 and simultaneously between 2 and 4. The complexity is $\alpha + (\beta + \gamma) n/4$. In total, we have complexity
$$\begin{align} \log_2(p) \alpha + (\beta + \gamma) n(p/2 + \cdots + 4 + 2 + 1)/p & = \log_2(p) \alpha + (\beta + \gamma) n(p-1)/p\\ & \approx \log_2(p) \alpha + (\beta + \gamma) n. \end{align}$$
This is better than the approaches combining existing collectives above since we removed the $\log_2(p)$ in front of $\beta$ and $\gamma$.
mimetext/htmlrootassigneelast_run_timestampAڝrpersist_js_state·has_pluto_hook_features§cell_id$f6f9447c-9bc9-432d-bd80-2c39f9d842f8depends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$9a100ccf-1ad3-4d2c-bbe0-e297969eb69equeued¤logsrunning¦outputbody<Before
procid | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| $x$ |
After
procid | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| $x$ | $x$ | $x$ | $x$ |
What is the number of edges ? What is the bisection width ?
Number of edges is $n\log_2(n)$ and bisection width is $n/2$.
What is the diameter and bisection width of $n$ computer nodes ?
Diameter is $2\log_2(n)$ and bisection width is 1. 
There can be $n$ simultaneous communications at the same time, provided that each input communicates with a different output. The figure on the right provides an example of such non-conflicting communications with the black dots indicating that the input of that row communicates to the corresponding output (case (a) of above figure). The switch at row 1 and column 2 is just propagating the input data horizontally and output data vertically (case (b) of above figure). The switch at row 0 and column 5 is receiving no data.
text/html,application/vnd.pluto.reactdomelement+objectmime,application/vnd.pluto.reactdomelement+objectrootassigneelast_run_timestampAڝr麶persist_js_state·has_pluto_hook_features§cell_id$133f4c7d-33e0-4e13-b716-f538125436cadepends_on_disabled_cells§runtimelpublished_object_keysdepends_on_skipped_cells§errored$3a50ca06-06e8-4a61-ade2-afbfc52ca655queued¤logsrunning¦outputbody
mimetext/htmlrootassigneelast_run_timestampAڝrypersist_js_state·has_pluto_hook_features§cell_id$3a50ca06-06e8-4a61-ade2-afbfc52ca655depends_on_disabled_cells§runtimepublished_object_keysdepends_on_skipped_cells§errored$6c1984f6-4e36-4637-b0da-c7dd8b0f9ff0queued¤logsrunning¦outputbodymimetext/plainrootassigneelast_run_timestampAڝrΞpersist_js_state·has_pluto_hook_features§cell_id$6c1984f6-4e36-4637-b0da-c7dd8b0f9ff0depends_on_disabled_cells§runtime ۵published_object_keysdepends_on_skipped_cells§errored$de20bf96-7d33-4a78-8147-f0b7f8488e46queued¤logsrunning¦outputbody eWould it be more efficient to have a specialized implementation instead of combining existing collectives ?
Let the size of $x_i$ be $n/p$ bytes.
MPI_Gather has complexity $\log_2(p)\alpha + \beta n$
MPI_Bcast acts on the concatenation $x_:$ which has length $n$ bytes so the complexity is $\log_2(p) (\alpha + \beta n)$
In total, we have the complexity $\log_2(p) (\alpha + \beta n)$. Can we do better ?
Start exchanging between 1 and 2 and simultaneously exchanging between 3 and 4. The complexity is $\alpha + \beta n/4$.
procid | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| $x_1$ | $x_1$ | |||
| $x_2$ | $x_2$ | |||
| $x_3$ | $x_3$ | |||
| $x_4$ | $x_4$ |
Next, we exchange between 1 and 3 and simultaneously between 2 and 4. The complexity is $\alpha + 2\beta n/4$. In total, we have complexity
$$\begin{align} \log_2(p) \alpha + \beta n(1 + 2 + 4 + \cdots + p/2)/p & = \log_2(p) \alpha + \beta n(p-1)/p\\ & \approx \log_2(p) \alpha + \beta n. \end{align}$$
Consider graph $G$ with nodes $v$ corresponding to computer nodes or switches.
There is an edge $(u, v) \in E$ if there is an ethernet cable directly connecting $u$ and $v$.
$e \in E$ are ethernet cables of bandwidth $w_e$
Distance (unweighted) from node $u \in V$ to node $v \in V$ is $d(G, u, v)$
Does not depend on bandwidth $w_e$ of edges of the path
mimetext/htmlrootassigneelast_run_timestampAڝr1persist_js_state·has_pluto_hook_features§cell_id$39b055f5-3dbf-403c-b21e-210e3813d8b0depends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$b0ca0392-71b8-4f44-8c6c-0978a02a0e6cqueued¤logslinemsgٔCompiling : `mpicc -O3 -I/home/runner/.julia/artifacts/207eb5b8330e24674fe59b50d72f4b3d946219c8/include /tmp/jl_BbghxG/main.c -o /tmp/jl_BbghxG/bin`text/plaincell_id$b0ca0392-71b8-4f44-8c6c-0978a02a0e6ckwargsidSimpleClang_e77d60b3fileA/home/runner/.julia/packages/SimpleClang/N4VZY/src/SimpleClang.jlgroupSimpleClanglevelInfolinemsg+Running : `mpiexec -n 2 /tmp/jl_BbghxG/bin`text/plaincell_id$b0ca0392-71b8-4f44-8c6c-0978a02a0e6ckwargsidSimpleClang_9f8d091bfileA/home/runner/.julia/packages/SimpleClang/N4VZY/src/SimpleClang.jlgroupSimpleClanglevelInfolinemsgbProcess 0/2 is running on node < int name_length = MPI_MAX_PROCESSOR_NAME;
char proc_name[name_length];
MPI_Get_processor_name(proc_name,&name_length);
printf("Process %d/%d is running on node <<%s>>\n",
procid,nprocs,proc_name); for(int size = 1; size <= (1<<20); size <<= 1){
char* buf = malloc(size);
if (procid == 0) {
MPI_Barrier(MPI_COMM_WORLD);
MPI_Send(buf, size, MPI_CHAR, procid + 1, 0, comm);
}
else {
MPI_Irecv(buf, size, MPI_CHAR, procid - 1, 0, MPI_COMM_WORLD, &rqst);
MPI_Barrier(MPI_COMM_WORLD);
double tic = MPI_Wtime();
MPI_Wait(&rqst, MPI_STATUS_IGNORE);
double toc = MPI_Wtime();
printf("[%d] I have received %d B in %f sec\n", procid, size, (toc-tic));
}
}num_processes =
srun : Synchronous (blocked) job
[blegat@lm4-f001 ~]$ srun --time=1 pwd
srun: job 3491072 queued and waiting for resources
srun: job 3491072 has been allocated resources
/home/users/b/l/blegat$ sbatch submit.sh : Asynchronous job, get status with
$ squeue --me
More details on the README
Before
procid | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| $x_1$ | ||||
| $x_2$ | ||||
| $x_3$ | ||||
| $x_4$ |
After
procid | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| $x_1$ | ||||
| $x_2$ | ||||
| $x_3$ | ||||
| $x_4$ |
mimetext/htmlrootassigneelast_run_timestampAڝr"persist_js_state·has_pluto_hook_features§cell_id$8a527c17-bf2b-4e6b-937f-ef3a269c5112depends_on_disabled_cells§runtime Bpublished_object_keysdepends_on_skipped_cells§errored$be0e3ba0-18cc-4b9a-a56d-2566f5148faequeued¤logsrunning¦outputbody:
Can MPI_Reduce_scatter be implemented by combining existing collectives ?
MPI_Reduce_scatter can be implemented by MPI_Reduce followed by MPI_Scatter
Bandwidth $\texttt{bw}(u, v)$ is the bandwidth of the cable if $(u, v) \in E$ or 0 otherwise. Given $S, T \subseteq V$ two disjoint subsets of nodes $S \cap T = \varnothing$,
$$\begin{align} \text{Width} &\qquad & w(S, T) & = |\{ (u, v) \in E \mid u \in S, v \in T \}|\\ \text{Bandwidth} & & \texttt{bw}(S, T) & = \sum_{u\in S, v\in T} \texttt{bw}(u,v) \end{align}$$
The width is exactly the number of edges between the two sets of nodes.
Free up memory.
MPI_Finalize();You could simply add lmpi but using mpicc and mpic++ is easier.
What is the bisection width of a $n \times n$ 2D array ?
It is $n = \sqrt{|V|}$: What is the bisection width of a $n^d$ $d$D array ? It is 1 for $d = 1$, $n$ for $d = 2$ and $n^2$ for $d = 3$. In general, it is $n^{d-1} = |V|^{(d-1)/d}$
What is the graph diameter ?
$|V| - 1$ if $u$ and $v$ are extreme points of the array
What is the graph diameter of a $n \times n$ 2D array ?
It is $2(n-1)$, attained for opposite vertices of the square. What is the graph diameter of a $n^d$ $d$D array ? It is $d(n-1)$, attained for opposite vertices of the hypercube.
text/html=8
text/htmlmime,application/vnd.pluto.reactdomelement+objectrootassigneelast_run_timestampAڝr$ persist_js_state·has_pluto_hook_features§cell_id$655e980d-b4e9-4f56-a5ae-380072242d27depends_on_disabled_cells§runtime N[published_object_keysdepends_on_skipped_cells§errored$4788d8b4-2efa-4489-80c3-71f405513644queued¤logsrunning¦outputbody2num_processes =
Lower bound complexity with $p$ processes if each $x_i$ has length $n/p$ bytes ?
Lower bound : $\log_2(p) \alpha$ using spanning tree algorithm and $\beta n$ as all messages need to be sent at least once.
First send $x_2$ from 2 to 1 and simultaneously send $x_4$ from 4 to 3. Complexity is $\alpha + \beta n/4$
procid | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| $x_1$ | ||||
| $x_2$ | $x_2$ | |||
| $x_3$ | ||||
| $x_4$ | $x_4$ |
Then send $(x_3, x_4)$ from 3 to 1. Complexity is $\alpha + 2\beta n/4$
procid | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| $x_1$ | ||||
| $x_2$ | $x_2$ | |||
| $x_3$ | $x_3$ | |||
| $x_4$ | $x_4$ | $x_4$ |
In total, it is $2\alpha + 3\beta n/4$. In general, we have
$$\log_2(p)\alpha + \beta n(1 + 2 + 4 + \cdots + p/2)/p = \log_2(p)\alpha + \beta n(p - 1)/p \approx \log_2(p)\alpha + \beta n$$
What about having each node sending directly to 1 ?
procid | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| $x_1$ | ||||
| $x_2$ | $x_2$ | |||
| $x_3$ | ||||
| $x_4$ |
Then
procid | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| $x_1$ | ||||
| $x_2$ | $x_2$ | |||
| $x_3$ | $x_3$ | |||
| $x_4$ |
Then
procid | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| $x_1$ | ||||
| $x_2$ | $x_2$ | |||
| $x_3$ | $x_3$ | |||
| $x_4$ | $x_4$ |
Here, we have $3\alpha + 3\beta n/4$. The coefficient is higher in front of $\alpha$. However, is the same in front of $\beta$. Indeed, even though the spanning tree above communicate more bytes through the network, as the communication from node 2 to node 1 and node 4 to node 3 are done in parallel, this isn't affecting the coefficient in front of $\beta$.
Can MPI_Allgather be implemented by combining existing collectives ?
MPI_Allgather can be implemented by MPI_Gather followed by MPI_Bcast
blocking factor : Ratio between upper links and lower links. Ratio is 1 for fat-tree to prevent bottlenecks if all nodes start communicating.
Blocking send/received with MPI_Send and MPI_Recv.
The network cannot buffer the whole message (unless it is short). The sender needs to wait for the receiver to be ready and then transfers its copy of the data.
What is the bisection width ?
The bisection width is 1 : 
What are the differences with Min-Cut ?
In Min-Cut, we fix a node in $S$, a node in $V \setminus S$ and the cardinality of S is not constrained. These differences allow Min-Cut to be solvable in polynomial time.
Fat-tree needs large switches, the root one of previous slide had 8 links. This is as many links as the number of processes, that's not scalable. An alternative is butterfly network for which each switch uses at most 4 links. In the figures above, the boxes with P represent a process, the ones with M represent their local memory and the other ones are the routers.
How to fix it ?
We should load gompi or at least OpenMPI:
[blegat@lm4-f001 examples]$ module load OpenMPI
[blegat@lm4-f001 examples]$ mpicc procname.c
[blegat@lm4-f001 examples]$ mpiexec -n 4 a.out
Process 1/4 is running on node <<lm4-f001>>
Process 3/4 is running on node <<lm4-f001>>
Process 0/4 is running on node <<lm4-f001>>
Process 2/4 is running on node <<lm4-f001>>Why are they all on same node ?
We are on the login node, we need to run jobs on the compute nodes using Slurm !
Lower bound complexity with $p$ processes if $x$ has length $n$ bytes ?
Lower bound : $\log_2(p) (\alpha + \beta n)$ using spanning tree algorithm:
After first communication (1 → 3):
procid | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| $x$ | $x$ |
After second communication (1 → 2 and 3 → 4 at the same time):
procid | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| $x$ | $x$ | $x$ | $x$ |
Worst case pairwise communication of two groups $S$ and $V \setminus S$ of almost ($\pm 1$) equal size.
NP-hard to compute for general graphs.
Follow README instructions to create an account and setup your computer
Don't wait the last minute, if you get into trouble it's easier to get this setup before you actually need it
Select 
cluster from the list + manneback for GPU. You only have access to Tier-2 clusters. This sadly leaves out:
Tier-1 clusters such as Lucia
Tier-0 cluster such as 
from 
Connect with SSH using ssh lemaitre4 or ssh manneback.
Before
procid | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| $x_1$ | ||||
| $x_2$ | ||||
| $x_3$ | ||||
| $x_4$ |
After MPI_Allgather
procid | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| $x_1$ | $x_1$ | $x_1$ | $x_1$ | |
| $x_2$ | $x_2$ | $x_2$ | $x_2$ | |
| $x_3$ | $x_3$ | $x_3$ | $x_3$ | |
| $x_4$ | $x_4$ | $x_4$ | $x_4$ |
MPI_Isend and MPI_Irecv where I stands for immediate or incomplete. MPI_Wait can be used to wait for the send and receive to finish.
[laptop]$ ssh lemaitre4
[blegat@lm4-f001 ~]$ cd LINMA2710/examples
[blegat@lm4-f001 examples]$ mpicc procname.c
-bash: mpicc: command not foundMPI 
is an open standard for distributed computing
MPICH, from 
and 
Open MPI 
(not to be confused with 
)
commercial implementations from 
, 
, 
, and 
Before
procid | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| $x_1$ | $x_2$ | $x_3$ | $x_4$ |
After
procid | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| $x_1 + x_2 + x_3 + x_4$ |
Specializing on topology is important for communication libraries like MPI/NCCL. For instance, Deepseek-V3 by-passed NCCL and used PTX directly to hardcode how their hardware should be used.
Specified in Slurm's topology.conf file.
Source : [Eij10; Section 2.7]
mimetext/htmlrootassigneelast_run_timestampAڝrWTpersist_js_state·has_pluto_hook_features§cell_id$4aac6ab5-053a-4f60-9e2e-e8d61ff0cecbdepends_on_disabled_cells§runtime ĵpublished_object_keysdepends_on_skipped_cells§errored$61af27f1-9f83-42f1-a419-06d12ea62133queued¤logsrunning¦outputbody{
mimetext/htmlrootassigneelast_run_timestampAڝrEach process runs the same executable. So how can we make them do different things ?
Even if the code is the same, MPI_Comm_rank will give different procid so the part of the program depending on the value of procid will differ.
Lower bound complexity with $p$ processes if each $x_i$ has length $n$ bytes and the arithmetic complexity is $\gamma$ ?
Lower bound : $\log_2(p) (\alpha + \beta n) + \log_2(p) \gamma n$ using spanning tree algorithm:
First communication (2 → 1 and 4 → 3 at the same time):
procid | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| $x_1 + x_2$ | $x_3 + x_4$ |
Then second communication (3 → 1)
mimetext/htmlrootassigneelast_run_timestampAڝrpersist_js_state·has_pluto_hook_features§cell_id$370f0f20-e373-4028-bca1-83e93678cbcbdepends_on_disabled_cells§runtime
:published_object_keysdepends_on_skipped_cells§errored$1bac238f-79c8-4f9f-a187-bacb288de3b0queued¤logsrunning¦outputbody PNG
IHDR B bKGD IDATxXAPAд" D RN66ܥˉښH29EAJl[%? i5
1"&?ǽ1<9s< pƻ/}sE d = @
(` $ @
(` $ @
(` $ @
(` $ @
(` $ @
(` $ @
(` $ @
(` $p= ~+++;w"000&&f̙?EQd T---\/fff:99I
@
%{uqqIHHXhȑ#wBٳG L+`f8;;͚5 455͘1C LIXS%!!c
!W^(Jnn ، !#ϝO `(`0`3M&x~ȑ#B@k`8 IXNNN ~appp|IXXؽ{8 Zu&v-[ !W^ !xwk]lِ!C$O u а\???5 c
ٳ=<What is the bisection width ?
The bisection width is 2: 
Def: Graph diameter
Graph diameter is $d(G) := \max_{u, v \in V} d(G, u, v)$
The time it takes to transfer $n$ bytes is usually modeled with
$$T(n) = \alpha + \beta n$$
where $\alpha$ is the latency (fixed-cost) and $\beta$ is the time per byte, so the inverse of the bandwidth, (linear cost). This simple model does not incorporate the fact that communicating between nodes that are not directly connected needs to pass through intermediate nodes or routers. Therefore, using these formula only gives a lower bound to the actual time. This bound is achieved for a fully-connected topology but for other topologies, they should really only be considered as a lower bound. So consider the bounds obtained in the Collectives section below as lower bounds.
See [Eij10; Section 2.7.8] for more details.
[Eij10] V. Eijkhout. Introduction to High Performance Scientific Computing. 3 Edition, Vol. 1 (Lulu.com, 2010).
[Eij17] V. Eijkhout. Parallel Programming in MPI and OpenMP. 2 Edition, Vol. 2 (Lulu.com, 2017).
Processes that are on the same node share the same processor_name (the hostname).
What is the graph diameter ?
$|V|/2$
What are the number of switches, edges, graph diameter and bisection width for $n$ computer nodes ?
There are $n^2$ switches one per intersection. This makes this architecture only suitable for small $n$.
The number of edges is : $|E| = 2n^2$ which consists of $n$ connections from an input to a switch, $n$ connections from a switch to an output and $2n(n-1)$ connections between switches.
The diameter is 2 if we don't count the in-between switches or $2n$ if we count them.
The bisection width is $n/2$.
Can MPI_Allreduce be implemented by combining existing collectives ?
Let the size of each $x_i$ be $n$ bytes. MPI_Allreduce can be implemented either by combining MPI_Reduce followed by MPI_Bcast or MPI_Reduce_scatter followed by MPI_Allgather. The first choice would lead to a complexity of $\log_2(p)(\alpha + \beta n + \gamma n )$. The second would lead to a complexity of $\log_2(p)\alpha + \beta n + \gamma n$. This second approach is faster for large $p$ since we removed $\log_2(p)$ in front of $\beta$ and $\gamma$.
[local computer]$ ssh lemaitre4[blegat@lm4-f001 ~]$ module list
Currently Loaded Modules:
1) tis/2018.01 (S) 2) releases/2023a (S) 3) StdEnv
Where:
S: Module is Sticky, requires --force to unload or purge[blegat@lm4-f001 ~]$ mpicc
-bash: mpicc: command not found
[blegat@lm4-f001 ~]$ module load gompi/2023a
[blegat@lm4-f001 ~]$ mpicc
gcc: fatal error: no input files
compilation terminated.[blegat@lm4-f001 ~]$ module list
Currently Loaded Modules:
1) tis/2018.01 (S) 11) libpciaccess/0.17-GCCcore-12.3.0
2) releases/2023a (S) 12) hwloc/2.9.1-GCCcore-12.3.0
3) StdEnv 13) OpenSSL/1.1
4) GCCcore/12.3.0 14) libevent/2.1.12-GCCcore-12.3.0
5) zlib/1.2.13-GCCcore-12.3.0 15) UCX/1.14.1-GCCcore-12.3.0
6) binutils/2.40-GCCcore-12.3.0 16) libfabric/1.18.0-GCCcore-12.3.0
7) GCC/12.3.0 17) PMIx/4.2.4-GCCcore-12.3.0
8) numactl/2.0.16-GCCcore-12.3.0 18) UCC/1.2.0-GCCcore-12.3.0
9) XZ/5.4.2-GCCcore-12.3.0 19) OpenMPI/4.1.5-GCC-12.3.0
10) libxml2/2.11.4-GCCcore-12.3.0 20) gompi/2023a
Where:
S: Module is Sticky, requires --force to unload or purgeEach node input is a row and each node output is a column; source of figure below.
Each intersection is a switch. The cases (a) and (c) represent conflicting cases where two inputs want to simultaneously communicate with the same output.
Initializes MPI, remove mpiexec, etc... from argc and argv.
MPI_Init(&argc, &argv) int tag = 0;
for(int size = 1; size <= (1<<20); size <<= 1){
char* buf = malloc(size);
if (procid == 0) {
MPI_Send(buf, size, MPI_CHAR, procid + 1, tag++, comm);
}
else {
double tic = MPI_Wtime();
MPI_Recv(buf, size, MPI_CHAR, procid - 1, tag++, comm, MPI_STATUS_IGNORE);
double toc = MPI_Wtime();
printf("[%d] I have received %d B in %f sec\n", procid, size, (toc-tic));
}
}Get the id of processes. procid is different for different processes.
int procid;
MPI_Comm_rank(MPI_COMM_WORLD, &procid);What is the number of edges ? What is the bisection width ?
Same as fat-tree.
mimetext/htmlrootassigneelast_run_timestampAڝr!persist_js_state·has_pluto_hook_features§cell_id$b94cd399-0370-49e9-a522-056f3af22955depends_on_disabled_cells§runtime/vpublished_object_keysdepends_on_skipped_cells§errored$58e12afd-6eb0-4731-bd57-d9ae7ab4e164queued¤logsrunning¦outputbodyV^LINMA2710 - Scientific Computing Distributed Computing with MPI
P.-A. Absil and B. Legat
mimetext/htmlrootassigneelast_run_timestampAڝr,persist_js_state·has_pluto_hook_features§cell_id$58e12afd-6eb0-4731-bd57-d9ae7ab4e164depends_on_disabled_cells§runtime2epublished_object_keysdepends_on_skipped_cells§errored$141d162c-c817-498f-be16-f1cd35d82487queued¤logsrunning¦outputbodyHow to collect the partial sums ?
MPI_Reduce
Get the number of processes. nprocs is the same on all processes.
int nprocs;
MPI_Comm_size(MPI_COMM_WORLD, &nprocs);NVIDIA Nsight Systems 
can profile CUDA code but also MPI
Available on manneback after loading CUDA with
[laptop]$ ssh manneback
[blegat@mbackf1 ~]$ nsys
-bash: nsys: command not found
[blegat@mbackf1 ~]$ ml CUDA
[blegat@mbackf1 ~]$ nsys for (int i = stride * procid; i < last; i++)
local_sum += vec[i];
float total = 0;
MPI_Reduce(&local_sum, &total, 1, MPI_FLOAT, MPI_SUM, 0, comm);
if (verbose >= 1)
fprintf(stderr, "proc id : %d / %d : [local = %f] : [total = %f]\n", procid, nprocs, local_sum, total);
text/html #/
text/htmlmime,application/vnd.pluto.reactdomelement+objectrootassigneelast_run_timestampAڝrpersist_js_state·has_pluto_hook_features§cell_id$0e640e07-82c7-4dab-a8f1-2f634bbebdeadepends_on_disabled_cells§runtimepublished_object_keysdepends_on_skipped_cells§errored$f2ebc6fb-e07c-4922-897d-9bbe0f5fa1d0queued¤logsrunning¦outputbodyattributesstyle#display: flex; flex-direction: row;tagdivchildrenThe bisection width is:
$$\min_{S \subset V : \lfloor |V|/2 \rfloor \le |S| \le \lceil |V|/2 \rceil} \quad w(S, V \setminus S)$$
The bisection bandwidth is:
$$\min_{S \subset V : \lfloor |V|/2 \rfloor \le |S| \le \lceil |V|/2 \rceil} \quad \texttt{bw}(S, V \setminus S)$$
There are two protocols:
Rendezvous protocol
the sender sends a header;
the receiver returns a ‘ready-to-send’ message;
the sender sends the actual data.
Eager protocol the message is buffered so MPI_Send can return eagerly, before the receiver is even ready
Eager protocol is used if the data size is smaller than the eager limit. To force the rendezvous protocol, use MPI_Ssend.
mimetext/htmlrootassigneelast_run_timestampAڝrdpersist_js_state·has_pluto_hook_features§cell_id$4e32f7fb-cd5a-4190-9c92-ba4029313475depends_on_disabled_cells§runtimepublished_object_keysdepends_on_skipped_cells§errored$dbc19cbb-1349-4904-b655-2452aa7e2452queued¤logsrunning¦outputbodyattributesstyle&display: flex; flex-direction: column;tagdivchildren}Before
procid | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| $x_{1,1}$ | $x_{1,2}$ | $x_{1,3}$ | $x_{1,4}$ | |
| $x_{2,1}$ | $x_{2,2}$ | $x_{2,3}$ | $x_{2,4}$ | |
| $x_{3,1}$ | $x_{3,2}$ | $x_{3,3}$ | $x_{3,4}$ | |
| $x_{4,1}$ | $x_{4,2}$ | $x_{4,3}$ | $x_{4,4}$ |
After MPI_Reduce_scatter
procid | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| $x_{1,1} + \cdots + x_{1,4}$ | ||||
| $x_{2,1} + \cdots + x_{2,4}$ | ||||
| $x_{3,1} + \cdots + x_{3,4}$ | ||||
| $x_{4,1} + \cdots + x_{4,4}$ |
Before
procid | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| $x_1$ | $x_2$ | $x_3$ | $x_4$ |
After MPI_Allreduce
procid | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| $x_1 + \cdots + x_4$ | $x_1 + \cdots + x_4$ | $x_1 + \cdots + x_4$ | $x_1 + \cdots + x_4$ |
Special case of multidimensional array
How to order the nodes so that consecutive nodes in the order are adjacent in the graph ?
Map nodes to binary number and use Gray code. 
mimetext/htmlrootassigneelast_run_timestampAڝr
persist_js_state·has_pluto_hook_features§cell_id$3ec3c058-a94d-4717-b99f-66373f2fa31ddepends_on_disabled_cells§runtime ,published_object_keysdepends_on_skipped_cells§errored±cell_dependencies $c55dcd4a-8438-4679-9c4a-78cceec6835dprecedence_heuristic cell_id$c55dcd4a-8438-4679-9c4a-78cceec6835ddownstream_cells_mappath$e44b0038-d68f-4a49-9da2-67fbcbe098c3$fc705b81-7310-44cc-ad9f-dc2cf8a9b645upstream_cells_map Luxor.DrawinglinecircleBoolstrokepathcurveLuxor.finishPointsignLuxor.background-@drawLuxor.sethue+*Luxor.originmoveLuxor.previewLuxor$8df4ff2f-d176-4b4e-a525-665b5d07ea52$6be49c46-4900-4457-81b4-0704cd7da0afprecedence_heuristic cell_id$6be49c46-4900-4457-81b4-0704cd7da0afdownstream_cells_mapupstream_cells_map@md_strFoldablegetindex$c1285653-38ba-418b-bdf5-cda99440998dprecedence_heuristic cell_id$c1285653-38ba-418b-bdf5-cda99440998ddownstream_cells_mapupstream_cells_map@md_strasideFoldabletipgetindex$4fdb4cd6-a794-4b14-84b0-72f484c6ea86precedence_heuristic cell_id$4fdb4cd6-a794-4b14-84b0-72f484c6ea86downstream_cells_mapupstream_cells_map@md_strgetindex$a59db59c-d34e-4abd-8865-9907607e06a8precedence_heuristic cell_id$a59db59c-d34e-4abd-8865-9907607e06a8downstream_cells_mapupstream_cells_map@md_strasideciteintro$063f0acc-c023-46d0-9ed9-fbd7fbdcfa3bgetindex$5a566137-fbd1-45b2-9a55-e4aded366bb3precedence_heuristic cell_id$5a566137-fbd1-45b2-9a55-e4aded366bb3downstream_cells_mapupstream_cells_map@md_strgetindex$ad3559d1-6180-4eaa-b97d-3c1f10f036b9precedence_heuristic cell_id$ad3559d1-6180-4eaa-b97d-3c1f10f036b9downstream_cells_mapupstream_cells_map@md_strgetindex$88f33f35-d922-4d98-af4a-ebb79d9b7dc6precedence_heuristic cell_id$88f33f35-d922-4d98-af4a-ebb79d9b7dc6downstream_cells_mapmpicc_cmd$c0daf219-cb87-4203-b835-49ab7eb955beupstream_cells_map@md_strgetindex$b540d5e3-6686-479a-b2c7-c1f65b85b6baprecedence_heuristic cell_id$b540d5e3-6686-479a-b2c7-c1f65b85b6badownstream_cells_mapupstream_cells_map@md_strgetindex$f6f9447c-9bc9-432d-bd80-2c39f9d842f8precedence_heuristic cell_id$f6f9447c-9bc9-432d-bd80-2c39f9d842f8downstream_cells_mapupstream_cells_map=>img$7565e3da-84ce-42b6-8d4b-3615576f33b7$9a100ccf-1ad3-4d2c-bbe0-e297969eb69eprecedence_heuristic cell_id$9a100ccf-1ad3-4d2c-bbe0-e297969eb69edownstream_cells_mapupstream_cells_map@md_strgetindex$a1b2d090-d498-4d5d-90a0-8cdc648dc833precedence_heuristic cell_id$a1b2d090-d498-4d5d-90a0-8cdc648dc833downstream_cells_mapupstream_cells_map@md_strgetindex$8b83570a-6982-47e5-a167-a6d6afee0f7dprecedence_heuristic cell_id$8b83570a-6982-47e5-a167-a6d6afee0f7ddownstream_cells_mapupstream_cells_map@md_strhboxDictDiv=>getindex$e3474aea-ee14-4c78-ae46-5badc66a543aprecedence_heuristic cell_id$e3474aea-ee14-4c78-ae46-5badc66a543adownstream_cells_maplist_1$c0daf219-cb87-4203-b835-49ab7eb955beupstream_cells_map@md_strFoldablegetindex$21d507f6-02f8-4f8b-84f1-bcb84731df66precedence_heuristic cell_id$21d507f6-02f8-4f8b-84f1-bcb84731df66downstream_cells_mapupstream_cells_map@md_strgetindex$de72d596-0daf-4629-bbb5-20bb8a67cbedprecedence_heuristic cell_id$de72d596-0daf-4629-bbb5-20bb8a67cbeddownstream_cells_mapupstream_cells_map@md_strFoldablegetindex$c253bb24-ad76-4b58-8dfc-7dc2576e3db5precedence_heuristic cell_id$c253bb24-ad76-4b58-8dfc-7dc2576e3db5downstream_cells_mapupstream_cells_map@md_strgetindex$e4d1de1d-d57a-48ab-ad7a-c09b427daa03precedence_heuristic cell_id$e4d1de1d-d57a-48ab-ad7a-c09b427daa03downstream_cells_mapupstream_cells_map@md_strFoldableimg$7565e3da-84ce-42b6-8d4b-3615576f33b7getindex$133f4c7d-33e0-4e13-b716-f538125436caprecedence_heuristic cell_id$133f4c7d-33e0-4e13-b716-f538125436cadownstream_cells_mapupstream_cells_map@md_strimg1$1152dec8-3810-42b1-bb2a-8755dcaef56cTwoColumnWideLeftgetindex$3a50ca06-06e8-4a61-ade2-afbfc52ca655precedence_heuristic cell_id$3a50ca06-06e8-4a61-ade2-afbfc52ca655downstream_cells_mapupstream_cells_map@md_strasidecitepara$3e98c0ca-1b47-4631-83d7-cd0c8c0a431dgetindex$6c1984f6-4e36-4637-b0da-c7dd8b0f9ff0precedence_heuristic cell_id$6c1984f6-4e36-4637-b0da-c7dd8b0f9ff0downstream_cells_maplist_2$c0daf219-cb87-4203-b835-49ab7eb955beupstream_cells_map@md_strFoldablegetindex$de20bf96-7d33-4a78-8147-f0b7f8488e46precedence_heuristic cell_id$de20bf96-7d33-4a78-8147-f0b7f8488e46downstream_cells_mapupstream_cells_map@md_strFoldablegetindex$51d70f9a-cd67-44b9-8fd1-5ab70b526c7aprecedence_heuristic cell_id$51d70f9a-cd67-44b9-8fd1-5ab70b526c7adownstream_cells_mapupstream_cells_map@md_strgetindex$98392c40-6542-4a26-8552-c0960bbaa6a6precedence_heuristic cell_id$98392c40-6542-4a26-8552-c0960bbaa6a6downstream_cells_mapupstream_cells_map@md_strgetindex$39b055f5-3dbf-403c-b21e-210e3813d8b0precedence_heuristic cell_id$39b055f5-3dbf-403c-b21e-210e3813d8b0downstream_cells_mapupstream_cells_mapimg$7565e3da-84ce-42b6-8d4b-3615576f33b7$b0ca0392-71b8-4f44-8c6c-0978a02a0e6cprecedence_heuristic cell_id$b0ca0392-71b8-4f44-8c6c-0978a02a0e6cdownstream_cells_mapupstream_cells_mapExample$c45ff9b5-35d9-4a9d-a801-c762333a1f02compile_and_runprocname_num_processes$a103c5af-42fe-4f8c-b78c-6946895105d7$26aa369f-e5c7-4fe5-8b6b-903f4f4e91baprecedence_heuristic cell_id$26aa369f-e5c7-4fe5-8b6b-903f4f4e91badownstream_cells_mapupstream_cells_mapExample$c45ff9b5-35d9-4a9d-a801-c762333a1f02compile_and_run$a103c5af-42fe-4f8c-b78c-6946895105d7precedence_heuristic cell_id$a103c5af-42fe-4f8c-b78c-6946895105d7downstream_cells_mapprocname_num_processes$b0ca0392-71b8-4f44-8c6c-0978a02a0e6cupstream_cells_map@md_strCore:Base.get@bindSliderBasePlutoRunnerPlutoRunner.create_bondCore.applicablegetindex$d8bb1d43-bf42-4a09-bdeb-5db406ef1ccdprecedence_heuristic cell_id$d8bb1d43-bf42-4a09-bdeb-5db406ef1ccddownstream_cells_mapupstream_cells_mapDicthbox@md_strDiv=>img$7565e3da-84ce-42b6-8d4b-3615576f33b7getindex$82230d6c-25ce-4d12-8842-e0651fc4b143precedence_heuristic cell_id$82230d6c-25ce-4d12-8842-e0651fc4b143downstream_cells_mapupstream_cells_map@md_strgetindex$fc43b343-79cd-4342-8d80-8ea72cf34942precedence_heuristic cell_id$fc43b343-79cd-4342-8d80-8ea72cf34942downstream_cells_mapupstream_cells_map@md_strhboxDictDiv=>getindex$d2104fbd-ba22-4501-b03a-8809271d598bprecedence_heuristic cell_id$d2104fbd-ba22-4501-b03a-8809271d598bdownstream_cells_mapupstream_cells_map@md_strgetindex$8a527c17-bf2b-4e6b-937f-ef3a269c5112precedence_heuristic cell_id$8a527c17-bf2b-4e6b-937f-ef3a269c5112downstream_cells_mapupstream_cells_map=>img$7565e3da-84ce-42b6-8d4b-3615576f33b7$be0e3ba0-18cc-4b9a-a56d-2566f5148faeprecedence_heuristic cell_id$be0e3ba0-18cc-4b9a-a56d-2566f5148faedownstream_cells_mapupstream_cells_map@md_str=>img$7565e3da-84ce-42b6-8d4b-3615576f33b7getindex$2ff573a3-4a84-4497-9305-2d97e35e5e3dprecedence_heuristic cell_id$2ff573a3-4a84-4497-9305-2d97e35e5e3ddownstream_cells_mapupstream_cells_map@md_strFoldablegetindex$1b617828-e2b2-4a94-a120-59fa533d3e11precedence_heuristic cell_id$1b617828-e2b2-4a94-a120-59fa533d3e11downstream_cells_mapupstream_cells_map@md_strgetindex$c3590376-06ed-45a4-af0b-2d46f1a387c8precedence_heuristic cell_id$c3590376-06ed-45a4-af0b-2d46f1a387c8downstream_cells_mapupstream_cells_map@md_strhboxBase.getindex@c_strBaseDivDict=>$35ba1eea-56ae-4b74-af96-21ec5a93c455precedence_heuristic cell_id$35ba1eea-56ae-4b74-af96-21ec5a93c455downstream_cells_mapupstream_cells_map@md_strgetindex$488b0c17-4f0f-43bf-a16c-b9faa7ae0595precedence_heuristic cell_id$488b0c17-4f0f-43bf-a16c-b9faa7ae0595downstream_cells_mapupstream_cells_mapasideciteintro$063f0acc-c023-46d0-9ed9-fbd7fbdcfa3b$10a1b3a7-21c7-4f97-93e1-006ad3aea40dprecedence_heuristic cell_id$10a1b3a7-21c7-4f97-93e1-006ad3aea40ddownstream_cells_mapupstream_cells_map@md_strgetindex$b68eb860-a5b4-4e9e-9fbf-6eb6ce43ae69precedence_heuristic cell_id$b68eb860-a5b4-4e9e-9fbf-6eb6ce43ae69downstream_cells_mapupstream_cells_map@md_strFoldable=>img$7565e3da-84ce-42b6-8d4b-3615576f33b7getindex$3dc860be-016d-49ee-8535-7d9457c70f85precedence_heuristic cell_id$3dc860be-016d-49ee-8535-7d9457c70f85downstream_cells_mapupstream_cells_map@md_strFoldablegetindex$2e4dc3f9-a132-444f-a35d-f583823a7dfdprecedence_heuristic cell_id$2e4dc3f9-a132-444f-a35d-f583823a7dfddownstream_cells_mapupstream_cells_map@md_strFoldablegetindex$8981b5e2-2497-478e-ab28-a14b62f6f916precedence_heuristic cell_id$8981b5e2-2497-478e-ab28-a14b62f6f916downstream_cells_mapupstream_cells_mapruncmd_gen@cmd$34a10003-2c32-4332-b3e6-ce70eec0cbbeprecedence_heuristic cell_id$34a10003-2c32-4332-b3e6-ce70eec0cbbedownstream_cells_mapupstream_cells_map@md_strgetindex$a0566fdb-a08d-4bcf-9b2f-ed211c9f111fprecedence_heuristic cell_id$a0566fdb-a08d-4bcf-9b2f-ed211c9f111fdownstream_cells_mapupstream_cells_mapasideciteintro$063f0acc-c023-46d0-9ed9-fbd7fbdcfa3b$655e980d-b4e9-4f56-a5ae-380072242d27precedence_heuristic cell_id$655e980d-b4e9-4f56-a5ae-380072242d27downstream_cells_mapupstream_cells_maphboximg$7565e3da-84ce-42b6-8d4b-3615576f33b7$4788d8b4-2efa-4489-80c3-71f405513644precedence_heuristic cell_id$4788d8b4-2efa-4489-80c3-71f405513644downstream_cells_mapsum_num_processes$35aa1295-642f-4525-bf19-df2a42ff39d6upstream_cells_map@md_strCore:Base.get@bindSliderBasePlutoRunnerPlutoRunner.create_bondCore.applicablegetindex$233c13ff-f008-40b0-a6c5-c5395b2215ecprecedence_heuristic cell_id$233c13ff-f008-40b0-a6c5-c5395b2215ecdownstream_cells_mapupstream_cells_map@md_strFoldablegetindex$6fc34de1-469b-41a9-9677-ff3182f7a498precedence_heuristic cell_id$6fc34de1-469b-41a9-9677-ff3182f7a498downstream_cells_mapupstream_cells_map@md_strFoldablegetindex$b53ec488-ff25-4647-ab00-fbf90963a795precedence_heuristic cell_id$b53ec488-ff25-4647-ab00-fbf90963a795downstream_cells_mapupstream_cells_map@md_strgetindex$c3c848ff-526a-450d-9b1c-5d9d3ccccf28precedence_heuristic cell_id$c3c848ff-526a-450d-9b1c-5d9d3ccccf28downstream_cells_mapupstream_cells_map@md_strgetindex$063f0acc-c023-46d0-9ed9-fbd7fbdcfa3bprecedence_heuristic cell_id$063f0acc-c023-46d0-9ed9-fbd7fbdcfa3bdownstream_cells_mapciteintro$70e88569-cd5c-40e8-9198-6bf6578fb0a2$921b5a18-0733-4032-a543-9d60e254b1b2$d7117a24-aba6-4479-a40e-5005310a6b38$8f46daf1-9ca2-4a08-99aa-4ed68af218b8$a0566fdb-a08d-4bcf-9b2f-ed211c9f111f$61af27f1-9f83-42f1-a419-06d12ea62133$488b0c17-4f0f-43bf-a16c-b9faa7ae0595$16f8d28b-f201-4fe5-8446-68d7d9ddfb3c$a59db59c-d34e-4abd-8865-9907607e06a8$f2417047-33fc-4489-8e89-115bc6b46c13upstream_cells_map*$4569aa05-9963-4976-ac63-caf3f3979e83precedence_heuristic cell_id$4569aa05-9963-4976-ac63-caf3f3979e83downstream_cells_mapupstream_cells_map@md_strgetindex$7565e3da-84ce-42b6-8d4b-3615576f33b7precedence_heuristic cell_id$7565e3da-84ce-42b6-8d4b-3615576f33b7downstream_cells_mapsave_imagePath$7565e3da-84ce-42b6-8d4b-3615576f33b7imgpathURL$7565e3da-84ce-42b6-8d4b-3615576f33b7img $c04bcc96-e5fe-4d6e-a12e-40dcde58c62e$4e32f7fb-cd5a-4190-9c92-ba4029313475$b94cd399-0370-49e9-a522-056f3af22955$370f0f20-e373-4028-bca1-83e93678cbcb$0e640e07-82c7-4dab-a8f1-2f634bbebdea$8a527c17-bf2b-4e6b-937f-ef3a269c5112$39f48c25-6efb-4ff2-aedc-9d3e722dad24$55e96151-2aa1-4ea0-b672-2038c57d911e$be0e3ba0-18cc-4b9a-a56d-2566f5148fae$d8bb1d43-bf42-4a09-bdeb-5db406ef1ccd$091dd042-580b-4fda-8086-e048663aed6c$7fc70992-973a-43c6-904a-dd1b622a5ed8$23bfbe95-7ba2-41b9-bd8b-dc4baa3ad53a$39b055f5-3dbf-403c-b21e-210e3813d8b0$b68eb860-a5b4-4e9e-9fbf-6eb6ce43ae69$f6f9447c-9bc9-432d-bd80-2c39f9d842f8$1551122c-70ae-4e37-b3fb-4be91fcc4afb$655e980d-b4e9-4f56-a5ae-380072242d27$e4d1de1d-d57a-48ab-ad7a-c09b427daa03$4aac6ab5-053a-4f60-9e2e-e8d61ff0cecb$3ec3c058-a94d-4717-b99f-66373f2fa31d$1152dec8-3810-42b1-bb2a-8755dcaef56cupstream_cells_map !HypertextLiteral.BypassPlutoUI.LocalResourcePlutoUI$8df4ff2f-d176-4b4e-a525-665b5d07ea52joinpathHypertextLiteral.contentstartswithStringendPlutoTeachingTools$8df4ff2f-d176-4b4e-a525-665b5d07ea52@htlHypertextLiteral.attribute_pair&PlutoTeachingTools.RobustLocalResourcePath$7565e3da-84ce-42b6-8d4b-3615576f33b7HypertextLiteral.ResultHypertextLiteral$8df4ff2f-d176-4b4e-a525-665b5d07ea52URL$7565e3da-84ce-42b6-8d4b-3615576f33b7*@__DIR__insplit$7fc70992-973a-43c6-904a-dd1b622a5ed8precedence_heuristic cell_id$7fc70992-973a-43c6-904a-dd1b622a5ed8downstream_cells_mapupstream_cells_map@md_strFoldable=>img$7565e3da-84ce-42b6-8d4b-3615576f33b7getindex$fa024a5d-52a6-459d-894d-13a60ec723d2precedence_heuristic cell_id$fa024a5d-52a6-459d-894d-13a60ec723d2downstream_cells_mapupstream_cells_map@md_strFoldablegetindex$f7f097cb-d7bd-49eb-a030-ac26f8f61a67precedence_heuristic cell_id$f7f097cb-d7bd-49eb-a030-ac26f8f61a67downstream_cells_mapupstream_cells_map@md_strgetindex$3a2bfd4e-0ce6-4a79-a578-fc1b4ef563c5precedence_heuristic cell_id$3a2bfd4e-0ce6-4a79-a578-fc1b4ef563c5downstream_cells_mapupstream_cells_map@md_strFoldablegetindex$a79c410a-bebf-434c-9730-568e0ff4f4c7precedence_heuristic cell_id$a79c410a-bebf-434c-9730-568e0ff4f4c7downstream_cells_mapupstream_cells_map@md_strgetindex$7cf59087-efca-4f03-90dc-f2acefdcbc8aprecedence_heuristic cell_id$7cf59087-efca-4f03-90dc-f2acefdcbc8adownstream_cells_mapupstream_cells_map@md_strgetindex$5d72bf87-7f3a-4229-9d7a-2e63c115087dprecedence_heuristic cell_id$5d72bf87-7f3a-4229-9d7a-2e63c115087ddownstream_cells_mapupstream_cells_map@md_strFoldablegetindex$e796b093-9c1d-4656-9acb-918de53f7e4dprecedence_heuristic cell_id$e796b093-9c1d-4656-9acb-918de53f7e4ddownstream_cells_mapupstream_cells_map@md_strgetindex$954f1ab1-1e2f-458b-96d7-a1746631fac7precedence_heuristic cell_id$954f1ab1-1e2f-458b-96d7-a1746631fac7downstream_cells_maptree$1bac238f-79c8-4f9f-a187-bacb288de3b0upstream_cells_map Luxor.DrawinglinecircleLuxor.finishPointsignLuxor.background-@drawLuxor.sethue+*Luxor.origintextLuxor.previewLuxor$8df4ff2f-d176-4b4e-a525-665b5d07ea52$a771f33f-7ed1-41aa-bee0-c215729a8c8dprecedence_heuristic cell_id$a771f33f-7ed1-41aa-bee0-c215729a8c8ddownstream_cells_mapupstream_cells_map@md_strgetindex$8da580fe-6b56-4d8f-ad43-aed7b728a06eprecedence_heuristic cell_id$8da580fe-6b56-4d8f-ad43-aed7b728a06edownstream_cells_mapupstream_cells_map@md_strgetindex$39f48c25-6efb-4ff2-aedc-9d3e722dad24precedence_heuristic cell_id$39f48c25-6efb-4ff2-aedc-9d3e722dad24downstream_cells_mapupstream_cells_map@md_str=>img$7565e3da-84ce-42b6-8d4b-3615576f33b7getindex$e119c2d3-1e24-464f-b812-62f28c00a913precedence_heuristic cell_id$e119c2d3-1e24-464f-b812-62f28c00a913downstream_cells_mapupstream_cells_map@md_strgetindex$a258eec9-f4f6-49bd-8470-8541836f5f6bprecedence_heuristic cell_id$a258eec9-f4f6-49bd-8470-8541836f5f6bdownstream_cells_mapupstream_cells_map@md_strhboxDictDiv=>getindex$79b405a5-54b5-4727-a0cd-b79522ad109fprecedence_heuristic cell_id$79b405a5-54b5-4727-a0cd-b79522ad109fdownstream_cells_mapupstream_cells_map@md_strgetindex$93f0c63c-b597-4f89-809c-7af0476f319aprecedence_heuristic cell_id$93f0c63c-b597-4f89-809c-7af0476f319adownstream_cells_mapupstream_cells_map@md_strgetindex$944d827e-bc6a-4de8-b959-5fde8790bedcprecedence_heuristic cell_id$944d827e-bc6a-4de8-b959-5fde8790bedcdownstream_cells_mapupstream_cells_map@md_strgetindex$c04bcc96-e5fe-4d6e-a12e-40dcde58c62eprecedence_heuristic cell_id$c04bcc96-e5fe-4d6e-a12e-40dcde58c62edownstream_cells_mapupstream_cells_map@md_str=>img$7565e3da-84ce-42b6-8d4b-3615576f33b7getindex$c420ad25-6af1-4fb4-823a-b6bbd4e10f7fprecedence_heuristic cell_id$c420ad25-6af1-4fb4-823a-b6bbd4e10f7fdownstream_cells_mapupstream_cells_map@md_strhboxDictDiv=>getindex$a6c337c4-0c81-4463-ad4f-9a4528d953abprecedence_heuristic cell_id$a6c337c4-0c81-4463-ad4f-9a4528d953abdownstream_cells_mapupstream_cells_map@md_strgetindex$921b5a18-0733-4032-a543-9d60e254b1b2precedence_heuristic cell_id$921b5a18-0733-4032-a543-9d60e254b1b2downstream_cells_mapupstream_cells_map@md_strciteintro$063f0acc-c023-46d0-9ed9-fbd7fbdcfa3bgetindex$2257220c-6f0e-4edf-9fea-7e388b84df9bprecedence_heuristic cell_id$2257220c-6f0e-4edf-9fea-7e388b84df9bdownstream_cells_mapupstream_cells_map@md_strgetindex$c45ff9b5-35d9-4a9d-a801-c762333a1f02precedence_heuristic cell_id$c45ff9b5-35d9-4a9d-a801-c762333a1f02downstream_cells_mapExample$b0ca0392-71b8-4f44-8c6c-0978a02a0e6c$35aa1295-642f-4525-bf19-df2a42ff39d6$ce7bf747-7116-4e76-9004-f234317046c3$26aa369f-e5c7-4fe5-8b6b-903f4f4e91ba$c45ff9b5-35d9-4a9d-a801-c762333a1f02SimpleClang.compile_libcodeSimpleClang.compile_and_run$c45ff9b5-35d9-4a9d-a801-c762333a1f02upstream_cells_mapsplitCCodedirnamejoinpathExample$c45ff9b5-35d9-4a9d-a801-c762333a1f02errorStringSimpleClang.compile_and_run$c45ff9b5-35d9-4a9d-a801-c762333a1f02endSimpleClang$8df4ff2f-d176-4b4e-a525-665b5d07ea52@__DIR__==CppCodeCLCoderead$4aac6ab5-053a-4f60-9e2e-e8d61ff0cecbprecedence_heuristic cell_id$4aac6ab5-053a-4f60-9e2e-e8d61ff0cecbdownstream_cells_mapupstream_cells_map=>img$7565e3da-84ce-42b6-8d4b-3615576f33b7$61af27f1-9f83-42f1-a419-06d12ea62133precedence_heuristic cell_id$61af27f1-9f83-42f1-a419-06d12ea62133downstream_cells_mapupstream_cells_mapasideciteintro$063f0acc-c023-46d0-9ed9-fbd7fbdcfa3b$52d428d5-cb33-4f2a-89eb-3a8ce3f5bb81precedence_heuristic cell_id$52d428d5-cb33-4f2a-89eb-3a8ce3f5bb81downstream_cells_mapupstream_cells_map@md_strFoldablegetindex$d7e31ced-4eb2-4221-b83f-462e8f32fe89precedence_heuristic cell_id$d7e31ced-4eb2-4221-b83f-462e8f32fe89downstream_cells_mapupstream_cells_map@md_strasideFoldablegetindex$2c84bd84-b54d-4594-b9f8-35db2124d7e8precedence_heuristic cell_id$2c84bd84-b54d-4594-b9f8-35db2124d7e8downstream_cells_mapupstream_cells_map@md_strgetindex$32f740e7-9338-4c42-8eaf-ce8022412c50precedence_heuristic cell_id$32f740e7-9338-4c42-8eaf-ce8022412c50downstream_cells_mapupstream_cells_map@md_strgetindex$db16e939-b490-497b-a03f-80ce2e8485afprecedence_heuristic cell_id$db16e939-b490-497b-a03f-80ce2e8485afdownstream_cells_mapupstream_cells_map@md_strFoldablegetindex$7d37fbea-baa3-43ec-b003-a4707017a4cfprecedence_heuristic cell_id$7d37fbea-baa3-43ec-b003-a4707017a4cfdownstream_cells_mapupstream_cells_map@md_strgetindex$568057f5-b0b8-4225-8e4b-5eec911a52efprecedence_heuristic cell_id$568057f5-b0b8-4225-8e4b-5eec911a52efdownstream_cells_mapupstream_cells_map@md_strgetindex$370f0f20-e373-4028-bca1-83e93678cbcbprecedence_heuristic cell_id$370f0f20-e373-4028-bca1-83e93678cbcbdownstream_cells_mapupstream_cells_mapimg$7565e3da-84ce-42b6-8d4b-3615576f33b7$1bac238f-79c8-4f9f-a187-bacb288de3b0precedence_heuristic cell_id$1bac238f-79c8-4f9f-a187-bacb288de3b0downstream_cells_mapupstream_cells_maptree$954f1ab1-1e2f-458b-96d7-a1746631fac7$40606ee3-38cc-4123-9b86-b774bf89e499precedence_heuristic cell_id$40606ee3-38cc-4123-9b86-b774bf89e499downstream_cells_mapupstream_cells_map@md_strgetindex$8df4ff2f-d176-4b4e-a525-665b5d07ea52precedence_heuristiccell_id$8df4ff2f-d176-4b4e-a525-665b5d07ea52downstream_cells_mapStaticArraysSimpleClang$c45ff9b5-35d9-4a9d-a801-c762333a1f02PlutoUI$58e12afd-6eb0-4731-bd57-d9ae7ab4e164$7565e3da-84ce-42b6-8d4b-3615576f33b7HypertextLiteral$58e12afd-6eb0-4731-bd57-d9ae7ab4e164$7565e3da-84ce-42b6-8d4b-3615576f33b7ExperimentalLayoutBenchmarkToolsMarkdown$e172f5c5-8b96-4efd-9cf3-805c58d1a6a3Luxor$c55dcd4a-8438-4679-9c4a-78cceec6835d$954f1ab1-1e2f-458b-96d7-a1746631fac7PlutoTeachingTools$58e12afd-6eb0-4731-bd57-d9ae7ab4e164$7565e3da-84ce-42b6-8d4b-3615576f33b7upstream_cells_map$23bfbe95-7ba2-41b9-bd8b-dc4baa3ad53aprecedence_heuristic cell_id$23bfbe95-7ba2-41b9-bd8b-dc4baa3ad53adownstream_cells_mapupstream_cells_map@md_strFoldable=>img$7565e3da-84ce-42b6-8d4b-3615576f33b7getindex$49b596b8-891d-4f3f-a6a4-a62cc8237df3precedence_heuristic cell_id$49b596b8-891d-4f3f-a6a4-a62cc8237df3downstream_cells_mapupstream_cells_map@md_strdefinition$e172f5c5-8b96-4efd-9cf3-805c58d1a6a3getindex$cf799c26-1cea-4b38-9a15-8497813bd668precedence_heuristic cell_id$cf799c26-1cea-4b38-9a15-8497813bd668downstream_cells_mapupstream_cells_map@md_strgetindex$70e88569-cd5c-40e8-9198-6bf6578fb0a2precedence_heuristic cell_id$70e88569-cd5c-40e8-9198-6bf6578fb0a2downstream_cells_mapupstream_cells_map@md_strciteintro$063f0acc-c023-46d0-9ed9-fbd7fbdcfa3bgetindex$5441e428-b320-433c-acde-15fe6bf58537precedence_heuristic cell_id$5441e428-b320-433c-acde-15fe6bf58537downstream_cells_mapupstream_cells_mapruncmd_gen@cmd$bfab5c2d-61c3-468b-9ddf-4aaa49cb7785precedence_heuristic cell_id$bfab5c2d-61c3-468b-9ddf-4aaa49cb7785downstream_cells_mapupstream_cells_map@md_strgetindex$7d9ac5f9-39bf-4052-ad8a-ac0fec15c64aprecedence_heuristic cell_id$7d9ac5f9-39bf-4052-ad8a-ac0fec15c64adownstream_cells_mapupstream_cells_map@md_strgetindex$86394e1c-0ff4-449a-8940-4b5906d8b6f0precedence_heuristic cell_id$86394e1c-0ff4-449a-8940-4b5906d8b6f0downstream_cells_mapupstream_cells_map@md_strFoldablegetindex$97d3cf3f-ddac-4850-8b05-bdc0c4741f61precedence_heuristic cell_id$97d3cf3f-ddac-4850-8b05-bdc0c4741f61downstream_cells_mapupstream_cells_map@md_strFoldablegetindex$b9a9e335-1328-4c63-a213-ce21263bc201precedence_heuristic cell_id$b9a9e335-1328-4c63-a213-ce21263bc201downstream_cells_mapupstream_cells_map@md_strFoldablegetindex$9b4cae31-c319-444e-98c8-2c0bfc6dfa0cprecedence_heuristic cell_id$9b4cae31-c319-444e-98c8-2c0bfc6dfa0cdownstream_cells_mapupstream_cells_map@md_strgetindex$7b1d26c6-9499-4e44-84c8-c272737a175eprecedence_heuristic cell_id$7b1d26c6-9499-4e44-84c8-c272737a175edownstream_cells_mapupstream_cells_map@md_strgetindex$360091c4-d3a0-462d-abcf-b9bbb9480871precedence_heuristic cell_id$360091c4-d3a0-462d-abcf-b9bbb9480871downstream_cells_mapupstream_cells_map@md_strgetindex$f2417047-33fc-4489-8e89-115bc6b46c13precedence_heuristic cell_id$f2417047-33fc-4489-8e89-115bc6b46c13downstream_cells_mapupstream_cells_map@md_strasideciteintro$063f0acc-c023-46d0-9ed9-fbd7fbdcfa3bgetindex$1152dec8-3810-42b1-bb2a-8755dcaef56cprecedence_heuristic cell_id$1152dec8-3810-42b1-bb2a-8755dcaef56cdownstream_cells_mapimg1$133f4c7d-33e0-4e13-b716-f538125436caupstream_cells_mapimg$7565e3da-84ce-42b6-8d4b-3615576f33b7$8f46daf1-9ca2-4a08-99aa-4ed68af218b8precedence_heuristic cell_id$8f46daf1-9ca2-4a08-99aa-4ed68af218b8downstream_cells_mapupstream_cells_mapasideciteintro$063f0acc-c023-46d0-9ed9-fbd7fbdcfa3b$143dca7c-f9a4-472a-a4bc-4578e4e8413bprecedence_heuristic cell_id$143dca7c-f9a4-472a-a4bc-4578e4e8413bdownstream_cells_mapupstream_cells_map@md_strgetindex$c0daf219-cb87-4203-b835-49ab7eb955beprecedence_heuristic cell_id$c0daf219-cb87-4203-b835-49ab7eb955bedownstream_cells_mapupstream_cells_map@md_strgetindexlist_2$6c1984f6-4e36-4637-b0da-c7dd8b0f9ff0list_1$e3474aea-ee14-4c78-ae46-5badc66a543ampicc_cmd$88f33f35-d922-4d98-af4a-ebb79d9b7dc6$d04b9af5-f004-4ca4-b1c9-2c86d46cb37dprecedence_heuristic cell_id$d04b9af5-f004-4ca4-b1c9-2c86d46cb37ddownstream_cells_mapupstream_cells_map@md_strgetindex$fc705b81-7310-44cc-ad9f-dc2cf8a9b645precedence_heuristic cell_id$fc705b81-7310-44cc-ad9f-dc2cf8a9b645downstream_cells_mapupstream_cells_mappath$c55dcd4a-8438-4679-9c4a-78cceec6835d$6d2b3dbc-0686-49f0-904a-56c3ce63b4ddprecedence_heuristic cell_id$6d2b3dbc-0686-49f0-904a-56c3ce63b4dddownstream_cells_mapupstream_cells_map@md_strhboxBase.getindex@c_strBaseDivDict=>$e172f5c5-8b96-4efd-9cf3-805c58d1a6a3precedence_heuristic cell_id$e172f5c5-8b96-4efd-9cf3-805c58d1a6a3downstream_cells_mapdefinition$49b596b8-891d-4f3f-a6a4-a62cc8237df3upstream_cells_mapMarkdown.AdmonitionMarkdown.MDMarkdown$8df4ff2f-d176-4b4e-a525-665b5d07ea52$ce7bf747-7116-4e76-9004-f234317046c3precedence_heuristic cell_id$ce7bf747-7116-4e76-9004-f234317046c3downstream_cells_mapupstream_cells_mapExample$c45ff9b5-35d9-4a9d-a801-c762333a1f02compile_and_run$d722a86d-6d51-4d91-ac22-53af94c91497precedence_heuristic cell_id$d722a86d-6d51-4d91-ac22-53af94c91497downstream_cells_mapupstream_cells_map@md_strBase.getindex@c_strBaseDictvboxDiv=>$273ad3a6-cb32-49bb-8702-fdaf8597e812precedence_heuristic cell_id$273ad3a6-cb32-49bb-8702-fdaf8597e812downstream_cells_mapupstream_cells_map@md_strgetindex$6041a909-d26c-4ab1-836b-29953c578759precedence_heuristic cell_id$6041a909-d26c-4ab1-836b-29953c578759downstream_cells_mapupstream_cells_map@md_strFoldablegetindex$b94cd399-0370-49e9-a522-056f3af22955precedence_heuristic cell_id$b94cd399-0370-49e9-a522-056f3af22955downstream_cells_mapupstream_cells_mapimg$7565e3da-84ce-42b6-8d4b-3615576f33b7$58e12afd-6eb0-4731-bd57-d9ae7ab4e164precedence_heuristic cell_id$58e12afd-6eb0-4731-bd57-d9ae7ab4e164downstream_cells_mapupstream_cells_mapPlutoTeachingTools$8df4ff2f-d176-4b4e-a525-665b5d07ea52PlutoUI$8df4ff2f-d176-4b4e-a525-665b5d07ea52HypertextLiteral.ResultHypertextLiteral$8df4ff2f-d176-4b4e-a525-665b5d07ea52HypertextLiteral.BypassHypertextLiteral.content$PlutoTeachingTools.ChooseDisplayMode@htlPlutoUI.TableOfContents$141d162c-c817-498f-be16-f1cd35d82487precedence_heuristic cell_id$141d162c-c817-498f-be16-f1cd35d82487downstream_cells_mapupstream_cells_map@md_strFoldablegetindex$e44b0038-d68f-4a49-9da2-67fbcbe098c3precedence_heuristic cell_id$e44b0038-d68f-4a49-9da2-67fbcbe098c3downstream_cells_mapupstream_cells_mappath$c55dcd4a-8438-4679-9c4a-78cceec6835d$b5a3e471-af4a-466f-bbae-96306bcc7563precedence_heuristic cell_id$b5a3e471-af4a-466f-bbae-96306bcc7563downstream_cells_mapupstream_cells_map@md_strBase.getindex@c_strBaseDictvboxDiv=>$21b6133f-db59-4885-9b3d-331c3d6ef306precedence_heuristic cell_id$21b6133f-db59-4885-9b3d-331c3d6ef306downstream_cells_mapupstream_cells_map@md_strgetindex$beee4908-d519-413a-964f-149bb82cdbb8precedence_heuristic cell_id$beee4908-d519-413a-964f-149bb82cdbb8downstream_cells_mapupstream_cells_map@md_strgetindex$091dd042-580b-4fda-8086-e048663aed6cprecedence_heuristic cell_id$091dd042-580b-4fda-8086-e048663aed6cdownstream_cells_mapupstream_cells_map@md_str=>img$7565e3da-84ce-42b6-8d4b-3615576f33b7getindex$60bc118f-6795-43f9-97a2-865fd1704895precedence_heuristic cell_id$60bc118f-6795-43f9-97a2-865fd1704895downstream_cells_mapupstream_cells_map@md_strgetindex$16f8d28b-f201-4fe5-8446-68d7d9ddfb3cprecedence_heuristic cell_id$16f8d28b-f201-4fe5-8446-68d7d9ddfb3cdownstream_cells_mapupstream_cells_mapasideciteintro$063f0acc-c023-46d0-9ed9-fbd7fbdcfa3b$35aa1295-642f-4525-bf19-df2a42ff39d6precedence_heuristic cell_id$35aa1295-642f-4525-bf19-df2a42ff39d6downstream_cells_mapupstream_cells_mapExample$c45ff9b5-35d9-4a9d-a801-c762333a1f02sum_num_processes$4788d8b4-2efa-4489-80c3-71f405513644compile_and_run$e832ce25-94e2-4743-854d-02b52cc7b56dprecedence_heuristic cell_id$e832ce25-94e2-4743-854d-02b52cc7b56ddownstream_cells_mapupstream_cells_map@md_strasideFoldablegetindex$9612a1ef-fd3a-4a58-87b0-b2255ac86331precedence_heuristic cell_id$9612a1ef-fd3a-4a58-87b0-b2255ac86331downstream_cells_mapupstream_cells_map@md_strgetindex$d7117a24-aba6-4479-a40e-5005310a6b38precedence_heuristic cell_id$d7117a24-aba6-4479-a40e-5005310a6b38downstream_cells_mapupstream_cells_mapasideciteintro$063f0acc-c023-46d0-9ed9-fbd7fbdcfa3b$0e640e07-82c7-4dab-a8f1-2f634bbebdeaprecedence_heuristic cell_id$0e640e07-82c7-4dab-a8f1-2f634bbebdeadownstream_cells_mapupstream_cells_maphbox=>img$7565e3da-84ce-42b6-8d4b-3615576f33b7$f2ebc6fb-e07c-4922-897d-9bbe0f5fa1d0precedence_heuristic cell_id$f2ebc6fb-e07c-4922-897d-9bbe0f5fa1d0downstream_cells_mapupstream_cells_mapDictBase.getindexhbox@md_str@html_strDivBaseBase.Docs.HTML=>$55e96151-2aa1-4ea0-b672-2038c57d911eprecedence_heuristic cell_id$55e96151-2aa1-4ea0-b672-2038c57d911edownstream_cells_mapupstream_cells_mapaside=>img$7565e3da-84ce-42b6-8d4b-3615576f33b7$67dee339-98b4-4714-88b2-8098a13235f2precedence_heuristic cell_id$67dee339-98b4-4714-88b2-8098a13235f2downstream_cells_mapupstream_cells_map@md_strgetindex$4e32f7fb-cd5a-4190-9c92-ba4029313475precedence_heuristic cell_id$4e32f7fb-cd5a-4190-9c92-ba4029313475downstream_cells_mapupstream_cells_mapimg$7565e3da-84ce-42b6-8d4b-3615576f33b7$dbc19cbb-1349-4904-b655-2452aa7e2452precedence_heuristic cell_id$dbc19cbb-1349-4904-b655-2452aa7e2452downstream_cells_mapupstream_cells_map@md_strvboxgetindex$0d69e94b-492a-4acc-adba-a2126b871724precedence_heuristic cell_id$0d69e94b-492a-4acc-adba-a2126b871724downstream_cells_mapupstream_cells_map@md_strvboxgetindex$4309dc43-aeb8-4ec7-94fe-0e320b784349precedence_heuristic cell_id$4309dc43-aeb8-4ec7-94fe-0e320b784349downstream_cells_mapupstream_cells_map@md_strgetindex$1551122c-70ae-4e37-b3fb-4be91fcc4afbprecedence_heuristic cell_id$1551122c-70ae-4e37-b3fb-4be91fcc4afbdownstream_cells_mapupstream_cells_map@md_strFoldable=>img$7565e3da-84ce-42b6-8d4b-3615576f33b7getindex$3e98c0ca-1b47-4631-83d7-cd0c8c0a431dprecedence_heuristic cell_id$3e98c0ca-1b47-4631-83d7-cd0c8c0a431ddownstream_cells_mapcitepara$3a50ca06-06e8-4a61-ade2-afbfc52ca655upstream_cells_map*$3ec3c058-a94d-4717-b99f-66373f2fa31dprecedence_heuristic cell_id$3ec3c058-a94d-4717-b99f-66373f2fa31ddownstream_cells_mapupstream_cells_mapimg$7565e3da-84ce-42b6-8d4b-3615576f33b7cell_execution_order $8df4ff2f-d176-4b4e-a525-665b5d07ea52$58e12afd-6eb0-4731-bd57-d9ae7ab4e164$bfab5c2d-61c3-468b-9ddf-4aaa49cb7785$063f0acc-c023-46d0-9ed9-fbd7fbdcfa3b$3e98c0ca-1b47-4631-83d7-cd0c8c0a431d$5a566137-fbd1-45b2-9a55-e4aded366bb3$a6c337c4-0c81-4463-ad4f-9a4528d953ab$cf799c26-1cea-4b38-9a15-8497813bd668$6d2b3dbc-0686-49f0-904a-56c3ce63b4dd$b5a3e471-af4a-466f-bbae-96306bcc7563$d722a86d-6d51-4d91-ac22-53af94c91497$c3590376-06ed-45a4-af0b-2d46f1a387c8$52d428d5-cb33-4f2a-89eb-3a8ce3f5bb81$273ad3a6-cb32-49bb-8702-fdaf8597e812$82230d6c-25ce-4d12-8842-e0651fc4b143$7d9ac5f9-39bf-4052-ad8a-ac0fec15c64a$a103c5af-42fe-4f8c-b78c-6946895105d7$21b6133f-db59-4885-9b3d-331c3d6ef306$35ba1eea-56ae-4b74-af96-21ec5a93c455$8981b5e2-2497-478e-ab28-a14b62f6f916$5441e428-b320-433c-acde-15fe6bf58537$70e88569-cd5c-40e8-9198-6bf6578fb0a2$40606ee3-38cc-4123-9b86-b774bf89e499$9b4cae31-c319-444e-98c8-2c0bfc6dfa0c$8b83570a-6982-47e5-a167-a6d6afee0f7d$5d72bf87-7f3a-4229-9d7a-2e63c115087d$7b1d26c6-9499-4e44-84c8-c272737a175e$fc43b343-79cd-4342-8d80-8ea72cf34942$233c13ff-f008-40b0-a6c5-c5395b2215ec$ad3559d1-6180-4eaa-b97d-3c1f10f036b9$c420ad25-6af1-4fb4-823a-b6bbd4e10f7f$db16e939-b490-497b-a03f-80ce2e8485af$4fdb4cd6-a794-4b14-84b0-72f484c6ea86$a258eec9-f4f6-49bd-8470-8541836f5f6b$6fc34de1-469b-41a9-9677-ff3182f7a498$de20bf96-7d33-4a78-8147-f0b7f8488e46$e119c2d3-1e24-464f-b812-62f28c00a913$dbc19cbb-1349-4904-b655-2452aa7e2452$2ff573a3-4a84-4497-9305-2d97e35e5e3d$6be49c46-4900-4457-81b4-0704cd7da0af$60bc118f-6795-43f9-97a2-865fd1704895$0d69e94b-492a-4acc-adba-a2126b871724$b9a9e335-1328-4c63-a213-ce21263bc201$a1b2d090-d498-4d5d-90a0-8cdc648dc833$a771f33f-7ed1-41aa-bee0-c215729a8c8d$141d162c-c817-498f-be16-f1cd35d82487$7cf59087-efca-4f03-90dc-f2acefdcbc8a$4788d8b4-2efa-4489-80c3-71f405513644$e832ce25-94e2-4743-854d-02b52cc7b56d$79b405a5-54b5-4727-a0cd-b79522ad109f$d2104fbd-ba22-4501-b03a-8809271d598b$4569aa05-9963-4976-ac63-caf3f3979e83$34a10003-2c32-4332-b3e6-ce70eec0cbbe$d7e31ced-4eb2-4221-b83f-462e8f32fe89$c3c848ff-526a-450d-9b1c-5d9d3ccccf28$67dee339-98b4-4714-88b2-8098a13235f2$3a50ca06-06e8-4a61-ade2-afbfc52ca655$32f740e7-9338-4c42-8eaf-ce8022412c50$93f0c63c-b597-4f89-809c-7af0476f319a$568057f5-b0b8-4225-8e4b-5eec911a52ef$a79c410a-bebf-434c-9730-568e0ff4f4c7$c1285653-38ba-418b-bdf5-cda99440998d$88f33f35-d922-4d98-af4a-ebb79d9b7dc6$e3474aea-ee14-4c78-ae46-5badc66a543a$6c1984f6-4e36-4637-b0da-c7dd8b0f9ff0$c0daf219-cb87-4203-b835-49ab7eb955be$51d70f9a-cd67-44b9-8fd1-5ab70b526c7a$944d827e-bc6a-4de8-b959-5fde8790bedc$3a2bfd4e-0ce6-4a79-a578-fc1b4ef563c5$beee4908-d519-413a-964f-149bb82cdbb8$b540d5e3-6686-479a-b2c7-c1f65b85b6ba$9a100ccf-1ad3-4d2c-bbe0-e297969eb69e$921b5a18-0733-4032-a543-9d60e254b1b2$9612a1ef-fd3a-4a58-87b0-b2255ac86331$98392c40-6542-4a26-8552-c0960bbaa6a6$c253bb24-ad76-4b58-8dfc-7dc2576e3db5$1b617828-e2b2-4a94-a120-59fa533d3e11$f2ebc6fb-e07c-4922-897d-9bbe0f5fa1d0$8da580fe-6b56-4d8f-ad43-aed7b728a06e$fa024a5d-52a6-459d-894d-13a60ec723d2$360091c4-d3a0-462d-abcf-b9bbb9480871$3dc860be-016d-49ee-8535-7d9457c70f85$c55dcd4a-8438-4679-9c4a-78cceec6835d$e44b0038-d68f-4a49-9da2-67fbcbe098c3$7d37fbea-baa3-43ec-b003-a4707017a4cf$fc705b81-7310-44cc-ad9f-dc2cf8a9b645$86394e1c-0ff4-449a-8940-4b5906d8b6f0$d7117a24-aba6-4479-a40e-5005310a6b38$2257220c-6f0e-4edf-9fea-7e388b84df9b$2e4dc3f9-a132-444f-a35d-f583823a7dfd$8f46daf1-9ca2-4a08-99aa-4ed68af218b8$2c84bd84-b54d-4594-b9f8-35db2124d7e8$4309dc43-aeb8-4ec7-94fe-0e320b784349$a0566fdb-a08d-4bcf-9b2f-ed211c9f111f$e796b093-9c1d-4656-9acb-918de53f7e4d$d04b9af5-f004-4ca4-b1c9-2c86d46cb37d$97d3cf3f-ddac-4850-8b05-bdc0c4741f61$61af27f1-9f83-42f1-a419-06d12ea62133$143dca7c-f9a4-472a-a4bc-4578e4e8413b$954f1ab1-1e2f-458b-96d7-a1746631fac7$1bac238f-79c8-4f9f-a187-bacb288de3b0$21d507f6-02f8-4f8b-84f1-bcb84731df66$b53ec488-ff25-4647-ab00-fbf90963a795$de72d596-0daf-4629-bbb5-20bb8a67cbed$488b0c17-4f0f-43bf-a16c-b9faa7ae0595$10a1b3a7-21c7-4f97-93e1-006ad3aea40d$f7f097cb-d7bd-49eb-a030-ac26f8f61a67$6041a909-d26c-4ab1-836b-29953c578759$16f8d28b-f201-4fe5-8446-68d7d9ddfb3c$a59db59c-d34e-4abd-8865-9907607e06a8$f2417047-33fc-4489-8e89-115bc6b46c13$7565e3da-84ce-42b6-8d4b-3615576f33b7$c04bcc96-e5fe-4d6e-a12e-40dcde58c62e$4e32f7fb-cd5a-4190-9c92-ba4029313475$b94cd399-0370-49e9-a522-056f3af22955$370f0f20-e373-4028-bca1-83e93678cbcb$0e640e07-82c7-4dab-a8f1-2f634bbebdea$8a527c17-bf2b-4e6b-937f-ef3a269c5112$39f48c25-6efb-4ff2-aedc-9d3e722dad24$55e96151-2aa1-4ea0-b672-2038c57d911e$be0e3ba0-18cc-4b9a-a56d-2566f5148fae$d8bb1d43-bf42-4a09-bdeb-5db406ef1ccd$091dd042-580b-4fda-8086-e048663aed6c$7fc70992-973a-43c6-904a-dd1b622a5ed8$23bfbe95-7ba2-41b9-bd8b-dc4baa3ad53a$39b055f5-3dbf-403c-b21e-210e3813d8b0$b68eb860-a5b4-4e9e-9fbf-6eb6ce43ae69$f6f9447c-9bc9-432d-bd80-2c39f9d842f8$1551122c-70ae-4e37-b3fb-4be91fcc4afb$655e980d-b4e9-4f56-a5ae-380072242d27$e4d1de1d-d57a-48ab-ad7a-c09b427daa03$4aac6ab5-053a-4f60-9e2e-e8d61ff0cecb$3ec3c058-a94d-4717-b99f-66373f2fa31d$1152dec8-3810-42b1-bb2a-8755dcaef56c$133f4c7d-33e0-4e13-b716-f538125436ca$c45ff9b5-35d9-4a9d-a801-c762333a1f02$b0ca0392-71b8-4f44-8c6c-0978a02a0e6c$35aa1295-642f-4525-bf19-df2a42ff39d6$ce7bf747-7116-4e76-9004-f234317046c3$26aa369f-e5c7-4fe5-8b6b-903f4f4e91ba$e172f5c5-8b96-4efd-9cf3-805c58d1a6a3$49b596b8-891d-4f3f-a6a4-a62cc8237df3last_hot_reload_time shortpath3_mpi.jlprocess_statusreadypath7/home/runner/work/LINMA2710/LINMA2710/Lectures/3_mpi.jlpluto_versionv1.0.3last_save_timeAڝr㬪cell_order $58e12afd-6eb0-4731-bd57-d9ae7ab4e164$bfab5c2d-61c3-468b-9ddf-4aaa49cb7785$063f0acc-c023-46d0-9ed9-fbd7fbdcfa3b$3e98c0ca-1b47-4631-83d7-cd0c8c0a431d$5a566137-fbd1-45b2-9a55-e4aded366bb3$a6c337c4-0c81-4463-ad4f-9a4528d953ab$c04bcc96-e5fe-4d6e-a12e-40dcde58c62e$cf799c26-1cea-4b38-9a15-8497813bd668$6d2b3dbc-0686-49f0-904a-56c3ce63b4dd$b5a3e471-af4a-466f-bbae-96306bcc7563$d722a86d-6d51-4d91-ac22-53af94c91497$c3590376-06ed-45a4-af0b-2d46f1a387c8$52d428d5-cb33-4f2a-89eb-3a8ce3f5bb81$273ad3a6-cb32-49bb-8702-fdaf8597e812$4e32f7fb-cd5a-4190-9c92-ba4029313475$82230d6c-25ce-4d12-8842-e0651fc4b143$7d9ac5f9-39bf-4052-ad8a-ac0fec15c64a$b0ca0392-71b8-4f44-8c6c-0978a02a0e6c$a103c5af-42fe-4f8c-b78c-6946895105d7$21b6133f-db59-4885-9b3d-331c3d6ef306$35ba1eea-56ae-4b74-af96-21ec5a93c455$8981b5e2-2497-478e-ab28-a14b62f6f916$5441e428-b320-433c-acde-15fe6bf58537$70e88569-cd5c-40e8-9198-6bf6578fb0a2$40606ee3-38cc-4123-9b86-b774bf89e499$b94cd399-0370-49e9-a522-056f3af22955$9b4cae31-c319-444e-98c8-2c0bfc6dfa0c$8b83570a-6982-47e5-a167-a6d6afee0f7d$5d72bf87-7f3a-4229-9d7a-2e63c115087d$7b1d26c6-9499-4e44-84c8-c272737a175e$fc43b343-79cd-4342-8d80-8ea72cf34942$233c13ff-f008-40b0-a6c5-c5395b2215ec$ad3559d1-6180-4eaa-b97d-3c1f10f036b9$c420ad25-6af1-4fb4-823a-b6bbd4e10f7f$db16e939-b490-497b-a03f-80ce2e8485af$4fdb4cd6-a794-4b14-84b0-72f484c6ea86$a258eec9-f4f6-49bd-8470-8541836f5f6b$6fc34de1-469b-41a9-9677-ff3182f7a498$de20bf96-7d33-4a78-8147-f0b7f8488e46$e119c2d3-1e24-464f-b812-62f28c00a913$dbc19cbb-1349-4904-b655-2452aa7e2452$2ff573a3-4a84-4497-9305-2d97e35e5e3d$6be49c46-4900-4457-81b4-0704cd7da0af$60bc118f-6795-43f9-97a2-865fd1704895$0d69e94b-492a-4acc-adba-a2126b871724$b9a9e335-1328-4c63-a213-ce21263bc201$a1b2d090-d498-4d5d-90a0-8cdc648dc833$a771f33f-7ed1-41aa-bee0-c215729a8c8d$370f0f20-e373-4028-bca1-83e93678cbcb$141d162c-c817-498f-be16-f1cd35d82487$7cf59087-efca-4f03-90dc-f2acefdcbc8a$35aa1295-642f-4525-bf19-df2a42ff39d6$4788d8b4-2efa-4489-80c3-71f405513644$e832ce25-94e2-4743-854d-02b52cc7b56d$79b405a5-54b5-4727-a0cd-b79522ad109f$d2104fbd-ba22-4501-b03a-8809271d598b$0e640e07-82c7-4dab-a8f1-2f634bbebdea$4569aa05-9963-4976-ac63-caf3f3979e83$34a10003-2c32-4332-b3e6-ce70eec0cbbe$ce7bf747-7116-4e76-9004-f234317046c3$d7e31ced-4eb2-4221-b83f-462e8f32fe89$c3c848ff-526a-450d-9b1c-5d9d3ccccf28$67dee339-98b4-4714-88b2-8098a13235f2$3a50ca06-06e8-4a61-ade2-afbfc52ca655$32f740e7-9338-4c42-8eaf-ce8022412c50$8a527c17-bf2b-4e6b-937f-ef3a269c5112$93f0c63c-b597-4f89-809c-7af0476f319a$568057f5-b0b8-4225-8e4b-5eec911a52ef$26aa369f-e5c7-4fe5-8b6b-903f4f4e91ba$a79c410a-bebf-434c-9730-568e0ff4f4c7$39f48c25-6efb-4ff2-aedc-9d3e722dad24$55e96151-2aa1-4ea0-b672-2038c57d911e$be0e3ba0-18cc-4b9a-a56d-2566f5148fae$c0daf219-cb87-4203-b835-49ab7eb955be$c1285653-38ba-418b-bdf5-cda99440998d$88f33f35-d922-4d98-af4a-ebb79d9b7dc6$e3474aea-ee14-4c78-ae46-5badc66a543a$6c1984f6-4e36-4637-b0da-c7dd8b0f9ff0$51d70f9a-cd67-44b9-8fd1-5ab70b526c7a$944d827e-bc6a-4de8-b959-5fde8790bedc$3a2bfd4e-0ce6-4a79-a578-fc1b4ef563c5$beee4908-d519-413a-964f-149bb82cdbb8$d8bb1d43-bf42-4a09-bdeb-5db406ef1ccd$b540d5e3-6686-479a-b2c7-c1f65b85b6ba$091dd042-580b-4fda-8086-e048663aed6c$9a100ccf-1ad3-4d2c-bbe0-e297969eb69e$921b5a18-0733-4032-a543-9d60e254b1b2$9612a1ef-fd3a-4a58-87b0-b2255ac86331$98392c40-6542-4a26-8552-c0960bbaa6a6$49b596b8-891d-4f3f-a6a4-a62cc8237df3$c253bb24-ad76-4b58-8dfc-7dc2576e3db5$1b617828-e2b2-4a94-a120-59fa533d3e11$f2ebc6fb-e07c-4922-897d-9bbe0f5fa1d0$8da580fe-6b56-4d8f-ad43-aed7b728a06e$fa024a5d-52a6-459d-894d-13a60ec723d2$360091c4-d3a0-462d-abcf-b9bbb9480871$e44b0038-d68f-4a49-9da2-67fbcbe098c3$3dc860be-016d-49ee-8535-7d9457c70f85$7fc70992-973a-43c6-904a-dd1b622a5ed8$c55dcd4a-8438-4679-9c4a-78cceec6835d$7d37fbea-baa3-43ec-b003-a4707017a4cf$fc705b81-7310-44cc-ad9f-dc2cf8a9b645$86394e1c-0ff4-449a-8940-4b5906d8b6f0$23bfbe95-7ba2-41b9-bd8b-dc4baa3ad53a$d7117a24-aba6-4479-a40e-5005310a6b38$2257220c-6f0e-4edf-9fea-7e388b84df9b$39b055f5-3dbf-403c-b21e-210e3813d8b0$2e4dc3f9-a132-444f-a35d-f583823a7dfd$b68eb860-a5b4-4e9e-9fbf-6eb6ce43ae69$8f46daf1-9ca2-4a08-99aa-4ed68af218b8$2c84bd84-b54d-4594-b9f8-35db2124d7e8$4309dc43-aeb8-4ec7-94fe-0e320b784349$f6f9447c-9bc9-432d-bd80-2c39f9d842f8$1551122c-70ae-4e37-b3fb-4be91fcc4afb$a0566fdb-a08d-4bcf-9b2f-ed211c9f111f$e796b093-9c1d-4656-9acb-918de53f7e4d$d04b9af5-f004-4ca4-b1c9-2c86d46cb37d$655e980d-b4e9-4f56-a5ae-380072242d27$133f4c7d-33e0-4e13-b716-f538125436ca$97d3cf3f-ddac-4850-8b05-bdc0c4741f61$61af27f1-9f83-42f1-a419-06d12ea62133$143dca7c-f9a4-472a-a4bc-4578e4e8413b$1bac238f-79c8-4f9f-a187-bacb288de3b0$e4d1de1d-d57a-48ab-ad7a-c09b427daa03$954f1ab1-1e2f-458b-96d7-a1746631fac7$21d507f6-02f8-4f8b-84f1-bcb84731df66$4aac6ab5-053a-4f60-9e2e-e8d61ff0cecb$b53ec488-ff25-4647-ab00-fbf90963a795$de72d596-0daf-4629-bbb5-20bb8a67cbed$488b0c17-4f0f-43bf-a16c-b9faa7ae0595$10a1b3a7-21c7-4f97-93e1-006ad3aea40d$f7f097cb-d7bd-49eb-a030-ac26f8f61a67$3ec3c058-a94d-4717-b99f-66373f2fa31d$6041a909-d26c-4ab1-836b-29953c578759$16f8d28b-f201-4fe5-8446-68d7d9ddfb3c$a59db59c-d34e-4abd-8865-9907607e06a8$f2417047-33fc-4489-8e89-115bc6b46c13$8df4ff2f-d176-4b4e-a525-665b5d07ea52$1152dec8-3810-42b1-bb2a-8755dcaef56c$7565e3da-84ce-42b6-8d4b-3615576f33b7$c45ff9b5-35d9-4a9d-a801-c762333a1f02$e172f5c5-8b96-4efd-9cf3-805c58d1a6a3julia_versionv1.12.6published_objectsnbpkginstall_time_ns Ginstantiatedòinstalled_versionsSimpleClang0.1.0StaticArrays1.9.17PlutoUI0.7.79!__internal_julia_manifest_version1.12.6HypertextLiteral1.0.0__internal_julia_version1.12.6BenchmarkTools1.6.3Luxor4.4.1MarkdownstdlibPlutoTeachingTools0.4.7terminal_outputsStaticArrays
[0m[1mResolving...[22m
[90m===[39m
[36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_davjuulzzu/Project.toml`
[36m[1m Manifest[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_davjuulzzu/Manifest.toml`
[0m[1mInstantiating...[22m
[90m===[39m
[0m[1mPrecompiling...[22m
[90m===[39m
Waiting for notebook process to start... Done. Starting precompilation...SimpleClang
[0m[1mResolving...[22m
[90m===[39m
[36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_davjuulzzu/Project.toml`
[36m[1m Manifest[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_davjuulzzu/Manifest.toml`
[0m[1mInstantiating...[22m
[90m===[39m
[0m[1mPrecompiling...[22m
[90m===[39m
Waiting for notebook process to start... Done. Starting precompilation...nbpkg_sync
[0m[1mResolving...[22m
[90m===[39m
[36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_davjuulzzu/Project.toml`
[36m[1m Manifest[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_davjuulzzu/Manifest.toml`
[0m[1mInstantiating...[22m
[90m===[39m
[0m[1mPrecompiling...[22m
[90m===[39m
Waiting for notebook process to start... Done. Starting precompilation...PlutoUI
[0m[1mResolving...[22m
[90m===[39m
[36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_davjuulzzu/Project.toml`
[36m[1m Manifest[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_davjuulzzu/Manifest.toml`
[0m[1mInstantiating...[22m
[90m===[39m
[0m[1mPrecompiling...[22m
[90m===[39m
Waiting for notebook process to start... Done. Starting precompilation...HypertextLiteral
[0m[1mResolving...[22m
[90m===[39m
[36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_davjuulzzu/Project.toml`
[36m[1m Manifest[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_davjuulzzu/Manifest.toml`
[0m[1mInstantiating...[22m
[90m===[39m
[0m[1mPrecompiling...[22m
[90m===[39m
Waiting for notebook process to start... Done. Starting precompilation...BenchmarkTools
[0m[1mResolving...[22m
[90m===[39m
[36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_davjuulzzu/Project.toml`
[36m[1m Manifest[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_davjuulzzu/Manifest.toml`
[0m[1mInstantiating...[22m
[90m===[39m
[0m[1mPrecompiling...[22m
[90m===[39m
Waiting for notebook process to start... Done. Starting precompilation...Markdown
[0m[1mResolving...[22m
[90m===[39m
[36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_davjuulzzu/Project.toml`
[36m[1m Manifest[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_davjuulzzu/Manifest.toml`
[0m[1mInstantiating...[22m
[90m===[39m
[0m[1mPrecompiling...[22m
[90m===[39m
Waiting for notebook process to start... Done. Starting precompilation...Luxor
[0m[1mResolving...[22m
[90m===[39m
[36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_davjuulzzu/Project.toml`
[36m[1m Manifest[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_davjuulzzu/Manifest.toml`
[0m[1mInstantiating...[22m
[90m===[39m
[0m[1mPrecompiling...[22m
[90m===[39m
Waiting for notebook process to start... Done. Starting precompilation...PlutoTeachingTools
[0m[1mResolving...[22m
[90m===[39m
[36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_davjuulzzu/Project.toml`
[36m[1m Manifest[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_davjuulzzu/Manifest.toml`
[0m[1mInstantiating...[22m
[90m===[39m
[0m[1mPrecompiling...[22m
[90m===[39m
Waiting for notebook process to start... Done. Starting precompilation...enabled÷restart_recommended_msgrestart_required_msgbusy_packageswaiting_for_permission,waiting_for_permission_but_probably_disabled«cell_inputs $c55dcd4a-8438-4679-9c4a-78cceec6835dcell_id$c55dcd4a-8438-4679-9c4a-78cceec6835dcoderfunction path(ring::Bool; s = 80, offset = 0.04)
off(a, b) = a + sign(b - a) * offset
p(i, j) = Point(i * s, j * s)
c(m, i, j) = circle(p(i, j), 0.06s, action = :fill)
a(i1, j1, i2, j2) = line(p(off(i1, i2), off(j1, j2)), p(off(i2, i1), off(j2, j1)), action = :stroke)
function ac(i1, j1, i2, j2, m)
a(i1, j1, i2, j2)
c(m, i2, j2)
end
@draw begin
c("1", -3, 0)
ac(-3, 0, -2, 0, "2")
ac(-2, 0, -1, 0, "3")
ac(-1, 0, 0, 0, "4")
ac(0, 0, 1, 0, "5")
if ring
move(p(off(1, 0), off(0, -1)))
curve(p(off(1, 2), off(0, -1)), p(-1, -1), p(off(-3, -2), off(0, -1)))
strokepath()
end
end 7.5s 1.7s
end;metadatashow_logsèdisabled®skip_as_script«code_folded$6be49c46-4900-4457-81b4-0704cd7da0afcell_id$6be49c46-4900-4457-81b4-0704cd7da0afcodeFoldable(
md"""
Would it be more efficient to have a specialized implementation instead of combining existing collectives ?
""",
md"""
Let the size of each ``x_{i,j}`` be ``n/p`` bytes.
1. `MPI_Reduce` acts on the concatenation ``x_{:,j}`` which has length ``n`` bytes hence the complexity is ``\log_2(p)(\alpha + \beta n + \gamma n)``
2. `MPI_Scatter` has the same complexity as `MPI_Gather` (since it's the same but backwards in time) : ``\log_2(p) \alpha + \beta n``
In total, we have the complexity ``\log_2(p) (\alpha + \beta n + \gamma n)``. Can we do better ?
Start exchanging between 1 and 2 and simultaneously exchanging between 3 and 4.
The complexity is ``\alpha + 2(\beta + \gamma) n/4``.
| `procid` | 1 | 2 | 3 | 4 |
|----------|---|---|---|---|
| | ``x_{1,1} + x_{1,2}`` | | ``x_{1,3} + x_{1,4}`` | |
| | | ``x_{2,1} + x_{2,2}`` | | ``x_{2,3} + x_{2,4}`` |
| | ``x_{3,1} + x_{3,2}`` | | ``x_{3,3} + x_{3,4}`` | |
| | | ``x_{4,1} + x_{4,2}`` | | ``x_{4,3} + x_{4,4}`` |
Next, we exchange between 1 and 3 and simultaneously between 2 and 4.
The complexity is ``\alpha + (\beta + \gamma) n/4``.
In total, we have complexity
```math
\begin{align}
\log_2(p) \alpha + (\beta + \gamma) n(p/2 + \cdots + 4 + 2 + 1)/p
& =
\log_2(p) \alpha + (\beta + \gamma) n(p-1)/p\\
& \approx
\log_2(p) \alpha + (\beta + \gamma) n.
\end{align}
```
This is better than the approaches combining existing collectives above since we removed the ``\log_2(p)`` in front of ``\beta`` and ``\gamma``.
""",
)metadatashow_logsèdisabled®skip_as_script«code_folded$c1285653-38ba-418b-bdf5-cda99440998dcell_id$c1285653-38ba-418b-bdf5-cda99440998dcodeaside(tip(Foldable(md"Use `module spider` to see which version are available",
md"""
```
[blegat@lm4-f001 ~]$ module spider gompi
----------------------------
gompi:
----------------------------
Description:
GNU Compiler Collection (GCC) based compiler toolchain, including OpenMPI for MPI support.
Versions:
gompi/2021b
gompi/2022b
gompi/2023a
gompi/2023b
----------------------------
For detailed information about a specific "gompi" package (including how to load the modules) use the module's full name.
Note that names that have a trailing (E) are extensions provided by other modules.
For example:
$ module spider gompi/2023b
----------------------------
```
""")), v_offset = -300)metadatashow_logsèdisabled®skip_as_script«code_folded$4fdb4cd6-a794-4b14-84b0-72f484c6ea86cell_id$4fdb4cd6-a794-4b14-84b0-72f484c6ea86codemd"## All gather"metadatashow_logsèdisabled®skip_as_script«code_folded$a59db59c-d34e-4abd-8865-9907607e06a8cell_id$a59db59c-d34e-4abd-8865-9907607e06a8code@aside(md"""From $(citeintro("Figure 2.27"))""", v_offset = -200)metadatashow_logsèdisabled®skip_as_script«code_folded$5a566137-fbd1-45b2-9a55-e4aded366bb3cell_id$5a566137-fbd1-45b2-9a55-e4aded366bb3code)md"# Single Program Multiple Data (SPMD)"metadatashow_logsèdisabled®skip_as_script«code_folded$ad3559d1-6180-4eaa-b97d-3c1f10f036b9cell_id$ad3559d1-6180-4eaa-b97d-3c1f10f036b9codemd"## Reduce"metadatashow_logsèdisabled®skip_as_script«code_folded$88f33f35-d922-4d98-af4a-ebb79d9b7dc6cell_id$88f33f35-d922-4d98-af4a-ebb79d9b7dc6codempicc_cmd = md"""
```sh
[blegat@lm4-f001 ~]$ mpicc
-bash: mpicc: command not found
[blegat@lm4-f001 ~]$ module load gompi/2023a
[blegat@lm4-f001 ~]$ mpicc
gcc: fatal error: no input files
compilation terminated.
```
""";metadatashow_logsèdisabled®skip_as_script«code_folded$b540d5e3-6686-479a-b2c7-c1f65b85b6bacell_id$b540d5e3-6686-479a-b2c7-c1f65b85b6bacode+md"## Profiling with NVIDIA Nsight Systems"metadatashow_logsèdisabled®skip_as_script«code_folded$f6f9447c-9bc9-432d-bd80-2c39f9d842f8cell_id$f6f9447c-9bc9-432d-bd80-2c39f9d842f8code٣img("https://raw.githubusercontent.com/VictorEijkhout/TheArtOfHPC_vol1_scientificcomputing/refs/heads/main/booksources/graphics/hypercubes.jpg", :width => "400pt")metadatashow_logsèdisabled®skip_as_script«code_folded$9a100ccf-1ad3-4d2c-bbe0-e297969eb69ecell_id$9a100ccf-1ad3-4d2c-bbe0-e297969eb69ecodemd"# Topology"metadatashow_logsèdisabled®skip_as_script«code_folded$a1b2d090-d498-4d5d-90a0-8cdc648dc833cell_id$a1b2d090-d498-4d5d-90a0-8cdc648dc833codemd"# Distributed sum"metadatashow_logsèdisabled®skip_as_script«code_folded$8b83570a-6982-47e5-a167-a6d6afee0f7dcell_id$8b83570a-6982-47e5-a167-a6d6afee0f7dcodehbox([
md"""Before
| `procid` | 1 | 2 | 3 | 4 |
|----------|---|---|---|---|
| | ``x`` | | | |
""",
Div(md"` `", style = Dict("margin" => "50pt")),
md"""After
| `procid` | 1 | 2 | 3 | 4 |
|----------|---|---|---|---|
| | ``x`` | ``x`` | ``x`` | ``x`` |
""",
])metadatashow_logsèdisabled®skip_as_script«code_folded$e3474aea-ee14-4c78-ae46-5badc66a543acell_id$e3474aea-ee14-4c78-ae46-5badc66a543acodelist_1 = Foldable(md"`[blegat@lm4-f001 ~]$ module list`", md"""
```
Currently Loaded Modules:
1) tis/2018.01 (S) 2) releases/2023a (S) 3) StdEnv
Where:
S: Module is Sticky, requires --force to unload or purge
```
""");metadatashow_logsèdisabled®skip_as_script«code_folded$21d507f6-02f8-4f8b-84f1-bcb84731df66cell_id$21d507f6-02f8-4f8b-84f1-bcb84731df66codemd"## Fat-tree"metadatashow_logsèdisabled®skip_as_script«code_folded$de72d596-0daf-4629-bbb5-20bb8a67cbedcell_id$de72d596-0daf-4629-bbb5-20bb8a67cbedcodeٖFoldable(md"What is the number of edges ? What is the bisection width ?",
md"""
Number of edges is ``n\log_2(n)`` and bisection width is ``n/2``.
""")metadatashow_logsèdisabled®skip_as_script«code_folded$c253bb24-ad76-4b58-8dfc-7dc2576e3db5cell_id$c253bb24-ad76-4b58-8dfc-7dc2576e3db5codemd"## Bisection bandwidth"metadatashow_logsèdisabled®skip_as_script«code_folded$e4d1de1d-d57a-48ab-ad7a-c09b427daa03cell_id$e4d1de1d-d57a-48ab-ad7a-c09b427daa03codeFoldable(md"What is the diameter and bisection width of ``n`` computer nodes ?",
md"""
Diameter is ``2\log_2(n)`` and bisection width is 1.
$(img("https://upload.wikimedia.org/wikipedia/commons/d/da/Bisected_tree.jpg") )
""")metadatashow_logsèdisabled®skip_as_script«code_folded$133f4c7d-33e0-4e13-b716-f538125436cacell_id$133f4c7d-33e0-4e13-b716-f538125436cacodeFTwoColumnWideLeft(
md"""
There can be ``n`` simultaneous communications at the same time, provided that each input communicates with a different output.
The figure on the right provides an example of such non-conflicting communications with the black dots indicating that the input of that row communicates to the corresponding output (case (a) of above figure). The switch at row 1 and column 2 is just propagating the input data horizontally and output data vertically (case (b) of above figure). The switch at row 0 and column 5 is receiving no data.
""",
img1("crossbar.jpg"),
)metadatashow_logsèdisabled®skip_as_script«code_folded$3a50ca06-06e8-4a61-ade2-afbfc52ca655cell_id$3a50ca06-06e8-4a61-ade2-afbfc52ca655codeBaside(md"""See $(citepara("Section 4.1.4.2"))""", v_offset = -100)metadatashow_logsèdisabled®skip_as_script«code_folded$6c1984f6-4e36-4637-b0da-c7dd8b0f9ff0cell_id$6c1984f6-4e36-4637-b0da-c7dd8b0f9ff0code_list_2 = Foldable(md"`[blegat@lm4-f001 ~]$ module list`", md"""
```
Currently Loaded Modules:
1) tis/2018.01 (S) 11) libpciaccess/0.17-GCCcore-12.3.0
2) releases/2023a (S) 12) hwloc/2.9.1-GCCcore-12.3.0
3) StdEnv 13) OpenSSL/1.1
4) GCCcore/12.3.0 14) libevent/2.1.12-GCCcore-12.3.0
5) zlib/1.2.13-GCCcore-12.3.0 15) UCX/1.14.1-GCCcore-12.3.0
6) binutils/2.40-GCCcore-12.3.0 16) libfabric/1.18.0-GCCcore-12.3.0
7) GCC/12.3.0 17) PMIx/4.2.4-GCCcore-12.3.0
8) numactl/2.0.16-GCCcore-12.3.0 18) UCC/1.2.0-GCCcore-12.3.0
9) XZ/5.4.2-GCCcore-12.3.0 19) OpenMPI/4.1.5-GCC-12.3.0
10) libxml2/2.11.4-GCCcore-12.3.0 20) gompi/2023a
Where:
S: Module is Sticky, requires --force to unload or purge
```
""");metadatashow_logsèdisabled®skip_as_script«code_folded$de20bf96-7d33-4a78-8147-f0b7f8488e46cell_id$de20bf96-7d33-4a78-8147-f0b7f8488e46codeOFoldable(
md"""
Would it be more efficient to have a specialized implementation instead of combining existing collectives ?
""",
md"""
Let the size of ``x_i`` be ``n/p`` bytes.
1. `MPI_Gather` has complexity ``\log_2(p)\alpha + \beta n``
2. `MPI_Bcast` acts on the concatenation ``x_:`` which has length ``n`` bytes so the complexity is ``\log_2(p) (\alpha + \beta n)``
In total, we have the complexity ``\log_2(p) (\alpha + \beta n)``. Can we do better ?
Start exchanging between 1 and 2 and simultaneously exchanging between 3 and 4.
The complexity is ``\alpha + \beta n/4``.
| `procid` | 1 | 2 | 3 | 4 |
|----------|---|---|---|---|
| | ``x_1`` | ``x_1`` | | |
| | ``x_2`` | ``x_2`` | | |
| | | | ``x_3`` | ``x_3`` |
| | | | ``x_4`` | ``x_4`` |
Next, we exchange between 1 and 3 and simultaneously between 2 and 4.
The complexity is ``\alpha + 2\beta n/4``.
In total, we have complexity
```math
\begin{align}
\log_2(p) \alpha + \beta n(1 + 2 + 4 + \cdots + p/2)/p
& =
\log_2(p) \alpha + \beta n(p-1)/p\\
& \approx \log_2(p) \alpha + \beta n.
\end{align}
```
""",
)metadatashow_logsèdisabled®skip_as_script«code_folded$51d70f9a-cd67-44b9-8fd1-5ab70b526c7acell_id$51d70f9a-cd67-44b9-8fd1-5ab70b526c7acodemd"## Launching a job"metadatashow_logsèdisabled®skip_as_script«code_folded$98392c40-6542-4a26-8552-c0960bbaa6a6cell_id$98392c40-6542-4a26-8552-c0960bbaa6a6codemd"""
* Consider graph ``G`` with nodes ``v`` corresponding to computer nodes or switches.
* There is an edge ``(u, v) \in E`` if there is an ethernet cable **directly** connecting ``u`` and ``v``.
* ``e \in E`` are ethernet cables of bandwidth ``w_e``
* Distance (unweighted) from node ``u \in V`` to node ``v \in V`` is ``d(G, u, v)``
- Does not depend on bandwidth ``w_e`` of edges of the path
"""metadatashow_logsèdisabled®skip_as_script«code_folded$39b055f5-3dbf-403c-b21e-210e3813d8b0cell_id$39b055f5-3dbf-403c-b21e-210e3813d8b0codeٌimg("https://raw.githubusercontent.com/VictorEijkhout/TheArtOfHPC_vol1_scientificcomputing/refs/heads/main/booksources/graphics/torus.jpeg")metadatashow_logsèdisabled®skip_as_script«code_folded$b0ca0392-71b8-4f44-8c6c-0978a02a0e6ccell_id$b0ca0392-71b8-4f44-8c6c-0978a02a0e6ccodeلcompile_and_run(Example("MPI/procname.c"); mpi = true, verbose = 1, show_run_command = true, num_processes = procname_num_processes)metadatashow_logsèdisabled®skip_as_script«code_folded$26aa369f-e5c7-4fe5-8b6b-903f4f4e91bacell_id$26aa369f-e5c7-4fe5-8b6b-903f4f4e91bacodeKcompile_and_run(Example("MPI/mpi_bench2.c"), mpi = true, num_processes = 2)metadatashow_logsèdisabled®skip_as_script«code_folded$a103c5af-42fe-4f8c-b78c-6946895105d7cell_id$a103c5af-42fe-4f8c-b78c-6946895105d7codeamd"`num_processes` = $(@bind procname_num_processes Slider(2:8, default = 2, show_value = true))"metadatashow_logsèdisabled®skip_as_script«code_folded$d8bb1d43-bf42-4a09-bdeb-5db406ef1ccdcell_id$d8bb1d43-bf42-4a09-bdeb-5db406ef1ccdcodehbox([Div(md"""
* `srun` : Synchronous (blocked) job
```
[blegat@lm4-f001 ~]$ srun --time=1 pwd
srun: job 3491072 queued and waiting for resources
srun: job 3491072 has been allocated resources
/home/users/b/l/blegat
```
* `$ sbatch submit.sh` : Asynchronous job, get status with
* `$ squeue --me`
* More details on the [README](https://github.com/blegat/LINMA2710)
""", style = Dict("flex-grow" => "1", "margin-right" => "30px")),
md"""
$(img("https://upload.wikimedia.org/wikipedia/commons/3/3a/Slurm_logo.svg", :width => "160px", :height => "160px"))
See [CÉCI documentation](https://support.ceci-hpc.be/doc/_contents/QuickStart/SubmittingJobs/SlurmTutorial.html)
""",
])metadatashow_logsèdisabled®skip_as_script«code_folded$82230d6c-25ce-4d12-8842-e0651fc4b143cell_id$82230d6c-25ce-4d12-8842-e0651fc4b143code)md"## Processor name identifies the node"metadatashow_logsèdisabled®skip_as_script«code_folded$fc43b343-79cd-4342-8d80-8ea72cf34942cell_id$fc43b343-79cd-4342-8d80-8ea72cf34942codehbox([
md"""Before
| `procid` | 1 | 2 | 3 | 4 |
|----------|---|---|---|---|
| | ``x_1`` | | | |
| | | ``x_2`` | | |
| | | | ``x_3`` | |
| | | | | ``x_4`` |
""",
Div(md"` `", style = Dict("margin" => "50pt")),
md"""After
| `procid` | 1 | 2 | 3 | 4 |
|----------|---|---|---|---|
| | ``x_1`` | | | |
| | ``x_2`` | | | |
| | ``x_3`` | | | |
| | ``x_4`` | | | |
""",
])metadatashow_logsèdisabled®skip_as_script«code_folded$d2104fbd-ba22-4501-b03a-8809271d598bcell_id$d2104fbd-ba22-4501-b03a-8809271d598bcodemd"## Blocking communication"metadatashow_logsèdisabled®skip_as_script«code_folded$8a527c17-bf2b-4e6b-937f-ef3a269c5112cell_id$8a527c17-bf2b-4e6b-937f-ef3a269c5112code٫img("https://raw.githubusercontent.com/VictorEijkhout/TheArtOfHPC_vol2_parallelprogramming/refs/heads/main/booksources/graphics/send-nonblocking.jpeg", :height => "200pt")metadatashow_logsèdisabled®skip_as_script«code_folded$be0e3ba0-18cc-4b9a-a56d-2566f5148faecell_id$be0e3ba0-18cc-4b9a-a56d-2566f5148faecodekmd"""## $(img("https://github.com/TACC/Lmod/raw/main/logos/2x/Lmod-4color%402x.png", :height => "30px"))"""metadatashow_logsèdisabled®skip_as_script«code_folded$2ff573a3-4a84-4497-9305-2d97e35e5e3dcell_id$2ff573a3-4a84-4497-9305-2d97e35e5e3dcodeٰFoldable(md"Can `MPI_Reduce_scatter` be implemented by combining existing collectives ?", md"`MPI_Reduce_scatter` can be implemented by `MPI_Reduce` followed by `MPI_Scatter`")metadatashow_logsèdisabled®skip_as_script«code_folded$1b617828-e2b2-4a94-a120-59fa533d3e11cell_id$1b617828-e2b2-4a94-a120-59fa533d3e11codemd"""
Bandwidth ``\texttt{bw}(u, v)`` is the bandwidth of the cable if ``(u, v) \in E``
or 0 otherwise. Given ``S, T \subseteq V`` two disjoint subsets of nodes ``S \cap T = \varnothing``,
```math
\begin{align}
\text{Width} &\qquad & w(S, T) & = |\{ (u, v) \in E \mid u \in S, v \in T \}|\\
\text{Bandwidth} & & \texttt{bw}(S, T) & = \sum_{u\in S, v\in T} \texttt{bw}(u,v)
\end{align}
```
The width is exactly the number of edges between the two sets of nodes.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$c3590376-06ed-45a4-af0b-2d46f1a387c8cell_id$c3590376-06ed-45a4-af0b-2d46f1a387c8codeghbox([
Div(md"""
Free up memory.
"""; style = Dict("flex-grow" => "1")),
c"""
MPI_Finalize();
""",
])metadatashow_logsèdisabled®skip_as_script«code_folded$35ba1eea-56ae-4b74-af96-21ec5a93c455cell_id$35ba1eea-56ae-4b74-af96-21ec5a93c455codeOmd"""
You could simply add `lmpi` but using `mpicc` and `mpic++` is easier.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$488b0c17-4f0f-43bf-a16c-b9faa7ae0595cell_id$488b0c17-4f0f-43bf-a16c-b9faa7ae0595code4aside(citeintro("Section 2.7.6.3"), v_offset = -150)metadatashow_logsèdisabled®skip_as_script«code_folded$10a1b3a7-21c7-4f97-93e1-006ad3aea40dcell_id$10a1b3a7-21c7-4f97-93e1-006ad3aea40dcodemd"## Butterfly"metadatashow_logsèdisabled®skip_as_script«code_folded$b68eb860-a5b4-4e9e-9fbf-6eb6ce43ae69cell_id$b68eb860-a5b4-4e9e-9fbf-6eb6ce43ae69codeFoldable(md"What is the bisection width of a ``n \times n`` 2D array ?",
md"""
It is ``n = \sqrt{|V|}``:
$(img("https://upload.wikimedia.org/wikipedia/commons/2/2f/Bisected_mesh.jpg", :width => "300pt"))
$(Foldable(md"What is the bisection width of a ``n^d`` ``d``D array ?",
md"It is 1 for ``d = 1``, ``n`` for ``d = 2`` and ``n^2`` for ``d = 3``. In general, it is ``n^{d-1} = |V|^{(d-1)/d}``"))
""")metadatashow_logsèdisabled®skip_as_script«code_folded$3dc860be-016d-49ee-8535-7d9457c70f85cell_id$3dc860be-016d-49ee-8535-7d9457c70f85codenFoldable(md"What is the graph diameter ?", md"``|V| - 1`` if ``u`` and ``v`` are extreme points of the array")metadatashow_logsèdisabled®skip_as_script«code_folded$2e4dc3f9-a132-444f-a35d-f583823a7dfdcell_id$2e4dc3f9-a132-444f-a35d-f583823a7dfdcode"Foldable(md"What is the graph diameter of a ``n \times n`` 2D array ?",
md"""
It is ``2(n-1)``, attained for opposite vertices of the square.
$(Foldable(md"What is the graph diameter of a ``n^d`` ``d``D array ?",
md"It is ``d(n-1)``, attained for opposite vertices of the hypercube."))
""")metadatashow_logsèdisabled®skip_as_script«code_folded$8981b5e2-2497-478e-ab28-a14b62f6f916cell_id$8981b5e2-2497-478e-ab28-a14b62f6f916coderun(`mpicc -show`)metadatashow_logsèdisabled®skip_as_script«code_folded$34a10003-2c32-4332-b3e6-ce70eec0cbbecell_id$34a10003-2c32-4332-b3e6-ce70eec0cbbecodemd"## Example"metadatashow_logsèdisabled®skip_as_script«code_folded$a0566fdb-a08d-4bcf-9b2f-ed211c9f111fcell_id$a0566fdb-a08d-4bcf-9b2f-ed211c9f111fcode2aside(citeintro("Section 2.7.5"), v_offset = -150)metadatashow_logsèdisabled®skip_as_script«code_folded$655e980d-b4e9-4f56-a5ae-380072242d27cell_id$655e980d-b4e9-4f56-a5ae-380072242d27codehbox([
img("https://ars.els-cdn.com/content/image/3-s2.0-B9781558608528500043-f01-09-9781558608528.jpg"),
img("https://ars.els-cdn.com/content/image/3-s2.0-B9781558608528500043-f01-10-9781558608528.jpg"),
])metadatashow_logsèdisabled®skip_as_script«code_folded$4788d8b4-2efa-4489-80c3-71f405513644cell_id$4788d8b4-2efa-4489-80c3-71f405513644code\md"`num_processes` = $(@bind sum_num_processes Slider(2:8, default = 2, show_value = true))"metadatashow_logsèdisabled®skip_as_script«code_folded$233c13ff-f008-40b0-a6c5-c5395b2215eccell_id$233c13ff-f008-40b0-a6c5-c5395b2215eccodeFoldable(
md"Lower bound complexity with ``p`` processes if each ``x_i`` has length ``n/p`` bytes ?",
md"""
Lower bound : ``\log_2(p) \alpha`` using *spanning tree* algorithm and ``\beta n`` as all messages need to be sent at least once.
First send ``x_2`` from 2 to 1 and simultaneously send ``x_4`` from 4 to 3.
Complexity is ``\alpha + \beta n/4``
| `procid` | 1 | 2 | 3 | 4 |
|----------|---|---|---|---|
| | ``x_1`` | | | |
| | ``x_2`` | ``x_2`` | | |
| | | | ``x_3`` | |
| | | | ``x_4`` | ``x_4`` |
Then send ``(x_3, x_4)`` from 3 to 1.
Complexity is ``\alpha + 2\beta n/4``
| `procid` | 1 | 2 | 3 | 4 |
|----------|---|---|---|---|
| | ``x_1`` | | | |
| | ``x_2`` | ``x_2`` | | |
| | ``x_3`` | | ``x_3`` | |
| | ``x_4`` | | ``x_4`` | ``x_4`` |
In total, it is ``2\alpha + 3\beta n/4``. In general, we have
```math
\log_2(p)\alpha + \beta n(1 + 2 + 4 + \cdots + p/2)/p = \log_2(p)\alpha + \beta n(p - 1)/p \approx \log_2(p)\alpha + \beta n
```
What about having each node sending directly to 1 ?
| `procid` | 1 | 2 | 3 | 4 |
|----------|---|---|---|---|
| | ``x_1`` | | | |
| | ``x_2`` | ``x_2`` | | |
| | | | ``x_3`` | |
| | | | | ``x_4`` |
Then
| `procid` | 1 | 2 | 3 | 4 |
|----------|---|---|---|---|
| | ``x_1`` | | | |
| | ``x_2`` | ``x_2`` | | |
| | ``x_3`` | | ``x_3`` | |
| | | | | ``x_4`` |
Then
| `procid` | 1 | 2 | 3 | 4 |
|----------|---|---|---|---|
| | ``x_1`` | | | |
| | ``x_2`` | ``x_2`` | | |
| | ``x_3`` | | ``x_3`` | |
| | ``x_4`` | | | ``x_4`` |
Here, we have ``3\alpha + 3\beta n/4``. The coefficient is higher in front of ``\alpha``. However, is the same in front of ``\beta``. Indeed, even though the spanning tree above communicate more bytes through the network, as the communication from node 2 to node 1 and node 4 to node 3 are done in parallel, this isn't affecting the coefficient in front of ``\beta``.
"""
)metadatashow_logsèdisabled®skip_as_script«code_folded$6fc34de1-469b-41a9-9677-ff3182f7a498cell_id$6fc34de1-469b-41a9-9677-ff3182f7a498code٤Foldable(md"Can `MPI_Allgather` be implemented by combining existing collectives ?", md"`MPI_Allgather` can be implemented by `MPI_Gather` followed by `MPI_Bcast`")metadatashow_logsèdisabled®skip_as_script«code_folded$b53ec488-ff25-4647-ab00-fbf90963a795cell_id$b53ec488-ff25-4647-ab00-fbf90963a795codeٙmd"""
*blocking factor* : Ratio between upper links and lower links. Ratio is 1 for fat-tree to prevent bottlenecks if all nodes start communicating.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$c3c848ff-526a-450d-9b1c-5d9d3ccccf28cell_id$c3c848ff-526a-450d-9b1c-5d9d3ccccf28code#md"## Eager vs rendezvous protocol"metadatashow_logsèdisabled®skip_as_script«code_folded$063f0acc-c023-46d0-9ed9-fbd7fbdcfa3bcell_id$063f0acc-c023-46d0-9ed9-fbd7fbdcfa3bcode*citeintro(what) = "[Eij10; " * what * "]";metadatashow_logsèdisabled®skip_as_script«code_folded$4569aa05-9963-4976-ac63-caf3f3979e83cell_id$4569aa05-9963-4976-ac63-caf3f3979e83codemd"""
Blocking send/received with `MPI_Send` and `MPI_Recv`.
The network cannot buffer the whole message (unless it is short). The sender needs to wait for the receiver to be ready and then transfers its copy of the data.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$7565e3da-84ce-42b6-8d4b-3615576f33b7cell_id$7565e3da-84ce-42b6-8d4b-3615576f33b7codetbegin
struct Path
path::String
end
function imgpath(path::Path)
file = path.path
if !('.' in file)
file = file * ".png"
end
return joinpath(joinpath(@__DIR__, "images", file))
end
function img(path::Path, args...; kws...)
return PlutoUI.LocalResource(imgpath(path), args...)
end
struct URL
url::String
end
function save_image(url::URL, html_attributes...; name = split(url.url, '/')[end], kws...)
path = joinpath("cache", name)
return PlutoTeachingTools.RobustLocalResource(url.url, path, html_attributes...), path
end
function img(url::URL, args...; kws...)
r, _ = save_image(url, args...; kws...)
return @htl("$r")
end
function img(file::String, args...; kws...)
if startswith(file, "http")
img(URL(file), args...; kws...)
else
img(Path(file), args...; kws...)
end
end
end
metadatashow_logsèdisabled®skip_as_script«code_folded$7fc70992-973a-43c6-904a-dd1b622a5ed8cell_id$7fc70992-973a-43c6-904a-dd1b622a5ed8codeټFoldable(md"What is the bisection width ?", md"""
The bisection width is 1 : $(img("https://upload.wikimedia.org/wikipedia/commons/7/79/Bisected_linear_array.jpg", :width => "300pt"))
""")metadatashow_logsèdisabled®skip_as_script«code_folded$fa024a5d-52a6-459d-894d-13a60ec723d2cell_id$fa024a5d-52a6-459d-894d-13a60ec723d2codeFoldable(md"What are the differences with Min-Cut ?",
md"""
In Min-Cut, we fix a node in ``S``, a node in ``V \setminus S``
and the cardinality of `S` is not constrained.
These differences allow Min-Cut to be solvable in polynomial time.
""")metadatashow_logsèdisabled®skip_as_script«code_folded$f7f097cb-d7bd-49eb-a030-ac26f8f61a67cell_id$f7f097cb-d7bd-49eb-a030-ac26f8f61a67codevmd"Fat-tree needs large switches, the root one of previous slide had 8 links. This is as many links as the number of processes, that's not scalable. An alternative is butterfly network for which each switch uses at most 4 links. In the figures above, the boxes with `P` represent a process, the ones with `M` represent their local memory and the other ones are the routers."metadatashow_logsèdisabled®skip_as_script«code_folded$3a2bfd4e-0ce6-4a79-a578-fc1b4ef563c5cell_id$3a2bfd4e-0ce6-4a79-a578-fc1b4ef563c5code'Foldable(md"How to fix it ?", md"""
We should load `gompi` or at least `OpenMPI`:
```sh
[blegat@lm4-f001 examples]$ module load OpenMPI
[blegat@lm4-f001 examples]$ mpicc procname.c
[blegat@lm4-f001 examples]$ mpiexec -n 4 a.out
Process 1/4 is running on node <LINMA2710 - Scientific Computing Distributed Computing with MPI
P.-A. Absil and B. Legat
$(PlutoTeachingTools.ChooseDisplayMode()) $(PlutoUI.TableOfContents(depth=1)) """)metadatashow_logsèdisabled®skip_as_script«code_folded$141d162c-c817-498f-be16-f1cd35d82487cell_id$141d162c-c817-498f-be16-f1cd35d82487codeAFoldable(md"How to collect the partial sums ?", md"`MPI_Reduce`")metadatashow_logsèdisabled®skip_as_script«code_folded$e44b0038-d68f-4a49-9da2-67fbcbe098c3cell_id$e44b0038-d68f-4a49-9da2-67fbcbe098c3codepath(false)metadatashow_logsèdisabled®skip_as_script«code_folded$b5a3e471-af4a-466f-bbae-96306bcc7563cell_id$b5a3e471-af4a-466f-bbae-96306bcc7563codeٽvbox([ Div(md"Get the number of processes. `nprocs` is the **same** on all processes."; style = Dict("flex-grow" => "1")), c""" int nprocs; MPI_Comm_size(MPI_COMM_WORLD, &nprocs); """, ])metadatashow_logsèdisabled®skip_as_script«code_folded$21b6133f-db59-4885-9b3d-331c3d6ef306cell_id$21b6133f-db59-4885-9b3d-331c3d6ef306codemd"## Compiling"metadatashow_logsèdisabled®skip_as_script«code_folded$beee4908-d519-413a-964f-149bb82cdbb8cell_id$beee4908-d519-413a-964f-149bb82cdbb8codemd"## Slurm"metadatashow_logsèdisabled®skip_as_script«code_folded$091dd042-580b-4fda-8086-e048663aed6ccell_id$091dd042-580b-4fda-8086-e048663aed6ccodemd""" * NVIDIA Nsight Systems $(img("https://developer.download.nvidia.com/images/nvidia-nsight-systems-icon-gbp-shaded-256.png", :width => "20pt")) can profile CUDA code but also MPI * Available on `manneback` after loading `CUDA` with $(img("https://github.com/TACC/Lmod/raw/main/logos/2x/Lmod-4color%402x.png", :height => "20px")) ```sh [laptop]$ ssh manneback [blegat@mbackf1 ~]$ nsys -bash: nsys: command not found [blegat@mbackf1 ~]$ ml CUDA [blegat@mbackf1 ~]$ nsys ``` """metadatashow_logsèdisabled®skip_as_script«code_folded$60bc118f-6795-43f9-97a2-865fd1704895cell_id$60bc118f-6795-43f9-97a2-865fd1704895codemd"## Allreduce"metadatashow_logsèdisabled®skip_as_script«code_folded$16f8d28b-f201-4fe5-8446-68d7d9ddfb3ccell_id$16f8d28b-f201-4fe5-8446-68d7d9ddfb3ccode4aside(citeintro("Section 2.7.6.2"), v_offset = -250)metadatashow_logsèdisabled®skip_as_script«code_folded$35aa1295-642f-4525-bf19-df2a42ff39d6cell_id$35aa1295-642f-4525-bf19-df2a42ff39d6codeecompile_and_run(Example("MPI/mpi_sum.c"), mpi = true, num_processes = sum_num_processes, verbose = 1)metadatashow_logsèdisabled®skip_as_script«code_folded$e832ce25-94e2-4743-854d-02b52cc7b56dcell_id$e832ce25-94e2-4743-854d-02b52cc7b56dcodeٯaside(Foldable(md"Why is it the first process that gets the sum ?", md"We gave 0 to the 6th argument of `MPI_Reduce`, this decides which node gets the sum."), v_offset = -100)metadatashow_logsèdisabled®skip_as_script«code_folded$9612a1ef-fd3a-4a58-87b0-b2255ac86331cell_id$9612a1ef-fd3a-4a58-87b0-b2255ac86331codemd"## Graph diameter"metadatashow_logsèdisabled®skip_as_script«code_folded$d7117a24-aba6-4479-a40e-5005310a6b38cell_id$d7117a24-aba6-4479-a40e-5005310a6b38code2aside(citeintro("Section 2.7.3"), v_offset = -150)metadatashow_logsèdisabled®skip_as_script«code_folded$0e640e07-82c7-4dab-a8f1-2f634bbebdeacell_id$0e640e07-82c7-4dab-a8f1-2f634bbebdeacodeZhbox([ img("https://raw.githubusercontent.com/VictorEijkhout/TheArtOfHPC_vol2_parallelprogramming/refs/heads/main/booksources/graphics/send-ideal.png", :height => "150pt"), img("https://raw.githubusercontent.com/VictorEijkhout/TheArtOfHPC_vol2_parallelprogramming/refs/heads/main/booksources/graphics/send-blocking.png", :height => "160pt"), ])metadatashow_logsèdisabled®skip_as_script«code_folded$f2ebc6fb-e07c-4922-897d-9bbe0f5fa1d0cell_id$f2ebc6fb-e07c-4922-897d-9bbe0f5fa1d0code#definition("Bisection bandwidth", hbox([ md""" The *bisection width* is: ```math \min_{S \subset V : \lfloor |V|/2 \rfloor \le |S| \le \lceil |V|/2 \rceil} \quad w(S, V \setminus S) ``` """, Div(html" ", style = Dict("flex-grow" => "1")), md""" The *bisection **band**width* is: ```math \min_{S \subset V : \lfloor |V|/2 \rfloor \le |S| \le \lceil |V|/2 \rceil} \quad \texttt{bw}(S, V \setminus S) ``` """])#)metadatashow_logsèdisabled®skip_as_script«code_folded$55e96151-2aa1-4ea0-b672-2038c57d911ecell_id$55e96151-2aa1-4ea0-b672-2038c57d911ecode|aside(img("https://upload.wikimedia.org/wikipedia/en/3/3e/The_LUMI_supercomputer.jpg", :height => "100pt"), v_offset = -140)metadatashow_logsèdisabled®skip_as_script«code_folded$67dee339-98b4-4714-88b2-8098a13235f2cell_id$67dee339-98b4-4714-88b2-8098a13235f2codemd""" There are two protocols: * Rendezvous protocol 1. the sender sends a header; 2. the receiver returns a ‘ready-to-send’ message; 3. the sender sends the actual data. * Eager protocol the message is buffered so `MPI_Send` can return eagerly, before the receiver is even ready Eager protocol is used if the data size is smaller than the *eager limit*. To force the rendezvous protocol, use `MPI_Ssend`. """metadatashow_logsèdisabled®skip_as_script«code_folded$4e32f7fb-cd5a-4190-9c92-ba4029313475cell_id$4e32f7fb-cd5a-4190-9c92-ba4029313475codeُimg("https://raw.githubusercontent.com/VictorEijkhout/TheArtOfHPC_vol2_parallelprogramming/refs/heads/main/booksources/graphics/mpi-node2.png")metadatashow_logsèdisabled®skip_as_script«code_folded$dbc19cbb-1349-4904-b655-2452aa7e2452cell_id$dbc19cbb-1349-4904-b655-2452aa7e2452codevbox([ md"""Before | `procid` | 1 | 2 | 3 | 4 | |----------|---|---|---|---| | | ``x_{1,1}`` | ``x_{1,2}`` | ``x_{1,3}`` | ``x_{1,4}`` | | | ``x_{2,1}`` | ``x_{2,2}`` | ``x_{2,3}`` | ``x_{2,4}`` | | | ``x_{3,1}`` | ``x_{3,2}`` | ``x_{3,3}`` | ``x_{3,4}`` | | | ``x_{4,1}`` | ``x_{4,2}`` | ``x_{4,3}`` | ``x_{4,4}`` | """, #Div(md"` `", style = Dict("margin" => "50pt")), md"""After `MPI_Reduce_scatter` | `procid` | 1 | 2 | 3 | 4 | |----------|---|---|---|---| | | ``x_{1,1} + \cdots + x_{1,4}`` | | | | | | | ``x_{2,1} + \cdots + x_{2,4}`` | | | | | | | ``x_{3,1} + \cdots + x_{3,4}`` | | | | | | | ``x_{4,1} + \cdots + x_{4,4}`` | """, ])metadatashow_logsèdisabled®skip_as_script«code_folded$0d69e94b-492a-4acc-adba-a2126b871724cell_id$0d69e94b-492a-4acc-adba-a2126b871724code}vbox([ md"""Before | `procid` | 1 | 2 | 3 | 4 | |----------|---|---|---|---| | | ``x_1`` | ``x_2`` | ``x_3`` | ``x_4`` | """, #Div(md"` `", style = Dict("margin" => "50pt")), md"""After `MPI_Allreduce` | `procid` | 1 | 2 | 3 | 4 | |----------|---|---|---|---| | | ``x_1 + \cdots + x_4`` |``x_1 + \cdots + x_4`` | ``x_1 + \cdots + x_4`` | ``x_1 + \cdots + x_4`` | """, ])metadatashow_logsèdisabled®skip_as_script«code_folded$4309dc43-aeb8-4ec7-94fe-0e320b784349cell_id$4309dc43-aeb8-4ec7-94fe-0e320b784349code*md"Special case of multidimensional array"metadatashow_logsèdisabled®skip_as_script«code_folded$1551122c-70ae-4e37-b3fb-4be91fcc4afbcell_id$1551122c-70ae-4e37-b3fb-4be91fcc4afbcodeFoldable( md""" How to order the nodes so that consecutive nodes in the order are adjacent in the graph ? """, md""" Map nodes to binary number and use [Gray code](https://en.wikipedia.org/wiki/Gray_code). $(img("https://raw.githubusercontent.com/VictorEijkhout/TheArtOfHPC_vol1_scientificcomputing/refs/heads/main/booksources/graphics/hypercubenumber.jpg", :width => "300pt")) """ )metadatashow_logsèdisabled®skip_as_script«code_folded$3e98c0ca-1b47-4631-83d7-cd0c8c0a431dcell_id$3e98c0ca-1b47-4631-83d7-cd0c8c0a431dcode)citepara(what) = "[Eij17; " * what * "]";metadatashow_logsèdisabled®skip_as_script«code_folded$3ec3c058-a94d-4717-b99f-66373f2fa31dcell_id$3ec3c058-a94d-4717-b99f-66373f2fa31dcodeّimg("https://raw.githubusercontent.com/VictorEijkhout/TheArtOfHPC_vol1_scientificcomputing/refs/heads/main/booksources/graphics/butterflys.jpeg")metadatashow_logsèdisabled®skip_as_script«code_foldedënotebook_id$59e5308a-9258-11f1-84a2-31aa71d9cdc4in_temp_dir¨metadata