高性能計算導論-高性能第一章ppt課件

1、高性能科學計算實際和方法高性能科學計算實際和方法教材n主要教材：帕切克 美國舊金山大學教授參考教材陳國良,中國科學技術(shù)大學教授課程考核n平常表現(xiàn)：包括出勤情況、課堂表現(xiàn)、課堂練習，占20n分組報告：課堂將有幾次分組討論作業(yè)，要求學生分組并完成相應的課后作業(yè)或者編程作業(yè)，并在課堂上進展演示，占40%。n期末考試：課程報告，可以是實際課程報告，也可以是實際課程報告，占40%第一章 為什么要并行計算n為什么需求不斷提升的性能n為什么需求構(gòu)建并行系統(tǒng)n為什么需求編寫并行程序n怎樣編寫并行程序時代變化n從1986年到2019年，微處置器的性能以平均每年50%的速度不斷提升n從2019年開場，單處置器的性

2、能提升速度降低到每年大約20%一個聰明的處理方案n不再繼續(xù)開發(fā)速度更快的單處置器芯片，而是開場將多個完好的單處置器放到一個集成電路芯片上。對程序員的影響n大多數(shù)串行程序是在單個處置器上運轉(zhuǎn)的，不會由于簡單地添加更多的處置器就獲得極大的性能提高n串行程序不會認識到多個處置器的存在，它們在一個多處置器系統(tǒng)上運轉(zhuǎn)的性能，往往與在多處置器系統(tǒng)的一個處置器上運轉(zhuǎn)的性能一樣。為什么需求不斷提升的性能不斷提升的計算才干曾經(jīng)成為許多飛速開展領(lǐng)域如科學、互聯(lián)網(wǎng)、文娛等的中心力量。隨著計算才干的提升，我們要思索處理的問題也在添加，下面舉些例子氣候模擬蛋白質(zhì)折疊藥物發(fā)現(xiàn)能源研討數(shù)據(jù)分析并行程序設計n為什么需求不斷提

3、升的性能n為什么需求構(gòu)建并行系統(tǒng)n為什么需求編寫并行程序n怎樣編寫并行程序為什么需求構(gòu)建并行系統(tǒng)n到目前為止，單處置器性能大幅度提升的主要緣由之一，是日益添加的集成電路晶體管密度晶體管是電子開關(guān)n但也有內(nèi)在的問題一點物理常識n更小的晶體管=速度更快的處置器n更快的處置器=增大的耗電量n增大的耗電量=添加的熱量n添加的熱量=不可靠的處置器處理方案n與其構(gòu)建更快、更復雜的單處置器，不如在單個芯片上放置多個相對簡單的處置器。n核 “core 曾經(jīng)成為中央處置器或者CPU的代名詞。n n 答案是并行！并行程序設計n為什么需求不斷提升的性能n為什么需求構(gòu)建并行系統(tǒng)n為什么需求編寫并行程序n怎樣編寫并行程

4、序為什么需求編寫并行程序n大多數(shù)為傳統(tǒng)單核系統(tǒng)編寫的程序無法利用多核處置器n雖然可以在多核系統(tǒng)上運轉(zhuǎn)一個程序的多個實例，但這樣意義不大。例如，在多個處置器上運轉(zhuǎn)一個喜歡的游戲程序的多個實例并不是我們需求的。n運轉(zhuǎn)得快！串行問題的處置方法n將串行程序改寫為并行程序n編寫一個翻譯程序來自動地將串行程序翻譯成并行程序n非常困難n鮮有突破更多的問題n雖然我們可以編寫一些程序，讓這些程序辨識串行程序的常見構(gòu)造，并自動將這些構(gòu)造轉(zhuǎn)換成并行程序的構(gòu)造，但轉(zhuǎn)化后的并行程序在實踐運轉(zhuǎn)時能夠很低效n一個串行程序的高效并行實現(xiàn)能夠不是經(jīng)過開掘其中每一個步驟的高效并行實現(xiàn)來獲得，相反，最好的并行化實現(xiàn)能夠是經(jīng)過一步步

5、回溯，然后發(fā)現(xiàn)一個全新的算法來獲得的例子n假設我們需求計算n個數(shù)的值再累加求和n串行代碼：例子續(xù)n如今我們假設有p個核，且p遠小于nn每個核可以計算大約n/p個數(shù)的值并累加求和，以得到部分和此處的前綴my_代表每個核都運用本人的私有變量，并且每個核可以獨立于其他核來執(zhí)行該代碼塊例子續(xù)n每個核都執(zhí)行完代碼后，變量my_sum中就會存儲調(diào)用Compute_next_value獲得的值的和n例如，假設有8個核，n=24，24次調(diào)用Compute_next_value獲得如下的值：1,4,3, 9,2,8, 5,1,1, 5,2,7, 2,5,0, 4,1,8, 6,5,1, 2,3,9例子續(xù)n當各個

6、核都計算完各自的my_sum值后，將本人的結(jié)果值發(fā)送給一個指定為“master的核主核， master核將收到的部分和累加而得到全局總和：例子續(xù)Core01234567my_sum8197157131214Global sum8 + 19 + 7 + 15 + 7 + 13 + 12 + 14 = 95Core01234567my_sum95197157131214n別急！還有一個更好的方法來計算全局總和更好的并行算法n不要由master核計算一切部分和的累加任務n將各個核兩兩結(jié)對，0號核將本人的部分和與1號核的部分和做加法，2號核將本人的部分和與3號核的部分和做加法，4號核將本人的部分和與5

