1、隨著半導(dǎo)體技術(shù)的不斷進(jìn)步，單個(gè)芯片上能夠集成的處理單元越來越多。片上網(wǎng)絡(luò)作為實(shí)現(xiàn)這些處理單元間互連的基礎(chǔ)通信架構(gòu)受到了學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注。硬件成本和通信性能是評(píng)價(jià)片上網(wǎng)絡(luò)可用性的兩個(gè)非常重要的指標(biāo)，如何以較低的硬件成本設(shè)計(jì)出能夠滿足實(shí)際應(yīng)用需求的片上網(wǎng)絡(luò)結(jié)構(gòu)是該領(lǐng)域研究的核心問題。本文針對(duì)片上網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計(jì)與性能分析中幾個(gè)關(guān)鍵問題展開研究，主要的研究工作如下：
　　(1)支持端口間緩存和虛通道共享的路由器微體系結(jié)構(gòu)研究

2、　　虛通道蟲孔交換片上網(wǎng)絡(luò)的性能、功耗和硬件成本都會(huì)受到虛通道數(shù)量、緩存容量和緩存組織方式的影響。為了在不引入較大的硬件開銷和功耗負(fù)擔(dān)的前提下最大化片上網(wǎng)絡(luò)的性能，需要盡可能地提高路由器緩存資源的利用率。這就要求對(duì)緩存資源進(jìn)行動(dòng)態(tài)的分配和管理，以適應(yīng)片上網(wǎng)絡(luò)流量的動(dòng)態(tài)變化?，F(xiàn)有的方案基本都是圍繞著如何在路由器的端口之間或者端口內(nèi)的虛通道之間實(shí)現(xiàn)緩存資源的共享，忽略了不同端口對(duì)虛通道數(shù)量的不同需求以及需求的動(dòng)態(tài)變化。
　　為此，本文

3、提出了一種支持端口間自適應(yīng)虛通道共享（Adaptive Virtual Channel Sharing，AVCS）的路由器微體系結(jié)構(gòu)，該結(jié)構(gòu)可以在運(yùn)行時(shí)根據(jù)網(wǎng)絡(luò)流量的變化動(dòng)態(tài)地調(diào)整每個(gè)路由器端口所能使用的緩存容量和虛通道數(shù)量。首先，本文分析了經(jīng)典路由器存在的主要問題，并針對(duì)這些問題提出了AVCS路由器的基本架構(gòu)。然后，本文面向AVCS路由器提出一個(gè)低成本的共享資源分配算法，該算法可以在運(yùn)行時(shí)將共享緩存資源按需分配給各個(gè)端口使用。最后，本

4、文又面向AVCS路由器提出了一個(gè)虛通道和交換機(jī)分配器請(qǐng)求端口共享方案，該方案讓每個(gè)端口的私有虛通道與對(duì)應(yīng)的共享虛通道復(fù)用同一個(gè)虛通道和交換機(jī)分配器的請(qǐng)求端口，從而顯著地降低了分配器的規(guī)模和硬件成本。本文提出的AVCS路由器具有緩存資源利用率高、硬件開銷小和平均延遲低等優(yōu)點(diǎn)。實(shí)驗(yàn)結(jié)果顯示，與具有同樣性能的經(jīng)典路由器結(jié)構(gòu)相比，AVCS路由器可以降低32.1％的功耗并節(jié)省11.7%的芯片面積。
　　(2)基于實(shí)時(shí)演算的片上網(wǎng)絡(luò)端到端延遲

5、上界分析方法研究
　　在基于片上網(wǎng)絡(luò)的多核處理器系統(tǒng)上部署實(shí)時(shí)應(yīng)用程序之前，必須要保證每條數(shù)據(jù)流在最差情況下的延遲上界都不違背其時(shí)限約束。針對(duì)這一需求，學(xué)術(shù)界已經(jīng)提出了基于確定性網(wǎng)絡(luò)演算的分析方法、基于流的分析方法和基于鏈路的分析方法來分析數(shù)據(jù)流的端到端延遲上界。然而，基于流和基于鏈路的分析方法都只能應(yīng)用于路由器的緩存容量足夠大的情況?；诰W(wǎng)絡(luò)演算的分析方法雖然沒有對(duì)緩存容量做任何假設(shè)，但是獲得的延遲上界比較悲觀，需要進(jìn)一步地改進(jìn)

6、。
　　為此，本文提出一個(gè)基于實(shí)時(shí)演算的端到端延遲分析算法來克服基于流和基于鏈路的延遲分析方法的應(yīng)用限制，并進(jìn)一步改進(jìn)確定性網(wǎng)絡(luò)演算的分析結(jié)果。首先，本文提出一個(gè)流量模型變換定理用于將切片級(jí)實(shí)時(shí)演算到達(dá)曲線變換成報(bào)文級(jí)實(shí)時(shí)演算到達(dá)曲線，該定理使得對(duì)報(bào)文級(jí)端到端延遲上界的分析成為可能；然后，本文為蟲孔交換片上網(wǎng)絡(luò)建立了一個(gè)實(shí)時(shí)服務(wù)曲線模型，并利用極小加代數(shù)的有關(guān)性質(zhì)推導(dǎo)出了信約流量控制器的等效實(shí)時(shí)服務(wù)曲線；最后，本文基于前面建立的報(bào)

