FPGA向け動作合成におけるメモリバインディングとスケジューリングアルゴリズムについて

• Item type: SIG Technical Reports(1)
• 公開日: 2008-01-17
• タイトル: FPGA向け動作合成におけるメモリバインディングとスケジューリングアルゴリズムについて
• タイトル / 言語: en
• タイトル: Memory Binding and Scheduling in High Level Synthesis for FPGAs
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 九州大学大学院システム情報科学府情報工学専攻
• 著者所属: 九州大学大学院システム情報科学府情報工学専攻
• 著者所属: 九州大学大学院システム情報科学研究院情報工学部門
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Electrical Engineering, Kyushu University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Electrical Engineering, Kyushu University
• 著者所属(英): en
• 著者所属(英): Faculty School of Information Science and Electrical Engineering, Kyushu University
• 著者名: 佐川, 由己; 貞方, 毅; 松永, 裕介
• 著者名(英): Yuki, SAGAWA; Tsuyoshi, SADAKATA; Yusuke, MATSUNAGA
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: FPGA(Field Programmable Gate Array)ではメモリのサイズや数、ポート数が決まっている。そのためFPGA向け動作合成では複数の配列を同じメモリヘバインディングしなければいけない場合がある。同じメモリへバインディングされた複数の配列に対する配列アクセス(参照や書き込み)は、メモリのポート数を超えて同じステップにスケジューリングする事ができない。そのためメモリバインディング次第で配列アクセスの並列度が変化する。配列アクセスが頻繁に起こるアプリケーションの合成では、演算の並列度が高くても配列アクセスの並列度が低いと最大ステップ数が多くなってしまう。本論文ではメモリサイズ、メモリ数、メモリのポート数制約下で配列アクセスの並列度を高めるようにメモリバインディングとスケジューリングを行なうヒューリスティックスを提案する。目的は各DFG(Data Flow Graph)の最大ステップ数の総和を最小化する事である。既存手法として、Simulated Annealing(以下、SA)を用いた手法が提案されている。SAを用いた手法の問題点として解を出すまでに時間がかかる事が挙げられる。提案手法とSAを用いた手法を比較した実験では、多くの場合ほぼ同じステップ数となる解を見つける事ができている。総ステップ数の悪化は最悪な場合で20％程度である。また最高で約2000倍、平均で約1500倍、高速に解を出す事ができている。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In High Level Synthesis for FPGAs, arrays in behavioral description may be bound to the same memory block since the number of memory block is fixed for FPGAs. The number of access to such arrays at one step is limited to the number of memory port. If arrays that are accessed frequently are bound to the same memory block, array accessess will conflict with each other and the conflict will affect the number of steps. Therefore, memory binding and scheduling should be considered simultaneously. In this paper, we propose a heuristic algorithm that deals with memory binding and scheduling simultaneously under the memory size, the number of memory, and the number of memory port constraints subject to minimize the sum of maximum step for all Data Flow Graphs. Experimental results show that the proposed algorithm can find as a good solution as the approach using Simulated Annealing in many cases.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11451459
• 書誌情報: 情報処理学会研究報告システムLSI設計技術（SLDM）; 巻 2008, 号 2(2008-SLDM-133), p. 91-96, 発行日 2008-01-17
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会