TWI263167B - Method and system for performing calculation operations and a device - Google Patents

Description

1263167 玖、發明說明： 【發明所屬之技術領域】 本發明係關於使用由―組 個資料輸入介面，及至少—彻次上丨从s民丨白杈至乂 i卜辞曾壯罢由、》 個-貝料輸出介面所構成的管線 义料：衣人Λ仃運异的方法’該管線階段包括至少-個 ,枓輸…及一個資料輪出介面，此方法 第？運算所用資料是輸入該装置；本發明也是關於由一组 系少兩個管線階段，至少-個資料輸入介面，及至少一;: #料^介面㈣成的管線化計算裝置内實行運算的系 統’该官線階段包括至少—個資料輸人介面及—個資料輸 出介面’且該計算裝置還包括第—與第二運算用的資料輸 二本發明還是關於由-组至少兩個管線階段，至少—個 貝，輸入"面，及至少—個資料輸出介面所構成的管線化 計算裝置内實行運算的I置，該管線階段包括至少__ 料輸入介面及-個資料輸出介面，且該計算裝置還包括第 一與第二運算用的資料輸入。 【先前技術】 有許多應用系統是須要使用乘法運算、乘法累加運算 (AMC)及其他運算的。纟一非限制性的例子中，多訊號： 理應用系統，例如數位訊號過濾應用、視訊/圖像處理應= 等等，是實行即時乘法運算的應用。其他須使用向量且 或矩陣的應用也須使用乘法及MAC運算。乘法運算通常以 求和及順位元運算實行。如此之乘法運算是高資源要求的 作業，因為一個介於兩個運算元的乘法運算是須要大量的 1263167 即時計算。因此，高速效率是對不同的視訊/圖像處理運 算法或次作業發展平行專門結構（加速器）的動力。先矿 的視訊/圖像處理系統技術包括數種類似的加速器（例J 如，絕對差和（SAD)，餘弦變換，等等），每一種皆包括了 大量的硬體元件。然而，由於行動通訊系統之發展，在硬 體方面，其影響系統的成本以及電源//能源的消耗，與高 速效率為同等重要的特性。一種趨向滿足所有這些要求的 方法是更現代化的數位化訊號處理器（DSPs)，並減少專門 加速器的數目。縱然在這些方面有所改進，但是這樣的系 統仍然無法滿足高速率及能量消耗的要求。 ” 表1概括一些主要的計算模式及經常使用這些模式的 視訊/圖像處理運算法的例子。這些模式中的運算是报基 本且相當為人所熟悉的。許多的文章已陳述過這些運： 的執:。在此強調與視訊/圖像處理運算相關的兩個特 ，。第-，運算元通常為中精確度（8至16位元）整數值。 第二，大部分的運算法利用大量平行運算。在某些情兄， ^平，運算共用同樣的運算元，例如，在數值量化方面， 陣乘二多的影像的像素（pixels)相乘；在向量矩 不同的列被乘以相同的輸入向量；在有 回應（FIR)濾波器中，相同的系數被包括在若干 MAC運算中，等等。 1263167 表1 計算模式 列式 運算法 平行加/減法 di二cti：hbi，i=1，.·.，k 動態補償，明度改變，離散餘弦轉換 (DCT)、離散波元轉換(DWT)、絕對 差和(SAD)之次運算，等等。 累加計算 κ ^ = Σ ΐ=\ 前置，後置處理之平均過濾，DWT 之次運算，向量對向量及矩陣對向量 之内積，捲積，等等。 平行乘法 mi^axxh or m^aiX, i=l, ...,Κ 量化，DCT，DWT，向量對向量及矩 陣對向量之内積，捲積，等等之次運 算。 乘法累加計算 (MAC) Sf = + i — \,···，iC， 印是未知整數 FIR濾波器之基本運算及矩陣對向量 運算 向量對向量之内 積 Κ s = aixi i=l DCT，DWT，向量對向量及矩陣對向 量之内積，捲積，等等之前置，後置 處理，次運算。 矩陣對向量乘積 P = Σαυχ] i = 1,..., K 顏色轉換，幾何操作，仿射運動估計 ，DCT，等等之前置，後置處理，次 運算。 HR濾波（捲積） P si = Hajxi-j 7=1 i = 1,..., K 前置，後置處理(圖像濾光強化，内 插，外插），DWT之基本運算。 絕對差和(SAD) K s = Σ~bi\^ /=1 動態估計，圖像逼真度標準平均絕對 誤差（MAE)。 視訊/圖像處理以及其他訊息處理之先前技術結構是 基於傳統的乘法運算。許多執行乘法運算及/或乘法累加 運算的方法及裝置已經發展出。以下所要考慮的情況是祇 有當乘法運算方法及一般乘法結構的兩個運算元（被乘數 與乘數）皆未知，兩個符號定點整數以2之補數表示的乘法 1263167 運算’即所謂的基數T(radix-T)方法。 &續元（包括符號）乘數一2之補數表示為 “H2,，及讀7^ (包括符號）被乘數X表示為 抑。α與^同樣的關係於1與巧表示如下’ η—2 …χ r=〇 -χ m~l 2m'] m-2 Ο) 在基數T的乘，法運算方，法中， T 木知少= α.χ的2之補數 少w+/7-的公式如下： 〜Mradix—T — 1 (2) y ~ Σ {Arx)2rtradi^-T r~〇 其主要兩個步驟是： 步驟1·產生部分乘積（pp)4.u 有效。 ，—，···，〜-&—Γ-/ 使式（2) 步驟2_平行地將所有初步向左 分乘積J „ —x-r位置的^個部 、r ’ ”··’％也-7·-/總和起來。 基數TMAC單元以類似的方 個數字(累加項)被加在第2步驟的二：不同的是另- j現Γ驟1作更進一步考慮^同的乘·ί7方^ 法運算方法。A Q 隹蛉出不同的乘 之表示法而定。一Η的選擇事實上是依乘數α I263l67 、最簡單的乘法運算方法是為基數2之方法，其使用α 、之補數表示於式（1 )的左邊。於此情況，乘積的2之 補數可依以下求得： 〜nradix—2 -I fl—2 y ^ ^ytrad^2 - Σ〇 i^rx)2r - ? (3) 即"Wx—2二”，及部分乘積 4.x，r = 〇，···，” —7 由 〜 土，2，且7—一％ 一^當尸二”一7所定義。這些部分乘 積可簡單地（並通常地）形成於使用一個2輸入及閘（AND Gates)陣列於乘數3被乘數y的2之補數位元間。 士·Χ，Γ = 〇，.·4 —7之值乘以/ (及向左移r個位置）於累加至 苐们^驟之韵。應注思的是此方法中的部分乘積4厂χ有 時也稱為修正因數，其視為不同於其他的部分乘積。/ 部分乘積之非一致性的性質可避免於使用另一種基數 2、紐運算法，其基於㈤㈣重新編碼使乘數的補數位元& 成為額外的符號位元。該乘積可表示為： 〜nradix-2 -1 n_^ y= Σ (Arx)2r=±(-ar+ar_j)xr, α_]=〇 (4) ’Ji、叫，nradbc—2 ..... ^ /刀、米積 一/現在都定義“一〜。與之前的方法 ㈣，將今^嗔少7之值乘以^於加至第2步驟之 W °在此方案中’部分乘積於恤中選擇一個。這些 其中兩個（0鱼X、Η4 口从 、 /、幻疋即付的，而1之求得要反轉3?的位元 10 1263167 並加上單位元。通常’單位元加法執行於部分乘積加總的 第2步驟中。 無論是BOOTH重新編碼或是非重新編碼，在基數2 乘法運异中共有”個部分乘積。為了減少部分乘積 的數目，即減少第2階段（部分乘積加總）的延遲，:是發 展出基於基數4修正BOOTH重新編碼（Mba)的方法/ ΜΒΛ是最通用的乘法運算之一，且被進一步的研究及優化 中。 為了簡化以下之公式，在任何情況下，當有一項，例 如π/Α發生時，即假設η是k的整數倍。這是有效的假設， 因為2之補數可由任一數目的位元作補數（重覆最高有效位 元）。 在MBA中，乘積的2之補數由而一個部分乘積 之總和獲得： (5) 〜nmdix—4 -1 η / 2—1 Σ (Arx)2 r = £ ([~2α2Γ+1+α2Γ+α2Γ.1]χ)22Γ, r=〇 r^〇 a—1 二 0 2，-/，0，/，2，Γ4,7，.··，”/2 —7，是依據乘數 3的 2 之 補數表示的3個連續位元α>+7,❻，％—7(α—尸〇而選擇。Λχ， /，乘以A (即在硬體中移左2r個位置）於加入 步驟2之前。 使用高於基數2非重新編碼的乘法運算以減少部分乘 積數目也是可能的。例如，在基數4非重新編碼運算法中， 1263167 依據乘數的2個連續位元 讀邙，气…。此;有擇樹… 產生。奇數邱能部分乘積：向左-次而 法運算也使用，頁再加—個X求和而得。若負數乘 效位元（即二 伸必須使用，部分乘積的最高有 Λ* )複製多次直至達到所須的位元長度。 ^，1，2,3,4,5,6,7卜\重:广碼”運算中’部分乘積心 遠婷你- —，的選擇是依據乘數的Μ固

