[發(fā)明專(zhuān)利]基于多核處理器的通用并行加速算法

在審

• 申請(qǐng)?zhí)枺?/td>: 201110165740.7
• 申請(qǐng)日: 2011-06-20
• 公開(kāi)（公告）號(hào): CN102214086A
• 公開(kāi)（公告）日: 2011-10-12
• 發(fā)明（設(shè)計(jì)）人: 曹偉;王伶俐;王穎;周學(xué)功;葉曉敏
• 申請(qǐng)（專(zhuān)利權(quán)）人: 復(fù)旦大學(xué)
• 主分類(lèi)號(hào): G06F9/38
• 分類(lèi)號(hào): G06F9/38;G06F9/50
• 代理公司: 上海正旦專(zhuān)利代理有限公司 31200
• 代理人: 陸飛;盛志范

1.一種基于多核處理器的通用并行加速算法，其特征在于依次包括識(shí)別并分解大規(guī)模數(shù)據(jù)計(jì)算的過(guò)程，調(diào)度分配計(jì)算序列至處理器計(jì)算核心執(zhí)行的過(guò)程，收集重組計(jì)算結(jié)果的過(guò)程；其中：

所謂識(shí)別并分解大規(guī)模數(shù)據(jù)計(jì)算的過(guò)程，是對(duì)于大規(guī)模、高密度數(shù)據(jù)計(jì)算，將數(shù)據(jù)相關(guān)性低或者沒(méi)有數(shù)據(jù)相關(guān)性的計(jì)算過(guò)程并分解為獨(dú)立的計(jì)算序列；

所謂調(diào)度分配計(jì)算序列至處理器計(jì)算核心執(zhí)行的過(guò)程，是將分解后獨(dú)立的計(jì)算序列分配到多核處理器的各計(jì)算核心上執(zhí)行；

所謂收集重組計(jì)算結(jié)果的過(guò)程，是在各計(jì)算核心執(zhí)行結(jié)束計(jì)算序列后，將各計(jì)算結(jié)果片段回收按序重新組合成完整的計(jì)算結(jié)果，實(shí)現(xiàn)計(jì)算性能加速。

2.根據(jù)權(quán)利要求1所述的基于多核處理器的通用并行加速算法，其特征在于所述識(shí)別并分解大規(guī)模數(shù)據(jù)計(jì)算的過(guò)程，包括：

（一）、數(shù)據(jù)輸入和計(jì)算過(guò)程描述?：構(gòu)建電路時(shí)序圖?

在基于塊的SSTA計(jì)算過(guò)程中，先將電路網(wǎng)表轉(zhuǎn)換成反映電路拓?fù)浣Y(jié)構(gòu)的時(shí)序圖，時(shí)序圖由節(jié)點(diǎn)集V和邊集E組成，節(jié)點(diǎn)集V中的節(jié)點(diǎn)代表電路網(wǎng)表中的門(mén)及輸入輸出等，邊集E中的邊代表在電路網(wǎng)表中的門(mén)及輸入輸出之間的連接；然后遍歷時(shí)序圖，對(duì)每個(gè)節(jié)點(diǎn)的不同配置進(jìn)行SUM和MAX操作，獲得分析結(jié)果；

時(shí)序圖是有向無(wú)環(huán)圖，使用空間復(fù)雜度為O(V+E)的鄰接數(shù)組來(lái)描述時(shí)序圖的數(shù)據(jù)結(jié)構(gòu)；鄰接數(shù)組表示的時(shí)序圖由兩個(gè)數(shù)組構(gòu)成：包含節(jié)點(diǎn)信息的節(jié)點(diǎn)數(shù)組以及包含邊信息的邊數(shù)組；將CPU端的時(shí)序圖轉(zhuǎn)換成GPU端CUDA模型使用的鄰接數(shù)組的形式，分為兩步：

（1）對(duì)CPU端的時(shí)序圖中的節(jié)點(diǎn)進(jìn)行廣度優(yōu)先遍歷，遍歷時(shí)對(duì)節(jié)點(diǎn)進(jìn)行編號(hào)并分層；

（2）按層次訪問(wèn)CPU端的時(shí)序圖中的節(jié)點(diǎn)，將節(jié)點(diǎn)信息和邊信息添加到節(jié)點(diǎn)數(shù)組Va和邊數(shù)組Ea中；

訪問(wèn)時(shí)序圖中的節(jié)點(diǎn)v并向Va和Ea添加信息進(jìn)行以下操作：

（1）獲得v在時(shí)序圖中的編號(hào)，將其設(shè)置為v在Va中的索引；

（2）遍歷v的前驅(qū)節(jié)點(diǎn)，將前驅(qū)節(jié)點(diǎn)的編號(hào)加入到邊數(shù)組Ea中；

（3）設(shè)置v在Va中的值，為v的第一個(gè)前驅(qū)節(jié)點(diǎn)在Ea中的索引；若v的前驅(qū)節(jié)點(diǎn)數(shù)量為0，則設(shè)為-1；

（二）、到達(dá)時(shí)間計(jì)算過(guò)程的分解

在SSTA中，一個(gè)門(mén)的輸出的到達(dá)時(shí)間（簡(jiǎn)稱(chēng)為AT）的計(jì)算過(guò)程是：首先對(duì)每個(gè)輸入管腳i的到達(dá)時(shí)間與從輸入管腳i到輸出的延時(shí)求和（SUM），然后對(duì)所有求出的和求最大值（MAX），得到當(dāng)前門(mén)的輸出的到達(dá)時(shí)間：

AT?=?MAX{(AT_ini?+?Delay_ini-out)},i=0,…,n

其中n表示輸入的個(gè)數(shù)。

3.根據(jù)權(quán)利要求2所述的基于多核處理器的通用并行加速算法，其特征在于所述調(diào)度分配計(jì)算序列至處理器計(jì)算核心執(zhí)行的過(guò)程，是將上一步驟得到的各計(jì)算單元分配到多核處理器的各個(gè)計(jì)算核心上并行執(zhí)行；在執(zhí)行過(guò)程中通過(guò)調(diào)度線程實(shí)現(xiàn)負(fù)載平衡，并且動(dòng)態(tài)管理內(nèi)存，實(shí)現(xiàn)內(nèi)存對(duì)齊。

4.根據(jù)權(quán)利要求3所述的基于多核處理器的通用并行加速算法，其特征在于所述收集重組計(jì)算結(jié)果的過(guò)程，是將上一步驟得到的各計(jì)算結(jié)果按照?qǐng)D表示中的對(duì)應(yīng)關(guān)系，進(jìn)行重新組合成完整的計(jì)算結(jié)果：把各計(jì)算核的SUM結(jié)果相加求和得到完整的SUM結(jié)果；把各計(jì)算核的MAX結(jié)果進(jìn)行簡(jiǎn)單的比較求最大值得到完整的MAX結(jié)果。