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

TEAM MEMBERS
Thomas W. Doeppner
Maurice P. Herlihy
John F. Hughes
Leslie Kaelbling
Philip N. Klein
Robert H.B. Netzer
Mariane Nodine
Franco P. Preparata
John E. Savage
Roberto Tamassia
Andries van Dam
Pascal Van Hentenryck
Peter Wegner
Stanley B. Zdonik

TITLE OF EFFORT
High Performance Design Environments (HPDE)

EXECUTIVE SUMMARY PARAGRAPH

High Performance Design Environments (HPDE) is a research effort (7/1/91--6/30/94 extended to 6/30/96), which focuses on the implementation of efficient multiparadigm design environments and on their use in the development of high performance applications.

OBJECTIVE

This effort will lead to a new generation of open software environments (extending systems such as FIELD) with 3D program visualization tools, advanced languages, parallel debugging, and object store support. The new environments will facilitate the programming of high performance applications in: graphics, CAD, operations research and scientific computing.

APPROACH

Our approach involves three facets:

  1. Research on programming environments for high performance applications, in particular on new 3D visualization techniques, debugging techniques, and code optimization methods.
  2. Research on enhancing the performance of specific programming paradigms and on linking them with the prototype environment under development (in particular concurrent constraint-based and concurrent object-oriented paradigms). This is coupled with the study of dynamic, approximate, and parallel algorithms.
  3. Research on key supporting technologies, such as 3D graphics, distributed operating systems, and multidatabases.

PROGRESS

We have combined in one experimental environment: control and fragment integration with a common editor appoarch. This is a considerable extension of the FIELD environments towards the objectives of HPDE. There has been considerable work on advanced languages, e.g., the NEWTON constraint-based prototype, on graphics support, and on database tools. In particular, we have developed a new method for indexing objects in a class hierarchy that has wide applicability and improves on existing commercial technology. Another important technology development is broadcast disks: a new technique for delivering data to clients in asymmetric communication environments.

PRODUCTS

The FIELD environment has been the basis for a number of commercial products from DEC, Sun and HP.

FY95 ACCOMPLISHMENTS

A new prototype programming environment based on an inexpensive data integration mechanism, called ``fragment integration''. The environment expands upon the concepts of ``control integration'', pioneered in FIELD, by offering a database that contains information derived from the various software artifacts. The environment utilizes a ``common editor'' based on the commercial word-processing system FrameMaker to provide either direct or live-link based access to the different software tools used to manage software artifacts. (Also, the completed description of the FIELD environment was published as a book).

The development of Trim, an interactive 3D graphics research testbed. It uses the interpreted scripting language called FLESH, developed previously as part of this effort.

A new constraint language (Newton) and its program to solve nonlinear constraint systems over the reals. The Newton constraint solver outperforms other methods in the area (continuation and interval methods) on most benchmarks. Newton will be the basis for the next generation of constraint languages.

A new method for indexing objects in a class hierarchy, according to a common attribute. This method, called indexing by class-division, is based on standard B-tree technology and offers an order of magnitude performance improvement over previous techniques (used in all commercial oodbs).

The development of broadcast disk technology. Broadcast disks are a technique for delivering data to clients in asymmetric communication environments. The technique is based on the notion of cyclical broadcast of data in advance of any client request. We have developed a scheme for structuring such a disk in which pages can be broadcast with different frequencies, and we have designed cache management policies that are closely coupled with the broadcast program.

FY 96 EVENTS

We expect to continue the development of an environment with control, fragment and common editor integration over the coming year. Our current system is implemented as a set of tools and an API for FrameMaker. Once the system becomes stable and usable by other researchers, probably by the end of the calendar year, we hope to make an experimental version available to other researchers via ftp.

We plan to extend our previous work on 3D software visualization to provide a front end for viewing a wide variety of information about the static and dynamic behaviour of a system. This work will concentrate on improving the quality of the presentations, implementing new information sources that show promise as visualization sources, and developing a common visual front end for defining queries and presentations simultaneously.

We plan to continue our constraint programming language, 3D graphics and database infrastructure work. In particular, the broadcast disk technology could have both military and commercial spin-offs, because of its impact on mobile computing applications.

PUBLICATIONS

S. Achyra, R. Alosno, M. Franklin, S. Zdonik. Broadcast Disks: Data Management for Asymmetric Communication Environments. ACM SIGMOD Symposium on the Management of Data, San Jose CA USA, May 1995.

J. Aspnes, M.P. Herlihy, and N. Shavit. Counting Networks. Journal of the ACM, 41(5): pp 1020--1048, September 1994.

F. Benhamou, D. McAllester, and P. Van Hentenryck CLP(Intervals) Revisited Proceedings of the International Logic Programming Symposium (ILPS-94), Ithaca, NY, November 1994

G. Bilardi, F.P. Preparata. Horizons of Parallel Computation. Journal of Parallel and Distributed Computing, 27,2,172-182, June 1995.

G. Bilardi, F.P. Preparata. Upper Bounds to Processor-Time Tradeoffs under Bounded-Speed Message Propagation. Proceedings - SPAA 95, 7th Annual Symposium on Parallel Algorithms & Architectures, July 16-18, 1995

Y.-J. Chiang, M.T. Goodrich, E.F. Grove, R. Tamassia, D.E. Vengroff and J.S. Vitter. External-Memory Graph Algorithms. Proc. ACM-SIAM Symp. on Discrete Algorithms (1995).