二：。可能部分乘積列是W，A ，仃3個分別的加/減法以得到 個x:可能部分乘積知可移動可能部分乘積氕向左-八乘j件。對於較高基數的情況（> =16)，有些可能部 U、例如及)無法由一次的加/減法求得。 圖1表不用以實行修正boo™運算法的裝置101。共 個booth編碼/解碼列，每一列包括i個Β〇〇τ_ 碼器102,及m+H„〇〇TH解碼器、1〇3，每兩個列為一組。 母個BOOTH編碼器、102解析乘數3的2之補數的3個連續 位7，有一位凡重疊，且輸出Q個訊號對應至解碼器103列。 在一些先前的設計中U。根據此一訊號，解碼器列與 =乘數位兀x輸入形成部分乘積⑷*机紅边}。X非負值 ^數可即時求得，因為2χ是由固線式移位形成。X的負值 化數的求彳寸方式是將相應的X正值倍數的位元反向並加1， 此通常於步驟2中實施。例如，美國專利6，173,304是一執 行BOOTH編碼及解碼的系統。於基數2的方法中，部分乘 12 1263167 知的獲得比修正b〇〇th運算法 運算法時，部録積㈣目減至1/2, 面積及電源消耗上顯著之優勢。 但是使用修正booth 如此，導向速度效率， 夕 為進一步減少部分乘積數 夕位元（任意基數T)編碼。 目，booth編碼已更延伸至 該乘積的一般方程式如下： Σ (Arx)2 r-〇 ,nit—1( Σ r~〇

X 2tr ⑹ a~l - 〇，T 二 = 2tradix-丁

^ nradix-T 乘積是依據乘數、 分乘積（Γ = 2，)，且每個部分 數列，該勸可崎乘積办 對地容易形成於兩個；…)能(::输能相 二方倍:之相加，及可能地位元反轉後的:的2 例如，基數8會報抱成从法 '弟2步驟）〇 土數8重新編碼的情況，可能部 咖，±2x，±h，±〇。所有數列中的、J為 自於m仙外，皆為即時可° ^除—了办得 倍數可依反向加丨之方法求得。在基數16 ==，負數 可能部分乘積列為㈣边执重^ 3個分別的加/減法以得到jx = x + 2x，5坆二可藉由執行 7x二8x-X。可能部分乘積分可 JX —x + 個位置而得。對於較古美翁 此口P分乘積h向左一 如’仏及说）無法由-次的加/減法乘積（例 圖2表示先前技術之基數τ (τ>=: 夕位元B〇〇Tii 13 1263167 及基數τ(τ>=4)新的非重新編碼(基數高㈣ : 又結構20卜此結構包括加法器陣列202以叶营 乘積數列，一個選擇區塊2〇3以選擇補部^ 二塊2〇4將被選擇的部分乘積加總，最後 項由總和區塊心 典型先進技術的基數高於4之乘法器的加法器陣 減法器，其“是可能部分乘積列内^值的 乘法，於T=8 B〇〇TH重新編碼或Τ=4非重新編碼 非重二以及s=3,於Τ=16Β00ΤΗ重新編碼或τ=8 ㈣通常快速進位預測（CLA) 吏用’因為可能部分乘積形成於如此的乘法器是相 =㈣。在專利us_5,875,125中提出申請的特殊仙加 ㈣基數8乘法H卜應注意的是混合式基數4/8乘 /益也已提出中請’例如，在美國專利號碼4,965 762中， =用在相互作用的（非平行的）乘法器，其中部分乘積 疋序列地產生及累加。美國專利號碼5,64M77揭示一種乘 法結構’其中任—基數的所有可能部分乘積由 式’以及包括-個產生办之仙加法器，兩個移位 個加/減法器之加法器陣列的χ之求和或差數而得。 典型先前技術的基數高於4乘法器的選擇區塊包括n/t 個基數TBOOTH編碼器及相同數目的解碼器列。每一個編 碼器解析相應乘法器的⑻）元組（tuple)，及輸出複數控 制訊號，依據該訊號，相應的部分乘積由解碼器列形成。 14 I263l67 關於如何延伸基數4 BO〇TH編碼器及解碼器至更高階的基 數’可以專利US-6,240,438為例。 以下，對部分乘積之加總，即第2個步驟，作更細節之 考慮。大部分的平行乘法器/MAC單元結構用包括一個壓 縮陣列跟隨著一個快速加法器（最終加法器）的總和區塊 作為步驟1部分乘積之加總（見圖1及圖2)。壓縮陣列將 的部分乘積數列減至2個數列對應到總和s及進位 C項，其於最加法器中相加。壓縮陣列通常包括全部或半個 ^法器（進位儲存加法器樹或Wallace樹）或4: 2壓縮器。 取終加法器通常為快速預先進位加法器，其是依據壓縮陣 列的不同位元的延遲詳加設計。 應注意的是，如果利用BOOTH重新編碼之方案，則實 行皁位元加法之結果於第丨步驟而非第2步驟，每個部分乘 積列伴隨一個位元值，若部分乘積是被乘數的負數倍，該 值為0 ’否則為單位元值。如此，實際上，數列的數目是 Γ。僅管這些i位元值可能合併至部分乘積列中，如 此數列的數目是〜—或〜逢—Γ + 7，但所須付的代價是增 加乘積列的長度⑴固位元）及變得不規則。在非重新編； 的方案中，至多祇有i個額外的位元值，所以可設 的壓縮陣列。 早 個與booth重新編碼乘法器之總和區塊相關聯 的問題疋如何處理訊號延伸，因為部分乘積列在加總前須 彼此相對地移位。一個簡單的執行是每個部分乘積（移位 後）應延伸至（科m)位元數，這是非常耗時的作法。特殊 15 1263167 符號的延法及電路已經發展可以減少#號延伸位元數 至每列中兩個。在非重新編碼乘法器_，符號延伸可處理 的更簡單’而沒有額外的符號位元，因為所有的部分乘積 除了一個以外皆是同符號的。 原則上有兩個延伸乘法器結構至mac單元的方法如圖 3&及3b所示。在第1個方案（圖20，兩個壓縮陣列301 ^輸出（總和項S及進位項c)回饋至其輸人，以使目前的

部分乘積與目前累加值的兩個加數作累加。最終的總和項S 及進位項c然後於最終加法器3G2内相加。在第2個方案 (圖3b)，這些輸出供給另一個壓縮陣列3〇3，其輸出再回 饋至自身（第2個I缩陣列）的輸入。再來，目前乘積的總 ，=及進位項C累加至目前的累加值直至最後一個循環 /最終的總和項SA進位項C於最終加法器3〇2内相加 t整個壓縮陣列的較（即所有的延遲）可能於第i個方 ”為較小’但寬度’即因此，面積及電源消耗卻是以 個方案為較小。 弟3

一種％為官線的方法可以用在與運算連接。亦 用管線的裝置包括2個或以上的管線階段，每個管線 一個 階段 16 1 f Λ Γ 的總結，纽意的是基崎高則步驟 2

數高於4的乘法運算法尚未穫得普及，或許因為其使用相I 3 ^產生部分乘積）愈㈣雜，但是步驟2則愈 4 的時間；面積於部分乘積器，包括加法陣列及選擇區塊： 通吊’基數4ΜΒΑ被視為是最好的先前技術乘法運算 且被用在許多實業上之乘法器中。 # 1263167 用以貫仃運异中的特定的某一或數個部分（即子運算），管 線間彼此聯繫，每個管線階段實行1或多個子運算，並於最 ，一個管線階段輸出計算結果。在此管線装置中，不同的 吕、之^作疋才木接績式地，因在匕，下一個管線階段開 始刼作子運算於前一個管線階段完成子運算之後◦若管線 階段是純粹地平衡（即某些階段顯著地快於其他的階段）， 這意謂著所有的管線除了一個以外大部分的時間皆在等待 或閒置。此外，所有的管線皆保留給某一特定的作業（計 算子運算）而無法實行其他的運算。 3有~乘法器/MAC單元的特性，從視訊及圖像的觀點 是希望具備的，但是先前技術的解決辦法是缺乏或不足 的，此將揭示於後。f先，最普及的絲4BOOTH重新編 碼的乘，器/MAC方法將被考慮。這個方法的—般缺點是 比起較高基數的方法消耗更多的電源。另—個—般的缺點 是，即使純於基數2乘法運算方法，部分乘積的數目減 半，但其仍可減至更少若使用更高的基數。亦即，這個方 法的複雜性主要集中在第2個步驟（部分乘積的加總）。當 管線化一個基數4 BOOTH重新編碼乘法器/MAC之結構 ，通常部分乘積產生區塊被考慮作第丨個管線階段，然而是 平衡於（即，較快於）其他的管線階段。 就基數高於4的BOOTH重新編碼器而言，已有不同的 此類乘法器實現，當僅考慮乘法運算的實行，其與基數4 的乘法器就時間及面積的標準而言，有相當的競爭性，然 而在能源消耗的表現上，卻遠勝過基4數乘法器。基數高於 17 1263167 4的主要缺點是在部分乘積產生區塊内須要有一個加法哭 陣列。 '口° 基數高於4的BOOTH重新編碼乘法器還有一項缺點是 關於必須處理被乘數的負倍數及符號的延伸。 基數T非重新編碼與基數2τ B00Th重新編碼於部分 乘積產生區塊内包括有相同數目的加法器。當使用基數高 於8的非重新編碼或基數高於163〇〇111重新編碼之乘法 器，須要使用1個階層以上的加法以產生可能部分乘積\ 表2a

乘法器型式 BR, T=4 BR, T=8 BR, T=16 AA寬度，s — 1 3 可能部分 乘積數目 5 9 17 SB之部件 編碼器 n/2BR4 n/3 BR8 n/4BR16 解碼器 n/2 (m+l)-BD4 n/3 (m+2)- 4:1 t/c n/4 (m+3)-8:l t/c SE Yes Yes Yes SB之延遲 6t 12t 16t CA之輸入數 n/2 (m+l)-bit + 3n/2 n/3 (m+2)-bit n/4 (m+3)-bit 1-bit +4n/3 1-bit +5n/4 1-bit FA-CA5 之 n=13，x 7 / 4 / 8t 5 / 3 / 6t 4 / 2 / 4t 輸入數/ MAC 9/5/ lOt 8 / 4 / 8t 6 / 3 / 6t 階層/延遲 n=\6,x 8/4/8t 6 / 3 / 6t 4 / 2 / 4t MAC 10/5/ lOt 8 / 4 / 8t 6/3/6t n=64,x 32/8/16t 22/7/ 14t 16/6/12t MAC 34/9/18t 24 / 7 / 14t 18/6/12t 4:2-CA 之 n=13,x 7/2/6t 5 / (4:2)+FA / 5t 4 /1 / 3t 輸入數/ MAC ~~——---- 9/2(4:2)+FA/8t 7 / 2 / 6t 6 / 2 / 6t 階層/延遲 n=16,x 8 / 2 / 6t 6 / 2 / 6t 4 /1 / 3t MAC -----— 10/3/9t 8 / 2 / 6t 6 / 2 / 6t n=64,x 32/4/ 12t 22/4/ 12t 16/3 /9t __— MAC 34/5/ 15t 24/4/ 12t 18/4/ 12t 18 1263167 表2b 乘法器型式 NR1, T=4 NR1,T=8 NR2, T=4 NR2, T=8 AA寬度 ,S 2 4 1 3 可能部分乘積數目 4 8 4 8 SB之部件 編碼器 No No 1 BR4 1 BR8 解碼器 n/2 (m+1)-4:1 n/3 (m+2)-8:l (m+l)-(BD4+n/2(4:l)) (m+2)(4:l t/c +n/3(8:l)) SE No No No No SB之延遲 5t 6t 6t 12t CA之輸入數 ((n-l)/2+l) (m+2)-bit ((11-1)/3+1) (m+3)-bit (n-l)/2 (m+4)-bit + 1 1-bit (n-l)/3 (m+6)-bit + 1 1-bit FA-CA5 之 η=13,χ 7 / 4 / 8t 5 / 3 / 6t 6 / 3 / 6t 4/2/4t 輸入數/ MAC 9 / 4 / 8t 7/4/8t 8/4/8t 6 / 3 / 6t 階層/延遲 n=16,x 9 / 4 / 8t 6 / 3 / 6t 8/4/8t 5 / 3 / 6t MAC 11 / 5/ lOt 8 / 4 / 8t 10/5/lOt 7 / 4 / 8t n=64，x 33/8/16t 22/7/ 14t 32/8/ 16t 21 / 7/ 14t MAC 35/9/ 18t 24/7/ 14t 34/9/ 18t 23/8/16t 4:2-CA 之 n=13，x 7 / 2 / 6t 5/(4:2)+FA / 5t 6/2/6t 4 /1 / 3t 輸入數/ MAC 9 / 2(4:2)+FA/8t 7/2/6t 8/2/6t 6 / 2 / 6t 階層/延遲 n=16,x 9/2(4:2)+FA/8t 6/2/6t 8/2/6t 5/(4:2)+FA/ 5t MAC ll/3/9t 8/2/6t 10/3/9t 7 / 2 / 6t n=64,x 33/4(4:2)+FA/14t 22/4/ 12t 32/4/12t 21/4/12t MAC 35/5/15t 24/4/ 12t 34/5/15t 23/4/12t 表2c BR Booth重新編碼基數_T乘法器 NR1 非重新編碼基數-T乘法器類型1 NR2 非重新編碼基數-Τ乘法器類刑2 SE 符號延伸電路 ----- BR4，BR8,BR16 相應基數Booth重新編碼器電路 BD4 基數-4 Booth解碼器電路 4:1,8:1,4:1 t/c, 8:1 t/c 相應輸入數目之多工器或實/補多~ — SB 選擇區塊 ~~-----— CA, FA-CA, 4:2 CA 加法器_及半加法器_之壓縮陣列，含4:2 Μ細态之壓縮陣列 19 1263167 表2a表tf不同區塊之不同特性，該區塊用於先前技術 ^ B00th重新編碼基數τ乘法器/mac單元作為n位元乘 ，與m位元«數之乘法運算。表2b表示不同區塊之不同 寸性’該區塊用於非重新編媽基數τ乘法器作為η位元乘 數與m位元被乘數之乘法運算。表&表示^以内 ㈣縮寫。當分析表2#21)時，可以發現對於大部份的η 每個乘法器/MAC單元型態内每個乘法器區塊的 =質上的不同。亦即，這些乘法器之直接管線化實施 2官線階段間之不良平衡而受阻礙。為使管線階段間有 父佳平衡，可藉由設料—個進位傳遞區塊时不同W ，目的進位賴（CLA)加法器，轉性地增加第丨與最後管 2線階段的傳輸率。此即何以這些區塊的延 …之中。某些情況，例如，小n、較高基數τ，：： =小的進：傳遞區塊，而因此大的面積。無論如； AS可旎為此兩階段增速之解決方法，侔管苴 ，最有效率的。此狀況對於中間之兩個管線階段;…:) 疋不同的，因為用於這些區塊的最先 最大效益而設計，以致於使得这此中」路疋為揮要技 τ錢於使传k些電路的内部管線作業並 =。 這些區塊的延遲對於每個先前技術之乘法 VMAC早70結構之每個型態（BR(T=8，16)，NR1 / 聯不同讀，彼此間之相對差異是非 ， 較高基數丁（例如丁二16乃#_ 伯、於更小II、 為慢，铁於里们主 M ) ’堤擇區塊較I縮陣列 為k…、於其他情況則相反。這意指著為一個 塊設計較快之電路並無法解決階段之間平衡的_般問題。。口 20 1263167 所有14些皆使得為先前技術之乘法器/MAC結構具有良好 管線化平衡而發展系統化之方法發生困難。 ” 、，另方面，若將獨立之先前技術乘法器/MAC單元之 平行陣歹i應用於複數個相應之運算，即使較快的區塊可以 用而不影響整體傳輸率，大的矽面積使用是必須的。此 卜如上所述，官線階段會產生不良平衡，若將管線化乘 法器/MAC單元應用於該陣列十。 “先。前技術的矩陣向量算術平行架構的設計是用複數獨 立乘法器結合加法器或複數獨立MAC單元。同時，對於不 同的運f通常有複數特定的電路。然而高基數乘法器包括 區塊（官線階段）其可再使用於其他的運算，例如，加/ 累加運异，等等。同時應提及的是，在矩陣向量算 :中’ 4寸別是用於視訊/圖像處理方面，如果高基數乘法 被使用，在許多情況，一個被乘數被乘以數個乘數意味著 、乘數的可犯部分乘積可能已被使用在所有的乘法運算 :j例如，在向量與矩陣運算中，同樣的乘數將使用許多 二，同樣的部分乘積將使用超過一次以上。當此種運算實 仃於先則技術架構，其計算部分乘積於每次須要時，而導 2體資源的無效率使用及增加電源之消耗。此外，如上 所述，有許多情況，先前的管線階段技術的乘法器是純粹 的平衡，因此減低裝置的效率。 【發明内容】 ―本發明的目標是提供一改良的計算結構及方法以實行 運异，其能夠儲存運算過程中的中間結果，特別是儲存乘 21 1263167 =運算之可能部分乘積之能力。依據本發明之方法，至少 ::運，計算階段’例如管線階段，之輪出資料是儲 體中，而儲存的f料作為另—個運算的輸入資 =許=存可rt乘積之外’計算裝置之記憶體可用 -电二广本鉍明之—有效計算裝置實施例是可依 、:““fl號而多功能化/可組態化成數種不同之结構。 本1之結構可有效地實行騎大型積體電路(VLSI)架構。 本發明有不同的實施例，复Φ一此 /、中些將於下文中揭示。 "二:疋利用—個記憶體單元儲存及再使用可 二數二=於㈣的被乘法被乘以數個乘數的情況時。有 ^的如矩陣向量乘法運算，FIR據波器，等等。 個具有相同被乘數的乘法運算中，祇有最初的 二：被執行’而避免了最須資源的可能部分乘 曾的 例如，當矩陣乘以向量時，祇有輪 、 完全的乘、、#、S I ^ # ^ σ里的弟1個分量須作 的宋法運开，而其他輸出分量的乘法運 執行。當實施FIR過濾時，完全的乘 、二“邛伤 乃非完全地執行。㈣其他《輸出時，乘法運算 第2個實施例是在矩陣向量中運用一 ，並同時彈性地將其組構成較小的作業。 去时…構 第：個實施例的結構可组構成執行 括：⑷複數乘法運算；（b)複數Mac 精確度（位元）的複數加/減 ）不同 累加運算。 建才，且/或（d)平行 22 1263167 第3個實施例是結合 (sad)加速結構的視 結構與絕對差和 架構，依-組不同的” 理結構。此結構是多功能 確切地說成不同叫 第一個運算中，至少一個法的主要特徵在於所述之 憶體，而於所述之第-個=段的輸出資料被儲存至記 線階段的輪入資料該被儲存之細^ 括-_作為儲存主要特徵在於包 段的輸出資料，且有一個=取=少一個管線階 之第二個運算中之管線階段輸入=將::資料用於所述 的主要特矜/Μ44 又翰入貝科。根據本發明之裝置 *至少-個管線階段的輸出資料，且有一== 儲存3用於戶 3電路_構適用於廣泛的計算模 方、以、目 "圖像處理運算。藉由使用本發明之 之比車=圖像處理方面，乘法運算與先前技術及裝置 數乘^運3=得較快Μ較節省電源。本發明在執行複 s及有—個共料h (共用被乘數） 邙：乘：法，/MACS時特別有效率。由於可儲存可能 使用它刚的運算中’可達成顯著面積及 面之減少。另外一個本發明的有效實施例能夠 叹疋不同管線階段為節省能源模式，當其不須且/或實質 同步地使用不同管線階段實行不同的運算時，可明顯地減 23 1263167 少電源的消耗。高速效率 彈性可能性的管線以平衡不;;=率）是歸因於運用具有 結構區間對最快速區塊的 1階段的延遲並減少總體 先前技術（基數4或更高）乘€ °=士加傳θ輸率相較於單管線 及不增加輸入/輪出n。。r疋以增加最少的面積 記憶體單元d:寬度而達成。 行加/減法運算（不同精確執;^乘法為基礎的運算時，平 、夢七s ^ 萑度）可旎執行於其他的作業。 段，二二、算二?f:例的優點是架構的第1管線階 & 〇靶0卩分乘積的加法器陣列，不須盥：M：他 ，階段平衡，因為在大部分的循環中，其並不:要： 置成化結構使得對於不㈣運算重覆使用相同的裝 成為可：。此外’運算可用以執行不同精確度的參數， 例如，W行8位元加法，或4個平行16位元加法。 次丹著^間與電源/能源消耗的節省可達成，因為耗 :取大綱可能部分乘積的計算從大部分的乘法運算中 去除。 ^ Τ 直你2夕功月匕木構’本發明的一有效實施例可取代數個 專作為某一訊號處理運算的硬體加速器，例如，視訊/圖

像處理運算。 U 【實施方式】 ^以下，疋第1個有效實施例的詳細說明。根據本發明 第1個實施例的裝置的-般結構如圖7所示。該裝置！以 24 1263167 不同笞線階段P1到P4為一組。本實施例裝置1含4個管線 階段，但是本發明的範圍可包括4以外之不同管線階段。此 結構還可組入一個記憶體區塊，使得相應於一個運算之第 一管線階段的輸出可以被寫入及再使用於相應之另一個運 算之第二管線階段的輸入。 管線技術是一通常用於實行複數個類似的操作以增加 系統的傳輸率，例如，乘法運算且/或MAC。考慮一典型 的先前技術基數T Booth重新編碼（τ=8，16)或非重新編碼 (Τ〜4 ’ 8)乘法結構的管線化實施，第1管線階段ρι是表“ 中的s加法器陣列，第2管線階段P2是選擇區塊，第3管 線階段P3是壓縮陣列，及最後數個階段p4(其數目將因不 同實施而有所不同）。 依據本發明第1個有效實施例的裝置組入了複數（排） 乘法器/MAC單元。基數T BOOTH重新編碼（T=8，16) 或非重新編碼（Τ=4，8)乘法器之不同排的一般結構顯示在 圖7。一排乘法器/MAC單元的有效實施例結構通常可描 述為一個管線化裝置1，其中第一個管線階段ρι含複數個， 如P ’包括s個加法器的陣列（AA，S)2，且所有陣列之$個加法 器2共用同一個輸入線6。第2個管線階段P2是複數個， 如？，選擇區塊（SB，s)3，第3個管線階段P3是複數個，如 w ’壓縮陣列（CA，s) 4，及第4個管線階段P4是複數個，如v， 隶終進位預測加法器（CLA，s)5。這些基本功能區塊（AA，s，SB，s， CA’s，及CLA，S)實際上與用在先進技術的乘法器且/或 MAC單元之相應的類型相同。因此，當p=q=u=v=i的情況， 25 1263167 對應至先進技術的乘法器且/或MAC單元結構，主要 在於該裝置包括-個記憶體21可用以儲存一個或多個運曾 ,程：中間結果，一非限制性的例子，譬如可能部分乘積T 夕工器2 2可用以選擇第_答綠β比π ΛΑ ^ , 管線階段P2的輸入。本/置輸出3或_21作為 號路徑至裝置且從-組内部4_換内部訊 擇裝置。該選擇裝置是由至個輸出訊號的選 由至夕兩個不同的選擇中，選擇至 少一個管線階段的輸入。在一個有效的實施例中，至少一 區ΐ於先前技術結構中被取代—個基本區塊以上。 ===個參數(ρ，"及V)，適當的選擇該參 數了^十出有良好均衡的管線階段裝置。一管線 區塊以時差的方式操作較優 、” 改變一此大致相 區塊的時間交錯操作原則 較大系統中的管線階段，咖 π你难认t 戈此，為使管線階段P1， ，P4 ，作傳輸率配合步驟區間，此功能區塊 數W固功能區塊，碼碼劭 被代之以稷 存器）“於其輸入，’及—:’：·，有管線暫存器（鎖 13於其輪出。參數％依問 ^夕工S 1G’ 11 ’ 12’ 管線階段pi，參數w對hit官線階段而定。對於第1 及第^管線階段的多工；J選:有 出。對於第2管線階段!>2，表:的-中之-至其輸 夕 w對應至q，即有q個管 26 1263167 及7，···，ν及第2管線階段的多工11 11選擇q輸入 5 '之至其輸出。對於第3管線階段P3，參數w對應 哭：，，即有u個管線暫存器〜"為，及第3管線階段的多工 :鈐ψ其包含兩個多工器（未圖示），各選擇u輸入之-為 個對於第4管線階段P4’參數W對應至V，即有v B、、- «存斋々，··.，心，及第4管線階段的多工器13選擇v 二：白其中之一至其輸出14。至管線階段P卜P2，P3，P4 。:二？輸入連接到每個w暫存器κ然而，這些暫存 W母—個僅開放於每评個操作步驟的其中之一，各步驟 =時間！。如此，在每個操作步驟，輸人z實際上祇連 =-個功能區塊的輸入’而其他的連接則是不活動的。 :關閉：：：他形成！線階段的功能區塊群之輸入暫存器 ‘、入。在每w操作步驟的第丨個步驟中，第1 =能區塊刚的輸人是開放的，在每w 個步驟中’第2個功能區塊FB2的輸人是開放的，等等弟。2 大體而言，於操作步驟，υ中，輸入7實際 ==的丘輸出’其中’ /=(㈠)⑽dw+卜於是，輸入/在空 b1疋J的，而暫時分配至管線階段的功能區塊 碼，…馬之間。於系統操作過程之步驟 至該階段之輸入資料流的取樣A進入功能區塊·; ’―個 於該階段設定。一但，於操作步驟^ 之最，完成其對a的操作，在多功能區塊之， ^ I 1夕工裔Μ ’ U ’ 12，13傳遞由，所得之結果至 該階段之輸出於下個操作步驟㈣“U。因此，^ 27 I263167 态10，11，12，13依循環卿規則操作。 由替換每個先前技術乘法器/MAC單元結構的功 區塊為複數個相似的功能 刀犯區塊，及由日寸間差操作的原則， :個較平衡的管線階段或可達成於適#地選擇在每個管線 t(即^、及0的區塊數目於預定的操作步驟。 :设f先前技術乘法器/MAC單元結構的4個階段的延遲 刀別=Dw，/)從，，乃⑴，且希求的系統傳輸率是#如乘 法運异MAC/運算每移、，則所希求的操作步驟區間將選擇為 心以，使，及上述之設計參數將為， P「一~/7^’ W =「如41，及^「^/7^ ，其中，符^厂^ 表示進位至下一個整數。 圖8揭示依據本發明的第2個有效實施例的計算裝 置，結構的可組態性依據本發明的第2個有效實施例是藉由 匕括或數個遙擇裝置而達成，例如，位於第1個p 1，第 3個P3 ’及第4個P4輸入管線階段的多工器丨5，丨6，17。 多工器15, 16, 17是2:丨多工器，其分別由對應的〇1， c2，c3汛號控制。此結構還包括一個輸出選擇器2〇，其由 第1個汛號c 1控制’以及第2個訊號及第3個訊號的〇R 組合（即巧〜3)。輸出選擇器20選擇資料於第！管線階段 P1，或於第4管線階段P4的輸出連接至結構的輸出匯流排 14夕工崙15，16，17的苐1個輸入連接至對應的輸入匯 流排6，多工器15，16，17的第2個輸入是彼此相連的， 當第2個輸入啟動時，結構作為乘法器/ mac運算裝置。 使用不同的控制訊號cl，c2，C3組合可能產生不同的結構 28 1263167 組態。選擇裝置可用以重新選擇内部訊號路徑至計算裳 置，且從一組内部訊號中選擇一個輸出訊號。選擇裝置由 至少兩個可供選擇中選擇至少一個管線階段的輸入^據些 訊號所產生的組態揭示於後。 當所有控制訊號cl，C2 ’ c3設定為邏輯1狀態，即 cfcecf；!，結構作為乘法器/ MAC裝置。當第i個控制訊 號cl為邏輯〇狀態，而其他控制訊號c2，c3是邏輯丨狀態， 即==〇, c2=c3 = l，結構作為sp加/減法陣列。祇有第\ 個管線階段P1 (即加法器2陣列）是啟動的，其他則是閒 置的。第3個可取組合是第丨個控制訊號為邏輯丨狀態， 其=控制訊號C2，C3是邏輯〇狀態（cl=〇，c2=〇 , c3 = i)。 此時，結構作為累加器。祇有壓縮陣列4及最終加法器運 作，其他的加法器陣列及選擇區塊則閒置。帛4個可取组合 J第1個控制訊號Cl及第2個控制訊號c2為邏輯"大態， 第3個控制訊號c3設定為邏輯〇狀態。 此時’結構作寬精確度器快速加法器。尚有另—可取组合， 當Cl=C2=c尸〇’結構同時作為sp加/減 。 很顯然的，上述之選擇穿f 17 ^禪展置16，17，20及依控制訊號cl， …之狀態而定的結構/運算模式祇是可能的方式之 、尚有他不同的可能方式可資應用於本發明範圍之 内。沒包括了運用其他的控制訊號，此將揭示於後。 圖8之、、、。構有另兩個其他的控制訊號c4及，其增加 結構的多功能性而不用重 ^ .y t 重新、、且構。弟4個控制訊號c4啟動 (例如c 4二1 )或停止f办丨丨、 丁止（例如c4=〇)介於第3管線階段内之 29 1263167 壓縮陣列4的輸出與輸入之間的回饋迴路。於是，若 ^ C2—C3 = 1，C4=〇時，該結構作為乘法器，·若心2吩c4】 守，该結構作為MAC單元。第 1，2或3你分f w 制況號c5 (其可能為 次3位㈣虎）控制第i管線 Γ度，以允許(例如C5為邏輯。或停止(二= 1Γ ΐΓ"σ" 5^4fa1"^^#^(carrypr~^^^ 後數加h陣列包括spj@ m位元輪人的加/減法哭 :刼作為複數2sp個m/2位元輸入的加/減法器，或可； 作為複數_個m/4位元輸入的加/減法器，等等。另外 選擇區塊3, I縮陣列4,及最終加法器5可稍作修改，以 由一個訊號控制及實行不同精確度的乘法器/mac運曾 也是可能的。 t 矩陣向量算術架構 以下，依據本發明的有效實施例之乘法器/MAC單 元結構用於實行矩陣向量運算，例如，純量至向量，或純 量至矩陣之運算。矩陣至向量乘法運算（及矩陣至矩陣乘法 運算，反矩陣計算，顏色反轉，快速正交變換，例如卯丁， 快速DCT，等等），以及捲積，有限脈衝回應濾波，及濾波 器組，特別是分離小波轉變應用。這些運算的共同點是被 乘數X是被乘以若干乘數屮，ί = 1，···，Γ。另一方面，一個高基 數乘法的重要特徵是顯著的複雜性從第2步驟（部分乘積加 總）移至弟1步驟（形成部分乘積）。基數越高，越多複雜 性轉移。 此可取之應用的主要構想是共同被乘數χ與第1個乘 30 1263167 數al的可此σ卩分乘積祇計算一次，然後重複使用這些部分 乘，於Χ吳其他乘數、2，...，Α：，相乘時。如此，k個乘法 ，二中祇須-個，皮完全執行，其餘的k_i的乘法運算則為非 凡王地三亦即不執行基數高於4乘法運算中最複雜的部分 (即计异可能部分乘積）。很明顯地，如此將可在時間及電 源/能源消耗方面達到顯著的節省。 依據此構想，為矩陣向量算術設計的架構之一般結構 可推&自本發明的第i個有效實施例中的乘法器單 元結構及第2個有效實施例中的可組態化裝置。此可由組入 -個記憶體21而達成，如圖7及圖8所示。存在一第㈣ 控制訊號C6，記憶體21據之以開放（第6個控制訊號c6 例如設定為邏輯〇 (低)）或關閉（第6個控制訊號c6例如 設f為邏輯1 (高））寫人。當狀記憶體為開放寫入， 可能部分乘積可由複數加法器陣列2的輸出儲存至記憶體 21。同一個控制訊號〇6可用在控制2: i多工器22。多工 為22的第1個輸入是連接到複數加法器陣列2，且多工器 22的第2個輸入是連接到記憶體21的輸出。於是，可能部 分乘積可直接由複數加法器陣列2 (第6個控制訊號“例 如設定為邏輯0)或記憶體21 (第6個控制訊號例如設 定為邏輯1)進入複數選擇區塊3。 圖9揭示矩陣向量算術結構之例子，其中兩個仲⑼ ，兀倍數累加運算可以同時實行。此結構組入分開的選擇 區塊3a及3b’由兩個不同的乘法器位元所控制。相同被乘 數（若C2,的可能部分乘積，或不相同兩個被乘數（若 31 1263167 C2矣q)的可能部分乘積可選擇作為選擇區塊仏，几的輸 入。兩個選擇區塊的輪出接著輸入至兩個各別有31個位元 回饋（於此例’ b=32是最終累加結果的最高位元精確度） 的麼縮陣列。這些壓縮陣列的總和s及進位c的輸出可合 :於(4x31)輸人壓縮陣列，其後跟隨—個最終加法器形成的 累加項，或可成對相加形成兩個累加項。如此，兩個分開 的塵縮陣列各有一個較小深度，即較短的回饋迴路，操作 ^累加階段。之後，兩對的總和項與進位項，或分開地（以 、對方式）相加於兩個CPAs(carry_pr〇㈣咖礙u，進位 味达加法器）’或共同地相加於第3個總和區塊。在第Hg) 二況兩個分開的運算的結果（例如，矩陣向 ㈣個輸出元素）是同時得到，在第2個情況，—個複^ 异被^成兩個較小的運算，再將所得結果合併。 μ貫際上’任何讀/寫記憶體可用在設計的矩陣向量計 ^結構中。兩個可取的記憶體形式揭示於圖10a及10b中。 中的記憶體形式相當於以個長度 存記憶體，其中L之异谇θp %什时之皙 能部分乘積於-個暫存」足以儲存一個被乘數的可 曰疋乘法運异中所用的基數，以及s ::二ί::中的加/減法器的數目。這個記憶體的定 位址環咖0規則對於每個正整數㈣產生 位址。^表示在運算階段叫，…，定址單元產生 為目前的位址值。然後，在輸入線上的可 以刀宋積值寫到暫存器會α㈣，WM，若第6個控 32 1263167 制訊號c6是低值（至記憶體 ♦ 的内容，即之前^者’暫存器會 至輪出線，若第6個控制訊號〇6是=能:分«值被寫 第2個記憶體形式揭示在圖i :了思體)。 每個運瞀步驟，笛Λ 制回饋的移位暫存器。在 ㈣，步驟’ ¥ ρ個暫存器單元 移至第㈣個暫存器單元，如者J Τ，广:2 ’被 存器單元都有回饋線，所古从 曼者/又有停止。母個暫 器，該多工器有_輸入線===輸入至㈣·」多工 (Ιορ/^〜上 深作為輸入（至記憶體）。多工哭由 § )位兀矾唬控制，該值設定為 (若c6=〇)，或者由箆使侍由輸入來的資料 (若

罵至弟〇個暫存器中。 A 第0個暫存器作輪出。 a體通电都疋由 更詳：二：個：常應用於視訊及圖像處理的執行過程將 本2 應注意的是這些應用例子祇是特定的運算 本魯月不设限於祇有這些運算， 明。所有其他的運算包括一丘⑽士μ ]子也非即本發 法運曾括/、同被乘數乘以數個乘數的乘 外^依本舍明矩陣向量算術之架構作相 外，其，類似的運算法可發展於以下考量中。- 考慮純量對向量的運算xa，此乃最明顯的有效 貝一 & 一共同被乘數（純量）被乘以多數個乘數屮， 的 二第：個步驟，當執行共同被乘數與第-個乘婁“1 的采法運异時，第6個控制訊號e6設定為低值，使 部分乘積x直接由第1管線階段P1的加法器陣列2傳遞： 33 1263167 弟:B線階段P2的複數選擇區塊3，同時寫… 記憶體21依據m〇dl模式扭a 、寫至记憶體21。 個外皆停止。第1管線^’而其他的暫存器除第〇 個外也皆停止，若祇有^的^有的加法器陣列以除第！ 運算實行時。由第二個運：：：與一個或數個向量之乘法 設定為高值，使得記憶體始，第6個控制訊號“ 之後，寫入記憶體的可能邛八丁籍’ A亚將在弟-個步驟 由對應的多工哭的第'乘積X由記憶體21取出，經 所有加法器陣/2(=Γ 至選擇區塊3。同時， ,,^ (括弟—個）或停止，戋韓撫5足_/ 作業。如此時間節省的目 & 、另一個 部分’即計算可能部分乘積，n口：去除了最耗時的 及能源的節省可達成、 要I㈣了。顯著電源 …々 達成因為於K中的K-1個運算步驟中， 第管線階段是停止或轉移至# 在此計算李統中，第二另個作業。另-個優點是， 至以平:階段P1無須與其他線階段Ρ2 上。選有_ Κ中的K-1個運算步驟，其並不在要徑 祇須——，是t乘數x由外部記憶體（未圖示）提取 、#人，然而於先前技術中，必須提取K次。 第二，考慮矩陣向量運算，

