| Presentation | 2000/6/19 A Study on Heuristic Algorithms for Net Assignment Problem Daisuke Ito, Takao Ono, Tomio Hirata, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | FPGA emulator / net assignment problem / simulated annealing |
| Paper # | COMP2000-14 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2000/6/19(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A Study on Heuristic Algorithms for Net Assignment Problem |
| Sub Title (in English) | |
| Keyword(1) | FPGA emulator |
| Keyword(2) | net assignment problem |
| Keyword(3) | simulated annealing |
| 1st Author's Name | Daisuke Ito |
| 1st Author's Affiliation | Fujitsu() |
| 2nd Author's Name | Takao Ono |
| 2nd Author's Affiliation | Nagoya University |
| 3rd Author's Name | Tomio Hirata |
| 3rd Author's Affiliation | Nagoya University |
| Date | 2000/6/19 |
| Paper # | COMP2000-14 |
| Volume (vol) | vol.100 |
| Number (no) | 144 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |