2部グラフに対する高速な辺彩色アルゴリズムの開発と実装

点击翻译按钮获取中文摘要

この研究は, (1)複雑なデータ構造を用いずに線形時間で作動する正則2部グラフの辺彩色アルゴリズムの開発と,(2)FPGAを用いてそのアルゴリズムをスイッチの実装に利用することを目標に始まった。計画の最終年度である本年度途中に、「複雑データ構造を処理する専用回路をFPGAで作成することで高速処理させる」というアイデアを着想した。その後、研究の重点を、理論面・実用面ともに興味深く思えたこちらのアイデアに移動した。その結果、k個の比較器を並列に作動させることで、n≦2^kまでのn個のデータをnに比例する時間でソートできる、ヒープの改良を考案できた。改良により、ヒープの動作をパイプライン的に処理可能になり、比較器を常に動作させることができるようになったため処理時間の改良に結びつけることができた。現在、FPGAでの実装と論文の作成中である。当初の目的であった、正則2部グラフの辺彩色アルゴリズム等は今後の課題として残されたが、データ処理の基本であるソートを高速化できる理論的な成果を得た。また、「並列計算・パイプライン等のハードウェアを意識したアルゴリズムの設計と改良、および、アルゴリズムにあわせた専用ハードウェアの開発」という、今後の発展の期待の持てる研究の方向性を提示することができた。この方向に研究を進めることで、「データ構造・アルゴリズムのプログラミング用ライブラリの機能を高速化する専用処理ボード」といったハードウェア製品の開発に結びつくと期待できる。