Open Access. Powered by Scholars. Published by Universities.®

Physical Sciences and Mathematics Commons™

Open Access. Powered by Scholars. Published by Universities.®

1993

Computer Sciences

Syracuse University

Articles 1 - 26 of 26

Full-Text Articles in Physical Sciences and Mathematics

Genetic Algorithms For Soft Decision Decoding Of Linear Block Codes, Harpal Maini, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka Nov 1993

Genetic Algorithms For Soft Decision Decoding Of Linear Block Codes, Harpal Maini, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka

Electrical Engineering and Computer Science - Technical Reports

Soft-decision decoding is an NP-hard problem of great interest to developers of communication systems. We show that this problem is equivalent to the problem of optimizing Walsh polynomials. We present genetic algorithms for soft-decision decoding of binary linear block codes and compare the performance with various other decoding algorithms. Simulation results show that our algorithms achieve bit-error-probabilities as low as 0.00183 for a [104, 52] code with a low signal-to-noise ratio of 2.5 dB, exploring only 30,000 codewords, whereas the search space contains 4.5 x 1015 codewords. We define a new crossover operator that exploits domain-specific information and compare it …

Go to article

Parametricity And Local Variables, Peter W. O'Hearn, R. D. Tennent Oct 1993

Parametricity And Local Variables, Peter W. O'Hearn, R. D. Tennent

Electrical Engineering and Computer Science - Technical Reports

We propose that the phenomenon of local state may be understood in terms of Strachey's concept of parametric (i.e., uniform) polymorphism. The intuitive basis for our proposal is the following analogy: a non-local procedure is independent of locally-declared variables in the same way that a parametrically polymorphic function is independent of types to which it is instantiated. A connection between parametricity and representational abstraction was first suggested by J. C. Reynolds. Reynolds used logical relations to formalize this connection in languages with type variables and user-defined types. We use relational parametricity to construct a model for an Algol-like language in …

Go to article

On Inverse Sigmoid Functions, Anil Ravindran Menon, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka Jun 1993

On Inverse Sigmoid Functions, Anil Ravindran Menon, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka

Electrical Engineering and Computer Science - Technical Reports

Networks with sigmoid node functions have been shown to be universal approximators, and can use straightforward implementations of learning algorithms. Mathematically, what is common to different sigmoid functions used by different researchers? We establish a common representation of inverse sigmoid functions in terms of the Guass Hypergeometric function, generalizing different node function formulations. We also show that the continuous Hopfield network equation can be transformed into a Legendre differential equation, without assuming the specific form of the node function; this establishes a link between Hopfield nets and the method of function approximation using Legendre polynomials

Go to article

Putting Humpty-Dumpty Together Again: Reconstructing Functions From Their Projections., Anil Ravindran Menon, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka Jun 1993

Putting Humpty-Dumpty Together Again: Reconstructing Functions From Their Projections., Anil Ravindran Menon, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka

Electrical Engineering and Computer Science - Technical Reports

We present a problem decomposition approach to reduce neural net training times. The basic idea is to train neural nets in parallel on marginal distributions obtained from the original distribution (via projection), and then reconstruct the original table from the marginals (via a procedure similar to the join operator in database theory). A function is said to be reconstructible, if it may be recovered without error from its projections. Most distributions are non-reconstructible. The main result of this paper is the Reconstruction theorem, which enables non-reconstructible functions to be expressed in terms of reconstructible ones, and thus facilitates the application …

Go to article

A Generalization Of The Trie Data Structure, Richard H. Connelly, F. Lockwood Morris Feb 1993

A Generalization Of The Trie Data Structure, Richard H. Connelly, F. Lockwood Morris

Electrical Engineering and Computer Science - Technical Reports

Tries, a form of string-indexed look-up structure, are generalized to permit indexing by terms built according to an arbitrary signature. The construction is parametric with respect to the type of data to be stored as values; this is essential, because the recursion which defines tries appeals from one value type to others. "Trie" (for any fixed signature) is then a functor, and the corresponding look-up function is a natural isomorphism. The trie functor is in principle definable by the "initial fixed point" semantics of Smyth and Plotkin. We simplify the construction, however, by introducing the "category-cpo", a class of category …