M. Das, T. Reps, and P. Van Hentenryck Semantic Foundations of Binding-Time Analysis for Imperative Programs ACM Symposium on Partial Evaluation and Semantic-based Program Manipulation (PEPM-95), La Jolla, CA, June 1995.

G. Di Battista, A. Garg, G. Liotta, R. Tamassia, E. Tassinari and F. Vargiu. An Experimental Comparison of Three Graph Drawing Algorithms. Proc. ACM Symp. on Computational Geometry (1995).

P.F. Fischer, F.P. Preparata, J.E. Savage. Generalized Scans and Tri-Diagonal Systems. Procs. 12th Annl. Symp. on Th. Aspects of Computer Science.

M.P. Herlihy and S. Rajsbaum. Set Consensus Using Arbitrary Objects. 12th Annual ACM Symposium on Principles of Distributed Systems

K.P. Herndon, T. Meyer. 3D Widgets for Exploratory Scientific Visualization. Proceedings of UIST '94, ACM SIGGRAPH, November, 1994, pp. 69-70.

P.C. Kanellakis, D. Michailidis, A.A. Shvartsman. Concurrency = Fault-Tolerance in Parallel Computation. 5th International Conference on Concurrency Theory, in LNCS 836, Uppsala Sweden, pp. 242--266, August 1994.

P.C. Kanellakis, G. Hillebrand, H.G. Mairson. An Analysis of Core-ML: Expressive Power and Type Inference. International Colloquium on Automata, Languages and Programming, in LNCS 820, Jerusalem Israel, pp. 83--105, July 1994.

P. Klein, D. Karger, R.E. Tarjan A randomized linear-time algorithm for finding a minimum spanning tree. Journal of the ACM, Vol. 42 (1995), pp. 321-328.

M. Loughlin, J.F. Hughes. An Annotation system for 3D Fluid Flow Visualization, Proceedings of Visualization '94, pp. 273-279, Washington, DC, Oct. 1994.

P. B. Miltersen, S. Subramanian, J. S. Vitter, R. Tamassia. Complexity Models for Incremental Computation. Theoretical Computer Science, vol. 130, pp. 203-236 (1994).

S. Ramaswamy, P.C., Kanellakis. OODB Indexing by Class-Division. ACM SIGMOD Symposium on the Management of Data, San Jose CA USA, May 1995.

S. P. Reiss. 3D visualization of Program Information. Graph Drawing '94.

S. P. Reiss. Fragments: a mechanism for low cost data integration. Tech Report, Brown University Dept of Computer Science

S. P. Reiss. An engine for the 3D visualization of program information J. Visual Languages (to appear 95)

S. P. Reiss FIELD: A Friendly Integrated Environment for Learning and Development Kluwer, 1994.

M.P. Stevens, R.C. Zeleznik, J.F. Hughes. An Architecture for an Extensible 3D Interface Toolkit. Proceedings of UIST '94, ACM SIGGRAPH, November, 1994.

S. Subramanian and T. Leung and S. Vandenberg and S. Zdonik The AQUA Approach to Querying Lists and Trees in Object-Oriented Databases Proceedings of the International Conference on Data Engineering

P. Van Hentenryck, D. McAllester, and D. Kapur Solving Polynomial Systems Using a Branch and Prune Approach SIAM Journal on Numerical Analysis (To Appear)

P. Van Hentenryck, A. Cortesi, and B. Le Charlier Evaluation of the Domain Prop Journal of Logic Programming, 22(3):179-208, March 1995

P. Van Hentenryck, A. Cortesi, and B. Le Charlier Type Analysis of Prolog using Type Graphs Journal of Logic Programming, 22(3):179-208, March 1995

P. Wegner. Interaction as a framework for Empirical Computer Science, Computing Surveys, March 1995.

TECHNOLOGY TRANSITION

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

SIGNIFICANT EVENTS

INTEGRATION IN PROGRAMMING ENVIRONMENTS: CONTROL, FRAGMENTS, COMMON EDITOR

Over the past year Steve Reiss and his students have been developing a prototype of a new programming environment based on an inexpensive data integration mechanism called fragment integration. The environment expands upon the concepts of control integration, pioneered in FIELD, by offering a database that contains information derived from the various software artifacts. This information is organized in terms of fragments, semantically significant portions of the original artifacts, and includes the information to identify and associate fragments based on syntactic and semantic information. The environment utilizes a common editor based on the commercial word-processing system FrameMaker to provide either direct or live-link based access to the different software tools used to manage different software artifacts. In addition to providing a central framework for accessing all software artifacts, the environment allows us to establish both static and dynamic links among the artifacts, preserves openness in terms of languages and support for existing tools and systems, and supports the notion of a fragment file. Fragment files contain sets of related fragments that have been extracted from their original source file. When they are saved, the modified fragments are inserted into the original locations. The overall approach is a significant extension of the FIELD programming environment.

BROADCAST DISKS

Broadcast disks are a technique developed by Stan Zdonik and his co-authors for delivering data to clients in asymmetric communication environments. The technique is based on the notion of cyclical broadcast of data in advance of any client request. Zdonik and his co-authors has developed a scheme for structuring such a disk in which pages can be broadcast with different frequencies, and has designed cache management policies that are closely coupled with the broadcast program. These results should generalize to account for update in a broadcast-based environment (this is work in progress). A working partnership with Intel and IBM has been developed in this area.

DATE PREPARED: July 7, 1995

Up Previous
Kathy Kirman