松崎 公紀 東京大学 大学院情報理工学系研究科 数理情報学専攻 数理第七研究室 助教 Email: kmatsu _at_ ipl.t.u-tokyo.ac.jp (_at_を@に置換して下さい)

研究テーマ

ワークショップ "Workshop on Parallelism Oblivious Programming" を2007年7月26-27日に行います. 広く参加者を募集しています.

現在, 私は「助っ人」プロジェクトにおいて, スケルトン並列プログラミング (Skeletal Parallelism) に関する研究を行っている. スケルトン並列プログラミングでは, スケルトンと呼ばれる並列計算でよく利用される処理を抽象化したものを組みあわせることでプログラミングを行う. この並列計算モデルには次のような利点がある.

• 簡潔性: 並列スケルトンを用いることで, ユーザはほとんど並列性を意識せずに並列プログラムを書くことができる.
• 効率性: それぞれの並列スケルトンは効率良く実装されるため, ユーザはスケーラビリティの高いプログラムを得ることができる.
• 抽象性: 並列スケルトンは並列計算を抽象化したものであるため, アーキテクチャへの依存が少く, 移植性に富むプログラムが得られる.

私はスケルトン並列プログラミングの分野において, 具体的に次に挙げるような内容について研究を行っている.

• 木に対する並列スケルトン: これまで, 並列スケルトンに関する研究は, 主に基本的なデータ構造であるリスト (配列) を中心に行なわれてきた. データ構造の一つである木は重要なデータ構造であるが, それらに対するデータ並列スケルトンについてはそれほど研究がなされていないのが現状である. そこで, 木に対する並列計算を抽象化した並列スケルトンの定義, 条件とその実現を目指している. これに関する最も最近の研究"Systematic Derivation of Tree Contraction Algorithms"という論文を, 国際ワークショップCMPP04 (International Workdhop on Constructive Methods for Parallel Programming) にて発表した.
• プログラミング変換を利用したスケルトン並列プログラミング環境の構築: スケルトン並列プログラミングの理論に関しては, これまで様々な研究がなされてきているが, 実用的に利用できるようなライブラリがまだ実現されていないのが現状である. そこで, 関数型言語の分野で研究されてきたプログラミング変換の手法を利用して, 実用的なスケルトン並列プログラミングの環境の構築を目指している. 現在, 電通大岩崎研究室と共同のグループで研究を行っており, これに関する最新の研究"A Fusion-Embedded Skeleton Library"という論文を, 国際会議EuroPar2004 (Annual European Conference on Parallel Processing) にて発表した.

研究関係の活動

• 「助っ人」プロジェクト (SkeTo project) 実用的なスケルトン並列プログラミング環境の構築を行うことを目的としたグループ.
• PDPS (Parallel and Distributed Programming Seminar) : 主に理論的な並列プログラミングに関する内容を扱うセミナーを隔週で行っています.
• 並列計算関係の会議リスト (締切順)
• 並列計算関係の会議リスト (開催順)
• 興味のある会議リスト (開催順)

• 2008年度
  • プログラミング演習 (数理情報工学演習第一C) 第9回
• 2007年度
  • 数理情報工学演習 第一A・C 第9回
• 2006年度
  • 数理実習C (離散手法)
    ウェブグラフを対象として, 基本的なグラフ探索アルゴリズムとそのプログラミングについて実習を行います.
• 2005年度
  • 数理実習C (離散手法)
    ウェブグラフを対象として, 基本的なグラフ探索アルゴリズムとそのプログラミングについて実習を行います.

発表資料等

1. 森畑 明昌, 松崎 公紀, 胡 振江, 武市 正人
   並列プログラムの候補生成と適合性検査による並列化
   情報処理学会論文誌：プログラミング, 採録決定.
2. Akimasa Morihata, Kiminori Matsuzaki, Zhenjiang Hu, Masato Takeichi
   The Third Homomorphism Theorem on Trees: Upward & Downward Leads to Divide-and-Conquer
   In Proceedings of the 36th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Savannah, GA, USA, January 21-23, 2009, pp. 177-185, ACM, 2009.
