Abstract
Cid is a parallel, “shared-memory” superset of C for distributed-memory machines. A major objective is to keep the entry cost low. For users-the language should be easily comprehensible to a C programmer. For implementors-it should run on standard hardware (including workstation farms); it should not require major new compilation techniques (which may not even be widely applicable); and it should be compatible with existing code, run-time systems and tools. Cid is implemented with a simple pre-processor and a library, uses available C compilers and packet-transport primitives, and links with existing libraries.
Cid extends C with MIMD threads and global objects and a common “join-variable” mechanism for dealing with asynchronous actions. The number of threads is arbitrary and may vary dynamically. Any C object can be registered as a global object; the resulting “global pointer” may be used to access the object from any PE (processing element) in a locked, coherent, cached manner. Combining locking with cacheing reduces communication traffic. Being entirely in software, there is the opportunity to vary coherence protocols to suit the application. Distributed data structures may built by linking across PEs with global pointers, or by using Cid's distributed array primitives.
The programmer does no explicit message-passing, but Cid exposes some abstractions of the distributed memory machine. PEs have separate address spaces; threads may be forked to different PEs, but a thread does not span PE boundaries. Threads access remote data only via thread arguments and results, and global objects. Finally, several Cid operations are made explicitly asynchronous, in recognition of the underlying communication and synchronization costs.
In this paper, we describe the language, our first, multi-threaded implementation, some preliminary results, and compare with related systems.
Preview
Unable to display preview. Download preview PDF.
References
A. Agarwal, D. Chaiken, G. D'Souza, K. Johnson, D. Kranz, J. Kubiatowicz, K. Kurihara, B.-H. Lim, G. Maa, D. Nussbaum, M. Parkin, and D. Yeung. The MIT Alewife Machine: A Large-Scale Distributed-Memory Multiprocessor. In Proc. Wkshp. on Multithreaded Computers, Supercomputing '91, Albuquerque NM, November 1991.
Arvind, B. S. Ang, and D. Chiou. StarT the Next Generation: Integrating Global Caches and Dataflow Architecture. In Proc. ISCA '92 Dataflow Workshop, Hamilton Island, Australia, 1994 (expected).
B. N. Bershad, M. J. Zekauskas, and W. A. Sawdon. The Midway Distributed Memory System. Technical Report CMU-CS-93-119, School of Computer Science, Carnegie Mellon University, March 1993.
M. C. Carlisle, A. Rogers, J. H. Reppy, and L. J. Hendren. Early Experience with Olden. In Proc. 6th Ann. Wkshp. on Languages and Compilers for Parallel Computing, Portland OR, Springer-Verlag LNCS 768, pages 1–20, August 12–14 1993.
D. Chaiken, C. Fields, K. Kurihara, and A. Agarwal. Directory-based Cache Coherence in Large-Scale Multiprocessors. IEEE Computer, 23(6):49–59, June 1990.
D. E. Culler, A. Dusseau, S. C. Goldstein, S. Lumetta, T. von Eicken, and K. Yelick. Parallel Programming in Split-C. In Proc. Supercomputing 93, Portland OR, November 1993.
D. E. Culler, A. Sah, K. E. Schauser, T. von Eicken, and J. Wawrzynek. Fine-grain Parallelism with Minimal Hardware Support: A Compiler-Controlled Threaded Abstract Machine. In 4th Intl. Conf. on Architectural Support for Programming Languages and Operating Systems, pages 164–175, April 1991.
R. Das, M. Uysal, J. Saltz, and Y.-S. Hwang. Communication Optimizations for Irregular Scientific Computations on Distributed Memory Architectures. Technical Report CS-TR-3163, U. Maryland Computer Science, October 1993.
M. Halbherr, Y. Zhou, and C. F. Joerg. MIMD-style Parallel Programming Based on Continuation-Passing Threads. Technical Report CSG Memo 355, MIT Laboratory for Computer Science, March 7 1994.
R. H. Halstead. Multilisp: A Language for Concurrent Symbolic Computation. ACM Trans. on Programming Languages and Systems, 7(4):501–539, October 1985.
High Performance Fortran Forum. High Performance Fortran: Language Specification, Version 1.0, May 3 1993. Anonymous ftp: titan.cs.rice.edu.
L. V. Kale. Parallel Programming with CHARM: An Overview. Technical Report 93-8, Dept. of Computer Science, University of Illinois at Urbana-Champaign, 1993.
J. Kuskin, D. Ofelt, M. Heinrich, J. Heinlein, R. Simoni, K. Gharachorloo, J. Chapin, D. Nakahira, J. Baxter, M. Horowitz, A. Gupta, M. Rosenblum, and J. Hennessy. The Stanford FLASH Multiprocessor. In Proc. ISCA 94, Chicago IL, April 1994.
D. Lenoski, J. Laudon, K. Gharachorloo, W.-D. Weber, A. Gupta, J. Hennessy, M. Horowitz, and M. S. Lam. The Stanford DASH Multiprocessor. IEEE Computer, pages 63–79, March 1992.
R. S. Nikhil. Id (Version 90.1) Reference Manual. Technical Report CSG Memo 284-2, MIT Laboratory for Computer Science, 545 Technology Square, Cambridge MA 02139, USA, July 15 1991.
R. S. Nikhil. A Multithreaded Implementation of Id using P-RISC Graphs. In Proc. 6th Ann. Wkshp. on Languages and Compilers for Parallel Computing, Portland, Oregon, Springer-Verlag LNCS 768, pages 390–405, August 12–14 1993.
S. K. Reinhardt, J. R. Larus, and D. A. Wood. Tempest and Typhoon: User-Level Shared Memory. In Proc. ISCA 94, Chicago IL, April 1994.
B. Totty and D. A. Reed. Dynamic Object Management for Distributed Data Structures. In Proc. Supercomputing 92, pages 692–701, November 1992.
T. von Eicken, D. E. Culler, S. C. Goldstein, and K. E. Schauser. Active Messages: a Mechanism for Integrated Communication and Computation. In Proc. 19th. Ann. Intl. Symp. on Computer Architecture, Australia, pages 256–266, May 1992.
D. A. Wood, S. Chandra, B. Falsafi, M. D. Hill, J. R. Larus, A. R. Lebeck, J. C. Lewis, S. Mukerjee, S. Palacharla, and S. K. Reinhardt. Mechanisms for Cooperative Shared Memory. In Proc. 21st ISCA, San Diego, CA, May 1993.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Nikhil, R.S. (1995). Cid: A parallel, “shared-memory” C for distributed-memory machines. In: Pingali, K., Banerjee, U., Gelernter, D., Nicolau, A., Padua, D. (eds) Languages and Compilers for Parallel Computing. LCPC 1994. Lecture Notes in Computer Science, vol 892. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0025891
Download citation
DOI: https://doi.org/10.1007/BFb0025891
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-58868-9
Online ISBN: 978-3-540-49134-7
eBook Packages: Springer Book Archive