Summary of Objectives and Approach.
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.
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.
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).
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.
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.
Transitions and DOD Interactions.
Software and Hardware Prototypes.
Invited and Contributed Presentations.
Honors, Prizes or Awards Received.
Project Personnel Promotions Obtained.