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 four-year research effort (7/1/91--6/30/94 extended through FY95 to 6/30/95) that focuses on the implementation of efficient multiparadigm design environments and their use in the development of high-performance applications. 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 has three facets (for which separate bullets are provided in FY94 accomplishments and FY95 plans).

Research on programming environments for high-performance applications, in particular on new 3D visualization techniques, debugging techniques, and code optimization methods.
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.
Research on key supporting technologies, such as 3D graphics, distributed operating systems, and multidatabases.

PROGRESS

A number of key components of our HPDE prototype environment have been developed and enhanced; in particular the VALLEY system for 3D visualizations and the AARD trace generation facility. There has been considerable work on advanced languages (e.g., new object-oriented and functional languages, and the cc(FD) and NEWTON constraint-based prototypes), graphics support, and database tools (e.g., new indexing methods for constraints, multidatabases, extensible optimization EPOQ, and the AQUA data model). There has been significant progress on algorithmic methods, including dynamic algorithms, approximation algorithms for combinatorial optimization, parallel computing and hierarchical learning. A major accomplishment has been a breakthrough linear-time algorithm for minimum spanning trees.

PRODUCTS

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

FY94 ACCOMPLISHMENTS

On programming environments and debugging
Our efforts in programming environments have concentrated on the evolution of a system for program visualization. We have developed a framework for providing a variety of 3D visualizations and a mapping language that allows arbitrary objects to be visualized. The prototype VALLEY is close to completion.
We have continued to work on trace-based debugging, porting our trace package AARD to Solaris and experimenting with various strategies to compact the trace data by several orders of magnitude to make the concept practical. We have been working on porting FIELD to Solaris to increase its compatibility with the native toolkit.
We have begun a new effort on fragment integration. The idea here is to provide the facilities associated with data integration in a programming environment, i.e. hypertext linking, intelligent editing, smart system rebuilding, without having to use a central repository.
In the last year we have continued to make significant progress on developing new debugging and programming tools for large, complex, parallel (and sequential) systems.
Components and Constraints in Programming Environments
We have studied component-based software technology and concurrent models of interaction.
We have developed new constraint languages for linear constraints and nonlinear constraints (NEWTON).
We have developed new randomized, parallel and dynamic algorithms for approximation problems and for computational geometry problems.
We have developed a model for multi-grained parallelism that addresses the question of which architectures are best for problems that express both serial and parallel behavior.
We have studied algorithms for planning in very large stochastic domains and controlling partially observable Markov decision processes.
Graphics and Database Support for Programming Environments
The Graphics Group continued research in new 3D user interface tools. Collaborating with research at NASA Ames, we have developed several 3D time-varying fluid-flow visualization tools: the streamline, particle path, ribbon, hedgehog, colorpicker, rake, and isosurface widgets. These tools will help scientists at NASA study fluid flows in a virtual-reality environment. We also developed a technique for annotating 3D time-varying data fields that lets scientists embed annotation markers in the same 3D space in which the flow data resides.
We are developing the Thread-Monitor Library, a system for monitoring Solaris-threads programs.
We continued our work on Interactions, an open, nested, flexible transaction model for multidatabases.
We also continued the design of an open, extensible query optimizer called EPOQ. As part of this effort, we have been exploring the extension of an object-oriented query algebra to include queries on lists and trees. We have completed an initial design of such a language in the context of the AQUA data model.

FY-95 PLANS

These plans fall under the same three headings as the approach above.

Programming Environments and Debugging
- Completion of the prototype 3D visualization tools, VALLEY. (A first version is close to release.) Testing and experimentation with VALLEY on software engineering and CAD problems are planned.
- Implementation of a query language for 3D software visualization and of a graph-drawing system that incorporates efficient algorithms and user-defined constraints.
- A new distribution of the FIELD environment, incorporating many of the results of our research.
- Instrumentation strategies for such problems as collecting run-time data necessary for visualization and performance measurement.
- Developing algorithms useful in debugging parallel systems and in checkpointing real-time systems.
Components and Constraints in Programming Environments
- Continue exploration of interfaces and interaction as a first-class mechanism for computing and development of models of interaction as a semantic basis for component-based software technology.
- Development of a new CLP (constraint logic programming) language called Newton that allows arbitrary constraints over reals and integers. This language will be used for various operations research applications that require global and combinatorial optimization.
- Design and prototype implementation of a constraint database language for spatial applications.
- Development of efficient algorithms for external-memory (I/O) computations for applications in spatial and temporal databases.
- Improved algorithms for solving hard combinatorial-optimization problems.
- Exploration of requirements on code to facilitate exploitation of parallelism and memory hierarchies.
Graphics and Database Support for Programming Environments
- Continued development of 3D user interfaces for scientific applications, geometric modeling, and virtual reality.
- Development of a formal design methodology for 3D user interfaces.
- Completion of the Thread-Monitor Library, a system for monitoring Solaris-Threads programs.
- Development of a prototype extensible optimizer for the AQUA object-oriented data model.
- Testing and evaluation of optimizer in using a variety of cost models.

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 software 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:

