Digital Commons Network^™

Finding Connected Components On A Scan Line Array Processor, Ronald I. Greenberg

Computer Science: Faculty Publications and Other Works

This paper provides a new approach to labeling the connected components of an n x n image on a scan line array processor (comprised of n processing elements). Variations of this approach yield an algorithm guaranteed to complete in o(n lg n) time as well as algorithms likely to approach O(n) time for all or most images. The best previous solutions require using a more complicated architecture or require Omega(n lg n) time. We also show that on a restricted version of the architecture, any algorithm requires Omega(n lg n) time in the worst case.

Biometric Imaging: Three Dimensional Imaging Of The Human Hand Using Coded Structured Lighting, T. A. Vuori, C. L. Smith

Research outputs pre 2011

In this report the results of applying a three dimensional range imaging system, based on coded structured light, are presented. This includes a description of a new improved spatial coding scheme. This new scheme increases the number of reference points available and provides a basis for more accurate calculation of their location. A detailed description of the image processing methods used to extract structural information and to identify structural objects from the camera image are given. In addition the method used to calculate the locations of reference points with 'subpixel' accuracy is described. Finally, the results of experiments with synthesised …

Formal Specification Of A Dynamically Configurable Distributed System, Ram Sethuraman, Kenneth J. Goldman

All Computer Science and Engineering Research

The Programmers' Playground is a programming environment that supports end-user construction of distributed multimedia applications. The system implements a new programming model that is based, in part, upon ideas from the formal I/O automaton model of Lynch and Tuttle. Important features of The Programmers' Playground are a separation of communication and computation and graphical support for dynamic reconfiguration. This paper provides a formal specification of the Playground programming model and runtime system in terms of the I/O automaton model on which it is based. Exploiting the compositionality properties of the I/O automaton model, the formal specification is describd as a …

Using Multiple Statistical Prototypes To Classify Continuously Valued Data, Tony R. Martinez, Dan A. Ventura

Faculty Publications

Multiple Statistical Prototypes (MSP) is a modification of a standard minimum distance classification scheme that generates muItiple prototypes per class using a modified greedy heuristic. Empirical comparison of MSP with other well-known learning algorithms shows MSP to be a robust algorithm that uses a very simple premise to produce good generalization and achieve parsimonious hypothesis representation.

An Efficient Multicomputer Algorithm For The Solution Of Chemical Process Flowsheeting Equations, Fikret Ercal, Neil L. Book, S. Pait, J. J. Fielding

Computer Science Faculty Research & Creative Works

This paper presents a parallel solution method of large sparse systems of linear equations arising in the context of a chemical process flowsheeting application on a message passing multicomputer. To maximize the performance, the algorithm uses a novel matrix decomposition and solution method, called parallel two-phased LU decomposition, which schedules the concurrent tasks in a maximally overlapping manner, and at the same time, tries to minimize the interprocessor data dependencies and obtain optimal load balancing. The forward elimination step is performed concurrently with the parallel two-phased LU decomposition step and backward substitution is parallelized in a piecewise manner. Implementation results …

Using Fuzzy Set Theory: Exploring How Generalties Can Pinpoint Where To Look For The Answers, Cosmin Radu, Ralph W. Wilkerson

Computer Science Faculty Research & Creative Works

No abstract provided.

Object Interactions As First Class Objects: From Design To Implementation, Mahesh Dodani, Benjamin Kok Siew Gan, Lizette Velazquez

Research Collection School Of Computing and Information Systems

Collaborations between objects make up the dynamic behavior of OO software. These collaborations among objects require careful design and implementation. Treating the interactions as responsibilities that are integrated in the participating objects, results in tight coupling between objects. Tight coupling increases complexity and reduces reusability. Object interactions need to be first class objects from design to implementation. Our research provides a unified approach to model and implement these interactions as first class objects. During analysis and design, they are modeled using DynaSpecs. During implementation, they are coded with a new language construct called Compositions. DynaSpecs and Compositions provide a consistent …

Relaxing Synchronization In Distributed Simulated Annealing, Bruce M. Mcmillin, Chul-Eui Hong

Computer Science Faculty Research & Creative Works

This paper presents a cost error measurement scheme and relaxed synchronization method, for simulated annealing on a distributed memory multicomputer, which predicts the amount of cost error that an algorithm will tolerate. An adaptive error control method is developed and implemented on an Intel iPSC/2

Error Estimates And Lipschitz Constants For Best Approximation In Continuous Function Spaces, M. Bartelt, W. Li

Mathematics & Statistics Faculty Publications

