這一小節(jié)沒有中文字幕饲趋，可以去youtube上看原版視頻，開啟實(shí)時(shí)中文字幕功能，youtube視頻鏈接Parallel Computer Architecture and Programming Spring 2018 P2 Lec 2 Modern - YouTube

今天的主題是從硬件角度討論并行計(jì)算,
你會(huì)發(fā)現(xiàn)硬件設(shè)計(jì)者在硬件層次結(jié)構(gòu)的多個(gè)不同的層次提供了并行計(jì)算的潛力殖熟，其中一些對(duì)程序員不可見，由硬件自己控制八千。而有一些是需要程序員或者編譯器顯式生成適當(dāng)?shù)拇a才能利用起來的吗讶，因此你必須對(duì)硬件有著足夠多的理解才能使硬件發(fā)揮最大的性能。

我們會(huì)介紹4個(gè)關(guān)鍵概念恋捆，其中兩個(gè)與并行執(zhí)行(parallel execution)有關(guān)照皆，兩個(gè)與訪問內(nèi)存的挑戰(zhàn)性(challenges of accessing memory)有關(guān)。
首先介紹并行執(zhí)行沸停。

1 parallel execution

1.1 pre multi-core era

在多核時(shí)代前膜毁，CPU執(zhí)行技術(shù)經(jīng)過了以下幾個(gè)階段的發(fā)展(此部分課中沒有涉及，但不了解的話在看lecture 2的時(shí)候容易迷惑愤钾，文字和圖都參考自文章什么是Speculative Execution瘟滨？為什么要有它？ - 知乎)：
386時(shí)代：指令是順序執(zhí)行的（假設(shè)一指令占一個(gè)時(shí)鐘周期）,如下圖

image.png

可以看到每個(gè)時(shí)鐘周期只能執(zhí)行一條指令

在486后能颁，引入了Pipeline(流水線)技術(shù)杂瘸，該技術(shù)將指令分為多個(gè)階段，每個(gè)時(shí)鐘周期允許多個(gè)指令執(zhí)行不同的階段伙菊，如下圖中將指令的執(zhí)行分為fetch败玉，decode敌土，execute和write四個(gè)階段。

image.png

此時(shí)的指令還是順序執(zhí)行(in order execution)的运翼，但圖中可以看到有很多wait的階段返干，導(dǎo)致這種現(xiàn)象的原因之一是指令間存在數(shù)據(jù)依賴，例如instr2需要instr1的結(jié)果血淌，因此在instr1執(zhí)行完成前矩欠，instr2還是要等待;還有的情況就是代碼中有if分支語句，此時(shí)也不能提前執(zhí)行后面的語句悠夯。

在奔騰II后癌淮，為了緩解該現(xiàn)象，Intel在CPU中引入了亂序執(zhí)行（out-of-order execution沦补，OOOE）,亂序執(zhí)行是指指令的執(zhí)行順序和指令在內(nèi)存中的數(shù)據(jù)不一致该默，如下圖中所示：

image.png

可以看到instr3會(huì)在instr2執(zhí)行之前執(zhí)行。
但亂序執(zhí)行還沒有解決由于條件分支而等待的問題策彤，這里就引出了分支預(yù)測技術(shù)和預(yù)測執(zhí)行(speculative execution)技術(shù)。
分支預(yù)測技術(shù)會(huì)根據(jù)某些信息（如前幾次的跳轉(zhuǎn)情況）判斷條件分支的跳轉(zhuǎn)情況匣摘，然后使用預(yù)測執(zhí)行技術(shù)提前執(zhí)行對(duì)應(yīng)部分的指令店诗。

