Theory and Algorithms Commons^™

An Analysis Of Bayesian Networks As Classifiers, Gregory C. Ahlquist

Theses and Dissertations

An analysis of Bayesian networks as classifiers is presented. This analysis results in an algorithm and several tools related to Bayesian network classifiers. The tools calculate and display the decision regions for two level Bayesian network classifiers. They collectively provide an approach to analyze the effects of changing network parameters on the network's decision regions. The algorithm defines a Bayesian network classifier to solve traditional classification problems. The algorithm is data driven, meaning that the resulting Bayesian network classifier is uniquely tuned to the classification problem at hand. Also, the algorithm contains procedures for defining the topology of a Bayesian …

The Fat-Pyramid And Universal Parallel Computation Independent Of Wire Delay, Ronald I. Greenberg

Computer Science: Faculty Publications and Other Works

This paper shows that a fat-pyramid of area Θ(A) requires only O(log A) slowdown to simulate any competing network of area A under very general conditions. The result holds regardless of the processor size (amount of attached memory) and number of processors in the competing networks as long as the limitation on total area is met. Furthermore, the result is valid regardless of the relationship between wire length and wire delay. We especially focus on elimination of the common simplifying assumption that unit time suffices to traverse a wire regardless of its length, since the assumption becomes more and more …

Logging Subsystem Performance: Model And Evaluation, Thomas K. Clark

Dissertations and Theses

Transaction logging is an integral part of ensuring proper transformation of data from one state to another in modern data management. Because of this, the throughput of the logging subsystem can be critical to the throughput of an application. The purpose of this research is to break the log bottleneck at minimum cost.

We first present a model for evaluating a logging subsystem, where a logging subsystem is made up of a log device, a log backup device, and the interconnect algorithm between the two, which we term the log backup method. Included in the logging model is a set …

Improved Algorithms For Bipartite Network Flow, Ravindra K. Ahuja, James B. B. Orlin, Clifford Stein, Robert E. Tarjan

Dartmouth Scholarship

In this paper, network flow algorithms for bipartite networks are studied. A network G = (V,E) is called bipartite if its vertex set V can be partitioned into two subsets V_1 and V_2 such that all edges have one endpoint in V_1 and the other in $V_2 $. Let $n = |V|, n_1 = |V_1 | , n_2 = |V_2 |, m = |E| and assume without loss of generality that n_1 \leqslant n_2. A bipartite network is called unbalanced if n_1 \ll n_2 $ and balanced otherwise. (This notion is necessarily imprecise.) It is shown that several maximum flow …

Defining Locally Shared Memory Constructs For Special Purpose Parallel Architectures, David J. Nielsen

Electrical & Computer Engineering Theses & Dissertations

Locally shared memory systems offer significant advantages over other parallel processing systems for specific classes of problems. Locally shared memory systems tend to be easier to program because explicit passing of messages is not necessary. The goal in defining a locally shared memory system is to allow only a small number of processors access to any single memory. If this goal is met, locally shared memory systems provide an architecture which is relatively simple to implement.

To make shared memory architectures attractive to designers of special purpose parallel architectures, the architectures must be scalable. To be scalable, the number of …

Genetic Algorithms And Artificial Life, Melanie Mitchell, Stephanie Forrest

Computer Science Faculty Publications and Presentations

Genetic algorithms are computational models of evolution that play a central role in many artificial-life models. We review the history and current scope of research on genetic algorithms in artificial life, giving illustrative examples in which the genetic algorithm is used to study how learning and evolution interact, and to model ecosystems, immune system, cognitive systems, and social systems. We also outline a number of open questions and future directions for genetic algorithms in artificial-life research

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 …

Dynamic Task Scheduling For The Atamm Multicomputer Operating System Using Embedded Firmware On Microcontrollers, Sudhir Sastry

Electrical & Computer Engineering Theses & Dissertations

A dynamic task scheduling strategy for the distributed processing of large grain dataflow algorithms using embedded firmware on an ATAMM testbed consisting of interconnected microcontrollers is presented in this thesis. The ODU/NASA developed Algorithm to Architecture Mapping Model, ATAMM, uses marked graph models to specify data and control flow for the execution of iterative, deterministic large grain dataflow algorithms in a multicomputing environment. The testbed consists of a bank of four 68HC11 microcontrollers that communicate over a token bus. The token bus arbitration scheme used is contention free and well suited for real-time computing applications. The execution of data flow …

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 …

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 …

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 …