Algorithmic Techniques for Solving Graph Problems on the Automata Processor

被引：9

作者：

Roy, Indranil ^{[1
]}

Jammula, Nagakishore ^{[1
]}

Aluru, Srinivas ^{[1
]}

机构：

[1] Georgia Inst Technol, Atlanta, GA 30332 USA

来源：

2016 IEEE 30TH INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM (IPDPS 2016) | 2016年

基金：

美国国家科学基金会;

关键词：

Automata Processor; Graph Algorithms; Reconfigurable Computing;

D O I：

10.1109/IPDPS.2016.116

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

The Automata Processor is a new accelerator technology that supports direct hardware implementation of a set of non-deterministic finite automata over a streaming input, and is designed for complex string pattern matching applications. In this paper, we broaden the scope of this architecture beyond its primary design goal, by developing algorithmic techniques to solve problems on unweighted graphs. We present a strategy to represent nodes and edges in a graph using strings, and use this transformation to develop algorithms for several classic graph problems including finding Hamiltonian paths and cycles, connected components, and breadth-first search. Our algorithms rely on a core set of automata building blocks which we designed for this purpose, and illustrate various design considerations that developers must bear in mind when harnessing this new technology. We expect that this work provides the foundations for solving graph problems using the Automata Processor.

引用

页码：283 / 292

页数：10

共 6 条

[1] An Efficient and Scalable Semiconductor Architecture for Parallel Automata Processing [J].