論Cannon算法在并行計(jì)算機(jī)上的運(yùn)用研究

摘要： Cannon算法是一種較為便捷的并行算法，多用于計(jì)算機(jī)上的運(yùn)用，采用這種算法能夠大大提高計(jì)算機(jī)的運(yùn)行效率，使得用戶能夠更好的使用計(jì)算機(jī)資源。本文主要從Cannon算法的基本原理，結(jié)合實(shí)際計(jì)算機(jī)運(yùn)用，探討Cannon算法在計(jì)算機(jī)環(huán)境中運(yùn)行的最佳效果。

關(guān)鍵詞： Cannon算法；計(jì)算機(jī)；并行算法

中圖分類號(hào)：TP338.6 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9599 （2012） 20-0000-02

計(jì)算機(jī)與數(shù)學(xué)是有著深厚的歷史淵源，許多計(jì)算機(jī)問題從本質(zhì)上來看都與數(shù)學(xué)運(yùn)算密不可分。隨著現(xiàn)代信息技術(shù)的發(fā)展，人們對(duì)并行運(yùn)算提出了更高的需求，多核化的趨勢(shì)也逐漸改變著計(jì)算機(jī)的面貌。

1 Cannon算法的矩陣劃分

矩陣相乘的并行算法有三種，分別是矩陣按行劃分、按照列劃分以及按照棋盤式的方式來劃分。相比較按行劃分和按列劃分，棋盤式的劃分方式更加全面，并且更加具有可開發(fā)性，能夠從并行度上予以更深入的研究和開發(fā)。針對(duì)n*n的方針，在棋盤劃分中可以最多采用 個(gè)處理器進(jìn)行并行計(jì)算相比較之下，按行或者按列來來分解最多只可以使用n個(gè)。我們將這種能夠開發(fā)出更高的并行度的算法稱作為Cannon算法。所謂棋盤劃分就是將矩陣分成若干個(gè)子矩陣，將這些被劃分的子矩陣分派給一個(gè)處理器，同時(shí)任一處理器均不包含正行或者整列。

2 并行計(jì)算的基本原理

并行算法是指一種采用多臺(tái)處理器聯(lián)合求解問題的方法和步驟，在并行算法中，原有的問題被分解成為了若干個(gè)子問題，從而在多臺(tái)計(jì)算機(jī)上同時(shí)對(duì)其進(jìn)行求解，最終解決原問題。將并行算法應(yīng)用到實(shí)際中去，需要一個(gè)相對(duì)完善的架構(gòu)-算法-編程的方法論。采用并行計(jì)算能偶將原有的大型且復(fù)雜的問題小化，分成若干個(gè)子問題，從而能夠提高大型復(fù)雜運(yùn)算的解決效率。此外，利用并行算法還能夠大大提高計(jì)算機(jī)本身的資源利用率，降低單個(gè)存儲(chǔ)器的限制。傳統(tǒng)的串行計(jì)算的方式是在單個(gè)計(jì)算機(jī)上完成軟件操作，受到計(jì)算機(jī)資源以及存儲(chǔ)器的限制較大，因此基于串行計(jì)算發(fā)展而來的并行算法大大提高了計(jì)算效率，能夠快速解決大型并且異常復(fù)雜的計(jì)算問題。

綜合來看，并行計(jì)算具有其自身的特征，包括了以下幾個(gè)方面：

一是將整體的復(fù)雜問題細(xì)化，將工作內(nèi)容進(jìn)行了分割和劃分成各個(gè)離散的子問題，利于各個(gè)子問題并行解決。二是在并行計(jì)算中能夠?qū)Χ鄠€(gè)程序進(jìn)行同步和及時(shí)的指令執(zhí)行；三是基于多個(gè)計(jì)算機(jī)資源下的并行算法能夠大大提高問題的解決速率，減少問題解決的耗時(shí)，相對(duì)于單個(gè)計(jì)算資源有很大的提升。

這里的并行解決是相對(duì)于串行計(jì)算方法來說的，其并行主要分為時(shí)間上和空間上的并行計(jì)算，其中，時(shí)間上的并行計(jì)算主要是指流水線的計(jì)算方式，通過各個(gè)環(huán)節(jié)的綜合運(yùn)行提高運(yùn)行效率?？臻g商的并行計(jì)算則是指能夠在多個(gè)處理器上并行執(zhí)行計(jì)算，按照并行計(jì)算的原理，可以對(duì)其進(jìn)行分類，一般來說我們將其分為單指令流多數(shù)據(jù)流和多指令流多數(shù)據(jù)流。并行計(jì)算的存儲(chǔ)結(jié)構(gòu)主要包括了共享內(nèi)存、分布式內(nèi)存、混合型分布式共享內(nèi)存等。