90年代的奔騰4， 通過超標(biāo)量實(shí)現(xiàn)指令級(jí)并行音榜，當(dāng)時(shí)的cpu使用了亂序執(zhí)行技術(shù)庞瘸。他們?cè)谛酒戏糯罅坑布钠胀ǖ某绦?視頻中稱為傳統(tǒng)程序）中提取各種并行的可能性赠叼。如下圖的橙紅色框中所示擦囊，奔騰4有多個(gè)指令decoder，可以從指令流中取一堆指令并decode嘴办，并將指令映射到一種新的瞬场，叫data flow的計(jì)算方式，然后CPU會(huì)追蹤有哪些值生成了涧郊，并把這些值填充到即將到來的指令中來解決數(shù)據(jù)的依賴問題贯被。最后通過許多復(fù)雜的硬件和控制將這些指令映射到一堆獨(dú)立的功能單元上并行執(zhí)行（這段話看不懂沒事，我也沒懂妆艘，視頻中老爺子也只是隨口一提彤灶，沒指望學(xué)生能懂 #疑惑）,如橙色框中所示。橙色框中有一個(gè)內(nèi)存接口單元用于存取內(nèi)存數(shù)據(jù)批旺，2個(gè)整數(shù)運(yùn)算單元幌陕，一個(gè)浮點(diǎn)數(shù)運(yùn)算單元和一個(gè)SIMD（single instruction multi data）單元, SIMD單元可以同時(shí)執(zhí)行多個(gè)浮點(diǎn)，整數(shù)運(yùn)算（之后會(huì)介紹）汽煮。
通過上面的技術(shù)搏熄，即使一個(gè)純順序執(zhí)行的程序棚唆，也可以具有一定的并行能力。當(dāng)然如果你寫的代碼比較友好或者你的編譯器很聰明搬卒，CPU也會(huì)更容易執(zhí)行指令級(jí)并行瑟俭。

image.png

上圖的黑色框部分是一些控制邏輯，會(huì)預(yù)測if分支的執(zhí)行并在預(yù)測出錯(cuò)的時(shí)候撤銷已經(jīng)執(zhí)行的契邀，受影響的指令(分支預(yù)測技術(shù))摆寄，如上方黑色框中的branch target buffer，他保存了控制指令歷史的跳轉(zhuǎn)結(jié)果信息坯门，并利用該歷史信息預(yù)測他們將來再次會(huì)跳轉(zhuǎn)到哪微饥。下方的黑色框會(huì)保存所有通過預(yù)測而執(zhí)行的指令（這些提前執(zhí)行的指令還不確定是否真的會(huì)執(zhí)行），并在預(yù)測成功后把確定執(zhí)行的指令移除古戴。

然而欠橘，前幾年的英特爾幽靈漏洞就利用了分支預(yù)測技術(shù)，原理是分支預(yù)測技術(shù)在提前執(zhí)行跳轉(zhuǎn)后的指令時(shí)现恼，不會(huì)對(duì)指令讀取的內(nèi)存的權(quán)限進(jìn)行檢查肃续。然后，讀取的內(nèi)存又會(huì)在cache中緩存叉袍，因此通過判斷哪個(gè)內(nèi)存的訪問時(shí)間快就可以知道之前內(nèi)存中的數(shù)據(jù)是多少了始锚，這種方法可以獲取任意內(nèi)存位置上的數(shù)據(jù)。具體可看本文最后的擴(kuò)展部分喳逛。

需要區(qū)分一下流水線和超標(biāo)量的區(qū)別瞧捌，咋看它們好像都可以在一個(gè)時(shí)鐘周期里運(yùn)行多條指令，但流水線技術(shù)在一個(gè)時(shí)鐘周期內(nèi)润文，處于某個(gè)階段的指令只能有一條姐呐，因?yàn)閷?duì)應(yīng)的硬件只有一套。而超標(biāo)量處理器中典蝌，相同功能的硬件有多套曙砂，因此一個(gè)時(shí)鐘周期內(nèi)可運(yùn)行多個(gè)處于同一階段的指令。

在前多核時(shí)代赠法，為了算的更快麦轰，使用了許多的晶體管，來增加cache容量砖织、設(shè)計(jì)更聰明的亂序執(zhí)行邏輯以及更聰明的分支預(yù)測款侵，當(dāng)然還有更高的時(shí)鐘頻率。然而侧纯，就像lecture 1所說新锈，他們不能無限制的通過手段這些增加性能，功耗太大了眶熬。

下面介紹多核時(shí)代妹笆。

1.2 multi-core era

在多核時(shí)代块请，人們的第一個(gè)想法是將不斷增加的晶體管數(shù)量用于在處理器上添加多個(gè)核，形成多核處理器拳缠，而不是執(zhí)著于通過加速單一指令流的執(zhí)行來增加單個(gè)核性能（通過亂序技術(shù)墩新，以及預(yù)測執(zhí)行（speculative operations）等技術(shù)）。

多核的每個(gè)核比之前的單核要弱(多個(gè)原因窟坐，如降低芯片設(shè)計(jì)復(fù)雜程度海渊，減少功耗)，但因?yàn)槭嵌鄠€(gè)核哲鸳，協(xié)作起來的話計(jì)算反而更快臣疑。

為什么多核可以降低功耗？這是因?yàn)楣牡暮艽笠徊糠质菍⑿盘?hào)從一個(gè)地方傳到另一個(gè)地方徙菠。在單核情況下讯沈，芯片面積大，通信功耗高婿奔。在多核情況下缺狠，核比較小，傳遞消耗比較小萍摊，這是功耗上的優(yōu)勢(shì)儒老。并且，核小的話记餐，信號(hào)從一段傳遞到另一端也更快，這是時(shí)間上的優(yōu)勢(shì)薇正。

在多核時(shí)代片酝，人們的第二個(gè)想法是增加多個(gè)ALU，這就是產(chǎn)生了SIMD挖腰，也就是單指令多數(shù)據(jù)雕沿。SIMD指令會(huì)將數(shù)據(jù)發(fā)送到多個(gè)ALU，并在多個(gè)ALU上同時(shí)計(jì)算猴仑。

如intel發(fā)布的avx和avx2指令集(advanced vector extensions审轮，高級(jí)向量擴(kuò)展)，可以同時(shí)對(duì)256位辽俗，即32字節(jié)的數(shù)據(jù)進(jìn)行操作,如下面代碼：

_m256 origx =_mm256_load_ps(&x[i]);//一次從x[i]處讀取256位疾渣，32字節(jié)；ps是pass single崖飘，意思是傳入的是單精度浮點(diǎn)數(shù)float; pd是double
m256 value origx;
m256 numer =_mm256_mul_ps(origx,_mm256_mul_ps(origx,origx));//分別計(jì)算8個(gè)單精度浮點(diǎn)數(shù)的立方
m256 denom =_mm256_broadcast_ss(&three_fact);

生成的匯編如下：

vloadps xmm0, addr[r1] 
vmulps xmm1, xmm0, xmm0 
vmulps xmm1, xmm1, xmm0

具有SIMD指令的CPU核的結(jié)構(gòu)如下圖榴捡，可以看到有多個(gè)ALU。

image.png

有SIMD功能的cpu中有專門的256位寄存器朱浴，用于向量指令吊圾。也有一些常規(guī)指令也會(huì)使用該寄存器达椰，但只會(huì)使用低位的4或8個(gè)字節(jié)。
編譯器某些特殊情況下也會(huì)生成利用AVX的指令项乒，但如果專門為了編譯器能夠生成這些指令去寫相應(yīng)的代碼的話啰劲，你需要加許多額外的提示啥的，有點(diǎn)吃力不討好檀何，還不如自己手動(dòng)去使用這些指令蝇裤。

如果遇到if語句，那SIMD是可以同時(shí)執(zhí)行true條件和false條件時(shí)的指令埃碱，就像它們是順序代碼一樣猖辫。在條件表達(dá)式執(zhí)行后，通過mask選擇最終保留的結(jié)果砚殿。如下圖中啃憎，true時(shí)會(huì)執(zhí)行黃色指令，fasle會(huì)執(zhí)行藍(lán)色指令似炎，SIMD會(huì)將黃色指令和藍(lán)色指令都執(zhí)行辛萍，并且通過一個(gè)mask區(qū)分哪些指令是true時(shí)該執(zhí)行的，哪些是fasle時(shí)該執(zhí)行的羡藐。

image.png

這種同時(shí)執(zhí)行的方法也是gpu的重要方法贩毕。

然后課里提到了指令流的一致性執(zhí)行（instruction stream coherence， coherence execution）和發(fā)散執(zhí)行（divergent execution）仆嗦。
其中一致性執(zhí)行有3個(gè)特點(diǎn)辉阶，分別是：相同的指令序列可以應(yīng)用到所有元素；一致性執(zhí)行對(duì)于SIMD是重要的瘩扼；一致性執(zhí)行對(duì)于多核之間的并行執(zhí)行沒啥用谆甜，因?yàn)槊總€(gè)核可以hold住一個(gè)不同類型的指令流。
而發(fā)散執(zhí)行則是指缺乏一致性的指令流集绰。
這是對(duì)SIMD的應(yīng)用場景做了介紹规辱，SIMD在具有一致性的指令流中很有效，而一致性可以理解為多個(gè)數(shù)據(jù)具有相同的處理模式栽燕，那么SIMD就可以同時(shí)對(duì)這些數(shù)據(jù)進(jìn)行處理罕袋。