FIELD programming environment of Steven Reiss at 635 sites. Most often used by the C++ community since it was the first reasonable debugging environment available. FIELD has also been licensed by DEC and is being distributed by them as DEC FUSE.
IDYL dynamic loader of Steven Reiss at 243 sites.
GARDEN visual programming environment of Steven Reiss at 317 sites.
ENCORE oodb of Stanley Zdonik at 553 sites.
SPHIGS and SRGP graphics packages of Andy van Dam mostly used in conjunction with his book at 2831 sites and 3089 sites.
THREADS packages of Tom Doeppner 30 sites with UNIX licenses and 535 sites for version that requires no special license.
FIX is Pascal Van Hentenryck's new general abstract interpreter at 68 sites.

PUBLICATIONS

N.M. Amato and F.P. Preparata, `A time-optimal parallel algorithm for 3D convex hulls', Algorithmica.

P. Bertolazzi, G. Di Battista, C. Mannino and R. Tamassia, Optimal upward planarity testing of single-source digraphs', Proc. European Symp., Lect. Notes in CS, vol. 726, Springer-Verlag.

J.D. Boissonnat, O. Devillers, L. Donati, and F.P. Preparata, `Motion planning of legged robots: the spider robot problem', Internat. J. Computation Geometry and App.

Anthony R. Cassandra, Leslie Pack Kaelbling and Michael L. Littman, `Acting optimally in partially observable stochastic domains', Proc. 12th National Conference on AI.

Tiziana Catarci and Isabel F. Cruz, `On expressing stratified Datalog', Second ICLP-Workshop on Deductive Databases and Logic Programming.

Y.J. Chiang, F.P. Preparata, and R. Tamassia, `A unified approach to dynamic point location, ray shooting, and shortest paths in planar maps', SIAM Journal on Computing.

R. Cole, P. N. Klein and R. E. Tarjan, `A linear-work parallel algorithm for finding a minimum spanning tree', Proc. 6th ACM Symp. on Parallel Algorithms and Architectures.

R. F. Cohen and Roberto Tamassia, `Combine and conquer: a general technique for dynamic algorithms', Proc. European Symp., Lect. Notes in CS, vol. 726, Springer-Verlag.

A. Cortesi, B. Le Charlier and P. Van Hentenryck, `Combinations of abstract domains for logic programming', Proc. ACM-SIGPLAN Symposium on Principles of Programming Languages (POPL-94).

Isabel F. Cruz, `User-defined visual query languages', IEEE 10th International Symposium on Visual Languages, VL '94.

Isabel F. Cruz, `Expressing constraints for data display specification: a visual approach', Brown University CS Techreport 93-57.

Isabel F. Cruz, `User-defined visual languages for querying data', Brown University CS Techreport 93-58.

O. Degimbe, B. Le Charlier, L. Olivier and P. Van Hentenryck, `Practical efficiency of three general-purpose fixpoint algorithms applied to the abstract interpretation of Prolog', International Workshop on Static Analysis (WSA-93).

T. W. Doeppner, `The thread-monitor library: a system for monitoring Solaris-threads programs', Brown University CS Technical Report 93-53.

T. W. Doeppner, `Open software: UNIX, DCE, and competitors', Proc. CERN School of Computing, 1994; Brown University CS Technical Report 93-59.

A. Garg and R. Tamassia, `Advances in graph drawing', Proc. CIAC'94, Lect. Notes in CS, vol. 778, Springer-Verlag.

S. Gottschalk and J. F. Hughes, `Autocalibration for virtual environment tracking hardware', Proc. SIGGRAPH '93.

Gerd Hillebrand and Paris Kanellakis, `Functional database query languages as typed lambda calculi of fixed order', Proc. ACM PODS 1994.

Gerd Hillebrand, Paris Kanellakis and Harry Mairson, `Database query languages embedded in the typed lambda calculus', invited to special issue of JCSS on IEEE LICS93.

Gerd Hillebrand, Paris Kanellakis and Harry Mairson, `An analysis of the core-ML language: expressive power and type reconstruction', Proc. ICALP 1994.

P. M. Hubbard, `Interactive collision detection', IEEE Symposium on Research Frontiers in Virtual Reality '93.

