MIT Department of Electrical Engineering & Computer Science

Master Works: a showcase for oral presentations of Master's theses.

Monday, May 1, 1995 . . . Program

Abstracts:

McLurkin (Brooks)

Micro-Robot design and construction

This talk describes the design and construction of autonomous cubic-inch robots. The robots are built using a new technique that permits electromechanical intergration at the printed-circuit board level. this level of intergration allows the robots to incorporate many sensors and actuators, while still remaining simple enough to construc in the lab. Dubbed the Ants, these robots have been designed to operate in a community, with the ultimate project goal being the implementation of a robotic ant colony.

----

Scassellati, Brian (Stein)

High-Level Perceptual Contours from a Variety of Low-Level Physical Features

For years, researchers in machine vision have focused on extracting object boundary information from luminance derivatives, color contrast, depth information, and textural patterns. However, no single one of these methods is sufficient for detecting all of the contour information that humans perceive. Humans have little difficulty discriminating depth-based contours from the fused images in a stereogram, extracting illusory contours from a Kanizsa square, or even in completing contours through the blind spot.

This work is concerned with combining various methods of edge identification into a perceptual contour identifier. I will present a background on the psychophysical data that supports each of these individual methods as means of boundary detection, offer a brief critique of some current vision architectures, and describe a novel visual processing framework that deals with contours as a high-level image feature. Finally, I will demonstrate the operation of this system on real-world images using a prototype active vision head that was designed to support this visual architecture.

Carney (Troxel)

Message-passing tools for software integration

The Communications Applications Handling Application Tool Suite (CHAT) provides the programmer with a suite of libraries that can be used to integrate software programs by means of peer-to-peer messages. There are three libraries of routines, providing support for packaging data into messages, handling incoming messages, and application connection. All three libraries are implemented both in C and Tcl/Tk, a scripting language and toolkit for creating graphical user interfaces under X-windows. The CHAT suite allows arbitrary combinations and architectures of C programs and Tcl/Tk programs to exchange messages. Libraries in the CHAT suite have been used to integrate a new factory display program into CAFE, MIT's Computer-Aided Fabrication Environment.

----

Zondervan (Liskov)

Increasing cross-domain call batching using promises and batched control structures

One way of guaranteeing data integrity in a client-server system is through separation of the client and serverinto distinct protecton domains. Such separation can be achieved by restricting the communication between client and server to a well-defined set of cross-domain calls. However, cross-domain calls are expensive and seriously affect the performance of the system. In his work on balanced futires, Bogle presents a mechanism that allows cross-domain calls to be batched, thus amortizing the overhead of the domain crossing.

In this work, we describe two mechanisms that can be used to improve the average size of batches (the batching factor): basic value promises and batched control structure. Basic value promises allow the batching of calls that return basic values (e.g., integers, booleans, characters, and reals). Batched control structures allow the batching of simple control-flow statements. Both mechanisms have been implemented in thor, an object-oriented database system.

---

Hadjicostis (Verghese)

Fault-tolerant computation in semigroups and semirings

Systems designed with the ability to detect and, if possible, correct internal failures are called fault-tolerant. The traditonal approach to fault-tolerant computation has been via modular redundancy. Although universal and simple, modular redundancy is inherently expensive and inefficient.

By exploiting particular structural features of a computation or an algorithm, recently developed Algorithm-Based Fault Tolerance (ABFT) techniques manage to offer more effective fault coverage at the cost of narrower applicability and harder design. In the special case of arithmetic codes, previous work has shown that a variety of useful results and constructive procedures can be obtained when the computations take place in an abelian group.

In this work, we develop a systematic algebraic approach for computations occurring in an abelian semigroup, thereby extending to a much more general setting many of the results obtained for the earlier group case.

Luchangco, (Lynch)

Using Simulation-Based Techniques to Prove Timing Properties