3. Kiminori Matsuzaki, Akimasa Morihata
   Balanced Ternary-Tree Representation of Binary Trees and Balancing Algorithms
   Technical Report METR 2008-30, 18 pages, Department of Mathematical Engineering and Information Physics, University of Tokyo, 2008. Available from METR List 2008.
   
4. Akimasa Morihata, Kiminori Matsuzaki
   A Parallel Tree Contraction Algorithm on Non-Binary Trees
   Technical Report METR 2008-27, 7 pages, Department of Mathematical Engineering and Information Physics, University of Tokyo, 2008. Available from METR List 2008.
5. Akimasa Morihata, Kiminori Matsuzaki, Masato Takeichi
   Write it Recursively: A Generic Framework for Optimal Path Queries
   In Proceedings of the 2008 ACM SIGPLAN International Conference on Functional Programming, Sept. 22-24, 2008, Victoria, BC, Canada, pp. 169-178, ACM.
6. Kento Emoto, Zhenjiang Hu, Kazuhiko Kakehi, Kiminori Matsuzaki, Masato Takeichi
   Generator-based GG Fortress Library
   Technical Report METR 2008-16, 19 pages, Department of Mathematical Engineering and Information Physics, University of Tokyo, 2008. To be available from METR List 2008.
   
   • Kento Emoto, Zhenjiang Hu, Kazuhiko Kakehi, Kiminori Matsuzaki, Masato Takeichi
     Generator-based GG Fortress Library --Collection of GGs and Theories--
     Technical Report METR 2008-17, 19 pages, Department of Mathematical Engineering and Information Physics, University of Tokyo, 2008. To be available from METR List 2008.
     
7. 松崎 公紀, 胡 振江, 武市 正人
   リスト上の最大マーク付け問題を解く並列プログラムの導出
   情報処理学会論文誌：プログラミング, Vol.49, No.SIG 3 (PRO36). 2008. pp. 16-27.
8. Kento Emoto, Kiminori Matsuzaki, Zhenjiang Hu, Masato Takeichi
   Domain-Specific Optimization Strategy for Skeleton Programs
   In Proceedings of 13th International European Conference on Parallel and Distributed Computing (EuroPar 2007), Lecture Notes in Computer Science 4641, pp. 705-714, Springer, 2007.
   
   • 江本 健斗, 松崎 公紀, 胡 振江, 武市 正人
     近傍要素を必要とするスケルトンプログラムの最適化
     第9回プログラミングおよびプログラミング言語ワークショップ (PPL 2007), pp. 125-139, 加賀温泉, 2007年3月8日-10日.
     • Kento Emoto, Kiminori Matsuzaki, Zhenjiang Hu, Masato Takeichi
       Domain-Specific Optimization for Skeleton Programs Involving Neighbor Elements
       Technical Report METR 2007-05, 29 pages, Department of Mathematical Engineering and Information Physics, University of Tokyo, 2007. To be available from METR List 2007.
       
9. Kazutaka Morita, Akimasa Morihata, Kiminori Matsuzaki, Zhenjiang Hu, Masato Takeichi
   Automatic Inversion Generates Divide-and-Conquer Parallel Programs
   In ACM SIGPLAN 2007 Conference on Programming Language Design and Implementation (PLDI 2007), pp. 146-155, San Diego, CA, June 10-13, 2007.
   
