Digital Commons Network^™

An Analysis Of The Root Causes Of Delays And Deficiencies In The Development Of Embedded Software For Air Force Weapon Systems, Jay R. Hopkins, Curtis De Keyrel

Theses and Dissertations

The importance of embedded software, used in every subsystem of ah major weapon systems used by the United States Air Force, has increased drastically over the last decades. However, in spite of the regulations currently in existence, developing and acquiring software which meets the user requirements within the original cost and schedule estimates continues to be difficult. At the same time, the Air Force has pushed to improve the development process with the Total Quality Management TQM program. The primary method used to improve the process has been to create metrics, collect data on these metrics, and then perform a …

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 …

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 …

A Probabilistic Approach To Fault Diagnosis In Linear Lightwave Networks, Robert H. Deng, A. A. Lazar, W. Wang

Research Collection School Of Computing and Information Systems

The application of probabilistic reasoning to fault diagnosis in linear lightwave networks (LLNs) is investigated. The LLN inference model is represented by a Bayesian network (or causal network). An inference algorithm is proposed that is capable of conducting fault diagnosis (inference) with incomplete evidence and on an interactive basis. Two belief updating algorithms are presented which are used by the inference algorithm for performing fault diagnosis. The first belief updating algorithm is a simplified version of the one proposed by Pearl (1988) for singly connected inference models. The second belief updating algorithm applies to multiply connected inference models and is …

User-Database Interface: The Effect Of Abstraction Levels On Query Performance, Hock Chuan Chan, Kwok Kee Wei, Keng Siau

Research Collection School Of Computing and Information Systems

A common classification of data models is based on their abstraction levels: physical, logical and conceptual. The user-database interaction can be similarly classified. For the conceptual-level interaction, the user and the database exchange information on the user's world, e.g., information of entities, relationships, and attributes. For the logical-level interaction, the user and the database communicate based on concepts in the database system, e.g., relations and join operations. We expect users to be familiar with concepts in their world but not the concepts in the database system. This is especially so for infrequent or naive database users. The conceptual level should …

Towards A General Distributed Platform For Learning And Generalization, Brent W. Hughes, Tony R. Martinez

Faculty Publications

Different learning models employ different styles of generalization on novel inputs. This paper proposes the need for multiple styles of generalization to support a broad application base. The Priority ASOCS model (Priority Adaptive Self-organizing Concurrent System) is overviewed and presented as a potential platform which can support multiple generalization styles. PASOCS is an adaptive network composed of many simple computing elements operating asynchronously and in parallel. The PASOCS can operate in either a data processing mode or a learning mode. During data processing mode, the system acts as a parallel hardware circuit. During leaming mode, the PASOCS incorporates rules, with …

The Importance Of Using Multiple Styles Of Generalization, Tony R. Martinez, D. Randall Wilson

Faculty Publications

There are many ways for a learning system to generalize from training set data. There is likely no one style of generalization which will solve all problems better than any other style, for different styles will work better on some applications than others. This paper presents several styles of generalization and uses them to suggest that a collection of such styles can provide more accurate generalization than any one style by itself. Empirical results of generalizing on several real-world applications are given, and comparisons are made on the generalization accuracy of each style of generalization. The empirical results support the …

Genetic Algorithms For Soft Decision Decoding Of Linear Block Codes, Harpal Maini, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka

Electrical Engineering and Computer Science - Technical Reports

Soft-decision decoding is an NP-hard problem of great interest to developers of communication systems. We show that this problem is equivalent to the problem of optimizing Walsh polynomials. We present genetic algorithms for soft-decision decoding of binary linear block codes and compare the performance with various other decoding algorithms. Simulation results show that our algorithms achieve bit-error-probabilities as low as 0.00183 for a [104, 52] code with a low signal-to-noise ratio of 2.5 dB, exploring only 30,000 codewords, whereas the search space contains 4.5 x 1015 codewords. We define a new crossover operator that exploits domain-specific information and compare it …

Wright State University College Of Engineering And Computer Science Bits And Pcs Newsletter, Volume 9, Number 9, November 1993, College Of Engineering And Computer Science, Wright State University

BITs and PCs Newsletter

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

A Computerized Instructional System For Mechanical Motion Of Objects, Jian J. Zhang

Electronic Dissertations and Theses

No abstract provided.

Object-Oriented Design And Implementation Of A Parallel Ada Simulation System, James T. Belford

Theses and Dissertations

Simulations which model the behavior real world entities are often large and complex, and require frequent changes to the configuration. This research effort examines the benefits of using object-oriented techniques to develop a distributed simulation environment which supports modularity, modifiability, and portability. The components of the Parallel Discrete Event Simulation PDES environment are identified and modeled using the Rumbaugh modeling technique. From the model, a prototype implementation of a Parallel Ada Simulation Environment PASE is accomplished using Classic Ada. A system interface for the Intel ipsc2 Hypercube was developed to illustrate the concepts of modularity and portability. In addition, the …

