Hint

Swipe to navigate through the chapters of this book

2012 | OriginalPaper | Chapter

1. Basic Concepts in Parallel Algorithms and Parallel Programming

Author: Yosi Ben-Asher

Publisher: Springer London

Published in: Multicore Programming Using the ParC Language

» Get access to the full version

Abstract

The world of parallel processing is complex and combines many different ideas together. We first consider the question what is a parallel machine? We answer this question by presenting a model to build parallel machines. Separately, we consider the need to define what “parallel programs” are. We use partial orders to define the notion of parallel programs and show how they can be potentially executed on parallel machines.

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

We assume that the reader is familiar with the notion of Context Free Grammars and derivations.

Beame, P., Astad, J.: Optimal bounds for decision problems on the CRCW PRAM. In: Ann. Symp. Theory of Computing, pp. 83–93 (1987)

Ben-Asher, Y., Farchi, E.: Using true concurrency to model execution of parallel programs. Int. J. Parallel Program. 22(4), 375–407 (1986) MathSciNetCrossRef

Ben-Asher, Y., Newman, I.: Geometric approach for optimal routing on mesh with buses. In: Proceedings IEEE Seventh IEEE Symposium on Parallel and Distributed Processing, 1995, pp. 145–152. IEEE, New York (2002). ISBN 0818671955

Ben-Asher, Y., Peleg, D., Ramaswami, R., Schuster, A.: The power of reconfiguration. J. Parallel Distrib. Comput. 13(2) (1991). Special issue on Massively Parallel Computation

Bermond, J.C., Fourneau, J.M., Jean-Marie, A.: Equivalence of multistage interconnection networks. Inf. Process. Lett. 26(1), 45–50 (1987) CrossRef

Blake, J.T., Trivedi, K.S.: Multistage interconnection network reliability. IEEE Trans. Comput. 38(11), 1600–1604 (1989) CrossRef

Dietzfelbinger, M., auf der Heide, F.: High performance universal hashing, with applications to shared memory simulations. In: Data Structures and Efficient Algorithms. Lecture Notes in Computer Science, vol. 594, pp. 250–269 (1992) CrossRef

Fiduccia, C.M.: Bused hypercubes and other pin-optimal networks. IEEE Trans. Parallel Distrib. Syst. 3(1), 14–24 (1992) CrossRef

Fox, G., Johnson, M., Lyzenga, G., Otto, S., Salmon, J., Walker, D.: Solving Problems on Concurrent Processors. Vol. I: General Techniques and Regular Problems. Prentice-Hall, New York (1988)

Iwama, K., Miyano, E.: Oblivious routing algorithms on the mesh of buses. In: Parallel Processing Symposium, pp. 721–727 (1997)

JáJá, J.: An Introduction to Parallel Algorithms. Addison Wesley Longman, Redwood City (1992). ISBN 0201548569 MATH

Kruskal, C.P., Snir, M.: The performance of multistage interconnection networks for multiprocessors. IEEE Trans. Comput. C-32(12), 1091–1098 (1983) CrossRef

Kruskal, C.P., Rudolph, L., Snir, M.: A complexity theory of efficient parallel algorithms. Theor. Comput. Sci. 71(1), 95–132 (1990) MathSciNetMATHCrossRef

Mourad, A., Özden, B., Malek, M.: Comprehensive testing of multistage interconnection networks. IEEE Trans. Comput. 40(8), 935–951 (1991) CrossRef

Reif, J.H.: Synthesis of Parallel Algorithms. Morgan Kaufmann, San Francisco (1993). ISBN 155860135X

Sheu, J.-P., Chen, W.-T.: Performance analysis of multiple bus interconnection networks with hierarchical requesting model. In: Intl. Conf. Distributed Comput. Syst., pp. 138–144 (1988)

Siegel, H.J.: Interconnection networks for SIMD machines. Computer 12(6), 57–65 (1979) CrossRef

Suel, T.: Permutation routing and sorting on meshes with row and column buses. Parallel Process. Lett. 5(1), 63–80 (1995) CrossRef

Title

Basic Concepts in Parallel Algorithms and Parallel Programming

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_1

Author:

Yosi Ben-Asher

Publisher

Springer London

Sequence number

Chapter number

Chapter 1