Determining the Optimal Redistribution for a Given Data Partition

The classical redistribution problem aims at optimally scheduling communications when moving from an initial data distribution to a target distribution where each processor will host a subset of data items. However, modern computing platforms are equipped with a powerful interconnection switch, and...

Full description

Saved in:
Bibliographic Details
Main Authors: Herault, Thomas, Herrmann, Julien, Marchal, Loris, Robert, Yves
Format: Conference Proceeding
Language:English
Subjects:
Bipartite graph
Complexity theory
Distributed databases
Kernel
Measurement
Optimization
Partitioning algorithms
Citations: Items that cite this one
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c253t-3d6e0486fdb0ccbc3db8c513f5e1011b887362c815554b00fb8fde5eb73e3e4c3
cites
container_end_page 102
container_issue
container_start_page 95
container_title
container_volume
creator Herault, Thomas
Herrmann, Julien
Marchal, Loris
Robert, Yves
description The classical redistribution problem aims at optimally scheduling communications when moving from an initial data distribution to a target distribution where each processor will host a subset of data items. However, modern computing platforms are equipped with a powerful interconnection switch, and the cost of a given communication is (almost) independent of the location of its sender and receiver. This leads to generalizing the redistribution problem as follows: find the optimal one-toone mapping of the subsets of data items onto the processors for which the cost of the redistribution is minimal. This paper studies the complexity of this generalized problem. We provide optimal algorithms and evaluate their gain over classical redistribution through simulations. We also show the NP-hardness of the problem to find the optimal data partition and processor permutation (defined by new subsets) that minimize the cost of redistribution followed by a simple computation kernel.
doi_str_mv 10.1109/ISPDC.2014.16
format conference_proceeding
fullrecord <record><control><sourceid>ieee_CHZPO</sourceid><recordid>TN_cdi_ieee_primary_6900206</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><ieee_id>6900206</ieee_id><sourcerecordid>6900206</sourcerecordid><originalsourceid>FETCH-LOGICAL-c253t-3d6e0486fdb0ccbc3db8c513f5e1011b887362c815554b00fb8fde5eb73e3e4c3</originalsourceid><addsrcrecordid>eNpFjs1KAzEURiMqWGuXrtzkBWa8N5lkkmWZ2lootPizLknmjkbaaclEwbdXUXD1cThw-Bi7RigRwd4uHzezphSAVYn6hF1iVVurLNr69B-MPWMjIWtbKKnEBZsMwxsASDTGGjti0xllSvvYx_6F51fi62OOe7fjD9TGIafo33M89Lw7JO74In5Qz2cuO75xKccfdcXOO7cbaPK3Y_Y8v3tq7ovVerFspqsiCCVzIVtNUBndtR5C8EG23gSFslOEgOiNqaUWwaBSqvIAnTddS4p8LUlSFeSY3fx2IxFtj-n7ZfrcagsgQMsv3gpLpg</addsrcrecordid><sourcetype>Publisher</sourcetype><iscdi>true</iscdi><recordtype>conference_proceeding</recordtype></control><display><type>conference_proceeding</type><title>Determining the Optimal Redistribution for a Given Data Partition</title><source>IEEE Xplore All Conference Series</source><creator>Herault, Thomas ; Herrmann, Julien ; Marchal, Loris ; Robert, Yves</creator><creatorcontrib>Herault, Thomas ; Herrmann, Julien ; Marchal, Loris ; Robert, Yves</creatorcontrib><description>The classical redistribution problem aims at optimally scheduling communications when moving from an initial data distribution to a target distribution where each processor will host a subset of data items. However, modern computing platforms are equipped with a powerful interconnection switch, and the cost of a given communication is (almost) independent of the location of its sender and receiver. This leads to generalizing the redistribution problem as follows: find the optimal one-toone mapping of the subsets of data items onto the processors for which the cost of the redistribution is minimal. This paper studies the complexity of this generalized problem. We provide optimal algorithms and evaluate their gain over classical redistribution through simulations. We also show the NP-hardness of the problem to find the optimal data partition and processor permutation (defined by new subsets) that minimize the cost of redistribution followed by a simple computation kernel.</description><identifier>ISSN: 2379-5352</identifier><identifier>ISBN: 1479959189</identifier><identifier>ISBN: 9781479959181</identifier><identifier>EISBN: 1479959197</identifier><identifier>EISBN: 9781479959198</identifier><identifier>DOI: 10.1109/ISPDC.2014.16</identifier><identifier>CODEN: IEEPAD</identifier><language>eng</language><publisher>IEEE</publisher><subject>Bipartite graph ; Complexity theory ; Distributed databases ; Kernel ; Measurement ; Optimization ; Partitioning algorithms</subject><ispartof>2014 IEEE 13th International Symposium on Parallel and Distributed Computing, 2014, p.95-102</ispartof><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c253t-3d6e0486fdb0ccbc3db8c513f5e1011b887362c815554b00fb8fde5eb73e3e4c3</citedby></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://ieeexplore.ieee.org/document/6900206$$EHTML$$P50$$Gieee$$H</linktohtml><link.rule.ids>309,310,776,780,785,786,23909,23910,25118,27902,54530,54907</link.rule.ids><linktorsrc>$$Uhttps://ieeexplore.ieee.org/document/6900206$$EView_record_in_IEEE$$FView_record_in_$$GIEEE</linktorsrc></links><search><creatorcontrib>Herault, Thomas</creatorcontrib><creatorcontrib>Herrmann, Julien</creatorcontrib><creatorcontrib>Marchal, Loris</creatorcontrib><creatorcontrib>Robert, Yves</creatorcontrib><title>Determining the Optimal Redistribution for a Given Data Partition</title><title>2014 IEEE 13th International Symposium on Parallel and Distributed Computing</title><addtitle>ISPDC</addtitle><description>The classical redistribution problem aims at optimally scheduling communications when moving from an initial data distribution to a target distribution where each processor will host a subset of data items. However, modern computing platforms are equipped with a powerful interconnection switch, and the cost of a given communication is (almost) independent of the location of its sender and receiver. This leads to generalizing the redistribution problem as follows: find the optimal one-toone mapping of the subsets of data items onto the processors for which the cost of the redistribution is minimal. This paper studies the complexity of this generalized problem. We provide optimal algorithms and evaluate their gain over classical redistribution through simulations. We also show the NP-hardness of the problem to find the optimal data partition and processor permutation (defined by new subsets) that minimize the cost of redistribution followed by a simple computation kernel.</description><subject>Bipartite graph</subject><subject>Complexity theory</subject><subject>Distributed databases</subject><subject>Kernel</subject><subject>Measurement</subject><subject>Optimization</subject><subject>Partitioning algorithms</subject><issn>2379-5352</issn><isbn>1479959189</isbn><isbn>9781479959181</isbn><isbn>1479959197</isbn><isbn>9781479959198</isbn><fulltext>true</fulltext><rsrctype>conference_proceeding</rsrctype><creationdate>2014</creationdate><recordtype>conference_proceeding</recordtype><sourceid>6IE</sourceid><recordid>eNpFjs1KAzEURiMqWGuXrtzkBWa8N5lkkmWZ2lootPizLknmjkbaaclEwbdXUXD1cThw-Bi7RigRwd4uHzezphSAVYn6hF1iVVurLNr69B-MPWMjIWtbKKnEBZsMwxsASDTGGjti0xllSvvYx_6F51fi62OOe7fjD9TGIafo33M89Lw7JO74In5Qz2cuO75xKccfdcXOO7cbaPK3Y_Y8v3tq7ovVerFspqsiCCVzIVtNUBndtR5C8EG23gSFslOEgOiNqaUWwaBSqvIAnTddS4p8LUlSFeSY3fx2IxFtj-n7ZfrcagsgQMsv3gpLpg</recordid><startdate>201406</startdate><enddate>201406</enddate><creator>Herault, Thomas</creator><creator>Herrmann, Julien</creator><creator>Marchal, Loris</creator><creator>Robert, Yves</creator><general>IEEE</general><scope>6IE</scope><scope>6IL</scope><scope>CBEJK</scope><scope>RIE</scope><scope>RIL</scope></search><sort><creationdate>201406</creationdate><title>Determining the Optimal Redistribution for a Given Data Partition</title><author>Herault, Thomas ; Herrmann, Julien ; Marchal, Loris ; Robert, Yves</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c253t-3d6e0486fdb0ccbc3db8c513f5e1011b887362c815554b00fb8fde5eb73e3e4c3</frbrgroupid><rsrctype>conference_proceedings</rsrctype><prefilter>conference_proceedings</prefilter><language>eng</language><creationdate>2014</creationdate><topic>Bipartite graph</topic><topic>Complexity theory</topic><topic>Distributed databases</topic><topic>Kernel</topic><topic>Measurement</topic><topic>Optimization</topic><topic>Partitioning algorithms</topic><toplevel>online_resources</toplevel><creatorcontrib>Herault, Thomas</creatorcontrib><creatorcontrib>Herrmann, Julien</creatorcontrib><creatorcontrib>Marchal, Loris</creatorcontrib><creatorcontrib>Robert, Yves</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></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext_linktorsrc</fulltext></delivery><addata><au>Herault, Thomas</au><au>Herrmann, Julien</au><au>Marchal, Loris</au><au>Robert, Yves</au><format>book</format><genre>proceeding</genre><ristype>CONF</ristype><atitle>Determining the Optimal Redistribution for a Given Data Partition</atitle><btitle>2014 IEEE 13th International Symposium on Parallel and Distributed Computing</btitle><stitle>ISPDC</stitle><date>2014-06</date><risdate>2014</risdate><spage>95</spage><epage>102</epage><pages>95-102</pages><issn>2379-5352</issn><isbn>1479959189</isbn><isbn>9781479959181</isbn><eisbn>1479959197</eisbn><eisbn>9781479959198</eisbn><coden>IEEPAD</coden><abstract>The classical redistribution problem aims at optimally scheduling communications when moving from an initial data distribution to a target distribution where each processor will host a subset of data items. However, modern computing platforms are equipped with a powerful interconnection switch, and the cost of a given communication is (almost) independent of the location of its sender and receiver. This leads to generalizing the redistribution problem as follows: find the optimal one-toone mapping of the subsets of data items onto the processors for which the cost of the redistribution is minimal. This paper studies the complexity of this generalized problem. We provide optimal algorithms and evaluate their gain over classical redistribution through simulations. We also show the NP-hardness of the problem to find the optimal data partition and processor permutation (defined by new subsets) that minimize the cost of redistribution followed by a simple computation kernel.</abstract><pub>IEEE</pub><doi>10.1109/ISPDC.2014.16</doi><tpages>8</tpages></addata></record>
fulltext fulltext_linktorsrc
identifier ISSN: 2379-5352
ispartof 2014 IEEE 13th International Symposium on Parallel and Distributed Computing, 2014, p.95-102
issn 2379-5352
language eng
recordid cdi_ieee_primary_6900206
source IEEE Xplore All Conference Series
subjects Bipartite graph
Complexity theory
Distributed databases
Kernel
Measurement
Optimization
Partitioning algorithms
title Determining the Optimal Redistribution for a Given Data Partition
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-02-09T22%3A07%3A01IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-ieee_CHZPO&rft_val_fmt=info:ofi/fmt:kev:mtx:book&rft.genre=proceeding&rft.atitle=Determining%20the%20Optimal%20Redistribution%20for%20a%20Given%20Data%20Partition&rft.btitle=2014%20IEEE%2013th%20International%20Symposium%20on%20Parallel%20and%20Distributed%20Computing&rft.au=Herault,%20Thomas&rft.date=2014-06&rft.spage=95&rft.epage=102&rft.pages=95-102&rft.issn=2379-5352&rft.isbn=1479959189&rft.isbn_list=9781479959181&rft.coden=IEEPAD&rft_id=info:doi/10.1109/ISPDC.2014.16&rft.eisbn=1479959197&rft.eisbn_list=9781479959198&rft_dat=%3Cieee_CHZPO%3E6900206%3C/ieee_CHZPO%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c253t-3d6e0486fdb0ccbc3db8c513f5e1011b887362c815554b00fb8fde5eb73e3e4c3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rft_ieee_id=6900206&rfr_iscdi=true