利用以滿足性解法器為基礎的高效邏輯修正技術來達成即時性可修正的現場可程式化邏輯陣列應用

Toward On-the-fly Reconfigurable FPGA Applications by Efficient SAT-Based Logic Rectification Techniques

黃柏凱(Po-Kai Huang)

指導教授 ： 黃鐘揚

國立臺灣大學/電機資訊學院/電機工程學研究所/碩士(2012年)

https://doi.org/10.6342/NTU.2012.00724

摘要

對於現場可程式化邏輯陣列的設計來說，即時性部分修改的技術在這幾年來逐漸成為重要的需求。利用這項技術，我們可以只修改部分系統，並同時保留系統其餘的部分來改變其行為。而這對需要有彈性與及時適應硬體架構的軍事與通訊設備而言，此技術顯得特別有效。然而，現今產生符合部分修正的適當修改之設計工具，仍只有受限的支援與自動化。此外，對於使用者來說，當修改的數量相當多時，利用手動來取得要求的功能是不切實際且沒有效率的。在這篇論文中，我們提出一個有效的自動化流程在系統中找尋需要考慮的部分，並產生符合修正的適當修改。精確地來說，我們的演算法可只藉由重新更改某些找查表（Look-Up Table）的功能，並保持原先的單元繞線與擺放，來實現所需要的功能。此外，我們開發若干技巧來降低修正流程的複雜度，並改善其效能。實驗結果顯示，我們的演算法可以在邏輯階層與暫存器轉移階層中，實現不同目標的功能。

關鍵字

錯誤診斷 ； 邏輯修正 ； 布林可滿足性 ； 現場可程式化邏輯陣列

並列摘要

On-the-fly partial reconfiguration on FPGA designs has become an increasingly im-portant requirement in recent years. With this attribute, the behavior of a system can be changed partially while the rest of the design is still preserved. It is especially useful for applications in such as military or communication devices which require flexible and adaptive hardware. However, there are limited supports and automation in design tools to generate appropriate modifications for partial reconfiguration. Moreover, when there are significant numbers of modifications, it is impractical and inefficient for users to derive the desired functions in a manual way. In this thesis, we propose an efficient automated flow which is able to search for the portions of the device needed for consideration and generate proper modifications for the reconfiguration. To be precise, our algorithm achieves the desired functionalities by only reconfiguring some of the Look-Up Tables (LUTs) while preserving engineering efforts on cell interconnections and placement. In addition, we develop several techniques to alleviate the complexity and improve the performance of the reconfiguration process. The experimental results show that our algorithm can achieve the reconfiguration of various targeted functions in both the logic and Register-Transfer (RT) levels efficiently and effectively.

並列關鍵字

Error diagnosis ； Logic rectification ； Boolean satisfiability ； FPGA

參考文獻

[1] Stephan Wong, Stamatis Vassiliadis, and Sorin Cotofana. Future directions of (programmable and reconfigurable) embedded processors. In Proc. SAMOS, pages 91–108, 2002.

[2] S. Hauck. The roles of FPGAs in reprogrammable systems. In Proc. IEEE, 86(4):615–638, 1998.

[3] James D. Hadley and Brad L. Hutchings. Design methodologies for partially reconfigured systems. In Proc. FCCM, pages 78–84, 1995.

[4] Scott McMillan and Steve Guccione. Partial run-time reconfiguration using JRTR. In Proc. FPL, pages 352–360, 2000.

[9] Berkeley Logic Synthesis and Verification Group. ABC: A system for sequential synthesis and verification. http://www.eecs.berkeley.edu/~alanmi/abc/