現(xiàn)在的CPU上有多種不同的SIMD指令，如128位的SSE碍岔，256位的AVX浴讯，512位的AVX512.
當(dāng)發(fā)生以下條件時(shí)，編譯器可以生成SIMD指令：

1. 程序員顯式使用了SIMD相關(guān)的語句
2. 程序中需要并行的部分使用了并行語言語義（例如forall蔼啦，這個(gè)不是很懂兰珍，后面的課中會(huì)講到，到時(shí)候回來補(bǔ) #疑惑）
3. 編譯器聰明地分析出了并行性（比較困難）询吴。

這里有個(gè)術(shù)語為顯式SIMD掠河，是指當(dāng)你不確定編譯器是否生成了SIMD代碼時(shí)亮元，可以查看匯編中有無相關(guān)指令，如vstoreps,vmulps等唠摹。

與之相對(duì)的是隱式SIMD, 如在GPU中爆捞，是硬件而不是編譯器負(fù)責(zé)在SIMD ALU上同時(shí)執(zhí)行并行計(jì)算。
課中提到了GPU是SPMD（single program multi data),即程序的不同部分可以做不同的事勾拉。（這里沒完全搞清楚煮甥，老爺子沒說的很明白。我直接把該頁ppt放下面藕赞，之后再來瞧瞧 #疑惑）(SPMD在lecture 3中會(huì)再次介紹成肘，看本節(jié)的時(shí)候不理解這個(gè)也沒影響。)

image.png

1.3 summay

總結(jié)一下斧蜕，在本節(jié)parallel execution中双霍，提到了3種現(xiàn)代處理器的并行策略，分別是：

1. 多核：在芯片上放多個(gè)核
   1. 提供了線程級(jí)的并行
   2. 由軟件(程序員)決定何時(shí)并行（使用pthreads API）
2. SIMD：在一個(gè)核中放多個(gè)ALUs批销，
   1. 高效的數(shù)據(jù)并行設(shè)計(jì)
   2. 由編譯器顯式生成SIMD或者由硬件自動(dòng)執(zhí)行
   3. 前提是執(zhí)行具有一致性（由程序員聲明或牛逼的編譯器自己發(fā)現(xiàn)）
3. 超標(biāo)量：探索指令級(jí)并行(ILP), 來自同一指令流的指令在一個(gè)核上并行運(yùn)行
   1. 由硬件自動(dòng)挖掘指令并行的可能性（程序員不可見）
   2. 對(duì)這個(gè)感興趣可以看課程CMU18447

2 accessing memory

接下來介紹內(nèi)存訪問相關(guān)的內(nèi)容洒闸。
雖然CPU的性能提升遇到了瓶頸掀宋，但相對(duì)于內(nèi)存存取速度的提升而言是趴，還是進(jìn)步比較大的肛搬。

關(guān)于內(nèi)存存取有兩個(gè)術(shù)語：

1. 內(nèi)存延遲：指內(nèi)存系統(tǒng)響應(yīng)處理器一個(gè)內(nèi)存請(qǐng)求（如load陶贼，store）的時(shí)間枉氮，如100 cycles惹悄，100nsec（1nsec=1e-9 sec）
2. 內(nèi)存帶寬：內(nèi)存系統(tǒng)提供數(shù)據(jù)給處理器的帶寬央星，如20GB/sec

首先介紹內(nèi)存延遲

2.1 memory latency

當(dāng)處理器不能執(zhí)行下一條指令（因?yàn)樵撝噶钜蕾嚽懊嬷噶畹臄?shù)據(jù)并且前面指令沒有執(zhí)行完畢）時(shí)，會(huì)暫停（stall）。
如下面的匯編：

ld r0 mem[r2]
ld r1 mem[r3]
add r0, r0, r1//依賴前面的指令的結(jié)果

而一次內(nèi)存存取延遲（memory access latency）為100個(gè)左右的時(shí)鐘周期黍判，拖累了CPU的運(yùn)行速度。

為了減少內(nèi)存存取的延遲吊说，方法一是在CPU和內(nèi)存間引入了cache機(jī)制以減少延遲(reduce latency)：

