An architecture for P2P bag-of-tasks execution with multiple task allocation policies in desktop grids

详细信息    查看全文

• 作者：Alessandro Ferreira Leite (1)
  Hammurabi Chagas Mendes (2)
  Li Weigang (1)
  Alba Cristina Magalhaes Alves de Melo (1)
  Azzedine Boukerche (3)
  
• 关键词：Grid computing ; Task allocation ; Desktop grids
• 刊名：Cluster Computing
• 出版年：2012
• 出版时间：December 2012
• 年：2012
• 卷：15
• 期：4
• 页码：351-361
• 参考文献：1. Foster, I.: Int. J. High Perform. Comput. Appl. 15(3), 220 (2001) CrossRef
  2. Stephanos, Spinellis, D.: ACM Comput. Surv. 36(4), 335 (2004) CrossRef
  3. Tang, P., Yew, P.C.: In: Intl. Conf. on Parallel Processing, pp.?528-35 (1986)
  4. Foster, I., Iamnitchi, A.: In: 2nd International Workshop on Peer-to-Peer Systems (IPTPSò03), pp.?118-28. (2003)
  5. Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Dover, New York (1998)
  6. Shao, G.: Adaptive scheduling of master/worker applications on distributed computational resources. Ph.D. dissertation, Univ. California at San Diego (2001)
  7. Mendes, H., Weigang, L., Boukerche, A., Melo, A.C.M.A.: In: 6th IFIP International Conference on Network and Parallel Computing, vol.?6, pp.?109-16. (2009) CrossRef
  8. Awan, A., Ferreira, R.A., Jagannathan, S., Grama, A.: Parallel Comput. 32(2), 115 (2006) CrossRef
  9. Blumofe, R.D., Leiserson, C.E.: In: An. Symp. on Found. of Comp. Science, pp.?356-68 (1994)
  10. Gong, L.: IEEE Internet Comput. 5, 88 (2001) CrossRef
  11. Aspnes, J., Shah, G.: ACM Trans. Algorithms 3(4), 37 (2007) CrossRef
  12. Blelloch, G.E., Gibbons, P.B., Matias, Y.: J. ACM 46(2), 281 (1999) CrossRef
  13. Michael, M.M., Vechev, M.T., Saraswat, V.A.: In: PPoPP-9: Proceedings of the 14th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp.?45-4. ACM, New York (2009)
  14. Kumar, V., Grama, A.Y., Vempaty, N.R.: J.?Parallel Distrib. Comput. 22(1), 60 (1994) CrossRef
  15. van Nieuwpoort, R.V., Kielmann, T., Bal, H.E.: In: PPoPP-1: Proceedings of the Eighth ACM SIGPLAN Symposium on Principles and Practices of Parallel Programming, pp.?34-3. ACM, New York (2001) CrossRef
  16. Blumofe, R.D., Lisiecki, P.A.: In: ATEC-7: Proceedings of the Annual Conference on USENIX Annual Technical Conference. USENIX Association, Berkeley (1997)
  17. Gkantsidis, C., Mihail, M., Saberi, A.: In: Proc. of IEEE INFOCOM (2004)
  18. Zhao, B.Y., Huang, L., Stribling, J., Rhea, S.C., Joseph, A.D., Kubiatowicz, J.D.: IEEE J. Sel. Areas Commun. 22(1), 41 (2004) CrossRef
  19. Chakravarti, A., Baumgartner, G., Lauria, M.: IEEE Trans. Syst. Man Cybern., Part A, Syst. Hum. 35(3), 373 (2005) CrossRef
  20. Caromel, D., Costanzo, A.D., Mathieu, C.: Parallel Comput. 33(4-), 275 (2007) CrossRef
  21. B?l?ni, L., Turgut, D., Marinescu, D.C.: Future Gener. Comput. Syst. 22(6), 676 (2006) CrossRef
  22. Edmonds, J., Karp, R.M.: J.?ACM 19(2), 248 (1972)
  23. Dinic, E.A.: Sov. Math. Dokl. 11(5), 1277 (1970)
  24. Goldberg, A.V., Tarjan, R.E.: J.?ACM 35(4), 921 (1988)
  25. Therning, N., Bengtsson, L.: Jalapeno-decentralized grid computing using peer-to-peer technology. In: Proc. of the 2nd Conference on Computing Frontiers (2005)
  
• 作者单位：Alessandro Ferreira Leite (1)
  Hammurabi Chagas Mendes (2)
  Li Weigang (1)
  Alba Cristina Magalhaes Alves de Melo (1)
  Azzedine Boukerche (3)
  
  1. University of Brasilia, Brasilia, Brazil
  2. Brown University, Providence, USA
  3. University of Ottawa, Ottawa, Canada
  
• ISSN：1573-7543

文摘

In this paper, we propose and evaluate a flexible architecture for desktop grids that supports multiple task allocation policies on top of a structured P2P overlay. In our proposal, a?Bag-of-Tasks application is submitted to random nodes and placed in their local queue, that is processed in a FIFO way. When a node becomes idle, a task allocation policy is executed that fetches tasks from remote nodes. The proposed architecture is flexible since it is decoupled from both the P2P middleware and the P2P overlay. A?prototype of the proposed architecture was implemented on top of the JXTA middleware, using the Chord P2P search overlay. The results obtained in a 16-machine heterogeneous desktop grid show that very good performance gains are obtained with multiple task allocation policies. Also, a speedup of 9.85 was achieved for an application composed of 270 network flow balancing tasks, reducing its wallclock execution time from 32.51?min to 3.3?min.