Digital Commons Network^™

Do Hypercubes Sort Faster Than Tree Machines?, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

We develop a balanced, parallel quicksort algorithm for a hypercube and compare it with a similar algorithm for a binary tree machine. The performance of the hypercube algorithm is measured on a Computing Surface.

Efficient Maximum-Likelihood Soft-Decision Decoding Of Linear Block Codes Using Algorithm A, Yunghsiang S. Han, Carlos R.P. Hartmann, Chih-Chieh Chen

Electrical Engineering and Computer Science - Technical Reports

In this report we present a novel and efficient maximum-likelihood soft-decision decoding algorithm for linear block codes. The approach used here is to convert the decoding problem into a search problem through a graph which is a trellis for an equivalent code of the transmitted code. Algorithm A*, which uses a priority-first search strategy, is employed to search through this graph. This search is guided by an evaluation function f defined to take advantage of the information provided by the received vector and the inherent properties of the transmitted code. This function f is used to drastically reduce the search …

Specifying Interdatabase Dependencies In A Multidatabase Environment, Marek Rusinkiewicz, Amit P. Sheth, George Karabatis

Kno.e.sis Publications

The problem of interdatabase dependencies and the effect they have on applications updating interdependent data are addressed. A model that allows specifications of constraints among multiple databases in a declarative fashion is proposed. The separation of the constraints from the application programs facilitates the maintenance of data constraints and allows flexibility in their implementation. It allows investigation of various mechanisms for enforcing the constraints, independently of the application programs. By grouping the constraints together, it is possible to check their completeness and discover possible contradictions among them. The concepts of polytransactions, which use interdatabase dependencies to generate a series of …

Design And Analysis Of Asynchronous Adders, Khalid Khanfar

Masters Theses

The aim of this study is to come up with a fast adder suitable for use in self-timed subsystems. 7 adders were evaluated.

The findings from this study indicated that a Conditional Sum Adder (CSA) is the best candidate for high speed addition. One of the two resulting adders was given the name High Speed Conditional Sum Adder (HSCSA) .

An Animated Graphical Postprocessor For The Saber Wargame, Gary W. Klabunde

Theses and Dissertations

One of the most cost effective ways to learn and home the skills necessary to conduct and win a war is through the use of realistic computer simulations of conflict, or wargames. The Saber wargame was developed for just this purpose. Saber is a multisided, theater-level simulation developed by the Air Force Institute of Technology for the Air Force Wargaming Center. It models conventional, nuclear, and chemical warfare between aggregated air and ground forces. To aid in the realism, the effects of logistics, satellites, weather, and intelligence are represented. Saber provides an avenue for senior level joint service officers to …

Establishing A Methodology For Evaluation And Selecting Computer Aided Software Engineering Tools For A Defined Software Engineering Environment At The Air Force Institute Of Technology School Of Engineering, Jody L. Mattingly

Theses and Dissertations

This thesis identifies the software engineering environment (SEE) as it exists at the Air Force Institute of Technology (AFIT) School of Engineering. It also describes the software process model employed and the software development methods presented as part of the curriculum. Based on this information, criteria was established to evaluate computer aided software engineering (CASE) tools being considered for integration into the SEE. Each criterion was weighted to indicate its importance when selecting CASE tools. The criteria were further used to establish a methodology to be used to evaluate and select the CASE tools under consideration as well as future …

A Hybrid Approach To Battlefield Parallel Discrete Event Simulation, Steven R. Soderholm

Theses and Dissertations

This thesis describes a method of parallelizing a battlefield discrete event simulation. The method combines elements of conservative time synchronization together with elements of optimistic computation and local rollback on a message passing hardware architecture. The battle simulation features aircraft moving in a battle area and launching missiles at enemy aircraft. Aircraft are randomly grouped into logical process (LPs), and a single LP is assigned to each processor. Aircraft state information is replicated across all LPs. Only the LP with the minimum next event time can execute safely. While one LP is executing safely all other LPs are precomputing their …

Formalization And Validation Of An Sadt Specification Through Executable Simulation In Vhdl, Daniel L. Eickmeier

Theses and Dissertations

Formalizing an informal requirements specification, such as SADT, and executing the formal specification in a simulation environment, such as VHDL, provides a requirements analyst a means to validate the behavior of a specification early in the development life cycle. This research effort investigated and demonstrated the feasibility and benefit of transforming an SADT specification of a system into an equivalent VHDL executable simulation. Both non-time related behavior and concurrent, real-time related behavior is addressed. First, a decision table extension to SADT is created so that detailed, executable behavior can be specified. Next a mapping from SADT to VHDL is defined. …

