This repository was archived by the owner on Aug 14, 2022. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathtpopt3.html
More file actions
603 lines (569 loc) · 25.3 KB
/
Copy pathtpopt3.html
File metadata and controls
603 lines (569 loc) · 25.3 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
<!doctype html>
<html lang="en">
<head>
<meta charset="utf-8">
<title>Pragmatic optimization in modern programming</title>
<meta name="description" content="Pragmatic optimization in modern programming">
<meta name="author" content="geek">
<meta name="apple-mobile-web-app-capable" content="yes">
<meta name="apple-mobile-web-app-status-bar-style" content="black-translucent">
<meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no, minimal-ui">
<link rel="stylesheet" href="css/reveal.css">
<link rel="stylesheet" href="css/theme/beige.css" id="theme">
<link rel="stylesheet" href="css/customization.css">
<link rel="stylesheet" href="lib/css/zenburn.css">
<link rel="shortcut icon" href="images/ico/favicon.ico">
<script>
var link = document.createElement( 'link' );
link.rel = 'stylesheet';
link.type = 'text/css';
link.href = window.location.search.match( /print-pdf/gi ) ? 'css/print/pdf.css' : 'css/print/paper.css';
document.getElementsByTagName( 'head' )[0].appendChild( link );
</script>
<!--[if lt IE 9]>
<script src="lib/js/html5shiv.js"></script>
<![endif]-->
</head>
<body>
<div class="reveal">
<div class="slides">
<section>
<h1>Pragmatic optimization</h1>
<h2>In modern programming</h2>
<h3>Modern computer architecture concepts</h3>
<p>
<small>Created by
<a href="https://github.com/cuda-geek">Marina (geek) Kolpakova</a>
for
<a href="unn.ru">UNN</a>
/ 2015-2016
</small>
</p>
</section>
<section>
<h2>Course Topics</h2>
<ul>
<li>Ordering optimization approaches</li>
<li>Demystifying a compiler</li>
<li>Mastering compiler optimizations</li>
<li><b>Modern computer architectures concepts</b></li>
</ul>
</section>
<section>
<h2>Outline</h2>
<ul>
<li>Three aspects of the computer architecture</li>
<li>Latency vs Throughput architectures</li>
<li>Architecture families
<ul>
<li>CISC</li>
<li>RISC</li>
<li>VLIW</li>
<li>Vector</li>
</ul>
</li>
<li>Why is it doing to be load/store?</li>
<li>Latest trends</li>
<li>summary</li>
</ul>
</section>
<section>
<section>
<h2>1-st Aspect of Computer Architecture</h2>
<blockquote><b>Instruction Set Architecture or ISA (interface)</b><br>
is a <strong>contract</strong> between HW and SW,<br> which specifies <strong>right</strong>,
<strong>possibilities</strong> & <strong>limitations</strong>.</blockquote>
<ul>
<li>Class of ISA (load-store, register-memory)</li>
<li>Memory addressing modes & rules (base-immediate, alignment requirements)</li>
<li>Types & sizes of operands (size of byte, short)</li>
<li>Operations (general arithmetic, control, logical)</li>
<li>Control flow instructions (branches, jumps, calls, returns)</li>
<li>Encoding an ISA (fixed or variable length)</li>
<li><i>All the conceptual aspects of the architecture</i></li>
</ul>
</section>
<section>
<h2>2-nd Aspect of Computer Architecture</h2>
<blockquote><b>Microarchitecture (organization)</b>
is a concrete implementation of the ISA, the high-level aspects of a processor design (memory system,
memory interconnect, design of the processor internals).</blockquote>
<ul>
<li>Pipeline width</li>
<li>Instruction latencies</li>
<li>Issue wight and scheduling</li>
<li>Speculation capabilities</li>
<li><i>All the concrete aspects of the architecture</i></li>
</ul>
</section>
<section>
<h2>3-nd Aspect of Computer Architecture</h2>
<blockquote><b>Hardware or chip (design)</b>
is the specifics of a computer, including the logic design and packaging. This is a concrete
implementation of the microarchitecture.</blockquote>
<ul>
<li>Tech-process</li>
<li>Clock rates</li>
<li>On die placement</li>
<li><i>All the properties of the chip</i></li>
</ul>
</section>
</section>
<section>
<section>
<h2>Architecture: Armv8-a</h2>
<table>
<colgroup>
<col style="width: 25%"/>
<col/>
<col/>
</colgroup>
<thead>
<tr>
<th>μarch</th>
<th>IP</th>
<th>Hardware</th>
</tr>
</thead>
<tbody>
<tr>
<td>Cortex-A53</td>
<td>ARM</td>
<td>Octa Exynos 7(7580) 1.6GHz 28nm<abbr title="High-k Metal Gate">HKMG</abbr></td>
</tr>
<tr>
<td width="17%">Cortex-A57</td>
<td>ARM</td>
<td>Octa Exynos 7(7420) <small style="vertical-align:bottom; ">big.LITTLE</small>
2.1/1.5 14<abbr title="Fin-Shaped Field Effect Transistor">FF</abbr> (
<abbr title="Low power Early">LPE</abbr>) (Samsung)</td>
</tr>
<tr>
<td>Cortex-A72</td>
<td>ARM</td>
<td>Deca MediaTek Helio X20 <small style="vertical-align:bottom; ">big.LITTLE</small> 2.5/2.0/1.4
20nm<abbr title="High-k Metal Gate">HKMG</abbr> (TSMC) </td>
</tr>
<tr>
<td>Cortex-A35</td>
<td>ARM</td>
<td>-</td>
</tr>
</tbody>
</table>
</section>
<section>
<h2>Architecture: Armv8-a</h2>
<table>
<colgroup>
<col style="width: 25%"/>
<col/>
<col/>
</colgroup>
<thead>
<tr>
<th>μarch</th>
<th>IP</th>
<th>Hardware</th>
</tr>
</thead>
<tbody>
<tr>
<td>Denver</td>
<td>NVIDIA</td>
<td>Dual Tegra K1 2.3GHz 28nm<abbr title="High Performance Mobile">HPM</abbr></td>
</tr>
<tr>
<td>Kryo</td>
<td>Qualcomm</td>
<td>Tetra S820 <small style="vertical-align:bottom; ">big.LITTLE</small>
2.2/1.6GHz 14<abbr title="Fin-Shaped Field Effect Transistor">FF</abbr> (
<abbr title="Low Power Plus">LPP</abbr>) (Samsung)</td>
</tr>
<tr>
<td>Exynos M1</td>
<td>Samsung</td>
<td>Quad Exynos 8890 <small style="vertical-align:bottom; ">big.LITTLE</small> 2.6/2.29GHz
14<abbr title="Fin-Shaped Field Effect Transistor">FF</abbr> (
<abbr title="Low Power Plus">LPP</abbr>) (Samsung)</td>
</tr>
</tbody>
</table>
</section>
<section>
<h2>Architecture: Armv8-a</h2>
<table>
<colgroup>
<col style="width: 25%"/>
<col/>
<col/>
</colgroup>
<thead>
<tr>
<th>μarch</th>
<th>IP</th>
<th>Hardware</th>
</tr>
</thead>
<tbody>
<tr>
<td>Cyclone</td>
<td>Apple</td>
<td>Dual A7 (APL0698) 1.4GHz 28nm<abbr title="High-k Metal Gate">HKMG</abbr> (Samsung)</td>
</tr>
<tr>
<td>Typhoon</td>
<td>Apple</td>
<td>Dual A8 (APL1012) 1.3GHz 20nm<abbr title="High-k Metal Gate">HKMG</abbr> (TSMC)</td>
</tr>
<tr>
<td style="border-bottom: none;" rowspan="2">Twister</td>
<td style="border-bottom: none;" rowspan="2">Apple</td>
<td>Dual A9 (APL0898) 1.85GHz 16nm<abbr title="Fin-Shaped Field Effect Transistor">FF+</abbr> (TSMC)</td>
</tr>
<tr >
<td>Dual A9 (APL1022) 1.85GHz 14nm<abbr title="Fin-Shaped Field Effect Transistor">FF</abbr>(
<abbr title="Low power Plus">LPP)</abbr> (Samsung)</td>
</tr>
</tbody>
</table>
</section>
</section>
<section>
<section>
<h2>Latency <small style="vertical-align: middle;">vs</small> Throughput architectures</h2>
<dl>
<dt><b>Latency</b> oriented architecture</dt>
<dd>
<ul>
<li><b>addresses latency hiding issues;</b></li>
<li>features sophisticated pipelining;</li>
<li>out-of-order;</li>
<li>employs advanced cache hierarchies;</li>
<li>widely uses speculation.</li>
<li><b>Compute cores occupy only a small part of a die.</b></li>
</ul>
</dd>
</dl>
</section>
<section>
<h2>Latency <small style="vertical-align: bottom;">vs</small> Throughput architectures</h2>
<dl>
<dt><b>Throughput</b> oriented architecture</dt>
<dd>
<ul>
<li><b>performs a bunch of operations in fly;</b></li>
<li>features many simple compute units/cores;</li>
<li>employs simple pipelines and large register file to provide a low-cost thread scheduling;</li>
<li>uses wide basses, tiling, programmable local memory.</li>
<li><b>Compute cores occupy most part of a die.</b></li>
</ul>
</dd>
</dl>
</section>
</section>
<!-- <section>add DIE shot for Maxwell and some Intel to compare building blocks</section> -->
<section>
<h2>Key architecture families</h2>
<dl>
<dt><strong>RISC</strong></dt>
<dd>Reduced Instruction Set Computer</dd>
<dt><strong>CISC</strong></dt>
<dd>Complex Instruction Set Computer</dd>
<dt><strong>VLIW</strong></dt>
<dd>Very Long Instruction Word</dd>
<dt><strong>Vector</strong> architecture</dt>
</dl>
</section>
<section>
<section>
<h2>CISC</h2>
<b>Complex Instruction Set Computer</b>
<ul>
<li><b>Designed in the 1970s</b> which was a time where <strong>transistors were expensive</strong> while
<strong>compilers were naive</strong>. Additionally, <strong>instruction packaging was the main concern
</strong> due to shortage of memory. <strong>The latency of the memory was just a bit higher then
registers.</strong></li>
<li><b>The goal</b> was to define an instruction set that allows high level language constructs
be translated into <strong>as few assembly language instructions as possible</strong>,
improving performance as well as code density.</li>
<li><b>Examples</b> are VAX, x86, <b>AMD64</b>.</li>
<li><b>Latency-oriented architecture</b>.</li>
</ul>
</section>
<section>
<h2>CISC</h2>
<ul>
<li><b>Heritage</b>
<ul>
<li><i>instructions access memory, a plenty of addressing modes</i>,</li>
<li>many instruction families and a <i>very rich variable length ISA</i> (alignment counts!),</li>
<li>consequently, <i><strong>complicated instruction decoding</strong></i> logic.</li>
<li>Moreover, a <i>few registers are available</i> for programmers.</li>
</ul>
</li>
<li><b>Nowadays</b>
<ol>
<li>Instructions are broken down into μcode which are much easy to pipeline and process power efficiently.</li>
<li>Transistors are spent to cache hierarchies, out-of-order execution, large <abbr title="reorder buffers">RB</abbr> and
speculation to eliminate stalls.</li>
<li>Symmetric multi-processing.</li>
</ol>
</li>
</ul>
</section>
</section>
<section>
<section>
<h2>RISC</h2>
<b>Reduced Instruction Set Computer</b>
<ul>
<li><b>Designed in the 1980s</b> which was a time there <abbr title="Instruction Level Parallelism">IPL</abbr>
was the great concern. The memory-processor gap already began to come out.</li>
<li><b>The goal</b> was to decrease the number of clocks per instruction (CPI) while pipeline instructions
as much as possible employing hardware to help with it. Uniform ISA, pipelining and large register file
is a must-have.</li>
<li><b>Examples</b> are <b>MIPS</b>, <b>ARM</b>, <b>PowerPC</b>.</li>
<li><b>Latency-oriented architecture</b>.</li>
</ul>
</section>
<section>
<h2>RISC</h2>
<ul>
<li><b>Heritage</b>
<ul>
<li>Relatively few instructions, all are the same length.</li>
<li>Only load and store instructions access memory.</li>
<li>Large resister file than typical CISC processors have.</li>
<li>No μcode</li>
</ul>
</li>
<li><b>Nowadays</b>
Most architectures that comes from RISC are called <b>Load-Store architectures</b>, while may employ
μops. They combine concepts of a classic RISC with usage of modern hardware enhancements:<br/>
<ol>
<li>deep pipelines, multi-cycle instructions,</li>
<li>out-of-order execution,</li>
<li>speculation.</li>
</ol>
</li>
</ul>
</section>
</section>
<section>
<h2>The Hardware/Software gap</h2>
<ul>
<li>Compiler
<ul>
<li>analyzes control flow, analyzes dependency</li>
<li>schedules instructions</li>
<li>maps variables to limited register set</li>
</ul><br>
</li>
<li>Hardware
<ul>
<li>analyzes control flow, analyzes dependency</li>
<li>schedules instructions</li>
<li>remaps ISA register to large internal register set</li>
</ul>
</li>
</ul>
</section>
<section>
<h2>A word towards registers</h2>
<blockquote>In deed, <b>registers</b> are temporary storage locations inside the processor that hold data and
addresses.</blockquote>
<ul>
<li>Local variables are not the same as registers in ISA, since compiler uses
<abbr title="Intermediate representation">IR</abbr> internally and does
register allocation close to the end of optimization process.</li>
<li>Registers provided by ISA is not the same as actual registers on the processor. Internal reorder buffers
which hold decoded instruction parameters and intermediate results are
closer to classic definition of a register file.</li>
</ul>
</section>
<section>
<section>
<h2>VLIW</h2>
<b>Very Long Instruction Word</b>
<ul>
<li><b>Designed in the 1980s</b> which was a time there <abbr title="Instruction Level Parallelism">IPL</abbr>
was the great concern.</li>
<li><b>The goal</b> was to pipeline instructions as much as possible employing software to help with it
reducing complexity of the hardware and mitigate the the Hardware/Software gap. Boost processor clock
simplifying work per cycle.</li>
<li><b>Example</b> is IntelHP Itanium.</li>
<li><b>Throughput-oriented architecture</b></li>
</ul>
</section>
<section>
<h2>VLIW</h2>
<ul>
<li><b>Heritage</b>
<ul>
<li>Compiler determines which instructions can be performed in parallel,</li>
<li>bundles this information and the instructions,</li>
<li>and passes the <b>bundle</b>(word) to the hardware.</li>
<li>No data dependencies between instructions in a word.</li>
<li>Each operation in a word assigned to specific issue slot (dedicated FU).</li>
</ul>
</li>
</ul>
</section>
<section>
<h2>VLIW</h2>
<ul>
<li><b>Nowadays</b>
<ul>
<li>hardly any generic processor implements VLIW
<ul>
<li>brunchy nature of <abbr title="Usually referenced as integer benchmarks">production codes</abbr>
(in contrast to HPC or scientific codes),</li>
<li>need to follow binary compatibility across the μarchitecture families.</li>
</ul></li>
<li>Whereas architecture is widely adopted for programmable co-processors where shrink in power consumption
without lose of performance is crucial (DSP, GPU).</li>
</ul>
</ul>
</section>
</section>
<section>
<section>
<h2>Vector Processors</h2>
<ul>
<li><b>First introduced in 1976</b> and dominated for HPC in the 1980s because of high instruction
throughput.</li>
<li><b>The goal</b> was to perform operations on vectors of data exposing data level parallelism (DLP)
to increase instruction throughput. Vector pipelining is also called chaining.</li>
<li><b>Example</b> is Cray</li>
<li><b>Throughput-oriented architectures.</b></li>
</ul>
</section>
<section>
<h2>Vector Processors</h2>
<ul>
<li><b>Heritage</b>
<ul>
<li>Process the data in vectors, each element in a vector (lane) is independent on any other.</li>
<li>Deep pipelines, wide execution units, not necessary the same width (batch length) as size
of vector in elements (vector length).</li>
<li>Most efficient for simple memory patterns, but getter/scatter is usually possible too.</li>
<li>Wide memory interfaces to saturate execution units.</li>
<li>Large vector register file, cache is not a strict requirement and absent for classical vector
processors.</li>
</ul>
</li>
<br>
</ul>
</section>
<section>
<h2>Vector Processors</h2>
<ul>
<li><b>Nowadays</b>
<ul>
<li>They aren't used in generic processors design, but used as a co-processors for
a specific workloads: HPC, multimedia.</li>
<li>Precursors of most designs of modern GPUs.</li>
<li>Vector pipes with short vector length (8-16 bytes) called SIMD units are widely integrated
in modern general purpose processors to accelerate most demanding loops.</li>
</ul>
</ul>
</section>
</section>
<section>
<section>
<h2>Why is it doing to be <strike>RISC</strike> Load/Store?</h2>
<ol>
<li><b>Simple fixed-width instructions & few addressing modes</b>
<ul>
<li>Cache-efficient instruction fetch, branches are aligned.</li>
<li>Simple hardware logic → power efficient chips.</li>
<li>Drive a higher clock rate.</li>
</ul>
</li>
<li><b>Concise ISA with orthogonal functionality</b>
<ul>
<li>Complex instructions are ignored by compilers due to semantic gap →
simple instructions simplify scheduling.</li>
<li>Complex addressing lead either to variable length instructions or big instruction size
→ inefficient decoding and scheduling as well as alignment issues.</li>
</ul>
</li>
<li><b>Large register set</b>
<ul>
<li>Expose possible instruction parallelism to the compiler.</li>
</ul>
</li>
</ol>
</section>
</section>
<section>
<h2>Latest trends</h2>
<ul>
<li>Architecture is seen as Load-store RISC-inherited</li>
<li>Internally instructions are broken down into single-pipe μops</li>
<li>μops are reordered and optionally organized into words</li>
<li>μops or words are scheduled for execution, caching in the highest level is usually performed on this
preprocessed view.</li>
<li>Latest generations of Intel processors, NVIDIA Denver architecture and 64-bit ARM Cortex-A processors
already employ this approach.</li>
</ul>
</section>
<section>
<section>
<h2>Summary</h2>
<ul style="width: 100%">
<li>There are three key aspects of computer architecture: Instruction Set Architecture,
μarchitecture and design.</li>
<li>Some architectures aim to hide latency while others aim to maximize instruction throughput.</li>
<li>CISC is created for compact code size and exact instruction encoding and used only on ISA level
nowadays.</li>
<li>RISC leads to less complicated decoding and pipeline stages allow boosting clock in affordable
power budget.</li>
<li>VLIW targets power efficient high performance devices for specific tasks or used internally on
μarchitecture level.</li>
<li>Vector processors transformed into SIMD-extensions and SIMT-like GPU designs.</li>
</ul>
</section>
<section>
<h2>Summary</h2>
<ul style="width: 100%">
<li>Loads-Store architectres with its simple fixed-width instructions, few addressing modes,
concise ISA<br> and optimal size register size is a winner solution.</li>
<li><strong>Architecture can expose different properties<br> for it's different levels
(ISA, μarchitecture).</strong></li>
</ul>
</section>
</section>
<section>
<h1>THE END</h1>
<img alt="The end" class="simple" src="images/popt/infinity.png">
<h4><a href="https://github.com/cuda-geek">Marina Kolpakova</a> / 2015-2016</h4>
</section>
</div>
</div>
<script src="lib/js/head.min.js"></script>
<script src="js/reveal.js"></script>
<script>
// Full list of configuration options available at:
// https://github.com/hakimel/reveal.js#configuration
Reveal.initialize({
controls: true,
progress: true,
history: true,
center: false,
slideNumber: true,
transition: 'slide', // none/fade/slide/convex/concave/zoom
// Optional reveal.js plugins
dependencies: [
{ src: 'lib/js/classList.js', condition: function() { return !document.body.classList; } },
{ src: 'plugin/markdown/marked.js', condition: function() { return !!document.querySelector( '[data-markdown]' ); } },
{ src: 'plugin/markdown/markdown.js', condition: function() { return !!document.querySelector( '[data-markdown]' ); } },
{ src: 'plugin/highlight/highlight.js', async: true, callback: function() { hljs.initHighlightingOnLoad(); } },
{ src: 'plugin/zoom-js/zoom.js' , async: true },
{ src: 'plugin/notes/notes.js', async: true }
]
});
</script>
</body>
</html>