Title :
Hardware accelerator for subgraph isomorphism problems
Author :
Ichikawa, Shuichi ; Udorn, Lerdtanaseangtham ; Konishi, Kouji
Author_Institution :
Dept. of Knowledge-Based Inf. Eng., Toyohashi Univ. of Technol., Japan
Abstract :
Many applications can be modeled as subgraph isomorphism problems, which are generally NP-complete. This paper presents an algorithm that is suited for hardware implementation. The prototype accelerator that operates at 16.5 MHz on a Lucent ORCA 2C15A FPGA outperforms the software implementation of Ullmann´s algorithm on a 400 MHz Pentium II by 10 times in the best case
Keywords :
field programmable gate arrays; hardware-software codesign; 400 MHz Pentium II; Lucent ORCA 2C15A FPGA; NP-complete; Ullmann´s algorithm; hardware accelerator; hardware implementation; prototype accelerator; software implementation; subgraph isomorphism problems; Application software; Chemical analysis; Databases; Design engineering; Field programmable gate arrays; Hardware; Image analysis; Knowledge engineering; Software algorithms; Software prototyping;
Conference_Titel :
Field-Programmable Custom Computing Machines, 2000 IEEE Symposium on
Conference_Location :
Napa Valley, CA
Print_ISBN :
0-7695-0871-5
DOI :
10.1109/FPGA.2000.903417
