Geodesic
Efficient plan for divisible tasks in MapReduce framework
Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, no. 2 (2011), pp. 55-66
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Framework MapReduce allows executing efficiently easily divisible tasks. Although for the group of tasks the task of optimal scheduling is NP-hard itself. Article describes mathematical model of MapReduce framework in two different distributed environments: with and without communication latency. For the environment without communication latency the optimal plan of MapReduce tasks scheduling is offered. For the environment in the presence of communication latency the author estimates the range of values of environment parameters when the offered plan is still efficient.
Keywords: scheduling in distributed environment, scheduling in the presence of communication, optimal scheduling, MapReduce framework. 
@article{VSPUI_2011_2_a5,
     author = {M. A. Panshenskov},
     title = {Efficient plan for divisible tasks in {MapReduce} framework},
     journal = {Vestnik Sankt-Peterburgskogo universiteta. Prikladna\^a matematika, informatika, processy upravleni\^a},
     pages = {55--66},
     year = {2011},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VSPUI_2011_2_a5/}
}
TY  - JOUR
AU  - M. A. Panshenskov
TI  - Efficient plan for divisible tasks in MapReduce framework
JO  - Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ
PY  - 2011
SP  - 55
EP  - 66
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/VSPUI_2011_2_a5/
LA  - ru
ID  - VSPUI_2011_2_a5
ER  - 
%0 Journal Article
%A M. A. Panshenskov
%T Efficient plan for divisible tasks in MapReduce framework
%J Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ
%D 2011
%P 55-66
%N 2
%U http://geodesic.mathdoc.fr/item/VSPUI_2011_2_a5/
%G ru
%F VSPUI_2011_2_a5
M. A. Panshenskov. Efficient plan for divisible tasks in MapReduce framework. Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, no. 2 (2011), pp. 55-66. http://geodesic.mathdoc.fr/item/VSPUI_2011_2_a5/

[1] Ghemawat S., Dean J., “MapReduce: Simplified Data Processing on Large Clusters”, Proceedings of the Sixth Symposium on Operating System Design and Implementation (San Francisco, USA), v. 6, 2004, 137–150

[2] Nemnyugin S. A., Osnovy parallelnogo programmirovaniya s ispolzovaniem MPI http://www.intuit.ru

[3] Jin C., Buyya R., MapReduce programming model for .NET-based distributed computing, Technical Report GRIDS-TR-2008-15. Grid Computing and Distributed Systems Laboratory, The University of Melbourne, Australia, 2008, 10 pp.

[4] Berthold J., Dieterle M., Loogen R., “Implementing parallel google map-reduce in eden”, Lecture Notes in Computer Science, 5704, eds. H. Sips, D. Epema, and H. Lin, Springer-Verlag, 2009, 990–1002 | DOI

[5] Pinedo M., Scheduling: Theory, Algorithms, and Systems, Prentice Hall, Englewood Cliffs, NJ, USA, 1995, 678 pp. | MR | Zbl

[6] Romanovskii I. V., Suboptimalnye resheniya, PetrGU, Petrozavodsk, 1998, 97 pp.

[7] Demyanovich Yu. K., Burova I. G., Algoritmy parallelnykh vychislenii i programmirovanie, (kurs lektsii), SPbGU, Sankt-Peterburg, 1995, 207 pp.

[8] Vakhitov A. T., Granichin O. N., Panshenskov M. A., “Metody otsenivaniya propusknoi sposobnosti kanalov dannykh v raspredelennykh sistemakh”, Neirokompyutery: razrabotka, primenenie, 2009, no. 11, 45–52

[9] Clyde L. Monma, Chris N. Potts, “On the Complexity of Scheduling with Batch Setup Times”, Operations Research, 37:5 (1989), 798–804 | DOI | MR | Zbl

[10] Yu Jia, Buyya Rajkumar, “Workflow Scheduling Algorithms for Grid Computing”, Studies in Computational Intelligence, 146, 2008, 173–214 | DOI | Zbl

[11] Panshenskov M. A., “Adaptivnyi metod upravleniya potokom resheniya izolirovannykh zadanii v parallelnoi vychislitelnoi srede”, Stokhasticheskaya optimizatsiya v informatike, 2008, no. 4, 185–195

[12] Panshenskov M. A., “Dinamicheskoe planirovanie kommunikatsii i metody otsenivaniya propusknoi sposobnosti kanalov dannykh v grid”, Trudy konferentsii «Nauchnyi servis v seti internet: masshtabiruemost, parallelnost, effektivnost», 2009, 403–408

[13] Xhafa F., Carretero J., Barolli L., Durresi A., “Immediate mode scheduling in grid systems”, Int. J. Web and Grid Services, 3:2 (2007), 219–236 | DOI

[14] Xiaoshan HE, Sun Xian-He, von Laszewski Gregor, “QoS Guided Min-Min Heuristic for Grid Task Scheduling”, Computer Science and Technology, 18:4 (2003), 442–451 | DOI | Zbl

[15] Hef Yuxiong,Jing Hsu Wen, Leiserson Charles E., “Provably Efficient Online Non-clairvoyant Adaptive Scheduling”, IEEE Transactions on Parallel and Distributed Systems archive, 19:9 (2008), 1263–1279 | DOI

[16] Agrawal Kunal, He Yuxiong, Jing Hsu Wen, Leiserson Charles E., “Adaptive task scheduling with parallelism feedback”, PPoPP (New York, USA), 2006, 100–109

[17] Eisenbrand F., Rothvo T., “Static-priority Real-time Scheduling: Response Time Computation is NP-hard”, IEEE Real-Time Systems Symposium (RTSS), 2008, 397–406

[18] Hall Leslie A.,Shmoys David B., Wein Joel, “Scheduling to minimize average completion time: off-line and on-line algorithms”, SODA. Society for Industrial and Applied Mathematics, 1996, 142–151 | MR | Zbl

[19] Chekuri C., Motwani R., Natarajan B., Stien C., “Approximation techniques for average completion time scheduling”, SODA. Society for Industrial and Applied Mathematics, 1997, 609–618 | MR

[20] Turek John, Ludwig Walter, Wolf Joel, Fleischer Lisa, Tiwari Prasoon, Glasgow Jason, Schwiegelshohn Uwe, Yu Philip S., “Scheduling parallelizable tasks to minimize average response time”, SPAA, 1994, 200–209

[21] Panshenskov M., Vakhitov A., “Transfer Speed Estimation for Adaptive Scheduling in the Data Grid”, IEEE. Workshops at the Grid and Pervasive Computing Conference, 2009, 58–63 | DOI