Colloquium Series - Spring 1998

By - James E. Smith

A fundamentally new generation of processor organization, or microarchitecture, appears only once in about 20 years, and each generation enables substantially higher levels of processor performance. Thus far, processors have passed from being serial to pipelined to superscalar. Commercial products belonging to the next generation will likely appear in the middle of the next decade. This talk begins with a brief discussion of technology trends that will drive the development of next generation microarchitectures; key technology trends are very high transistor counts and the domi nance of on-chip wire delays.

Overall characteristics of next generation processors will be discussed; these processors will likely rely on multiple processing elements with a new level of control hierarchy to manage them. A number of supporting microarchitectural technologies must be developed to enable next generation processors. Several of these technologies, including high level control flow prediction, trace caching, instruction pre-processing, and data value prediction will be described. These technologies, and others, will likely dominate microarchitecture research for the next several years.

By - Gary Leavens

We will explore the design of Java, especially compared with C++. Java will be considered from several points of view: as a language design, as a tool for practical programming, and as a teaching vehicle. As a language design Java is fairly conservative. However, compared with C++ it has several useful features, including garbage collection, more extenssive use of exceptions, and threads. Unfortunately, Java does not have templates. As(31) Library book a practical programming tool, Java is less flexible than C++, but that seems to make it easier for most people to use. Java's simplicity, portability, and standard libraries also seem to make it good for teaching.

By - David A. Schmidt

This tutorial presentation simplifies and clarifies Bernhard Steffen's depiction of data flow analysis (``dfa'') as model checking: By employing Cousot-Cousot-style abstract interpretation (``ai'') to generate program traces and by utilizing Kozen's modal mu-calculus to express trace properties, we express in simplest possible terms that a dfa is a model check of a program's ai trace. In particular, the classic flow equations for bit-vector-based dfas reformat trivially into modal mu-calculus formulas. A surprising consequence is that two of the classical dfas are exposed as unsound; this problem is analyzed and simply repaired. In the process of making the above discoveries, we clarify the relationship between ai and dfa in terms of the often-misunderstood notion of ``collecting semantics'' and we highlight how the research areas of flow analysis, abstract interpretation, and model checking have grown together.

By - Don Heller

We have the opportunity, and perhaps the obligation, to equip systems and programs with long-term measurement capability. The costs, technical problems, and potential benefits will be discussed. System characterization, performance prediction, and algorithm adaptability, are fundamentally different problems when computing on local or national platforms. Separating the factors of system performance should not become a strenuous exercise in statistical analysis.

By - Al Baker

Unarguably there is a far greater range of types of software development tools in use today than in, say, 1985. One of the questions for academic departments training students to work in Information Technology (IT) into the next millennium is whether the current curricula are providing students with the necessary foundation of knowledge to work with these tools. In this talk we will enumerate some of the categories of tools currently in use and attempt to extract some of the "thinking skills" required of developers to successfully use these tools. At the conclusion of the talk we can speculate on whether the requisite set of "thinking skills" has shifted or grown in the last 15 years.

By - James Smith

A model for program predictability is defined and studied. The model consists of a graph, the Dynamic Prediction Graph, based on dynamic dependences. Nodes correspond to instructions and arcs are labeled with the predictability of instruction inputs and outputs. Underlying the model is a value predictor. Three such predictors are considered: last value, stride, and context based. We take the view that program predictability originates at certain points during a program's execution, flows through subsequent instructions, and then predictability ends at other points in the program. In terms of the model, these key components of predictability -- generation, propagation, and termination -- are defined and studied. It is shown that most predictability flows from immediate values, although control flow (loops) are also a very important factor. Write once data and repeated use of input data values are also significant contributors, but sequence patterns in data input are not. Possible applications of the model are described as a starting point for discussion.

The Class Validation System

By- Marybeth Gurski

Traditionally, rigorous software testing occurs at the end of the software development cycle -- errors found at this time may be costly to correct. Many software development techniques and strategies have attempted to integrate the testing phase earlier into the development cycle. The Class Validation System provides additional rigor to the software development process by integrating formal specifications into software testing. It allows testing before implementation of the components via directly executing the specification and automatically testing an implementation against the specification. Formal specification provides a way to describe software behavior precisely. Use of formal specifications allows implementations to be proven correct (with respect to the specification) using formal proof techniques. Because it is simpler and more convenient than formal proofs of correctness, software testing remains the primary method of ensuring software quality. Traditional software testing does not provide a way to easily test against a formal specification, or even to test the specification itself. This research brings formal specifications and testing together. The Class Validation System supports rigorously testing a formal specification of a software component, and a corresponding implementation. Sufficient testing of a software component is something that is important to consider when developing a software testing tool such as this one. Thorough testing requires using large numbers of test cases. The Class Validation System provides support for automatic generation of values to be used in the testing of the specification and a corresponding implementation. Two methods have been developed for generating abstract values -- values used in testing a specification. One of these methods readily supports generating values for an implementation. These methods and how they aid the testing process as supported by the Class Validation System will be the focus of this presentation.

Visual Cryptography

By - Douglas Stinson

Visual Cryptography was introduced at EUROCRYPT '94 by Naor and Shamir. A (t,w) visual threshold scheme is a method to encode a secret image, consisting of black and white pixels, into w shadow images called shares, such that any t of the shares enable the visual recovery of the secret image. The visual recovery consists of xeroxing the shares onto transparencies, and then stacking them. Any t shares will reveal the secret image without any cryptographic computation. However, no information about the image can be obtained by examining any t-1 shares, even with infinite computational resources. This seemingly impossible problem can be solved if we allow the recovered image to have lower contrast than the original image. It is therefore of interest to construct schemes that minimize this loss of contrast. For example, in a (2,2) visual threshold scheme, the optimal solution involves a 50% loss of contrast. In this talk, we discuss basic construction methods, and bounds on the contrast, for (t,w) visual threshold schemes. We concentrate on (2,w) schemes, which are the cases of greatest practical interest. For (2,w) schemes, essentially complete results are known. This talk is based on joint work with C. Blundo and A. De Santis of the University of Salerno, Italy.

By Karthik Balakrishnan

The ability to successfully navigate in a wide range of {\em a-priori} unknown and often dynamic environments is essential to the survival of animals. Indeed, animals employ a wide variety of mechanisms to acquire representations of their spatial environments and effectively localize within them. The {\em hippocampal formation} (a region of the brain) is believed to play a critical role in spatial learning and localization in animals, particularly rodents. In this talk, we will review relevant neurobiological and cognitive data concerning hippocampal involvement in animal spatial learning, and explore their relationship to models of robot spatial learning. We will also develop a computational model of hippocampal spatial function and characterize it using {\em Kalman filter} based tools for information fusion from multiple uncertain sources. In particular, the resulting computational model allows the simulated animal to learn metric spatial maps of its environment and to fuse incrementally-acquired local maps into global ones. These maps allow the animal to localize in the environment in a stochastically optimal manner. The model also includes a mechanism for learning and representing goal locations, allowing the simulated animal to navigate in a goal-directed fashion. The contributions of this model in the explanation of neuroscientific and behavioral data will be highlighted and its implications for robot spatial learning and navigation will be discussed.

By - Robyn Lutz

Reuse of software requirements is a natural extension of code reuse, potentially offering cost savings, faster development, and reduced defects. In requirements reuse for safety-critical domains, the biggest obstacle is that the requirements must be demonstrably hazard-free. This talk reports work on several methods for safe reuse of software requirements that have proven effective. First, techniques for safety analysis of a product family approach to reusable requirements are described. The application of these techniques to a line of flight instrumentation displays for commercial aircraft is presented. Second, the reuse of a requirements model on the fault protection software for two spacecraft is described. The requirements model was formally specified and verified prior to its reuse. The talk concludes by outlining some current work on reusable requirements for spaceborne interferometers and remote (deep space) sampling.

By - Larry Snyder