On-Line And Dynamic Shortest Paths Through Graph Decompositions, Hristo N. Djidjev, Grammati E. Pantziou, Christos D. Zaroliagis

Computer Science Technical Reports

We describe algorithms for finding shortest paths and distances in a planar digraph which exploit the particular topology of the input graph. An important feature of our algorithms is that they can work in a dynamic environment, where the cost of any edge can be changed or the edge can be deleted. For outerplanar digraphs, for instance, the data structures can be updated after any such change in only $O(\log n)$ time, where $n$ is the number of vertices of the digraph. We also describe the first parallel algorithms for solving the dynamic version of the shortest path problem. Our …

Parallel Max Cut Approximations, Grammati E. Pantziou, Paul G. Spirakis, Christos D. Zaroliagis

Computer Science Technical Reports

Given a graph with positive integer edge weights one may ask whether there exists an edge cut whose weight is bigger than a given number. This problem is NP-complete. We present here an approximation algorithm in NC which provides tight upper bounds to the proportion of edge cuts whose size is bigger than a given number. Our technique is based on the methods to convert randomized parallel algorithms into deterministic ones introduced by Karp and Wigderson. The basic idea of those methods is to replace an exponentially large sample space by one of polynomial size. In this work, we prove …

Asynchronous Parallel Schemes: A Survey, Eric Jui-Lin Lu, Michael Gene Hilgers, Bruce M. Mcmillin

Computer Science Technical Reports

It is well known that synchronization and communication delays are the major sources of performance degradation of synchronous parallel algorithms. It has been shown that asynchronous implementations have the potential to reduce the overhead to minimum. This paper surveys the existing asynchronous schemes and the sufficient conditions for the convergence of the surveyed schemes. Some comparisons among these schemes are also presented.

Multiple Query Optimization With Depth-First Branch-And-Bound, Ahmet Cosar, Ee Peng Lim, Jaideep Srivastava

Research Collection School Of Computing and Information Systems

In certain database applications such as deductive databases, batch query processing, and recursive query processing etc., a single query can be transformed into a set ofclosely related database queries. Great benefits can be obtained by executing a group of related queries all together in a single unijied multi-plan instead of executing each query separately. In order to achieve this, Multiple Query Optimization (MQO) identifies common task(s) (e.g. common subezpressions, joins, etc.) among a set of query plans and creates a single unified plan (multiplan) which can be executed to obtain the required outputs forall queries at once. In this paper, …

Query Optimization And Processing In Federated Database Systems, Ee Peng Lim, Jaideep Srivastava

Research Collection School Of Computing and Information Systems

No abstract provided.

Ensuring Relaxed Atomicity For Flexible Transactions In Multidatabase Systems, Aidong Zhang, Marian H. Nodine, Omran Bukhres

Department of Computer Science Technical Reports

No abstract provided.

Curve Fitting With Cubic A-Splines, Chandrajit L. Bajaj, Guoliang Xu

Department of Computer Science Technical Reports

No abstract provided.

Project Isaac: Building Simulations For Virtual Environments, George Vanĕček, James Cremer

Department of Computer Science Technical Reports

No abstract provided.

Dealing With Mobility: Issues And Research Challenges, Evaggelia Pitoura, Bharat Bhargava

Department of Computer Science Technical Reports

No abstract provided.

The Design And Implementation Of Tripwire: A File System Integrity Checker, Gene H. Kim, Eugene H. Spafford

Department of Computer Science Technical Reports

No abstract provided.

An Adaptive Coding Scheme With Code Combining For Mobile Radio Systems, Robert H. Deng, Huafei Zhou

Research Collection School Of Computing and Information Systems

The authors propose and study an adaptive error-control coding scheme for binary digital FM (BFM) mobile radio transmission. The scheme employs code combining through packet retransmissions. The number of transmissions of a packet is in proportion to the channel fading/noise levels, which is in contrast to time diversity techniques where a fixed number of repetitions of a data packet is performed even in the absence of channel errors. Furthermore, the receiver uses received signal envelopes as channel state information, which significantly improves the throughput and bit error rate (BER) performance. Performance of the proposed scheme is analyzed for frequency-flat Rayleigh …

Methodology For Modeling High Performance Distributed And Parallel Systems, Rakesh Kushwaha

Dissertations

Performance modeling of distributed and parallel systems is of considerable importance to the high performance computing community. To achieve high performance, proper task or process assignment and data or file allocation among processing sites is essential. This dissertation describes an elegant approach to model distributed and parallel systems, which combines the optimal static solutions for data allocation with dynamic policies for task assignment. A performance-efficient system model is developed using analytical tools and techniques.