image.png

L1 cache的存取延遲為3-4時(shí)鐘周期，L2為10-12颁井，L3為30-70, 都比內(nèi)存的存取延遲小很多厅贪。

減少內(nèi)存存取延遲的方法二是預(yù)取技術(shù)(prefetching)以隱藏延遲(hides latency)。
所有的現(xiàn)代處理器都有將數(shù)據(jù)預(yù)先取到cache的邏輯雅宾，他們通過分析程序訪問內(nèi)存的模式來預(yù)測哪些數(shù)據(jù)將會(huì)被訪問养涮。(看過CSAPP的同學(xué)可能對(duì)此有印象，在講到存儲(chǔ)器山的時(shí)候提到眉抬，當(dāng)存取步長為1時(shí)贯吓，即使工作集大小超過了L1和L2的大小，讀吞吐量也相對(duì)保持不變蜀变，這是有因?yàn)轭A(yù)取技術(shù)悄谐。具體在CSAPP的p446)
然而，事物都有兩面性库北，當(dāng)預(yù)取技術(shù)預(yù)測失敗時(shí)爬舰，會(huì)降低性能（占用了內(nèi)存帶寬，并可能覆蓋了cache中其他有用的數(shù)據(jù)）

減少內(nèi)存存取延遲的方法三是多線程以隱藏延遲(文中具體指超線程技術(shù)寒瓦，在后文中也叫硬件多線程)情屹。其中，cache機(jī)制是減少延遲的技術(shù)杂腰，而超線程和預(yù)取是隱藏延遲的技術(shù)（沒有減少延遲）垃你。
超線程技術(shù)在一個(gè)線程等待內(nèi)存存取的時(shí)候，當(dāng)前核可以切換到另一個(gè)線程繼續(xù)運(yùn)行(交錯(cuò)執(zhí)行線程)喂很。
為了實(shí)現(xiàn)這個(gè)目的惜颇，一個(gè)core中必須有多個(gè)線程的執(zhí)行上下文（execution context）：

image.png

上圖中的左圖只有一套執(zhí)行上下文（Execution context）(下面的藍(lán)色塊)，因此只能保存一個(gè)線程的信息恤筛。
上圖的右圖有4套執(zhí)行上下文，因此可以同時(shí)保存4個(gè)線程的信息芹橡。
一個(gè)執(zhí)行上下文包含了一套寄存器等硬件毒坛，因此可以超線程的core中會(huì)有多套寄存器。而超線程中ALUs，cache等是多個(gè)線程共享的煎殷，只是寄存器單獨(dú)一套屯伞。

超線程技術(shù)是面向吞吐量的系統(tǒng)，這就意味著它會(huì)通過增加單個(gè)線程的運(yùn)行時(shí)間來減少整體（多個(gè)線程）的運(yùn)行時(shí)間豪直。
例如只有一個(gè)線程的運(yùn)行時(shí)間是5s劣摇，順序運(yùn)行4個(gè)線程的時(shí)間為20秒。而在超線程時(shí)弓乙，有4個(gè)一起運(yùn)行的相同線程末融，每個(gè)的運(yùn)行時(shí)間增加到6秒，但4個(gè)線程結(jié)束時(shí)間卻變成了15秒暇韧，少于20秒勾习。

通過增加單個(gè)處理的延遲來增加整體的吞吐量是一個(gè)很常用的想法，如網(wǎng)絡(luò)中的多路復(fù)用懈玻。
高吞吐量比低延遲更容易實(shí)現(xiàn)巧婶。
另一種超線程的實(shí)現(xiàn)是使用L1 cache作為執(zhí)行上下文，存儲(chǔ)多個(gè)線程的狀態(tài)涂乌。
超線程很復(fù)雜艺栈，具體的要去計(jì)算機(jī)體系結(jié)構(gòu)課講。

下圖中的cpu有16個(gè)core湾盒，每個(gè)core中有8個(gè)ALU湿右，4個(gè)執(zhí)行上下文；因此總共有16個(gè)同時(shí)運(yùn)行的指令流（16個(gè)core）历涝，64個(gè)并發(fā)的指令流（16個(gè)core诅需，每個(gè)4個(gè)線程），需要512個(gè)獨(dú)立的工作塊才能使該CPU飽和（64個(gè)線程荧库，每個(gè)線程使用全部的8個(gè)ALU）着茸。

