Top

previous chapter Improving the Performance of Parallel Programs:...

next chapter Working with Sequential Versions

Hint

Swipe to navigate through the chapters of this book

2012 | OriginalPaper | Chapter

6. Compilation Techniques

Author: Yosi Ben-Asher

Publisher: Springer London

Published in: Multicore Programming Using the ParC Language

» Get access to the full version

Abstract

Compiler technologies are crucial for the efficient execution of sequential programs, a statement which is also true for parallel programs. For parallel programs its the operating system performs most of the work. As a result, the overhead for scheduling and distributed shared memory simulation increases. In this chapter we present simple compilation techniques that can be used to guarantee efficient execution of shared memory parallel programs and in particular for multicore machines. We address the difficulties involved with supporting preemption/context-switch of threads in compiled code. Note that preemption is crucial for fair execution of shared memory programs but not necessarily every thread should be preempted repeatedly.

Please log in to get access to this content

To get access to this content you need the following product:

Computer Science Explorer

Purchase now

Addison, C., LaGrone, J., Huang, L., Chapman, B.: Openmp 3.0 tasking implementation in Openuh. In: Open64 Workshop at CGO 2009 (2009)

Ayguade, E., Blainey, B., Duran, A., Labarta, J., Martìnez, F., Martorell, X., Silvera, R.: Is the schedule clause really necessary in Openmp? In: Proceedings of the International Workshop on OpenMP Applications and Tools 2003. Lecture Notes in Computer Science, vol. 2716, pp. 69–83 (2003)

Ben-Asher, A.S.Y., Sibeyn, J.F.: Load balancing: A programmer’s approach or the impact of task-length parameters on the load balancing performance of parallel programs. Int. J. High Speed Comput. 7(2), 303–325 (1995) CrossRef

Berry, G.: Preemption in concurrent systems. In: Foundations of Software Technology and Theoretical Computer Science, pp. 72–93. Springer, Berlin (1993) CrossRef

Brucker, P.: Scheduling Algorithms. Springer, Berlin (2007). ISBN 354069515X MATH

Burdorf, C., Marti, J.: Non-preemptive Time Warp scheduling algorithms. Oper. Syst. Rev. 24(2), 7–18 (1990) CrossRef

Culler, D., Karp, R., Patterson, D., Sahay, A., Schauser, K.E., Santos, E., Subramonian, R., von Eiken, T.: LogP: Towards a realistic model of parallel computation. In: Symp. Principles & Practice of Parallel Programming, pp. 1–12 (1993)

Goldstein, S.C., Schauser, K.E., Culler, D.E.: Lazy threads, stacklets, and synchronizers: Enabling primitives for compiling parallel languages. In: Third Workshop on Languages, Compilers, and Run-Time Systems for Scalable Computers (1995)

Goldstein, S.C., Schauser, K.E., Culler, D.E., Lazy threads: Implementing a fast parallel call. J. Parallel Distrib. Comput. 37, 5–20 (1996) CrossRef

Hauck, E.A., Dent, B.A.: Burroughs’ B6500/B7500 stack mechanism. In: AFIPS Spring Joint Comput. Conf., vol. 32, pp. 245–251 (1968)

Hummel, S.F., Schonberg, E.: Low-overhead scheduling of nested parallelism. IBM J. Res. Dev. 35(5/6), 743–765 (1991) CrossRef

Hummel, S.F., Schonberg, E., Flynn, L.E.: Factoring: A method for scheduling parallel loops. Commun. ACM 35(8), 90–101 (1992) CrossRef

Kearns, J.P., Meier, C.J., Soffa, M.L.: The performance evaluation of control implementations. IEEE Trans. Softw. Eng. 8(2), 89–96 (1982) CrossRef

Krueger, P., Livny, M.: A comparison of preemptive and non-preemptive load distributing. In: Intl. Conf. Distributed Comput. Syst., pp. 123–130 (1988)

Li, T., Baumberger, D., Koufaty, D.A., Hahn, S.: Efficient operating system scheduling for performance-asymmetric multi-core architectures. In: Proceedings of the 2007 ACM/IEEE Conference on Supercomputing, pp. 1–11. ACM, New York (2007) CrossRef

Mogul, J.C., Borg, A.: The effect of context switches on cache performance. In: Intl. Conf. Architect. Support for Prog. Lang. & Operating Syst., pp. 75–84 (1991)

Muchnick, S.S.: Advanced Compiler Design and Implementation. Morgan Kaufmann, San Mateo (1997). ISBN 1558603204

Pittman, T.: The Art of Compiler Design. Prentice Hall, New York (1992) MATH

Polychronopoulos, C.D.: Parallel Programming and Compilers. Kluwer Academic, Dordrecht (1988) MATHCrossRef

Reddy, V.K., Sule, A., Anantaraman, A.: Hyper-threading on the Pentium 4. ECE 792E Advanced Microarchitecture (2002)

Tullsen, D.M., Eggers, S.J., Levy, H.M.: Simultaneous multithreading: Maximizing on-chip parallelism. In: Proceedings of the 22nd Annual International Symposium on Computer Architecture, pp. 392–403. ACM, New York (1995). ISBN 0897916980 CrossRef

Ungerer, T., Robič, B., Šilc, J.: A survey of processors with explicit multithreading. ACM Comput. Surv. 35(1), 29–63 (2003) CrossRef

Weber, W.-D., Gupta, A.: Exploring the benefits of multiple hardware contexts in a multiprocessor architecture: Preliminary results. In: Ann. Intl. Symp. Computer Architecture Conf. Proc., pp. 273–280 (1989) CrossRef

Wilhelm, R.: Compiler Design. Addison-Wesley, Reading (1995) MATH

Title

Compilation Techniques

Book

Multicore Programming Using the ParC Language

Print ISBN: 978-1-4471-2163-3

Electronic ISBN: 978-1-4471-2164-0

https://doi.org/10.1007/978-1-4471-2164-0

DOI

https://doi.org/10.1007/978-1-4471-2164-0_6

Author:

Yosi Ben-Asher

Publisher

Springer London

Sequence number

Chapter number

Chapter 6