High Performance Design Environments (HPDE)

Table of Contents:

  1. Principal Investigator.
  2. Productivity Measures.
  3. Summary of Objectives and Approach.
  4. Detailed Summary of Technical Progress.
  5. Transitions and DOD Interactions.
  6. Software and Hardware Prototypes.
  7. List of Publications.
  8. Invited and Contributed Presentations.
  9. Honors, Prizes or Awards Received.
  10. Project Personnel Promotions.
  11. Project Staff.
  12. Multimedia URL.
  13. Keywords.
  14. Business Office.
  15. Expenditures.
  16. Students.
  17. Book Plans.
  18. Sabbatical Plans.
  19. Related Research.
  20. History.

Principal Investigator.

Productivity Measures.

Summary of Objectives and Approach.

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.

Detailed Summary of Technical Progress.

  1. 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.

Transitions and DOD Interactions.

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:

Software and Hardware Prototypes.

See previous section.

List of Publications.

  1. ``Broadcast Disks: Data Management for Asymmetric Communication Environments'', S. Achyra, R. Alosno, M. Franklin, S. Zdonik. ACM SIGMOD Symposium on the Management of Data, San Jose CA USA, May 1995.
  2. ``Counting Networks'', J. Aspnes, M.P. Herlihy, and N. Shavit. Journal of the ACM, 41(5): pp 1020--1048, September 1994.
  3. ``CLP(Intervals) Revisited'', F. Benhamou, D. McAllester, and P. Van Hentenryck. Proceedings of the International Logic Programming Symposium (ILPS-94), Ithaca, NY, November 1994.
  4. ``Horizons of Parallel Computation'', G. Bilardi, F.P. Preparata. Journal of Parallel and Distributed Computing, 27,2,172-182, June 1995.
  5. ``Upper Bounds to Processor-Time Tradeoffs under Bounded-Speed Message Propagation'', G. Bilardi, F.P. Preparata. Proceedings - SPAA 95, 7th Annual Symposium on Parallel Algorithms & Architectures, July 16-18, 1995.
  6. ``External-Memory Graph Algorithms'', Y.-J. Chiang, M.T. Goodrich, E.F. Grove, R. Tamassia, D.E. Vengroff and J.S. Vitter. Proc. ACM-SIAM Symp. on Discrete Algorithms (1995).
  7. ``Semantic Foundations of Binding-Time Analysis for Imperative Programs'', M. Das, T. Reps, and P. Van Hentenryck. ACM Symposium on Partial Evaluation and Semantic-based Program Manipulation (PEPM-95), La Jolla, CA, June 1995.
  8. ``An Experimental Comparison of Three Graph Drawing Algorithms'', G. Di Battista, A. Garg, G. Liotta, R. Tamassia, E. Tassinari and F. Vargiu. Proc. ACM Symp. on Computational Geometry (1995).
  9. ``Generalized Scans and Tri-Diagonal Systems'', P.F. Fischer, F.P. Preparata, J.E. Savage. Procs. 12th Annl. Symp. on Th. Aspects of Computer Science.
  10. ``Set Consensus Using Arbitrary Objects'', M.P. Herlihy and S. Rajsbaum. 12th Annual ACM Symposium on Principles of Distributed Systems.
  11. ``3D Widgets for Exploratory Scientific Visualization'', K.P. Herndon, T. Meyer. Proceedings of UIST '94, ACM SIGGRAPH, November, 1994, pp. 69-70.
  12. ``Concurrency = Fault-Tolerance in Parallel Computation'', P.C. Kanellakis, D. Michailidis, A.A. Shvartsman. 5th International Conference on Concurrency Theory, in LNCS 836, Uppsala Sweden, pp. 242--266, August 1994.
  13. ``An Analysis of Core-ML: Expressive Power and Type Inference'', P.C. Kanellakis, G. Hillebrand, H.G. Mairson. International Colloquium on Automata, Languages and Programming, in LNCS 820, Jerusalem Israel, pp. 83--105, July 1994.
  14. ``A randomized linear-time algorithm for finding a minimum spanning tree'', P. Klein, D. Karger, R.E. Tarjan. Journal of the ACM, Vol. 42 (1995), pp. 321-328.
  15. ``An Annotation system for 3D Fluid Flow Visualization'', M. Loughlin, J.F. Hughes. Proceedings of Visualization '94, pp. 273-279, Washington, DC, Oct. 1994.
  16. ``Complexity Models for Incremental Computation'', P. B. Miltersen, S. Subramanian, J. S. Vitter, R. Tamassia. Theoretical Computer Science, vol. 130, pp. 203-236 (1994).
  17. ``OODB Indexing by Class-Division'', S. Ramaswamy, P.C., Kanellakis. ACM SIGMOD Symposium on the Management of Data, San Jose CA USA, May 1995.
  18. ``3D visualization of Program Information'', S. P. Reiss. Graph Drawing '94.
  19. ``Fragments: a mechanism for low cost data integration'', S. P. Reiss. Tech Report, Brown University Dept of Computer Science.
  20. ``An engine for the 3D visualization of program information'', S. P. Reiss. J. Visual Languages (to appear 95).
  21. ``FIELD: A Friendly Integrated Environment for Learning and Development'', S. P. Reiss. Kluwer, 1994.
  22. ``An Architecture for an Extensible 3D Interface Toolkit'', M.P. Stevens, R.C. Zeleznik, J.F. Hughes. Proceedings of UIST '94, ACM SIGGRAPH, November, 1994.
  23. ``The AQUA Approach to Querying Lists and Trees in Object-Oriented Databases'', S. Subramanian and T. Leung and S. Vandenberg and S. Zdonik. Proceedings of the International Conference on Data Engineering.
  24. ``Solving Polynomial Systems Using a Branch and Prune Approach'', P. Van Hentenryck, D. McAllester, and D. Kapur. SIAM Journal on Numerical Analysis (To Appear).
  25. ``Evaluation of the Domain'', P. Van Hentenryck, A. Cortesi, and B. Le Charlier. Prop Journal of Logic Programming, 22(3):179-208, March 1995.
  26. ``Type Analysis of Prolog using Type Graphs'', P. Van Hentenryck, A. Cortesi, and B. Le Charlier. Journal of Logic Programming, 22(3):179-208, March 1995.
  27. ``Interaction as a framework for Empirical Computer Science'', P. Wegner. Computing Surveys, March 1995.

