| 講演名 | 2008-01-17 FPGA向け動作合成におけるメモリバインディングとスケジューリングアルゴリズムについて(ICCAD報告と動作合成,FPGA応用及び一般) 佐川 由己, 貞方 毅, 松永 裕介, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | FPGA (Field Programmable Gate Array)ではメモリのサイズや数、ポート数が決まっている。そのためFPGA向け動作合成では複数の配列を同じメモリへバインディングしなければいけない場合がある。同じメモリへバインディングされた複数の配列に対する配列アクセス(参照や書き込み)は、メモリのポート数を超えて同じステップにスケジューリングする事ができない。そのためメモリバインディング次第で配列アクセスの並列度が変化する。配列アクセスが頻繁に起こるアプリケーションの合成では、演算の並列度が高くても配列アクセスの並列度が低いと最大ステップ数が多くなってしまう。本論文ではメモリサイズ、メモリ数、メモリのポート数制約下で配列アクセスの並列度を高めるようにメモリバインディングとスケジューリングを行なうヒューリスティックスを提案する。目的は各DFG (Data Flow Graph)の最大ステップ数の総和を最小化する事である。既存手法として、Simulated Annealing(以下、SA)を用いた手法が提案されている。SAを用いた手法の問題点として解を出すまでに時間がかかる事が挙げられる。提案手法とSAを用いた手法を比較した実験では、多くの場合ほぼ同じステップ数となる解を見つける事ができている。総ステップ数の悪化は最悪な場合で20%程度である。また最高で約2000倍、平均で約1500倍、高速に解を出す事ができている。 |
| 抄録(英) | 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. |
| キーワード(和) | 動作合成 / メモリバインディング / スケジューリングFPGA |
| キーワード(英) | High-Level Synthesis / Memory Binding / Scheduling FPGA |
| 資料番号 | VLD2007-120,CPSY2007-63,RECONF2007-66 |
| 発行日 |
| 研究会情報 | |
| 研究会 | VLD |
|---|---|
| 開催期間 | 2008/1/10(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | VLSI Design Technologies (VLD) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | FPGA向け動作合成におけるメモリバインディングとスケジューリングアルゴリズムについて(ICCAD報告と動作合成,FPGA応用及び一般) |
| サブタイトル（和） | |
| タイトル（英） | Memory Binding and Scheduling in High Level Synthesis for FPGAs |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 動作合成 / High-Level Synthesis |
| キーワード(2)（和/英） | メモリバインディング / Memory Binding |
| キーワード(3)（和/英） | スケジューリングFPGA / Scheduling FPGA |
| 第 1 著者 氏名（和/英） | 佐川 由己 / Yuki SAGAWA |
| 第 1 著者 所属（和/英） | 九州大学大学院システム情報科学府情報工学専攻 Graduate School of Information Science and Electrical Engineering, Kyushu University |
| 第 2 著者 氏名（和/英） | 貞方 毅 / Tsuyoshi SADAKATA |
| 第 2 著者 所属（和/英） | 九州大学大学院システム情報科学府情報工学専攻 Graduate School of Information Science and Electrical Engineering, Kyushu University |
| 第 3 著者 氏名（和/英） | 松永 裕介 / Yusuke MATSUNAGA |
| 第 3 著者 所属（和/英） | 九州大学大学院システム情報科学研究院情報工学部門 Faculty School of Information Science and Electrical Engineering, Kyushu University |
| 発表年月日 | 2008-01-17 |
| 資料番号 | VLD2007-120,CPSY2007-63,RECONF2007-66 |
| 巻番号（vol） | vol.107 |
| 号番号（no） | 415 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |