Digital Commons Network^™

View-Centric Reasoning About Parallel And Distributed Computation, Marc L. Smith

Retrospective Theses and Dissertations

The development of distributed applications has not progressed as rapidly as its enabling technologies. In part, this is due to the difficulty of reasoning about such complex systems. In contrast to sequential systems, parallel systems give rise to parallel events, and the resulting uncertainty of the observed order of these events. Loosely coupled distributed systems complicate this even further by introducing the element of multiple imperfect observers of these parallel events. The goal of this dissertation is to advance parallel and distributed systems development by producing a parameterized model that can be instantiated to reflect the computation and coordination properties …

An Intelligent Editor For Natural Language Processing Of Unrestricted Text, Demetrios George Glinos

Retrospective Theses and Dissertations

The understanding of natural language by computational methods has been a continuing and elusive problem in artificial intelligence. In recent years there has been a resurgence in natural language processing research. Much of this work has been on empirical or corpus-based methods which use a data-driven approach to train systems on large amounts of real language data. Using corpus-based methods, the performance of part-of-speech (POS) taggers, which assign to the individual words of a sentence their appropriate part of speech category (e.g., noun, verb, preposition), now rivals human performance levels, achieving accuracies exceeding 95%. Such taggers have proved useful as …

Finding Paths In The Rotation Graph Of Binary Trees, Rodney O. Rogers

Retrospective Theses and Dissertations

A binary tree coding scheme is a bijection mapping a set of binary trees to a set of integer tuples called codewords. One problem considered in the literature is that of listing the codewords for n-node binary trees, such that successive codewords represent trees differing by a single rotation, a standard operation for rebalancing binary search trees. Then, the codeword sequence corresponds to an Hamiltonian path in the rotation graph R_n of binary trees, where each node is labelled with an n-node binary tree, and an edge connects two nodes when their trees differ by a …

Shape Reconstruction From Shading Using Linear Approximation, Ping Sing Tsai

Retrospective Theses and Dissertations

Shape from shading (SFS) deals with the recovery of 3D shape from a single monocular image. This problem was formally introduced by Horn in the early 1970s. Since then it has received considerable attention, and several efforts have been made to improve the shape recovery. In this thesis, we present a fast SFS algorithm, which is a purely local method and is highly parallelizable. In our approach, we first use the discrete approximations for surface gradients, p and q, using finite differences, then linearize the reflectance function in depth, Z ( x , y), instead of p and q. This …

Experimenting With The Finite Element Method In The Calculation Of Radiosity Form Factors, Donna Marie Chesteen

Retrospective Theses and Dissertations

Radiosity has been used to create some of the most photorealistic computer-generated images to date. The problem, however, is that radiosity algorithms are so computationally and memory expensive that few applications can employ them successfully. Form factor calculation is the most costly part of the process. This report describes an algorithm for using the finite element method to reduce the amount of time that is used in the form factor calculation portion of the radiosity algorithm. This technique for form factor calculation significantly reduces the number of projections done at each iteration by using shape functions to determine the distribution …

Global Domination Of Factors Of A Graph, Julie R. Carrington

Retrospective Theses and Dissertations

A factoring of a graph G = (V, E) is a collection of spanning subgraphs F₁, F₂, ... , F_k, known as factors into which the edge set E has been partitioned. A dominating set of a graph is a set of nodes such that every node in the graph is either contained in the set or has an edge to some node in the set. Each factor F_i is itself a graph and so has a dominating set. This set is called a local dominating set or LDS. An LDS of minimum …

Edge Contours, Donna J. Williams

Retrospective Theses and Dissertations

The accuracy with which a computer vision system is able to identify objects in an image is heavily dependent upon the accuracy of the low level processes that identify which points lie on the edges of an object. In order to remove noise and fine texture from an image, it is usually smoothed before edge detection is performed. This smoothing causes edges to be displaced from their actual location in the image. Knowledge about the changes that occur with different degrees of smoothing (scales) and the physical conditions that cause these changes is essential to proper interpretation of the results …

Generating Multiple User Interfaces For Multiple Application Domains, Mahesh Hassomal Dodani

Retrospective Theses and Dissertations

