Þ¥bonds€¬cell_resultsÞEÙ$8a51b9c5-8888-4578-ae40-cf906ec9b5faŠ¦queuedÂ¤logs§runningÂ¦output†¤bodyÙÔ

[Eij10] V. Eijkhout. Introduction to High Performance Scientific Computing. 3 Edition, Vol. 1 (Lulu.com, 2010).

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚeÒ#ÜM°persist_js_stateÃ·has_pluto_hook_featuresÂ§cell_idÙ$8a51b9c5-8888-4578-ae40-cf906ec9b5fa¹depends_on_disabled_cellsÂ§runtimeÎñ±óµpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$19943be2-1633-48c9-8cb3-2a73fb96e4aeŠ¦queuedÂ¤logs§runningÂ¦output†¤body ¤mimeªtext/plain¬rootassigneeÀ²last_run_timestampËAÚeÓ6^¦°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$19943be2-1633-48c9-8cb3-2a73fb96e4ae¹depends_on_disabled_cellsÂ§runtimeÎ3ûµpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$98a65469-573e-43b5-9043-f3d0f3198bccŠ¦queuedÂ¤logs§runningÂ¦output†¤bodyÚs ¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚeÓŠô°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$98a65469-573e-43b5-9043-f3d0f3198bcc¹depends_on_disabled_cellsÂ§runtimeÎ jðôµpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$8e337fad-abcf-4ad3-bf75-ab3980f36baaŠ¦queuedÂ¤logs§runningÂ¦output†¤body ¤mimeªtext/plain¬rootassigneeÀ²last_run_timestampËAÚeØÐ°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$8e337fad-abcf-4ad3-bf75-ab3980f36baa¹depends_on_disabled_cellsÂ§runtimeÎ ¹µpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$9e78f2a1-0811-4f61-957d-ad4718430f7fŠ¦queuedÂ¤logs§runningÂ¦output†¤bodyÙt

Cache hierarchy for a multi-core CPU

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚeÒŸœc°persist_js_stateÃ·has_pluto_hook_featuresÂ§cell_idÙ$9e78f2a1-0811-4f61-957d-ad4718430f7f¹depends_on_disabled_cellsÂ§runtimeÎF¿µpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$e83baa29-ad2b-4ffc-99f5-cdbca9e31233Š¦queuedÂ¤logs§runningÂ¦output†¤bodyÙb

Application to parallel sum

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚeÒ¡¦°persist_js_stateÃ·has_pluto_hook_featuresÂ§cell_idÙ$e83baa29-ad2b-4ffc-99f5-cdbca9e31233¹depends_on_disabled_cellsÂ§runtimeÎÐ°µpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$96bffd66-24fc-46f7-b211-57e7d27bc316Š¦queuedÂ¤logs§runningÂ¦output†¤body…¦prefix§Float32¨elementsÜ’’¨0.700597ªtext/plain’’¨0.429158ªtext/plain’’¨0.159631ªtext/plain’’¨0.174324ªtext/plain’’¨0.834876ªtext/plain’’¨0.742624ªtext/plain’’§0.60752ªtext/plain’’¨0.819994ªtext/plain’ ’¨0.744194ªtext/plain’ ’¨0.817196ªtext/plain’’¨0.515746ªtext/plain’’©0.0915513ªtext/plain’ ’¨0.204315ªtext/plain’’¨0.266617ªtext/plain’’©0.0926264ªtext/plain’’§0.73415ªtext/plain’’¨0.392629ªtext/plain’’¨0.409257ªtext/plain’’¨0.427472ªtext/plain’’¨0.535635ªtext/plain¤more’Íÿ÷’¨0.114796ªtext/plain’Íÿø’¨0.943326ªtext/plain’Íÿù’¨0.481296ªtext/plain’Íÿú’¨0.639699ªtext/plain’Íÿû’¨0.645393ªtext/plain’Íÿü’¨0.407587ªtext/plain’Íÿý’¨0.304633ªtext/plain’Íÿþ’¨0.967761ªtext/plain’Íÿÿ’¨0.830977ªtext/plain’Î’¨0.820921ªtext/plain¤type¥Array¬prefix_short ¨objectid°262fefed9465eccd¤mimeÙ!application/vnd.pluto.tree+object¬rootassignee¨many_vec²last_run_timestampËAÚe×>Ì§°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$96bffd66-24fc-46f7-b211-57e7d27bc316¹depends_on_disabled_cellsÂ§runtimeÍÆíµpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$658ca396-2d73-4c93-8138-33c101deee7bŠ¦queuedÂ¤logs§runningÂ¦output†¤bodyÚÎ

Accessing value not in the cache â†’ cache miss
This value is then loaded along with a whole cache line (e.g., 64 or 128 contiguous bytes)
Following cache lines may also be anticipated and prefetched

This shows the importance of data locality. An algorithm performs better if it accesses data close in memory and in a predictable pattern.

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚeÒœ›°persist_js_stateÃ·has_pluto_hook_featuresÂ§cell_idÙ$658ca396-2d73-4c93-8138-33c101deee7b¹depends_on_disabled_cellsÂ§runtimeÎ Ãµpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$d5432907-3e55-4035-9c91-183c37d886eaŠ¦queuedÂ¤logs§runningÂ¦output†¤bodyÚ± ¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚeÓˆžé°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$d5432907-3e55-4035-9c91-183c37d886ea¹depends_on_disabled_cellsÂ§runtimeÎÊjµpublished_object_keys‘Ù573dc2256-4ab3-11f1-b967-89f2e690ee32/8850476c856a19d0¸depends_on_skipped_cellsÂ§erroredÂÙ$e90fd21d-d046-4852-823c-5d7210068923Š¦queuedÂ¤logs§runningÂ¦output†¤bodyÙ‰

Cache coherence : Update L1 cache when the corresponding memory is modified by another core.

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚeÒŸÌ°persist_js_stateÃ·has_pluto_hook_featuresÂ§cell_idÙ$e90fd21d-d046-4852-823c-5d7210068923¹depends_on_disabled_cellsÂ§runtimeÎü4µpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$4b7a62a4-1e88-410b-8549-3021f6cdf6daŠ¦queuedÂ¤logs§runningÂ¦output†¤bodyÚU

$F_s$ : Fraction of $T_1$ that is sequential
$F_p = 1 - F_s$ : Fraction of $T_1$ that is parallelizable

$$\begin{align} T_p &= T_1F_s + T_1F_p/p\\ S_p &= \frac{1}{F_s + F_p/p} & E_p &= \frac{1}{pF_s + F_p}\\ \lim_{p \to \infty} S_p &= \frac{1}{F_s} \end{align}$$

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚeÒ¡SL°persist_js_stateÃ·has_pluto_hook_featuresÂ§cell_idÙ$4b7a62a4-1e88-410b-8549-3021f6cdf6da¹depends_on_disabled_cellsÂ§runtimeÎîßµpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$b26ab400-ce89-4a76-ad48-464ac6821dd2Š¦queuedÂ¤logs§runningÂ¦output†¤bodyÙL

Amdahl's law

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚeÒ¡³°persist_js_stateÃ·has_pluto_hook_featuresÂ§cell_idÙ$b26ab400-ce89-4a76-ad48-464ac6821dd2¹depends_on_disabled_cellsÂ§runtimeÎÓØµpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$34519b36-0e60-4c2c-92d6-3b8ed71e6ad1Š¦queuedÂ¤logs§runningÂ¦output†¤body ¤mimeªtext/plain¬rootassigneeÀ²last_run_timestampËAÚeÐËõË°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$34519b36-0e60-4c2c-92d6-3b8ed71e6ad1¹depends_on_disabled_cellsÂ§runtimeÎCçûµpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$1f45bab8-afb7-4cd2-8a37-1f258f37ad8fŠ¦queuedÂ¤logs§runningÂ¦output†¤bodyÙJ

Many processors

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚeÒ $°persist_js_stateÃ·has_pluto_hook_featuresÂ§cell_idÙ$1f45bab8-afb7-4cd2-8a37-1f258f37ad8f¹depends_on_disabled_cellsÂ§runtimeÎz¸µpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$e7445ed8-cbf7-475d-bd67-3df8d9015de2Š¦queuedÂ¤logs§runningÂ¦output†¤bodyÙD

Parallel sum

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚeÒŸù‡°persist_js_stateÃ·has_pluto_hook_featuresÂ§cell_idÙ$e7445ed8-cbf7-475d-bd67-3df8d9015de2¹depends_on_disabled_cellsÂ§runtimeÎ?ðµpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$ccfd4488-a32a-4b35-a922-2e830f91ca08Š¦queuedÂ¤logs§runningÂ¦output†¤body ¤mimeªtext/plain¬rootassigneeÀ²last_run_timestampËAÚeÓµ°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$ccfd4488-a32a-4b35-a922-2e830f91ca08¹depends_on_disabled_cellsÂ§runtimeÎ!%|µpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$ebe1cd42-ba25-4538-acbe-353e0e47009eŠ¦queuedÂ¤logs§runningÂ¦output†¤body ¤mimeªtext/plain¬rootassigneeÀ²last_run_timestampËAÚeÓÍ’¸°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$ebe1cd42-ba25-4538-acbe-353e0e47009e¹depends_on_disabled_cellsÂ§runtimeÎÒúµpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$8b98b33e-f65d-4cbd-9e80-20a7132cd349Š¦queuedÂ¤logs§runningÂ¦output†¤body£0.2¤mimeªtext/plain¬rootassigneeÀ²last_run_timestampËAÚeÙ¢8v°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$8b98b33e-f65d-4cbd-9e80-20a7132cd349¹depends_on_disabled_cellsÂ§runtimeÎÚO¿µpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$1b9fb8aa-71cf-4e69-ad84-666c1b66bb5eŠ¦queuedÂ¤logs§runningÂ¦output†¤bodyÚÍ

Can you spot the issue in the code ?

The same variable total is shared between the threads, so its value in the register should be sync'ed between the threads, this is a performance issue! More importantly, the access to the total variable are not atomic. Therefore, two threads may read the value, add, and then store â†’ only one of the two add will then be accounted for! Let's fix this ?

This is still a performance issue, can you see why ?

The entries of local_results are close to each other in memory. There are therefore very likely going to be part of the same block on cache. This means that when one threads modifies it, the cache block will need to be written and then other threads will need to refresh the value of this block in their cache. variable total is shared between the threads, so its value in the register should be sync'ed between the threads! This is called false sharing. Let's fix this ?

Wait, these didn't make any difference in the benchmark, how can it be ?