This work presents a methodology based on simulations and invariants for proving timing properties of real-time, distributed systems. This methodology is used to prove tight time bounds for two systems, a leader election protocol for a ring of processes, and Fischer's timing-based mutual exclusion algorithm. A framework for verifying these proofs using the Larch tools is also developed, and the proof for Fischer's algorithm is checked within this framework.

Many formal methods have been developed for proving the correctness of untimed distributed systems. However, real-time systems often have subtle timing dependencies that are difficult to analyze and reason about. Furthermore, for many real-time systems, correctness is insufficient; it is important to satisfy certain performance requirements. It is necessary, therefore, to extend the formal models and techniques to the timed setting. We use a timed automaton model, together with simulations which establish that one automaton implements another. The methodology presented here exploits the strengths of simulation-based techniques, and is demonstrated to be applicable to real-time systems, for proving performance, as well as correctness, properties. The resulting proofs are rigorous and systematic, and have a hierarchical structure that appears to scale reasonably to large systems. In addition, they are amenable to automated verification.

---

Reiss (Finn)

Message routing in Level I of the Wide-Band All-optical network

Optical fibers can support terabit-per-second transmission. However, modern electronic components are limited to gigabit-per-second rates. This creates an electronic bottleneck when electro-optical networks are constructed. A communication network comprised solely of optical components would avoid this bottleneck. Such a network is being built by the Wide-Band All Optical Network (AON) Consortium, whose members are AT&T, Digitial Equipment Cporporation, and MIT.

In this work, we develop a method for optimally configuring the network to maximize network throughput. We show analytially that the resulting resource allocation algorithm's performance in close to that of an ideal algorithm, and we use simmulation to compare its performnace with that of other possible algorithms.

---

Lew (Kaashoek / Johnson)

A case study of shared-memory and message-passing: The triangle puzzle

We descrbe the first controlled case study that compares shared-memory and message-passing implementations of an application that sovles the triangle puzzle and runs on actual hardware. The implementation runs on the MIT Alewife machine, a cache-coherent, distributed-shared-memory multiprocessor that efficiently supports bot the shared memory and message-passing programming models. The goal of the triangle puzzle is to count the number of solutions to a simple puzzle in which a set of pegs, arranged in a triangle, is reduced to one peg by jumping over and removing another peg, as in checkers.

For our application, we observe a maximum of 52% performance improvement of a message-passing implementation over the best shared-memory one that uses both synchronization and data transfer. We also observe a maxmimum of 14% improvement of shared-memory over message-passing when there is low contention. Thus, sometimes message-passing is better than shared memory, and sometimes the reverse is true, and we advocate parallel machines that efficiently support both communication styles.

Pioch (Zeltzer)

Officer of the Deck: Validation of a virtual environment for training

The U.S. Naval Training Center and Office of Naval Research are supporting a research effort at MIT in building virtual environments, immersive computer-generated worlds, for training purposes. Under the Virtual Environment Technology for Training (VETT) initiative, a prototype simulator for training a naval submarine officer called the Officer of the Deck (OOD) has been implemented on a testbed of distributed commercial graphics workstations and VE devices. This thesis gives an in-depth validation of the VE along three main dimensions: autonomy (computational models), interaction (logical interface), and presence (number and fidelity of sensors and displays).

The thesis begins with a task description and analysis of the responsibilities of the OOD. This is then used as a basis for specification of the requirements of the prototype simulator, which models only the most essential task elements. The next section describes the implementation of the prototype, including both hardware and software components. The requirements and the implementation are also described using Zeltzer's Autonomy-Interaction-Presence taxonomy for VE's (Zeltzer, 1992).

The validation explores each dimension of the implementation and checks that the requirement specifications for the prototype simulator are satisfied. Techniques used in the validation include unit tests on the voice recognition system, mathematical verification of object locations, experiments with object recognition in the visual display, integrated testing of correctness of course information, and formal evaluation by domain experts. Such a validation is necessary before performing further experiments to determine the ``training transfer'' value of the simulator. The thesis concludes with general remarks about VE validation techniques and brief examples of their application to other VE training tasks.

