All Undergraduate and graduate students, faculty, research staff, and technical staff of VI-A companies are cordially invited to attend.
Room 34-301 Session I 3:00-4:00 Session II 4:15-5:15 Room 34-302 Session III 3:00-4:00 Session IV 4:15-5:15 Room 34-303 Session V 3:00-4:00 Sesson VI 4:15-5:15 Room 34-304 Session VII 3:00-4:00 Session VIII 4:15-5:15 Room 34-401A Session IX 3:00-4:00 Session X 4:15-5:15 Room 34-401B Session XI 3:00-4:00 Session XII 4:15-5:15
Modern compiler optimizations can be roughly characterized as static or dynamic. Static optimizations, by definition, have no knowledge of program behavior and must optimize around general case assumptions. Dynamic optimizations circumvent this problem by delaying instruction bindings until run-time values are known, allowing for highly specialized code sequences. However, very little optimization analysis can be performed at runtime as any computation performed is in the critical path of the program, reducing the benefit of the resulting code. A computational model called Quasistatic Computing melds static and dynamic analysis in a framework that explicitly includes program profiling, analysis and automatic recompilation as part of the deployed program lifecycle. Run-time feedback information is leveraged from previous program executions by off-line analyses for optimizations based around expected run-time behavior. Applications in quasistatic computing systems are enabled to continually adapt to changing end-user data sets and environments.
This thesis introduces a research system that implements a framework for quasistatic computation and explores the issues involved in engineering environments that support quasistatic computation. The research framework is enabled by three key components: automated profiling mechanisms, program graph storage and an analysis engine. Profiling techniques such as PC-sampling, basic block counting, block timing and variable sampling are well documented. The system provides an interface to these profiling techniques for use by the analysis engine. In order to maintain feedback information across multiple program runs, the program's intermediate graphs must be retained. This system utilizes Stanford's SUIF intermediate format as its stored intermediate program representation.
The key features of the compiler system lie in the analysis engine. This engine maintains a collection of optimization strategies and applies per- application ordered sets of these optimizations to the intermediate program graph, initiating feedback acquisition and recompilation when necessary. As the space of all possible sets of optimizations is quite large, the system must be careful to find a near optimal set within very few recompilations. To accomplish this quick convergence the system uses a combination of learning, probabilistic analysis and heuristic search techniques. Optimization is currently limited to programs written in C.
This talk will describe the design and implementation of a compiler for the CAM-8 computer. CAM-8 is a scalable parallel computer developed at the MIT Lab for Computer Science. It is optimized for simulating very large 3-dimensional arrays of cellular logic. It uses conventional memory chips in a pipelined, lock-step synchronized, virtual-processor architecture. Applications of CAM-8 include discrete molecular dynamics simulations of physical systems, large-scale logic simulation, volume rendering, and image processing.
From the programmer's point of view, CAM-8 is a large-scale spatially organized SIMD machine. Every operation applies to all data-cells, and is a combination of a 16-bit input / 16-bit output table-lookup operation, and uniform streaming of spatial data between all data-cells.
Unfortunately, work with the CAM-8 has been limited to date by the development tools available for programming its highly unique architecture. It's design, while very powerful computationally, also offers unique challenges to either the programmer or compiler designer. Current programming tools are close to the machine language level, and require that the programmer understand the unusual details of the CAM-8 architecture.
This talk will describe the design of an optimizing compiler written specifically for this type of architecture. A compiler for this type of machine should both hide and exploit the unique features of the architecture, thus allowing the programmer to focus on the application, rather than the implementation details.
While CPU speed has been increasing dramatically over the last decade, disk access time has only improved slowly. Disk I/O thus presents a major bottleneck in many computer systems. This thesis explores a new disk system architecture which, in contrast to traditional storage systems, provides resource protection (who can access what data in which way) but leaves resource management (how data is organized, allocated, accessed and cached) to applications. Applications can thus implement their own specialized disk storage abstractions on top of the disk system and (potentially) achieve better performance and greater flexibility than in current disk system architectures.
Exodisk, the disk system described in this talk, safely and efficiently space-multiplexes disk storage among applications at a very fine grain (down to a single disk sector). It exports the raw disk storage using a two-level model: On the first level, it provides applications with protected extents of contiguous disk sectors which are explicitly allocated by applications. Extents belonging to different applications or file systems can be arbitrarily interleaved on disk (unlike conventional file system organizations that can only be interleaved at the partition level), thus resulting in new possibilities for optimizing disk access.
On the second level, several such extents can be combined in a larger unit that represents a lightweight i-node implementation. This so-called exonode represents an important optimization to applications, since they do not need to pay the overhead of per-extent protection, while still allowing for finely interleaved file systems. Furthermore, the ability to augment exonodes with arbitrary-length application-defined data enables applications to collocate meta-data associated with their own storage abstractions with exodisk system meta-data.
The goal of an Intelligent Tutoring System (ITS) is to provide instruction that adapts to the student's needs, often utilizing Artificial Intelligence methodologies. There are, of course, a number of differt ways to go about building such a system. This talk will outline one approach, describe an application of that approach, and conclude with some thoughts about when and why the approach is appropriate.
Most Intelligent Tutoring Systems built since the 1970's have been built using a domain module, a student module, and a pedagogic module. My work has focused on finding efficient ways to construct and use these modules. I build both the domain and student modules on top of an existing expert system. The tutoring module guides the interaction with the student based on differential modeling between the expert and the student.
This talk will describe STAND-UP, a system built following this paradigm. STAND-UP is an ITS covering the emergency procedures of the T-37B Tweet, the aircraft used by the Air Force for primary pilot training. The domain knowledge for STAND-UP is extracted directly from the T-37B-1 Flight Manual. This neatly avoids the problems associated with traditional knowledge acquisition and also ensures that the knowledge used by the system has been debugged and accepted by educators in the field. Based on the student's responses, relevant rules are tagged in the knowledge base to assemble a student model.
In this thesis, we are concerned with the problem of achieving ease of use for non-professional practitioners of programming in the small. We present a novel software development approach based on a flexible component software architecture that makes it easy to create or modify applications by reusing available functionality as much as possible.
In our approach, software is structured into flexible components, which are executable pieces of software that are programmable, interoperable, and combinable. A flexible component persents a programming interface that can be arbitrarily elementary or sophisticated. According to the purpose and target user of a component, this interface can consist of anything from simple point-and-click programming mechanisms to a full-featured programming language. Accordingly, the component will permit smaller or deeper modifications. The programming interface can be considered as a generalization of the traditional property/method interface of OLE or OpenDoc components. Interoperability of components is achieved by similar mechanisms as in existing component software standards: a standardized component architecture and an underlying engine that coordinates component interoperation.
We have implemented a prototype environment Alego that demonstrates the usefulness of flexible components in application areas that are inherently vague, creative, and individual, e.g., education and games.
The goal of my thesis project was to examine the feasibility and efficiency of developing code through an automatic code generation system called MOUSETRAP. Specifically, my thesis project focuses on the design and development of a datalink layer protocol for a Motorola radio and the steps that were taken to develop this module through the MOUSETRAP system. The major steps in this project included developing the code through traditional software engineering techniques, understanding the method of automatic code generation, writing a tool that was critical to the performance of the automatic code generator, adding functionality to the code generation system, testing the auto generated code, and finally comparing the results to the code that was developed through traditional methods.
This experiment was valuable for many reasons. First, the transformer has been used before to generate code for other hardware platforms and for other radio operating systems such as pSOS, and so there are rules in the transformer's rule base that take advantage of these hardware platforms and contain the specialized programming knowledge to produce efficient code in these environments. However, there are no such rules for the environment of the HC16 microprocessor and the ROS (Radio Operating System). So, while designing the specifications of the datalink layer protocol, I discovered the unique characteristics of this environment so that it could be incorporated into the rule base. This project demonstrated flexibility of the MOUSETRAP transformer mechanism to be adapted to different environments even though the rules could change depending on the application domain.
Expanding the rule base with specialized rules for the HC16 using ROS was also useful to other developers who develop code on this platform because they can focus their efforts on their design rather than the special "tricks" of implementing. These "tricks" might influence the way that certain data structures are implemented, or certain rules in the transformer rule base may no longer be valid under this hardware platform. These are ideas that an experienced programmer working with the hardware would know, and incorporating them into rules would be a way to preserve that knowledge. Another advantage of using automatic code generation in this type of project is that if the protocol is modified, then it will be much simpler to change the specifications and then just regenerate the code, rather than modifying actual code. Additionally, specifications are much shorter in length than the actual code, and much of the complexity of the code can be incorporated very simply into the specifications.
Finally, this project demonstrated the feasibility of using auto-generated code on a commmercial product and will also help enhance the capabilities and knowledge base of the MOUSETRAP system.
We present the design of an efficient garbage collection scheme for large object-oriented databases in a client-server environment. Our scheme uses a partitioned approach: A database is divided into disjoint partitions and each partition is collected independently. It maintains transaction semantics and survives server crashes. It can be run concurrently with client applications. It also compacts objects in the partition being collected.
The garbage collector has been implemented in Thor, a new, distributed object-oriented database. It runs as a low-priority thread in the system. The collector interacts with the clients incrementally to obtain root information for collection. Client applications can continue to fetch objects from the database or commit transactions with no extra overhead while collection is happening.
To allow partitions to be collected independently, the database server has to maintain a list of object references between partitions for each partition. We call this list an inter-partition reference list (IRL). One major problem with any partitioned garbarge collection scheme is the cost associated with the updates of IRLs, which have to be maintained persistently because they are too expensive to recompute after server crashes. We describe an optimization that reduces the number of I/Os required to update the IRLs. IRL update operations are logged and deferred. They are re-ordered and processed in a batch at some later time.
A RAID system is abstractly composed of two components: a disk array and a disk array controller. The disk array is a collection of magnetic disks that can be accessed in parallel. The controller's function is to receive an operation from the user of the disk array, and to carry out that operation by performing a set of actions on specific disks. The user has no knowledge about the existence of a disk array and sees it as one large, logical disk with high performance.
RAID systems have two main advantages. First, data on the disks can be accessed in parallel which improves the I/O performance. Secondly, disk arrays contain some form of redundancy which allows fault tolerance.
Many algorithms have been devised for the controller. These algorithms allow fine interleavings between actions on the disks. As a consequence, their implementations are difficult to test. This is the reason why it is useful to apply formal methods to validate these algorithms.
We consider an algorithm for the RAID level 5 controller. We describe the algorithm and its specification using I/O automata and use the simulation proof technique to show that the algorithm implements its specification.
We present a new efficient method for verifying the termination of recursively defined functions written in pure first-order functional languages and operating on monomorphic inductive data types. Our method extends previous work done by C. Walther on the same subject. Walther's method does not yield a direct answer as to whether a given function terminates. Instead, it produces a set of termination hypotheses whose truth "implies" that the function terminates. But then an external general-purpose induction theorem prover must be invoked to verify the hypotheses.
By contrast, our method is a self-contained procedure that always produces a direct Yes/No verdict. Moreover, our method is remarkably faster, and, unlike methods such as the one used in the Boyer-Moore system, it requires no interaction with the user. A programming environment in which one can define inductive data types and functions has been implemented in order to test our method, and the latter was found to be very efficient in practice, having readily proven the termination of many classic algorithms, including QuickSort, SelectionSort, MinSort, and other sorting algorithms, algorithms for computing greatest common divisors and transforming propositional wffs into normal forms, and many others.
We offer a solution to the problem of locating and replacing personally- identifying information in medical records that extends beyond straight search-and-replace procedures, and we provide techniques for minimizing risk to patient confidentiality. There is little doubt that one of the biggest challenges facing medical informatics is the electronic sharing and dissemination of medical records while maintaining a commitment to patient confidentiality. Retrospective research, reduced institution costs, improved medical care, advances in medical expert systems and the development of electronic medical records using World Wide Web technology are some of the benefits possible when the content of medical records are reviewed by professionals. But these researchers, administrators, medical students, and computer scientists stretch this general notion of confidentiality. What is needed is a mechanism to provide only the information necessary to the professional who has a need to know.
At first glance, the problem of substituting patient information in a medical record seems trivial. After all the records are in a field-structured database, doesn't one simply search for all instances of the patient's name and replace it with a fictitious value and likewise with the patient's address, clinician's name, and so forth? The straightforward approach of global search and replace properly located no more than 30-60% of all personally-identifying information that appeared explicitly in our sample medical databases -- failing miserably when the record contained letters and shorthand notes in which references included nick names, employment history, names of relatives, names of referring physicians and other uniquely identifying information.
On the other hand, our Scrub system found 99-100% of all personally- identifying information that appeared explicitly. Scrub utilizes numerous detection algorithms competing in parallel to label contiguous characters of text as being a proper name, an address block, a phone number, and so forth. These detection algorithms employ templates and specialized knowledge based on a probabilistic model of occurrence and the linguistic properties of the text being scrubbed. Numerous tests were conducted using Scrub and it reliably detected all explicit references to personally-identifying information. However, finding explicit references to replace is only part of the problem. One must take care to choose an effective replacement strategy that isn't likely to be a real person's name or address; and, one must carefully select candidate records for the Scrub process in order to limit the ability to reverse the process and thereby identify real people. Solutions and mechanisms to handle these problems are presented and surrounding issues are explored.
In client-server systems, server integrity can be maintained by disallowing direct client access to server data and requiring communication through well defined interfaces. Typically, this communication requires expensive cross-domain calls, or even more expensive network communication. The main goal of this thesis is to create a system with fast, safe server access by allowing the server to import client code. Importing code allows the client to access the server through direct procedure calls which are much faster than indirect access which is typically used to maintain integrity. Server integrity is maintained through the use of a type-safe client language and by verifying imported code.
In order to explore the benefit of allowing the server to import code for client-server communications, a Java interface to the Thor Object-Oriented Database System has been implemented, using code importing techniques for safe database access. This Java interface to Thor does not require modification of the client programming language. The interface presented to the client is identical to the Java-Thor interface which uses standard communication techniques instead of code importing. Finally, initial performance benchmarks indicate the use of code importing in the Java interface to Thor provides a performance improvement of two orders of magnitude over the Java interface to Thor using standard communication techniques. These benchmarks indicate that the Java interface to Thor outperforms the C++ interface to Thor which uses cross-domain calls. Yet, because Java is interpreted, and thus an order of magnitude slower than most compiled languages, importing Java code is outperformed by code written in the language of the database itself. In the future, the use of just in time compilation should allow Java to be competitive.
This presentation will describe the construction of a simulator for studying the assembly of icosahedral virus shells. Understanding how virus shells assemble has long been a perplexing problem for biologists. One approach to understanding this problem, the local rules theory of Berger et. al., has provided considerable insight. However, prior theoretical and simulation work with local rules has been unable to answer some important questions because models have been too abstract. In order to address this, I have implemented a new simulator incorporating a physically realistic model of reaction kinetics and thermodynamics. This simulator should allow exploration of many previously unanswerable questions.
The presentation will cover several aspects of the simulator's design and use. First, it will briefly present some background into the problem of virus shell assembly and explain how it motivates the construction of the simulator. Next, it will describe the design constraints used in planning the simulator. The majority of the presentation will focus on the implementation of the simulator itself, including both its functionality and the most important underlying algorithms and numerical methods. Finally, the presentation will present a short description of preliminary work with the simulator and draw some conclusions about its use.
A common objective in many applied problems is to infer properties of the interior of an object based on tomographic projections (line-integral measurements through the object). In a number of applications the ultimate goal is to characterize (e.g., detect, locate) regions of the object's interior which are, in some sense, anomalous. A familiar example is the detection of tumors from medical CAT-scan data. A major challenge is to develop methods which can characterize anomalies directly in the data domain (i.e., without first reconstructing a detailed image of the object's interior). My research has focused on the development of data domain techniques for the detection and localization of a single anomaly from tomographic measurements. These techniques are based upon a multiscale hypothesis test (MSHT) framework.
A MSHT represents an efficient alternative to a very large conventional M-ary hypothesis test which may be computationally infeasible due to the overwhelming number of hypotheses which must be considered. Previous application of MSHTs to anomaly localization problems has focused on the intuitive idea of spatial zooming with natural (but not necessarily good) statistics. In a spatial zooming approach, the anomaly is first localized to a coarse scale region and then to successively finer scale regions. A region (at any scale) is selected as containing the anomaly based on the values of some suitably chosen statistics. A major contribution of my work is the broader interpretation of multiscale hypothesis testing as statistical zooming on the set of hypotheses rather than spatial zooming in the image domain. This broader interpretation leads naturally to the formulation of an optimization problem, the solution of which provides a MSHT statistic which yields improved performance.
Existing radiosity rendering algorithms achieve interactivity or high fidelity, but not both. Most radiosity renderers optimize interactivity by converting to a polygonal representation and Gouraud interpolating shading samples, thus sacrificing visual fidelity. A few renderers achieve improved fidelity by performing a per-pixel irradiance "gather" operation, much as in ray-tracing. This approach does not achieve interactive frame rates on existing hardware.
This research bridges the gap, by describing a data structure and algorithm which enable interactive, high-fidelity rendering of radiosity solutions. In essence, our algorithm "factors" the radiosity rendering computation into two components: an offline phase, in which a per-surface representation of irradiance is constructed; and an online phase, in which this representation is rapidly queried to produce a radiosity value at each pixel. The key components of the offline phase are a conservative discontinuity ranking algorithm, which identifies only the strongest discontinuities, and a hybrid quadtree-mesh data structure which prevents combinatorial interactions between most discontinuities. The online phase involves a novel use of perspective-correct texture-mapping hardware to produce nonlinear, analytic shading effects.
Dynamo is an image manipulation system designed to stabilize moving images; it is based upon the assumption that the motion of a given region can be well approximated by a parametric motion field. Currently Dynamo does not stably track objects that partially leave the camera's field of view or become partially occluded. The motion tracking is also dependent on the user defined analysis region which might not contain trackable features. In this thesis we address these issues by introducing an automatic dynamically configured image region.
All of the mentioned problems stem from the fact that a user specified region is used for the motion estimation. To make the estimation more robust, we segment an image into pixels consistent with the tracked motion and those that are not. This division is accomplished in three steps: first we estimate motion from the analysis region, whether the region is that specified by the user or the segmented region recovered in the previous frame. Second, we find all pixels that move according to this estimated motion; the test for consistency is based upon measured statistics of the image. Third, we morphologically group these pixels into coherent regions which define the new analysis region.
It is shown that this method of estimating motion can track objects that were previously impossible to track. Furthermore, modeling the interpolation error can segment trackable features more accurately, and removes some dependency on morphological operations.
Real-time visual simulation of complex environments such as a city can be useful for city planning, embedding of commercial databases, military training, and entertainment. Maintaining a high frame rate is essential for a realistic virtual navigation experience. For a large, irregular outdoor environment where most objects are visible, visibility-based algorithms for reducing the number of polygons to be rendered are often not applicable. Approximation algorithms that simplify individual objects or clusters of objects often require cost/benefit heuristics to select the best representation, and make no guarantee of visual quality. However, with emerging hardware support for texture mapping, a scheme that approximates parts of the scene as texture maps can be realized.
In this talk, we present a new approach to the visual approximation problem. The novel aspects of our algorithm are that 1) it maintains, in physical memory, a constant amount of state for scenes of bounded density; 2) dramatically reduces the number of polygons to be rendered; 3) requires no cost/benefit calculation; 4) exploits object spatial and temporal coherence; and 5) makes an absolute guarantee of image quality based on the display resolution.
During a preprocessing stage, all possible viewpoints are divided into viewboxes or cells. Then for each viewbox, using motion parallax, polygons in the scene are partitioned into near and far sets. The far polygons are projected onto the sides of a bounding box and stored as texture maps. During interactive simulation, as the synthetic viewpoint moves, its corresponding viewbox can be determined. Based on the viewbox, near polygons are retrieved, culled, and rendered as before. Instead of the original far polygons, only a constant number of far texture maps are retrieved and rendered, thus significantly reducing the rendering load in each frame.
X-ray coronary angiography is a widely used imaging technique for visualizing the presence of coronary artery disease (CAD). The measurement of arterial diameter from these images reflects disease burden, and provides an assessment of treatment benefit from existing and experimental therapies. Unfortunately, existing derivative-based and model-based measurement methods provide poor estimates for small vessel diameters -- precisely the range that is associated with the presence of clinically significant stenoses.
We have found that because of blurring and noise, the apparent widths of small vessels in angiographic images contain little information about the real diameters, leading to poor estimation performance by existing techniques. Information about vessel diameter does remain available in the intensity height, but this has not, until now, been exploited to improve diameter estimation. The use of intensity information is complicated by a variable, non-linear relationship between intensity and vessel diameter. Separate x-ray calibration procedures might be used to experimentally determine crude approximations to this non-linear relationship. However to date, such procedures are clinically impractical to perform. To overcome this limitation, we have used a more accurate description of x-ray imaging function to pose this problem within a model-based estimation framework. With this approach, we can estimate the unknown imaging model parameters directly from an angiographic image, without the need for additional x-ray experiments. The intensity relationship thus determined forms the basis for a novel model-based estimator which uses the combined intensity and width information within an angiogram to measure arterial diameter.
We have used computer simulation to analyze the performance and sensitivity of this method to imaging noise, blurring, angiographic backgrounds, imaging system operating points and estimating initial conditions. These simulations have shown that this approach is robust to variations in each of the conditions studied. Finally we have compared the diameter estimates from our technique against those from existing methods, using simulated arterial vessel images and real x-ray images of vessel phantoms. Our results suggest that diameter estimation using our new approach is significantly improved over estimation using the current forms of diameter measurement.
This thesis investigates the use of visible light for breast cancer imaging. The use of light at this frequency avoids the potential danger of ionizing radiation from frequent mammographic screening. This method is inexpensive and harmless and is potentially attractive since it could be used more frequently than mammography, increasing the chances of early detection and successful treatment.
The hardware required consists of a movable light source, or multiple sources, and many detectors. The light is incident upon one side of the tissue and measured at the opposite side. In addition, mathematical computations are required for the discrimination of tumor material from normal tissue. This is suggested to be possible since tumors are known to both scatter and absorb light more than normal tissue. This research focuses on reconstruction algorithms which allow for the detection of changes in absorption according to their representation in the circuit model.
Beginning with a nominal case of uniform scattering and absorption, a perturbation approach to the reconstruction of the change in the absorption parameter is attempted. Improvements in the reconstruction algorithm due to regularization will be demonstrated with an aim at pushing performance up to the limit of resolution. An approximation of this resolution limit is also investigated and discussed.
The remote microscope was developed at MIT as part of the Computer Integrated Design and Manufacturing project to aid in the remote fabrication of integrated circuits, and will allow a user to operate and view in "real time" an actual microscope located at a distant facility. We envision a growing trend in the semiconductor processing field for more collaboration and sharing resources, so it will become important for researchers to have access to a telemicroscopy system like the one developed at MIT in order to perform remote inspections of semiconductor wafers.
The MIT remote microscope is extremely versatile; it operates over the internet and allows a user to run the graphical microscope interface on any ordinary UNIX workstation, thereby providing easy access to the microscope for researchers located throughout the world. The actual remote microscope utilizes readily available hardware as well, making the entire system very straightforward and economical to implement. To the best of our knowledge, the MIT remote microscope is the first telemicroscopy system to operate on the internet. The remote microscope also is original in that it allows multiple users to view the microscope at the same time in a conference inspection, which should be very useful when geographically distant researchers wish to collaboratively inspect a wafer. The overwhelming response to the remote microscope has been very positive, as it was officially demonstrated in August 1995 between MIT and Stanford during the annual TCAD symposium.
In a semiconductor wafer fabrication facility (Fab), layout designs for integrated circuits are transformed to physical reality i.e., the circuits are built on (and using) Silicon (or other semiconductor materials) wafers. However, unlike some other manufacturing processes, semiconductor manufacturing is highly non-linear in its dynamics (non-conveyor-belt-type, with lots of feedback flows) and very susceptible to chaoes (small changes resulting in big effects). Also, the extremely high demand market for ICs today is facing a crisis: the rapidly fluctuating history of the industry has made manufacturers extremely sensitive to investment for capacity increase, since additional, non-reversible investment is a risky business. Hence, there is a great motivation for a thorough understanding of efficient manufacturing of semiconductor ICs.
This thesis details a methodology for making intelligent, optimum decisions for this complex manufacturing scenario. Using computer simulations, a dynamic approach is initiated which looks at the manufacturing process's key macro-parameters (Cycle Time, Thruput Rate and WIP (Work in Progress) and micro-parameters (Work Release Policies, Equipment Scheduling Options, Process Complexity, Equipment Setup Rules, Inventory Control, Work Priority, etc.). A simulation model is first constructed and then subsequently validated by matching various simulation output parameters against historical data. This model is then used to study the Cost and Performance (Trade-off) impact of the following:
For high speed chip-to-chip data transfers, meeting the critical narrow timing requirement is essential for a secure communication. In addition to the clock skew on the board and the actual flight time of the data signal across the chip's I/O interface, there are uncertainties that need to be considered in the timing budget. These include clock skew at the PLL on the chip level, and variation of signal integrity for the traveling data signal on the I/O bus. To investigate the effects of these variations, a detailed model was developed in this study which is a CMOS point-to-point network including driver and receiver chips with 32 drivers and predrivers, core, and power distribution; PGA package with Vcc and Vss planes, pins, and bondwires; 3D realization of the board with curent return paths; and bus transmission lines with multilevel connections for cross-talk. It incorporates many aspects that affect the signal integrity of the data signal on the chip and allows future studies to simulate conditions closer to real world situations.
The model of the environment surrounding the I/O buffers was built and simulated for an eye diagram analysis with changing parameters such as process corner, temperature, supply voltage, data pattern, edge-rate, and board impedance. Each parameter variation contributes to a variation in the timing of the trasitioning signal edge. When all of the parameters are varied, the signal edge varies for a certain amount of time which can be described as the uncertainty region. The total sampling window less this uncertainty region is our clean window to sample a guaranteed valid data. An eye diagram analysis was performed to determine this uncertainty region and timings for a common clock data transfer. Future study of data transfer performance is recommended using the model for signal integrity analysis to guarantee a valid communication.
Research activities in field emitter array devices are driven by the potential of their application to flat panel displays and high power microwave systems. While the operating voltage has been reduced to about 50 - 100 V by the application of micromachining and IC fabrication techniques, the operating voltages are far from optimized, and need to be reduced to levels compatible with CMOS circuits, (5 - 10 V).
In development efforts, especially when exploring the limits in device technology, it is beneficial to conduct simulation of the devices to be fabricated. Simulation allows device performance to be predicted and optimized before costly and time consuming fabrication. There are many available electrostatic simulators which can provide e field solutions for complex structures. It is however difficult to compare device performance based only on the e field solution. Presently there are limited tools available for the simulation of field emission devices. A tool needs to be developed to take the electrostatic solution from a simulator and create device characteristics, (I-V characteristics, FN plots, and electron trajectories) to be used to evaluate performance.
Recent work on reducing the operating voltage has focused on reducing the gate aperture. This research effort examines the critical device parameters required for scaling the gate operating voltage to CMOS compatible levels, and calculate electron trajectories for display applications. Numerical simulation of PrealisticH device structures will be performed using a commercially available electrostatic simulator (ANSOFT) and custom written software. The scaling behavior and scaling limits of FEA devices will be determined, and a device design guideline will be given for the above mentioned applications.
A natural constraint on many digital systems is that a block of data must be processed in a given amount of time (throughput constrained computing). For example, an MPEG decoder must process (or decompress) a full frame of video every 30 msec. However, the amount of processing per block may vary. Continuing the example, the number of times an MPEG decoder implements an inverse discrete cosine transform (IDCT) per frame varies widely. More generally there are DSP applications which naturally have time-varying computational complexity, either due to data dependencies or algorithmic construction, and with fixed throughput, the processor idles for some fraction of the time. The goal of this project is to take advantage of that idle time to lower overall power.
In CMOS circuits, most of the power is dissipated charging and discharging capacitors, so power is roughly proportional to V^2. Voltage cannot be lowered arbitrarily because clock frequency constrains the gate delay to some maximum value, and gate delay depends on the supply voltage as Td=(A * V)/(V-Vt)^2, where A and Vt depend on the process. The equations can be combined to show that average power per block scales roughly as (workload)^3, so power can be saved by spreading computation over the maximum time, lowering the supply voltage and slowing the clock accordingly.
Our approach uses standard synchronous design with a ring- oscillator based clock and simple switching supply. The clock frequency is controlled by a digital phase-locked loop with the supply voltage as the control signal for the ring-oscillator. If the ring oscillator is well matched to the circuits, logic should function properly, since logic transitions take place in nanoseconds, while voltage changes in microseconds for typical switching supplies.
A chip is being built to verify predictions about loop stability and the functionality of static and dynamic logic circuits. Future research will include investigation of rate controller design, active power supply damping.
The advent of the erbium doped fiber amplifier has revolutionized optical communications, enabling long range communication links without repeaters. However, in addition to amplification of optical signals, a fiber amplifier also introduces significant broad-band noise. When the signal is detected, optical and electronic filters are necessary to separate the narrow-band communication signal from the broad-band noise.
We describe the analysis and design of a new class of optical filter, engineered to match the spectral response of an incident optical communications signal. A matched filter can be shown to yield the optimal signal-to-noise ratio, when used to filter broad-band noise. Such a filter can be realized by patterning a weak Bragg reflection grating into the surface of an optical waveguide. A matched optical filter should provide increased receiver sensitivity when compared with conventional optical filters, and could replace currently used electronic post-detection filters.
For optical signals modulated at the low-loss carrier wavelength of 1.55 microns, the corresponding grating period must be approximately 530 nm (in glass waveguide materials), necessitating the use of advanced nanolithography techniques. The desired filter bandwidth dictates the length of the grating. For a typical communications bit-rate of 10 Gbits/sec, the corresponding grating length must be approximately 1 cm in glass waveguide materials. Thus, we are faced with the challenge of fabricating long, coherent, fine period gratings. We propose a fabrication scheme employing a combination of optical lithography, interferometric lithography, and x- ray lithography, and we analyze the effects of fabrication errors on device performance.
Because the filter seeks to eliminate noise generated during optical amplification the filtered signal cannot be re-amplified without reintroducing noise. Emphasis is therefore placed on achieving a filter design which minimizes the total insertion loss of the device. We present an analysis of total device loss, including material loss, fiber coupling loss, and bending loss.
As time proceeds, different schemes of passively modelocked fiber lasers will be selected according to their abilities to produce stable short pulses with the required duration and intensity. Susceptibility to environmental noise will differ among these different systems. Therefore, understanding the noise mechanism in the fiber laser not only will lead us to better understand these lasers, but also is crucial to obtain quieter lasers required for many applications. Some work has been done on the noise characteristics of these modelocked lasers when they are biased in the soliton regime. However, a systematic noise study for the soliton laser does not exist. Moreover, very little investigation has been done outside the soliton regime.
This thesis reports a systematic study of the noise characteristics of the modelocked fiber ring lasers operating under additive pulse modelocking (APM) principle. The noise characteristics of the APM lasers operating in the soliton regime and in the non-soliton regime are studied both theoretically and experimentally. For the soliton laser the frequency domain noise structures are predicted and the pulse to pulse energy fluctuation and timing jitter induced by the quantum noise are calculated. Experimental observation of this quantum induced noise confirms the theoretical predictions. For the non-soliton regime the noise of a stretched-pulse laser is investigated. Equations of motion for different noise components have been derived. Experimental studies support the derived equations qualitatively. The noise structures of the two lasers are then compared.
It is concluded that both fiber lasers operate very quietly. The energy fluctuation of the soliton laser can be as little as 0.2% of the pulse energy; and its quantum-limited timing jitter is 27 pm of the round-trip time. The energy fluctuation of the stretched pulse laser is 0.15% of the pulse energy; and its timing jitter is negligible.
Wavelength division multiplexing (WDM) can be used to increase data transmission rates in fiber-optic communication systems. This technique utilizes the large bandwidth of optical fibers by multiplexing several bit streams on distinct communication channels which are separated in wavelength. The RcoloredS bit streams are then transmitted along a single fiber. Along the data link, it may be necessary to detect a particular channel. One approach to demultiplex WDM signals is to use channel dropping filters to select out a desired channel. The channel dropping filter should transfer the radiation within the band to the receiver without pertubing the channels outside the band.
Gain Distributed Feedback (GDFB) structures are used to form a novel type of channel dropping filters. It is demonstrated that these filters possess several unique and desirable features which makes them an ideal choice for use in WDM systems. GDFB channel dropping filters are tunable and allow transparent detection of selected channels. Moreover, they provide better suppression of undesired resonances than passive filters leading to better out-of-band performance. Equivalent circuits of GDFB filters are developed. A general scheme to assemble the equivalent circuits of arbitrary number of coupled GDFB resonators is devised. This technique is a very powerful tool to analyse and design higher-order filters. Second and third order filters are designed using the equivalent circuit model. Optical gain in semiconductors is reviewed and its relation to the injected current density through the device is discussed. A simple gain grating design is discussed and is used as an example to illustrate the spurious effect of index coupling and net travelling wave gain (or dc gain) on the performance of the device. Techniques to minimize these effects are explored.
Applications in optical frequency metrology often require the synthesis of exact ratios between input and output frequencies. Specifically, in the realization of an optical-to-microwave frequency chain it is useful to construct an exact 2:1 optical frequency divider. One approach to optical frequency division is based on optical parametric oscillators (OPO's). To achieve a 2-to-1 frequency ratio, the OPO must be phase-locked at the frequency degenerate point. It has been demonstrated that a type-I phase matched OPO can be operated in a self-phase locked regime at frequency degeneracy. A type-II phase matched OPO, which is better suited for precision frequency measurements, does not in general exhibit self-phase locking. The purpose of this work is to evaluate the possibility of achieving self-phase locking in a type-II phase matched OPO by adding intracavity polarization mixing to the OPO system.
This talk will outline the design, implementation, and experimental results of a family of all-optical switching devices based on a single-arm interferometer (SAI) geometry. This work was undertaken as part of a research effort in devices for ultra-high speed (~ 100 Gb/s) time division multiplexed networks. It is shown that the functional versatility of the SAI geometry allows one to implement generalized all-optical logic elements that are cascadable, interferometrically stable, compact, and can potentially be integrated in semiconductor. Except for the SAI based devices presented in this talk, all-optical switches to date have not simultaneously exhibited all these characteristics. Experimental results of all-optical demultiplexing, AND, NOT, OR, NOR, and XOR gating at data rates up to 40 Gb/s will be presented. These results represent the highest rate demonstration of bit-wise optical logic to date.
Flow electrification in transformers results from the entrainment of electrical double layer charge into the volume of the transformer's flowing oil dielectric. As the oil ages due to thermal and electrical stress, and also becomes contaminated by the byproducts of the similarly aging cellulose pressboard insulation, its properties change. The effects of an electrification reducing agent BTA (benzotriazole) are studied in new and aged oils. The electrification phenomena is observed in an apparatus consisting of two coaxial stainless steel cylinders, where the region between cylinders is filled with the oil dielectric. The inner cylinder is rotated, resulting in a well mixed, turbulent flow between the cylinders. Measurements of fluid volume charge density, open circuit voltage, and short circuit current between cylinders are made at various temperatures and rotational rates.
A second factor influencing electrification and efficiency in transformers is the conductivity of the oil impregnated pressboard dielectric. The pressboard is a non-ohmic, dispersive material which has a frequency dependent conductivity that is highly dependent on its moisture content. Time domain recovery voltage measurements, consisting of partial charging and discharging of a dielectric system followed by open circuit terminal measurements, are related to measured frequency domain dielectric properties.
This thesis investigates the effect of pars flaccida, a small compliant section of the tympanic membrane, on the signal transmission properties of the middle ear through acoustic and electro-physiological measurements. Toward this goal, the middle-ear input admittance, ear-canal to middle-ear sound pressure ratio, and round-window cochlear potential were measured in the ears of twelve gerbils. Measurements were made before and after various middle ear and tympanic membrane manipulations, including stiffening or removing the pars flaccida. The results are compared to the predictions of the middle-ear model proposed by Kohlloffel (Hearing Research, 13:83-88, 1984).
The input-admittance measurements show that the pars flaccida can be accurately modeled by a simple RLC circuit with a resonance at approximately 500 Hz. With the exception of a small frequency range from 300-600 Hz, our cochlear potential measurements support the assumption that the pars flaccida and pars tensa function as two independent sound paths. Within this range, the pars flaccida acts as a shunt path around the main ossicular transmission pathway. At frequencies below the pars flaccida resonance, this extra pathway reduces the ossicular transmission to the inner ear by increasing the middle-ear pressure. These results thus suggest that pars flaccida reduces low frequency hearing sensitivity, in agreement with the prediction of Kohlloffel's model.
The electric utility service might be very simply modeled, looking back from an electrical connection, as a sinusoidal voltage source in series with an inductor and a resistor. At the building level in the distribution system, these impedances arise predominantly from an upstream transformer, protection circuity, and a length of cable. Harmonic currents generated by some loads flow through these impedances, creating harmonic voltages that result in a distorted voltage waveform in the electrical "neighborhood" of the harmonic source.
The impedances of the electrical service could be identified by briefly closing a capacitor across the electrical service at a precise point in the line voltage waveform. The shape and decay of the transient capacitor current in this RLC circuit can be used to estimate the line impedance. The DESIRE (Determination of Supply Inductance and Resistance) system created in this thesis identifies local utility impedances using this technique. By identifying local impedances, DESIRE assists in the prediction of local voltage waveform distortion created by "power quality offenders". This talk will describe the design, implementation and use of the DESIRE system
A mechanical-state observer is developed for the high-speed operation of a variable-reluctance motor (VRM). The observer is designed to provide rotor position and motor speed state feedback for the purposes of transient speed control and phase commutation. The plant output, providing the innovation terms for the observer, is the rotor position as estimated from phase currents which are mea sured a short delay after phase commutation.
A Kalman filter design is employed for the observer using a motor model which incorporates the dynamic behavior of interpolation steps between position estimates calculated from phase current measurements. A proportional-plus-integral controller is designed to modulate the commutation angles of the VRM for transient speed control. The observer drives the controller through the feedback of the estimated position and speed which are used as inputs to the controller. To support the observer and controller design, a VRM model is developed using a periodic nonlinear function representing the flux linkage relationship to phase currents. Computer simulations are developed around the VRM model, the speed controller, and the observer. The simulations are verified by laboratory experiments. The experimental drive system designed and constructed for the tests is based on a 2 hp 6-4 VRM with a design speed of 10 krpm.
Torque modeling errors are discussed in the context of the experimental performance; they have limited effect on the performance of the observer which is dominated by the innovation terms. For this reason, a sophisticated nonlinear electrical model may not be necessary in applications with limited torque imbalance. Furthermore, decreased accuracy of the position inversion from current measurements results in unstable operation when sensed near the maximum misalignment position. The principal conclusion is that implementation of this observer for propulsion system drives is feasible with the design modifications proposed to maintain similar sensing accuracy for arbitrary commutation angles. Furthermore if the observer and controller are implemented in hardware rather than software, the theoretical speed limit for the observer-based control scheme is dominated by the decay time of the eddy currents, 6.9 msec, resulting in a maximum VRM speed in excess of 100 krpm.
Power control has increasingly become an important issue in cellular radio communication systems. In order to accommodate as many users as possible, cellular systems are designed so that a number of users share the same frequency spectrum. As a result, users cause interference to other users. The objective of power control is to minimize this cochannel interference. This is achieved by continually adjusting the transmit power of each user to the lowest level that still permits reliable communication. Therefore, maximizing system capacity, measured in terms of the number of users a system can support, depends critically on efficient power control.
The most common approach to power control is to define the quality of the transmission links by the carrier- to-interference ratio (CIR). Reliable communication is possible only when the CIR of a particular user is above some specified threshold. Consequently, the goal of power control is to find the minimum transmit power of a particular user such that its CIR constraint is satisfied. The motivation for this research is the fact that past analyses on power control neglect the fading aspects of cellular radio channels, and focus only on interference caused by other users. It is well known that cellular radio channels are also subject to time-varying multiple paths, which account for the signal fading. Standard power control algorithms considered in past research may actually be detrimental when fading is present.
We develop power control algorithms that maintain reliable communication links for mobile users in cellular radio systems. The algorithms are designed to achieve good performance in the presence of both cochannel interference and signal fading. We construct a narrowband fading model that is derived from a standard characterization of fading multipath channels. The development and analysis of power control algorithms for various cellular network scenarios are based on this fading model. We study simple scenarios, such as the single cell network and the two cell network, in order to examine the effects of both intracell and intercell interference. An extension to a general multiple cell network is presented. Power control algorithms for the single cell network are based on minimum mean squared error (MMSE) estimation. The performance of the estimation algorithms depends on the fading rate. In contrast, the multiple cell network requires the use of an interative power control algorithm in order to alleviate complexity. The performance of the interative algorithm depends on the rate of change of the channel, the rate of convergence of the algorithm, and the amplitude range over which the channel varies.
Chaotic signals and systems are potentially attractive in a variety of signal modeling and signal synthesis applications. We have developed state estimation algorithms for chaotic sequences corresponding to tent map dynamics in the presence of nonstationary additive Gaussian noise, intersymbol interference, and multiple access interference.
Although these algorithms may be useful in a wide range of noise removal, deconvolution, and signal separation contexts, the talk will focus on a specific example of the potential application of chaotic systems in communication, in particular in the modulation or coding of analog sources for transmission over channels with unknown or multiple SNR. We embed the source data in the initial state of a chaotic system with dynamics corresponding to the tent map. Although the dynamics of such a one-dimensional system appear rather simple, with the appropriate choice of observation function we can obtain a large class of codes. For example, convolutional codes are a subset of this class. To provide some insight into the possibilities, we explore the case where the observation function is the identity function. The code corresponding to this case can be interpreted as the superposition of information about less significant bits on top of information about more significant bits. It can also be interpreted as a nonlinear modulation system. We show that this simple coding system can outperform M-ary digital codes and linear modulation codes in a range of power-bandwidth regimes.
Coherent laser radars are capable of collecting range images by raster-scanning a field of view in pulsed-imager operation. In this work, a theoretical framework is established for maximum-likelihood (ML) multiresolution laser radar range imaging using the expectation-maximization (EM) algorithm. In particular, this procedure determines the maximum-likelihood fitting of a multiresolution (wavelet) basis -- at a sequence of increasingly fine resolutions -- to laser radar range data. Specialization to the Haar-wavelet basis yields a procedure that is both computationally efficient and numerically robust. Basic analytical properties of the estimation algorithm and its performance are presented based on real laser radar range data. It is shown that the weights associated with the EM iterations provide a reliable indicator for terminating the course-to-fine resolution progression. At increasingly fine resolutions, error performance measurements show that bias decreases and error variance approaches the ultimate limit set by the complete data bound.
|
Modified: Jun 25, 1997|
Current events|
Your comments
and inquiries are welcome.