Parallel symbolic processing based on suspending construction

Research Supervisor: Steven D. Johnson
Postdoctoral Researcher: Eric Jeschke

Project summary and rationale

This is an opportunistic project, taking advantage of existing resources and available expertise to advance experimental studies of symbolic processing support on shared-memory multiprocessors. The necessary equipment, an SGI Power Challenge, was acquired in 1993 under an ARI grant and is now available for projects of this kind. Funding is budgeted for post-doctorate researcher Eric Jeschke and one graduate assistant implement Jeschke's doctoral project, a demand-oriented computational model, on the Power Challenge. The resulting system would be used for performance studies of low-level generic support for parallel heap management, and, orthogonally, continued investigation of a stream-oriented functional modeling language.

Since this project does not involve a change in supervision or locale, it does not appear to qualify under the CISE Post-Doctoral Research Associates program. However, we believe that program's general objectives are well served by this project. In supporting his spouse's career development, Jeschke is remaining in Bloomington for the next two years. He is uniquely qualified to do this work. In addition, this project makes use of an NSF-funded research vehicle ideally suited to its purpose. The work spawns new opportunities for collaboration with researchers at Indiana investigating parallel symbolic processing. Finally, the proposed funding would enable a new generation of students to train for an experimental effort that has been ongoing since 1979.

Description of the research

The DSI programming system is a model of concurrent demand-oriented processing in which the only synchronizing mechanism is a suspending constructor. Newly allocated data cells are initialized with transparent computations for computing their fields. Field access is blocked until these suspensions compute and replace themselves with concrete values.

Suspensions are ultra-lightweight tasks. The DSI system is a vehicle for experimenting with various approaches to concurrent symbolic computation, including output-driven parallelism, demand propagation, delayed list ordering, and speculative scheduling. In twenty years of exploring these aspects, we have also developed general perspectives on architecture and resource management for parallel heap memories. Our motive is not to promote a particular computation model, but to contribute to the evolution of general purpose computers toward better symbolic processing capabilities.

Our experimentation has focused on moderate scale, shared memory multiprocessing models, involving tens of processors and giga-byte-scale memories. This architecture represents the coming generation of general-purpose work stations. We also believe that symbolic processing will prevail on these machines, owing to the heterogeneity of network computing, hence, the need to coordinate disparate local and remote tasks.

The proposed work is to instrument a DSI implementation on the Indiana University Computer Science Department's SGI Power Challenge computer. The Power Challenge, funded by ARI grant CDA93-03189 (PD David S. Wise) in 1993, is an instance of the architecture class for which DSI was originally targeted. The implementation would be a test bed for performance studies of storage and task management, and process synchronization.

As in the past, we would continue to explore applicative surface languages for DSI, particularly system modeling languages geared toward stream processing. The current surface language for DSI, a quasi-functional language called Daisy, is especially agile for building and observing stream networks. We are interested in techniques for improving the granularity of such programs. However, our primary intent is to investigate underlying architecture and resource management issues for the parallel heap-based processing.

Background sketch

The original DSI model emerged from the idea of a "lazy cons" proposed by Friedman and Wise in 1976. Johnson and Kohlstaedt refined a concurrent virtual machine model in 1979-1981. A stream-oriented programming paradigm arises naturally from this approach, especially when I/O devices are introduced to the heap as pseudo-suspensions, using the same basic synchronization mechanics.

Based on this work, Johnson embarked on research (funded through MIPS) adapting applicative programming methodology to hardware specification and verification (he has 30 refereed publications in this area). Although this formal-methods did not support continued language implementation work, DSI and its surface language were used very effectively to animate hardware specifications. Thus, while DSI was extensively used in support of methodological research, providing a novel collection of features for stream models, its implementation details were never the focus of published articles.

With assistantship support from the Computer Science Department, Jeschke took over DSI development in 1987. He created a highly portable C implementation and also a version running the department's 32-node BBN Butterfly. Informed by performance measurements on the Butterfly, Jeschke completely redesigned DSI for shared-memory parallel implementation. Components of the design included a parallel mark-sweep collector, distributed allocation system, and several variants of a fine-grained, parallel task scheduler, and a virtual processor model.

Another important aspect of Jeschke's work is a multi-window I/O server, which, for one thing, facilitated Johnson's system modeling methodology. However, the two most significant contributions of Jeschke's work may be its investigation of the role of I/O processes in speculative task scheduling and the potential of data recreation as a mechanism for load balancing.


This project's goals are (1) to consolidate and publish architectural insights for parallel symbolic processing, (2) to create an instrumented parallel test bed on the Power Challenge, and (3) to enable a new cadre of students to participate in this work. Our budgeting request has three items, post-doctoral support for Jeschke, a modest line for travel, and one graduate assistantship. In addition to the Power Challenge implementation, a compatible version with a functional surface language, and enhanced windowing system will be maintained for uniprocessor hosts. Jeschke will conduct an ongoing research seminar (2 hours per semester) on topics related to this project.

Johnson will administer the project at no cost.

The Computer Science Department will provide access to and support for the Power Challenge and front-end workstations. It will waive its standard computer services fees.

Possible collaborations

There are several related research projects at Indiana. The largest is a parallel Scheme implementation effort headed by Kent Dybvig. David Wise, who heads the ARI project, has done research in parallel matrix decomposition, parallel heap memory architectures, and applicative file systems, which all reflect interests in common with Johnson. Indeed, the DSI/Daisy model arose through collaborations between Johnson and Wise.

Condensed bibliography of DSI research

  1. Eric R. Jeschke. An Architecture for Parallel Symbolic Processing Based on Suspending Construction . Ph.D dissertation, Indiana University Computer Science Department (November 1995) 152 pgs.
  2. Steven D. Johnson. Daisy, DSI and LiMP: Issues in architecture for suspending construction. Indiana University Computer Science Dept. Technical Report No. 288 (August 1989).
  3. Steven D. Johnson. How Daisy is lazy: Suspending construction at target levels. Indiana University Computer Science Dept. Technical Report No. 286 (August 1989).
  4. Steven D. Johnson. Storage allocation for list multiprocessing. Indiana University Computer Science Dept. Technical Report No. 168 (March 1985).
  5. Steven D. Johnson. Synthesis of Digital Designs from Recursion Equations, The ACM Distinguished Dissertation Series, The MIT Press, Cambridge, MA., 1984.
  6. Steven D. Johnson. Daisy Programming Manual. Draft language manual, Indiana University Computer Science Dept., Bloomington, Indiana, USA.
  7. A. T. Kohlstaedt and Steven D. Johnson. DSI program description. Indiana University Computer Science Dept. Technical Report No. 120 (November 1981).
  8. Steven D. Johnson. Connection networks for output-driven list multiprocessing. Indiana University Computer Science Dept. Technical Report No. 114 (1981).
  9. Steven D. Johnson. An Interpretive Model for a Language Based on Suspended Construction, Masters Thesis, Indiana University Computer Science Dept., Bloomington, 1977.