The compiler most probably use a register (actually a SIMD register here (if there is any) since we used #pragma omp simd) as accumulator for the for loop and only stored the value of that register into total, local_results[thread_num] or no_false_sharing (depending on the version). Despite all this, it is still important to be careful about this issue and not trust the execution on one environment or rely too much on compiler optimizations for the code to be portable.

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚeÓ®&È°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$1b9fb8aa-71cf-4e69-ad84-666c1b66bb5e¹depends_on_disabled_cellsÂ§runtimeÎUd7µpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$f95dd40b-8c56-4e10-abbc-3dbb58148e1fŠ¦queuedÂ¤logs§runningÂ¦output†¤bodyÙL

Amdahl's law

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚeÒ ªC°persist_js_stateÃ·has_pluto_hook_featuresÂ§cell_idÙ$f95dd40b-8c56-4e10-abbc-3dbb58148e1f¹depends_on_disabled_cellsÂ§runtimeÎÚ‡µpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$d8238145-9787-40f0-a151-1ef73d8c97eeŠ¦queuedÂ¤logs§runningÂ¦output†¤bodyƒ¨children’’Û óŸ

©text/html’Û0_

©text/html©classnameÀ¥styleÙ#display: flex; flex-direction: row;¤mimeÙ'application/vnd.pluto.divelement+object¬rootassigneeÀ²last_run_timestampËAÚeÚ28°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$d8238145-9787-40f0-a151-1ef73d8c97ee¹depends_on_disabled_cellsÂ§runtimeÎþáµpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$a32ba8f2-a9c9-41c6-99b4-577f0823bd9fŠ¦queuedÂ¤logs§runningÂ¦output†¤bodyÙ\

Cache lines and prefetch

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚeÒ–c•°persist_js_stateÃ·has_pluto_hook_featuresÂ§cell_idÙ$a32ba8f2-a9c9-41c6-99b4-577f0823bd9f¹depends_on_disabled_cellsÂ§runtimeÎ›µpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$cd6c2bda-e80d-46ba-8242-f0f61a250471Š¦queuedÂ¤logs§runningÂ¦output†¤bodyÙ+definition (generic function with 1 method)¤mimeªtext/plain¬rootassigneeÀ²last_run_timestampËAÚeÚ\«°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$cd6c2bda-e80d-46ba-8242-f0f61a250471¹depends_on_disabled_cellsÂ§runtimeÎk_µpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$253bd533-99b7-4012-b3f4-e86a2466a919Š¦queuedÂ¤logs§runningÂ¦output†¤body ¤mimeªtext/plain¬rootassigneeÀ²last_run_timestampËAÚeÓ×Kb°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$253bd533-99b7-4012-b3f4-e86a2466a919¹depends_on_disabled_cellsÂ§runtimeÎ":µpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$910fc9b2-c57d-4874-b8b2-df440fc921c0Š¦queuedÂ¤logs‘ˆ¤lineÿ£msg’Ù& 9.137 Î¼s (3 allocations: 80 bytes) ªtext/plain§cell_idÙ$910fc9b2-c57d-4874-b8b2-df440fc921c0¦kwargs¢id´PlutoRunner_d1acb81e¤fileÙP/home/runner/.julia/packages/Pluto/1XRxx/src/runner/PlutoRunner/src/io/stdout.jl¥group¦stdout¥level®LogLevel(-555)§runningÂ¦output†¤body«32735.955f0¤mimeªtext/plain¬rootassigneeÀ²last_run_timestampËAÚeÙ‘›°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$910fc9b2-c57d-4874-b8b2-df440fc921c0¹depends_on_disabled_cellsÂ§runtimeÏu ‡µpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$6f70144e-5240-41ef-a719-8a8942e18feeŠ¦queuedÂ¤logs§runningÂ¦output†¤bodyÛó

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚeÚÈ`°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$6f70144e-5240-41ef-a719-8a8942e18fee¹depends_on_disabled_cellsÂ§runtimeÎ›µpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$caec43a3-9bac-4f73-a8e5-288cfa9e1606Š¦queuedÂ¤logs§runningÂ¦output†¤bodyÚw ¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚeÒÔ<§°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$caec43a3-9bac-4f73-a8e5-288cfa9e1606¹depends_on_disabled_cellsÂ§runtimeÍBµpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$db24839c-eb42-4d5c-8545-3714abc01bc5Š¦queuedÂ¤logs§runningÂ¦output†¤bodyÙ>

Benchmark

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚeÒ Ný°persist_js_stateÃ·has_pluto_hook_featuresÂ§cell_idÙ$db24839c-eb42-4d5c-8545-3714abc01bc5¹depends_on_disabled_cellsÂ§runtimeÎÚµpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$6657e4dd-f5c2-47c4-b0d6-a2a56aac7b96Š¦queuedÂ¤logs§runningÂ¦output†¤body ¤mimeªtext/plain¬rootassigneeÀ²last_run_timestampËAÚeØÇ\°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$6657e4dd-f5c2-47c4-b0d6-a2a56aac7b96¹depends_on_disabled_cellsÂ§runtimeÎ 8ßµpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$ea9ff1a9-615d-4e18-a4c8-9aad20447156Š¦queuedÂ¤logs§runningÂ¦output†¤bodyÚw ¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚeÓAº°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$ea9ff1a9-615d-4e18-a4c8-9aad20447156¹depends_on_disabled_cellsÂ§runtimeÍ=µpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$c0bda86a-136b-45ca-84ba-7365c367d265Š¦queuedÂ¤logs§runningÂ¦output†¤bodyÙT

Arithmetic intensity

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚeÒž¨D°persist_js_stateÃ·has_pluto_hook_featuresÂ§cell_idÙ$c0bda86a-136b-45ca-84ba-7365c367d265¹depends_on_disabled_cellsÂ§runtimeÎ‡öµpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$11b1c6a8-3918-4dda-9028-17af2d6c44c4Š¦queuedÂ¤logs§runningÂ¦output†¤bodyÚ`

Consider a program requiring m load / store operations with memory for o arithmetic operations.

The arithmetic intensity is the ratio $a = o / m$.
The arithmetic time is $t_\text{arith} = o / \text{frequency}$
The data transfer time is $t_\text{mem} = m / \text{bandwidth} = o / (a \cdot \text{bandwidth})$

As arithmetic operations and data transfer are done in parallel, the time per iteration is

$$\max(t_\text{arith}, t_\text{mem}) / o = 1/\min(\text{frequency}, a \cdot \text{bandwidth})$$

So the number of operations per second is $\min(\text{frequency}, a \cdot \text{bandwidth})$.

This piecewise linear function in $a$ gives the roofline model.

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚeÒžýa°persist_js_stateÃ·has_pluto_hook_featuresÂ§cell_idÙ$11b1c6a8-3918-4dda-9028-17af2d6c44c4¹depends_on_disabled_cellsÂ§runtimeÎWòµpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$d221bad8-98fb-4c1d-9c9c-66e1b697f023Š¦queuedÂ¤logs§runningÂ¦output†¤bodyÚ7

compute-bound : For large arithmetic intensity (Alg2 in above picture), performance determined by processor characteristics
bandwidth-bound : For low arithmetic intensity (Alg1 in above picture), performance determined by memory characteristics
Bandwidth line may be lowered by inefficient memory access (e.g., no locality)
Peak performance line may be lowered by inefficient use of CPU (e.g., not using SIMD)

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚeÒŸo?°persist_js_stateÃ·has_pluto_hook_featuresÂ§cell_idÙ$d221bad8-98fb-4c1d-9c9c-66e1b697f023¹depends_on_disabled_cellsÂ§runtimeÎ •Nµpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$a7118fbb-66d6-44a1-a6ae-839f0e42a3ecŠ¦queuedÂ¤logs‘ˆ¤lineÿ£msg’Ù% 3.078 Î¼s (0 allocations: 0 bytes) ªtext/plain§cell_idÙ$a7118fbb-66d6-44a1-a6ae-839f0e42a3ec¦kwargs¢id´PlutoRunner_d1acb81e¤fileÙP/home/runner/.julia/packages/Pluto/1XRxx/src/runner/PlutoRunner/src/io/stdout.jl¥group¦stdout¥level®LogLevel(-555)§runningÂ¦output†¤body«32735.955f0¤mimeªtext/plain¬rootassigneeÀ²last_run_timestampËAÚe×ô&5°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$a7118fbb-66d6-44a1-a6ae-839f0e42a3ec¹depends_on_disabled_cellsÂ§runtimeÎ¨çïµpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$6e8865f5-84ad-4083-bb19-57ad1b561fabŠ¦queuedÂ¤logs§runningÂ¦output†¤bodyÙP

The roofline model

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚeÒŸ+¿°persist_js_stateÃ·has_pluto_hook_featuresÂ§cell_idÙ$6e8865f5-84ad-4083-bb19-57ad1b561fab¹depends_on_disabled_cellsÂ§runtimeÎU©µpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$d718f117-41da-42ff-9bcd-8bef0e7e6974Š¦queuedÂ¤logs§runningÂ¦output†¤bodyÙn

If we have many processors, we may want to speed up the last part as well:

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚeÒ }°persist_js_stateÃ·has_pluto_hook_featuresÂ§cell_idÙ$d718f117-41da-42ff-9bcd-8bef0e7e6974¹depends_on_disabled_cellsÂ§runtimeÎÃµpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$3887824b-7c7f-4c24-bf6d-7a55ed7adc89Š¦queuedÂ¤logs§runningÂ¦output†¤bodyÙF

Memory layout

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚeÒ2?Í°persist_js_stateÃ·has_pluto_hook_featuresÂ§cell_idÙ$3887824b-7c7f-4c24-bf6d-7a55ed7adc89¹depends_on_disabled_cellsÂ§runtimeÎçµpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$050a67f8-7f02-4ac9-8ac4-20327d46c5e8Š¦queuedÂ¤logs§runningÂ¦output†¤body ¤mimeªtext/plain¬rootassigneeÀ²last_run_timestampËAÚe×ôW÷°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$050a67f8-7f02-4ac9-8ac4-20327d46c5e8¹depends_on_disabled_cellsÂ§runtimeÎƒµpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$62297efe-3a15-4dab-ac17-b823ab3e7933Š¦queuedÂ¤logs‘ˆ¤lineÿ£msg’Ù% 2.774 Î¼s (0 allocations: 0 bytes) ªtext/plain§cell_idÙ$62297efe-3a15-4dab-ac17-b823ab3e7933¦kwargs¢id´PlutoRunner_d1acb81e¤fileÙP/home/runner/.julia/packages/Pluto/1XRxx/src/runner/PlutoRunner/src/io/stdout.jl¥group¦stdout¥level®LogLevel(-555)§runningÂ¦output†¤body«32811.023f0¤mimeªtext/plain¬rootassigneeÀ²last_run_timestampËAÚeÖq÷×°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$62297efe-3a15-4dab-ac17-b823ab3e7933¹depends_on_disabled_cellsÂ§runtimeÎŸŒ]µpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$31727049-ac0a-45a6-aae0-934d4549b541Š¦queuedÂ¤logs‘ˆ¤lineÿ£msg’Ù& 2.340 Î¼s (3 allocations: 80 bytes) ªtext/plain§cell_idÙ$31727049-ac0a-45a6-aae0-934d4549b541¦kwargs¢id´PlutoRunner_d1acb81e¤fileÙP/home/runner/.julia/packages/Pluto/1XRxx/src/runner/PlutoRunner/src/io/stdout.jl¥group¦stdout¥level®LogLevel(-555)§runningÂ¦output†¤bodyª32811.03f0¤mimeªtext/plain¬rootassigneeÀ²last_run_timestampËAÚe×4’°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$31727049-ac0a-45a6-aae0-934d4549b541¹depends_on_disabled_cellsÂ§runtimeÎ´rÇµpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$2a1f3d29-4d6b-4634-86f3-4ecd4a7821a2Š¦queuedÂ¤logs§runningÂ¦output†¤bodyÙX

Speed-up and efficency

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚeÒ ÖÐ°persist_js_stateÃ·has_pluto_hook_featuresÂ§cell_idÙ$2a1f3d29-4d6b-4634-86f3-4ecd4a7821a2¹depends_on_disabled_cellsÂ§runtimeÎ3iµpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$81465bf1-8e54-461f-892c-2769bf94fdfeŠ¦queuedÂ¤logs§runningÂ¦output†¤bodyÚ

Latency of n bytes of data is given by

$$\alpha + \beta n$$

where $\alpha$ is the start up time and $\beta$ is the inverse of the bandwidth.

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚeÒ–5Î°persist_js_stateÃ·has_pluto_hook_featuresÂ§cell_idÙ$81465bf1-8e54-461f-892c-2769bf94fdfe¹depends_on_disabled_cellsÂ§runtimeÎ=²µpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$3a5d674d-7c5b-4dac-b9ae-d65a1e9a5cbaŠ¦queuedÂ¤logs§runningÂ¦output†¤body…¦prefix§Float32¨elementsÜ’’§0.85051ªtext/plain’’©0.0503311ªtext/plain’’¨0.198103ªtext/plain’’©0.0931568ªtext/plain’’©0.0859969ªtext/plain’’¨0.695007ªtext/plain’’¨0.736921ªtext/plain’’¨0.212104ªtext/plain’ ’¨0.362795ªtext/plain’ ’¨0.110771ªtext/plain’’¨0.555139ªtext/plain’’©0.0231498ªtext/plain’ ’¨0.835648ªtext/plain’’¨0.349553ªtext/plain’’¨0.663635ªtext/plain’’¨0.100212ªtext/plain’’©0.0345355ªtext/plain’’¨0.931736ªtext/plain’’§0.53907ªtext/plain’’§0.26969ªtext/plain¤more’Íÿ÷’§0.73696ªtext/plain’Íÿø’§0.26269ªtext/plain’Íÿù’¨0.617377ªtext/plain’Íÿú’¨0.540314ªtext/plain’Íÿû’¨0.849055ªtext/plain’Íÿü’¨0.216793ªtext/plain’Íÿý’¨0.796756ªtext/plain’Íÿþ’¨0.767626ªtext/plain’Íÿÿ’¨0.954686ªtext/plain’Î’¨0.186273ªtext/plain¤type¥Array¬prefix_short ¨objectid°57a27ca5a9c857f3¤mimeÙ!application/vnd.pluto.tree+object¬rootassignee£vec²last_run_timestampËAÚeÓ¨2n°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$3a5d674d-7c5b-4dac-b9ae-d65a1e9a5cba¹depends_on_disabled_cellsÂ§runtimeÎ‹}µpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$6c021710-5828-4ac0-8619-ce690ba89d5fŠ¦queuedÂ¤logs§runningÂ¦output†¤bodyÚ± ¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚe×=ëŽ°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$6c021710-5828-4ac0-8619-ce690ba89d5f¹depends_on_disabled_cellsÂ§runtimeÎ: µpublished_object_keys‘Ù573dc2256-4ab3-11f1-b967-89f2e690ee32/3583170c6e86b605¸depends_on_skipped_cellsÂ§erroredÂÙ$e867d9be-5668-4756-af7f-c23c48962f08Š¦queuedÂ¤logs§runningÂ¦output†¤bodyÚv ¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚeÒÓOÆ°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$e867d9be-5668-4756-af7f-c23c48962f08¹depends_on_disabled_cellsÂ§runtimeÍCçµpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$de0bbef2-1240-4f85-889f-0af509d6cfffŠ¦queuedÂ¤logs§runningÂ¦output†¤bodyÚý ¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚeÓ@(¿°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$de0bbef2-1240-4f85-889f-0af509d6cfff¹depends_on_disabled_cellsÂ§runtimeÎ¶’µpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$d52b5227-0ef4-4dc6-b443-03364b0caeffŠ¦queuedÂ¤logs§runningÂ¦output†¤body ¤mimeªtext/plain¬rootassigneeÀ²last_run_timestampËAÚeÒÇ^°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$d52b5227-0ef4-4dc6-b443-03364b0caeff¹depends_on_disabled_cellsÂ§runtimeÎõ½µpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$138caa9b-1d53-4c01-a3b9-c1a097413736Š¦queuedÂ¤logs§runningÂ¦output†¤bodyÛú3

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚeÙézp°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$138caa9b-1d53-4c01-a3b9-c1a097413736¹depends_on_disabled_cellsÂ§runtimeÎþ#{µpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$d1aef3d4-33d1-4151-8ba3-2169f734ea6bŠ¦queuedÂ¤logs§runningÂ¦output†¤bodyÚÍ

How to get $1/F_s = \lim_{p \to \infty} S_p$ ?

The algorithm cannot use more than $n$ processes so if $p \ge n$, we have $T_p = 1 + \log_2(n)$. Therefore, $\lim_{p \to \infty} S_p = S_n = \frac{n}{1 + \log_2(n)}$. Ignoring the constant $1$, we get $F_s = \log_2(n)/n$.

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚeÙ–¤¾°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$d1aef3d4-33d1-4151-8ba3-2169f734ea6b¹depends_on_disabled_cellsÂ§runtimeÎtµpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$947b8e5c-9cb7-4fe6-aff6-48416879fb43Š¦queuedÂ¤logs‘ˆ¤lineÿ£msg’Ùathread id : 0 / 2 0:32767 thread id : 1 / 2 32768:65535 thread id : 0 / 1 0:1 0.000088 seconds ªtext/plain§cell_idÙ$947b8e5c-9cb7-4fe6-aff6-48416879fb43¦kwargs¢id´PlutoRunner_d1acb81e¤fileÙP/home/runner/.julia/packages/Pluto/1XRxx/src/runner/PlutoRunner/src/io/stdout.jl¥group¦stdout¥level®LogLevel(-555)§runningÂ¦output†¤body«32811.023f0¤mimeªtext/plain¬rootassigneeÀ²last_run_timestampËAÚeÙ“Ø°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$947b8e5c-9cb7-4fe6-aff6-48416879fb43¹depends_on_disabled_cellsÂ§runtimeÎÜCOµpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$4b9cfb4d-2355-42e3-be2f-35e2638e984bŠ¦queuedÂ¤logs§runningÂ¦output†¤bodyÚ!

#include <vector>
#include <stdint.h>
#include <omp.h>
#include <stdio.h>

extern "C" {
float sum(float *vec, int length, int num_threads, int verbose) {
  float total = 0;
  omp_set_dynamic(0); // Force the value `num_threads`
  omp_set_num_threads(num_threads);
  #pragma omp parallel
  {
    int thread_num = omp_get_thread_num();
	int stride = length / num_threads;
    int last = stride * (thread_num + 1);
    if (thread_num + 1 == num_threads)
      last = length;
	if (verbose >= 1)
      fprintf(stderr, "thread id : %d / %d %d:%d\n", thread_num, omp_get_num_threads(), stride * thread_num, last - 1);
    #pragma omp simd
    for (int i = stride * thread_num; i < last; i++)
      total += vec[i];
  }
  return total;
}
}

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚeÓÖ÷ƒ°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$4b9cfb4d-2355-42e3-be2f-35e2638e984b¹depends_on_disabled_cellsÂ§runtimeÍ!9µpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$3bff6f16-ad66-4aed-9a29-4bdcfe41b57fŠ¦queuedÂ¤logs§runningÂ¦output†¤bodyÚV]

