Theory and Algorithms Commons^™

Electroencephalogram Artifact Removal Using A Wavelet Neural Network, Hoang-Anh T. Nguyen

Electrical & Computer Engineering Theses & Dissertations

A wavelet neural network (WNN) technique rs developed for electroencephalogram (EEG) artifact removal without electrooculographic (EOG) recordings. The algorithm combines the universal approximation characteristics of neural networks and the time/frequency property of wavelet, where the neural network was trained on a simulated dataset with known ground truths. The contribution of this thesis is two-fold. First, many EEG artifact removal algorithms, including regression based methods, require reference EOG signals, which are not always available. To remove EEG ai1ifacts, a WNN tries to learn the characteristics of the artifacts first and does not need reference EOG signals once trained. Second, WNNs are …

The Modular Clock Algorithm For Blind Rendezvous, Nicholas C. Theis

Theses and Dissertations

This thesis examines the problem in initializing communications whereby cognitive radios need to find common spectrum with other cognitive radios, a process known as frequency rendezvous. It examines the rendezvous problem as it exists in a dynamic spectrum access cognitive network. Specifically, it addresses the problem of rendezvous in an infrastructureless environment. A new algorithm, the modular clock algorithm, is developed and analyzed as a solution for the simple rendezvous environment model, coupled with a modified version for environment models with less information. The thesis includes a taxonomy of commonly used environment models, and analysis of previous efforts to solve …

A Multilane Pipelined Architecture For Real Time Enhancement Of Color Video Streams, Adam Redd Livingston

Electrical & Computer Engineering Theses & Dissertations

Video stream enhancement is a key fixture in a wide variety of applications from video surveillance, automatic navigation, medical imagery, to facial/object recognition systems. When a video stream contains non-uniform lighting it can be difficult to obtain what is in the darker regions without over enhancing brighter regions. The Adaptive and Integrated Neighborhood Dependant Approach for Nonlinear Enhancement (AINDANE) algorithm combines a tunable nonlinear transfer function, convolution by a multi-scale Gaussian kernel, and tunable contrast enhancement to address this problem for a single image. Luminance values are tuned based on the global cumulative distribution function (CDF) of an image. Contrast …

A Tabu Search Algorithm To Minimize The Makespan For The Unrelated Parallel Machines Scheduling Problem With Setup Times, Magdy Helal, Ghaith Rabadi, Ameer Al-Salem

Engineering Management & Systems Engineering Faculty Publications

In this paper we propose a tabu search implementation to solve the unrelated parallel machines scheduling problem with sequence- and machine- dependent setup times to minimize the schedules makespan. The problem is NP-hard and finding an optimal solution efficiently is unlikely. Therefore, heuristic techniques are more appropriate to find near-optimal solutions. The proposed tabu search algorithm uses two phases of perturbation schemes: the intra-machine perturbation, which optimizes the sequence of jobs on the machines, and the inter-machine perturbation, which balances the assignment of the jobs to the machines. We compare the proposed algorithm to an existing one that addressed the …

Efficient Scheduling For Sdmg Cioq Switches, Mei Yang, S. Q. Zheng

Electrical & Computer Engineering Faculty Research

Combined input and output queuing (CIOQ) switches are being considered as high-performance switch architectures due to their ability to achieve 100% throughput and perfectly emulate output queuing (OQ) switch performance with a small speedup factor S. To realize a speedup factor S, a conventional CIOQ switch requires the switching fabric and memories to operate S times faster than the line rate. In this paper, we propose to use a CIOQ switch with space-division multiplexing expansion and grouped input/output ports (SDMG CIOQ switch for short) to realize speedup while only requiring the switching fabric and memories to operate at the line …

Vector Operations In Superscalar Architectures, Nathan Daniel Flinn

Electrical & Computer Engineering Theses & Dissertations

Vector calculations are very prevalent today. Though the vector-processing computer is quite an old concept, superscalar processors lack hardware support for vector operations. This thesis investigates whether an ordinary superscalar computer architecture can be designed to include hardware support for improved vector operations without drastically changing the existing superscalar design and behavior. A computer architecture design was created and implemented that included the vector multiply (dot product) operation. The design includes a Vector Operations Unit that captures incoming vector operations and generates the necessary set of machine instructions to complete the vector operation internally. It then delivers these instructions to …

Hierarchical Hybrid Multicast An End System Multicast Algorithm Approach, Guillermo Loaisiga

Electrical & Computer Engineering Theses & Dissertations

Due to the rapid development in the computer and communication technologies, the Internet is experiencing an increasing demand of high-speed, real-time distributed applications, such as live streaming multimedia, videoconferencing, distributed simulations, and multiparty games. Multicast is an efficient transmission mechanism to support these applications. Historically, IP Multicast (IPM) has provided multicast support with well-known benefits, especially in bandwidth savings. However, it has experienced little deployment due to economic and architectural limitations.

Overlay multicast holds promise for the implementation of large scale Internet multicast services. An overlay network is a virtual topology constructed on top of the Internet infrastructure. This concept …

Architectural Optimization Of Digital Libraries, Aileen O. Biser

Computer Science Theses & Dissertations

This work investigates performance and scaling issues relevant to large scale distributed digital libraries. Presently, performance and scaling studies focus on specific implementations of production or prototype digital libraries. Although useful information is gained to aid these designers and other researchers with insights to performance and scaling issues, the broader issues relevant to very large scale distributed libraries are not addressed. Specifically, no current studies look at the extreme or worst case possibilities in digital library implementations. A survey of digital library research issues is presented. Scaling and performance issues are mentioned frequently in the digital library literature but are …

Modeling And Comparison Of Wormhole Routed Mesh And Torus Networks, Ronald I. Greenberg, Lee Guan

Computer Science: Faculty Publications and Other Works

2D-mesh and torus networks have often been proposed as the interconnection pattern for parallel computers. In addition, wormhole routing has increasingly been advocated as a method of reducing latency. Most analysis of wormhole routed networks, however, has focused on the torus and the broader class of k-ary n-cubes to which it belongs. This paper presents a performance model for the wormhole routed mesh, and it compares the performance of the mesh and torus based on theoretical and empirical analyses.

An Improved Analytical Model For Wormhole Routed Networks With Application To Butterfly Fat-Trees, Ronald I. Greenberg, Lee Guan

Computer Science: Faculty Publications and Other Works

A performance model for wormhole routed interconnection networks is presented and applied to the butterfly fat-tree network. Experimental results agree very closely over a wide range of load rate. Novel aspects of the model, leading to accurate and simple performance predictions, include (1) use of multiple-server queues, and (2) a general method of correcting queuing results based on Poisson arrivals to apply to wormhole routing. These ideas can also be applied to other networks.

Scheduling Processors For Distributed, Critical, Real-Time Systems, Hari K. Narasimhamurthy

Electrical & Computer Engineering Theses & Dissertations

The development of a procedure to obtain cyclo-static schedules for distributed, critical real-time applications is presented in this thesis. The applications considered in this thesis are characterized by hard deadlines and periodic inputs. The applica­ tions are described by a data flow graph model which guarantees performance. Given the data flow graph representation, processors are scheduled to complete tasks as specified in the representation. The scheduling technique separates the scheduling of tasks in time and the assignment of processors to tasks. While different criteria exist for task scheduling, a schedule which minimizes latency and maximizes throughput is used in this …

Fault Tolerance In Critical Real-Time Systems, Balaji Tirukarneswaran

Electrical & Computer Engineering Theses & Dissertations

Critical real-time applications require work to be completed before a predefined deadline, else the consequences may be catastrophic. The anticipation of faults in such systems necessitates the need for fault tolerance. Fault tolerance can be achieved in many different ways. A real-time system designer may impose restrictions on any of the system performance measures such as the latency, throughput and number of processors, depending on the type of application. In this work, several different fault tolerant strategies for any given DFG (Data Flow Graph) are discussed. DFG models are developed using the strategies and the resulting worst case performances a.re …

Real-Time Communication In The Algorithm To Architecture Mapping Model, Somesh M. Varma

Electrical & Computer Engineering Theses & Dissertations

The objective of this thesis is to analyze schedules of communication resources to obtain deterministic and contention-free communication in the Algorithm To Architecture Mapping Model (ATAMM). In ATAMM, performance must be deterministic to guarantee meeting deadlines. It is difficult to achieve deterministic performance in the presence of contention during communication. This thesis develops new data-flow models to study and analyze different schedules of communication resources to achieve deterministic and contention-free communication. These models are the Synchronous Communication Marked Graph (SCMG) and the Asynchronous Communication Marked Graph (ACMG). The SCMG is based on message passing synchronous communication. It defines schedules for …

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 …

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 …

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

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

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.

Software Tools For Performance Evaluation Of Concurrent Processing, Rodrogo A. Obando

Electrical & Computer Engineering Theses & Dissertations

The development and use of software tools for performance evaluation of concurrent processing is presented in this thesis. The particular concurrent processing architecture proposed by Stoughton and Mielke is investigated. The modelling of this architecture is based on Petri net theory and it can be studied making use of circuit theory. Computation of lower bounds for Time Between Outputs (TBO) and Time Between Input and Output (TBIO) can be accomplished by using principles of circuit theory, among others. This new modelling needs to be deeply evaluated and studied. This evaluation and study is accomplished with the tools developed and presented …

Randomized Routing On Fat-Trees, Ronald I. Greenberg

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+lgnlglgn) with probability 1-O(1/ …