Go to article

Fast Mapping And Remapping Algorithms For Irregular And Adaptive Problems, Chao Wei Ou, Sanjay Ranka, Geoffrey C. Fox Jan 1993

Fast Mapping And Remapping Algorithms For Irregular And Adaptive Problems, Chao Wei Ou, Sanjay Ranka, Geoffrey C. Fox

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

This paper describes the performance of locality-based mapping and remapping partitioners for unstructured grids. We show that the algorithm produces good mappings at a relatively low cost and can be easily parallelized. Further, the algorithm can provide remapping for incremental problems at a fraction of the total cost.

Go to article

A Model For Syntactic Control Of Interference, Peter W. O'Hearn Jan 1993

A Model For Syntactic Control Of Interference, Peter W. O'Hearn

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

Two imperative programming language phrases interfere when one writes to a storage variable that the other reads from or writes to. Reynolds has described an elegant linguistic approach to controlling interference in which a refinement of typed λ-calculus is used to limit sharing of storage variables; in particular, different identifiers are required never to interfere. This paper examines semantic foundations of the approach. We describe a category that has (an abstraction of) interference information built into all objects and maps. This information is used to define a “tensor” product whose components are required never to interfere. Environments are defined using …

Go to article

A Probabilistic Analysis Of A Locality Maintaining Load Balancing Algorithm, Kishan Mehrotra, Sanjay Ranka, Jhy-Chun Wang Jan 1993

A Probabilistic Analysis Of A Locality Maintaining Load Balancing Algorithm, Kishan Mehrotra, Sanjay Ranka, Jhy-Chun Wang

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

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.

Go to article

Static And Runtime Scheduling Of Unstructured Communication, Sanjay Ranka, Jyu-Chun Wang Jan 1993

Static And Runtime Scheduling Of Unstructured Communication, Sanjay Ranka, Jyu-Chun Wang

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

With the advent of new routing methods, the distance to which a message is sent is becoming relatively less and less important. Thus assuming no link contention, permutation seems to be an efficient collective communication primitive. All-to-many communication is required for solving a large class of irregular and loosely synchronous problems on distributed memory MIMD machines. In this paper we present several algorithms for decomposing all-to-many personalized communication into a set of disjoint partial permutations. These partial permutations avoid node contention and/or link contention. We discuss several algorithms and study their effectiveness both from the view of static scheduling as …

Go to article

Distributed Scheduling Of Unstructured Collective Communication On The Cm-5 (1993), Jyu-Chun Wang, Tseng-Hui Lin, Sanjay Ranka Jan 1993

Distributed Scheduling Of Unstructured Collective Communication On The Cm-5 (1993), Jyu-Chun Wang, Tseng-Hui Lin, Sanjay Ranka

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

Parallelization of many irregular applications results in unstructured collective communication. In this paper we present a distributed algorithm for scheduling such communication on parallel machines. We describe the performance of this algorithm on the CM-5 and show that the scheduling algorithm has very small overhead and gives a significant improvement over naive methods.

Go to article

Solving The Region Growing Problem On The Connection Machine, Nawal Copty, Sanjay Ranka, Geoffrey C. Fox, Ravi Shankar Jan 1993

Solving The Region Growing Problem On The Connection Machine, Nawal Copty, Sanjay Ranka, Geoffrey C. Fox, Ravi Shankar

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

This paper presents a parallel algorithm for solving the region growing problem based on the split and merge approach. The algorithm was implemented on the CM-2 and the CM-5 in the data parallel and message passing models. The performance of these implementations is examined and compared.

Go to article

Genetic Algorithms For Stochastic Flow Shop No Wait Scheduling, Harpal Maini, Ubirajara R. Ferreira Jan 1993

Genetic Algorithms For Stochastic Flow Shop No Wait Scheduling, Harpal Maini, Ubirajara R. Ferreira

Electrical Engineering and Computer Science - Technical Reports

ln this paper we present Genetic Algorithms - evolutionary algorithms based on an analogy with natural selection and survival of the fittest - applied to an NP Complete combinatorial optimization problem: minimizing the makespan of a Stochastic Flow Shop No Wait (FSNW) schedule. This is an important optimization criteria in real-world situations and the problem itself is of practical significance. We restrict our applications to the three machine flow shop no wait problem which is known to be NP complete. The stochastic hypothesis is that the processing times of jobs are described by normally distributed random variables. We discuss how …

