Comparison of Single Source Shortest Path Algorithms on Two Recent Asynchronous Many-task Runtime Systems

With the advent of the exascale era, new runtimes and algorithm design techniques need to be explored. In this paper, we investigate performance of three different single-source shortest path algorithms in two relatively recent asynchronous many-task runtime systems AM++ and HPX-5. We identify the u...

Full description

Saved in:
Bibliographic Details
Main Authors: Firoz, Jesun Sahariar, Barnas, Martina, Zalewski, Marcin, Lumsdaine, Andrew
Format: Conference Proceeding
Language:English
Subjects:
Algorithm design and analysis
Algorithms
Approximation algorithms
Computational modeling
Computer networks
Conferences
Decentralized control
Design engineering
Feasibility
Graphs
Libraries
Run time (computers)
Runtime
Shortest-path problems
Synchronization
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites
container_end_page 681
container_issue
container_start_page 674
container_title
container_volume
creator Firoz, Jesun Sahariar
Barnas, Martina
Zalewski, Marcin
Lumsdaine, Andrew
description With the advent of the exascale era, new runtimes and algorithm design techniques need to be explored. In this paper, we investigate performance of three different single-source shortest path algorithms in two relatively recent asynchronous many-task runtime systems AM++ and HPX-5. We identify the underlying set of differential features for these runtimes, and we compare and contrast the performance of Δ-stepping algorithm, Distributed Control based algorithm, K-level Asynchronous algorithm in AM++ and in HPX-5, for which we also include chaotic implementation. We observe that specific runtime characteristics or lack thereoff and different graph inputs can impact the feasibility of an algorithmic approach.
doi_str_mv 10.1109/ICPADS.2015.90
format conference_proceeding
fullrecord <record><control><sourceid>proquest_CHZPO</sourceid><recordid>TN_cdi_proquest_miscellaneous_1793236917</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><ieee_id>7384353</ieee_id><sourcerecordid>1793236917</sourcerecordid><originalsourceid>FETCH-LOGICAL-i208t-9cec6105e3c23415f676c6b34e473da656aaad16f5abe2b33621c5d6bdb5acdd3</originalsourceid><addsrcrecordid>eNotjrtOwzAAAA0SEm1hZWHxyJLiR-zUYxRelYqo2jJHjuM0hsQutiOUvydSmW45nQ6AO4yWGCPxuC62-dN-SRBmS4EuwBxlXDCWrRi_BDPCBUqY4OwazEP4QoggytAMmML1J-lNcBa6Bu6NPXYa7t3g1YTW-ahDhFsZW5h3R-dNbPsAJ_nw6-BOK20jzMNoVeuddUOA79KOSZThG-4GG00_VcYQdR9uwFUju6Bv_7kAny_Ph-It2Xy8rot8kxiCVjERSiuOEdNUEZpi1vCMK17RVKcZrSVnXEpZY94wWWlSUcoJVqzmVV0xqeqaLsDDuXvy7meY7sveBKW7Tlo9DZY4E5RQLnA2qfdn1Wity5M3vfRjmdFVShmlfxzfZlo</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>conference_proceeding</recordtype><pqid>1793236917</pqid></control><display><type>conference_proceeding</type><title>Comparison of Single Source Shortest Path Algorithms on Two Recent Asynchronous Many-task Runtime Systems</title><source>IEEE Xplore All Conference Series</source><creator>Firoz, Jesun Sahariar ; Barnas, Martina ; Zalewski, Marcin ; Lumsdaine, Andrew</creator><creatorcontrib>Firoz, Jesun Sahariar ; Barnas, Martina ; Zalewski, Marcin ; Lumsdaine, Andrew</creatorcontrib><description>With the advent of the exascale era, new runtimes and algorithm design techniques need to be explored. In this paper, we investigate performance of three different single-source shortest path algorithms in two relatively recent asynchronous many-task runtime systems AM++ and HPX-5. We identify the underlying set of differential features for these runtimes, and we compare and contrast the performance of Δ-stepping algorithm, Distributed Control based algorithm, K-level Asynchronous algorithm in AM++ and in HPX-5, for which we also include chaotic implementation. We observe that specific runtime characteristics or lack thereoff and different graph inputs can impact the feasibility of an algorithmic approach.</description><identifier>EISSN: 2690-5965</identifier><identifier>EISSN: 1521-9097</identifier><identifier>EISBN: 0769557856</identifier><identifier>EISBN: 9780769557854</identifier><identifier>DOI: 10.1109/ICPADS.2015.90</identifier><identifier>CODEN: IEEPAD</identifier><language>eng</language><publisher>IEEE</publisher><subject>Algorithm design and analysis ; Algorithms ; Approximation algorithms ; Computational modeling ; Computer networks ; Conferences ; Decentralized control ; Design engineering ; Feasibility ; Graphs ; Libraries ; Run time (computers) ; Runtime ; Shortest-path problems ; Synchronization</subject><ispartof>2015 IEEE 21st International Conference on Parallel and Distributed Systems (ICPADS), 2015, p.674-681</ispartof><woscitedreferencessubscribed>false</woscitedreferencessubscribed></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://ieeexplore.ieee.org/document/7384353$$EHTML$$P50$$Gieee$$H</linktohtml><link.rule.ids>309,310,314,780,784,789,790,23929,23930,25139,27923,27924,54554,54931</link.rule.ids><linktorsrc>$$Uhttps://ieeexplore.ieee.org/document/7384353$$EView_record_in_IEEE$$FView_record_in_$$GIEEE</linktorsrc></links><search><creatorcontrib>Firoz, Jesun Sahariar</creatorcontrib><creatorcontrib>Barnas, Martina</creatorcontrib><creatorcontrib>Zalewski, Marcin</creatorcontrib><creatorcontrib>Lumsdaine, Andrew</creatorcontrib><title>Comparison of Single Source Shortest Path Algorithms on Two Recent Asynchronous Many-task Runtime Systems</title><title>2015 IEEE 21st International Conference on Parallel and Distributed Systems (ICPADS)</title><addtitle>PADSW</addtitle><description>With the advent of the exascale era, new runtimes and algorithm design techniques need to be explored. In this paper, we investigate performance of three different single-source shortest path algorithms in two relatively recent asynchronous many-task runtime systems AM++ and HPX-5. We identify the underlying set of differential features for these runtimes, and we compare and contrast the performance of Δ-stepping algorithm, Distributed Control based algorithm, K-level Asynchronous algorithm in AM++ and in HPX-5, for which we also include chaotic implementation. We observe that specific runtime characteristics or lack thereoff and different graph inputs can impact the feasibility of an algorithmic approach.</description><subject>Algorithm design and analysis</subject><subject>Algorithms</subject><subject>Approximation algorithms</subject><subject>Computational modeling</subject><subject>Computer networks</subject><subject>Conferences</subject><subject>Decentralized control</subject><subject>Design engineering</subject><subject>Feasibility</subject><subject>Graphs</subject><subject>Libraries</subject><subject>Run time (computers)</subject><subject>Runtime</subject><subject>Shortest-path problems</subject><subject>Synchronization</subject><issn>2690-5965</issn><issn>1521-9097</issn><isbn>0769557856</isbn><isbn>9780769557854</isbn><fulltext>true</fulltext><rsrctype>conference_proceeding</rsrctype><creationdate>2015</creationdate><recordtype>conference_proceeding</recordtype><sourceid>6IE</sourceid><recordid>eNotjrtOwzAAAA0SEm1hZWHxyJLiR-zUYxRelYqo2jJHjuM0hsQutiOUvydSmW45nQ6AO4yWGCPxuC62-dN-SRBmS4EuwBxlXDCWrRi_BDPCBUqY4OwazEP4QoggytAMmML1J-lNcBa6Bu6NPXYa7t3g1YTW-ahDhFsZW5h3R-dNbPsAJ_nw6-BOK20jzMNoVeuddUOA79KOSZThG-4GG00_VcYQdR9uwFUju6Bv_7kAny_Ph-It2Xy8rot8kxiCVjERSiuOEdNUEZpi1vCMK17RVKcZrSVnXEpZY94wWWlSUcoJVqzmVV0xqeqaLsDDuXvy7meY7sveBKW7Tlo9DZY4E5RQLnA2qfdn1Wity5M3vfRjmdFVShmlfxzfZlo</recordid><startdate>20151201</startdate><enddate>20151201</enddate><creator>Firoz, Jesun Sahariar</creator><creator>Barnas, Martina</creator><creator>Zalewski, Marcin</creator><creator>Lumsdaine, Andrew</creator><general>IEEE</general><scope>6IE</scope><scope>6IL</scope><scope>CBEJK</scope><scope>RIE</scope><scope>RIL</scope><scope>7SC</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope></search><sort><creationdate>20151201</creationdate><title>Comparison of Single Source Shortest Path Algorithms on Two Recent Asynchronous Many-task Runtime Systems</title><author>Firoz, Jesun Sahariar ; Barnas, Martina ; Zalewski, Marcin ; Lumsdaine, Andrew</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-i208t-9cec6105e3c23415f676c6b34e473da656aaad16f5abe2b33621c5d6bdb5acdd3</frbrgroupid><rsrctype>conference_proceedings</rsrctype><prefilter>conference_proceedings</prefilter><language>eng</language><creationdate>2015</creationdate><topic>Algorithm design and analysis</topic><topic>Algorithms</topic><topic>Approximation algorithms</topic><topic>Computational modeling</topic><topic>Computer networks</topic><topic>Conferences</topic><topic>Decentralized control</topic><topic>Design engineering</topic><topic>Feasibility</topic><topic>Graphs</topic><topic>Libraries</topic><topic>Run time (computers)</topic><topic>Runtime</topic><topic>Shortest-path problems</topic><topic>Synchronization</topic><toplevel>online_resources</toplevel><creatorcontrib>Firoz, Jesun Sahariar</creatorcontrib><creatorcontrib>Barnas, Martina</creatorcontrib><creatorcontrib>Zalewski, Marcin</creatorcontrib><creatorcontrib>Lumsdaine, Andrew</creatorcontrib><collection>IEEE Electronic Library (IEL) Conference Proceedings</collection><collection>IEEE Proceedings Order Plan All Online (POP All Online) 1998-present by volume</collection><collection>IEEE Xplore All Conference Proceedings</collection><collection>IEEE Electronic Library (IEL)</collection><collection>IEEE Proceedings Order Plans (POP All) 1998-Present</collection><collection>Computer and Information Systems Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext_linktorsrc</fulltext></delivery><addata><au>Firoz, Jesun Sahariar</au><au>Barnas, Martina</au><au>Zalewski, Marcin</au><au>Lumsdaine, Andrew</au><format>book</format><genre>proceeding</genre><ristype>CONF</ristype><atitle>Comparison of Single Source Shortest Path Algorithms on Two Recent Asynchronous Many-task Runtime Systems</atitle><btitle>2015 IEEE 21st International Conference on Parallel and Distributed Systems (ICPADS)</btitle><stitle>PADSW</stitle><date>2015-12-01</date><risdate>2015</risdate><spage>674</spage><epage>681</epage><pages>674-681</pages><eissn>2690-5965</eissn><eissn>1521-9097</eissn><eisbn>0769557856</eisbn><eisbn>9780769557854</eisbn><coden>IEEPAD</coden><abstract>With the advent of the exascale era, new runtimes and algorithm design techniques need to be explored. In this paper, we investigate performance of three different single-source shortest path algorithms in two relatively recent asynchronous many-task runtime systems AM++ and HPX-5. We identify the underlying set of differential features for these runtimes, and we compare and contrast the performance of Δ-stepping algorithm, Distributed Control based algorithm, K-level Asynchronous algorithm in AM++ and in HPX-5, for which we also include chaotic implementation. We observe that specific runtime characteristics or lack thereoff and different graph inputs can impact the feasibility of an algorithmic approach.</abstract><pub>IEEE</pub><doi>10.1109/ICPADS.2015.90</doi><tpages>8</tpages></addata></record>
fulltext fulltext_linktorsrc
identifier EISSN: 2690-5965
ispartof 2015 IEEE 21st International Conference on Parallel and Distributed Systems (ICPADS), 2015, p.674-681
issn 2690-5965
1521-9097
language eng
recordid cdi_proquest_miscellaneous_1793236917
source IEEE Xplore All Conference Series
subjects Algorithm design and analysis
Algorithms
Approximation algorithms
Computational modeling
Computer networks
Conferences
Decentralized control
Design engineering
Feasibility
Graphs
Libraries
Run time (computers)
Runtime
Shortest-path problems
Synchronization
title Comparison of Single Source Shortest Path Algorithms on Two Recent Asynchronous Many-task Runtime Systems
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-08T15%3A39%3A58IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_CHZPO&rft_val_fmt=info:ofi/fmt:kev:mtx:book&rft.genre=proceeding&rft.atitle=Comparison%20of%20Single%20Source%20Shortest%20Path%20Algorithms%20on%20Two%20Recent%20Asynchronous%20Many-task%20Runtime%20Systems&rft.btitle=2015%20IEEE%2021st%20International%20Conference%20on%20Parallel%20and%20Distributed%20Systems%20(ICPADS)&rft.au=Firoz,%20Jesun%20Sahariar&rft.date=2015-12-01&rft.spage=674&rft.epage=681&rft.pages=674-681&rft.eissn=2690-5965&rft.coden=IEEPAD&rft_id=info:doi/10.1109/ICPADS.2015.90&rft.eisbn=0769557856&rft.eisbn_list=9780769557854&rft_dat=%3Cproquest_CHZPO%3E1793236917%3C/proquest_CHZPO%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-i208t-9cec6105e3c23415f676c6b34e473da656aaad16f5abe2b33621c5d6bdb5acdd3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=1793236917&rft_id=info:pmid/&rft_ieee_id=7384353&rfr_iscdi=true