---

Sakhuja (Lester / Tennenhouse)

Air interface standards for digital mobile cellular systems

Regualtors in the US, Europe, and Japan have proceeded in very different ways in establishing standards for the digital mobile cellular industry. This work traces the history of the standards-making process in an attempt to explain some of the differences in these approaches. I analyze the decisions surrounding the use of a single digitial standard, the bandwidth allocation procedure, channel spacing, voice codec, and modulation schemes. I conclude by explaining how these decisons have left technology in very different places in these regions and describe some of the strengths and weaknesses of each region's decision-making process.

Moyne (Boning)

Run-by-run control: Interfaces, Implementation, and Integration

Run-by-run (RbR) control is a form of adaptive modeling based onprocess control where recipe changes are performed between runs of the process. Itis becomig popular in the areaof VLSI processing, but its acceptance has been hindered by the integration issues. Existing systems cannon be replaced due to massive capital investments, so the RbR controller must mesh with these systems without requiring large modifications. Two steps have been taken to ease this integration. First, an abstract data model has been developed for RbR control which can be easily communicated between modules. Second,a three-tier communication modelhas been developed to allow multiple levels of interaction with the RbR control module.

An RbR control server has been implemented to demonstrate the robustness of the communication modeland data abstraction. This server provided RbR control to a variety of clients via TCP/IP network sockets. One of these clients is a graphical user interface that allows direct operation of of the control algorithms. The controller has been integrated into a local computer-intergrated manufacturing (CIM) system, as well as a control framework being developed by the University of Michigan and SEMATECH.

---

White (Boning / Athans)

In-situ wafer uniformity estimation using principal components analysis and function approximation methods

For semiconductor processes there exist constraints on both sensor technology and process repeatability taht require improvements in system identification and estimation methods for diagnostics and control. It has been shown that optical emission spectroscopy (OES) can provide information regarding process conditions during plasma etch. However, this information is often buried among a wide range of sepctral measurements that hinder real-time processing.

This work presents a real-time estimation appraoch that correlates multivariable sensor data during a plasma etch to estimate two wafer state characteristics: line reduction and etch time. The estimator combines principal component analysus with conventional and learning-algorithm-based function approximation. The approach is verified for two different experimental designs: the first is for a polysilicon etch wirh an Applied Materials Precision 5000 etcher at MIT. The second is for an aluminum etch usig a Lam 9600 etcher at Texas Instruments.

---

Sinn (Bennet / del Alamo)

Characterzation of surface roughness on mismatched InAlAs epitaxial layers on InP

Epitaxial layers of InAlAs on InP substrates are attractive for optoelectronic applications. While the lattice-matched variant, In[0.52]Al[0.48]As, has been applied extensively, novel applications and detailed performance improvements are compelling the use of lattice mismatched layers. When the mismatch strain is excessive, it produces crystalline dsilocations and surface roughening. The ubiquity of roughness severely compormises the near-surfce crystalline integrity taht is essential for good electronic transport/ Techniques to efficiently characterize it must be developed.

This work investigates Atomic Force Microscopy (AFM) and two optical techniques, Variable Azimuthal Angle Ellipsometry (VAAE) and ex-situ Laser Light Scattering (LLS). Our work allows us to conclude that LLS and VAAE are simple, non-destructive,andsensitive techniques for characterizing surface roughness.

Sarmenta (Ward)

Synchronous communication techniques for rationally clocked systems

An increasingly common problem in designing high-performance computer systems today is that of achieving efficient communication between systems running at different clock speeds. This problem occurs, for example, in uniprocessor systems where the processor runs faster than the bus, and in heterogeneous multiprocessor systems where processors of different kinds run at their own maximum speeds. Asynchronous solutions to this problem, which assume the systems' clocks to be completely independent, are typically inefficient because they must allow for sufficiently long synchronization delays to attain acceptable levels of reliability. Synchronous solutions, on the other hand, though more efficient and reliable, have traditionally lacked flexibility because they require the clock frequencies to be related by integer factors. An efficient and flexible synchronous solution, called rational clocking, has been proposed that permits data to be transferred reliably and efficiently between two systems whose clock frequencies are related by the ratio of two small integers. This rational frequency constraint allows a wide variety of frequencies to be used, and at the same time, assures a periodic relationship between the two clocks that can be used to determine a schedule for data transfers between the two systems.

