LogP Modelling of List Algorithms
Resumo
We present techniques for distributing lists for processing on distributed and shared memory architectures. The LogP cost model is extended for evaluating the schedules for the given problems and architectures. We consider both bounded and unbounded lists. The theoretical results are confirmed by measurements on a KSR-1.
Palavras-chave:
Parallel List Computations, LogP Model, Runtime Predictions and Measurements
Referências
W. Amme, E. Zehendner: Data dependence analysis in programs with pointers. Proc. 6th Workshop on Compilers for Parallel Computers (CPC'96), Aachen, 1996. Konferenzen des Forschungszentrums Jülich. Vol. 21, 1996. p. 371-382.
D. Culler, R. Karp, D. Pallerson, A. Sahay. K. E. Schauser. E. Santos, R. Subramonian. and T. von Eicken. LogP: Towards a realistic model of parallel computation. In 4th ACM SJGPLAN Symposium on Principles and Practice of Parallel Programming (PPOPP 93), pages 1-12. 1993. published in: SIGPLAN Notices (28) 7.
D. Culler, R. Karp, D. Patterson. A. Sahay, K. E. Schauser. E. Santos. R. Subramonian, and T. von Eicke n. LogP: A practical model of parallel computation. Communications of the ACM. 39(11):78-85, 1996.
J. Eisenbiegler, W. Lowe, and A. Wehrenpfennig. On the optimization by redundancy using an extended logp model. In International Conference on Advances in Parallel and Distributed Computing. IEEE Computer Society Press, 1997.
W. Löwe, W Zimmermann. and J. Eisenbiegler. Optimizing parallel programs on machines with expensive communicalion. EUROPAR' 96. Parallel Processing, 1996.
B. Di Martino and G. Ianello. Parallelization of non-simultaneous iteralive methods for systems of linear equations. In LNCS 854. Parallel Processing: CONPAR'94-VAPP VI, pages 254-264. Springcr. 1994.
Kendall Square Research, KSR/Series Parallel Programming, KSR/Series Performance und KSR/Series C Programming
A. Matsumoto, D. S. Han, T. Tsuda: Alias analysis of pointers in Pascal and Fortran 90: dependence analys is between pointer references. Acta Informatica. Vol. 33 (1996) 99- 130.
H. Zima, B. Chapman: Supercompilers for parallel and vector computers. New York: ACM Press, 1990.
D. Culler, R. Karp, D. Pallerson, A. Sahay. K. E. Schauser. E. Santos, R. Subramonian. and T. von Eicken. LogP: Towards a realistic model of parallel computation. In 4th ACM SJGPLAN Symposium on Principles and Practice of Parallel Programming (PPOPP 93), pages 1-12. 1993. published in: SIGPLAN Notices (28) 7.
D. Culler, R. Karp, D. Patterson. A. Sahay, K. E. Schauser. E. Santos. R. Subramonian, and T. von Eicke n. LogP: A practical model of parallel computation. Communications of the ACM. 39(11):78-85, 1996.
J. Eisenbiegler, W. Lowe, and A. Wehrenpfennig. On the optimization by redundancy using an extended logp model. In International Conference on Advances in Parallel and Distributed Computing. IEEE Computer Society Press, 1997.
W. Löwe, W Zimmermann. and J. Eisenbiegler. Optimizing parallel programs on machines with expensive communicalion. EUROPAR' 96. Parallel Processing, 1996.
B. Di Martino and G. Ianello. Parallelization of non-simultaneous iteralive methods for systems of linear equations. In LNCS 854. Parallel Processing: CONPAR'94-VAPP VI, pages 254-264. Springcr. 1994.
Kendall Square Research, KSR/Series Parallel Programming, KSR/Series Performance und KSR/Series C Programming
A. Matsumoto, D. S. Han, T. Tsuda: Alias analysis of pointers in Pascal and Fortran 90: dependence analys is between pointer references. Acta Informatica. Vol. 33 (1996) 99- 130.
H. Zima, B. Chapman: Supercompilers for parallel and vector computers. New York: ACM Press, 1990.
Publicado
29/09/1999
Como Citar
AMME, W.; BRAUN, P.; LÖWE, W.; ZEHENDNER, E..
LogP Modelling of List Algorithms. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 11. , 1999, Natal.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
1999
.
p. 157-163.
DOI: https://doi.org/10.5753/sbac-pad.1999.19785.
