SkeTo Project

Contents

Links

What is SkeTo?

SkeTo (Skeletons in Tokyo) is a constructive parallel skeleton library written in C++ with MPI intended for distributed environments such as PC clusters. SkeTo provides data parallel skeletons for lists (distributed one-dimensional arrays), matrices (distributed two-dimensional arrays), and trees (distributed binary trees). SkeTo enables users to write parallel programs as if they were sequential, since the distribution, gathering, and parallel computation of data are concealed within constructors of data types or definitions of parallel skeletons. This is the results of the research of the "SkeTo Project".

The latest version of SkeTo (version 1.5) does not include tree skeletons due to the delay of the restructuring process of the entire code. They will be available in the near future. To use tree skeletons, please download the older version (version 0.21).

SkeTo is named after the Japanese word "Suketto", whose meaning is helper or supporter, in the hope that SkeTo library will help programmers easily develop efficient parallel programs.

NEWS

SkeTo Project

"SkeTo Project" is a research project working on skeletal parallelism (or algorithmic skeletons).

We are studying parallel skeletons based on the constructive algorithmics. The main contributions of our project are as follows:

• Parallel Skeletons for Several Data Structures: The constructive algorithms provides a general handling of various data structures. Based on this, we are studying parallel skeletons for lists, matrices, and trees.
• Optimization Mechanism for Skeletal Programs: A program with many skeletons may lead undesirable overheads. We are studying an optimization mechanism of the skeletal programs, based on the program transformation techniques.

This project has been partially supported by:

• HPC Systems Inc.,
• PRESTO program by Japan Science and Technology Agency (JST),
• Grant-in-Aid for Scientific Research (B), No. 17300005, Japan Society for the Promotion of Science, and
• Grant-in-Aid for Scientific Research (C), No. 20500029, Japan Society for the Promotion of Science.

Results

We have proposed several fundamental parallel skeletons for data structures lists, matrices, and trees based on the BMF (Bird-Meertens Formalism), which provides a concise interface of skeletons, and shown their efficient implementations. We have also formalized and proposed the optimization mechanism by the fusion transformation over parallel skeletons on lists.

We implemented our ideas as a parallel skeleton library. The current version of our parallel skeleton library includes several data parallel skeletons for lists, matrices, and trees. The optimization mechanism is now implemented by the C++-template technique called expression templates. Our parallel skeleton library is available from the Download page.

Members

SkeTo is a joint project of The University of Tokyo, The University of Electro-Communications, National Institute of Informatics, and Kochi University of Technology in Japan.

Current Members

• Kento EMOTO (The University of Tokyo)
• Zhenjiang HU (National Institute of Informatics)
• Hideya IWASAKI (The University of Electro-Communications)
• Yu LIU (National Institute of Informatics)
• Kiminori MATSUZAKI (Kochi University of Technology)
• Shigeyuki SATO (The University of Electro-Communications)

Old Members

Yoshiki AKASHI, Kousuke ARIMA, Yu ISHIDO, Kazuhiko KAKEHI, Yuki KARASAWA, Kazutoshi KARIYA, Shunji KINOSHITA, Yoshiaki NOMURA, Noriyuki OHKAWA, Haruto TANNO, Masato TAKEICHI

Publications

2013

• Kento Emoto, Kiminori Matsuzaki
  An Automatic Fusion Mechanism for Variable-Length List Skeletons in SkeTo.
  METR 2013-04, Department of Mathematical Engineering and Information Physics, The University of Tokyo, 2013.)

2010

• Kiminori Matsuzaki, Kento Emoto:
  Lessons from Implementing the BiCGStab Method with SkeTo Library
  Fourth International Workshop on High-level Parallel Programming and Applications (HLPP 1010), pp.15-24, 2010.
• Kiminori Matsuzaki, Kento Emoto:
  Implementing Fusion-Equipped Parallel Skeletons by Expression Templates
  Implementation and Application of Functional Languages: 21st International Symposium, IFL 2009, Revised Selected Papers, Lecture Notes in Computer Science 6041, Springer, pp.72-89, 2010.

2009

• Shigeyuki Sato, Hideya Iwasaki:
  A Skeletal Parallel Framework with Fusion Optimizer for GPGPU Programming
  7th Asian Symposium on Programming Languages and Systems (APLAS 2009), Lecture Notes in Computer Science 5904, Springer, pp.79-94, 2009.
• Kiminori Matsuzaki, Kento Emoto:
  Implementing Fusion-Equipped Parallel Skeletons by Expression Templates
  Draft Proceedings of the 21st International Symposium on Implementation and Application of Functional Languages (IFL 2009), Technical Report: SHU-TR-CS-2009-09-1, Seton Hall University, pp.100-115, 2009.
  (Revised version appears as above.)
• Yuki Karasawa, Hideya Iwasaki:
  A Parallel Skeleton Library for Multi-core Clusters
  38th International Conference on Parallel Processing (ICPP 2009), pp.84-91, 2009.
