計算速率的追求──

平行處理

【摘要】近五年來，平行處理的研究正大紅大紫，到底為什麼會有此現象？其研究內涵為何？本文將告訴你答案。

「人多好做事」──這就是「平行處理」的直覺觀念。如果一部計算機要花X秒才能算完的問題，用N部計算機「大家一起來」做，是不是能把時間縮短到X／N秒算完呢？平行處理的基本信念就是這麼平庸、單純。這種想法非但不新穎，簡直古老，而且做事的人，人人都會這麼想。

然而，近五年來，有關「平行處理」的研究卻大紅大紫；美、歐、日等工業國家在官方、學術界、企業界的通力合作之下，投入了數百計的研究計畫來開發「平行處理」的技術。為什麼有這種現象？為什麼要這麼做呢？

就近因來說，這一場競爭──結合了學術與工業的研究和開發的競爭，是日本第五代計算機計畫所誘發出來的。根據第五代計算機的計畫，所謂第五代計算機是智慧型的計算機，它不僅將擁有一些解決問題的智慧來幫我們做事，而且將以人與人溝通的方式一──用自然語言和文字一一來和我們交往，在這個命題下，計算機要做的事將遠比目前所能做的多得太多。根據研究的數據估計，要達到上述的目標，第五代計算機的運算速率至少要比目前同型的機種快數千倍、數萬倍，乃至數十萬倍。換句話說，如果第五代計算機無法比目前的快萬倍以上，它根本就成功不了。因此，計算速率的追求成為第五代計算機的命脈和成功的必要條件之一。也正因如此，激起了近五年來追求計算速率突破的狂熱。

電子計算機在本質上是一具電子儀器。所以，由儀器系統的觀點它的計算速率可由下列三個層次來增加：一、在元件層次上，儘量用快的元件；二、在包裝（packing）層次上，儘量減短訊號流經的途徑；三、在系統結構層次上，尋求更好的架構和演算方法（algorithm）以減少運算的時間。

綜觀這三個層次，在過去三十多年以來，計算機各種性能的改進，包括：容量、能力、效率、對能源的消耗、可靠性以及計算速率等等都得歸功於前二者：元件和包裝技術，而此二者之突飛猛進實與微電子技術的發展息息相關。然而，目前有些元件製作技術已趨飽和，有些元件的速率已趨近理論值之極限，今後要求速率上大幅的突破，其情勢早已今非昔比，不可能再循舊途改進。由另一角度來看，計算機的結構在過去三十幾年間一直沒有什麼重大的改變，也該是變一變的時候了。可是，怎麼變呢？如何突破傳統的結構？這個問題引起了所有研究人員的關心，並導致對計算的本質作更深入了解的探求。

馮紐曼模式

傳統的計算機結構是所謂的馮紐曼模式（von Neumann model），如圖一所示。在圖一（a）的機器裡，只有一個處理機，一個記憶單元和一個收發通道（input／output channel）。因為只有一個處理機控制全部機器運作，故又稱為單處理機系統（uni-processor system）。它做事的方法是：一個命令對應一組數據資料；命令加諸於資料則產生一個基本的運算動作；命令成串排列，一脈單傳地一個一個依次執行。這種操作的方式稱為單序操作（monosequencing operation），而這種計算機亦稱為循序處理機（serial processor）。這種結構和人做事的方法類似；人做事，也是以單序操作的形態為主。傳統的解題方法也依附這個結構，人們把它寫成程式，上計算機解問題。所以，馮紐曼模式是相當「自然」的模式，人們不知不覺地已用了三十幾年。它和人們配合得相當好，以致於寫程式時，幾乎忘了機體結構的存在，用不著擔心所寫的程式是否能配合計算機的結構作有效的運算──反正它們是配得差不到那裡去。

要突破這樣一個窠臼，實在不是件容易的事。溯本清源來探究計算的本質是必要的。要言之，馮紐曼模式是單處理機單序操作的典型，在此情況下，無論所解的問題為何，計算性質的也好，非計算性質的也好，都已無再變化之餘地。因此，為突破速率的極限，就自然而然地走上「人多好做事」的多處理器結構，也就是所謂「平行處理」的研究領域中了；人們希望用成千上萬的處理器堆砌出速度來！

基本概念與運用