3 Cannon算法在計(jì)算機(jī)上的運(yùn)用

3.1 Cannon算法在并行機(jī)器上減少通信時(shí)延的應(yīng)用

眾所周知，當(dāng)通信數(shù)據(jù)量很大時(shí)便會(huì)造成較大的通信開銷，或者當(dāng)通信過于頻繁時(shí)，即是數(shù)據(jù)量很小，也會(huì)造成通信開銷，如何通過計(jì)算來減少通信開銷，做好數(shù)據(jù)交換和分配具有重要意義。當(dāng)數(shù)據(jù)在各個(gè)服務(wù)器端進(jìn)行交換時(shí)，采用重疊技術(shù)，能夠?qū)崿F(xiàn)時(shí)延隱藏。Cannon算法運(yùn)用于減少通信時(shí)延主要是做好任務(wù)的分配以及數(shù)據(jù)包的處理，因此在進(jìn)行任務(wù)分配時(shí)，主要是采用輪流發(fā)放數(shù)據(jù)包的形式，當(dāng)?shù)谝粋€(gè)數(shù)據(jù)包發(fā)完之后依次發(fā)送第二個(gè)數(shù)據(jù)包，采用這樣緊密的連續(xù)發(fā)送方式提高數(shù)據(jù)包的任務(wù)分配，當(dāng)采用這種方式輪流發(fā)放數(shù)據(jù)包時(shí)，服務(wù)器接到數(shù)據(jù)包之后就進(jìn)行計(jì)算，采用這樣的數(shù)據(jù)包接收和計(jì)算方式能夠大大減少服務(wù)器接收數(shù)據(jù)包的耗時(shí)，提高服務(wù)器的計(jì)算工作效率 ，最終實(shí)現(xiàn)了在并行機(jī)器上減少通信時(shí)延的目的。

3.2 Cannon算法運(yùn)用于并行計(jì)算機(jī)的優(yōu)勢(shì)

Cannon算法相對(duì)于單行或者單列的算法具有明顯的組合優(yōu)勢(shì)以及可開發(fā)優(yōu)勢(shì)，將其運(yùn)用到并行計(jì)算機(jī)中能夠大大提高并行計(jì)算機(jī)的運(yùn)行效率，具體來說，Cannon算法運(yùn)用于并行計(jì)算機(jī)的優(yōu)勢(shì)體現(xiàn)在以下幾個(gè)方面：首先它改變了陣列的各行和各列實(shí)施多到多播送的傳統(tǒng)方式，實(shí)現(xiàn)了在各行和各列之間的循環(huán)移位，這對(duì)于并行計(jì)算機(jī)的總存儲(chǔ)器來說大大降低了存儲(chǔ)負(fù)擔(dān)，從而減少了對(duì)處理器的存儲(chǔ)的要求，客觀上有利于釋放存儲(chǔ)空間，提高處理器的運(yùn)行效率。其次，Cannon算法運(yùn)用到并行計(jì)算機(jī)中能夠大大提高并行計(jì)算的速率，在進(jìn)行任務(wù)分配時(shí)能夠縮短處理器的等待時(shí)間，緩解當(dāng)前并行計(jì)算機(jī)中通信相對(duì)滯后的局面，因此總的來說，Cannon算法對(duì)于計(jì)算機(jī)的數(shù)值計(jì)算具有重要意義，大大提高了計(jì)算機(jī)的運(yùn)行和計(jì)算速率。此外，Cannon算法運(yùn)用到并行計(jì)算機(jī)中去能夠提高對(duì)于復(fù)雜問題的解決能力，將各個(gè)大型的復(fù)雜問題進(jìn)行分離，最終逐個(gè)快速解決，一定程度上采用Cannon算法能夠提高運(yùn)算的準(zhǔn)確性和運(yùn)算的速度，提高并行計(jì)算機(jī)處理問題的效率。

3.3 發(fā)展趨勢(shì)及應(yīng)用前景

