Digital Commons Network^™

Embedding Data Mappers With Distributed Memory Machine Compilers, Ravi Ponnusamy, Joel Saltz, Raja Das, Charles Koelbel, Alok Choudhary

Electrical Engineering and Computer Science - Technical Reports

In scalable multiprocessor systems, high performance demands that computational load be balanced evenly among processors and that interprocessor communication be limited as much as possible. Compilation techniques for achieving these goals have been explored extensively in recent years [3, 9, 11, 13, 17, 18]. This research has produced a variety of useful techniques, but most of it has assumed that the programmer specifies the distribution of large data structures among processor memories. A few projects have attempted to automatically derive data distributions for regular problems [12, 10, 8, 1]. In this paper, we study the more challenging problem of automatically …

A Probabilistic Analysis Of A Locality Maintaining Load Balancing Algorithm, Kishan Mehrotra, Sanjay Ranka, Jhy-Chun Wang

Electrical Engineering and Computer Science - Technical Reports

This paper presents a simple load balancing algorithm and its probabilistic analysis. Unlike most of the previous load balancing algorithms, this algorithm maintains locality. We show that the cost of this load balancing algorithm is small for practical situations and discuss some interesting applications for data remapping.

On Planar Routing Of Multi-Terminal Nets In Vlsi Physical Design, Jahangir A. Hashmi

Masters Theses

In this thesis, we study two problems related to the physical design of VLSI circuits. One problem is related to the VLSI global routing and the other is related to the detailed routing in a bounded region.

We consider the routing of multiple multi-terminal nets on a single layer. We suggest a new approach for this problem. Our approach is based on simultaneously finding a forest of k non-intersecting spanning trees. We present an O(n^3) algorithm for finding two spanning trees corresponding to two nets on a single layer.

We also study the problem of finding a minimum Steiner tree …

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 …

Feature Extraction And Classification Of Flir Imagery Using Relative Locations Of Non-Homogeneous Regions With Feedforward Neural Networks, Kevin L. Priddy

Theses and Dissertations

The classification of forward looking infrared (FLIR) imagery is explored using Gabor transform decomposition and relative locations of non- homogeneous regions combined with feedforward neural networks. A feature saliency metric is developed from a Bayesian sensitivity analysis of feedforward neural networks. This metric is then used to reduce the dimensionality of the feature vectors used to identify FLIR imagery without any degradation of classification accuracy. Several system architectures are developed using a roving window combined with a series of Gabor filters to produce feature vectors for presentation to a neural network classifier. One architecture uses the Gabor filter coefficients to …

Reasoning By Analogy In A Multi-Level System Architecture For The Design Of Mechanisms, Ghassan F. Issa

Computer Science Theses & Dissertations

Since the first attempts to integrate AI technology and engineering design nearly two decades ago, few expert systems have been shown to demonstrate sufficient reasoning capabilities to solve real-world design problems. The complex nature of design, the lack of understanding of the design process, and the limitations of current expert system technology have all been shown to have adverse effects on the maturity of this research area. Therefore, our direction in this research concentrates on understanding the design process, investigating a novel area of research focusing on creative design, and incorporating the results into a system model feasible for production …

A Survey Of Computer Use In Occupational Therapy Fieldwork Sites, Martha E. Parks

Masters Theses

Eighty-three Western Michigan University occupational therapy fieldwork sites were surveyed to determine: (a) extent of computer use, (b) diagnostic categories with which computers are used, (c) extent of computer knowledge of registered occupational therapists (OTRs), and (d) adequacy of computer knowledge of fieldwork students. Forty-seven (56.6%) of the 83 surveys were returned. OTRs at 36 (76.6%) of the 47 sites currently use computers. Word processing is the most common way in which these OTRs use computers. The most common clinical use of computers is perceptual/motor assessment and treatment, while the most common research use of computers is for report writing. …

Monitoring Computer Systems: An Intelligent Approach, Myron Zhihong Xu

Computer Science Theses & Dissertations

Monitoring modern computer systems is increasingly difficult due to their peculiar characteristics. To cope with this situation, the dissertation develops an approach to intelligent monitoring. The resulting model consists of three major designs: representing targets, controlling data collection, and autonomously refining monitoring performance. The model explores a more declarative object-oriented model by introducing virtual objects to dynamically compose abstract representations, while it treats conventional hard-wired hierarchies and predefined object classes as primitive structures. Taking the representational framework as a reasoning bed, the design for controlling mechanisms adopts default reasoning backed up with ordered constraints, so that the amount of data …

An Algorithm For Generating Executable Assertions For Fault Tolerance, Martina Schollmeyer, Hanan Lutfiyya, Bruce M. Mcmillin

Computer Science Technical Reports

This paper presents an algorithm for deriving executable assertions that can be evaluated in a faulty distributed environment. A transformation from the global auxiliary variable approach into a new proof system based on the history of the auxiliary variables is introduced. This transformation, which matches the operational distributed environment more closely than the global auxiliary variable system, is then shown to retain the properties of this system such as noninterference, satisfaction, soundness, and completeness. An example is presented in which a model problem is transformed from one system into the other.

The Interbase Parallel Language: Supporting The Flex Transaction Model And Beyond, Ahmed K. Elmagarmid, Jiansan Chen

Department of Computer Science Technical Reports

No abstract provided.

Fault-Tolerant Distributed Database Lock Managers Formally Derived From Program Verification, Hanan Lutfiyya, Martina Schollmeyer, Bruce M. Mcmillin

Computer Science Technical Reports

This paper presents a system for formally deriving executable assertions that can be evaluated in the faulty distributed computing environment. Since executable assertions for fault tolerance need to show that a program meets its specification and, since program verification is the process of formally showing that a program satisfies some particular properties with respect to its specification, we use program verification as a basis for derivation. It is well known that in the sequential computing environment the assertions from a program verification proof outline may be translated directly into executable assertions. However, due to the lack of global state information …

Integrated Symbolic-Numeric Computing In //Ellpack: Experiences And Plans, Sanjiva Weerawarana, Ann C. Catlin, Elias N. Houstis, John R. Rice

Department of Computer Science Technical Reports

No abstract provided.

Performance Analysis Of A Polyhedral Boolean Set Operations Algorithm, George Vanĕček, Dana S. Nau, Raghu R. Karinthi

Department of Computer Science Technical Reports

No abstract provided.

The Speedup And Efficiency Of 3-D Fft On Distributed Memory Mimd Systems, Dan C. Marinescu

Department of Computer Science Technical Reports

No abstract provided.

Ppmb: A Partial-Multiple-Bus Multiprocessor Architecture With Improved Cost-Effectiveness, Hong Jiang, Kenneth C. Smith

School of Computing: Faculty Publications

This paper addresses the design and performance analysis of partial-multiple-bus interconnection networks. They are bus architectures that have evolved from multiple-bus structure by dividing buses into groups and reducing bus connections. Their effect is to reduce cost and alleviate arbitration and drive requirements without degrading performance significantly. One such structure, called processor-oriented partial-multiple-bus (or PPMB), is proposed. It serves as an alternative to the conventional structure called memory-oriented partial-multiple-bus (or MPMB) and is aimed at higher system performance at less or equal system cost. It has been shown, both analytically and by simulation, that a substantial increase in system bandwidth …

Wright State University College Of Engineering And Computer Science Bits And Pcs Newsletter, Volume 8, Number 3, March 1992, College Of Engineering And Computer Science, Wright State University

BITs and PCs Newsletter

An eight page newsletter created by the Wright State University College of Engineering and Computer Science that addresses the current affairs of the college.

An Examination Of Hypercube Implementations Of Genetic Algorithms, Andrew Dymek

Theses and Dissertations

Genetic algorithms are stochastic search algorithms which model natural adaptive systems. In support of the development of a genetic search package for AFIT's iPSC/2 Hypercube, this study focused on two problem areas associated with hypercube implementations. Premature convergence occurs when the population becomes dominated by locally optimal, but globally inferior, solutions. Based on an examination of past hypercube implementations, the selection and communication strategies were hypothesized as causes of premature convergence. Experiments to test these hypotheses were conducted on Rosenbrock's saddle, a function often associated with premature convergence. Communication of best solutions led to premature convergence in small population sizes, …

Development Of A Flight Information System Using The Structured Method, Yeong-Lae Kwak

Theses and Dissertations

This thesis documents the development of a database system for the Flight Information System (FIS) of the Korean Air Force. The scope of the FIS is too large to be covered by this thesis. Thus, this thesis covers only the core part of the FIS due to the limitation of time and man-power. This thesis uses the structured method. Structured analysis and structured design techniques are mainly used two techniques. This thesis focused not only the development of the FIS but also the application of the software development method, the structured method, and its tools such as DFD, DD, ERD, …

Satool Ii: An IdefO Case Workbench Using Ada And The X Window System, Betty Topp

Theses and Dissertations

The objective of this research effort is to perform an object oriented analysis, design and implementation of the graphical user interface (GUI) for the SATool II system. SATool II is a computer Assisted Software Engineering (CASE) workbench developed using Ada and the X Window system. It is designed to serve as an IDEFo graphical project editor and data dictionary editor. IDEF₀ is the ICAM Definition Method Zero graphical notation language adopted by the Air Force to produce a function model of a manufacturing system or environment. The Air Force Institute of Technology is conducting on-going research in the use …

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 …