根據上述的發展情形，「平行處理」一詞目前是用來泛指不只一個處理器（或處理元素，processing element）的計算機系統結構（參考資料1. 2.），其研究重點在尋找於多處理器情況下，什麼是理論上共同特徵？如何根據這些特徵來建立其理論模式？以及如何依據此理論模式來發展適當的演算方法（亦即平行演算法）？這些問題都觸及計算科學的核心問題，譬如：什麼是計算？以及如何計算？什麼是可算的和不可算的？如何評定一個演算方法的好壞等等問題。而這些問題，到目前為止都還沒有滿意的答案。也正因為沒有答案，所以吸引大批的研究者一探寶山的決心。這是平行處理變成熱門研究問題的主因和遠因。

前文已說過，平行處理的概念實在不是什麼新東西。設計硬體的工程師，老早就用過它了，這幾乎是每一位設計電路工程師都有過的經驗。在上一期的「計算機和語文」專欄裡，我們談「記憶與速率」的問題時，交織式的記憶庫結構和隱藏記憶（cache memory）的層次結構，就是兩種基本平行結構的典型。前者是將硬體加多（重複相同的硬體），並同時工作（存與取）以達到速率加快的目的。而後者是一種管道型式（pipe-lined）的安排，其目的在加大某工作流程中單位時間的流量。比方說，有一條生產線的工作，如圖二所示。此工作以一個人來做時要十九分鐘(a)，如果分為甲乙丙三人來做，雖然增加了些工作分派及管理上的工作，使得總共的時間為廿一分鐘，但其流量（throughput，即在重複性工作之供應不斷的情形下，單位時間的生產量）反而增加，亦即每九分鐘可做完一件事(b)。若是將(b)中乙的工作再分為二，如(c)中所示，則更可將流量提高至每六分鐘可完成一件事。在圖三中，若甲乙丙均為電路，則在甲乙丙各級間必須加暫存器，以安置算好的或等待下一級運算的資料，這種暫存器名為管道式暫存器（pipe-lined registers）是設計高速運算電路常用的法寶之一。而cache及記憶體的層次結構的構想，也和此管道式的想法相關聯。又如，在計算機中指令執行之同時，預先將下一個指令先行解碼的做法（instruction look-ahead），亦一典型之管道式平行結構。

雖然平行處理不是新觀念，而且，已往在設計計算機硬體時也常用，可是，目前我們對平行處理的了解還是極膚淺的，而且多半將它應用在一些特殊結構上。除了上述的例子以外，數位系統（計算機）用於軍事系統，生產控制以及各種儀表的設計裡，均可找出無數個特殊平行結構的例子。換言之，如果針對某一特殊問題，已經有一個解決問題的流程（它通常包含一些同時處理的步驟），而據此流程所做的硬體設計都是些特殊的平行結構（special purpose parallel structure）。而這種做法早已行之有年。

高度平行的結構

所以，目前平行處理研究的主力，並不放在這些特殊平行結構上，而是著重在對一般性質（general purpose）平行結構的了解，和對平行運算本質的了解。這些通用的平行結構又稱為高度的平行結構，在圖三裡有二個代表性的架構。由圖三中可知，考慮平行處理的結構時，主要的系統元素是處理器和記憶體。而設計平行結構的目的是：集合一群循序處理機並使之能在相互合作和溝通的運作下，很快速地解決複雜的大問題（參考資料3）。

根據上面的說法，研究平行處理系統涉及三項特徵：

一、共通性（generality）：也就是對系統整體能力，如：處理流量之大小，或反應時間之快慢等，應具有可測的性質。

二、功能度（scalability）：是指增加處理機數目時，對整體系統功能增減的單位幅度（以每處理機為準）應為可測。

三、單機形象（single system image）：無論此平行處理系統用了多少處理機，對使用者而言，應如同他在使用一個極高速的計算機一般，而無視於這些處理機的存在。

而這三項特徵也正是目前作平行處理研究的重要前提假設。

定義和基本問題

人多雖好做事，可是也有「三個和尚沒水吃」的可能。平行處理的概念雖是老生常談，然而在執行時卻有太多的變因而使得問題變成複雜難解。為了了解這些複雜的變因，讓我們用前述平行結構的定義，來做個條列式的說明。

一、「集合一群循序處理機……」，相關的變因有：

•多少個？有人做以十計的，有以千計的，甚至有用超大型積體電路以百萬個處理器計的。

•多大一個？大多以16位元或32位元的微處理機為參考。

•什麼樣的處理機？它的指令集是些什麼？

　•記憶單元有多大？將依處理機功能及資料之區域性（data locality）而定。

•這些處理機的收發功能如何？將依處理機之功能以及處理機之間通訊的負荷而定。

二、「……並使之能在相互合作和溝通的運作下……」，相關的變因有：