This Ph.D. dissertation presents a classification scheme for User Interface Development Environments (UIDEs) based on the multiplicity of user interfaces and application domains that can be supported. The SISD, SIMD and MISD [S= Single, I= user Interface(s), M= Multiple, D= application Domain(s)] generator classes encompass most of the UIDEs described in the literature. A major goal of this research is to allow any user to develop a personalized interface for any interactive application, that is, the development of an MIMD UIDE.

Fundamental to the development of such a UIDE is the complete separation of the user interface component from the …

Hardware Algorithms For Data Compression, N. Ranganathan

Retrospective Theses and Dissertations

Data compression is the reduction of redundancy m data representation in order to decrease storage and communication costs. Data compression techniques have been used in practice primarily through software implementations which fail to meet the speed and performance requirements of current and future systems. This Ph.D. dissertation presents a set of hardware algorithms for compression and decompression techniques and the results of detailed simulations performed to quantify the effects of incorporating such hardware in various architectural environments. A new pipelined algorithm for data compression applicable to static binary encoding schemes is presented. A fast hardware algorithm for decompression that uses …

A Coprocessor Design For The Architectural Support Of Non-Numeric Operations, Timothy W. Curry

Retrospective Theses and Dissertations

Computer Science is concerned with the electronic manipulation of information. Continually increasing amounts of computer time are being expended on information that is not numeric. This is represented in part by modem computing requirements such as the block moves associated with context switching and virtual memory management, peripheral device communication, compilers, editors, word processors, databases, and text retrieval. This dissertation examines the traditional support of non-numeric information from a software, firmware, and hardware perspective and presents a coprocessor design to improve the performance of a set of non-numeric operations. Simple micro-coding of operations can provide a degree of performance improvement …

Some Optimally Adaptive Parallel Graph Algorithms On Erew Pram Model, Sajal K. Das

Retrospective Theses and Dissertations

The study of graph algorithms is an important area of research in computer science, since graphs offer useful tools to model many real-world situations. The commercial availability of parallel computers have led to the development of efficient parallel graph algorithms.

Using an exclusive-read and exclusive-write (EREW) parallel random access machine (PRAM) as the computation model with a fixed number of processors, we design and analyze parallel algorithms for seven undirected graph problems, such as, connected components, spanning forest, fundamental cycle set, bridges, bipartiteness, assignment problems, and approximate vertex coloring. For all but the last two problems, the input data structure …

Automatically Generating Syntax-Directed Editors For Graphical Languages, Farahangiz Arefi

Retrospective Theses and Dissertations

This research is concerned with the automatic generation of syntax-directed editors for graphical programming languages. A specification technique that is used to uniformly define graphical languages along with their syntax-directed editors is developed. The novel aspect of this specification technique, called a general graph transformation system, is that the graphical languages are described by specifying a family of editing operations. In this manner, a language is defined as a dynamic object which, by applying different editing operations, changes from one form to another, each form representing a sentence of the language. In order to demonstrate this process, the language of …

On K - Y - Insensitive Donimation, Teresa Haynes Rice

Retrospective Theses and Dissertations

A connected graph G is defined to be k-1-insensitive if the domination number 1(G) is unchanged when an arbitrary set of k edges is removed. The problem has been solved fork= 1. This Ph.D. dissertation focuses on finding extremal k-1-insensitive graphs on p nodes, fork~ 2. A graph is extremal if it has the minimum number of edges. Two subproblems are considered. The first, which has been solved completely, specifies that the same set of nodes dominates each graph obtained from G by removing k edges. The second requires only that the graph G be connected. This is a much …

A Relational Object-Oriented Management System And An Encapsulated Object-Oriented Programming System, Michael L. Nelson

Retrospective Theses and Dissertations

The purpose of the Relational Object-Oriented Management System (ROOMS) is to show that the relational database scheme is a viable approach for storing objectoriented data. ROOMS is designed so that it can be implemented in any object-oriented language with appropriate I/O commands, or added to any objectoriented database management system that allows userdefined collections of data. Various problems were encountered in developing ROOMS. While these problems have been solved, the best solution is to use the Encapsulated Object-Oriented Programming System (EOOPS) . EOOPS is based upon an inheritance scheme which preserves encapsulation. This encapsulated approach avoids the problems associated with …

