[發明專利]算術或邏輯運算樹的計算

無效

• 申請號: 200580048372.0
• 申請日: 2005-12-13
• 公開（公告）號: CN101124538A
• 公開（公告）日: 2008-02-13
• 發明（設計）人: 布魯諾·巴拉林
• 申請（專利權）人: 皇家飛利浦電子股份有限公司
• 主分類號: G06F7/50
• 分類號: G06F7/50
• 代理公司: 中科專利商標代理有限責任公司
• 代理人: 朱進桂

技術領域

本發明涉及一種算術或邏輯運算樹的計算。

背景技術

算術或邏輯運算樹包括根據樹結構而組織的算術或邏輯運算。該樹結構包括多個節點，每個節點具有至少兩個輸入端和一個輸出端。每個節點與其輸入端所接收到的數據之間的算術或邏輯運算相對應，并在其輸出端提供該算術或邏輯運算的結果。

可以將該樹結構分成連續的等級：

-包括葉節點的第一等級，

-若干中間等級，每個中間等級包括具有輸入端的節點，該輸入端直接連接到相同在前等級的節點的輸出端，以及

-具有根節點的根等級。

這種運算樹的計算需要多次迭代。在迭代期間，執行與相同等級的節點相對應的所有運算。

典型地，用于在包括至少n個并行處理元件的微處理器上計算算術或邏輯運算的至少第一樹和第二樹的方法包括：

a)使用n個處理元件來并行地執行第一樹的第一迭代的n個算術或邏輯運算，然后

b)使用從用于計算第一迭代的n個處理元件中選出的m個處理元件，在第一迭代的結果之間并行地執行m個算術或邏輯運算，其他n-m個處理元件不用于第二迭代的計算，其中m是嚴格小于n的整數。

一旦計算出第一運算樹，則以相似的方式來配置處理元件，以便處理第二運算樹。

這是使用具有并行處理元件的微處理器的低效方式，因為在第一運算樹的第二迭代的計算期間，一些處理元件沒有得到使用。

在Andrew?Paul?Wallace的US?2003/0088603中，描述了包括n個并行處理元件的微處理器的示例。

發明內容

因此，本發明的目的是提供一種用于計算至少第一和第二運算樹的方法，該方法以更有效的方式來使用具有多個并行處理元件的微處理器。

本發明提供了一種用于在這種微處理器上計算至少第一和第二運算樹的方法，其中與第一樹的第二迭代計算并行的是，該方法包括使用從不用于計算第一樹的第二迭代的n-m個處理元件中選出的k個處理元件，并行地執行第二樹的k個算術或邏輯運算，其中k是小于或等于n-m的整數。

在上述方法中，將n-m個不用于第一運算樹的迭代的處理元件用于并行地計算第二運算樹的算術或邏輯運算。因此，并行使用的處理元件的數量和并行執行的運算數量增加。因此，包括多個并行處理元件的微處理器的使用更加有效。

權利要求2所述的特征減少了處理時間量，因為在m個處理元件之間轉移數據的所需時間內，還并行地轉移k個處理元件之間的數據。

權利要求3所述的特征減少了處理元件之間的數據轉移時間。

本發明還涉及具有用于執行上述方法的指令的存儲器和微處理器程序。

本發明還涉及電信設備中的解擴方法，該電信設備使用上述方法來計算相同的算術或邏輯運算的至少第一樹和第二樹。

附圖說明

圖1是典型運算樹的示意圖；

圖2是用于計算圖1的運算樹的SIMD(單指令多數據)微處理器的示意圖；

圖3是使用圖2的微處理器來并行地計算諸如圖1中的運算樹的8個運算樹的方法的流程圖；

圖4A-4B，5A-5B以及圖6是圖3中的方法的步驟的例證。

具體實施方式

圖1示出了運算樹2的示例。例如，在圖1中，以并行的垂直行來組織節點，每一行與運算樹的等級相對應。在圖1的最左邊的行包括所有葉節點LFi，并且圖1的最右邊的行僅包括根節點RN。

每個葉節點LFi具有兩個輸入端，旨在用于接收待處理的數據。兩個葉節點LFi的輸出端連接到下一行的節點的輸入端。所述下一行的節點的輸出端以類似的方式連接到再下一行的輸入端。重復將一行的節點連接到下一行節點的這種方式，直到達到具有根節點RN的根行。

這里，運算樹2是二叉樹的和，并且每個節點對應于兩個輸入數據之間的相加。例如，將運算樹2用于計算大量數據的相加，例如CDMA(碼分多址)電信系統中的擴頻信號的每個碼片的碼片值。

運算樹2的計算需要多次迭代ITi。在第一迭代IT1期間，執行葉節點LFi的算術或邏輯運算。然后，在下一迭代IT2期間，執行與左邊第二行的節點相對應的運算。重復這個過程，直到執行與根節點RN相對應的運算。

例如，如果運算樹2中輸入數據的數量n等于256，則對運算數2進行8次迭代計算。在迭代IT1到IT8期間執行的相加次數分別是128、64、32、16、8、4、2和1。