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 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, 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 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 graphics, distributed operating systems, and multidatabases.

PROGRESS

A number of key components of our HPDE prototype environment have been developed: in particular the PLUM system for 3D visualizations and the VMON analysis and debugging component. There has been considerable work on advanced languages (e.g., new object-oriented and functional languages, and the CCEL and cc(FD) constraint-based prototypes), on parallel debugging support, on graphics support, and on database tools (e.g., the MONGREL multidatabase and the EPOQ optimizer). There has been significant progress on algorithmic methods including: dynamic algorithms, approximation algorithms for combinatorial optimization, parallel computing and hierarchical learning.

FY93 ACCOMPLISHMENTS

Steven Reiss and his students have been working on the framework and tools for a new prototype HPDE. They have developed three prototype systems over the past year. (a) The first, PLUM, is designed as the backbone of the program visualization efforts. This new 3D visualization tool is one of the significant events of this year's work (see first significant event below). (b) The second prototype system, VMON, is designed to provide run time information for program visualization, analysis, and debugging. The system dynamically modifies the executable and its shared libraries to generate, store and analyze trace information. The implementation provides memory typestate checking ala Purify and linkage to the FIELD programming environment for fast function and line tracing. (c) The third is the design and implementation of the language CCEL, a constraint-based version of C++. The relevant publications in this area are [12,30,34,42-45].

Much has been accomplished on debugging tools, operating system support and optimization techniques that are critical for HPDE efficiency. (a) In debugging tools, Robert Netzer and his students have addressed tracing to support execution replay in both shared-memory and message-passing systems. The techniques reduce trace requirements by orders of magnitude over past work. The relevant publications are [36-37,67]. (b) In operating systems support, Tom Doeppner has improved the Brown Threads package so that its I/O efficiency rivals that of OS-supported threads packages. (c) In optimization techniques, Stan Zdonik and his students have designed (and are currently testing) the extensible optimization architecture EPOQ for heterogeneous oodbs [31,35,50].

In the area of languages: (a) Peter Wegner has published extensively on object-oriented modeling (both books and articles) with particular emphasis on concurrency and reactiveness [1,51,57-66]. He has, (in an article with Ceri and Wiederhold) formalized the notion of megaprogramming. He is developing a framework for component-based systems, which are interactive, open, distributed, and suited to modeling changing application domains. (b) In the area of constraint-based languages, Pascal Van Hentenryck has completed the final design and implementation of the constraint language cc(FD) (see second significant event below). Extensive research was conducted on constraint programming concepts see [8-9,11,13,19,28-29,53-56].

In the area of databases: (a) Paris Kanellakis and his students developed a new framework for functional query languages in databases (see third significant event below) [18]. (b) Paris Kanellakis, Jeff Vitter and their students developed new indexing algorithms with improved I/O performance [22]. (c) Jeff Vitter and his students have new prefetching techniques, with applications to CAD and very promising benchmark performance [10]. (d) Stan Zdonik and his students have augmented the Interactions transaction mechanism for concurrency and recovery in multidatabases with new reactive features [38-39,68].

