Theory and Algorithms Commons^™

Polylog Depth Circuits For Integer Factoring And Discrete Logarithms, Jonathan P. Sorenson

Scholarship and Professional Work - LAS

AbstractIn this paper, we develop parallel algorithms for integer factoring and for computing discrete logarithms. In particular, we give polylog depth probabilistic boolean circuits of subexponential size for both of these problems, thereby solving an open problem of Adleman and Kompella.

Existing sequential algorithms for integer factoring and discrete logarithms use a prime base which is the set of all primes up to a bound B. We use a much smaller value for B for our parallel algorithms than is typical for sequential algorithms. In particular, for inputs of length n, by setting B = nlogdn with d a positive …

Effective Parallel Algorithm Animation, Paul W. Chase

Theses and Dissertations

The AFIT Algorithm Animation Research Facility AAARF was developed by the Air Force Institute of Technology AFIT as a teaching aid for data structures and algorithm design. In particular, an extensive set of performance animations has been developed for the Intel iPSC Hypercube parallel processing system. This research focuses in part on developing animation support for discrete event simulation, mission routing, and evolutionary algorithms based on abstract representations of parallel algorithm behavior. The effort also builds extensions to the AAARF system and examines direction for further research. An innovative adaptable application-specific animation construction environment has been designed and implemented. The …

Adaptive Execution Of Data Parallel Computations On Networks Of Heterogeneous Workstations, Robert Prouty, Steve Otto, Jonathan Walpole

Computer Science Faculty Publications and Presentations

Parallel environments consisting of a network of heterogeneous workstations introduce an inherently dynamic environment that differs from multicomputers. Workstations are usually considered “shared” resources while multicomputers provide dedicated processing power. The number of workstations available for use is continually changing; the parallel machine presented by the network is in effect continually reconfiguring itself. Application programs must effectively adapt to the changing number of processing nodes while maintaining computational efficiency. This paper examines methods for adapting to this dynamic environment within the framework of explicit message passing under the data parallel programming model. We present four requirements which we feel a …

A Topology-Aware Collision Resolution Algorithm, Lewis Barnett Iii

Department of Math & Statistics Technical Report Series

A new collision resolution algorithm called the Space Division Multiple Access protocol (SDMA) is presented. SDMA gains a performance advantage over similar protocols by using information about the positions of stations on the network. The protocol can operate asynchrononsly on a broadcast bus, allowing variable sized packet traffic. Through simulation the protocol is demonstrated to have better performance than Ethernet and the Capetanakis Tree protocol, a similar collision resolution protocol, under some traffic conditions. In particular, under heavy loads, SDMA displays better average throughput and lower variance of delay than Ethernet. The protocol demonstrates a performance bias based on the …

A Greedy Hypercube-Labeling Algorithm, D. Bhagavathi, C. E. Grosch, S. Olariu

Computer Science Faculty Publications

Due to its attractive topological properties, the hypercube multiprocessor has emerged as one of the architectures of choice when it comes to implementing a large number of computational problems. In many such applications, Gray-code labelings of the hypercube are a crucial prerequisite for obtaining efficient algorithms. We propose a greedy algorithm that, given an n-dimensional hypercube H with N=2² nodes, returns a Gray-code labeling of H, that is, a labeling of the nodes with binary strings of length n such that two nodes are neighbors in the hypercube if, and only if, their labels differ in exactly …

Parallel Algorithms For Single-Layer Channel Routing, Ronald I. Greenberg, Shih-Chuan Hung, Jau-Der Shih

Computer Science: Faculty Publications and Other Works

We provide efficient parallel algorithms for the minimum separation, offset range, and optimal offset problems for single-layer channel routing. We consider all the variations of these problems that have linear-time sequential solutions rather than limiting attention to the ``river-routing'' context, where single-sided connections are disallowed. For the minimum separation problem, we obtain O(lgN) time on a CREW PRAM or O(lgN/lglgN) time on a CRCW PRAM, both with optimal work (processor-time product) of O(N), where N is the number of terminals. For the offset range problem, we obtain the same time and processor bounds as long as only one side of …

Universal Wormhole Routing, Ronald I. Greenberg, Hyeong-Cheol Oh

Computer Science: Faculty Publications and Other Works

We examine the wormhole routing problem in terms of the "congestion" c and "dilation" d for a set of packet paths. We show, with mild restrictions, that there is a simple randomized algorithm for routing any set of P packets in O(cdη + cLηlog P) time, where L is the number of flits in a packet, and η = min {d,L]; only a constant number of flits are stored in each queue at any time. Using this result, we show that a fat-tree network of area Θ(A) can simulate wormhole routing on any network of comparable area with O(log 3 …

Cyclo-Static Scheduling Of Large Grain Dataflow Algorithms On A Local Area Atamm Multicomputing Testbed, Sudeepto Roy

Electrical & Computer Engineering Theses & Dissertations

A strategy for cyclo-statically scheduling deterministic large grain dataflow (LGDF) algorithms for distributed execution on loosely coupled multicomputer architectures is presented in this research. The computational paradigm used is the ODU/NASA developed Algorithm To Architecture Mapping Model (ATAMM), which consists of marked graphs and Gantt chart representations that model the iterative execution of deterministic LGDF algorithms for different values of throughput and computation time. It is postulated that the behavior of these algorithms could be represented by the aggregate execution of an ensemble of cyclically shifted threads of a specific node sequence. Assuming the existence of one or more such …

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 …

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 …

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.

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 …

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 …

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 …

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 …

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).

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 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 …