並行數值計算方法

『壹』 除有限單元法外，岩土工程常用到哪些數值方法，並對比其優缺點

岩土工程常用的數值方法包括：有限差分法、邊界元法、離散元法、顆粒元法、不連續變形分析法、流形元法、模糊數學方法、概率論與可靠度分析方法、灰色系統理論、人工智慧與專家系統、神經網路方法、時間序列分析法。
有限單元法的優缺點：有限單元法的理論基礎是虛功原理和基於最小勢能的變分原理，它將研究域離散化，對位移場和應力場的連續性進行物理近似。有限單元法適用性廣泛，從理論上講對任何問題都適用，但計算速度相對較慢。即，物理概念清晰、靈活、通用、計算速度叫慢。
有限差分法：該方法適合求解非線性大變形問題，在岩土力學計算中有廣泛的應用。有限差分法和有限單元法都產生一組待解方程組。盡管這些方程是通過不同方式推導出來的，但兩者產生的方程是一致。另外，有限單元程序通常要將單元矩陣組合成大型整體剛度矩陣，而有限差分則無需如此，因為它相對高效地在每個計算步重新生成有限差分方程。在有限單元法中，常採用隱式、矩陣解算方法，而有限差分法則通常採用「顯式」、時間遞步法解算代數方程。
邊界元法：該方法的理論基礎是Betti功互等定理和Kelvin基本解，它只要離散求解域的邊界，因而得到離散代數方程組中的未知量也只是邊界上的量。邊界元法化微分方程為邊界積分方程，離散劃分少，可以考慮遠場應力，有降低維數的優點，可以用較少的內存解決較大的問題，便於提高計算速度。
離散元法：離散元法的理論基礎是牛頓第二定律並結合不同的本構關系，適用對非連續體如岩體問題求解。該方法利用岩體的斷裂面進行網格劃分，每個單元就是被斷裂面切割的岩塊，視岩塊的運動主要受控於岩體節理系統。它採用顯式求解的方法，按照塊體運動、弱面產生變形，變形是接觸區的滑動和轉動，由牛頓定律、運動學方程求解，無需形成大型矩陣而直接按時步迭代求解，在求解過程中允許塊體間開裂、錯動，並可以脫離母體而下落。離散元法對破碎岩石工程，動態和准動態問題能給出較好解答。
顆粒元法：顆粒元方法是通過離散單元方法來模擬圓形顆粒介質的運動及其相互作用，它採用數值方法將物體分為有代表性的多個顆粒單元，通過顆粒間的相互作用來表達整個宏觀物體的應力響應，從而利用局部的模擬結果來計算顆粒群群體的運動與應力場特徵。 不連續變形分析方法：該方法是並行於有限單元法的一種方法，其不同之處是可以計算不連續面的錯位、滑移、開裂和旋轉等大位移的靜力和動力問題。此方法在岩石力學中的應用備受關注。
流形元法；該方法是運用現代數學「流形」的有限覆蓋技術所建立起來的一種新的數值方法。有限覆蓋是由物理覆蓋和數學覆蓋所組成的，它可以處理連續和非連續的問題，在統一解決有限單元法、不連續變形分析法和其他數值方法的耦合計算方面，有重要的應用前景。
無單元法：該方法是一種不劃分單元的數值計算方法，它採用滑動最小二乘法所產生的光滑函數去近似場函數，而且又保留了有限單元法的一些特點。它只要求結點處的信息，而不需要也沒有單元的信息。無單元法可以求解具有復雜邊界條件的邊值問題，如開裂問題，只要加密離散點就可以跟蹤裂縫的傳播。它在解決岩石力學非線性、非連續問題等方面具有重要價值和發展前景。
混合法：對於復雜工程問題，可採用混合法，即有限單元法、邊界元法、離散元法等兩兩耦合來求解。
模糊數學方法：模糊理論用隸屬函數代替確定論中的特徵函數描述邊界不清的過渡性問題，模糊模式識別和綜合評判理論對多因素問題分析適用。 概率論與可靠度分析方法：運用概率論方法分析事件發生的概率，進行安全和可靠度評價。對岩土力學而言，包括岩石（土）的穩定性判斷、強度預測預報、工程可靠度分析、頂板穩定性分析、地震研究、基礎工程穩定性研究等。
灰色系統理論：以「灰色、灰關系、灰數」為特徵，研究介於「黑色」和「白色」之間事件的特徵，在社會科學及自然科學領域應用廣泛。岩土力學中，用灰色系統理論進行岩體分類、滑坡發生時間預測、岩爆分析與預測、基礎工程穩定性、工程結構分析，用灰色關聯度分析岩土體穩定性因素主次關系等。
人工智慧與專家系統：應用專家的知識進行知識處理、知識運用、搜索、不確定性推理分析復雜問題並給出合理的建議和決策。岩石力學中，可進行如岩土（石）分類、穩定性分析、支護設計、加固方案優化等研究。 神經網路方法：試圖模擬人腦神經系統的組織方式來構成新型的信息處理系統，通過神經網路的學習、記憶和推理過程進行信息處理。岩石力學中，用於各種岩土力學參數分析、地應力處理、地壓預測、岩土分類、穩定性評價與預測等。
時間序列分析法：通過對系統行為的漲落規律統計，用時間序列函數研究系統的動態力學行為。岩石力學中，用於礦壓顯現規律研究、岩石蠕變、岩石工程的位移、邊坡和硐室穩定性等、基礎工程中降水、開挖、沉降變形等與時間相關的問題。

『貳』 雅可比法求對稱矩陣的特徵值的並行演算法

如果把所有非對角元掃描一遍作為一次迭代，那麼幾步迭代後就能收斂，換句話說需要O(n^2)步旋轉才能收斂，因為Jacobi演算法具有漸進二次收斂性。

Jacobi演算法一般比較慢，但是如果慢的過分一般來講是你的代碼有問題，你可以把非對角元的平方和輸出出來觀察一下收斂速度。

『叄』 《並行演算法的設計與分析》pdf下載在線閱讀，求百度網盤雲資源