Causal Univariate Spatial-Temporal Autoregressive Moving Averages (Starma) Modelling Of Target Information To Generate Tasking Of A World-Wide Sensor System, Kelly A. Greene

Theses and Dissertations

The Department of Defense employs a resource limited world-wide sensor system to detect certain events of interest. The purpose of this research was to establish a methodology using a univariate causal STARMA model for forecasting the relative probability of an event occurring in a geographical location during a time block of the day. These relative probabilities are used as input for a tasking model that assigns the scarce sensor resources so as to optimize the detection of these events. The STARMA model is appropriate for forecasting the relative probabilities because a definite temporal relationship and a definite spatial relationship exists …

Boolean Reasoning And Informed Search In The Minimization Of Logic Circuits, James J. Kainec

Theses and Dissertations

The minimization of logic circuits has been an important area of research for more than a half century. The approaches taken in this field, however, have for the most part been ad hoc. Boolean techniques have been employed to manipulate formulas, but not to perform symbolic reasoning. Boolean equations are employed principally as icons; they are never solved. The first objective of this dissertation is to apply Boolean reasoning systematically and uniformly to the minimization problem. Boolean reasoning entails the reduction of systems of Boolean equations to a single equation; the single equation is an abstraction, independent of the form …

Hardware-Verification Through Logic Extraction, Michael A. Dukes

Theses and Dissertations

A Prolog-based system is described which employs logic-extraction to perform hardware-verification. The extraction rules are built automatically from hierarchical structural VHDL models, enabling the equivalence of a structural VHDL description and a layout specification to be verified. Pin-to-pin critical- path analysis is performed within the logic-extraction process; many noncritical paths are pruned early, making pin-to-pin critical path analysis of large circuits feasible. It is demonstrated that a design methodology based on logic extraction, VHDL, and a layout tool can provide a fabricated functionally- correct IC design without circuit-level or switch-level simulation. This methodology is shown to be practical for VLSI …

Reservable Transactions: An Approach For Reliable Multidatabase Transaction Management, Ahmed K. Elmagarmid, Jin Jing, James G. Mullen, Jamshid Sharif-Askary

Department of Computer Science Technical Reports

No abstract provided.

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 …

Software Forensics: Can We Track Code To Its Authors?, Eugene H. Spafford, Stephen A. Weeber

Department of Computer Science Technical Reports

No abstract provided.

Conceptual Background For Symbolic Computation, Klaus Berkling

Electrical Engineering and Computer Science - Technical Reports

This paper is a tutorial which examines the three major models of computation--the Turing Machine, Combinators, and Lambda Calculus--with respect to their usefulness to practical engineering of computing machines. While the classical von Neumann architecture can be deduced from the Turing Machine model, and Combinator machines have been built on an experimental basis, no serious attempts have been made to construct a Lambda Calculus machine. This paper gives a basic outline of how to incorporate a Lambda Calculus capability into a von Neumann type architecture, maintaining full backward compatibility and at the same time making optimal use of its advantages …

Wright State University College Of Engineering And Computer Science Bits And Pcs Newsletter, Volume 8, Number 2, February 1992, College Of Engineering And Computer Science, Wright State University

BITs and PCs Newsletter

An eight page newsletter created by the Wright State University College of Engineering and Computer Science that addresses the current affairs of the college.

Dynamic Machine Scheduling, Expansion, And Control Of A Generic Workcell, Peter A. Murray

Theses

Factory automation has come a long way since the invention of the automatic flour mill. A workcell is a group of machines (robots) working together to produce a product. In the past workcells have been hard wired using methods such as Programmable Logic Controllers (PLCs). To change a part of this system would require reprogramming the entire system.

The Generic Work Cell (GWC) is a dynamic architecture which allows a workcell to be modified on the fly. The architecture enables the generation of new cells with minimal effort, and the modification of the system without reprogramming the entire system. The …

Binary Image Decomposition And Compression Using Mathematical Morphology For Object Recognition, Venu Gopal Gogusetti

Theses

Image segmentation has been studied for several years. There are several segmentation techniques which are fast and effective but all of them are lacking the property of invariency to shift, rotation and sizing. In this study a new process is introduced which overcomes the shift, size and rotation variance and the compressed data can be used for object recognition.

Euclidean distance measurement is used in the compression process which is rotation invarient but is expensive in terms of time. Eucledean distance transformation is calculated using optimal double two scan algorithm with gray scale morphology, a new method developed by Dr. …