In this work we present, improve, and test the rational clocking technique. We begin with the simple table-based implementation originally proposed by Pratt and Ward, where the communication schedules are precomputed and stored in lookup tables, and discuss some minor variations and improvements. Then, we improve the throughput of this technique with a double-buffering scheme that provides 100% efficiency for all frequency ratios. We also improve the space-efficiency and flexibility of the scheduling hardware dramatically by using a set of run-time scheduling algorithms that do not require lookup tables. Finally, we test all these ideas using a combination of software and hardware tools, including Verilog simulations and a custom-designed CMOS VLSI chip.

---

Voss (Rosowski / Peake)

What is the effective acoustic stimulus for the inner ear?

The hair cells that transduce acoustic signals to the neural signals that are sent to the brain are located within the fluid-filled inner ear (cochlea). The cochlea is enclosed by a bony capsule with two membrane-covered holes that face the middle-ear air apce: the oval and round windows. In a normal ear, sound is transmitted from the ear drum to the oval window through the linkage of three small bones (ossicles). In pathological ears with missing ossicles, hearing sensitivity is greatly reduced but hearingis still possible; in this case ear surgeons assume the pressure difference between the oval and round windows is the stimulus to the cochlea.

Most theoretical representations of cochlear hydrodynamic assume that because the oval and round windows are connected through incompressible cochlear fluid, the cochlear response is proportional only to the pressure-difference between the two windows. However, both electro-physiological measurements and theoretical considerations suggest that the cochlear response could have componets that respond to the sum of the pressure at the oval and round windows, i.e., the common-mode component of the two input pressures.

This work tests experimentally tests the assumption that the pressure difference between the windows is the only acoustic stimulus for cochlear response: cochlear potential measurements on ear of anesthetized cats are used as a measure of cochlear response. The results confirm that surgical procedures to improve hearing sensitivity in ears without ossicles should be aimed toward increasing the pressure difference between the cochlear windows, and the place an upper-bound on the effectiveness of common-mode inputs.

---

Zahn (Leeb)

Remote resonant frequency detection in the 55-90 Mhz range

A detection system that remotely and accurately measures the resonant frequencies of high Q resonant circuits is designed, built, and tested. In many communication system applications precise tuning of resonant circuits is necessary for the correct operation of a system. Detecting detuned high frequency resonant circuits can be cumbersome and may not produce correct results due to parasitic capacitance and inductance in connecting probe leads which can alter the resonant frequency of the circuit. Older remote detection technologies, such as grid-dip meters, are dependent on manual operation of the system and are not cost-efficient for testing large numbers of circuits.

In this remote detection system, a signal source is used to sweep the frequency range from 55 - 90 MHz in discrete steps. A transmitting antenna is used to produce a magnetic flux which generates an electromotive force that drives a resonant circuit. The resonant circuit will then re-radiate significant electromagnetic fields when the signal source is near the circuit's resonant frequency. The receiving antenna will be subjected to the magnetic flux of both the transmitting antenna and the resonant circuit. From measurement of the total received power, the data acquisition system detects the contribution from a remote resonant circuit. Manufacturer's can use this remote test circuitry method without direct electrical contact, so that detuned circuits can be quickly located and corrected.

Poletto, Massimiliano (Kaashoek)

Path Splitting: A Technique for Improving Data Flow Analysis

Code optimizations performed by compilers fall under two general categories: machine-dependent optimizations, such as register allocation and ``peephole'' optimizations, and machine-independent transformations, such as copy propagation and common subexpression elimination. The latter optimizations make use of information available statically at compile time to restructure the code in ways which should improve performance independently of the specific characteristics of the target machine. Most machine-independent optimizations rely on data flow analysis, a process of collecting information about the way in which variables are used at various points throughout a program.

