[發(fā)明專利]充分利用并行處理器用于數(shù)據(jù)處理

有效

• 申請(qǐng)?zhí)枺?/td>: 201380007148.1
• 申請(qǐng)日: 2013-01-17
• 公開(kāi)（公告）號(hào): CN104081378A
• 公開(kāi)（公告）日: 2014-10-01
• 發(fā)明（設(shè)計(jì)）人: M·赫希;S·T·克萊因;Y·托夫
• 申請(qǐng)（專利權(quán)）人: 國(guó)際商業(yè)機(jī)器公司
• 主分類號(hào): G06F15/16
• 分類號(hào): G06F15/16
• 代理公司: 北京市金杜律師事務(wù)所 11256
• 代理人: 酆迅;陳穎

1.一種用于在多個(gè)初始化步驟之后充分利用多個(gè)并行處理器的集合、以在計(jì)算環(huán)境中由處理器設(shè)備對(duì)數(shù)據(jù)組塊序列執(zhí)行任務(wù)的方法，其中所述數(shù)據(jù)組塊中的每個(gè)數(shù)據(jù)組塊在若干時(shí)間步驟中且被多個(gè)層處理，所述多個(gè)層在所述時(shí)間步驟中的每個(gè)時(shí)間步驟被多個(gè)處理器中的至少一個(gè)處理器處置，所述方法包括：

將所述多個(gè)并行處理器的所述集合根據(jù)所述多個(gè)并行處理器的所述集合的索引分割成不相交子集，從而所述不相交子集中的每個(gè)不相交子集的大小對(duì)應(yīng)于被指派為在所述多個(gè)層之一處理所述數(shù)據(jù)組塊的多個(gè)處理器的數(shù)目；

根據(jù)所述分割向在所述數(shù)據(jù)組塊中的不同數(shù)據(jù)組塊中的所述多個(gè)層中的不同層指派所述多個(gè)處理器中的每個(gè)處理器，從而所述多個(gè)處理器中的每個(gè)處理器忙碌、并且所述數(shù)據(jù)組塊中的每個(gè)數(shù)據(jù)組塊在數(shù)目等同于所述多個(gè)層的數(shù)目的所述時(shí)間步驟內(nèi)被完全處理；以及

設(shè)計(jì)從所述多個(gè)并行處理器的所述集合在所述時(shí)間步驟之一的所述索引到所述多個(gè)并行處理器的所述集合在后繼時(shí)間步驟的所述索引的轉(zhuǎn)換函數(shù)，其中所述轉(zhuǎn)換函數(shù)與所述指派相一致。

2.根據(jù)權(quán)利要求1所述的方法，其中所述多個(gè)處理器中被指派為在所述多個(gè)層之一處理所述數(shù)據(jù)組塊的所述數(shù)目小于所述多個(gè)處理器中被指派為在所述多個(gè)層的先前層處理所述數(shù)據(jù)組塊的處理器的數(shù)目。

3.根據(jù)前述權(quán)利要求中的任一權(quán)利要求所述的方法，還包括使所述轉(zhuǎn)換函數(shù)受到多個(gè)約束。

4.根據(jù)權(quán)利要求3所述的方法，其中所述多個(gè)約束包括將在所述時(shí)間步驟中的每個(gè)時(shí)間步驟的所述多個(gè)處理器中的至少一個(gè)處理器限制于所述多個(gè)層中被指派為處理所述數(shù)據(jù)組塊的相同層。

5.根據(jù)權(quán)利要求3所述的方法，其中所述多個(gè)約束包括將所述多個(gè)并行處理器中被指派為在所述多個(gè)層中并非第一層的層處理所述數(shù)據(jù)組塊的處理器集合限制為所述多個(gè)并行處理器的所述集合中被指派為在所述多個(gè)層中的先前層處理所述數(shù)據(jù)組塊的子集。

6.根據(jù)前述權(quán)利要求中的任一權(quán)利要求所述的方法，其中所述多個(gè)并行處理器中可用的處理器的數(shù)目是n＝2^d-1，其中d是所述多個(gè)層的數(shù)目，所述多個(gè)處理器中向級(jí)0指派的處理器的數(shù)目是n＝2^d-1，并且所述多個(gè)處理器中被指派為在所述多個(gè)層中并非第一層的一層處理所述數(shù)據(jù)組塊的處理器的數(shù)目是所述多個(gè)處理器中被指派為在所述多個(gè)層中的所述先前層處理所述數(shù)據(jù)組塊的處理器的數(shù)目的一半。

7.根據(jù)前述權(quán)利要求中的任一權(quán)利要求所述的方法，其中所述多個(gè)并行處理器是按整數(shù)0至2n-2的編索引集合，對(duì)于i＝0,1,…,d-1，所述多個(gè)處理器中被指派為在被編索引為i的所述多個(gè)層之一處理所述數(shù)據(jù)組塊的處理器的數(shù)目是n/2ⁱ，并且n/2ⁱ個(gè)所述多個(gè)并行處理器的所述索引是具有以0跟隨有i個(gè)一為結(jié)束的、長(zhǎng)度為(d+1)的標(biāo)準(zhǔn)二進(jìn)制表示的n/2ⁱ個(gè)編號(hào)。

8.根據(jù)權(quán)利要求1至6中的任一權(quán)利要求所述的方法，其中所述多個(gè)并行處理器是按整數(shù)0至2n-1的編索引集合，對(duì)于i＝0,1,…,d-1，所述多個(gè)處理器中被指派為在被編索引為i的所述多個(gè)層之一處理所述數(shù)據(jù)組塊的處理器的數(shù)目是n/2ⁱ，并且n/2ⁱ個(gè)所述多個(gè)并行處理器的所述索引是具有以1跟隨有i個(gè)零為結(jié)束的、長(zhǎng)度為(d+1)的標(biāo)準(zhǔn)二進(jìn)制表示的n/2ⁱ個(gè)編號(hào)。

9.根據(jù)前述權(quán)利要求中的任一權(quán)利要求所述的方法，還包括與所述設(shè)計(jì)結(jié)合將所述轉(zhuǎn)換函數(shù)選擇為將向左移位至少一位的循環(huán)移位應(yīng)用于所述多個(gè)處理器的所述索引的標(biāo)準(zhǔn)二進(jìn)制表示。