2026-05-05T23:01:01Zhttps://uvadoc.uva.es/oai/requestoai:uvadoc.uva.es:10324/755342025-04-07T19:01:05Zcom_10324_1165com_10324_931com_10324_894col_10324_1337
UVaDOC
author
Fresno Bausela, Javier
author
González Escribano, Arturo
author
Llanos Ferraris, Diego Rafael
2025-04-07T08:03:46Z
2025-04-07T08:03:46Z
2011
19th International Euromicro Conference on Parallel, Distributed and Network-based Processing, PDP 2011, Ayia Napa, Cyprus, 9-11 February 2011
978-0-7695-4328-4
https://uvadoc.uva.es/handle/10324/75534
10.1109/PDP.2011.38
This paper studies the impact of using automatic data-layout techniques on the process of coding the well-known multigrid MG NAS parallel benchmark. We describe the sequential problem in detail, and discuss the parallel version and its optimizations. Then, we implement the parallel algorithm using Hitmap, a highly-efficient modular library for hierarchical tiling and mapping of arrays. We describe how to use the library plug-in system to add a new data-layout module that encapsulates a generalization of the data-alignment policy of the MG benchmark. The module system applies this policy to automatically adapt the data distribution and communication code to any grain level. The impact of using these techniques is qualitatively and quantitatively described in terms of development effort and performance. Our results show that it is possible to introduce flexible automatic data-layout techniques in current parallel compiler technology, without sacrificing performance.
eng
Informática
Automatic Data Partitioning Applied to Multigrid PDE Solvers
info:eu-repo/semantics/conferenceObject
77u/QUNVRVJETyBERSAgRURJQ0nDk04gRUxFQ1RSw5NOSUNBIFkgRElGVVNJw5NOIEVOIElOVEVSTkVUIAoKRWwgb2JqZXRpdm8gZnVuZGFtZW50YWwgZGVsIFJlcG9zaXRvcmlvIEluc3RpdHVjaW9uYWwgIGVzICBsYSBkaXZ1bGdhY2nDs24gZGUgbGEgUFJPRFVDQ0nDk04gQ0lFTlTDjUZJQ0EgCmRlIGxhIFVuaXZlcnNpZGFkICBkZSBWYWxsYWRvbGlkLCBwYXJhIGxvIGN1YWwgbGEgVW5pdmVyc2lkYWQgcG9uZSBsb3MgbWVkaW9zIHTDqWNuaWNvcyBuZWNlc2FyaW9zIG9mcmVjaWVuZG8gIHVuYSAgCmJhc2UgIGRlICBkYXRvcyAgYSB0ZXh0byBjb21wbGV0byB5IGVuIGZvcm1hdG8gZWxlY3Ryw7NuaWNvLCBhIHRyYXbDqXMgZGUgSW50ZXJuZXQsIGZhY2lsaXRhbmRvIGFzw60gCmxhIHZpc2liaWxpZGFkIHkgYWNjZXNvIGEgbGEgaW5mb3JtYWNpw7NuIGNpZW50w61maWNhIHkgdMOpY25pY2EuCgpQYXJhICBxdWUgIGVsIFJlcG9zaXRvcmlvIGRlIGxhIFVuaXZlcnNpZGFkIGRlIFZhbGxhZG9saWQgcHVlZGEgcmVwcm9kdWNpciAgeSAgY29tdW5pY2FyIHDDumJsaWNhbWVudGUgc3UgCmRvY3VtZW50byBlcyBuZWNlc2FyaW8gbGEgYWNlcHRhY2nDs24gZGUgbG9zIHNpZ3VpZW50ZXMgdMOpcm1pbm9zLgoKQWNlcHRhbmRvIGVzdGUgQWN1ZXJkbywgdXN0ZWQgIE1BTklGSUVTVEE6CgpQUklNRVJPOiBTZXIgIEVsIGF1dG9yIGRlIGVzdGUgVHJhYmFqbyB5IHRpdHVsYXIgZGUgbG9zIGRlcmVjaG9zIGRlICBwcm9waWVkYWQgIGludGVsZWN0dWFsLiAgTWFuaWZlc3RhbmRvICBxdWUgc29icmUgCmxhIG1pc21hIG5vIHRpZW5lIGNvbnRyYcOtZG9zIG5pIGNvbnRyYWVyw6EgY29tcHJvbWlzb3MgbyBncmF2w6FtZW5lcyBkZSBuaW5ndW5hIGVzcGVjaWUgIHF1ZSBhdGVudGVuIApjb250cmEgbG9zIGRlcmVjaG9zIHF1ZSBhIGxhIFVuaXZlcnNpZGFkIGxlIGNvcnJlc3BvbmRhbi4KU0VHVU5ETzogUXVlIGVsIGRvY3VtZW50byBlcyB1biB0cmFiYWpvIG9yaWdpbmFsIHN1eW8geSBxdWUgdGllbmUgZGVyZWNobyAgcGFyYSAgb3RvcmdhciAgIGxvcyBkZXJlY2hvcyBjb250ZW5pZG9zIAplbiBlc3RlIGFjdWVyZG8uIApEZWNsYXJhICBxdWUgIHN1IGRvY3VtZW50byBubyBpbmZyaW5nZSwgZW4gdGFudG8gZW4gY3VhbnRvIGxlIHNlYSBwb3NpYmxlICBzYWJlciwgIGxvcyAgZGVyZWNob3MgZGUgYXV0b3IgZGUgbmluZ3VuYSAKb3RyYSBwZXJzb25hIG8gZW50aWRhZC4KVEVSQ0VSTzogU2kgZWwgZG9jdW1lbnRvIGNvbnRpZW5lIG1hdGVyaWFsZXMgZGUgbG9zIGN1YWxlcyBubyB0aWVuZSBsb3MgIGRlcmVjaG8gIGRlICBhdXRvciwgIGRlY2xhcmEgIHF1ZSAgaGEgIG9idGVuaWRvCmVsIHBlcm1pc28gc2luIHJlc3RyaWNjacOzbiBkZWwgcHJvcGlldGFyaW8gZGUgbG9zIGRlcmVjaG8gZGUgYXV0b3IgcGFyYSBvdG9yZ2FyIGEgbGEgIFVuaXZlcnNpZGFkICBkZSAgVmFsbGFkb2xpZCwgIApsb3MgIGRlcmVjaG8gIHJlcXVlcmlkb3MgcG9yIGVzdGUgQWN1ZXJkbyAgeSAgcXVlICBlc2UgbWF0ZXJpYWwgIGN1eW9zICBkZXJlY2hvcyBzb24gZGUgdGVyY2Vyb3MgZXN0w6EgY2xhcmFtZW50ZSAgCmlkZW50aWZpY2FkbyB5ICByZWNvbm9jaWRvICBlbiBlbCB0ZXh0byBvIGNvbnRlbmlkbyBkZWwgZG9jdW1lbnRvIGVudHJlZ2Fkby4KQ1VBUlRPOiBTaSBlbCBkb2N1bWVudG8gc2UgYmFzYSBlbiB1bmEgb2JyYSBxdWUgaGEgc2lkbyBwYXRyb2NpbmFkYQpvIGFwb3lhZGEgcG9yIHVuYSBhZ2VuY2lhIHUgb3JnYW5pemFjacOzbiBkaWZlcmVudGUgZGUgbGEgVW5pdmVyc2lkYWQgZGUgVmFsbGFkb2xpZCBzZSBwcmVzdXBvbmUgcXVlIHNlIGhhIGN1bXBsaWRvIApjb24gY3VhbHF1aWVyIGRlcmVjaG8gZGUgcmV2aXNpw7puIHUgb3RyYXMgb2JsaWdhY2lvbmVzIHJlcXVlcmlkYXMgcG9yIGVzdGUgQWN1ZXJkby4KUVVJTlRPOiBSZWNvbm9jZXIgcXVlIGFjZXB0YW5kbyBlc3RlIEFjdWVyZG8sIGVmZWN0w7phIHVuYSAgY2VzacOzbiAKbm8gZXhjbHVzaXZhIGRlIGVzdGUgVHJhYmFqbyBhIGxhIFVuaXZlcnNpZGFkIGRlIFZhbGxhZG9saWQsICBjb24gY2Fyw6FjdGVyICBncmF0dWl0byB5ICBjb24gZmluZXMgZXhjbHVzaXZhbWVudGUgZGUgCmludmVzdGlnYWNpw7NuIHkgZG9jZW5jaWEsICBhc8OtICBjb21vICBsYSAgY2VzacOzbiBubyBleGNsdXNpdmEgZGUgIGxvcyBkZXJlY2hvcyBkZSByZXByb2R1Y2Npw7NuLCAKY29tdW5pY2FjacOzbiAgeSAgZGlzdHJpYnVjacOzbiAgZGUgIHN1ICB0cmFiYWpvIG11bmRpYWxtZW50ZSwgZW4gZm9ybWF0byBlbGVjdHLDs25pY28gcGFyYSBzdSBkaWZ1c2nDs24gCnDDumJsaWNhLiAKTGEgdGl0dWxhcmlkYWQgZGUgbG9zIGRlcmVjaG9zIGRlIGV4cGxvdGFjacOzbiBkZSBsYSBwcm9waWVkYWQgaW50ZWxlY3R1YWwgc29icmUgbGEgb2JyYSBwZXJ0ZW5lY2UgeSBzZWd1aXLDoSAKcGVydGVuZWNpZW5kbyBhbCBBdXRvci4KCkxhIFVuaXZlcnNpZGFkIGRlIFZhbGxhZG9saWQsIGVuIHZpcnR1ZCBkZWwgcHJlc2VudGUgQWN1ZXJkbyAKREVDTEFSQSBRdWU6CgpQUklNRVJPOiBBbGJlcmdhcsOhIGVuIGVsIHJlcG9zaXRvcmlvIGluc3RpdHVjaW9uYWwgZGUgbGEgVW5pdmVyc2lkYWQgZGUgIFZhbGxhZG9saWQgIGVzdGUgVHJhYmFqby4gU2luIHBlcmp1aWNpbyBkZSBxdWUgCmVuIHVuIGZ1dHVybywgY29uIGVsIG9iamV0aXZvIGRlIGNvbnNlZ3VpciB1bmEgbWF5b3IgZGlmdXNpw7NuLCBzZWEgcmVjb2dpZG8gdGFtYmnDqW4gZW4gb3Ryb3MgcmVwb3NpdG9yaW9zIHF1ZSAKcHVlZGFuIGNvbnN0aXR1aXJzZSBhIG5pdmVsIHJlZ2lvbmFsLG5hY2lvbmFsIG8gaW50ZXJuYWNpb25hbC4gClNFR1VORE86IExhIFVuaXZlcnNpZGFkIGRlIFZhbGxhZG9saWQgcG9uZHLDoSBhIGRpc3Bvc2ljacOzbiBkZSBzdXMgdXN1YXJpb3MgbGEgIFBST0RVQ0NJw5NOIENJRU5Uw41GSUNBIApwYXJhIGVsIHVzbyBwcml2YWRvIHkgZmluZXMgZGUgaW52ZXN0aWdhY2nDs24gIHkgIGRvY2VuY2lhICBhdW5xdWUgIG5vIGdhcmFudGl6YSBuaSBhc3VtZSBuaW5ndW5hIHJlc3BvbnNhYmlsaWRhZCAgcG9yICAKbGFzICBmb3JtYXMgIGVuICBxdWUgIGxvcyAgdXN1YXJpb3MgIGhhZ2FuIHBvc3Rlcmlvcm1lbnRlIHVzbyBkZSBzdSBUcmFiYWpvLgpURVJDRVJPOiBMYSBVbml2ZXJzaWRhZCBubyB0aWVuZSBsYSBpbnRlbmNpw7NuIGRlIGNlbnN1cmFyIG5pIHJldmlzYXIgZWwgVHJhYmFqbyBkZWwgYXV0b3IgeSBlbiBjb25zZWN1ZW5jaWEgc2Vyw6EgCmVsIGF1dG9yICByZXNwb25zYWJsZSBkZWwgY29udGVuaWRvIGRlIHN1IG9icmEuCkNVQVJUTzogRW4gZWwgcmVwb3NpdG9yaW8gaW5zdGl0dWNpb25hbCBkZSBsYSBVbml2ZXJzaWRhZCBkZSBWYWxsYWRvbGlkICBzZSBoYXLDoSBtZW5jacOzbiBleHByZXNhIGEgbG9zIHVzb3MgCmF1dG9yaXphZG9zIGRlIGxhIG9icmEsIGJham8gbGEgbGljZW5jaWEgQ3JlYXRpdmUgQ29tbW9ucyBzZWxlY2Npb25hZGFzIHBvciBlbCBhdXRvciBkZWwgVHJhYmFqby4KCkVsIHByZXNlbnRlIEFjdWVyZG8gZW50cmFyw6EgZW4gdmlnb3IgZW4gZXN0ZSBtb21lbnRvIHkgdGVuZHLDoSB1bmEgZHVyYWNpw7NuIGluZGVmaW5pZGEuIFNpbiBwZXJqdWljaW8gZGUgCmVzdGEgZHVyYWNpw7NuIGluZGVmaW5pZGEgaW5pY2lhbG1lbnRlIHBhY3RhZGEsIHNlIHBvZHLDoSBwb25lciBmaW4gYWwgcHJlc2VudGUgQWN1ZXJkbzogcG9yIHZvbHVudGFkIGRlIGxhcyBwYXJ0ZXMsIApwb3IgaW5jdW1wbGltaWVudG8gZGUgY3VhbHF1aWVyYSBkZSBsYXMgb2JsaWdhY2lvbmVzIGRlcml2YWRhcyBkZWwgQWN1ZXJkbywgcG9yIHZvbHVudGFkIGV4cHJlc2EgZGVsIEF1dG9yCkVuICBwcnVlYmEgZGUgY29uZm9ybWlkYWQsIGxhcyBwYXJ0ZXMgYWNlcHRhbiBlbCBwcmVzZW50ZSBBY3VlcmRvCgoKCgo=
URL
https://uvadoc.uva.es/bitstream/10324/75534/1/Automatic_Data_Partitioning_Applied_to_Multigrid_PDE_Solvers.pdf
File
MD5
5b9288ac3a54ad3f18bc4b1299751b18
368062
application/pdf
Automatic_Data_Partitioning_Applied_to_Multigrid_PDE_Solvers.pdf