7、文級(jí)實(shí)時(shí)到達(dá)曲線模型和路由器的實(shí)時(shí)服務(wù)曲線模型提出了一個(gè)端到端延遲分析算法。與已有的方法相比，該算法同時(shí)支持固定優(yōu)先級(jí)搶占調(diào)度和輪詢調(diào)度，對(duì)于緩存容量有限的片上網(wǎng)絡(luò)也能給出正確的分析結(jié)果，并且獲得的延遲上界比已有的方法更加緊致。
　　(3)基于實(shí)時(shí)演算的片上網(wǎng)絡(luò)緩存分配算法研究
　　路由器的緩存容量對(duì)整個(gè)片上網(wǎng)絡(luò)的性能、功耗和硬件成本都有巨大的影響。為了降低基于優(yōu)先級(jí)的蟲孔交換片上網(wǎng)絡(luò)的硬件成本，學(xué)術(shù)界已經(jīng)提出了虛通道共享方

8、案和基于鏈路的緩存分配算法。然而，虛通道共享方案會(huì)嚴(yán)重影響網(wǎng)絡(luò)的通信性能，而且在特定的路由策略下還會(huì)引起死鎖?；阪溌返木彺娣峙渌惴m然可以保證網(wǎng)絡(luò)的通信性能，但是緩存分配結(jié)果過于保守。
　　為此，本文提出一種基于實(shí)時(shí)演算的片上網(wǎng)絡(luò)緩存分配算法來降低基于優(yōu)先級(jí)的蟲孔交換片上網(wǎng)絡(luò)的硬件成本。該算法在保證時(shí)限約束的前提下，按照優(yōu)先級(jí)順序優(yōu)化每條數(shù)據(jù)流在其經(jīng)過的路由器上預(yù)留的緩存資源。首先，本文基于實(shí)時(shí)演算理論給出了每條數(shù)據(jù)流在其經(jīng)過的

9、每個(gè)路由器上都不觸發(fā)流量控制的一個(gè)充分條件，該條件可以用于確定整個(gè)緩存優(yōu)化算法的迭代初始值；然后，本文給出了一個(gè)緩存分配過程來減少路由器為每條數(shù)據(jù)流預(yù)留的緩存資源，并結(jié)合前面給出的迭代初值定理提出了一個(gè)可以確保最差情況下通信性能的緩存分配算法。與已有的緩存分配算法相比，本文提出的算法可以顯著地降低路由器的硬件開銷，極大地降低路由器的硬件成本、功耗和芯片面積。
　　(4)低延遲路徑選擇算法及其快速驗(yàn)證技術(shù)研究
　　在蟲孔交換片

10、上網(wǎng)絡(luò)中，每條數(shù)據(jù)流的端到端延遲都會(huì)受到網(wǎng)絡(luò)中其它數(shù)據(jù)流的傳輸路徑和流量特性的影響。因此，在為高優(yōu)先級(jí)數(shù)據(jù)流確定傳輸路徑時(shí)應(yīng)當(dāng)盡量選擇那些對(duì)低優(yōu)先級(jí)數(shù)據(jù)流影響較小的鏈路，以盡可能的優(yōu)化每一條數(shù)據(jù)流的端到端延遲。在確定了所有數(shù)據(jù)流的傳輸路徑之后，還需要一種有效的延遲分析方法來快速地確定是否每條數(shù)據(jù)流的延遲約束都得到了滿足。如果有數(shù)據(jù)流違背延遲約束，則應(yīng)該嘗試為其選擇一條新的傳輸路徑。
　　針對(duì)上述需求，本文提出了一種面向Mesh網(wǎng)絡(luò)

11、的低延遲路徑選擇算法來優(yōu)化每條數(shù)據(jù)流的端到端延遲。首先，該算法根據(jù)每條鏈路對(duì)低優(yōu)先級(jí)數(shù)據(jù)流的重要性程度為其賦予不同的權(quán)重。在確定鏈路的權(quán)重時(shí)，該算法充分利用了Mesh網(wǎng)絡(luò)的基本性質(zhì)和組合數(shù)學(xué)的相關(guān)方法，大幅度地降低了已有方法的計(jì)算復(fù)雜度和存儲(chǔ)開銷。然后，該算法利用Dijkstra算法為每個(gè)數(shù)據(jù)流選擇一條合適的傳輸路徑。最后，該算法又利用之前提出的基于實(shí)時(shí)演算的延遲分析算法對(duì)每條數(shù)據(jù)流的延遲約束進(jìn)行檢查。為了加快延遲約束的檢查速度，本文還