A Case Study In Software Reuse: The Rntds Architecture, Barry J. Stevens

Computer Science Theses & Dissertations

It has been asserted that the most significant gains in software productivity will come from increased levels of software reuse. Some economic models for predicting savings through software reuse exist, but none are based on actual project experience. This paper surveys those models and presents the results of a case study, the Restructured Naval Tactical Data Systems (RNTDS) architecture, in the light of those models. According to the models, software reuse via the RNTDS architecture has enabled the production of fourteen major computer programs at five to twenty-one percent of the cost to create them without software reuse. Organizational characteristics …

Object-Oriented Analysis And Design Of The Saber Wargame, Christine M. Sherry

Theses and Dissertations

This thesis presents an object-oriented analysis and design of Saber, a theater-level computerized wargame, for the Air Force Wargaming Center, Maxwell AFB, Alabama. The analysis and design is based on a recently developed conceptual model, and existing land battle, and additional research. This thesis also begins the implementation process. The design was accomplished using an iterative, five step design process. Objects and operations were chosen and then encapsulated in Ada packages. This thesis also makes necessary changes to the land battle as described by the conceptual model and as the result of additional research. Sound software engineering principles were used …

Structured Hypermedia Application Development Model (Shadm): A Structured Model For Technical Documentation Application Design, Peter W. Cassell

Theses and Dissertations

This research was conducted to determine how a Royal Australian Air Force technical maintenance publication could be transformed into a task oriented hypermedia application and to develop a model that could be used for future similar transformations. The model was developed following in-depth analysis of the existing USAF F-15E maintenance publication set and validation was conducted using a prototype developed in HyperWriter, a commercial hypermedia product. The prototype model was based around the performance of three maintenance tasks on an aircraft sub-subsystem and incorporated online user access to the necessary support data for task completion. Publication managers, producers, and users …

Possible Application Of Quality Function Deployment In Software Systems Development In The United States Air Force, Craig R. Lamb

Theses and Dissertations

The objectives of the thesis were to determine whether the methods of Quality Function Deployment (QFD) could be used in the software development environment within the USAF, and whether or not this area should be researched further. The research was limited to the requirements analysis and definition phase. The different areas of study included a brief review of the structured analysis methodology, a detailed review of the QFD models currently being used in the product industries, a review of how QFD fits into the software development cycle, and specific software modifications to the QFD methodology. A review of some applications …

Investigative Search Of Quality Historical Software Support Cost Data And Software Support Cost-Related Data, Brent L. Barber

Theses and Dissertations

The purpose of the study was to determine what software support cost data and software support cost-related data should and can be collected by the Air Force. In addition, the study was to determine how the subject data should be collected. The collection of this data is necessary in order to measure the accuracy and calibration requirements of the software support cost models used by the Air Force. The study found there was no standard set of data items, and no standard procedures in place for the collection of this data. In most cases data were available or easily accessible, …

An Expert System Advisor For Medical Evaluation Boards, Jerry S. G. Harrington

Theses and Dissertations

Expert system technology has proven itself to be able to improve productivity and decision making in a variety of fields of endeavor. The purpose of this study was to determine if an expert system for medical evaluation boards (MEBs) could improve upon the processing of medical evaluation board cases. Research was conducted to develop an expert system and measure the capabilities of the system, both in terms of accuracy and timeliness of case completion of the medical evaluation administrators/clerks who were assisted by the system. The research methodology involved a three - phase approach. The objective of phase one was …

Parallel Implementation Of Vhdl Simulations On The Intel Ipsc/2 Hypercube, Ronald C. Comeau

Theses and Dissertations

VHDL models are executed sequentially in current commercial simulators. As chip designs grow larger and more complex, simulations must run faster. One approach to increasing simulation speed is through parallel processors. This research transforms the behavioral and structural models created by Intermetrics' sequential VHDL simulator into models for parallel execution. The models are simulated on an Intel iPSC/2 hypercube with synchronization of the nodes being achieved by utilizing the Chandy Misra paradigm for discrete-event simulations. Three eight-bit adders, the ripple carry, the carry save, and the carry-lookahead, are each run through the parallel simulator. Simulation time is cut in at …

Analysis Of A Decision Support System For Case Tool Selection And The Specification Of An Ada To Sql Abstract Interface, Tina M. Deangelis

Theses and Dissertations

