SELECTED BIBLIOGRAPHY OF PROJECT PUBLICATIONS
The Toolkit is a family of hardware modules (processors, memory, interconnect, and input-output devices) and a collection of software modules (compilers, simulators, scientific libraries, and high-level front ends) from which high-performance special-purpose computers can be easily configured and programmed. The hardware modules are intended to be standard, reusable parts. These are combined by means of a user-reconfigurable, static interconnect technology. The Toolkit's software support, based on novel compilation techniques, produces extremely high-performance numerical code from high-level language input, and will eventually automatically configure hardware modules for particular applications.
We have completed fabrication of the Toolkit processor module, and an eight-processor configuration is running at MIT. As a demonstration of the power of the Toolkit approach, we have used the prototype Toolkit to perform an integration of the motion of the Solar System in a computation that extends previous results by nearly two orders of magnitude.
The Supercomputer Toolkit is a proposed family of standard hardware and software components from which special-purpose machines can be easily configured. Using the Toolkit, a scientist or an engineer, starting with a suitable computational problem, will be able to readily configure a special purpose multiprocessor that attains supercomputer-class performance on that problem, at a fraction of the cost of a general purpose supercomputer.
While the Toolkit project is not complete, we believe our results show evidence that generating special-purpose computers from standard modules can be an important method of performing intensive scientific computing. This paper briefly describes the Toolkit's hardware and software modules, the Solar System simulation, and conclusions and future plans.
The Bifurcation Interpreter is a computer program that autonomously explores the steady-state orbits of one-parameter families of periodically-driven oscillators. To report its findings, the Interpreter generates schematic diagrams and English text descriptions similar to those appearing in the science and engineering research literature. Given a system of equations as input, the Interpreter uses symbolic algebra to automatically generate numerical procedures that simulate the system. The Interpreter incorporates knowledge about dynamical systems theory, which it uses to guide the simulations, to interpret the results, and to minimize the effects of numerical error.
Computer programs that combine traditional numeric methods with symbolic algebra and with specific knowledge of application-based techniques can provide new levels of computational support for engineering design. We illustrate this with a computer-based ``control-engineer's assistant.'' Although this program is focussed on control-system design, it demonstrates techniques that should be widely applicable across many engineering disciplines. In particular, we show how, with symbolic computing, a computer-aided design system can usefully simulate engineering models early in the design process, before all (or any) system parameters have been specified numerically. Our system employs a flexible, extensible, object-oriented representation for control systems, which admits multiple mathematical models of designs and provides a framework for integrating tools that operate on diverse representations.
Combining numerical techniques with ideas from symbolic computation and methods incorporating knowledge of science and mathematics leads to a new category of intelligent computational tools for scientists and engineers. These tools autonomously prepare simulation experiments from high-level specifications of physical models. For computationally intensive experiments, they automatically design special-purpose numerical engines optimized to perform the necessary computations. They actively monitor numerical and physical experiments. They interpret experimental data and formulate numerical results in qualitative terms. They enable their human users to control computational experiments in terms of high-level behavioral descriptions.
This article exhibits programs that illustrate the power and simplicity of Lisp as a language for expressing design and organization and computational systems. Lisp's vitality is rooted in it's power to express robust designs for computational systems. A design for a system is robust if small changes in the system requirements can be accomplished by small changes in design. One way to enhance the robustness of design is to express it in terms of a natural representation of the problem domain, where each relevant entity in the problem is modeled by a computational entity and each relation or operation in the problem domain is modeled by a computational relation or function. With such an organization, small changes in the configuration of the problem domain can be accommodated by small changes in the configuration of the computational model. For a programming language to support such natural representations, it must allow programmers the freedom to construct appropriate computational abstractions to represent the elements of problem domains.
The dynamicist's workbench is a system for automating some of the work of experimental dynamics. We describe a portion of our system that deals with the setting up and execution of numerical simulations. This part of the workbench includes a spectrum of computational tools - numerical methods, symbolic algebra, and semantic constraints. These tools are designed so that combined methods, tailored to particular problems, can be constructed on the fly.
We exhibit programs that illustrate the power of Lisp as a language for expressing the design and organization of computational systems. The examples are chosen to highlight the importance of abstraction in program design and to draw attention to the use of procedures to express abstractions.
Programming is most often viewed as a way for experts to get computers to perform complex tasks efficiently and reliably. Boxer presents an alternative image-programming as a way for nonexperts to control a reconstructible medium, much like written language, but with dramatically extended interactive capabilities.
We describe a small set of additions to Scheme to support object-oriented programming, including a form of multiple inheritance. The extensions proposed are are in keeping with the spirit of the Scheme language and consequently differ from Lisp-based object systems such as Flavors and the Common Lisp Object. Our extensions mesh neatly with the underlying Scheme system. We motivate our design with examples, and then describe implementation techniques that yields efficiency comparable to dynamic object-oriented language implementations considered to be high performance.
We have designed and built the Orrery, a special computer for high-speed, high-precision orbital mechanics computations. On the problems the Orrery was designed to solve, it achieves approximately 10 Mflops in about one cubic foot of space while consuming 150w of power. The specialized parallel architecture of the Orrery, which is well matched to orbital mechanics problems, is the key to obtaining such high performance. In this paper, we discuss the design, construction and programming of the Orrery.
We have used a special purpose computer to integrate the orbits of the outer five planets for 100 Myr into the past. The strongest features in the Fourier transforms of the orbital elements of the Jovian planets can be identified with the frequencies predicted by linear secular theory. Many of the weaker features in the Fourier spectra are identified as linear combinations of the basic frequencies. We note serious differences between our measurements and the prediction of Bretagnon (1974). The amplitude of the 3.796 Myr period libration of Pluto's longitude of perihelion is modulated with a period of 34 Myr. Very long periods, on the order of 137 million years, are also seen. The orbit of Pluto is stable for the duration of our integration; the maximum Lyapunov characteristic exponent is less than 10^-6.8 yr^-1. .
In this paper we describe syntactic closures. Syntactic closures address the scoping problems that arise when writing macros. We discuss some issues raised by introducing syntactic closures into the macro expansion into the macro expansion interface, and we compare syntactic closures with other approaches. Included is a complete implementation.
Spatial aggregation is a framework for organizing computations around image-like, analogue representations of physical processes in data interpretation and control tasks. It conceptualizes common computational structures in a class of implemented problem solvers for difficult scientific and engineering problems. It comprises a mechanism, a language, and a programming style. The spatial aggregation mechanism transforms a numerical input field to successively higher-level descriptions by applying a small, identical set of operators to each layer given a metric, neighborhood relation and equivalence relation. This paper describes the spatial aggregation language and its applications.
The spatial aggregation language provides two abstract data types --- neighborhood graph and field --- and a set of interface operators for constructing the transformations of the field, together with a library of component implementations from which a user can mix-and-match and specialize for a particular application. The language allows users to isolate and express important computational ideas in different problem domains while hiding low-level details. We illustrate the use of the language with examples ranging from trajectory grouping in dynamics interpretation to region growing in image analysis. Programs for these different task domains can be written in a modular, concise fashion in the spatial aggregation language.
Active structural strengthening is an emerging technology that adjusts the dynamic behavior of structural members to prevent buckling, thereby allowing structures to be made stronger, lighter, and more reliable than would otherwise be possible. Early experiments have achieved stabilization of the first two modes of column buckling, yielding a strength increase of 5.6x and demonstrating that active control of buckling can allow a member to be loaded well in excess of its critical buckling load. This paper presents an overview of these early experiments and describes potential military and commercial applications of active structural strengthening technology.
The buckling of compressively-loaded members is one of the most important factors limiting the overall strength and stability of a structure. I have developed novel techniques for using active control to wiggle a structural element in such a way that buckling is prevented. I present the results of analysis, simulation, and experimentation to show that buckling can be prevented through computer-controlled adjustment of dynamical behavior.
I have constructed a small-scale railroad-style truss bridge that contains compressive members that actively resist buckling through the use of piezo-electric actuators. I have also constructed a prototype actively controlled column in which the control forces are applied by tendons, as well as a composite steel column that incorporates piezo-ceramic actuators that are used to counteract buckling. Active control of buckling allows this composite column to support 5.6 times more load than would otherwise be possible.
These techniques promise to lead to intelligent physical structures that are both stronger and lighter than would otherwise be possible.
We describe the key role played by partial evaluation in the Supercomputer Toolkit, a parallel computing system for scientific applications that effectively exploits the vast amount of parallelism exposed by partial evaluation. The Supercomputer Toolkit parallel processor and its associated partial evaluation-based compiler have been used extensively by scientists at M.I.T., and have made possible recent results in astrophysics showing that the motion of the planets in our solar system is chaotically unstable.
We have used active control to increase the strength of a structure by preventing the catastrophic buckling of compressively loaded members. For many geometries, buckling is the factor that limits the maximum compressive force that may be applied to a member; for long slender members, the strength limitation imposed by buckling is several orders of magnitude more important than other load-limiting factors, such as plastic deformation. Experimental results obtained using a prototype actively-controlled column indicate that this approach has the potential to produce structures that are both lighter and stronger than would otherwise be feasible.
This work demonstrates how partial evaluation can be put to practical use in the domain of high-performance numerical computation. I have developed a technique for performing partial evaluation by using placeholders to propagate intermediate results, and have implemented a prototype compiler based on this technique. For an important class of numerical programs, this compiler improves performance by an order of magnitude over conventional compilation techniques. I also show that by eliminating inherently sequential data-structure references, partial evaluation exposes the low-level parallelism inherent in a computation. I have implemented a parallel program generator, as well as several analysis programs that study the tradeoffs involved in the design of an architecture that can effectively utilize this parallelism. I present these results using the 9-body gravitational attraction problem as an example.
We have developed a compiler that uses partial evaluation and parallel scheduling techniques. Where conventional compilers compile a program without any knowledge of the data the program will be run on, our system uses information about the data when transforming the program. This technique, by eliminating nearly all the user's control and data abstractions, produces high-performance code. For an important class of numerical programs, partial evaluation dramatically improves performance: we have achieved speedups over conventionally compiled code that range from seven times faster to ninety one times faster. We also show how partial evaluation can be applied to the programming of parallel computers. By eliminating inherently sequential data structure references and their associated conditional branches, partial evaluation exposes the low-level parallelism inherent in a computation. We present the results of applying a parallel scheduler to a partially evaluated program that simulates the motions of nine bodies under mutual gravitational attraction.
Scheme86 is a computer system designed to interpret programs written in the Scheme dialect of Lisp. A specialized architecture, coupled with new techniques for optimizing register management in the interpreter, allow Scheme86 to execute interpreted Scheme at a speed comparable to that of compiled Lisp on conventional workstations.
There have been many demonstrations that the expressive power of Lisp can greatly simplify the process of writing numerical programs, but at the cost of reduced performance. I show that by coupling Lisp's abstract, expressive style of programming with a compiler that uses partial evaluation, data abstractions can be eliminated at compile time, producing extremely high-performance code. For an important class of numerical programs, partial evaluation achieves order-of-magnitude speed-ups over conventional Lisp compilation technology. This approach has proven to be especially effective when used in conjunction with schedulers for VLIW and highly pipelined architectures, because the elimination of data structures and procedural abstractions exposes the low-level parallelism inherent in a computation.
The MIT-Scheme program development environment includes a general-purpose text editor, Edwin, that has an extension language, Edwin Scheme. Edwin is very similar to another general-purpose text editor, GNU Emacs, which also has an extension language, Emacs Lisp. The popularity of GNU Emacs has lead to a large library of tools written in Emacs Lisp. The goal of this thesis is to implement a useful subset of Emacs Lisp in Edwin Scheme. This subset was chosen to be sufficient for simple operation of the GNUS news reading program.
Chaos is common in physical systems, but control engineers have, until very recently, deemed it undesirable and gone to great lengths to avoid it. Such tactics can represent a needless sacrifice in performance - chaos has a variety of useful properties that can significantly enhance engineering designs. In particular, phase-space trajectories on a chaotic attractor densely cover a set of non-zero measure, making all points in that set reachable from any initial condition in its basin of attraction. Moreover, the size, shape, and position of the attractor are affected by changes in system parameters, following certain highly characteristic patterns. These properties have been used, in simulations, to broaden the capture range of the common phase-locked loop circuit. An external modulating input is used to throw the unlocked loop into a chaotic regime that overlaps the original capture range. The chaos-inducing modulation is then turned off, allowing the loop's original dynamics to capture the signal. This technique is not limited to this system or even to this branch of engineering; it applies, modulo a few constraints and limitations, to any system that exhibits chaotic behavior and that is subject to design requirements.
Hugh Herr, an 18-year-old star rock climber and somewhat unenthusiastic student, was disabled in a winter mountaineering accident in 1982, losing both of his lower legs to frostbite. Confronted with standard leg prostheses, he immediately began to redesign them, awakening an abiding passion for engineering design. His self-designed prostheses - incorporating composites, epoxies and bladders that adapt to the stump - were not only good enough to allow him to regain his prior climbing level, but actually led other climbers to tease him about having an unfair competitive advantage. Herr then branched out into other areas of human-powered design, leading to several US patents and eventually to the PhD program in mechanical engineering at MIT. One of those patents, under development by the ASICS shoe company, covers a running shoe with a graphite spring in the sole. The underlying principle is that passive energy storage devices can reduce the metabolic cost associated with running or other physical work; Herr also holds a related patent on a spring suit that stores and then returns the energy involved in the swing of a runner's arm. Colleagues describe Herr's designs as ``crazily creative - they either succeed or fail spectacularly.'' Herr believes that this risk-taking creativity - what he terms ``believing without seeing'' - is the hardest part of being a designer, but he appears to have little difficulty applying it.
Control algorithms that exploit chaotic behavior can vastly improve the performance of many practical and useful systems. The program Perfect Moment is built around a collection of such techniques. It autonomously explores a dynamical system's behavior, using rules embodying theorems and definitions from nonlinear dynamics to zero in on interesting and useful parameter ranges and state-space regions. It then constructs a reference trajectory based on that information and causes the system to follow it. This program and its results are illustrated with several examples, among them the phase-locked loop, where sections of chaotic attractors are used to increase the capture range of the circuit.
This paper describes a computational environment that has been developed to aid control system design for a particular class of nonlinear applications. The analysis and design tools that comprise this environment are based upon knowledge about phase-space dynamics of nonlinear and chaotic systems. We describe two implemented, complementary programs that exploit the special properties of such systems to automatically synthesize powerful control systems. Phase Space Navigator visualizes phase-space dynamics through flow pipes and navigates systems along automatically synthesized reference trajectories. Perfect Moment identifies and uses chaotic phase-space features like strange attractors in its segmented control trajectories, gaining otherwise-unobtainable performance. Though the phase-space paradigm is very powerful, its global and computationally-intensive nature makes some of the techniques that exploit it difficult to implement. Fast computers and powerful computational techniques that combine symbolic/numeric and algebraic/geometric computing with new reasoning mechanisms from artificial intelligence make this paradigm feasible in spite of its inherent demands.
Control algorithms that exploit chaos's unique properties can vastly improve the performance of many practical and useful systems. The program Perfect Moment is built around such an algorithm. Given a differential equation and two points in the system's state space, it automatically maps the space, chooses a set of trajectory segments from the maps, uses them to construct a composite path between the points, and causes the system to follow that path by monitoring the state and switching parameter values at the segment junctions. The creation of and search through the maps are computationally intensive processes. However, the sensitivity of a chaotic system's state-space topology to the parameters of its equations and the sensitivity of the paths of its trajectories to the initial conditions make this approach rewarding in spite of its computational demands. This program and its results are illustrated with several examples, among them the driven single pendulum and its electronic analog, the phase-locked loop. In this particular case, strange attractor bridges, which traverse boundaries of basins of attraction and thus alter the reachability of different state space points, can be used to broaden the capture range of the circuit.
This paper presents techniques that actively exploit chaotic behavior to accomplish otherwise-impossible control tasks. The state space is mapped by numerical integration at different system parameter values and trajectory segments from several of these maps are automatically combined into a path between the desired system states. A fine-grained search and high computational accuracy are required to locate appropriate trajectory segments, piece them together and cause the system to follow this composite path. The sensitivity of a chaotic system's state-space topology to the parameters of its equations and of its trajectories to the initial conditions make this approach rewarding in spite of its computational demands. Boundaries of basins of attraction can be breached, vastly altering both global and local convergence properties. Strange attractor bridges can be found that connect previously unreachable points. Examples of both are shown.
Most of the recent literature on chaos and nonlinear dynamics is written either for popular science magazine readers or for advanced mathematicians. This paper gives a broad introduction to this interesting and rapidly growing field at a level that is between the two. The graphical and analytical tools used in the literature are explained and demonstrated, the rudiments of the current theory are outlined and that theory is discussed in the context of several examples: an electronic circuit, a chemical reaction and a system of satellites in the solar system.
The time dependent solution to Schrödinger's equation is obtained using a parallel algorithm on a massively parallel computer. The algorithms used are reviewed and their running speed on serial and parallel architectures is contrasted. The system studied has a classical analogue which undergoes a gradual transition from regular to chaotic motion as a function of a parameter of the Hamiltonian. The decay of the autocorrelation function is studied. In addition, the time dependence of the information measure and spatial correlation is studied.
Current fashion in ``user-friendly'' software design tends to place an overreliance on direct manipulation interfaces. To be truly expressive (and thus truly user-friendly), applications need both learnable interfaces and domain-enriched languages that are accessible to the user. This paper discusses some of the design issues that arise in the creation of such programmable applications. As an example, we present ``SchemePaint,'' a graphics application that combines a MacPaint-like interface with an interpreter for (a ``graphics-enriched'') Scheme.
The Kineticist's Workbench is a program that expands the expressiveness of computer simulation: it combines symbolic and numerical techniques in simulating a particular class of complex systems-chemical reaction mechanisms. The Workbench assists chemists by predicting, generating, and interpreting numerical data. Prior to simulation, it analyzes a given mechanism to predict that mechanism's behavior; it then simulates the mechanism numerically; and afterward, it interprets and summarizes the data that it has generated. In performing these tasks, the Workbench brings to bear a wide variety of techniques: graph-theoretic algorithms (for the analysis of mechanisms), traditional numerical simulation methods, and algorithms that examine the simulation results and reinterpret them in qualitative terms. Moreover, the Workbench can use symbolic procedures to help guide or simplify the task of numerical simulation; and it can sometimes use its summary of numerical results to suggest additional numerical analysis. Thus, it serves as a prototype for a new class of scientific computational tools-tools that provide symbiotic collaborations between qualitative and quantitative methods.
In simulating chemical reaction mechanisms, a combination of both qualitative analysis and traditional numerical techniques can produce insights not obtained with either approach alone. For instance, if a program can deduce on qualitative grounds that a system must reach equilibrium, it can use this information to steer numerical simulations, to choose appropriate numerical methods, and to produce qualitative interpretations of numerical results.
This paper describes a program that implements mixed qualitative-quantitative analysis of chemical mechanisms, whose simulation usually entails numerically integrating (possibly large) systems of coupled nonlinear differential equations. The program guides the integration by means of qualitative information that it deduces from the structure of the mechanisms prior to numerical simulation.
The Kineticist's Workbench is a computer program currently under development whose purpose is to help chemists understand, analyze, and simplify complex chemical reaction mechanisms. This paper discusses one module of the program that numerically simulates mechanisms and constructs qualitative descriptions of the simulation results. These descriptions are given in terms that are meaningful to the working chemist (e.g. steady states, stable oscillations, etc.); and the descriptions (as well as the data structures used to construct them) are accessible as input to other programs.
Programming in Scheme and Programming in MacScheme each provide an accessible introduction to this learnable dialect of LISP. The books assume no programming experience on the part of the reader and cover all of the basics of the language plus some advanced topics. Both texts also include a number of runnable projects. Programming in Scheme uses Texas Instruments' `` PC Scheme'' software as a source of examples, while Programming in MacScheme uses Lightship Software's `` MacScheme''.
Programming languages that treat procedures as ``object-like'' (for example, allowing procedures to be passed as arguments to other procedures) offer major advantages in semantic power and syntax elegance. In this paper, we examine how novice programmers appropriate the idea of procedures as objects. Based on a series of structured interviews with students in the introductory computer science course at MIT, we develop a model of the students' ontology of procedures. We conclude that many students view procedures as inherently active entities, with few object-like properties. We speculate on the implications of these results for the design and teaching of languages that treat procedures as objects.
A revolution in earthmoving, a $100 billion industry, can be achieved with three components: the GPS location system, sensors and computers in earthmoving vehicles, and Site Controller, a central computer system that maintains design data and directs operations. The first two components are widely available; I built Site Controller to complete the triangle and describe it here.
Civil engineering challenges computer scientists in the following areas: computational geometry, large spatial databases, floating-point artihmetic, software reliability, management of complexity, and real-time control. Site Controller demonstrates that most of these challenges may be surmounted by the use of state-of-the-art algorithms, object databases, software development tools, and code-generation techniques. The system works well enough that Caterpillar was able to use Site Controller to supervise operations of a 160-ton autonomous truck.
Site Controller assists civil engineers in the design, estimation, and construction of earthworks, including hazardous waste site remediation. The core of Site Controller is a site modelling system that represents existing and prospective terrain shapes, road and property boundaries, hydrology, important features such as trees, utility lines, and general user notations. Around this core are analysis, simulation, and vehicle control tools. Integrating these modules into one program enables civil engineers and contractors to use a single interface and database throughout the life of a project.
This area is exciting because so much of the infrastructure is in place. A small effort by computer scientists could cut the cost of earthmoving in half, enabling poor countries to build roads and rich countries to clean up hazardous waste.
We illustrate how the liberal use of high-order procedural abstractions and infinite streams helps us to express some of the vocabulary and methods of numerical analysis. We develop a software toolbox encapsulating the technique of Richardson extrapolation, and we apply these tools to the problems of numerical integration and differentiation. By separating the idea of Richardson extrapolation from use in particular circumstances, we indicate how numerical programs can be written that exhibit the structure of the ideas from which they are formed.
MIT Scheme is an implementation of the Scheme programming language that runs on many popular workstations. The MIT Scheme Reference Manual describes the special forms, procedures, and datatypes provided by the implementation for use by application programmers.
The Scheme dialect of Lisp is properly tail-recursive - it relies entirely on procedure calls to express iteration. As elegant as tail-recursion may be from the perspective of the programmer or the theoretician, it poses challenges for the compiler designer. This paper describes stack-allocation techniques for compiling tail-recursive languages. We have implemented these techniques in the MIT Scheme compiler. We show that the performance is comparable to implementations of non-tail-recursive languages. In particular, the code sequences generated for tail-recursive procedure calls are as efficient as those that implement the special-purpose iteration constructs on non-tail-recursive languages.
High-speed computation is dramatically changing the way science is done. Traditionally investigators have developed idealized models from which predictions can be made that are tested by observation or experiment. In complicated systems, it is hard to find simplifications without taking the risk of ``throwing the baby out with the bath water'', because some of the most important phenomena can arise from unforseen combinations or amplification of small effects. Computers are enabling investigators to cope successfully with such phenomena, which range from the diffusion of charge carriers in semi-conductor to collisions between galaxies containing millions of stars.
This work combines tree algorithms for the N-body problem where the number of particles is on the order of a million. The main concern of this work is the organization and performance of these computations on parallel computers. The work introduces the formulation of the N-body problem as a set of recursive equations based on a few elementary functions. It is shown that both the algorithm of Barnes-Hut and that of Greengard-Rokhlin satisfy these equations using different elementary functions. The recursive formulation leads directly to a computational structure in the form of a pyramid-like graph, where each vertex is a process, and each arc a communication link.
In many types of computer simulation, a ring polymer of length l in a particular solvent is represented as a polygon of N sides of length lp, where N ~= l/lp and lp is the Kuhn length. There are many established methods to make such polygons, including kink-jump, bead-spring, and dimerization. This paper introduces a very efficient and easy-to-program method, called vector shuffling, which is useful for generating such polygons in the important special case where the quality of the solvent is good, and the polymer is said to be under theta-conditions.
Vector Length Caching (VLC) is a technique which provides high-speed hardware bounds checking for array accesses. The entries of a vector V, of length N, starting at address V, are usually accessed (read/written) by means of LOAD/STORE instructions. VLC introduces two additional instructions, VLOAD/VSTORE, and a simple software convention, that N is stored at address V - 1. These new instructions look and work like LOAD/STORE, except that they also provide automatic bounds checking. The first time that VLOAD/VSTORE accesses an entry of V, there will be an automatic one-time hardware-imposed penalty of a read from address V - 1, where N is placed into the VLC; afterwards, these new instructions run at exactly the same speed as their conventional counterparts, for any element of V. VLC enables many programs to become either more robust or faster, particularly if they are written in Lisp or ML.
We have designed the Standard Map Machine (SMM) as an answer to the intensive computational requirements involved in the study of chaotic behavior in nonlinear systems. The high-speed and high-precision performance of this computer is due to its simple architecture specialized to the numerical computations required of nonlinear systems. In this report, we discuss the design and implementation of this special-purpose machine.
The general subset sum problem is NP-complete. However, there are two algorithms, one due to Brickell and the other to Lagarias and Odlyzko, which in polynomial time solve almost all subset sum problems of sufficiently low density. Both methods rely on basis reduction algorithms to find short non-zero vectors in special lattices. The Lagarias-Odlyzko algorithm would solve almost all subset sum problems of density < 0.6463... in polynomial time if it could invoke a polynomial-time algorithm for finding the shortest non-zero vector in a lattice. This paper presents two modifications of that algorithm, either one of which would solve almost all problems of density < 0.9408... if it could find shortest non-zero vectors in lattices. These modifications also yield dramatic improvements in practice when they are combined with known lattice basis reduction algorithms.
The presumed difficulty of computing discrete logarithms in finite fields is the basis of several popular public key cryptosystems. The secure identification option of the Sun Network File System, for example, uses discrete logarithms in a field GF(p) with p a prime of 192 bits. This paper describes an implementation of a discrete logarithm algorithm which shows that primes of under 200 bits, such as that in the Sun system, are very insecure. Some enhancements to this system are suggested.
Many of the fast methods for factoring integers and computing discrete logarithms require the solution of large sparse linear systems of equations over finite fields. This paper presents the results of implementations of several linear algebra algorithms. It shows that very large sparse systems can be solved efficiently by using combinations of structured Gaussian elimination and the conjugate gradient, Lanczos, and Wiedemann methods.
The process of exploring the behavior of nonlinear, dynamical systems can be a time-consuming and tedious process. In this thesis, I have written a program which automates much of the work of an experimental dynamicist. In particular, the program automatically characterizes the behavior of any driven, nonlinear, electrical circuit exhibiting interesting behavior below the 10 Mhz range. In order to accomplish this task, the program can autonomously select interesting input parameters, drive the circuit, measure its response, perform a set of numeric computations on the measured data, interpret the results and decompose the circuit's parameter space into regions of qualitatively distinct behavior. The output is a two-dimensional portrait summarizing the high-level, qualitative behavior of the nonlinear circuit for every point in the graph as well as an accompanying textual explanation describing any interesting patterns observed in the diagram. In addition to the graph and the text, the program generates a symbolic description of the circuit's behavior. This intermediate data structure can then be passed onto other programs for further analysis.
A simple set of extensions to the SCHEME language removes the need for a distinguished top level interaction environment by providing first-class environments. These extensions also provide a powerful mechanism for code packaging and may be used to implement simple object-oriented systems. In addition, a mechanism is presented that implements compiled references to free variables as efficiently as in languages like C, provided the code does not directly manipulate first-class environments. The mechanism requires a simple static analysis performed by the compiler and meshes with a slower mechanism used by both interpreted code and compiled code that manipulates first-class environments.
In this thesis, I designed and implemented a system which autonomously designs optimal CMOS operational amplifiers. Throughout the design search, my system assembles the op amps by composing subcircuits. I evaluate op amps' performances by applying symbolic transformations and numerical techniques to the set of asserted approximate design equations. I also implemented a simulator-based performance evaluator that verifies the optimal designs.
My system controls the optimal design quest with a robust genetic algorithm. I integrate the searches through the topological and design parameter spaces in a novel, unique way. As a result, my system's design search is efficient, exhaustive, global, unbiased, and autonomous.
My system also designs op amps following an alternative strategy inspired by observation of human designers. In addition, my system autonomously generates such strategies.
Finally, I demonstrate my system's ability to autonomously design optimal CMOS op amps through a number of successful design experiments: a minimal area, high speed, micropower, high bandwidth, and high gain optimal designs.
Most physical phenomena are nonlinear in nature and exhibit the complicated and seemingly random behavior known as chaos. Studying chaotic behavior in nonlinear systems requires numerous computations in order to simulate the behavior of such systems. The Standard Map Machine (SMM) was designed and implemented as a special computer for performing these intensive computations with high-speed and high-precision. SMM's impressive performance is due to its simple architecture specialized to the numerical computations required of nonlinear systems. This report discusses the design and implementation of the Standard Map Machine and its use in the study of nonlinear mappings, in particular, the study of the standard map.
Cooperation between independent agents depends upon establishing a degree of security. Each of the cooperating agents needs assurance that the cooperation will not endanger resources of value to that agent. In a computer system, a computational mechanism can assure safe cooperation among the system's users by mediating resource access according to desired security policy. Such a mechanism, which is called a security kernel, lies at the heart of many operating systems and programming environments.
The dissertation describes Scheme 48, a programming environment whose design is guided by established principles of operating system security. Scheme 48's security kernel is small, consisting of the call-by-value lambda-calculus with a few simple extensions to support abstract data types, object mutation, and access to hardware resources. Each agent (user or subsystem) has a separate evaluation environment that holds objects representing privileges granted to that agent. Because environments ultimately determine availability of object references, protection and sharing can be controlled largely by the way in which environments are constructed.
I will describe experience with Scheme 48 that shows how it serves as a robust and flexible experimental platform. Two successful applications of Scheme 48 are the programming environment for the Cornell mobile robots, where Scheme 48 runs with no (other) operating system support; and a secure multi-user environment that runs on workstations.
This paper describes a modified form of Kohlbecker's algorithm for reliably hygienic (capture-free) macro expansion in block-structured languages, where macros are source-to-source transformations specified using a high-level pattern language. Unlike previous algorithms, the modified algorithm runs in linear instead of quadratic time, copies few constants, does not assume that syntactic keywords are reserved words, and allows local (scoped) macros to refer to lexical variables in a referentially transparent manner.
Syntactic closures have been advanced as an alternative to hygienic macro expansion. The problem with syntactic closures is that they are inherently low-level and therefore difficult to use correctly, especially when syntactic keywords are not reserved. It is impossible to construct a pattern-based, automatically hygienic macro system on top of syntactic closures because the pattern interpreter must be able to determine the syntactic role of an identifier (in order to close it in the correct syntactic environment) before macro expansion has made that role apparent.
Kohlbecker's algorithm may be viewed as a book-keeping technique for deferring such decisions until macro expansion is locally complete. Building on that insight, this paper unifies and extends the competing paradigms of hygienic macro expansion and syntactic closures to obtain an algorithm that combines the benefits of both.
Several prototypes of a complete macro system for Scheme have been based on the algorithm presented here.
The report gives a defining description of the programming language Scheme. Scheme is a statically scoped and properly tail-recursive dialect of the Lisp programming language invented by Guy Steele Jr. and Gerald Jay Sussman. It was designed to have an exceptionally clear and simple semantics and few different ways to form expressions. A wide variety of programming paradigms, including imperative, functional and message passing styles, find convenient expression in Scheme.
Macros provide a general way to extend the syntax of a language. A macro defines a new language construct via a syntactic transformation function that rewrites an instance of the new construct as an expression using other language constructs. However, because they are textual rewrite rules, macros suffer from the drawbacks of call-by-text: lexical scoping rules are not obeyed, so free variables in both the uses of the macro and in its definition may be inadvertently captured. Thus the details of the implementation of the macro may be exposed to the macro's clients. A solution to this difficulty is given by a device called syntactic closures. Like an Algol 60 thunk, a syntactic closure packages an expression with its proper lexical context before the expression is substituted into a different context. I have implemented an extended Scheme dialect that supports the practical use of syntactic closures for writing macros in modularly constructed programs.
We present the first system for estimating and using data-dependent expression execution times in a language with first-class procedures and imperative constructs. The presence of first-class procedures and imperative constructs makes cost estimation a global problem that can benefit from type information. We estimate expression costs with the aid of an algebraic type reconstruction system that assigns every procedure a type that includes a static dependent cost. A *static dependent cost* describes the execution time of a procedure in terms of its inputs. In particular, a procedure's static dependent cost can depend on the size of input data structures and the cost of input first-class procedures. Our cost system produces symbolic cost expressions that contain free variables describing the size and cost of the procedure's inputs. At run-time, a cost estimate is dynamically computed from the statically determined cost expression and run-time cost and size information. We present experimental results that validate our cost system on three compilers and architectures. We experimentally demonstrate the utility of cost estimates in making dynamic parallelization decisions. In our experience, dynamic parallelization meets or exceeds the parallel performance of any fixed number of processors.
We developed LEGO/Logo as a type of Artificial Life Construction Kit for children. Using LEGO/Logo, children build artificial creatures using LEGO bricks, motors, gears, and sensors, and they write Logo programs to control the creatures' behaviors. The creatures are wired to a personal computer through a custom interface box.
Braitenberg Bricks is a alternate construction kit that puts computational power inside the LEGO bricks themselves - enabling children to create autonomous, free-ranging creatures. With Braitenberg Bricks, children can construct creatures resembling those described in Valentino Braitenberg's Vehicles. Children "program" the creatures by selecting various Braitenberg Bricks, plugging them onto the creature, and wiring them together. The B-Brick set includes effectors (motors, lights, beepers), sensors (sound, light, touch), and logic elements (and's, or's, flip-flop's).
In a growing number of research fields (including Artificial Life), researchers are adopting self-organization as a paradigm for understanding the workings of the world. But there is a problem: most people have difficulty thinking about and understanding self-organizing phenomena. One solution is to provide people with computational environments in which they can simulate and "play with" self-organizing systems. This paper describes such an environment, designed particularly for pre-college students. The environment, called *Logo, is based on two primary types of objects: turtles (creatures in the world) and patches (pieces of the world). Users can simulate self-organizing behavior by programming local interactions among the turtles and patches. The paper presents three sample *Logo simulations of self-organizing systems. The goal of these simulations (and *Logo in general) is not to perfectly simulate life-like behavior, but rather to help people explore core concepts of self-organization.
In a growing number of computer applications (such as animation, robotics, and desktop video), people need to control several objects at the same time. But concurrent actions are difficult to program with traditional sequential programming languages. This paper describes an extension of Logo, called MultiLogo, that provides new constructs and metaphors for controlling concurrent actions. MultiLogo is designed with non-experts in mind; it places special emphasis on language learnability. To explore how children appropriate new ideas about concurrency, I conducted an experimental study with a group of elementary-school students. The students used MultiLogo to control simple robotic devices built out of LEGO bricks. In analyzing the children's work, I develop three primary categories of MultiLogo programming bugs: problem-decomposition bugs, synchronization bugs, and object-oriented bugs. Based on the results, I recommend ways to improve the design and teaching of concurrent programming languages for non-experts.
This paper describes a mechanism for implementing CLOS method dispatch efficiently on stock hardware, in the current generation of Common Lisp implementations. This mechanism is implemented in the newest version of PCL, a portable implementation of CLOS, and runs in more than ten Common Lisps. This work is based on a careful analysis of the behavior of existing CLOS programs. The method dispatch mechanism differs from previously published work in three important ways. First, the use of a new hashing algorithm improves memoization table density and distribution. Second, the selection of memoization table format based on the dynamic history of each generic function makes it possible to store information in the memoization tables more efficiently and do the runtime method dispatch more quickly. Third, lazy updating techniques are used to speed interactive programming environment response without undue degradation of program execution.
A compiler that automatically chooses a program's parallelization is often unable to choose either the best one or the particular one that a programmer has in mind. This has led to systems that provide the programmer with explicit control over a program's parallelization, for example, via compiler pragmas. The pragma approach is like the metaobject protocol (MOP) approach in that pragmas provide control over what would otherwise be hidden aspects of an implementation. However, it differs because the set of pragmas is fixed, thereby limiting the amount of control provided. We investigated whether it was possible to increase the amount of control using the full MOP approach. We were in fact successful, but the resulting MOP differs from previous ones in that it is present at compile-time rather than at run-time. In this paper, we compare the MOP approach with other approaches, and discuss what is needed in order to produce a production-quality MOP-based statically parallelizing compiler.
Currently, there exist different approaches to parallelizing a computation at a coarse-grain. One approach is to parallelize a computation by placing compiler declarations in the source code. This approach makes it possible to conceptually separate the code describing a computation from the code (i.e. declarations) describing its parallelization. This approach also makes it possible to explicitly control a computation's parallelization, thereby providing an opportunity to increase the computation's performance. However, there are cases when it is not reasonable to expect a desired mechanism for concurrency to be supported by the available, and fixed set of declarations, such as when the desired mechanism is highly specialized to a given computation and target architecture. In these cases, the declaration-based approach fails. In this thesis, we demonstrate that metaobject protocols (MOPs) can solve this problem. Under the MOP approach, a computation is parallelized by marking source code expressions with marks supported by the compiler. Marks, like declarations, are used to separate a computation from its parallelization. When the supported marks can not be used to express a desired mechanism for concurrency, the MOP is used to incrementally augment the compiler's parallelization strategy to support the desired mechanism. The MOP is a model of the compiler's parallelization strategy that provides the knowledge necessary to augment the strategy incrementally, without exposing arbitrary or irrelevant implementation details. In order to demonstrate the effectiveness of the MOP-based approach, we present Anibus, a MOP-based compiler. We give several examples of using marks, and of incrementally augmenting Anibus's parallelization strategy. The examples include two implementations of the n-body gravity problem.
The typical subroutines that compute sin(x) and exp(x) bear little resemblance to our mathematical knowledge of these functions: they are composed of concrete arithmetic expressions that include many mysterious numerical constraints. Instead of programming these subroutines conventionally, we can express their construction using symbolic ideas such as periodicity, Taylor series and economization. Such an approach has many advantages: the code is closer to the mathematical basis of the function, is less vulnerable to errors ans is trivially adaptable to various precisions.
This report introduces translucent procedures as a new mechanism for implementing behavioral abstractions. Like an ordinary procedure, a translucent procedure can be invoked, and thus provides an obvious way to capture a behavior. Translucent procedures, like ordinary procedures, can be manipulated as first-class objects and combined using functional composition. But unlike ordinary procedures, translucent procedures have structure that can be examined in well-specified non-destructive ways, without invoking the procedure.
I have developed an experimental implementation of a normal-order lambda-calculus evaluator augmented with novel reflection mechanisms for controlled violation of the opacity of procedures. I demonstrate the utility of translucent procedures by using this evaluator to develop large application examples from the domains of graphics, computer algebra, compiler design, and numerical analysis.
A computational model of observation in quantum mechanics is presented. The model provides a clean and simple computational paradigm which is used to illustrate and possibly explain some of the unintuitive and unexpected behavior of some quantum mechanical systems. As examples, the model is used to simulate three seminal quantum mechanical experiments. The results obtained agree with predictions of quantum mechanics (and physical measurements), yet the model is perfectly deterministic and maintains a notion of locality.
This thesis explores automating the qualitative analysis of physical systems. Scientists and engineers model many physical systems with ordinary differential equations. They deduce the behavior of the systems by analyzing the equations. Most realistic models are nonlinear, hence difficult or impossible to solve explicitly. Analysts must resort to approximations or sophisticated mathematical techniques. This report describes a program called PLR (for Piecewise Linear Reasoner), that formalizes an analysis strategy employed by experts. PLR takes parameterized ordinary differential equations as input and produces a qualitative description of the solutions for all initial values. It approximates intractable nonlinear systems with piecewise linear ones, analyzes the approximations, and draws conclusions about the original systems. It chooses approximations that are accurate enough to reproduce the essential properties of their nonlinear prototypes, yet simple enough to be analyzed completely and efficiently.
We show that for many physical systems the dependence of attractor basin geometry on parameter variations and noise can be characterized by power laws. We introduce new invariants-the basin immunities-that quantify this dependence and we analyze their origin and properties. Results from extensive numerical experiments are presented; examples include the driven pendulum and the Hénon map. Potential applications of basin immunities include quantifying the effect of parameter uncertainties and noise on the behavior of nonlinear devices, as well as improving parameter estimation algorithms.
We present a novel approach to parameter estimation of systems with complicated dynamics, as well as eveidence for the existence of a universal power law that enables us to quantify the dependence of global geometry on small changes in the parameters of the system. This power law gives rise to what seems to be a new dynamical system invariant.
Efficient parallel computation of fluid dynamics is demonstrated using a cluster of HP9000/700 workstations and a 10Mbps shared-bus Ethernet network. The system is applied to a real problem in fluid flow and acoustics in two-dimensions, and achieves 80% efficiency with 20 workstations. The success of simulations that last several days depends on automatic process migration from busy hosts to free hosts. The performance is measured as a function of the number of processors and grain size. Although good performance is obtained in two-dimensions, poor performance is obtained in three-dimensions because of limited network bandwidth. Two algorithms for simulating fluid dynamics, finite differences and the lattice Boltzmann method, are tested.
An alternative approach of implementing initial and boundary conditions for the lattice Boltzmann method is presented. The basic idea is to calculate the lattice Boltzmann populations at a boundary node from the fluid variables that are specified at this node using the gradients of the fluid velocity. The numerical performance of the lattice Boltzmann method is tested on several problems with exact solutions and is also compared to an explicit finite difference projection method. The discretization error of the lattice Boltzmann method decreases quadratically with finer resolution both in space and in time. The roundoff error of the lattice Boltzmann method creates problems unless double precision arithmetic is used.
A tantalizing version of Maxwell's demon is presented which appears to operate reversibly. A container of hard core disks is separated into two chambers of equal volume by a membrane that selects which disk can penetrate depending on the disk's angle of incidence. It is shown that the second law of thermodynamics requires the incompressibility of microscopic dynamics or an appropriate energy cost for compressible microscopic dynamics.
An automated Maxwell's demon inspired by Smoluchowski's ideas of 1912 is simulated numerically. Two gas chambers of equal area are connected via an opening that is covered by a trapdoor. The trapdoor can open to the left but not to the right, and is intended to rectify naturally occurring variations in density between the two chambers. The simulation results confirm that though the trapdoor behaves as a rectifier when large density differences are imposed by external means, it can not extract useful work from the thermal motion of the molecules when left on its own.
High order multistep methods, run at constant stepsize, are one of the most effective schemes for integrating the Newtonian solar system, for long periods of time. I have studied the stability and error growth of these methods, when applied to harmonic oscillators and two-body systems like the Sun-Jupiter pair. I have found that the truncation error of multistep methods on two-body systems grows in time like t^2, and the roundoff like t^1.5 and I have a theory that accounts for this. I have also tried to design better multistep integrators than the traditional Stormer and Cowell methods, and have found a few interesting ones. A second result of my search for new methods is that I did not find any predictor that is stable on the Sun-Jupiter system, for stepsizes smaller than 108 steps per cycle, whose order of accuracy is greater than 12. For example, Stormer-13 becomes unstable at 108 steps per cycle. This limitation between stability and accuracy seems to be a general property of multistep methods.
Partial evaluation techniques have been known to yield order of magnitude speedups of real-world applications. Despite this tremendous potential, partial evaluators are rarely put to practical use. This is primarily because it is not easy for users to extend partial evaluators to work on their specific applications. This thesis describes Blitzkrieg, a user-extensible online partial evaluator designed to make partial evaluation more accessible to a wider class of users and applications.
Blitzkrieg uses an object system to simplify the implementation of the partial evaluation system and to allow users to easily express their own domain-specific optimizations.
The viability of Blitzkrieg is shown by applying it to the Stormer integrator on a 6-body problem (achieving a factor of 610 speedup) and the Runge-Kutta integrator on the same problem (a factor of 365.5 speedup). In addition, the flexibility of the approach is demonstrated by applying Blitzkrieg to handle port input programs, achieving a factor of 1.35 speedup on a representative program. Finally, Blitzkrieg's ability to do user-expressed domain specific optimizations is demonstrated on a graphics application, achieving a factor of 4.04 speedup.
We describe an approach to parallel compilation that seeks to harness the vast amount of fine-grain parallelism that is exposed through partial evaluation of numerically-intensive scientific programs. We have constructed a compiler for the Supercomputer Toolkit parallel processor that uses partial evaluation to break down data abstractions and program structure, producing huge basic blocks that contain large amounts of fine-grain parallelism. We show that this fine-grain parallelism can be effectively utilized even on coarse-grain parallel architectures by selectively grouping operations together so as to adjust the parallelism grain-size to match the inter-processor communication capabilities of the target architecture.
This thesis demonstrates a compiler that uses partial evaluation to achieve outstandingly efficient parallel object code from very high-level source programs. The source programs are ordinary Scheme numerical programs, written abstractly, with no attempt to structure them for parallel execution. The compiler identifies and extracts parallelism completely automatically; nevertheless, it achieves speedups equivalent to or better than the best observed results achieved by previous supercomputer compilers that require manual restructuring of code.
This thesis represents one of the first attempts to capitalize on partial evaluation's ability to expose low-level parallelism. To demonstrate the effectiveness of this approach, we targeted the compiler for the Supercomputer Toolkit, a parallel machine with eight VLIW processors. Experimental results on integration of the gravitational n-body problem show that the compiler, generating code for 8 processors, achieves a factor of 6.2 speedup over an almost optimal uniprocessor computation, despite the Toolkit's relatively slow interprocessor communication speed. This compares with an average speedup factor of 4.0 on 8 processors obtained at University of Illinois using manual code restructuring of a suite of benchmarks for the Cray YMP.
The evolution of the entire planetary system has been numerically integrated for a time span of nearly 100 million years. This calculation confirms that the evolution of the solar system as a whole is chaotic, with a time scale of exponential divergence of about 4 million years. Additional numerical experiments indicate that the Jovian planet subsystem is chaotic, although some small variations in the model can yield quasiperiodic motion. The motion of Pluto is independently and robustly chaotic.
The Digital Orrery has been used to perform an integration of the motion of the outer planets for 845 million years. This integration indicates that the long-term motion of the planet Pluto is chaotic. Nearby trajectories diverge exponentially with an e-folding time of only 20 million years.
We consider the resonant excitiation of surface waves inside a rectangular wave tank of arbitrary water depth with a flap-type wavemaker on one side. Depending on the length and width of the tank rlative to the sinusoidal forcing frequency of the wave paddle, three classes of resonant mechanisms can be identified. The first two are the well-known synchronous, resonantly forced longitudinal standing waves, and subhormonic, parametrically excited transverse (cross) waves. These have been studied by a number of investigators, notably in deep water. We rederive the governing equations and show good comparisons with the experimental data of Lin and Howard (1960). The third class is new and involves the simultaneous resonance of the synchronous longitudinal and subharmonic cross-waves and their internal interactions. In this case, temporal chaotic motions are found for a broad range of parameter values and initial conditions. These are studied by local bifurcation and stability analysis, direct numerical simulations, estimations of the Lyapunov exponents and power spectra, and examination of Poincare sections. To obtain a global criterion for widespread chaos, the method of resonance overlap (Chirikov, 1979) is adopted and found to be remarkably effective.
SLIVERS are a new approach to expressing computations as combinations of mix-and-match operators on aggregate data. Unlike other aggregate data models, slivers enable programmers to control fine-grained operational aspects of modular programs. In particular, slivers can guarantee that networks of operators exhibit the desirable storage behavior and operation scheduling of intricate loops and recursions. For example, slivers can preserve the space efficiency of a complex tree algorithm when it is expressed as the superposition of simpler tree walks.
The sliver technique is based on a dynamic model of lock step processing that enables combinations of list and tree operators to simulate the operational behavior of a single recursive procedure. Operational control is achieved through SYNCHRONIZED LAZY AGGREGATES, dynamically unfolding data structures that constrain how the processing of separate operators is interwoven. The key to the technique is the SYNCHRON, a novel first-class object that allows a dynamically determined number of concurrently executing operators to participate in a barrier synchronization. Slivers embody a notion of COMPUTATIONAL SHAPE that specifies how the operational patterns of a process can be composed out of the patterns of its components.
The utility of slivers is illustrated in the context of SYNAPSE, a simple language for expressing linear and tree-shaped computations. SYNAPSE is built on top of OPERA, a new concurrent dialect of Scheme that incorporates the concurrency, synchronization, and non-strictness required by the lock step processing model. The semantics of OPERA are explained in terms of EDGAR, a novel graph reduction model based on explicit demand propagation.
Non-uniformities in buffer delays and wire lengths introduce skew in clock distribution trees. Previous techniques exist for eliminating skew introduced by each of these causes, not both. This method uses a pair of matched variable delay lines to eliminate skew caused both by differing buffer delays and wire lengths.
We outline a multiprocessor architecture that uses modular arithmetic to implement numerical computation with 900 bits of intermediate precision. A proposed prototype, to be implemented with off-the-shelf parts, will perform high-precision arithmetic as fast as some workstations and mini-computers can perform IEEE double-precision arithmetic. We discuss how the structure of modular arithmetic conveniently maps into a simple, pipelined multiprocessor architecture. We present techniques we developed to overcome a few classical drawbacks of modular arithmetic. Our architecture is suitable to and essential for the study of chaotic dynamical systems.
Does knowledge of language consist of symbolic rules? How do children learn and use their linguistic knowledge? To elucidate these questions, we present a computational model that acquires phonological knowledge from a corpus of common English nouns and verbs. In our model the phonological knowledge is encapsulated as boolean constraints operating on classical linguistic representations of speech sounds in term of distinctive features. The learning algorithm compiles a corpus of words into increasingly sophisticated constraints. The algorithm is incremental, greedy, and fast. It yields one-shot learning of phonological constraints from a few examples. Our system exhibits behavior similar to that of young children learning phonological knowledge. As a bonus the constraints can be interpreted as classical linguistic rules. The computational model can be implemented by a surprisingly simple hardware mechanism. Our mechanism also sheds light on a fundamental AI question: How are signals related to symbols?
Humans rapidly and reliably learn many kinds of regularities and generalizations. We propose a novel model of fast learning that exploits the properties of sparse representations and the constraints imposed by a plausible hardware mechanism. To demonstrate our approach we describe a computational model of acquisition in the domain of morphophonology. We encapsulate phonological information as bidirectional boolean constraint relations operating on the classical linguistic representations of speech sounds in term of distinctive features. The performance model is described as a hardware mechanism that incrementally enforces the constraints. Phonological behavior arises from the action of this mechanism. Constraints are induced from a corpus of common English nouns and verbs. The induction algorithm compiles the corpus into increasingly sophisticated constraints. The algorithm yields one-shot learning from a few examples. Our model has been implemented as a computer program. The program exhibits phonological behavior similar to that of young children. As a bonus the constraints that are acquired can be interpreted as classical linguistic rules.
High-level understanding of data must involve the interplay between substantial prior knowledge with geometric and statistical techniques. Our approach emphasizes the recovery of basic structural elements and their interaction patterns in order to summarize and draw inferences about the significant features contained in the data. As a testbed for modeling how scientists analyze and extract knowledge of structure morphogenesis from data, we examine the datasets obtained from numerical simulation of turbulence. We describe a program that automatically extracts 3D structures, classifies them geometrically, and analyzes their spatial and temporal coherence. Our program is constructed by mixing and matching the aggregate, classify, and re-describe operators of the spatial aggregation language. The research is a continuation of the effort to investigate the role of imagistic reasoning in human thinking.
Visual thinking plays an important role in scientific reasoning. Based on the research in automating diverse reasoning tasks about dynamical systems, nonlinear controllers, kinematic mechanisms, and fluid motion, we have identified a style of visual thinking, {\em imagistic reasoning}. Imagistic reasoning organizes computations around image-like, analogue representations so that perceptual and symbolic operations can be brought to bear to infer structure and behavior. Programs incorporating imagistic reasoning have been shown to perform at an expert level in domains that defy current analytic or numerical methods.
We have developed a computational paradigm, {\em spatial aggregation}, to unify the description of a class of imagistic problem solvers. A program written in this paradigm has the following properties. It takes a continuous field and optional objective functions as input, and produces high-level descriptions of structure, behavior, or control actions. It computes a multi-layer of intermediate representations, called spatial aggregates, by forming equivalence classes and adjacency relations. It employs a small set of generic operators such as aggregation, classification, and localization to perform bidirectional mapping between the information-rich field and successively more abstract spatial aggregates. It uses a data structure, the {\em neighborhood graph}, as a common interface to modularize computations. To illustrate our theory, we describe the computational structure of three implemented problem solvers -- {\sc kam}, {\sc maps}, and {\sc hipair} --- in terms of the spatial aggregation generic operators by mixing and matching a library of commonly used routines.
A new kind of symbolic program to aid the heuristic simplification of fluid models is presented. The program, AOM, employs order of magnitude analysis and method of dominant balance to generate simplified models. It has two novel features: (1) it uses heuristic techniques to decide what equations to solve and what algebra to do, and (2) it explains its deduction steps. The basic operation of AOM consists of five steps: (1) assign order of magnitude estimates to terms in the equations, (2) find maximal terms of each equation, i.e., terms that are not dominated by any other terms in the same equation, (3) consider all possible n-term dominant balance assumptions, (4) propagate the effects of the balance assumptions, and (5) remove partial models based on inconsistent balance assumptions. AOM also exploits constraints among equations and submodels to simplify complicated fluid models such as the triple deck equations. Three annotated examples are presented to explain the operations of AOM. The implications for the development of computer-aided analysis programs for fluid dynamics and education are discussed.
One of the important problems in reasoning about a physical system is finding an approximate model that is mathematically tractable and yet captures the essence of the problem. This paper describes an implemented program AOM which automates a powerful simplification method. AOM is based on two domain-independent ideas: self-consistent approximations and asymptotic order of magnitude reasoning. The basic operation of AOM consists of five steps: (1) assign order of magnitude estimates to terms in the equations, (2) find maximal terms of each equation, i.e., terms that are not dominated by any other terms in the same equation, (3) consider all possible n-term dominant balance assumptions, (4) propagate the effects of the balance assumptions, and (5) remove partial models based on inconsistent balance assumptions. AOM also exploits constraints among equations and submodels. We demonstrate its power by showing how the program simplifies difficult fluid models described by coupled nonlinear partial differential equations with several parameters. We believe the derivation given by AOM is more systematic and easily understandable than those given in published papers.
KAM is a computer program that can automatically plan, monitor, and interpret numerical experiments with two degrees of freedom. The program has recently helped solve an open problem in hydrodynamics - the prediction of onset of chaos in a resonantly excited rectangular wave tank of finite depth. Unlike other approaches to qualitative reasoning about physical system dynamics, KAM embodies a significant amount of knowledge about nonlinear dynamics. KAM's ability to control numerical experiments arises from the fact that it not only produces pictures for us to see, but it also looks at (in its "mind's eye") the pictures that it draws to guide its own actions. By combining techniques with sophisticated dynamical invariants, KAM is able to exploit mathematical knowledge, represented in terms of a ``grammar'' that dictates consistency constraints on the structure of the phase space and parameter space. KAM is organized in three semantic levels: orbit recognition, phase-space searching, and parameter-space searching. Within each level spatial properties and relationships that are not explicitly represented in the initial representation are extracted by applying three operations - (1) aggregation, (2) partition, and (3) classification - iteratively.
Even with powerful numerical computers, exploring complex dynamical systems requires significant human effort and judgement to prepare simulations and interpret numerical results. This paper describes one aspect of a computer program, KAM, that can autonomously prepare numerical simulations and can automatically generate high-level, qualitative interpretations of quantitative results.
The phase space is a powerful tool for representing and reasoning about the qualitative behavior of non-linear dynamical systems. Significant physical phenomena of the dynamical system - periodicity , recurrence, stability and the like - are reflected by outstanding geometric features of the trajectories in the phase space. Successful use of numerical computations to completely the dynamics of phase space depends on the ability to (1) interpret the numerical results, and (2) control the numerical experiments. This paper presents an approach for automatic reconstruction of the full dynamical behavior from the numerical results.
We describe the automatic synthesis of a global nonlinear controller for stabilizing a magnetic levitation system. The synthesized control system can stabilize the maglev vehicle with large initial displacements from an equilibrium, and possesses a much larger operating region than the classical linear feedback design for the same system.
The controller is automatically synthesized by a suite of computational tools. This work demonstrates that the difficult control synthesis task can be automated, using programs that actively exploit knowledge of nonlinear dynamics and state space and combine powerful numerical and symbolic computations with spatial-reasoning techniques.
We describe the automatic synthesis of a global nonlinear controller for stabilizing a magnetic levitation system. The synthesized control system can stabilize the maglev vehicle with large initial displacements from an equilibrium, and possesses a much larger operating region than the classical linear feedback design for the same system.
The controller is automatically synthesized by a suite of computational tools. This work demonstrates that the difficult control synthesis task can be automated, using programs that actively exploit knowledge of nonlinear dynamics and state space and combine powerful numerical and symbolic computations with spatial-reasoning techniques.
Generality, representation, and control have been the central issues in machine recognition. Model-based recognition is the search for consistent matches of the model and image features. We present a comparative framework for the evaluation of different approaches, particularly those of Acronym, Raf, and Ikeuchi et al. The strengths and weaknesses of these approaches are discussed and compared and the remedies are suggested. Various tradeoffs made in the implementations are analyzed with respect to the systems' intended task-domains. The requirements for a versatile recognition system are motivated. Several directions for future research are pointed out.
We develop computational mechanisms for intelligently simulating nonlinear control systems. These mechanisms enhance numerical simulations with deep domain knowledge of dynamical systems theory and control theory, a qualitative phase-space representation of dynamical systems, symbolic and geometric manipulation capabilities, and a high-level interface. Programs equipped with these capabilities are able to autonomously simulate a dynamical system, analyze the simulation results, and utilize the analysis to perorm design tasks. We demonstrate the mechanisms with an implemented computational environment called the Control Engineer's Workbench.
We develop a qualitative method for understanding and representing phase space structures of complex systems. To demonstrate this method, a program called MAPS has been constructed that understands qualitatively different regions of a phase space and represents and extracts geometric shape information about these regions, using deep domain knowledge of dynamical system theory. Given a dynamical system specified as a system of governing equations, MAPS applies a successive sequence of operations to incrementally extract the qualitative information and generates a complete, high level symbolic description of the phase space structure, through a combination of numerical, combinatorial, and geometric computations and spatial reasoning techniques. The high level description is sensible to human beings and manipulable by other programs. We are currently applying the method to a difficult engineering design domain in which controllers for complex systems are to be automatically synthesized to achieve desired properties, based on the knowledge of the phase space ``shapes'' of the systems.
We develop a novel autonomous control synthesis strategy called Phase Space Navigator for the automatic synthesis of nonlinear control systems. The Phase Space Navigator generates global control laws by synthesizing flow shapes of dynamical systems and planning and navigating system trajectories in the phase spaces. Parsing phase spaces into trajectory flow pipes provide a way to efficiently reason about the phase space structures and search for global control paths. The strategy is particularly suitable for synthesizing high-performance control systems that do not lend themselves to traditional design and analysis techniques.
This paper reports on a fast implementation of the three-dimensional non-adaptive Parallel Multipole Method (PMM) on the Connection Machine system model CM-2. The data interactions within the decomposition tree are modeled by a hierarchy of three dimensional grids forming a pyramid in which parent nodes have degree eight. The base of the pyramid is embedded in the Connection Machine as a three dimensional grid. The standard grid embedding feature is used. For 10 or more particles per processor the communication time is insignificant. The evaluation of the potential field for a system with 128k particles takes 5 seconds, and a million particle system about 3 minutes. The maximum number of particles that can be represented in 2G bytes of primary storage is ~50 million. The execution rate of this implementation of the PMM is at about 1.7 Gflops/sec for a particle-processor-ratio of 10 or greater. A further speed improvement is possible by an improved use of the memory hierarchy associated with each floating-point unit in the system.
Generality, representation, and control have been the central issues in machine recognition. Model-based recognition is the search for consistent matches of the model and image features. We present a comparative framework for the evaluation of different approaches, particularly those of ACRONYM, RAF, and Ikeuchi et al. The strengths and weaknesses of these approaches are discussed and compared and the remedies are suggested. Various tradeoffs made in the implementations are analyzed with respect to the systems' intended task-domains. The requirements for a versatile recognition system are motivated. Several directions for future research are pointed out.