Project Reporting FINAL REPORT FOR AWARD # 9705594

Michael L Scott ; University of Rochester
Experimental Evaluation of Software Coherence for Next-Generation Networks

Participant Individuals:
CoPrincipal Investigator(s) : Sandhya Dwarkadas; Wei Li
Graduate student(s) : Robert Stets; Galen C Hunt; Umit Rencuzogullari; DeQing (Luke) Chen; Chunqiang Tang; Srinivasan Parthasarathy; Nikolaos Hardavellas

Partner Organizations:
Compaq Computer Corp: Financial Support; In-kind Support; Collaborative Research

The principal computer equipment employed in this project was acquired
with the help of Digital Equipment Corp. Research Agreement
#US-1998036 (Cluster-Wide Shared Memory via Memory Channel), with a
value of $983,176.  Dr. Leonidas Kontothanassis, a Rochester alumnus
and, for several years, a member of research staff at Compaq's
Cambridge Research Laboratory, was a major contributor to the project.
 Dr. Rishiyur S. Nikhil, one of Leonidas's colleagues at Compaq, was
also a coauthor on one of the project papers.

Microsoft Corporation: Financial Support; In-kind Support; Collaborative Research
Microsoft Research donated a modest amount of equipment and software
in support of the project.  Dr. Galen Hunt, a Rochester alumnus now at
Microsoft, was actively involved in the project during his graduate
studies, and continued to be peripherally involved after his move to
Seattle.

Intel Corporation: Financial Support
Intel provided a modest amount of equipment to support experimentation
with the VIA network interface standard.

Other collaborators:

During 1998 we collaborated on a joint study and paper with Drs.
Kourosh Gharachorloo and Daniel Scales of Compaq's Western Research
Laboratory.

Activities and findings:

Research and Education Activities: 
The activities and findings of the sponsored research are documented extensively in the scientific literature. Principal activities have included: - Design and implementation of the Cashmere-1L software distributed shared memory system, as presented at ISCA '97. - Design and implementation of the Cashmere-2L system, as presented at SOSP '97. - Design and implementation of the Cashmere-VLM large-memory system, as presented at IPPS/SPDP '99. - Initial design and implementation of the InterWeave distributed sharing system, as presented at LCR 2000. - Comparative evaluation of the Cashmere and Shasta S-DSM systems, as presented at HPCA '99. - Detailed evaluation of the impact of low-latency networks, and the relative impact of various network features, on the performance of S-DSM, as presented at HPCA 2000. - Development of the CRAUL system for run-time adaptive load- balancing, and the InterAct system for sharing in client-server systems, as presented at LCR '98. - Development of dynamic load-balancing mechanisms for multiprogrammed systems, as presented at PPoPP 2001. - Application and algorithm development in the areas of data- mining, computational fluid dynamics, and scalable synchronization, reported in various venues.

Findings:
The activities and findings of the sponsored research are documented extensively in the scientific literature. Principal findings include: - Software distributed shared memory systems can provide excellent speedups for medium-size clusters on a variety of applications. Using benchmarks drawn from the Splash-2 benchmark suite, the TreadMarks suite, locally developed kernels, and applications from genetic linkage analysis and stellar dynamics, all running on an 8-node AlphaServer cluster with 4 processors per node, we obtained an average speedup of just under 20. [SOSP 1997, HPCA 2000] - Hardware coherence within SMP nodes and software coherence among nodes can be combined efficiently. In particular, the use of 'two-way diffs' obviates the need for TLB shootdown when bringing in data that has been modified off-node. [SOSP 1997] - Emerging system-area networks with fast, user-level messages, can significantly increase S-DSM performance. The principal benefit comes simply from low-latency communication, which allows write notices to be propagated aggressively. Secondary benefits come from in-order messaging, which eliminates the need for some acknowledgments, and from remote writes, which eliminate the need to interrupt a remote node in order to put data in its memory. [HPCA 2000] - For applications that have sufficiently coarse grain sharing to scale well under S-DSM, virtual-memory based write detection generally outperforms write detection through software instrumentation. Moreover software-instrumented S-DSM does not appear to be able to effectively exploit intro-node hardware coherence. At the same time, software-instrumented S-DSM is less sensitive to the performance degradation caused by fine- grain sharing. [HPCA 1999] - User-level control of page-out strategy can significantly enhance the performance of S-DSM systems for appliations with out-of-core data sets. [IPPS/SPDP 1999] - Careful integration of compiler and run-time coherence management can produce significantly better speedup than either strategy alone, often rivaling the performance of hand-tuned message- passing code. [PPoPP 1997, LCR 1998, J. Sci. Prog. 1999] - Heterogeneous machine architectures and programming languages need not be an obstacle to efficient, convenient shared-memory programming. [WSDSM 2000] - Highly relaxed, application-specific coherence models, combined with S-DSM style diffing, can lead to acceptable performance for important classes of distributed applications, even on low- bandwidth networks. [LCR 1998, LCR 2000]