image.png

總結(jié)一下超線程：

1. 優(yōu)點(diǎn)： 一個(gè)core的ALU利用率上升
   1. 隱藏內(nèi)存延遲
   2. 可以充分填充具有超標(biāo)量的體系結(jié)構(gòu)中的功能單元（當(dāng)線程ILP比較少時(shí)）
2. 開銷：
   1. 要求額外的線程上下文的存儲(chǔ)
   2. 增加單個(gè)線程的運(yùn)行時(shí)間（不是什么大問題始衅，一般我們關(guān)注的是吞吐量）
   3. 這條沒懂： Requires additional independent work in a program (more independent work than ALUs!) #疑惑
   4. 嚴(yán)重依賴內(nèi)存帶寬
      1. 更多的線程->更多的工作集->每個(gè)線程的cache更少了
      2. 更加頻繁地訪問內(nèi)存（線程多了）
         前面說了超線程是一種硬件多線程，而在課件ppt的最后提到硬件多線程分為交叉(interleaved)多線程，同時(shí)(simultaneous)多線程锋谐，具體可看本博客第3節(jié)。

2.2 Bandwidth

下面簡單介紹GPU.
GPU是極度面向吞吐量的處理器,NVIDIA GTX 480有16個(gè)core棘利，每個(gè)core的結(jié)構(gòu)如下：

image.png

每個(gè)黃色框是一個(gè)SIMD功能單元持痰，
有兩組功能單元，每組16個(gè)SIMD功能單元邀桑。

在每一組功能單元中:

1. 一條指令一次可以操作32個(gè)數(shù)據(jù)（稱為“warps”）瞎疼，也就是說該線程發(fā)射（issue）了一條32寬的向量指令；
2. 可以交叉執(zhí)行48個(gè)warps壁畸，總共48*32=1500個(gè)元素
3. 為啥warp是32個(gè)數(shù)據(jù)贼急，而每一組功能單元只有16個(gè)SIMD功能單元那茅茂？因?yàn)锳LU的時(shí)鐘比芯片的其他部分快1倍，每一條指令在16個(gè)SIMD ALU上可以運(yùn)行2個(gè)ALU時(shí)鐘周期太抓，相當(dāng)于32個(gè)SIMD ALU空闲。不過從程序員角度看就是執(zhí)行了1次32寬度的操作。

GTX480 可以并發(fā)處理48 x 32 x 15 = 23000個(gè)數(shù)據(jù)(注意走敌，不是并行)
GTX480 可以并行處理32(ALUs) x 15(cores) =480個(gè)數(shù)據(jù)

下圖展示了CPU和GPU的內(nèi)存層次結(jié)構(gòu)：

image.png

其中CPU cache更大碴倾，線程更少，內(nèi)存存取速度一般（主要靠緩存和預(yù)取技術(shù)）掉丽。
而GPU cache小(給ALU騰空間)跌榔，線程多，內(nèi)存存取速度塊（主要依賴于多線程）

理論上机打，每個(gè)時(shí)鐘周期GTX480可以計(jì)算480個(gè)數(shù)據(jù)矫户，每個(gè)數(shù)據(jù)4字節(jié)。
假設(shè)我們要計(jì)算C=AxB残邀，那么有3次內(nèi)存存取操作皆辽，對(duì)于GTX 480的1.2GHZ頻率來說，每秒需要6.4TB的帶寬（480x4x3x1.2G）芥挣，然而GTX 480的內(nèi)存帶寬只有177GB驱闷，3%的效率，但依舊是當(dāng)時(shí)最快cpu的7倍（但該cpu的內(nèi)存帶寬只有25GB/sec空免，計(jì)算效率也只有3%）
因此對(duì)于吞吐量系統(tǒng)設(shè)計(jì)者而言空另，內(nèi)存帶寬是一個(gè)嚴(yán)重的挑戰(zhàn)。

不管是CPU還是GPU蹋砚，內(nèi)存帶寬比計(jì)算更加稀缺扼菠，因此作為一個(gè)程序員你可以采取一些奇妙的技巧來減少內(nèi)存訪問,如：

1. 組織代碼使得更少地從內(nèi)存中獲取數(shù)據(jù)。
   1. 復(fù)用該進(jìn)程之前讀取的數(shù)據(jù)（屬于傳統(tǒng)的線程內(nèi)局部性優(yōu)化坝咐。如計(jì)算數(shù)組累加時(shí)循榆，可以使用臨時(shí)變量）
   2. 在線程間共享數(shù)據(jù)（線程間合作）