Invited and Contributed Presentations.

  1. Andries Van Dam: Keynote Lecture, "VR as a Forcing Function: Software Implications of a New Paradigm", IEEE Symposium on Virtual Reality, San Jose, CA (October 1993)
  2. Andries Van Dam: Keynote Lecture, "The Desktop of the Future", ENUF (European Network Users Forum, London, England (October 1993)
  3. Paris Kanellakis was invited speaker at ICALP94 in Jerusalem Israel, TACS94 in Sendai Japan and CONCUR94 in Uppsala Sweden.
  4. Peter Wegner lectured at the University of Arizona, Tucson, November 1993, Arizona State University, Phoenix, November 1993, Laval University, Quebec, March 1994, University of Puerto Rico, Ponce, Puerto Rico, April 1994 DIMACS Workshop on Parallel Computing, Princeton, May 1994, at ECOOP, Bologna Italy, July 1994
  5. Steven Reiss lectured on "Program Visualization: Where We Go From Here" at Sun Microsystems, Northeastern U., NYNEX Science and Technology Center.
  6. Marian Nodine, "Interactions: Multidatabase Support for Planning Applications", Colloquium talk at Purdue University Center for Database Studies February, 1993.
  7. Pascal Van Hentenryck gave a tutorial at AAAI'94. He lectured at WSA'93, International Symposium on Mathematical Programming ( August 1994), ENS, INRIA, Paris, France (April, 1994).
  8. Isabel Cruz lectured at: MIT, Media Lab, Cambridge, Massachussetts, USA, December 1993; University of Rome ``La Sapienza'', Rome, Italy, December 1993; Johns Hopkins University, Baltimore, February 1994; UNC Charlotte, Charlotte, NC, March 1994; ATT, Bell Laboratories, Murray Hill, NJ, March 1994; Tufts University, Medford, MA, March 1994; Villanova University, Villanova, PA, March 1994; Boston University, Boston, MA, April 1994; Northeastern University, Boston, MA, April 1994; MIT, Cambridge, MA, April 1994; University of Bergen, Norway, May 1994; University of Newcastle, Australia, June 1994.
  9. Thomas Doeppner was invited to present the Thread-monitor library at the "SunWorld Conference" in June 1994.
  10. Leslie Kaelbling gave invited talks at: inaugural meeting of MLNET (European Machine Learning Network), Blanes, Spain, 1993; at National Conference on AI, Seattle, 1994; at European Conference on AI, Amsterdam, 1994; Invited tutorial at International Conference on Machine Learning Conference on Learning Theory, Rutgers, 1994; Invited talk at Meckler conference on Virtual Reality, San Jose, California, 1994.
  11. John Savage gave invited talk at MIT on 4/6/94
  12. Roberto Tammassia gave invited lectures at: 4/94 892nd Meeting of the American Mathematical Society, Brooklyn, New York; 2/94 Second Italian Conference on Algorithms and Complexity (CIAC '94), Rome, Italy; 12/93 University of Rome, ``La Sapienza''; 10/93 State University of New York at Buffalo.
  13. Philip Klein was invited to speak at Theory Day at Columbia University and gave invited talks at at Waterloo, Princeton, New York University, MIT, International Compute Science Institute, DIMACS Workshop on Parallel Algorithms.

Honors, Prizes or Awards Received.

AWARDS
  1. Andries Van Dam: 1994 IEEE Fellow Award, 1994 ACM Fellow Award, 1994 ACM Karl. V. Karlstrom Outstanding Educator Award
  2. Pascal Van Hentenryck: NSF National Young Investigator 1993
  3. Leslie Kaelbling NSF Presidential Faculty Fellow 1994
  4. Robert Netzer: his paper ``Adaptive Independent Checkpointing for Reducing Rollback Propagation'' won best-paper award (in the systems track) of the IEEE Symposium on Parallel and Distributed
EDITORSHIPS
  1. Leslie Kaelbling was elected to Editorial Board of Machine Learning Journal, Editorial Board of Autonomous Systems, Advisory Committee of International Joint Conference on AI.
  2. John Savage joined the editorial board of JCSS.
  3. Paris Kanellakis joined the editorial boards of Information and Computation and the Chicago (electronic) Journal of Theoretical CS.
  4. Isabel Cruz: Guest editor special issue of the Journal of Visual Languages and Computing on ``Graph Drawing'', with co-guest editor Peter Eades,
  5. Roberto Tammassia is guest editing three issues: Journal of Computer and System Sciences, Special Issue on selected papers presented at the 26th ACM Symposium on Theory of Computing (STOC '94), to appear. Algorithmica, Special Issue on Graph Drawing, to appear. Computational Geometry: Theory and Applications, Special Issue on Geometric Representations of Graphs, to appear.
PROGRAM COMMITTEES
  1. Andries Van Dam: 1993 SIGGRAPH Technical Papers Committee
  2. Paris Kanellakis: IEEE LICS94, ACM SIGMOD94, First Workshop on Digital Libraries (Rutgers May 94).
  3. John Hughes: 1993 SIGGRAPH Technical Papers Committee, 1994 SIGGRAPH Technical Papers Committee
  4. S.B. Zdonik: 4th International Workshop on Database Programming Languages, New York, NY, September, 1993.
  5. Robert Netzer: 1994 IEEE Symposium on Parallel and Distributed Processing.
  6. Pascal Van Hentenryck: AAAI'94, CCL'94, ICLP'94, PASCO'94, PEPM'94, SAS'94.
  7. Isabel Cruz: AVI '94, International Workshop on Advanced Visual Interfaces, Bari, Italy, June 1994. ACM SIGMOD '95 International Conference on Data Management.
  8. Leslie Kaelbling: National Conference on AI, International Conference on Machine Learning, Conference on AI Planning, Conference on Simulation of Adaptive Behavior.
  9. Leslie Kaelbling: Co-organizer Workshop in Reinforcement Learning at International Machine Learning Conference.
  10. Roberto Tammassia: 10th ACM Annual Symposium on Computational Geometry, June 6-8 1994, Stony Brook, New York. 26th ACM Symposium on Theory of Computing (STOC '94), May 23-25, 1994, Montreal, Canada. ALCOM International Workshop on Graph Drawing and Topological Graph Algorithms (Graph Drawing '93), September 25-29, 1993, Paris, France. 3rd Workshop on Algorithms and Data Structures (WADS '93), August 11-13 1993, Montreal, Canada
  11. Philip Klein: ACM-SIAM Symposium on Discrete Algorithms

Project Personnel Promotions.

  1. Philip Klein was promoted to Associate Prof with tenure (July 94).
  2. Maurice Herlihy (formerly of DEC) joined the CS Department and the project staff as Associate Prof with tenure (June 94).
  3. Isabel Cruz, a postdoc with project during last 2 years, is now an Assistant Prof at Tufts.

Project Staff.

  1. Name: Dr Eugene Charniak
  2. Name: Dr Steven Reiss
  3. Name: Dr Paris Kanellakis
  4. Name: Dr Thomas Doeppner
  5. Name: Dr Maurice Herlihy
  6. Name: Dr John Hughes
  7. Name: Dr Philip Klein
  8. Name: Dr Leslie Kaelbling
  9. Name: Dr Robert Netzer
  10. Name: Dr Franco Preparata
  11. Name: Dr John Savage
  12. Name: Dr Roberto Tamassia
  13. Name: Dr Andries van Dam
  14. Name: Dr Pascal Van Hentenryck
  15. Name: Dr Peter Wegner
  16. Name: Dr Stan Zdonik

Multimedia URL.

  1. EOYL FY95
  2. EOYL FY94

Keywords.

  1. Design Environments
  2. Programming Environments
  3. Concurrent OO-Languages
  4. Constraint Languages
  5. OO Databases
  6. 3D Graphics
  7. Scientific Visualization

Business Office

Expenditures

Students

Book Plans

Sabbatical Plans

Related Research

History

  1. This is an extension of the fourth year of the HPDE project with small support relative to previous years.