以機率方式解時間切換式現場可程式化邏輯閘陣列之分割問題

Abstract

由於可利用分時共享的技術以增加邏輯密度 (logic density)，時間切換式現場可程式化邏輯閘陣列 (time multiplexed FPGA) 已成為重組計算上的一個重要研究議題。因為在時間切換式現場可程式化邏輯閘陣列中電路元件的執行先後順序限制 (precedence constraint) 以及容量限制 (capacity constraint), 使得時間切換式現場可程式化邏輯閘陣列的分割問題 (partitioning) 跟傳統的分割問題有所不同。在這篇論文中，我們提出一個以機率為基礎的漸進改良 (iterative-improvement) 方式來達到不同分割區域 (partition) 之間連線花費的最小化 (communicating cost)， 並且同時滿足優先權限制以及容量限制。我們更進一步使用分群 (clustering) 方法來減低問題搜尋空間，以改進大型電路的執行時間及品質。在以Xilinx時間切換式現場可程式化邏輯閘陣列上的實驗顯示，我們的方法在連線花費上分別比List scheduling以及network-flow-based method 要節省33.2%以及12.4%。

Improving logic density by time-sharing, time-multiplexed FPGAs (TMFPGAs) have become an important research topic for reconfigurable computing. Due to the precedence and capacity constraints in TMFPGAs, the partitioning problems for TMFPGAs are different from the traditional ones. In this paper, with both the precedence and capacity considerations, we propose a probability-based iterative-improvement approach to minimize the communication cost among different partitions. We further present a clustering algorithm to reduce the problem size, so that the runtime and quality of solutions of our approach can be improved simultaneously for large circuits. Experimental results based on the Xilinx TMFPGA architecture show that our algorithm reduces the maximum numbers of micro registers required by average improvements of 33.2\% and 12.4\% compared with the List scheduling and the network-flow-based methods, respectively.