A Prototyping System for Parallel and Distributed Applications

Table of Contents:

  1. Principal Investigator.
  2. Productivity Measures.
  3. Summary of Objectives and Approach.
  4. Detailed Summary of Technical Progress.
  5. Transitions and DOD Interactions.
  6. Software and Hardware Prototypes.
  7. List of Publications.
  8. Invited and Contributed Presentations.
  9. Honors, Prizes or Awards Received.
  10. Project personnel promotions obtained.
  11. Project Staff.
  12. Misc Hypermedia URL.
  13. Keywords.

- Revised: Wed Sep 21 11:14:39 1994 by nyland@cs.unc.edu

Principal Investigator.

Productivity Measures.

Summary of Objectives and Approach.

  1. To provide a prototyping-based design methodology that supports the architecture-independent development of parallel and distributed systems. The Proteus system provides the language and tools supporting this methodology.

    This work addresses a fundamental problem: naive implementations of abstract models of parallel computation lead to impractical implementations, whereas machine-specific models lead to intractable analysis of even the simplest programs. The goal of our work is to provide tools for exploring the design space of a parallel application by a process of prototyping and successive refinement.

Detailed Summary of Technical Progress.

  1. Development of object-oriented mechanisms for task-parallel communication and synchronization.

    Significant progress has been made in language design in the development of an extensible foundation for explicit task parallelism. Communication is through a shared object model in which the access to shared state is controlled through object methods and class directives which constrain mutual exclusion of methods [GPR+94]. Predefined classes such as for single-assignment objects which synchronize a producer with a consumer, together with provisions for private state with barrier synchronization allow the expression of a wide range of parallel computing paradigms, key to providing an expressive and uniform vehicle for refinement.

  2. Development of methodology for performance prediction in which computing model varies with level of refinement; development of improved computational model LogP-HMM.

    To support early analysis of program efficiency and resource utilization we are developing a methodology for performance predicition which uses, as program refinement progresses, increasingly detailed parallel computational models. The accuracy and confidence of assessment thus increases as the level of architectural detail incorporated into the program increases. To support the assessment of multi-paradigm programs, different models are used for analysis of code segments following different paradigms, such as the VRAM for data-parallelism and the LogP message-passing, with suitable instrumentation to attach the model to the program. At the same time, to support more accurate modeling of costs such as cache and I/O, we are developing improved performance models, i.e., a new hybrid model of parallel computation, the LogP-HMM model [LMR94], which fills a gap in the hierachy of refined models by extending a network model (the LogP) with a sequential hierarchical memory model (the HMM).

  3. Completion and release of the DTRE3 transformation system.

    The refinement subsystem of Proteus, called DTRE3, has been completed. This system has supported work in transformation of data parallel Proteus programs to vector models. A new system called Specware, which significantly generalizes DTRE3 is being developed. In addition to supporting refinement and generation of C and Lisp code, Specware has powerful category-theory-based operations for manipulating diagrams (directed graphs) logical theories. The logical theories are used to hierarchically define (partial) specifications, architectural descriptions, refinements, and other software artifacts. The operations are used to compose, refine, and instantiate components to build systems. A preliminary version of the Specware has been released.

  4. Participation in the Hiper-D GeoServer demonstration activity.

    In November 1993, we participated in a community-wide prototyping experiment defined by the Hiper-D program at NSWC as part of their next-generation Aegis development effort. Using Proteus, we developed a series of prototypes to explore design approaches to a geometric classification problem. An initial design was elaborated to reflect the functional structure of the radar system and the interactions with a system operator. Another prototype explored designs for the system in demanding high-traffic situations using a sophisticated parallel algorithm. All prototypes were executable using the Proteus interpreter, were rapidly developed, and were judged to have contributed useful knowledge about design options to NSWC. An external review of the participating ProtoTech languages in this experiment assigned the highest overall score to the Proteus and Haskell efforts.

  5. FY-95 PLANS:

