基于M etis圖劃分算法的圖平衡劃分方法.pdf

1、隨著集成電路技術(shù)的發(fā)展,具有低延遲、低功耗的片上網(wǎng)絡(luò)(Network on Chip, No C)成為了SoC新的發(fā)展方向。FPGA原型驗(yàn)證成為了NoC研究的熱點(diǎn)。大規(guī)模多核NoC無法在單個(gè)FPGA上實(shí)現(xiàn)驗(yàn)證,需要?jiǎng)澐值蕉鄠€(gè)FPGA。本論文主要針對(duì)多核NoC電路劃分問題提出一種基于Metis圖劃分算法的多權(quán)值約束的劃分方法,并完成算法的測試驗(yàn)證。
　　論文首先對(duì)劃分的關(guān)鍵問題進(jìn)行分析,將電路劃分問題轉(zhuǎn)化為圖劃分問題進(jìn)行研究,分析比

2、較了多種典型的劃分算法,并總結(jié)了劃分的基本設(shè)計(jì)方法。重點(diǎn)分析了Metis圖劃分算法的基本原理及工作流程,并提出了改進(jìn)的多權(quán)值約束的劃分算法。在劃分前對(duì)多權(quán)值進(jìn)行融合,并在劃分后評(píng)估劃分效果以改進(jìn)融合參數(shù),提高各個(gè)部分的平衡度。最后采用多個(gè)不同規(guī)模的多權(quán)值圖對(duì)所提出算法進(jìn)行了測試驗(yàn)證。仿真結(jié)果表明所提出算法能夠有效地節(jié)省FPGA資源,降低成本。
　　本文提出了一種基于Metis算法的多權(quán)值圖劃分算法,在考慮到劃分約束條件的情況下保證