We use a structural characterization of the metric projection PG(f), from the continuous function space to its one-dimensional subspace G, to derive a lower bound of the Hausdorff strong unicity constant (or weak sharp minimum constant) for PG and then show this lower bound can be attained. Then the exact value of Lipschitz constant for PG is computed. The process is a quantitative analysis based on the Gâteaux derivative of PG, a representation of local Lipschitz constants, the equivalence of local and global Lipschitz constants for lower semicontinuous mappings, and construction …

A Mathematical Model Of Cycle Chemotherapy, J. C. Panetta, J. Adam

Mathematics & Statistics Faculty Publications

A mathematical model is used to discuss the effects of cycle-specific chemotherapy. The model includes a constraint equation which describes the effects of the drugs on sensitive normal tissue such as bone marrow. This model investigates both pulsed and piecewise-continuous chemotherapeutic effects and calculates the parameter regions of acceptable dose and period. It also identifies the optimal period needed for maximal tumor reduction. Examples are included concerning the use of growth factors and how they can enhance the cell kill of the chemotherapeutic drugs.

Ensuring The Satisfaction Of A Temporal Specification At Run-Time, Grace Tsai, Matt Insall, Bruce M. Mcmillin

Mathematics and Statistics Faculty Research & Creative Works

A responsive computing system is a hybrid of real-time, distributed and fault-tolerant systems. In such a system, severe consequences can occur if the run-time behavior does not conform to the expected behavior or specifications. In this paper, we present a formal approach to ensure satisfaction of the specifications in the operational environment as follows. First we specify behavior of the systems using Interval Temporal Logic (ITL). Next we give algorithms for trace checking of programs in such systems. Finally, we present a fully distributed run-time evaluation system which causally orders the events of the system during its execution and checks …

A Linear-Time Recognition Algorithm For P4-Reducible Graphs, B. Jamison, S. Olariu

Computer Science Faculty Publications

The P₄-reducible graphs are a natural generalization of the well-known class of cographs, with applications to scheduling, computational semantics, and clustering. More precisely, the P₄-reducible graphs are exactly the graphs none of whose vertices belong to more than one chordless path with three edges. A remarkable property of P₄-reducible graphs is their unique tree representation up to isomorphism. In this paper we present a linear-time algorithm to recognize P₄-reducible graphs and to construct their corresponding tree representation.

Linear Time Optimization Algorithms For P4-Sparse Graphs, Beverly Jamison, Stephan Olariu

Computer Science Faculty Publications

Quite often, real-life applications suggest the study of graphs that feature some local density properties. In particular, graphs that are unlikely to have more than a few chordless paths of length three appear in a number of contexts. A graph G is P₄-sparse if no set of five vertices in G induces more than one chordless path of length three. P₄-sparse graphs generalize both the class of cographs and the class of P₄-reducible graphs. It has been shown that P₄-sparse graphs can be recognized in time linear in the size of the …

An Ada-Like Language To Facilitate Reliable Coding Of Low Cost Embedded Systems, Michael Collins

Theses : Honours

Due to a lack of operating system (0/S) support, it is more difficult to develop programs for embedded systems than for workstations. For those developing on a low budget, the problem is often further compounded by the necessity of using inappropriate, 0/S dependent, compilers. This study attempts to ascertain those elements of a High Level Language (HLL) which are absolutely necessary and implementable to produce reliable, efficient, embedded programs without the benefit of a large budget. The study is based upon the Ada philosophy as the Ada language incorporates many desirable features for modelling real-world problems in terms of embedded …

Implementation And Evaluation Of Enhanced Areal Interpolation Using Mapinfo And Mapbasic, Gordon Wragg

Theses : Honours

Many researchers today have a need to analyse data in a spatial context. An inherent problem is the mismatch of boundaries between the geographic regions for which data is collected and those regions for which the data is required. Often the solution is to interpolate data from one set of regions to another. This project examines and implements a method of areal interpolation that enables the user to use extra information in areal interpolation to increase the "intelligence ' of the process. This method of Enhanced Areal Interpolation uses a conditional Poisson distribution and the EM algorithm to provide estimated …

Transplanting Manufacturing Power: Observations From Five Years At Fujitsu, Steven M. Miller

Research Collection School Of Computing and Information Systems

Within a factory, what are the underpinnings of manufacturing power? During my thirty-month residency at Fujitsu's factory in Oyama, Japan, I constantly reflected on this question. The standard view of a factory structure provided by an organization chart was inadequate for summarizing my observations.

First Measurement Of The Quark-To-Photon Fragmentation Function, D. Buskulic, Manoj Thulasidas

Research Collection School Of Computing and Information Systems

