| 講演名 | 2000/6/19 COMP2000-14 ネット割当て問題のヒューリスティック解法に関する研究 伊藤 大介, 小野 孝男, 平田 富夫, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本論文では論理エミュレータにおけるネット割当て問題を考察する。論理エミュレータ上には多数のFPGAとクロスバが配置されており、配線要求(ネット)に従ってクロスバによりFPGAをつなぐ。ネット割当て問題とは、このようなネットの集合(ネットリスト)が与えられたときに各ネットをクロスバへ割当てる問題である。この問題は一般にはNP-完全であり、従来いくつかのグリーディアルゴリズムが提案されている。本論文では、この問題に対してシミュレーテッドアニーリング(SA)を適用するアルゴリズムを提案しその性能を実験的に示す。さらに、実験で用いられる問題例の性質を利用したアルゴリズム(NPA)を提案する。SAの初期解生成アルゴリズムとしてNPAを用いると計算時間が短く解を見付ける性能の高いアルゴリズムが得られることを実験的に示す。 |
| 抄録(英) | In this paper, we consider the net assignment problem in the logic emulation system based on field-programmable gate arrays(FPGAs). This problem is also known as the board-level-routing problem. There are FPGAs and crossbars on a board. Each FPGA is connected to each crossbar. Connection requests between FPGAs are called"nets, "and FPGAs are interconnected through crossbars. We are required to assign each net to the suitable crossbar. Since this problem is known to be NP-complete in general, there have been propose some heuristic algorithms. They are considered as greedy algorithms. In this paper, we propose an algorithm which generates an initial assignment by a greedy algorithm and improves the assignment by simulated annealing. In addition, we propose the net packing algorithm(NPA) specialized to the board used in the experiments. We observed that NPA as an initial assignment generator yields a high performance algorithm. |
| キーワード(和) | FPGAエミュレータ / ネット割当て問題 / シミュレーテッドアニーリング |
| キーワード(英) | FPGA emulator / net assignment problem / simulated annealing |
| 資料番号 | COMP2000-14 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2000/6/19(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | COMP2000-14 ネット割当て問題のヒューリスティック解法に関する研究 |
| サブタイトル（和） | |
| タイトル（英） | A Study on Heuristic Algorithms for Net Assignment Problem |
| サブタイトル（和） | |
| キーワード(1)（和/英） | FPGAエミュレータ / FPGA emulator |
| キーワード(2)（和/英） | ネット割当て問題 / net assignment problem |
| キーワード(3)（和/英） | シミュレーテッドアニーリング / simulated annealing |
| 第 1 著者 氏名（和/英） | 伊藤 大介 / Daisuke Ito |
| 第 1 著者 所属（和/英） | 富士通 Fujitsu |
| 第 2 著者 氏名（和/英） | 小野 孝男 / Takao Ono |
| 第 2 著者 所属（和/英） | 名古屋大 Nagoya University |
| 第 3 著者 氏名（和/英） | 平田 富夫 / Tomio Hirata |
| 第 3 著者 所属（和/英） | 名古屋大 Nagoya University |
| 発表年月日 | 2000/6/19 |
| 資料番号 | COMP2000-14 |
| 巻番号（vol） | vol.100 |
| 号番号（no） | 144 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |