山中研究室の石川君(卒業生)による論文が国際会議The 14th Asia-Pacific Conference on Communications (APCC 2008)において、Best Paper Awardを受賞しました。
APCCは主にアジア太平洋地域を中心とした国際会議で、今年は東京・秋葉原で200本以上の論文を集めて開催されました。

石川君の研究は、並列データフロー型リコンフィギュラブルプロセッサを用いた集合被覆問題を高速で解くアルゴリズムの提案と、その実装です。
集合被覆問題は、一般的にはNP困難問題です。
石川君の研究では、リコンフィギュラブルプロセッサに適したアルゴリズムを提案し、厳密解を並列パイプライン処理を用いることで、これまでの100倍以上の高速化が行えることを理論的に証明しただけでなく、提案アルゴリズムを実装し、実験によっても効果を確認しました。
今後、低消費電力ネットワーク設計などの複雑な最適化問題などへの応用が期待されています。

タイトル，要旨は以下のとおりです．

タイトル: “Fast Replica Allocation Method by Parallel Calculation on DAPDNA-2”
著者: Hiroyuki Ishikawa, Sho Shimizu, Yutaka Arakawa, Naoaki Yamanaka, and Kosuke Shiba
要旨: This paper proposes a fast calculation method of the replica placement problem, which is implemented on reconfigurable processor DAPDNA-2 of IPFlex Inc. Our proposed method divides the combination optimally and performs pipeline operation. Beeler’s algorithm can calculate all combinations in ascending order but it has data dependence. It’s difficult to calculate any pattern because each data increases irregularly. In order to solve this problem, we propose the new algorithm that generates any order pattern. In addition, the optimal number of partitions depends on the number of combinations and calculation clocks of Beeler’s algorithm. In order to solve this problem, we think about the optimal division number in theory. While the time complexity of conventional method is proportional to the number of combinations, that of proposed method is proportional to the square root of the number of combinations. Experimental results show that the proposed algorithm reduces the execution time by 40 times compared to Intel Pentium 4 (2.8GHz).