Earlier measurements at LEP of isolated hard photons in hadronic Z decays, attributed to radiation from primary quark pairs, have been extended in the ALEPH experiment to include hard photon production inside hadron jets. Events are selected where all particles combine democratically to form hadron jets, one of which contains a photon with a fractional energy z 0:7. After statistical subtraction of non-prompt photons, the quark-to-photon fragmentation function, D(z), is extracted directly from the measured 2-jet rate. By taking into account the perturbative contributions to D(z) obtained from an O(S ) QCD calculation, the unknown non-perturbative component of D(z) is …

Scheduling Of Parallel Jobs On Dynamic, Heterogenous Networks, Dan Clark, Jeremy Casas, Steve Otto, Robert Prouty, Jonathan Walpole

Computer Science Faculty Publications and Presentations

In using a shared network of workstations for parallel processing, it is not only important to consider heterogeneity and differences in processing power between the workstations but also the dynamics of the system as a whole. In such a computing environment where the use of resources vary as other applications consume and release resources, intelligent scheduling of the parallel jobs onto the available resources is essential to maximize resource utilization. Despite this realization, however, there are few systems available that provide an infrastructure for the easy development and testing of these intelligent schedulers. In this paper, an infrastructure is presented …

A Proposal For A Development Platform For Microcontroller-Based Devices, Michael L. Wetton

Theses: Doctorates and Masters

This thesis is concerned with designing, implementing and testing a miniaturised temperature data logging device. Investigations demonstrated that a microcontroller could provide a low-cost single-chip solution to this problem and after a detailed review of 8-bit microcontrollers, the MC68HCll was chosen for this task. This document also includes discussion on an environment that was developed for creating and testing MC68HC11 software and the use of Motorola's evaluation boards. To ensure that the device was designed to software engineering standards an investigation into software engineering analysis techniques took place. This resulted in the Jackson Structured Programming (JSP) methodology being adapted to …

Optimizing Object Invocation Using Optimistic Incremental Specialization, Jon Inouye, Andrew P. Black, Charles Consel, Calton Pu, Jonathan Walpole

Computer Science Faculty Publications and Presentations

To make object invocation efficient, it is important to minimize overhead. In general, overhead is incurred in order to maintain transparency; with the advent of mobile computer systems, persistence, increasing security and privacy concerns, transparency becomes more expensive and overhead is increasing. Invocation mechanisms maintain transparency by finding objects, choosing communication media, performing data translation into common formats (e.g., XDR), marshalling arguments, encrypting confidential data, etc. Performing all of these operations on every invocation would lead to unacceptable performance, so designers often avoid operations by specializing object invocation for more restricted environments. For example, the Emerald compiler performs several optimizations …

Multicriteria Mission Route Planning Using A Parallel A* Search, Michael S. Gudaitis

Theses and Dissertations

The Mission Route Planning (MRP) Problem falls into the general class of multicriteria path search problems. Multiple criteria are evaluated to select an optimal aircraft mission route through a hostile environment. Criteria for distance travelled and radar exposure are combined into a single cost function for route evaluation. Radar calculations are performed dynamically. The A* search algorithm is applied to the MRP problem, and a parallel implementation is developed and tested. A unique combination of distributed OPEN lists with a global CLOSED list strategy produced fast execution times on the Paragon. Test cases for scenarios with 15 radars took less …

Program Modeling And Control Synthesis For Robotic Manipulators, Ramiz N. Ballou, Arlan R. Dekock, David D. Ardayfio

Computer Science Technical Reports

The control and programming methodology of industrial robots is becoming increasingly important. The speed and accuracy of data generation, and the performance of the robot are considered the most important factors in robotics control. This paper presents and discusses algorithms that solve for the inverse solution for a given point in space at a very high speed based on the top down abstract method. The algorithms are independent of any specific type of manipulator configuration or programming language. The algorithms were implemented for the IBM-PC™ using the FORTRAN language to control the Armdroid™ robot. The program generates 500 sets of …

Survey And Implementation Of Commercial Manual Controllers For A Generic Telerobotics Architecture, Thomas E. Deeter

Theses and Dissertations

The purpose of this study is to determine an input device for the Air Force's generic telerobotics architecture for large aircraft maintenance and repair. One area of concern is the human to machine interface, more specifically, which manual controller should be used for the specified tasks in this architecture. We mailed a survey to 68 companies in order to compile a list of possible input devices that the telerobotics architecture could use. 32 companies responded which gave me enough data to generate a list that described the physical traits of the input devices. We then divided the required tasks into …

Parallelization Of The 2d Roe Scheme On The Intel Paragon, John R. Graham Iii

