Automatic data decomposition for message-passing machines.

The data distribution problem is very complex, because it involves trade-off decisions between minimizing communication and maximizing parallelism. A common approach towards solving this problem is to break the data mapping into two stages: an alignment stage and a distribution stage. The alignment stage attempts to increase parallelism, while the distribution stage attempts to decrease communication overhead. As opposed to previous approaches, we consider the alignment and distribution problems in a unified framework, and attempt to simultaneously maximize parallelism and minimize communication overhead. The problem becomes harder if dynamic remapping, multi-dimensional distributions, array replications and control flow are taken into account. This paper formulates the full data decomposition problem that addresses all these issues and presents a simple new algorithm to find the optional solution of the dynamic data distribution problem, given the number of processors and a partitioning of the input program into phases. The algorithm runs efficiently for small search spaces (several hundreds of data distributions).

Main Author: Damian-Iordache, Mirela.
Other Authors: Pemmaraju, Sriram V.
Language: English
Published: 1998
Online Access: http://ezproxy.villanova.edu/login?url=https://digital.library.villanova.edu/Item/vudl:175644
PID vudl:175644
id vudl:175644
modeltype_str_mv vudl-system:CoreModel
vudl-system:CollectionModel
vudl-system:ResourceCollection
datastream_str_mv DC
PARENT-QUERY
PARENT-LIST-RAW
PARENT-LIST
MEMBER-QUERY
MEMBER-LIST-RAW
LEGACY-METS
LICENSE
AGENTS
PROCESS-MD
THUMBNAIL
STRUCTMAP
RELS-EXT
hierarchytype
sequence_vudl_175631_str 0000000005
has_order_str no
hierarchy_top_id vudl:171664
hierarchy_top_title Villanova Digital Collection
hierarchy_parent_id vudl:175631
hierarchy_parent_title Damian Mirela
hierarchy_sequence 0000000005
hierarchy_first_parent_id_str vudl:175644
hierarchy_sequence_sort_str 0000000005
hierarchy_all_parents_str_mv vudl:171664
vudl:172968
vudl:175631
first_indexed 2014-01-11T23:30:06Z
last_indexed 2014-01-11T23:30:06Z
recordtype vudl
fullrecord <root> <url> http://digital.library.villanova.edu/files/vudl:175644/DC </url> <thumbnail> http://digital.library.villanova.edu/files/vudl:175644/THUMBNAIL </thumbnail> </root>
spelling
institution Villanova University
collection Digital Library
language English
dc_source_str_mv Lecture Notes in Computer Science 1366, 1998, 64-78.
author Damian-Iordache, Mirela.
author_s Damian-Iordache, Mirela.
spellingShingle Damian-Iordache, Mirela.
Automatic data decomposition for message-passing machines.
author-letter Damian-Iordache, Mirela.
author_sort_str Damian-Iordache, Mirela.
author2 Pemmaraju, Sriram V.
author2Str Pemmaraju, Sriram V.
dc_title_str Automatic data decomposition for message-passing machines.
title Automatic data decomposition for message-passing machines.
title_short Automatic data decomposition for message-passing machines.
title_full Automatic data decomposition for message-passing machines.
title_fullStr Automatic data decomposition for message-passing machines.
title_full_unstemmed Automatic data decomposition for message-passing machines.
collection_title_sort_str automatic data decomposition for message-passing machines.
title_sort automatic data decomposition for message-passing machines.
description The data distribution problem is very complex, because it involves trade-off decisions between minimizing communication and maximizing parallelism. A common approach towards solving this problem is to break the data mapping into two stages: an alignment stage and a distribution stage. The alignment stage attempts to increase parallelism, while the distribution stage attempts to decrease communication overhead. As opposed to previous approaches, we consider the alignment and distribution problems in a unified framework, and attempt to simultaneously maximize parallelism and minimize communication overhead. The problem becomes harder if dynamic remapping, multi-dimensional distributions, array replications and control flow are taken into account. This paper formulates the full data decomposition problem that addresses all these issues and presents a simple new algorithm to find the optional solution of the dynamic data distribution problem, given the number of processors and a partitioning of the input program into phases. The algorithm runs efficiently for small search spaces (several hundreds of data distributions).
publishDate 1998
normalized_sort_date 1998-01-01T00:00:00Z
dc_date_str 1998
license_str protected
REPOSITORYNAME FgsRepos
REPOSBASEURL http://hades.library.villanova.edu:8088/fedora
fgs.state Active
fgs.label Automatic data decomposition for message-passing machines.
fgs.ownerId diglibEditor
fgs.createdDate 2013-01-22T04:52:56.187Z
fgs.lastModifiedDate 2013-12-05T17:10:18.357Z
dc.title Automatic data decomposition for message-passing machines.
dc.creator Damian-Iordache, Mirela.
Pemmaraju, Sriram V.
dc.description The data distribution problem is very complex, because it involves trade-off decisions between minimizing communication and maximizing parallelism. A common approach towards solving this problem is to break the data mapping into two stages: an alignment stage and a distribution stage. The alignment stage attempts to increase parallelism, while the distribution stage attempts to decrease communication overhead. As opposed to previous approaches, we consider the alignment and distribution problems in a unified framework, and attempt to simultaneously maximize parallelism and minimize communication overhead. The problem becomes harder if dynamic remapping, multi-dimensional distributions, array replications and control flow are taken into account. This paper formulates the full data decomposition problem that addresses all these issues and presents a simple new algorithm to find the optional solution of the dynamic data distribution problem, given the number of processors and a partitioning of the input program into phases. The algorithm runs efficiently for small search spaces (several hundreds of data distributions).
dc.date 1998
dc.identifier vudl:175644
dc.source Lecture Notes in Computer Science 1366, 1998, 64-78.
dc.language en
license.mdRef http://digital.library.villanova.edu/copyright.html
agent.name Falvey Memorial Library, Villanova University
KHL
has_thumbnail true
THUMBNAIL_contentDigest_type MD5
THUMBNAIL_contentDigest_digest 203c69e18f4f46c81e9892448d2c07cd
THUMBNAIL_contentLocation_type INTERNAL_ID
THUMBNAIL_contentLocation_ref http://hades.library.villanova.edu:8088/fedora/get/vudl:175644/THUMBNAIL/2013-01-22T04:52:58.027Z
relsext.hasModel info:fedora/vudl-system:CoreModel
info:fedora/vudl-system:CollectionModel
info:fedora/vudl-system:ResourceCollection
relsext.itemID oai:digital.library.villanova.edu:vudl:175644
relsext.isMemberOf info:fedora/vudl:175631
relsext.hasLegacyURL http://digital.library.villanova.edu/Villanova%20Digital%20Collection/Faculty%20Fulltext/Damian%20Mirela/DamianMirela-393bfef3-db61-4d2b-aea0-0eff4c08be6f.xml
relsext.sortOn title
relsext.sequence vudl:175631#5
_version_ 1504180035542581248
score 13.645308
subpages