Principal Investigator(s) Name(s): Eugene Charniak (admin. contact) Steven Reiss (techn. contact) Paris Kanellakis (techn. contact) PI Institution: Brown University PI Phone Number: (401) 863-7600 PI E-mail Address: darpa@cs.brown.edu Grant or Contract Title: High Performance Design Environments Grant or Contract Number: N00014-91-J-4052 ARPA ord. 8225 Reporting Period: 1 Oct 91 - 30 Sept 92 1. Productivity measures. Refereed papers submitted but not yet published: 32 Refereed papers published: 40 Unrefereed reports and articles: 23 Books or parts thereof submitted but not yet published: 0 Books or parts thereof published: 8 Patents filed but not yet granted: 0 Patents granted (include software copyrights): 0 Invited presentations: 62 Contributed presentations: 14 Honors received (fellowships, technical society appointments, 34 conference committee roles, editorships, etc.): also include descriptions of the specific honors. HONORS: John Savage, Fellow of the IEEE. Andries Van Dam, L. Herbert Ballou University Chair Professor PROGRAM COMMITTEE CHAIRS AND CO-CHAIRS: Paris Kanellakis, Program chair for the: 11th ACM Symposium on the Principles of Database Systems (June 1992 in San Diego). John Savage, Co-Chair Program Committee, Brown/MIT Conference on Advanced Research in VLSI and Parallel Systems. INVITED SPEAKERS AT CONFERENCES: Franco Preparata, invited speaker for the 25th Anniversary of INRIA, France December 1992. Steven Reiss, Keynote Speaker, IFIP World Conference Andries Van Dam, Pleneary Speaker, Hawaii International Conference on Systems Sciences Andries Van Dam, Keynote Speaker, SIGGRAPH Symposium on Interactive 3D Graphics Andries Van Dam, Keynote Speaker, Hewlett Packard Peripherals Developers Conference Andries Van Dam, Panel Chair, "Graphics Software Architecture for the Future", 1992 SIGGRAPH Conference NEW EDITORIAL POSITIONS: Paris Kanellakis, edited proceedings for the: 11th ACM Symposium on the Principles of Database Systems (June 1992 in San Diego). Paris Kanellakis, in 1992, completed editing special issue on database theory for TCS and started editing a special issue on database theory for JCSS. Paris Kanellakis, co-edited the book: ``Database Programming Languages: Bulk Types and Persistent Data (3rd International Workshop)'' with Joachim Schmidt, Morgan-Kaufmann, March 1992. Paris Kanellakis, starting Sept 15 1992, associate editor for the ACM Transactions on Database Systems. John Savage, Co-Editor Proceedings of Brown/MIT Conference on Advanced Research in VLSI and Parallel Systems, published by MIT Press. Pascal Van Hentenryck, associate editor of Journal of Logic Programming. Pascal Van Hentenryck, guest editor of Journal of Logic Programming, special issue on constraint logic programming. Jeff Vitter, Editor, Mathematical Systems Theory: An International Journal on Mathematical Computing Theory. Jeff Vitter, Guest Editor, special issue of Algorithmica on the subject of Disk I/O and Large-Scale Memory. Peter Wegner, Editor in Chief ACM Press Books Peter Wegner, ACM Publication Board PROGRAM COMMITTEE MEMBERSHIPS: Paris Kanellakis, Prog. Committee 2nd International Conf. on Deductive and Object Oriented Databases (Munich, Germany December 1991). Paris Kanellakis, Prog. Committee 92 Joint International Conference and Symposium on Logic Programming (Washington DC, November 1992). Paris Kanellakis, Prog. Committee for the upcoming 1993 Conference on Very Large Databases (Dublin Ireland, August 1993). Paris Kanellakis, Program Committee for the upcoming 25th ACM Symposium on the Theory of Computing (San Diego CA, May 1993). Pascal Van Hentenryck, Prog. Commitee ICLP-93 Pascal Van Hentenryck, Prog. Commitee LPAR-93 Jeff Vitter, Member of Program Committee, MIT-Brown Conference on Parallelism and VLSI, Providence, R.I., March 1992. Jeff Vitter, Member of Program Committee, 1992 IEEE Data Compression Conference (DCC'92), Snowbird, UT, March 1992. Jeff Vitter, Member of Program Committee, 1993 Workshop on Algorithms and Data Structures (WADS'93), Montreal, Canada, August 1993. Jeff Vitter, Member of Program Committee, 1993 IEEE Data Compression Conference (DCC'93), Snowbird, UT, March~1993. Stanley Zdonik, Prog. Committee POS (Persistent Object Systems) Stanley Zdonik, Prog. Committee VLDB (Very Large Databases) Stanley Zdonik, Prog. Committee DOM (Distributed Object Management) Prizes or awards received (Nobel, Japan, Turing, etc.): 1 AWARDS: Leslie Kaelbling, NSF National Young Investigator Award Promotions obtained: 0 Graduate students supported >= 25% of full time: 10 Post-docs supported >= 25% of full time: 0 Minorities supported (include Blacks, Hispanics, American Indians 0 and other native Americans such as Aleuts, Pacific Islanders, etc.; do not include Asians or Asian-Americans): Principal Investigator(s) Name(s): Eugene Charniak (admin. contact) Steven Reiss (techn. contact) Paris Kanellakis (techn. contact) PI Institution: Brown University PI Phone Number: (401) 863-7600 PI E-mail Address: darpa@cs.brown.edu Grant or Contract Title: High Performance Design Environments Grant or Contract Number: N00014-91-J-4052 ARPA ord. 8225 Reporting Period: 1 Oct 91 - 30 Sept 92 2. Detailed summary of technical progress. OBJECTIVES ---------- 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 the following: (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, and multi-databases. 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. FIRST YEAR 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 (journal and conference papers and a number of system and subsystem implementations). 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 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 and their students 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. In software environments for robotics applications, Leslie Kaelbling has built CritterWorld. This is a two-dimensional graphical simulator which will serve as a testbed for performing experiments in robotic learning. In theoretical computer science, there has been significant progress and publications on dynamic geometric methods (by Roberto Tamassia and his students), approximation methods for combinatorial optimization (by Philip Klein and his students), parallel methods for large scale sorting (by Jeff Vitter and his students), and on parallel algorithm implementations on the CM (by John Savage and his students). This algorithmic work stresses parallel and I/O efficiency. TWO SIGNIFICANT EVENTS IN FIRST YEAR ------------------------------------ (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. 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. Principal Investigator(s) Name(s): Eugene Charniak (admin. contact) Steven Reiss (techn. contact) Paris Kanellakis (techn. contact) PI Institution: Brown University PI Phone Number: (401) 863-7600 PI E-mail Address: darpa@cs.brown.edu Grant or Contract Title: High Performance Design Environments Grant or Contract Number: N00014-91-J-4052 ARPA ord. 8225 Reporting Period: 1 Oct 91 - 30 Sept 92 3. Lists of publications, presentations and reports. Refereed papers submitted but not yet published: 32 ------------------------------------------------ S. Abiteboul, P. Kanellakis, S. Ramaswamy, E. Waller, "Method Schemas" submitted to JCSS special issue. A. Agrawal, P. N. Klein, and R. Ravi, ``When trees collide: An approximation algorithm for the generalized Steiner tree problem on networks,'' submitted to SIAM J. Comput. A. Agrawal, P. N. Klein, and R. Ravi, ``Ordering problems approximated: register sufficiency, single-processor scheduling and interval graph completion,'' submitted to J. Algorithms. A. Agrawal, P. N. Klein, and R. Ravi, ``Near-optimal nested dissection,'' submitted to SIAM J. Comput. K.J. Basye and T.L.Dean and Jeff Vitter ``Coping with Uncertainty in Map Learning'' Machine Learning, to appear. G. Bilardi and F. P.Preparata , "Horizons of Parallel Computation," keynote address, INRIA 25th Anniversary,Paris, France, December 1992; to appear in Springer-verlag LNCS. D. Brookshire Conner and Andries van Dam, "Sharing Between Graphical Objects Using Delegation", Workshop on Object-Oriented Graphics, to be published. Kenneth P. Herndon, Robert C. Zeleznik, Daniel C. Robbins, D. Brookshirt Conner, Scott S. Snibbe, and Andries van Dam, "Interactive Shadows", UIST '92 Proceedings, to be published. G. Hillebrand, P. Kanellakis, H. Mairson, M. Vardi, "Undecidable Boundeness Problems for Datalog Programs", sumbitted to the Journal of Logic Programming. P.G. Howard, J.S. Vitter, ``Analysis of Arithmetic Coding for Data Compression'' invited paper in special issue on data compression for images and texts in The Journal of Information Processing and Management (edited by J. Storer), to appear. P.G. Howard, J.S. Vitter, ``New Methods for Lossless Image Compression Using Arithmetic Coding'' invited paper in special issue on data compression for images and texts in The Journal of Information Processing and Management (edited by J. Storer), to appear. P. Kanellakis, G. Kuper, P. Revesz, "Constraint Query Languages" submitted to JCSS. P. N. Klein, S. Rao, A. Agrawal, and R. Ravi, ``An approximate max-flow min-cut relation for multicommodity flow, with applications,'' submitted to Combinatorica. P. N. Klein, ``A parallel randomized approximation scheme for shortest paths,'' submitted to J. Algorithms. P. N. Klein and R. Ravi, ``Approximation through uncrossing,'' submitted to 4th ACM-SIAM Symposium on Discrete Algorithms. P. Klein and R. Ravi, ``When cycles collapse: a general approximation technique for constrained two-connectivity problems,'' submitted to Algorithmica. J.-H. Lin, Jeff Vitter ``Approximation Algorithms for Geometric Median Problems'' Information Processing Letters, to appear. Y. Matias, W.-C. Ni, J.S. Vitter ``Dynamic Generation of Discrete Random Variates'' Proceedings of the 4th Annual SIAM/ACM Symposium on Discrete Algorithms (SODA'93), Austin, TX, January 1993, to appear. Marian H. Nodine, "InterActions: Multidatabase Support for Planning Applications", Parallel and Distributed Information Systems Proceedings, 1993 to appear. M.H. Nodine, Jeff Vitter, ``Paradigms for Optimal Sorting with Multiple Disks''. Proceedings of the 26th Hawaii International Conference on Systems Sciences, January 1993, to appear. M.H. Nodine, Jeff Vitter, ``Optimal Deterministic Sorting in Parallel Memory Hierarchies'' submitted. M.H. Nodine, Jeff Vitter ``Greed Sort: An Optimal Sorting Algorithm for Multiple Disks'' submitted. M.H. Nodine, Jeff Vitter ``Large-Scale Sorting in Uniform Memory Hierarchies'' special issue on parallel I/O systems in Journal of Parallel and Distributed Computing (edited by A. Choudhary), to appear January 1993. R. Ravi, ``Approximation algorithms for Steiner augmentations for two-connectivity,'' submitted to Algorithmica. Steven P. Reiss, Manojit Sarkar "Generating program abstractions" Submitted for publication. Manojit Sarkar, Steven P. Reiss "Manipulating screen space with StretchTools: Visualizing large structure on a small screen" Submitted for publication E.A. Shriver, Jeff Vitter ``Optimal Algorithms for Parallel Memory I: Two-Level Memories'', revised for Algorithmica. E.A. Shriver, Jeff Vitter ``Optimal Algorithms for Parallel Memory II: Hierarchical Multilevel Memories'' revised for Algorithmica. R. Tamassia, Jeff Vitter, ``Optimal Cooperative Search in Fractional Cascaded Data Structures'' accepted after revision for special issue of Algorithmica (edited by M. Snir). Tom J. True and John F. Hughes, "Volume Morphing", Visualization '92, to be published. P. Van Hentenryck, Y. Deville and C.M. Teng. "A Generic Arc Consistency Algorithm and its Specializations". To appear in Artificial Intelligence. P. Van Hentenryck, H. Simonis and M. Dincbas. "Constraint Satisfaction using Constraint Logic Programming". To appear in Artificial Intelligence, Special Issue on Constraint-based Reasoning. Refereed papers published: 40 -------------------------- Alan H. Barr, Bena Currin, Steven Gabriel, and John F. Hughes, "Smooth Interpolation of Orientations with Angular Velocity Constraints Using Quaternions", SIGGRAPH '92 Proceedings. P. Bertolazzi, R.F. Cohen, G. Di Battista, R. Tamassia, and I.G. Tollis, ``How to Draw a Series-Parallel Digraph,'' Algorithm Theory (Proc. SWAT), Lecture Notes in Computer Science, vol. 621, pp. 272-283 (1992). S. Ceri, G. Wiederhold, P. Wegner "Towards Megaprogramming", CACM November 1992. R. F. Cohen, G. Di Battista, R. Tamassia, I.G. Tollis, and P. Bertolazzi, ``A Framework for Dynamic Graph Drawing,'' Proc. ACM Symp. on Computational Geometry, pp. 261-270 (1992). G. Di Battista, R. Tamassia, and I.G. Tollis, ``Area Requirement and Symmetry Display of Planar Upward Drawings,'' Discrete & Computational Geometry, vol.7(4), pp.381-401 (1992). G. Di Battista, R. Tamassia, and I.G. Tollis, ``Constrainted Visibility Representations of Graphs,'' Information Processing Letters, vol. 41, pp.1-7 (1992). M. Dincbas, H. Simonis, and P. Van Hentenryck. "Solving a Cutting-Stock Problem with the Constraint Logic Programming Language CHIP." Mathl. Comput. Modelling, 16(1):95-105, 1992. D. Brookshire Conner, Scott S. Snibbe, Kenneth P. Herndon, Daniel C. Robbins, Robert C. Zeleznik, and Andries van Dam, "Extending Widgets in Three-Dimensional Geometry and Behavior", 1992 SIGGRAPH Symposium on Interactive 3D Graphics. Dhamdhere, D. M. and Rosen, B. K. and Zadeck, F. K., ``How to Analyse Large Programs Efficiently and Informatively", Proc. SIGPLAN'92 Symp. on Compiler Construction" 1992. P.G. Howard, J.S. Vitter ``Practical Implementations of Arithmetic Coding'' invited paper in Images and Text Compression, (edited by J.A. Storer), Kluwer Academic Publishers, 1992. A summary appears as an invited paper in Proceedings of the 3rd International Conference on Advances in Communication and Control Systems (COMCON'91), Victoria, Canada, October 1991. P.G. Howard, J.S. Vitter ``Error Modeling for Hierarchical Lossless Image Compression'' Proceedings of the 1992 IEEE Data Compression Conference (DCC'92), Snowbird, UT, March 1992, 269--278. P.G. Howard, J.S. Vitter ``Parallel Lossless Image Compression Using Huffman and Arithmetic Coding'' Proceedings of the 1992 IEEE Data Compression Conference (DCC'92), Snowbrid, UT, March 1992, 299--308. John F. Hughes, "Scheduled Fourier Volume Morphing", SIGGRAPH '92 Proceedings William M. Hsu and John F. Hughes, "Direct Manipulation of Free-Form Deformations", SIGGRAPH '92 Proceedings J.L. Imbert and P. Van Hentenryck. "Efficient Handling of Disequations in Linear Rational Arithmetic", Constraint Logic Programming: Selected Research, MIT Press, 1992. P. Kanellakis, H. Mairson, J. Mitchell, "Unification and ML-Type Reconstruction" Chapter 13, in Computational Logic, Essays in Honor of Alan Robinson, MIT Press, 1991. A. Kanevsky, R. Tamassia, J. Chen, and G. Di Battista, ``On-Line Maintenance of the Four-Connected Components of a Graph,'' Proc. 32th IEEE Symp. on Foundations of Computer Science, pp. 793-801 (1991). C.M. Kenyon, J. S. Vitter ``Maximum Queue Size and Hashing with Lazy Deletion'' Algorithmica, 6 (4), 1991, 597--619. C. M. Kenyon-Mathieu, J. S. Vitter ``General Methods for the Analysis of the Maximum Size of Dynamic Data Structures'', SIAM Journal on Computing, 20 (5), October 1991, 807--823. B. Le Charlier and P. Van Hentenryck. "Reexecution in Abstract Interpretation of Prolog" International Joint Conference and Symposium on Logic Programming, Washington, DC, November 1992. J.-H. Lin, J.S. Vitter, ``Complexity Results on Learning by Neural Nets'', Machine Learning, 6, 1991, 211--230. J.-H. Lin, J.S. Vitter, ``Learning in Parallel'' Information and Computation, 92(2), February 1992, 179--202. J.-H. Lin, J.S. Vitter, ``Approximations with Minimum Packing Constraint Violation'' Proceedings of the 24th Annual ACM Symposium on Theory of Computing (STOC'92), Victoria, Canada, May 1992, 771--782. J.-H. Lin, J.S. Vitter, ``Nearly Optimal Vector Quantization via Linear Programming'' Proceedings of the 1992 IEEE Data Compression Conference (DCC'92)}, Snowbird, UT, March 1992, 22--31. J.-H. Lin, J.S. Vitter, ``A Theory for Memory-Based Learning'' Proceedings of the 5th Annual ACM Workshop on Computational Learning Theory (COLT'92), Pittsburgh, PA, July 1992, 103--115. Scott Meyers, Steven P. Reiss "An empirical study of multiple-view software development", Proc. SIGSOFT '92. Scott Meyers, Steven P. Reiss "A system for multiparadigm development of software systems", Proc 6th Intl Workshop on Software Specification and Design October, 1991 Marian H. Nodine and Sridhar Ramaswamy and Stanley B. Zdonik, "A Cooperative Transaction Model for Design Databases", Database Transaction Models for Advanced Applications, 1991, Morgan-Kaufmann. Marian H. Nodine and Stanley B. Zdonik, "Cooperative Transaction Hierarchies", VLDB Journal, 1, 1, 1992. F.P. Preparata and R. Tamassia, ``Efficient Point Location in a Convex Spatial Cell Complex,'' SIAM J. Computing, vol. 21(2), pp. 267-280 (1992). F.P. Preparata, J.S. Vitter, and M. Yvinec,``Output-Sensitive Generation of the Perspective View of Isothetic Parallepipeds'' Algorithmica, 8, 1992, 257--283. Steven P. Reiss, Scott Meyers, Lijter Moises "Support for maintaining object-oriented programs" Proc. of the Conference on Software Maintenance October, 1991. JE Savage and M.G. Wloka, ``Parallelism in Graph-Partitioning'' Journal of Parallel and Distributed Computing, 13, pp. 257-272, November 1991. Scott S. Snibbe, Kenneth P. Herndon, Daniel C. Robbins, D. Brookshire Conner, and Andries van Dam, "Using Deformations to Explore 3D Widget Design", SIGGRAPH '92 Proceedings R. Tamassia, I.G. Tollis, and J.S. Vitter, ``Lower Bounds for Planar Orthogonal Drawings of Graphs,'' Information Processing Letters, vol. 39, pp. 35-40 (1991). R. Tamassia, I.G. Tollis, and J.S. Vitter, ``Lower Bounds and Parallel Algorithms for Planar Orthogonal Grid Drawings,'' Proc. IEEE Symposium on Parallel and Distributed Processing, pp. 386-393 (1991). P. Van Hentenryck and T. Graf. "Standard Forms for Rational Linear Arithmetics in Constraint Logic Programming". Annals of Mathematics and Artificial Intelligence, 5(2-4), 1992. P. Van Hentenryck and Y. Deville. "The Cardinality Operator: A new Logical Connective and its Application to Constraint Logic Programming," In Constraint Logic Programming: Selected Research, MIT Press, 1992. J. S. Vitter and P. Krishnan. ``Optimal Prefetching via Data Compression,'' Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science (FOCS'91), San Juan, Puerto Rico, October 1991, 121--130. P. Wegner "Dimensions of Object-Oriented Modeling", IEEE Computer, Oct 1992 Unrefereed reports and articles: 23 --------------------------------- P. Bertolazzi, R.F. Cohen, G. Di Battista, R. Tamassia, and I.G. Tollis, ``How to Draw a Series-Parallel Digraph,'' Technical Report CS-92-41, Dept. of Computer Science, Brown Univ., 1992. R. F. Cohen, G. Di Battista, R. Tamassia, and I.G. Tollis, ``Dynamic Graph Drawing,'' Technical Report CS-92, Dept. of Computer Science, Brown Univ., 1992. R.F. Cohen and R. Tamassia, ``Combine and Conquer,'' Technical Report CS-92-19, Dept. Computer Science, Brown Univ. (1992). G. Di Battista and R. Tamassia, ``On-Line Planarity Testing,'' Technical Report CS-92-39, Dept. of Computer Science, Brown Univ., 1992. G. Di Battista and R. Tamassia, ``On-Line Maintenance of Triconnected Components with SPQR-Trees,'' Technical Report CS-92-40, Dept. of Computer Science, Brown Univ., 1992. Y.-J. Chiang, F.P. Preparata, and R. Tamassia, ``A Unified Approach to Dynamic Point Location, Ray Shooting and Shortest Paths in Planar Maps,'' Technical Report CS-92-07, Dept. Computer Science, Brown Univ. (1992). Y.-J. Chiang and R. Tamassia, ``Dynamization of the Trapezoid Method for Planar Point Location,'' Technical Report CS-92-06, Dept. of Computer Science, Brown Univ. (1992). V. Englebert, B. Le Charlier, D. Roland, and P. Van Hentenryck. "Generic Abstract Interpretation Algorithms for Prolog: Two Optimization Techniques and Their Experimental Evaluation". Fourth International Symposium on Programming Language Implementation and Logic Programming (PLILP-92), Leuven, Belgium, August 1992. P. N. Klein, J. Borger, and T. S. Kang, ``Approximating concurrent flow with uniform demands and capacities: an implementation,'' Proceedings, DIMACS Implementation Challenge Workshop: Algorithms for Network Flows and Matching, D. S. Johnson and C. C. McGeoch (eds.), DIMACS Technical Report 92-4 (1992), pp. 225-240. Knobe, K. and Zadeck, F. K., ``Register Allocation Using Control Trees", Dept. of Computer Sci., Brown U., Providence, RI, CS-92-13, 1992. B. Le Charlier and P. Van Hentenryck. "Experimental Evaluation of a Generic Abstract Interpretation Algorithm for Prolog". In Fourth IEEE International Conference on Computer Languages ICCL'92), San Fransisco, CA, April 1992. H.-I Lu and R. Ravi, ``The power of local optimization: approximating the maximum-leaf spanning tree,'' Proceedings, 30th Annual Allerton Conference on Communication, Control, and Computing (September 1992). Gail Mitchell and Stanley B. Zdonik and Umeshwar Dayal "An Architecture for Query Processing in Persistent Object Stores", Proceedings of the 25th Hawaii International Conference on System Sciences, January 1992. M. H. Nodine and J. S. Vitter. ``Optimal Deterministic Sorting on Parallel Disks'' Technical Report No. CS--92--08, Dept. of Computer Science, Brown University, revised August 1992. F.P. Preparata, J.S. Vitter ``A Simplified Technique for Hidden-Line Elimination in Terrains'' ). Proceedings of the 1992 Symposium on Theoretical Aspects of Computer Science (STACS'92), Paris, France, February 1992, published in Lecture Notes in Computer Science, 577, Springer-Verlag, Berlin, 135--146. R. Ravi, B. Raghavachari, and P. N. Klein, ``Approximation through local optimality: designing networks with small degree,'' Proceedings, 12th Annual Conference on Foundations of Software Technology and Theoretical Computer Science (1992). Steven P. Reiss, "Program visualization: Where we go from here" Proc. IFIP World Conference on Computing September 1992 S. Sairam, R. Tamassia, and J.S. Vitter, ``"A Divide and Conquer Approach to Shortest Paths in Planar Layered Digraphs,'' Technical Report CS-92-15, Dept. of Computer Science, Brown Univ. (1992.). S. Sairam, J.S. Vitter, and R. Tamassia, ``A Complexity Theoretic Approach to Incremental Computation,'' Technical Report CS-91-66, Dept. of Computer Science, Brown Univ. (1991.). JE Savage and M.G. Wloka, ``Parallel Graph-Embedding Heuristics,'' Proceedings of the 5th SIAM Conference on Parallel Processing for Scientific Computing, 1991. JE Savage and M.G. Wloka, ``The Parallel Complexity of a Channel Routing Heuristic,'' in Proceedings of the Second Great Lakes Symposium on VLSI, pp. 3034, February 28-29, 1992. P. Wegner "Design Issues for Object-Based Concurrency", in LNCS #612, Object-Based Concurrent Programming, Eds M. Tokoro, O. Nierstrasz, P. Wegner, 1992 P. Wegner "Object-Based Versus Logic Programming", Proc FGCS 92, Tokyo, June 1992 Books or parts thereof published: 8 --------------------------------- Francois Bancilhon, Claude Delobel, Paris Kanellakis (Editors), ``Building an Object-Oriented Database System: the Story of O2'' Morgan Kaufmann, June 1992. Y. Deville and P. Van Hentenryck. "Construction of CLP Programs", In Logic Programming: New Frontiers, Kluwer Academic Publishers, 1992. Paris Kanellakis (Editor) Proceedings for the: 11th ACM Symposium on the Principles of Database Systems (June 1992 in San Diego). Paris Kanellakis, Joachim Schmidt (Editors) ``Database Programming Languages: Bulk Types and Persistent Data (3rd International Workshop)'', Morgan-Kaufmann, March 1992. JE Savage, T. Knight, (Editors) Proceedings of Brown/MIT Conference on Advanced Research in VLSI and Parallel Systems, published by MIT Press, 1992. Book (and report) co-authored by Andries Van Dam "Computing the Future: A Broader Agenda for Computer Science and Engineering", Committee to Assess the Scope and Direction of Computer Science and Technology. P. Van Hentenryck. "Constraint Logic Programming". In Encyclopedia of Artificial Intelligence (Second Edition), Wiley, 1992. "Object-Based Concurrent Programming" LNCS #612, , Eds M. Tokoro, O. Nierstrasz, P. Wegner, 1992 Principal Investigator(s) Name(s): Eugene Charniak (admin. contact) Steven Reiss (techn. contact) Paris Kanellakis (techn. contact) PI Institution: Brown University PI Phone Number: (401) 863-7600 PI E-mail Address: darpa@cs.brown.edu Grant or Contract Title: High Performance Design Environments Grant or Contract Number: N00014-91-J-4052 ARPA ord. 8225 Reporting Period: 1 Oct 91 - 30 Sept 92 4. Transitions and DoD interactions. Many of the software prototypes developed by HPDE co-PIs have been widely distributed to industry and universities (see 5 below for statistics). In the last year, the department of CS at Brown (as part of our Industrial Partners Program) has organized two one-day symposia on themes closely related to the research of HPDE. (1) Symposium on Software Development and CASE (organized by Steve Reiss March 19, 1992) (2) Symposium on Progress in Distributed Object-Oriented Computing (organized by Peter Wegner October 1, 1992). These symposia were well attended by researchers and developers from industry. HPDE co-PIs and industrial partners presented on-going work on the symposia themes. This process has generated a number of Brown-industry collaborations. In addition, there has been a great deal of interaction between a number of co-PIs and various research groups from the IBM T.J. Watson Labs (e.g., on compilers, constraint logic languages, databases). There has been interaction with Texas Instruments for object-oriented database language technology. Our graphics research and software have been distributed to industrial partners, including IBM, Sun Microsystems, and NCR. Some of our algorithmic work has led to algorithm implementations and use in larger systems. For example, our graph partitioning algorithms for the CM have been distributed to many university sites. Technology transfer in the area of graph layout algorithms has been conducted with Cadre Technologies Inc (e.g., the Cadre Teamwork system, is a state-of-the-art tool for computer-aided software engineering that automates structured methodologies using interactive computer graphics and uses these algorithms). Principal Investigator(s) Name(s): Eugene Charniak (admin. contact) Steven Reiss (techn. contact) Paris Kanellakis (techn. contact) PI Institution: Brown University PI Phone Number: (401) 863-7600 PI E-mail Address: darpa@cs.brown.edu Grant or Contract Title: High Performance Design Environments Grant or Contract Number: N00014-91-J-4052 ARPA ord. 8225 Reporting Period: 1 Oct 91 - 30 Sept 92 5. Software and hardware prototypes. 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: (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. FIELD has also been licensed by DEC and is being distributed by them as DEC FUSE. (2) IDYL dynamic loader of Steven Reiss at 209 sites. (3) GARDEN visual programming environment of Steven Reiss 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 terms of other completed prototypes: (8) The UGA (Unified Graphics Architecture) system is a large-scale, object-oriented 3D graphics platform used to create 3D interactive graphics applications. It can be used to rapidly prototype 3D graphical user interfaces, and is used as a testbed for ongoing graphics research in the Brown Graphics Group. UGA is used for 4D modeling and animation research. (9) Theodora is a mobile workstation email system. (10) We have implemented and distributed various parallel algorithms for basic combinatorial tasks on the CM, and various graph layout heuristics. Some software prototypes are close to completion: (a) Initial tools are ready for abstraction visualization in programming environments by Steven Reiss (see Section 2). (b) Mongrel is a prototype multidatabase by Stan Zdonik and his students. Mongrel supports standard, atomic global transactions as well as our open nested transaction model, InterActions. It is being developed to explore issues of transaction management, recovery, and long-lived (planning) tasks that require information from multiple databases. (c) EPOQ is a prototype open, extensible object-oriented query optimizer by Stan zdonik and his students. It has been designed to allow multiple query transformation strategies to exist and operate within the optimizer at the same time. It is currently under development, and when it is completed, we will compare its performance to other extensible optimizers such as EXODUS. (d) Pascal Van Hentenryck has designed and implemented cc(FD), a constraint programming language including, constraint operations (satisfiability, entailment) generalization combinators (blocking implication, cardinality, constructive disjunction, nondeterminism, conjunction). Distribution is considered for the end of the year. (e) CritterWorld of Leslie Kaelbling is a two-dimensional graphical simulator which will serve as a testbed for performing experiments in robotic learning, using both reinforcement-learning techniques and spatial algorithms. It is written in CommonLisp and uses the CLX and CLM packages to provide a Motif interface. It allows the user to write control programs for individual agents in CommonLisp.