2008年度受賞者詳細
2008年度コンピュータサイエンス領域奨励賞受賞者詳細
|
●漸増的なパストライ構築に基づく高速・軽量XML文書フィルタリング |
|
萩尾 一仁 君 （正会員） 発表時所属： 九州大学大学院システム情報科学府情報理学専攻受賞時所属： 日本電気株式会社ITプラットフォームビジネスユニットOSSプラットフォーム開発本部 |
| [推薦理由] 対象論文は，XPath式によるストリーム型XML文書フィルタを開発している．基本手法としては，パストライを用いたフィルタ処理を行っている．パストライとは，XML木におけるパス文字列全体の集合をトライ(Trie)として表現したものである．本研究では，XMLデータを走査しながらパストライ構築とパス照合を同時に行うことによって，XMLストリームに対して高速にフィルタ処理を行っている点に新規性がある．代表的なストリーム型XML文書フィルタと比較し，実行速度で2～5倍の向上，メモリ使用量で80%～95%の削減を実現しており，その有用性は極めて高い．よって，CS領域奨励賞に値すると判断する． |
| [ 戻る ] |
|
●プログラム依存グラフを用いたアスペクトの干渉検出ツールの実装 |
|
平井 孝 君 （正会員） 発表時所属： 立命館大学大学院理工学研究科修士2回生受賞時所属： 野村総合研究所 金融システム事業本部 |
| [推薦理由] 本論文は，プログラムの挙動の同値性でアスペクトの干渉を定義し，AspectJで記述されたプログラムのプログラム依存グラフの等価性判定により，干渉を検出する手法とツールを提案している．アスペクト指向プログラミングでは，クラスに現れる横断的関心事を分離できる反面，アスペクトが互いに干渉しあい意図通りに動作しないことがある．この干渉を検出する手法としてプログラム依存グラフを用いる着眼点が新しく，これにより干渉検出の自動化に成功している．自動化ツールを統合開発環境Eclipseに組み入れ，干渉検出に要する時間を計測する実験結果を示すことで，実際のソフトウェア開発における有効性を立証している点も評価できる． |
| [ 戻る ] |
|
●動的切り替え可能なSIMD/MIMD型プロセッサにおけるMIMDコアの低コスト実現法 |
|
野本 祥平 君 （正会員） 発表時所属： NECシステムIPコア研究所受賞時所属： NECシステムIPコア研究所 |
| [推薦理由] 本論文では，高並列SIMDプロセッサが有する高性能・低消費電力性，およびMIMDプロセッサが有する並列性の柔軟な活用可能性の双方の性質を併せ持つプロセッサを実現する新しい構成方式を提案している．具体的には，高並列SIMDプロセッサのProcessing Element(PE)アレイが有する豊富な回路資源に着目し，1)複数PEのメモリ・レジスタファイルを流用したキャッシュ機構，2)SIMD/MIMDコアにおけるデータパスの共有，3)複数PE演算器群を流用した浮動小数点データパスにより，複数PEを組み合わせて１つのMIMDコアを実現する．さらに，実装上の追加コストを，MIMDコア全体の回路規模の約10％までに抑えられることも明らかにした．実用的に有用な手法の提案および実証を行っていることを高く評価し，本奨励賞に推薦する． |
| [ 戻る ] |
|
●柔軟な負荷分散を可能にする分散型シングルIPクラスタ |
|
藤田 肇 君 （正会員） 発表時所属： 東京大学大学院情報理工学系研究科コンピュータ科学専攻修士2年受賞時所属： 東京大学情報基盤センタースーパーコンピューティング研究部門 |
| [推薦理由] 分散型シングルIPクラスタは，負荷分散，耐故障性，利便性の観点から優位な方式であるが，従来の方式ではクライアントの情報に基づいた静的な接続割当てにのみ対応し，局面に応じた動的な負荷分散を行いにくいなどの問題があった．本研究では，TCP-DSCと呼ぶ，クラスタのノードのうち一つをTCP接続受理用のマスタノードを用い，接続確立後は各ノードに処理を分散する方式を提案し，実装を行った． 新規性のある分散型シングルIPクラスタの一方式を提案，HTTPサーバで評価を行い，実装と方式の問題点を明らかにした．特に実装した点を評価する． |
| [ 戻る ] |
|
●統計情報に基づく省電力Linuxスケジューラ |
|
金井 遵 君 （学生会員） 発表時所属： 東京農工大学工学府電子情報工学専攻博士後期課程1学年受賞時所属： 東京農工大学工学府電子情報工学専攻博士後期課程2学年 |
| [推薦理由] 本研究は，統計情報に基づいて計算機環境毎に最適化された性能予測モデルと，フィードバック制御を用いて，プロセス単位で省電力化を行うOSスケジューラを提案している．OSレベルでの実装により，アプリケーションに電力制御のコードを埋め込むことなく，容易に計算機毎の性能予測モデルの最適化と，プロセス単位での省電力化制御を行うことができる． 提案された統計情報に基づくプロセス単位の省電力スケジューラは多く使われているLinuxで活用が見込め，その価値は高い．性能解析も十分であり，説得力がある． |
| [ 戻る ] |
|
●マルチタスク環境におけるスクラッチパッドメモリ領域活用法 |
|
高瀬 英希 君 （学生会員） 発表時所属： 名古屋大学大学院情報科学研究科情報システム学専攻修士課程2年受賞時所属： 名古屋大学大学院情報科学研究科情報システム学専攻 |
| [推薦理由] 本論文は，ソフトウェア制御可能なオンチップメモリであるスクラッチパッドメモリを有効利用することによりメモリサブシステムのエネルギー消費を削減する手法を提案している．従来からシングルタスクを対象としたスクラッチパッドメモリの利用法は数多く提案されてきたが，複数のタスクが同時に実行されるマルチタスクを対象とした手法はほとんど提案されていなかった．本手法はスクラッチパッドメモリを時分割および空間分割して，複数のタスクに最適に配分することによりメモリサブシステムの消費エネルギーを最大４７％削減することに成功した．手法の独創性および有効性ともに高く評価できる．以上の理由により本論文をCS領域奨励賞に推薦する． |
| [ 戻る ] |
|
●準形式的モデル検査のハードウェア実装による高速化の検討 |
|
森下 賢志 君 （学生会員） 発表時所属： 東京大学工学部電子工学科４年受賞時所属： 東京大学大学院工学系研究科電気系工学専攻 |
| [推薦理由] 本論文は，大規模集積回路の検証を高速化する手法を提案している．現在非常に有効な検証手法と考えられているモデル検査は，適用する回路の規模が大きくなると状態爆発を起こし，検証時間が急激に増加するという問題がある．本手法はモデル検査手法の一つであるコンパイルドシミュレーションの処理の一部を専用ハードウェアによって実行することにより検証速度を大幅に短縮した．ソフトウェアと専用ハードウェアの通信を効率化する方法も提案している．いくつかの例題を使った実験では，既存手法に比べて平均で6.7倍の高速化が実現できることを確認している．手法の独創性および有効性ともに高く評価できる．以上の理由により本論文をCS領域奨励賞に推薦する． |
| [ 戻る ] |
|
●精度混合型Krylov部分空間反復法における疎行列ベクトル積のCell BE上での実装と性能評価 |
|
木原 崇智 君 （正会員） 発表時所属： 筑波大学大学院システム情報工学研究科コンピュータサイエンス専攻受賞時所属： 日本電気株式会社 |
| [推薦理由] 大規模シミュレーションで現れる線形方程式の解法としてKrylov 部分空間反復法が用いられる．このとき，前処理の計算時間が大部分を占める場合 が多く，その高速化が重要となる．本研究では，精度混合型Krykov部分空間反復法において演算誤差の解への影響を解析し，適切な反復公式を用いれば単精度前処理を用いても倍精度の解が得られることを示した．さらに，多項式前処理に用いられる単精度疎行列ベクトル積のCell BEプロセッサ上での実装方法を提案し，数値実験により高い性能が得られることを示した．非対称型マルチコアプロセッサの性能を発揮させるための研究を非常に高いレベルで行っていることはCS領域奨励賞に十分値し，今後のさらなる研究に期待して本賞に推薦する． |
| [ 戻る ] |
|
●性能モデルに基づくCPU及びGPUを併用する効率的なFFTライブラリ |
|
尾形 泰彦 君 （学生会員） 発表時所属： 東京工業大学情報理工学研究科数理・計算科学専攻修士課程1年受賞時所属： 東京工業大学情報理工学研究科数理・計算科学専攻修士課程2年 |
| [推薦理由] 高い演算性能を有するGPUを利用した数値計算が近年注目されているが，本研究はGPUを利用した計算におけるオーバーヘッドを考慮した場合，GPUと（マルチコア）CPUの実効性能差はそれほど大きくないことに着目し，2次元FFTを対象としてCPUとGPUを併用したライブラリを構築している．本ライブラリは，GPUにおけるFFTとして既存の2種のライブラリを利用しているが，GPU単体のメモリ以上のデータのFFTを実行可能としており，CPUとGPUの計算配分（割り当て率）を設定することができる．本ライブラリの性能はこの割り当て率に依存するが，本研究では性能モデルに基づいた最適割り当て率の予測機能に関する提案を行い，数値実験では5%以下の誤差で最適値を予測している．また，CPU1コアやGPU単体での実行と比べて，1.19から1.55倍の速度向上を実現している．このような質の高い研究を修士課程において行っていることはＣＳ領域奨励賞に値 し，今後のさらなる研究に期待して本賞に推薦する． |
| [ 戻る ] |
|
●リスト上の最大マーク付け問題を解く並列プログラムの導出 |
|
松崎 公紀 君 （正会員） 発表時所属： 東京大学大学院情報理工学系研究科数理情報学専攻受賞時所属： 東京大学大学院情報理工学系研究科数理情報学専攻 |
| [推薦理由] 本論文は，すでに提案されている再帰データ構造上の最大マーク付け問題に対して，データ構造をリストに限定し，著者らによって提案されている並列計算のための関数スケルトンに適用する手法を提案している．定義域が有限な場合に，並列#?鮗存修垢觸犒觜臉?砲弔い董ご愎瑤紡个垢覦貅錣竜婀愎瑤鯢修箸#て導出する手法を新たに示している．このアイデアに著者らによる既存の並列化手法を適用し，従来は逐次的であった最大マーク付け問題に対する並列プログラムの導出手法を示している．導出のためのオーバーヘッドは，最適化後で２倍以下であり，並列化による高速化が可能であることが実験に基づいて示されており，有用性も高い．よって，CS領域奨励賞に推薦する． |
| [ 戻る ] |
|
●多相レコード型に基づくRubyプログラムの型推論 |
|
松本宗太郎 君 （学生会員） 発表時所属： 筑波大学大学院システム情報工学研究科コンピュータサイエンス専攻後期博士課程1学年受賞時所属：筑波大学大学院システム情報工学研究科コンピュータサイエンス専攻 |
| [推薦理由] この論文は動的型付けを持った言語に型推論による静的型付けを導入するという，比較的に長い伝統のあるテーマにおいて，新たにRubyという言語を対象にすることで，類のない面白い試みとなっている．Rubyの一部を型付ける型推論アルゴリ#坤爐Ⅳ茲咾修侶織轡好謄爐#(部分的な)健全性を証明していることで，確実な成果を上げている．健全性を必ずしも重視しない方針を取ることで，将来的には実用的なRubyプログラムも対象としており，今後の発展にも十分に期待できる．よって，CS領域奨励賞にふさわしい研究と考え，推薦するものである． |
| [ 戻る ] |
|
●Sign-Solvable Linear Complementarity Problems |
|
垣村 尚徳 君 （正会員） 発表時所属： 東京大学大学院情報理工学系研究科数理情報学専攻博士課程3年受賞時所属： 東京大学大学院情報理工学系研究科数理情報学専攻数理情報第二研究室 |
| [推薦理由] 線形相補性(LCP)とは，線形計画や凸二次計画を特殊ケースとして含む数理計画問題である．LCPが符号可解であるとは，解の取りうる符号パターンの集合が係数要素の大きさによらず定まることをいう．本研究では，係数行列の対角要素がすべて非零であるLCPに対して，その符号可解性に対する必要十分条件を与えている．また，符号可解LCPの解の符号パターンを効率的に得るための組合せ解法も提案している．本研究の内容は非常に興味深く，数学的にも優れている．以上のことから、CS領域奨励賞にふさわしい成果として推薦する． |
| [ 戻る ] |
|
●Dirichlet Process Unigram Mixture Modelに対するCollapsed Variational Bayes inferenceの適用 |
|
佐藤 一誠 君 （正会員） 発表時所属： 東京大学大学院情報理工学系研究科受賞時所属： （株）日立製作所 |
| [推薦理由] Unigram Mixture Mode(UMM)は教師無し文書分類で幅広く使われている確率的生成モデルである．UMMは，混合モデルなので実際の適用にはユーザーの混合数決定問題を常に保持している．近年，このような混合モデルにおいて，Dirichlet Process(DP)を用いたノンパラメトリックベイズモデルが注目を集めている．DPを用いることでデータに合わせてモデル構造(混合数)を変化させることができる．このようなモデルは総称してDirichlet Process Mixture Model(DPMM)と呼ばれている．本研究では，DPを用いてDPMMに拡張したUMMに対して，Collapsed Variational Bayes inferenseを用いてモデル学習する手法を示している．そして，現実的な応用を考慮して情報検索や教師無し文書分類で使われているF-scoreと相互情報量による評価を行い，これにより従来手法に対する有効性を確認している．以上のことを総合的に評価した結果，本論文を受賞論文として推薦する． |
| [ 戻る ] |
|
●確率木文法近似理論の RNA 二次構造解析への応用 |
|
小笠原和哉 君 （正会員） 発表時所属： 電気通信大学情報工学科受賞時所属： （株）日立製作所 |
| [推薦理由] 本研究ではシュードノット構造を含むRNA二次構造を解析するためのツールとして非常に有用なものである．しかし，解析にかかる計算時間が大きく，その点が実用上の問題となっている．本研究では，確率木文法を確率正則文法で近似する手法を提案している．そして，これを用いてゲノム配列におけるRNAファミリーの候補位置で不要な物を取り除くことについて報告している．以上のように研究内容は非常に良くまとまっており，その成果も明確に記載されている．このことから，本論文を受賞論文として推薦する． |
| [ 戻る ] |
|
●UMLによる組込みソフトウェア設計のレビュー支援ツールの開発 |
|
鈴木 健司 君 （正会員） 発表時所属： 茨城大学大学院理工学研究科情報工学専攻博士前期課程２年受賞時所属： 富士フイルム株式会社 R&D統括本部ソフトウエア開発センター |
| [推薦理由] ソフトウェアの設計表現手法としてのUMLは組込みソフトウェアの分野で急速に浸透しつつあるが，組込みシステムを表現する上では様々な工夫が必要となる．本研究では組込みシステムが有する並列性，リアルタイム性などに着目し組込みソフトウェアに適した拡張記述を提案するとともに，それらに着目した設計レビューの観点いついても考察している．また，これらをもとに設計レビューを支援するためのツールを作成し，その効果に関して実証している点を高く評価できる． |
| [ 戻る ] |
|
●OSEKアプリケーション統合のための柔軟なスケジューリングフレームワーク |
|
松原 豊 君 （学生会員） 発表時所属： 名古屋大学大学院情報科学研究科情報システム学専攻高田・冨山研究室博士後期課程2年受賞時所属： 名古屋大学大学院情報科学研究科情報システム学専攻高田・冨山研究室博士後期課程3年 |
| [推薦理由] 複数のアプリケーションが統合して動作する組込みシステムでは時間制約がきわめて重要な問題となる．この課題解決の手法として階層化スケジューリング手法があるが，本研究では自動車分野で利用されるOSEK OSをモチーフとして，スケジューリングフレームワークを設計し，その設計をもとに実装したプロトタイプを用いた実験をとおして有効性について議論をしている．この研究で示されたスケジューリングフレームワークの設計思想や，プロトタイプによる評価結果などは，様々な組込みシステム構築の際に参考になるものと考えられる． |
| [ 戻る ] |