Computer Sciences Commons^™

Parallel Fast Multipole Algorithm Using Mpi, Daniel Okunbor, Eric Jui-Lin Lu

Computer Science Technical Reports

The simulation of many-body, many-particle system has a wide range of applications in area such as biophysics, chemistry, astrophysics, etc. It is known that the force calculation contributes ninety percent of the simulation time. This is mainly due to the fact that the total number of interactions in the force is 0( N 2 ), where N is the number of particles in the system. The fast multipole algorithm, proposed by Greengard and Rokhlin, reduces the time complexity of the force calculation to O(N). We implement the fast multipole algorithm, using MPI, based on optimal communication scheme which minimizes the …

Integration Methods For N-Body Problems, D. I. Okunbor

Computer Science Technical Reports

Particle simulation studies the time evolution of the dynamical state of a system of interacting particles by the computation of trajectories of particles based on the numerical integration of the Newton equations of motion. This approach is widely used in biomolecular modeling to study, for example, proteins; and in astrophysics to study gravitational N-body system. The dimension of this system of equations of motion is in the order of tens of thousands. To solve this system involves an enormous amount of computer time. Several techniques have been advanced to reduce the computational complexity of this problem. Some of which are: …

Software Testing Paradigms, A. Subramaniam, G. Zobrist

Computer Science Technical Reports

The development of software follows a series of steps adopted from the Classical Life Cycle approach. Amongst all the steps, Software testing demands a lot of attention considering the amount of effort applied in it. There are various techniques by which a software can be tested. A review of techniques available are discussed. A methodology that can be applied to software testing has also been suggested. This document can be used by a programmer to select the technique for software testing and also assists in providing a narrowed view to the vast number of techniques available for software testing.

Discovery Of Integrity Relationships In Relational Databases, D. Harrier, D. C. St. Clair

Computer Science Technical Reports

The use of database management system integrity constraints has been a powerful tool in raising the quality of data within an application subject database. Unfortunately, the successful use of integrity constraints requires that the database administrator has implemented the constraint before data are inserted into the database.

The results of this research provide a methodology for discovering previously unknown integrity relationships in a relational database. The methodology uses the principles of knowledge discovery from the artificial intelligence community, and Quinlan's ID3 machine learning algorithm as the discovery tool. Experimental results are provided that demonstrate how the methodology can be applied.

From Formal Security Specifications To Executable Assertions - A Distributed Systems Preliminary Study, C. Serban, B. Mcmillin

Computer Science Technical Reports

A security policy for a distributed system can be checked for compliance at run-time, as the system executes, using assertions embedded in software. This paper presents the concept of run-time security assurance, according to a given security policy for a given distributed system, along with mechanisms for its usage. A model problem illustrates the implementation of executable security assertions and their run-time validation on histories (traces) of events.

Parallel Algorithm Derivation And Program Transformation In A Preprocessing Compiler For Scientific Languages: The Psi Project And Hpf, L. R. Mullin, Thom Mcmahon

Computer Science Technical Reports

Scientific Programming and subsequent compilation is significantly complicated when programs are expected to perform on one or many processors for any size or dimensional problem. Scientific languages, although sophisticated and powerful, have been slow to evolve from their Von Neumann scalar by scalar operations to monolithic data parallel functions, e.g. Fortran 90/95. The structure of an array and corresponding architectural topology to which the arrays are mapped, may provide ways to increase portability and scalability of designs. This paper presents how the Psi(w) Calculus in conjunction with a useful algebra that provides convolutions, permutations, and scalar operations, is being used …

On Programming Scientific Applications In A Functional Language Extended By A \L' - Calculus Subsystem For Array Operations, L. R. Mullin, Werner Kluge

Computer Science Technical Reports

This paper discusses some of the pros and cons of extending functional languages by high-level array operations similar to those that are available in APL. This extension is based on the lp~calculus, an algebra of arrays which provides a small set of essential array operations defined in terms of dimensionalities, shapes and indexing functions. Since these operations specify context-free substitutions of array expressions by others, the lpcalculus fits perfectly into a functional programming paradigm.

In order to demonstrate the programming techniques made possible by the lp-calculus, we study a functional program for the approximation of numerical solutions of partial differential …

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

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.

Automatic Pcb Inspection Systems, M. Moganti, Fikret Erçal

Computer Science Faculty Research & Creative Works

There are more than 50 process steps required to fabricate a printed circuit board (PCB). To ensure quality, human operators simply inspect the work visually against prescribed standards. The decisions made by this labor intensive, and therefore costly, procedure often also involve subjective judgements. Automatic inspection systems remove the subjective aspects and provide fast, quantitative dimensional assessments. Machine vision may answer the manufacturing industry's need to improve product quality and increase productivity. The major limitation of existing inspection systems is that all the algorithms need a special hardware platform to achieve the desired real-time speeds. This makes the systems extremely …

Adaptive Resonance Theory (Art): An Introduction, Lucien G. Heins, Daniel R. Tauritz

