
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

The Design and Evaluation of DataDependent Hardware for Subgraph Isomorphism Problem
Shoji YAMAMOTO Shuichi ICHIKAWA Hiroshi YAMAMOTO
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E87D
No.8
pp.20382047 Publication Date: 2004/08/01 Online ISSN:
DOI: Print ISSN: 09168532 Type of Manuscript: Special Section PAPER (Special Section on Reconfigurable Systems) Category: Recornfigurable Systems Keyword: FPGA, custom circuit, graph algorithm, NPcomplete, partial evaluation,
Full Text: PDF>>
Summary:
Subgraph isomorphism problems have various important applications, while generally being NPcomplete. Though Ullmann and Konishi proposed the custom circuit designs to accelerate subgraph isomorphism problem, they require many hardware resources for large problems. This study describes the design of datadependent circuits for subgraph isomorphism problem with evaluation results on an actual FPGA platform. Datadependent circuits are logic circuits specialized in specific input data. Such circuits are smaller and faster than the original circuit, although it is not reusable and involves circuit generation for each input. In the present study, the circuits were implemented on Xilinx XC2V3000 FPGA, and they successfully operated at a clock frequency 25 MHz. In the case of graphs with 16 vertices, the average execution time is about 7.0% of the software executed on an uptodate microprocessor (Athlon XP 2600+ of 2.1 GHz clock). Even if the circuit generation time is included, datadependent circuits are about 14.4 times faster than the software (for random graphs with 16 vertices). This performance advantage becomes larger for larger graphs. Two algorithms (Ullmann's and Konishi's) were examined, and the datadependent approach was found to be equally effective for both algorithms. We also examined two types of input graph sets, and found that the datadependent approach shows advantage in both cases.


