Kento EMOTO's Home Page

Research Topics

• Skeletal Parallel Programing on Two-Dimensional Arrays
  We have been working on "Skeletal Parallelism", in which we are encouraged to build efficient parallel programs by composing the ready-made components, called skeletons. Computations on two-dimensional arrays, such as matrix computations, image processing, and relational database managements, are one of the most fundamental and ubiquitous computations in computational science and its vast application areas. However, development of efficient parallel programs on two-dimensional arrays is known to be hard. Therefore, we have been studying (1) a design of general parallel skeletons, i.e., useful basic patterns of parallel computation on two-dimensinal arrays, (2) implementation of such skeletons on various parallel computer architectures, and (3) a methodology to derive efficient parallel program systematically or automatically from ones naively composed with skeletons.
• Generator-based parallel programming
  We are trying to develop a novel parallel programming style called generator-based parallel programming, in which we develop parallel programs naively using generators, and get efficient execution via drastic optimization driven by generators based on mathematical properties of computation objects. Basically, parallelization of sophisticated sequential programs is very hard, and not necessarily results in good parallel programs. Rather, naively composed parallel programs can be optimized drastically into efficient ones, keeping their parallelism, which enables development of reliable and efficient parallel programs. Therefore, we are studying generators that bring naive generate-and-test parallel programs and their effective optimization based on our theories of skeletons. This research topic is of parallelism oblivious programming, in the sense that programmers do not have to be aware of parallelism and can just concentrate on making naive correct programs with generators that hide parallelism from them.

Research Activities

• SkeTo Project
  We have been developing a practical parallel skeleton library named 'SkeTo', which provides a set of parallel skeletons (basic patterns of common parallel computation) to be composed with each other to form parallel programs naively. Also, we have been trying to implement an optimization mechanism on skeletons within the library.
• Collaboration Work with Sun Microsystems Laboratories on Parallel Programming
  We have been developing growing libraries for reliable, easy parallel programming in Fortress based on our knowledge about skeletal parallel programming. One of the most important features of our libraries is that libraries themselves implement optimization mechanisms to provide efficient execution to naively composed parallel programs. Some results have been included in the standard library of Fortress.

Publications

Refereed Papers

1. 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.
   
2. Kento Emoto, Zhenjiang Hu, Kazuhiko Kakehi, Masato Takeichi
   A Compositional Framework for Developing Parallel Programs on Two Dimensional Arrays
   International Journal of Parallel Programming (IJPP), Volume 35, Number 6, pp. 615-658, Springer, 2007.
3. Yasushi Hayashi, Dongxi Liu, Kento Emoto, Kazutaka Matsuda, Zhenjiang Hu, Masato Takeichi
   A Web Service Architecture for Bidirectional XML Updating
   Joint conference of the 9th Asia-Pacific Web Conference and the 8th International Conference on Web-Age Information Management (APWeb/WAIM 2007), pp. 721-732, Huangshan, China, June 16-18, 2007.
   
4. 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.
5. 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.
   
6. 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.
   
7. Zhenjiang Hu, Kento Emoto, Shin-Cheng.Mu, Masato Takeichi
   Bidirectionalizing Tree Transformations
   Workshop on New Approaches to Software Construction (WNASC 2004), The University of Tokyo, Komaba, Tokyo, Japan, September 13-14, 2004. pp.3-22.
   

Presentations/Non-Refereed Papers/Technical Reports

1. 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.
   
2. 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.
   
3. 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.
   
4. 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.
5. 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.
6. Kento Emoto, Zhenjiang Hu, Kazuhiko Kakehi, Masato Takeichi
   A Compositional Framework for Developing Parallel Programs on Two Dimensional Arrays
   Technical Report METR2005-09, Department of Mathematical Informatics, University of Tokyo, 2005.
   

Thesis

1. Kento Emoto
   Homomorphism-based Structured Parallel Programming
   Graduate School of Information Science and Technology, University of Tokyo.
   

Japanese publications are listed in Japanese Page

Other Activities

• Grid Challenge 2006
  Our team took the 7th prize in Grid Challenge 2006.
• Grid Challenge in SACSIS2005
  Our team took the 4th prize in the advanced course and the 5th prize in the beginners' course at Grid Challenge in SACSIS2005.
• ACM ICPC (International Collegiate Programming Contest)
  Our team took the 4th prize (and the 1st prize in Java Challenge) at Kanazawa Regional Contest 2002,
  and the 12th prize (and the 2nd prize in Java Challenge) at Aizu Regional Contest 2003.
• CCFlib
  CCFlib is a library for computation of "Combinatorial Canonical Form (CCF)" of layered mixed matrices, and is available as source tarball(bz2). The source is written in C++.