平行處理的計算方法

【摘要】平行處理不只要有足夠多的處理單元；更重要的是要有好的平行計算方法……

很多人以為平行處理（parallel processing）只要有足夠多的處理單元（processing unit）就可以解決一切問題，因此只在硬體技術的發展上投資大量的金錢和人力。其實，更重要的是平行處理要有好的平行計算方法（parallel algorithm）。如果沒有好的平行計算方法，即使你擁有一百萬個處理單元也是毫無意義的。

兩兩交換排序法

讓我們以一個將數字由小到大的排序問題來說明。讀者也許知道在傳統的計算機上，如何處理一千個數字的排序問題。但是，如果給你1,000個處理單元的平行計算機，你該怎麼做呢？是不是反而有英雄無用武之地的感覺呢？事實上，這是因為你不了解排序問題的平行計算方法。

有一種叫做兩兩交換的排序方法（odd-even transposition sort）可以幫助你解決這個問題。讓我們考慮用6個處理器來排6個數目的大小。這六個數分別放在PE（1）, PE（2）, ……PE（6），排成一線的六個處理單元裡，如圖一所示：而這個排序方法的動作就如圖二：在每個奇數的步驟裡，每個單號的PE（i）和PE（i＋1）做比較與交換資料的動作；將較小的放在PE（i），將較大的放在PE（i＋1）。而在每個偶數的步驟裡，每個雙號的PE（i）和PE（i＋1）做同樣的動作。經過五個步驟之後，排序就完成了。對於任意N個數用N個處理器，可以用上述的方法在N－1個步驟後排好大小。

上面這個方法也稱為“systolic”的計算方法；systolic是心臟收縮的意思。當心臟正常收縮的時候，血液被送到身體的每一個角落，而systolic計算方法在一群處理器上同時運作，每一個處理器就像心臟抽送血液一樣地輸入及輸出資料。

讓我們再看一個矩陣和向量乘法（matrix-vector product）的systolic計算方法來加深印象：對任意一個矩陣 


和向量

 

計算

 這個問題可以靠圖三所示的處理器做為解決問題的基本元件，這個元件可以靠一個乘法器和加法器做成：每當z_in和y準備好之後，就可以由z_out得到z_in+x^.y的結果。用三個基本元件像圖四般的組合，並將資料依序輸入便可以工作了：

用上面的結構，我們可以在各時間內得到以下的計算結果，而被框起來的那三個就是我們的答案：
是不是？這是一種相當優美的平行計算方法。

分裂與各個擊破

systolic計算方法並不是唯一的平行計算方法，事實上我們可以靠「各個擊破」（divide-and-conquer）法則導出許多其他的平行計算方法。讓我們來考慮8個數1, 2, 3, 4, 5, 6, 7, 8找最大值的方法：

步驟一：將8個數任意分成兩堆^{1, 2, 3, 4,}_{5, 6, 7, 8}

步驟二：分別求這兩堆數的最大值，其結果分別是4和8

步驟三：對4和8求出較大值8，這就是我們的答案

大家可以看出在步驟二中已經有平行性的存在，即有二組「四個數求最大值」的問題，可以同時而互不干擾地解決。而每一組「四個數求最大值」的問題，又可以靠遞迴（recursive）各個擊破的法則，繼續分解而求解，而最後的答案是由步驟三做合併（merging）而得。

要利用各個擊破法則來導出問題的平行計算方法，最重要的就是了解問題的性質而找出好的合併方法。讓我們考慮8個數：8, 1, 2, 4, 6, 7, 5, 3的排列大小問題，我們以下列的步驟來處理：

步驟一 將這8個數任意分成兩堆

8, 1, 2, 4和 6, 7, 5, 3

步驟二 分別地（互不干擾而同時地）去解決兩個4個數的排列大小問題，我們得到

1, 2, 4, 8
和 3, 5, 6, 7

步驟三 將上述兩列中單號的數1,4和3,6合併，雙號的數2,8和5,7合併，這兩件事也可以不相干擾地同時做。於是我們得到

1, 3, 4, 6
和 2, 5, 7, 8

步驟四 將雙箭頭所指數對同時兩兩比較交換
結果就成以下的大小排列在步驟二裡，我們仍是遞迴地用同樣地方法各個擊破，這個方法就是有名的Batcher兩兩合併排序法（odd-even merge sort）。

超級電腦的管線計算原理

以下我們要介紹最近流行的超級計算機（如Cray-1和Cyber 205）的基本工作原理，同時我們也要介紹如何設計適合這種超級計算機的計算方法。

幾乎所有商業上的超級計算機，都用管線原理來設計。假定我們有m個相同的工作要處理，每個工作的處理過程需費時n個時間單位，那麼處理全部m個 工作要花m×n個單位時間。

