Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Keyword
-
- HPF (3)
- Arrays (2)
- High Performance Fortran (2)
- Algorithms (1)
- Array redistribution (1)
-
- Attributed shape grammars (1)
- BCH code (1)
- BLOCK (1)
- Block codes (1)
- CYCLIC (1)
- Cluster computing (1)
- Cluster management software (1)
- Code tree (1)
- Collaboration (1)
- Commerce (1)
- Communication (1)
- Communication latency (1)
- Communication primitives (1)
- Computational chemistry (1)
- Computational fluid dynamics (1)
- Control flow graph models (1)
- Coordination library (1)
- Data Space Tiling (1)
- Data distribution (1)
- Data partitioning (1)
- Data-parallel applications (1)
- Data-parallel computations (1)
- Data-parallel language (1)
- Decoding (1)
- Development (1)
Articles 1 - 22 of 22
Full-Text Articles in Physical Sciences and Mathematics
Efficient Heuristic Search Algorithms For Soft-Decision Decoding Of Linear Block Codes, Ching-Cheng Shih, C. R. Wulff, Carlos R.P. Hartmann, Chilukuri K. Mohan
Efficient Heuristic Search Algorithms For Soft-Decision Decoding Of Linear Block Codes, Ching-Cheng Shih, C. R. Wulff, Carlos R.P. Hartmann, Chilukuri K. Mohan
Electrical Engineering and Computer Science - Technical Reports
This paper deals with maximum-likelihood soft-decision decoding as well as suboptimal soft-decision decoding of linear block codes. In this paper we present a novel and efficient hybrid decoding algorithm for (n, k) linear block codes. This algorithm consists of three new decoding algorithms: M A*, H*, and Directed Search. It hybridizes these three algorithms to take advantage of their strengths and make the decoding more efficient. The first algorithm, M A*, is a modified Algorithm A* that conducts a heuristic search through a code tree of the transmitted code when the decoding problem is transformed into a problem of graph-search …
Probabilistic Analysis Of The Median Rule: Asymptotics And Applications, Anil Ravindran Menon, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka
Probabilistic Analysis Of The Median Rule: Asymptotics And Applications, Anil Ravindran Menon, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka
Electrical Engineering and Computer Science - Technical Reports
The solution of integer optimization problems by relaxation methods consists of three parts. First, the discrete problem is converted into a continuous optimization problem, which is generally more tractable. Second, the relaxed problem is solved efficiently, yielding a optimal solution in the continuous space. Finally, an assignment procedure is used to map this solution to a "suitable" discrete solution. One heuristic - we call it the relaxation heuristic - that often guides the choice and design of assignment algorithms is: "given a continuous optimal solution, the corresponding integer optimal solution is likely to be nearby" (with respect to some well …
A Library-Based Approach To Task Parallelism In A Data-Parallel Language, Ian Foster, David R. Kohr, Rakesh Krishnaiyer, Alok Choudhary
A Library-Based Approach To Task Parallelism In A Data-Parallel Language, Ian Foster, David R. Kohr, Rakesh Krishnaiyer, Alok Choudhary
College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects
The data-parallel language High Performance Fortran (HPF) does not allow efficient expression of mixed task/data-parallel computations or the coupling of separately compiled data-parallel modules. In this paper, we show how these common parallel program structures can be represented, with only minor extensions to the HPF model, by using a coordination library based on the Message Passing Interface (MPI). This library allows data-parallel tasks to exchange distributed data structures using calls to simple communication functions. We present microbenchmark results that characterize the performance of this library and that quantify the impact of optimizations that allow reuse of communication schedules in common …
Array Decompositions For Nonuniform Computational Environments, Maher Kaddoura, Sanjay Ranka, Albert Wang
Array Decompositions For Nonuniform Computational Environments, Maher Kaddoura, Sanjay Ranka, Albert Wang
College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects
Two-dimensional arrays are useful in a large variety of scientific and engineering applications. Parallelization of these applications requires the decomposition of array elements among different machines. Several data-decomposition techniques have been studied in the literature for machines with uniform computational power. In this paper we develop new methods for decomposing arrays into a cluster of machines with nonuniform computational power. Simulation results show that our methods provide superior decomposition over naive schemes.
Hierarchical Growing Cell Structures, Vanco Burzevski, Chilukuri K. Mohan
Hierarchical Growing Cell Structures, Vanco Burzevski, Chilukuri K. Mohan
College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects
We propose a hierarchical self-organizing neural network ("HiGS") with adaptive architecture and simple topological organization. This network combines features of Fritzke's Growing Cell Structures and traditional hierarchical clustering algorithms. The height and width of the tree structure depend on the user-specified level of error desired, and the weights in upper layers of the network do not change in later phases of the learning algorithm. Parameters such as node deletion rate are adaptively modified by the learning algorithm.
A Unified Tiling Approach For Out-Of-Core Computations, Rajesh Bordawekar, Alok Choudhary, J. Ramanujam, Mahmut Kandemir
A Unified Tiling Approach For Out-Of-Core Computations, Rajesh Bordawekar, Alok Choudhary, J. Ramanujam, Mahmut Kandemir
College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects
This paper describes a framework by which an out-of-core stencil program written in a data-parallel language can be translated into node programs in a distributed-memory message-passing machine with explicit I/O and communication. We focus on a technique called Data Space Tiling to group data elements into slabs that can fit into memories of processors. Methods to choose legal tile shapes under several constraints and deadlock-free scheduling of tiles are investigated. Our approach is unified in the sense that it can be applied to both FORALL loops and the loops that involve flow-dependences.
Shape Recognition Using Genetic Algorithms, Ender Ozcan, Chilukuri K. Mohan
Shape Recognition Using Genetic Algorithms, Ender Ozcan, Chilukuri K. Mohan
College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects
Shape recognition is a challenging task when shapes overlap, forming noisy, occluded, partial shapes. This paper uses a genetic algorithm for matching input shapes with model shapes described in terms of features such as line segments and angles (extracted using traditional algorithms). The quality of matching is gauged using a measure derived from attributed shape grammars [12, 13]. Preliminary results, using shapes with about 30 features each, are extremely encouraging.
Unsupervised Algorithms For Learning Emergent Spatio-Temporal Correlations, Chaitanya Tumuluri
Unsupervised Algorithms For Learning Emergent Spatio-Temporal Correlations, Chaitanya Tumuluri
Electrical Engineering and Computer Science - Technical Reports
Many applications require the extraction of spatiotemporal correlations among dynamically emergent features of non-stationary distributions. In such applications it is not possible to obtain an a priori analytical characterization of the emergent distribution. This paper extends the Growing Cell Structures (GCS) network and presents two novel (GIST and GEST) networks, which combine unsupervised feature-extraction and Hebbian learning, for tracking such emergent correlations. The networks were successfully tested on the challenging Data Mapping problem, using an execution driven simulation of their implementation in hardware. The results of the simulations show the successful use of the GIST and GEST networks for extracting …
A Review Of Commercial And Research Cluster Management Software, Mark Baker, Geoffrey C. Fox, Hon W. Yau
A Review Of Commercial And Research Cluster Management Software, Mark Baker, Geoffrey C. Fox, Hon W. Yau
Northeast Parallel Architecture Center
In the past decade there has been a dramatic shift from mainframe or ‘host-centric’ computing to a distributed ‘client-server’ approach. In the next few years this trend is likely to continue with further shifts towards ‘network-centric’ computing becoming apparent. All these trends were set in motion by the invention of the mass-reproducible microprocessor by Ted Hoff of Intel some twenty-odd years ago. The present generation of RISC microprocessors are now more than a match for mainframes in terms of cost and performance. The long-foreseen day when collections of RISC microprocessors assembled together as a parallel computer could outperform the vector …
Tests Of Random Number Generators Using Ising Model Simulations, Paul D. Coddington
Tests Of Random Number Generators Using Ising Model Simulations, Paul D. Coddington
Northeast Parallel Architecture Center
Large-scale Monte Carlo simulations require high-quality random number generators to ensure correct results. The contrapositive of this statement is also true – the quality of random number generators can be tested by using them in large-scale Monte Carlo simulations. We have tested many commonly used random number generators with high precision Monte Carlo simulations of the 2-d Ising model using the Metropolis, Swendsen-Wang, and Wolff algorithms. This work is being extended to the testing of random number generators for parallel computers. The results of these tests are presented, along with recommendations for random number generators for high-performance computers, particularly for …
An Application Perspective On High-Performance Computing And Communications, Geoffrey C. Fox
An Application Perspective On High-Performance Computing And Communications, Geoffrey C. Fox
Northeast Parallel Architecture Center
We review possible and probable industrial applications of HPCC focusing on the software and hardware issues. Thirty-three separate categories are illustrated by detailed descriptions of five areas -- computational chemistry; Monte Carlo methods from physics to economics; manufacturing; and computational fluid dynamics; command and control; or crisis management; and multimedia services to client computers and settop boxes. The hardware varies from tightly-coupled parallel supercomputers to heterogeneous distributed systems. The software models span HPF and data parallelism, to distributed information systems and object/data flow parallelism on the Web. We find that in each case, it is reasonably clear that "HPCC works …
Snap, Crackle, Webwindows!, Geoffrey C. Fox, Wojtek Furmanski
Snap, Crackle, Webwindows!, Geoffrey C. Fox, Wojtek Furmanski
Northeast Parallel Architecture Center
We elaborate the SNAP---Scalable (ATM) Network and (PC) Platforms---view of computing in the year 2000. The World Wide Web will continue its rapid evolution, and in the future, applications will not be written for Windows NT/95 or UNIX, but rather for WebWindows with interfaces defined by the standards of Web servers and clients. This universal environment will support WebTop productivity tools, such as WebWord, WebLotus123, and WebNotes built in modular dynamic fashion, and undermining the business model for large software companies. We define a layered WebWindows software architecture in which applications are built on top of multi-use services. We discuss …
The Distributed Array Descriptor For A Pcrc Hpf Compiler Version 2.0 Sccs-770d, Bryan Carpenter, James Cowie, Donald Leskiw, Xiaoming Li
The Distributed Array Descriptor For A Pcrc Hpf Compiler Version 2.0 Sccs-770d, Bryan Carpenter, James Cowie, Donald Leskiw, Xiaoming Li
Northeast Parallel Architecture Center
We describe a distributed array descriptor that can be used by a runtime supporting HPFlike compilers. This descriptor captures all five types of alignment and BLOCK and CYCLIC distribution as defined in HPF specification. In essence, this descriptor does not distinguish whole array and array sections. Prior to this version, we had versions 1.0, 1.1, and 1.2. This version is not only an update of previous versions, but more importantly it also directly reflects our current practice in an HPF compilation effort.
A Tale Of Two Applications On The Nii, Geoffrey C. Fox
A Tale Of Two Applications On The Nii, Geoffrey C. Fox
Northeast Parallel Architecture Center
We describe the expected capability of the NII (as an evolution of the Internet) interns of five broad service areas---collaboration, multimedia information dissemination, commerce, metacomputing, and Webtop productivity. We illustrate the demands on these services and the technology implications by examination of two application areas---manufacture of complex systems, such as aircraft and crisis management, command and control.
Exploration Of Emerging Hpcn Technologies For Web-Based Distributed Computing, Hon W. Yau, Alvin Leung, Wojtek Furmanski, Geoffrey C. Fox
Exploration Of Emerging Hpcn Technologies For Web-Based Distributed Computing, Hon W. Yau, Alvin Leung, Wojtek Furmanski, Geoffrey C. Fox
Northeast Parallel Architecture Center
The surge in the popularity of the World Wide Web (WWW) has corresponded to a decreasing market for specialised high performance computers. This paper discusses how, by making use of technology developed from the broader end of the computing pyramid, much of the past decade's work in distributed computing can be realised in the context of the larger WWW market. Not only do these new technologies offer fresh possibilities, but their pace of development is unlikely to be matched by the traditional high performance research community. A motivating application, discussions of the pertinent emerging technologies, and NPAC's investigations of them, …
Benchmarking The Computation And Communication Performance Of The Cm-5, Kivanc Dincer, Zeki Bozkus, Sanjay Ranka, Geoffrey C. Fox
Benchmarking The Computation And Communication Performance Of The Cm-5, Kivanc Dincer, Zeki Bozkus, Sanjay Ranka, Geoffrey C. Fox
Northeast Parallel Architecture Center
Thinking Machines' CM-5 machine is a distributed-memory, message-passing computer. In this paper we devise a performance benchmark for the base and vector units and the data communication networks of the CM-5 machine. We model the communication characteristics such as communication latency and bandwidths of point-to-point and global communication primitives. We show, on a simple Gaussian elimination code, that an accurate static performance estimation of parallel algorithms is possible by using those basic machine properties connected with computation, vectorization, communication, and synchronization. Furthermore, we describe the embedding of meshes or hypercubes on the CM-5 fat-tree topology and illustrate the performance results …
An Extended Two-Phase Method For Accessing Sections Of Out-Of-Core Arrays, Rajeev Thakur, Alok Choudhary
An Extended Two-Phase Method For Accessing Sections Of Out-Of-Core Arrays, Rajeev Thakur, Alok Choudhary
Electrical Engineering and Computer Science - All Scholarship
A number of applications on parallel computers deal with very large data sets that cannot fit in the main memory. In such applications, data must be stored in files on disks and fetched into memory during program execution. Parallel programs with large out-of-core arrays stored in files must read/write smaller sections of the arrays from/to files. In this paper, we describe a method for accessing sections of out-of-core arrays efficiently. Our method, the extended two phase method, uses collective I/O: Processors cooperate to combine several I/O requests into fewer larger granularity requests, reorder requests so that the file is accessed …
Efficient Algorithms For Array Redistribution, Rajeev Thakur, Alok Choudhary, J. Ramanujam
Efficient Algorithms For Array Redistribution, Rajeev Thakur, Alok Choudhary, J. Ramanujam
Electrical Engineering and Computer Science - All Scholarship
Dynamic redistribution of arrays is required very often in programs on distributed memory parallel computers. This paper presents efficient algorithms for redistribution between different cyclic(k) distributions, as defined in High Performance Fortran. We first propose special optimized algorithms for a cyclic(x) to cyclic(y) redistribution when x is a multiple of y, or y is a multiple of x. We then propose two algorithms, called the GCD method and the LCM method, for the general cyclic(x) to cyclic(y) redistribution when there is no particular relation between x and y. We have implemented these algorithms on the Intel Touchstone Delta, and find …
The Isomorphism Conjecture Fails Relative To A Random Oracle, Stuart A. Kurtz, Stephen R. Mahaney, James S. Royer
The Isomorphism Conjecture Fails Relative To A Random Oracle, Stuart A. Kurtz, Stephen R. Mahaney, James S. Royer
Electrical Engineering and Computer Science - All Scholarship
Berman and Hartmanis [BH77] conjectured that there is a polynomialtime computable isomorphism between any two languages complete for NP with respect to polynomial-time computable many-one (Karp) reductions. Joseph and Young [JY85] gave a structural definition of a class of NP-complete sets---the k-creative sets---and defined a class of sets (the K k f 's) that are necessarily k-creative. They went on to conjecture that certain of these K k f 's are not isomorphic to the standard NP-complete sets. Clearly, the Berman--Hartmanis and Joseph--Young conjectures cannot both be correct. We introduce a family of strong one-way functions, the scrambling functions. If …
Every Polynomial-Time 1-Degree Collapses Iff P = Pspace, Stephen A. Fenner, Stuart A. Kurtz, James S. Royer
Every Polynomial-Time 1-Degree Collapses Iff P = Pspace, Stephen A. Fenner, Stuart A. Kurtz, James S. Royer
Electrical Engineering and Computer Science - All Scholarship
A set A is m-reducible (or Karp-reducible) to B iff there is a polynomial-time computable function f such that, for all x, x ∈ A <--> f (x) ∈ B. Two sets are: (a) 1-equivalent iff each is m-reducible to the other by one-one reductions; (b) p-invertible equivalent iff each is m-reducible to the other by one-one, polynomial-time invertible reductions; and (c) p-isomorphic iff there is an m-reduction from one set to the other that is one-one, onto, and polynomial-time invertible. In this paper we show the following characterization. Theorem : The following are equivalent: (a) P = PSPACE. (b) Every …-->
Compile-Time Performance Prediction Of Hpf/Fortran 90d, Manish Parashar, Salim Hariri
Compile-Time Performance Prediction Of Hpf/Fortran 90d, Manish Parashar, Salim Hariri
Electrical Engineering and Computer Science - All Scholarship
In this paper we present an interpretive approach for accurate and cost-effective performance prediction in a high performance computing environment, and describe the design of a compile-time HPF/Fortran 90D performance prediction framework based on this approach. The performance prediction framework has been implemented as a part of the HPF/Fortran 90D application development environment that integrates it with a HPF/Fortran 90D compiler and a functional interpreter. The current implementation of the environment framework is targeted to the iPSC/860 hypercube multicomputer system. A set of benchmarking kernels and application codes have been used to validate the accuracy, utility, and usability of the …
Hierarchical Control Flow Graph Models, Douglas G. Fritz, Robert G. Sargent
Hierarchical Control Flow Graph Models, Douglas G. Fritz, Robert G. Sargent
Electrical Engineering and Computer Science - All Scholarship
Hierarchical Control Flow Graph Models define a modeling paradigm for discrete event simulation modeling based upon hierarchical extensions to Control Flow Graph Models. Conceptually, models consist of a set of encapsulated, concurrently operating model components that interact solely via message passing. The primary objectives of Hierarchical Control Flow Graph Models are: (1) to facilitate model development by making it easier to develop, maintain, and reuse models and model elements, and (2) to support the flexible and efficient execution of models. Hierarchical Control Flow Graph Models use two complementary types of hierarchical model specification structures, one to specify components and their …