The system model is accomplished in three steps. First, the basic client-server model which allows only data transfer is evaluated. A prediction and evaluation method is …

A Comprehensive Part Model And Graphical Schema Representation For Object-Oriented Databases, Michael H. Halper

Dissertations

Part-whole modeling plays an important role in the development of database schemata in data-intensive application domains such as manufacturing, design, computer graphics. text document processing, and so on. Object-oriented databases (OODBs) have been targeted for use in such areas. Thus, it is essential that OODBs incorporate a part relationship as one of their modeling primitives. In this dissertation, we present a comprehensive OODB part model which expands the boundaries of OODB part-whole modeling along three fronts. First, it identifies and codifies new semantics for the OODB part relationship. Second, it provides two novel realizations for part relationships and their associated …

Morphological Operations In Image Processing And Analysis, Chamim Christopher Pu

Dissertations

Morphological operations applied in image processing and analysis are becoming increasingly important in today's technology. Morphological operations which are based on set theory, can extract object features by suitable shape (structuring elements). Morphological filters are combinations of morphological operations that transform an image into a quantitative description of its geometrical structure which based on structuring elements. Important applications of morphological operations are shape description, shape recognition, nonlinear filtering, industrial parts inspection, and medical image processing.

In this dissertation, basic morphological operations are reviewed, algorithms and theorems are presented for solving problems in distance transformation, skeletonization, recognition, and nonlinear filtering. A …

Medium Access Control Mechanisms For High Speed Metropolitan Area Networks, Michail Papamichail

Dissertations

In this dissertation novel Medium Access Control mechanisms for High Speed Metropolitan Area networks are proposed and their performance is investigated under the presence of single and multiple priority classes of traffic. The proposed mechanisms are based on the Distributed Queue Dual Bus network, which has been adopted by the IEEE standardization committee as the 802.6 standard for Metropolitan Area Networks, and address most of its performance limitations. First, the Rotating Slot Generator scheme is introduced which uses the looped bus architecture that has been proposed for the 802.6 network. According to this scheme the responsibility for generating slots moves …

Characterization Of Three-Dimensional Shear Flows, Kurra Bhaswan

Theses

This work investigates techniques to analyze and characterize the presence of microstructure in moderately dilute three-dimensional shear flows. In three dimensional shear flows, a distinct structure develops as the coefficient of restitution is lowered with the particles exhibiting a strong tendency towards the formation of clusters. There exists a need to automatically detect and characterize this microstructure in the given flow. Several methods are examined for effective characterization of the microstructure. The techniques employed are based on the classification of the data based on the properties of the Voronoi diagram constructed from the positional parameters of the two-dimensional slices of …

Using Temporal Subsumption For Developing Efficient Error-Detecting Distributed Algorithms, Martina Schollmeyer, Bruce M. Mcmillin

Computer Science Technical Reports

Distributed algorithms can use executable assertions derived from program verification to detect errors at run-time. However, a complete verification proof outline contains a large number of assertions, and embedding all of them into the program to be checked at run-time would make error-detection very inefficient.

The technique of temporal subsumption examines the dependencies between the individual assertions along program execution paths. In contrast to classical subsumption, where all logical expressions to be examined are true simultaneously, an assertion need only be true when the corresponding statement in the distributed program has been executed. Thus, temporal subsumption based on the set …

A Run-Time Decision Procedure For Responsive Computing Systems, Grace Tsai, Matt Insall, Bruce M. Mcmillin

Computer Science Technical Reports

A responsive computing system is a hybrid of real-time, distributed and fault-tolerant systems. In such a system, severe consequences will occur if the logical and physical specifications of the system are not met. In this paper, we present a logic, Interval Temporal Logic (ITL), to specify responsive systems and give decision procedures to verify properties of the system at run-time as follows. First, we collect, during execution, events occurring in the system to represent a distributed computation. Next, we specify properties of the system using ITL formulas. Finally, we apply the decision procedures to determine satisfaction of the formulas. Thus, …

Establishing A Distributed Processing And Distributed Database Environment For Intergraph Mge & Orscle Products, Praveen Chandrasekhar

Electronic Dissertations and Theses

The department of Agricultural Economics undertake various government contracts for GIS based applications. Currently, they have multi-year contracts with the Louisiana Department of Health and Hospitals (LDHH). This contract is carried out in the Agricultural Economics Geographical Information System lab (AEGIS). One part of the contract is to integrate a heterogenous system comprising of PCs and Intergraph workstations so that the PC can share the data or Microstation Geographical information system Environment (MGE) and ORACLE based applications. Since the Department also undertakes other contracts which requires them to use ARC/INFOR as the front-end while the data would reside in ORACLE …