Date: Tue, 14 Jan 1997 19:33:28 GMT
Server: NCSA/1.5.1
Last-modified: Wed, 21 Sep 1994 15:14:39 GMT
Content-type: text/html
Content-length: 19878
A Prototyping System for Parallel and Distributed Applications
A Prototyping System for Parallel and Distributed Applications
Table of Contents:
- Principal Investigator.
- Productivity Measures.
- Summary of Objectives and Approach.
- Detailed Summary of Technical Progress.
- Transitions and DOD Interactions.
- Software and Hardware Prototypes.
- List of Publications.
- Invited and Contributed Presentations.
- Honors, Prizes or Awards Received.
- Project personnel promotions obtained.
- Project Staff.
- Misc Hypermedia URL.
- Keywords.
- Revised: Wed Sep 21 11:14:39 1994 by nyland@cs.unc.edu
Principal Investigator.
- PI Name: Allen Goldberg
- PI Institution: Kestrel Institute
- PI Phone Number: (415) 493-6871
- PI Fax Number:
- PI E-mail Address: goldberg@kestrel.edu
- PI URL Home Page: http://kestrel.edu/pub/mosaic/kestrel.html
- Grant Title: A Prototyping System for Parallel and Distributed Applications
- Grant/Contract Number: N00014-92-C-0182
- R&T Number: 3331773-09
- Reporting Period: 7/1/93 -- 6/30/94
- PI Name: Jan Prins
- PI Institution: University of North Carolina
- PI Phone Number: (919) 962-1913
- PI Fax Number: (919) 962-1799
- PI E-mail Address: prins@cs.unc.edu
- PI URL Home Page: http://www.cs.unc.edu
- Grant Title: A Prototyping System for Parallel and Distributed Applications
- Grant/Contract Number: N00014-92-C-0182
- R&T Number: 3331773-09
- Reporting Period: 7/1/93 -- 6/30/94
- PI Name: John Reif
- PI Institution: Duke University
- PI Phone Number: (919) 660-6568
- PI Fax Number: (919) 660-6519
- PI E-mail Address: reif@cs.unc.edu
- PI URL Home Page: http://www.cs.duke.edu
- Grant Title: A Prototyping System for Parallel and Distributed Applications
- Grant/Contract Number: N00014-92-C-0182
- R&T Number: 3331773-09
- Reporting Period: 7/1/93 -- 6/30/94
Productivity Measures.
- Number of refereed papers submitted not yet published: 4
- Number of refereed papers published: 0
- Number of unrefereed reports and articles: 5
- Number of books or parts thereof submitted but not published: 2
- Number of books or parts thereof published: 1
- Number of project presentations: 18
- Number of patents filed but not yet granted: 0
- Number of patents granted and software copyrights: 0
- Number of graduate students supported >= 25% of full time: 3 (unc), 1 (duke)
- Number of post-docs supported >= 25% of full time: 0
- Number of minorities supported: 0
Summary of Objectives and Approach.
- 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.
- 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.
- 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).
- 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.
- 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.
- FY-95 PLANS:
- Full development of an integrated task- and data-parallel
programming notation.
- Elaboration of a design model for concurrent systems based on
successive refinement.
- Support for resource requirement estimation using
multiple refined performance-prediction models.
- Further development of Specware, including integration with
Proteus.
- Unified, single-step translation of data-parallel applications to
vector execution.
- Application development to assist in prototyping methodology description.
- Notational Formalism and Software Support for Real-Time Educational
Simulations
- Participation in the Hiper-D advanced GeoServer prototyping activity.
Transitions and DOD Interactions.
- 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.
- Medical Imaging group at UNC is using Proteus to develop sophisticated
parallel algorithms for segmenting medical images into physical
objects.
- Our FMA code is being examined by others, at Duke University, CMU and
Brooklyn Polytechnic, as a guide to lead their own implementations.
- 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.
- 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.
- A prototype system for translation of Proteus programs to
executable parallel code has been developed.
- Enhancement of the Proteus interpreter continues.
List of Publications.
-
Lee Blaine, et. al. SPECWARE User Manual, Kestrel Institute
Technical Report, June, 1994.
-
Rickard E. Faith, Doug L. Hoffman, and David G. Stahl. UnCvL: The
University of North Carolina C Vector Library. Technical Report, May,
1993.
-
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.
-
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.
-
Allen Goldberg, Richard Jullig, Y.V. Srinivas, Refinement of
Specifications, Kestrel Institute Technical Report, Oct. 1993.
-
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.
-
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.
-
Gary Levin and Lars Nyland. An introduction to Proteus, version 0.9.
Technical report, UNC-CH, 1993.
-
"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.
-
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.
-
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.
-
Daniel W. Palmer. DPL- data parallel library manual. Technical
report, UNC, 1993.
- Qian, X.L. and Allen Goldberg, Referential Opacity in
Nondeterministic Data Refinement, to appear in ACM Letters on
Programming Languages and Systems.
- 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.
-
"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.
-
"The Proteus System for the Development of Parallel Software", Jan Prins,
Parallel Software Engineering CRDA, Griffiss AFB, Rome NY. 7/28/93.
- "Targeting Multiple Virtual Machines with the Proteus System", Jan Prins,
Workshop on Parallel Virtual Machine Concepts, Griffiss AFB, Rome, NY.
10/4/93.
-
"Practical Parallel Algorithms for the MasPar MP-1", Jan Prins,
U.S. Naval Academy, Annapolis, MD. 11/22/93.
- "The Proteus System for the Development of Parallel Algorithms",
Jan Prins, Workshop on Parallel Algorithms, DIMACS, Rutgers, NJ.
11/17/93.
- "A Proteus Solution for the Geometric Region Server", Lars
Nyland, Computer Sciences Corp., Dalgren VA, 12/9/93.
-
"Parallel Implementations of Molecular Dynamics Simulations", Jan Prins,
Computational Biology Colloquium Series, NCSC, RTP, NC. 1/27/94.
- "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
- Distinguished Lecture: "Predictive Computing:An Emerging Paradigm
for Efficient Computation", John Reif, School of Computer Science,
April 14, 1994, CMU
-
"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.
-
"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.
- "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.
- "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.
- "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.
- Jan Prins, promoted to tenured Associate Professor.
Project Staff.
- Allen Goldberg, Principal Investigator, Kestrel Institute
- Jan F. Prins, Principal Investigator, UNC
- John H. Reif, Principal Investigator, Duke University
- Stephen Westfold, Senior Scientist, Kestrel Institute
- Peter H. Mills, Research Associate, Duke University
- Lars S. Nyland, Research Assistant Professor, UNC
- Zhiyong Li, Graduate Student, Duke University
- Rickard Faith, Graduate Student, UNC
- Daniel Palmer, Graduate Student, UNC
- James Riely, Graduate Student, UNC
- Bill Yakowenko, Graduate Student, UNC
- Madelyn Mann, Secretary, UNC
- Kenneth Robinson, Secretary, Duke University
Misc Hypermedia.
- The Proteus System Home Page.
An overview, all publications, software, examples, demonstrations and
personnel descriptions can be found here.
- Quad-chart for 1994. Three versions:
HTML hypermedia (8K bytes),
Macintosh Powerpoint (17K bytes),
and
postscript (45K bytes)
Keywords.
- Prototype Program Development
- Parallel Programming
- Program Transformation
- Fast Multipole Algorithm (FMA)