LINMA2710 - Scientific Computing Shared-Memory Multiprocessing

P.-A. Absil and B. Legat

Full Width Mode Present Mode ¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚeÒÆå“°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$3bff6f16-ad66-4aed-9a29-4bdcfe41b57f¹depends_on_disabled_cellsÂ§runtimeÎ.£µpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$f7da896d-089c-4430-b82c-db86c380b171Š¦queuedÂ¤logs§runningÂ¦output†¤bodyÚ@

The first sum_to takes $n/p$ operations. Assuming factor is 2, there is one operation for each of the $\log_2(p)$ subsequent sum_to.

$$\begin{align} T_1 & = n\\ T_p & = n/p + \log_2(p)\\ S_p & = \frac{1}{1/p + \log_2(p)/n} & E_p & = \frac{1}{1 + p\log_2(p)/n} \end{align}$$

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚeÒ¡ÜÊ°persist_js_stateÃ·has_pluto_hook_featuresÂ§cell_idÙ$f7da896d-089c-4430-b82c-db86c380b171¹depends_on_disabled_cellsÂ§runtimeÎ@4µpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$655d59f3-665b-410b-b534-afadae96295bŠ¦queuedÂ¤logs§runningÂ¦output†¤bodyÚÚ ¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚeÒÐÌš°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$655d59f3-665b-410b-b534-afadae96295b¹depends_on_disabled_cellsÂ§runtimeÎE µpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$5d7cd5e3-5fc2-4835-bea1-c4897467365bŠ¦queuedÂ¤logs§runningÂ¦output†¤bodyÚÝ

#include <stdio.h>

float sum(float *mat, int n, int m) {
  float total = 0;
  for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
	  total += mat[i + j * n];
	}
  }
  return total;
}

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚeÓ9½f°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$5d7cd5e3-5fc2-4835-bea1-c4897467365b¹depends_on_disabled_cellsÂ§runtimeÍ6µpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$81da94b8-1bbf-4773-ba53-d229452cef75Š¦queuedÂ¤logs§runningÂ¦output†¤bodyÚ‚256Ã—256 Matrix{Float32}: 0.0597793 0.417787 0.126267 0.859484 â€¦ 0.371382 0.500273 0.938325 0.535802 0.242073 0.0661986 0.185958 0.154594 0.210403 0.471678 0.650056 0.062982 0.59131 0.536327 0.966751 0.744848 0.274031 0.318135 0.288982 0.104517 0.251897 0.251931 0.234469 0.0543474 0.427851 0.45264 0.0766009 0.310852 0.746904 0.00116313 0.693265 0.737975 0.119318 0.209818 0.86741 â€¦ 0.468451 0.139429 0.0551009 0.0502196 0.897035 0.595642 0.305991 0.0977772 0.160193 0.243116 â‹® â‹± â‹® 0.420051 0.933573 0.288458 0.385103 â€¦ 0.733172 0.30978 0.991448 0.105571 0.65548 0.528511 0.605652 0.0840088 0.853477 0.7249 0.947079 0.30351 0.6983 0.179855 0.841775 0.839626 0.217399 0.143247 0.649893 0.37815 0.672719 0.215264 0.902336 0.00395232 0.00201213 0.883567 0.349935 0.920309 0.647945 0.369827 0.625111 0.579034 0.364038 0.0776384 0.0328473 â€¦ 0.573341 0.850136 0.074568¤mimeªtext/plain¬rootassignee£mat²last_run_timestampËAÚeÒïCÝ°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$81da94b8-1bbf-4773-ba53-d229452cef75¹depends_on_disabled_cellsÂ§runtimeÎ–µpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$258817e3-8495-4136-8cb9-00a4475245b2Š¦queuedÂ¤logs§runningÂ¦output†¤bodyÚÕ

#include <omp.h>
#include <stdio.h>

extern "C" {
void sum_to(float *vec, int length, float *local_results, int num_threads, int verbose) {
  omp_set_dynamic(0); // Force the value `num_threads`
  omp_set_num_threads(num_threads);
  #pragma omp parallel
  {
    int thread_num = omp_get_thread_num();
	int stride = length / num_threads;
    int last = stride * (thread_num + 1);
    if (thread_num + 1 == num_threads)
      last = length;
	if (verbose >= 1)
      fprintf(stderr, "thread id : %d / %d %d:%d\n", thread_num, omp_get_num_threads(), stride * thread_num, last - 1);
	float no_false_sharing = 0;
    #pragma omp simd
    for (int i = stride * thread_num; i < last; i++)
      no_false_sharing += vec[i];
	local_results[thread_num] = no_false_sharing;
  }
}

float sum(float *vec, int length, int num_threads, int factor, int verbose) {
  float* buffers[2] = {new float[num_threads], new float[num_threads / factor]};
  sum_to(vec, length, buffers[0], num_threads, verbose);
  int prev = num_threads, cur;
  int buffer_idx = 0;
  for (cur = num_threads / factor; cur > 0; cur /= factor) {
	sum_to(buffers[buffer_idx % 2], prev, buffers[(buffer_idx + 1) % 2], cur, verbose);
	prev = cur;
	buffer_idx += 1;
  }
  if (prev == 1)
	return buffers[buffer_idx % 2][0];
  sum_to(buffers[buffer_idx % 2], prev, buffers[(buffer_idx + 1) % 2], 1, verbose);
  return buffers[(buffer_idx + 1) % 2][0];
}
}

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚeØ„'°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$258817e3-8495-4136-8cb9-00a4475245b2¹depends_on_disabled_cellsÂ§runtimeÍ#µpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$a144f991-3af4-4f88-a7e8-c1f3e9d7f7e2Š¦queuedÂ¤logs§runningÂ¦output†¤bodyÚÄ’ ¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚeÚ>ÿ°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$a144f991-3af4-4f88-a7e8-c1f3e9d7f7e2¹depends_on_disabled_cellsÂ§runtimeÎJŠxµpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$dbe9c6d8-611e-46f9-9a8e-2b3647e813faŠ¦queuedÂ¤logs§runningÂ¦output†¤bodyÚlñ

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚeÙã°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$dbe9c6d8-611e-46f9-9a8e-2b3647e813fa¹depends_on_disabled_cellsÂ§runtimeÎÖL…µpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$4ae73a28-d945-4c1b-a281-aa4931bf0bfdŠ¦queuedÂ¤logs‘ˆ¤lineÿ£msg’Ù& 79.369 Î¼s (0 allocations: 0 bytes) ªtext/plain§cell_idÙ$4ae73a28-d945-4c1b-a281-aa4931bf0bfd¦kwargs¢id´PlutoRunner_d1acb81e¤fileÙP/home/runner/.julia/packages/Pluto/1XRxx/src/runner/PlutoRunner/src/io/stdout.jl¥group¦stdout¥level®LogLevel(-555)§runningÂ¦output†¤body«32710.873f0¤mimeªtext/plain¬rootassigneeÀ²last_run_timestampËAÚeÕÆaö°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$4ae73a28-d945-4c1b-a281-aa4931bf0bfd¹depends_on_disabled_cellsÂ§runtimeÏáJÒ•µpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$19655acd-5880-44fa-ac29-d56faf43e87bŠ¦queuedÂ¤logs§runningÂ¦output†¤body ¤mimeªtext/plain¬rootassigneeÀ²last_run_timestampËAÚeÓ¯~°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$19655acd-5880-44fa-ac29-d56faf43e87b¹depends_on_disabled_cellsÂ§runtimeÎ59òµpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$b2b3beda-c8bf-4616-b1bd-bdd907d11636Š¦queuedÂ¤logs§runningÂ¦output†¤bodyƒ¨children“’Ùº

Def: Speed-up

$$S_p = \frac{T_1}{T_p}$$

Def: Efficiency

$$E_p = \frac{S_p}{p}$$

Let $T_p$ bet the time with $p$ processes

$E_p > 1$ â†’ Unlikely
$E_p = 1$ â†’ Ideal
$E_p < 1$ â†’ Realistic

©text/html©classnameÀ¥style»flex-grow: 1; margin: 30px;Ù'application/vnd.pluto.divelement+object©classnameÀ¥styleÙQalign-items: center; display: flex; flex-direction: row; justify-content: center;¤mimeÙ'application/vnd.pluto.divelement+object¬rootassigneeÀ²last_run_timestampËAÚeÚDÐ°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$b2b3beda-c8bf-4616-b1bd-bdd907d11636¹depends_on_disabled_cellsÂ§runtimeÎ ¬l–µpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$37d9b5f0-48b6-4ff3-873d-592230687995Š¦queuedÂ¤logs§runningÂ¦output†¤bodyÙ>

