發(fā)布時(shí)間：2020-06-28 17:29

【摘要】：并行處理作為一個(gè)重要的研究領(lǐng)域，受到研究者越來越多的重視，而提高通信效率是一個(gè)重要的研究課題。本文針對(duì)程序中的通信效率問題，分析了產(chǎn)生通信擁擠的三個(gè)因素，即BSP程序引起的通信擁擠、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)引起的通信擁擠和網(wǎng)絡(luò)嵌入算法不當(dāng)引起的通信擁擠。在此基礎(chǔ)上，選擇這三個(gè)問題作為本文的主攻方向。經(jīng)過三年的研究，在閱讀大量文獻(xiàn)的基礎(chǔ)上，取得了理想的研究成果。針對(duì)并行程序的效率，本文提出了CSA-BSP模型，該模型能夠引導(dǎo)程序設(shè)計(jì)者寫出高效率的并行程序；針對(duì)互連網(wǎng)絡(luò)，本文提出了RP(k)網(wǎng)絡(luò)，該網(wǎng)絡(luò)拓?fù)渚哂性S多優(yōu)良的性質(zhì)，因而能夠更好地提高通信效率；針對(duì)網(wǎng)絡(luò)嵌入問題，本文設(shè)計(jì)了將環(huán)、Mesh和Hypercube通信模式嵌入RP(k)互連網(wǎng)絡(luò)的高效算法，使得在這些網(wǎng)絡(luò)上已開發(fā)的應(yīng)用能夠高效地移植到RP(K)網(wǎng)絡(luò)上。 經(jīng)過三年深入的研究，達(dá)到了預(yù)期的目的，取得了理想的結(jié)果，本文的主要?jiǎng)?chuàng)新點(diǎn)如下： ① 提出了一類基于Petersen圖的互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)RP(k)。該網(wǎng)絡(luò)的連接度為5，直徑為[k／2]+2；該網(wǎng)絡(luò)具有短的網(wǎng)絡(luò)直徑、簡單的拓?fù)浣Y(jié)構(gòu)、方便的路由策略；該網(wǎng)絡(luò)硬件復(fù)雜度低、實(shí)現(xiàn)簡單；在環(huán)、Mesh和Hypercube上設(shè)計(jì)的算法能夠高效地嵌入RP(k)。同時(shí)，針對(duì)不同的互連網(wǎng)絡(luò)規(guī)模，本文對(duì)該網(wǎng)絡(luò)進(jìn)行了擴(kuò)展，提出了RP(P，k_1，k_2)網(wǎng)絡(luò)拓?fù)�，并討論了其性質(zhì)。 ② 設(shè)計(jì)了RP(k)互連網(wǎng)絡(luò)上的路由算法，主要設(shè)計(jì)了點(diǎn)點(diǎn)路由、置換路由、廣播路由和All-to-all路由算法。這些算法的通信次數(shù)分別為[k／2]+2、k+5、[k／2]+2、k+5。這樣，RP(k)網(wǎng)絡(luò)和其上的路由算法為并行體系結(jié)構(gòu)提供了一個(gè)實(shí)用的工具集。同時(shí)，在RP(P，k_1，k_2)網(wǎng)絡(luò)上，本文也設(shè)計(jì)了以上四個(gè)通信模式的路由算法，它們的通信次數(shù)分別為[k_2／2]+[k_1／2]+2、4+m{k_2，k_1}+(k_2-1)~*(k_1-1)、[k_2／2]+[k_1／2]+2和10~*k_1*k_2-4。 ③ 提出了將Ring和Mesh嵌入RP(k)網(wǎng)絡(luò)的算法，證明了RP(k)網(wǎng)絡(luò)是一個(gè)Hamiltonian圖�？紤]到網(wǎng)絡(luò)的容錯(cuò)情況，當(dāng)RP(k)網(wǎng)絡(luò)中每個(gè)片有一個(gè)節(jié)點(diǎn)出現(xiàn)故障時(shí)，去掉故障節(jié)點(diǎn)和相應(yīng)的邊，得到互連網(wǎng)絡(luò)RP-1(k)，我們證明了該網(wǎng)絡(luò)也是Hamiltonian圖。因此，可以分別將10*k和9*k個(gè)節(jié)點(diǎn)的環(huán)嵌入到RP(k)和RP-1(k)網(wǎng)絡(luò)中去。同時(shí)，我們也設(shè)計(jì)了將2-D mesh嵌入RP(k)網(wǎng)絡(luò)的方法，取得了良好的嵌入性能。 ④ 基于光RP(k)網(wǎng)絡(luò)，本文設(shè)計(jì)了一個(gè)實(shí)現(xiàn)n維Hypercube通信模式的算法，該算法最多需要max{2，[(5／3)~*2~(n-5)]}條波長。同時(shí)，設(shè)計(jì)了一個(gè)將n維Hypercube嵌入環(huán)網(wǎng)絡(luò)
【學(xué)位授予單位】：中國科學(xué)院研究生院（計(jì)算技術(shù)研究所）
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2001
【分類號(hào)】：TP338.6

【引證文獻(xiàn)】

相關(guān)期刊論文 前1條

1 李靜梅;張岐;王軍鋒;;多核處理器并行計(jì)算模型研究[J];智能計(jì)算機(jī)與應(yīng)用;2011年05期

相關(guān)博士學(xué)位論文 前1條

1 成斌;基于TCPN模型的并行系統(tǒng)性能分析方法研究[D];上海大學(xué);2011年

相關(guān)碩士學(xué)位論文 前1條

1 杜艷;幾類網(wǎng)絡(luò)模型及路由算法研究[D];山東師范大學(xué);2011年

本文編號(hào)：2733268