• Haruto Tanno, Hideya Iwasaki:
  Parallel Skeletons for Variable-length Lists in SkeTo Skeleton Library
  15th International Euro-Par Conference (Euro-Par 2009), Lecture Notes in Computer Science 5704, Springer, pp.666-677, 2009.

2008

• Yuki Karasawa, Hideya Iwasaki:
  Parallel Skeletons for Sparse Matrices in SkeTo Skeleton Library
  IPSJ Transactions on Programming, Vol.49, No.SIG 3 (PRO 36), pp.1-15, 2008.
  (PDF file of this paper is available also from the IMP page.)

2007

• Kento Emoto, Zhenjiang Hu, Kazuhiko Kakehi, Masato Takeichi:
  A Compositional Framework for Developing Parallel Programs on Two Dimensional Arrays
  International Journal of Parallel Programming, Vol.35, No.6, pp.615-658, 2007.
• Kento Emoto, Kiminori Matsuzaki, Zhenjiang Hu, Masato Takeichi:
  Domain-Specific Optimization Strategy for Skeleton Programs
  13th International Euro-Par Conference (Euro-Par 2007), Lecture Notes in Computer Science 4641, Springer, pp.705-714, 2009.
• Kiminori Matsuzaki:
  Efficient Implementation of Tree Accumulations on Distributed-Memory Parallel Computers
  Fourth International Workshop on Practical Aspects of High-level Parallel Programming (PAPP 2007), part of The International Conference on Computational Science (ICCS 2007), Lecture Notes in Computer Science 4488, Springer, pp.609-616, 2007.
• Kazuhiko Kakehi, Kiminori Matsuzaki, Kento Emoto:
  Efficient Parallel Tree Reductions on Distributed Memory Environments
  Fourth International Workshop on Practical Aspects of High-level Parallel Programming (PAPP 2007), part of The International Conference on Computational Science (ICCS 2007), Lecture Notes in Computer Science 4488, Springer, pp.601-608, 2007.

2006

• Kiminori Matsuzaki, Zhenjiang Hu, Masato Takeichi:
  Parallel Skeletons for Manipulating General Trees
  Parallel Computing, Vol.32, No.7-8, pp.590-603, 2006.
  
• Kento Emoto, Kiminori Matsuzaki, Zhenjiang Hu, Masato Takeichi:
  Surrounding Theorem: Developing Parallel Programs for Matrix-Convolutions
  12th International Euro-Par Conference (Euro-Par 2006), Lecture Notes in Computer Science 4128, Springer, pp.605-614, 2006.
• Kiminori Matsuzaki, Zhenjiang Hu, Masato Takeichi:
  Towards Automatic Parallelization of Tree Reductions in Dynamic Programming
  18th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2006), pp.39-48, 2006.
  
• Kiminori Matsuzaki, Kento Emoto, Hideya Iwasaki, Zhenjiang Hu:
  A Library of Constructive Skeletons for Sequential Style of Parallel Programming (Invited Paper)
  First International Conference on Scalable Information Systems (InfoScale 2006), 2006.
  

2005

• Kiminori Matsuzaki, Zhenjiang Hu, Kazuhiko Kakehi, Masato Takeichi:
  Systematic Derivation of Tree Contraction Algorithms
  Parallel Processing Letters, Vol.15, No.3, pp.321-336, 2005.
  

2004

• Hideya Iwasaki, Zhenjiang Hu:
  A New Parallel Skeleton for General Accumulative Computations
  International Journal of Parallel Programming, Vol.32, No.5, pp.389-414, 2004.
  
• Kiminori Matsuzaki, Kazuhiko Kakehi, Hideya Iwasaki, Zhenjiang Hu, Yoshiki Akashi:
  A Fusion-Embedded Skeleton Library
  10th International Euro-Par Conference (Euro-Par 2004), Lecture Notes in Computer Science 3149, Springer, pp.644-653, 2004.
  
• Kiminori Matsuzaki, Kazuhiko Kakehi, Zhenjiang Hu, Masato Takeichi:
  Systematic Derivation of Tree Contraction Algorithms
  4th International Workshop on Constructive Methods for Parallel Programming (CMPP 2004), Technical Report of Westfalische wilhelms-univeersitat munster, pp.109-123.
  (Revised version appears as above.)

2003

• Kazuhiko Kakehi, Zhenjiang Hu, Masato Takeichi:
  List Homomorphism with Accumulation
  4th International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing (SNPD 2003), pp.250-259, 2003.
  
• Kiminori Matsuzaki, Zhenjiang Hu, Masato Takeichi:
  Parallelization with Tree Skeletons
  9th International Euro-Par Conference (Euro-Par 2003), Lecture Notes in Computer Science 2790, Springer, pp.789-798, 2003.
  (An extended version appears as Mathematical Engineering Technical Report METR 2003-21, Department of Mathematical Engineering and Information Physics, The University of Tokyo, 2003.)