Information overload has long been a problem in the fast moving technical field of software development. Yet quality information is needed to make informed decisions about buying software tools that help in software development. Computer Aided Software Engineering (CASE) tools help to coordinate and control information in large software developments. Many CASE tool purchases, however, are being based on ad hoc tool evaluation and selection methods which depend on biased vendor information. To capture specific knowledge about how to pick a tool for a given software development effort, a historical database that identifies important tool characteristics needed to be maintained …

An Event Driven State Based Interface For Synthetic Environments, Mark J. Gerken

Theses and Dissertations

Previous research at the Air Force Institute of Technology (AFIT) has produced synthetic environments using head mounted displays (HMDs) and hand measurement devices. This thesis is a continuation of AFIT synthetic environment research. Hand measurement data from a VPL DataGlove is combined with hand orientation and translational data to define a set of valid gestures. These gestures form the basis of an input language for class of finite automata known as finite state machines. Using the input symbols from this language, the user may define a finite state machine which associates a stream of input symbols with one or more …

Design And Implementation Of A Graphical User Interface And Database Management System For The Saber Wargame, Andrew M. Horton

Theses and Dissertations

Saber is a theater level, multi-sided, airpower employment computerized wargame that can be programmed to simulate any combat scenario. The model simulates theater level combat between air and land forces, and takes into account the effects of logistics, resupply, and both theater nuclear and chemical warfare. The major objective of the Saber model is to provide a suitable educational platform to allow users to apply basic, tactical employment concepts to multiple combat units, each having a specialized mission, and incorporating every branch of the armed services. This thesis documents a graphical user interface and data management system that has been …

Enhanced Animation Of Parallel Algorithms, Michael D. Lack

Theses and Dissertations

Algorithm animation is a visualization method used to enhance understanding of the functioning of an algorithm or program. Visualization is used for many purposes, including education, algorithm research, performance analysis, and program debugging. This research, which follows from previous work, examines algorithm animation requirements for the various visualization purposes and extends the capabilities of an existing facilities, the AFIT algorithm Animation Research Facility (AAARF). The structure of AAARF is summarised and its visualization capabilities presented, analysed and compared with other similar packages. This research focuses on the parallel data requirements of the AAARF users, and the meaningful display of large …

Graph-Based Visualization Of Formal Specification And Domain Specific Languages, Randel K. Langloss

Theses and Dissertations

This research develops and implements Visual Refine, a graph-based visualization system, for the Refine wide-spectrum formal specification language and environment developed and marketed by Reasoning Systems, Inc. Refine specifications are represented in the Refine object base as abstract syntax trees (AST). Using these AST representations, one-to-one mappings are defined between nodes of the AST and the graphical icons of Visual Refine. Visual Refine uses these mappings to implement a set of formal transformations. Each transformation is encapsulated within a Refine rule, and this set of rules form the Visual Refine transformation system. The Visual Refine transformation system, in conjunction with …

Improved Task Scheduling For Parallel Simulations, Andrew E. Mcnear

Theses and Dissertations

The objective of this investigation is to design, analyze, and validate the generation of optimal schedules for simulation systems. Improved performance in simulation execution times can greatly improve the return rate of information provided by such simulations resulting in reduced development costs of future computer/electronic systems. Optimal schedule generation of precedence-constrained task systems including iterative feedback systems such as VHDL or war gaming simulations for execution on a parallel computer is known to be N P-hard. Efficiently parallelizing such problems takes full advantage of present computer technology to achieve a significant reduction in the search times required. Unfortunately, the extreme …

A Spatially Partitioned Parallel Simulation Of Colliding Objects, Robert S. Moser

Theses and Dissertations

This study investigated the application of a conservative synchronization paradigm to the classical, distributed pool balls simulation executed on an eight node, Intel iPSC/2 hypercube. Wieland's concept of spatial partitioning and limited data replication was used. Analysis has shown that 100% parallelization of execution is possible in a conservative environment via assignment of multiple sectors to nodes. Two conservative formulations for minimum safe time were derived. A tradeoff exists between scalability and efficiency. Optimum sectoring prediction has been shown possible through application of linear regression techniques. The results of this research reveal that a conservative approach to distributed, discrete event …

Three-Dimensional Medical Image Registration Using A Patient Space Correlation Technique, Patrick J. Rizzuto Jr.

Theses and Dissertations

The routine clinical use of three-dimensional data provided by modern medical imaging procedures is often impeded by the difficulty in accurately correlating the resultant volume datasets. These data are frequently obtained at different times using the same modality, or images of the same patient are sometimes produced using more than one imaging modality. In order to analyze the similarities and differences between such images, it is necessary for the medical imaging data to be spatially aligned using a process known as image registration. This research investigated a structure-based image registration technique based upon simple, three-dimensional relationships among user identified landmarks. …