《並行演算法的設計與分析》（陳國良）電子書網盤下載免費在線閱讀

資源鏈接：

鏈接：https://pan..com/s/1sSu7g5YpTBi1Y7o5KdnbqA

書名：並行演算法的設計與分析

作者：陳國良

出版年份：2009-8

頁數：813

內容簡介：第3版在修訂版的基礎上進行了大幅度的修訂，新增加3章、重寫3章，改寫8章。《普通高等教育十一五國家級規劃教材·並行演算法的設計與分析(第3版)》系統深入地討論了計算機領域中諸多計算問題的並行演算法的設計和分析方法。在著重介紹各種並行計算模型上的常用和典型的並行演算法的同時，也力圖反映本學科的最新成就、學科前沿和發展趨勢。

全書共分二十章，包括基礎篇4章(緒論、設計技術、前綴計算、排序和選擇網路)，並行演算法篇9章（排序和選擇演算法、分布式演算法、並行搜索、選路演算法、串匹配、表達式求值、上下文無關語言、圖論演算法、計算幾何），數值並行演算法篇3章（矩陣運算、數值計算、快速傅氏變換），理論篇4章（組合搜索、隨機演算法、VLSI計算理論、並行計算理論）。

《普通高等教育十一五國家級規劃教材·並行演算法的設計與分析(第3版)》取材豐富，內容系統深入，可作為高等學校計算機及其他信息類有關專業高年級本科生和研究生的教材，也可供從事計算機科學理論和並行演算法研究的科技人員閱讀參考。

《普通高等教育十一五國家級規劃教材·並行演算法的設計與分析(第3版)》初版曾獲1994年度教育部高等學校優秀教材一等獎和1997年度國家級教學成果二等獎。

『肆』 Matlab計算一個循環有100個函數值需要計算，請問如何提高計算速度用並行計算嗎謝謝！

樓上的回答有那麼點意思，但似乎並未答到點子上。

原因是，並行計算的parfor循環把變數劃分成幾類：即Loop Variable、Sliced Variables、Broadcast Variables、Rection Variables、Temporary Variables，幾類變數各有不同的限制和用途。而題主的循環中f本來應該是Sliced Variables，但由於其索引方式用到了變數col，導致不好分類。

解決辦法：如樓上建議的那樣，直接用for循環是一個辦法，但就目前的循環來看，似乎並無使用循環的必要，直接用向量化的賦值語句就可以了。

題主最好把mengte函數的代碼貼出來，我再幫著看看怎樣改寫以提高效率。

『伍』 pso的並行演算法

與大多數隨機優化演算法相似，當適應值評價函數的計算量比較大時，PSO演算法的計算量會很大。為了解決該問題，研究者提出了並行PSO演算法。與並行遺傳演算法類似，並行PSO演算法也可以有三種並行群體模型：主從並行模型、島嶼群體模型和鄰接模型。
Schutte採用同步實現方式，在計算完一代中所有點的適應值之後才進入下一代。這種並行方法雖然實現簡單，但常常會導致並行效率很差。故而有人提出非同步方式的並行演算法，可以在對數值精度影響不大的條件下提高PSO演算法的並行性能。這兩種方式採用的都是主從並行模型，其中非同步方式在求解上耦合性更高，更容易產生通信瓶頸。
Baskar提出一種兩個子種群並行演化的並發PSO演算法，其中一個子種群採用原始的PSO演算法，另一個子種群採用基於適應值距離比的PSO演算法（FDR-PSO）；兩個子種群之間頻繁地進行信息交換。而El-Abd研究了在子種群中採用局部鄰域版本的協作PSO演算法，並研究了多種信息交換的方式及其對演算法性能的影響。黃芳提出一種基於島嶼群體模型的並行PSO演算法，並引入一種集中式遷移策略，提高了求解效率，同時改善了早收斂現象。
Li提出延遲交換信息的並行演算法屬於鄰接模型，該演算法可以提高速度，但可能使得解的質量變差。

『陸』 並行處理的並行演算法的基本策略

