基于空間特性優(yōu)化的映射布局算法研究.pdf

1、隨著半導(dǎo)體工藝技術(shù)的發(fā)展，集成電路設(shè)計者能夠?qū)⒃絹碓綇?fù)雜的電路功能集成到單硅片上，并最終在20世紀(jì)90年代中期開發(fā)出SoC(System on Chip，系統(tǒng)芯片)。SoC代表著集成電路向集成系統(tǒng)轉(zhuǎn)變的大方向。但是，隨著SoC中所包含的IP核數(shù)目增至成千上萬的時候，現(xiàn)有的以總線結(jié)構(gòu)為通信基礎(chǔ)的SoC技術(shù)面臨著在性能、功耗、延時和可靠性等方面的巨大挑戰(zhàn)。為了解決復(fù)雜SoC所面臨的問題，在2001年左右，一些研究機構(gòu)借鑒和吸收通信網(wǎng)絡(luò)中的一

2、些思想，提出了以通信為核心的復(fù)雜SoC的IP核的集成方法，即片上網(wǎng)絡(luò)(Networkon Chip，NoC)。
　　 本文的研究工作主要集中在一下幾個方面，首先對目前片上網(wǎng)絡(luò)設(shè)計中的路由算法，交換技術(shù)，幀傳輸技術(shù)，網(wǎng)絡(luò)拓撲，映射布局等方面做了詳細的介紹。其次，本文提出一種基于貪心思想的映射布局算法，本文集中討論了幾種常用的數(shù)據(jù)結(jié)構(gòu)方式：0-tree，B*tree，隊列結(jié)構(gòu)，Map結(jié)構(gòu)。隨著應(yīng)用負載的形式與種類的不斷地增多，0-t

3、ree以及B*tree結(jié)構(gòu)無法滿足不規(guī)則應(yīng)用負載以及非聯(lián)通負載的要求。本文算法采用更加靈活的隊列結(jié)構(gòu)對映射布局進行建模，使用隊列結(jié)構(gòu)移動模塊的時間復(fù)雜度僅為0(1)，旋轉(zhuǎn)模塊的時間復(fù)雜度為0(n)，計算解的質(zhì)量的時間復(fù)雜度為0(a3)。通過Map結(jié)構(gòu)的輔助，計算解的質(zhì)量的時間復(fù)雜度降低為0(a2)。
　　 在本文中使用了一些新的技術(shù)，如：標(biāo)志位標(biāo)示法，動態(tài)窗口策略，初始布局優(yōu)化方法，移動估值矩陣等。標(biāo)志位標(biāo)示法解決了Map結(jié)構(gòu)中