Ux，或等同地 Ρ Σα/'，7Χ7 7=1 :l，u 、此運算是許多代數及視訊/圖像處理運算法的一部 二：：，矩陣對矩陣乘法運算，反矩陣計算，圖像顏色 、’快速正父轉換（例如TFT，快速DCT，等等）， Μ操作’邊㈣查’等等。矩陣向量乘法運算可視為多 34 1263167 重的向量對向量乘法運算，所以 執行運算。然而，瘅注音的θγΛ β Θ或—排MAC單元 〜，Μ户，乗以tf：：的疋輸入向量X的分量（被乘數） 依據本發明的〜其為矩陣A的第j行分量。 量ί=:二例，結構中的記憶體2"乍為矩陣向 并對輸入向置X的每個分詈 = = = Γ可能部分乘積則儲存於 ，、已3足夠的暫存器（即户以）。 長路f述^⑫，在圖形理論巾是表示起始點至終點的最 =理:f用於本發明時’要徑表示在管線化系統中’ 過程的起點至終點的最長路線。要徑的長度表示 声的“…、 析，可發現影響要徑長 二的糸、、先某‘刀。當發現後，可解析並找尋縮短該部分長 ς ^性。相對地’試圖縮短不屬於要握的部分通常是 不須要且也是無助益的。 〃為初始化(hP)矩陣對向量的乘法運算，依據本發明實 把例’結構應依適當的控制訊號值組構如下。依_dp模 式’記憶體21設定啟動，且暫存器從記憶體的？至r停止、。 架構，壓縮陣列4藉由將控制訊號以設定為高值，而作為 累加器使用。第6個控制訊號C6^開始時設定為低值，當 每個分量勹，/ = 1，.·.，ρ的可能部分乘積於p個操作步驟田 Ρ +1’··.，/? + Ρ中形成，其中步驟Ρ是第一個管線階段的延遲， 其等^管線階段内加法器陣列的數目。在這些操作步驟 中刀畺xy，J =丨，.··，户的可能部分乘積直接從第1管線階段 pi的加法器陣列2經由多工器22傳至第2管線階段？2的 35 1263167 :旻數選擇區塊3，並於同時寫至記憶體21。於是陣列a的 弟1列與輸入向量χ的乘法運算得以實施，並且同時地將每

