Scheduling divisible MapReduce computations

被引：50

作者：

Berlinska, J. ^{[2
]}

Drozdowski, M. ^{[1
]}

机构：

[1] Poznan Univ Tech, Inst Comp Sci, PL-60965 Poznan, Poland

[2] Adam Mickiewicz Univ, Fac Math & Comp Sci, PL-61614 Poznan, Poland

来源：

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING | 2011年 / 71卷 / 03期

关键词：

Parallel processing; MapReduce; Scheduling; Divisible loads; Performance evaluation; DISTRIBUTED COMPUTATION; TREE NETWORKS; LOADS;

D O I：

10.1016/j.jpdc.2010.12.004

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In this paper we analyze MapReduce distributed computations as a divisible load scheduling problem. The two operations of mapping and reducing can be understood as two divisible applications with precedence constraints. A divisible load model of the computation, and two load partitioning algorithms are proposed. Performance limits of MapReduce computations are investigated. To our best knowledge this is the first time that processing applications with precedence constraints have been considered on the grounds of divisible load theory. (C) 2010 Elsevier Inc. All rights reserved.

引用

页码：450 / 459

页数：10

共 26 条

[1] PARTITIONING TECHNIQUES FOR LARGE-GRAINED PARALLELISM [J].

AGRAWAL, R ;

JAGADISH, HV .

IEEE TRANSACTIONS ON COMPUTERS, 1988, 37 (12) :1627-1634

[2]

[Anonymous], 2005, Scientific Programming

[3]

[Anonymous], 2016, MapReduce

[4]

[Anonymous], 2010, Lp solve reference guide, Patent No. 7 810 000

[5]

[Anonymous], 1996, Scheduling divisible loads in parallel and distributed systems

[6] Scheduling divisible loads on star and tree networks: Results and open problems [J].

Beaumont, O ;

Casanova, H ;

Legrand, A ;

Robert, Y ;

Yang, Y .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2005, 16 (03) :207-218

[7] Experimental study of scheduling with memory constraints using hybrid methods [J].

Berlinska, J. ;

Drozdowski, M. ;

Lawenda, M. .

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, 2009, 232 (02) :638-654

[8]

Berlinska J., 2009, RA0909 POZN U TECHN

[9] Scheduling divisible jobs on hypercubes [J].

Blazewicz, J ;

Drozdowski, M .

PARALLEL COMPUTING, 1995, 21 (12) :1945-1956

[10] DISTRIBUTED COMPUTATION FOR A TREE NETWORK WITH COMMUNICATION DELAYS [J].

CHENG, YC ;

ROBERTAZZI, TG .

IEEE TRANSACTIONS ON AEROSPACE AND ELECTRONIC SYSTEMS, 1990, 26 (03) :511-516

← 1 2 3 →