| 講演名 | 2005-09-16 FPGA上へのGA回路設計支援ツールの提案(設計手法と高性能化) 橘 達弘, 村田 佳洋, 柴田 直樹, 安本 慶一, 伊藤 実, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 遺伝的アルゴリズム(GA)は様々なアプリケーションに用いることができる.GAを用いたアプリケーションは, ハードウェア上に実装することで, 安価で資源の少ない情報機器上で利用することができる.本論文では, 適用する問題や利用可能な回路規模に従って, 実行効率の良いGA回路を合成するためのアーキテクチャを提案し, またこのアーキテクチャに従って実装される回路の規模予測モデルを提案する.本アーキテクチャおよび回路規模予測モデルを用いて, 指定するFPGAデバイスに実装が可能なパラメタを探索するツールと, そのパラメタをもとにVHDLで記述されたRTレベル回路記述を自動で生成するツールを作成した.提案手法の有効性を示すために, ナップサック問題と巡回セールスマン問題を対象とするGA回路を提案アーキテクチャに従って実装し, これらが優れた解探索性能を示し, また低消費電力で動作することを確認した.また, 回路規模の予測結果が実際に論理合成を行って得たサイズに十分近いことを確認した. |
| 抄録(英) | Genetic Algorithm (GA) can be used for various applications including complex computations such as combinatory optimization problems. Such GA applications can be available to information appliances with poor resources by implementing them on dedicated hardware chips like FPGA. In this paper, we propose a method for efficiently design and implement GA applications on FPGA. Our method consists mainly of a parallel and pipelined architecture for various GA applications and a model to predict the size of the synthesized hardware circuits for various parameter values such as the size of the problem and the number of parallel pipelines. To facilitate hardware design, we have implemented two tools. The first tool uses a prediction model and calculates parameter values with which the hardware circuits can be synthesized on a specified FPGA device. The second tool generates the RT level VHDL description when the parameter values are given. In order to show efficiency of the proposed method, we have applied our method to Knapsack Problem and Traveling Salesman Problem. As a result, we have confirmed that the circuits synthesized with our tools achieve high performance and low power consumption, and that our prediction models predict the sizes of the synthesized circuits accurately enough for practical use. |
| キーワード(和) | 遺伝的アルゴリズム / ハードウェア自動合成 / ナップサック問題 / 巡回セールスマン問題 |
| キーワード(英) | genetic algorithm / FPGA / hardware design automation / Knapsack Problem / Traveling Salesman Problem |
| 資料番号 | RECONF2005-42 |
| 発行日 |
| 研究会情報 | |
| 研究会 | RECONF |
|---|---|
| 開催期間 | 2005/9/9(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Reconfigurable Systems (RECONF) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | FPGA上へのGA回路設計支援ツールの提案(設計手法と高性能化) |
| サブタイトル（和） | |
| タイトル（英） | A Proposal of Design Support Tool for Genetic Algorithm Circuits on FPGA |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 遺伝的アルゴリズム / genetic algorithm |
| キーワード(2)（和/英） | ハードウェア自動合成 / FPGA |
| キーワード(3)（和/英） | ナップサック問題 / hardware design automation |
| キーワード(4)（和/英） | 巡回セールスマン問題 / Knapsack Problem |
| 第 1 著者 氏名（和/英） | 橘 達弘 / Tatsuhiro TACHIBANA |
| 第 1 著者 所属（和/英） | 奈良先端科学技術大学院大学情報科学研究科 Graduate School of Information Science Nara Institute of Science and Technology |
| 第 2 著者 氏名（和/英） | 村田 佳洋 / Yoshihiro MURATA |
| 第 2 著者 所属（和/英） | 奈良先端科学技術大学院大学情報科学研究科 Graduate School of Information Science Nara Institute of Science and Technology |
| 第 3 著者 氏名（和/英） | 柴田 直樹 / Naoki SHIBATA |
| 第 3 著者 所属（和/英） | 滋賀大学経済学部情報管理学科 Department of Information Processing and Managem ent, Shiga University |
| 第 4 著者 氏名（和/英） | 安本 慶一 / KEIICHI Yasumoto |
| 第 4 著者 所属（和/英） | 奈良先端科学技術大学院大学情報科学研究科 Graduate School of Information Science Nara Institute of Science and Technology |
| 第 5 著者 氏名（和/英） | 伊藤 実 / Minoru ITO |
| 第 5 著者 所属（和/英） | 奈良先端科学技術大学院大学情報科学研究科 Graduate School of Information Science Nara Institute of Science and Technology |
| 発表年月日 | 2005-09-16 |
| 資料番号 | RECONF2005-42 |
| 巻番号（vol） | vol.105 |
| 号番号（no） | 288 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |