Computer Sciences Commons^™

Multiple-Length Division Revisited: A Tour Of The Minefield, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

Long division of natural numbers plays a crucial role in Cobol arithmetic, cryptography, and primality testing. Only a handful of textbooks discuss the theory and practice of long division, and none of them do it satisfactorily. This tutorial attempts to fill this surprising gap in the literature on computer algorithms. We illustrate the subtleties of long division by examples, define the problem concisely, summarize the theory, and develop a complete Pascal algorithm using a consistent terminology.

Numerical Solution Of Laplace's Equation, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

This tutorial discusses Laplace's equation for steady state heat flow in a two-dimensional region with fixed temperatures on the boundaries. The equilibrium temperatures are computed for a square grid using successive overrelaxation with parity ordering of the grid elements. The numerical method is illustrated by a Pascal algorithm. We assume that the reader is familiar with elementary calculus.

Parallel Cellular Automata: A Model Program For Computational Science, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

We develop a model program for parallel execution of cellular automata on a multicomputer. The model program is then adapted for simulation of forest fires and numerical solution of Laplace's equation for stationary heat flow. The performance of the parallel program is analyzed and measured on a Computing Surface configured as a matrix of transputers with distributed memory.

Minimum Separation For Single-Layer Channel Routing, Ronald I. Greenberg, F. Miller Maley

Computer Science: Faculty Publications and Other Works

We present a linear-time algorithm for determining the minimum height of a single-layer routing channel. The algorithm handles single-sided connections and multiterminal nets. It yields a simple routability test for single-layer switchboxes, correcting an error in the literature.

Formal Generation Of Executable Assertions For Application-Oriented Fault Tolerance, Hanan Lutfiyya, Martina Schollmeyer, Bruce M. Mcmillin

Computer Science Technical Reports

Executable assertions embedded into a distributed computing system can provide run-time assurance by ensuring that the program state, in the actual run-time environment, is consistent with the logical stage specified in the assertions; if not, then an error has occurred and a reliable communication of this diagnostic information is provided to the system such that reconfiguration and recovery can take place. Application- oriented fault tolerance is a method that provides fault detection using executable assertions based on the natural constraints of the application.

This paper focuses on giving application-oriented fault tolerance a theoretical foundation by providing a mathematical model for …

Designing Efficient Maximum-Likelihood Soft-Decision Decoding Algorithms For Linear Block Codes Using Algorithm A*, Yunghsiang S. Han, Carlos R.P. Hartmann

Electrical Engineering and Computer Science - Technical Reports

In this report we present a class of efficient maximum-likelihood soft-decision decoding algorithms 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 …

Primality Testing, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

This tutorial describes the Miller-Rabin method for testing the primality of large integers. The method is illustrated by a Pascal algorithm. The performance of the algorithm was measured on a Computing Surface.

Simulated Annealing, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

This tutorial describes simulated annealing, an optimization method based on the principles of statistical mechanics. Simulated annealing finds near-optimal solutions to optimization problems that cannot be solved exactly because they are NP-complete. The method is illustrated by a Pascal algorithm for the traveling salesperson problem. The performance of the algorithm was measured on a Computing Surface.

New Algorithms For Mid-Crack Codes In Image Processing, Wai-Tak Wong

Theses

The chain code is a widely-used description for a contour image. Recently, a mid-crack code algorithm has been proposed as another more precise method for image representation. New algorithms using this new mid-crack code for image representation, restoration, and skeletonization are developed. The efficiency and accuracy can be increased obviously.

Firstly, the conversion of a binary image with multiple regions into the mid-crack codes is presented. A fast on-line implementation can be achieved using tables look-up. The input binary image may contain several object regions and their mid-crack codes can be extracted at the same time in a single-pass row-by-row …

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.

Scheduling Regular And Irregular Communication Patterns On The Cm-5, Ravi Ponnusamy, Rajeev Thakur, Alok Choudhary, Geoffrey C. Fox

Northeast Parallel Architecture Center

In this paper, we study the communication characteristics of the CM-5 and the performance effects of scheduling regular and irregular communication patterns on the CM-5. We consider the scheduling of regular communication patterns such as complete exchange and broadcast. We have implemented four algorithms for complete exchange and studied their performances on a 2D FFT algorithm. We have also implemented four algorithms for scheduling irregular communication patterns and studied their performance on the communication patterns of several synthetic as well as real problems such as the conjugate gradient solver and the Euler solver.