在並行處理技術中所使用的演算法主要遵循三種策略：
1．分而治之法：也就是把多個任務分解到多個處理器或多個計算機中，然後再按照一定的拓撲結構來進行求解。
2．重新排序法：分別採用靜態或動態的指令詞度方式。
3．顯式/隱式並行性結合：顯式指的是並行語言通過編譯形成並行程序，隱式指的是串列語言通過編譯形成並行程序，顯式/隱式並行性結合的關鍵就在於並行編譯，而並行編譯涉及到語句、程序段、進程以及各級程序的並行性。
二、並行性描述定義
利用計算機語言進行並行性描述的時候主要有三種方案：
1．語言擴展方案：也就是利用各種語言的庫函數來進行並行性功能的擴展。
2．編譯制導法：也稱為智能編譯，它是隱式並行策略的體現，主要是由並行編譯系統進行程序表示、控制流的分析、相關分析、優化分析和並行化劃分，由相關分析得到方法庫管理方案，由優化分析得到知識庫管理方案，由並行化劃分得到程序重構，從而形成並行程序。
3．新的語言結構法：這是顯式並行策略的體現。也就是建立一種全新的並行語言的體系，而這種並行語言通過編譯就能直接形成並行程序。
三、並行軟體
並行軟體可分成並行系統軟體和並行應用軟體兩大類，並行系統軟體主要指並行編譯系統和並行操作系統，並行應用軟體主要指各種軟體工具和應用軟體包。在軟體中所牽涉到的程序的並行性主要是指程序的相關性和網路互連兩方面。
1．程序的相關性：程序的相關性主要分為數據相關、控制相關和資源相關三類。
數據相關說明的是語句之間的有序關系，主要有流相關、反相關、輸出相關、I/O相關和求知相關等，這種關系在程序運行前就可以通過分析程序確定下來。數據相關是一種偏序關系，程序中並不是每一對語句的成員都是相關聯的。可以通過分析程序的數據相關，把程序中一些不存在相關性的指令並行地執行，以提高程序運行的速度。
控制相關指的是語句執行次序在運行前不能確定的情況。它一般是由轉移指令引起的，只有在程序執行到一定的語句時才能判斷出語句的相關性。控制相關常使正在開發的並行性中止，為了開發更多的並行性，必須用編譯技術克服控制相關。
而資源相關則與系統進行的工作無關，而與並行事件利用整數部件、浮點部件、寄存器和存儲區等共享資源時發生的沖突有關。軟體的並行性主要是由程序的控制相關和數據相關性決定的。在並行性開發時往往把程序劃分成許多的程序段——顆粒。顆粒的規模也稱為粒度，它是衡量軟體進程所含計算量的尺度，一般用細、中、粗來描述。劃分的粒度越細，各子系統間的通信時延也越低，並行性就越高，但系統開銷也越大。因此，我們在進行程序組合優化的時候應該選擇適當的粒度，並且把通訊時延盡可能放在程序段中進行，還可以通過軟硬體適配和編譯優化的手段來提高程序的並行度。
2．網路互連：將計算機子系統互連在一起或構造多處理機或多計算機時可使用靜態或動態拓撲結構的網路。靜態網路由點一點直接相連而成，這種連接方式在程序執行過程中不會改變，常用來實現集中式系統的子系統之間或分布式系統的多個計算結點之間的固定連接。動態網路是用開關通道實現的，它可動態地改變結構，使之與用戶程序中的通信要求匹配。動態網路包括匯流排、交叉開關和多級網路，常用於共享存儲型多處理機中。在網路上的消息傳遞主要通過尋徑來實現。常見的尋徑方式有存儲轉發尋徑和蟲蝕尋徑等。在存儲轉發網路中以長度固定的包作為信息流的基本單位，每個結點有一個包緩沖區，包從源結點經過一系列中間結點到達目的結點。存儲轉發網路的時延與源和目的之間的距離(段數)成正比。而在新型的計算機系統中採用蟲蝕尋徑，把包進一步分成一些固定長度的片，與結點相連的硬體尋徑器中有片緩沖區。消息從源傳送到目的結點要經過一系列尋徑器。同一個包中所有的片以流水方式順序傳送，不同的包可交替地傳送，但不同包的片不能交叉，以免被送到錯誤的目的地。蟲蝕尋徑的時延幾乎與源和目的之間的距離無關。在尋徑中產生的死鎖問題可以由虛擬通道來解決。虛擬通道是兩個結點間的邏輯鏈，它由源結點的片緩沖區、結點間的物理通道以及接收結點的片緩沖區組成。物理通道由所有的虛擬通道分時地共享。虛擬通道雖然可以避免死鎖，但可能會使每個請求可用的有效通道頻寬降低。因此，在確定虛擬通道數目時，需要對網路吞吐量和通信時延折衷考慮。
四、硬體技術在硬體技術方面主要從處理機、存儲器和流水線三個方面來實現並行。
1．處理機：主要的處理機系列包括CISC、RISC、超標量、VL1W、超流水線、向量以及符號處理機。
傳統的處理機屬於復雜指令系統計算(CISC)結構。指令系統大，指令格式可變，通用寄存器個數較少，基本上使用合一的指令與數據高速緩存，時鍾頻率較低，CPI較高，大多數利用ROM 實現微碼控制CPU，而當今的精簡指令系統計算(RISC)處理機指令格式簡單規范，面向寄存器堆，採用重疊寄存器窗口技術，具有多級Cache，多種流水線結構，強調編譯優化技術，時鍾頻率快，CPI低，大多數用硬連線控制CPU。
CISC或RISC標量處理機都可以採用超標量或向量結構來改善性能。標量處理機在每個周期內只發射一條指令並要求周期只完成從流水線來的一條指令。而在超標量處理機中，使用了多指令流水線，每個周期要發射多條指令並產生多個結果。由於希望程序中有許多的指令級並行性，因此超標量處理機更要依靠優化編譯器去開發並行性。
VL1W 結構是將水平微碼和超標量處理這兩種普遍採用的概念結合起來產生的。典型的超長指令字VL1W 機器指令字長度有數百位。在VLlW 處理機中，多個功能部件是並發工作的，所有的功能部件共享使用公用大型寄存器堆，由功能部件同時執行的各種操作是用VL1W 指令來同步的，每條指令可指定多個操作。VL1W 指令解碼比超標量指令容易，但在開發不同數量的並行性時總是需要不同的指令系統。VL1W 主要是開發標量操作之間的並行性，它的成功與否很大程度取決於代碼壓縮的效率，其結構和任何傳統的通用處理機完全不兼容。即使同一結構的不同實現也不大可能做到彼此二進制兼容。VL1W 的主要優點在於它的硬體結構和指令系統簡單，在科學應用領域可以發揮良好作用，但在一般應用場合可能並不很好用。
向量處理機對數組執行向量指令，每條指令都包含一串重復的操作。它是專門設計用來完成向量運算的協處理機，通常用於多流水線超級計算機中。向量處理機可以利用循環級展開所得的並行性，它可以附屬於任何標量處理機。專用的向量流水線可以在循環控制中消除某些軟體開銷，它的效果與優化編譯器將順序代碼向量化的性能很有關系。從理論上說，向量機可以具有和超標量處理機同樣的性能，因此可以說向量機的並行性與超標量機相同。
符號處理機是為AI應用而研製的，已用於定理證明、模式識別、專家系統、知識工程、文本檢索、科學以及機器智能等許多應用領域。在這些應用中，數據和知識表達式、原語操作、演算法特性、存儲器、I/0和通信以及專用的結構特性與數值計算是不一樣的，符號處理機也稱為邏輯程序設計語言處理機、表處理語言處理機或符號變換器。符號處理並不和數值數據打交道，它處理的是邏輯程序、符號表、對象、劇本、黑板、產生式系統、語義網路、框架以及人工神經網路等問題。這些操作需要專門的指令系統，通常不使用浮點操作。
2．存儲器：存儲設備按容量和存取時間從低到高可分為寄存器、高速緩存、主存儲器、磁碟設備和磁帶機五個層次。較低層存儲設備與較高層的相比，存取速度較快、容量較小，每位元組成本較高、帶寬較寬、傳輸單位較小。
存放在存儲器層次結構中的信息滿足三個重要特性：包含性、一致性和局部性。所謂包含性，指的是一個信息字的復製品可以在比它高的所有層中找到，而如果在高層中丟失了一個信息，則在比它低的所有層中此信息也將丟失。CPU 和高速緩存之間的信息傳送是按字進行的，高速緩存和主存儲器間用塊作為數據傳送的基本單位，主存和磁碟之間又是以頁面為基本單位來傳送信息的，而在磁碟和磁帶機之間的數據傳送則是按文件級處理的。所謂一致性要求的是同一個信息項與後繼存儲器層次上的副本是一致的。也就是說，如果在高速緩存中的一個字被修改過，那麼在所有更高層上該字的副本也必須立即或最後加以修改。為了盡量減少存儲器層次結構的有效存取時間，通常把頻繁使用的信息放在較低層次。維護存儲器層次結構一致性一般有兩種策略，一種是寫直達策略，也就是如果，則立即在所有高層存儲器中進行同樣的修改；另一種是寫回策略，也就是在較低層中對信息進行修改後並不立即在高層存儲器中進行相應的修改，而是等到該信息將被替換或將從低層中消失時才在所有高層存儲器中進行同樣的修改。甚至可以將寫直達和寫回策略的優點結合起來，形成寫一次協議來維護存儲器的一致性。
存儲器的層次結構是在一種程序行為——訪問的局部性基礎上開發出來的。主要有時間局部性、空間局部性和順序局部性。時間局部性指的是最近的訪問項很可能在不久的將來再次被訪問。它往往會引起對最近使用區域的集中訪問。空間局部性表示一種趨勢，指的是一個進程訪問的各項其地址彼此很近。順序局部性指的是在典型程序中，除非是轉移指令，一般指令都是順序執行的。
在多處理機系統中一般使用共享存儲器。對共享存儲器的組織一般採用低位交叉、高位交叉、高低位交叉三種方法。低位交叉又稱並發存取，它是把相鄰的地址放在相鄰的存儲器模塊中，在訪問時不容易產生沖突，並行性較好，但可靠性容錯能力和擴展性均較差。高位交叉又稱允許同時存取，它是把相鄰地址分配到同一個存儲器模塊中，可靠性、容錯能力和擴展性均較強，但訪問時易產生沖突，帶寬較窄，並行性較差。高低位交叉存取又稱C—s存取，它是結合了高位交叉和低位交叉兩種方法的優點，既解決了沖突問題，又能有效地提高容錯能力和並行性，最適合於向量處理機結構。
3．流水線：流水線技術主要有指令流水線技術和運算流水線技術兩種。
指令流水線技術主要目的是要提高計算機的運行效率和吞吐率。它主要通過設置預取指令緩沖區、設置多功能部件、進行內部數據定向、採取適當的指令調度策略來實現。指令調度的策略主要有靜態和動態兩種，靜態詞度是基於軟體的，主要由編譯器完成，動態詞度是基於硬體的，主要是通過硬體技術進行。
運算流水線主要有單功能流水線和多功能流水線兩種。其中多功能流水線又可分為靜態流水線和動態流水線。靜態流水線技術只用來實現確定的功能，而動態流水線可以在不同時間重新組合，實現不同的功能，它除流線連接外，還允許前饋和反饋連接，因此也稱為非線性流水線。這些前饋和反饋連接使得進入流水線的相繼事件的詞度變得很不簡單。由於這些連接，流水線不一定從最後一段輸出。根據不同的數據流動模式，人們可以用同一條流水線求得不同功能的值。
並行計算機發展簡述
40 年代開始的現代計算機發展歷程可以分為兩個明顯的發展時代：串列計算時代、並行計算時代。每一個計算時代都從體系結構發展開始，接著是系統軟體（特別是編譯器與操作系統）、應用軟體，最後隨著問題求解環境的發展而達到頂峰。創建和使用並行計算機的主要原因是因為並行計算機是解決單處理器速度瓶頸的最好方法之一。
並行計算機是由一組處理單元組成的，這組處理單元通過相互之間的通信與協作，以更快的速度共同完成一項大規模的計算任務。因此，並行計算機的兩個最主要的組成部分是計算節點和節點間的通信與協作機制。並行計算機體系結構的發展也主要體現在計算節點性能的提高以及節點間通信技術的改進兩方面。
60 年代初期，由於晶體管以及磁芯存儲器的出現，處理單元變得越來越小，存儲器也更加小巧和廉價。這些技術發展的結果導致了並行計算機的出現，這一時期的並行計算機多是規模不大的共享存儲多處理器系統，即所謂大型主機（Mainframe）。IBM360 是這一時期的典型代表。
到了60 年代末期，同一個處理器開始設置多個功能相同的功能單元，流水線技術也出現了。與單純提高時鍾頻率相比，這些並行特性在處理器內部的應用大大提高了並行計算機系統的性能。伊利諾依大學和Burroughs 公司此時開始實施IlliacIV 計劃，研製一台64 個CPU 的SIMD 主機系統，它涉及到硬體技術、體系結構、I/O 設備、操作系統、程序設計語言直至應用程序在內的眾多研究課題。不過，當一台規模大大縮小了的16CPU 系統終於在1975 年面世時，整個計算機界已經發生了巨大變化。
首先是存儲系統概念的革新，提出虛擬存儲和緩存的思想。IBM360/85 系統與360/91是屬於同一系列的兩個機型，360/91 的主頻高於360/85，所選用的內存速度也較快，並且採用了動態調度的指令流水線；但是，360/85 的整體性能卻高於360/91，唯一的原因就是前者採用了緩存技術，而後者則沒有。
其次是半導體存儲器開始代替磁芯存儲器。最初，半導體存儲器只是在某些機器被用作緩存，而CDC7600 則率先全面採用這種體積更小、速度更快、可以直接定址的半導體存儲器，磁芯存儲器從此退出了歷史舞台。與此同時，集成電路也出現了，並迅速應用到了計算機中。元器件技術的這兩大革命性突破，使得IlliacIV 的設計者們在底層硬體以及並行體系結構方面提出的種種改進都大為遜色。
1976 年CRAY-1 問世以後，向量計算機從此牢牢地控制著整個高性能計算機市場15 年。CRAY-1 對所使用的邏輯電路進行了精心的設計，採用了我們如今稱為RISC 的精簡指令集，還引入了向量寄存器，以完成向量運算。這一系列全新技術手段的使用，使CRAY-1 的主頻達到了80MHz。
微處理器隨著機器的字長從4 位、8 位、16 位一直增加到32 位，其性能也隨之顯著提高。正是因為看到了微處理器的這種潛力，卡內基- 梅隆大學開始在當時流行的DECPDP11 小型計算機的基礎上研製成功一台由16 個PDP11/40 處理機通過交叉開關與16 個共享存儲器模塊相連接而成的共享存儲多處理器系統C.mmp。
從80 年代開始，微處理器技術一直在高速前進。稍後又出現了非常適合於SMP 方式的匯流排協議，而伯克利加州大學則對匯流排協議進行了擴展，提出了Cache 一致性問題的處理方案。從此，C.mmp 開創出的共享存儲多處理器之路越走越寬；現在，這種體系結構已經基本上統治了伺服器和桌面工作站市場。
同一時期，基於消息傳遞機制的並行計算機也開始不斷涌現。80 年代中期，加州理工成功地將64 個i8086/i8087 處理器通過超立方體互連結構連結起來。此後，便先後出現了Intel iPSC 系列、INMOS Transputer 系列，Intel Paragon 以及IBM SP 的前身Vulcan 等基於消息傳遞機制的並行計算機。
80 年代末到90 年代初，共享存儲器方式的大規模並行計算機又獲得了新的發展。IBM將大量早期RISC 微處理器通過蝶形互連網路連結起來。人們開始考慮如何才能在實現共享存儲器緩存一致的同時，使系統具有一定的可擴展性（Scalability）。90 年代初期，斯坦福大學提出了DASH 計劃，它通過維護一個保存有每一緩存塊位置信息的目錄結構來實現分布式共享存儲器的緩存一致性。後來，IEEE 在此基礎上提出了緩存一致性協議的標准。
90 年代以來，主要的幾種體系結構開始走向融合。屬於數據並行類型的CM-5 除大量採用商品化的微處理器以外，也允許用戶層的程序傳遞一些簡單的消息；CRAY T3D是一台NUMA 結構的共享存儲型並行計算機，但是它也提供了全局同步機制、消息隊列機制，並採取了一些減少消息傳遞延遲的技術。
隨著商品化微處理器、網路設備的發展，以及MPI/PVM 等並行編程標準的發布，機群架構的並行計算機出現。IBM SP2 系列機群系統就是其中的典型代表。在這些系統中，各個節點採用的都是標準的商品化計算機，它們之間通過高速網路連接起來。
今天，越來越多的並行計算機系統採用商品化的微處理器加上商品化的互連網路構造，這種分布存儲的並行計算機系統稱為機群。國內幾乎所有的高性能計算機廠商都生產這種具有極高性能價格比的高性能計算機，並行計算機就進入了一個新的時代，並行計算的應用達到了前所未有的廣度和深度。
並行計算機隨著微處理晶元的發展，已經進入了一個新時代。目前並行計算機的性能已經突破20PFLOPS，正在向百億億次發展。我國並行計算機的研製已經走在世界前列。2003年由聯想公司生產的深騰6800 在2003 年11 月世界TOP500 排名中位列第14 名，2004 年曙光公司生產的曙光4000A 在2004 年6 月的世界TOP500 排名中位列第10 名，這是我國公開發布的高性能計算機在世界TOP500 中首次進入前十名，這標志著我國在並行計算機系統的研製和生產中已經趕上了國際先進水平，為提高我國的科學研究水平奠定了物質基礎。2013年國際超級計算機大會最新發布的世界超級計算機500強排名中，國防科技大學研製的天河二號超級計算機系統，以峰值計算速度每秒5.49億億次、持續計算速度每秒3.39億億次雙精度浮點運算的優異性能位居榜首。
從TOP500 的前10 名來看，美國仍然是超級計算機的最大擁有者。按照世界TOP500 的統計數據來分析，美國在計算能力上佔有近全世界的一半，在TOP500 中的所有計算機中擁有的數量超過50%。