Training and Development:
Four graduate students supported in part by the grant have finished Ph.D.s. Two took academic positions; the other two are at leading industrial research labs. One student went to industry after finishing an M.S. Four additional students are expected to finish Ph.D.s soon. At least six undergraduates have worked actively on Cashmere or its successor, InterWeave, several under funding from an REU supplement. All supported graduate students assisted in undergraduate instruction as part of their graduate training, with close faculty oversight and coaching.

Journal Publications:
R. Stets, G. C. Hunt, and M. L. Scott, "Component-based Operating System APIs: A Versioning and Distributed Resource Solution", Computer, vol. , (1999), p. 54. Published
M. M. Michael and M. L. Scott, "Nonblocking Algorithms and Preemption-Safe Locking on Multiprogrammed Shared Memory Multiprocessors", Journal of Parallel and Distributed Computing, vol. , (1998), p. 1. Published
G. Delamarter, S. Dwarkadas, A. Frank, and R. Stets, "Portable Parallel Programming on Emerging Platforms", Current Science Journal, vol. , (2000), p. ?. Published
S. Ioannidis, U. Rencuzogullari, R. Stets, and S. Dwarkadas, "CRAUL: Compiler and Run-Time Integration for Adaptation Under Load", Journal of Scientific Programming, vol. , (1999), p. ?. Published
S. Dwarkadas, H. Lu, A. L. Cox, R. Rajamony, and W. Zwaenepoel, "Combining Compile-Time and Run-Time Support for Efficient Software Distributed Shared Memory", Proceedings of the IEEE, vol. , (1999), p. 476. Published
C. Amza, A. L. Cox, S. Dwarkadas, L-J Jin, K. Rajamani, and W. Zwaenepoel, "Adaptive Protocols for Software Distributed Shared Memory", Proceedings of the IEEE, vol. , (1999), p. ?. Published
H. Lu, S. Dwarkadas, A. L. Cox, and W. Zwaenepoel, "Quantifying the Performance Differences between PVM and TreadMarks", Journal of Parallel and Distributed Computing, vol. , (1997), p. 65. Published
M. J. Zaki, S. Parthasarathy, and W. Li, "A Localized Algorithm for Parallel Association Mining", Journal of Parallel and Distributed Computing, vol. 43, (1997), p. 156. Published
S. Parthasarathy and S. Dwarkadas, "Shared State for Distributed Interactive Data Mining Applications", International Journal of Distributed and Parallel Databases, vol. , (2002), p. ?. Accepted

