Abstract
Lazy task creation (LTC) is an efficient approach for executing divide and conquer parallel programs that has been used in the implementation of Multilisp's future construct. Unfortunately it requires a specialized memory management scheme, in particular for stack frames, which makes it hard to use in the context of conventional languages. We have designed a variant of LTC which has a stack management discipline that is compatible with the semantics of conventional languages. This mechanism, which we call lazy remote procedure call, has been used to implement a parallel variant of C. A first prototype of our system has been ported to shared-memory multiprocessors and network of workstations. Experimental results on a Cray T3D multiprocessor show that good performance can be achieved on several symbolic programs.
Preview
Unable to display preview. Download preview PDF.
References
G. Bilardi and A. Nicolau. Adaptive bitonic sorting: An optimal parallel algorithm for shared-memory machines. SIAM Journal of Computing, 12(2):216–228, April 1989.
D. Bobrow and B. Wegbreit. A model and stack implementation of multiple environments. Communications of the ACM, 16(10):591–603, 1973.
D. Callahan and B. Smith. A future-based parallel language for a general-purpose highly-parallel computer. In Papers from the Second Workshop on Languages and Compilers for Parallel Computing, pages 95–113. University of Illinois at Urbana-Champaign, 1989.
M. Feeley, M. Turcotte, and G. Lapalme. Using Multilisp for solving constraint satisfaction problems: an application to nucleic acid 3D structure determination. Lisp and Symbolic Computation, 7(2/3):231–246, 1994.
M. Feeley. An Efficient and General Implementation of Futures on Large Scale Shared-Memory Multiprocessors. PhD thesis, Brandeis University Department of Computer Science, 1993. Available as publication #869 from département d'informatique et recherche opérationnelle de l'Université de Montréal.
M. Feeley. Polling efficiently on stock hardware. In Proceedings of the 1993 ACM Conference on Functional Programming Languages and Computer Architecture, 1993.
R. Halstead. Multilisp: A language for concurrent symbolic computation. In ACM Trans. on Prog. Languages and Systems, pages 501–538, October 1985.
P. H. Hartel, M. Feeley, M. Alt, L. Augustsson, P. Baumann, M. Beemster, E. Chailloux, C. H. Flood, W. Grieskamp, J. H. G. Van Groningen, K. Hammond, B. Hausman, M. Y. Ivory, R. E. Jones, P. Lee, X. Leroy, R. D. Lins, S. Loosemore, N. Röjemo, M. Serrano, J.-P. Talpin, J. Thackray, S. Thomas, P. Weis, and P. Wentworth. Benchmarking implementations of functional languages with “pseudoknot” a float-intensive benchmark. To appear in Journal of Functional Programming, 1996.
M. Katz and D. Weise. Continuing into the future: on the interaction of futures and first-class continuations. In Proceedings of the 1990 ACM Conference on Lisp and Functional Programming, Nice, France, June 1990.
E. Mohr. Dynamic Partitioning of Parallel Lisp Programs. PhD thesis, Yale University Department of Computer Science, October 1991.
R. S. Nikhil. Cid: A parallel, shared-memory C for distributed-memory machines. In Languages and Compilers for Parallel Computing, pages 376–390, August 1994.
R. W. Numrich. The Cray T3D Address Space and How to Use It. Cray Research Inc., 1994.
A. Rogers, M. C. Carlisle, J. H. Reppy, and L. J. Hendren. Supporting dynamic data structures on distributed-memory machines. ACM Transactions on Programming Languages and Systems, 17(2):233–263, March 1995.
D. B. Wagner and B. G. Calder. Leapfrogging: A portable technique for implementing efficient futures. In Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, May 1993.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Feeley, M. (1996). Lazy remote procedure call and its implementation in a parallel variant of C. In: Ito, T., Halstead, R.H., Queinnec, C. (eds) Parallel Symbolic Languages and Systems. PSLS 1995. Lecture Notes in Computer Science, vol 1068. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0023053
Download citation
DOI: https://doi.org/10.1007/BFb0023053
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61143-1
Online ISBN: 978-3-540-68332-2
eBook Packages: Springer Book Archive