『柒』 並行處理計算機系統的結構原理

並行處理計算機的結構主要有流水線方式 、多功能部件方式 、陣列方式、多處理機方式和數據流方式。 將指令的執行過程分解為若干段，每段進行一部分處理。一條指令順序流過所有段即執行完畢獲得結果。當本條指令在本段已被處理完畢而進入下段時，下條指令即可流入本段。因此，在整個流水線上可以同時處理若干條指令。若各段的執行時間均為一個時鍾節拍，則在正常情況下每拍可以輸出一個結果，即完成一條指令。這就可加快處理機的速度。
程序中相鄰指令的相關性會影響流水線處理機效率的發揮。例如，條件轉移指令在上條指令執行完以前，有時不能確定後繼指令；又如本條指令需要用上條指令的結果作為操作數等，都將中斷流水線而使效率下降。 一台處理機由多個相同的處理部件和一個統一的控制器組成。這個控制器解釋指令並傳送操作命令至全部處理部件。各處理部件按照控制器的命令同時進行完全相同的操作。陣列處理機又可分為浮點陣列處理機和位片式陣列處理機兩類。
ILLIAC-Ⅳ機屬於浮點陣列處理機，包括64個完全相同的處理部件(PU)和一個公共的控制部件(CU)。每個處理部件包括一個能執行64位浮點操作的處理單元(PE)和一個容量為2k字的存儲器(PM)。64個處理部件排列成8×8陣列。每個處理部件與四鄰處理部件均有直接數據通路。 在直接耦合多處理機系統中，實現處理機與存儲器、處理機與處理機之間連接的互連網路十分重要。互連網路有三種主要形式。
①匯流排結構：匯流排結構是多處理機系統中最為簡單的網路結構。實際的多處理機系統的互連網路，往往是在匯流排結構的基礎上發展起來的（圖3）。
②交叉開關結構：交叉開關由縱橫開關陣列組成，將橫向的處理機與縱向的存儲器模塊連接起來（圖4）。
③多埠存儲器結構：把交叉開關結構中的各交叉點上的開關移到相應存儲器的介面內部，形成多埠存儲器結構。 數據流處理機是受到人們重視的高度並行的處理機。它雖保留了存儲程序的做法，但在主要原理上已與諾依曼計算機結構不同。它不按程序計數器指出的指令順序執行程序，只要所需操作數全部具備，指令即可被執行,亦即程序的執行不是由控制流驅動,而是由數據流驅動。
數據流處理機是以語言為基礎的處理機。它使用數據流程序圖作為用戶語言與計算機結構之間的介面。數據流程序圖用能動框表示 。每個能動框有多個域 ，分別存放操作碼、操作數和目標地址。數據流程序以能動框集合的方式保存在能動存儲器中。當某條指令可以執行時，相應的能動框地址便被送入指令排隊器。讀取部件則按地址從存儲器中取出該能動框，形成操作包，送至操作部件進行處理，產生結果包。修改部件根據結果包的目標地址將結果數據送至規定的能動框作為操作數，並將具備操作數的指令的地址送至指令排隊器。指令排隊器中的指令均具備執行條件，因而只需增加部件數量或增強部件流水程度 ， 就可以高速並行執行。此外，還可將多個指令處理單元連接成數據流多處理機系統，進一步提高處理能力。
並行演算法和並行語言
提高並行處理效率的關鍵之一是並行演算法。演算法須適應計算機的結構。如果一種演算法所表達出來的並行度與計算機的並行度基本一致，便能提高計算機的解題效率。
在向量計算機中，提高並行度的主要問題在於把可並行處理的操作數用向量表示。許多常用的數值計演算法，如數列求和、矩陣乘、高斯消元、快速傅里葉變換等，已成功地在向量計算機上實現了並行處理。較為通行的並行語言基本上是FORTRAN語言的擴展。
在多處理機系統中，提高程序並行性的關鍵，是把任務分解成足夠多的可同時操作的進程。在程序語言中，還須擴充能明確表達進程並發性的語句，以便程序運行時能為相應的控制機構提供控制和管理手段，其中包括並行任務的派生、通信和調度。ADA 語言為描述多處理機並行程序結構提供了必要的語句。為適應數據流計算機而出現的若干數據流語言如Id語言和VAL語言已經在試用。 其重要特點是把數組看成是值而不是目標。用數據流語言編寫的程序能夠自然地表達出最大的運算並行性。

