Lecture 1: Brief Introduction
對ICS的簡單回顧
已經(jīng)學(xué)過的幾種并行模式：
- 多進(jìn)程：并發(fā)（底層的串行，高層的并行）
- 多線程：并行
- 多核：并行
- 向量運(yùn)算
對并行計(jì)算中幾個重要問題的論述
-
計(jì)算密集型：
- 比特幣：利用隨機(jī)數(shù)碰撞產(chǎn)生答案，最后挖礦的效果主要受計(jì)算的效果限制。
- 為什么計(jì)算密集：對于存儲器訪問少，主要可以存儲于寄存器
- 計(jì)算機(jī)中最難做的是數(shù)據(jù)的傳輸，但是比特幣主要利用GPU或者專用ASIC的計(jì)算能力
- 不需要數(shù)據(jù)傳輸?shù)牟⑿惺?strong>embarrassing parrallel，并沒有什么難度
- 有一類應(yīng)用不需要傳輸，只需要做出計(jì)算單元，就可以快速提升任務(wù)完成速度
-
訪存密集：
- 比如GDDR在芯片外面存儲信息，由于傳輸速度的限制，傳輸數(shù)據(jù)到計(jì)算單元的速度低于計(jì)算速度
- 表現(xiàn)：訪存帶寬充滿（90%+），運(yùn)算單元吃不飽（20%+），瓶頸在于數(shù)據(jù)傳輸
- 過去幾年浮點(diǎn)定點(diǎn)大幅提高，但是傳輸速度只是線性增加
- 訪存密集型任務(wù)在真實(shí)并行任務(wù)中大量存在
-
通訊密集：
瓶頸不再是運(yùn)算，也不再是數(shù)據(jù)搬運(yùn)
以排序算法為例，在單個服務(wù)器上是訪存密集型任務(wù)，受制于芯片與內(nèi)存?zhèn)鬏數(shù)膸?，?jì)算復(fù)雜性較低
-
數(shù)據(jù)量到達(dá)一定程度，需要放置在多個服務(wù)器中進(jìn)行工作。
考察下面的例子：比如我們的服務(wù)器從1臺到100臺：
計(jì)算能力（CPU） *100
訪存帶寬（共同訪存） *100
但是并不是這樣的情況就會讓我們的性能提升100倍，因?yàn)檫@里需要大量服務(wù)器之間的交互。
通訊量上升巨大，瓶頸變成了網(wǎng)絡(luò)帶寬（GB/S）
-
訪外存密集：
- 某些大數(shù)據(jù)場景，以地震數(shù)據(jù)為例，數(shù)據(jù)量極其巨大，內(nèi)存根本放不下
- 采用分布式外排序算法，數(shù)據(jù)都存放在外存中
- 如果硬盤很慢，那么瓶頸在于硬盤帶寬
- 硬盤帶寬提升迅速
- 通訊帶寬都最大可能成為未來并行任務(wù)的瓶頸
并行計(jì)算解決的一些實(shí)際問題
- 宇宙學(xué)模擬：在考慮萬有引力的時候如果兩個兩個計(jì)算，那么計(jì)算的時間復(fù)雜度是$O(n^2)$，這在有很多星體的時候明顯不是一個很好的想法
- 找一個截斷半徑，距離長于階段半徑的部分就不再管了
- 對于整個空間（假設(shè)為正方體的空間，便于坐標(biāo)計(jì)算）不斷均分為8個部分（想像在正方體的三個方向各切一刀），如此進(jìn)行下去直到每個小塊里面只有一個星體。
在計(jì)算的時候多個星體可以方便地取到重心，對于大范圍內(nèi)只有一個的星體我們可以直接用大正方體的中心替代其位置
- 湍流現(xiàn)象模擬
- 蛋白質(zhì)折疊現(xiàn)象模擬
- 利用分子動力學(xué)
- 選擇合適的step-gap
- Google服務(wù)器：
- 并行處理大量事務(wù)
- 游戲中的圖像處理
- 淘寶服務(wù)器：
- Map Reduce
一點(diǎn)后話：
- 實(shí)際可以應(yīng)用的算法最高不超過$O(nlogn)$，因?yàn)楝F(xiàn)實(shí)生活中面對的往往都是極其大量的數(shù)據(jù)
- 如果沒有標(biāo)準(zhǔn)的可以達(dá)到這個層次的算法，有時就要進(jìn)行適當(dāng)?shù)慕疲ɡ碚撃Ｐ蛌s計(jì)算模型）
- 利用模型中的稀疏性，具體的應(yīng)用場景會賦予真實(shí)的方程很大的稀疏性，必須要利用起來
