KAAPI: A thread scheduling runtime system for data flow computations on cluster of multi-processors

ABSTRACT

The high availability of multiprocessor clusters for computer science seems to be very attractive to the engineer because,at a first level, such computers aggregate high performances. Nevertheless, obtaining peak performances on irregular applications such as computer algebra problems remains a challenging problem. The delay to access memory is non uniform and the irregularity of computations requires to use scheduling algorithms in order to automatically balance the workload among the processors.

This paper focuses on the runtime support implementation to exploit with great efficiency the computation resources of a multiprocessor cluster. The originality of our approach relies on the implementation of an efficient work-stealing algorithm for a macro data flow computation based on minor extension of POSIX thread interface.

REFERENCES

• 1: J. Allard, S. Cotin, F. Faure, P.-J. Bensoussan, F. Poyer, C. Duriez, H. Delingette, and L. Grisoni. Sofafian open source framework for medical simulation. In Medicine Meets Virtual Reality (MMVR), 2007.
• 2: Thomas E. Anderson , Brian N. Bershad , Edward D. Lazowska , Henry M. Levy, Scheduler activations: effective kernel support for the user-level management of parallelism, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.95-109, October 13-16, 1991, Pacific Grove, California, United States
• 3: X. Besseron, S. Jafar, T. Gautier, and J.-L. Roch. Cck: An improved coordinated checkpoint/rollback protocol for data flow applications in kaapi. In IEEE, editor,Proceedings of the IEEE Conference on Information and Communication Technologies (ICTTA '06):from Theory to Applications, pages 3353--3358, Damascus, Syria, April 2006.
• 4: Guy E. Blelloch, NESL: A Nested Data-Parallel Language (Version 2.6), Carnegie Mellon University, Pittsburgh, PA, 1993
• 5: R. Blumofe and C. Leiserson. Scheduling multithreaded computations by work stealing. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico., pages 356--368, November 1994.
• 6: Robert D. Blumofe , Philip A. Lisiecki, Adaptive and reliable parallel computing on networks of workstations, Proceedings of the annual conference on USENIX Annual Technical Conference, p.10-10, January 06-10, 1997, Anaheim, California
• 7: Robert D. Blumofe , Christopher F. Joerg , Bradley C. Kuszmaul , Charles E. Leiserson , Keith H. Randall , Yuli Zhou, Cilk: an efficient multithreaded runtime system, Journal of Parallel and Distributed Computing, v.37 n.1, p.55-69, Aug. 25, 1996 [doi>10.1006/jpdc.1996.0107 ]
• 8: Robert D. Blumofe , Charles E. Leiserson, Space-Efficient Scheduling of Multithreaded Computations, SIAM Journal on Computing, v.27 n.1, p.202-229, Feb. 1998 [doi>10.1137/S0097539793259471]
• 9: D. E. Culler , Arvind, Resource requirements of dataflow programs, Proceedings of the 15th Annual International Symposium on Computer architecture, p.141-150, May 30-June 02, 1988, Honolulu, Hawaii, United States
• 10: Vincent Danjean , Roland Gillard , Serge Guelton , Jean-Louis Roch , Thomas Roche, Adaptive loops with kaapi on multicore and grid: applications in symmetric cryptography, Proceedings of the 2007 international workshop on Parallel symbolic computation, July 27-28, 2007, London, Ontario, Canada [doi>10.1145/1278177.1278185]
• 11: J.-G. Dumas, T. Gautier, M. Giesbrecht, P. Giorgi, B. Hovinen, E. Kaltofen, B. D. Saunders, W. J. Turner, and G. Villard. Linbox: A generic library for exact linear algebra. In Proceedings of the International Congress of Mathematical Software (ICMS '02), Beijing,China, pages 40--50. World Scientific, 2002.
• 12: P.Fatourou and P. G. Spirakis. Efficient scheduling of strict multithreaded computations. Theory of Computing Systems, 33(3): 173--232, 2000.
• 13: H. Franke, R. Russell, and M. Kirkwood. Fuss, futexes and furwocks: Fast userlevel locking in linux. In Proceedings of the Ottawa Linux Symposium, 2002.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Distributed programming

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

General Terms:
Algorithms, Experimentation, Performance

Keywords:
cluster, data flow, multi-core, multi-processor, work-stealing