The Application of Reconfigurable Logic Circuits to Hard Computation Problems

虽然有许多计算困难的问题。那些有重要应用的，很难解决大规模的问题。本研究的目的是研究定制电路技术来加速硬计算问题。特别是，可重构逻辑技术被广泛地用于一个实例应用(子图同构问题)。子图同构问题是NP完全问题，针对该问题的定制电路设计，已经提出了两种硬件算法：Ullmann算法和Konishi算法。我们研究了这两种算法的各种实现，发现这些设计的逻辑规模太大，不适合实际应用，通常情况下，如果逻辑电路的一些输入固定为常量，逻辑电路的逻辑规模就会减小。派生电路变得比原始电路更小、更快，而它依赖于输入实例，因此不能重复使用。在本研究中，我们将这种电路称为“数据依赖电路”。使用数据依赖设计，我们可以在相同的逻辑规模下实现比其数据独立的硬件版本更大的问题。可重构逻辑器件非常适合于数据相关电路，因为它们在运行时是可重编程的。这种方法的一个缺点是我们必须为每个输入实例生成数据相关电路。因此，数据依赖电路的总执行时间由电路生成时间和执行时间组成。如果电路生成时间远远大于执行时间，则电路生成时间可能会抵消定制电路的加速。在这项研究中，我们设计、实现和评估了子图同构问题的数据依赖电路，结果表明，即使包括电路生成时间，它们也比软件快。

Although there are many hard computation problems. that have important applications, it is very difficult to solve large-scale problems. The purpose of this study is to investigate the custom circuit technology to accelerate hard computation problems. In particular, reconfigurable logic technology is extensively examined for an example application (subgraph isomorphism problem). Subgraph isomorphism problems are NP-complete, and two hardware algorithms have been proposed for the custom circuit design of this problem ; Ullmann's algorithm and Konishi's algorithm. We examined various implementations of these two algorithms, and found that the logic scales of these designs are too large for practical applications.Generally, the logic scale of a logic circuit is reduced if some of its inputs are fixed to constant values. The derived circuit becomes smaller and faster than the original, while it is dependent on the input instances and thus not reusable. We call this kind of circuits as "data dependent circuits" in this study. With data dependent design, we can implement larger problems than its data "independent" version of hardware in the same logic scale. Reconfigurable logic devices are well suited for data dependent circuits, because they are reprogrammable at run-time One of the drawbacks of this approach is that we have to generate data dependent circuits for each input instances. Therefore, the total execution time of a data dependent circuit consists of the circuit generation time and the execution time. If the circuit generation time is much larger than the execution time, the circuit generation time may offset the acceleration by custom circuit. In this study, we designed, implemented, and evaluated the data dependent circuits for subgraph isomorphism problems, and showed that they are faster than the software even if the circuit generation time is included.