Efficient distributed workstealing via matchmaking Article Swipe

PDF

Hrushit Parikh , Vinit Deodhar , Ada Gavrilovska , Santosh Pande ·

YOU? · · 2016 · Open Access · · DOI: https://doi.org/10.1145/2851141.2851175

Many classes of high-performance applications and combinatorial problems exhibit large degree of runtime load variability. One approach to achieving balanced resource use is to over decompose the problem on fine-grained tasks that are then dynamically balanced using approaches such as workstealing. Existing work stealing techniques for such irregular applications, running on large clusters, exhibit high overheads due to potential untimely interruption of busy nodes, excessive communication messages and delays experienced by idle nodes in finding work due to repeated failed steals. We contend that the fundamental problem of distributed work-stealing is of rapidly bringing together work producers and consumers. In response, we develop an algorithm that performs timely, lightweight and highly efficient matchmaking between work producers and consumers which results in accurate load balance. Experimental evaluations show that our scheduler is able to outperform other distributed work stealing schedulers, and to achieve scale beyond what is possible with current approaches.

Related Topics

Mechanical Engineering

Mathematics

Concepts

Computer science Distributed computing Idle Work (physics) Load balancing (electrical power) Scheduling (production processes) Processor scheduling Scale (ratio) Resource (disambiguation) Computer network Mathematical optimization Operating system Quantum mechanics Engineering Geometry Physics Mechanical engineering Mathematics Grid

Metadata

Type: article
Language: en
Landing Page: https://doi.org/10.1145/2851141.2851175
PDF: https://dl.acm.org/doi/pdf/10.1145/2851141.2851175?download=true
OA Status: gold
Cited By: 4
References: 5
Related Works: 10
OpenAlex ID: https://openalex.org/W2283000186

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W2283000186

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.1145/2851141.2851175

Digital Object Identifier
Title: Efficient distributed workstealing via matchmaking

Work title
Type: article

OpenAlex work type
Language: en

Primary language
Publication year: 2016

Year of publication
Publication date: 2016-02-22

Full publication date if available
Authors: Hrushit Parikh, Vinit Deodhar, Ada Gavrilovska, Santosh Pande

List of authors in order
Landing page: https://doi.org/10.1145/2851141.2851175

Publisher landing page
PDF URL: https://dl.acm.org/doi/pdf/10.1145/2851141.2851175?download=true

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: gold

Open access status per OpenAlex
OA URL: https://dl.acm.org/doi/pdf/10.1145/2851141.2851175?download=true

Direct OA link when available
Concepts: Computer science, Distributed computing, Idle, Work (physics), Load balancing (electrical power), Scheduling (production processes), Processor scheduling, Scale (ratio), Resource (disambiguation), Computer network, Mathematical optimization, Operating system, Quantum mechanics, Engineering, Geometry, Physics, Mechanical engineering, Mathematics, Grid

Top concepts (fields/topics) attached by OpenAlex
Cited by: 4

Total citation count in OpenAlex
Citations by year (recent): 2021: 1, 2017: 2, 2016: 1

Per-year citation counts (last 5 years)
References (count): 5

