Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Keyword
-
- Chemistry (3)
- Load balancing (3)
- Logic programming (3)
- Neural networks (3)
- Parallel algorithms (3)
-
- Parallel computing (3)
- Algorithms (2)
- Data allocation (2)
- Data partitioning (2)
- Fast Fourier transform (2)
- Generic algorithms (2)
- Multicomputer Systems (2)
- Network Partitioning (2)
- Performance Evaluation (2)
- Physical optimization methods (2)
- Program specification (2)
- Programming paradigms (2)
- Quicksort (2)
- Task Scheduling (2)
- Task allocation. (2)
- Tree machine (2)
- All-pairs shortest paths (1)
- Artificial intelligence; computer control; constraint theory; delays; monitoring; safety; system integrity (1)
- Asynchronous structures (1)
- Automata (1)
- Average dependence (1)
- Backpropagation (1)
- Classification Problems (1)
- Clustering (1)
- Combinational circuits (1)
- Publication
Articles 1 - 30 of 48
Full-Text Articles in Physical Sciences and Mathematics
A Note On Many-One And 1-Truth-Table Complete Languages, Steven Homer, Stuart A. Kurtz, James S. Royer
A Note On Many-One And 1-Truth-Table Complete Languages, Steven Homer, Stuart A. Kurtz, James S. Royer
Electrical Engineering and Computer Science - Technical Reports
The polynomial time 1-tt complete sets for EXP and RE are polynomial time many-one complete.
An Efficient Neural Algorithm For The Multiclass Problem, Rangachari Anand, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka
An Efficient Neural Algorithm For The Multiclass Problem, Rangachari Anand, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka
Electrical Engineering and Computer Science - Technical Reports
One connectionist approach to the classification problem, which has gained popularity in recent years, is the use of backpropagation-trained feed-forward neural networks. In practice, however, we find that the rate of convergence of net output error is especially low when training networks for multi-class problems. In this paper, we show that while backpropagation will reduce the Euclidean distance between the actual and desired output vectors, the difference between some of the components of these vectors will actually increase in the first iteration. Furthermore, the magnitudes of subsequent weight changes in each iteration are very small, so that many iterations are …
Efficient Maximum-Likelihood Soft-Decision Decoding Of Linear Block Codes Using Algorithm A, Yunghsiang S. Han, Carlos R.P. Hartmann, Chih-Chieh Chen
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 …
Parallel Divide And Conquer, Per Brinch Hansen
Parallel Divide And Conquer, Per Brinch Hansen
Electrical Engineering and Computer Science - Technical Reports
We develop a generic divide and conquer algorithm for a parallel tree machine. From the generic algorithm we derive balanced, parallel versions of quicksort and the fast Fourier transform by substitution of data types, variables and statements. The performance of these algorithms is analyzed and measured on a Computing Surface configured as a tree machine with distributed memory.
Do Hypercubes Sort Faster Than Tree Machines?, Per Brinch Hansen
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.
The Fast Fourier Transform, Per Brinch Hansen
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.
Constructively Typed Timed Automata, J. F. Peters Iii
Constructively Typed Timed Automata, J. F. Peters Iii
Electrical Engineering and Computer Science - Technical Reports
A new class of communicating automata called typed Timed lnput/Output Automata (tTAi/os) is introduced. A tTAi/o is a predicate automaton used for specifying and reasoning about real-time systems. The typing discipline suggested for predicate automata is in the tradition of Martin-Löf's constructive type theory. A type A is a proposition, which is defined when a prescription for constructing a proof of A is given. A fragment of Girard's linear logic is used in classifying state types. An illustration of the use of tTAi/os in specifying a light-controller is presented. An abstract program is extracted during a proof of an automaton …
A Reconstruction Of Context-Dependent Document Processing In Sgml, Allen Brown Jr., T. Wakayama, Howard A. Blair
A Reconstruction Of Context-Dependent Document Processing In Sgml, Allen Brown Jr., T. Wakayama, Howard A. Blair
Electrical Engineering and Computer Science - Technical Reports
SGML achieves a certain degree of context-dependent document processing through attributes and linking. These mechanisms are deficient in several respects. To address these deficiencies we propose augmenting SGML's LINK and ATTLISTconstructs with two new mechanisms, coordination and (rule-based) attribution. The latter can be used to specify the result of context-dependent processing in a uniform fashion while considerably increasing SGML's expressive power. We illustrate this enhanced power by sketching a specification of (the result of) document layout that can be encoded in SGML augmented with coordination and attribution.
A Practical Hierarchical Model Of Parallel Computation Ll: Binary Tree And Fft Algorithms, Todd Heywood, Sanjay Ranka
A Practical Hierarchical Model Of Parallel Computation Ll: Binary Tree And Fft Algorithms, Todd Heywood, Sanjay Ranka
Electrical Engineering and Computer Science - Technical Reports
A companion paper has introduced the Hierarchical PRAM (H-PRAM) model of parallel computation, which achieves a good balance between simplicity of usage and reflectivity of realistic parallel computers. In this paper, we demonstrate the usage of the model by designing and analyzing various algorithms for computing the complete binary tree, and the FFT/butterfly graph. By concentrating on two problems, we are able to demonstrate the results of different combinations of organizational strategies and different types of sub-models of the H-PRAM. The philosophy in algorithm design is to maximize the number of processors P that are efficiently usable with respect to …
Resolution Without Unification, William C. Purdy
Resolution Without Unification, William C. Purdy
Electrical Engineering and Computer Science - Technical Reports
Resolution as an inference procedure forms the basis of most automated theorem-proving and reasoning systems. The most costly constituent of the resolution procedure in its conventional form is unification. This paper describes PCS, a first-order language in which resolution-based inference can be conducted without unification. PCS resembles the language of elementary logic with the difference that singular predicates supplant individual constants and functions. The result is a uniformity in the treatment of individual constants, functions and predicates. An especially costly part of unification is the occur check. Since unification is unnecessary for resolution in PCS, the occur check is completely …
On The Question ‘Do We Need Identity?’, William C. Purdy
On The Question ‘Do We Need Identity?’, William C. Purdy
Electrical Engineering and Computer Science - Technical Reports
Sommers posed the question 'Do We Need Identity?' and answered in the negative. According to Sommers, the need for a special identity relation resulted from an arbitrary distinction between concept and object introduced by Frege and retained in modern predicate logic (MPL). This is reflected in the syntactic distinction between predicate and individual constant. Traditional formal logic (TFL) does not respect this distinction and, as a consequence, has no need for a special identity relation. But Sommers' position has not gained general acceptance. On the contrary, it has received considerable criticism. While it is conceded that TFL can express the …
Distributed Memory Compiler Methods For Irregular Problems -- Data Copy Reuse And Runtime Partitioning, Raja Das, Ravi Ponnusamy, Joel Saltz, Dimitri Mavriplis
Distributed Memory Compiler Methods For Irregular Problems -- Data Copy Reuse And Runtime Partitioning, Raja Das, Ravi Ponnusamy, Joel Saltz, Dimitri Mavriplis
Electrical Engineering and Computer Science - Technical Reports
This paper outlines two methods which we believe will play an important role in any distributed memory compiler able to handle sparse and unstructured problems. We describe how to link runtime partitioners to distributed memory compilers. In our scheme, programmers can implicitly specify how data and loop iterations are to be distributed between processors. This insulates users from having to deal explicitly with potentially complex algorithms that carry out work and data partitioning. We also describe a viable mechanism for tracking and reusing copies of off-processor data. In many programs, several loops access the same off-processor memory locations. As long …
Structural Changes And Enhancements In Dnase I Footprinting Experiments?, Jerry Goodisman, James C. Dabrowiak
Structural Changes And Enhancements In Dnase I Footprinting Experiments?, Jerry Goodisman, James C. Dabrowiak
Chemistry - All Scholarship
In footprinting experiments, an increase in DNA cleavage with addition of ligand to a system may be due to a ligand-induced structural change. Ligand binding also enhances cleavage by displacing the cleavage agent from ligand-binding sites, thus increasing its concentration elsewhere. The theory and characteristics of this mass-action enhancement are given, and it is shown how it may be recognized. Results of DNase I footprinting of small oligomers, with actinomycin D as ligand, are analyzed to reveal which enhancements are due to mass action, and which can reasonably be ascribed to structural changes. Patterns in the footprinting plots from our …
Site-Specific Binding Constants For Actinomycin D On Dna Determined From Footprinting Studies, Jerry Goodisman, Robert Rehfuss, Brian Ward, James C. Dabrowiak
Site-Specific Binding Constants For Actinomycin D On Dna Determined From Footprinting Studies, Jerry Goodisman, Robert Rehfuss, Brian Ward, James C. Dabrowiak
Chemistry - All Scholarship
We report site-specific binding constants for the intercalating anticancer drug actinomycin D (Act-D), binding to a 139-base-pair restriction fragment from pBR 322 DNA. The binding constants are derived from analysis of footprinting experiments, in which the radiolabeled 139-mer is cleaved using DNase I, the cleavage products undergo gel electrophoresis, and, from the gel autoradiogram, spot intensities, proportional to amounts of cleaved fragments, are measured. A bound drug prevents DNase I from cleaving at -7 bonds, leading to decreased amounts of corresponding fragments. With the radiolabel on the 3’ end of the noncoding strand (A-label), we measured relative amounts of 54 …
Binary Perfect Weighted Coverings (Pwc) I. The Linear Case, G. D. Cohen, S. N. Litsyn, H. F. Mattson Jr
Binary Perfect Weighted Coverings (Pwc) I. The Linear Case, G. D. Cohen, S. N. Litsyn, H. F. Mattson Jr
Electrical Engineering and Computer Science - Technical Reports
This paper deals with an extension of perfect codes to fractional (or weighted) coverings. We shall derive a Lloyd theorem --- a strong necessary condition of existence---and start a classification of these perfect coverings according to their diameter. We illustrate by pointing to list decoding.
On Perfect Weighted Coverings With Small Radius, G. D. Cohen, S. N. Litsyn, H. F. Mattson Jr
On Perfect Weighted Coverings With Small Radius, G. D. Cohen, S. N. Litsyn, H. F. Mattson Jr
Electrical Engineering and Computer Science - Technical Reports
We extend the results of our previous paper [8] to the nonlinear case: The Lloyd polynomial of the covering has at least R distinct roots among 1, ... , n, where R is the covering radius. We investigate PWC with diameter 1, finding a partial characterization. We complete an investigation begun in [8] on linear PMC with distance 1 and diameter 2.
A Comparison Of Load Balancing Algorithms For Parallel Computations, N. Mansouri, Geoffrey C. Fox
A Comparison Of Load Balancing Algorithms For Parallel Computations, N. Mansouri, Geoffrey C. Fox
Electrical Engineering and Computer Science - Technical Reports
Three physical optimization methods are considered in this paper for load balancing parallel computations. These are simulated annealing, genetic algorithms, and neural networks. Some design choices and the inclusion of additional steps lead to new versions of the algorithms with different solution qualities and execution times. The performances of these versions are critically evaluated and compared for test cases with different topologies and sizes. Orthogonal recursive coordinate bisection is also included in the comparison as a typical simple deterministic method. Simulation results show that the algorithms have diverse properties. Hence, different algorithms can be applied to different problems and requirements. …
Parallel Genetic Algorithms With Application To Load Balancing For Parallel Computing, N. Mansouri, Geoffrey C. Fox
Parallel Genetic Algorithms With Application To Load Balancing For Parallel Computing, N. Mansouri, Geoffrey C. Fox
Electrical Engineering and Computer Science - Technical Reports
A new coarse grain parallel genetic algorithm (PGA) and a new implementation of a data-parallel GA are presented in this paper. They are based on models of natural evolution in which the population is formed of discontinuous or continuous subpopulations. In addition to simulating natural evolution, the intrinsic parallelism in the two PGA's minimizes the possibility of premature convergence that the implementation of classic GA's often encounters. Intrinsic parallelism also allows the evolution of fit genotypes in a smaller number of generations in the PGA's than in sequential GA's, leading to superlinear speed-ups. The PGA's have been implemented on a …
Surface Tension Of A Charged And Polarized System, Jerry Goodisman
Surface Tension Of A Charged And Polarized System, Jerry Goodisman
Chemistry - All Scholarship
Usually, the formula for the surface tension of a planar charged and polarized interface is obtained from that for a system involving only short-range forces, y = - dz [p - px(z)] by replacing the tangential pressure p , by p , + E2/8u. Problems with this include (a) p, is no longer explicitly defined, (b) the electrostatic stress term E2/8 pi is not correct in general but only if polarization is proportional to density of polarizable species, (c) the derivation of the formula in terms of p and p, involves calculating the work to expand a volume containing the …
Explicit Clock Temporal Logic In Timing Constraints For Real-Time Systems, S. Ramanna, J. F. Peters Iii
Explicit Clock Temporal Logic In Timing Constraints For Real-Time Systems, S. Ramanna, J. F. Peters Iii
Electrical Engineering and Computer Science - Technical Reports
A form of explicit clock temporal logic (called TLrt) useful in specifying timing constraints on controller actions, a real-time database (rtdb) items, and constraints in a real-time constraint base (rtcb), is presented. Timing as well as other forms of constraints are stored in the rtcb. A knowledge-based approach to ensure the integrity of information in an rtdb is given. The rtcb is realized as a logic program called Constrainer, which is a historyless integrity checker for a real-time database. The consistency and integrity issues for an rtcb and rtdb are investigated. The formal bases for a temporally complete rtdb and …
An Improved Algorithm For Neural Network Classification Of Imbalanced Training Sets, Rangachari Anand, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka
An Improved Algorithm For Neural Network Classification Of Imbalanced Training Sets, Rangachari Anand, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka
Electrical Engineering and Computer Science - Technical Reports
In this paper, we analyze the reason for the slow rate of convergence of net output error when using the backpropagation algorithm to train neural networks for a two-class problems in which the numbers of exemplars for the two classes differ greatly. This occurs because the negative gradient vector computed by backpropagation for an imbalanced training set does not point initially in a downhill direction for the class with the smaller number of exemplars. Consequently, in the initial iteration, the net error for the exemplars in this class increases significantly. The subsequent rate of convergence of the net error is …
Semi-Distributed Load Balancing For Massively Parallel Multicomputer Systems, Ishfaq Ahmad, Arif Ghafoor
Semi-Distributed Load Balancing For Massively Parallel Multicomputer Systems, Ishfaq Ahmad, Arif Ghafoor
Electrical Engineering and Computer Science - Technical Reports
This paper presents a semi-distributed approach, for load balancing in large parallel and distributed systems, which is different from the conventional centralized and fully distributed approaches. The proposed strategy uses a two-level hierarchical control by partitioning the interconnection structure of a distributed or multiprocessor system into independent symmetric regions (spheres) centered at some control points. The central points, called schedulers, optimally schedule tasks within their spheres and maintain state information with low overhead. We consider interconnection structures belonging to a number of families of distance transitive graphs for evaluation, and using their algebraic characteristics, show that identification of spheres and …
Nonlinear System Identification Using Recurrent Networks, Hyungkeun Lee, Y. Park, Kishan Mehrotra, Sanjay Ranka
Nonlinear System Identification Using Recurrent Networks, Hyungkeun Lee, Y. Park, Kishan Mehrotra, Sanjay Ranka
Electrical Engineering and Computer Science - Technical Reports
This paper presents empirical results on the application of neural networks to system identification and inverse system identification. Recurrent and Feedforward network models are used to build an emulator of a simple nonlinear gantry crane system, and for the inverse dynamics of the system. Recurrent networks were observed to perform slightly better than feedforward networks for these problems.
A Generic Multiplication Pipeline, Per Brinch Hansen
A Generic Multiplication Pipeline, Per Brinch Hansen
Electrical Engineering and Computer Science - Technical Reports
This paper illustrates the benefits of developing generic algorithms for parallel programming paradigms which can be adapted to different applications. We consider a combinatorial problem called tuple multiplication. This paradigm includes matrix multiplication and the all-pairs shortest paths problem as special cases. We develop a generic pipeline for tuple multiplication. From the generic algorithm we derive pipelines for matrix multiplication and shortest paths computation by making substitutions of data types and functions. The performance of the matrix multiplication pipeline is analyzed and measured on a Computing Surface.
Constructing Real-Time Systems From Temporal I/O Automata, J. F. Peters Iii, S. Ramanna
Constructing Real-Time Systems From Temporal I/O Automata, J. F. Peters Iii, S. Ramanna
Electrical Engineering and Computer Science - Technical Reports
A new class of communicating automata called Temporal Input/Output Automata (TAi/os) is introduced. A TAi/o is a predicate automaton used to specify real-time systems. The specification provided by a TAi/o includes state predicates with proof expressions and abstract program syntax as attributes. An abstract program is extracted during a constructive proof of the specification using the proof expressions. A TAi/o specification also includes hard, real-time constraints on program behavior. The predictability of deterministic, temporally complete TAi/o is investigated. The formulation of real-time system transductions and transduction rules for TAi/os in explicit clock temporal logic is given. An illustration of the …
The Complexity Of Local Stratification, Peter Cholak, Howard A. Blair
The Complexity Of Local Stratification, Peter Cholak, Howard A. Blair
Electrical Engineering and Computer Science - Technical Reports
The class of locally stratified logic programs is shown to be Π11-complete by the construction of a reducibility of the class of infinitely branching nondeterministic finite register machines.nondeterministic finite register machines.
Fault-Tolerant Load Management For Real-Time Distributed Computer Systems, Arif Ghafoor, Ishfaq Ahmad
Fault-Tolerant Load Management For Real-Time Distributed Computer Systems, Arif Ghafoor, Ishfaq Ahmad
Electrical Engineering and Computer Science - Technical Reports
This paper presents a fault-tolerant scheme applicable to any decentralized load balancing algorithms used in soft real-time distributed systems. Using the theory of distance-transitive graphs for representing topologies of these systems, the proposed strategy partitions these systems into independent symmetric regions (spheres) centered at some control points. These central points, called fault-control points, provide a two-level task redundancy and efficiently re-distribute the load of failed nodes within their spheres. Using the algebraic characteristics of these topologies, it is shown that the identification of spheres and fault-control points is, in general, is an NP-complete problem. An efficient solution for this problem …
A Variable-Free Logic For Mass Terms, William C. Purdy
A Variable-Free Logic For Mass Terms, William C. Purdy
Electrical Engineering and Computer Science - Technical Reports
This paper presents a logic appropriate for mass terms, that is, a logic that does not presuppose interpretation in discrete models. Models may range from atomistic to atomless. This logic is a generalization of the author's work on natural language reasoning. The following claims are made for this logic. First, absence of variables makes it simpler than more conventional formalizations based on predicate logic. Second, capability to deal effectively with discrete terms, and in particular with singular terms, can be added to the logic, making it possible to reason about discrete entities and mass entities in a uniform manner. Third, …
A Sixteen-Valued Algorithm For Test Generation In Combinational Circuits, Akhtar Uz Zaman, M. Ali, Carlos R.P. Hartmann
A Sixteen-Valued Algorithm For Test Generation In Combinational Circuits, Akhtar Uz Zaman, M. Ali, Carlos R.P. Hartmann
Electrical Engineering and Computer Science - Technical Reports
A 16-valued logic system for testing combinational circuits is presented. This logic system has been used to develop SIMPLE, an efficient test generation algorithm for single stuck-at faults. The proposed scheme for testing stuck-at faults is based on imposing all the constraints that must be satisfied in order to sensitize a path from a fault site to a primary output. Consequently all deterministic implications are fully considered prior to the enumeration process. The resulting ability to identify inconsistencies prior to enumeration improves the possibility of quicker identification of redundant faults. In order to prune the search space we have introduced …
An Evolutionary Approach To Load Balancing Parallel Computations, N. Mansouri, Geoffrey C. Fox
An Evolutionary Approach To Load Balancing Parallel Computations, N. Mansouri, Geoffrey C. Fox
Electrical Engineering and Computer Science - Technical Reports
We present a new approach to balancing the workload in a multicomputer when the problem is decomposed into subproblems mapped to the processors. It is based on a hybrid genetic algorithm. A number of design choices for genetic algorithms are combined in order to ameliorate the problem of premature convergence that is often encountered in the implementation of classical genetic algorithms. The algorithm is hybridized by including a hill climbing procedure which significantly improves the efficiency of the evolution. Moreover, it makes use of problem specific information to evade some computational costs and to reinforce favorable aspects of the genetic …