個分暑Y 7 yM，.·.，户，的可能部分乘積儲存於連續的暫存器 =贼在P + P運算步驟後，控制訊號C6設定為高值，使得記 f思體21關閉耷λ η . ”、、，且χ厂，可能部分乘積循環地由 ^ 、、二由2 ··1多工器的第2個輸入擷取複數選擇區塊 ^ 第5個控制訊號C5於一個步驟設定為低值以重 ^二新的累加器。如此重複Κ_1次，直至矩陣A所有的 J白乘，向里χ。由操作步驟^户開始，所有加法器2陣列 包括第1個）若非停止就是轉移至另一個作業。如此， ρκ曰個立乘法運算中的ρ個是完全實施的，而其餘的ρ(κ])個 5部分：施，即不包括最複雜的第-步驟。與純量對向 里乘法運算之案例相似，這個運算也導向顯著時間及電源 /能源消耗的節省。 、下將依據本發明的捲積或FIR濾波作更詳細的考 慮。該運算式為 p 〜= Σϋ，i=i，.··，尤， 7=1 中，通常P<<夂。有兩個方案是可能實行FIR濾波於 依據本發明矩陣對向量運算的結構。 2 一個方案中，FIR濾波被視為p-對角線矩陣A與輸 向乘去運异’該向量有P個分量X/，卜-尸+ 7，·..，0對應 至負2標並向下移動P個位置。基於矩陣A是稀疏的（祇 有p料線有非〇項），上述之矩陣向量乘法運算的—般方案 1263167 ^為™濾波稱作修改。矩陣Al列”U，祇有？個 非〇項目，濾波系數~，风.·，户於行讲1，/ + p —!。在此實 :::二對輸入向量的所有分量而言，可能部分乘積非同 二 =記憶體中，而是祇有p個分量的可能部分乘積被 =儲存。母P個運算步驟，一組新的目前輸入之可能部 於複數加法陣列内’並取代記憶體21中較早的 卢這是藉由每p個運算步料定第6個控制訊 C6至低值而達成。因此加法器陣列2無法完全停止，作 =了時緩慢P倍，且不儲存可能部分乘積。祇-的㈣個乘法運算是完全實施，而其他祇有部分實施。 的可案’當計算第—個輸出取樣時，P個瀘、波系數 輪存，記_ 21 °然後’當計算其他κ·ι 這音著能部分乘積循環地從記憶體21取出。 PK中的p個乘法運算是完全實施，其 纪施所:旦所有的濾波系數的可能部分乘積儲存於 業 > 茶疋更有利於第1個方案。然而，筮9 度二官線階段P1的加/減法器2有足夠精確 ;ί 可能部分乘積時，才有可能實施。 現訊/圖像處理之多功能架構 =發明的結構可有效地應用為視訊/圖像處理多功& AVIP)。圖11揭示—個依據本發明視訊處理杜構= 有效貫施例。此實施例έ士播 ϋ冓的 構24。湖架構之_^= /謂絕對差和（，架 般釔構揭不於圖4，其中包括以時間 37 1263167 差方式操作所謂訊號差（DS)單元25的複數陣列，一有回饋 的壓縮陣列4，及一個最終加法器5其後跟隨一個最小評量 器（M)單元26，此單元須用於動態評估處理（基於SAD)， 但對SAD的計算本身是不須要。每個ds單元25(DS陣列 或縮寫為DSA)包括S個DS單元27(圖5)，其中每一個是8 位元減法器，其後跟隨著XOR閘28介於符號位元及其他的 差值位元之間。壓縮陣列的輸入是由s個丨位元（符號資 料），S個n位元（差值資料，通常n=8 )，及兩個 位元回饋（通常，K=256)。最終加法器可能有（w+1〇g幻位 元精確度。一個SAD架構的例子包括8個DS單元（減法 器）及對應至尸7，fS，Η，及尺ϋ的情況顯示於 圖6 〇 比較圖4的SAD結構與基於圖8之結構的乘法器，及 特別是比較圖6與圖8或圖9之結構，可注意到兩個結構間 一些重要的相似處。兩種結構類型主要皆包括一含複數加 法器或減法器的區塊4，27 (在SAD實例，其跟隨著一個 XOR閘），資料選路區塊（data routing M〇ck),其在以乘法 器為基礎的結構之情況是選擇區塊3，在SAD之情況則是 直接連接，以及總和區塊包括壓縮陣列及最終加法器。= 些相似性可作為統一這兩種結構，並結合為一可組態化架 構，其可使用少許控制訊號而組構成這兩種結構任何之、 一。如此，更進一步的架構之多功能性可用極少的簡單邏 輯訊號控制之代價而達成。 有數個可選擇方式用以結合SAD結構與乘法器結構。 38 1263167 圖11表示可選擇方式之一的視訊/圖像處理多功能架構的 一般結構。此結構是經由簡單修改基本乘法器為基礎之結 構的每個區塊而得。此情況，基本結構是圖8所示的矩陣向 置计异架構。圖13表示由圖9之矩陣向量計算架構推導得 之視訊/圖像處理多功能架構之實施例。 在一個實施中，視訊/圖像處理多功能架構包括加法 器2陣列，其可依第1個控制訊號C1及第5個控制訊號C5 組構成加/減法器或DS單元，因此可表示為Aa/dsa。一 個AA/DSA單元之可能實施例表示於圖12。每m位元加 /減法器陣列由r個連續（m/r)位元加/減法器跟隨著一 XOR閘組成（於圖13， m=16， r=2)。因此，X〇r閘祇活 動於當時，即（Cl，C5)=(1，〇)，當架構操作為sad架 構時。另一方面，介於r個連續（m/r)位元加/減法器之間 的進位延伸可提供於祇當h =〇時。第1個控制訊號C1及第 5個控制訊號C5的結合也可用於控制是否數個不同輸入 (W4)(加數或SAD運算元）或者一個輸入(被乘 數）進入陣列中。無論是實施加法或減法皆由訊號控 制，其依據乘法運算法及位於AA/DS A單元内之m位元加 /減法器的位置而定。如此，依控制訊號c丨及C5， AA/DSA早元可以組構成不同型態的運算如下· 39 1263167 (Cl,C5) AA/DSA運算模 式 — 輸入 輸出 _ π平行加/小位元 加/減法 π 酉己 對（XA)， i=l, ...,r rs (m/r+1)-位元 總和 ^=1/+乂·， 平行加/減法器 (〇J) s平行6^-位元加 /減法 —------- nsYm/rj-位元配 對(X妙/), i=l，…，r rs (m/r+1)-位 元差值 (1〇) a (m/r)-位元平行 減法，然後X〇Rs rs 位元配 對(χπλ i=l，…，r rs 位元 Μ： 值資料，及μ [ 位元資料 SAD架才 階段（複數DS單 元） (U) s加法或減法依據 基數-T乘法運算法 ------ l(m-t)-位元乘 數(MogT) s m-位元部分 乘積及a 7-bit 0值 基數-Τ乘法ΐΐ 第一階段(ΑΑ) 圖11的MAVIP實施例中，有一個資料選路區塊介於 AA/DSA單元區塊與壓縮陣歹區塊之間，其由與aa/DSA單 元相同的訊號C1與C5控制。選擇區塊的時鐘訊號（未圖 示）藉由一個及閘結合訊號C1使得選擇區塊停止於當C1=0 時。架構在此情況操作為加/減法器的平行陣列。依據控 制訊號C5，資料選路區塊或組構成直接連接，如同在SAD 架構内（若C5=0)直接由AA/DSA單元的輸出傳送r個（m/r) 位元差資料及r個1位元資料至壓縮陣列，或作為相應的乘 法器結構内的標準選擇區塊，由AA/DS A單元或記憶體傳 送S個m位元平行乘積至壓縮陣列區塊。此藉由插入一個 資料一體化編碼器/多工器區塊（data unifier / multiplexer) 23從相應的線路選擇資料而達成。資料一體化編碼器/多 工器區塊23或選擇AA/DSA單元區塊的輸出，若C5=0,或 選擇區塊的輸出，若C5 = l，並將資料類型轉換為適於壓縮 陣列4的型態。例如，圖13中的壓縮陣列的輸入包括兩組 40 1263167 以較快速地累加更多的部分結果。 表3列出一些運算其可實行於圖13的MAVIP實施例伴 隨著相關控制訊號c Y，·.·，9之選擇。 表3