•如何將之連接？有用縱橫式交換機（cross-bar）、樹（tree）、矩陣（arrays）、超空間方塊（hyper-cube）或者洗牌（shuffles）網路等連接者。

•如何溝通？那些訊息需要溝通？

•如何同步（解決工作順序與工作時差之間的問題）？

•工作如何劃分（使之合作）？單位工作的大小（grain size）為何？

•操作系統如何設計或溝通？

•用單指令束或複指令束結構？（關於此項，下面將作詳細解釋。）

三、「……很快速地解決複雜的大問題」，相關的變因有：

•那些是「複雜的大問題」？那些應用有這類問題？

•計算模式為何？

•由程式設計的觀點來看：

•問題如何分解？

•如何訂定平行運算的規格？

•上述的事情由誰來做？人或是系統？

•有任何工具可用嗎？譬如描述平行處理演算方法的語言？或是有平行處理特性的其他工具？

•上述之語言有編譯程式嗎？

•平行演算的法則和演算方法是什麼？

•有多快？

•這樣的系統，其可靠性、可用性及維護性如何？以上這些問題，沒有一個好回答。在第一類中的問題，主要是涉及硬體結構。在第三類中的問題，則主要涉及平行演算方法、軟體和理論模式。第二類中的問題涉及通訊，並與軟硬體均有牽連。目前，有關硬體架構之問題並不大，而平行處理的理論模式和演算方法是整個研究亟待解決的癥結所在。

系統內的連接方式與計算模式

弗林教授（M.J.Flynn）是最早嘗試為各種處理的連接方法做分類的人。在1972年，他依據資料流束（data stream）和指令流束（instruction stream）的數目來分類，此分類法至今仍常採用，詳如表一（見下頁）。

在表一中，最簡單的結構是SISD（single instruction stream and single data stream以下簡寫可類推），亦即單指令束和單資料束的狀況。這就是傳統的馮紐曼模式。管道模式是MISD的典型，它只有一資料束，可是每一個處理機對此資料束做的指令均不同，所以是複指令束。管道模式曾用於Cray-1及Cyber 205等超級計算機中來做向量的運算。SIMD的單指令束複資料束的結構則出現於早期號稱第一台超級計算機的Illiac-Ⅳ中，它一共用了64個處理機來分享一個指令，也就是同時對64組數據只能做同一種運算。這種結構適合作矩陣或向量的計算。MIMD是較通用型的結構，如圖三的例子。

弗林的分類法提供了很好的參考點，它使我們有系統的了解各種不同的內部結構。然而，它欠缺具體的計算模式，對於系統特性的分析方面功用並不大，因此，近年來又有許多模式的出現，茲將重要者介紹如下：

一、洗牌模式（shuffer-exchange model）：此模式的處理機數目與記憶單元數目相等，而彼此間之連接是以排列的匹配函數（permutation function）來連接的。這個模式的優點是簡潔，容易在此模式下導出平行運算的演算方法，有許多很好的排序（sort）及搜尋（search）的平行演算法均在此模式下導出。它的毛病是以積體電路的技術來做時相當複雜，不易付諸實用。然而在理論研究上，有其肯定的價值。

二、超空間方塊模式（hyper-cube model）：這是加州理工學院在解某物理問題時所發明的模式。之後，此專利為Intel公司收購，並於去年推出上市，是唯一的平行處理元件商品。它的機種叫iPSC，分為32、64以及128個處理機的三種型號。它的處理機是80286／80287每個附帶有512KBytes的記憶單元。其主控部分是Intel 310微計算機，用Zenix操作系統，並提供C及Lisp語言編譯器。這種系統仍較適合SIMD方式的運作（雖然不一定要如此），它可將N次的運算減低到〔〕*次（N為處理器的數目）。註：〔〕表示大於之最小正整數。

三、樹狀機模式（tree machine）：在資料結構中，樹狀結構是最常用到的一種。因此，為配合資料結構乃有樹狀機的產生。這種機種自然是適合樹狀資料的運算，在做數學運算（SIMD方式），及在樹狀結構的資料中搜查時，它均可將N次的運算降為〔〕次。