『捌』 畢業設計 我想闡述一下並行計算的發展

從20世紀40年代開始的現代計算機發展歷程可以分為兩個明顯的發展時代：串列計算時代、並行計算時代。每一個計算時代都從體系結構發展開始，接著是系統軟體（特別是編譯器與操作系統）、應用軟體，最後隨著問題求解環境的發展而達到頂峰。

並行計算機是由一組處理單元組成的。這組處理單元通過相互之間的通信與協作，以更快的速度共同完成一項大規模的計算任務。因此，並行計算機的兩個最主要的組成部分是計算節點和節點間的通信與協作機制。並行計算機體系結構的發展也主要體現在計算節點性能的提高以及節點間通信技術的改進兩方面。

節點性能不斷進步

20世紀60年代初期，由於晶體管以及磁芯存儲器的出現，處理單元變得越來越小，存儲器也更加小巧和廉價。這些技術發展的結果導致了並行計算機的出現。這一時期的並行計算機多是規模不大的共享存儲多處理器系統，即所謂大型主機。IBM 360是這一時期的典型代表。

到了20世紀60年代末期，同一個處理器開始設置多個功能相同的功能單元，流水線技術也出現了。與單純提高時鍾頻率相比，這些並行特性在處理器內部的應用大大提高了並行計算機系統的性能。伊利諾依大學和Burroughs公司此時開始實施Illiac Ⅳ計劃，研製一台64顆CPU的SIMD主機系統，它涉及到硬體技術、體系結構、I/O設備、操作系統、程序設計語言直至應用程序在內的眾多研究課題。不過，當一台規模大大縮小的原型系統（僅使用了16顆CPU）終於在1975年面世時，整個計算機界已經發生了巨大變化。

