Computer Sciences Commons^™

Feasible Offset And Optimal Offset For Single-Layer Channel Routing, Ronald I. Greenberg, Jau-Der Shih

Computer Science: Faculty Publications and Other Works

The paper provides an efficient method to find all feasible offsets for a given separation in a VLSI channel routing problem in one layer. The prior literature considers this task only for problems with no single-sided nets. When single-sided nets are included, the worst-case solution time increases from Theta(n) to Omega(n^2), where n is the number of nets. But, if the number of columns c is O(n), one can solve the problem in time O(n^{1.5}lg n ), which improves upon a `naive' O(cn) approach. As a corollary of this result, the same time bound suffices to find the optimal offset …

Minimizing Channel Density With Movable Terminals, Ronald I. Greenberg, Jau-Der Shih

Computer Science: Faculty Publications and Other Works

We give algorithms to minimize density for channels with terminals that are movable subject to certain constraints. The main cases considered are channels with linear order constraints, channels with linear order constraints and separation constraints, channels with movable modules containing fixed terminals, and channels with movable modules and terminals. In each case, previous results for running time and space are improved by a factor of L/lg n and L , respectively, where L is the channel length and n is the number of terminals.

Matching Points To Lines: Sonar-Based Localization For The Psubot, Kevin Blythe Stanton

Dissertations and Theses

The PSUBOT (pronounced pea-es-you-bought) is an autonomous wheelchair robot for persons with certain disabilities. Its use of voice recognition and autonomous navigation enable it to carry out high level commands with little or no user assistance. We first describe the goals, constraints, and capabilities of the overall system including path planning and obstacle avoidance. We then focus on localization-the ability of the robot to locate itself in space. Odometry, a compass, and an algorithm which matches points to lines are each employed to accomplish this task. The matching algorithm (which matches "points" to "lines") is the main contribution to this …

A Fast Serial Algorithm For The Finite Temperature Quenched Potts Model, Gregory N. Hassold, Elizabeth A. Holm

Physics Publications

An efficient serial algorithm for finite temperature, quenched Potts model simulations of domain evolution has been developed. This ''n‐fold way'' algorithm eliminates unsuccessful spin flip attempts a priori by flipping sites with a frequency proportional to their site activity, defined as the sum of the probability of success for every possible spin flip at that site. Finite temperature efficiency for high‐spin degeneracy systems is achieved by utilizing a new, analytical expression for the portion of the site activity due to flips to non-neighbor spin values. Hence, to determine the activity of a site, only flips to the …

On The Difficulty Of Manhattan Channel Routing, Ronald I. Greenberg, Joseph Jaja, Sridhar Krishnamurthy

Computer Science: Faculty Publications and Other Works

We show that channel routing in the Manhattan model remains difficult even when all nets are single-sided. Given a set of n single-sided nets, we consider the problem of determining the minimum number of tracks required to obtain a dogleg-free routing. In addition to showing that the decision version of the problem isNP-complete, we show that there are problems requiring at least d+Omega(sqrt(n)) tracks, where d is the density. This existential lower bound does not follow from any of the known lower bounds in the literature.

Generalization And Parallelization Of Messy Genetic Algorithms And Communication In Parallel Genetic Algorithms, Laurence D. Merkle

Theses and Dissertations

Genetic algorithms (GA) are highly parallelizable, robust semi- optimization algorithms of polynomial complexity. The most commonly implemented GAs are 'simple' GAs (SGAs). Reproduction, crossover, and mutation operate on solution populations. Deceptive and GA-hard problems are provably difficult for simple GAs. Messy GAs (MGA) are designed to overcome these limitations. The MGA is generalized to solve permutation type optimization problems. Its performance is compared to another MGA's, an SGA's, and a permutation SGA's. Against a fully deceptive problem the generalized MGA (GMGA) consistently performs better than the simple GA. Against an NP-complete permutation problem, the GMGA performs better than the other …

Packet Routing In Networks With Long Wires, Ronald I. Greenberg, H.-C. Oh

Computer Science: Faculty Publications and Other Works

In this paper, we examine the packet routing problem for networks with wires of differing length. We consider this problem in a network independent context, in which routing time is expressed in terms of “congestion” and “dilation” measures for a set of packet paths. We give, for any constant ε > 0, a randomized on-line algorithm for routing any set of N packets in O((Clg^ε(Nd)+Dlg(Nd))/lglg(Nd)) time, where C is the maximum congestion and D is the length of the longest path, both taking wire delays into account, and d is the longest path in terms of number of wires. We also …

Autonomous Face Segmentation, Kevin P. Gay

Theses and Dissertations

The purpose of this study was to implement an autonomous face segmentor as the front end to a face recognition system on a Sun SPARCStation2. Face recognition performance criteria, specifically, the capabilities to isolate and resize faces in an image to a consistent scale, were analyzed to determine current practical limitations. Face images were acquired using a S-VHS camcorder. Segmentation was accomplished using motion detection and predefined rules. Tests were run to determine the suitable of the autonomous segmentor as the front-end to a face recognition system. The segmentation system developed consistently located faces and rescaled those faces to a …

Multiple Learner Systems Using Resampling Methods, Binyun Xie

Computer Science Theses & Dissertations

The N-Learners Problem deals with combining a number of learners such that the resultant system is "better", under some criterion, than the best of the individual learners. We consider a system of probably approximately correct concept learners. Depending on the available information, there are several methods to make the composite system better than the best of the individual learners. If a sample and an oracle that generates data points (but, not their classification) is available, then we show that we can achieve arbitrary levels of the normalized confidence of the composite system if (a) a robust learning algorithm is available, …

Formant Estimation From Dctc's Using A Feedforward Neural Network, Shubhangi U. Kelkar

Electrical & Computer Engineering Theses & Dissertations

Formants are the natural frequencies of the human vocal tract. Existing methods for estimating formants from speech signals are computationally complex and subject to errors for certain type of speech sounds. This thesis describes a method for estimating vowel formant frequencies from Discrete Cosine Transform Coefficients (DCTC's), a form of cepstral coefficients, using a feedforward neural network with back-propagation training. Experimental results are based on a large multispeaker data base. The results are obtained for both a linear transformation and a feedforward neural network with a nonlinear hidden layer. In general, the neural network transformation is superior to the linear …

Implementation And Analysis Of Np-Complete Algorithms On A Distributed Memory Computer, Joel S. Garmon

Theses and Dissertations

The purpose of this research is to explore methods used to parallelize NP-complete problems and the degree of improvement that can be realized using different methods of load balancing. A serial and four parallel A* branch and bound algorithms were implemented and executed on an Intel iPSC/2 hypercube computer. One parallel algorithm used a global, or centralized, list to store unfinished work and the other three parallel algorithms used a distributed list to store unfinished work locally on each processor. the three distributed list algorithms are: without load balancing, with load balancing, and with load balancing and work distribution. The …

Finding A Maximum-Density Planar Subset Of A Set Of Nets In A Channel, Ronald I. Greenberg, Jau-Der Shih

Computer Science: Faculty Publications and Other Works

We present efficient algorithms to find a maximum-density planar subset of n 2-pin nets in a channel. The simplest approach is to make repeated usage of Supowit's dynamic programming algorithm for finding a maximum-size planar subset, which leads to O(n^3) time to find a maximum-density planar subset. But we also provide an algorithm whose running time is dependent on other problem parameters and is often more efficient. A simple bound on the running time of this algorithm is O(nlgn+n(t+1)w), where t is the number of two-sided nets, and w is the number of nets in the output. Though the worst-case …

Face Recognition With The Karhunen-Loeve Transform, Pedro F. Suarez

Theses and Dissertations

The major goal of this research was to investigate machine recognition of faces. The approach taken to achieve this goal was to investigate the use of Karhunen-Loe've Transform (KLT) by implementing flexible and practical code. The KLT utilizes the eigenvectors of the covariance matrix as a basis set. Faces were projected onto the eigenvectors, called eigenfaces, and the resulting projection coefficients were used as features. Face recognition accuracies for the KLT coefficients were superior to Fourier based techniques. Additionally, this thesis demonstrated the image compression and reconstruction capabilities of the KLT. This theses also developed the use of the KLT …

Control Of A Large Flexible Space Structure Using Multiple Model Adaptive Algorithms, John A. Gustafson

Theses and Dissertations

The development and performance of moving-bank multiple model adaptive estimation (MMAE) and control (MMAC) algorithms for quelling vibrations induced in the SPICE 2 space structure are analyzed in this thesis. The structure consists of a large platform and a smaller platform connected by three legs in a tripod fashion. The model supplied by Phillips Laboratory, Kirtland AFB is used to develop a truth model and multiple reduced ordered filter models. The filter models are developed from modal analysis and internally balanced techniques. Deviations of the line-of-sight vector from the center of the large platform to the center of the smaller …

Visual Knowledge Query Language As A Front-End To Relational Systems, Keng Siau, Kok Phuang Tan, Hock Chuan Chan

Research Collection School Of Computing and Information Systems

Relational query languages like SQL and QUEL require the users to understand the complex database structure. This is a burden on end users, especially novice end users who access the database on a casual and infrequent basis. To alleviate the need to know the logical database organization, this paper proposes the use of a semantic data model, known as the Enhanced Entity-Relationship (EER) model, as a front-end to the relational systems. A formal, high-level Visual Knowledge Query Language (VKQL) has also been designed for this interface. This language provides for knowledge abstraction as the user communicates only domain knowledge with …

Visual Knowledge Query Language As A Front-End To Relational Systems, Keng Siau, Kok Phuang Tan, Hock Chuan Chan

Research Collection School Of Computing and Information Systems

Relational query languages like SQL and QUEL require the users to understand the complex database structure. This is a burden on end users, especially novice end users who access the database on a casual and infrequent basis. To alleviate the need to know the logical database organization, this paper proposes the use of a semantic data model, known as the Enhanced Entity-Relationship (EER) model, as a front-end to the relational systems. A formal, high-level Visual Knowledge Query Language (VKQL) has also been designed for this interface. This language provides for knowledge abstraction as the user communicates only domain knowledge with …

Indifference Graphs And The Single Row Routing Problem, Peter J. Looges

Computer Science Theses & Dissertations

This thesis investigates the subclass of interval graphs known as indifference graphs. New optimal algorithms for recognition, center, diameter, maximum matching, Hamiltonian path and domination in indifference graphs are presented. The recognition algorithm produces a linear order with properties which allow the solution of the other problems in linear time. Indifference graphs are further applied to the single row routing problem which results in both sequential,. and parallel routing algorithms.

Simulator For Concurrent Processing Data Flow Architectures, Mahyar R. Malekpour

Electrical & Computer Engineering Theses & Dissertations

A software simulator capable of simulating execution of an algorithm graph on a given system under the Algorithm To Architecture Mapping Model (ATAMM) rules is presented in this thesis. ATAMM is capable of modeling the execution of large-grained algorithms on distributed data flow architectures. Investigating the behavior and determining the performance of an ATAMM based system requires the aid of software tools. The ATAMM Simulator presented in this thesis is capable of determining the behavior, performance, and reliability of a system without having to build a hardware prototype. Case studies are performed on four algorithms to demonstrate the capabilities of …

An Analysis And Implementation Of Linear Derivation Strategies, Winston M. Tabada

Theses: Doctorates and Masters

This study examines the efficacy of six linear derivation strategies: (i) s-linear resolution, (ii) the ME procedure; (iii) t-linear resolution, (iv) SL -resolution, (v) the GC procedure, and (vi) SLM. The analysis is focused on the different restrictions and operations employed in each derivation strategy. The selection function, restrictive ancestor resolution, compulsory ancestor resolution on literals having atoms which are or become identical, compulsory merging operations, reuse of truncated literals, spreading of FALSE literals, no-tautologies resection, no two non-B-literals having identical atoms restriction, and the use of semantic information to trim irrelevant derivations from the search tree are the major …

A Mergeable Double-Ended Priority Queue, S. Olariu, Z. Wen

Computer Science Faculty Publications

An implementation of a double-ended priority queue is discussed. This data structure referred to as min–max–pair heap can be built in linear time; the operations Delete-min, Delete-max and Insert take O(log n) time, while Find-min and Find-max run in O(1) time. In contrast to the min-max heaps, it is shown that two min–max–pair heaps can be merged in sublinear time. More precisely, two min–max–pair heaps of sizes n and k can be merged in time O(log (n/k) * log k).

A Software Design Tool For Predictable Performance In Real-Time, Data Flow Architectures, Brij Mohan V. Mandala

Electrical & Computer Engineering Theses & Dissertations

A software design tool which aids in the performance evaluation and selection of operating points for an algorithm implemented in ATAMM defined data flow architectures is presented in this thesis. ATAMM (Algorithm To Architecture Mapping Model) is a new graph theoretic model developed by researchers at Old Dominion University and the NASA-Langley Research Center. ATAMM is capable of modeling the execution of large-grained algorithms on distributed data flow architectures. A software tool is required for predicting the performance, determining the resource requirements and for selecting suitable operating points for an ATAMM based system. The ATAMM Design Tool presented in this …

Encoding Phonetic Knowledge For Use In Hidden Markov Models Of Speech Recognition, Danming Qian

Electrical & Computer Engineering Theses & Dissertations

Hidden Markov models (HMM's) have achieved considerable success for isolated-word speaker-independent automatic speech recognition. However, the performance of an HMM algorithm is limited by its inability to discriminate between similar sounding words. The problem arises because all differences between speech patterns are treated as equally important. Thus the algorithm is particularly susceptible to confusions caused by phonetically-irrelevant differences. This thesis presents two types of preprocessing schemes as candidates for improving HMM performance. The aim is to maximize the differences between phonologically-distinct speech sounds while minimizing the effect of variations in phonologically-equivalent speech sounds. The preprocessors presented are a discrete cosine …

A Root Finding Algorithm For Parallel Architecture Machines, Stuti Moitra

Computer Science Theses & Dissertations

In this thesis a parallel algorithm for determining the zeros of any given analytic function is described. Parallelism is achieved by modifying the traditional bisection algorithm for architecture machines.

Given any user supplied function f(X), continuous on the interval A_o ≤ x ≤ B₀, and the tolerance of accuracy an algorithm of determining up to ten roots, with error of approximation less than or equal to tolerance, on parallel systems like Distributed Array Processor (OAP) and N-cube is considered.

A variation of the bisection method has been adapted for this purpose. At each level of iteration a …

Diagnostics Software For Concurrent Processing Computer Systems, Robert L. Jones Iii

Electrical & Computer Engineering Theses & Dissertations

Diagnostics software for analyzing ATAMM based concurrent processing systems is presented in this thesis. ATAMM (Algorithm to Architecture Mapping Model) is a new model developed by researchers at Old Dominion University and the NASA-Langley Research Center. ATAMM is capable of modeling the execution of large grain algorithms on distributed data flow architectures. Investigating a real or simulated ATAMM based system requires the aid of software tools. The software tool presented in this thesis can evaluate the behavior and performance of an ATAMM based system. The tool graphically portrays algorithm activities and processor activities. The tool's measurement capabilities indicate computing speed, …

Efficient Schemes To Evaluate Transaction Performance In Distributed Database Systems, R. Mukkamala, S. C. Bruell

Computer Science Faculty Publications

Database designers and researchers often need efficient schemes to evaluate transaction performance. In this paper, we chose two important performance measures: the average number of nodes accessed and the average number of data items accessed per node by a transaction in a distributed database system. We derive analytical expressions to evaluate these metrics. For general applicability, we consider partially replicated distributed database systems. Our first set of analytic results are closed-form expressions for these two measures. These are based on some fairly restrictive simplifying assumptions. When these assumptions are relaxed, no closed-form expressions exist for these averages. Hence, we develop …

Pipelining Data Compression Algorithms, R. L. Bailey, R. Mukkamala

Computer Science Faculty Publications

Many different data compression techniques currently exist. Each has its own advantages and disadvantages. Combining (pipelining) multiple data compression techniques could achieve better compression rates than is possible with either technique individually. This paper proposes a pipelining technique and investigates the characteristics of two example pipelining algorithms. Their performance is compared with other well-known compression techniques.

Optical Machine Recognition Of Lower-Case Greek Characters Of Any Size, Ivan X. D. D'Cunha

Electrical & Computer Engineering Theses & Dissertations

An algorithm utilizing a syntactic approach and a criterion based on normalized moments is defined for the reliable, automatic, machine recognition of handwritten and printed Greek characters of any size and font. In this approach a binary image of the character in question is obtained initially; its skeleton is then produced by utilizing a standard thinning algorithm. The classification process then incorporates the topological features of the characters such as existence of closed curves, number of intersections, number and location of free ends, axial symmetry, and the criteria derived from normalized moments to uniquely identify each pattern. Experiments conducted demonstrated …

Efficient Interconnection Schemes For Vlsi And Parallel Computation, Ronald I. Greenberg

Computer Science: Faculty Publications and Other Works

This thesis is primarily concerned with two problems of interconnecting components in VLSI technologies. In the first case, the goal is to construct efficient interconnection networks for general-purpose parallel computers. The second problem is a more specialized problem in the design of VLSI chips, namely multilayer channel routing. In addition, a final part of this thesis provides lower bounds on the area required for VLSI implementations of finite-state machines. This thesis shows that networks based on Leiserson's fat-tree architecture are nearly as good as any network built in a comparable amount of physical space. It shows that these "universal" networks …

Efficient Multi-Layer Channel Routing, Ronald I. Greenberg

Computer Science: Faculty Publications and Other Works

No abstract provided.

Randomized Routing On Fat-Trees, Ronald I. Greenberg, Charles E. Leiserson

Computer Science: Faculty Publications and Other Works

Fat-trees are a class of routing networks for hardware-efficient parallel computation. This paper presents a randomized algorithm for routing messages on a fat-tree. The quality of the algorithm is measured in terms of the load factor of a set of messages to be routed, which is a lower bound on the time required to deliver the messages. We show that if a set of messages has load factor lambda on a fat-tree with n processors, the number of delivery cycles (routing attempts) that the algorithm requires is O(lambda + lg n lg lg n) with probability 1-O(1/n). The best previous …