Leslie Pack Kaelbling and R. Ashar, `Learning hierarchies in stochastic domains', 4th Wkshp on Comp. Learning Theory and Natural Learning Systems.

Paris Kanellakis, Sridhar Ramaswamy, Darren Vengroff, and Jeffrey Vitter, `Indexing for data models with constraints and classes', Proc. 12th ACM PODS, 1993; invited to appear in the special issue of JCSS for PODS 1993.

Paris Kanellakis and Dina Goldin, `Constraint programming and database query languages', Proc. Theoretical Aspects of Computer Software TACS 1994.

G. Kant, G. Liotta, R. Tamassia and I.G. Tollis, `Area requirement of visibility representations of trees', Proc. 5th Canadian Conf. on Computational Geometry.

P. N. Klein, S. Rao, M. Rauch, and S. Subramanian, `Faster shortest-path algorithms for planar graphs', Proc. 26th Symp. on Theory of Computing.

P. N. Klein and S. Subramanian, `A linear-processor, polylog-time algorithm for shortest paths in planar graphs', Proc. 34th Symp. on Foundations of Computer Science.

P. N. Klein and R. E. Tarjan, `A randomized linear-time algorithm for finding a minimum spanning tree', Journal of the ACM, Proc. 26th Symp. on Theory of Computing.

P. N. Klein, A. K. Agrawal, and R. Ravi, `When trees collide: an approximation algorithm for the generalized Steiner tree problem on networks', SIAM Journal Comput.

P. N. Klein, S. Plotkin, C. Stein and E. Tardos, `Faster approximation algorithms for the unit capacity concurrent flow problem with applications to routing and finding sparse cuts', SIAM Journal Comput.

P. N. Klein, `Efficient parallel algorithms for chordal graphs', SIAM Journal Comput.

B. Le Charlier and P. Van Hentenryck, `Experimental evaluation of a generic abstract interpretation algorithm for Prolog', ACM Transactions on Programming Languages and Systems.

T. Leung, et al., `The AQUA data model and algebra', Proc. 4th Int. Workshop on Database Prog. Lang. '93.

H.-I. Lu, P. N. Klein, and R. H. B. Netzer, `Detecting race conditions in parallel programs that use one semaphore' Workshop on Algorithms and Data Structures '93.

K. Miriyala, S.W. Hornick and R. Tamassia, `An incremental approach to aesthetic graph layout', Proc. Int. Workshop on Computer-Aided Software Engineering CASE'93.

G. Mitchell, U. Dayal, and S. Zdonik, `Control of an extensible query optimizer: a planning-based approach', Proc. VLDB Conference '93.

R. H. B. Netzer and S. K. Damodaran-Kamal, `Accurate race condition detection for message-passing programs', Brown University Technical Report.

R. H. B. Netzer, S. Subramanian, and J. Xu, `Critical-path-based message logging for incremental replay of message-passing programs', IEEE International Conf. on Distributed Computing Systems '94.

R. H. B. Netzer and M. H. Weaver, `Optimal tracing and incremental reexecution for debugging long-running programs', Proc. ACM SIGPLAN Conf. Prog. Lang. Des. and Imp., 1994.

R. H. B. Netzer and J. Xu, `Necessary and sufficient conditions for consistent global snapshots', IEEE Trans. on Parallel and Dist. Systems, to appear, 1994.

R. H. B. Netzer, `Trace size vs. parallelism in trace-and-replay debugging of shared-memory programs', in Lecture Notes in Computer Science 768.

R. H. B. Netzer and J. Xu, `Adaptive message logging for incremental replay of message-passing programs', IEEE Parallel and Distributed Technology '93.

Ann Nicholson and Leslie Pack Kaelbling, `Toward approximate planning in very large state spaces', Proc. AAAI Spring Symp. on Decision-Theoretic Planning.

M. H. Nodine, `Supporting long-running tasks on an evolving multidatabase using interactions and events', Proc. 2nd Int. Conf. on Parallel and Dist. Info. Syst. '93.

M. H. Nodine and S. B. Zdonik, `Automating compensation in a multidatabase', Proc. Hawaii Int. Conf. on Systems Science '94.

M. H. Nodine, N. Nakos, and S. B. Zdonik, `Specifying flexible tasks in a multidatabase', Proc. 2nd Int. Conf. on Cooperative Info. Sys. '94.

V.Y. Pan and F.P. Preparata, `Work-preserving speed-up of parallel matrix computations', SIAM Journal on Computing.

A. Pietracaprina and F.P. Preparata, `A practical constructive scheme for deterministic shared-memory access', Proc. ACM 1993, SPAA.

F.P. Preparata and J.S. Vitter, `A simplified technique for hidden-line elimination in terrains', International Computational Geometry and Applications.

