Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Keyword
-
- Mapping (2)
- Active Messages (1)
- Algorithm (1)
- Asynchronous communication (1)
- Communication latency (1)
-
- Connection machine (1)
- Data locality (1)
- Data parallel (1)
- Distributed scheduling (1)
- Interference (1)
- Interrupt handler (1)
- Irregularity (1)
- Link and node contention (1)
- Load balancing (1)
- Locality-based mapping (1)
- Loosely synchronous communication (1)
- Message passing (1)
- Node contention (1)
- Partitioners (1)
- Personalized communication (1)
- Probabilistic analysis (1)
- Programming languages (1)
- Region growing (1)
- Remapping partitioners (1)
- Runtime and static scheduling (1)
- Split and merge (1)
- Storage variables (1)
- Unstructured communication (1)
- Unstructured grids (1)
Articles 1 - 6 of 6
Full-Text Articles in Physical Sciences and Mathematics
Fast Mapping And Remapping Algorithms For Irregular And Adaptive Problems, Chao Wei Ou, Sanjay Ranka, Geoffrey C. Fox
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.
A Model For Syntactic Control Of Interference, Peter W. O'Hearn
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 …
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
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.
Static And Runtime Scheduling Of Unstructured Communication, Sanjay Ranka, Jyu-Chun Wang
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 …
Distributed Scheduling Of Unstructured Collective Communication On The Cm-5 (1993), Jyu-Chun Wang, Tseng-Hui Lin, Sanjay Ranka
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.
Solving The Region Growing Problem On The Connection Machine, Nawal Copty, Sanjay Ranka, Geoffrey C. Fox, Ravi Shankar
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.