平行計算
之我見指導老師：陳麗萍
學院：資訊科學與工程學院
班級：計科0908班
姓名：原海南
學號：0909083125
完成日期：2023年5月21日
目錄1.平行計算簡介
1.1什麼是平行計算
1.2為什麼需要平行計算
1.3平行計算的歷史
1.4平行計算的現狀
2.平行計算與網際網路
2.1平行計算的體系結構
2.2平行計算網路拓撲結構
3.並行機分類
3.1傳統分類
3.1.1單指令多資料流（simd）
3.1.2多指令多資料流（mimd）
3.2按記憶體訪問模型，微處理器和網路的不同分類
3.2.1對稱多處理共享儲存並行機 （**p）
3.2.2分布共享儲存並行機（d**）
3.2.3機群（cluster）
3.2.4星群（constellation）
3.2.5大規模並行機（mpp）
4.並行演算法
4.1並行演算法的歷史
4.2平行計算的分類及簡介
5.平行計算程式的效能與優化
5.1平行計算的程式的執行時間
5.2並行程式效能優化
6.參考文獻
正文1.平行計算簡介
1.1什麼是平行計算
平行計算（paralled ***puting）是指，在並行機上，將這個任務分解成多個子任務，分配給不同的處理器。各個處理器之間相互協同，並行地執行子任務，從而達到加速求解速度，或者求解問題規模的目的。
1.2為什麼需要平行計算
大規模科學與工程計算應用是推動平行計算發展的主要動力。長期以來，它們對平行計算的需要是相依相扶的。比如，全球氣象預報中天氣預報模式要求在24小時內完成48小時天氣**資料模擬。
此時，至少需要計算635萬個網格點，記憶體需求大於1tb，計算效能要求達到25萬億次/秒。除此之外，在天體物理，流體力學，密碼破譯，海洋大氣環境，石油勘探，**資料處理，生物資訊處理，新藥研製，工業製造，影象處理等均需要平行計算的支援。
1.3平行計算的歷史
從20世紀40年代開始的現代計算機發展歷程可以分為兩個明顯的發展時代：序列計算時代、平行計算時代。每乙個計算時代都從體系結構發展開始，接著是系統軟體（特別是編譯器與作業系統）、應用軟體，最後隨著問題求解環境的發展而達到頂峰。
20世紀60年代初期，由於電晶體以及磁芯儲存器的出現，處理單元變得越來越小，儲存器也更加小巧和廉價。這些技術發展的結果導致了並行計算機的出現。這一時期的並行計算機多是規模不大的共享儲存多處理器系統，即所謂大型主機。
ibm 360是這一時期的典型代表。
到了20世紀60年代末期，同乙個處理器開始設定多個功能相同的功能單元，流水線技術也出現了。與單純提高時鐘頻率相比，這些並行特性在處理器內部的應用大大提高了並行計算機系統的效能。伊利諾依大學和burroughs公司此時開始實施illiac ⅳ計畫，研製一台64顆cpu的simd主機系統，它涉及到硬體技術、體系結構、i/o裝置、作業系統、程式語言直至應用程式在內的眾多研究課題。
不過，當一台規模大大縮小的原型系統（僅使用了16顆cpu）終於在2023年面世時，整個計算機界已經發生了巨大變化。
20世紀80年代中期，加州理工學院成功地將64個i8086/i8087處理器通過超立方體互鏈結構鏈結起來。此後，便先後出現了intel ipsc系列、inmos transputer系列，intel paragon以及ibm sp的前身vulcan等基於訊息傳遞機制的並行計算機。 20世紀80年代末到90年代初，共享儲存器方式的大規模並行計算機又獲得了新的發展。
ibm將大量早期risc微處理器通過蝶形互連網路鏈結起來。人們開始考慮如何才能在實現共享儲存器快取一致的同時，使系統具有一定的可擴充套件性。
20世紀90年代初期，史丹福大學提出了dash計畫，它通過維護乙個儲存有每一快取塊位置資訊的目錄結構來實現分布式共享儲存器的快取一致性。後來，ieee在此基礎上提出了快取一致性協議的標準。
20世紀90年代至今，主要的幾種體系結構開始走向融合。 屬於資料並行型別的cm-5除大量採用商品化的微處理器以外，也允許使用者層的程式傳遞一些簡單的訊息。 cray t3d是一台numa結構的共享儲存型並行計算機，但是它也提供了全域性同步機制、訊息佇列機制，並採取了一些減少訊息傳遞延遲的技術。
隨著微處理器商品化、網路裝置的發展以及mpi/pvm等並行程式設計標準的發布，集群架構的並行計算機出現開始。ibm sp2系列集群系統就是其中的典型代表。在這些系統中，各個節點採用的都是標準的商品化計算機，它們之間通過高速網路連線起來。
1.4平行計算的現狀
目前，在計算力學領域內，圍繞著基於變分原理的有限元法和基於邊界積分方程的邊界元法，以及基於現在問世的各種並行計算機，逐漸形成了乙個新的學科分支——有限元平行計算。它是高效能的，使得許多現在應用序列計算機和序列演算法不能解決或求解不好的大型的、複雜的力學問題能得到滿意的解答，故其發展速度十分驚人。在國際上已經掀起了利用並行機進行工程分析和研究的高潮。
從1975到2023年的二十年間，有關有限元方法和相應的數值平行計算的文章已發表1000餘篇。 有限元平行計算正在向兩個方向發展。一是對系統方程組實施並行求解的各種演算法。
二是並行分析方法，包括有限元並行演算法和邊界元並行演算法，前者趨向成熟，而後者的研究較少。對這一方面的研究，是為了挖掘有限元計算自身潛在的並行性，是有限元平行計算的根本問題。
並行演算法的設計和有效實現強烈地依賴於並行機的硬軟體環境。國內僅極少數單位擁有並行機，且機型雜亂，因此研究人員少，起步晚，而且侷限於特定的硬體環境。從有限元分析方法的內容來看，發表的幾十篇研究**（報告）還未顯示出較強的系統性。
國內平行計算方法的研究，在硬體上基於向量機、分布式並行機和共享存貯式並行機；在內容上，似乎面很廣，但系統性和深度還很不夠，軟體開發距實際應用和商品化還有很大距離，對不依賴並行機具體環境的通用並行演算法研究還很少，同樣對旨在進行結構有限元分析的平行計算的硬體研究也很少。
自從美國國家宇航局（nasa）的a.k.noor於2023年發表第一篇有限元平行計算的文章以來，有限元並行處理技術幾乎與並行計算機同步發展。
距不完全統計，到2023年，國外已發表了400餘篇這方面的**，其中後5年的文章篇數是前12年的總和。在研究內容上也由過去的演算法研究發展到了演算法、軟體和硬體相結合的研究，並針對一些機型開發了一些實用的大型結構分析軟體。
當前， 並行和分布計算發展的基本狀況是：
1 並行軟體的發展遠遠落後於並行和分布計算體系結構的發展。
2 並行和分布計算應用遠遠落後於並行和分布計算技術的發展。
3 向盡量採用商品化的軟、 硬體甚至系統來構成並行和分布計算系統平台的方向發展。
4 計算系統的規模可伸縮性和可程式設計性已成為並行和分布計算系統進一步發展的一對主要矛盾。
5 由高速網聯成的各種型別的、 規模可伸縮計算機群， 由於其經濟有效性而發展很快， 加上可移植異構程式設計環境pvm(parallel virtual macrine) 日益流行和標準的訊息傳送平台mpi(message passing inte***ce) 並行程式設計環境的日益普及， 已經並將進一步促使並行和分布計算應用有較大的發展。
6 由基於numa(non-uniform memory access) 方式構成的分布共享儲存器(distributed shared memory，d**) 組成的並行機系統， 特別是採用目錄方法來保持各cache 之間資料一致性的cc-numa(cache coherent numa)， 由於具有良好的可伸縮性和可程式設計性， 已受到諸多計算機廠商的青睞， 不少廠商已經和準備推出有關cc-numa 並行機系統。
7 大規模並行處理系統已不再是主要研究領域。 由於負載難於平衡和相應的並行演算法設計困難， 據國外**， 在高能計算機市場中，mpp 所佔的份額將從目前的7% 降為2000 年的3%。
美國在並行和分布計算研究領域中， 一直處於領先地位。 研究重點已從原來熱門非凡的mpp 系統轉向可伸縮並行機(scalable parallel ***puters) 和各種型別的計算機機群。 特別是後者， 因為如果部門或單位已有現成的由區域網連線起來的眾多任務作站、pc 機、 伺服器及並行機系統， 則組成計算機機群的分布計算系統的成本就相當低， 而它們的整體效能則可隨機群局域網際網路效能的提高( 從10mbps、100mbps、155mbps、622mbps 到1gbps 等)、 構成機群的結點機效能提高以及執行軟體的效率提高而不斷提高。
美國計算機廠商對由numa 方式， 特別是cc-numa 方式構成的可伸縮並行機系統特別看好。sgi 公司推出的origin 2000 採用可伸縮共享記憶體多處理器結構， 採用mips r10000 4 路超標量處理器。 每個結點機由若干個cpu、 一定容量儲存器、 相應i/o 頻寬和電源模組組成。
隨著模組數增多， 系統規模也隨之增大， 在增加處理器數目的同時， 儲存器容量和i/o 頻寬也按比例增長。 為了提高整個系統頻寬， 各模組間用高速的craylink( 高速光纜) 聯結器連線起來， 從而保證系統具有良好的可伸縮性。sequent 公司則用傳統**p 多機系統作為結點機， 最小規模的結點機內有4 個intel 的pentium-pro 超標量機以及相應儲存器和7 個pci 槽。
這種結點模組稱為numa-q(quad)。 更大規模的結點機可由若干個quad 組成。 各quad 之間用高速iq link 聯結器連線起來， 形成規模可伸縮cc-numa 並行機系統。
hp 公司沿用sequent 公司的類似方法和技術來構成自己的cc-numa 並行機產品。 應指出的是上述的cc-numa 系統都是遵照基於目錄表原理的sci(scalable coherence inte***ce)ieee 互連標準而加以實現的。
計算機體系結構複習
模擬試題一 課程名稱計算機系統結構適用班級 考試時間 120 分鐘班級學號姓名 一 單項選擇題 本大題共10小題，每小題2分，共20分。在每小題的四個備選答案中選出乙個符合題意的，並將其前面的序號填在題後的括號內。1.按flynn分類法，處理機illiac iv屬於 sisd simd misd m...
計算機體系結構報告
計算機組織與體系結構 實驗報告 實驗名稱 姓名班級 學號實驗一基本運算器實驗 一 實驗目的 1 了解運算器的組成結構。2 掌握運算器的工作原理。二 實驗裝置 pc 機一台，td cma 實驗系統一套。三 實驗原理 本實驗的原理如圖 1 1 1 所示。運算器內部含有三個獨立運算部件，分別為算術 邏輯和...
計算機體系結構習題答案
第1章計算機系統結構的基本概念 1.1 解釋下列術語 層次機構 按照計算機語言從低階到高階的次序，把計算機系統按功能劃分成多級層次結構，每一層以一種不同的語言為特徵。這些層次依次為 微程式機器級，傳統機器語言機器級，組合語言機器級，高階語言機器級，應用語言機器級等。虛擬機器 用軟體實現的機器。翻譯 ...