Ϊ~~W ~---- 控制訊號 ^^ Cl C2 C3 C4 C5 C6 C? 平行8-位元加/減法 一'一'-- SAD ~~~~~--——- 0 x x x 0 1 1 fjrv 1 3fe 〇4- -----—_—- 1 x x x 0 0 1 rkx 1 ^ 5 (1 v1JVTq~7Z a~~~~--~~-—-- 1 x 0 0 1 1 〇 ()至（lxk)13位几向量對向量内積(k<65) 10 0 110 (記憶體不在使用） _)至（lxk)13位福量對向量内積(k<65) 111110 ~~〇~ (記憶體在使用） (P )至(kXl) 13 位 長度P tfL號灸-查汉敏τπτ> ------- 1 C2 C3 1 1 0 〇 C2=c3=0 first (k/2) cycles and C2=C3=1 after that ----------_____________ 1 c2 c3 1 1 0 0 C2=c3=0最初（k/2)楯環反 之後 C2=C3==J 許多不同的可選擇方案，因為乘法器/ 個社Μ Γ 干不同類型的延伸可供制。此外，每 ==設計參數的選擇導致不同的可選擇方案。本 裝置。-可選擇的方案是蜀立(緊密或分開成對) 這種配置可取代處理器内的乘=處理器内的功能單元。 擇方案可達相同目H中I早7"。尚有其他許多可選 部分，不包括複數加法哭陣列/貫施於不同實施例之一 ° "弟1管線階段Pi)及記憶體 43 1263167 21 ’而用作為處理器内的功能單元。處理器的加/減法哭 則作為複數加法器陣列，而暫存器作為使用於矩陣對向二 運异結構内的記憶體。 、。里 爲 π 1我器（Texas lnstrUments)TMS32〇C64x DSi

