Abstract
A number of interesting properties for scheduling and/or cost estimation arise when using parallel programming models that restrict the topology of a program’s task graph to an SP (series-parallel) form. A critical question however, is to what extent the ability to exploit parallelism is compromised when only SP coordination structures are allowed. This paper presents new application parameters which are key factors to predict this loss of parallelism at both language modeling and program execution levels, for shared-memory architectures. Our results indicate that a wide range of parallel computations can be expressed using a structured coordination model with a loss of parallelism that is small and predictable.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
R.D. Blumofe and C.E. Leiserson. Scheduling multithreaded computations by work stealing. In Proc. Annual Symposium on FoCS, pages 356–368, nov 1994.
J. Darlington, Y. Guo, H.W. To, and J. Yang. Functional skeletons for parallel coordination. In Europar’95, LNCS, pages 55–69, 1995.
L. Finta, Z. Liu, I. Milis, and E. Bampis. Scheduling UET-UCT series-parallel graphs on two processors. DIMACS Series in DMTCS, 162:323–340, aug1996.
A.J.C. vanGemund. The importance of synchronization structure in parallel program optimization. In Proc. 11th ACM ICS, pages 164–171, Vienna, July 1997.
A. González-Escribano, V. Cardeñoso, and A.J.C. vanGemund. On the loss of parallelism by imposing synchronization structure. In Proc. 1st Euro-PDS Int’l Conf. on Parallel and Distributed Systems, pages 251–256, Barcelona, July 1997.
A. González-Escribano, V. Cardeñoso, and A.J.C. vanGemund. Loss of parallelism on highly regular DAG structures as a result of SP-ization. Technical Report 1-60340-44(1999)-04, TU Delft, The Netherlands, July1999.
A. González-Escribano, A.J.C. vanGemund, V. Cardeñoso-Payo, H-X. Lin, and V. Vaca-Díez. Expressiveness versus optimizability in coordinating parallelism. In Parallel Computing, Fundamentals & Applications. Proc. Int. Conf. ParCo99, pages 526–533, Delft (The Netherlands), August 1999. Imperial College Press.
Paul Graham. OpenMP: A parallel programming model for shared memory architecture. Technical-watch report, EPCC, The University of Edinburgh, Mar1999. available from http://www.epcc.ed.ac.uk/epcc-tec/documents/.
E.J. Gumbel. Statistical Theory of Extreme Values (Main Results), chapter 6, pages 56–93. Wiley Publications in Statistics. John Wiley & Sons, 1962.
C.W. Kessler. NestStep: nested parallelism and virtual shared memory for the BSP model. In Int. Conf. on Parallel and Distrbuted Processing Techniques and Applications (PDPTA’99), Las Vegas (USA), June–July 1999.
X. Martorell, E. Ayguadé, N. Navarro, J. Corbalán, M.González, and J. Labarta. Thread fork/join techniques for multi-level parallelism exploitation in NUMA mul-tiprocessors. In ICS’99, pages 294–301, Rhodes, Greece, 1999.
OpenMP organization. www. on http://www.openmp.org.
PGamma: Measuring the performance impact of SP programming: Resources and tools. WWW. on http://www.infor.uva.es/pnal/arturo/pgamma.
R.A. Sahner and K.S. Trivedi. Performance and reliability analysis using directed acyclic graphs. IEEE Trans. on Software Eng., 13(10):1105–1114, Oct 1987.
D.B. Skillicorn. A cost calculus for parallel functional programming. Journal of Parallel and Distributed Computing, 28:65–83, 1995.
D.B. Skillicorn and D. Talia. Models and languages for parallel computation. ACM Computing Surveys, 30(2):123–169, June 1998.
A. Vaca-Díez. Tools and techniques to assess the loss of parallelism when imposing synchronization structure. Technical Report1-68340-28(1999)02, TU Delft, Mar 1999.
L.G. Valiant. A bridging model for parallel computation. C.ACM, 33(8):103–111, Aug 1990.
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
González-Escribano, A., van Gemund, A.J.C., Cardeñoso-Payo, V., Alonso-López, J., Martín-García, D., Pedrosa-Calvo, A. (2001). Measuring the Performance Impact of SP-Restricted Programming in Shared-Memory Machines. In: Palma, J.M.L.M., Dongarra, J., Hernández, V. (eds) Vector and Parallel Processing — VECPAR 2000. VECPAR 2000. Lecture Notes in Computer Science, vol 1981. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44942-6_10
Download citation
DOI: https://doi.org/10.1007/3-540-44942-6_10
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-41999-0
Online ISBN: 978-3-540-44942-3
eBook Packages: Springer Book Archive