University of Illinois at Urbana-Champaign. Department of Computer Science

Herbert Edelsbrunner

Cecil Jose A. Delfinado

Abstract: "A general and direct method for computing the betti numbers of the homology groups of a finite simplicial complex is given. For subcomplexes of a triangulation of S© this method has implementations that run in time O(n ̄(n)) and O(n), where n is the number of simplicesin the triangulation. If applied to the family of ̄-shapes of a finite point set in R© it takes time O(n ̄(n)) to compute the betti numbers of all ̄-shapes."

An Incremental Algorithm for Betti Numbers of Simplicial Complexes

William F. Opdyke

Refactoring Object-oriented Frameworks

Edward H. Gornish

Adaptive and Integrated Data Cache Prefetching for Shared-memory Multiprocessors

Changwen Liu

Abstract: "The thesis is concerned with the behavior of corrupted real-time control systems and their corrupted trajectories. The difference between the corrupted trajectory and the precise trajectory is called the tracking error. We analyze the consequence of imprecise computation, caused by corrupted input and/or prematurely terminated output computation, on tracking errors for single-input-single-output and multiple-input- multiple-output time-invariant systems with deterministic errors as well as random errors. We establish the tracking error models and give upper bounds of the tracking errors. We find conditions under which the imprecise computation has certain desired convergence properties and show how to design control systems so that the systems have satisfactory performance."

Imprecise Computation in Real-time Control Systems

Principles of Object-oriented Operating System Design

Thomas Richard Ioerger

While many excellent induction algorithms are known for making predictions from databases in well-studied domains, learning systems still perform poorly in many difficult real-world domains, such as weather prediction or financial risk analysis. Two characteristics of real-world domains are inadequately addressed by current machine learning research. First, the difficulty in these domains is often caused by a low-level representation, which necessitates shifting to a higher-level representation. But the space of possible representations is very large, so we need intelligent methods for finding higher-level representations. Second, background knowledge is almost always available in real-world domains, which we would like to take advantage of to increase predictive accuracy. However, known roles for domain knowledge in machine learning are often inflexible, requiring the use of a specific induction algorithm or being sensitive to incorrectness or incompleteness in the knowledge. We propose a general framework for change-of-representation based on searching for alternative representations to improve the accuracy of an underlying induction algorithm. Representations are selected as candidates by querying a strategy component, which relies on domain knowledge to suggest which alternatives to search. An evaluation component then compares these representations by applying each representation to a set of examples and running the induction algorithm on the transformed examples to empirically determine the effect of the change on accuracy. This approach provides solutions to the two characteristic problems of learning in real-world domains. First, domain knowledge is used as a heuristic to guide the search for alternative representations, enabling more intelligent decisions during change-of-representation. Second, the framework provides a flexible role for knowledge that can be used with any learning algorithm and is tolerant of uncertainty. An implementation of this framework could be used as an interface between a human expert and a learning program in which: (1) the human uses background knowledge to generate and prioritize alternative representations, and (2) the system empirically evaluates these to discover the best change for improving accuracy. We apply our framework for change-of-representation to the difficult, real-world domain of protein tertiary (3D) structure prediction. The best computational method to date for determining the structure of a protein from its amino acid sequence is homology modeling, which is based on sequence alignments with a protein database. Homology modeling can fail in cases where the sequence similarity is low between proteins with similar structures. However, the physical and chemical properties of amino acids are believed to relevant to protein structure. Using an instantiation of our framework, we incorporate this domain knowledge to suggest ways to change the representation of amino acid sequences. Efficient search procedures are derived from the knowledge that lead to the discovery of representations that improve the ability to predict protein structures by homology modeling.

Change of Representation in Machine Learning, and an Application to Protein Structure Prediction

Sanjay Bhansali

Laxmikant Vasudeo Kalé

Verification of Chare-kernel Programs

Wei Shu

Programming Examples and Performance on Multi-processors

The Chare-kernel Base Language

The Design Philosophy of the Chare Kernel Parallel Programming System

Chin Lu

This thesis discusses process migration in message-based systems and procedure-oriented systems. The issues that we deal with are the correctness of process migration and the design of migration schemes. The design goal of the migration schemes is to maintain migration transparency. A formal user and environment interaction model is given for procedure-oriented systems. The execution environment of a user process is decomposed into environment objects. Environment objects are specified as state machines. System calls are external operations of environment objects. We argue that the transparency of process migration depends on how much knowledge a process has about its environment objects. The notion of environment view is introduced to distinguish what a user process can observe about its environment from the state of its environment. Two correctness criteria are proposed for maintaining migration transparency. The state consistency criterion requires that the internal state of a process at suspension time is kept the same until its resumption time. The view consistency criterion requires that the environment view of a process at any time after its migration must be consistent with its view at suspension time. Two migration schemes are designed for procedure-oriented systems. The implementation design of the two schemes are demonstrated in UNIX environment as examples. In message-based systems, the key issue in process migration is to ensure reliable interprocess communication, namely, to ensure that messages are delivered correctly. Three migration schemes are discussed to ensure reliable user communications. Two protocols used for message loss prevention scheme are designed to support process migration in message-based systems.

Process Migration in Distributed Systems

Quarterly Technical Progress Report

Alan Lewis Gordon

Summary of Design Approaches for Symmetric Parallel Multipliers

James Leo

An Evaluation of Two Data Dictionary Directories

Kyungoh Min

Distributed deadlock in a distributed database system is a system state in which a set of concurrently running transactions are circularly waiting for each other to release resources. Over the past decade a number of algorithms have been proposed in the literature to detect such a deadlock, but not much attention has been given to their performance. Lack of understanding of the workload for such distributed algorithms has made it difficult to predict their performance prior to actually implementing them on a distributed system. In this thesis, we present an approach to distributed workload analysis which can be used as a basis for the performance study of distributed deadlock detection algorithms. In particular, the expected number of times a deadlock detection algorithm is locally initiated and the subsequent number of remote invocations are derived. Simulation work was done to validate our approach. For the performance analysis of distributed deadlock detection algorithms, we introduce three performance measures and explain how we can analytically derive them for a given system configuration. Then, we discuss some limitations of our approach and present the alternatives we took to study the performance of distributed deadlock detection algorithms using the results of the workload analysis. Finally, results from the analysis are validated using the results from the simulations and we compare the performance of two representative algorithms.

Performance Study of Distributed Deadlock Detection Algorithms for Distributed Database Systems

University of Illinois at Urbana-Champaign. Department of Computer Science

About

Books

Join the club