p包括8個功能單元，其中6個可操作為料位元的加/減g 器，這每一個可操作2個32位元或4個16位元或8個/8必 兀之加/減法器。其尚包括128個64位元暫存器，這每一 個可用為2個32位元或4個16位元或8個8位元之暫存哭 假設另-個功能單元（FC)類似圖6所示，但沒有加法器^ =區：包括ΐ處理器内。如此，此功能單元包括複數個選 -鬼，禝數個壓縮陣列，個及複數個快速最終加 法運算或乘法為基礎的運算於以下兩個循環（目前 士 〇C64x乘法器之乘法運算也採兩個循環）。於第工個 、:吉=暫力;C咸☆器計算被乘數χ的可晴^ 選並、她子為。接下來步驟中，適當的部分乘積組將被挑 使用二ΐίΓΓ單71。在此實例中，被乘數X被重複 祇^涉人的乘法運算時，第1個循環可能 紙執仃一次，但 b 時間盥能源d M則省略而導向顯著 地小的系數，實施FIR遽波（捲積）以—合理 用於數個(可铲_個)oc?x的加/減法器於開始時，將祇被 積，並料、纟^㈣:能部分乘 貫行於功能單元，而載入 ^、之冲具則依本發明 減法器於其他的目的 子早7^則給予機會使用加/ 、他的目峨料使肋節 44 1263167 ™S32GC64X1前實行™滤波時，所有功能單元包括乘法 恭及加/藏法益皆忙碌於該作業中。 宋去 尚有其他的可選擇方案可對不同的位元精確度 發明的可取結構，„BI例如，—法I器單心二 -個㈣乘法運算，或兩個㈣…或似㈣乘法運 4個(《/2)+/2)乘法運算於一個操作步驟。 '-或 圖14揭示-個依據本發明的有效實施例 f置包括一個控制單元30以控制裝置的操作。此裝置還t 括一個數位訊號處理單元3】作垚每一 ^ 替㈣m义 貫订其他處理作業，例如 據本發明—有效實_的計«置1適合應用 體:。理為二3二此t理t元也可包括-個有效的共同記憶 41由/理二衣/控制單元3〇所用，及一個内部記憶體 奸壯:早7^ 1作為内部使用，例如儲存可能部分乘積。 =置的制者介面33包括顯示裝置34,音 積 :36:及例如一個視訊相機37。裝置29包括通訊裝置％建 :J:I動通訊裝置，以與通訊網路聯通及與其他類似的裝 :貧訊（未圖示）。記憶體裝置39用於儲存不同的資料 王式例如控制單元30的操作指令。

