Active Messages: A Mechanism for Integrated Communication and Computation

@inproceedings{goldstein-waci06,
  author = {Goldstein, Seth Copen},
  title = {Brain in a Bottle},
  booktitle = {Wild and Crazy Ideas Session of ASPLOS},
  year = {2006},
  month = {Oct},
  url = {http://www.cs.cmu.edu/~seth/papers/goldstein-waci06.pdf},
  keywords = {Brain, Parallel Computing, Self-Assembly},
}

@inproceedings{goldstein-ymw98,
  title = {The Lazy Multithreaded Implementation Design Space},
  booktitle = {The Yale Multithreaded Workshop},
  author = {Goldstein, Seth Copen and Culler, David E.},
  address = {New Haven, CT},
  year = {1998},
  month = {Jun},
  keywords = {Lazy Threads,Parallel Computing},
}

@phdthesis{goldstein-phd97,
  title = {Lazy Threads Compiler and Runtime Structures for
     Fine-Grained Parallel Programming},
  url = {http://www.cs.cmu.edu/~seth/papers/goldstein-phd97.pdf},
  author = {Goldstein, Seth Copen},
  school = {University of California--Berkeley},
  year = {1997},
  address = {Berkeley, CA},
  keywords = {Lazy Threads,Parallel Computing,Split-C,Threaded
     Abstract Machine (TAM)},
}

@article{goldstein96-jpdc,
  author = {Goldstein, Seth Copen and Schauser, Klaus Erik and Culler,
     David E.},
  title = {Lazy threads: implementing a fast parallel call},
  journal = {Journal of Parallel and Distributed Computing},
  volume = {37},
  number = {1},
  year = {1996},
  pages = {5--20},
  publisher = {Academic Press, Inc.},
  address = {Orlando, FL, USA},
  keywords = {Lazy Threads, Parallel Computing},
  url = {http://www.cs.cmu.edu/~seth/papers/goldstein96-jpdc.pdf},
  abstract = {In this paper, we describe lazy threads, a new approach
     for implementing multithreaded execution models on conventional
     machines. We show how they can implement a parallel call at
     nearly the efficiency of a sequential call. The central idea is
     to specialize the representation of a parallel call so that it
     can execute as a parallel-ready sequential call. This allows
     excess parallelism to degrade into sequential calls with the
     attendant efficient stack management and direct transfer of
     control and data, yet a call that truly needs to execute in
     parallel, gets its own thread of control. The efficiency of lazy
     threads is achieved through a careful attention to storage
     management and a code generation strategy that allows us to
     represent potential parallel work with no overhead.},
}

@inproceedings{goldstein-lcr95,
  title = {Enabling Primitives for Compiling Parallel Languages},
  url = {http://www.cs.cmu.edu/~seth/papers/goldstein-lcr95.pdf},
  booktitle = {Third Workshop on Languages, Compilers, and Run-Time
     Systems for Scalable Computers},
  author = {Goldstein, Seth Copen and Culler, David E. and Schauser,
     Klaus Erik},
  address = {Rochester, NY},
  year = {1995},
  month = {May},
  keywords = {Parallel Computing,Lazy Threads},
}

@inproceedings{schauser-fplca95,
  title = {How Much Non-Strictness Do Lenient Programs Require?},
  url = {http://www.cs.cmu.edu/~seth/papers/schauser-fplca95.pdf},
  booktitle = {Conference on Functional Programming Languages and
     Computer Architecture},
  author = {Schauser, Klaus Erik and Goldstein, Seth Copen},
  address = {La Jolla, CA},
  year = {1995},
  month = {Jun},
  keywords = {Functional Programming, Parallel Computing},
}

@techreport{dusseau-tr92,
  title = {Introduction to Split-C},
  url = {http://www.cs.cmu.edu/~seth/papers/dusseau-tr92.pdf},
  author = {Culler, David E. and Dusseau, Andrea and Goldstein, Seth
     Copen and Krishnamurthy, Arvind and Lumetta, Steven and
     von~Eicken, Thorsten and Yelick, Katherine},
  month = {Apr},
  institution = {University of California--Berkeley},
  year = {1995},
  keywords = {Parallel Computing,Split-C},
}

@inproceedings{callahan-isca95,
  title = {NIFDY: A Low Overhead, High Throughput Network Interface},
  url = {http://www.cs.cmu.edu/~seth/papers/callahan-isca95.pdf},
  booktitle = {Proceedings of the 22nd International Symposium on
     Computer Architecture},
  author = {Callahan, Timothy J and Goldstein, Seth Copen},
  address = {Santa Margherita Ligure, Italy},
  year = {1995},
  month = {Jun},
  keywords = {parallel Computing, NIFDY},
}

@inproceedings{SCG95,
  author = {Schauser, Klaus Erik and Culler, David E. and Goldstein,
     Seth Copen},
  booktitle = {Proceedings of the Principles of Programming
     Languages},
  title = {Separation Constraint Partitioning --- A New Algorithm for
     Partitioning non-Strict Programs Into Sequential Threads},
  year = {1995},
  address = {San Francisco, CA},
  month = {Jan},
  keywords = {Parallel Computing},
  url = {http://www.cs.cmu.edu/~seth/papers/SCG95.pdf},
}

@techreport{GSC95,
  author = {Goldstein, Seth Copen and Culler, David E. and Schauser,
     Klaus Erik},
  title = {{Lazy Threads, Stacklets, and Synchronizers: Enabling
     primitives for compiling parallel languages}},
  institution = {University of California at Berkeley},
  year = {1995},
  keywords = {Lazy Threads, Parallel Computing},
}

@misc{goldstein-cm5users94,
  title = {Active Messages: A Communication Foundation for Parallel
     Programming Models},
  howpublished = {CM-5 Users Group},
  author = {Goldstein, Seth Copen},
  address = {Santa Fe, NM},
  year = {1994},
  month = {Feb},
  keywords = {Active Messages,Parallel Computing},
}

@mastersthesis{goldstein94,
  author = {Goldstein, Seth Copen},
  title = {The Implementation of a Threaded Abstract Machine},
  school = {University of California at Berkeley},
  year = {1994},
  address = {Computer Science Division, University of California,
     Berkeley, Ca 94720},
  month = {May},
  also = {UC-Berkeley Technical Report UCB/CSD-94-818},
  keywords = {Parallel Computing, Threaded Abstract Machine (TAM)},
}

@inproceedings{culler-sc93,
  author = {Culler, David E. and Dusseau, Andrea and Goldstein, Seth
     Copen and Krishnamurthy, Arvind and Lumetta, Steven and
     von~Eicken, Thorsten and Yelick, Katherine},
  title = {Parallel Programming in Split-C},
  booktitle = {Proceedings of the Supercomputing '93 Conference},
  pages = {262-273},
  year = {1993},
  address = {Portland, OR},
  month = {Nov},
  keywords = {Active Messages,Parallel Computing},
  url = {http://www.cs.cmu.edu/~seth/papers/culler-sc93.pdf},
}

@inproceedings{SpertusGSvECD93,
  author = {Spertus, Ellen and Goldstein, Seth Copen and Schauser,
     Klaus Erik and von~Eicken, Thorsten and Culler, David E. and
     Dally, William J.},
  title = {{Evaluation of Mechanisms for Fine-Grained Parallel
     Programs in the J-Machine and the CM-5}},
  booktitle = {Proceedings of the 20th International Symposium on
     Computer Architecture (ISCA)},
  address = {San Diego, CA},
  month = {May},
  year = {1993},
  keywords = {Active Messages, Parallel Computing,Threaded Abstract
     Machine (TAM)},
  url = {http://www.cs.cmu.edu/~seth/papers/SpertusGSvECD93.pdf},
}

@article{CullerGSvE93,
  author = {Culler, David E. and Goldstein, Seth Copen and Schauser,
     Klaus Erik and von~Eicken, Thorsten},
  title = {{TAM --- a compiler controlled threaded abstract machine}},
  journal = {Journal of Parallel and Distributed Computing},
  year = {1993},
  volume = {18},
  pages = {347-370},
  month = {Jul},
  abstract = {The Threaded Abstract Machine (TAM) refines dataflow
     execution models to address the critical constraints that modern
     parallel architectures place on the compilation of
     general-purpose parallel programming languages. TAM defines a
     self-scheduled machine language of parallel threads, which
     provides a path from dataflow-graph program representations to
     conventional control flow. The most important feature of TAM is
     the way it exposes the interaction between the handling of
     asynchronous message events, the scheduling of computation, and
     the utilization of the storage hierarchy. This paper provides a
     complete description of TAM and codifies the model in terms of a
     pseudo machine language TL0. Issues in compilation from a high
     level parallel language to TL0 are discussed in general and
     specifically in regard to the Id90 language. The implementation
     of TL0 on the CM-5 multiprocessor is explained in detail. Using
     this implementation, a cost model is developed for the various
     TAM primitives. The TAM approach is evaluated on sizable Id90
     programs on a 64 processor system. The scheduling hierarchy of
     quanta and threads is shown to provide substantial locality while
     tolerating long latencies. This allows the average thread
     scheduling cost to be extremely low.},
  url = {http://www.cs.cmu.edu/~seth/papers/CullerGSvE93.pdf},
  keywords = {Active Messages, Parallel Computing,Threaded Abstract
     Machine (TAM)},
}

@inproceedings{goldstein-id92,
  title = {Studying Dynamic Program Behavior `In the Large'},
  booktitle = {ID Workshop},
  author = {Goldstein, Seth Copen},
  address = {Minneapolis, MN},
  year = {1992},
  month = {Nov},
  keywords = {Parallel Computing,Threaded Abstract Machine (TAM),
     Id90},
}

@inproceedings{goldstein-ilpc92,
  title = {Supporting Implicitly Parallel Languages},
  booktitle = {14th Annual Industrial Liaison Program Conference},
  author = {Goldstein, Seth Copen},
  address = {Berkeley, CA},
  year = {1992},
  month = {Mar},
  keywords = {Parallel Computing,Threaded Abstract Machine (TAM),
     Id90},
}

@inproceedings{voneicken-isca92,
  author = {von~Eicken, Thorsten and Culler, David E. and Goldstein,
     Seth Copen and Schauser, Klaus Erik},
  title = {{Active Messages}: A Mechanism for Integrated Communication
     and Computation},
  month = {May},
  booktitle = {Proceedings of the 19th International Symposium on
     Computer Architecture (ISCA)},
  address = {Gold Coast, Australia},
  pages = {430--440},
  year = {1992},
  url = {http://www.cs.cmu.edu/~seth/papers/voneicken-isca92.pdf},
  abstract = {The design challenge for large-scale multiprocessors is
     (1) to minimize communication overhead, (2) allow communication
     to overlap computation, and (3) coordinate the two without
     sacrificing processor cost/performance. We show that existing
     message passing multiprocessors have unnecessarily high
     communication costs. Research prototypes of message driven
     machines demonstrate low communication overhead, but poor
     processor cost/performance. We introduce a simple communication
     mechanism, {\em Active Messages}, show that it is intrinsic to
     both architectures, allows cost effective use of the hardware,
     and offers tremendous flexibility. Implementations on nCUBE/2 and
     CM-5 are described and evaluated using a split-phase
     shared-memory extension to C, {\em Split-C}. We further show that
     active messages are sufficient to implement the dynamically
     scheduled languages for which message driven machines were
     designed. With this mechanism, latency tolerance becomes a
     programming/compiling concern. Hardware support for active
     messages is desirable and we outline a range of enhancements to
     mainstream processors.},
  keywords = {Active Messages, Parallel Computing},
}

@inproceedings{culler-wdc92,
  author = {Culler, David E. and Goldstein, Seth Copen and Schauser,
     Klaus Erik and von~Eicken, Thorsten},
  title = {{Empirical Study of a Dataflow Language on the CM-5}},
  booktitle = {Proc. of the Dataflow Workshop, 19th Int'l Symposium on
     Computer Architecture},
  address = {Gold Coast, Australia},
  month = {May},
  year = {1992},
  pages = {187--210},
  keywords = {Parallel Computing,Threaded Abstract Machine (TAM),
     Id90, Dataflow},
  url = {http://www.cs.cmu.edu/~seth/papers/culler-wdc92.pdf},
}

@inproceedings{bacon-wpdd91,
  title = {Hardware-Assisted Replay of Multiprocessor Programs},
  url = {http://www.cs.cmu.edu/~seth/papers/bacon-wpdd91.pdf},
  booktitle = {Proceedings of the ACM/ONR Workshop on Parallel and
     Distributed Debugging},
  author = {Bacon, David F. and Goldstein, Seth Copen},
  year = {1991},
  address = {Santa Cruz, CA},
  month = {May},
  keywords = {Debugging,Parallel Computing},
}

@misc{goldstein-cm5users94,
  title = {Active Messages: A Communication Foundation for Parallel
     Programming Models},
  howpublished = {CM-5 Users Group},
  author = {Goldstein, Seth Copen},
  address = {Santa Fe, NM},
  year = {1994},
  month = {Feb},
  keywords = {Active Messages,Parallel Computing},
}

@inproceedings{culler-sc93,
  author = {Culler, David E. and Dusseau, Andrea and Goldstein, Seth
     Copen and Krishnamurthy, Arvind and Lumetta, Steven and
     von~Eicken, Thorsten and Yelick, Katherine},
  title = {Parallel Programming in Split-C},
  booktitle = {Proceedings of the Supercomputing '93 Conference},
  pages = {262-273},
  year = {1993},
  address = {Portland, OR},
  month = {Nov},
  keywords = {Active Messages,Parallel Computing},
  url = {http://www.cs.cmu.edu/~seth/papers/culler-sc93.pdf},
}

@inproceedings{SpertusGSvECD93,
  author = {Spertus, Ellen and Goldstein, Seth Copen and Schauser,
     Klaus Erik and von~Eicken, Thorsten and Culler, David E. and
     Dally, William J.},
  title = {{Evaluation of Mechanisms for Fine-Grained Parallel
     Programs in the J-Machine and the CM-5}},
  booktitle = {Proceedings of the 20th International Symposium on
     Computer Architecture (ISCA)},
  address = {San Diego, CA},
  month = {May},
  year = {1993},
  keywords = {Active Messages, Parallel Computing,Threaded Abstract
     Machine (TAM)},
  url = {http://www.cs.cmu.edu/~seth/papers/SpertusGSvECD93.pdf},
}

@article{CullerGSvE93,
  author = {Culler, David E. and Goldstein, Seth Copen and Schauser,
     Klaus Erik and von~Eicken, Thorsten},
  title = {{TAM --- a compiler controlled threaded abstract machine}},
  journal = {Journal of Parallel and Distributed Computing},
  year = {1993},
  volume = {18},
  pages = {347-370},
  month = {Jul},
  abstract = {The Threaded Abstract Machine (TAM) refines dataflow
     execution models to address the critical constraints that modern
     parallel architectures place on the compilation of
     general-purpose parallel programming languages. TAM defines a
     self-scheduled machine language of parallel threads, which
     provides a path from dataflow-graph program representations to
     conventional control flow. The most important feature of TAM is
     the way it exposes the interaction between the handling of
     asynchronous message events, the scheduling of computation, and
     the utilization of the storage hierarchy. This paper provides a
     complete description of TAM and codifies the model in terms of a
     pseudo machine language TL0. Issues in compilation from a high
     level parallel language to TL0 are discussed in general and
     specifically in regard to the Id90 language. The implementation
     of TL0 on the CM-5 multiprocessor is explained in detail. Using
     this implementation, a cost model is developed for the various
     TAM primitives. The TAM approach is evaluated on sizable Id90
     programs on a 64 processor system. The scheduling hierarchy of
     quanta and threads is shown to provide substantial locality while
     tolerating long latencies. This allows the average thread
     scheduling cost to be extremely low.},
  url = {http://www.cs.cmu.edu/~seth/papers/CullerGSvE93.pdf},
  keywords = {Active Messages, Parallel Computing,Threaded Abstract
     Machine (TAM)},
}

@inproceedings{voneicken-isca92,
  author = {von~Eicken, Thorsten and Culler, David E. and Goldstein,
     Seth Copen and Schauser, Klaus Erik},
  title = {{Active Messages}: A Mechanism for Integrated Communication
     and Computation},
  month = {May},
  booktitle = {Proceedings of the 19th International Symposium on
     Computer Architecture (ISCA)},
  address = {Gold Coast, Australia},
  pages = {430--440},
  year = {1992},
  url = {http://www.cs.cmu.edu/~seth/papers/voneicken-isca92.pdf},
  abstract = {The design challenge for large-scale multiprocessors is
     (1) to minimize communication overhead, (2) allow communication
     to overlap computation, and (3) coordinate the two without
     sacrificing processor cost/performance. We show that existing
     message passing multiprocessors have unnecessarily high
     communication costs. Research prototypes of message driven
     machines demonstrate low communication overhead, but poor
     processor cost/performance. We introduce a simple communication
     mechanism, {\em Active Messages}, show that it is intrinsic to
     both architectures, allows cost effective use of the hardware,
     and offers tremendous flexibility. Implementations on nCUBE/2 and
     CM-5 are described and evaluated using a split-phase
     shared-memory extension to C, {\em Split-C}. We further show that
     active messages are sufficient to implement the dynamically
     scheduled languages for which message driven machines were
     designed. With this mechanism, latency tolerance becomes a
     programming/compiling concern. Hardware support for active
     messages is desirable and we outline a range of enhancements to
     mainstream processors.},
  keywords = {Active Messages, Parallel Computing},
}