Anahy-DVM: um Módulo de Escalonamento Distribuído
Resumo
O uso de aglomerados de computadores para fins de alto desempenho vem aumentando nos últimos anos. Porém, a programação dessas arquiteturas não é trivial. Além de desenvolver a aplicação, detectar e explicitar a concorrência nela existente, o programador também deve implementar o escalonamento de sua aplicação para explorar, efetivamente, o paralelismo da arquitetura. Algumas ferramentas se propõem a solucionar esses problemas, oferecendo recursos de escalonamento de tarefas; entre elas, Anahy. Este trabalho apresenta a implementação de um módulo para Anahy com fins de dotá-la de suporte à execução em ambientes com memória distribuída. Para tanto, seu núcleo executivo foi estendido para que se possa ter acesso às estruturas de dados imprescindíveis à distribuição da carga computacional. Também foi desenvolvido um mecanismo de comunicação para troca de informações entre os nós do aglomerado. Por fim, o módulo desenvolvido é avaliado através de seu uso em uma aplicação sintética.
Referências
R. Blumofe and C. Leiserson. Scheduling multithreaded computations by work stealing. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico., pages 356–368, November 1994.
R. D. Blumofe, C. F. Joerg, B. C. Kuszmaul, C. E. Leiserson, K. H. Randall, and Y. Zhou. Cilk: an efficient multithreaded runtime system. ACM SIGPLAN Notices, 30(8):207–216, Aug. 1995.
G. G. H. Cavalheiro. A general scheduling framework for parallel execution environments. In CCGrid 2001, Brisbane, Australia, May 2001.
G. G. H. Cavalheiro, E. D. Benitez, D. S. Peranconi, and E. Moschetta. Dynamic list scheduling of threads on clusters. In DSM 2006/CCGrid 2006, 2006.
G. G. H. Cavalheiro, E. C. Dall’Agnol, and L. C. Villa Real. Uma biblioteca de processos leves para a implementação de aplicações altamente paralelas. In IV WSCAD, pages 117– 124, São Paulo, Brasil, Nov. 2003.
G. G. H. Cavalheiro, Y. Denneulin, and J.-L. Roch. A general modular specification for distributed schedulers. Lecture Notes in Computer Science, 1470:373–377, 1998.
G. G. H. Cavalheiro, L. P. Gaspary, M. A. Cardozo, and O. C. Cordeiro. Anahy: a programing environment for cluster computing. In VecPar 2006 (A aparecer), 2006.
E. C. Dall’Agnol, L. C. Villa Real, D. S. Peranconi, M. A. Cardozo Jr., and G. G. H. Cavalheiro. Construção de um mecanismo de comunicação para ambientes de processamento de alto desempenho. In V WSCAD, pages 169–175, Foz do Iguaçú, Brasil, Oct. 2004.
D. G. Feitelson. Job scheduling in multiprogrammed parallel systems. IBM Research Report RC 19790 (87657), Aug. 1997.
F. Gallilée, J.-L. Roch, G. G. H. Cavalheiro, and M. Doreille. Athapascan-1: On-line building data flow graph in a parallel language. In PACT’98, pages 88–95, Paris, Oct. 1998.
R. L. Graham. Bounds on multiprocessing timing anomalies. SIAM Journal on Applied Mathematics, 17(2):416–429, Mar. 1969.
T. C. Hu. Parallel sequencing and assembly line problems. Operations Research, 19(6):841–848, 1961.
M. Iverson and F. Ozguner. Dynamic, competitive scheduling of multiple dags in a distributed heterogeneous environment. In HCW’98, page 70, Washington, USA, 1998.
D. S. Peranconi. Alinhamento de Seqüências Biológicas em Arquiteturas com Memória Distribuída. Master’s thesis, PIPCA - Unisinos, São Leopoldo, Brasil, Mar. 2005.
M. C. Rinard and M. S. Lam. The design, implementation, and evaluation of Jade. ACM Transactions on Programming Languages and Systems, 20(3):483–545, May 1998.
M. C. Rinard, D. J. Scales, and M. S. Lam. Jade: A highlevel machine-independent language for parallel programming. Computer, 26(6):28–38, 1993.
R. Sakellariou and H. Zhao. A hybrid heuristic for dag scheduling on heterogeneous systems. ipdps, 02:111b, 2004.
O. Sinnen and L. Sousa. List scheduling: extension for contention awareness and evaluation of node priorities for heterogeneous cluster architectures. Parallel Computing, 30(1):81–101, 2004.
E. Tärnvik. Dynamo - a portable tool for dynamic load balancing on distributed memory multicomputers. In CONPAR’ 92/VAPP V, pages 485–490, London, UK, 1992.
L. G. Valiant. A Bridging Model for Parallel Computation. Communications of the ACM, 33(8):103–111, Aug. 1990.
T. Yang and A. Gerasoulis. DSC: Scheduling parallel tasks on an unbounded number of processors. Technical Report TRCS94-12, 20, 1994.