The Fast Fourier Transform, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

This tutorial discusses the fast Fourier transform, which has numerous applications in signal and image processing. The FFT computes the frequency components of a signal that has been sampled at n points in O( n log n) time. We explain the FFT and illustrate it by examples and Pascal algorithms. We assume that you are familiar with elementary calculus.

Indifference Graphs And The Single Row Routing Problem, Peter J. Looges

Computer Science Theses & Dissertations

This thesis investigates the subclass of interval graphs known as indifference graphs. New optimal algorithms for recognition, center, diameter, maximum matching, Hamiltonian path and domination in indifference graphs are presented. The recognition algorithm produces a linear order with properties which allow the solution of the other problems in linear time. Indifference graphs are further applied to the single row routing problem which results in both sequential,. and parallel routing algorithms.

Three--Dimensional Medical Imaging: Algorithms And Computer Systems, M. R. Stytz, G. Frieder, O. Frieder

College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects

This paper presents an introduction to the field of three-dimensional medical imaging It presents medical imaging terms and concepts, summarizes the basic operations performed in three-dimensional medical imaging, and describes sample algorithms for accomplishing these operations. The paper contains a synopsis of the architectures and algorithms used in eight machines to render three-dimensional medical images, with particular emphasis paid to their distinctive contributions. It compares the performance of the machines along several dimensions, including image resolution, elapsed time to form an image, imaging algorithms used in the machine, and the degree of parallelism used in the architecture. The paper concludes …

A Software Design Tool For Predictable Performance In Real-Time, Data Flow Architectures, Brij Mohan V. Mandala

Electrical & Computer Engineering Theses & Dissertations

A software design tool which aids in the performance evaluation and selection of operating points for an algorithm implemented in ATAMM defined data flow architectures is presented in this thesis. ATAMM (Algorithm To Architecture Mapping Model) is a new graph theoretic model developed by researchers at Old Dominion University and the NASA-Langley Research Center. ATAMM is capable of modeling the execution of large-grained algorithms on distributed data flow architectures. A software tool is required for predicting the performance, determining the resource requirements and for selecting suitable operating points for an ATAMM based system. The ATAMM Design Tool presented in this …

Towards A Bound For The Compression Of The Lzw Algorithm, Anoop Kumar Srivastava, Shinu Gupta

Theses

The LZW algorithm is a well known efficient adaptive compression algorithm. It is based on constructing a dictionary containing character strings from the text. A number of researchers have attempted to add variations to the original algorithm to achieve higher compression values. In this thesis we attempt to find a bound for the LZW approach. That is, we build a dictionary which gives maximum compression and satisfies prefix property of LZW algorithm.

In order to build such an optimum dictionary, the dynamic programming technique is applied. The final dictionary selected consists of entries which give maximum overall compression and also …

Performance Modeling And Enhancement For The Atamm Data Flow Architecture, Sukhamoy Som

Electrical & Computer Engineering Theses & Dissertations

Algorithm To Architecture Mapping Model (ATAMM) is a new marked graph model from which the rules for data and control flow in a homogeneous, multicomputer, data flow architecture may be defined. This research is concerned with performance modeling and performance enhancement for periodic execution of large-grain, decision-free algorithms in such an ATAMM defined architecture. Performance measures and bounds are established. Algorithm transformation techniques are identified for performance enhancement and reduction of computing element requirements. Operating strategies are developed for optimum time performance and for sub-optimum time performance under limited availability of computing elements. An ATAMM simulator is used to test …

A Color-Exchange Algorithm For Exact Graph Coloring, Thomas J. Sager, Shi-Jen Lin

Computer Science Technical Reports

DEXCH, a color-exchange exact graph coloring algorithm is presented. On many classes of graphs, DEXCH can, in the mean, find the chromatic number of a graph considerably faster than the DSATUR algorithm. The improvement over DSATUR stems from the ability to reorganize the subset of colored vertices and to detect in certain instances the existence of a complete subgraph of cardinality equal to the number of colors used in the best coloring found so far. The mean improvement over DSATUR is greatest on high edge-density graphs attaining the value of 42% on random graphs of edge-density 0.7 on 64 vertices.

Weak Bipolarizable Graphs, Stephan Olariu

Computer Science Faculty Publications

We characterize a new class of perfectly orderable graphs and give a polynomial-time recognition algorithm, together with linear-time optimization algorithms for this class of graphs.

