本文選題：互連網(wǎng)絡(luò) + 局部扭曲立方體　； 參考：《重慶大學(xué)》2012年碩士論文

【摘要】：并行計(jì)算機(jī)的基礎(chǔ)互連網(wǎng)絡(luò)為處理器（結(jié)點(diǎn)）之間進(jìn)行數(shù)據(jù)通信提供了物理基礎(chǔ)，其拓?fù)浣Y(jié)構(gòu)決定了結(jié)點(diǎn)間通信效率，是影響并行計(jì)算機(jī)性能的主要因素之一，因而成為并行計(jì)算領(lǐng)域的研究熱點(diǎn)。當(dāng)在互連網(wǎng)絡(luò)上執(zhí)行并行算法時(shí)，常常需要在結(jié)點(diǎn)之間進(jìn)行數(shù)據(jù)通信，其通信開(kāi)銷是算法執(zhí)行時(shí)間的重要組成部分�；诨ミB網(wǎng)絡(luò)的特性來(lái)研究如何高效地完成數(shù)據(jù)通信，這是一項(xiàng)很有意義的研究課題。 類超立方體是一類重要的互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，目前，關(guān)于變形超立方體通信算法方面的研究成果還很少，，相應(yīng)的通信問(wèn)題沒(méi)有得到很好的解決，因而難以開(kāi)發(fā)關(guān)于變形立方體的并行算法，同時(shí)也使得變形立方體到目前為止還缺乏實(shí)用的價(jià)值。本學(xué)位論文研究變形立方體上的通信問(wèn)題，取得的主要研究成果如下： 首先，對(duì)一種重要的類超立方體---局部扭曲立方體，研究了其單點(diǎn)廣播問(wèn)題。單點(diǎn)廣播是一個(gè)基本的通信問(wèn)題，需要把一組消息從一個(gè)給定的結(jié)點(diǎn)發(fā)送到網(wǎng)絡(luò)中其他所有的結(jié)點(diǎn)。針對(duì)這一問(wèn)題，本文提出了一個(gè)能夠在O (N log N)時(shí)間內(nèi)完成n維局部扭曲立方體上單點(diǎn)廣播任務(wù)的算法，其中N=2n為結(jié)點(diǎn)數(shù)；證明了該算法在同類算法中通信時(shí)延最小。就我們所知，這還是國(guó)際上首次研究局部扭曲立方體上的單點(diǎn)廣播問(wèn)題。 其次，對(duì)另一種重要的類超立方體---交叉立方體，研究了其獨(dú)立生成樹問(wèn)題。容錯(cuò)通信和安全消息分發(fā)是互連網(wǎng)絡(luò)領(lǐng)域的一項(xiàng)重要研究課題。普遍認(rèn)為：設(shè)計(jì)多個(gè)獨(dú)立生成樹來(lái)作為廣播方案或分發(fā)協(xié)議可以得到良好的容錯(cuò)性和安全性。本文提出了一個(gè)能夠構(gòu)造出n維交叉立方體中n棵獨(dú)立生成樹算法，其時(shí)間開(kāi)銷為O (N log N)，其中N=2~n為結(jié)點(diǎn)數(shù)。該算法可以并行化，其時(shí)間開(kāi)銷降為O (log N)。該算法使獨(dú)立生成樹的數(shù)目達(dá)到了最大，從這個(gè)意義上講，該算法是最優(yōu)的。
[Abstract]:The basic interconnection network of parallel computers provides a physical basis for data communication between processors (nodes). Its topology determines the communication efficiency between nodes and is one of the main factors that affect the performance of parallel computers.Therefore, it has become a research hotspot in the field of parallel computing.When parallel algorithms are executed on interconnection networks, data communication between nodes is often required, and the communication overhead is an important part of the algorithm execution time.It is a significant research topic to study how to accomplish data communication efficiently based on the characteristics of interconnection network.Hypercube is an important topology of interconnection network. At present, there are few researches on the algorithm of deformed hypercube communication, and the corresponding communication problems have not been solved well.Therefore, it is difficult to develop parallel algorithms for deformable cubes, and at the same time, deformable cubes still lack practical value.In this dissertation, the communication problem on the deformed cube is studied, and the main research results are as follows:Firstly, the problem of single point broadcasting for an important hypercube---locally twisted cube is studied.Single point broadcasting is a basic communication problem. It is necessary to send a set of messages from a given node to all other nodes in the network.In order to solve this problem, this paper proposes an algorithm that can complete a single point broadcast task on an n-dimensional locally twisted cube in O ~ n log N time, where N ~ (2) n is the number of nodes, and it is proved that the algorithm has the minimum communication delay among the similar algorithms.As far as we know, this is the first time in the world to study the problem of single point broadcasting on partially distorted cubes.Secondly, the problem of independent spanning tree is studied for another important hypercube-cross cube.Fault-tolerant communication and secure message distribution is an important research topic in the field of interconnection networks.It is generally believed that designing multiple independent spanning trees as broadcast schemes or distribution protocols can achieve good fault tolerance and security.In this paper, we propose an algorithm that can construct n independent spanning trees in n-dimensional cross cubes, whose time cost is O n log n, where N ~ (2 +) n is the number of nodes.The algorithm can be parallelized, and its time cost is reduced to O log N.The algorithm maximizes the number of independent spanning trees. In this sense, the algorithm is optimal.
【學(xué)位授予單位】：重慶大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2012
【分類號(hào)】：TP338.6

【共引文獻(xiàn)】

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

1 O賜蜢

本文編號(hào)：1770141