Hierarchy

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚeÒ…ôª°persist_js_stateÃ·has_pluto_hook_featuresÂ§cell_idÙ$37d9b5f0-48b6-4ff3-873d-592230687995¹depends_on_disabled_cellsÂ§runtimeÎ´¼µpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$fa017c45-6410-4c14-b9a2-ede33759d396Š¦queuedÂ¤logs§runningÂ¦output†¤body ¤mimeªtext/plain¬rootassigneeÀ²last_run_timestampËAÚeÓ60”°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$fa017c45-6410-4c14-b9a2-ede33759d396¹depends_on_disabled_cellsÂ§runtimeÎKLüµpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$91f7f3fe-cb4d-4461-9147-81c72b650a4bŠ¦queuedÂ¤logs§runningÂ¦output†¤bodyÙ%img (generic function with 3 methods)¤mimeªtext/plain¬rootassigneeÀ²last_run_timestampËAÚeÙ¬x6°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$91f7f3fe-cb4d-4461-9147-81c72b650a4b¹depends_on_disabled_cellsÂ§runtimeÎ˜Vjµpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$b5f1d18c-53ad-4441-8ca8-e02d6ab840d0Š¦queuedÂ¤logs‘ˆ¤lineÿ£msg’ÙKthread id : 0 / 2 0:32767 thread id : 1 / 2 32768:65535 0.000062 seconds ªtext/plain§cell_idÙ$b5f1d18c-53ad-4441-8ca8-e02d6ab840d0¦kwargs¢id´PlutoRunner_d1acb81e¤fileÙP/home/runner/.julia/packages/Pluto/1XRxx/src/runner/PlutoRunner/src/io/stdout.jl¥group¦stdout¥level®LogLevel(-555)§runningÂ¦output†¤bodyª32811.03f0¤mimeªtext/plain¬rootassigneeÀ²last_run_timestampËAÚe×=Là°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$b5f1d18c-53ad-4441-8ca8-e02d6ab840d0¹depends_on_disabled_cellsÂ§runtimeÎˆd¢µpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$c6ea9bc5-bb15-4e25-a854-de3417d736a6Š¦queuedÂ¤logs§runningÂ¦output†¤bodyÚw ¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚeÓAö{°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$c6ea9bc5-bb15-4e25-a854-de3417d736a6¹depends_on_disabled_cellsÂ§runtimeÍ<Ûµpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$02be0de6-70dc-4cf4-b630-b541a304eecdŠ¦queuedÂ¤logs§runningÂ¦output†¤bodyÛoK

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚeÙê,Ô°persist_js_stateÂ·has_pluto_hook_featuresÂ§cell_idÙ$02be0de6-70dc-4cf4-b630-b541a304eecd¹depends_on_disabled_cellsÂ§runtimeÎºjµpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂÙ$f26f0a70-c16b-491d-b4cf-45ca146727c2Š¦queuedÂ¤logs§runningÂ¦output†¤bodyÙ`

Illustration with matrices

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÚeÒœJ¥°persist_js_stateÃ·has_pluto_hook_featuresÂ§cell_idÙ$f26f0a70-c16b-491d-b4cf-45ca146727c2¹depends_on_disabled_cellsÂ§runtimeÎH2µpublished_object_keys¸depends_on_skipped_cellsÂ§erroredÂ±cell_dependenciesÞEÙ$8a51b9c5-8888-4578-ae40-cf906ec9b5fa„´precedence_heuristic §cell_idÙ$8a51b9c5-8888-4578-ae40-cf906ec9b5fa´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$19943be2-1633-48c9-8cb3-2a73fb96e4ae„´precedence_heuristic §cell_idÙ$19943be2-1633-48c9-8cb3-2a73fb96e4ae´downstream_cells_map¥c_sum•Ù$4ae73a28-d945-4c1b-a281-aa4931bf0bfdÙ$62297efe-3a15-4dab-ac17-b823ab3e7933Ù$31727049-ac0a-45a6-aae0-934d4549b541Ù$b5f1d18c-53ad-4441-8ca8-e02d6ab840d0Ù$a7118fbb-66d6-44a1-a6ae-839f0e42a3ec²upstream_cells_map‡®sum_matrix_lib‘Ù$fa017c45-6410-4c14-b9a2-ede33759d396£Ptr¦Matrix¦Cfloat¤size¤Cint¥ccallÙ$98a65469-573e-43b5-9043-f3d0f3198bcc„´precedence_heuristic §cell_idÙ$98a65469-573e-43b5-9043-f3d0f3198bcc´downstream_cells_map«column_wise‘Ù$fa017c45-6410-4c14-b9a2-ede33759d396²upstream_cells_mapŒ§@md_str¤Core¨Base.get¥@bind¥aside¨Foldable«PlutoRunner¨CheckBox·PlutoRunner.create_bond¤Base¯Core.applicable¨getindexÙ$8e337fad-abcf-4ad3-bf75-ab3980f36baa„´precedence_heuristic §cell_idÙ$8e337fad-abcf-4ad3-bf75-ab3980f36baa´downstream_cells_map‚°many_sum_md_code‘Ù$258817e3-8495-4136-8cb9-00a4475245b2¬many_sum_lib‘Ù$6657e4dd-f5c2-47c4-b0d6-a2a56aac7b96²upstream_cells_map‚many_sum_code‘Ù$050a67f8-7f02-4ac9-8ac4-20327d46c5e8«compile_libÙ$9e78f2a1-0811-4f61-957d-ad4718430f7f„´precedence_heuristic §cell_idÙ$9e78f2a1-0811-4f61-957d-ad4718430f7f´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$e83baa29-ad2b-4ffc-99f5-cdbca9e31233„´precedence_heuristic §cell_idÙ$e83baa29-ad2b-4ffc-99f5-cdbca9e31233´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$96bffd66-24fc-46f7-b211-57e7d27bc316„´precedence_heuristic §cell_idÙ$96bffd66-24fc-46f7-b211-57e7d27bc316´downstream_cells_map¨many_vec’Ù$a7118fbb-66d6-44a1-a6ae-839f0e42a3ecÙ$910fc9b2-c57d-4874-b8b2-df440fc921c0²upstream_cells_map„many_log_size‘Ù$6c021710-5828-4ac0-8619-ce690ba89d5f¡^¦Cfloat¤randÙ$658ca396-2d73-4c93-8138-33c101deee7b„´precedence_heuristic §cell_idÙ$658ca396-2d73-4c93-8138-33c101deee7b´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$d5432907-3e55-4035-9c91-183c37d886ea„´precedence_heuristic §cell_idÙ$d5432907-3e55-4035-9c91-183c37d886ea´downstream_cells_map‚«num_threads’Ù$31727049-ac0a-45a6-aae0-934d4549b541Ù$b5f1d18c-53ad-4441-8ca8-e02d6ab840d0¨log_size‘Ù$3a5d674d-7c5b-4dac-b9ae-d65a1e9a5cba²upstream_cells_map§@md_str¤Core¡:¤vbox¨Base.get¥@bind¦Slider¥aside¤Base«PlutoRunner·PlutoRunner.create_bond¯Core.applicable¨getindexÙ$e90fd21d-d046-4852-823c-5d7210068923„´precedence_heuristic §cell_idÙ$e90fd21d-d046-4852-823c-5d7210068923´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$4b7a62a4-1e88-410b-8549-3021f6cdf6da„´precedence_heuristic §cell_idÙ$4b7a62a4-1e88-410b-8549-3021f6cdf6da´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$b26ab400-ce89-4a76-ad48-464ac6821dd2„´precedence_heuristic §cell_idÙ$b26ab400-ce89-4a76-ad48-464ac6821dd2´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$34519b36-0e60-4c2c-92d6-3b8ed71e6ad1„´precedence_heuristic§cell_idÙ$34519b36-0e60-4c2c-92d6-3b8ed71e6ad1´downstream_cells_map‰¬StaticArrays«SimpleClang§PlutoUI’Ù$3bff6f16-ad66-4aed-9a29-4bdcfe41b57fÙ$91f7f3fe-cb4d-4461-9147-81c72b650a4b°HypertextLiteral’Ù$3bff6f16-ad66-4aed-9a29-4bdcfe41b57fÙ$91f7f3fe-cb4d-4461-9147-81c72b650a4b²ExperimentalLayout®BenchmarkTools–Ù$4ae73a28-d945-4c1b-a281-aa4931bf0bfdÙ$62297efe-3a15-4dab-ac17-b823ab3e7933Ù$31727049-ac0a-45a6-aae0-934d4549b541Ù$a7118fbb-66d6-44a1-a6ae-839f0e42a3ecÙ$910fc9b2-c57d-4874-b8b2-df440fc921c0Ù$8b98b33e-f65d-4cbd-9e80-20a7132cd349¨Markdown‘Ù$cd6c2bda-e80d-46ba-8242-f0f61a250471¥Luxor²PlutoTeachingTools’Ù$3bff6f16-ad66-4aed-9a29-4bdcfe41b57fÙ$91f7f3fe-cb4d-4461-9147-81c72b650a4b²upstream_cells_map€Ù$1f45bab8-afb7-4cd2-8a37-1f258f37ad8f„´precedence_heuristic §cell_idÙ$1f45bab8-afb7-4cd2-8a37-1f258f37ad8f´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$e7445ed8-cbf7-475d-bd67-3df8d9015de2„´precedence_heuristic §cell_idÙ$e7445ed8-cbf7-475d-bd67-3df8d9015de2´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$ccfd4488-a32a-4b35-a922-2e830f91ca08„´precedence_heuristic §cell_idÙ$ccfd4488-a32a-4b35-a922-2e830f91ca08´downstream_cells_map¬c_sum_matrix‘Ù$fa017c45-6410-4c14-b9a2-ede33759d396²upstream_cells_map‚¥CCode¡*Ù$ebe1cd42-ba25-4538-acbe-353e0e47009e„´precedence_heuristic §cell_idÙ$ebe1cd42-ba25-4538-acbe-353e0e47009e´downstream_cells_map‚«sum_md_code‘Ù$4b9cfb4d-2355-42e3-be2f-35e2638e984b§sum_lib‘Ù$253bd533-99b7-4012-b3f4-e86a2466a919²upstream_cells_map„°no_false_sharing‘Ù$1b9fb8aa-71cf-4e69-ad84-666c1b66bb5elocal_results‘Ù$1b9fb8aa-71cf-4e69-ad84-666c1b66bb5eªc_sum_code‘Ù$19655acd-5880-44fa-ac29-d56faf43e87b«compile_libÙ$8b98b33e-f65d-4cbd-9e80-20a7132cd349„´precedence_heuristic §cell_idÙ$8b98b33e-f65d-4cbd-9e80-20a7132cd349´downstream_cells_map€²upstream_cells_map®BenchmarkTools‘Ù$34519b36-0e60-4c2c-92d6-3b8ed71e6ad1Ù$1b9fb8aa-71cf-4e69-ad84-666c1b66bb5e„´precedence_heuristic §cell_idÙ$1b9fb8aa-71cf-4e69-ad84-666c1b66bb5e´downstream_cells_map„°no_false_sharing‘Ù$ebe1cd42-ba25-4538-acbe-353e0e47009elocal_results‘Ù$ebe1cd42-ba25-4538-acbe-353e0e47009e§no_difffalse_sharing²upstream_cells_mapŒ§@md_str¤Core¨Base.get¥@bind¥aside¨Foldable«PlutoRunner¨CheckBox·PlutoRunner.create_bond¤Base¯Core.applicable¨getindexÙ$f95dd40b-8c56-4e10-abbc-3dbb58148e1f„´precedence_heuristic §cell_idÙ$f95dd40b-8c56-4e10-abbc-3dbb58148e1f´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$d8238145-9787-40f0-a151-1ef73d8c97ee„´precedence_heuristic §cell_idÙ$d8238145-9787-40f0-a151-1ef73d8c97ee´downstream_cells_map€²upstream_cells_mapƒ¤hbox¢=>£img‘Ù$91f7f3fe-cb4d-4461-9147-81c72b650a4bÙ$a32ba8f2-a9c9-41c6-99b4-577f0823bd9f„´precedence_heuristic §cell_idÙ$a32ba8f2-a9c9-41c6-99b4-577f0823bd9f´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$cd6c2bda-e80d-46ba-8242-f0f61a250471„´precedence_heuristic §cell_idÙ$cd6c2bda-e80d-46ba-8242-f0f61a250471´downstream_cells_mapªdefinition‘Ù$b2b3beda-c8bf-4616-b1bd-bdd907d11636²upstream_cells_mapƒ³Markdown.Admonition«Markdown.MD¨Markdown‘Ù$34519b36-0e60-4c2c-92d6-3b8ed71e6ad1Ù$253bd533-99b7-4012-b3f4-e86a2466a919„´precedence_heuristic §cell_idÙ$253bd533-99b7-4012-b3f4-e86a2466a919´downstream_cells_map¥c_sum•Ù$4ae73a28-d945-4c1b-a281-aa4931bf0bfdÙ$62297efe-3a15-4dab-ac17-b823ab3e7933Ù$31727049-ac0a-45a6-aae0-934d4549b541Ù$b5f1d18c-53ad-4441-8ca8-e02d6ab840d0Ù$a7118fbb-66d6-44a1-a6ae-839f0e42a3ec²upstream_cells_map‡¦length§sum_lib‘Ù$ebe1cd42-ba25-4538-acbe-353e0e47009e£Ptr¦Cfloat¤Cint¥ccall¦VectorÙ$910fc9b2-c57d-4874-b8b2-df440fc921c0„´precedence_heuristic §cell_idÙ$910fc9b2-c57d-4874-b8b2-df440fc921c0´downstream_cells_map€²upstream_cells_mapŒ¹BenchmarkTools.ParametersÙ,BenchmarkTools.generate_benchmark_definition®##many_vec#310¨many_vec‘Ù$96bffd66-24fc-46f7-b211-57e7d27bc316º#___this_pluto_module_name§println®BenchmarkTools‘Ù$34519b36-0e60-4c2c-92d6-3b8ed71e6ad1°base_num_threads‘Ù$6c021710-5828-4ac0-8619-ce690ba89d5f¨many_sum‘Ù$6657e4dd-f5c2-47c4-b0d6-a2a56aac7b96¦@btime¦factor‘Ù$6c021710-5828-4ac0-8619-ce690ba89d5f¢==Ù$6f70144e-5240-41ef-a719-8a8942e18fee„´precedence_heuristic §cell_idÙ$6f70144e-5240-41ef-a719-8a8942e18fee´downstream_cells_map€²upstream_cells_map£img‘Ù$91f7f3fe-cb4d-4461-9147-81c72b650a4bÙ$caec43a3-9bac-4f73-a8e5-288cfa9e1606„´precedence_heuristic §cell_idÙ$caec43a3-9bac-4f73-a8e5-288cfa9e1606´downstream_cells_map€²upstream_cells_map‚¥aside§bibcite‘Ù$d52b5227-0ef4-4dc6-b443-03364b0caeffÙ$db24839c-eb42-4d5c-8545-3714abc01bc5„´precedence_heuristic §cell_idÙ$db24839c-eb42-4d5c-8545-3714abc01bc5´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$6657e4dd-f5c2-47c4-b0d6-a2a56aac7b96„´precedence_heuristic §cell_idÙ$6657e4dd-f5c2-47c4-b0d6-a2a56aac7b96´downstream_cells_map¨many_sum’Ù$947b8e5c-9cb7-4fe6-aff6-48416879fb43Ù$910fc9b2-c57d-4874-b8b2-df440fc921c0²upstream_cells_map‡¥ccall¦length£Ptr¦Cfloat¤Cint¬many_sum_lib‘Ù$8e337fad-abcf-4ad3-bf75-ab3980f36baa¦VectorÙ$ea9ff1a9-615d-4e18-a4c8-9aad20447156„´precedence_heuristic §cell_idÙ$ea9ff1a9-615d-4e18-a4c8-9aad20447156´downstream_cells_map€²upstream_cells_map‚¥aside§bibcite‘Ù$d52b5227-0ef4-4dc6-b443-03364b0caeffÙ$c0bda86a-136b-45ca-84ba-7365c367d265„´precedence_heuristic §cell_idÙ$c0bda86a-136b-45ca-84ba-7365c367d265´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$11b1c6a8-3918-4dda-9028-17af2d6c44c4„´precedence_heuristic §cell_idÙ$11b1c6a8-3918-4dda-9028-17af2d6c44c4´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$d221bad8-98fb-4c1d-9c9c-66e1b697f023„´precedence_heuristic §cell_idÙ$d221bad8-98fb-4c1d-9c9c-66e1b697f023´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$a7118fbb-66d6-44a1-a6ae-839f0e42a3ec„´precedence_heuristic §cell_idÙ$a7118fbb-66d6-44a1-a6ae-839f0e42a3ec´downstream_cells_map€²upstream_cells_mapŠ¹BenchmarkTools.Parameters¥c_sum’Ù$19943be2-1633-48c9-8cb3-2a73fb96e4aeÙ$253bd533-99b7-4012-b3f4-e86a2466a919®##many_vec#304¦@btimeÙ,BenchmarkTools.generate_benchmark_definition¨many_vec‘Ù$96bffd66-24fc-46f7-b211-57e7d27bc316º#___this_pluto_module_name¢==§println®BenchmarkTools‘Ù$34519b36-0e60-4c2c-92d6-3b8ed71e6ad1Ù$6e8865f5-84ad-4083-bb19-57ad1b561fab„´precedence_heuristic §cell_idÙ$6e8865f5-84ad-4083-bb19-57ad1b561fab´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$d718f117-41da-42ff-9bcd-8bef0e7e6974„´precedence_heuristic §cell_idÙ$d718f117-41da-42ff-9bcd-8bef0e7e6974´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$3887824b-7c7f-4c24-bf6d-7a55ed7adc89„´precedence_heuristic §cell_idÙ$3887824b-7c7f-4c24-bf6d-7a55ed7adc89´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$050a67f8-7f02-4ac9-8ac4-20327d46c5e8„´precedence_heuristic §cell_idÙ$050a67f8-7f02-4ac9-8ac4-20327d46c5e8´downstream_cells_mapmany_sum_code‘Ù$8e337fad-abcf-4ad3-bf75-ab3980f36baa²upstream_cells_map§CppCodeÙ$62297efe-3a15-4dab-ac17-b823ab3e7933„´precedence_heuristic §cell_idÙ$62297efe-3a15-4dab-ac17-b823ab3e7933´downstream_cells_map€²upstream_cells_mapŠ¹BenchmarkTools.Parameters¥c_sum’Ù$19943be2-1633-48c9-8cb3-2a73fb96e4aeÙ$253bd533-99b7-4012-b3f4-e86a2466a919£vec‘Ù$3a5d674d-7c5b-4dac-b9ae-d65a1e9a5cba¦@btimeÙ,BenchmarkTools.generate_benchmark_definition©##vec#292®BenchmarkTools‘Ù$34519b36-0e60-4c2c-92d6-3b8ed71e6ad1º#___this_pluto_module_name¢==§printlnÙ$31727049-ac0a-45a6-aae0-934d4549b541„´precedence_heuristic §cell_idÙ$31727049-ac0a-45a6-aae0-934d4549b541´downstream_cells_map€²upstream_cells_map‹¹BenchmarkTools.Parameters¥c_sum’Ù$19943be2-1633-48c9-8cb3-2a73fb96e4aeÙ$253bd533-99b7-4012-b3f4-e86a2466a919Ù,BenchmarkTools.generate_benchmark_definition©##vec#298®BenchmarkTools‘Ù$34519b36-0e60-4c2c-92d6-3b8ed71e6ad1º#___this_pluto_module_name§println£vec‘Ù$3a5d674d-7c5b-4dac-b9ae-d65a1e9a5cba¦@btime«num_threads‘Ù$d5432907-3e55-4035-9c91-183c37d886ea¢==Ù$2a1f3d29-4d6b-4634-86f3-4ecd4a7821a2„´precedence_heuristic §cell_idÙ$2a1f3d29-4d6b-4634-86f3-4ecd4a7821a2´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$81465bf1-8e54-461f-892c-2769bf94fdfe„´precedence_heuristic §cell_idÙ$81465bf1-8e54-461f-892c-2769bf94fdfe´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$3a5d674d-7c5b-4dac-b9ae-d65a1e9a5cba„´precedence_heuristic §cell_idÙ$3a5d674d-7c5b-4dac-b9ae-d65a1e9a5cba´downstream_cells_map£vec”Ù$62297efe-3a15-4dab-ac17-b823ab3e7933Ù$31727049-ac0a-45a6-aae0-934d4549b541Ù$b5f1d18c-53ad-4441-8ca8-e02d6ab840d0Ù$947b8e5c-9cb7-4fe6-aff6-48416879fb43²upstream_cells_map„¡^¦Cfloat¤rand¨log_size‘Ù$d5432907-3e55-4035-9c91-183c37d886eaÙ$6c021710-5828-4ac0-8619-ce690ba89d5f„´precedence_heuristic §cell_idÙ$6c021710-5828-4ac0-8619-ce690ba89d5f´downstream_cells_mapƒmany_log_size‘Ù$96bffd66-24fc-46f7-b211-57e7d27bc316°base_num_threads’Ù$947b8e5c-9cb7-4fe6-aff6-48416879fb43Ù$910fc9b2-c57d-4874-b8b2-df440fc921c0¦factor’Ù$947b8e5c-9cb7-4fe6-aff6-48416879fb43Ù$910fc9b2-c57d-4874-b8b2-df440fc921c0²upstream_cells_map§@md_str¤Core¡:¤vbox¨Base.get¥@bind¦Slider¥aside¤Base«PlutoRunner·PlutoRunner.create_bond¯Core.applicable¨getindexÙ$e867d9be-5668-4756-af7f-c23c48962f08„´precedence_heuristic §cell_idÙ$e867d9be-5668-4756-af7f-c23c48962f08´downstream_cells_map€²upstream_cells_map‚¥aside§bibcite‘Ù$d52b5227-0ef4-4dc6-b443-03364b0caeffÙ$de0bbef2-1240-4f85-889f-0af509d6cfff„´precedence_heuristic §cell_idÙ$de0bbef2-1240-4f85-889f-0af509d6cfff´downstream_cells_map€²upstream_cells_map…§@md_str¥aside§bibcite‘Ù$d52b5227-0ef4-4dc6-b443-03364b0caeff£tip¨getindexÙ$d52b5227-0ef4-4dc6-b443-03364b0caeff„´precedence_heuristic §cell_idÙ$d52b5227-0ef4-4dc6-b443-03364b0caeff´downstream_cells_map§bibcite•Ù$e867d9be-5668-4756-af7f-c23c48962f08Ù$caec43a3-9bac-4f73-a8e5-288cfa9e1606Ù$de0bbef2-1240-4f85-889f-0af509d6cfffÙ$ea9ff1a9-615d-4e18-a4c8-9aad20447156Ù$c6ea9bc5-bb15-4e25-a854-de3417d736a6²upstream_cells_map¡*Ù$138caa9b-1d53-4c01-a3b9-c1a097413736„´precedence_heuristic §cell_idÙ$138caa9b-1d53-4c01-a3b9-c1a097413736´downstream_cells_map€²upstream_cells_map‚£URL‘Ù$91f7f3fe-cb4d-4461-9147-81c72b650a4b£img‘Ù$91f7f3fe-cb4d-4461-9147-81c72b650a4bÙ$d1aef3d4-33d1-4151-8ba3-2169f734ea6b„´precedence_heuristic §cell_idÙ$d1aef3d4-33d1-4151-8ba3-2169f734ea6b´downstream_cells_map€²upstream_cells_mapƒ§@md_str¨Foldable¨getindexÙ$947b8e5c-9cb7-4fe6-aff6-48416879fb43„´precedence_heuristic §cell_idÙ$947b8e5c-9cb7-4fe6-aff6-48416879fb43´downstream_cells_map€²upstream_cells_mapÞ¥@time³Base.gc_alloc_count¦Base.*¦Base.-«Base.gc_num°base_num_threads‘Ù$6c021710-5828-4ac0-8619-ce690ba89d5f¿Base.cumulative_compile_time_ns¬Base.GC_Diff¨Base.===«Base.string¤Base£vec‘Ù$3a5d674d-7c5b-4dac-b9ae-d65a1e9a5cba¨many_sum‘Ù$6657e4dd-f5c2-47c4-b0d6-a2a56aac7b96¯Base.time_print¦factor‘Ù$6c021710-5828-4ac0-8619-ce690ba89d5f¬Base.time_ns»Base.Threads.lock_profiling¦Base./¾Base.cumulative_compile_timingÙ$4b9cfb4d-2355-42e3-be2f-35e2638e984b„´precedence_heuristic §cell_idÙ$4b9cfb4d-2355-42e3-be2f-35e2638e984b´downstream_cells_map€²upstream_cells_map«sum_md_code‘Ù$ebe1cd42-ba25-4538-acbe-353e0e47009eÙ$3bff6f16-ad66-4aed-9a29-4bdcfe41b57f„´precedence_heuristic §cell_idÙ$3bff6f16-ad66-4aed-9a29-4bdcfe41b57f´downstream_cells_map€²upstream_cells_map‰²PlutoTeachingTools‘Ù$34519b36-0e60-4c2c-92d6-3b8ed71e6ad1·HypertextLiteral.Bypass·HypertextLiteral.Result°HypertextLiteral‘Ù$34519b36-0e60-4c2c-92d6-3b8ed71e6ad1§PlutoUI‘Ù$34519b36-0e60-4c2c-92d6-3b8ed71e6ad1¸HypertextLiteral.contentÙ$PlutoTeachingTools.ChooseDisplayMode¤@htl·PlutoUI.TableOfContentsÙ$f7da896d-089c-4430-b82c-db86c380b171„´precedence_heuristic §cell_idÙ$f7da896d-089c-4430-b82c-db86c380b171´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$655d59f3-665b-410b-b534-afadae96295b„´precedence_heuristic §cell_idÙ$655d59f3-665b-410b-b534-afadae96295b´downstream_cells_map€²upstream_cells_mapƒ§@md_str¥aside¨getindexÙ$5d7cd5e3-5fc2-4835-bea1-c4897467365b„´precedence_heuristic §cell_idÙ$5d7cd5e3-5fc2-4835-bea1-c4897467365b´downstream_cells_map€²upstream_cells_map‚¥aside¯sum_matrix_code‘Ù$fa017c45-6410-4c14-b9a2-ede33759d396Ù$81da94b8-1bbf-4773-ba53-d229452cef75„´precedence_heuristic §cell_idÙ$81da94b8-1bbf-4773-ba53-d229452cef75´downstream_cells_map£mat‘Ù$4ae73a28-d945-4c1b-a281-aa4931bf0bfd²upstream_cells_mapƒ¡^¦Cfloat¤randÙ$258817e3-8495-4136-8cb9-00a4475245b2„´precedence_heuristic §cell_idÙ$258817e3-8495-4136-8cb9-00a4475245b2´downstream_cells_map€²upstream_cells_map°many_sum_md_code‘Ù$8e337fad-abcf-4ad3-bf75-ab3980f36baaÙ$a144f991-3af4-4f88-a7e8-c1f3e9d7f7e2„´precedence_heuristic §cell_idÙ$a144f991-3af4-4f88-a7e8-c1f3e9d7f7e2´downstream_cells_map€²upstream_cells_map†§@md_str¥aside£URL‘Ù$91f7f3fe-cb4d-4461-9147-81c72b650a4b¢=>£img‘Ù$91f7f3fe-cb4d-4461-9147-81c72b650a4b¨getindexÙ$dbe9c6d8-611e-46f9-9a8e-2b3647e813fa„´precedence_heuristic §cell_idÙ$dbe9c6d8-611e-46f9-9a8e-2b3647e813fa´downstream_cells_map‚¤file£dir²upstream_cells_map†£run§cmd_gen¨joinpath¤@cmd©mktempdir£img‘Ù$91f7f3fe-cb4d-4461-9147-81c72b650a4bÙ$4ae73a28-d945-4c1b-a281-aa4931bf0bfd„´precedence_heuristic §cell_idÙ$4ae73a28-d945-4c1b-a281-aa4931bf0bfd´downstream_cells_map€²upstream_cells_mapŠ£mat‘Ù$81da94b8-1bbf-4773-ba53-d229452cef75¹BenchmarkTools.Parameters¥c_sum’Ù$19943be2-1633-48c9-8cb3-2a73fb96e4aeÙ$253bd533-99b7-4012-b3f4-e86a2466a919¦@btimeÙ,BenchmarkTools.generate_benchmark_definition®BenchmarkTools‘Ù$34519b36-0e60-4c2c-92d6-3b8ed71e6ad1©##mat#286¢==§printlnº#___this_pluto_module_nameÙ$19655acd-5880-44fa-ac29-d56faf43e87b„´precedence_heuristic §cell_idÙ$19655acd-5880-44fa-ac29-d56faf43e87b´downstream_cells_mapªc_sum_code‘Ù$ebe1cd42-ba25-4538-acbe-353e0e47009e²upstream_cells_mapƒ¡*¤Bool§CppCodeÙ$b2b3beda-c8bf-4616-b1bd-bdd907d11636„´precedence_heuristic §cell_idÙ$b2b3beda-c8bf-4616-b1bd-bdd907d11636´downstream_cells_map€²upstream_cells_map‡§@md_str¤hboxªdefinition‘Ù$cd6c2bda-e80d-46ba-8242-f0f61a250471¤Dict£Div¢=>¨getindexÙ$37d9b5f0-48b6-4ff3-873d-592230687995„´precedence_heuristic §cell_idÙ$37d9b5f0-48b6-4ff3-873d-592230687995´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$fa017c45-6410-4c14-b9a2-ede33759d396„´precedence_heuristic §cell_idÙ$fa017c45-6410-4c14-b9a2-ede33759d396´downstream_cells_map‚¯sum_matrix_code‘Ù$5d7cd5e3-5fc2-4835-bea1-c4897467365b®sum_matrix_lib‘Ù$19943be2-1633-48c9-8cb3-2a73fb96e4ae²upstream_cells_mapƒ¬c_sum_matrix‘Ù$ccfd4488-a32a-4b35-a922-2e830f91ca08«column_wise‘Ù$98a65469-573e-43b5-9043-f3d0f3198bcc«compile_libÙ$91f7f3fe-cb4d-4461-9147-81c72b650a4b„´precedence_heuristic §cell_idÙ$91f7f3fe-cb4d-4461-9147-81c72b650a4b´downstream_cells_map…ªsave_image¤Path‘Ù$91f7f3fe-cb4d-4461-9147-81c72b650a4b§imgpath£URL“Ù$138caa9b-1d53-4c01-a3b9-c1a097413736Ù$a144f991-3af4-4f88-a7e8-c1f3e9d7f7e2Ù$91f7f3fe-cb4d-4461-9147-81c72b650a4b£img–Ù$dbe9c6d8-611e-46f9-9a8e-2b3647e813faÙ$138caa9b-1d53-4c01-a3b9-c1a097413736Ù$02be0de6-70dc-4cf4-b630-b541a304eecdÙ$d8238145-9787-40f0-a151-1ef73d8c97eeÙ$6f70144e-5240-41ef-a719-8a8942e18feeÙ$a144f991-3af4-4f88-a7e8-c1f3e9d7f7e2²upstream_cells_mapÞ¡!·HypertextLiteral.BypassµPlutoUI.LocalResource§PlutoUI‘Ù$34519b36-0e60-4c2c-92d6-3b8ed71e6ad1¨joinpath¸HypertextLiteral.contentªstartswith¦String£end²PlutoTeachingTools‘Ù$34519b36-0e60-4c2c-92d6-3b8ed71e6ad1¤@htl¿HypertextLiteral.attribute_pairÙ&PlutoTeachingTools.RobustLocalResource¤Path‘Ù$91f7f3fe-cb4d-4461-9147-81c72b650a4b·HypertextLiteral.Result°HypertextLiteral‘Ù$34519b36-0e60-4c2c-92d6-3b8ed71e6ad1£URL‘Ù$91f7f3fe-cb4d-4461-9147-81c72b650a4b¡*¨@__DIR__¢in¥splitÙ$b5f1d18c-53ad-4441-8ca8-e02d6ab840d0„´precedence_heuristic §cell_idÙ$b5f1d18c-53ad-4441-8ca8-e02d6ab840d0´downstream_cells_map€²upstream_cells_mapÞ¥@time³Base.gc_alloc_count¦Base.*¥c_sum’Ù$19943be2-1633-48c9-8cb3-2a73fb96e4aeÙ$253bd533-99b7-4012-b3f4-e86a2466a919¦Base.-«Base.gc_num¿Base.cumulative_compile_time_ns¬Base.GC_Diff¨Base.===«Base.string¤Base£vec‘Ù$3a5d674d-7c5b-4dac-b9ae-d65a1e9a5cba¯Base.time_print¬Base.time_ns«num_threads‘Ù$d5432907-3e55-4035-9c91-183c37d886ea»Base.Threads.lock_profiling¦Base./¾Base.cumulative_compile_timingÙ$c6ea9bc5-bb15-4e25-a854-de3417d736a6„´precedence_heuristic §cell_idÙ$c6ea9bc5-bb15-4e25-a854-de3417d736a6´downstream_cells_map€²upstream_cells_map‚¥aside§bibcite‘Ù$d52b5227-0ef4-4dc6-b443-03364b0caeffÙ$02be0de6-70dc-4cf4-b630-b541a304eecd„´precedence_heuristic §cell_idÙ$02be0de6-70dc-4cf4-b630-b541a304eecd´downstream_cells_map€²upstream_cells_map£img‘Ù$91f7f3fe-cb4d-4461-9147-81c72b650a4bÙ$f26f0a70-c16b-491d-b4cf-45ca146727c2„´precedence_heuristic §cell_idÙ$f26f0a70-c16b-491d-b4cf-45ca146727c2´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindex´cell_execution_orderÜEÙ$34519b36-0e60-4c2c-92d6-3b8ed71e6ad1Ù$3bff6f16-ad66-4aed-9a29-4bdcfe41b57fÙ$8a51b9c5-8888-4578-ae40-cf906ec9b5faÙ$d52b5227-0ef4-4dc6-b443-03364b0caeffÙ$3887824b-7c7f-4c24-bf6d-7a55ed7adc89Ù$655d59f3-665b-410b-b534-afadae96295bÙ$37d9b5f0-48b6-4ff3-873d-592230687995Ù$81465bf1-8e54-461f-892c-2769bf94fdfeÙ$e867d9be-5668-4756-af7f-c23c48962f08Ù$a32ba8f2-a9c9-41c6-99b4-577f0823bd9fÙ$658ca396-2d73-4c93-8138-33c101deee7bÙ$caec43a3-9bac-4f73-a8e5-288cfa9e1606Ù$f26f0a70-c16b-491d-b4cf-45ca146727c2Ù$81da94b8-1bbf-4773-ba53-d229452cef75Ù$98a65469-573e-43b5-9043-f3d0f3198bccÙ$ccfd4488-a32a-4b35-a922-2e830f91ca08Ù$fa017c45-6410-4c14-b9a2-ede33759d396Ù$19943be2-1633-48c9-8cb3-2a73fb96e4aeÙ$5d7cd5e3-5fc2-4835-bea1-c4897467365bÙ$c0bda86a-136b-45ca-84ba-7365c367d265Ù$11b1c6a8-3918-4dda-9028-17af2d6c44c4Ù$de0bbef2-1240-4f85-889f-0af509d6cfffÙ$6e8865f5-84ad-4083-bb19-57ad1b561fabÙ$d221bad8-98fb-4c1d-9c9c-66e1b697f023Ù$ea9ff1a9-615d-4e18-a4c8-9aad20447156Ù$9e78f2a1-0811-4f61-957d-ad4718430f7fÙ$e90fd21d-d046-4852-823c-5d7210068923Ù$c6ea9bc5-bb15-4e25-a854-de3417d736a6Ù$e7445ed8-cbf7-475d-bd67-3df8d9015de2Ù$d5432907-3e55-4035-9c91-183c37d886eaÙ$3a5d674d-7c5b-4dac-b9ae-d65a1e9a5cbaÙ$1b9fb8aa-71cf-4e69-ad84-666c1b66bb5eÙ$19655acd-5880-44fa-ac29-d56faf43e87bÙ$ebe1cd42-ba25-4538-acbe-353e0e47009eÙ$4b9cfb4d-2355-42e3-be2f-35e2638e984bÙ$253bd533-99b7-4012-b3f4-e86a2466a919Ù$4ae73a28-d945-4c1b-a281-aa4931bf0bfdÙ$62297efe-3a15-4dab-ac17-b823ab3e7933Ù$31727049-ac0a-45a6-aae0-934d4549b541Ù$b5f1d18c-53ad-4441-8ca8-e02d6ab840d0Ù$1f45bab8-afb7-4cd2-8a37-1f258f37ad8fÙ$db24839c-eb42-4d5c-8545-3714abc01bc5Ù$d718f117-41da-42ff-9bcd-8bef0e7e6974Ù$6c021710-5828-4ac0-8619-ce690ba89d5fÙ$96bffd66-24fc-46f7-b211-57e7d27bc316Ù$a7118fbb-66d6-44a1-a6ae-839f0e42a3ecÙ$050a67f8-7f02-4ac9-8ac4-20327d46c5e8Ù$8e337fad-abcf-4ad3-bf75-ab3980f36baaÙ$258817e3-8495-4136-8cb9-00a4475245b2Ù$6657e4dd-f5c2-47c4-b0d6-a2a56aac7b96Ù$947b8e5c-9cb7-4fe6-aff6-48416879fb43Ù$910fc9b2-c57d-4874-b8b2-df440fc921c0Ù$f95dd40b-8c56-4e10-abbc-3dbb58148e1fÙ$2a1f3d29-4d6b-4634-86f3-4ecd4a7821a2Ù$b26ab400-ce89-4a76-ad48-464ac6821dd2Ù$4b7a62a4-1e88-410b-8549-3021f6cdf6daÙ$e83baa29-ad2b-4ffc-99f5-cdbca9e31233Ù$f7da896d-089c-4430-b82c-db86c380b171Ù$d1aef3d4-33d1-4151-8ba3-2169f734ea6bÙ$8b98b33e-f65d-4cbd-9e80-20a7132cd349Ù$91f7f3fe-cb4d-4461-9147-81c72b650a4bÙ$dbe9c6d8-611e-46f9-9a8e-2b3647e813faÙ$138caa9b-1d53-4c01-a3b9-c1a097413736Ù$02be0de6-70dc-4cf4-b630-b541a304eecdÙ$d8238145-9787-40f0-a151-1ef73d8c97eeÙ$6f70144e-5240-41ef-a719-8a8942e18feeÙ$a144f991-3af4-4f88-a7e8-c1f3e9d7f7e2Ù$cd6c2bda-e80d-46ba-8242-f0f61a250471Ù$b2b3beda-c8bf-4616-b1bd-bdd907d11636´last_hot_reload_timeË©shortpath«2_shared.jl®process_status¥ready¤pathÙ:/home/runner/work/LINMA2710/LINMA2710/Lectures/2_shared.jlpluto_version¨v0.20.24®last_save_timeËAÚeÎ¹zÈªcell_orderÜEÙ$3bff6f16-ad66-4aed-9a29-4bdcfe41b57fÙ$8a51b9c5-8888-4578-ae40-cf906ec9b5faÙ$d52b5227-0ef4-4dc6-b443-03364b0caeffÙ$3887824b-7c7f-4c24-bf6d-7a55ed7adc89Ù$dbe9c6d8-611e-46f9-9a8e-2b3647e813faÙ$655d59f3-665b-410b-b534-afadae96295bÙ$37d9b5f0-48b6-4ff3-873d-592230687995Ù$138caa9b-1d53-4c01-a3b9-c1a097413736Ù$81465bf1-8e54-461f-892c-2769bf94fdfeÙ$e867d9be-5668-4756-af7f-c23c48962f08Ù$a32ba8f2-a9c9-41c6-99b4-577f0823bd9fÙ$02be0de6-70dc-4cf4-b630-b541a304eecdÙ$658ca396-2d73-4c93-8138-33c101deee7bÙ$caec43a3-9bac-4f73-a8e5-288cfa9e1606Ù$f26f0a70-c16b-491d-b4cf-45ca146727c2Ù$4ae73a28-d945-4c1b-a281-aa4931bf0bfdÙ$81da94b8-1bbf-4773-ba53-d229452cef75Ù$19943be2-1633-48c9-8cb3-2a73fb96e4aeÙ$5d7cd5e3-5fc2-4835-bea1-c4897467365bÙ$98a65469-573e-43b5-9043-f3d0f3198bccÙ$fa017c45-6410-4c14-b9a2-ede33759d396Ù$ccfd4488-a32a-4b35-a922-2e830f91ca08Ù$c0bda86a-136b-45ca-84ba-7365c367d265Ù$11b1c6a8-3918-4dda-9028-17af2d6c44c4Ù$de0bbef2-1240-4f85-889f-0af509d6cfffÙ$6e8865f5-84ad-4083-bb19-57ad1b561fabÙ$d8238145-9787-40f0-a151-1ef73d8c97eeÙ$d221bad8-98fb-4c1d-9c9c-66e1b697f023Ù$ea9ff1a9-615d-4e18-a4c8-9aad20447156Ù$9e78f2a1-0811-4f61-957d-ad4718430f7fÙ$6f70144e-5240-41ef-a719-8a8942e18feeÙ$e90fd21d-d046-4852-823c-5d7210068923Ù$c6ea9bc5-bb15-4e25-a854-de3417d736a6Ù$e7445ed8-cbf7-475d-bd67-3df8d9015de2Ù$4b9cfb4d-2355-42e3-be2f-35e2638e984bÙ$62297efe-3a15-4dab-ac17-b823ab3e7933Ù$31727049-ac0a-45a6-aae0-934d4549b541Ù$b5f1d18c-53ad-4441-8ca8-e02d6ab840d0Ù$3a5d674d-7c5b-4dac-b9ae-d65a1e9a5cbaÙ$253bd533-99b7-4012-b3f4-e86a2466a919Ù$a144f991-3af4-4f88-a7e8-c1f3e9d7f7e2Ù$d5432907-3e55-4035-9c91-183c37d886eaÙ$1b9fb8aa-71cf-4e69-ad84-666c1b66bb5eÙ$ebe1cd42-ba25-4538-acbe-353e0e47009eÙ$19655acd-5880-44fa-ac29-d56faf43e87bÙ$1f45bab8-afb7-4cd2-8a37-1f258f37ad8fÙ$258817e3-8495-4136-8cb9-00a4475245b2Ù$db24839c-eb42-4d5c-8545-3714abc01bc5Ù$d718f117-41da-42ff-9bcd-8bef0e7e6974Ù$947b8e5c-9cb7-4fe6-aff6-48416879fb43Ù$a7118fbb-66d6-44a1-a6ae-839f0e42a3ecÙ$910fc9b2-c57d-4874-b8b2-df440fc921c0Ù$96bffd66-24fc-46f7-b211-57e7d27bc316Ù$6657e4dd-f5c2-47c4-b0d6-a2a56aac7b96Ù$6c021710-5828-4ac0-8619-ce690ba89d5fÙ$8e337fad-abcf-4ad3-bf75-ab3980f36baaÙ$050a67f8-7f02-4ac9-8ac4-20327d46c5e8Ù$f95dd40b-8c56-4e10-abbc-3dbb58148e1fÙ$2a1f3d29-4d6b-4634-86f3-4ecd4a7821a2Ù$b2b3beda-c8bf-4616-b1bd-bdd907d11636Ù$b26ab400-ce89-4a76-ad48-464ac6821dd2Ù$4b7a62a4-1e88-410b-8549-3021f6cdf6daÙ$e83baa29-ad2b-4ffc-99f5-cdbca9e31233Ù$f7da896d-089c-4430-b82c-db86c380b171Ù$d1aef3d4-33d1-4151-8ba3-2169f734ea6bÙ$34519b36-0e60-4c2c-92d6-3b8ed71e6ad1Ù$8b98b33e-f65d-4cbd-9e80-20a7132cd349Ù$91f7f3fe-cb4d-4461-9147-81c72b650a4bÙ$cd6c2bda-e80d-46ba-8242-f0f61a250471±published_objects‚Ù573dc2256-4ab3-11f1-b967-89f2e690ee32/3583170c6e86b605ƒ¨children“’ÚO

many_log_size = 16

©text/html’Ú4

base_num_threads = 2

©text/html’Ú

factor = 2

©text/html©classnameÀ¥styleÙ&display: flex; flex-direction: column;Ù573dc2256-4ab3-11f1-b967-89f2e690ee32/8850476c856a19d0ƒ¨children’’ÚE

log_size = 16

©text/html’Ú*

num_threads = 2

©text/html©classnameÀ¥styleÙ&display: flex; flex-direction: column;¥nbpkgŠ¯install_time_nsÏ|+&¬instantiatedÃ²installed_versionsˆ«SimpleClang¥0.1.0¬StaticArrays¦1.9.17§PlutoUI¦0.7.79°HypertextLiteral¥1.0.0®BenchmarkTools¥1.6.3¥Luxor¥4.4.1¨Markdown¦stdlib²PlutoTeachingTools¥0.4.7°terminal_outputs‰¬StaticArraysÚé [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_voodkaakaf/Project.toml` [32m[1m Updating[22m[39m `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_voodkaakaf/Manifest.toml` [90m[d091e8ba] [39m[92m+ Xorg_libXfixes_jll v6.0.2+0[39m [90m[a65dc6b1] [39m[92m+ Xorg_libpciaccess_jll v0.19.0+0[39m [90m[8e53e030] [39m[92m+ libdrm_jll v2.4.125+1[39m [90m[9a156e7d] [39m[92m+ libva_jll v2.23.0+0[39m [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_voodkaakaf/Project.toml` [32m[1m Updating[22m[39m `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_voodkaakaf/Manifest.toml` [90m[d091e8ba] [39m[92m+ Xorg_libXfixes_jll v6.0.2+0[39m [90m[a65dc6b1] [39m[92m+ Xorg_libpciaccess_jll v0.19.0+0[39m [90m[8e53e030] [39m[92m+ libdrm_jll v2.4.125+1[39m [90m[9a156e7d] [39m[92m+ libva_jll v2.23.0+0[39m [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_voodkaakaf/Project.toml` [32m[1m Updating[22m[39m `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_voodkaakaf/Manifest.toml` [90m[d091e8ba] [39m[92m+ Xorg_libXfixes_jll v6.0.2+0[39m [90m[a65dc6b1] [39m[92m+ Xorg_libpciaccess_jll v0.19.0+0[39m [90m[8e53e030] [39m[92m+ libdrm_jll v2.4.125+1[39m [90m[9a156e7d] [39m[92m+ libva_jll v2.23.0+0[39m [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_voodkaakaf/Project.toml` [32m[1m Updating[22m[39m `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_voodkaakaf/Manifest.toml` [90m[d091e8ba] [39m[92m+ Xorg_libXfixes_jll v6.0.2+0[39m [90m[a65dc6b1] [39m[92m+ Xorg_libpciaccess_jll v0.19.0+0[39m [90m[8e53e030] [39m[92m+ libdrm_jll v2.4.125+1[39m [90m[9a156e7d] [39m[92m+ libva_jll v2.23.0+0[39m [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_voodkaakaf/Project.toml` [32m[1m Updating[22m[39m `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_voodkaakaf/Manifest.toml` [90m[d091e8ba] [39m[92m+ Xorg_libXfixes_jll v6.0.2+0[39m [90m[a65dc6b1] [39m[92m+ Xorg_libpciaccess_jll v0.19.0+0[39m [90m[8e53e030] [39m[92m+ libdrm_jll v2.4.125+1[39m [90m[9a156e7d] [39m[92m+ libva_jll v2.23.0+0[39m [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_voodkaakaf/Project.toml` [32m[1m Updating[22m[39m `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_voodkaakaf/Manifest.toml` [90m[d091e8ba] [39m[92m+ Xorg_libXfixes_jll v6.0.2+0[39m [90m[a65dc6b1] [39m[92m+ Xorg_libpciaccess_jll v0.19.0+0[39m [90m[8e53e030] [39m[92m+ libdrm_jll v2.4.125+1[39m [90m[9a156e7d] [39m[92m+ libva_jll v2.23.0+0[39m [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_voodkaakaf/Project.toml` [32m[1m Updating[22m[39m `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_voodkaakaf/Manifest.toml` [90m[d091e8ba] [39m[92m+ Xorg_libXfixes_jll v6.0.2+0[39m [90m[a65dc6b1] [39m[92m+ Xorg_libpciaccess_jll v0.19.0+0[39m [90m[8e53e030] [39m[92m+ libdrm_jll v2.4.125+1[39m [90m[9a156e7d] [39m[92m+ libva_jll v2.23.0+0[39m [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_voodkaakaf/Project.toml` [32m[1m Updating[22m[39m `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_voodkaakaf/Manifest.toml` [90m[d091e8ba] [39m[92m+ Xorg_libXfixes_jll v6.0.2+0[39m [90m[a65dc6b1] [39m[92m+ Xorg_libpciaccess_jll v0.19.0+0[39m [90m[8e53e030] [39m[92m+ libdrm_jll v2.4.125+1[39m [90m[9a156e7d] [39m[92m+ libva_jll v2.23.0+0[39m [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_voodkaakaf/Project.toml` [32m[1m Updating[22m[39m `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_voodkaakaf/Manifest.toml` [90m[d091e8ba] [39m[92m+ Xorg_libXfixes_jll v6.0.2+0[39m [90m[a65dc6b1] [39m[92m+ Xorg_libpciaccess_jll v0.19.0+0[39m [90m[8e53e030] [39m[92m+ libdrm_jll v2.4.125+1[39m [90m[9a156e7d] [39m[92m+ libva_jll v2.23.0+0[39m [0m[1mInstantiating...[22m [90m===[39m [0m[1mPrecompiling...[22m [90m===[39m Waiting for notebook process to start... Done. Starting precompilation...§enabledÃ·restart_recommended_msgÀ´restart_required_msgÀbusy_packages¶waiting_for_permissionÂÙ,waiting_for_permission_but_probably_disabledÂ«cell_inputsÞEÙ$8a51b9c5-8888-4578-ae40-cf906ec9b5fa„§cell_idÙ$8a51b9c5-8888-4578-ae40-cf906ec9b5fa¤codeÙ™md"[Eij10] V. Eijkhout. [Introduction to High Performance Scientific Computing.](https://theartofhpc.com/istc.html) 3 Edition, Vol. 1 (Lulu.com, 2010). "¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$19943be2-1633-48c9-8cb3-2a73fb96e4ae„§cell_idÙ$19943be2-1633-48c9-8cb3-2a73fb96e4ae¤codeÙxc_sum(x::Matrix{Cfloat}) = ccall(("sum", sum_matrix_lib), Cfloat, (Ptr{Cfloat}, Cint, Cint), x, size(x, 1), size(x, 2));¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÂÙ$98a65469-573e-43b5-9043-f3d0f3198bcc„§cell_idÙ$98a65469-573e-43b5-9043-f3d0f3198bcc¤codeÚkaside( Foldable( md"What is the performance issue of this code ?", md"The way matrices are represented by Julia in memory is by concatenating all columns as single continuous memory. This means that it is more efficient to access the matrix column by column ! Switch to column-wise sum $(@bind column_wise CheckBox(default = false))", ), v_offset = -275 )¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$8e337fad-abcf-4ad3-bf75-ab3980f36baa„§cell_idÙ$8e337fad-abcf-4ad3-bf75-ab3980f36baa¤codeÙymany_sum_md_code, many_sum_lib = compile_lib(many_sum_code("float"), lib = true, cflags = ["-O3", "-mavx2", "-fopenmp"]);¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$9e78f2a1-0811-4f61-957d-ad4718430f7f„§cell_idÙ$9e78f2a1-0811-4f61-957d-ad4718430f7f¤codeÙ+md"## Cache hierarchy for a multi-core CPU"¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$e83baa29-ad2b-4ffc-99f5-cdbca9e31233„§cell_idÙ$e83baa29-ad2b-4ffc-99f5-cdbca9e31233¤codeÙ"md"## Application to parallel sum"¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$96bffd66-24fc-46f7-b211-57e7d27bc316„§cell_idÙ$96bffd66-24fc-46f7-b211-57e7d27bc316¤codeÙ(many_vec = rand(Cfloat, 2^many_log_size)¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÂÙ$658ca396-2d73-4c93-8138-33c101deee7b„§cell_idÙ$658ca396-2d73-4c93-8138-33c101deee7b¤codeÚgmd""" * Accessing value not in the cache â†’ *cache miss* * This value is then loaded along with a whole cache line (e.g., 64 or 128 contiguous bytes) * Following cache lines may also be anticipated and prefetched This shows the importance of *data locality*. An algorithm performs better if it accesses data close in memory and in a predictable pattern. """¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$d5432907-3e55-4035-9c91-183c37d886ea„§cell_idÙ$d5432907-3e55-4035-9c91-183c37d886ea¤codeÙÊaside(vbox([ md"`log_size` = $(@bind log_size Slider(14:24, default = 16, show_value = true))", md"`num_threads` = $(@bind num_threads Slider(2:8, default = 2, show_value = true))", ]), v_offset = -900)¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$e90fd21d-d046-4852-823c-5d7210068923„§cell_idÙ$e90fd21d-d046-4852-823c-5d7210068923¤codeÙhmd""" *Cache coherence* : Update L1 cache when the corresponding memory is modified by another core. """¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$4b7a62a4-1e88-410b-8549-3021f6cdf6da„§cell_idÙ$4b7a62a4-1e88-410b-8549-3021f6cdf6da¤codeÚ%md""" * ``F_s`` : Fraction of ``T_1`` that is sequential * ``F_p = 1 - F_s`` : Fraction of ``T_1`` that is parallelizable ```math \begin{align} T_p &= T_1F_s + T_1F_p/p\\ S_p &= \frac{1}{F_s + F_p/p} & E_p &= \frac{1}{pF_s + F_p}\\ \lim_{p \to \infty} S_p &= \frac{1}{F_s} \end{align} ``` """¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$b26ab400-ce89-4a76-ad48-464ac6821dd2„§cell_idÙ$b26ab400-ce89-4a76-ad48-464ac6821dd2¤code³md"## Amdahl's law"¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$34519b36-0e60-4c2c-92d6-3b8ed71e6ad1„§cell_idÙ$34519b36-0e60-4c2c-92d6-3b8ed71e6ad1¤codeÙ‹using PlutoUI, PlutoUI.ExperimentalLayout, HypertextLiteral, Luxor, StaticArrays, BenchmarkTools, PlutoTeachingTools, Markdown, SimpleClang¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÂÙ$1f45bab8-afb7-4cd2-8a37-1f258f37ad8f„§cell_idÙ$1f45bab8-afb7-4cd2-8a37-1f258f37ad8f¤code¶md"## Many processors"¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$e7445ed8-cbf7-475d-bd67-3df8d9015de2„§cell_idÙ$e7445ed8-cbf7-475d-bd67-3df8d9015de2¤code²md"# Parallel sum"¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$ccfd4488-a32a-4b35-a922-2e830f91ca08„§cell_idÙ$ccfd4488-a32a-4b35-a922-2e830f91ca08¤codeÚÍfunction c_sum_matrix(T; column_wise) code = """ #include $T sum($T *mat, int n, int m) { $T total = 0; """ idx = column_wise ? 'j' : 'i' len = column_wise ? 'm' : 'n' code *= """ for (int $idx = 0; $idx < $len; $idx++) { """ idx = column_wise ? 'i' : 'j' len = column_wise ? 'n' : 'm' code *= """ for (int $idx = 0; $idx < $len; $idx++) { """ code *= """ total += mat[i + j * n]; } } return total; } """ return CCode(code) end;¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$ebe1cd42-ba25-4538-acbe-353e0e47009e„§cell_idÙ$ebe1cd42-ba25-4538-acbe-353e0e47009e¤codeÙÅsum_md_code, sum_lib = compile_lib(c_sum_code("float"; local_results, no_false_sharing, simd = true), lib = true, cflags = ["-O3", "-mavx2", "-I/usr/lib/llvm-18/lib/clang/18/include", "-fopenmp"]);¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÂÙ$8b98b33e-f65d-4cbd-9e80-20a7132cd349„§cell_idÙ$8b98b33e-f65d-4cbd-9e80-20a7132cd349¤codeÙ/BenchmarkTools.DEFAULT_PARAMETERS.seconds = 0.2¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÂÙ$1b9fb8aa-71cf-4e69-ad84-666c1b66bb5e„§cell_idÙ$1b9fb8aa-71cf-4e69-ad84-666c1b66bb5e¤codeÚðbegin no_diff = Foldable( md"Wait, these didn't make any difference in the benchmark, how can it be ?", md""" The compiler most probably use a register (actually a SIMD register here (if there is any) since we used `#pragma omp simd`) as accumulator for the `for` loop and only stored the value of that register into `total`, `local_results[thread_num]` or `no_false_sharing` (depending on the version). Despite all this, it is still important to be careful about this issue and not trust the execution on one environment or rely too much on compiler optimizations for the code to be portable. """, ) false_sharing = Foldable( md"This is still a performance issue, can you see why ?", md""" The entries of `local_results` are close to each other in memory. There are therefore very likely going to be part of the same block on cache. This means that when one threads modifies it, the cache block will need to be written and then other threads will need to refresh the value of this block in their cache. variable `total` is shared between the threads, so its value in the register should be sync'ed between the threads! This is called *false sharing*. Let's fix this ? $(@bind no_false_sharing CheckBox(default = false)) $no_diff """, ) aside(Foldable( md"Can you spot the issue in the code ?", md""" The same variable `total` is shared between the threads, so its value in the register should be sync'ed between the threads, this is a performance issue! More importantly, the access to the `total` variable are not **atomic**. Therefore, two threads may read the value, `add`, and then store â†’ only one of the two `add` will then be accounted for! Let's fix this ? $(@bind local_results CheckBox(default = false)) $false_sharing """, ), v_offset = -800) end¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$f95dd40b-8c56-4e10-abbc-3dbb58148e1f„§cell_idÙ$f95dd40b-8c56-4e10-abbc-3dbb58148e1f¤code²md"# Amdahl's law"¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$d8238145-9787-40f0-a151-1ef73d8c97ee„§cell_idÙ$d8238145-9787-40f0-a151-1ef73d8c97ee¤codeÚAhbox([ img("https://github.com/VictorEijkhout/TheArtOfHPC_vol1_scientificcomputing/raw/refs/heads/main/booksources/graphics/roofline1.jpeg", :height => "260px"), img("https://github.com/VictorEijkhout/TheArtOfHPC_vol1_scientificcomputing/raw/refs/heads/main/booksources/graphics/roofline3.jpeg", :height => "260px"), ])¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$a32ba8f2-a9c9-41c6-99b4-577f0823bd9f„§cell_idÙ$a32ba8f2-a9c9-41c6-99b4-577f0823bd9f¤code¿md"## Cache lines and prefetch"¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$cd6c2bda-e80d-46ba-8242-f0f61a250471„§cell_idÙ$cd6c2bda-e80d-46ba-8242-f0f61a250471¤codeÙzfunction definition(name, content) return Markdown.MD(Markdown.Admonition("key-concept", "Def: $name", [content])) end¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$253bd533-99b7-4012-b3f4-e86a2466a919„§cell_idÙ$253bd533-99b7-4012-b3f4-e86a2466a919¤codeÙžc_sum(x::Vector{Cfloat}; num_threads = 1, verbose = 0) = ccall(("sum", sum_lib), Cfloat, (Ptr{Cfloat}, Cint, Cint, Cint), x, length(x), num_threads, verbose);¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÂÙ$910fc9b2-c57d-4874-b8b2-df440fc921c0„§cell_idÙ$910fc9b2-c57d-4874-b8b2-df440fc921c0¤codeÙ4@btime many_sum($many_vec; base_num_threads, factor)¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÂÙ$6f70144e-5240-41ef-a719-8a8942e18fee„§cell_idÙ$6f70144e-5240-41ef-a719-8a8942e18fee¤codeÙŠimg("https://github.com/VictorEijkhout/TheArtOfHPC_vol1_scientificcomputing/raw/refs/heads/main/booksources/graphics/cache-hierarchy.jpg")¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$caec43a3-9bac-4f73-a8e5-288cfa9e1606„§cell_idÙ$caec43a3-9bac-4f73-a8e5-288cfa9e1606¤codeÙ.aside(bibcite("Figure 1.11"), v_offset = -280)¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$db24839c-eb42-4d5c-8545-3714abc01bc5„§cell_idÙ$db24839c-eb42-4d5c-8545-3714abc01bc5¤code°md"## Benchmark"¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$6657e4dd-f5c2-47c4-b0d6-a2a56aac7b96„§cell_idÙ$6657e4dd-f5c2-47c4-b0d6-a2a56aac7b96¤codeÙÊmany_sum(x::Vector{Cfloat}; base_num_threads = 1, factor = 2, verbose = 0) = ccall(("sum", many_sum_lib), Cfloat, (Ptr{Cfloat}, Cint, Cint, Cint, Cint), x, length(x), base_num_threads, factor, verbose);¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÂÙ$ea9ff1a9-615d-4e18-a4c8-9aad20447156„§cell_idÙ$ea9ff1a9-615d-4e18-a4c8-9aad20447156¤codeÙ.aside(bibcite("Figure 1.16"), v_offset = -360)¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$c0bda86a-136b-45ca-84ba-7365c367d265„§cell_idÙ$c0bda86a-136b-45ca-84ba-7365c367d265¤code»md"## Arithmetic intensity"¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$11b1c6a8-3918-4dda-9028-17af2d6c44c4„§cell_idÙ$11b1c6a8-3918-4dda-9028-17af2d6c44c4¤codeÚ¸md""" Consider a program requiring `m` load / store operations with memory for `o` arithmetic operations. * The *arithmetic intensity* is the ratio ``a = o / m``. * The arithmetic time is ``t_\text{arith} = o / \text{frequency}`` * The data transfer time is ``t_\text{mem} = m / \text{bandwidth} = o / (a \cdot \text{bandwidth})`` As arithmetic operations and data transfer are done in parallel, the time per iteration is ```math \max(t_\text{arith}, t_\text{mem}) / o = 1/\min(\text{frequency}, a \cdot \text{bandwidth}) ``` So the number of operations per second is ``\min(\text{frequency}, a \cdot \text{bandwidth})``. This piecewise linear function in ``a`` gives the *roofline model*. """¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$d221bad8-98fb-4c1d-9c9c-66e1b697f023„§cell_idÙ$d221bad8-98fb-4c1d-9c9c-66e1b697f023¤codeÚ¯md""" * *compute-bound* : For large arithmetic intensity (Alg2 in above picture), performance determined by processor characteristics * *bandwidth-bound* : For low arithmetic intensity (Alg1 in above picture), performance determined by memory characteristics * Bandwidth line may be lowered by inefficient memory access (e.g., no locality) * Peak performance line may be lowered by inefficient use of CPU (e.g., not using SIMD) """¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$a7118fbb-66d6-44a1-a6ae-839f0e42a3ec„§cell_idÙ$a7118fbb-66d6-44a1-a6ae-839f0e42a3ec¤code·@btime c_sum($many_vec)¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÂÙ$6e8865f5-84ad-4083-bb19-57ad1b561fab„§cell_idÙ$6e8865f5-84ad-4083-bb19-57ad1b561fab¤code¹md"## The roofline model"¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$d718f117-41da-42ff-9bcd-8bef0e7e6974„§cell_idÙ$d718f117-41da-42ff-9bcd-8bef0e7e6974¤codeÙTmd""" If we have many processors, we may want to speed up the last part as well: """¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$3887824b-7c7f-4c24-bf6d-7a55ed7adc89„§cell_idÙ$3887824b-7c7f-4c24-bf6d-7a55ed7adc89¤code³md"# Memory layout"¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$050a67f8-7f02-4ac9-8ac4-20327d46c5e8„§cell_idÙ$050a67f8-7f02-4ac9-8ac4-20327d46c5e8¤codeÚ¨function many_sum_code(T) code = """ #include #include extern "C" { void sum_to($T *vec, int length, $T *local_results, int num_threads, int verbose) { omp_set_dynamic(0); // Force the value `num_threads` omp_set_num_threads(num_threads); #pragma omp parallel { int thread_num = omp_get_thread_num(); int stride = length / num_threads; int last = stride * (thread_num + 1); if (thread_num + 1 == num_threads) last = length; if (verbose >= 1) fprintf(stderr, "thread id : %d / %d %d:%d\\n", thread_num, omp_get_num_threads(), stride * thread_num, last - 1); $T no_false_sharing = 0; #pragma omp simd for (int i = stride * thread_num; i < last; i++) no_false_sharing += vec[i]; local_results[thread_num] = no_false_sharing; } } $T sum($T *vec, int length, int num_threads, int factor, int verbose) { $T* buffers[2] = {new $T[num_threads], new $T[num_threads / factor]}; sum_to(vec, length, buffers[0], num_threads, verbose); int prev = num_threads, cur; int buffer_idx = 0; for (cur = num_threads / factor; cur > 0; cur /= factor) { sum_to(buffers[buffer_idx % 2], prev, buffers[(buffer_idx + 1) % 2], cur, verbose); prev = cur; buffer_idx += 1; } if (prev == 1) return buffers[buffer_idx % 2][0]; sum_to(buffers[buffer_idx % 2], prev, buffers[(buffer_idx + 1) % 2], 1, verbose); return buffers[(buffer_idx + 1) % 2][0]; } } """ return CppCode(code) end;¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$62297efe-3a15-4dab-ac17-b823ab3e7933„§cell_idÙ$62297efe-3a15-4dab-ac17-b823ab3e7933¤codeÙ0@btime c_sum($vec, num_threads = 1, verbose = 0)¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÂÙ$31727049-ac0a-45a6-aae0-934d4549b541„§cell_idÙ$31727049-ac0a-45a6-aae0-934d4549b541¤codeÙ,@btime c_sum($vec; num_threads, verbose = 0)¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÂÙ$2a1f3d29-4d6b-4634-86f3-4ecd4a7821a2„§cell_idÙ$2a1f3d29-4d6b-4634-86f3-4ecd4a7821a2¤code½md"## Speed-up and efficency"¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$81465bf1-8e54-461f-892c-2769bf94fdfe„§cell_idÙ$81465bf1-8e54-461f-892c-2769bf94fdfe¤codeÙ£md"""Latency of `n` bytes of data is given by ```math \alpha + \beta n ``` where ``\alpha`` is the start up time and ``\beta`` is the inverse of the bandwidth. """¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$3a5d674d-7c5b-4dac-b9ae-d65a1e9a5cba„§cell_idÙ$3a5d674d-7c5b-4dac-b9ae-d65a1e9a5cba¤code¾vec = rand(Cfloat, 2^log_size)¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÂÙ$6c021710-5828-4ac0-8619-ce690ba89d5f„§cell_idÙ$6c021710-5828-4ac0-8619-ce690ba89d5f¤codeÚ*aside(vbox([ md"`many_log_size` = $(@bind many_log_size Slider(14:24, default = 16, show_value = true))", md"`base_num_threads` = $(@bind base_num_threads Slider(2:8, default = 2, show_value = true))", md"`factor` = $(@bind factor Slider(2:8, default = 2, show_value = true))", ]), v_offset = -500)¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$e867d9be-5668-4756-af7f-c23c48962f08„§cell_idÙ$e867d9be-5668-4756-af7f-c23c48962f08¤codeÙ-aside(bibcite("Figure 1.5"), v_offset = -300)¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$de0bbef2-1240-4f85-889f-0af509d6cfff„§cell_idÙ$de0bbef2-1240-4f85-889f-0af509d6cfff¤codeÙR aside(tip(md""" See examples in $(bibcite("Section 1.6.1")). """), v_offset=-300)¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$d52b5227-0ef4-4dc6-b443-03364b0caeff„§cell_idÙ$d52b5227-0ef4-4dc6-b443-03364b0caeff¤codeÙ(bibcite(what) = "[Eij10; " * what * "]";¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$138caa9b-1d53-4c01-a3b9-c1a097413736„§cell_idÙ$138caa9b-1d53-4c01-a3b9-c1a097413736¤codeÙ‰img(URL("https://github.com/VictorEijkhout/TheArtOfHPC_vol1_scientificcomputing/raw/refs/heads/main/booksources/graphics/hierarchy.jpg"))¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$d1aef3d4-33d1-4151-8ba3-2169f734ea6b„§cell_idÙ$d1aef3d4-33d1-4151-8ba3-2169f734ea6b¤codeÚ3Foldable(md"How to get ``1/F_s = \lim_{p \to \infty} S_p`` ?", md""" The algorithm cannot use more than ``n`` processes so if ``p \ge n``, we have ``T_p = 1 + \log_2(n)``. Therefore, ``\lim_{p \to \infty} S_p = S_n = \frac{n}{1 + \log_2(n)}``. Ignoring the constant ``1``, we get ``F_s = \log_2(n)/n``. """)¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$947b8e5c-9cb7-4fe6-aff6-48416879fb43„§cell_idÙ$947b8e5c-9cb7-4fe6-aff6-48416879fb43¤codeÙ:@time many_sum(vec; base_num_threads, factor, verbose = 1)¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÂÙ$4b9cfb4d-2355-42e3-be2f-35e2638e984b„§cell_idÙ$4b9cfb4d-2355-42e3-be2f-35e2638e984b¤code«sum_md_code¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$3bff6f16-ad66-4aed-9a29-4bdcfe41b57f„§cell_idÙ$3bff6f16-ad66-4aed-9a29-4bdcfe41b57f¤codeÙû@htl("""

LINMA2710 - Scientific Computing Shared-Memory Multiprocessing

P.-A. Absil and B. Legat

$(PlutoTeachingTools.ChooseDisplayMode()) $(PlutoUI.TableOfContents(depth=1)) """)¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$f7da896d-089c-4430-b82c-db86c380b171„§cell_idÙ$f7da896d-089c-4430-b82c-db86c380b171¤codeÚ4md""" The first `sum_to` takes ``n/p`` operations. Assuming `factor` is `2`, there is one operation for each of the ``\log_2(p)`` subsequent `sum_to`. ```math \begin{align} T_1 & = n\\ T_p & = n/p + \log_2(p)\\ S_p & = \frac{1}{1/p + \log_2(p)/n} & E_p & = \frac{1}{1 + p\log_2(p)/n} \end{align} ```"""¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$655d59f3-665b-410b-b534-afadae96295b„§cell_idÙ$655d59f3-665b-410b-b534-afadae96295b¤codeÙEaside(md"Try it on your laptop! ```sh $ lstopo ```", v_offset = -200)¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$5d7cd5e3-5fc2-4835-bea1-c4897467365b„§cell_idÙ$5d7cd5e3-5fc2-4835-bea1-c4897467365b¤codeÙ'aside(sum_matrix_code, v_offset = -470)¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$81da94b8-1bbf-4773-ba53-d229452cef75„§cell_idÙ$81da94b8-1bbf-4773-ba53-d229452cef75¤code¼mat = rand(Cfloat, 2^8, 2^8)¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÂÙ$258817e3-8495-4136-8cb9-00a4475245b2„§cell_idÙ$258817e3-8495-4136-8cb9-00a4475245b2¤code°many_sum_md_code¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$a144f991-3af4-4f88-a7e8-c1f3e9d7f7e2„§cell_idÙ$a144f991-3af4-4f88-a7e8-c1f3e9d7f7e2¤codeÚaside(md""" Low level implementation using POSIX Threads (pthreads) covered in "LEPL1503 : Projet 3". We use the high level $(img(URL("https://upload.wikimedia.org/wikipedia/commons/e/eb/OpenMP_logo.png"), :width => "45pt")) library in this course. """, v_offset = -1000)¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$dbe9c6d8-611e-46f9-9a8e-2b3647e813fa„§cell_idÙ$dbe9c6d8-611e-46f9-9a8e-2b3647e813fa¤codeÙjbegin dir = mktempdir() file = joinpath(dir, "topo.png") run(`lstopo $file`) img(file) end¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$4ae73a28-d945-4c1b-a281-aa4931bf0bfd„§cell_idÙ$4ae73a28-d945-4c1b-a281-aa4931bf0bfd¤code²@btime c_sum($mat)¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÂÙ$19655acd-5880-44fa-ac29-d56faf43e87b„§cell_idÙ$19655acd-5880-44fa-ac29-d56faf43e87b¤codeÚ”function c_sum_code(T; local_results::Bool, no_false_sharing::Bool, simd::Bool) code = """ #include #include #include #include extern "C" { $T sum($T *vec, int length, int num_threads, int verbose) { $T total = 0; omp_set_dynamic(0); // Force the value `num_threads` omp_set_num_threads(num_threads); """ if local_results code *= """ std::vector<$T> local_results(num_threads); """ end code *= """ #pragma omp parallel { int thread_num = omp_get_thread_num(); int stride = length / num_threads; int last = stride * (thread_num + 1); if (thread_num + 1 == num_threads) last = length; if (verbose >= 1) fprintf(stderr, "thread id : %d / %d %d:%d\\n", thread_num, omp_get_num_threads(), stride * thread_num, last - 1); """ if no_false_sharing code *= """ $T no_false_sharing = 0; """ end if simd code *= """ #pragma omp simd """ end code *= """ for (int i = stride * thread_num; i < last; i++) $(local_results ? (no_false_sharing ? "no_false_sharing" : "local_results[thread_num]") : "total") += vec[i]; """ if local_results && no_false_sharing code *= """ local_results[thread_num] = no_false_sharing; """ end code *= """ } """ if local_results code *= """ for (int i = 0; i < local_results.size(); i++) total += local_results[i]; """ end code *= """ return total; } } """ return CppCode(code) end;¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$b2b3beda-c8bf-4616-b1bd-bdd907d11636„§cell_idÙ$b2b3beda-c8bf-4616-b1bd-bdd907d11636¤codeÚËhbox([ definition("Speed-up", md""" ```math S_p = \frac{T_1}{T_p} ```"""), Div(definition("Efficiency", md""" ```math E_p = \frac{S_p}{p} ```"""); style = Dict("margin-left" => "30px")), Div(md""" Let ``T_p`` bet the time with ``p`` processes * ``E_p > 1`` â†’ Unlikely * ``E_p = 1`` â†’ Ideal * ``E_p < 1`` â†’ Realistic """; style = Dict("margin" => "30px", "flex-grow" => "1")), ]; style = Dict("align-items" => "center", "justify-content" => "center"))¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$37d9b5f0-48b6-4ff3-873d-592230687995„§cell_idÙ$37d9b5f0-48b6-4ff3-873d-592230687995¤code°md"## Hierarchy"¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$fa017c45-6410-4c14-b9a2-ede33759d396„§cell_idÙ$fa017c45-6410-4c14-b9a2-ede33759d396¤codeÙ‰sum_matrix_code, sum_matrix_lib = compile_lib(c_sum_matrix("float"; column_wise), lib = true, cflags = ["-O3", "-mavx2", "-ffast-math"]);¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$91f7f3fe-cb4d-4461-9147-81c72b650a4b„§cell_idÙ$91f7f3fe-cb4d-4461-9147-81c72b650a4b¤codeÚsbegin 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¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$b5f1d18c-53ad-4441-8ca8-e02d6ab840d0„§cell_idÙ$b5f1d18c-53ad-4441-8ca8-e02d6ab840d0¤codeÙ*@time c_sum(vec; num_threads, verbose = 1)¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÂÙ$c6ea9bc5-bb15-4e25-a854-de3417d736a6„§cell_idÙ$c6ea9bc5-bb15-4e25-a854-de3417d736a6¤codeÙ.aside(bibcite("Figure 1.13"), v_offset = -250)¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$02be0de6-70dc-4cf4-b630-b541a304eecd„§cell_idÙ$02be0de6-70dc-4cf4-b630-b541a304eecd¤codeÙ„img("https://github.com/VictorEijkhout/TheArtOfHPC_vol1_scientificcomputing/raw/refs/heads/main/booksources/graphics/prefetch.jpeg")¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃÙ$f26f0a70-c16b-491d-b4cf-45ca146727c2„§cell_idÙ$f26f0a70-c16b-491d-b4cf-45ca146727c2¤codeÙ!md"## Illustration with matrices"¨metadataƒ©show_logsÃ¨disabledÂ®skip_as_scriptÂ«code_foldedÃ«notebook_idÙ$73dc2256-4ab3-11f1-b967-89f2e690ee32«in_temp_dirÂ¨metadata€