Computer Science Faculty Research & Creative Works

No abstract provided.

Using Taguchi''S Method Of Experimental Design To Control Errors In Layered Perceptrons, William E. Bond, Gerald E. Peterson, Daniel C. St. Clair, Stephen R. Aylward

Computer Science Faculty Research & Creative Works

A significant problem in the design and construction of an artificial neural network for function approximation is limiting the magnitude and the variance of errors when the network is used in the field. Network errors can occur when the training data does not faithfully represent the required function due to noise or low sampling rates, when the network's flexibility does not match the variability of the data, or when the input data to the resultant network is noisy. This paper reports on several experiments whose purpose was to rank the relative significance of these error sources and thereby find neural …

Using Neural Networks For Aerodynamic Parameter Modeling, Gerald E. Peterson, William E. Bond, Roger Germann, Barry Streeter, James Urnes

Computer Science Faculty Research & Creative Works

Neural networks are being developed at McDonnell Douglas Corporation to provide an onboard model of an aircraft's aerodynamics to support advanced flight control systems. These flight control systems, constructed using neural networks and advanced controllers, have the potential to reduce flight control development costs and to improve inflight performance. Neural networks are useful in this situation because they can compactly represent the data and operate in real-time

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 …

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 …

Hardware Assists For High Performance Computing Using A Mathematics Of Arrays, Hardy J. Pottinger, W. Eatherton, J. Kelly, T. Schiefelbein, Lenore Mullin, R. Ziegler

Electrical and Computer Engineering Faculty Research & Creative Works

Work in progress at the University of Missouri-Rolla on hardware assists for high performance computing is presented. This research consists of a novel field programmable gate array (FPGA) based reconfigurable coprocessor board (the Chameleon Coprocessor) being used to evaluate hardware architectures for speedup of array computation algorithms. These algorithms are developed using a Mathematics of Arrays (MOA). They provide a means to generate addresses for data transfers that require less data movement than more traditional algorithms. In this manner, the address generation algorithms are acting as an intelligent data prefetching mechanism or special purpose cache controller. Software implementations have been …

Computing Χ² Values, John F. Dooley, Daniel C. St Clair, William E. Bond

Mathematics and Statistics Faculty Research & Creative Works

Textbooks and courses on numerical algorithms contain numerous examples which lead students to believe that the algorithm of choice for computing the zeros of a function f1994 is Newton's algorithm. In many of these courses little or no time is spent in providing students with "real world" experiences where Newton's method fails. The work presented in this paper describes a slow convergence problem encountered while trying to use Newton to estimate values for the 2 distributions. The problem occurred while the authors were trying to implement a well-known machine learning algorithm from the field of artificial intelligence. The function being …

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 …

A New Approach To Automatic Target Recognition Using Wavelet Transforms, Anitha Panapakkam, S. N. Balakrishnan, Daniel St. Clair

Computer Science Technical Reports

Automatic Target Recognition (ATR) systems have significant impact in defense applications. There is a continuing need to develop new and robust techniques to handle the increasingly complex ATR problem. The objectives of this thesis are two-fold. First a new technique to be used for ATR is developed and secondly an integrated ATR system to investigate and combine all subsystems is developed. In this thesis, we have developed a new technique for the feature extraction stage of ATR problem using wavelet transforms. Wavelet transforms have been one of the widely investigated areas of research in the past few years. The promising …

Performance Monitoring Of Hybrid Intelligent Systems, Nariman Abdel Baky, Fikret Ercal

Computer Science Technical Reports

Development of an automated system to enable the ongoing monitoring and control of the performance of HIS is a step towards increasing the confidence and security with which ordinary users will perceive AI-based Systems. The main objective of this research was to develop a prototype intelligent system to perform this monitoring. The proposed monitming system integrates performance metrics for the HIS's components with heuristics for evaluating data quality by checking data types, data ranges, percentage of missing data and the composition of data. The research demonstrated the possibility of developing such system and the feasibility of using it for a …

Ccsp - A Formal System For Distributed Program Debugging, Hanan Lutfiyya, Bruce Mcmillin, Beth Arrowsmith, Cristina Serban

Computer Science Technical Reports

One major problem with programming in a parallel/distributed environment is the difficulty in debugging the programs owing to the complex interactions of their component processes. Complete knowledge of the program's state is not generally attainable in a distributed system. This paper presents a distributed system for debugging distributed programs that allows for the execution and evaluation of embedded assertions expressed in Hoare's CSP [6]. We show examples of the use of this system, prove its correctness, and describe how the system can be used for the more general case of ensuring an application's correctness at run-time.

R-By-C Crozzle: An Np-Hard Problem, Michelle Gower, Ralph Wilkerson

Computer Science Technical Reports

