Theory and Algorithms Commons^™

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 …

The Reliability Of The Computer Communication Networks Including Mobile Nodes, Sahin Yasar

Electrical & Computer Engineering Theses & Dissertations

The wireless computer networks have an uncertainty in their structures aside from their big advantages for the users. The environmental conditions, changing locations of the mobile hosts and the changing components in the system can easily affect their reliability. In order to know a system capability performing its functions, keep the reliability at a certain level and/or detect the deficiency of the system, it is necessary to analyze the reliability of a computer communication network including the wired and wireless parts. But the above reasons also make the analysis and a unique solution difficult so a set of algorithms is …

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 …

Robust And Efficient Localization Techniques For Cellular And Wireless Sensor Networks, Haseebulla M. Khan

Computer Science Theses & Dissertations

Localization in wireless networks refers to a collection of tasks that, collectively, determines the location of a mobile user, striving to hide the effects of mobility from the user and/or application. Localization has become an important issue and has drawn considerable attention, as many applications including E-911, cargo tracking, locating patients, location-sensitive billing, etc., require knowledge of the location of user/objects. It was realized, quite a while back, that extending emergency 911-like services (E-911) to continually growing mobile population is one of the extremely important localization applications. The bulk of the proposed solutions to emergency location management in wireless environments …

Mobility-Pattern Based Localization Update Algorithm For Mobile Wireless Sensor Networks, Mohammad Yacoub Al-Laho

Electrical & Computer Engineering Theses & Dissertations

In mobile wireless sensor networks, sensors move in the monitored area at any direction and speed. Unlike many other networking hosts, sensor nodes do not have global addresses. They are often identified by using a location-based addressing scheme. Therefore, it is important to have the knowledge of the sensor location indicating where the data came from. In this thesis, three localization update algorithms were designed, Specifically, a sensor movement is divided into three states: Pause, Linear, and Random. Each state adopts different localization update algorithm. Since complex movement involves different mobility patterns, a state transition model is developed to …

Introduction: Data Communication And Topology Algorithms For Sensor Networks, Stephan Olariu, David Simplot-Ryl, Ivan Stojmenovic

Computer Science Faculty Publications

(First paragraph) We are very proud and honored to have been entrusted to be Guest Editors for this special issue. Papers were sought to comprehensively cover the algorithmic issues in the “hot” area of sensor networking. The concentration was on network layer problems, which can be divided into two groups: data communication problems and topology control problems. We wish to briefly introduce the five papers appearing in this special issue. They cover specific problems such as time division for reduced collision, fault tolerant clustering, self-stabilizing graph optimization algorithms, key pre-distribution for secure communication, and distributed storage based on spanning trees …

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 …

An Algorithm For Locating Fundamental Frequency (F0) Markers In Speech, Princy Dikshit

Electrical & Computer Engineering Theses & Dissertations

Speech has been the principal form of human communication since it began to evolve at least one hundred thousand years ago. Speech is produced by vibrations of the vocal cords. The rate of vibration of the cords is called fundamental frequency (F0) or pitch. The objective of this thesis is to locate pitch period cycles on a cycle-by-cycle basis. The complexity in identifying pitch cycles stems from the highly irregular nature of human speech. Dynamic programming is used to combine two sources of information for pitch period marking. One source of information is the "local" information corresponding to the location …

A Fast And Simple Algorithm For Computing M-Shortest Paths In State Graph, M. Sherwood, Laxmi P. Gewali, Henry Selvaraj, Venkatesan Muthukumar

Electrical & Computer Engineering Faculty Research

We consider the problem of computing m shortest paths between a source node s and a target node t in a stage graph. Polynomial time algorithms known to solve this problem use complicated data structures. This paper proposes a very simple algorithm for computing all m shortest paths in a stage graph efficiently. The proposed algorithm does not use any complicated data structure and can be implemented in a straightforward way by using only array data structure. This problem appears as a sub-problem for planning risk reduced multiple k-legged trajectories for aerial vehicles.

Unidirectional Cordic For Efficient Computation Of Trigonometric And Hyperbolic Functions, Satish Ravichandran

Electrical & Computer Engineering Theses & Dissertations

CORDIC (Coordinate Rotation Digital Computer) is an iterative algorithm to compute values of trigonometric, logarithmic and transcendental functions by performing vector rotations, which can be implemented with only shift and add operations in a digital system. CORDIC algorithms are extensively used in the areas of digital signal processing, digital image processing and artificial neural networks. A new technique, named unidirectional CORDIC, for efficient computation of trigonometric and hyperbolic functions is presented in this thesis. In the conventional CORDIC algorithm, the vector rotations are performed in both clockwise and counterclockwise directions, but in the unidirectional CORDIC the vectors are rotated only …

