多核調(diào)度的問題研究
各位好，今天看到有朋友提了一下多核程序設計方面的東西，恰好前段時間看過相關的內(nèi)容，所以就花了一個晚上，總結(jié)了一下?？赡軐懙貌皇呛芎?，不過但愿能夠起到拋磚引玉的效果。希望各位都談談自己對于多核程序設計的一點想法，這樣大家都能夠有所提高。謝謝！
多核下的多線程程序設計與傳統(tǒng)的單核下的多線程程序設計有著一定的差別，在單CPU下，是多個線程在同一個CPU上并發(fā)地執(zhí)行，而在多核下，則是由多個線程在多個核上并行地執(zhí)行。 但是，目前的程序設計中對于多核的利用并沒有達到預期的效果。因此，為了能夠在多核的環(huán)境下設計出更適合多核系統(tǒng)的程序，則是一個挑戰(zhàn)。 要做到這一點，就必須將應用程序看做是眾多相互依賴的任務的集合，將應用程序劃分成多個獨立的任務，并確定這些任務之間的相互依賴關系，這就稱為分解(decomposition)。如下如示：
任務分解：對應用程序根據(jù)其執(zhí)行的功能進行分解的過程稱為任務分解(task decomposition)。根據(jù)這種方法，就能夠?qū)Ρ姸嗟莫毩⑷蝿者M行分類。如果其中兩個任務能夠同時運行，那么開發(fā)人員就應該對其進行調(diào)度，形成二者之間的并行執(zhí)行。
數(shù)據(jù)分解：數(shù)據(jù)分解也稱為數(shù)據(jù)級并行(data-level parallelism)。是將應用程序根據(jù)各任務所處理的數(shù)據(jù)而非按任務來進行分解的方法，即以數(shù)據(jù)為中心。一般而言，能夠按照數(shù)據(jù)分解方式進行分解的應用程序都包含多個線程，這些線程分別對不同的數(shù)據(jù)對象執(zhí)行相同的操作。
數(shù)據(jù)流分解：在很多情況下，當對一個問題進行分解時，關鍵問題不在于采用一些什么任務來完成這個工作，而在于數(shù)據(jù)在這些任務之間是如何流動的。這個時候就要采用數(shù)據(jù)流分解方式，如典型的生產(chǎn)者/消費者問題。
對于任務分解，有兩個需要注意的地方：
劃分的對象是計算，將計算劃分為不同的任務
劃分后，研究不同任務所需的數(shù)據(jù)，如果這些數(shù)據(jù)不相交，則證明劃分是成功的，如果數(shù)據(jù)有相當程序的相交，意味著要重新進行數(shù)據(jù)劃分和功能劃分。 如在一個氣候模型中，需要考慮到地表模型、水文模型與海洋模型等多種情況，那么就應該將這幾種模型劃分成不同的任務，再分別進行并行地運算。
對于數(shù)據(jù)分解，劃分的對象是數(shù)據(jù)，可以是算法的輸入數(shù)據(jù)、中間處理數(shù)據(jù)和輸出數(shù)據(jù)。在劃分時應該考慮到數(shù)據(jù)上的相應操作。 最簡單的情況下，比如對1000萬個數(shù)進行相加，可以對其進行數(shù)據(jù)上的分解，用多個線程來分別計算不同批次的數(shù)據(jù)。然后再將計算的中間數(shù)據(jù)加到一起成為最終的結(jié)果。
【文章福利】小編推薦自己的Linux內(nèi)核技術(shù)交流群:【891587639】整理了一些個人覺得比較好的學習書籍、視頻資料共享在群文件里面，有需要的可以自行添加哦！?。。ê曨l教程、電子書、實戰(zhàn)項目及代碼)??
常見的并行程序設計問題的解決方法
線程過多 線程并不是越多越好，對于某個程序，如果線程過多反而會嚴重地降低程序的性能。這種影響主要在于： 將給定的工作量劃分給過多的線程會造成每個線程的工作量過少，因此可能導致線程啟動和終止的開銷比程序?qū)嶋H工作的時間還要多。 同時，太多并發(fā)線程的存在將導致共享有限硬件資源的開銷增大。如保存和恢復寄存器狀態(tài)的開銷、保存和恢復線程cache狀態(tài)的開銷、廢除虛存的開銷、線程聚集在一起等待獲取某個鎖。 怎樣解決這個問題： 限制可運行線程的個數(shù) 將計算線程與I/O線程分離開 使用已有的技術(shù)，如OpenMP，線程池等
數(shù)據(jù)競爭、死鎖 死鎖，想必大家都很熟悉。這里談談一些簡單的避免死鎖的規(guī)則： 加鎖的順序是關鍵，使用嵌套的鎖時必須保證以相同的順序獲取鎖 防止發(fā)生饑餓：即這個代碼的執(zhí)行是否一定會結(jié)束。 不要重復請求同一個鎖 越復雜的加鎖方案越有可能造成死鎖—設計應力求簡單
競爭激烈的鎖 即使是正確使用鎖來避免數(shù)據(jù)競爭，但如果各線程對鎖的競爭很激烈，那么也會引發(fā)性能問題。即很多個線程來競爭同一個鎖。在這個情況下，可以考慮將資源劃分成若干個部分，然后用彼此獨立的鎖分別保護各個部分。即合理地安排加鎖粒度的問題。在早期的Linux內(nèi)核中就使用了大內(nèi)核鎖，現(xiàn)在已經(jīng)把鎖給細劃到不同的子系統(tǒng)中去了。 如果一個數(shù)據(jù)結(jié)構(gòu)被頻繁讀取但不被頻繁寫入，就可以使用讀寫鎖來解決競爭。
線程安全函數(shù) 已有的一些函數(shù)并不是線程安全的，具體的線程安全函數(shù)可以參考APUE2上面的線程一章。
存儲效率問題 目前，處理器的速度已經(jīng)比存儲器快很多，一個處理器從內(nèi)存中讀或?qū)懸粋€值的時間內(nèi)可以完成上百次的操作。因此，現(xiàn)在的程序往往受限于存儲器的瓶頸。 首先，可以通過節(jié)省帶寬，可以減少與存儲器的數(shù)據(jù)交換數(shù)量，要節(jié)省帶寬就要將數(shù)據(jù)壓縮得更加緊湊。 其次是cache的利用?？梢詼p少數(shù)據(jù)在不同CPU的cache間的移動。CPU親合力(CPU Affinity)就是指在Linux系統(tǒng)中能夠?qū)⒁粋€或多個進程綁定到一個或多個處理器上運行。一個進程的CPU親合力掩碼決定了該進程將在哪個或哪幾個CPU上運行，在一個多處理器系統(tǒng)中，設置CPU親合力的掩碼可能會獲得更好的性能。 在下面的例子中講解了如何利用將某個進程綁定以某個CPU上運行的實例。
Cache緩存與一些程序性能優(yōu)化的小方法：
由于CPU運算速度的增長遠遠大于內(nèi)存速度的增長，同時由于程序運行的局部性原理，所以現(xiàn)代計算機體系結(jié)構(gòu)中引入了cache。 其實系統(tǒng)的存儲器本身就是一個層次結(jié)構(gòu)，從寄存器->高速緩存->主存->本地磁盤->頒布式文件系統(tǒng)。?
高速緩存的性能主要有以下幾個方面：
高速緩存的大小： 當CPU接收到指令后，它會最先向CPU中的一級緩存去尋找相關的數(shù)據(jù)，如果未命中，則繼續(xù)向下一級的二級緩存中尋找。所以高速緩存越大，命中的機率也就越高。
塊大小的影響 大的塊有利有弊，一方面，較大的塊能利用程序中可能存在的空間局部性，幫助提高命中率。不過，對于給定的高速緩存的大小，塊越大就意味著緩存行數(shù)越小，這會損害時間局部性比空間局部性更好的程序中的命中率。同時，因為塊越大，傳達時間也就越長。
相聯(lián)度的影響 較高的相聯(lián)度的優(yōu)點的降低了高速緩存由于沖突不命中出現(xiàn)抖動的可能性。不過，較高的相聯(lián)度會造成較高的成本。
前端總線的影響 現(xiàn)在的CPU技術(shù)發(fā)展很快，運算速度提高很大，而足夠大的前端總線可以保障有足夠的數(shù)據(jù)供給CPU，較低的前端總線將無法供給足夠的數(shù)據(jù)給CPU，限制了CPU性能的發(fā)揮。 最后談談程序性能優(yōu)化的相關內(nèi)容。 對于程序性能的優(yōu)化，首先應該考慮的架構(gòu)以及算法這兩方面的優(yōu)化，最后再來考慮下面所講述的這些優(yōu)化。 消除連續(xù)的函數(shù)調(diào)用 消除不必要的存儲器引用 通過展開循環(huán)降低循環(huán)開銷 提高并行性 重新排列循環(huán)以提高空間局部性 讓最常運行部分運行得更快
