創(chuàng)新計算機(jī)體系結(jié)構(gòu)設(shè)計的 法分析 創(chuàng)新計算機(jī)體系結(jié)構(gòu)設(shè)計的 法分析 摘要 為了設(shè)計專注于高性能計算的新型計算機(jī)體系結(jié)構(gòu)，需要研究典型應(yīng)用，藉此了解系統(tǒng)結(jié)構(gòu)應(yīng)具備的主要特性。 本文 作為設(shè)計創(chuàng)新高性能計算機(jī)體系結(jié)構(gòu)的準(zhǔn)備工作的一部分，針對應(yīng)用 程序 在計 算和訪存等方面的特性，給出 了 專為 題中的 法 而 優(yōu)化的體系結(jié)構(gòu)設(shè)計策略 。 近年來出現(xiàn)的一些新型計算機(jī)體系結(jié)構(gòu)都不約而同的把注意力放在了提高硬件執(zhí)行效能之上，為此這些新型計算機(jī)體系往往針對某些特定范圍的應(yīng)用做了優(yōu)化。 類似于 體系 結(jié)構(gòu) 中，由于 存在 針對圖形處理優(yōu)化的體系 設(shè)計 和特殊硬件， 其 在圖形相關(guān)的領(lǐng)域 有著 非常好的應(yīng)用。 而 諸如類 的 可重構(gòu)體系結(jié)構(gòu)， 往往 具有 粗顆 粒度的 動態(tài) 可重構(gòu) 的硬件設(shè)計 ， 從而 能夠針對不同應(yīng)用 的 特點 ，動態(tài)的 給予硬件相應(yīng)的優(yōu)化配置，保證硬件總能最大程度的發(fā)揮自身的 性能。 依照 以上 所述的基于應(yīng)用分析的 研究方法 ，本 文選取了 題這樣一個應(yīng)用范疇作為分析對象。 題又稱多體問題， 是天體物理學(xué) 、流體力學(xué)以及 分子動力學(xué)的基本問題之一，用來模擬一個系統(tǒng)中 相互作用的粒子 的運動規(guī)律 。一般可以被描述為： 在 一定的空間中，分布著 多個 粒子，每對粒子之間都存在著相互作用力（如萬有引力、庫侖力等），使這些粒子發(fā)生運動。它們的初始位置和速度是已知的，每隔一定的 時間， 通過 計算粒子之間的作用力，來更新它們的位置和速度。 題早在三百多年前已被提出，幾百年來人們經(jīng)過對它的 不斷研究和實驗，已經(jīng)總結(jié)出相當(dāng)成熟和可靠的算法。隨著科技的不斷發(fā)展， 題的規(guī)模也隨之不停地擴(kuò)大，現(xiàn)今已 達(dá)到了 上億、甚至上百億 的規(guī)模。這 樣大規(guī)模的運算對計算機(jī)的運算 速度提出了非常大 的挑戰(zhàn)， 因此， 題是高性能計算領(lǐng)域最具代表性、 影響力和 挑戰(zhàn)性的問題之一。 問題的常見算法有如下幾種 ：直接套用公式計算的 法；使用密 度網(wǎng)格計算勢能的 法；把計算劃分為遠(yuǎn)程區(qū)域與近程區(qū)域的 法。 其中 法又包括 法 以及改進(jìn)型的 法 。為了從這些算法中挑選出具有代表性的 文從時間復(fù)雜度和計算精度 等 幾個方面對它們進(jìn)行了分析。 法是最直接 最簡單 的算法，時間復(fù)雜度為 O( 法是一種在粒子系統(tǒng)里計算引力的方法，它的基本原理是把一個由粒子組成的系統(tǒng)轉(zhuǎn)換成一個密度 的網(wǎng)格（或“篩”），通過該密度網(wǎng)格求解得到 勢能，然后，根據(jù)粒子在網(wǎng)格中所處的單元以及在單元中的位置，將力應(yīng)用到每個粒子上去。 它的 時間復(fù)雜度是 O(其中 離散網(wǎng)格大小 。但 此只適用于粒子彼此之間距離較遠(yuǎn)的系統(tǒng)。 法應(yīng)用樹形結(jié)構(gòu)對空間進(jìn)行劃分，并以此將 題的計算劃分為近程與遠(yuǎn)程。它被廣泛地應(yīng)用于天體力學(xué)?？煽焖儆嬎愀鼽c受到的力，計算復(fù)雜度為 O( 雖然 該算法的 誤差范圍 小于 1%， 但也只能 夠處理天體力學(xué) 范疇 的問題。 法 則 是對 法的改進(jìn)，區(qū)別于 法在每個結(jié)點處直接計算作用力， 法通過 計算 多項展開式的方法 來實現(xiàn) 不同區(qū)域 之間 勢能 的轉(zhuǎn)換 ，即 通過計算 及它們之間的轉(zhuǎn)換， 法可以將 題的時間復(fù)雜度降低到O(N)。 同時 ， 通過控制 法中多項展開式的截斷值 ， 還 能夠依據(jù) 不同應(yīng)用 對精度的不同需求 控制 其 計算精度。 以此 ， 本文認(rèn)為 法相較于 法和 法 更具有 優(yōu)勢， 創(chuàng)新計算機(jī)體系結(jié)構(gòu)設(shè)計的 法分析 更加適合 作為 新型 高性能計算 機(jī) 的典型應(yīng)用加以分析。 一個流體力學(xué)的應(yīng)用程序， 它通過使用 法來 模擬二維空間中的 畢奧薩伐爾 （ 方程。 在流體力學(xué)中，可以把流體看作是由大量的粒子所組成，并通過計算眾多粒子的速度，來模擬 程或者 程，這種方法叫做渦流質(zhì)點方法（ 由于渦流粒子的數(shù)量巨大，各自計算又相互獨立且依賴粒子間的相互作用，因此可以看作是 題加以解決。 是依據(jù)渦流質(zhì)點方法設(shè)計出的應(yīng)用程序，用來計算在二維空間中高斯分布下 的渦流粒子按照畢奧薩伐爾定律發(fā)生的速度變化。 C+實現(xiàn)，以 基礎(chǔ)設(shè)計了相關(guān)的數(shù)據(jù)結(jié)構(gòu)和算法，并初步實現(xiàn)了 的并行。 用四叉樹結(jié)構(gòu)對二維空間進(jìn)行劃分，并 據(jù)此劃分 出近程區(qū)域與遠(yuǎn)程區(qū)域。 在此基礎(chǔ)之上， 照先自底向上再自頂向下的順序 執(zhí)行算法 ，依次為 ： 生成底層劃分的 照劃分層次從下往上傳遞 每層劃分中轉(zhuǎn)換 遠(yuǎn)程區(qū)域的 上往下傳遞 后由 換到每個粒子的速度。 用中涉及到四叉樹、本地列表和交互列表等數(shù)據(jù)結(jié)構(gòu)，本文對他們的 內(nèi)存占用做了定量分析。 為了探討 算和訪存的特點，針對 序中的各個階段， 本文還 給出了定量的計算量和訪存量分析。最后 根據(jù) 以上分析， 初步給出了針對 法優(yōu)化的體系結(jié)構(gòu)方案 ，包括計算單元的種類與數(shù)量、訪存單元的配置比例和片上緩存的設(shè)計 策略，具體包括：運算器陣列以雙精度 基本運算單元；需要放置特殊運算單元以滿足雙精度除法和自然指數(shù)運算的需要；為了保證不出現(xiàn)訪存瓶頸，至少需要為每個運算器陣列配置一個獨立的訪存單元；片上緩存應(yīng)設(shè)計為可編程而不是一般 的 構(gòu) ；針對片上緩存的大小，需要調(diào)整算法迭代的次序和并行計算分塊的策略 。 最后，本文 還 指出了在體系機(jī)構(gòu)設(shè)計 的后續(xù)階段 ， 法分析還需要繼續(xù)跟進(jìn)的一些 工作。 關(guān)鍵詞： 體系結(jié)構(gòu)、高 性能計算， 題 ， 法 創(chuàng)新計算機(jī)體系結(jié)構(gòu)設(shè)計的 法分析 o we to of As of an of on of as to a in to do to a a be to In to of In in a of is of to be to is of of is to a of of as be as in a of of a by or of if in of is at of we of at or of of in is in be of in a to s as a we as a of to of be a 創(chuàng)新計算機(jī)體系結(jié)構(gòu)設(shè)計的 法分析 to a to in TM H (is H 3M, 3M PP is a ( PM a to of to to PM ( in g of As a M BH a or an to BH is in a of BH as In to H an is of H to MM we to It (N) to On MM be by of MM it be to of M H is we a to do is an to of MM to in In of be by of in it in is as a to is In a of be as is in a is an +, to It a to in on by of an as a to as of we to In P In a to to to at of to in At to of 2M ( 2P ( as as of in a MM is is on by a of 創(chuàng)新計算機(jī)體系結(jié)構(gòu)設(shè)計的 法分析 in to of of at is to be as a to of MM to be At as a a is to be in to of of 創(chuàng)新計算機(jī)體系結(jié)構(gòu)設(shè)計的 法分析 第 1 頁 共 2 頁 目 錄 第一章 緒論 . 1 法 . 1 M 算法（ 子網(wǎng)格算法） . 1 M 算法（ 結(jié)構(gòu)算法） . 2 合算法 . 2 種新型高性能計算機(jī)體系結(jié) 構(gòu) . 2 重構(gòu)專用處理器 . 2 用計算圖形處理器 . 3 結(jié) . 3 第二章 法過程分析 . 3 M 算法 . 4 法概述 . 4 法分析 . 4 H 算法 . 4 法概述 . 5 法分析 . 5 法 . 6 法概述 . 6 法分析 . 7 結(jié) . 7 第三章 法應(yīng)用分析 . 7 用簡介 . 8 據(jù)結(jié)構(gòu)分析 . 8 于四叉樹的空間劃分 . 8 居列表、本地列表與交互列表 . 9 法流程分析 . 11 始化 . 11 底向上運算 . 11 頂向下運算 . 12 算量、訪存量分析 . 12 階段計算量 . 13 階段訪存量 . 13 階段訪存計算比 . 14 對新型體系結(jié)構(gòu)的分析 . 15 算單元配置 . 15 存單元配置 . 15 上緩存配置 . 15 結(jié) . 16 創(chuàng)新計算機(jī)體系結(jié)構(gòu)設(shè)計的 法分析 第 2 頁 共 2 頁 第四章 結(jié)論 . 16 參考文獻(xiàn) . 17 謝辭 . 18 創(chuàng)新計算機(jī)體系結(jié)構(gòu)設(shè)計的 法分析 第 1 頁 共 18 頁 第一章 緒論 題又稱多體問題， 是天體物理學(xué) 、流體力學(xué)以及 分子動力學(xué) 的基本問題之一 ，用來 模擬 一個系統(tǒng)中 N 個 相互作用的 粒子 的運動規(guī)律 。一般 可以 被描述為： 在 一定的空間中，分布著 N 個粒子 ，每對 粒子 之間 都 存在著 相互作用力（如 萬有引力 、庫侖力等）， 使這些粒子 發(fā)生運動。 它 們的初始位置和速度是已知的，每隔一定的 時間 ， 通過 計算 粒子 之間的作用 力 ， 來 更新 它 們的位置和速度 1。 題早在三百多年前已被提出，幾百年來人們經(jīng)過對多體問題不斷地研究和實驗，已經(jīng)總結(jié)出相當(dāng)成熟和可靠的算法。隨著科技的不斷發(fā)展， 題的規(guī)模也隨之不 停地擴(kuò)大，現(xiàn)今已 達(dá)到了上億、 甚至上 百 億的規(guī)模。這 樣 大規(guī)模的運算對計算機(jī)的運算 速度提出了很 高的挑戰(zhàn)， 而 題 中 各 對作用力計算 相互獨立的特性 ，表明其更適合應(yīng)用并行計算的方法來解決。 因此， 題是高性能計算領(lǐng)域最具代表性、最有影響力以及最有挑戰(zhàn)性的問題之一。 為了設(shè)計出 創(chuàng)新 高性能計算機(jī)體系結(jié)構(gòu)，需要通過分析 樣的典型應(yīng)用，找出其 對計算、存儲和通信等特性 的要求，從而以應(yīng)用自身為出發(fā)點，提出針對應(yīng)用 優(yōu)化的 體系結(jié)構(gòu) 設(shè)計方案。 法 題可以被看作是 一組已知初始值的常微分方程組，即已知初始值，在 i 不等于 j 時 ，解出下列二階常微分方程組 1： 3() , 1 , 2 , . . . ,n i j j m q qm q j (1) 在公式 (1)中， 代表 n 個質(zhì)點質(zhì)量的常量。 , 21是以時間 t 為變量描述質(zhì)點位置的三維矢量函數(shù)。 題的數(shù)值模擬實 質(zhì)上是求解關(guān)于時間的常微分方程組。 通常將直接計算公式 (1)的方法稱為 法（ 法），在每個時間步迭代時都需要計算每對粒子之間的相互作用，其時間復(fù)雜度為 O( 法的優(yōu)點是精確度高，并且易于并行化處理。但其缺點也很明顯，就是算法復(fù)雜度較高 ，當(dāng)問題規(guī)模很大時，使用這種算法模擬問題的效率很低。因此，找到時間復(fù)雜度更低的 題算法是高性能計算領(lǐng)域的挑戰(zhàn)之一，至今 學(xué)術(shù)界 已提出了下面 幾類優(yōu)化算法 2： M 算法（ 子網(wǎng)格算法） 法是一種在粒子系統(tǒng)里計算引力的方法，它的基本原理是把一個由粒子組成的 系統(tǒng)轉(zhuǎn)換成一個密度的網(wǎng)格（或“篩”），通過該密度網(wǎng)格求解得到 勢能，然后，根據(jù)粒子在網(wǎng)格中所處的單元以及在單元中的位置， 再 將 作用 力應(yīng)用到每個粒子上去 3。 在離散的網(wǎng)格空間中，假設(shè)粒子分布在網(wǎng)格頂點間，這種情況下，計算勢能比較容易，因為泊松等式 ，即公式 (2)中， 2 4 G (2) 是勢能函數(shù)， G 是牛頓常量， 是密度，即網(wǎng)格內(nèi)粒子的數(shù)量，用快速傅立葉變換（ 換成更簡單的公式 (3)。 創(chuàng)新計算機(jī)體系結(jié)構(gòu)設(shè)計的 法分析 第 2 頁 共 18 頁 24 G (3) 其中， k 代表了共動波數(shù) (作用在粒子上的力可以取勢能函數(shù)的梯度獲得。 法的優(yōu)點是速度很快，時間復(fù)雜度是 O(其中 離散網(wǎng)格大小。 法的缺點是，如果粒子之間的距離較小，用這種方法計算得到的粒子之間的力是不精確的，它只能用于計算長距離間粒子互相作用的力 3。 M 算法（ 結(jié)構(gòu)算 法） 法也 叫多層算法，是一種 經(jīng)過 改進(jìn) 的 法 2。在這種算法中，粒子被分為遠(yuǎn)程粒子和鄰近粒子。遠(yuǎn)程粒子的受力計算是用了近似計算的方法將遠(yuǎn)程粒子團(tuán)（簇）的作用近似地看成一個粒子的作用從而減少計算量，其本質(zhì)上是把大系統(tǒng)切成小立方體，只計算小立方體之間的引力，這樣原來 1000 個點，可能只切成 10 個立方體，從而大大降低計算復(fù)雜度。近距離的粒子（鄰近粒子）則采用 法。在實際過程中近距離的粒子要比遠(yuǎn)程的粒子少的多，因此影響算法復(fù)雜度的主要因素是對遠(yuǎn)程粒子的計算。近距離的粒子雖然使用了法，但是由于所占 的比重微乎其微，并不會對算法的效率產(chǎn)生重大的影響。因此，采用 法有利于快速計算和并行劃分。 法中的典型算法包括 法（ 4和 法（ 速多極子算法） 5。 法可快速計算各點受到的力，時間復(fù)雜度為O(但 誤差 通常只有 過對于某些研究領(lǐng)域來說，如天體力學(xué)，這個精度已足夠。 法通過層次劃分和位勢函數(shù)的多極子（ 開計算各點位勢，以 O(N) 的時間復(fù)雜度可達(dá)到任 意精度。 采用樹結(jié)構(gòu)的算法還有 法和 法，而 法是 法和多極子算法的結(jié)合。 合算法 除了上述兩種主要的算法外，也有混合各種算法以達(dá)到更好計算效果的嘗試。 法 3、 3M3（自適應(yīng)網(wǎng)格）、 （粒子樹 法等都是 混合算法。通常，在混合算法中， 于計算遠(yuǎn)程粒子之間的力，而直接計算粒子之間的力的 法則用于計算鄰近 粒 子之間的力。 種新型 高性能計算機(jī)體系結(jié)構(gòu) 近年來出現(xiàn)了幾種新型的高性能計算機(jī)體系 結(jié)構(gòu) ， 它們不約而同的把關(guān)注點放 在了提高性能功耗比、性能價格比之上。這些 新型體系結(jié)構(gòu)的共同點在于它們都是 通過前期的應(yīng)用分析和巧妙的硬件配置， 設(shè)計出針對特定 范圍的 應(yīng)用優(yōu)化 過 的體系結(jié)構(gòu)， 以此來充分利用高性能計算機(jī)的處理能力 。常見的幾種新型高性能計算機(jī)體系結(jié)構(gòu) 包括：可重 構(gòu)專用處理器 、通用計算圖形處理器等。 重構(gòu)專用處理器 可重構(gòu)處理器 是 指 硬件上具有可編程特性的一類處理器，他們的芯片中具有 可配置 的 硬件 控制點， 處理器依賴 于 不同的 硬件配置 來滿足特定的計算 需求 ， 以 最大限度的發(fā)揮硬件性能。 可重構(gòu)處理器不同于 等傳統(tǒng)可重構(gòu) 硬件的關(guān)鍵在于，可重構(gòu)處理器 往往是 粗顆粒度上的可重構(gòu)， 且通常 只有部分可重構(gòu) ，并 具有 動態(tài)可重構(gòu) 的特性 。 因而 可重構(gòu)專用處理器不僅可以為某個特定 應(yīng)用提供類似于專用處理器的性能，而且能夠根據(jù)不同應(yīng)用的特性 動態(tài) 調(diào)整硬件體系，以保證處理器的通用性。 典型的可重構(gòu)專用處理器 如 和 等。 專為具有數(shù)據(jù) 級 并行、計算高度規(guī)則和吞吐量巨大 這三種特性的 一類應(yīng)用設(shè)計的新型體系結(jié)構(gòu)， 主要應(yīng)用 于 圖像處理和視頻壓縮等領(lǐng)域 6。 它 由 一塊可重構(gòu) 的 處理器陣列、 一顆 通用 處理器 和一組高帶寬的訪存部件組成。其中通用處理器 為一顆 心 ， 用以執(zhí)行輸入的程序 ， 并根據(jù)程序邏輯 動態(tài)的 控制可 重構(gòu)處理器陣列的配置 與計算 ，從而 實現(xiàn) 針對不同應(yīng)用的動態(tài)可重構(gòu)。 為 一顆 典型的 可重構(gòu)處理器，具有粗顆粒度可重構(gòu)，部分 可重構(gòu)和動態(tài)可重構(gòu)的特點。 創(chuàng)