Automatic Speaker Identification Using Reusable And Retrainable Binary-Pair Partitioned Neural Networks, Ashutosh Mishra

Electrical & Computer Engineering Theses & Dissertations

This thesis presents an extension of the work previously done on speaker identification using Binary Pair Partitioned (BPP) neural networks. In the previous work, a separate network was used for each pair of speakers in the speaker population. Although the basic BPP approach did perform well and had a simple underlying algorithm, it had the obvious disadvantage of requiring an extremely large number of networks for speaker identification with large speaker populations. It also requires training of networks proportional to the square of the number of speakers under consideration, leading to a very large number of networks to be trained …

Interpolation Techniques For Overset Grids, Paul S. Sherman, Nathan B. Edgar

Journal of the Arkansas Academy of Science

The use of finite difference schemes in computational aeroacoustics requires the use of structured grids incomputational space. Complex geometries in the physical space can be modeled using multiple overlapping grids that are transformed into computational space. In this work, finite difference schemes are used that necessitate the addition of psuedo- or ghost-points in the overlap region of the grids for closure of the difference stencil. The functional values at these ghost points must be approximated from the values at the original grid points. This paper investigates interpolation techniques for these overset grids. An n th order interpolation scheme using Lagrange …

Minimum Mean Square Error Spectral Peak Envelope Estimation For Automatic Vowel Classification, Jaishree Venugopal

Electrical & Computer Engineering Theses & Dissertations

Spectral feature computations continue to be a very difficult problem for accurate machine recognition of speech. In this work, which focuses on vowels, a new spectral peak envelope method for vowel classification is developed, based on a missing frequency components model of speech recognition. According to the missing frequency components model, vowel recognition depends only on the spectral (harmonic) peaks. Smoothing and interpolation of the spectra, performed in the standard cepstral analysis method commonly used in automatic speech recognition, actually loses valuable information and results in reduced recognition accuracy. The new method for feature extraction presented in this thesis is …

Rekabentuk Cip Pemamtapatan Data, Ismail Shah Rizal

Student Works (2000-2009)

Dokumen ini telah disiapkan untuk membuat cadangan projek Timiah Tahun Akhir yang bertajuk Rekabentuk Perkakasan Cip Pemampatan Data. Babagian pertama adalah berkenaan pengenalan yang memberi gambaran tentang tujuan, objektif dan kepenringan projek juga keperluan perkakasan dan perisian dalarn proses pembanguoan. Bahagian kedua pula, tumpuan diberikan kepada pemampatan data iaitu jenis teknik, algoritma Huffman dan contoh penggunaan Huffman. Dalarn bahagian ketiga, pengenalan terhadap perisian yang akan digunakan iaitu perisian VHDL. Bahagian keempat dokumen menyentuh tentang pendekatan pembangunan modul rekabentuk dan rekabentuk akhir perkakasan yang akan dibangunkan. Juga turut dimasukkan ialab gambarajah status bertujuan untuk memudahkan pemahaman. Dalam bahagian lima pula, implementasi …

Investigation Of Image Feature Extraction By A Genetic Algorithm, Steven P. Brumby, James P. Theiler, Simon J. Perkins, Neal R. Harvey, John J. Szymanski, Jeffrey J. Bloch, Melanie Mitchell

Computer Science Faculty Publications and Presentations

We describe the implementation and performance of a genetic algorithm which generates image feature extraction algorithms for remote sensing applications. We describe our basis set of primitive image operators and present our chromosomal representation of a complete algorithm. Our initial application has been geospatial feature extraction using publicly available multi-spectral aerial-photography data sets. We present the preliminary results of our analysis of the efficiency of the classic genetic operations of crossover and mutation for our application, and discuss our choice of evolutionary control parameters. We exhibit some of our evolved algorithms, and discuss possible avenues for future progress.

Two Approaches To Critical Path Scheduling For A Heterogeneous Environment, Guangxia Liu

Computer Science Theses & Dissertations

Advances in computing and networking technologies are making large scale distributed heterogeneous computing a reality. Multi-Disciplinary Optimization (MDO) is a class of applications that is being addressed under this paradigm. It consists of multiple heterogeneous modules interacting with each other to solve an overall design problem. An efficient implementation of such an application requires scheduling heterogeneous modules (with different computing and disk 1/0 requirements) on a heterogeneous set of resources (with different CPU, memory, disk IO specifications).

Given a set of tasks and a set of resources, an optimal schedule of the tasks on the resources is very hard to …

Variability Analysis Of Discrete Cosine Transform Coefficient (Dctc) Features For Speech Processing, Bingjun Dai

Electrical & Computer Engineering Theses & Dissertations

In this research, the variability of Discrete Cosine Transform Coefficient (DCTC) features was investigated. Additionally, a new pitch-synchronous processing method was explored to increase the stability of features and to reduce window effects when compared to the regular method. The noise sources that lead to feature variability were analyzed, and different smoothing methods were tested. It was found that longer frames, frequency warping, time smoothing of the log spectrum, and DCS level time smoothing, all help reduce DCTC variability and increase classification performance. The pitch­ synchronous method was implemented with Matlab. Important processing methods, including pitch period estimation, time­ domain …

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.

Dynamic Load Distribution In Mist, K. Al-Saqabi, R. M. Prouty, Dylan Mcnamee, Steve Otto, Jonathan Walpole

Computer Science Faculty Publications and Presentations

This paper presents an algorithm for scheduling parallel applications in large-scale, multiuser, heterogeneous distributed systems. The approach is primarily targeted at systems that harvest idle cycles in general-purpose workstation networks, but is also applicable to clustered computer systems and massively parallel processors. The algorithm handles unequal processor capacities, multiple architecture types and dynamic variations in the number of processes and available processors. Scheduling decisions are driven by the desire to minimize turnaround time while maintaining fairness among competing applications. For efficiency, the virtual processors (VPs) of each application are gang scheduled on some subset of the available physical processors.

Specification And Verification Of Generic Cell Rate Algorithms In Pvs, Huseyin Ozgungor

Electrical & Computer Engineering Theses & Dissertations

Formal verification methods have been considered as a powerful complementary approach to define standards and to prove correctness of the systems. In this work, formal specification of Generic Cell Rate Algorithms are defined and proved. The specification process enables standardization for constructing Generic Cell Rate Algorithms. Standardization is an important process in the Asynchronous Transfer Mode (ATM) networks. By employing formal methods, the necessary standards could be constructed to allow different algorithms to be employed which still meet system requirements. Those system requirements are quantified in the Quality of Service (QOS).

Congestion management is a vital concept for networks in …

Single Row Routing: Theoretical And Experimental Performance Evaluation, And New Heuristic Development, David A. Hysom

Computer Science Theses & Dissertations

The Single Row Routing Problem (SRRP) is an abstraction arising from real-world multilayer routing concerns. While NP-Complete, development of efficient SRRP routing heuristics are of vital concern to VLSI design. Previously, researchers have introduced various heuristics for SRRP; however, a comprehensive examination of SRRP behavior has been lacking.

We are particularly concerned with the street-congestion minimization constraint, which is agreed to be the constraint of greatest interest to industry. Several theorems stating lower bounds on street congestion are known. We show that these bounds are not tight in general, and argue they may be in error by at least 50% …

Resource/Dataflow Graph Operating System Development, Sriram J. Coimbatore

Electrical & Computer Engineering Theses & Dissertations

Implementation of a new dataflow schedule model is the objective of this thesis. The dataflow model algorithm called the resource/dataflow graph model is implemented on a peer-to-peer communication network comprising of six personal computers. This dataflow model is implemented making use of an earlier dataflow model called ATAMM (Algorithm to Architecture Mapping Model) developed by ODU and National Aeronautics and Space Administration (NASA). Development issues include modification of the RDFG testbed operating system and a scheme to transfer data buffers using the ethernet channel from one processor to another processor. This, in turn, equips each sub-module of an application with …

Visual Speech Recognition Using Multiple Deformable Lip Models, Devi Chandramohan

Electrical & Computer Engineering Theses & Dissertations

Motivated by the fact that human speech perception is a bimodal process (auditory and visual), several researchers have designed and implemented automatic speech recognition (ASR) systems consisting of both audio and visual subsystems, and shown improved performance relative to traditional purely auditory systems. Several visual speech reading approaches have used deformable templates to model the shape of a speaker's lips. Deformable templates are models of image objects, which can be deformed by adjusting a set of parameters to match the object in some optimal way, as defined by a cost function. Using a single deformable lip model has disadvantages such …

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 …

Simulator For The Performance Analysis Of Cpm Schemes In An Indoor Wireless Environment, Ronald Chua

Theses : Honours

A software simulator for characterising Continuous Phase Modulation (CPM) schemes in an indoor multipath environment has been developed using SIMULINK and MATLAB. The simulator is capable of simulating a wide range of CPM schemes to determine bandwidth efficiency and robustness to additive white Gaussian noise (AWGN) and Rician fading. Initial trials of the simulator indicate that the simulator is functioning correctly. Eventually, the simulator will be used to determine the most suitable modulation scheme for the development of an actual indoor wireless system.

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 …