Theses and Dissertations

This study presented a methodology for determining the general performance characteristics of a computational fluid dynamics (CFD) algorithm on the Intel Paragon. By performing a rigorous time complexity analysis of a parallel CFD algorithm, the general performance could be characterized before the code was actually parallelized. This was shown by implementing a serial version of the 2-D Roe Scheme on the Paragon. This explicit code was parallelized by the addition of generic yet efficient routines that decomposed the domain, automatically adjusted partition indices, and performed 2-D and 3-D buffer exchanges. Additionally, efficient global routines available for the Paragon were used …

Toward Scalable Parallel Software: An Active Object Model And Library To Support Von Neumann Languages, George K. Thiruvathukal

Computer Science: Faculty Publications and Other Works

Scalable parallel processing has been proposed as the technology scientists and engineers can use today to solve the problems of tomorrow. Many computational Grand Challenge problems require between two and three orders of magnitude than can be provided with the scalable parallel hardware of the early nineteen-nineties. While hardware continues to become more scalable and cheaper, software is not advancing at the same pace and remains a very expensive part of systems development.

A great deal of emphasis on software technology to support scalable parallel processing is placed on von Neumann languages. One of two approaches is common: (a) augment …

Space Modeler: An Expanded, Distributed, Virtual Environment For Space Visualization, John C. Vanderburgh

Theses and Dissertations

The Space Modeler is the first truly immersive virtual environment that models the solar system, models satellites in near-Earth orbit, and can operate in a Distributed Interactive Simulation (DIS) environment. It increases the capabilities of the 1993 Satellite Modeler by expanding the physical limits of the environment and by implementing a new three-dimensional user interface. Satellite orbits are modeled using NASA two line element sets. The positions of the Sun, Moon and planets are computed using an algorithm based on planetary orbital element sets using a linear polynomial fit. For higher precision, the planetary orbits can be computed using an …

Using Object-Oriented Database Technology To Develop A Multiple Domain Capability For Domain-Oriented Application Composition Systems, Alfred W. Harris Jr.

Theses and Dissertations

This thesis describes the design and implementation of a multiple domain capability for a domain-oriented application composition system, named Architect. The research goal was to show how object-oriented database management system (OODBMS) technology can be used to provide simultaneous access to multiple domain-oriented knowledge bases. Since the Architect system was originally designed using the object-oriented paradigm, insertion of OODBMS technology was relatively simple and many of the object-oriented concepts, such as inheritance and aggregation, proved beneficial. Inheritance was used to encapsulate domain knowledge by defining each domain as a subclass of Architect's software architecture. Aggregation was used to allow applications …

Analytic Performance Models For Parallel Discrete Event Battlefield Simulation With Conservative Synchronization, James B. Hiller

Theses and Dissertations

This study investigated the development and use of analytic models for performance analysis of parallel discrete event battlefield simulation using conservative synchronization. A simulation architecture with layered application, simulation, and host machine services provided the model development basis. Simulation entities were modeled with set-theoretic definitions. Deterministic performance models using these definitions were developed for event prediction, scheduling, and execution in sequential battlefield simulation. The sequential model was expanded to include relative bounds for overhead factors introduced when the simulation is spatially decomposed for a parallel distributed memory machine. Comparison of sequential and parallel models instantiated for a simulation with uniform …

Modeiing Operational Task Assignment In Air Force Wing Command And Control, Robert J. Hunt

Theses and Dissertations

This research investigated the feasibility of applying software engineering technology to the Air Force wing command and control (C2) domain. As part of this research, domain analysis and object-oriented techniques were investigated and a specific approach was chosen to analyze the domain. Analysis of the domain resulted in an object-oriented domain model that captured the key objects, operations, and associations, and behavior of wing C2. The domain model was used to design and implement a prototype software tool that enables wing decision makers to assign resources to mission tasks and to make assessments about automation's impact on wing C2 operations.

Unification Of Larch And Z-Based Object Models To Support Algebraically-Based Design Refinement: The Z Perspective, Kathleen M. Wabiszewski

Theses and Dissertations

This research established a foundation for formalizing the evolution of based object models to theories, part of a dual approach for formally extending object-oriented analysis models using the Z and LARCH languages. For the initial phase, a comprehensive, consistent, and correct Z language parser was implemented within the SOFTWARE REFINERY™ Programming Environment. The Z parser produced abstract syntax trees (ASTs) of objects, thereby forming the basis for analyzing the similarities and differences between the based and LARCH-based object representations. The second phase used the analysis of the two languages to identify fundamental core constructs that consisted of similar syntactic and …