In an Auslralian magazine, a monetary prize is awarded to the person with the best answer to a word puzzle called a Crozzle. Each valid placement of given words into a 10x 15 grid is given a score, and the best answer is the placement with the largest score. Various search techniques have been utilized lo solve this problem. No one has shown whether there is a polynomial-time algorithm to find the best Crozzle. This paper proves that the Crozzle is in NP. It also creates a similar word puzzle, called R-by-C Crozzle, by lifting the constraint on the grid …

Eighth-Order Explicit Symplecticrunge-Kutta-Nyström Integrators, Daniel I. Okunbor, Eric J. Lu

Computer Science Technical Reports

We consider the solution of Hamiltonian dynamical systems by constructing eighth-order explicit symplectic Runge-Kutta-Nyström integrators. The application of highorder integrators may be important in areas such as in astronomy. They require large number of function evaluations, which make them computationally expensive and easily susceptible to errors. The integrators developed in this paper require 17 function evaluations as opposed to the 26-stage (effectively 24) eighth-order explicit symplectic Runge-Kutta-Nyström method derived by Calvo and Sanz-Serna. Numerical tests using the 2-Body and the sine-Gordon problems indicate that our methods are comparable to that of Calvo and Sanz-Serna and Yoshida.

How To Program In Ccsp, Beth Arrowsmith

Computer Science Technical Reports

No abstract provided.

Teaching The Practice Of Formal Methods In Distributed Computing Systems - A Module, Beth Arrowsmith, Bruce Mcmillin

Computer Science Technical Reports

No abstract provided.

A Recursive Least Squares Training Algorithm For Multilayer Recurrent Neural Networks, Q. Xu, K. Krishnamurthy, Bruce M. Mcmillin, Wen Feng Lu

Mechanical and Aerospace Engineering Faculty Research & Creative Works

Recurrent neural networks have the potential to perform significantly better than the commonly used feedforward neural networks due to their dynamical nature. However, they have received less attention because training algorithms/architectures have not been well developed. In this study, a recursive least squares algorithm to train recurrent neural networks with an arbitrary number of hidden layers is developed. The training algorithm is developed as an extension of the standard recursive estimation problem. Simulated results obtained for identification of the dynamics of a nonlinear dynamical system show promising results.

Identification Of Cutting Force In End Milling Operations Using Recurrent Neural Networks, Q. Xu, K. Krishnamurthy, Bruce M. Mcmillin, Wen Feng Lu

Mechanical and Aerospace Engineering Faculty Research & Creative Works

The problem of identifying the cutting force in end milling operations is considered in this study. Recurrent neural networks are used here and are trained using a recursive least squares training algorithm. Training results for data obtained from a SAJO 3-axis vertical milling machine for steady slot cuts are presented. The results show that a recurrent neural network can learn the functional relationship between the feed rate and steady-state average resultant cutting force very well. Furthermore, results for the Mackey-Glass time series prediction problem are presented to illustrate the faster learning capability of the neural network scheme presented here

Hardware Assists For High Performance Computing Using A Mathematics Of Arrays, H. Pottinger, W. Eatherton, L. Mullin, T. Schiefelbein

Computer Science Technical Reports

Work in progress at the University of Missouri - Rolla on hardware assists for high performance computing and communication is presented. This research consists of a field programmable gate array based rapid prototyping environment (Chameleon) being used to evaluate hardware architectures for speedup of array partitioning and routing algorithms. These algorithms have been developed using a Mathematics of Arrays (MOA) and are optimal in the sense that they reduce normal array indexing operations to a series of primitive additions based on array shape. The method is simple yet powerful, produces algorithms which are provably correct, and are independent of dimensionality. …

An Fpga Based Reconfigurable Coprocessor Board Utilizing A Mathematics Of Arrays, H. Pottinger, W. Eatherton, T. Schiefelbein, L. Mullin, R. Ziegler

Computer Science Technical Reports

Work in progress at the University of Missouri-Rolla on hardware assists for high performance computing is presented. This research consists of a novel field programmable gate array (FPGA) based reconfigurable coprocessor board (the Chameleon Coprocessor) being used to evaluate hardware architectures for speedup of array computation algorithms. These algorithms have been developed using a Mathematics of Arrays (MOA) and are optimal in the sense that they reduce normal array cartesian indexing operations to a series of primitive additions and offsets based on array shape. The method is simple yet powerful, produces algorithms which are provably correct, and are independent of …

Qualitative Study Of The Symplectic Stormer-Verlet Integrator, D. J. Hardy, D. I. Okunbor

Computer Science Technical Reports

Symplectic numerical integrators, such as the Stormer-Verlet method, are useful in preserving certain important properties that are not preserved by conventional numerical integrators. This paper analyzes the Stormer-Verlet method as applied to the simple harmonic model, which is an important model for molecular dynamics simulations. Restricting our attention to the one-dimensional case, both the exact solution and the Stormer-Verlet solution to this model are expressed as functions of the number of time steps taken, and then both of these functions are interpreted geometrically. The paper shows the existence of an upper bound on the error from the Stormer-Verlet method, and …