Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Keyword
-
- Algorithms (7)
- Logic programming (2)
- Primality testing (2)
- Simulated annealing (2)
- Adjacent transposition sorting (1)
-
- Benchmarking (1)
- Cellular automata (1)
- Comparators (1)
- Computing Surface (1)
- Concurrent programming-distributed programming (1)
- Connection Machine (1)
- D.1.3Programming Techniques (1)
- Data mappers (1)
- G.3 Probability and Statistics: Probabilistic algorithms (Monte Carlo) (1)
- G.3 [Probability and Statistics]: Probabilistic algorithms (Monte Carlo) (1)
- G.l.8 Numerical Analysis (1)
- Image Processing (1)
- Laplace's equation (1)
- Loosely synchronous communication (1)
- Miniswaps (1)
- Monte Carlo trials (1)
- Multicomputer algorithms (1)
- Multicomputers (1)
- Multiple-length integer division (1)
- Networks (1)
- Node contention (1)
- Non-uniform message size (1)
- Partial Differential Equations-difference methods (1)
- Performance Analysis (1)
- Personalized communications (1)
Articles 1 - 17 of 17
Full-Text Articles in Physical Sciences and Mathematics
Numerical Solution Of Laplace's Equation, Per Brinch Hansen
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
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.
Multiple-Length Division Revisited: A Tour Of The Minefield, Per Brinch Hansen
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.
All-To-Many Communication Avoiding Node Contention, Sanjay Ranka, Jhy-Chun Wang
All-To-Many Communication Avoiding Node Contention, Sanjay Ranka, Jhy-Chun Wang
Electrical Engineering and Computer Science - Technical Reports
In this paper we present several algorithms for all-too-many personalized communications which avoid node contention.
Simulated Annealing, Per Brinch Hansen
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.
Parallel Monte Carlo Trials, Per Brinch Hansen
Parallel Monte Carlo Trials, Per Brinch Hansen
Electrical Engineering and Computer Science - Technical Reports
The best results of Monte Carlo methods are generally obtained by performing the same computation many times with different random numbers. We develop a generic algorithm for parallel execution of Monte Carlo trials on a multicomputer. The generic algorithm has been adapted for simulated annealing and primality testing by simple substitutions of data types and procedures. The performance of the parallel algorithms was measured on a Computing Surface.
Primality Testing, Per Brinch Hansen
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.
Designing Efficient Maximum-Likelihood Soft-Decision Decoding Algorithms For Linear Block Codes Using Algorithm A*, Yunghsiang S. Han, Carlos R.P. Hartmann
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 …
General Model Theoretic Semantics For Higher-Order Horn Logic Programming, Mino Bai, Howard A. Blair
General Model Theoretic Semantics For Higher-Order Horn Logic Programming, Mino Bai, Howard A. Blair
Electrical Engineering and Computer Science - Technical Reports
We introduce model-theoretic semantics [6] for Higher-Order Horn logic programming language. One advantage of logic programs over conventional non-logic programs has been that the least fixpoint is equal to the least model, therefore it is associated to logical consequence and has a meaningful declarative interpretation. In simple theory of types [9] on which Higher-Order Horn logic programming language is based, domain is dependent on interpretation [10]. To define T p operator for a logic program P, we need a fixed domain without regard to interpretation which is usually taken to be a set of atomic propositions. We build a semantics …
Embedding Data Mappers With Distributed Memory Machine Compilers, Ravi Ponnusamy, Joel Saltz, Raja Das, Charles Koelbel, Alok Choudhary
Embedding Data Mappers With Distributed Memory Machine Compilers, Ravi Ponnusamy, Joel Saltz, Raja Das, Charles Koelbel, Alok Choudhary
Electrical Engineering and Computer Science - Technical Reports
In scalable multiprocessor systems, high performance demands that computational load be balanced evenly among processors and that interprocessor communication be limited as much as possible. Compilation techniques for achieving these goals have been explored extensively in recent years [3, 9, 11, 13, 17, 18]. This research has produced a variety of useful techniques, but most of it has assumed that the programmer specifies the distribution of large data structures among processor memories. A few projects have attempted to automatically derive data distributions for regular problems [12, 10, 8, 1]. In this paper, we study the more challenging problem of automatically …
A Probabilistic Analysis Of A Locality Maintaining Load Balancing Algorithm, Kishan Mehrotra, Sanjay Ranka, Jhy-Chun Wang
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.
A Non-Deterministric Parallel Sorting Algorithm, Xue Shirley Li, F. Lockwood Morris
A Non-Deterministric Parallel Sorting Algorithm, Xue Shirley Li, F. Lockwood Morris
Electrical Engineering and Computer Science - Technical Reports
A miniswap Si,1 ≤ i < n, compares two adjacent keys Пi, Пi+1 in the sequence (П1, ... , Пn), and transposes them if they are out of order. A full sweep is any composition of all n - 1 possible miniswaps. We prove that the composition of any n- 1 full sweeps is a sorting function.
Conceptual Background For Symbolic Computation, Klaus Berkling
Conceptual Background For Symbolic Computation, Klaus Berkling
Electrical Engineering and Computer Science - Technical Reports
This paper is a tutorial which examines the three major models of computation--the Turing Machine, Combinators, and Lambda Calculus--with respect to their usefulness to practical engineering of computing machines. While the classical von Neumann architecture can be deduced from the Turing Machine model, and Combinator machines have been built on an experimental basis, no serious attempts have been made to construct a Lambda Calculus machine. This paper gives a basic outline of how to incorporate a Lambda Calculus capability into a von Neumann type architecture, maintaining full backward compatibility and at the same time making optimal use of its advantages …
Fault-Detection In Networks, H. F. Mattson Jr
Fault-Detection In Networks, H. F. Mattson Jr
Electrical Engineering and Computer Science - Technical Reports
To find broken links in networks we use the cut-set space. Information on which nodes can talk, or not, to which other nodes allows reduction of the problem to that of decoding the cut-set code of a graph. Special classes of such codes are known to have polynomial-time decoding algorithms. We present a simple algorithm to achieve the reduction and apply it in two examples.
A Declarative Foundation Of Λprolog With Equality, Mino Bai
A Declarative Foundation Of Λprolog With Equality, Mino Bai
Electrical Engineering and Computer Science - Technical Reports
We build general model-theoretic semantics for higher-order logic programming languages. Usual semantics for first-order logic is two-level: i.e., at a lower level we define a domain of individuals, and then, we define satisfaction of formulas with respect to this domain. In a higher-order logic which includes the propositional type in its primitive set of types, the definition of satisfaction of formulas is mutually recursive with the process of evaluation of terms. As result of this in higher-order logic it is extremely difficult to define an effective semantics. For example to define T p operator for logic program P, we need …
The Expressiveness Of Locally Stratified Programs, Howard A. Blair, Wiktor Marek, John S. Schlipf
The Expressiveness Of Locally Stratified Programs, Howard A. Blair, Wiktor Marek, John S. Schlipf
Electrical Engineering and Computer Science - Technical Reports
This paper completes an investigation of the logical expressibility of finite, locally stratified, general logic programs. We show that every hyperarithmetic set can be computed by a suitably chosen locally stratified logic program (as a set of values of a predicate over its perfect model). This is an optimal result, since the perfect model of a locally stratified program is itself an implicitly definable hyperarithmetic set (under a recursive coding of the Herbrand base); hence to obtain all hyperarithmetic sets requires something new, in this case selecting one predicate from the model. We find that the expressive power of programs …
Benchmarking The Cm-5 For Image Processing Applications, Ravi V. Shankar, Ravi Ponnusamy, Sanjay Ranka
Benchmarking The Cm-5 For Image Processing Applications, Ravi V. Shankar, Ravi Ponnusamy, Sanjay Ranka
Electrical Engineering and Computer Science - Technical Reports
This paper presents benchmarking results for image processing algorithms on the Connection Machine model CM-5 and compares them with the results from the CM-2 and the Sun-4. Image processing algorithms with varying communication and computational requirements were implemented, tested and timed. The performance and the scalabilty of the CM-5 were analyzed and compared with that of the CM-2.