2. 減少請(qǐng)求數(shù)據(jù)的次數(shù)（用計(jì)算代替）
   1. 術(shù)語:“算術(shù)密度”——指令流中算術(shù)操作與數(shù)據(jù)訪問操作的比率
   2. 算術(shù)密度越高，現(xiàn)代處理器的執(zhí)行更加高效墨坚。

2.3 summary

1. 現(xiàn)代處理器都使用了下面三個(gè)思想
   1. 多核
   2. SIMD
   3. 超線程
2. 現(xiàn)在芯片計(jì)算能力很強(qiáng)秧饮，因此需要并行程序的瓶頸在內(nèi)存帶寬
3. GPU架構(gòu)使用與cpu相同的吞吐量計(jì)算思想:但GPU將這些概念推向了極致

3 Review

老爺子可能知道講的太多了，還另外搞了一個(gè)復(fù)習(xí)泽篮，回顧了一下CPU的發(fā)展史盗尸。
首先是最簡單的單核CPU，超標(biāo)量單核CPU, 雙核CPU:

image.png

不過需要注意超標(biāo)量的圖示帽撑。圖示中有2個(gè)exec分別是exec1和exec2泼各，容易讓人認(rèn)為是核中有2套一模一樣的exec 單元，但實(shí)際上并不是亏拉，具體可以看看本文前面部分的奔騰4的硬件結(jié)構(gòu)扣蜻。這里的圖示只是一種抽象寸癌，從程序員的角度看確實(shí)是可以理解為有2套一樣的exec。

然后是超標(biāo)量雙核弱贼，四核，帶有SIMD的四核：

image.png

最后是帶有超線程磷蛹、SIMD的四核處理器吮旅，以及帶有超線程、超標(biāo)量以及SIMD的四核處理器味咳。

image.png

最后的最后庇勃，看一下帶有超線程、超標(biāo)量以及SIMD的四核處理器的簡單結(jié)構(gòu)圖：

image.png

總結(jié)一下本課提出的幾種技術(shù)：

1. 多核: 通過在CPU上放置多個(gè)核來達(dá)到多線程并行槽驶。
   1. 特征责嚷，多個(gè)指令流分布在多個(gè)核。
2. 超標(biāo)量: 通過在單個(gè)核上放置多個(gè)相同類型的硬件來達(dá)到指令級(jí)并行掂铐。
   1. 特點(diǎn)：每個(gè)核上一個(gè)指令流罕拂；在一個(gè)核上，每個(gè)時(shí)鐘周期可執(zhí)行多條指令
3. SIMD：在單個(gè)核上放置多個(gè)ALUs全陨，可以通過一條指令調(diào)用多個(gè)ALUs進(jìn)行并行計(jì)算爆班。
   1. 特點(diǎn)：每個(gè)核上一個(gè)指令流；每個(gè)時(shí)鐘周期執(zhí)行一條指令辱姨；一條指令調(diào)用多個(gè)ALU柿菩；
4. 超線程（硬件多線程）：在單個(gè)核上放置多個(gè)執(zhí)行上下文，使得單個(gè)核上可以同時(shí)存在多個(gè)線程雨涛。
   1. 同步多線程（Simultaneous multi-threading枢舶，SMT）：多個(gè)線程是并行的，需要處理器具有超標(biāo)量結(jié)構(gòu)替久，可實(shí)現(xiàn)在單個(gè)core上的多個(gè)線程的指令級(jí)并行凉泄。
      1. 特點(diǎn)：每個(gè)核上多個(gè)指令流；每個(gè)時(shí)鐘周期可執(zhí)行多個(gè)指令流的指令侣肄；
   2. 交叉多線程（Interleaved multi-threading旧困，IMT）：多個(gè)線程是并發(fā)的，交錯(cuò)執(zhí)行的稼锅，不需要處理器具有超標(biāo)量結(jié)構(gòu)吼具，
      1. 特點(diǎn)：每個(gè)核上多個(gè)指令流；每個(gè)時(shí)鐘周期僅執(zhí)行一個(gè)指令流的一條指令矩距；

