可重組裝置之面積最佳化問題

Abstract

運用可重組裝置來設計嵌入式系統已逐漸成為一個重要的議題。透過可重組裝置進行可重組計算，並使用最少的面積來設計嵌入式系統，是一個仍需克服的挑戰。不同於以往提出的研究，本論文將探討在可重組計算環境中，可重組裝置使用之面積最佳化問題。除分析不同限制條件下之子問題的複雜度外，同時提出可解決問題之演算法與無法解決問題之複雜度證明。並透過模擬退火演算法與其他演算法之比較，以及有系統的模擬實驗與實例研究之分析，作為系統設計時可提供之參考。

Reconfiguration has become an important and practical issue in product designs and their lifetime. In this paper, we target an essential issue in the reconfiguration designs of embedded systems. In particular, we explore the size minimization problems of reconfigurable devices in partial reconfiguration schedules We identify factors that contribute to the NP-hardness of the problems. We first present problems with efficient algorithms and their solutions. We then address factors for NP-hardness and provide some proofs. A simulated annealing algorithm is later proposed to serve as a comparison with heuristics-based algorithm to provide insights in system designs. A series of extensive simulation experiments and a case study are presented to provide insights and comparisons among different approaches.