V. Ramachandran and P. Van Hentenryck, `Incremental algorithms for constraint solving and entailment over rational trees', Proc. 13th Conference on Foundations of Software Technology and Theoretical Computer Science.

Sridhar Ramaswamy and Sairam Subramanian, `Path caching: a technique for optimal external searching', Proc. 13th ACM PODS, 1993.

S. P. Reiss, `A framework for abstract 3-D visualization', Proc. Visual Languages '93.

S. P. Reiss, `Presentation and editing of structured 3-D graphics', Proc. HCI '93.

Steven P. Reiss and Isabel F. Cruz, `Practical software visualization', Software Visualization (SIGCHI) Workshop.

M. Sarkar, S. S. Snibbe, O J. Tversky, and S. P. Reiss, `Stretching the rubber sheet: a metaphor for viewing large layouts on small screens', Proc. ACM SIGGRAPH UIST '93.

J.E. Savage, A model for multigrained parallelism, 6th Annl. ACM Symp. on Parallel Algorithms and Architectures.

B. Subramanian et al., `Ordered types in the AQUA data model', Proc. 4th Int. Workshop on Database Prog. Lang. '93.

R. Tamassia and I.G. Tollis, `Reachability in planar digraphs with one source and one sink', Theoretical Computer Science A, vol. 119.

P. Van Hentenryck, `Scheduling and packing in the constraint language cc(FD)', in Intelligent Scheduling, Morgan Kaufman.

P. Van Hentenryck and V. Ramachandran, `Backtracking without trailing in CLP(Rlin)', Proc. ACM-SIGPLAN Conference on Programming Language Design and Implementation (PLDI-94).

P. Van Hentenryck, A. Cortesi and B. Le Charlier, `Type analysis of Prolog using type graphs', Proc. ACM-SIGPLAN Conference on Programming Language Design and Implementation (PLDI-94).

P. Van Hentenryck, O. Degimbe, B. Le Charlier and L. Olivier, `The impact of granularity in abstract interpretation of Prolog', International Workshop on Static Analysis (WSA-93).

Peter Wegner, `Computer literacy for undergraduates: a computer literacy approach', Brown University CS Techreport 94-21.

Peter Wegner, `Models and paradigms of interaction', Springer Verlag LNCS Monograph, also Brown University CS Techreport 93-48.

Peter Wegner, `Towards component-based software technology', Brown University CS Techreport 93-11.

Peter Wegner, `Beyond computable functions, or escape from the Turing tarpit', Brown University CS Techreport, TR 94-01; to appear in Proc. DIMACS Workshop on Parallel Specification.

Peter Wegner, `Reasoning, modeling and component-based technology', Proc. 4th Int. Conf. of Logic Programming and Automatic Programming', Springer Verlag.

Peter Wegner, Gul Agha and Akinori Yonezawa (editors), `Research directions in concurrent object-oriented programming', The MIT Press.

Peter Wegner, `Tradeoffs between reasoning and modeling', in `Research directions in concurrent object-oriented programming', ed. Wegner, Agha and Yonezawa, The MIT Press.

Peter Wegner, `Dimensions of object-oriented modeling', IEEE Computer.

Peter Wegner, `Concepts and paradigms of object-oriented programming (Japanese translation)'.

Peter Wegner, `New directions in the introductory computer science curriculum', Proc. 1994 ACM Computer Science Conference.

J. Xu and R. H. B. Netzer, `Adaptive independent checkpointing for reducing rollback propagation', IEEE Symposium on Parallel and Distributed Processing '94.

R. C. Zeleznik, K. P. Herndon, D. C. Robbins, N. Huang, T. Meyer, N. Parker, and J. F. Hughes, `An interactive 3D toolkit for constructing 3D widgets', Proc. SIGGRAPH '93.

S. Zdonik, `Incremental database systems: databases from the ground up', Proc. ACM SIGMOD '93.

Significant Events

3D-VISUALIZATION TOOLS: VALLEY

The development of Steve Reiss' prototype 3-D visualization tool, VALLEY, is almost at a point where it can be released. We hope to make VALLEY available by the end of the summer. To experiment with this system, we have developed a prototype front end for static program visualization (i.e. call graphs, class hierarchy, variable usage) and another for visualizing semantic networks. We have been working on making the system practical and have used it to visualize representations with over 8,000 nodes and 45,000 arcs.

A LINEAR-TIME ALGORITHM FOR MINIMUM SPANNING TREES

Klein (Brown) and Tarjan (Princeton) have discovered a randomized linear-time algorithm for finding minimum spanning trees. They have also adapted these ideas for parallel implementation, obtaining the first parallel algorithm for finding minimum spanning trees that does only linear work.

DATE PREPARED

1 July 1994

John Bazik