Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Keyword
-
- Algol-like languages (2)
- Interference control (2)
- Programming languages (2)
- Algol (1)
- Bounded traffic (1)
-
- Communication-efficient algorithms (1)
- External data redistribution (1)
- Functional languages (1)
- Functor-category approach (1)
- Functors (1)
- Graph partition (1)
- Graph partitioning (1)
- Heterogeneous computing (1)
- Hyperarithmetic set (1)
- Imperative languages (1)
- Imperative programs (1)
- Irregular problems (1)
- Kripke logic relations (1)
- Locally stratified programs (1)
- Logic relations (1)
- Logics and meanings of programs (1)
- Loosely synchronous communication (1)
- Lotka Volterra systems (1)
- Many-to-many communication (1)
- Message size variance (1)
- Network of workstations (1)
- Node contention (1)
- Non-uniform message size (1)
- Nonuniform environments (1)
- Nonuniform machines (1)
Articles 1 - 12 of 12
Full-Text Articles in Physical Sciences and Mathematics
Many-To-Many Personalized Communication With Bounded Traffic, Sanjay Ranka, Ravi V. Shankar, Khaled A. Alsabti
Many-To-Many Personalized Communication With Bounded Traffic, Sanjay Ranka, Ravi V. Shankar, Khaled A. Alsabti
College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects
This paper presents solutions for the problem of many-to-many personalized communication, with bounded incoming and outgoing traffic, on a distributed memory parallel machine. We present a two-stage algorithm that decomposes the many-to-many communication with possibly high variance in message size into two communications with low message size variance. The algorithm is deterministic and takes time 2tµ (+ lower order terms) when t >= O(p2; + p tau/µ). Here t is the maximum outgoing or incoming traffic at any processor, tau is the startup overhead and µ is the inverse of the data transfer rate. Optimality is achieved when the traffic …
Kripke Logical Relations And Pcf, Peter W. O'Hearn, John G. Riecke
Kripke Logical Relations And Pcf, Peter W. O'Hearn, John G. Riecke
College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects
Sieber has described a model of PCF consisting of continuous functions that are invariant under certain (finitary) logical relations, and shown that it is fully abstract for closed terms of up to third-order types. We show that one may achieve full abstraction at all types using a form of "Kripke logical relations" introduced by Jung and Tiuryn to characterize λ definability.
Objects, Interference, And The Yoneda Embedding, Peter W. O'Hearn, Uday S. Reddy
Objects, Interference, And The Yoneda Embedding, Peter W. O'Hearn, Uday S. Reddy
College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects
We present a new semantics for Algol-like languages that combines methods from two prior lines of development: [1] the object-based approach of [28,29], where the meaning of an imperative program is described in terms of sequences of observable actions, and [2] the functor-category approach initiated by Reynolds [31], where the varying nature of the run-time stack is explained using functors from a category of store shapes to a category of cpos. The semantics gives an account of both the phenomena of local state and irreversibility of state change. As an indication of the accuracy obtained, we present a full abstraction …
Syntactic Control Of Interference Revisited, Peter W. O'Hearn, A. J. Power, M. Takeyama, R. D. Tennent
Syntactic Control Of Interference Revisited, Peter W. O'Hearn, A. J. Power, M. Takeyama, R. D. Tennent
College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects
In "Syntactic Control of Interference" (POPL, 1978), J. C. Reynolds proposes three design principles intended to constrain the scope of imperative state effects in Algol-like languages. The resulting linguistic framework seems to be a very satisfactory way of combining functional and imperative concepts, having the desirable attributes of both purely functional languages (such as pcf) and simple imperative languages (such as the language of while programs). However, Reynolds points out that the "obvious" syntax for interference control has the unfortunate property that fi-reductions do not always preserve typings. Reynolds has subsequently presented a solution to this problem (ICALP, 1989), but …
Parametricity And Local Variables, Peter W. O'Hearn, R. D. Tennent
Parametricity And Local Variables, Peter W. O'Hearn, R. D. Tennent
College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects
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 …
Note On Algol And Conservatively Extending Functional Programming, Peter W. O'Hearn
Note On Algol And Conservatively Extending Functional Programming, Peter W. O'Hearn
College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects
A simple Idealized Algol is considered, based on Reynolds's "essence of Algol." It is shown that observational equivalence in this language conservatively extends observational equivalence in its assignment-free functional sublanguage.
Irregular Personalized Communication On Distributed Memory Machines, Sanjay Ranka, Jhy-Chun Wang
Irregular Personalized Communication On Distributed Memory Machines, Sanjay Ranka, Jhy-Chun Wang
College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects
In this paper we present several algorithms for performing all-to-many personalized communication on distributed memory parallel machines. We assume that each processor sends a different message (of potentially different size) to a subset of all the processors involved in the collective communication. The algorithms are based on decomposing the communication matrix into a set of partial permutations. We study the effectiveness of our algorithms both from the view of static scheduling and from runtime scheduling.
Run-Time Support For Parallelization Of Data-Parallel Applications On Adaptive And Nonuniform Computational Environments, Maher Kaddoura, Sanjay Ranka
Run-Time Support For Parallelization Of Data-Parallel Applications On Adaptive And Nonuniform Computational Environments, Maher Kaddoura, Sanjay Ranka
College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects
In this paper we discuss the runtime support required for the parallelization of unstructured data parallel applications on nonuniform and adaptive environments. The approach presented is reasonably general and is applicable to a wide variety of regular as well as irregular applications. We present performance results for the solution of an unstructured mesh on a cluster of heterogeneous workstations.
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
College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects
This paper completes an investigation of the logical expressibility of finite, locally stratified, general logic programs. We show that every hyperarithmetic set can be defined 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 …
Communication-Efficient And Memory-Bounded External Redistribution, Jang Sun Lee, Sanjay Ranka, Ravi V. Shankar
Communication-Efficient And Memory-Bounded External Redistribution, Jang Sun Lee, Sanjay Ranka, Ravi V. Shankar
College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects
This paper presents communication-efficient algorithms for the external data redistribution problem. Deterministic lower bounds and upper bounds are presented for the number of I/O operations, communication time and the memory requirements of external redistribution. Our algorithms differ from most other algorithms presented for out-of-core applications in that it is optimal (within a small constant factor) not only in the number of I/O operations, but also in the time taken for communication. A coarse-grained MIMD architecture with I/O subsystems attached to each processor is assumed, but the results are expected to be applicable over a wider variety of architectures.
Mapping Unstructured Computational Graphs For Adaptive And Nonuniform Computational Environments, Maher Kaddoura, Chao Wei Ou, Sanjay Ranka
Mapping Unstructured Computational Graphs For Adaptive And Nonuniform Computational Environments, Maher Kaddoura, Chao Wei Ou, Sanjay Ranka
College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects
In this paper we study the problem of mapping a large class of irregular and loosely synchronous data-parallel applications in a nonuniform and adaptive computational environment. The computational structure of these applications can be described in terms of a computational graph, where nodes of the graph represent computational tasks and edges describe the communication between tasks. Parallelization of these applications on nonuniform computational environments requires partitioning the graph among the processors in such fashion that the computation load on each node is proportional to its computational power, while communication is minimized. We discuss the applicability of current methods for graph …
Optimization Using Replicators, Anil Ravindran Menon, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka
Optimization Using Replicators, Anil Ravindran Menon, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka
College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects
Replicator systems are among the simplest complex systems and can be considered to be at the foundation of many popularly used models ranging from theories of evolution and neurobiology to sociobiology and ecology. This paper presents the first successful application 2 of replicators to optimization problems. For a graph bi-partitioning problem with 50,000 nodes and 300,000 edges, for instance, close to optimal solutions were obtained in a few hundred iterations. Replicators provide a potentially powerful new tool to solve other optimization problems as well.