Transitions and DOD Interactions.

  1. Duke and UNC are collaborating with John Board in the E.E. Department of Duke University and J. Hermans of the Biochemistry Department at UNC in the investigation and implementation of parallel Fast Multipole Algorithms (FMA) for molecular dynamics simulations. NCSC and UNC were recently awarded a 5-year $2.5M NIH grant for the development and implementation of parallel algorithms for molecular dynamics. The use of Proteus is an integral component of this effort.
  2. Medical Imaging group at UNC is using Proteus to develop sophisticated parallel algorithms for segmenting medical images into physical objects.
  3. Our FMA code is being examined by others, at Duke University, CMU and Brooklyn Polytechnic, as a guide to lead their own implementations.
  4. Release of Specware to Mitre, Motorola, Air Forces Institute of Technology, and Rome Labs. Motorola is specifying and (eventually) implementing the kernal of a crypto system using Specware. AFIT and Rome Labs are evaluating Specware for use within their research programs in software engineering. Mitre is evaluating Specware technology.
  5. Specware, which is described above, requires a UNIX/X environment, and Refine (available at low-cost to educational institutions). The POC is Maria Pryce, pryce@kestrel.edu, 415-493-6871.

Software and Hardware Prototypes.

  1. A prototype system for translation of Proteus programs to executable parallel code has been developed.
  2. Enhancement of the Proteus interpreter continues.

List of Publications.

  1. Lee Blaine, et. al. SPECWARE User Manual, Kestrel Institute Technical Report, June, 1994.
  2. Rickard E. Faith, Doug L. Hoffman, and David G. Stahl. UnCvL: The University of North Carolina C Vector Library. Technical Report, May, 1993.
  3. Allen Goldberg, Peter Mills, Lars Nyland, Jan Prins, John Reif, and James Riely. Specification and Development of Parallel Applications using the Proteus System. Proc. DIMACS Workshop on Specification of Parallel Algorithms, 1994.
  4. Allen Goldberg, Jan Prins, John Reif, Rickard Faith, Zhiyong Li, Peter Mills, Lars Nyland, Daniel Palmer, and James Riely. The Proteus system for the development of parallel applications. Technical report, UNC-CH, May 1994. To be published in the ProtoTech compendium.
  5. Allen Goldberg, Richard Jullig, Y.V. Srinivas, Refinement of Specifications, Kestrel Institute Technical Report, Oct. 1993.
  6. Jullig, R. and Srinivas, Y. Describing software architectures formally: A case-study using KWIC. Kestrel Institute Technical Report KES.U.94.4, Kestrel Institute, April 1994.
  7. Jullig, R. and Srinivas, Y. Diagrams for software synthesis. Proceedings of the 8th Knowledge-Based Software Engineering Conference, IEEE, Chicago, IL, September 20--23, 1993.
  8. Gary Levin and Lars Nyland. An introduction to Proteus, version 0.9. Technical report, UNC-CH, 1993.
  9. "Models and Resource Metrics for Parallel and Distributed Computation", Z. Li, P. Mills and J. Reif. To appear in 28th Hawaii International Conference on System Sciences (HICSS-28, Parallel Algorithms Software Technology Track), Maui, Hawaii, January 3-6, 1995.
  10. P.H. Mills, L.S. Nyland, J.F. Prins, and J.H. Reif. Software Issues in High-Performance Computing and a Framework for the Development of HPC Applications. Computer Science Agendas for High-Performance Computing (U. Vishkin, ed.), ACM, 1994.
  11. Z. Li, P.H. Mills, and J.H. Reif. Models and Resource Metrics for Parallel and Distributed Computation. Duke Technical Report, Submitted for publication, 1994.
  12. Daniel W. Palmer. DPL- data parallel library manual. Technical report, UNC, 1993.
  13. Qian, X.L. and Allen Goldberg, Referential Opacity in Nondeterministic Data Refinement, to appear in ACM Letters on Programming Languages and Systems.
  14. T.C. Wang and Allen Goldberg, KITP-93: An automated inference system for program analysis, Proceedings of the Conference on Automated Deduction, Nancy, France, June, 1994.

