Project Summary

ORGANIZATION
Computer Science, Brown University
SUBCONTRACTORS
None
PRINCIPAL INVESTIGATORS
Eugene Charniak ec@cs.brown.edu 401-863-7601,
Steven P. Reiss spr@cs.brown.edu 401-863-7641,
Paris C. Kanellakis pck@cs.brown.edu 401-863-7647
TITLE OF EFFORT
High-Performance Design Environments (HPDE)

OBJECTIVE

High Performance Design Environments (HPDE) is a three year research effort (7/1/91--6/30/94), which focuses on the implementation of efficient multiparadigm design environments and on the use of such environments in the development of high performance applications. This work includes: (1) Research on programming environments for high performance applications, in particular on new visualization techniques, debugging techniques, and code optimization methods. (2) Research enhancing the performance of specific programming paradigms, in particular concurrent constraint-based and concurrent object-oriented. This is coupled with the study of dynamic, approximate, and parallel algorithms. (3) Research on key supporting technologies, such as graphics, distributed operating systems, multi-databases, and hardware design systems.

APPROACH

The work in High Performance Design Environments (HPDE) at Brown considerably extends our previous research on design environments that employ multiple programming paradigms. Our approach involves three facets:
  1. Integrating into the FIELD open system many of the visual programming techniques of the GARDEN system, moving from 2-D to 3-D graphical interfaces, and adding new parallel debugging tools. The extended system can handle multiple paradigm programming, but, for efficiency, requires special database support. This requires the design and implementation of a heterogeneous object-oriented database (oodb) facility. Extensible oodb optimization technology is very useful for this phase of the project, as well as, new I/O efficient caching methods. In summary, the proposed prototype HPDE will incorporate state-of-the-art visualization techniques, parallel debugging and will be supported by the most efficient oodb technology available.
  2. Parallel high-level languages and algorithms are essential for realizing the promise of parallel architetures. One focus here is on developing novel paradigms that make use of concurrency, e.g., concurrent object-oriented processes and concurrent constraint programming. Constraint programming will be tested on extensive operations research and spatial data management applications. Another focus is the study of dynamic algorithms, approximation algorithms, and good parallelizable heuristics for hard combinatorial problems.
  3. Advanced supporting technologies are also part of the overall effort. These technologies are as follows: (i) Graphics research (on time parametrized or 4D graphics and on 3D widgets for user interfaces) provides state-of-the-art animation and visualization tools for the overall effort. (ii) Research on operating systems includes "Mobile Workstations" and threads. By focusing on systems that present a network of workstations as a loosely coupled parallel computer, this research ties our high performance work with our workstation environment. (iii) Multi-database access through a uniform interface and using a single global transaction mechanism is technology to facilitate heterogeneous system integration.

PROGRESS

In programming environments the first year was devoted to: initial development of the underlying tools to enable abstraction visualization, a novel concept originating in HPDE. There has been considerable work on system and language support for HPDE in optimization, graphics, and databases (23 journal and conference papers and a number of system and subsystem implementations -- see recent accomplishments below). In theoretical computer science, there has been significant progress and publications (21 journal and conference papers) on dynamic geometric methods, approximation methods for combinatorial optimization, and parallel methods for large scale sorting.

RECENT ACCOMPLISHMENTS

Recent contributions in programming environments involve: the novel method of ``abstraction visualization'', by Steven Reiss. Its initial development includes a 3-D layout package compatible with Motif, a hierarchical browser, a data structure to graphics mapping language, a C++ front end to provide the necessary semantic information, and specifications for a heterogeneous oodb and query language for defining abstractions. This is the basic platform on which a prototype HPDE will be built.

Much has been accomplished on optimization techniques that are critical for HPDE efficiency. (a) Two new high-level language optimization techniques applicable to object-oriented languages, by Kenneth Zadeck and his students (b) Stan Zdonik and his students have designed (and are currently testing) various extensible optimization architectures for efficient heterogeneous oodbs. (c) Jeff Vitter and his students have new caching techniques.

Peter Wegner has published extensively on object-oriented concurrency (also has two forthcoming edited books). He has also published a CACM article towards a definition of megaprogramming (with Ceri and Wiederhold).