Go to article

Binary Resolution In Surface Reasoning, William C. Purdy Jan 1993

Binary Resolution In Surface Reasoning, William C. Purdy

Electrical Engineering and Computer Science - Technical Reports

Intuition suggests the hypothesis that everyday human reasoning is conducted in the written or spoken natural language, rather than in some disparate representation into which the surface language is translated. An examination of human reasoning reveals patterns of inference that parallel binary resolution. But any standard implementation of resolution requires Skolemization. Skolemization would seem an unlikely component of human reasoning. This appears to contradict the hypothesis that human reasoning takes place at the surface. To reconcile these observations, this paper develops a new rule of inference, which operates on surface expressions directly. This rule is shown to produce results which …

Go to article

Fortran 90d/Hpf Compiler For Distributed Memory Mimd Computers: Design, Implementation, And Performance Results, Zeki Bozkus, Alok Choudhary, Geoffrey C. Fox, Tomasz Haupt Jan 1993

Fortran 90d/Hpf Compiler For Distributed Memory Mimd Computers: Design, Implementation, And Performance Results, Zeki Bozkus, Alok Choudhary, Geoffrey C. Fox, Tomasz Haupt

Northeast Parallel Architecture Center

Fortran 90D/HPF is a data parallel language with special directives to enable users to specify data alignment and distributions. This paper describes the design and implementation of a Fortran90D/HPF compiler. Techniques for data and computation partitioning, communication detection and generation, and the run-time support for the compiler are discussed. Finally, initial performance results for the compiler are presented which show that the code produced by the compiler is portable, yet efficient. We believe that the methodology to process data distribution, computation partitioning, communication system design and the overall compiler design can be used by the implementors of HPF compilers.

Go to article

A Compilation Approach For Fortran 90d/Hpf Compilers On Distributed Memory Mimd Computers, Zeki Bozkus, Alok Choudhary, Geoffrey C. Fox, Tomasz Haupt Jan 1993

A Compilation Approach For Fortran 90d/Hpf Compilers On Distributed Memory Mimd Computers, Zeki Bozkus, Alok Choudhary, Geoffrey C. Fox, Tomasz Haupt

Northeast Parallel Architecture Center

This paper describes a compilation approach for a Fortran 90D/HPF compiler, a source-to-source parallel compiler for distributed memory systems. Different from Fortran 77 parallelizing compilers, a Fortran90D/HPF compiler does not parallelize sequential constructs. Only parallelism expressed by Fortran 90D/HPF parallel constructs is exploited. The methodology of parallelizing Fortran programs such as computation partitioning, communication detection and generation, and the run-time support for the compiler are discussed. An example of Gaussian Elimination is used to illustrate the compilation techniques with performance results.

Go to article

Runtime Compilation Techniques For Data Partitioning And Communication Schedule Reuse, Ravi Ponnusamy, Joel Saltz, Alok Choudhary Jan 1993

Runtime Compilation Techniques For Data Partitioning And Communication Schedule Reuse, Ravi Ponnusamy, Joel Saltz, Alok Choudhary

Northeast Parallel Architecture Center

In this paper, we describe two new ideas by which HPF compiler can deal with irregular computations effectively. The first mechanism invokes a user specified mapping procedure via a set of compiler directives. The directives allow the user to use program arrays to describe graph connectivity, spatial location of army elements and computational load. The second is a simple conservative method that in many cases enables a compiler to recognize that it is possible to reuse previously computed results from inspectors (e.g. communication schedules, loop iteration partitions, information that associates off-processor data copies with on-processor buffer locations). We present performance …

Go to article

Integrating Multiple Programming Paradigms On Connection Machine Cm5 In A Dataflow-Based Software Environment, Gang Cheng, Geoffrey C. Fox, Kim Mills Jan 1993

Integrating Multiple Programming Paradigms On Connection Machine Cm5 In A Dataflow-Based Software Environment, Gang Cheng, Geoffrey C. Fox, Kim Mills

