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

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

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

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