Invited and Contributed Presentations.

  1. "Work-efficient Parallel Implementations of Sparse Grid-based Computations", Jan Prins, Workshop on Parallel Algorithms for Unstructured and Dynamic Problems, DIMACS, Rutgers, NJ. 6/2/93.
  2. "The Proteus System for the Development of Parallel Software", Jan Prins, Parallel Software Engineering CRDA, Griffiss AFB, Rome NY. 7/28/93.
  3. "Targeting Multiple Virtual Machines with the Proteus System", Jan Prins, Workshop on Parallel Virtual Machine Concepts, Griffiss AFB, Rome, NY. 10/4/93.
  4. "Practical Parallel Algorithms for the MasPar MP-1", Jan Prins, U.S. Naval Academy, Annapolis, MD. 11/22/93.
  5. "The Proteus System for the Development of Parallel Algorithms", Jan Prins, Workshop on Parallel Algorithms, DIMACS, Rutgers, NJ. 11/17/93.
  6. "A Proteus Solution for the Geometric Region Server", Lars Nyland, Computer Sciences Corp., Dalgren VA, 12/9/93.
  7. "Parallel Implementations of Molecular Dynamics Simulations", Jan Prins, Computational Biology Colloquium Series, NCSC, RTP, NC. 1/27/94.
  8. "Social Potential Fields: A Distributed Behavioral Control for Autonomous Robots", John Reif and H. Wang. Workshop on the Algorithmic Foundations of Robotics (WAFR), San Francisco, February, 1994
  9. Distinguished Lecture: "Predictive Computing:An Emerging Paradigm for Efficient Computation", John Reif, School of Computer Science, April 14, 1994, CMU
  10. "The Role of Program Transformations in the Proteus System", Jan Prins, IFIP WG10.3 Working Conference on Programming Environments for Massively Parallel Computing, Ascona, Switzerland. 4/25/94.
  11. "Models, Control Primitives, and Resource Metrics for Parallel and Distributed Computation", J. Reif. Invited keynote presentation at 8th International Parallel Processing Symposium (IPPS '94), Cancun, Mexico, April 26-29, 1994.
  12. "Dynamic Parallel Tree Contraction", John Reif and S. R. Tate, 5th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA'94), Cape May, NJ, June 1994. pp.114-121.
  13. "O(log^2 n) Time Efficient Parallel Factorization of Dense, Sparse Separable, and Banded Matrices", John Reif. 5th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA'94), Cape May, NJ, June 1994.
  14. "Predictive Computing:An Emerging Paradigm for Efficient Computation", John Reif, Dartmouth Institute for Advanced Graduate Studies(DAGS94), July 5, 1994, Hanover, New Hampshire

Honors, Prizes or Awards Received.

Project Personnel Promotions Obtained.

  1. Jan Prins, promoted to tenured Associate Professor.

Project Staff.

  1. Allen Goldberg, Principal Investigator, Kestrel Institute
  2. Jan F. Prins, Principal Investigator, UNC
  3. John H. Reif, Principal Investigator, Duke University
  4. Stephen Westfold, Senior Scientist, Kestrel Institute
  5. Peter H. Mills, Research Associate, Duke University
  6. Lars S. Nyland, Research Assistant Professor, UNC
  7. Zhiyong Li, Graduate Student, Duke University
  8. Rickard Faith, Graduate Student, UNC
  9. Daniel Palmer, Graduate Student, UNC
  10. James Riely, Graduate Student, UNC
  11. Bill Yakowenko, Graduate Student, UNC
  12. Madelyn Mann, Secretary, UNC
  13. Kenneth Robinson, Secretary, Duke University

Misc Hypermedia.

  1. The Proteus System Home Page. An overview, all publications, software, examples, demonstrations and personnel descriptions can be found here.
  2. Quad-chart for 1994. Three versions: HTML hypermedia (8K bytes), Macintosh Powerpoint (17K bytes), and postscript (45K bytes)


  1. Prototype Program Development
  2. Parallel Programming
  3. Program Transformation
  4. Fast Multipole Algorithm (FMA)