北海道大学 大学院情報科学研究院

卒業生とその進路

近似最近傍探索のためのハードウェア指向Locality-Sensitive HashingアルゴリズムとそのFPGAアーキテクチャに関する研究


定久 紀基

2015 年度 卒 ／修士（工学）

修士論文の概要

近年、情報爆発という言葉に現れるようにインターネット上のデータが爆発的に増加している。それを処理するデータセンタにはより多くのデータを処理するため分散化を行い処理能力の向上を図っている。しかし、分散処理の弊害として導入コストの増加や消費電力の増加といった問題を抱えてしまった。そのため、データセンタを構成するサーバーのスループット、レイテンシの改善が求められている。

ソフトウェアの領域では、大量のデータから価値を創出するデータマイニングの分野において、データセンタへの負荷の少ないアルゴリズムの創出が進められている。近年では大量のデータを処理するため機械学習を用いた方法や、正確性を犠牲にして高速にデータを処理する近似アルゴリズムの研究が盛んになっている。一方ハードウェアの領域では、従来汎用プロセッサによって行われていた処理をFPGAによる専用ハードウェアで処理を行うことによって、高速化する研究が盛んである。例として、Microsoftによる検索エンジンBingのFPGA実装、XilinxによるデータベースのFPGAアクセラレータなどが挙げられる。

本研究はそうした2つの流れを汲み、データマイニングで用いられるアルゴリズムをFPGAに実装することにより、データセンタで行われる処理を高速化することを主題とした。その対象として情報検索に着目した。情報検索の分野では、使われる殆どのアルゴリズムで演算時間が検索対象の数に比例することがわかっている。そのため、演算時間がデータの数に依存しない仕組みが求められている。その結果創出されたのが、Locality-Sensitive Hashing（LSH）であり、1990年代に発表されてから現在まで研究が進められている。本研究はこれらの背景を元に今後重要になるLSHをFPGAに実装した。

学術論文

  1. Fukuda E.S., Inoue H., Takenaka T., Kim D., Sadahisa T., Asai T., and Motomura M., "Enhancing memcached by caching its data and functionalities at network interface," IPSJ Journal, vol. 56, no. 3, pp. 143-152 (2015).

国際会議

  1. Fukuda E.S., Inoue H., Takenaka T., Kim D., Sadahisa T., Asai T., and Motomura M., "Achieving higher performance of memcached by caching at network interface," The 2014 International Conference on Field Programmable Technology, Parkyard Hotel, Shanghai, China (Dec. 10-12, 2014).
  2. Kim D., Fukuda E.S., Sadahisa T., Asai T., and Motomura M., "Hardware architecture for accelerating key-value retrieval implemented on FPGA," The 3rd Japan-Korea Joint Workshop on Complex Communication Sciences, Paradise Hotel, Busan, Korea (Oct. 27-28, 2014).
  3. Fukuda E.S., Inoue H., Takenaka T., Kim D., Sadahisa T., Asai T., and Motomura M., "Caching memcached at reconfigurable network interface," The 24th International Conference on Field Programmable Logic and Applications, Technische Universität München, Munich, Germany (Sep. 2-4, 2014).

受賞

  1. Kim D., Fukuda E.S., Sadahisa T., Asai T., and Motomura M., "Hardware architecture for accelerating key-value retrieval implemented on FPGA," The 3rd Japan-Korea Joint Workshop on Complex Communication Sciences - Best Student Paper Award, Oct. 28, 2014.

国内学会

  1. 山本 佳生, 定久 紀基, 浅井 哲也, 本村 真人, "FPGAによる多重ハッシュを用いた頻出アイテムセットマイニングのストリームプロセッシング," 電子情報通信学会リコンフィギャラブルシステム研究会, 富士通研究所, (川崎), 2016年5月19-20日.
  2. 定久 紀基, 山本 佳生, 浅井 哲也, 本村 真人, "二重ハッシングによる類似検索ハードウェアアーキテクチャのFPGA実装," LSIとシステムのワークショップ, 北九州国際会議場, (北九州市), 2015年5月11-13日.
  3. 山本 佳生, 定久 紀基, 金 多厚, 福田 駿 エリック, 浅井 哲也, 本村 真人, "頻出アイテムセットマイニング高速化のためのストリームプロセッサ," LSIとシステムのワークショップ, 北九州国際会議場, (北九州市), 2015年5月11-13日.
  4. 定久 紀基, 山本 佳生, 金 多厚, 福田 駿 エリック, 浅井 哲也, 本村 真人, "Locality-Sensitive HashingのスケーラブルなハードウェアアーキテクチャのFPGA実装," 電子情報通信学会総合大会, 立命館大学びわこ・くさつキャンパス, (草津), 2015年3月10-13日.
  5. 定久 紀基, 山本 佳生, 金 多厚, 福田 駿 エリック, 浅井 哲也, 本村 真人, "類似検索を行うLocality-Sensitive Hashingのスケーラブルなハードウェアアーキテクチャ," 電子情報通信学会集積回路研究会・コンピュータシステム研究会合同 平成26年度若手研究会, 機械振興会館, (東京), 2014年12月1-2日.
  6. 定久 紀基, 福田 駿 エリック, 浅井 哲也, 本村 真人, "実データ統計を用いた動的なMemcached評価用ロードジェネレータ," 電子情報通信学会総合大会, 新潟大学 五十嵐キャンパス, (新潟), 2014年3月18-21日.
  7. 福田 駿 エリック, 定久 紀基, 井上 浩明, 竹中 崇, 浅井 哲也, 本村 真人, "二重キャッシングによるMemcached高速化の提案," 電子情報通信学会 リコンフィギャラブルシステム研究会, 慶応義塾大学, (日吉), 2014年1月28-29日.

Copyright © 1999-2024 Tetsuya ASAI & Laboratories for Advanced LSI Engineering (LALSIE), Hokkaido University. All Rights Reserved.