本么明不受限以上揭示的實施例，而可依據下 h專利範圍作修改。 T 45 Ϊ263167 【圖式簡單說明】 基數4 BOOTH重新編碼乘法器的標準結構， 圖2基數TBOOTH重新編碼（⑺）或非重新編碼（Μ) 乘法器的一般結構， 圖在平行基數T MAC單元結構内之總和區塊的實施 例，其中總和區塊是作為n/t選擇部分乘積及回饋與 進位項的一般壓縮區塊，

^另^固在平行基數T MAC單元結構内之總和區塊的 實施例，其中總和區塊被實行為分開的壓縮陣列， β 4絕對差和的-般結構，其中Ds單元作為減法器， XOR(互斥或）閘跟隨其後， 圖5 Ds單元的一般結構， ，6絕對差和結構，其中㈣，dn θ根據本發明第一個有效實施例之計算裝置社 構簡化圖， θ根據本發明第三個有效實施例之複數個乘法/财〔

圖9 Γίί可組態化計算裝置的一般結構方塊簡圖， 根據本㈣的兩個同步⑺奶）位元倍數累加運省 的矩陣向量計算架構的有效實施例， ' 圖心備有—個在循環_d Ρ模式的暫存記憶體， ϊ :Γ:ί:個在循環m°dp回饋迴圈的移動暫存記憶體, " 根據本發明作為視訊/圖像處理多功能竿槿Μ## 圖U AA/DSA單元的實施例， 力月匕木構的結構， 圖13將圖6中的SAD結構及圖9中的矩陣向量計算架構 46

Claims (1)

1263167 拾、申請專利範圍： 【申請專利範圍】 !•一種使用由-組至少第一及第二之兩個管線階段、 至少-個資料輸入介面、及至少一個資料輸出介面所 的管線化計算裝置實行運算的方法，該管線階段含至少一 個資料輸入介面及至少一個資料輸出介面；在該方法中， 實行第:與第=運算之資料是輸入至該計算裝置，其特徵 在於該第一運算中，至少-個管線階段的輸出資料 园ί·> 式土 於§己憶體’而在弟二運算中，將兮性左一 段的輸入資料。，中將《存之㈣作為管線階 -= Γ 1項之方法，其特徵在於該方法為 回基數非Booth重新編碼運算方法。 3·如申請專利範圍第1 作為第一個、方法，八特徵在於該運算分 果儲存起來，^ 運"' 弟一次運算的結 子起來再運用於複數個第二次運算中。 4·如申請專利範圍第1 為乘法運算，苴中被^ : 徵在於該運算是 被宋數乘以一個乘數，於第一管蟑 於記憶體。 ^卩刀乘積，並將可能部分乘積儲存 5.如申請相範圍第1奴方法，其特徵在於該運算是 48 ί ι·；Κ. 1263167 為乘法運算，其中被乘數χ乘以數 算共同被乘數（X)的可能部分乘積；春（^㈠…欠)以計 數幻時，可能部分乘積儲存於記憶三？，&數乘以第—個乘 乘積用於乘數（χ)與其他乘數0,, ❼儲存之可能部分 1， , 幻相乘時。 6·如申請專利範，項之方法 少部分地是以時間差方式實行， 、$ 運算至 個部分次運算，並指定每個部欠们人運异分為數 刀大運异予不同的時間。 7. 如申請專利範圍第！至第6項之任 徵在於該方法係用於視頻資訊處理。 、之方法，其特 8. 如申請專利範圍第1至第6項之任一項 徵在於一個乘法運算與另一 、之方法，其特 另-=運算開始操作於前此 r個乘法運算至少分為第！與第2個次運曾’ί之則，此 异於一個管線階段中實行，、 斤母一個次運 於-個管線，第二個乘法運*二财運异是平行實施 運算完成之前。運异的次運算開始於第—個乘法 9·如申明專利範圍第j至第 徵在於選擇資料路徑是實行於計算裝置，其特 個資料介面選擇於其他至 -中對於至少- 一個資料介面與所選擇M 以連接該至少 谇貝科介面作為資料選路。 49 1263167 i〇. —種使用由一組至少第一及笙一 a .η 乐一之兩個管線购 &、至少一個資料輸入介面、及至少— 八 構成的管線化計算装置實行運算的系統，該管:= =!料輸：介面：及至：一個資料輸出介面二： t衣置還包括第一與第二運算用之資 在於包括一個記憶體（21)以儲存上述至少"二個总:”徵 第-運算輸出資料’及一個資料取出器蚀又的 作為第二運算中管線階段的輸入資料。（）將所儲存之資料 n· Μ請專職圍第⑴m其特徵在於該計 名置為一咼基數非B〇〇th重新編碼乘法器。 管八12·如中請專利範圍第1Q項之系統，其特徵在於 ^刀成為一個實行於第一管線階段的第一次運曾， 個實行於其他管線階段的第二次. :设數 算結果被難於記⑼，而1；：’弟—個次運算的計 于、匕u骽U1)，而一個貧料取出哭，1 個多工器連接記憶體之輸出至其他至少一個管線階匕二 次㈣存料算結果使用於上述之複數個第二 13·如申請專利範圍第10項之系統，其特徵在於當一 官線階段包括加法器⑺陣列，第二管線階 擇 ⑺’第三管線階段包括厂堅縮陣列(4)，及第四管線=鬼 50 1263167 進位預測力σ法器（5);第一管線一 記憶體之輪Α @ 5次 又、輸出資料介面連接至 連'至資料取出器之另一個輸入二二;體之輪出 接至弟二管線階段的資料輸入介面。 ☆之輪出連 14· ’申請專利範圍第1 〇項之系絲，甘 憶體包括複數個斬广σσ 、 …、、，、特徵在於該記 括-個定：！"'，每一個暫存器儲存-個值，及包 们疋址早7C當於暫存器之一 及包 器讀/寫資料。 Τ，作為從/至暫存 15·如申請專利範圍第1〇頊之糸紅^ 憶體包括複數^ 、.糸、、先，/、特徵在於該記 ⑬數個暫存杰，母_個暫存 值，及包括_個多工顿女排錯存一個 一的於屮、， —。口 、擇體的輸入或暫存器之 存器的輸出連接至記憶體之輸出弟，存…第-個暫 統，1盆6特1〇至第15項之任一項之系 一符徵在於其包括至少一個吝工哭从去w -輪出資料介面及一個第 I…攸至少一個第 (IM，P2，pw^ 出貝料介面選擇至管線階段 在門題中1 、輸入貧料介面，此第-輸出資料介面是 在另碭中則一個管線階段的輸出。 17·如申請專利範圍第10至第15項之任一項之奉 統’其特徵在於其包括視頻資訊處理之裝置。、” 51 1263167 1δ· 一種使用由一組至少第一及第二之兩個管線階 至；一 4固貝料輸入介面、&至少—個資料輸出介面所 的管線化計算裝置實行運算的裝置，該管線階段含至 二7個資料輸入介面’及至少一個資料輸出介面，而該計 2置還包括第一與第二運算用之資料輸入；本裝置之特 二在於包括-個記憶體⑼以儲存上述至少—個管線階段 料運算輸出資料，及一個資料取出器(22)將所儲存之資 艸作為第二運算中管線階段的輸入資料。 19· μ請專㈣㈣18項之裝置，其特徵在於該計 ν、置為阿基數非Booth重新編碼乘法器。 曾八士、力y ^ 、衣1 ’具特徵在於該運 二成^個貫行於第—管線階段的第_次運算，及複數 ^订於其他管線階段的第三次運算；第—個次運 异結果被儲存於記憶體⑼，而一個資料取出器，其：。— :多連接記憶體之輸出至其他至少一個管線階 ： =面’將儲存的計算結果使用於上述之複數個第： 如申請專利範圍第18項之裝置 52 1263167 進位預測加法器（5);第一管線階段的輸出資料介面 :憶體之輸入及至資料取出器之一個輸入，記憶體 接ϊί她出器之另一個輸入，而資料取出器之輸出連 接至弟二管線階段的資料輸入介面。 22 ·如申請專利範圍第18項之裝置，i特微名## :體::複數個暫存器，每一個暫存器錯存—個值，： 器讀% =元當於暫存器之一定址時，作為從/至暫存 划Τ謂·寻利範圍第 值，及包括-個多工器用以選擇記情 女排储存—個 -的輪出’並將選資料儲存於第一個：：入或暫存器之 存器的輸出連接至記憶體之輸出。9 且弟一個暫 24·如申請專利範圍第18至 置，其特徵在於其包括至少—個夕σσ 、之任一項之裝 -輸出資料介面及—個第 =器作為從至少-個第 (PI，Ρ2, Ρ3，Ρ4)的輸入資料；面貝料介面選擇至管線階段 在問題中前一個管線階段的輪出。’此第一輸出資料介面是

25· 如申請專利範圍 其特徵在於其包括視 第18至第23項之任— 頻資訊處理之裝置。 項之裝 53 1263167 26·如申請專利範圍第is至第 置，其特徵在於一個乘法運算與另 -個管線階段的輸入資料介：置至包；:：㈣位於至少 至少-個管線階段的輸出，以及 α夕工杰位於所述 管線暫存器，使得祇有—個管㈣控制上述之 至所述管線階段的輸人資料介面^開發於寫入資料 至少第-與第二次運算，料·— .Λ之乘法運算被分成 個第 行於-個管線階段，而其中至少―個=次運算被執 實行於一管線，其中第二個乘法運I 破女排平行地 於相應的第-個乘法運算的次運算、^^運异破安排開始 27·如申請專利範圍第18至第23 置，其特徵在於其包括選擇資料路徑之穿員1壬:項之裝 此選擇裝置包括連接一個資 二（，3,4,5)， 面之一作為資料選路。”丨▼夕兩個其他資料介 罢2甘8·如申請專利範圍第18至第2S項之任一頂之壯 /、特被在於其包括一個無線通訊裝置。 、衣 置I·特:二範圍第18至第23項之任-㈣ 在於其為一積體電路。 其特徵在18至第23項之任一項之裝置， 54