Athapascan-1: On-line building data flow graph in a parallel language
- 27 November 2002
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
In order to achieve practical efficient execution on a parallel architecture, a knowledge of the data dependencies related to the application appears as the key point for building an efficient schedule. By restricting accesses in shared memory, we show that such a data dependency graph can be computed on-line on a distributed architecture. The overhead introduced is bounded with respect to the parallelism expressed by the user: each basic computation corresponds to a user-defined task, each data-dependency to a user-defined data structure. We introduce a language named Athapascan-1 that allows built a graph of dependencies from a strong typing of shared memory accesses. We detail compilation and implementation of the language. Besides, the performance of a code (parallel time, communication and arithmetic works, memory space) are defined from a cost model without the need of a machine model. We exhibit efficient scheduling with respect to these costs on theoretical machine models.Keywords
This publication has 8 references indexed in Scilit:
- Space-Efficient Scheduling of Multithreaded ComputationsSIAM Journal on Computing, 1998
- Efficient PRAM simulation on a distributed memory machineAlgorithmica, 1996
- Programming parallel algorithmsCommunications of the ACM, 1996
- Provably efficient scheduling for languages with fine-grained parallelismPublished by Association for Computing Machinery (ACM) ,1995
- A bridging model for parallel computationCommunications of the ACM, 1990
- How to emulate shared memoryPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1987
- Parallelism in random access machinesPublished by Association for Computing Machinery (ACM) ,1978
- Bounds on Multiprocessing Timing AnomaliesSIAM Journal on Applied Mathematics, 1969