1990-91 ACADEMIC ACTIVITIES REPORT NAME: TIMOTHY J. HICKEY DEPARTMENT: Computer Science I. INSTRUCTIONAL ACTIVITY (Summer 1990, Fall 1990, Spring 1991) a Semester Course Number and Title Class Contact Enrollment Hours Undergrad. Graduate Weekly 1. Autumn 1990 CS140 Logic Programming 6 hr/wk 7 u.g., 6 gr. 2. Spring 1991 CS150 Compiler Design 6 hr/wk 4 u.g., 9 gr. 3. 1990-91 CS99 Senior Research 1 hr/wk 1 u.g. 4. 1990-91 CS300 Master's Project 1 hr/wk 1 gr. 5. 1990-91 CS406 Dissertation Rsh 2 hr/wk 2 gr. b) Advising (total contact hours per week: ) 1 hr/wk 1) number of general or freshman advisees: 14 2) number of undergraduate departmental advisees: 7 3) number of graduate advisees: 3 c) Please describe your involvement in the direction of senior theses, graduate dissertations and other student research projects. 1. Advisor of 2 Ph.D. students (S. Mudambi, D. Smith) 2. Dissertation Committee for 2 CS Ph.D. students (E. Simoudis, M. Feeley) 3. Dissertation Committee for 1 Chem Ph.D. students (T. Miller) 3. Regularly advising 3 CS Ph.D. students (R. Sun, L. Bookman, C. Constantinescu) 4. Directing 1 master's students research (K. Bell) 5. Directing 1 senior's honors research (I. Lokuge) In total I am playing an active role in directing the research of 10 students. II. RESEARCH, PUBLICATIONS, ARTISTIC CREATION (use additional page if necessary.) a) Describe current research activities or work in progress: My current research is in two areas: 1) Parallel Programming, and 2) Logic Programming. In Parallel Programming: 1. Completely Automatic Analysis Of A Class Of Parallel Programs. (with J. Cohen, N. Mercouroff, A. Yurik) We are studing the mathematical structure of the performance of a class of parallel programs which includes almost all programs written form moderate scale (2-1000 processor) machines. This work generalizes our previous work on the microanalysis of sequential programs. 2. Languages for Divide and Conquer on Massively Parallel SIMD Machines. (with Z.G. Mou, and C. Constantinescu) One of the most exciting new developments in computing technology in the past few years has been the proliferation of massively parallel SIMD computers. These machines all have at least 16,000 processors which all execute the same sequence of instructions (although some may selectively skip certain instructions). The largest of these machines have the potential to execute over 5 billion floating point operations per second (about 5000 times more than a personal computer). One of the outstanding challenges today is to design programming techniques which can realize this potential performance on actual applications. In our research we are developing languages for expressing the well-known Divide and Conquer class of algorithms and we are studying implementation techniques which guarantee high performance levels on a wide variety of massively parallel machines. Since we are also concerned with developing theoretical models of program performance, this research seems likely to lead to a better understanding of the relative importance of processor interconnections and processor speed which may suggest new machine architectures that are best suited for Divide and Conquer algorithms. 3. Integrated Software Tools for Analyzing Parallel MIMD Programs. (w J. Cohen, I. Lokuge, K. Bell) Moderate scale MIMD parallel computers (2-1000 processors) are also evolving at a rapid rate and this rapid change in hardware technology has brought about a crisis in program development tools. MIMD computers are designed so that each processor executes its own sequence of instructions and all processors coordinate their activities either by sending messages or by sharing memory. This project is concerned with developing tools which aid the program developer to debug MIMD programs and to tune the performance. We are using a combination of state-of-the-art window-based graphics tools integrated with constraint logic programming technology to develop powerful and easy-to-use software development tools. These tools are based on our theoretical models of parallel program execution and performance. In Logic Programming: 1. General CLP Languages. The field of Logic Programming began as the study of a single language (PROLOG) which was based on a small fragment of mathematical logic. In the past 10 years, an intense international effort has been dedicated to designing logic languages which are efficiently implementable and include a larger subset of classical logic. This has resulted in an explosion of new languages. Two of the most notable are Constraint Logic Programming (in which axiomatized mathematical domains augment the logical basis of the language) and Logic Programming with Negation (in which some form of negation is allowed in the programming syntax). In this work, we show how these two branches of Logic Programming can be rejoined in a new class of languages (called General CLP) which allow arbitrary (first order) logical theories as the constraint domain and which allow unrestricted use of negation in the program. This class of languages has a simple semantics (similar to that used in functional languages) and many of the currently known implementation techniques can be applied to this more general class of languages. Our current work includes constructing a solid theoretical foundation for these languages, generalizing the theoretical results for CLP and Negation to this new class of languages, and studying implementations of interesting new languages belonging to this class. 2. Merging Scheme and CLP via the Environment Model. Two years ago I showed that constraint logic programming and functional programming could both be viewed as special cases of a simple class of languages based on the concept of a constraint abstraction. I also provided an efficient implementation of one of these languages and demonstrated its viability. My current work in this area is to extend this work to include side-effecting operations (such as assignment) and to include the set-based model of programming. Preliminary research suggests that by merging these disparate models of computation into a single (and simpler) model of computation, new programming paradigms will arise. 3. Partial Evaluation of CLP (with D. Smith) In this work we are studying the problem of optimizing CLP programs using partial evaluation and related program transformation techniques. Partial evaluation has not been very successful for earlier generations of languages principally because their underlying model of computation was too complex (e.g. the von Neuman machine). On the other hand, these optimizations are very promising for logic programs because of the simplicity of their semantics and we suspect that partial evaluation tools will soon be as common as debugging tools for logic programs. 4. Parallel Implementation of CLP languages (with S. Mudambi, the Swedish Institute of Computer Science, and Argonne National Laboratories) In this work, we are attempting to develop parallel implementations of Prolog (and other CLP languages) which obtain the best possible performance on parallel MIMD machines. Recent results suggest that our implementation of Prolog, when running on the most powerful MIMD currently available (a 128 processor Butterfly II) will be the fastest Prolog system in the world by a factor of 2 or 3. Our interest is primarily in understanding what the performance bottlenecks are and in developing theoretical models of parallel Prolog execution on this class of MIMD machines. The fact that our system is performing so well is an indication of the validity of our theoretical models. Articles submitted for publication: 1. Divide and Conquer on a 3 Dimensional Mesh (with Z.G. Mou, and C. Constantinescu) Submitted to the Supercomputer Conference '91. 2. Magic Sets and CLP (with M. Goodman) Submitted to International Symposium in Logic Programming '91. Articles in preparation 1. DIVACON - the language and its implementation (w ZG Mou) 2. The Soundness and Completeness of the Substitution Model for General CLP 3. The Semantics of General CLP b) Manuscript (s) or artistic work accepted for publication (List journal or publisher and anticipated publication date.) 1. Computer Assisted Microanalysis of Parallel Programs (with J. Cohen, H. Hotta, and T. Petitjean), Spr. 92, accepted in ACM Transactions on Programming Languages and Systems 2. Metalevel Interpretation of Constraint Languages, A Case Study: Logical Primitives, (w. J. Cohen, V. Deschamps), Spr. 92, accepted in New Generation Computing 3. Toward the Partial Evaluation of CLP Languages (with D. Smith) Jun. 91 accepted in the Proceedings of the ACM/IFIP Symposium on Partial Evaluation and Semantics Based Program Manipulation, ACM Press. c) Publications since June, 1989 (with inclusive page reference for articles). Please use standard form: author(s) or editor(s), title, number of pages, publisher, location, date. 1. Partial Evaluation of a CLP Language (with D. Smith) Proceedings North American Conference on Logic Programming, MIT Press, pp. 119-138, 1990. d) Artistic creation (please describe) III. AWARDS AND HONORS (dates) Distinguished Lectures: 1. Invited Speaker at 2nd International Workshop on Constraint Logic Programming. (Jan, 1991, Marseilles, France) Grant Support 1. NSF research grant in Logic Programming CCR-8718989, co-PI with J. Cohen. 2. NSF research grant in Microanalysis CCR-8814261, participant w J. Cohen, 3. REU supplement to CCR-8814261 supporting undergraduate research $8,800, co-PI with J. Cohen IV. PROFESSIONAL ACTIVITIES OUTSIDE THE UNIVERSITY (lectures, activities in professional societies, legislative testimony, paid consulting, equity arrangements, etc.) 1. Refereed articles submitted for publication in a) Journal of Logic Programming b) International Logic Programming Symposium 2. Refereed 2 books on Logic Programming for Addison-Wesley V. PARTICIPATION IN DEPARTMENTAL ACTIVITIES AND ADMINISTRATION 1. Supervised Systems Administrator 2. Department Liason to Admissions Department VI. PARTICIPATION IN UNIVERSITY ACTIVITIES, COMMITTEES, ETC. 1. Member of Wien Advisory Committee