On Efficient Load Balancing for Irregular Applications

1. Agha, G.: Actors: A Model of Concurrent Computation in Distributed Systems. The MIT Press (1987)

   Google Scholar 

2. America, P., Rutten, J.: A layered semantics for a parallel object-oriented languages. In: de Bakker, J.W., de Roever, W.-P., Rozenberg, G. (eds.) REX 1990. LNCS, vol. 489, pp. 91–123. Springer, Heidelberg (1991)

   Chapter  Google Scholar 

3. Blumofe, R.D., Joerg, C.F., Kuszmaul, B.C., Leiserson, C.E., Randall, K.H., Zhou, Y.: Cilk: an efficient multithreaded runtime system. In: Proceedings of the Fifth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 1995, pp. 207–216 (1995)

   Google Scholar 

4. Charles, P., Grothoff, C., Saraswat, V., Donawa, C., Kielstra, A., Ebcioglu, K., von Praun, C., Sarkar, V.: X10: an object-oriented approach to non-uniform cluster computing. SIGPLAN Not. 40(10), 519–538 (2005)

   Article  Google Scholar 

5. Cong, G., Kodali, S., Krishnamoorthy, S., Lea, D., Saraswat, V., Wen, T.: Solving large, irregular graph problems using adaptive work-stealing. In: ICPP 2008: Proceedings of the 2008 37th International Conference on Parallel Processing, pp. 536–545. IEEE Computer Society (2008)

   Google Scholar 

6. Feeley, M.: A message passing implementation of lazy task creation. In: Halstead, R.H., Ito, T. (eds.) US/Japan WS 1992. LNCS, vol. 748, pp. 94–107. Springer, Heidelberg (1993)

   Chapter  Google Scholar 

7. Feeley, M.: Lazy remote procedure call and its implementation in a parallel variant of C. In: Queinnec, C., Halstead, R.H., Ito, T. (eds.) PSLS 1995. LNCS, vol. 1068, pp. 3–21. Springer, Heidelberg (1996)

   Chapter  Google Scholar 

8. Frigo, M., Leiserson, C.E., Randall, K.H.: The implementation of the Cilk-5 multithreaded language. ACM SIGPLAN Notices (PLDI 1998) 33(5), 212–223 (1998)

   Article  Google Scholar 

9. Goldstein, S.C., Schauser, K.E., Culler, D.E.: Lazy Threads: Implementing a fast parallel call. Journal of Parallel and Distributed Computing 3(1), 5–20 (1996)

   Article  Google Scholar 

10. Guo, Y., Barik, R., Raman, R., Sarkar, V.: Work-first and help-first scheduling policies for async-finish task parallelism. In: 23rd IEEE International Symposium on Parallel and Distributed Processing (IPDPS 2009), pp. 1–12 (May 2009)

    Google Scholar 

11. Guo, Y., Zhao, J., Cave, V., Sarkar, V.: Slaw: a scalable locality-aware adaptive work-stealing scheduler. In: 24th IEEE International Symposium on Parallel and Distributed Processing (IPDPS 2010), pp. 1–12 (April 2010)

    Google Scholar 

12. Halstead, R.H.: New ideas in parallel Lisp: Language design, implementation, and programming tools. In: Ito, T., Halstead, R.H. (eds.) US/Japan WS 1989. LNCS, vol. 441, pp. 2–57. Springer, Heidelberg (1990)

    Google Scholar 

13. Hiraishi, T., Yasugi, M., Umatani, S., Yuasa, T.: Backtracking-based load balancing. In: Proceedings of the 14th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP 2009), pp. 55–64 (February 2009)

    Google Scholar 

14. Hiraishi, T., Yasugi, M., Yuasa, T.: A transformation-based implementation of lightweight nested functions. IPSJ Digital Courier 2, 262–279 (2006), IPSJ Transactions on Programming 47(SIG 6(PRO 29)), 50–67

    Google Scholar 