Implementing Ray Tracing Algorithm In Parallel Environment, Tjah Jadi

Dissertations and Theses

Ray tracing is a very popular rendering algorithm in the field of computer graphics because it can generate highly-realistic images from three-dimensional models. Unfortunately, the computational cost is very expensive. To speed up the rendering process we present both static and dynamic scheduling (balancing) strategies for a multiprocessor system. Hence, the load balancing among the processors is the most important problem in parallel processing. The implementation of the algorithm is based on a modified octree structure.

Algebraic Geometry For Computer-Aided Geometric Design, Thomas W. Sederberg, Ronald N. Goldman

Faculty Publications

Classical algebraic geometry has been virtually ignored in computer-aided geometric design. However, because it deals strictly with algorithms, it is really more suited to this field than is modern algebraic geometry, which introduces abstractions far removed from the algorithmic nature of computer-aided design. This tutorial examines resultants, curve implicitization, curve inversion, and curve intersection. Discussion follows a series of examples simple enough for those with only a modest algebra background to follow.

An Improved Algorithm For Generating Minimal Perfect Hash Functions, Thomas J. Sager

Computer Science Technical Reports

A minimal perfect hash function (MPHF) is a function from a set of M objects to the first M non-negative integers. MPHF's are useful for the compact storage and fast retrieval of frequently used objects such as reserved words in a programming language or commonly employed words in a natural language. In this paper we improve on an earlier result and present an algorithm for generating MPHF's with an expected time complexity proportional to M⁴. We also give a MPHF for the 256 most frequently used words in the English language.

A Direct Formulation And Computer-Implementation Of A Symbolic Network Analysis Algorithm, Timothy James Knerr

Electrical & Computer Engineering Theses & Dissertations

An algorithm for the symbolic analysis of linear, time-invariant, active or passive networks is presented. The algorithm incorporates the best features of earlier numerical and topological methods of symbolic analysis. A hybrid set of equations is formulated for a closed linear graph and arranged in matrix form. A numerical evalu­ation procedure for the determinant of this hybrid matrix results in an efficient method of symbolic analysis. A proof of the algorithm based on determinant evaluation by a permutation product expansion provides insight into relationships with other methods of symbolic analysis. A computer program implementation of the algorithm is described and …

An Algorithm For The Electromagnetic Scattering Due To An Axially Symmetric Body With An Impedance Boundary Condition, F. Stenger, M. Hagmann, J. Scheing

Computer Science Faculty Publications

Let B be a body in R³, and let S denote the boundary of B. The surface S is described by S = {(x, y, z): (x² + Y²)^½= ƒ(z), -1≤ z ≤ I}, where ƒ analytic function that is real and positive on (-1, 1) and ƒ(±1) = 0. An algorithm is described for computing the scattered field due to a plane wave incident field, under Leontovich boundary conditions. The Galerkin method of solution used here leads to a block diagonal matrix involving 2M …

An Efficient Dft Algorithm Using The Walsh Transform, Albert P. Gerheim

Electrical & Computer Engineering Theses & Dissertations

The matrix transformation relating the sequency and frequency domains is derived. It is shown that these­ frequency-to-frequency conversion can be performed via a computationally efficient sparse matrix algorithm. The sequency-to-frequency algorithm can be used with a fast Hadamard transform to implement a discrete Fourier trans­ form. The efficiencies of this combined algorithm and a radix-two fast Fourier transform are compared.

The algorithm is applied to the sequency domain de­ sign of a Wiener digital filter. Improved computational efficiencies are achieved relative to the procedure de­veloped by Kahveci and Hall (9).

An Algorithm For Finding All Isomorphisms Of Two Graphs, Atanas Radenski

Mathematics, Physics, and Computer Science Faculty Articles and Research

No abstract provided.

On The Decomposition Of Asynchronous Systems, Robert M. Keller

All HMC Faculty Publications and Research

This paper reports of part of a continuing investigation of parallel computation, in particular, efforts toward understanding the nature of different types of parallel control. The first section defines an asynchronous system to be a simple type of state machine. This was arrived at in an attempt to generalize from the types of control in parallel program schemata and networks of asynchronous modules without bounded delays. Asynchronous systems with output are also defined in a familiar way. The deviation from standard work comes in the definition of a parallel decomposition of asynchronous systems. Some preliminary work on compositions of this …