Parallel Interval Stabbing on the Automata Processor
Parallel Interval Stabbing on the Automata Processor
复制标题
自动机处理器上的并行间隔刺伤
DOI：
10.1109/ia3.2016.008
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Aluru, Srinivas
中科院分区：
文献类型：
--
作者：
Roy, Indranil;Srivastava, Ankit;Grimm, Matt;Aluru, Srinivas
自动机处理器是为字符串模式匹配而设计的。在本文中，我们展示了它在执行整数和浮点比较方面的用途，并将其应用于加速间隔刺探查询。区间刺探查询确定集合中的哪些区间与查询点重叠。此类查询通常用于计算几何、模式匹配、数据库管理系统和地理信息系统。每个间隔的检查被编程为单个自动机，并且并行执行多个自动机以提供显着的性能增益。在处理32位整数或单精度浮点数时，每秒最多可以执行2.75万亿次比较，而对于64位整数或双精度浮点数，每秒可以完成0.79万亿次比较。此外，我们的解决方案使集合中的间隔保持无序；允许在恒定时间内添加或删除间隔。对于当代的解决方案来说，这是不可能的，其中间隔是有序的，使得查询时间更快，但使得间隔的更新变得复杂。我们的自动机设计体现了最大化资源利用率和最小化性能瓶颈的技术，这可能对该处理器上的未来应用程序开发人员有用。它们的模块化设计使它们能够成为更大自动机的组成部分，其中数值比较是整个模式匹配操作的一部分。我们已经在硬件上验证了设计，生成必要的自动机并在 AP 上执行它们的例程将很快作为软件库提供。
The Automata Processor was designed for string-pattern matching. In this paper, we showcase its use to execute integer and floating-point comparisons and apply the same to accelerate interval stabbing queries. An interval stabbing query determines which of the intervals in a set overlap a query point. Such queries are often used in computational geometry, pattern matching, database management systems, and geographic information systems. The check for each interval is programmed as a single automaton and multiple automata are executed in parallel to provide significant performance gains. While handling 32-bit integers or single-precision floating-point numbers, up to 2.75 trillion comparisons can be executed per second, whereas 0.79 trillion comparisons per second can be completed for 64-bit integers or double-precision floating-point numbers. Additionally, our solution leaves the intervals in the set unordered; allowing addition or deletion of an interval in constant time. This is not possible for contemporary solutions wherein the intervals are ordered, making the query times faster, but making the updating of intervals complex. Our automata designs exemplify techniques that maximize resource utilization and minimize performance bottlenecks, which may be useful to future application developers on this processor. Their modular design allows them to become constituent parts of larger automata, where the numerical comparisons are part of the overall pattern matching operation. We have validated the designs on hardware, and the routines to generate the necessary automata and execute them on the AP will be made available as software libraries shortly.
登录
查看更多内容
影响因子：
1.8
作者：
H. Edelsbrunner
通讯作者：
H. Edelsbrunner
在自动机处理器上迈向机器学习
DOI：
--
发表时间：
2016
期刊：
Information Security Conference
影响因子：
--
作者：
Tommy Tracy;Yao Fu;Indranil Roy;Eric Jonas;P. Glendenning
通讯作者：
P. Glendenning
Micron Automata 处理器上的 Brill 标记
DOI：
--
发表时间：
2015
期刊：
Proceedings of the 2015 IEEE 9th International Conference on Semantic Computing (IEEE ICSC 2015)
影响因子：
--
作者：
Keira Zhou;J. J. Fox;Ke Wang;Donald E. Brown;K. Skadron
通讯作者：
K. Skadron
DOI：
10.1109/ipdps.2015.101
发表时间：
2015-05
期刊：
2015 IEEE International Parallel and Distributed Processing Symposium
影响因子：
--
作者：
Ke Wang;Yanjun Qi;J. J. Fox-J.;Mircea R. Stan;K. Skadron
通讯作者：
Ke Wang;Yanjun Qi;J. J. Fox-J.;Mircea R. Stan;K. Skadron
使用 Micron 自动机处理器进行顺序模式挖掘
DOI：
--
发表时间：
2016
期刊：
Conf. Computing Frontiers
影响因子：
--
作者：
Ke Wang;Elaheh Sadredini;K. Skadron
通讯作者：
K. Skadron