Design And Performance Analysis Of A Relational Replicated Database Systems, Jon Gregory Hanson

Retrospective Theses and Dissertations

The hardware organization and software structure of a new database system are presented. This system, the relational replicated database system (RRDS), is based on a set of replicated processors operating on a partitioned database. Performance improvements and capacity growth can be obtained by adding more processors to the configuration. Based on designing goals a set of hardware and software design questions were developed. The system then evolved according to a five-phase process, based on simulation and analysis, which addressed and resolved the design questions. Strategies and algorithms were developed for data access, data placement, and directory management for the hardware …

The Slicing Extent Technique For Fast Ray Tracing, Sudhanshu Kumar Semwal

Retrospective Theses and Dissertations

A new technique for image generation using ray tracing is introduced. The “Slicing Extent Technique” (SET) partitions object space with slicing planes perpendicular to all three axes. Planes are divided into two dimensional rectangular cells, which contain pointers to nearby objects. Cell size and the space between slices varies, and is determined by the objects’ locations and orientations. Unlike oct-tree and other space-partitioning methods, SET is not primarily concerned with dividing space into mutually exclusive volume elements (‘voxels’) and identifying objects within each voxel. Instead, SET is based on analysis of projections of objects onto slicing planes. In comparison to …

Epsilon Precedence Grammars And Languages, Masoud T. Milani

Retrospective Theses and Dissertations

The classes of simple and weak precedence grammars are generalized to include ε-rules (productions with the empty right parts). The descriptive power of epsilon simple precedence (ESP) grammars increases directly with the number of ε-rules permitted; the class of ESP grammars with no ε-rules, ESP₀, is identical to the class of simple precedence grammars; ESP grammars with at most one ε-rule, ESP₁, define a class of languages which properly includes the class of ESP₀ languages, but is itself properly included in the class of deterministic, context-free languages. In general, ESP grammars having at most i …

Intra Region Routing, Robert Alan Eustace

Retrospective Theses and Dissertations

The custom integrated circuit routing problem normally requires partitioning into rectangular routing regions. Natural partitions usually result in regions that form both "channels" and "areas". This dissertation introduces several new channel and area routing algorithms and measures their performance.

A formal description of the channel routing problem is presented and a relationship is established between the selection of intervals for each track and the number of tracks in the completed channel. This relationship is used as an analysis tool that leads to the development of two new and highly effective channel routing algorithms: the Revised and LCP algorithms. The performance …

Multiprocessor Scheduling With Practical Constraints, Kenneth Burton Donovan

Retrospective Theses and Dissertations

The problem of scheduling tasks onto multiprocessor systems has increasing practical importance as more applications are being addressed with multiprocessor systems. Actual applications and multiprocessor systems have many characteristics which become constraints to the general scheduling problem of minimizing the schedule length. These practical constraints include precedence relations and communication delays between tasks, yet few researchers have considered both these constraints when developing schedulers.

This work examines a more general multiprocessor scheduling problem, which includes these practical scheduling constraints, and develops a new scheduling heuristic using a list scheduler with dynamically computed priorities. The dynamic priority heuristic is compared against …

Incremental Analysis Of Programs, Vida Ghodssi

Retrospective Theses and Dissertations

Algorithms used to determine the control and data flow properties of computer programs are generally designed for one-time analysis of an entire new input. Application of such algorithms when the input is only slightly modified results in an inefficient system. In this theses a set of incremental update algorithms are presented for data flow analysis. These algorithms update the solution from a previous analysis to reflect changes in the program. Thus, extensive reanalysis to reflect changes in the program. Thus, extensive reanalysis of programs after each program modification can be avoided. The incremental update algorithms presented for global flow analysis …

An Analytical Model For Evaluating Database Update Schemes, Kathryn C. Kinsley

Retrospective Theses and Dissertations

A methodology is presented for evaluating the performance of database update schemes. The methodology uses the M/Hr/1 queueing model as a basis for this analysis and makes use of the history of how data is used in the database. Parameters have been introduced which can be set based on the characteristics of a specific system. These include update to retrieval ratio, average file size, overhead, block size and the expected number of items in the database. The analysis is specifically directed toward the support of derived data within the relational model. Three support methods are analyzed. These are first examined …