In the area of graphics: Andries van Dam, John Hughes and their graphics group made the UGA 3D interactive illustration development environment more powerful, flexible, and usable through significant enhancements to the FLESH scripting language. They have developed an interactive toolkit to facilitate the visual programming of the geometry and behavior of interactive 3D user interfaces. In the virtual environments area, the graphics group has also been involved in developing algorithms and software for improved tracking technology. In related projects, the graphics group began investigating 3D user interfaces for virtual environments (in conjunction with NASA's Virtual Windtunnel project) and developing multiprocessor graphics applications. The relevant publications are [7,16,17,52,69].

Much has been accomplished in new algorithmic techniques which have applications to HPDE. (a) John Savage completed two projects in the last year. The first is a study of space-time tradeoffs in multi-level memory hierarchies [48], and the second is a formalization of heterogeneous supercomputing called the Mesh SuperHet model with tight performance bounds for many key problems [49]. (b) Roberto Tamassia and his students have developed new dynamic algorithms for basic geometric problems such as point location and ray shooting. They have developed new shortest path algorithms and new notions of incremental complexity [2-6,14-15,46-47]. (c) Philip Klein and his students have developed new algorithms for approximation problems in network optimization [23-27,32,40-41]. He has also collaborated with Robert Netzer on some new debugging algorithms [33]. (d) Leslie Kaelbling has developed the first hierarchical algorithm for learning from reinforcement in stochastic domains [20-21].

FY-94 PLANS

Realizing a prototype HPDE, which will integrate tools such as the PLUM, VMON, CCEL systems described above and an object store.

New parallel debugging tools that will be integrated into the HPDE. OSF's DCE will be used to experiment with distributed object-oriented programming.

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, mobile workstation technology, multidatabases, approximation and dynamic/parallel algorithms.

PUBLICATIONS

For the list of 69 publications partly supported see appendix.

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: (1) FIELD programming environment of Steven Reiss at 571 sites. (2) IDYL dynamic loader of Steven Reiss at 265 sites. (3) GARDEN visual programming environment at 255 sites. (4) ENCORE oodb of Stanley Zdonik at 454 sites. (5) SPHIGS and SRGP graphics packages of Andy van Dam mostly used in conjunction with his book at 1991 sites and 2129 sites. (6) THREADS packages of Tom Doeppner 30 sites with UNIX licenses and 424 sites for version that requires no special license. (7) FIX is Pascal Van Hentenryck's new general abstract interpreter at 41 sites. (8) The AARD memory analysis debugging tool 262 sites.
DATE PREPARED
July 2 1993

APPENDIX: PUBLICATION LIST

  1. G. Agha, P. Wegner, and A. Yonezawa (eds.). "Research Directions in Concurrent Object-Oriented Programming." MIT Press 1993.
  2. P. Bertolazzi, R.F. Cohen, G. Di Battista, R. Tamassia, and I.G. Tollis. "How to Draw a Series-Parallel Digraph." Proceedings of the Workshop on Algorithm Theory (SWAT '92), Springer LNCS 621, 1992.
  3. Y.-J. Chiang and R. Tamassia. "Dynamization of the Trapezoid Method for Planar Point Location in Monotone Subdivisions." Int. J. of Computational Geometry & Applications, 1992.
  4. Y.-J. Chiang, F.P. Preparata, and R. Tamassia. "A Unified Approach to Dynamic Point Location, Ray Shooting and Shortest Paths in Planar Maps." Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 1993.
  5. R.F. Cohen, G. Di Battista, A. Kanevsky, and R. Tamassia. "Reinventing the Wheel: An Optimal Data Structure for Connectivity Queries." Proceedings of the 25th ACM Symposium on the Theory of Computing (STOC '93), San Diego, April 1993.
  6. R.F. Cohen, S. Sairam, R. Tamassia, and J.S. Vitter. "Dynamic Algorithms for Optimization Problems in Bounded Tree-Width Graphs." Proceedings of the Third Integer Programming and Combinatorial Optimization Conference, 1993.
  7. D. Brookshire Conner and Andries van Dam. "Sharing Between Graphical Objects Using Delegation." Proceedings of the Third Eurographics Workshop on Object-Oriented Graphics, October 1992.
  8. Isabel F. Cruz. "Using a Visual Constraint Language for Data Display Specification." Proceedings of the First Workshop on Principles and Practice of Constraint Programming (PPCP '93), Newport, April 1993.
  9. Isabel F. Cruz, Roberto Tamassia, and Pascal Van Hentenryck. "A Visual Approach to Graph Drawing." To appear in Proceedings of Graph Drawing '93, Paris, September 1993.
  10. K. M. Curewitz, P. Krishnan, and J. S. Vitter. "Practical Prefetching via Data Compression." Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data (SIGMOD '93), Washington, May 1993.
  11. O. Degimbe, B. Le Charlier, L. Michel, and P. Van Hentenryck. "Practical Efficiency of Three General Purpose Fixpoint ALgorithms Applied to the Abstract Interpretation of Prolog." Proc. WSA '93, Padova, September 1993.
  12. Carolyn K. Duby, Scott Meyers, and Steven P. Reiss. "Constraining the Structure and Style of Object-Oriented Programs." Proceedings of the First Workshop on Principles and Practice of Constraint Programming (PPCP '93), Newport, April 1993.
  13. V. Englebert, B. Le Charlier, D. Roland, and P. Van Hentenryck. "Generic Abstract Interpretation Algorithms for Prolog: Two Optimization Techniques and Their Experimental Evaluation." Software Practice and Experience, 23(4), April 1993.
  14. A. Garg, M.T. Goodrich and R. Tamassia. "Area-Efficient Upward Tree Drawings." Proceedings of the ACM Symposium on Computational Geometry, 1993.
  15. M.T. Goodrich and R. Tamassia. "Dynamic Ray Shooting and Shortest Paths via Balanced Geodesic Triangulations." Proceedings of the ACM Symposium on Computational Geometry, 1993.
  16. Stefan Gottschalk and John F. Hughes. "Autocalibration for Virtual Environments Tracking Hardware." To appear in Proc. SIGGRAPH '93, August 1993.
  17. Kenneth P. Herndon, Robert C. Zeleznik, Daniel C. Robbins, D. Brookshire Conner, Scott S. Snibbe, and Andries van Dam. "Interactive Shadows." Proc. UIST '92, November 1992.
  18. G. Hillebrand, P.C. Kanellakis, and H.G. Mairson. "Database Query Languages Embedded in the Typed Lambda Calculus." Proceedings of the Eighth IEEE Symposium on Logic in Computer Science (LICS '93), Montreal, June 1993.
  19. J.L. Imbert and P. Van Hentenryck. "Efficient Handling of Disequations in Linear Rational Arithmetic." To appear in "Constraint Logic Programming: Selected Research," MIT Press, 1993.
  20. Leslie Pack Kaelbling. "Hierarchical Reinforcement Learning: Preliminary Results." Proceedings of the Tenth International Conference on Machine Learning, 1993.
  21. Leslie Pack Kaelbling. "Learning to Achieve Goals." Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence, 1993.
  22. P.C. Kanellakis, S. Ramaswamy, D.E. Vengroff, and J.S. Vitter. "Indexing for Data Models with Constraints and Classes." Proceedings of the Twelfth ACM Symposium on the Principles of Database Systems (PODS '93), Washington, May 1993.
  23. Philip N. Klein, Serge Plotkin, and Satish Rao. "Excluded Minors, Network Decomposition, and Multicommodity Flow." Proceedings of the 25th ACM Symposium on Theory of Computing (STOC '93), San Diego, April 1993.
  24. Philip N. Klein and R. Ravi. "A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees." Proceedings of the Third Symposium on Integer Programming and Combinatorial Optimization, 1993.
  25. Philip N. Klein and R. Ravi. "When Cycles Collapse: A General Approximation Technique for Constrained Two-Connectivity Problems." Proceedings of the Third Symposium on Integer Programming and Combinatorial Optimization, 1993.
  26. Philip N. Klein and Sairam Sairam. "Fully Dynamic Approximation Schemes for Shortest Path Problems in Planar Graphs." To appear in Proceedings of the Workshop on Algorithms and Data Structures (WADS '93), 1993.
  27. Philip N. Klein. "On Gazit and Miller's Parallel Algorithm for Planar Separators: Achieving Greater Efficiency Through Random Sampling." To appear in Proceedings of the Fifth ACM Symposium on Parallel Algorithms and Architectures, 1993.
  28. B. Le Charlier and P. Van Hentenryck. "Reexecution in Abstract Interpretation of Prolog." International Joint Conference and Symposium on Logic Programming, Washington, November 1992.
  29. B. Le Charlier and P. Van Hentenryck. "Experimental Evaluation of an Abstract Interpretation Algorithm for Prolog." To appear in ACM Transactions on Programming Languages and Systems.
  30. Moises Lejter, Scott Meyers, and Steven P. Reiss. "Support for Maintaining Object-Oriented Programs." IEEE Transactions on Software Engineering, December 1992.
  31. T. Leung et. al. "The AQUA Data Model and Algebra." Proceedings of the Fourth International Workshop on Database Programming Languages, New York, September 1993.
  32. Hsueh-I Lu and R. Ravi. "The Power of Local Optimization: Approximation Algorithms for Maximum-Leaf Spanning Tree." Proceedings of the Thirteenth Allerton Conference on Communication, Control and Computing, 1992.
  33. Hsueh-I Lu, Philip N. Klein, and Robert H. B. Netzer. "Detecting Race Conditions in Parallel Programs That Use One Semaphore." To appear in Proceedings of the Workshop on Algorithms and Data Structures (WADS '93), 1993.
  34. Scott Meyers and Steven P. Reiss. "An Empirical Study of Multiple-View Software Development." Proceedings of the Fifth ACM Symposium on Software Development Environments (ACM SIGSOFT '92), December 1992.
  35. G. Mitchell, U. Dayal, and S. Zdonik. "Control of an Extensible Query Optimizer: A Planning Based Approach." Proc. VLDB '93, August 1993.
  36. Robert H.B. Netzer. "Trace Size vs. Parallelism in Trace-and-Replay Debugging of Shared-Memory Programs." To appear in Proceedings of the Sixth Workshop on Languages and Compilers for Parallelism, Portland, Oregon, August 1993. (Also Techreport 93-27, Brown University, May 1993.)
  37. Robert H.B. Netzer and Jian Xu. "Adaptive Message Logging for Incremental Replay of Message-Passing Programs." To appear in Supercomputing '93, Portland, Oregon, November 1993. (Also Techreport 93-26, Brown University, May 1993.)
  38. Marian Nodine. "Supporting Long-Running Tasks on an Evolving Multidatabase Using Interactions and Events." Proceedings of the Second International Conference on Parallel and Distributed Information Systems, January 1993.
  39. Marian Nodine. "Interactions: Multidatabase Support for Planning Applications." PhD Thesis, Brown University, May 1993.
  40. R. Ravi, Balaji Raghavachari, and Philip N. Klein. "Approximation Through Local Optimality: Designing Networks with Small Degree." Proceedings of the Twelfth Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Springer LNCS 652, 1992.
  41. R. Ravi, M. V. Marathe, S. S. Ravi, D. J. Rosenkrantz, and H. B. Hunt III. "Many Birds With One Stone: Multi-Objective Approximation Algorithms." Proceedings of the 25th ACM Symposium on Theory of Computing (STOC '93), San Diego, April 1993.
  42. Steven P. Reiss. "Program Visualization: Where We Go From Here." Proc. Information Processing 92, pp. 218-227, September 1992.
  43. Steven P. Reiss. "Trace-based debugging." Proc. AADEBUG '93, May 1993.
  44. Steven P. Reiss. "A Framework for Abstract 3D Visualization." To appear in Proc. VL'93, August 1993.
  45. Steven P. Reiss. "Presentation and Editing of Structured 3D Graphics." To appear in Proc. HCI '93, August 1993.
  46. S. Sairam, R. Tamassia, and J.S. Vitter. "A Divide and Conquer Approach to Shortest Paths in Planar Layered Digraphs." Proceedings of the IEEE Symposium on Parallel and Distributed Processing, 1992.
  47. S. Sairam, J.S. Vitter, and R. Tamassia. "A Complexity Theoretic Approach to Incremental Computation." Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS '93), Springer LNCS 665, 1993.
  48. J.E. Savage. "Space-Time Tradeoffs in Memory Hierarchies." Technical Report 93-08, Brown University, February 1993.
  49. J.E. Savage. "Limits on Heterogeneous Supercomputing." Technical Report 93-19, Brown University, June 1993.
  50. B. Subramanian et. al. "Ordered Types in the AQUA Data Model." Proceedings of the Fourth International Workshop on Database Programming Languages, New York, September 1993.
  51. M. Tokoro, O. Nierstrasz, and P. Wegner (eds.). "Object-Based Concurrent Computing." Springer LNCS 612, 1992.
  52. Tom J. True and John F. Hughes. "Volume Morphing." Proceedings Visualization '92, October 1992.
  53. P. Van Hentenryck, Y. Deville and C.M. Teng. "A Generic Arc Consistency Algorithm and its Specializations." Artificial Intelligence, 57(2-3), October 1992.
  54. P. Van Hentenryck, H. Simonis and M. Dincbas. "Constraint Satisfaction using Constraint Logic Programming." Artificial Intelligence, 58(1), November 1992.
  55. P. Van Hentenryck. "Scheduling and Packing in the Constraint Language cc(FD)." To appear in "Intelligent Scheduling," Morgan Kaufman, 1993.
  56. P. Van Hentenryck and Y. Deville. "The Cardinality Operator: A new Logical Connective and its Application to Constraint Logic Programming." To appear in "Constraint Logic Programming: Selected Research," MIT Press, 1993.
  57. P. Wegner. "Reusability Considered Harmful." Technical Report, Brown University, November 1989.
  58. P. Wegner. "Design Issues for Object-Oriented Concurrency." In Tokoro, Nierstrasz, Wegner (eds.), "Object-Based Concurrent Programming," Springer LNCS 612, 1992.
  59. P. Wegner. "Object-Based Versus Logic Programming." Proceedings of the International Conference on Fifth-Generation Computing, Tokyo, June 1992.
  60. P. Wegner. "Dimensions of Object-Oriented Modeling." IEEE Computer, October 1992.
  61. P. Wegner. "Ada Pro and Con." Proc. 1992 Tri-Ada, November 1992.
  62. P. Wegner. "Tradeoffs between Reasoning and Modeling." In G. Agha, P. Wegner, A. Yonezawa (eds.), "Research Directions in Concurrent Object-Oriented Programming," MIT Press 1993.
  63. P. Wegner. "Reasoning and Modeling Paradigms are Incompatible." Proc. 1993 Hawaii System Conference, Hawaii, 1993.
  64. P. Wegner. "Towards Component-Based Software Technology." Technical Report 93-11, Brown University, June 1993.
  65. P. Wegner. "Reasoning, Modeling, and Component-Based Technology." Proceedings of the Fourth International Conference on Logic Programming and Automated Programming, St. Petersburg, July 1993. (Invited talk.)
  66. G. Wiederhold, P. Wegner, and S. Ceri. "Towards Megaprogramming." CACM, November 1992.
  67. Jian Xu and Robert H.B. Netzer. "Adaptive Independent Checkpointing for Reducing Rollback Propagation." Technical Report 93-25, Brown University, May 1993.
  68. S. Zdonik. "Incremental Database Systems: Databases From the Ground Up." Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data (SIGMOD '93), Washington, May 1993.
  69. Robert C. Zeleznik, Kenneth P. Herndon, Daniel C. Robbins, Nate Huang, Tom Meyer, Noah Parker and John F. Hughes. "An Interactive 3D Toolkit for Constructing 3D Widgets." To appear in Proc. SIGGRAPH '93, August 1993.

SIGNIFICANT EVENTS

  1. DESIGN AND IMPLEMENTATION OF PLUM: A 3D PROGRAM VISUALIZATION TOOL
    Steven Reiss has developed PLUM, a system that provides a flexible framework to support a wide range of 3D visualizations of program structures. This framework allows the definition and integration of different visualization strategies such as graphs in 2 and 3 dimensions, tagged objects, scatter plots, file representations, constraint-based tilings, simple objects, and time-sequence representations. Both the framework and a variety of different strategies to demonstrate its utility have been implemented.
  2. DESIGN AND IMPLEMENTATION OF THE CONSTRAINT-BASED LANGUAGE cc(FD)
    In the area of constraint-based languages, Pascal Van Hentenryck has completed the final design and implementation of the constraint language cc(FD). This (concurrent constraint with finite domains) system was applied to novel applications such as frequency allocation for mobile telephones, scheduling in digital scheduling applications, and two dimensional packing. The language will be distributed at the end of the summer.
  3. A SIMPLE FUNCTIONAL FRAMEWORK FOR DATABASE QUERY LANGUAGES
    Paris Kanellakis and his students have shown in [18] how to efficiently embed in a typed functional setting a very broad spectrum of database query languages. This spectrum includes most relational and complex object database languages that have been defined to date. The proof techniques shed new light on the capabilities of the simply typed lambda calculus, which is a basic programming language type system in current use.
Up
John Bazik