以廣義網路流為基礎之低功率可程式邏輯閘陣列記憶體映射演算法

A Generalized Network Flow Based Algorithm for Power-Aware FPGA Memory Mapping

許天騵(Tien-Yuan Hsu)

指導教授 ： 王廷基

國立清華大學/電機資訊學院/資訊工程學系/碩士(2007年)

https://doi.org/10.6843/NTHU.2007.00611

摘要

在可程式邏輯閘陣列上，裝置上的實體記憶體是很重要的一個部份，它可以實作設計者所設計的各種記憶體結構。由於實體記憶體的廣泛使用，起動這些實體記憶體所耗費的能量成為了整體動態耗電量的相當重要的一部份。在這一篇論文裡，我們提出了一個低功率記憶體映射的演算法，在考慮記憶體數量的限制之下，將邏輯記憶體映射到實體記憶體上。我們的方法將記憶體映射的問題轉換成一個廣義網路流的問題，它可以同時將實體記憶體資源分配給邏輯記憶體，而不是將邏輯記憶體一個接著一個地做資源分配的工作；在和另一個已存在的方法比較之後，可以展示出我們的方法是比較優秀的，在問題有解的情況之下，我們一定可以找到一個耗電量最少的最佳解，這是另一個已存在的方法做不到的。

關鍵字

廣義網路流 ； 低功率 ； 可程式邏輯閘陣列 ； 記憶體映射

並列摘要

Embedded memory blocks in FPGAs allow designers to implement a variety of memory structures. With the increasing use of embedded memory blocks, the power consumed by them has formed a significant part of the total dynamic power consumption. In this thesis, we present a power-aware memory mapping algorithm, which maps user-defined logical memories to physical embedded memory blocks under the memory resource constraint. Our algorithm converts the memory mapping problem to a generalized network flow (GNF) problem, which can distribute embedded memory blocks to all logical memories at the same time. Our algorithm is compared with an existing method, and the promising experimental results show that our algorithm can always efficiently generate optimal solutions while the existing method cannot.

並列關鍵字

Generalized Network Flow ； Power-Aware ； FPGA ； Memory Mapping

參考文獻

[1] S. Bakshi and D. Gajski, “A Memory Selection Algorithm for High-Performance Pipelines”, in Proceedings of the European Design Automation Conference, pp. 124-129, 1995.

[2] H. Schmit and D. Thomas, “Address Generation for Memories Containing Multiple Arrays”, in IEEE Transactions on VLSI Systems, vol. 17, pp. 377-385, 1998.

[3] D. Karchmer and J. Rose, “Definition and Solution of the Memory Packing Problem for Field-Programmable Systems,” in Proceedings of International Conference on Computer-Aided Design, pp. 20-26, 1994.

[5] R. Tessier, V. Betz, D. Neto, and T. Gopalsamy, “Power-aware RAM Mapping for FPGA Embedded Memory Blocks,” in Proceedings of FPGA symposium, pp. 189-198, 2006.

[7] Xilinx Corporation, Virtex-4 User Guide, April, 2007.