課程的最后留了一個(gè)問題拗盒，我也不是很確定答案，大家可以在評(píng)論區(qū)討論一下：
你寫了一個(gè)具有2個(gè)線程的程序锥债，它運(yùn)行在一個(gè)帶有超線程的（每個(gè)核有兩個(gè)執(zhí)行上下文）陡蝇、SIMD的雙核處理器上
問題1：誰將你的線程放置到處理器上的痊臭？
答：之前寫多線程都沒關(guān)注過哪個(gè)線程放到哪個(gè)核上，那應(yīng)該是OS控制的登夫。
問題2：如果你是OS广匙，你現(xiàn)在有4個(gè)可用的核，那你將如何分配這兩個(gè)線程恼策？
答：有兩種方案鸦致，感覺各有有缺點(diǎn)。
方案一是放在兩個(gè)不同的核涣楷，優(yōu)點(diǎn)是單個(gè)運(yùn)行時(shí)間可能會(huì)短分唾，缺點(diǎn)是同一個(gè)程序的兩個(gè)線程應(yīng)該有很多數(shù)據(jù)會(huì)共用，放到兩個(gè)核的話狮斗，L1和L2就隔離了绽乔，cache的miss會(huì)變多。
方案二是放在同一個(gè)核碳褒，因?yàn)樗浅€程折砸，所以兩個(gè)線程可以并發(fā)執(zhí)行。優(yōu)點(diǎn)是L1和L2 可以共用沙峻，減少內(nèi)存延遲鞍爱，缺點(diǎn)是兩個(gè)線程的速度可能會(huì)變慢。
我也不知道選方案幾专酗。睹逃。
問題3：如果你的程序有5個(gè)線程，該如何分配祷肯？
答：還是要確定問題2的答案才行沉填。

4 擴(kuò)展

4.1 分支預(yù)測與幽靈漏洞

前幾年的英特爾幽靈漏洞就利用了分支預(yù)測技術(shù)，原理是佑笋，分支預(yù)測技術(shù)在預(yù)測并執(zhí)行跳轉(zhuǎn)后的指令時(shí)翼闹，不會(huì)對(duì)指令讀取的內(nèi)存權(quán)限進(jìn)行檢查。然后蒋纬，讀取的內(nèi)存又會(huì)在cache中緩存猎荠，因此通過判斷哪個(gè)內(nèi)存的訪問時(shí)間快就可以知道之前內(nèi)存中的數(shù)據(jù)是多少了，這種方法可以獲取任意內(nèi)存位置上的數(shù)據(jù)蜀备。
舉個(gè)例子关摇，現(xiàn)在程序中有個(gè)數(shù)組a[100]，假設(shè)我們想要獲取的數(shù)據(jù)在內(nèi)存中與數(shù)組a的偏移量為2333碾阁，則我們?cè)诔绦蛑袑懸粭l指令if(xxx) int tmp=a[a[2333]];输虱，
假設(shè)a[2333]處的權(quán)限是我們不可讀，那么正常情況下脂凶，執(zhí)行tmp=a[2333]會(huì)報(bào)錯(cuò)宪睹，我們不可能知道其數(shù)據(jù)愁茁。但分支預(yù)測的時(shí)候，黑客通過精心的構(gòu)造亭病，可以使得分支預(yù)測在預(yù)測if的跳轉(zhuǎn)時(shí)鹅很，認(rèn)為程序會(huì)跳轉(zhuǎn)到該if語句的內(nèi)部，因此cpu提前執(zhí)行了tmp=a[a[2333]];,此時(shí)不會(huì)對(duì)是否可讀a[2333]的權(quán)限進(jìn)行檢查罪帖，因此a[a[2333]]被緩存到了cache上道宅。之后，if的條件執(zhí)行完胸蛛，CPU發(fā)現(xiàn)預(yù)測錯(cuò)了，不走if樱报，那么CPU就會(huì)撤銷已經(jīng)執(zhí)行指令葬项，但cache中的數(shù)據(jù)沒被撤銷。最后迹蛤，黑客只需要在主程序內(nèi)依次遍歷a數(shù)組的數(shù)據(jù)民珍，然后發(fā)現(xiàn)讀取a[30]的時(shí)候很快，那他就知道a[2333]的數(shù)據(jù)是30了盗飒。
更加具體的描述可看該鏈接 15分鐘讀懂英特爾熔斷幽靈漏洞-Emory - 知乎