Number of works referenced by this work
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W2283000186
doi	https://doi.org/10.1145/2851141.2851175
ids.doi	https://doi.org/10.1145/2851141.2851175
ids.mag	2283000186
ids.openalex	https://openalex.org/W2283000186
fwci	0.86773991
type	article
title	Efficient distributed workstealing via matchmaking
awards[0].id	https://openalex.org/G3428810155
awards[0].funder_id	https://openalex.org/F4320306076
awards[0].display_name
awards[0].funder_award_id	1320752,1217577
awards[0].funder_display_name	National Science Foundation
biblio.issue
biblio.volume
biblio.last_page	2
biblio.first_page	1
topics[0].id	https://openalex.org/T10054
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9998999834060669
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1708
topics[0].subfield.display_name	Hardware and Architecture
topics[0].display_name	Parallel Computing and Optimization Techniques
topics[1].id	https://openalex.org/T10101
topics[1].field.id	https://openalex.org/fields/17
topics[1].field.display_name	Computer Science
topics[1].score	0.9998999834060669
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/1710
topics[1].subfield.display_name	Information Systems
topics[1].display_name	Cloud Computing and Resource Management
topics[2].id	https://openalex.org/T10715
topics[2].field.id	https://openalex.org/fields/17
topics[2].field.display_name	Computer Science
topics[2].score	0.9998000264167786
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/1705
topics[2].subfield.display_name	Computer Networks and Communications
topics[2].display_name	Distributed and Parallel Computing Systems
funders[0].id	https://openalex.org/F4320306076
funders[0].ror	https://ror.org/021nxhr62
funders[0].display_name	National Science Foundation
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C41008148
concepts[0].level	0
concepts[0].score	0.8570550084114075
concepts[0].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[0].display_name	Computer science
concepts[1].id	https://openalex.org/C120314980
concepts[1].level	1
concepts[1].score	0.7888549566268921
concepts[1].wikidata	https://www.wikidata.org/wiki/Q180634
concepts[1].display_name	Distributed computing
concepts[2].id	https://openalex.org/C16320812
concepts[2].level	2
concepts[2].score	0.6628977060317993
concepts[2].wikidata	https://www.wikidata.org/wiki/Q1812200
concepts[2].display_name	Idle
concepts[3].id	https://openalex.org/C18762648
concepts[3].level	2
concepts[3].score	0.5771395564079285
concepts[3].wikidata	https://www.wikidata.org/wiki/Q42213
concepts[3].display_name	Work (physics)
concepts[4].id	https://openalex.org/C138959212
concepts[4].level	3
concepts[4].score	0.5604819655418396
concepts[4].wikidata	https://www.wikidata.org/wiki/Q1806783
concepts[4].display_name	Load balancing (electrical power)
concepts[5].id	https://openalex.org/C206729178
concepts[5].level	2
concepts[5].score	0.5022635459899902
concepts[5].wikidata	https://www.wikidata.org/wiki/Q2271896
concepts[5].display_name	Scheduling (production processes)
concepts[6].id	https://openalex.org/C2984822820
concepts[6].level	3
concepts[6].score	0.4426324963569641
concepts[6].wikidata	https://www.wikidata.org/wiki/Q1123036
concepts[6].display_name	Processor scheduling
concepts[7].id	https://openalex.org/C2778755073
concepts[7].level	2
concepts[7].score	0.43737637996673584
concepts[7].wikidata	https://www.wikidata.org/wiki/Q10858537
concepts[7].display_name	Scale (ratio)
concepts[8].id	https://openalex.org/C206345919
concepts[8].level	2
concepts[8].score	0.3982555866241455
concepts[8].wikidata	https://www.wikidata.org/wiki/Q20380951
concepts[8].display_name	Resource (disambiguation)
concepts[9].id	https://openalex.org/C31258907
concepts[9].level	1
concepts[9].score	0.30761125683784485
concepts[9].wikidata	https://www.wikidata.org/wiki/Q1301371
concepts[9].display_name	Computer network
concepts[10].id	https://openalex.org/C126255220
concepts[10].level	1
concepts[10].score	0.1378980278968811
concepts[10].wikidata	https://www.wikidata.org/wiki/Q141495
concepts[10].display_name	Mathematical optimization
concepts[11].id	https://openalex.org/C111919701
concepts[11].level	1
concepts[11].score	0.1062566339969635
concepts[11].wikidata	https://www.wikidata.org/wiki/Q9135
concepts[11].display_name	Operating system
concepts[12].id	https://openalex.org/C62520636
concepts[12].level	1
concepts[12].score	0.0
concepts[12].wikidata	https://www.wikidata.org/wiki/Q944
concepts[12].display_name	Quantum mechanics
concepts[13].id	https://openalex.org/C127413603
concepts[13].level	0
concepts[13].score	0.0
concepts[13].wikidata	https://www.wikidata.org/wiki/Q11023
concepts[13].display_name	Engineering
concepts[14].id	https://openalex.org/C2524010
concepts[14].level	1
concepts[14].score	0.0
concepts[14].wikidata	https://www.wikidata.org/wiki/Q8087
concepts[14].display_name	Geometry
concepts[15].id	https://openalex.org/C121332964
concepts[15].level	0
concepts[15].score	0.0
concepts[15].wikidata	https://www.wikidata.org/wiki/Q413
concepts[15].display_name	Physics
concepts[16].id	https://openalex.org/C78519656
concepts[16].level	1
concepts[16].score	0.0
concepts[16].wikidata	https://www.wikidata.org/wiki/Q101333
concepts[16].display_name	Mechanical engineering
concepts[17].id	https://openalex.org/C33923547
concepts[17].level	0
concepts[17].score	0.0
concepts[17].wikidata	https://www.wikidata.org/wiki/Q395
concepts[17].display_name	Mathematics
concepts[18].id	https://openalex.org/C187691185
concepts[18].level	2
concepts[18].score	0.0
concepts[18].wikidata	https://www.wikidata.org/wiki/Q2020720
concepts[18].display_name	Grid
keywords[0].id	https://openalex.org/keywords/computer-science
keywords[0].score	0.8570550084114075
keywords[0].display_name	Computer science
keywords[1].id	https://openalex.org/keywords/distributed-computing
keywords[1].score	0.7888549566268921
keywords[1].display_name	Distributed computing
keywords[2].id	https://openalex.org/keywords/idle
keywords[2].score	0.6628977060317993
keywords[2].display_name	Idle
keywords[3].id	https://openalex.org/keywords/work
keywords[3].score	0.5771395564079285
keywords[3].display_name	Work (physics)
keywords[4].id	https://openalex.org/keywords/load-balancing
keywords[4].score	0.5604819655418396
keywords[4].display_name	Load balancing (electrical power)
keywords[5].id	https://openalex.org/keywords/scheduling
keywords[5].score	0.5022635459899902
keywords[5].display_name	Scheduling (production processes)
keywords[6].id	https://openalex.org/keywords/processor-scheduling
keywords[6].score	0.4426324963569641
keywords[6].display_name	Processor scheduling
keywords[7].id	https://openalex.org/keywords/scale
keywords[7].score	0.43737637996673584
keywords[7].display_name	Scale (ratio)
keywords[8].id	https://openalex.org/keywords/resource
keywords[8].score	0.3982555866241455
keywords[8].display_name	Resource (disambiguation)
keywords[9].id	https://openalex.org/keywords/computer-network
keywords[9].score	0.30761125683784485
keywords[9].display_name	Computer network
keywords[10].id	https://openalex.org/keywords/mathematical-optimization
keywords[10].score	0.1378980278968811
keywords[10].display_name	Mathematical optimization
keywords[11].id	https://openalex.org/keywords/operating-system
keywords[11].score	0.1062566339969635
keywords[11].display_name	Operating system
language	en
locations[0].id	doi:10.1145/2851141.2851175
locations[0].is_oa	True
locations[0].source
locations[0].license
locations[0].pdf_url	https://dl.acm.org/doi/pdf/10.1145/2851141.2851175?download=true
locations[0].version	publishedVersion
locations[0].raw_type	proceedings-article
locations[0].license_id
locations[0].is_accepted	True
locations[0].is_published	True
locations[0].raw_source_name	Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming
locations[0].landing_page_url	https://doi.org/10.1145/2851141.2851175
indexed_in	crossref
authorships[0].author.id	https://openalex.org/A5026597814
authorships[0].author.orcid
authorships[0].author.display_name	Hrushit Parikh
authorships[0].countries	US
authorships[0].affiliations[0].institution_ids	https://openalex.org/I130701444
authorships[0].affiliations[0].raw_affiliation_string	Georgia Institute of Technology
authorships[0].institutions[0].id	https://openalex.org/I130701444
authorships[0].institutions[0].ror	https://ror.org/01zkghx44
authorships[0].institutions[0].type	education
authorships[0].institutions[0].lineage	https://openalex.org/I130701444
authorships[0].institutions[0].country_code	US
authorships[0].institutions[0].display_name	Georgia Institute of Technology
authorships[0].author_position	first
authorships[0].raw_author_name	Hrushit Parikh
authorships[0].is_corresponding	False
authorships[0].raw_affiliation_strings	Georgia Institute of Technology
authorships[1].author.id	https://openalex.org/A5047612630
authorships[1].author.orcid
authorships[1].author.display_name	Vinit Deodhar
authorships[1].countries	US
authorships[1].affiliations[0].institution_ids	https://openalex.org/I130701444
authorships[1].affiliations[0].raw_affiliation_string	Georgia Institute of Technology
authorships[1].institutions[0].id	https://openalex.org/I130701444
authorships[1].institutions[0].ror	https://ror.org/01zkghx44
authorships[1].institutions[0].type	education
authorships[1].institutions[0].lineage	https://openalex.org/I130701444
authorships[1].institutions[0].country_code	US
authorships[1].institutions[0].display_name	Georgia Institute of Technology
authorships[1].author_position	middle
authorships[1].raw_author_name	Vinit Deodhar
authorships[1].is_corresponding	False
authorships[1].raw_affiliation_strings	Georgia Institute of Technology
authorships[2].author.id	https://openalex.org/A5085918364
authorships[2].author.orcid	https://orcid.org/0000-0003-4199-2512
authorships[2].author.display_name	Ada Gavrilovska
authorships[2].countries	US
authorships[2].affiliations[0].institution_ids	https://openalex.org/I130701444
authorships[2].affiliations[0].raw_affiliation_string	Georgia Institute of Technology
authorships[2].institutions[0].id	https://openalex.org/I130701444
authorships[2].institutions[0].ror	https://ror.org/01zkghx44
authorships[2].institutions[0].type	education
authorships[2].institutions[0].lineage	https://openalex.org/I130701444
authorships[2].institutions[0].country_code	US
authorships[2].institutions[0].display_name	Georgia Institute of Technology
authorships[2].author_position	middle
authorships[2].raw_author_name	Ada Gavrilovska
authorships[2].is_corresponding	False
authorships[2].raw_affiliation_strings	Georgia Institute of Technology
authorships[3].author.id	https://openalex.org/A5061235810
authorships[3].author.orcid	https://orcid.org/0000-0001-6723-8062
authorships[3].author.display_name	Santosh Pande
authorships[3].countries	US
authorships[3].affiliations[0].institution_ids	https://openalex.org/I130701444
authorships[3].affiliations[0].raw_affiliation_string	Georgia Institute of Technology
authorships[3].institutions[0].id	https://openalex.org/I130701444
authorships[3].institutions[0].ror	https://ror.org/01zkghx44
authorships[3].institutions[0].type	education
authorships[3].institutions[0].lineage	https://openalex.org/I130701444
authorships[3].institutions[0].country_code	US
authorships[3].institutions[0].display_name	Georgia Institute of Technology
authorships[3].author_position	last
authorships[3].raw_author_name	Santosh Pande
authorships[3].is_corresponding	False
authorships[3].raw_affiliation_strings	Georgia Institute of Technology
has_content.pdf	True
has_content.grobid_xml	True
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://dl.acm.org/doi/pdf/10.1145/2851141.2851175?download=true
open_access.oa_status	gold
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Efficient distributed workstealing via matchmaking
has_fulltext	True
is_retracted	False
updated_date	2025-11-06T03:46:38.306776
primary_topic.id	https://openalex.org/T10054
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9998999834060669
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1708
primary_topic.subfield.display_name	Hardware and Architecture
primary_topic.display_name	Parallel Computing and Optimization Techniques
related_works	https://openalex.org/W2128410848, https://openalex.org/W2105625331, https://openalex.org/W2102390841, https://openalex.org/W2118368532, https://openalex.org/W2126232624, https://openalex.org/W2434525066, https://openalex.org/W3140149227, https://openalex.org/W2130555437, https://openalex.org/W2096289371, https://openalex.org/W3023290810
cited_by_count	4
counts_by_year[0].year	2021
counts_by_year[0].cited_by_count	1
counts_by_year[1].year	2017
counts_by_year[1].cited_by_count	2
counts_by_year[2].year	2016
counts_by_year[2].cited_by_count	1
locations_count	1
best_oa_location.id	doi:10.1145/2851141.2851175
best_oa_location.is_oa	True
best_oa_location.source
best_oa_location.license
best_oa_location.pdf_url	https://dl.acm.org/doi/pdf/10.1145/2851141.2851175?download=true
best_oa_location.version	publishedVersion
best_oa_location.raw_type	proceedings-article
best_oa_location.license_id
best_oa_location.is_accepted	True
best_oa_location.is_published	True
best_oa_location.raw_source_name	Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming
best_oa_location.landing_page_url	https://doi.org/10.1145/2851141.2851175
primary_location.id	doi:10.1145/2851141.2851175
primary_location.is_oa	True
primary_location.source
primary_location.license
primary_location.pdf_url	https://dl.acm.org/doi/pdf/10.1145/2851141.2851175?download=true
primary_location.version	publishedVersion
primary_location.raw_type	proceedings-article
primary_location.license_id
primary_location.is_accepted	True
primary_location.is_published	True
primary_location.raw_source_name	Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming
primary_location.landing_page_url	https://doi.org/10.1145/2851141.2851175
publication_date	2016-02-22
publication_year	2016
referenced_works	https://openalex.org/W1539676025, https://openalex.org/W2146381930, https://openalex.org/W2293010966, https://openalex.org/W1558008742, https://openalex.org/W2173994910
referenced_works_count	5
abstract_inverted_index.In	99
abstract_inverted_index.We	81
abstract_inverted_index.an	103
abstract_inverted_index.as	39
abstract_inverted_index.by	70
abstract_inverted_index.in	73, 120
abstract_inverted_index.is	22, 90, 130, 145
abstract_inverted_index.of	2, 11, 61, 87, 91
abstract_inverted_index.on	28, 50
abstract_inverted_index.to	17, 23, 57, 77, 132, 140
abstract_inverted_index.we	101
abstract_inverted_index.One	15
abstract_inverted_index.and	5, 67, 97, 109, 116, 139
abstract_inverted_index.are	32
abstract_inverted_index.due	56, 76
abstract_inverted_index.for	45
abstract_inverted_index.our	128
abstract_inverted_index.the	26, 84
abstract_inverted_index.use	21
abstract_inverted_index.Many	0
abstract_inverted_index.able	131
abstract_inverted_index.busy	62
abstract_inverted_index.high	54
abstract_inverted_index.idle	71
abstract_inverted_index.load	13, 122
abstract_inverted_index.over	24
abstract_inverted_index.show	126
abstract_inverted_index.such	38, 46
abstract_inverted_index.that	31, 83, 105, 127
abstract_inverted_index.then	33
abstract_inverted_index.what	144
abstract_inverted_index.with	147
abstract_inverted_index.work	42, 75, 95, 114, 136
abstract_inverted_index.large	9, 51
abstract_inverted_index.nodes	72
abstract_inverted_index.other	134
abstract_inverted_index.scale	142
abstract_inverted_index.tasks	30
abstract_inverted_index.using	36
abstract_inverted_index.which	118
abstract_inverted_index.beyond	143
abstract_inverted_index.degree	10
abstract_inverted_index.delays	68
abstract_inverted_index.failed	79
abstract_inverted_index.highly	110
abstract_inverted_index.nodes,	63
abstract_inverted_index.achieve	141
abstract_inverted_index.between	113
abstract_inverted_index.classes	1
abstract_inverted_index.contend	82
abstract_inverted_index.current	148
abstract_inverted_index.develop	102
abstract_inverted_index.exhibit	8, 53
abstract_inverted_index.finding	74
abstract_inverted_index.problem	27, 86
abstract_inverted_index.rapidly	92
abstract_inverted_index.results	119
abstract_inverted_index.running	49
abstract_inverted_index.runtime	12
abstract_inverted_index.steals.	80
abstract_inverted_index.timely,	107
abstract_inverted_index.Existing	41
abstract_inverted_index.accurate	121
abstract_inverted_index.approach	16
abstract_inverted_index.balance.	123
abstract_inverted_index.balanced	19, 35
abstract_inverted_index.bringing	93
abstract_inverted_index.messages	66
abstract_inverted_index.performs	106
abstract_inverted_index.possible	146
abstract_inverted_index.problems	7
abstract_inverted_index.repeated	78
abstract_inverted_index.resource	20
abstract_inverted_index.stealing	43, 137
abstract_inverted_index.together	94
abstract_inverted_index.untimely	59
abstract_inverted_index.achieving	18
abstract_inverted_index.algorithm	104
abstract_inverted_index.clusters,	52
abstract_inverted_index.consumers	117
abstract_inverted_index.decompose	25
abstract_inverted_index.efficient	111
abstract_inverted_index.excessive	64
abstract_inverted_index.irregular	47
abstract_inverted_index.overheads	55
abstract_inverted_index.potential	58
abstract_inverted_index.producers	96, 115
abstract_inverted_index.response,	100
abstract_inverted_index.scheduler	129
abstract_inverted_index.approaches	37
abstract_inverted_index.consumers.	98
abstract_inverted_index.outperform	133
abstract_inverted_index.techniques	44
abstract_inverted_index.approaches.	149
abstract_inverted_index.distributed	88, 135
abstract_inverted_index.dynamically	34
abstract_inverted_index.evaluations	125
abstract_inverted_index.experienced	69
abstract_inverted_index.fundamental	85
abstract_inverted_index.lightweight	108
abstract_inverted_index.matchmaking	112
abstract_inverted_index.schedulers,	138
abstract_inverted_index.Experimental	124
abstract_inverted_index.applications	4
abstract_inverted_index.fine-grained	29
abstract_inverted_index.interruption	60
abstract_inverted_index.variability.	14
abstract_inverted_index.applications,	48
abstract_inverted_index.combinatorial	6
abstract_inverted_index.communication	65
abstract_inverted_index.work-stealing	89
abstract_inverted_index.workstealing.	40
abstract_inverted_index.high-performance	3
cited_by_percentile_year.max	96
cited_by_percentile_year.min	89
countries_distinct_count	1
institutions_distinct_count	4
sustainable_development_goals[0].id	https://metadata.un.org/sdg/8
sustainable_development_goals[0].score	0.5600000023841858
sustainable_development_goals[0].display_name	Decent work and economic growth
citation_normalized_percentile.value	0.74772454
citation_normalized_percentile.is_in_top_1_percent	False
citation_normalized_percentile.is_in_top_10_percent	False