Mapeamento de Programas I3 para Aplicações Anthill Paralelas de Fluxos de Dados baseadas em Filtros
Resumo
Aplicações atuais de mineração de dados, simulação e visualização científica oferecem várias oportunidades de paralelismo por serem iterativas, irregulares e intensivas em termos de EIS (programas l3). O mapeamento e escalonamento de programas l3 para aplicações paralelas de fluxos de dados baseadas em filtros é bastante complexo, pois eles devem considerar aspectos de localidade, dependência de dados e tarefas. A platafoma Anthill provê um modelo de programação adequado para implementação e execução de aplicações paralelas baseadas em filtros. Portanto, neste trabalho, nossos objetivos principais são: a proposta e implementação do algoritmo AnthillPart para o mapeamento de um grafo de tarefas de um programa l3 em filtros; a análise do desempenho das aplicações mapeadas pelo AnthillPart e escalonadas pelo AnthillSched.
Referências
Andrade, N., Cirne, W., Brasileiro, F., Roisenberg, P., "OurGrid: An Approach to Easily Assemble Grids with Equitable Resource Sharing", Job Scheduling Strategies for Parallel Processing, 2003.
Batat, A., Feitelson, D., "Gang Scheduling with Memory Considerations", IEEE International Parallel and Distributed Processing Symposium, 2000, pp. 109-114.
Beaumont, 0., Boudet, V. and Roben, Y., "A Realistic Model and an Efficient Heuristic for Scheduling with Heterogeneous Processors", IEEE Heterogeneous Computing Workshop, 2002.
Beynon, C. M., Ferreira, R., Kurc, T., Sussmany, A. and Saltz, J., "DataCutter: Middleware for Filtering Very Large Scientific Datasets on Archival Storage Systems", IEEE Mass Storage Systems, 2000.
Chapin, S.J. et ai, "Benchmarks and Standards for the Evaluation of Parallel Job Schedulers", Job Scheduling Strategies for Parallel Processing, 1999, pp. 67-90. 151
Feitelson, D. and Nitzberg, B., "Job Characteristics of a Production Parallel Scientific Workload on the NASA Ames iPSC/860", Job Scheduling Strategies for Parallel Processing, 1995, pp. 337-360.
Feitelson, D., Rudolph, L., "Evaluation of Design Choices for Gang Scheduling using Distributed Hierarchical Control", Journal of Parallel and Distributed Computing, 1996, pp. 18-34.
Feitelson, D.G., "A Survey of Scheduling in Multiprogrammed Parallel Systems", Research Repon RC 19790 (87657), IBM T. J. Watson Research Center, 1997.
Paul E. Utgoff and Carla E. Brodley., "An Incremental Method for Finding Multivariate Splits for Decision Trees", Seventh International Conference on Machine Learning, Morgan Kaufman, 1990.
Feitelson, D., Rudolph, L., "Metrics and Benchmarking for Parallel Job Scheduling", Job Scheduling Strategies for Parallel Processing, 1998, pp. 1-24.
Feitelson, D., "Metric and Workload Effects on Computer Systems Evaluation", IEEE Computer, 2003, pp. 18-25.
Franke, H., Jann, J, Moreira, J., Pattnaik, P., Jette, M., "An Evaluation of Parallel Job Scheduling for ASCI BluePacific", ACMIIEEE Conference on Supercomputing, 1999.
Frachtenberg, E., Feitelson, D.G., Petrini, F. and Femandez, J., "Fiexible CoScheduling: Mitigating Load Imbalance and Improving Utilization of Heterogeneous Resources", 17th International Parallel and Distributed Processing Symposium, 2003.
Góes, L. F. W., Martins, C. A. P. S., "Proposta e Desenvolvimento de um Algoritmo Reconfigurável de Escalonamento Paralelo de Tarefas", Dissertação de Mestrado, PUC-Minas, Belo Horizonte, Brasil, 2004.
Góes, L. F. W., Martins, C. A. P. S., "Reconfigurable Gang Scheduling Algorithm", Job Scheduling Strategies for Parallel Processing, 2004.
Góes, L. F. W. et al, "AnthiilSched: A Scheduling Strategy for Irregular and Iterative l/O-Intensive Parallel Jobs", Job Scheduling Strategies for Parallel Processing, 2005.
Nascimento, L.T., Ferreira, R., "LPSched - Escalonamento de Aplicações de Fluxos de Dados em Grids", Dissertação de Mestrado, UFMG, Belo Horizonte, Brasil, 2004.
Neto, E. S., Cime, W., Brasileiro. F., Lima, A., "Exploiting Replication and Data Reuse to Efficiently Anais WSCAD 2005 Schedule Data-intensive Applications on Grids, Job Scheduling Strategies for Parallel Processing, 2004.
Silva, F. A. B., Carvalho, S., Hruschka, E.R., A Scheduling Algorithm for Running Bag-of-Tasks Data Mining Applications on the Grid, EuroPar, 2004.
Streit, A., A Self-Tuning Job Scheduler Family with Dynamic Policy Switching, Job Scheduling Strategies for Parallel Processing, 2002, pp. 1-23.
Veloso, A., Meira, W.. Ferreira, R., et al., Asynchronous and Anticipatory Filter-Stream Based Parallel Algorithm for Frequent ltemset Mining, European Conference on Principies of Data Mining and Knowledge Discovery, 2004.
Wiseman. Y., Feitelson. D., Paired Gang Scheduling, IEEE Transactions Parallel and Distributed Systems, 2003, pp. 581-592.
Zhang, Y., H. Franke, Moreira, E.J., Sivasubramaniam, A., Improving Parallel Job Scheduling by Combining Gang Scheduling and Backfilling Techniques, IEEE International Parallel and Distributed Processing Symposium, 2000.
Zhang, Y., Yang, A., Sivasubramaniam, A., Moreira, J., Gang Scheduling Extensions for I/O Intensive Workloads, Job Scheduling Strategies for Parallel Processing, 2003.
Zhou, B. B., Brent, R. P., Gang Scheduling with a Queue for Large Jobs, IEEE Intemational Parallel and Distributed Processing Symposium, 200 I.
Han, J. & Kamber, M., Data Mining: Concepts and Techniques, Morgan Kaufmann, 2001.
Ferreira, R. A., W. Meira Jr., Guedes, D., Drumond, D. Anthill: A Scalable Run-Time Environment for Data Mining Applications, SBAC-PAD, 2005.
Batat, A., Feitelson, D., "Gang Scheduling with Memory Considerations", IEEE International Parallel and Distributed Processing Symposium, 2000, pp. 109-114.
Beaumont, 0., Boudet, V. and Roben, Y., "A Realistic Model and an Efficient Heuristic for Scheduling with Heterogeneous Processors", IEEE Heterogeneous Computing Workshop, 2002.
Beynon, C. M., Ferreira, R., Kurc, T., Sussmany, A. and Saltz, J., "DataCutter: Middleware for Filtering Very Large Scientific Datasets on Archival Storage Systems", IEEE Mass Storage Systems, 2000.
Chapin, S.J. et ai, "Benchmarks and Standards for the Evaluation of Parallel Job Schedulers", Job Scheduling Strategies for Parallel Processing, 1999, pp. 67-90. 151
Feitelson, D. and Nitzberg, B., "Job Characteristics of a Production Parallel Scientific Workload on the NASA Ames iPSC/860", Job Scheduling Strategies for Parallel Processing, 1995, pp. 337-360.
Feitelson, D., Rudolph, L., "Evaluation of Design Choices for Gang Scheduling using Distributed Hierarchical Control", Journal of Parallel and Distributed Computing, 1996, pp. 18-34.
Feitelson, D.G., "A Survey of Scheduling in Multiprogrammed Parallel Systems", Research Repon RC 19790 (87657), IBM T. J. Watson Research Center, 1997.
Paul E. Utgoff and Carla E. Brodley., "An Incremental Method for Finding Multivariate Splits for Decision Trees", Seventh International Conference on Machine Learning, Morgan Kaufman, 1990.
Feitelson, D., Rudolph, L., "Metrics and Benchmarking for Parallel Job Scheduling", Job Scheduling Strategies for Parallel Processing, 1998, pp. 1-24.
Feitelson, D., "Metric and Workload Effects on Computer Systems Evaluation", IEEE Computer, 2003, pp. 18-25.
Franke, H., Jann, J, Moreira, J., Pattnaik, P., Jette, M., "An Evaluation of Parallel Job Scheduling for ASCI BluePacific", ACMIIEEE Conference on Supercomputing, 1999.
Frachtenberg, E., Feitelson, D.G., Petrini, F. and Femandez, J., "Fiexible CoScheduling: Mitigating Load Imbalance and Improving Utilization of Heterogeneous Resources", 17th International Parallel and Distributed Processing Symposium, 2003.
Góes, L. F. W., Martins, C. A. P. S., "Proposta e Desenvolvimento de um Algoritmo Reconfigurável de Escalonamento Paralelo de Tarefas", Dissertação de Mestrado, PUC-Minas, Belo Horizonte, Brasil, 2004.
Góes, L. F. W., Martins, C. A. P. S., "Reconfigurable Gang Scheduling Algorithm", Job Scheduling Strategies for Parallel Processing, 2004.
Góes, L. F. W. et al, "AnthiilSched: A Scheduling Strategy for Irregular and Iterative l/O-Intensive Parallel Jobs", Job Scheduling Strategies for Parallel Processing, 2005.
Nascimento, L.T., Ferreira, R., "LPSched - Escalonamento de Aplicações de Fluxos de Dados em Grids", Dissertação de Mestrado, UFMG, Belo Horizonte, Brasil, 2004.
Neto, E. S., Cime, W., Brasileiro. F., Lima, A., "Exploiting Replication and Data Reuse to Efficiently Anais WSCAD 2005 Schedule Data-intensive Applications on Grids, Job Scheduling Strategies for Parallel Processing, 2004.
Silva, F. A. B., Carvalho, S., Hruschka, E.R., A Scheduling Algorithm for Running Bag-of-Tasks Data Mining Applications on the Grid, EuroPar, 2004.
Streit, A., A Self-Tuning Job Scheduler Family with Dynamic Policy Switching, Job Scheduling Strategies for Parallel Processing, 2002, pp. 1-23.
Veloso, A., Meira, W.. Ferreira, R., et al., Asynchronous and Anticipatory Filter-Stream Based Parallel Algorithm for Frequent ltemset Mining, European Conference on Principies of Data Mining and Knowledge Discovery, 2004.
Wiseman. Y., Feitelson. D., Paired Gang Scheduling, IEEE Transactions Parallel and Distributed Systems, 2003, pp. 581-592.
Zhang, Y., H. Franke, Moreira, E.J., Sivasubramaniam, A., Improving Parallel Job Scheduling by Combining Gang Scheduling and Backfilling Techniques, IEEE International Parallel and Distributed Processing Symposium, 2000.
Zhang, Y., Yang, A., Sivasubramaniam, A., Moreira, J., Gang Scheduling Extensions for I/O Intensive Workloads, Job Scheduling Strategies for Parallel Processing, 2003.
Zhou, B. B., Brent, R. P., Gang Scheduling with a Queue for Large Jobs, IEEE Intemational Parallel and Distributed Processing Symposium, 200 I.
Han, J. & Kamber, M., Data Mining: Concepts and Techniques, Morgan Kaufmann, 2001.
Ferreira, R. A., W. Meira Jr., Guedes, D., Drumond, D. Anthill: A Scalable Run-Time Environment for Data Mining Applications, SBAC-PAD, 2005.
Publicado
24/10/2005
Como Citar
GÓES, Luís F. W.; GIOVANI, Ítalo; FERREIRA, Renato; MEIRA JR., Wagner.
Mapeamento de Programas I3 para Aplicações Anthill Paralelas de Fluxos de Dados baseadas em Filtros. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 6. , 2005, Rio de Janeiro.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2005
.
p. 145-152.
DOI: https://doi.org/10.5753/wscad.2005.18987.
