本文關(guān)鍵詞：多核處理器的任務(wù)映射與通信路由算法研究　出處：《復(fù)旦大學(xué)》2012年碩士論文　論文類型：學(xué)位論文

  更多相關(guān)文章： 片上網(wǎng)路 任務(wù)映射 任務(wù)綁定 路由算法 銀行家算法 迷宮算法

【摘要】：隨著半導(dǎo)體技術(shù)的發(fā)展,越來(lái)越多的IP核被集成到一個(gè)單芯片上,然而各個(gè)IP核之間的互連成為了制約芯片性能提高的主要瓶頸。近幾年提出的片上網(wǎng)絡(luò)能夠很好地實(shí)現(xiàn)各個(gè)IP核之間的并行通信,具有高性能和低功耗兩大優(yōu)勢(shì),并且由于其具有很好的可擴(kuò)展性和可重用性,已經(jīng)成為近幾年業(yè)界和學(xué)術(shù)界研究的重點(diǎn)。然而,在硬件發(fā)展的同時(shí),如何將應(yīng)用程序映射到片上網(wǎng)絡(luò)的硬件并使其能夠高效地運(yùn)行又具有低功耗的特點(diǎn),成為了制約片上網(wǎng)絡(luò)性能發(fā)揮的難點(diǎn)。 本文致力于片上網(wǎng)絡(luò)軟件編譯器的設(shè)計(jì),提出了本項(xiàng)目組編譯器的設(shè)計(jì)思路,實(shí)現(xiàn)應(yīng)用程序在片上網(wǎng)絡(luò)的高效運(yùn)行。重點(diǎn)介紹了編譯器設(shè)計(jì)中的任務(wù)映射和路由算法兩部分。 任務(wù)映射中,在深入研究分支限界算法的基礎(chǔ)上進(jìn)行優(yōu)化,提出了任務(wù)綁定的思想。任務(wù)映射的目標(biāo)在于減少整個(gè)NoC網(wǎng)絡(luò)節(jié)點(diǎn)之間的通信功耗。為了降低搜索空間,本文將通信量大的任務(wù)通信對(duì)綁定,一起映射到相鄰的NoC網(wǎng)絡(luò)節(jié)點(diǎn)上,顯著地提高了任務(wù)映射的效率。實(shí)驗(yàn)表明,優(yōu)化的算法可以在更短的時(shí)間為多核系統(tǒng)找到性能相當(dāng)?shù)挠成浞桨�。例�?當(dāng)映射25個(gè)任務(wù)到5×5的NoC系統(tǒng)時(shí),只用傳統(tǒng)算法的26.3%的時(shí)間就可以找到性能相同的映射方案。 路由算法中,在分析傳統(tǒng)路由算法的基礎(chǔ)上,提出了通信通道時(shí)分復(fù)用的思想,減小了對(duì)NoC系統(tǒng)的帶寬的需求。在對(duì)通信請(qǐng)求進(jìn)行硬件資源分配和回收時(shí),引入了被廣泛用于操作系統(tǒng)的銀行家的算法。在對(duì)通信請(qǐng)求尋找最短路徑時(shí),引入了迷宮算法。同時(shí),當(dāng)存在多條通信路徑時(shí),用了盡量靠近NoC網(wǎng)絡(luò)邊緣、中心和隨機(jī)三種規(guī)則進(jìn)行選擇。實(shí)驗(yàn)結(jié)果表明,考慮了通信通道時(shí)分復(fù)用后的路由算法相對(duì)于傳統(tǒng)的路由算法對(duì)NoC系統(tǒng)的帶寬需求大大降低。同時(shí),當(dāng)存在多條通信路徑時(shí),盡量選擇靠近NoC系統(tǒng)邊緣的做法更有利于減少通信網(wǎng)絡(luò)的阻塞。
[Abstract]:With the development of semiconductor technology, more and more IP cores are integrated into a single chip, however, the connection of each IP core has become the bottleneck of improving the system performance. The network proposed in recent years on chip can realize parallel communication between each IP core, with high performance and low power consumption two major advantages, and because it has good scalability and reusability, has in recent years become the focus of the industry and academia. However, in the hardware development at the same time, how the application is mapped to the network on chip hardware and its characteristics can run efficiently and with low power consumption that has become the key to play on the network performance constraints.
This paper is devoted to the design of the software compiler on the network on chip. The design idea of the project group compiler is put forward to achieve the efficient operation of the application on the chip network. The two parts of the task mapping and routing algorithm in the compiler design are mainly introduced.
Task mapping, optimization based on in-depth study of the branch and bound algorithm, put forward the task of binding thoughts. The goal is to reduce the task of mapping between the NoC power communication network nodes. In order to reduce the search space, the task of large communication to bind together, mapped to the network node on the adjacent NoC, significantly improve the efficiency of task mapping. Experiments show that the algorithm can find the optimal mapping scheme of equivalent performance in a shorter time for multi-core system. For example, when mapping 25 tasks to the NoC system of 5 * 5, only 26.3% of the time of the traditional algorithm can find the mapping scheme for the same performance.
The routing algorithm, based on the analysis of the traditional routing algorithm, proposes a communication channel time division multiplexing thought, reduces the bandwidth requirements of NoC system. The hardware resource allocation and recovery in the communication request, is widely used in the operating system of the banker 's algorithm is introduced. In the search for the shortest path to the communication request when the maze algorithm is used. At the same time, when multiple communication paths exist when used as close to the edge of the NoC network, select the center and three kinds of random rules. The experimental results show that the routing algorithm of communication channel time division multiplexing of NoC system is greatly reduced compared to the bandwidth requirements of traditional routing algorithms. At the same time. When multiple communication paths exist, as close to the edge of the practice NoC system can reduce the block of communication.

【學(xué)位授予單位】：復(fù)旦大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2012
【分類號(hào)】：TP332;TN47

【參考文獻(xiàn)】

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

1 蔣韻聯(lián);孫廣中;許胤龍;;并行異構(gòu)系統(tǒng)中的一種高效任務(wù)調(diào)度算法[J];計(jì)算機(jī)工程;2007年11期

2 陳延倉(cāng);謝倫國(guó);李晉文;;一種基于遺傳算法的片上網(wǎng)絡(luò)映射算法[J];計(jì)算機(jī)工程與科學(xué);2009年S1期

3 劉軼;張昕;李鶴;錢德沛;;多核處理器大規(guī)模并行系統(tǒng)中的任務(wù)分配問(wèn)題及算法[J];小型微型計(jì)算機(jī)系統(tǒng);2008年05期

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

1 石澤文;多核處理器的容錯(cuò)路由與粒度建模研究[D];復(fù)旦大學(xué);2011年

，

本文編號(hào)：1370218