首先從并行程序設(shè)計(jì)的現(xiàn)狀來看，雖然整體上基于并行計(jì)算的方法的程序設(shè)計(jì)方法正在逐漸完善，但是在實(shí)際應(yīng)用中采用這種方法的系統(tǒng)相對(duì)較少，從而限制了這種方法的推廣。就目前的應(yīng)用情況來看，并行軟件的開發(fā)和推廣是落后于并行硬件的，此外相對(duì)于傳統(tǒng)的串行系統(tǒng)的應(yīng)用軟件的來說，當(dāng)前并行系統(tǒng)應(yīng)用軟件還較少并且在實(shí)際應(yīng)用中還存在諸多不足。綜觀產(chǎn)生當(dāng)前并行軟件發(fā)展難，Cannon算法推廣使用難的原因主要體現(xiàn)在以下幾個(gè)方面：一是Cannon算法的程序設(shè)計(jì)相對(duì)于串行程序設(shè)計(jì)更為復(fù)雜，其中包含了許多富有挑戰(zhàn)性的問題，并且很大程度上對(duì)處理器的依賴較大；二是串行程序設(shè)計(jì)中常用的模型主要是馮諾依曼模型，并且該模型經(jīng)過長(zhǎng)期的使用已經(jīng)趨于成熟，相比之下，基于Cannon算法的并行程序設(shè)計(jì)其模型更為復(fù)雜，雖然有很多，但到目前為止還沒有一個(gè)模型是得到普遍認(rèn)可和使用的；三是相對(duì)來說Cannon算法的并行程序設(shè)計(jì)對(duì)于客觀的硬件環(huán)境要求比串行程序設(shè)計(jì)要求高，需要的處理器也更多，更先進(jìn)，因此在投入上明顯多于串行設(shè)計(jì)；四是在過去的軟件設(shè)計(jì)和開發(fā)中，串行設(shè)計(jì)應(yīng)用廣泛，并且為大多數(shù)人接受，且滿足了用戶的基本需求，基于長(zhǎng)期的工作經(jīng)驗(yàn)設(shè)計(jì)師更傾向于選擇串聯(lián)軟件設(shè)計(jì)，基于Cannon算法的并行軟件設(shè)計(jì)開發(fā)因?yàn)槠溟_發(fā)范例相對(duì)較少，還未得到社會(huì)的普遍認(rèn)可和廣泛接受，因此其推廣和應(yīng)用上相對(duì)緩慢。

綜合上述目前基于Cannon算法在并行設(shè)計(jì)的應(yīng)用現(xiàn)狀來看，開發(fā)和設(shè)計(jì)的深度和廣度是明顯不夠的，隨著時(shí)代的發(fā)展以及現(xiàn)代信息技術(shù)的日新月異，就需要我們緊隨時(shí)代發(fā)展的步伐，把握研究的方向，將基于Cannon算法的并行算法的研究不斷深化和拓寬，為其在并行計(jì)算機(jī)以及相關(guān)軟件程序的開發(fā)設(shè)計(jì)中得到更廣泛的應(yīng)用努力。

4 結(jié)束語

并行計(jì)算機(jī)系統(tǒng)下各個(gè)計(jì)算機(jī)之間的銜接以及數(shù)據(jù)包的處理是Cannon算法處理的關(guān)鍵，通過該算法大大提高了并行計(jì)算機(jī)的工作效率。在機(jī)群計(jì)算機(jī)系統(tǒng)的環(huán)境下，要提高并行算法的效果可以通過研究深入探討其他算法的并行效果。總的來說，采用Cannon算法能夠?qū)崿F(xiàn)欺騙盤劃分，實(shí)現(xiàn)各個(gè)矩陣之間的循環(huán)移動(dòng)，減少并行及其的通信時(shí)延，從而提高并行機(jī)器接收數(shù)據(jù)包的等待時(shí)間，隱藏了客戶機(jī)發(fā)送數(shù)據(jù)的通信時(shí)延。相信隨著Cannon算法的深入研究以及相關(guān)模型和算法的完善，Cannon算法在機(jī)群系統(tǒng)中將會(huì)有更加廣泛的應(yīng)用前景。

參考文獻(xiàn)：

[1]齊景嘉，夏麗華.并行矩陣乘法算法的研究[J].黑龍江大學(xué)自然科學(xué)學(xué)報(bào)，2006，23（3）：78-81.

[2]陳傳偉.并行計(jì)算機(jī)系統(tǒng)下的矩陣乘法[J].武漢科技學(xué)院學(xué)報(bào)，2008（11）：106-108.

[3]嚴(yán)蔚敏，陳文博.數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程[M].北京：清華大學(xué)出版社，2001.

[4]陳晶，黃曙光.分布式并行矩陣乘算法分析[J].測(cè)控技術(shù)，2005（5）：42-45.

[5]唐俊奇.多處理機(jī)中矩陣乘法的算法研究[J].中國(guó)西部科技，2007（2）：65-67.

[作者簡(jiǎn)介]蔣瀚洋（1977，8-），男，漢族，湖南衡南人，衡陽師范學(xué)院計(jì)算機(jī)科學(xué)系講師，研究方向：并行計(jì)算、GPU計(jì)算。