首先是存儲系統概念的革新，提出虛擬存儲和緩存的思想。以IBM 360/85和IBM 360/91為例，兩者是屬於同一系列的兩個機型，IBM 360/91的主頻高於IBM 360/85，所選用的內存速度也較快，並且採用了動態調度的指令流水線。但是，IBM 360/85的整體性能卻高於IBM 360/91，惟一的原因就是前者採用了緩存技術，而後者則沒有。

其次是半導體存儲器開始代替磁芯存儲器。最初，半導體存儲器只是在某些機器中被用作緩存，而CDC7600則率先全面採用這種體積更小、速度更快、可以直接定址的半導體存儲器，磁芯存儲器從此退出了歷史舞台。與此同時，集成電路也出現了，並迅速應用到計算機中。元器件技術的這兩大革命性突破，使得Illiac Ⅳ的設計者們在底層硬體以及並行體系結構方面提出的種種改進都大為遜色。

處理器高速發展

1976年Cray-1問世以後，向量計算機從此牢牢地控制著整個高性能計算機市場15年。Cray-1對所使用的邏輯電路進行了精心的設計，採用了我們如今稱為RISC的精簡指令集，還引入了向量寄存器，以完成向量運算。這一系列技術手段的使用，使Cray-1的主頻達到了80MHz。