10. Kiminori Matsuzaki
    Efficient Implementation of Tree Accumulations on Distributed-Memory Parallel Computers
    In Fourth International Workshop on Practical Aspects of High-level Parallel Programming (PAPP 2007), part of The International Conference on Computational Science (ICCS 2007), pp. 609-616, Beijing, China, May 27-30, 2007.
    • Kiminori Matsuzaki, Zhenjiang Hu
      Efficient Implementation of Tree Skeletons on Distributed-Memory Parallel Computers
      Technical Report METR 2006-65, 22 pages, Department of Mathematical Engineering and Information Physics, University of Tokyo, 2006. Available from METR List in 2006.
    • Kiminori Matsuzaki, Zhenjiang Hu, Masato Takeichi
      Implementation of parallel tree skeletons on distributed systems
      In Proceedings of the Third Asian Workshop on Programming Languages and Systems (APLAS '02), pp. 258-271, Shanghai, China, 2002.
      • 松崎 公紀, 胡 振江, 武市 正人
        分散メモリ型並列計算機上での木に対する並列スケルトンの実現
        日本ソフトウェア科学会 第19回大会 (2002年度) 論文集, 2002.
11. Kazuhiko Kakehi, Kiminori Matsuzaki, Kento Emoto
    Efficient Parallel Tree Reductions on Distributed Memory Environments
    In Fourth International Workshop on Practical Aspects of High-level Parallel Programming (PAPP 2007), part of The International Conference on Computational Science (ICCS 2007), pp. 601-608, Beijing, China, May 27-30, 2007.
    • Kazuhiko Kakehi, Kiminori Matsuzaki, Kento Emoto, Zhenjiang Hu
      An Practicable Framework for Tree Reductions under Distributed Memory Environments
      Technical Report METR 2006-64, 21 pages, Department of Mathematical Engineering and Information Physics, University of Tokyo, 2006. Available from METR List 2006.
12. 野村 芳明, 江本 健斗, 松崎 公紀, 胡 振江, 武市 正人
    木スケルトンによるXPathクエリの並列化とその評価
    コンピュータソフトウェア, 24 (3): 51-62, 2007.
    • 野村 芳明, 江本 健斗, 松崎 公紀, 胡 振江, 武市 正人
      木スケルトンによるXPathクエリの並列化とその評価
      日本ソフトウェア科学会第22回大会論文集, 東北大学, 2005年9月13日-15日
13. Kiminori Matsuzaki, Zhenjiang Hu, Masato Takeichi
    Parallel Skeletons for Manipulating General Trees
    Parallel Computing, Vol. 32, No. 7-8, pp. 590-603, Elsevier B.V., 2006.
    
    • Kiminori Matsuzaki, Zhenjiang Hu, Masato Takeichi
      Design and Implementation of General Tree Skeletons
      Technical Report METR2005-30, Department of Mathematical Engineering and Information Physics, University of Tokyo, 2005.
      • Kiminori Matsuzaki
        Parallel Tree Reduction and its Implementation in C++
        Presentation at the first DIKU-IST Workshop, Sep 23-24, 2005.
14. Kiminori Matsuzaki, Zhenjiang Hu, Masato Takeichi
    Towards Automatic Parallelization of Tree Reductions in Dynamic Programming
    In SPAA 2006: 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures, July 30 - August 2, 2006, Cambridge, Massachusetts, USA, pages 39 - 48, 2006. Available from ACM Digital Library
15. Kento Emoto, Kiminori Matsuzaki, Zhenjiang Hu, Masato Takeichi
    Surrounding Theorem: Developing Parallel Programs for Matrix-Convolutions
    In 12th International Euro-Par Conference, Dresden, Germany, August/September 2006, Proceedings, pages 605 - 614, Lecture Notes in Computer Science 4128, 2006.
    
16. Kiminori Matsuzaki, Kento Emoto, Hideya Iwasaki, Zhenjiang Hu
    A Library of Constructive Skeletons for Sequential Style of Parallel Programming
    First International Conference on Scalable Information Systems (InfoScale 2006), Hong Kong, May 29 - June 1, 2006. Available from ACM Digital Library.
    
    • 松崎 公紀, 明石 良樹, 江本 健斗, 岩崎 英哉, 胡 振江
      助っ人：構成的な並列スケルトンによる並列プログラミングライブラリ
      日本ソフトウェア科学会第22回大会論文集, 東北大学, 2005年9月13日-15日
17. Kazuhiko Kakehi, Kiminori Matsuzaki, Akimasa Morihata, Kento Emoto, Zhenjiang Hu
    Parallel Dynamic Programming using Data-Parallel Skeletons
    In Proceedings of the 22nd JSSST Conference, Sep, 2005.
18. Kiminori Matsuzaki, Zhenjiang Hu, Kazuhiko Kakehi, Masato Takeichi
    Systematic Derivation of Tree Contraction Algorithms
    In Parallel Processing Letters, Vol. 15, No. 3, pp. 321-336, 2005.
    
    • Kiminori Matsuzaki, Zhenjiang Hu, Kazuhiko Kakehi, Masato Takeichi
      Systematic Derivation of Tree Contraction Algorithms
      In Proceedings of the 4th International Workshop on Constructive Methods for Parallel Programming (CMPP 2004), 14th July, 2004, Technical Report of Westfalische wilhelms-univeersitat munster, pp. 109-123.
      
      • 松崎 公紀, 筧 一彦, 胡 振江, 武市 正人
        Systematic Derivation of Tree Contraction Algorithms
        第7回プログラミングおよびプログラミング言語ワークショップ (PPL 2005), カテゴリ2 (CMPP 2004の論文の紹介)
        
19. Kiminori Matsuzaki, Kazuhiko Kakehi, Hideya Iwasaki, Zhenjiang Hu, Yoshiki Akashi
    A Fusion-Embedded Skeleton Library
    In Proceedings of Annual European Conference on Parallel Processing (Euro-Par 2004), 31th August - 3rd September, 2004, Lecture Notes in Computer Science 3149, pp. 644-653, Springer Verlag.
    
    • 明石 良樹, 松崎 公紀, 岩崎 英哉, 筧 一彦, 胡 振江
      最適化機構を持つC++並列スケルトンライブラリ
      コンピュータソフトウェア, Vol. 22, No. 3, pp. 214-222, 2005
    • 明石 良樹, 松崎 公紀, 岩崎 英哉, 筧 一彦, 胡 振江
      最適化機構を持つC++並列スケルトンライブラリ
      日本ソフトウェア科学会第21回大会 論文集, 東京工業大学, 2004年9月15日-17日
20. Kiminori Matsuzaki, Kazuhiko Kakehi, Zhenjiang Hu, Masato Takeichi
    Parallelizing Polytypic Programs with Accumulations
    Proceedings of 20th JSSST Conference, 2003
21. Kiminori Matsuzaki, Zhenjiang Hu, Masato Takeichi
    Parallelization with Tree Skeletons
    In Proceedings of the International Conference on Parallel and Distributed Computing (Euro-Par 2003), Klagenfurt, Austria, 26th - 29th August 2003, Lecture Notes in Computer Science, pp. 789-798, Springer Verlag.
    
    • Kiminori Matsuzaki, Zhenjiang Hu, Masato Takeichi
      Parallelization with Tree Skeletons
      Technical Report METR 2003-21, Mathematical Informatics, Graduate School of Information Science and Technology, University of Tokyo, 2003.
      
    • Kiminori Matsuzaki
      Parallelization with Tree Skeletons
      Presentation at Workshop on Robust Software Construction (WRSC 2003), Hayama, Kanagawa, Feb 2003.
      
22. 松崎 公紀, 岩崎 英哉
    プログラム設計を支援する学習環境Soegi
    夏のプログラミング・シンポジウム 報告集, pp.57-63, 2001.

研究外活動

• ACM ICPC プログラミングコンテスト
  2002年のアジア地区予選 金沢大会において総合7位 (Javaチャレンジ 2位) という成果を収めました.
• ARIEL (学科内サークル)
  学生対抗バーチャルリアリティコンテスト (IVRC'99) において, 「バーチャル金魚すくい」という作品で優勝しました.

研究室内部向け

• 時間割・予定
• ポストスクリプトプリンタで片面・両面印刷