但是，我們可以將處理過程分成k個階段，每個階段都由一個處理器來執行。那麼，整個處理過程是由一連串的k個處理器來執行，如圖五所示。我們也可以假定這m個工作，是一個接著一個送進這一連串的處理器的。於是，當1號處理器完成第一份工作第一階段的處理後，第二份工作就送進1號處理器，而2號處理器就開始處理第一份工作第二階段，我們以k＝3來作示範，整個的過程如圖六所示，在步驟3之後所有的處理器都同時工作著，除了起動時間（start up time）外，每個步驟都有一個工作完成。從時間上來比較，原來需時m×n，現在只需，我們可以說整個過程增快了k倍。當k值慢慢增大時，速度的增快就逐漸顯著了。

超級計算機之所以快，是因為下面二個理由：一、處理器使用高速的元件，每一個動作只需極短的時間單位；二、處理器使用管線原理製作，每一個運算的處理過程都分成了許多階段。

讓我們看一下圖七，這是一個應用管線原理處理指令的典型例子。當抓取一個指令的動作完成後，如果可能的話，處理器會去抓下一個指令（當然，我們要知道下一個指令要到那兒去抓，才能做這件事）。所以讀者應該可以了解，對超級計算機來說，當運算和數據變得有規律和重複時，計算方法就變得相當有效率了。

Cray-1的單位動作時間（clock cycle）是12.5×10^-9秒。一個乘法要七個單位動作時間，那麼，在一秒內可執行次乘法，但是如果是向量運算的話它會更快。

假定我們有二個向量x=(x₁,x₂,…,x₆₄)和y=(y₁,y₂,…,y₆₄)，而且我們想要計算，在這個例子裡，我們可以看到，除了起動時間外，所有的處理器都同時地忙碌著，如圖八所示。從使用者的觀點來看，在穩定的狀態下，每一個單位動作時間都有一個乘法完成，所以在一秒鐘內，執行乘法的數目是

Cray-1裡還有一個加法器（adder）可以和乘法器（multiplier）同時工作，所以Cray-1在一秒鐘內所執行的運算的全部數目是160×10⁶。這也就是為什麼我們叫Cray-1是160Mflops（mega floating point processing per second）的機器了。下面一個例子可以說明即使是超級計算機仍然要有好的計算方法，才能使它有效率地工作。

我們要解決下面的帶狀線性系統（banded linear system）的9階聯立線性方程式的問題：

從表面上看來，這個問題幾乎不可能有效率地在超級計算機上解決。我們雖可以馬上求得x₁，但求得x₁後才可以求得x₂；x₂求得之後，才可以求得x₃；然後如此繼續下去。這些過程似乎和超級計算機所擅長的向量運算無關，事實上，為了解決這個問題，有一個特別為超級計算機設計的計算方法。

這個計算方法基本上是消去a_i，我們把數據分成三部分，第一步如下所示地消去a₁，a₄，a₇。

舉個例子來看一下，要消掉a₁，我們用x₁=y₁和a₁x₁+x₂=y₂，可以得到x₂=y₂-a₁y₁。同樣地x₅=a₃a₄x₃+(y₅-a₄y₄)，x₈=a₆a₇x₆+(y₈-a₇y₇)。於是我們就有了如下的三個向量：

然後運算y₂-a₁y₁=b₂，y₅-a₄y₄=b₅和y₈-a₇y₇=a₈，完成了之後，我們就可以得到x₁和x₂。

第二步，我們消去a₂，a₅和a₈，如下所示

做一下下面的運算 ，再一次地藉著組


合此三個向量，就可以得到b₃，


b₆，b₉，完成之後就可以求得x₃。求得x₃之後，藉由下面的方程式可同時求得x₄，x₅和x₆：

x₄=-a₃x₃+y₄

x₅=a₃a₄x₃+b₅

x₆=-a₃a₄a₅x₃+b₆
求得x₆之後，我們可以如下地求得x₇，x₈和x₉：

x₇=-a₆x₆+y₇

x₈=a₆a₇x₆+b₈

x₉=-a₆a₇a₈x₆+b₉

由此我們可以了解，要用像Cray-1這種超級計算機，仍然必須製作向量化的計算方法，才能提高計算速率。硬體技術一天天地進步，平行處理越來越接近實用的階段。在這篇文章裡，我們不厭其煩地強調計算方法的重要性，無非是希望讀者在驚歎硬體的突飛猛進之餘，更應該想想我們要如何去應用它們。

唐傳義、陳俊良均係交通大學計算機工程研究所博士班畢；李家同任教於清華大學工學院

回到最上面

科學月刊全文資料庫

最佳瀏覽解析度800*600，請使用IE4.0以上版本的瀏覽器

科學月刊雜誌社．金台灣資訊事業有限公司．圖龍文化事業股份有限公司版權所有
Copyright 2000 Science Monthly and King-Taiwan Information Technology Inc. All Rights Reserved.