7、號核的部分和做加法，以次類推。多個處置器求全局總和分析比較n在8個核的情況下，第一種方法中，master核需求執(zhí)行7次接納操作和7次加法n第二種方法中，master核僅需求執(zhí)行3次接納操和3次加法n第二種方法比第一種方法快2倍！分析比較續(xù)n當有更多的核時，兩者的差別更大。n在1000個核的情況下，第一種方法需求999次接納和加法操作，而第二種方法只需求10次，提高了100倍。n非常明顯，第一種計算全局總和的方法是對串行求和程序的普通化：將求和的任務在核之間平分，等到每個核都計算出部分和之后，master簡單地反復串行程序中根本的串行求和。而第二種計算全局總和的方法與原來的串行程序沒有多大關(guān)系。

8、并行程序設計n為什么需求不斷提升的性能n為什么需求構(gòu)建并行系統(tǒng)n為什么需求編寫并行程序n怎樣編寫并行程序怎樣編寫并行程序n義務并行n將待處理問題所需求執(zhí)行的各個義務分配到各個核上執(zhí)行.n數(shù)據(jù)并行n將待處理問題所需求處置的數(shù)據(jù)分配給各個核.n每個核在分配到的數(shù)據(jù)集上執(zhí)行大致類似的操作.例子15 個問題300 份試卷3個助教數(shù)據(jù)并行TA#1TA#2TA#3100 exams100 exams100 exams義務并行TA#1TA#2TA#3Questions 1 - 5Questions 6 - 10Questions 11 - 15求和例子的第一部分數(shù)據(jù)并行n數(shù)據(jù)是經(jīng)過Compute_next_

9、value計算得到的值，每個核在所賦予的數(shù)據(jù)集上執(zhí)行大致一樣的操作：經(jīng)過調(diào)用Compute_next_value獲取所需的數(shù)據(jù)，再將數(shù)據(jù)累加求部分和。求和例子的第二部分義務并行n總共有兩個義務：一個義務由master核執(zhí)行，擔任接納從其他核傳來的部分和，并累加部分和； 另一個義務由其他核執(zhí)行， 擔任將本人計算得到的部分和傳送給master核。第一章的課堂練習n練習1. 為求全局總和例子中的my_first_i和my_last_i推導一個公式。需求留意的是：在循環(huán)中，應該給各個核分配數(shù)目大致一樣的計算元素。quotient = n / p;remainder = n % p;if (my_ran

10、k remainder) my_n_count = quotient + 1; my_first_i = my_rank * my_n_count; else my_n_count = quotient; my_first_i = my_rank * my_n_count + remainder;my_last_i = my_first_i + my_n_count - 1;練習2n嘗試寫出樹形構(gòu)造求全局總和的偽代碼。假設核的數(shù)目是2的冪1、2、4、8等。提示：運用變量divisor來決議一個核應該是發(fā)送部分和還是接納部分和，divisor的初始值為2，并且每次迭代后增倍。運用變量core_d

11、ifference來決議哪個核與當前核協(xié)作，它的初始值為1，并且每次迭代后增倍。例如，在第一次迭代中0 % divisor = 0，1 % divisor = 1，所以0號核擔任接納和，1號核擔任發(fā)送。在第一次迭代中0 + core_difference = 1，1-core_difference = 0，所以0號核與1號核在第一次迭代中協(xié)作。divisor = 2;core_difference = 1;sum = my_value;while ( divisor = number of cores ) if ( my_rank % divisor = 0 ) partner = my_ra

12、nk + core_difference; receive value from partner core; sum += received value; else partner = my_rank - core_difference; send my sum to partner core; divisor *= 2; core_difference *=2;練習3n作為前面問題的另一種解法，可以運用C言語的位操作來實現(xiàn)樹形構(gòu)造的求全局總和。為了了解它是如何任務的，寫下核的二進制數(shù)編號是非常有協(xié)助的，留意每個階段相互協(xié)作的成對的核。n從表中我們可以看到在第一階段，每個核與其二進制編號的最右

13、位不同編號的核配對，在第二階段與其二進制編號的最右第二位不同編號的核配對，第三階段與其二進制編號的最右第三位不同編號的核配對。因此，假設在第一階段有二進制掩碼bitmask0012、第二階段有0102、第三階段有1002，那么可以經(jīng)過將編號中對應掩碼中非零位置的二進制數(shù)取反來獲得配對核的編號，也即經(jīng)過異或操作或者操作。n運用位異或操作或者左移操作編寫偽代碼來實現(xiàn)上述算法。bitmask = 1;divisor = 2;sum = my_value;while ( bitmask number of cores ) partner = my_rank bitmask; if ( my_rank % divisor = 0 ) receive value from partner core; sum += received value; else send my_sum to partner core; bitmask = 1;divisor *= 2;練習4在以下情況中，推導公式求出0號核執(zhí)行接納與加法操作的次數(shù)。 a. 最初的求全局總和的偽代碼。 b. 樹形構(gòu)造求全局總和。制造一張表來比較這兩種算法在總核數(shù)是2、4、8、1024時，0號核執(zhí)行的接納與加法操作的次數(shù)。