On constraint-based programming: (a) Pascal Van Hentenryck has developed a number of improved constraint solving methods, has implemented FD a constraint language over finite domains (37,000 lines of C), and has implemented new generic abstract interpretation algorithms for logic programming systems. The applications of this language work are primarily the specification and automatic solution of operations research problems. (b) Paris Kanellakis has developed new indexing strategies for constraint-based data management. The application of this work involves better query languages for spatial databases.

In addition to above work on databases: (a) Paris Kanellakis has published a book on the O2 oodb, which is one of the major systems of its kind. (b) Stan Zdonik and his students have designed the InerActions global transaction mechanism for concurrency and recovery in multi-databases.

In graphics, Andy van Dam and John Hughes have developed the scripting language FLESH for time parameterized (4D) graphics and for 3D widgets employed in user interfaces. This technology is being exploited in the programming environment work of this project.

In operating systems, Tom Doeppner and his students have implemented a new mobile workstation email system (Theodora) and have designed a system (QuaHog) that presents a network of workstations as a loosely coupled parallel computer.

FY-93 PLANS

Realizing a prototype HPDE based on abstraction visualization. To the initial tools described above add a new heterogeneous oodb facility.

New parallel debugging tools that will be integrated into the HPDE. (Note that a new faculty member has joined the project, Robert Netzer, whose expertise is parallel debugging and scientific computing).

Design and implementation of efficient constraint programming languages and constraint query languages. Research planned on both user interface and efficient use of secondary storage.

Advances are expected in: 4D graphics technology, mobile workstation technology, design software for VLSI, and dynamic/parallel algorithms.

TECHNOLOGY TRANSITION

Considerable use is made by universities and research laboratories of the software prototypes developed through this (and its predecessor) DARPA efforts. The distribution of hardware has been centralized in the department and the responsible systems staff member is John Bazik jsb@cs.brown.edu 401-863-7624. Since June 1990 (when our accounting was put in place) there are the following statistics:

(1) FIELD programming environment of Steven Reiss at 389 sites. Most often used by the C++ community since it was the first reasonable debugging environment available. (2) IDYL dynamic loader of Steven Reiss at 209 sites. (3) GARDEN visual programming environment at 239 sites. (4) ENCORE oodb of Stanley Zdonik at 315 sites. (5) SPHIGS and SRGP graphics packages of Andy van Dam mostly used in conjunction with his book at 1444 sites and 1508 sites. (6) THREADS packages of Tom Doeppner 24 sites with UNIX licences and 371 sites for version that requires no special license. (7) FIX.TAR.Z is Pascal Van Hentenryck's new general abstract interpreter at 23 sites. In addition, there are a number of newer prototypes: e.g., a 4D modeling and animation package, the Theodora mobile workstation email system, parallel algorithm implementations for the CM, and graph layout packages.

DATE PREPARED

July 7 1992

SIGNIFICANT EVENTS

  1. ABSTRACTION VISUALIZATION IN THE FIELD PROGRAMMING ENVIRONMENT
    A practical programming environment is being developed by Steven Reiss and his students, based on the new notion of ``abstraction visualization''. Abstractions are the basis for most of the ways that programmers look at their programs, data, and execution. They can be defined and generated along several dimensions: based on syntax, based on the underlying semantics, based on execution, or based on data structures. Examples of abstractions include the call graph and class hierarchy provided by FIELD, program slices, a state transition view of a scanner, and a Petri net view of a distributed system.

    Initial development is complete of the underlying tools to enable abstraction visualization in the FIELD environment. This includes a 3-D layout package compatible with Motif, a hierarchical browser, a data structure to graphics mapping language, a C++ front end to provide the necessary semantic information, and specifications for a heterogeneous object-oriented database and query language for defining abstractions.

  2. PUBLICATION OF THE BOOK: ``BUILDING AN OBJECT-ORIENTED DATABASE SYSTEM: The Story of O2'' Francois Bancilhon, Claude Delobel, Paris Kanellakis (editors), Morgan Kaufmann, June 1992.
    This book provides an in-depth perspective of the new oodb technology through the description of a complete example prototype: the object-oriented database system O2. The exposition ranges from the data model through the system implementation to applications. The format of the book is a commented and edited collection of papers that cover all aspects of one of the better known prototype oodbs. This book can help researchers, database system designers, and users to assess the nature and potential of the new technology.
Up
John Bazik