Eintrag weiter verarbeiten
Joint optimization of overlapping phases in MapReduce
Gespeichert in:
Zeitschriftentitel: | ACM SIGMETRICS Performance Evaluation Review |
---|---|
Personen und Körperschaften: | , , , |
In: | ACM SIGMETRICS Performance Evaluation Review, 41, 2014, 3, S. 16-18 |
Format: | E-Article |
Sprache: | Englisch |
veröffentlicht: |
Association for Computing Machinery (ACM)
|
Schlagwörter: |
author_facet |
Lin, Minghong Zhang, Li Wierman, Adam Tan, Jian Lin, Minghong Zhang, Li Wierman, Adam Tan, Jian |
---|---|
author |
Lin, Minghong Zhang, Li Wierman, Adam Tan, Jian |
spellingShingle |
Lin, Minghong Zhang, Li Wierman, Adam Tan, Jian ACM SIGMETRICS Performance Evaluation Review Joint optimization of overlapping phases in MapReduce Computer Networks and Communications Hardware and Architecture Software |
author_sort |
lin, minghong |
spelling |
Lin, Minghong Zhang, Li Wierman, Adam Tan, Jian 0163-5999 Association for Computing Machinery (ACM) Computer Networks and Communications Hardware and Architecture Software http://dx.doi.org/10.1145/2567529.2567534 <jats:p>MapReduce is a scalable parallel computing framework for big data processing. It exhibits multiple processing phases, and thus an efficient job scheduling mechanism is crucial for ensuring efficient resource utilization. This work studies the scheduling challenge that results from the overlapping of the "map" and "shuffle" phases in MapReduce. We propose a new, general model for this scheduling problem. Further, we prove that scheduling to minimize average response time in this model is strongly NP-hard in the offline case and that no online algorithm can be constant-competitive in the online case. However, we provide two online algorithms that match the performance of the offline optimal when given a slightly faster service rate.</jats:p> Joint optimization of overlapping phases in MapReduce ACM SIGMETRICS Performance Evaluation Review |
doi_str_mv |
10.1145/2567529.2567534 |
facet_avail |
Online |
finc_class_facet |
Informatik Technik |
format |
ElectronicArticle |
fullrecord |
blob:ai-49-aHR0cDovL2R4LmRvaS5vcmcvMTAuMTE0NS8yNTY3NTI5LjI1Njc1MzQ |
id |
ai-49-aHR0cDovL2R4LmRvaS5vcmcvMTAuMTE0NS8yNTY3NTI5LjI1Njc1MzQ |
institution |
DE-105 DE-14 DE-Ch1 DE-Zi4 DE-15 |
imprint |
Association for Computing Machinery (ACM), 2014 |
imprint_str_mv |
Association for Computing Machinery (ACM), 2014 |
issn |
0163-5999 |
issn_str_mv |
0163-5999 |
language |
English |
mega_collection |
Association for Computing Machinery (ACM) (CrossRef) |
match_str |
lin2014jointoptimizationofoverlappingphasesinmapreduce |
publishDateSort |
2014 |
publisher |
Association for Computing Machinery (ACM) |
recordtype |
ai |
record_format |
ai |
series |
ACM SIGMETRICS Performance Evaluation Review |
source_id |
49 |
title |
Joint optimization of overlapping phases in MapReduce |
title_unstemmed |
Joint optimization of overlapping phases in MapReduce |
title_full |
Joint optimization of overlapping phases in MapReduce |
title_fullStr |
Joint optimization of overlapping phases in MapReduce |
title_full_unstemmed |
Joint optimization of overlapping phases in MapReduce |
title_short |
Joint optimization of overlapping phases in MapReduce |
title_sort |
joint optimization of overlapping phases in mapreduce |
topic |
Computer Networks and Communications Hardware and Architecture Software |
url |
http://dx.doi.org/10.1145/2567529.2567534 |
publishDate |
2014 |
physical |
16-18 |
description |
<jats:p>MapReduce is a scalable parallel computing framework for big data processing. It exhibits multiple processing phases, and thus an efficient job scheduling mechanism is crucial for ensuring efficient resource utilization. This work studies the scheduling challenge that results from the overlapping of the "map" and "shuffle" phases in MapReduce. We propose a new, general model for this scheduling problem. Further, we prove that scheduling to minimize average response time in this model is strongly NP-hard in the offline case and that no online algorithm can be constant-competitive in the online case. However, we provide two online algorithms that match the performance of the offline optimal when given a slightly faster service rate.</jats:p> |
container_issue |
3 |
container_start_page |
16 |
container_title |
ACM SIGMETRICS Performance Evaluation Review |
container_volume |
41 |
format_de105 |
Article, E-Article |
format_de14 |
Article, E-Article |
format_de15 |
Article, E-Article |
format_de520 |
Article, E-Article |
format_de540 |
Article, E-Article |
format_dech1 |
Article, E-Article |
format_ded117 |
Article, E-Article |
format_degla1 |
E-Article |
format_del152 |
Buch |
format_del189 |
Article, E-Article |
format_dezi4 |
Article |
format_dezwi2 |
Article, E-Article |
format_finc |
Article, E-Article |
format_nrw |
Article, E-Article |
_version_ |
1792329270339567620 |
geogr_code |
not assigned |
last_indexed |
2024-03-01T13:06:30.442Z |
geogr_code_person |
not assigned |
openURL |
url_ver=Z39.88-2004&ctx_ver=Z39.88-2004&ctx_enc=info%3Aofi%2Fenc%3AUTF-8&rfr_id=info%3Asid%2Fvufind.svn.sourceforge.net%3Agenerator&rft.title=Joint+optimization+of+overlapping+phases+in+MapReduce&rft.date=2014-01-10&genre=article&issn=0163-5999&volume=41&issue=3&spage=16&epage=18&pages=16-18&jtitle=ACM+SIGMETRICS+Performance+Evaluation+Review&atitle=Joint+optimization+of+overlapping+phases+in+MapReduce&aulast=Tan&aufirst=Jian&rft_id=info%3Adoi%2F10.1145%2F2567529.2567534&rft.language%5B0%5D=eng |
SOLR | |
_version_ | 1792329270339567620 |
author | Lin, Minghong, Zhang, Li, Wierman, Adam, Tan, Jian |
author_facet | Lin, Minghong, Zhang, Li, Wierman, Adam, Tan, Jian, Lin, Minghong, Zhang, Li, Wierman, Adam, Tan, Jian |
author_sort | lin, minghong |
container_issue | 3 |
container_start_page | 16 |
container_title | ACM SIGMETRICS Performance Evaluation Review |
container_volume | 41 |
description | <jats:p>MapReduce is a scalable parallel computing framework for big data processing. It exhibits multiple processing phases, and thus an efficient job scheduling mechanism is crucial for ensuring efficient resource utilization. This work studies the scheduling challenge that results from the overlapping of the "map" and "shuffle" phases in MapReduce. We propose a new, general model for this scheduling problem. Further, we prove that scheduling to minimize average response time in this model is strongly NP-hard in the offline case and that no online algorithm can be constant-competitive in the online case. However, we provide two online algorithms that match the performance of the offline optimal when given a slightly faster service rate.</jats:p> |
doi_str_mv | 10.1145/2567529.2567534 |
facet_avail | Online |
finc_class_facet | Informatik, Technik |
format | ElectronicArticle |
format_de105 | Article, E-Article |
format_de14 | Article, E-Article |
format_de15 | Article, E-Article |
format_de520 | Article, E-Article |
format_de540 | Article, E-Article |
format_dech1 | Article, E-Article |
format_ded117 | Article, E-Article |
format_degla1 | E-Article |
format_del152 | Buch |
format_del189 | Article, E-Article |
format_dezi4 | Article |
format_dezwi2 | Article, E-Article |
format_finc | Article, E-Article |
format_nrw | Article, E-Article |
geogr_code | not assigned |
geogr_code_person | not assigned |
id | ai-49-aHR0cDovL2R4LmRvaS5vcmcvMTAuMTE0NS8yNTY3NTI5LjI1Njc1MzQ |
imprint | Association for Computing Machinery (ACM), 2014 |
imprint_str_mv | Association for Computing Machinery (ACM), 2014 |
institution | DE-105, DE-14, DE-Ch1, DE-Zi4, DE-15 |
issn | 0163-5999 |
issn_str_mv | 0163-5999 |
language | English |
last_indexed | 2024-03-01T13:06:30.442Z |
match_str | lin2014jointoptimizationofoverlappingphasesinmapreduce |
mega_collection | Association for Computing Machinery (ACM) (CrossRef) |
physical | 16-18 |
publishDate | 2014 |
publishDateSort | 2014 |
publisher | Association for Computing Machinery (ACM) |
record_format | ai |
recordtype | ai |
series | ACM SIGMETRICS Performance Evaluation Review |
source_id | 49 |
spelling | Lin, Minghong Zhang, Li Wierman, Adam Tan, Jian 0163-5999 Association for Computing Machinery (ACM) Computer Networks and Communications Hardware and Architecture Software http://dx.doi.org/10.1145/2567529.2567534 <jats:p>MapReduce is a scalable parallel computing framework for big data processing. It exhibits multiple processing phases, and thus an efficient job scheduling mechanism is crucial for ensuring efficient resource utilization. This work studies the scheduling challenge that results from the overlapping of the "map" and "shuffle" phases in MapReduce. We propose a new, general model for this scheduling problem. Further, we prove that scheduling to minimize average response time in this model is strongly NP-hard in the offline case and that no online algorithm can be constant-competitive in the online case. However, we provide two online algorithms that match the performance of the offline optimal when given a slightly faster service rate.</jats:p> Joint optimization of overlapping phases in MapReduce ACM SIGMETRICS Performance Evaluation Review |
spellingShingle | Lin, Minghong, Zhang, Li, Wierman, Adam, Tan, Jian, ACM SIGMETRICS Performance Evaluation Review, Joint optimization of overlapping phases in MapReduce, Computer Networks and Communications, Hardware and Architecture, Software |
title | Joint optimization of overlapping phases in MapReduce |
title_full | Joint optimization of overlapping phases in MapReduce |
title_fullStr | Joint optimization of overlapping phases in MapReduce |
title_full_unstemmed | Joint optimization of overlapping phases in MapReduce |
title_short | Joint optimization of overlapping phases in MapReduce |
title_sort | joint optimization of overlapping phases in mapreduce |
title_unstemmed | Joint optimization of overlapping phases in MapReduce |
topic | Computer Networks and Communications, Hardware and Architecture, Software |
url | http://dx.doi.org/10.1145/2567529.2567534 |