This work explores path splitting, a new technique for improving the amount of data flow information about a fragment of code statically available to the compiler. Path splitting replicates code in order to make the most detailed possible reaching definition information available on entry to each basic block in the program's control flow graph. This improved information is used to extend the applicability of various classical code optimizations, including copy and constant propagation, common subexpression elimination, dead code elimination, and code hoisting. In addition, path splitting can contribute to decreasing register pressure, and creates clean, uninterrupted instruction sequences useful for trace scheduling and hence extracting instruction-level parallelism.

We describe the path splitting algorithm, analyze it from a more theoretical perspective, present heuristics used to decide when to replicate code to improve data flow analysis and generate good traces, evaluate the algorithm's performance on various benchmarks, and discuss it in the context of other optimization techniques.

---

Brown (Knight)

Feedback-directed specialization of C

Programmers constantly make tradeoffs between code size and complexity, and eventual compiled running speed. Generalized functions and operations are used in many contexts without requiring additional code to be written and debugged, but with current compiler technology, these generalizations come at the expense of a great deal of run-time overhead; the cumulative effect of function calls, parameter passing, and referencing variables instead of constants is very noticeable. My work explores reducing the overhead incurred by highly general source-code by using profiling information (feedback) gathered from program runs to direct automatic specialization of the program at programmer-selected points of interest.

Built on the framework provided by the Stanford Compiler Group's SUIF Compiler System (an easily-extensible research compiler for C and FORTRAN) this research enables a programmer to annotate source-code to indicate regions of interest for specialization. In an initial compilation, regions of interest are marked for profiling; in each subsequent recompilation, the results of the previous rounds of profiling are used to direct specialization and further profiling.

Specialization takes the form of three semantics-preserving transformations: inlining functions; producing specialized versions of a function based on calling-site parameters determined to be constant at compile-time; and producing multiple versions of critical code-blocks, each optimized for feedback-discovered likely cases, of which the relevant block is selected at run-time. In addition to discovering likely cases, feedback is used to guide heuristic moderation of code-expansion -- determining whether to inline a function, generate a specialized version of it that might be sharable across several calling sites, or to leave it unmodified; deciding which likely-cases deserve a version of a critical code block, and which should use the general-case block; etc. This moderation is necessary because while on an ideal computer, exponentially increasing a program's size by inlining all function calls would result in strictly increasing the speed of the resulting executable, cache and paging effects ensure that this will not actually be the case on real machines.

---

Miller (Leiserson)

Cilk: A multithreaded extension to C

Cilk (pronounced ``silk'') is a runtime system for multithreaded parallel programming, which allows a computation to be expressed as a collection of concurrently executing threads. The Cilk runtime system schedules threads for execution on multiple processors with provably low time and space overhead. Unfortunately, the runtime system is difficult to program directly, since it requires each thread to be broken up into nonblocking tasks. In order to shield programmers from the requirements of the runtime system, we have developed a simple language, based on C with a small amount of new syntax, which allows a parallel computation to be expressed with forks and joins.

I will describe the compiler that translates the Cilk language into ordinary C with calls to the Cilk runtime system. The compiler is much more than a macro preprocessor; it actually type-checks the Cilk program before converting it to C, so that comprehensible error messages can be reported to the user. As a result, the emitted C code is guaranteed to be type-correct. The compiler also performs data-flow analysis on the Cilk program in order to produce efficient C code. Despite these optimizations, the compiler's output is readable; it does not look like assembly code written in C, as might be expected.

The Cilk compiler is based on a compiler framework we have developed called C-to-C, which parses an ANSI C program into an abstract syntax tree, performs type-checking and data-flow analysis directly on the syntax tree, and then unparses the syntax tree to recover the original C program. I will show how C-to-C makes it easy to build compilers for C extension languages like Cilk.