Physical Sciences and Mathematics Commons^™

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 …

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 …

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 …

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 …