Northeast Parallel Architecture Center

By viewing different parallel programming paradigms as essential heterogeneous approaches in mapping "real-world" problems to parallel systems, we discuss methodologies in integrating multiple programming models on a Connection Machine CM5. In a data flow based integration model built in a visualization software AVS, we demonstrate a simple, effective and modular way to couple sequential, data-parallel and explicit message-passing modules into an integrated programming environment on the CM5.

Go to article

The Multicomputer Toolbox - First-Generation Scalable Libraries, Anthony Skjellum, Alvin Leung, Steven G. Smith, Robert D. Falgout Jan 1993

The Multicomputer Toolbox - First-Generation Scalable Libraries, Anthony Skjellum, Alvin Leung, Steven G. Smith, Robert D. Falgout

Northeast Parallel Architecture Center

"First-generation" scalable parallel libraries have been achieved, and are maturing, within the Multicomputer Toolbox. The Toolbox includes sparse, dense, iterative linear algebra, a stiff ODE/DAE solver, and an open software technology for additional numerical algorithms, plus an inter-architecture Makefile mechanism for building applications. We have devised C-based strategies for useful classes of distributed data structures, including distributed matrices and vectors. The underlying Zipcodemessage passing system has enabled process-grid abstractions of multicomputers, communication contexts, and process groups, all characteristics needed for building scalable libraries, and scalable application software. We describe the data-distribution-independent approach to building scalable libraries, which is needed so …

Go to article

A Message Passing Interface For Parallel And Distributed Computing, Salim Hariri, Jongbaek Park, Fang-Kuo Yu, Manish Parashar Jan 1993

A Message Passing Interface For Parallel And Distributed Computing, Salim Hariri, Jongbaek Park, Fang-Kuo Yu, Manish Parashar

Northeast Parallel Architecture Center

The proliferation of high performance workstations and the emergence of high speed networks have attracted a lot of interest in parallel and distributed computing (PDC). We envision that PDC environments with supercomputing capabilities will be available in the near future. However, a number of hardware and software issues have to be resolved before the full potential of these PDC environments can be exploited. The presented research has the following objectives: (1) to characterize the message-passing primitives used in parallel and distributed computing; (2) to develop a communication protocol that supports PDC; and (3) to develop an architectural support for PDC …

Go to article

Hierarchical Tree-Structures As Adaptive Meshes, David J. Edelsohn Jan 1993

Hierarchical Tree-Structures As Adaptive Meshes, David J. Edelsohn

Northeast Parallel Architecture Center

Introduction: Two basic types of simulations exist for modeling systems of many particles: grid-based (point particles indirectly interacting with one another through the potential calculated from equivalent particle densities on a mesh) and particle-based (point particles directly interacting with a one another through potentials at their positions calculated from the other particles in the system). Grid-based solvers traditionally model continuum problems, such as fluid and gas systems, and mixed particle-continuum systems. Particle-based solvers find more use modeling discrete systems such as stars within galaxies or other rarefied gases. Many different physical systems, including electromagnetic interactions, gravitational interactions, and fluid vortex …

Go to article

An Interpretive Framework For Application Performance Prediction, Manish Parashar, Salim Hariri, Tomasz Haupt, Geoffrey C. Fox Jan 1993

An Interpretive Framework For Application Performance Prediction, Manish Parashar, Salim Hariri, Tomasz Haupt, Geoffrey C. Fox

Northeast Parallel Architecture Center

Software development in parallel/distributed environment is a non-trivial task and depends greatly on the availability of appropriate support in terms of development tools and environments. Performance prediction /evaluation tools form a critical part of any software development environment as they enable the developer to visualize the effects of various design choices on the performance of the application. This paper presents an interpretive model for a source driven performance prediction framework. A prototype framework based on the proposed model has been developed for the iPSC/860 system. Numerical results obtained on this system are presented. These results confirm the potential of interpretive …

Go to article

Complete Exchange On A Wormhole Routed Mesh, Rajeev Thakur, Alok Choudhary, Geoffrey C. Fox Jan 1993

Complete Exchange On A Wormhole Routed Mesh, Rajeev Thakur, Alok Choudhary, Geoffrey C. Fox

