Optimizing Ordered Graph Algorithms with GraphIt Article Swipe
Yunming Zhang
,
Ajay Brahmakshatriya
,
Xinyi Chen
,
Laxman Dhulipala
,
Shoaib Kamil
,
Saman Amarasinghe
,
Julian Shun
·
YOU?
·
· 2019
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.1911.07260
YOU?
·
· 2019
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.1911.07260
Many graph problems can be solved using ordered parallel graph algorithms that achieve significant speedup over their unordered counterparts by reducing redundant work. This paper introduces a new priority-based extension to GraphIt, a domain-specific language for writing graph applications, to simplify writing high-performance parallel ordered graph algorithms. The extension enables vertices to be processed in a dynamic order while hiding low-level implementation details from the user. We extend the compiler with new program analyses, transformations, and code generation to produce fast implementations of ordered parallel graph algorithms. We also introduce bucket fusion, a new performance optimization that fuses together different rounds of ordered algorithms to reduce synchronization overhead, resulting in $1.2\times$--3$\times$ speedup over the fastest existing ordered algorithm implementations on road networks with large diameters. With the extension, GraphIt achieves up to 3$\times$ speedup on six ordered graph algorithms over state-of-the-art frameworks and hand-optimized implementations (Julienne, Galois, and GAPBS) that support ordered algorithms.
Related Topics
Concepts
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/1911.07260
- https://arxiv.org/pdf/1911.07260
- OA Status
- green
- Cited By
- 1
- References
- 46
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W3002717751
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W3002717751Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.1911.07260Digital Object Identifier
- Title
-
Optimizing Ordered Graph Algorithms with GraphItWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2019Year of publication
- Publication date
-
2019-11-17Full publication date if available
- Authors
-
Yunming Zhang, Ajay Brahmakshatriya, Xinyi Chen, Laxman Dhulipala, Shoaib Kamil, Saman Amarasinghe, Julian ShunList of authors in order
- Landing page
-
https://arxiv.org/abs/1911.07260Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/1911.07260Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/pdf/1911.07260Direct OA link when available
- Concepts
-
Speedup, Computer science, Algorithm, Graph, Implementation, Parallel computing, Theoretical computer science, Programming languageTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
1Total citation count in OpenAlex
- Citations by year (recent)
-
2022: 1Per-year citation counts (last 5 years)
- References (count)
-
46Number of works referenced by this work
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W3002717751 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.1911.07260 |
| ids.doi | https://doi.org/10.48550/arxiv.1911.07260 |
| ids.mag | 3002717751 |
| ids.openalex | https://openalex.org/W3002717751 |
| fwci | 0.10688576 |
| type | preprint |
| title | Optimizing Ordered Graph Algorithms with GraphIt |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T12292 |
| 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/1707 |
| topics[0].subfield.display_name | Computer Vision and Pattern Recognition |
| topics[0].display_name | Graph Theory and Algorithms |
| topics[1].id | https://openalex.org/T10829 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.996999979019165 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1705 |
| topics[1].subfield.display_name | Computer Networks and Communications |
| topics[1].display_name | Interconnection Networks and Systems |
| topics[2].id | https://openalex.org/T10720 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.995199978351593 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1703 |
| topics[2].subfield.display_name | Computational Theory and Mathematics |
| topics[2].display_name | Complexity and Algorithms in Graphs |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C68339613 |
| concepts[0].level | 2 |
| concepts[0].score | 0.8774292469024658 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q1549489 |
| concepts[0].display_name | Speedup |
| concepts[1].id | https://openalex.org/C41008148 |
| concepts[1].level | 0 |
| concepts[1].score | 0.8103222846984863 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[1].display_name | Computer science |
| concepts[2].id | https://openalex.org/C11413529 |
| concepts[2].level | 1 |
| concepts[2].score | 0.5939915776252747 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q8366 |
| concepts[2].display_name | Algorithm |
| concepts[3].id | https://openalex.org/C132525143 |
| concepts[3].level | 2 |
| concepts[3].score | 0.5368478894233704 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q141488 |
| concepts[3].display_name | Graph |
| concepts[4].id | https://openalex.org/C26713055 |
| concepts[4].level | 2 |
| concepts[4].score | 0.5033478140830994 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q245962 |
| concepts[4].display_name | Implementation |
| concepts[5].id | https://openalex.org/C173608175 |
| concepts[5].level | 1 |
| concepts[5].score | 0.4005359411239624 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q232661 |
| concepts[5].display_name | Parallel computing |
| concepts[6].id | https://openalex.org/C80444323 |
| concepts[6].level | 1 |
| concepts[6].score | 0.32221847772598267 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q2878974 |
| concepts[6].display_name | Theoretical computer science |
| concepts[7].id | https://openalex.org/C199360897 |
| concepts[7].level | 1 |
| concepts[7].score | 0.12122219800949097 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q9143 |
| concepts[7].display_name | Programming language |
| keywords[0].id | https://openalex.org/keywords/speedup |
| keywords[0].score | 0.8774292469024658 |
| keywords[0].display_name | Speedup |
| keywords[1].id | https://openalex.org/keywords/computer-science |
| keywords[1].score | 0.8103222846984863 |
| keywords[1].display_name | Computer science |
| keywords[2].id | https://openalex.org/keywords/algorithm |
| keywords[2].score | 0.5939915776252747 |
| keywords[2].display_name | Algorithm |
| keywords[3].id | https://openalex.org/keywords/graph |
| keywords[3].score | 0.5368478894233704 |
| keywords[3].display_name | Graph |
| keywords[4].id | https://openalex.org/keywords/implementation |
| keywords[4].score | 0.5033478140830994 |
| keywords[4].display_name | Implementation |
| keywords[5].id | https://openalex.org/keywords/parallel-computing |
| keywords[5].score | 0.4005359411239624 |
| keywords[5].display_name | Parallel computing |
| keywords[6].id | https://openalex.org/keywords/theoretical-computer-science |
| keywords[6].score | 0.32221847772598267 |
| keywords[6].display_name | Theoretical computer science |
| keywords[7].id | https://openalex.org/keywords/programming-language |
| keywords[7].score | 0.12122219800949097 |
| keywords[7].display_name | Programming language |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:1911.07260 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400194 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | arXiv (Cornell University) |
| locations[0].source.host_organization | https://openalex.org/I205783295 |
| locations[0].source.host_organization_name | Cornell University |
| locations[0].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[0].license | |
| locations[0].pdf_url | https://arxiv.org/pdf/1911.07260 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | text |
| locations[0].license_id | |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | http://arxiv.org/abs/1911.07260 |
| locations[1].id | doi:10.48550/arxiv.1911.07260 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306400194 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | True |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | arXiv (Cornell University) |
| locations[1].source.host_organization | https://openalex.org/I205783295 |
| locations[1].source.host_organization_name | Cornell University |
| locations[1].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[1].license | |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | article-journal |
| locations[1].license_id | |
| locations[1].is_accepted | False |
| locations[1].is_published | |
| locations[1].raw_source_name | |
| locations[1].landing_page_url | https://doi.org/10.48550/arxiv.1911.07260 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5102790106 |
| authorships[0].author.orcid | https://orcid.org/0000-0003-3087-5580 |
| authorships[0].author.display_name | Yunming Zhang |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Yunming Zhang |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5046807118 |
| authorships[1].author.orcid | https://orcid.org/0000-0002-5295-4186 |
| authorships[1].author.display_name | Ajay Brahmakshatriya |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Ajay Brahmakshatriya |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5100457118 |
| authorships[2].author.orcid | https://orcid.org/0000-0003-3321-2483 |
| authorships[2].author.display_name | Xinyi Chen |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Xinyi Chen |
| authorships[2].is_corresponding | False |
| authorships[3].author.id | https://openalex.org/A5065818820 |
| authorships[3].author.orcid | https://orcid.org/0000-0003-0685-064X |
| authorships[3].author.display_name | Laxman Dhulipala |
| authorships[3].author_position | middle |
| authorships[3].raw_author_name | Laxman Dhulipala |
| authorships[3].is_corresponding | False |
| authorships[4].author.id | https://openalex.org/A5039453861 |
| authorships[4].author.orcid | https://orcid.org/0000-0001-5965-3717 |
| authorships[4].author.display_name | Shoaib Kamil |
| authorships[4].author_position | middle |
| authorships[4].raw_author_name | Shoaib Kamil |
| authorships[4].is_corresponding | False |
| authorships[5].author.id | https://openalex.org/A5046791216 |
| authorships[5].author.orcid | https://orcid.org/0000-0002-7231-7643 |
| authorships[5].author.display_name | Saman Amarasinghe |
| authorships[5].author_position | middle |
| authorships[5].raw_author_name | Saman Amarasinghe |
| authorships[5].is_corresponding | False |
| authorships[6].author.id | https://openalex.org/A5051583907 |
| authorships[6].author.orcid | https://orcid.org/0000-0001-6163-6625 |
| authorships[6].author.display_name | Julian Shun |
| authorships[6].author_position | last |
| authorships[6].raw_author_name | Julian Shun |
| authorships[6].is_corresponding | False |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://arxiv.org/pdf/1911.07260 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Optimizing Ordered Graph Algorithms with GraphIt |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T12292 |
| 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/1707 |
| primary_topic.subfield.display_name | Computer Vision and Pattern Recognition |
| primary_topic.display_name | Graph Theory and Algorithms |
| related_works | https://openalex.org/W2317245370, https://openalex.org/W4249323025, https://openalex.org/W198851386, https://openalex.org/W2030310580, https://openalex.org/W947442053, https://openalex.org/W1980160788, https://openalex.org/W1500978221, https://openalex.org/W2148915962, https://openalex.org/W2283866686, https://openalex.org/W4287182096 |
| cited_by_count | 1 |
| counts_by_year[0].year | 2022 |
| counts_by_year[0].cited_by_count | 1 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:1911.07260 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400194 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | arXiv (Cornell University) |
| best_oa_location.source.host_organization | https://openalex.org/I205783295 |
| best_oa_location.source.host_organization_name | Cornell University |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| best_oa_location.license | |
| best_oa_location.pdf_url | https://arxiv.org/pdf/1911.07260 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | text |
| best_oa_location.license_id | |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | http://arxiv.org/abs/1911.07260 |
| primary_location.id | pmh:oai:arXiv.org:1911.07260 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400194 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | arXiv (Cornell University) |
| primary_location.source.host_organization | https://openalex.org/I205783295 |
| primary_location.source.host_organization_name | Cornell University |
| primary_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| primary_location.license | |
| primary_location.pdf_url | https://arxiv.org/pdf/1911.07260 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | text |
| primary_location.license_id | |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | http://arxiv.org/abs/1911.07260 |
| publication_date | 2019-11-17 |
| publication_year | 2019 |
| referenced_works | https://openalex.org/W2235134718, https://openalex.org/W2098153911, https://openalex.org/W1593868476, https://openalex.org/W2566870951, https://openalex.org/W2931294367, https://openalex.org/W2739409954, https://openalex.org/W2094224753, https://openalex.org/W2964010284, https://openalex.org/W2100218206, https://openalex.org/W2034102265, https://openalex.org/W2788981395, https://openalex.org/W2780077279, https://openalex.org/W2604668004, https://openalex.org/W2792524085, https://openalex.org/W2962865652, https://openalex.org/W1788180225, https://openalex.org/W2022704179, https://openalex.org/W2931071418, https://openalex.org/W78077100, https://openalex.org/W2227557434, https://openalex.org/W2086337948, https://openalex.org/W2000041758, https://openalex.org/W2905135312, https://openalex.org/W2035080386, https://openalex.org/W2980119420, https://openalex.org/W2572767837, https://openalex.org/W2523378841, https://openalex.org/W1783256592, https://openalex.org/W2904192253, https://openalex.org/W2565964892, https://openalex.org/W2963146589, https://openalex.org/W2915012400, https://openalex.org/W2132473764, https://openalex.org/W2581090187, https://openalex.org/W2905048389, https://openalex.org/W3012204286, https://openalex.org/W2041470524, https://openalex.org/W2721246439, https://openalex.org/W2131071574, https://openalex.org/W2101196063, https://openalex.org/W2057112598, https://openalex.org/W1807272711, https://openalex.org/W2788443250, https://openalex.org/W1974154846, https://openalex.org/W2524623326, https://openalex.org/W2798525482 |
| referenced_works_count | 46 |
| abstract_inverted_index.a | 26, 32, 55, 92 |
| abstract_inverted_index.We | 66, 87 |
| abstract_inverted_index.be | 4, 52 |
| abstract_inverted_index.by | 19 |
| abstract_inverted_index.in | 54, 109 |
| abstract_inverted_index.of | 82, 101 |
| abstract_inverted_index.on | 119, 134 |
| abstract_inverted_index.to | 30, 39, 51, 78, 104, 131 |
| abstract_inverted_index.up | 130 |
| abstract_inverted_index.The | 47 |
| abstract_inverted_index.and | 75, 142, 147 |
| abstract_inverted_index.can | 3 |
| abstract_inverted_index.for | 35 |
| abstract_inverted_index.new | 27, 71, 93 |
| abstract_inverted_index.six | 135 |
| abstract_inverted_index.the | 64, 68, 113, 126 |
| abstract_inverted_index.Many | 0 |
| abstract_inverted_index.This | 23 |
| abstract_inverted_index.With | 125 |
| abstract_inverted_index.also | 88 |
| abstract_inverted_index.code | 76 |
| abstract_inverted_index.fast | 80 |
| abstract_inverted_index.from | 63 |
| abstract_inverted_index.over | 15, 112, 139 |
| abstract_inverted_index.road | 120 |
| abstract_inverted_index.that | 11, 96, 149 |
| abstract_inverted_index.with | 70, 122 |
| abstract_inverted_index.fuses | 97 |
| abstract_inverted_index.graph | 1, 9, 37, 45, 85, 137 |
| abstract_inverted_index.large | 123 |
| abstract_inverted_index.order | 57 |
| abstract_inverted_index.paper | 24 |
| abstract_inverted_index.their | 16 |
| abstract_inverted_index.user. | 65 |
| abstract_inverted_index.using | 6 |
| abstract_inverted_index.while | 58 |
| abstract_inverted_index.work. | 22 |
| abstract_inverted_index.GAPBS) | 148 |
| abstract_inverted_index.bucket | 90 |
| abstract_inverted_index.extend | 67 |
| abstract_inverted_index.hiding | 59 |
| abstract_inverted_index.reduce | 105 |
| abstract_inverted_index.rounds | 100 |
| abstract_inverted_index.solved | 5 |
| abstract_inverted_index.Galois, | 146 |
| abstract_inverted_index.GraphIt | 128 |
| abstract_inverted_index.achieve | 12 |
| abstract_inverted_index.details | 62 |
| abstract_inverted_index.dynamic | 56 |
| abstract_inverted_index.enables | 49 |
| abstract_inverted_index.fastest | 114 |
| abstract_inverted_index.fusion, | 91 |
| abstract_inverted_index.ordered | 7, 44, 83, 102, 116, 136, 151 |
| abstract_inverted_index.produce | 79 |
| abstract_inverted_index.program | 72 |
| abstract_inverted_index.speedup | 14, 111, 133 |
| abstract_inverted_index.support | 150 |
| abstract_inverted_index.writing | 36, 41 |
| abstract_inverted_index.GraphIt, | 31 |
| abstract_inverted_index.achieves | 129 |
| abstract_inverted_index.compiler | 69 |
| abstract_inverted_index.existing | 115 |
| abstract_inverted_index.language | 34 |
| abstract_inverted_index.networks | 121 |
| abstract_inverted_index.parallel | 8, 43, 84 |
| abstract_inverted_index.problems | 2 |
| abstract_inverted_index.reducing | 20 |
| abstract_inverted_index.simplify | 40 |
| abstract_inverted_index.together | 98 |
| abstract_inverted_index.vertices | 50 |
| abstract_inverted_index.3$\times$ | 132 |
| abstract_inverted_index.algorithm | 117 |
| abstract_inverted_index.analyses, | 73 |
| abstract_inverted_index.different | 99 |
| abstract_inverted_index.extension | 29, 48 |
| abstract_inverted_index.introduce | 89 |
| abstract_inverted_index.low-level | 60 |
| abstract_inverted_index.overhead, | 107 |
| abstract_inverted_index.processed | 53 |
| abstract_inverted_index.redundant | 21 |
| abstract_inverted_index.resulting | 108 |
| abstract_inverted_index.unordered | 17 |
| abstract_inverted_index.(Julienne, | 145 |
| abstract_inverted_index.algorithms | 10, 103, 138 |
| abstract_inverted_index.diameters. | 124 |
| abstract_inverted_index.extension, | 127 |
| abstract_inverted_index.frameworks | 141 |
| abstract_inverted_index.generation | 77 |
| abstract_inverted_index.introduces | 25 |
| abstract_inverted_index.algorithms. | 46, 86, 152 |
| abstract_inverted_index.performance | 94 |
| abstract_inverted_index.significant | 13 |
| abstract_inverted_index.counterparts | 18 |
| abstract_inverted_index.optimization | 95 |
| abstract_inverted_index.applications, | 38 |
| abstract_inverted_index.hand-optimized | 143 |
| abstract_inverted_index.implementation | 61 |
| abstract_inverted_index.priority-based | 28 |
| abstract_inverted_index.domain-specific | 33 |
| abstract_inverted_index.implementations | 81, 118, 144 |
| abstract_inverted_index.synchronization | 106 |
| abstract_inverted_index.high-performance | 42 |
| abstract_inverted_index.state-of-the-art | 140 |
| abstract_inverted_index.transformations, | 74 |
| abstract_inverted_index.$1.2\times$--3$\times$ | 110 |
| cited_by_percentile_year.max | 94 |
| cited_by_percentile_year.min | 89 |
| countries_distinct_count | 0 |
| institutions_distinct_count | 7 |
| sustainable_development_goals[0].id | https://metadata.un.org/sdg/4 |
| sustainable_development_goals[0].score | 0.75 |
| sustainable_development_goals[0].display_name | Quality Education |
| citation_normalized_percentile.value | 0.48303897 |
| citation_normalized_percentile.is_in_top_1_percent | False |
| citation_normalized_percentile.is_in_top_10_percent | False |