ilp.tex 37 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123
  1. % vim: set foldmethod=marker foldmarker=<<<,>>>:
  2. \section{Instruction level optimization}
  3. % https://www.youtube.com/watch?v=BP6NxVxDQIs
  4. %<<< How code executes on a computer
  5. \begingroup
  6. \setbeamertemplate{background canvas}{%
  7. \begin{tikzpicture}[remember picture,overlay]
  8. \only<3>{
  9. \draw[line width=20pt,red!60!black]
  10. (11,-2) -- (15,-8);
  11. \draw[line width=20pt,red!60!black]
  12. (15,-2) -- (11,-8);
  13. }
  14. \end{tikzpicture}}
  15. \begin{frame}[fragile] \frametitle{How code executes on a computer}{}
  16. \begin{columns}
  17. \column{0.4\textwidth}
  18. \begin{overprint}
  19. \onslide<1->%<<<
  20. \begin{minted}[
  21. frame=lines,
  22. fontsize=\footnotesize,
  23. linenos,
  24. gobble=8,
  25. mathescape
  26. ]{C++}
  27. void laplace(double* u, double* x,
  28. double* y, double* f,
  29. long Ns, long Nt) {
  30. for (long t = 0; t < Nt; t++) {
  31. for (long s = 0; s < Ns; s++) {
  32. double rx, ry, rz;
  33. rx = x[s*3]-y[t*3];
  34. ry = x[s*3+1]-y[t*3+1];
  35. rz = x[s*3+2]-y[t*3+2];
  36. double r2 = rx*rx+ry*ry+rz*rz;
  37. if (r2 > 0) {
  38. double rinv = 1/sqrt(r2);
  39. u[t] += f[s] * rinv;
  40. }
  41. }
  42. }
  43. }
  44. \end{minted}
  45. %>>>
  46. \end{overprint}
  47. \column{0.25\textwidth}
  48. \center
  49. \resizebox{0.99\textwidth}{!}{\begin{tikzpicture} %<<<
  50. \draw[draw=black,ultra thick] (0,0) rectangle (4,4.2);
  51. \node at (2,3.8) {\Large CPU};
  52. \draw[draw=black,ultra thick] (0.25,0.125) rectangle (3.75,1.125);
  53. \node at (2,0.625) {\Large Cache};
  54. \draw[draw=black,ultra thick] (0.25,1.25) rectangle (3.75,2.25);
  55. \node at (2,1.75) {\Large Control Unit};
  56. \draw[draw=black,ultra thick] (0.25,2.375) rectangle (3.75,3.375);
  57. \node at (2,2.875) {\Large ALU};
  58. \draw[latex-latex, ultra thick] (1,0) -- (1,-1);
  59. \draw[latex-latex, ultra thick] (2,0) -- (2,-1);
  60. \draw[latex-latex, ultra thick] (3,0) -- (3,-1);
  61. \draw[draw=black,ultra thick] (0,-2.2) rectangle (4,-1);
  62. \node at (2,-1.6) {\Large RAM};
  63. \end{tikzpicture}} %>>>
  64. \column{0.31\textwidth}
  65. \begin{itemize}
  66. \setlength\itemsep{0.75em}
  67. \item code executes line-by-line
  68. \item one scalar operation at a time
  69. \item one operation per clock cycle
  70. \item sequentially and in order
  71. \end{itemize}
  72. \only<2>{}
  73. \end{columns}
  74. % Programming language and hardware abstraction go hand-in-hand
  75. % most languages don't make it easy to specify when it is safe to vectorize (aliasing)
  76. % lies! forget that!
  77. % you have been lied to!
  78. % that is not how code executes on a computer at all
  79. % instructions can execute in any order -- but you are guaranteed that the net effect is the same as sequential
  80. % execution
  81. \end{frame}
  82. \endgroup
  83. %>>>
  84. \begin{frame} \frametitle{Core microarchitecture}{} %<<<
  85. \begin{columns}[t]
  86. \column{0.55\textwidth}
  87. \resizebox{0.99\textwidth}{!}{\begin{tikzpicture}
  88. \only<1>{
  89. %\write18{wget -O figs/skylake-arch.svg https://en.wikichip.org/w/images/e/ee/skylake_server_block_diagram.svg}
  90. %\write18{convert figs/skylake-arch.svg figs/skylake-arch.png}
  91. \node at (0,0) {\includegraphics[width=0.9\textwidth]{figs/skylake-arch}};
  92. }
  93. \only<2>{
  94. \node[opacity=0] at (0,0) {\includegraphics[width=0.9\textwidth]{figs/skylake-arch}};
  95. \node at (0,0) {\includegraphics[width=0.99\textwidth]{figs/skylake_scheduler}};
  96. \node at (0,-3) {\small Skylake micro-architecture (wikichip.org)};
  97. }
  98. \end{tikzpicture}}
  99. \column{0.45\textwidth}
  100. \begin{itemize}
  101. \setlength\itemsep{0.85em}
  102. \item {Branch prediction and speculative execution}
  103. \item {Out-of-order execution}
  104. \only<2>{
  105. \item {Superscalar execution:} \\
  106. \quad 2-FP, 2-reads, 1-write
  107. \item {Vector instructions}
  108. \item {Pipelining:} `assembly line' \\
  109. \quad latency and throughput
  110. }
  111. %Instruction pipelining where the execution of multiple instructions can be partially overlapped.
  112. %Superscalar execution, VLIW, and the closely related explicitly parallel instruction computing concepts, in which
  113. %multiple execution units are used to execute multiple instructions in parallel.
  114. %Out-of-order execution where instructions execute in any order that does not violate data dependencies. Note that
  115. %this technique is independent of both pipelining and superscalar execution. Current implementations of out-of-order
  116. %execution dynamically (i.e., while the program is executing and without any help from the compiler) extract ILP from
  117. %ordinary programs. An alternative is to extract this parallelism at compile time and somehow convey this information
  118. %to the hardware. Due to the complexity of scaling the out-of-order execution technique, the industry has re-examined
  119. %instruction sets which explicitly encode multiple independent operations per instruction.
  120. %Register renaming which refers to a technique used to avoid unnecessary serialization of program operations imposed
  121. %by the reuse of registers by those operations, used to enable out-of-order execution.
  122. %Speculative execution which allows the execution of complete instructions or parts of instructions before being
  123. %certain whether this execution should take place. A commonly used form of speculative execution is control flow
  124. %speculation where instructions past a control flow instruction (e.g., a branch) are executed before the target of
  125. %the control flow instruction is determined. Several other forms of speculative execution have been proposed and are
  126. %in use including speculative execution driven by value prediction, memory dependence prediction and cache latency
  127. %prediction.
  128. %Branch prediction which is used to avoid stalling for control dependencies to be resolved. Branch prediction is used
  129. %with speculative execution.
  130. \end{itemize}
  131. \end{columns}
  132. % CPU core complexity: https://www.youtube.com/watch?v=eICYHA-eyXM&t=555s
  133. % out-of-order, vector, branch-prediction
  134. \end{frame}
  135. %>>>
  136. \begin{frame} \frametitle{Instruction level parallelism}{} %<<<
  137. \center
  138. \includegraphics[width=0.8\textwidth]{figs/intel-core-gflops}
  139. {\footnotesize John McCalpin - Memory bandwidth and system balance in HPC systems, 2016}
  140. \end{frame}
  141. %>>>
  142. \begin{frame}[fragile] \frametitle{Instruction latency and throughput}{} %<<<
  143. \begin{columns}[t]
  144. \column{0.45\textwidth}
  145. \footnotesize
  146. \begin{overprint}
  147. \onslide<1>%<<<
  148. \begin{minted}[
  149. frame=lines,
  150. fontsize=\footnotesize,
  151. linenos,
  152. gobble=8,
  153. mathescape
  154. ]{C++}
  155. #include <iostream>
  156. #include <omp.h>
  157. int main(int argc, char** argv) {
  158. double x = 3.141, one = 1.0;
  159. double T = -omp_get_wtime();
  160. for (long i = 0; i < 1000000000L; i++) {
  161. x = one + x;
  162. }
  163. T += omp_get_wtime();
  164. std::cout<<"T = "<< T <<'\n';
  165. std::cout<<"cycles/iter = "<< 3.3*T <<'\n';
  166. return 0;
  167. }
  168. \end{minted}
  169. %>>>
  170. \onslide<2-3>%<<<
  171. \begin{minted}[
  172. frame=lines,
  173. fontsize=\footnotesize,
  174. linenos,
  175. gobble=8,
  176. mathescape
  177. ]{C++}
  178. #include <iostream>
  179. #include <omp.h>
  180. int main(int argc, char** argv) {
  181. double x = 3.141, one = 1.0;
  182. double T = -omp_get_wtime();
  183. for (long i = 0; i < 1000000000L; i++) {
  184. x = one + x;
  185. }
  186. T += omp_get_wtime();
  187. std::cout<<"T = "<< T <<'\n';
  188. std::cout<<"cycles/iter = "<< 3.3*T <<'\n';
  189. std::cout<<x<<'\n';
  190. return 0;
  191. }
  192. \end{minted}
  193. %>>>
  194. \onslide<4-5>%<<<
  195. \begin{minted}[
  196. frame=lines,
  197. fontsize=\footnotesize,
  198. linenos,
  199. gobble=10,
  200. mathescape
  201. ]{C++}
  202. double x[32], one = 1;
  203. // ... initialize x
  204. double T = -omp_get_wtime();
  205. for (long i = 0; i < 1000000000L; i++) {
  206. x[0] = one + x[0];
  207. x[1] = one + x[1];
  208. x[2] = one + x[2];
  209. x[3] = one + x[3];
  210. ...
  211. x[31] = one + x[31];
  212. }
  213. T += omp_get_wtime();
  214. std::cout<<"T = "<< T <<'\n';
  215. std::cout<<"cycles/iter = "<< 3.3*T <<'\n';
  216. \end{minted}
  217. %>>>
  218. \end{overprint}
  219. \column{0.1\textwidth}
  220. \column{0.45\textwidth}
  221. \begin{overprint}
  222. \onslide<1-2>%<<<
  223. \begin{minted}[gobble=8,fontsize=\footnotesize]{text}
  224. $ g++ -O3 -march=native -fopenmp test.cpp
  225. $ ./a.out
  226. T = 0
  227. cycles/iter = 0
  228. \end{minted}
  229. %>>>
  230. \onslide<3-4>%<<<
  231. \begin{minted}[gobble=8,fontsize=\footnotesize]{text}
  232. $ g++ -O3 -march=native -fopenmp test.cpp
  233. $ ./a.out
  234. T = 0
  235. cycles/iter = 0
  236. $ g++ -O3 -march=native -fopenmp test.cpp
  237. $ ./a.out
  238. T = 1.22387
  239. cycles/iter = 4.03876
  240. \end{minted}
  241. %>>>
  242. \onslide<5-5>%<<<
  243. \begin{minted}[gobble=8,fontsize=\footnotesize]{text}
  244. $ g++ -O3 -march=native -fopenmp test.cpp
  245. $ ./a.out
  246. T = 0
  247. cycles/iter = 0
  248. $ g++ -O3 -march=native -fopenmp test.cpp
  249. $ ./a.out
  250. T = 1.22387
  251. cycles/iter = 4.03876
  252. $ g++ -O3 -march=native -fopenmp test.cpp
  253. $ ./a.out
  254. T = 1.22366
  255. cycles/iter = 4.03809
  256. \end{minted}
  257. \textcolor{red}{\qquad 8 adds/cycle!}
  258. %>>>
  259. \end{overprint}
  260. \end{columns}
  261. \end{frame}
  262. %>>>
  263. \begin{frame}[t] \frametitle{SIMD vector instructions}{} %<<<
  264. \begin{columns}[t]
  265. \column{0.7\textwidth}
  266. \only<1>{
  267. \begin{itemize}
  268. \setlength\itemsep{1em}
  269. \item Think in vectors instead of scalars (float, double)
  270. \item Re-organize computations as vector operations
  271. \begin{itemize}
  272. \item Struct-of-arrays (SOA) \\
  273. $\{x_1,y_1,z_1, ~~x_2,y_2,z_2, \cdots, ~~x_n,y_n,z_n\}$
  274. \item Array-of-struct (AOS) \\
  275. $\{x_1,\cdots, x_n, ~~y_1,\cdots, y_n, ~~z_1,\cdots, z_n\}$
  276. \end{itemize}
  277. \item Tell the compiler it is safe to use SIMD instructions
  278. \begin{itemize}
  279. \item most languages don't make it easy to specify when it is safe to vectorize (aliasing)
  280. \end{itemize}
  281. \end{itemize}
  282. }
  283. \only<2>{
  284. \begin{itemize}
  285. \setlength\itemsep{1em}
  286. \item {Auto vectorization:} \textcolor{red}{unreliable!}
  287. \begin{itemize}
  288. \item Compiler specific hints:\\
  289. {-fopt-info-vec-optimized} \\
  290. {\color{blue} \_\_builtin\_assume\_aligned(a, 32)} \\
  291. {\color{magenta} \#pragma ivdep}
  292. \item OpenMP 4.0: {\color{magenta} \#pragma omp simd}
  293. \end{itemize}
  294. \item {Assembly:} \textcolor{red}{too hard!}
  295. \item {Vector intrinsics:} \textcolor{red}{works but messy!}
  296. \begin{itemize}
  297. \item {\_mm512\_add\_pd(\_\_m512d, \_\_m512d)}
  298. \item {\_mm512\_mul\_pd(\_\_m512d, \_\_m512d)}
  299. \end{itemize}
  300. \item {C++ vector libraries:} \textcolor{green}{intuitive and clean}
  301. %\begin{itemize}
  302. % \item Vector objects, overloaded operators (+, -, *, $||$, \&\& etc)
  303. %\end{itemize}
  304. \end{itemize}
  305. }
  306. \only<3>{
  307. \begin{itemize}
  308. \setlength\itemsep{1em}
  309. \item {C++ vector libraries:} \textcolor{green}{intuitive and clean}
  310. \begin{itemize}
  311. \setlength\itemsep{1em}
  312. \item Vector objects, overloaded operators (+, -, *, $||$, \&\& etc)
  313. \item Vector Class Library - Agner Fog\\
  314. \url{https://github.com/vectorclass/version2}
  315. \item SCTL (\url{https://github.com/dmalhotra/SCTL})
  316. \item Similar proposals for future C++ standard library \\
  317. {\scriptsize \url{https://en.cppreference.com/w/cpp/experimental/simd}}
  318. \end{itemize}
  319. \end{itemize}
  320. }
  321. \column{0,3\textwidth}
  322. \center
  323. \begin{tikzpicture}%<<<
  324. \node at (0,0.5) {\scriptsize SSE};
  325. \node at (0,0.2) {\scriptsize 128-bit};
  326. \draw[fill=c2] (-0.7,-0.0) rectangle (-0.5,-0.2);
  327. \draw[fill=c2] (-0.7,-0.2) rectangle (-0.5,-0.4);
  328. \node at (-0.27,-0.2) {\scriptsize =};
  329. \draw[fill=c2] (0,-0.0) rectangle (0.2,-0.2);
  330. \draw[fill=c2] (0,-0.2) rectangle (0.2,-0.4);
  331. \node at (0.42,-0.2) {\scriptsize $+$};
  332. \draw[fill=c2] (0.7,-0.0) rectangle (0.9,-0.2);
  333. \draw[fill=c2] (0.7,-0.2) rectangle (0.9,-0.4);
  334. \draw[draw=none] (0.7,-1.4) rectangle (0.9,-1.6);
  335. \end{tikzpicture}%>>>
  336. \hspace{1.5em}
  337. \begin{tikzpicture}%<<<
  338. \node at (0,0.5) {\scriptsize AVX};
  339. \node at (0,0.2) {\scriptsize 256-bit};
  340. \draw[fill=c3] (-0.7,-0.0) rectangle (-0.5,-0.2);
  341. \draw[fill=c3] (-0.7,-0.2) rectangle (-0.5,-0.4);
  342. \draw[fill=c3] (-0.7,-0.4) rectangle (-0.5,-0.6);
  343. \draw[fill=c3] (-0.7,-0.6) rectangle (-0.5,-0.8);
  344. \node at (-0.27,-0.4) {\scriptsize =};
  345. \draw[fill=c3] (0,-0.0) rectangle (0.2,-0.2);
  346. \draw[fill=c3] (0,-0.2) rectangle (0.2,-0.4);
  347. \draw[fill=c3] (0,-0.4) rectangle (0.2,-0.6);
  348. \draw[fill=c3] (0,-0.6) rectangle (0.2,-0.8);
  349. \node at (0.42,-0.4) {\scriptsize $+$};
  350. \draw[fill=c3] (0.7,-0.0) rectangle (0.9,-0.2);
  351. \draw[fill=c3] (0.7,-0.2) rectangle (0.9,-0.4);
  352. \draw[fill=c3] (0.7,-0.4) rectangle (0.9,-0.6);
  353. \draw[fill=c3] (0.7,-0.6) rectangle (0.9,-0.8);
  354. \draw[draw=none] (0.7,-1.4) rectangle (0.9,-1.6);
  355. \end{tikzpicture}%>>>
  356. \begin{tikzpicture}%<<<
  357. \node at (0,0.5) {\scriptsize AVX512};
  358. \node at (0,0.2) {\scriptsize 512-bit};
  359. \draw[fill=c4] (-0.7,-0.0) rectangle (-0.5,-0.2);
  360. \draw[fill=c4] (-0.7,-0.2) rectangle (-0.5,-0.4);
  361. \draw[fill=c4] (-0.7,-0.4) rectangle (-0.5,-0.6);
  362. \draw[fill=c4] (-0.7,-0.6) rectangle (-0.5,-0.8);
  363. \draw[fill=c4] (-0.7,-0.8) rectangle (-0.5,-1.0);
  364. \draw[fill=c4] (-0.7,-1.0) rectangle (-0.5,-1.2);
  365. \draw[fill=c4] (-0.7,-1.2) rectangle (-0.5,-1.4);
  366. \draw[fill=c4] (-0.7,-1.4) rectangle (-0.5,-1.6);
  367. \node at (-0.27,-0.8) {\scriptsize =};
  368. \draw[fill=c4] (0,-0.0) rectangle (0.2,-0.2);
  369. \draw[fill=c4] (0,-0.2) rectangle (0.2,-0.4);
  370. \draw[fill=c4] (0,-0.4) rectangle (0.2,-0.6);
  371. \draw[fill=c4] (0,-0.6) rectangle (0.2,-0.8);
  372. \draw[fill=c4] (0,-0.8) rectangle (0.2,-1.0);
  373. \draw[fill=c4] (0,-1.0) rectangle (0.2,-1.2);
  374. \draw[fill=c4] (0,-1.2) rectangle (0.2,-1.4);
  375. \draw[fill=c4] (0,-1.4) rectangle (0.2,-1.6);
  376. \node at (0.42,-0.8) {\scriptsize $+$};
  377. \draw[fill=c4] (0.7,-0.0) rectangle (0.9,-0.2);
  378. \draw[fill=c4] (0.7,-0.2) rectangle (0.9,-0.4);
  379. \draw[fill=c4] (0.7,-0.4) rectangle (0.9,-0.6);
  380. \draw[fill=c4] (0.7,-0.6) rectangle (0.9,-0.8);
  381. \draw[fill=c4] (0.7,-0.8) rectangle (0.9,-1.0);
  382. \draw[fill=c4] (0.7,-1.0) rectangle (0.9,-1.2);
  383. \draw[fill=c4] (0.7,-1.2) rectangle (0.9,-1.4);
  384. \draw[fill=c4] (0.7,-1.4) rectangle (0.9,-1.6);
  385. \end{tikzpicture}%>>>
  386. \end{columns}
  387. \end{frame}
  388. %>>>
  389. \begin{frame}[t,fragile] \frametitle{Instruction latency and throughput}{} %<<<
  390. \vspace{-1em}
  391. \begin{columns}[t]
  392. \column{0.45\textwidth}
  393. \footnotesize
  394. \begin{overprint}
  395. \onslide<1-2>%<<<
  396. \begin{minted}[
  397. frame=lines,
  398. fontsize=\footnotesize,
  399. linenos,
  400. gobble=10,
  401. mathescape
  402. ]{C++}
  403. sctl::Vec<double,8> x[8], one = 1;
  404. // ... initialize x
  405. double T = -omp_get_wtime();
  406. for (long i = 0; i < 1000000000L; i++) {
  407. x[0] = one + x[0];
  408. x[1] = one + x[1];
  409. x[2] = one + x[2];
  410. x[3] = one + x[3];
  411. ...
  412. x[8] = one + x[8];
  413. }
  414. T += omp_get_wtime();
  415. std::cout<<"T = "<< T <<'\n';
  416. std::cout<<"cycles/iter = "<< 3.3*T <<'\n';
  417. \end{minted}
  418. %>>>
  419. \onslide<3->%<<<
  420. \begin{minted}[
  421. frame=lines,
  422. fontsize=\footnotesize,
  423. linenos,
  424. gobble=10,
  425. mathescape
  426. ]{C++}
  427. sctl::Vec<double,8> x[8], one = 1;
  428. // ... initialize x
  429. double T = -omp_get_wtime();
  430. for (long i = 0; i < 1000000000L; i++) {
  431. x[0] = one / x[0];
  432. x[1] = one / x[1];
  433. x[2] = one / x[2];
  434. x[3] = one / x[3];
  435. ...
  436. x[8] = one / x[8];
  437. }
  438. T += omp_get_wtime();
  439. std::cout<<"T = "<< T <<'\n';
  440. std::cout<<"cycles/iter = "<< 3.3*T <<'\n';
  441. \end{minted}
  442. %>>>
  443. \end{overprint}
  444. \column{0.1\textwidth}
  445. \column{0.45\textwidth}
  446. \begin{overprint}
  447. \onslide<2>%<<<
  448. \begin{minted}[gobble=8,fontsize=\footnotesize]{text}
  449. $ g++ -O3 -march=native -fopenmp test.cpp
  450. $ ./a.out
  451. T = 1.22806
  452. cycles/iter = 4.05259
  453. \end{minted}
  454. \textcolor{red}{\qquad 16 adds/cycle!}
  455. %>>>
  456. \onslide<3>%<<<
  457. \begin{minted}[gobble=8,fontsize=\footnotesize]{text}
  458. $ g++ -O3 -march=native -fopenmp test.cpp
  459. $ ./a.out
  460. T = 1.22806
  461. cycles/iter = 4.05259
  462. \end{minted}
  463. \textcolor{red}{\qquad 16 adds/cycle!}
  464. \vspace{0.5em}
  465. \qquad --- floating-point division ---
  466. %>>>
  467. \onslide<4>%<<<
  468. \begin{minted}[gobble=8,fontsize=\footnotesize]{text}
  469. $ g++ -O3 -march=native -fopenmp test.cpp
  470. $ ./a.out
  471. T = 1.22806
  472. cycles/iter = 4.05259
  473. \end{minted}
  474. \textcolor{red}{\qquad 16 adds/cycle!}
  475. \vspace{0.5em}
  476. \qquad --- floating-point division ---
  477. \begin{minted}[gobble=8,fontsize=\footnotesize]{text}
  478. $ g++ -O3 -march=native -fopenmp test.cpp
  479. $ ./a.out
  480. T = 39.1521
  481. cycles/iter = 129.202
  482. \end{minted}
  483. \textcolor{red}{\qquad $\sim 32\times$ slower!}
  484. %>>>
  485. \onslide<5->%<<<
  486. \begin{minted}[gobble=8,fontsize=\footnotesize]{text}
  487. $ g++ -O3 -march=native -fopenmp test.cpp
  488. $ ./a.out
  489. T = 1.22806
  490. cycles/iter = 4.05259
  491. \end{minted}
  492. \textcolor{red}{\qquad 16 adds/cycle!}
  493. \vspace{0.5em}
  494. \qquad --- floating-point division ---
  495. \begin{minted}[gobble=8,fontsize=\footnotesize]{text}
  496. $ g++ -O3 -march=native -fopenmp test.cpp
  497. $ ./a.out
  498. T = 39.1521
  499. cycles/iter = 129.202
  500. \end{minted}
  501. \textcolor{red}{\qquad $\sim 32\times$ slower!}
  502. \footnotesize
  503. \vspace{0.5em}
  504. \quad {\normalsize Fast}: bitwise ops, int \& fp ops ($+,-,*$)
  505. \vspace{0.2em}
  506. \quad {\normalsize Slow}: branches, $/, {\sqrt \cdot}, \sin, \cos, \cdots$
  507. %>>>
  508. \end{overprint}
  509. \end{columns}
  510. \end{frame}
  511. %>>>
  512. \begin{frame}[fragile] \frametitle{Pipelining polynomial eval (Horner's rule)} %<<<
  513. \begin{columns}[T]
  514. \column{0.15\textwidth}
  515. {\bf Input:} \\
  516. x,~a,~b,~c,~d,~e,~f,~g,~h \\
  517. \vspace{1em}
  518. {\bf Compute:} \\
  519. ((((((ax+b)x+c)x+d)x\\
  520. ~~~~+e)x+f)x+g)x+h
  521. \column{0.6\textwidth}
  522. \resizebox{0.88\textwidth}{!}{\begin{tikzpicture}[nodes={draw, ellipse}, latex-]
  523. \node{$\times, +$}
  524. child { node {$\times, +$}
  525. child { node {$\times, +$}
  526. child { node {$\times, +$}
  527. child { node {$\times, +$}
  528. child { node {$\times, +$}
  529. child { node {$\times, +$}
  530. child { node {a} }
  531. child { node {x} }
  532. child { node {b} }
  533. }
  534. child { node {x} }
  535. child { node {c} }
  536. }
  537. child { node {x} }
  538. child { node {d} }
  539. }
  540. child { node {x} }
  541. child { node {e} }
  542. }
  543. child { node {x} }
  544. child { node {f} }
  545. }
  546. child { node {x} }
  547. child { node {g} }
  548. }
  549. child { node {x} }
  550. child { node {h} };
  551. \end{tikzpicture}}%
  552. \column{0.25\textwidth}
  553. \textcolor{c1}{u = a * x + b}\only<1-4>{ $\leftarrow$} \\
  554. \textcolor{c2}{v = u * x + c}\only<5-8>{ $\leftarrow$} \\
  555. \textcolor{c3}{w = v * x + d}\only<9-12>{ $\leftarrow$} \\
  556. \textcolor{c4}{p = w * x + e}\only<13-16>{ $\leftarrow$} \\
  557. \textcolor{c5}{q = p * x + f}\only<17-20>{ $\leftarrow$} \\
  558. \textcolor{c6}{r = q * x + g}\only<21-24>{ $\leftarrow$} \\
  559. \textcolor{c7}{s = r * x + h}\only<25-28>{ $\leftarrow$} \\
  560. \vspace{1em}
  561. {\bf Pipeline:}
  562. \vspace{0.5em}
  563. \resizebox{0.99\textwidth}{!}{\begin{tikzpicture}
  564. \draw[draw=none] (0,0) rectangle (4,1);
  565. \only<1-28>{
  566. \draw[fill=white] (0,0) rectangle (1,0.5);
  567. \draw[fill=white] (1,0) rectangle (2,0.5);
  568. \draw[fill=white] (2,0) rectangle (3,0.5);
  569. \draw[fill=white] (3,0) rectangle (4,0.5);
  570. \draw[fill=white] (0,0.6) rectangle (1,1.1);
  571. \draw[fill=white] (1,0.6) rectangle (2,1.1);
  572. \draw[fill=white] (2,0.6) rectangle (3,1.1);
  573. \draw[fill=white] (3,0.6) rectangle (4,1.1);
  574. }
  575. \only<1>{\draw[fill=c1] (0,0) rectangle (1,0.5);}
  576. \only<2>{\draw[fill=c1] (1,0) rectangle (2,0.5);}
  577. \only<3>{\draw[fill=c1] (2,0) rectangle (3,0.5);}
  578. \only<4>{\draw[fill=c1] (3,0) rectangle (4,0.5);}
  579. \only<5>{\draw[fill=c2] (0,0) rectangle (1,0.5);}
  580. \only<6>{\draw[fill=c2] (1,0) rectangle (2,0.5);}
  581. \only<7>{\draw[fill=c2] (2,0) rectangle (3,0.5);}
  582. \only<8>{\draw[fill=c2] (3,0) rectangle (4,0.5);}
  583. \only<9 >{\draw[fill=c3] (0,0) rectangle (1,0.5);}
  584. \only<10>{\draw[fill=c3] (1,0) rectangle (2,0.5);}
  585. \only<11>{\draw[fill=c3] (2,0) rectangle (3,0.5);}
  586. \only<12>{\draw[fill=c3] (3,0) rectangle (4,0.5);}
  587. \only<13>{\draw[fill=c4] (0,0) rectangle (1,0.5);}
  588. \only<14>{\draw[fill=c4] (1,0) rectangle (2,0.5);}
  589. \only<15>{\draw[fill=c4] (2,0) rectangle (3,0.5);}
  590. \only<16>{\draw[fill=c4] (3,0) rectangle (4,0.5);}
  591. \only<17>{\draw[fill=c5] (0,0) rectangle (1,0.5);}
  592. \only<18>{\draw[fill=c5] (1,0) rectangle (2,0.5);}
  593. \only<19>{\draw[fill=c5] (2,0) rectangle (3,0.5);}
  594. \only<20>{\draw[fill=c5] (3,0) rectangle (4,0.5);}
  595. \only<21>{\draw[fill=c6] (0,0) rectangle (1,0.5);}
  596. \only<22>{\draw[fill=c6] (1,0) rectangle (2,0.5);}
  597. \only<23>{\draw[fill=c6] (2,0) rectangle (3,0.5);}
  598. \only<24>{\draw[fill=c6] (3,0) rectangle (4,0.5);}
  599. \only<25>{\draw[fill=c7] (0,0) rectangle (1,0.5);}
  600. \only<26>{\draw[fill=c7] (1,0) rectangle (2,0.5);}
  601. \only<27>{\draw[fill=c7] (2,0) rectangle (3,0.5);}
  602. \only<28>{\draw[fill=c7] (3,0) rectangle (4,0.5);}
  603. \only<29>{\node at (2,0.75) {\Large 28 cycles};}
  604. \only<29>{\node at (2,0.25) {\Large 12.5\% utilization!};}
  605. \end{tikzpicture}}%
  606. \end{columns}
  607. % Helmholtz kernel code example
  608. % sample sort code
  609. % evaluating a polynomial
  610. % what we think happens
  611. % reality!
  612. \end{frame}
  613. %>>>
  614. \begin{frame}[fragile] \frametitle{Pipelining: polynomial eval (Estrin's method)} %<<<
  615. \begin{columns}[T]
  616. \column{0.75\textwidth}
  617. {\bf Input:} \\
  618. x,~a,~b,~c,~d,~e,~f,~g,~h \\
  619. \vspace{1em}
  620. {\bf Compute:} \\
  621. ((ax+b)x\textsuperscript{2}+(cx+d))x\textsuperscript{4}+(ex+f)x\textsuperscript{2}+(gx+h)
  622. \resizebox{0.99\textwidth}{!}{\begin{tikzpicture}[
  623. baseline,
  624. level distance=15mm,
  625. %text depth=.5em,
  626. %text height=.8em,
  627. level 1/.style={sibling distance=10em},
  628. level 2/.style={sibling distance=5em},
  629. level 3/.style={sibling distance=2.5em},
  630. level 4/.style={sibling distance=1em},
  631. nodes={draw, ellipse}, latex-]
  632. \node{$\times,+$}
  633. child { node {$\times,+$}
  634. child { node {$\times,+$}
  635. child { node {a} }
  636. child { node {x} }
  637. child { node {b} }
  638. }
  639. child { node {$\times$}
  640. child { node {x} }
  641. }
  642. child { node {$\times,+$}
  643. child { node {c} }
  644. child { node {x} }
  645. child { node {d} }
  646. }
  647. }
  648. child { node {$\times$}
  649. child { node {$\times$}
  650. child { node {x} }
  651. }
  652. }
  653. child { node {$\times,+$}
  654. child { node {$\times,+$}
  655. child { node {e} }
  656. child { node {x} }
  657. child { node {f} }
  658. }
  659. child { node {$\times$}
  660. child { node {x} }
  661. }
  662. child { node {$\times,+$}
  663. child { node {g} }
  664. child { node {x} }
  665. child { node {h} }
  666. }
  667. };
  668. \end{tikzpicture}}%
  669. \column{0.25\textwidth}
  670. %<<<
  671. \textcolor{c1}{x\textsuperscript{2} = x * x} \only<1-4>{ $\leftarrow$} \\ %
  672. \textcolor{c2}{x\textsuperscript{4} = x\textsuperscript{2} * x\textsuperscript{2}}\only<5-8>{ $\leftarrow$} \\ %
  673. \textcolor{c3}{u = a * x + b} \only<1-4>{ $\leftarrow$} \\
  674. \textcolor{c4}{v = c * x + d} \only<2-5>{ $\leftarrow$} \\ %
  675. \textcolor{c5}{w = e * x + f} \only<2-5>{ $\leftarrow$} \\
  676. \textcolor{c6}{p = g * x + h} \only<3-6>{ $\leftarrow$} \\ %
  677. \textcolor{c7}{q = u * x\textsuperscript{2} + v} \only<6-9>{ $\leftarrow$} \\ %
  678. \textcolor{c8}{r = w * x\textsuperscript{2} + p} \only<7-10>{ $\leftarrow$} \\ %
  679. \textcolor{c9}{s = q * x\textsuperscript{4} + r} \only<11-14>{ $\leftarrow$} \\ %
  680. \vspace{0.5em}
  681. {\bf Pipeline:}
  682. \vspace{0.1em}
  683. \resizebox{0.99\textwidth}{!}{\begin{tikzpicture}
  684. \draw[draw=none] (0,0) rectangle (4,1);
  685. \only<1-14>{
  686. \draw[fill=white] (0,0) rectangle (1,0.5);
  687. \draw[fill=white] (1,0) rectangle (2,0.5);
  688. \draw[fill=white] (2,0) rectangle (3,0.5);
  689. \draw[fill=white] (3,0) rectangle (4,0.5);
  690. \draw[fill=white] (0,0.6) rectangle (1,1.1);
  691. \draw[fill=white] (1,0.6) rectangle (2,1.1);
  692. \draw[fill=white] (2,0.6) rectangle (3,1.1);
  693. \draw[fill=white] (3,0.6) rectangle (4,1.1);
  694. }
  695. \only<1>{\draw[fill=c1] (0,0) rectangle (1,0.5);}
  696. \only<2>{\draw[fill=c1] (1,0) rectangle (2,0.5);}
  697. \only<3>{\draw[fill=c1] (2,0) rectangle (3,0.5);}
  698. \only<4>{\draw[fill=c1] (3,0) rectangle (4,0.5);}
  699. \only<5>{\draw[fill=c2] (0,0) rectangle (1,0.5);}
  700. \only<6>{\draw[fill=c2] (1,0) rectangle (2,0.5);}
  701. \only<7>{\draw[fill=c2] (2,0) rectangle (3,0.5);}
  702. \only<8>{\draw[fill=c2] (3,0) rectangle (4,0.5);}
  703. \only<1>{\draw[fill=c3] (0,0.6) rectangle (1,1.1);}
  704. \only<2>{\draw[fill=c3] (1,0.6) rectangle (2,1.1);}
  705. \only<3>{\draw[fill=c3] (2,0.6) rectangle (3,1.1);}
  706. \only<4>{\draw[fill=c3] (3,0.6) rectangle (4,1.1);}
  707. \only<2>{\draw[fill=c4] (0,0) rectangle (1,0.5);}
  708. \only<3>{\draw[fill=c4] (1,0) rectangle (2,0.5);}
  709. \only<4>{\draw[fill=c4] (2,0) rectangle (3,0.5);}
  710. \only<5>{\draw[fill=c4] (3,0) rectangle (4,0.5);}
  711. \only<2>{\draw[fill=c5] (0,0.6) rectangle (1,1.1);}
  712. \only<3>{\draw[fill=c5] (1,0.6) rectangle (2,1.1);}
  713. \only<4>{\draw[fill=c5] (2,0.6) rectangle (3,1.1);}
  714. \only<5>{\draw[fill=c5] (3,0.6) rectangle (4,1.1);}
  715. \only<3>{\draw[fill=c6] (0,0) rectangle (1,0.5);}
  716. \only<4>{\draw[fill=c6] (1,0) rectangle (2,0.5);}
  717. \only<5>{\draw[fill=c6] (2,0) rectangle (3,0.5);}
  718. \only<6>{\draw[fill=c6] (3,0) rectangle (4,0.5);}
  719. \only<6>{\draw[fill=c7] (0,0) rectangle (1,0.5);}
  720. \only<7>{\draw[fill=c7] (1,0) rectangle (2,0.5);}
  721. \only<8>{\draw[fill=c7] (2,0) rectangle (3,0.5);}
  722. \only<9>{\draw[fill=c7] (3,0) rectangle (4,0.5);}
  723. \only<7>{\draw[fill=c8] (0,0) rectangle (1,0.5);}
  724. \only<8>{\draw[fill=c8] (1,0) rectangle (2,0.5);}
  725. \only<9>{\draw[fill=c8] (2,0) rectangle (3,0.5);}
  726. \only<10>{\draw[fill=c8] (3,0) rectangle (4,0.5);}
  727. \only<11>{\draw[fill=c9] (0,0) rectangle (1,0.5);}
  728. \only<12>{\draw[fill=c9] (1,0) rectangle (2,0.5);}
  729. \only<13>{\draw[fill=c9] (2,0) rectangle (3,0.5);}
  730. \only<14>{\draw[fill=c9] (3,0) rectangle (4,0.5);}
  731. \only<15>{\node at (2,0.75) {\Large 14 cycles};}
  732. \only<15>{\node at (2,0.25) {\Large 2\times speedup!};}
  733. \end{tikzpicture}}%
  734. %>>>
  735. %%<<<
  736. %\textcolor{c1}{x\textsuperscript{2} = x * x} \only<1-4>{ $\leftarrow$} \\
  737. %\textcolor{c2}{x\textsuperscript{4} = x\textsuperscript{2} * x\textsuperscript{2}}\only<5-8>{ $\leftarrow$} \\
  738. %\textcolor{c3}{u = a * x + b} \only<2-5>{ $\leftarrow$} \\
  739. %\textcolor{c4}{v = c * x + d} \only<3-6>{ $\leftarrow$} \\
  740. %\textcolor{c5}{w = e * x + f} \only<4-7>{ $\leftarrow$} \\
  741. %\textcolor{c6}{p = g * x + h} \only<6-9>{ $\leftarrow$} \\
  742. %\textcolor{c7}{q = u * x\textsuperscript{2} + v} \only<7-10>{ $\leftarrow$} \\
  743. %\textcolor{c8}{r = w * x\textsuperscript{2} + p} \only<10-13>{ $\leftarrow$} \\
  744. %\textcolor{c9}{s = q * x\textsuperscript{4} + r} \only<14-17>{ $\leftarrow$} \\
  745. %\vspace{0.5em}
  746. %{\bf Pipeline:}
  747. %\vspace{0.1em}
  748. %\resizebox{0.99\textwidth}{!}{\begin{tikzpicture}
  749. % \draw[draw=none] (0,0) rectangle (4,1);
  750. % \only<1-17>{
  751. % \draw[fill=white] (0,0) rectangle (1,1);
  752. % \draw[fill=white] (1,0) rectangle (2,1);
  753. % \draw[fill=white] (2,0) rectangle (3,1);
  754. % \draw[fill=white] (3,0) rectangle (4,1);
  755. % }
  756. % \only<1>{\draw[fill=c1] (0,0) rectangle (1,1);}
  757. % \only<2>{\draw[fill=c1] (1,0) rectangle (2,1);}
  758. % \only<3>{\draw[fill=c1] (2,0) rectangle (3,1);}
  759. % \only<4>{\draw[fill=c1] (3,0) rectangle (4,1);}
  760. % \only<5>{\draw[fill=c2] (0,0) rectangle (1,1);}
  761. % \only<6>{\draw[fill=c2] (1,0) rectangle (2,1);}
  762. % \only<7>{\draw[fill=c2] (2,0) rectangle (3,1);}
  763. % \only<8>{\draw[fill=c2] (3,0) rectangle (4,1);}
  764. % \only<2>{\draw[fill=c3] (0,0) rectangle (1,1);}
  765. % \only<3>{\draw[fill=c3] (1,0) rectangle (2,1);}
  766. % \only<4>{\draw[fill=c3] (2,0) rectangle (3,1);}
  767. % \only<5>{\draw[fill=c3] (3,0) rectangle (4,1);}
  768. %
  769. % \only<3>{\draw[fill=c4] (0,0) rectangle (1,1);}
  770. % \only<4>{\draw[fill=c4] (1,0) rectangle (2,1);}
  771. % \only<5>{\draw[fill=c4] (2,0) rectangle (3,1);}
  772. % \only<6>{\draw[fill=c4] (3,0) rectangle (4,1);}
  773. %
  774. % \only<4>{\draw[fill=c5] (0,0) rectangle (1,1);}
  775. % \only<5>{\draw[fill=c5] (1,0) rectangle (2,1);}
  776. % \only<6>{\draw[fill=c5] (2,0) rectangle (3,1);}
  777. % \only<7>{\draw[fill=c5] (3,0) rectangle (4,1);}
  778. %
  779. % \only<6>{\draw[fill=c6] (0,0) rectangle (1,1);}
  780. % \only<7>{\draw[fill=c6] (1,0) rectangle (2,1);}
  781. % \only<8>{\draw[fill=c6] (2,0) rectangle (3,1);}
  782. % \only<9>{\draw[fill=c6] (3,0) rectangle (4,1);}
  783. % \only<7>{\draw[fill=c7] (0,0) rectangle (1,1);}
  784. % \only<8>{\draw[fill=c7] (1,0) rectangle (2,1);}
  785. % \only<9>{\draw[fill=c7] (2,0) rectangle (3,1);}
  786. % \only<10>{\draw[fill=c7] (3,0) rectangle (4,1);}
  787. % \only<10>{\draw[fill=c8] (0,0) rectangle (1,1);}
  788. % \only<11>{\draw[fill=c8] (1,0) rectangle (2,1);}
  789. % \only<12>{\draw[fill=c8] (2,0) rectangle (3,1);}
  790. % \only<13>{\draw[fill=c8] (3,0) rectangle (4,1);}
  791. % \only<14>{\draw[fill=c9] (0,0) rectangle (1,1);}
  792. % \only<15>{\draw[fill=c9] (1,0) rectangle (2,1);}
  793. % \only<16>{\draw[fill=c9] (2,0) rectangle (3,1);}
  794. % \only<17>{\draw[fill=c9] (3,0) rectangle (4,1);}
  795. % \only<18>{\node at (2,0.75) {\Large 17 cycles};}
  796. % \only<18>{\node at (2,0.25) {\Large 60\% faster!};}
  797. %\end{tikzpicture}}%
  798. %%>>>
  799. \end{columns}
  800. % Helmholtz kernel code example
  801. % sample sort code
  802. % evaluating a polynomial
  803. % what we think happens
  804. % reality!
  805. \end{frame}
  806. %>>>
  807. \begin{frame}[t,fragile] \frametitle{Polynomial evaluation: actual performance} %<<<
  808. \vspace{-1em}
  809. \begin{columns}[t]
  810. \column{0.55\textwidth}
  811. \footnotesize
  812. \begin{overprint}
  813. \onslide<1>%<<<
  814. \begin{minted}[
  815. frame=lines,
  816. fontsize=\footnotesize,
  817. linenos,
  818. gobble=10,
  819. mathescape
  820. ]{C++}
  821. // Horner's rule
  822. for (long i = 0; i < 1000000000L; i++) {
  823. x = (((((a*x+b)*x+c)*x+d)*x+e)*x+f*x+g)*x+h;
  824. }
  825. \end{minted}
  826. \begin{minted}[
  827. frame=lines,
  828. fontsize=\footnotesize,
  829. linenos,
  830. gobble=10,
  831. mathescape
  832. ]{C++}
  833. // Estrin's method
  834. for (long i = 0; i < 1000000000L; i++) {
  835. double x2 = x * x;
  836. double x4 = x2 * x2;
  837. x = ((a*x+b)*x2+(c*x+d))*x4+(e*x+f)*x2+(g*x+h);
  838. }
  839. \end{minted}
  840. %>>>
  841. \onslide<2>%<<<
  842. \begin{minted}[
  843. frame=lines,
  844. fontsize=\footnotesize,
  845. linenos,
  846. gobble=10,
  847. mathescape
  848. ]{C++}
  849. // Horner's rule
  850. for (long i = 0; i < 1000000000L; i++) {
  851. x = (((((a*x+b)*x+c)*x+d)*x+e)*x+f*x+g)*x+h;
  852. }
  853. \end{minted}
  854. \begin{minted}[
  855. frame=lines,
  856. fontsize=\footnotesize,
  857. linenos,
  858. gobble=10,
  859. mathescape
  860. ]{C++}
  861. // Estrin's method (unrolled)
  862. for (long i = 0; i < 1000000000L; i++) {
  863. double x2 = x * x;
  864. double x4 = x2 * x2;
  865. double u = a * x + b;
  866. double v = c * x + d;
  867. double w = e * x + f;
  868. double p = g * x + h;
  869. double q = u * x2 + v;
  870. double r = w * x2 + p;
  871. x = q * x4 + r;
  872. }
  873. \end{minted}
  874. %>>>
  875. \end{overprint}
  876. \column{0.05\textwidth}
  877. \column{0.35\textwidth}
  878. \begin{overprint}
  879. \onslide<1>%<<<
  880. \begin{minted}[gobble=8,fontsize=\footnotesize]{text}
  881. Using Horner's rule:
  882. T = 8.82432
  883. cycles/iter = 29.1203
  884. Using Estrin's method:
  885. T = 5.7813
  886. cycles/iter = 19.0783
  887. \end{minted}
  888. \textcolor{red}{\qquad only $1.5\times$ speedup :(}
  889. %>>>
  890. \onslide<2>%<<<
  891. \begin{minted}[gobble=8,fontsize=\footnotesize]{text}
  892. Using Horner's rule:
  893. T = 8.82432
  894. cycles/iter = 29.1203
  895. Using Estrin's method:
  896. T = 4.5794
  897. cycles/iter = 15.112
  898. \end{minted}
  899. \textcolor{red}{\qquad $1.9\times$ speedup!}
  900. %>>>
  901. \end{overprint}
  902. \end{columns}
  903. % perf - show stalled cycles
  904. \end{frame}
  905. %>>>
  906. \begin{frame} \frametitle{Vectorization - GEMM micro-kernel}{} %<<<
  907. % show different ways of vectorizing that don't work
  908. % most languages don't make it easy to specify when it is safe to vectorize (aliasing)
  909. % start with triple loop
  910. % compiler options
  911. % loop unrolling
  912. % __restrict__
  913. %
  914. \end{frame}
  915. %>>>
  916. \begin{frame} \frametitle{Instruction-level parallelism -- summary}{} %<<<
  917. % Use fast operations instead of slow
  918. % Cast all computations in additions, multiplications, bitwise ops (eg. baobzi)
  919. % Avoid expensive ops (div), branches
  920. % vectorization
  921. % data arrangement: AoS vs SoA
  922. % out-of-order execution, pipelining, vectorization:
  923. % - refactor code to expose instruction level parallelism (sometimes even at the cost of extra work)
  924. % batch operations, loop unrolling/fixed-length loops, expose instruction level parallelism
  925. % benefits from fixed-size blocking (compiler can unroll)
  926. % loops have conditionals, so unrolling is difficult
  927. %%%%%%%%%%%%%%% maybe
  928. % unaligned memory accesses
  929. % show penalty from branches
  930. % vector dot product: show data dependency stalls
  931. %%%%%%%%%%%%%%%%%%% not needed
  932. % remove un-necessary operations (pre-allocate memory)
  933. % reduce number of operations (caching)
  934. \end{frame}
  935. %>>>
  936. \begin{frame} \frametitle{Optimized libraries for function evaluation and vectorization} %<<<
  937. % Fast function evaluation using polynomial evaluation
  938. % baobzi
  939. % sf_benchmarks :
  940. \end{frame}
  941. %>>>