Book(s) of other one-time publications(s):
M. J. Zaki, M. Ogihara, and S. Dwarkadas, "Sequence Mining in Dynamic and Interactive Environments" , bibl. Chapter 16, Kluwer Academic, (2000). Book chapter Published
of Collection: W. Abramowicz and J. Zurada, "Knowledge Discovery for Business Information Systems"
S. Parthasarathy, S. Dwarkadas, and M. Ogihara, "Active Mining in a Distributed Setting" , bibl. LNAI Vol. 1759, Springer-Verlag, (2000). Book chapter Published
of Collection: Mohammed Zaki and Howard Ho, "Large-Scale Parallel Data Mining"
U. Rencuzogullari and S. Dwarkadas, "Dynamic Adaptation to Available Resources for Parallel Computing in an Autonomous Network of Workstations" , bibl. ACM, (2001). Refereed conference paper Published
of Collection: , "8th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming"
S. Parthasarathy and S. Dwarkadas, "Shared State for Client-Server Mining" , bibl. SIAM, (2001). Refereed conference paper Published
of Collection: , "1st SIAM International Conference on Data Mining (SDM 2001)"
D. Chen, S. Dwarkadas, S. Parthasarathy, E. Pinheiro, and M. L. Scott, "InterWeave: A Middleware System for Distributed Shared State" , bibl. Rochester, NY, (2000). Refereed workshop paper Published
of Collection: , "Proceedings of the 5th workshop on Languages, Compilers, and Run-Time Systems for Scalable Computers"
E. Pinheiro, D. Chen, S. Dwarkadas, S. Parthasarathy, and M. L. Scott, "S-DSM for Heterogeneous Machine Architectures" , bibl. Held in conjunction with the International Conference on Supercomputing, (2000). Refereed workshop paper Published
of Collection: , "2nd Workshop on Software Distributed Shared Memory"
R. Stets. S. Dwarkadas, L. Kontothanassis, U. Rencuzogullari, and M. L. Scott, "The Effect of Network Total Order, Broadcast, and Remote-Write Capability on Network-Based Shared Memory Computing" , bibl. IEEE, (2000). Book Published
of Collection: , "6th International Symposium on High-Performance Computer Architecture"
S. Parthasarathy, M. J. Zaki, M. Ogihara, and S. Dwarkadas, "Incremental and Interactive Sequence Mining" , bibl. ACM, (1999). Refereed conference paper Published
of Collection: , "Eighth International Conference on Information and Knowledge Management (CIKM)"
S. Parthasarathy, S. Dwarkadas, and M. Ogihara, "Active Mining in a Distributed Setting" , bibl. held in conjunction with the International Conference on Knowledge Discovery and Data Mining, KDD99, (1999). Refereed workshop paper Published
of Collection: , "SIGKDD Workshop on Large-Scale Parallel KDD Systems"
S. Dwarkadas, N. Hardavellas, L. Kontothanassis, R. Nikhil, and R. Stets, "Cashmere-VLM: Remote Memory Paging for Software Distributed Shared Memory" , bibl. IEEE, (1999). Refereed conference paper Published
of Collection: , "International Parallel Processing Symposium (IPPS/SPDP)"
S. Dwarkadas, K. Gharachorloo, L. Kontothanassis, D. J. Scales, M. L. Scott, and R. J. Stets, "Comparative Evaluation of Fine- and Coarse-Grain Software Distributed Shared Memory" , bibl. IEEE, (1999). Refereed conference paper Published
of Collection: , "5th International Symposium on High-Performance Computer Architecture"
S. Ioannidis and S. Dwarkadas, "Compiler and Run-Time Support for Adaptive Load Balancing in Software Distributed Shared Memory Systems" , bibl. Pittsburgh, PA, (1998). Refereed workshop paper Published
of Collection: , "Fourth Workshop on Languages, Compilers, and Run-time Systems for Scalable Computers"
S. Parthasarathy and S. Dwarkadas, "InterAct: Virtual Sharing for Interactive Client-Server Applications" , bibl. Pittsburgh, PA, (1998). Refereed workshop paper Published
of Collection: , "Fourth Workshop on Languages, Compilers, and Run-time Systems for Scalable Computers"
R. Stets, S. Dwarkadas, N. Hardavellas, G. Hunt, L. Kontothanassis, S. Parthasarathy, and M. L. Scott, "Cashmere-2L: Software Coherent Shared Memory on a Clustered Remote-Write Network" , bibl. ACM, (1997). Refereed conference paper Published
of Collection: , "ACM Symposium on Operating Systems Principles"
R. L. Carceroni, W. Meira Jr., R. Stets, and S. Dwarkadas, "Evaluating the Trade-Offs in the Parallelization of Probabilistic Search Algorithms" , bibl. Campos do Jordao, SP, Brazil, (1997). Refereed conference paper Published
of Collection: , "9th Brazilian Symposium on Computer Architecture and High Performance Processing"
S. Dwarkadas, H. Lu, A. L. Cox, R. Rajamony, and W. Zwaenepoel, "Compiler and Software Distributed Shared Memory Support for Irregular Applications" , bibl. ACM, (1997). Refereed conference paper Published
of Collection: , "ACM Symposium on the Principles and Practice of Parallel Programming"
L. I. Kontothanassis, G. Hunt, R. Stets, N. Hardavellas, M. Cierniak, S. Parthasarathy, W. Meira, S. Dwarkadas, and M. L. Scott, "VM-Based Shared Memory on Low-Latency, Remote-Memory-Access Networks" , bibl. ACM/IEEE, (1997). Refereed conference paper Published
of Collection: , "24th International Symposium on Computer Architecture"
M. L. Scott and W. N. Scherer III, "Scalable Queue-Based Spin Locks with Timeout" , bibl. Snowbird, UT, (2001). Refereed conference paper Published
of Collection: , "Eighth ACM Symposium on Principles and Practice of Parallel Programming (PPoPP)"
R. J. Stets, D. Chen, S. Dwarkadas, N. Hardavellas, G. C. Hunt, L. Kontothanassis, G. Magklis, S. Parthasarathy, U. Rencuzogullari, and M. L. Scott, "The Implementation of Cashmere" , bibl. TR 723, Computer Science Department, University of Rochester, (1999). Technical report Published
D. Chen, C. Tang, X Chen, S. Dwarkadas, and M. L. Scott, "Beyond S-DSM: Shared State for Distributed Systems" , bibl. TR 744, Computer Science Department, University of Rochester, (2001). Technical report/conference submission Submitted
M. M. Michael, A. K. Nanda, B.-H. Lim, and M. L. Scott, "Coherence Controller Architectures for SMP-Based CC-NUMA Multiprocessors" , bibl. Denver, CO, (1997). Refereed conference paper Published
of Collection: , "Twenty-Fourth International Symposium on Computer Architecture"
G. C. Hunt and M. L. Scott, "Coign: Automated Distributed Partitioning of Component Applications" , bibl. St. Malo, France, (1997). Poster presentation Published
of Collection: , "Sixteenth ACM Symposium on Operating Systems Principles"
G. C. Hunt and M. L. Scott, "A Guided Tour of the Coign Automatic Distributed Partitioning System" , bibl. San Diego, CA, (1998). Refereed conference paper Published
of Collection: , "Enterprise Distributed Object Computing '98"
G. C. Hunt and M. L. Scott, "The Coign Automatic Distributed Partitioning System" , bibl. New Orleans, LA, (1999). Refereed conference paper Published
of Collection: , "Third Symposium on Operating Systems Design and Implementation"
G. C. Hunt and M. L. Scott, "Intercepting and Instrumenting COM Applications" , bibl. San Diego, CA, (1999). Refereed conference paper Published
of Collection: , "Fifth Conference on Object-Oriented Technologies and Systems"
L. Kontothanassis, M. L. Scott, R. Stets, S. Dwarkadas, N. Hardavellas, and G. Hunt, "Apparatus and Method for Maintaining Data Coherence Within a Cluster of Symmetric Multiprocessors" , bibl. U.S. Patent #6,341,339, (2002). U.S. Patent Published
S. Parthasarathy and M. Ogihara, "Exploiting Dataset Similarity for Distributed Mining" , bibl. ?, (2000). Refereed workshop paper Published
of Collection: , "Workshop on High Performance Data Mining"
S. Parthasarathy, M. J. Zaki, and W. Li, "Memory Placement Techniques for Parallel Association Mining" , bibl. AAAI/IEEE, (1998). Refereed conference paper Published
of Collection: , "4th International Conference on Knowledge Discovery and Data Mining (KDD)"
S. Parthasarathy, R. Subramonian, and R. Venkata, "Generalized Discretization for Summarization and Classification" , bibl. London, (1998). Refereed conference paper Published
of Collection: , "3rd International Conference on the Practical Applications of Discovery and Datamining (PADD98)"
S. Parthasarathy and R. Subramonian, "Facilitating Data Mining on a Network of Workstations" , bibl. IASTED, (1999). Refereed conference paper Published
of Collection: , "IASTED International Conference on Parallel and Distributed Systems"
R. Subramonian and S. Parthasarathy, "A Framework for Distributed Data Mining" , bibl. AAAI/IEEE, (1998). Refereed workshop paper Published
of Collection: , "International Workshop on Distributed Data Mining (with KDD98)"

