IEICE TRANSACTIONS on Information
The Design and Evaluation of Data-Dependent Hardware for Subgraph Isomorphism Problem
Summary :
Subgraph isomorphism problems have various important applications, while generally being NP-complete. 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 data-dependent circuits for subgraph isomorphism problem with evaluation results on an actual FPGA platform. Data-dependent 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 up-to-date microprocessor (Athlon XP 2600+ of 2.1 GHz clock). Even if the circuit generation time is included, data-dependent 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 data-dependent approach was found to be equally effective for both algorithms. We also examined two types of input graph sets, and found that the data-dependent approach shows advantage in both cases.
- Publication
- IEICE TRANSACTIONS on Information Vol.E87-D No.8 pp.2038-2047
- Publication Date
- 2004/08/01
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section on Reconfigurable Systems)
- Category
- Recornfigurable Systems
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Shoji YAMAMOTO, Shuichi ICHIKAWA, Hiroshi YAMAMOTO, "The Design and Evaluation of Data-Dependent Hardware for Subgraph Isomorphism Problem" in IEICE TRANSACTIONS on Information,
vol. E87-D, no. 8, pp. 2038-2047, August 2004, doi: .
Abstract: Subgraph isomorphism problems have various important applications, while generally being NP-complete. 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 data-dependent circuits for subgraph isomorphism problem with evaluation results on an actual FPGA platform. Data-dependent 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 up-to-date microprocessor (Athlon XP 2600+ of 2.1 GHz clock). Even if the circuit generation time is included, data-dependent 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 data-dependent approach was found to be equally effective for both algorithms. We also examined two types of input graph sets, and found that the data-dependent approach shows advantage in both cases.
URL: https://global.ieice.org/en_transactions/information/10.1587/e87-d_8_2038/_p
Copy
@ARTICLE{e87-d_8_2038,
author={Shoji YAMAMOTO, Shuichi ICHIKAWA, Hiroshi YAMAMOTO, },
journal={IEICE TRANSACTIONS on Information},
title={The Design and Evaluation of Data-Dependent Hardware for Subgraph Isomorphism Problem},
year={2004},
volume={E87-D},
number={8},
pages={2038-2047},
abstract={Subgraph isomorphism problems have various important applications, while generally being NP-complete. 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 data-dependent circuits for subgraph isomorphism problem with evaluation results on an actual FPGA platform. Data-dependent 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 up-to-date microprocessor (Athlon XP 2600+ of 2.1 GHz clock). Even if the circuit generation time is included, data-dependent 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 data-dependent approach was found to be equally effective for both algorithms. We also examined two types of input graph sets, and found that the data-dependent approach shows advantage in both cases.},
keywords={},
doi={},
ISSN={},
month={August},}
Copy
TY - JOUR
TI - The Design and Evaluation of Data-Dependent Hardware for Subgraph Isomorphism Problem
T2 - IEICE TRANSACTIONS on Information
SP - 2038
EP - 2047
AU - Shoji YAMAMOTO
AU - Shuichi ICHIKAWA
AU - Hiroshi YAMAMOTO
PY - 2004
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E87-D
IS - 8
JA - IEICE TRANSACTIONS on Information
Y1 - August 2004
AB - Subgraph isomorphism problems have various important applications, while generally being NP-complete. 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 data-dependent circuits for subgraph isomorphism problem with evaluation results on an actual FPGA platform. Data-dependent 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 up-to-date microprocessor (Athlon XP 2600+ of 2.1 GHz clock). Even if the circuit generation time is included, data-dependent 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 data-dependent approach was found to be equally effective for both algorithms. We also examined two types of input graph sets, and found that the data-dependent approach shows advantage in both cases.
ER -
English
