The Design and Evaluation of Data-Dependent Hardware for Subgraph Isomorphism Problem(Recornfigurable Systems)(<Special Section>Reconfigurable Systems)

概要

論文の詳細を見る
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.
社団法人電子情報通信学会の論文
2004-08-01

The Design and Evaluation of Data-Dependent Hardware for Subgraph Isomorphism Problem(Recornfigurable Systems)(<Special Section>Reconfigurable Systems)

スポンサーリンク

概要

著者

関連論文

スポンサーリンク