Abstract
Parallel programs executing on non-dedicated SMPs should be adaptive, that is, they should be able to execute on a dynamically varying environment without loss of efficiency. This paper defines a unified set of services, implemented at the operating system level, which can be used to embed adaptability in any thread-based programming paradigm. These services meet simultaneously three goals: they are highly efficient; they are orthogonal and transparent to the multithreading programming model and its API; and they are non-intrusive, that is, they do not compromise the native operating system’s resource management policies. The paper presents an implementation and evaluation of these services in the Linux kernel, using two popular multithreading programming systems, namely OpenMP and Cilk. Our experiments show that using these services in a multiprogrammed SMP yields a throughput improvement of up to 41.2%.
This work has been carried out while the second author was with the High Performance Information Systems Laboratory, University of Patras, Greece.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
N. Arora, R. Blumofe, and G. Plaxton. Thread scheduling for Multiprogrammed Multiprocessors. In Proc. of the 10th ACM Symposium on Parallel Algorithms and Architectures, pages 119–129, Puerto Vallarta, Mexico, June 1998.
M. Frigo, C. Leiserson, and K. Randall. The Implementation of the Cilk-5 Multithreaded Language. In Proc. of the 1998 ACM SIGPLAN Conference on Programming Language Design and Implementation, Montreal, Canada, June 1998.
A. Gupta, A. Tucker, and S. Urushibara. The Impact of Operating System Scheduling Policies and Synchronization Methods on the Performance of Parallel Applications. In Proc. of the 1991 ACM Conference on Measurement and Modeling of Computer Systems, pages 120–132, San Diego, USA, May 1991.
IEEE. Portable Operating System Interface (POSIX)-Part 1: System Application Program Interface (API) [C Language], 1996 edition, 1996.
H. Jin, M. Frumkin, and J. Yan. The OpenMP Implementation of NAS Parallel Benchmarks and its Performance. Technical report nas-99-011, NASA Ames Research Center, 1999.
L. Kontothanassis, R. Wisniewski, and M. Scott. Scheduler-Conscious Synchronization. ACM Transactions on Computer Systems, 15(1):3–40, February 1997.
X. Leroy. The LinuxThreads library home page. http://pauillac.inria.fr/~xleroy/linuxthreads/index.html.
D. Nikolopoulos, C. Antonopoulos, I. Venetis, P. Hadjidoukas, E. Polychronopoulos, and T. Papatheodorou. Achieving Multiprogramming Scalability on Intel SMP Platforms: Nanothreading in the Linux Kernel. In Proc. of the 1999 Parallel Computing Conference, pages 623–630, Delft, The Netherlands, August 1999.
OpenMP A. R. B. OpenMP Fortran Application Program Interface, Version 2.0, 2000 edition, November 2000.
D. Papadopoulos. Hood: A User-Level Thread Library for Multiprogrammed Multiprocessors. Master’s thesis, Department of Computer Sciences, University of Texas at Austin, August 1998.
C. Polychronopoulos, N. Bitar, and S. Kleiman. Nanothreads: A User-Level Threads Architecture. Technical report 1297, CSRD, University of Illinois at Urbana-Champaign, 1993.
E. Polychronopoulos, D. Nikolopoulos, T. Papatheodorou, N. Navarro, and X. Martorell. An Efficient Kernel-Level Scheduling Methodology for Multiprogrammed Shared Memory Multiprocessors. In Proc. of the 12th Int. Conference on Parallel and Distributed Computing Systems, USA, August 1999.
M. Sato, S. Satoh, K. Kusano, and Y. Tanaka. Design of OpenMP Compiler for an SMP Cluster. In Proc. of the 1st European Workshop on OpenMP, pages 32–39, Lund, September 1999.
A. Tucker and A. Gupta. Process Control and Scheduling Issues for Multipro-grammed Shared-memory Multiprocessors. In Proc. of the 12th ACM Symposium on Operating System Principles, Litchfield Pk., USA, December 1989.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Venetis, I.E., Nikolopoulos, D.S., Papatheodorou, T.S. (2001). A Transparent Operating System Infrastructure for Embedding Adaptability to Thread-Based Programming Models. In: Sakellariou, R., Gurd, J., Freeman, L., Keane, J. (eds) Euro-Par 2001 Parallel Processing. Euro-Par 2001. Lecture Notes in Computer Science, vol 2150. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44681-8_75
Download citation
DOI: https://doi.org/10.1007/3-540-44681-8_75
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42495-6
Online ISBN: 978-3-540-44681-1
eBook Packages: Springer Book Archive