小規模不定形応用に適した再構成可能論理システムの研究

本研究では、小規模かつ不定形な応用に対して再構成可能論理回路がどのように適用可能であるか調査研究した。既に一部の定型的応用、即ち大量の均質的データ処理をともなう画像処理やシミュレーション等については、再構成可能論理回路を利用した専用回路によって大きな性能向上が得られることが知られている。しかし多くの応用では処理の構造が複雑でこのような単純な手法で性能向上を得ることはできない。また大量の入出力が伴う応用では、計算機全体の構成が問題となり一部回路の専用化では処理性能の大きな向上は望めない。そこで本研究では、計算時間が支配的で処理の高速化が望まれる応用(しかも入出力による制約を受けない応用)として、“マルチプロセッサのスケジューリング問題"と“部分グラフ同型判定問題"を選び出して研究を行った。これらの計算困難問題では問題規模に対して指数的に計算量が増大するが、理論上効率の良いアルゴリズムは存在しない。そのため専用回路や並列化による高速化が強く望まれている。また、入出力がほとんどないため比較的容易に性能を改善できる可能性がある。研究の結果、部分グラフ同型判定問題に関しては、現状で使用可能なLSI(FPGA)でも実用規模の問題に対して数十倍の性能向上が得られる見込みが得られた。マルチプロセッサ・スケジューリング問題に関しては、モデリングが非常に複雑でソフトウェアによる実用的な解法を得ること自体が難しいことが判明し、専用回路化を検討するには至らなかった。しかし本問題に関しても多くの成果が得られたので数年以内に専用回路化が検討できる段階に至ると思われる。

本研究では、小規模かつ不定形な応用に対して再構成可能論理回路がどのように適用可能であるか調査研究した。既に一部の定型的応用、即ち大量の均質的データ処理をともなう画像処理やシミュレーション等については、再構成可能論理回路を利用した専用回路によって大きな性能向上が得られることが知られている。しかし多くの応用では処理の構造が複雑でこのような単純な手法で性能向上を得ることはできない。また大量の入出力が伴う応用では、計算機全体の構成が問題となり一部回路の専用化では処理性能の大きな向上は望めない。そこで本研究では、計算時間が支配的で処理の高速化が望まれる応用(しかも入出力による制約を受けない応用)として、“マルチプロセッサのスケジューリング問題"と“部分グラフ同型判定問題"を選び出して研究を行った。これらの計算困難問題では問題規模に対して指数的に計算量が増大するが、理論上効率の良いアルゴリズムは存在しない。そのため専用回路や並列化による高速化が強く望まれている。また、入出力がほとんどないため比較的容易に性能を改善できる可能性がある。研究の結果、部分グラフ同型判定問題に関しては、現状で使用可能なLSI(FPGA)でも実用規模の問題に対して数十倍の性能向上が得られる見込みが得られた。マルチプロセッサ・スケジューリング問題に関しては、モデリングが非常に複雑でソフトウェアによる実用的な解法を得ること自体が難しいことが判明し、専用回路化を検討するには至らなかった。しかし本問題に関しても多くの成果が得られたので数年以内に専用回路化が検討できる段階に至ると思われる。