15. Honda, K., Tokoro, M.: An object calculus for asynchronous communication. In: America, P. (ed.) ECOOP 1991. LNCS, vol. 512, pp. 133–147. Springer, Heidelberg (1991)

    Chapter  Google Scholar 

16. Intel Corporation: Intel Threading Building Block Tutorial (2007), http://threadingbuildingblocks.org/

17. Michael, M.M., Vechev, M.T., Saraswat, V.A.: Idempotent work stealing. In: Proceedings of the 14th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP 2009), pp. 45–54 (February 2009)

    Google Scholar 

18. Mohr, E., Kranz, D.A., Halstead, R.H.: Lazy task creation: A technique for increasing the granularity of parallel programs. IEEE Transactions on Parallel and Distributed Systems 2(3), 264–280 (1991)

    Article  Google Scholar 

19. Sakai, S., Yamaguchi, Y., Hiraki, K., Kodama, Y., Yuba, T.: An architecture of a dataflow single chip processor. In: Proc. of the 16th Annual International Symposium on Computer Architecture, pp. 46–53 (June 1989)

    Google Scholar 

20. Shibayama, E.: An Object-Based Approach to Modeling Concurrent Systems. Ph.D. thesis, Department of Information Science, The University of Tokyo (1991)

    Google Scholar 

21. Strumpen, V.: Indolent closure creation. Tech. Rep. MIT-LCS-TM-580, MIT (June 1998)

    Google Scholar 

22. Supercomputing Technologies Group: Cilk 5.4.6 Reference Manual. Massachusetts Institute of Technology, Laboratory for Computer Science, Cambridge, Massachusetts, USA

    Google Scholar 

23. Taura, K., Tabata, K., Yonezawa, A.: StackThreads/MP: Integrating futures into calling standards. In: Proceedings of ACM SIGPLAN Symposium on Principles & Practice of Parallel Programming (PPoPP 1999), pp. 60–71 (May 1999)

    Google Scholar 

24. Terauchi, T.: Checking race freedom via linear programming. In: Proceedings of the 2008 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2008, pp. 1–10 (2008)

    Google Scholar 

25. Umatani, S., Yasugi, M., Komiya, T., Yuasa, T.: Pursuing laziness for efficient implementation of modern multithreaded languages. In: Veidenbaum, A., Joe, K., Amano, H., Aiso, H. (eds.) ISHPC 2003. LNCS, vol. 2858, pp. 174–188. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

26. Vandevoorde, M.T., Roberts, E.S.: WorkCrews: An abstraction for controlling parallelism. International Journal of Parallel Programming 17(4), 347–366 (1988)

    Article  Google Scholar 

27. Wagner, D.B., Calder, B.G.: Leapfrogging: A portable technique for implementing efficient futures. In: Proceedings of Principles and Practice of Parallel Programming (PPoPP 1993), pp. 208–217 (1993)

    Google Scholar 

28. Yasugi, M.: A concurrent object-oriented programming language system for highly parallel data-driven computers and its applications. Tech. Rep. 94-7e, Department of Information Science, Faculty of Science, University of Tokyo (April 1994), Doctoral Thesis (March 1994)

    Google Scholar 

29. Yasugi, M., Hiraishi, T., Umatani, S., Yuasa, T.: Parallel graph traversals using work-stealing frameworks for many-core platforms. Journal of Information Processing 20(1), 128–139 (2012)

    Article  Google Scholar 

30. Yasugi, M., Hiraishi, T., Yuasa, T.: Lightweight lexical closures for legitimate execution stack access. In: Mycroft, A., Zeller, A. (eds.) CC 2006. LNCS, vol. 3923, pp. 170–184. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

31. Yonezawa, A. (ed.): ABCL: An Object-Oriented Concurrent System — Theory, Language, Programming, Implementation and Application. The MIT Press (1990)

    Google Scholar 

32. Yonezawa, A., Briot, J.P., Shibayama, E.: Object-oriented concurrent programming in ABCL/1. In: Proc. of ACM Conference on OOPSLA, pp. 258–268 (1986)

    Google Scholar 

Download references