Other Specific Products:

Software (or netware)
We contributed to development of the TreadMarks Distributed Shared
Memory system, available from Rice University
See http://www.cs.rice.edu/~willy/TreadMarks/overview.html

Internet Dissemination:

http://www.cs.rochester.edu/research/cashmere http://www.cs.rochester.edu/research/interweave/

First URL is main project site.
Second URL is site for follow-on project, launched near end of grant.

Contributions:

Contributions within Discipline:

 Shared-memory multiprocessors are widely used in business and science
to solve problems too time-consuming for a uniprocessor machine. 
Machines with up to several hundred processors are available from a
variety of vendors, but their cost per processor is dramatically
higher than the cost of a uniprocessor, mainly due to the complexity
of maintaining coherence among copies of data cached by different
processors.  By contrast, machines with fewer than about ten
processors are comparatively inexpensive.

Software Distributed Shared Memory (S-DSM) systems attempt to provide
most of the performance of a large multiprocessor at the cost per
processor of small machines.  They do so by maintaining cache
coherence in software.  The Cashmere system (the principal product of
the funded research) is one of several S-DSM systems developed over
the past ten years.  Among such systems it makes two principal
contributions:  First, it integrates the hardware coherence available
within small symmetric multiprocessor (SMP) nodes with software
coherence among nodes, in a much more efficient manner than had
previously been thought possible. (This integration is the subject of
US Patent #6,341,339, awarded jointly to researchers at the University
of Rochester and Compaq Computer Corporation in January 2002.) 
Second, Cashmere exploits the capabilities of newly available
low-latency networks to maintain coherence information more
efficiently than has previously been possible.  In particular, it
recognizes that overall performance may improve if notifications of
data updates are propagated aggressively, even if the overall number
of messages increases.

As clusters of small multiprocessors become increasingly ubiquitous,
the technology developed by the funded research should allow
application developers to take software developed for small SMPs and
use it, economically, to address significantly larger and more
important problems.

Contributions to Other Disciplines:
 In collaboration with colleages in other disciplines, we have used
Cashmere to demonstrate significant speedups on programs from several
important appliation domains, including parallel data-mining, stellar
simulation, and genetic linkage analysis.

Contributions to Education and Human Resources:
 Four graduate students supported in part by the grant have finished
Ph.D.s.  Two took academic positions; the other two are at leading
industrial research labs.  One student went to industry after
finishing an M.S.  Four additional students are expected to finish
Ph.D.s soon.

At least six undergraduates have worked actively on Cashmere or its
successor, InterWeave, several under funding from an REU supplement.


Contributions to Resources for Science and Technology:
 The Cashmere and InterWeave systems have been used as courseware in
several graduate-level classes.


Categories for which nothing is reported:
Outreach Activities
Contributions Beyond Science and Engineering


FastLane Home Page Take you to the Project System Control Screen We welcome comments on this system

If you have trouble accessing any FastLane page, please contact the FastLane Help Desk at 1-800-673-6188