Search

The central question addressed by the project is how humans learn complex visualmotor tasks. Can we construct a model of human learning of such tasks based purely on visualmotor performance data? We answer this question in the affirmative. From a large sequential corpus of visualmotor data gathered from human subjects during learning, We track the evolution of control policies as subjects make the transition from being novices to becoming task experts. The visualmotor data is non-stationary; it is characterized by periods of slow evolution punctuated by conceptual shifts in which policies, change radically. We have developed algorithms that build and track models of control policies across these conceptual shifts. These models are rich enough to capture individual differences in the task, and are simple enough to learn in real-time. That is, we have developed methods for learning objective models of cognitive activity (instead of relying on objective verbal reconstructions) by observing the time course of visualmotor performance. These models can be used to shape and speed up the training of human subjects on complex visualmotor tasks with significant strategic components.

This project investigated a number of problems that arise in compiling application code for embedded systems. These systems present the compiler with a number of challenges that arise from economic constraints, physical constraints, and idiosyncratic requirements of the application and processors. The project developed new techniques in optimization and code generation that addressed problems including code size reduction, instruction scheduling, data placement (on partitioned register set machines), spill code reduction, and operator strength reduction. It also produced fundamental work on transformation ordering., The original document contains color images.

This paper provides a methodology for the systematic derivation of subdivision schemes that model solutions to inhomogeneous order linear differential equations. In previous work, we showed that subdivision can be used to capture very efficiently the solutions of homogeneous order, linear differential equations. The resulting subdivision masks are stationary and can be precomputed, allowing for very simple and fast application of these schemes. In this paper, we show that this method can be extended to express solutions of systems of inhomogeneous order, linear differential equations. Even though the resulting subdivision masks may be non-stationary, the masks can again be precomputed. Thus, the resulting subdivision schemes capture very efficiently solutions of inhomegeneous order, linear partial differential equations., Presented at Intl. Conference on Curves and Surfaces (4th). Held in St. Malo, France, 1-7 Jul 1999. Publ. in Proceedings, v2, Curve and Surface Fitting, p411-420. This article is from ADA399401 International Conference on Curves and Surfaces (4th), Saint-Malo, France, 1-7 July 1999. Proceedings, Volume 2. Curve and Surface Fitting

Resultants are the standard tool used to compute the implicit equation of a rational curve or surface. Here we present a new way to compute the implicit equation of a rational curve by taking the determinant of a matrix having the style of the Sylvester resultant but the size of the Bezout resultant. Thus the new method has the advantages of both resultant schemes, representing the implicit equation as the determinant of a matrix with simple linear entries and lots of zeros just like the Sylvester resultant, but with the same small size as the Bezout resultant., Presented at Intl. Conference on Curves and Surfaces (4th). Held in St. Malo, France, 1-7 Jul 1999. Publ. in Proceedings, v1, Curve and Surface Design, p17-26. This article is from ADA399461 International Conference on Curves and Surfaces (4th), Saint-Malo, France, 1-7 July 1999. Proceedings, Volume 1. Curve and Surface Design

Sender-based message logging supports transparent fault tolerance in distributed systems in which all communication is through messages and all processes execute deterministically between received messages. It uses a pessimistic message logging protocol that requires no specialized hardware. Sender-based message logging differs from previous message logging methods in that it logs each message in the local volatile memory of the machine from which it was sent, thus greatly reducing the overhead of message logging.

A causal distributed breakpoint is initiated by a sequential breakpoint in one process of a distributed computation, and restores each process in the computation to its earliest state that reflects all events that happened before the breakpoint. A causal distributed breakpoint is the natural extension for distributed programs of the conventional notion of a breakpoint in a sequential program. We present an algorithm for finding the causal distributed breakpoint given a sequential breakpoint in one of the processes. Approximately consistent checkpoint sets are used for efficiently restoring each process to its state in a causal distributed breakpoint. Causal distributed breakpoints assume deterministic processes that communicate solely by messages. The dependencies that arise from communication between processes are logged. Dependency logging and approximately consistent checkpoint sets have been implemented on a network of SUN workstations running the V-System. Overhead on the message passing primitive varies between 1 and 14 percent for dependency logging. Execution time overhead for a 200 x 200 Gaussian elimination is less than 4 percent, and generates a dependency log of 288 kilobytes., Sponsored in part by Grant NSF-CDA86-19893.

In a distributed system using rollback recovery, information saved on stable storage during failure-free execution allows certain states of each process to be recovered after a failure. For example, in a deterministic system using message logging and checkpointing, a process state can be recovered only if all messages received by the process since its previous checkpoint have been logged. In a nondeterministic system using checkpointing alone, a process state can be recovered only if it has been recorded in a checkpoint. Optimistic rollback recovery methods in general record this information asynchronously, assuming that a suitable recoverable system state can be constructed for use during recovery. A system is called recoverable if and only if it is consistent and the state of each individual process in that system state can be recovered. This paper shows that in any system using optimistic rollback recovery, there is always a unique maximum recoverable system state, extending our previous result for systems using message logging and checkpointing. We also present a simple new algorithm for finding the maximum recoverable system state, and describe some experience with its implementation. These results can be applied to deterministic and to nondeterministic systems.

In a distributed system using message logging and checkpointing to provide fault tolerance, there is always a unique maximum recoverable system state, regardless of the message logging protocol used. The proof of this relies on the observation that the set of system states that have occurred during any single execution of a system forms a lattice, with the sets of consistent and recoverable system states as sublattices. The maximum recoverable system state never decreases, and if all messages are eventually logged, the domino effect cannot occur. This paper presents a general model for reasoning about recovery in such a system and, based on this model, an efficient algorithm for determining the maximum recoverable system state at any time. This work unifies existing approaches to fault tolerance based on message logging and checkpointing, and improves on existing methods for optimistic recovery in distributed systems.

Fault tolerance can allow processes executing in a computer system to survive failures within the system. This thesis addresses the theory and practice of transparent fault-tolerance methods using message logging and checkpointing in distributed systems. A general model for reasoning about the behavior and correctness of these methods is developed, and the design, implementation, and performance of two new low-overhead methods based on this model are presented. No specialized hardware is required with these new methods. The model is independent of the protocols used in the system. Each process state is represented by a dependency vector, and each system state is represented by a dependency matrix showing a collection of process states. The set of system states that have occurred during any single execution of a system forms a lattice, with the sets of consistent and recoverable system states as sublattices. There is thus always a unique maximum recoverable system state. (KR)