四、數據流模式（data-flow model）：這是歐洲、日本和美國麻省理工學院熱衷研究的模式，它的特徵是具有結構的可塑性（re-configurable）。換言之，其內部的接線是可依程式的不同而改變的，這一點和上述的三種模式大不相同。它和傳統的模式也大異其趣：它沒有傳統的控制單元和程式記數器（program counter）作程式執行控制，取而代之的是對數據的可用狀態作偵測，一旦數據準備妥當時，便能立刻做相關的運算。在理論上，此模式有更健全的計算模式，因此在計算理論的角度上看來，它的發展前途均較前三者為佳。然而，其理論模式甚為複雜，描述不易，因而使其使用之語言呈現出圖形的結構（詳情參閱圖四），不易使用。

平行的演算方法

演算方法是真正平行處理研究的成敗關鍵。如果沒有有效的平行演算方法，有再多的處理機也無用武之地。反之，有了好的平行演算方法，用硬體做也好，用軟體模擬也好，總可以充分利用既有的計算設備把問題解出來。目前，研究平行演算法的人很多，題目也很多，因為以前發展的所有單序演算法，全部可以考慮重新來過改為平行演算法。

然而，根據上一節的討論，演算法亦將受限於其硬體連接的模式。譬如說，在樹狀機模式下的演算法一定與洗牌模式下的演算法迥異。因此，它幾乎又多了一維（dimension）的變化。

綜合和歸納各種演算法，將有希望導出新的計算模式。雖然目前尚無此方面的具體結果，然而，這將是未來研究的一線希望。

根據目前研究的成績，我們已經發現有些問題的演算法適合用平行的方式來解；有些則不適合，只宜用單序演算法來做。然而如何判斷何類問題適合用何種解法仍是一未解的難題。

此外，能描述平行處理的語言將是推展平行處理應用的成敗關鍵，可惜目前此方面的研究仍待努力。

有關平行演算法部分，就討論至此，有興趣一探究竟的讀者可參閱本期介紹平行演算法的「平行處理的計算方法」一文。

平行處理之前途看好

平行處理的研究，固然是為了對計算速率的追求，然而，其盛行的緣起亦有環境的客觀因素存在：那就是由於超大型積體電路技術的發展，充分提供了「硬體不值錢」的環境，使得一次的設計投資可以長期的享用，而硬體的直接生產成本幾乎變得和電路的複雜度無關。這種環境不只使得平行處理的研究如火如荼地展開，也改變了數位系統設計的整個理念和價值觀；設計人員不再追求省一些電路以降低成本，而反過來研究如何多用一些電路來加強系統的可靠性、可測性及對錯誤的容忍度等等。這些都是硬體昂貴時不願去碰的問題。因此，大型積體電路不僅是發展平行處理的必要元件，更是發展更複雜的大型系統必要的技術。

平行處理的研究雖然目前極為熱門，然而，其研究的成果究竟將如何仍是個未知數。主要的原因是因為人不習慣於平行處理的方式，能有老頑童周伯通「分心神功」的人，少之又少。所以發展這種不甚「自然」的平行（處理）演算法，似乎仍有一段長長的路要走。同樣的理由，要訓練使用計算機的人用平行處理的語言，並且時時要記得將演算法配合特有的平行硬體結構來寫程式，是件極苦的差事，也極不容易做好。是不是能發展出有系統的科學方法，將單序演算法自動轉換為平行演算法呢？目前此方面的研究成果仍然有限得很，只能做些最簡單的轉換而已（如數據流模式即已有些此功能）。

由上觀之，我們對平行運算的本質了解得還不夠。如果在計算理論上對平行處理的了解沒有突破性的進展，那麼對平行處理的知識和應用將滯留在某一程度上也是顯而易見的。

平行的演算法在本質上是屬於各個擊破法（divide and conquer）解題策略中的一種。由於問題被擊破的程度不同，在其平行結構上亦將產生極大的差異。如何在此間求得一最佳大小的擊破（問題分解），目前仍是以系統的計算成本作為選擇的主要依據。這方面的研究直接影響到平行處理的結構，也是值得注意的發展領域。

總而言之，平行處理的研究是突破現有計算速率的希望所在，雖然目前看來仍然有許多問題，可是前途依然看好！

參考資料

1. G. Almasi ＆ S Harvey, "An Introduction to parallel processing", J. of Electronic Defense, pp 31∼42, may 1986.

2. E T. Fathi ＆ M Krieger, "Multiple Processor Systems：What, Why, and When", IEEE Computer, pp23-32,March, 1983.

3. G.S. Almasi,"Overview of parallel processing", Parallel Computing, 2：191∼203, Elsevier Science Publisher, B.V. North Holland, 1985.

※作者保留著作權

　謝清俊任職於中研院資訊科學研究所，本刊編輯顧問

回到最上面

科學月刊全文資料庫

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

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