微處理器隨著機器的字長從4位、8位、16位一直增加到32位，其性能也隨之顯著提高。正是因為看到了微處理器的這種潛力，卡內基·梅隆大學開始在當時流行的DEC PDP-11小型計算機的基礎上研製一台由16台PDP-11/40處理機通過交叉開關與16個共享存儲器模塊相連接而成的共享存儲多處理器系統C.mmp。

從20世紀80年代開始，微處理器技術一直在高速前進。稍後又出現了非常適合於SMP方式的匯流排協議。而伯克利加州大學則對匯流排協議進行了擴展，提出了Cache一致性問題的處理方案。從此，C.mmp開創出的共享存儲多處理器之路越走越寬。現在，這種體系結構已經基本上統治了伺服器和桌面工作站市場。

通信機制穩步前進

同一時期，基於消息傳遞機制的並行計算機也開始不斷涌現。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.2 有限元並行計算的發展和現狀
目前，在計算力學領域內，圍繞著基於變分原理的有限元法
和基於邊界積分方程的邊界元法，以及基於現在問世的各種並行
計算機，逐漸形成了一個新的學科分支——有限元並行計算。它
是高效能的，使得許多現在應用串列計算機和串列演算法不能解決
或求解不好的大型的、復雜的力學問題能得到滿意的解答，故其
發展速度十分驚人。在國際上已經掀起了利用並行機進行工程分
析和研究的高潮。從1975到1995年的二十年間，有關有限元方法
和相應的數值並行計算的文章已發表1000餘篇。
有限元並行計算正在向兩個方向發展。一是對系統方程組實
施並行求解的各種演算法。二是並行分析方法，包括有限元並行算
法和邊界元並行演算法，前者趨向成熟，而後者的研究較少。對這
一方面的研究，是為了挖掘有限元計算自身潛在的並行性，是有
限元並行計算的根本問題。
1.2.1國內
並行演算法的設計和有效實現強烈地依賴於並行機的硬軟體環
境。國內僅極少數單位擁有並行機，且機型雜亂，因此研究人員
少，起步晚，而且局限於特定的硬體環境。從有限元分析方法的
內容來看，發表的幾十篇研究論文（報告）還未顯示出較強的系
統性。
1）南京航空航天大學周樹荃教授等在YH-1向量機上實現了剛度
矩陣計算、對稱帶狀矩陣的Cholesky分解和線性方程組的求解等
並行處理。針對不規則結構工程分析問題，他們還採用了變帶寬
存貯方法，並實現了剛度矩陣的並行計算以及求解變帶寬稀疏線
性方程組的並行直接解法【20】。
2）中國科學院計算中心王藎賢研究員等在基於Transputer晶元
的分布式MIMD系統上，提出了有限元分析中變帶寬線性方程組的
並行直接解法，初步完成了一個靜力分析程序【21】。
3）重慶大學張汝清教授等藉助於ELXSI-6400共享存貯器型MIMD
系統，先後開展了范圍比較廣泛的並行演算法研究，主要成果有：
a)提出了靜力分析中子結構解法的並行演算法，以及動力分析中模
態綜合子結構法的並行演算法；
b)從波前法出發，發展了多波前並行演算法以求解大型結構分析
問題；
c)從Jacobi塊迭代法和加權殘差法出發，導出了基於非同步控制的
有限元方程並行解法和有限元並行迭代的基本格式；
d)利用圖論中的著色理論，實現了剛度矩陣的並行計算；
e)實現了基於有色線剖分的SOR並行迭代解法；
f)實現了子空間迭代法、Lanczos法以及利用多項式割線迭代法
和矢量迭代法求解結構固有頻率和模態的並行演算法；
g)針對彈塑性分析，提出了一種多波前子結構並行演算法；
h)針對彈性接觸問題，提出了一種基於參數變分原理的並行解法；
i)實現了一步積分法的並行處理【22】。
4）南京航空航天大學喬新教授等藉助於Transputer晶元的分布式
MIMD系統實現了有限元方程組的並行直接解法，並提出了基於子結
構的預處理共軛梯度法的並行計算方法【23】。
此外，浙江大學姚堅【24】、中國科學院西南計算中心馬寅國、
東北工學院張鐵以及國防科技大學六系也曾對有限元分析的並行計
算開展了一些研究。
上述研究結果表明，國內並行計算方法的研究，在硬體上基於
向量機、分布式並行機和共享存貯式並行機；在內容上，似乎面很
廣，但系統性和深度還很不夠，軟體開發距實際應用和商品化還有
很大距離，對不依賴並行機具體環境的通用並行演算法研究還很少，
同樣對旨在進行結構有限元分析的並行計算的硬體研究也很少。
1.2.2國外
自從美國國家宇航局（NASA）的A.K.Noor於1975年發表第一篇
有限元並行計算的文章以來，有限元並行處理技術幾乎與並行計算
機同步發展。距不完全統計，到1992年，國外已發表了400餘篇這方
面的論文，其中後5年的文章篇數是前12年的總和。在研究內容上也
由過去的演算法研究發展到了演算法、軟體和硬體相結合的研究，並針對
一些機型開發了一些實用的大型結構分析軟體。
1）有限元機器FEM【25】（Finite Element Machine）。早在70年
代末，就有人發表了有關FEM的論文，1982年美國國家宇航局Langley
研究中心的O.O.Storaasli等撰文詳細地介紹了該中心設計的供研究
用的FEM。該機器由1個處理器陣列、1台作為控制器的微機和1個並行
操作系統及一些模塊化了的通用並行演算法程序組成，用戶使用系統的
文本編輯器和控制器的其它特殊功能，能建立有限元計算模型並進行
分析。10多年來，又有一些人在這一方面進行了不懈的努力，但FEM
的發展前景仍然不太令人樂觀。
2）心動陣列並行機【26】。心動陣列並行機主要應用於信號和圖象
的並行處理，但由於其高效的矩陣計算功能，近年來有人把它應用於
有限元分析，並作了一些有益的嘗試。
3）巨型向量機【27】。在有限元分析中越來越顯示出巨大的威力，
處於領先的是美國思維公司的CM-2。許多結構分析家把這個具有65536
個處理器的巨型向量機應用於有限元計算，如T.Belyschko等人採用顯
式方法，完成了具有32768個單元的殼的非線性有限元計算，並行效率
極高，速度幾乎比CRAY X-MP/14並行機高出1個數量級。
4）並行機網路和工作站網路【28】。日本東京大學矢川等藉助高速網
絡把3台CRAY Y-MP機聯成網路進行有限元分析，有限元方程求解採用
的是基於區域分裂技術的共軛梯度法（CGM）， 在求解三維彈性問題
時自由度個數超過了100萬，系統平均運行速度高達1.74GFLOPS。另外，
他們還基於一個工程工作站網路，在並行環境下進行了類似的研究，
求解問題的自由度數高達20萬個。
--
我左看右看前看後看可還是看不過來
這個....那個....我越看越奇怪....
不是我不明白，這世界變化快