Northeast Parallel Architecture Center

The complete exchange (or all-to-all personalized) communication pattern occurs frequently in many important parallel computing applications. We discuss several algorithms to perform complete exchange on a two dimensional mesh connected computer with wormhole routing. We propose algorithms for both powerof -two and non power-of-two meshes as well as an algorithm which works for any arbitrary mesh. We have developed analytical models to estimate the performance of the algorithms on the basis of system parameters. These models take into account the effects of link contention and other characteristics of the communication system. Performance results on the Intel Touchstone Delta are presented …

Go to article

A Methodology For Developing High Performance Computing Models: Storm-Scale Weather Prediction, Nikos Chrisochoides, Kelvin Droegemeier, Geoffrey C. Fox, Kim Mills, Ming Xue Jan 1993

A Methodology For Developing High Performance Computing Models: Storm-Scale Weather Prediction, Nikos Chrisochoides, Kelvin Droegemeier, Geoffrey C. Fox, Kim Mills, Ming Xue

Northeast Parallel Architecture Center

A methodology for developing future generations of a storm-scale weather prediction model for Massively Parallel Processing is described. The forecast model is the Advanced Regional Prediction System (ARPS), a three-dimensional, fully compressible, non-hydrostatic predictive model. In the short term, the computational goals include developing a portable, scalable model for distributed memory SIMD and MIMD architectures, while preserving a high degree of modularity to support rapid design and validation, maintainability, educational goals and operational testing. Longer term computational goals include a parallel adaptive mesh refinement scheme. A FortranD/High Performance Fortran version of the ARPS provides portability in the current version of …

Go to article

Multimedia Object Modelling And Storage Allocation Strategies For Heterogeneous Parallel Access Storage Devices In Real Time Multimedia Computing Systems, C.Y. Roger Chen, Kingsley C. Nwosu, P. B. Berra Jan 1993

Multimedia Object Modelling And Storage Allocation Strategies For Heterogeneous Parallel Access Storage Devices In Real Time Multimedia Computing Systems, C.Y. Roger Chen, Kingsley C. Nwosu, P. B. Berra

Electrical Engineering and Computer Science - All Scholarship

The improvements in disk speeds have not kept up with improvements in processor and memory speeds. Conventional storage techniques, in the face of multimedia data, are inefficient and/or inadequate. Here, an efficient multimedia object allocation strategy is presented. We describe a multimedia object model, the object and storage device characteristics, and the fragmentation strategy. A bipartite graph approach is used for mapping fragments to storage devices and a cost function is used to determine an efficient allocation of an object and to balance the loads on the devices.

Go to article

Architectural Support For High-Performance Distributed Computing, Jongbaek Park, Salim Hariri Jan 1993

Architectural Support For High-Performance Distributed Computing, Jongbaek Park, Salim Hariri

Electrical Engineering and Computer Science - All Scholarship

The emergence of high speed networks and the proliferation of high performance workstations have attracted a lot of interest in workstation-based distributed computing. Current trend in local area networks is toward higher communication bandwidth as we progress from Ethernet networks that operate at 10 Mbit/sec to higher speed networks that can operate in Gbit/sec range. Also, current workstations are capable of delivering tens and hundreds of Megaflops of computing power. By using a cluster of such high-performance workstations and the high-speed networks, a high-performance distributed computing environment could be built in cost-effective manner as an alternative of supercomputing platform. However, …

Go to article

Software And Hardware Support For Workstation-Based, Salim Hariri, Manish Parashar, Jongbaek Park Jan 1993

Software And Hardware Support For Workstation-Based, Salim Hariri, Manish Parashar, Jongbaek Park

Electrical Engineering and Computer Science - All Scholarship

The proliferation of high performance workstations and the emergence of high speed networks have attracted a lot of interest in workstation-based supercomputing. We project that workstation-based environments with supercomputing capabilities will be available in the not-so-distant future. However a number of hardware and software issues have to be resolved before the full potential of these workstation-based supercomputing environments can be exploited. The presented research has two main objectives: (1) to investigate the limitations of communications techniques used in current workstation-based systems and to identify a set of requirements that must be satisfied to achieve workstation-based supercomputing; (2) to use these …

Go to article