Effect Of Spatial Locality Prefetching On Structural Locality, Dirk D. Schalch

Theses and Dissertations

The purpose of this research was to analyze the effect that spatial locality prefetching in cache memory has on the structural locality of program memory referencing behavior. To examine this, a software simulator was built to model a proposed two-level cache memory subsystem. The proposed subsystem was designed to use spatial locality prefetching to exploit the structural locality contained in executing computer workloads. New memory referencing models were developed to incorporate the combined use of structural locality and spatial locality prefetching. From these models, equations were derived to predict the hit rates for both caches. Combined with the state transition …

An Application Of The Object-Oriented Paradigm To A Flight Simulator, Dennis J. Simpson

Theses and Dissertations

This thesis describes the object-oriented software development techniques that were used to analyze, design and implement a flight simulator. The objective of this thesis was to present a comprehensive object-oriented software development methodology and show how it was used in constructing an actual application. An extensive review of current object-oriented practices is presented along with the methods that were used to take the flight simulator from analysis to design and through to implementation. The description of the methodology concentrates upon the design and implementation phases of the object-oriented software lifecycle. Examples from the design of the flight simulator demonstrate how …

A Cache Design To Exploit Structural Locality, Curtis M. Winstead

Theses and Dissertations

A design and VHDL implementation of a content-addressable memory (CAM) to exploit structural locality is the subject of this research. The concept of structural locality is that memory locations are referenced in the same order as they were previously referenced. Therefore, if memory locations that exhibit structural locality can be made available to the CPU (Center Processing Unit) through a fast data store, an increase in speed of the computer system can be realized. The CAM's purpose is to store memory references in the order they were used by the CPU and prefetch these locations to a smaller on- chip …

Parallelizing Serial Code For A Distributed Processing Environment With An Application To High Frequency Electromagnetic Scattering, Paul R. Work

Theses and Dissertations

This thesis investigates the parallelization of existing serial programs in computational electromagnetics for use in a parallel environment. Existing Algorithms for calculating the radar cross section of a object are covered, and a ray-tracing code is chosen for implementation on a parallel machine. Current parallel architectures are introduced and a suitable parallel machine is selected for the implementation of the chosen ray tracing algorithm. The standard techniques for the parallelization of serial code are discussed, including load balancing and decomposition considerations, and appropriate methods for the parallelization effort are selected. A load balancing algorithm is modified to increase the efficiency …

Face Recognition With The Karhunen-Loeve Transform, Pedro F. Suarez

Theses and Dissertations

The major goal of this research was to investigate machine recognition of faces. The approach taken to achieve this goal was to investigate the use of Karhunen-Loe've Transform (KLT) by implementing flexible and practical code. The KLT utilizes the eigenvectors of the covariance matrix as a basis set. Faces were projected onto the eigenvectors, called eigenfaces, and the resulting projection coefficients were used as features. Face recognition accuracies for the KLT coefficients were superior to Fourier based techniques. Additionally, this thesis demonstrated the image compression and reconstruction capabilities of the KLT. This theses also developed the use of the KLT …

Reducing Requirements Errors Through The Use Of Computer-Aided Software Engineering (Case) Tools And During Requirements Analysis, Marvin B. Key Jr.

Theses and Dissertations

This study investigated whether using CASE tools in the requirements analysis phase of software development reduced the software coding errors attributable to requirement analysis. A survey of the population gathered data as to the current practices and efforts in the use of CASE tools. The data was gathered in two groups: a control group and a sample group. The data was analyzed by group and in various combinations to obtain a greater understanding into population trends and tendencies. The results of the research indicate that the Air Force does not use CASE tools to any great extent. Also, error and …

A Formal Definition Of The Object-Oriented Paradigm For Requirements Analysis, Andrew D. Boyd

Theses and Dissertations

This paper develops a formal definition of the Object-Oriented paradigm for requirements analysis. The literature was surveyed for both formal and informal methods for conducting an Object-Oriented Requirements Analysis (OORA). The informal methods reviewed are: Bailin's, Shlaer and Mellor's, Booch's, and Coad and Yourdon's. The formal methods reviewed are: Bralick's, Z, and REFINE. None of the methods were found to be adequate for doing an OORA. A formal definition of an OORA, based on the concept of classes, is developed. The definition itself is presented as set and relation theory. A supporting graphical representation is also developed and presented. The …