『玖』 如何利用4位並行算術邏輯運算單元74LS181實現16位二進制數運算有哪些解決方案

實驗中所用的運算器數據通路圖如圖3.1-1。圖中所示的是由兩片74LS181 晶元以並/串形式構成的8 位字長的運算器。右方為低4 位運算晶元，左方為高4 位運算晶元。低位晶元的進位輸出端Cn+4 與高位晶元的進位輸入端Cn 相連，使低4 位運算產生的進位送進高4位運算中。低位晶元的進位輸入端Cn 可與外來進位相連，高位晶元的進位輸出引至外部。兩個晶元的控制端S0～S3 和M 各自相連。為進行雙操作數運算，運算器的兩個數據輸入端分別由兩個數據暫存器DR1、DR2（用鎖存器74LS273 實現）來鎖存數據。要將內匯流排上的數據鎖存到DR1 或DR2 中，則鎖存器74LS273 的控制端LDDR1 或LDDR2 須為高電平。當T4 脈沖來到的時候，匯流排上的數據就被鎖存進DR1 或DR2 中了。為控制運算器向內匯流排上輸出運算結果，在其輸出端連接了一個三態門（用74LS245 實現）。若要將運算結果輸出到匯流排上，則要將三態門74LS245 的控制端ALU-B 置低電平。否則輸出高阻態。數據輸入單元(實驗板上印有INPUT DEVICE)用以給出參與運算的數據。其中，輸入開關經過一個三態門（74LS245）和內匯流排相連，該三態門的控制信號為SW-B，取低電平時，開關上的數據則通過三態門而送入內匯流排中。匯流排數據顯示燈（在BUS UNIT 單元中）已與內匯流排相連，用來顯示內匯流排上的數據。控制信號中除T4 為脈沖信號，其它均為電平信號。由於實驗電路中的時序信號均已連至「W/R UNIT」單元中的相應時序信號引出端，因此，需要將「W/R UNIT」單元中的T4 接至「STATE UNIT」單元中的微動開關KK2 的輸出端。在進行實驗時，按動微動開關，即可獲得實驗所需的單脈沖。圖3.1-1 運算器通路圖 S3、S2、 S1、S0 、Cn、M、LDDR1、LDDR2、ALU-B、SW-B 各電平控制信號則使用「SWITCH UNIT」單元中的二進制數據開關來模擬，其中Cn、ALU-B、SW-B 為低電平有效，LDDR1、LDDR2 為高電平有效。對於單匯流排數據通路，作實驗時就要分時控制匯流排，即當向DR1、DR2 工作暫存器打入數據時，數據開關三態門打開，這時應保證運算器輸出三態門關閉；同樣，當運算器輸出結果至匯流排時也應保證數據輸入三態門是在關閉狀態。四、實驗步驟（1）按圖2.6-2 連接實驗電路並檢查無誤。圖中將用戶需要連接的信號線用小圓圈標明（其它實驗相同，不再說明）。（2）開電源開關。（3）用輸入開關向暫存器DR1 置數。①撥動輸入開關形成二進制數01100101（或其它數值）。（數據顯示燈亮為0，滅為1）。②使SWITCH UNIT 單元中的開關SW-B=0（打開數據輸入三態門）、ALU-B=1（關閉 ALU 輸出三態門）、LDDR1=1、LDDR2=0。③按動微動開關KK2，則將二進制數01100101 置入DR1 中。（4）用輸入開關向暫存器DR2 置數。①撥動輸入開關形成二進制數10100111（或其它數值）。②SW-B=0、ALU-B=1 保持不變，改變LDDR1、LDDR2，使LDDR1=0、LDDR2=1。③按動微動開關KK2，則將二進制數10100111 置入DR2 中。（5）檢驗DR1 和DR2 中存的數是否正確。①關閉數據輸入三態門（SW-B=1），打開ALU 輸出三態門（ALU-B=0），並使LDDR1=0、LDDR2=0，關閉寄存器。②置S3、S2、 S1、S0 、M 為1 1 1 1 1，匯流排顯示燈則顯示DR1 中的數。③置S3、S2、 S1、S0 、M 為1 0 1 0 1，匯流排顯示燈則顯示DR2 中的數。（6）改變運算器的功能設置，觀察運算器的輸出。①SW-B=1、ALU-B=0 保持不變。②按表2-2 置S3、S2、 S1、S0 、M、Cn 的數值，並觀察匯流排顯示燈顯示的結果。例如：置S3、S2、 S1、S0 、M、Cn 為1 0 0 1 0 1，運算器作加法運算。置S3、S2、 S1、S0 、M、Cn 為0 1 1 0 0 0，運算器作減法運算。（7）驗證74LS181 的算術運算和邏輯運算功能（採用正邏輯）在給定DR1=65、DR2=A7 的情況下，改變運算器的功能設置，觀察運算器的輸出，填入下表中，並和理論分析進行比較、驗證。圖3.1-2 算術邏輯實驗連線這個是2片181組成8位的ALU