資料緩衝區(buffer) 在SOC中常被使用於溝通兩個擁有不同操作頻率的裝置。在晶片上，緩衝區在所佔的體積以及消耗的能量佔有相當大的比例，因此如何來減小緩衝區的使用量變成了一個重要的議題。而當一個緩衝區被用在以一種操作狀態下，緩衝區的設計以及大小的決定是相當直覺的，一但希望同一個緩衝區可以用在多種操作狀態下，則緩衝區的設計變的相當複雜，因為這個緩衝區必須符合每種操作狀態下的條件及限制，則設計對應的硬體也變得更加困難及耗時。因此，如何能找到緩衝區最小的使用量並且加快硬體設計的時間均是我們所要解決的目標。
在本篇論文中，我們提出了兩個基於表格形式的演算法來探勘混合時域緩衝區的大小，並使之最小化。包含了SLBM (Single-Line-Buffer-Minimization) 可找到單一緩衝區的最小大小，以及PLBM (Parallel-Line-Buffer-Minimization)找到多個並行輸出的緩衝區的最小數量這兩個演算法，並且在演算法結束後，產生相對應的RTL codes 的硬體架構。根據實際實驗結果顯示，SLBM以及PLBM演算法，在分析多種操作情形後，確實能將緩衝區設計的時間提升到幾分鐘，甚至是幾秒左右。

Buffers in system-on-a-chip (SOC) are usually used as synchronization devices among modules in different clock domains or operating speed. Due to area and power concerns, the reduction of the on-chip buffer size has become an issue. When a buffer is designed to operate in just one condition (or operation mode), the design is relatively straightforward. The challenges come when there are various multiple modes. Designers not only need to find the minimum size of the buffers, but also need to make sure the designed buffers can meet performance requirements for all modes in hardware implementation.
In this work, we first present formulation of this new problem; then propose not only two table-based algorithms to minimize buffers for multiple modes, but also design automation tool to generate synthesizable register-transfer level (RTL) hardware description language. The proposed two algorithms, Single-Line-Buffer-Minimization (SLBM) and Parallel-Line-Buffer-Minimization (PLBM), systematically analyze sequences and speeds of the input and the output to minimize the size of the buffer. Then it generates the corresponding hardware in RTL to simplify the tedious design process and shorten the design time.
Experimental results using realistic test cases show that the buffers thus designed and generated only need seconds to minutes in time depending on the complexity in requirements.

[1] Arvind, R.S. Nikhil, D.L. Rosenband, and N. Dave, “High-level synthesis: an essential ingredient for designing complex ASICs,” Proceedings of the International conference on Computer-aided design, pp. 775-782, 2004,.
[2] J. Koehl, D.E. Lackey, and G. Doerre, “IBM's 50 Million gate ASICs,” Proceedings of the 2003 conference on Asia South Pacific design automation, pp. 628-634, 2003.
[3] Synopsys inc., “Galaxy design platform multi-voltage Design, available online,” http://www.synopsys.com/products/power/multivoltage_bkgrd.pdf .
[4] D. Gajski and L. Ramachandran, “Introduction to high-level synthesis,” IEEE Design & Test of Computers, vol.11, pp. 44-54, 1994.
[5] S. Narayana, “On-Chip Communication Hardware Resources for Globally Asynchronous and Locally Synchronous Systems,” Proceedings of the 8th International Symposium on Parallel Architectures, Algorithms and Networks, IEEE Computer Society, pp. 208-213, 2005.
[6] A.S. Huang, G. Siavenburg, J.P. Shen, G. Reinman, D.M. Tullsen, and M.H. Lipasti, “Data supply Data Supply Instruction,” 1995.
[7] S. Han, X. Guerin, S. Chae, and A.A. Jerraya, “Buffer memory optimization for video codec application modeled in Simulink,” Proceedings of the 43rd annual conference on Design automation, pp. 689-694, 2006.
[8] P. Boncz, S. Manegold, and M.L. Kersten, “Database Architecture Optimized for the new Bottleneck: Memory Access,” Proceedings Of VLDB Conference, pp. 54-65, 1999.
[9] Chih-Cheng Wei and Chin-Hsing Chen, “Generalized Bilinear Interpolation of Motion Vectors for Quad-Tree Mesh,” International Conference on Intelligent Information Hiding and Multimedia Signal Processing, pp. 635-638, 2008.
[10] J. Vanne, E. Aho, T. Hamalainen, and K. Kuusilinna, “A Parallel Memory System for Variable Block-Size Motion Estimation Algorithms,” IEEE Transactions on Circuits and Systems for Video Technology, vol.18, pp. 538-543, 2008.
[11] Y.G. Lee, J.H. Lee, and J.B. Ra, “Fast half-pixel motion estimation based on directional search and a linear model,” SPIE Processing VCIP 2003, pp. 1513-1520, 2003.
[12] E. Lee and D. Messerschmitt, “Synchronous data flow,” Proceedings of the IEEE, vol.75, pp. 1235-1245, 1987.
[13] S. Stuijk, M. Geilen, and T. Basten, “SDF^3: SDF For Free,” Application of Concurrency to System Design, 6th International Conference, pp. 276–278, 2006.
[14] J. Hahn and P.H. Chou, “Buffer optimization and dispatching scheme for embedded systems with behavioral transparency,” Proceedings of the 7th ACM & IEEE International Conference on Embedded Software, pp. 94-103, 2007.
[15] P.K. Murthy and S.S. Bhattacharyya, “Shared Buffer Implementations of Signal Processing Systems Using Lifetime Analysis Techniques,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol.20, pp. 177-198, 2001.
[16] P.K. Murthy and S.S. Bhattacharyya, “Buffer merging -- a powerful technique for reducing memory requirements of synchronous dataflow specifications,” ACM Transaction Design Automation Electronic Systems, vol.9, pp. 212-237, 2004.
[17] J. Mun, S. Cho, and S. Hong, “Flexible Controller Design and Its Application for Concurrent Execution of Buffer Centric Dataflows,” Journal of VLSI Signal Processing, vol.47, pp. 233-257, Jun. 2007.
[18] Clifford E. Cummings, “Simulation and Synthesis Techniques for Asynchronous FIFO Design with Asynchronous Pointer Comparisons,” Synopsys Users Group, San Jose, California: 2002.
[19] R.W. Apperson, Z. Yu, M.J. Meeuwsen, T. Mohsenin, and B.M. Baas, “A scalable dual-clock FIFO for data transfers between arbitrary and haltable clock domains,” IEEE Transaction on VLSI Systems, vol.15, pp. 1125-1134, 2007.