{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/92959"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/92959","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Towards a deeper understanding of hybrid programming","abstract":"With the end of Dennard scaling, future high performance computers are expected to consist of distributed nodes that comprise more cores with direct access to shared memory on a node. However, many parallel applications still use a pure message-passing programming model based on the message-passing interface (MPI). Thereby, they potentially do not make optimal use of shared memory resources. The pure message-passing approach---as argued in this work---is not necessarily the best fit to current and future supercomputing architectures. In this thesis, I therefore present a detailed performance analysis of so-called hybrid programming models that aim at improving performance by combining a shared memory model with the message-passing model on current symmetric multiprocessor (SMP) systems. First, inter-node communication performance is investigated in the context of (hybrid) message-passing programs. A novel performance model for estimating communication performance on current SMP nodes is presented. As is demonstrated, in contrast to the typically used classic postal performance model, the new model allows to more accurately predict inter-node communication performance in the presence of simultaneously communicating processes and saturation of the network interface controller on current multicore architectures. The implications of the new model on hybrid programs are discussed. In addition, I demonstrate the (current) difficulties of multithreaded MPI communication based on results obtained for a multithreaded ping pong benchmark. Moreover, I show how intra-node MPI communication performance can significantly be improved upon for small to medium size messages by saving message-passing overhead and/or superior cache usage. This is achieved through a direct copy in shared memory using either the hybrid MPI+MPI or the MPI+OpenMP programming method. Furthermore, I contrast and evaluate several (pure and hybrid) implementation options for a structured grid sparse matrix-vector multiplication in depth. These choices differ in how hybrid parallelism is exploited at the application level (coarse-grained vs. fine-grained problem decomposition) and with respect to the hybrid programming systems (pure MPI vs. MPI+MPI vs. MPI+OpenMP). I discuss their performance factors such as locality, overhead, efficient use of MPI's derived datatypes, and the serial fraction in Amdahl's law. Moreover, I experimentally demonstrate how a coarse-grained hybrid application design can be used to control these factors, resulting in significant performance improvements (compared to a pure MPI parallelization) in communication and/or synchronization for both the hybrid MPI+MPI and MPI+OpenMP parallel programming approaches for different grid decompositions.","abstract_html":"With the end of Dennard scaling, future high performance computers are expected to consist of distributed nodes that comprise more cores with direct access to shared memory on a node. However, many parallel applications still use a pure message-passing programming model based on the message-passing interface (MPI). Thereby, they potentially do not make optimal use of shared memory resources. The pure message-passing approach---as argued in this work---is not necessarily the best fit to current and future supercomputing architectures. In this thesis, I therefore present a detailed performance analysis of so-called hybrid programming models that aim at improving performance by combining a shared memory model with the message-passing model on current symmetric multiprocessor (SMP) systems. First, inter-node communication performance is investigated in the context of (hybrid) message-passing programs. A novel performance model for estimating communication performance on current SMP nodes is presented. As is demonstrated, in contrast to the typically used classic postal performance model, the new model allows to more accurately predict inter-node communication performance in the presence of simultaneously communicating processes and saturation of the network interface controller on current multicore architectures. The implications of the new model on hybrid programs are discussed. In addition, I demonstrate the (current) difficulties of multithreaded MPI communication based on results obtained for a multithreaded ping pong benchmark. Moreover, I show how intra-node MPI communication performance can significantly be improved upon for small to medium size messages by saving message-passing overhead and/or superior cache usage. This is achieved through a direct copy in shared memory using either the hybrid MPI+MPI or the MPI+OpenMP programming method. Furthermore, I contrast and evaluate several (pure and hybrid) implementation options for a structured grid sparse matrix-vector multiplication in depth. These choices differ in how hybrid parallelism is exploited at the application level (coarse-grained vs. fine-grained problem decomposition) and with respect to the hybrid programming systems (pure MPI vs. MPI+MPI vs. MPI+OpenMP). I discuss their performance factors such as locality, overhead, efficient use of MPI's derived datatypes, and the serial fraction in Amdahl's law. Moreover, I experimentally demonstrate how a coarse-grained hybrid application design can be used to control these factors, resulting in significant performance improvements (compared to a pure MPI parallelization) in communication and/or synchronization for both the hybrid MPI+MPI and MPI+OpenMP parallel programming approaches for different grid decompositions.","abstract_has_math":false,"creators":["Samfass, Philipp Johannes"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Gropp, William","Olson, Luke N."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2016,"date_issued":"2016-11-10T18:27:54Z","date_published":"2016-11-10T18:27:54Z","updated_at":"2026-07-22T22:26:35Z","subjects":["hybrid programming models","performance modeling","ping pong benchmark","Message-passing interface (MPI)","OpenMP","MPI+X","MPI shared memory","parallel computing","sparse matrix-vector multiplication"],"languages":["en"],"rights":["Copyright 2016 Philipp Samfass"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/92959","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Gropp, William","Olson, Luke N."]},{"key":"dc:creator","label":"Author","values":["Samfass, Philipp Johannes"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2016-11-10T18:27:54Z","2024-02-21T06:00:00Z","2016-07-18","2016-08"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["hybrid programming models","performance modeling","ping pong benchmark","Message-passing interface (MPI)","OpenMP","MPI+X","MPI shared memory","parallel computing","sparse matrix-vector multiplication"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2016 Philipp Samfass"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/92959"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["With the end of Dennard scaling, future high performance computers are expected to consist of distributed nodes that comprise more cores with direct access to shared memory on a node. However, many parallel applications still use a pure message-passing programming model based on the message-passing interface (MPI). Thereby, they potentially do not make optimal use of shared memory resources. The pure message-passing approach---as argued in this work---is not necessarily the best fit to current and future supercomputing architectures. In this thesis, I therefore present a detailed performance analysis of so-called hybrid programming models that aim at improving performance by combining a shared memory model with the message-passing model on current symmetric multiprocessor (SMP) systems. First, inter-node communication performance is investigated in the context of (hybrid) message-passing programs. A novel performance model for estimating communication performance on current SMP nodes is presented. As is demonstrated, in contrast to the typically used classic postal performance model, the new model allows to more accurately predict inter-node communication performance in the presence of simultaneously communicating processes and saturation of the network interface controller on current multicore architectures. The implications of the new model on hybrid programs are discussed. In addition, I demonstrate the (current) difficulties of multithreaded MPI communication based on results obtained for a multithreaded ping pong benchmark. Moreover, I show how intra-node MPI communication performance can significantly be improved upon for small to medium size messages by saving message-passing overhead and/or superior cache usage. This is achieved through a direct copy in shared memory using either the hybrid MPI+MPI or the MPI+OpenMP programming method. Furthermore, I contrast and evaluate several (pure and hybrid) implementation options for a structured grid sparse matrix-vector multiplication in depth. These choices differ in how hybrid parallelism is exploited at the application level (coarse-grained vs. fine-grained problem decomposition) and with respect to the hybrid programming systems (pure MPI vs. MPI+MPI vs. MPI+OpenMP). I discuss their performance factors such as locality, overhead, efficient use of MPI's derived datatypes, and the serial fraction in Amdahl's law. Moreover, I experimentally demonstrate how a coarse-grained hybrid application design can be used to control these factors, resulting in significant performance improvements (compared to a pure MPI parallelization) in communication and/or synchronization for both the hybrid MPI+MPI and MPI+OpenMP parallel programming approaches for different grid decompositions.","Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2018-08-01","The student, Philipp Samfass, accepted the attached license on 2016-07-15 at 15:00.","The student, Philipp Samfass, submitted this Thesis for approval on 2016-07-15 at 15:14.","This Thesis was approved for publication on 2016-07-18 at 10:36.","DSpace SAF Submission Ingestion Package generated from Vireo submission #9967 on 2016-11-10 at 12:20:53","Made available in DSpace on 2016-11-10T18:27:54Z (GMT). No. of bitstreams: 2 SAMFASS-THESIS-2016.pdf: 2155481 bytes, checksum: aacd2529681a470b3da93cf0a53f3a89 (MD5) LICENSE.txt: 4221 bytes, checksum: d5d30dab0355066c5663edb8e59d34ff (MD5) Previous issue date: 2016-07-18","Embargo set by: Seth Robbins for item 95379 Lift date: 2018-11-10T18:28:02Z Reason: Author requested closed access (OA after 2yrs) in Vireo ETD system","U of I Only Restriction set for Item 95379 on 2018-08-08T16:35:25Z with date 2020-08-08 by astein@illinois.edu.","U of I Only Restriction set for Item 95379 on 2018-08-08T16:35:47Z with date 2020-08-08 by astein@illinois.edu.","U of I Only Restriction set for Item 95379 on 2020-07-23T17:55:31Z with date 2022-08-08 by lac7@illinois.edu.","U of I Only Restriction set for Item 95379 on 2020-07-23T17:55:42Z with date 2022-08-08 by lac7@illinois.edu.","U of I Only Restriction set for Item 95379 on 2020-07-23T17:55:55Z with date 2022-08-08 by lac7@illinois.edu.","U of I Only Restriction set for Item 95379 on 2022-02-21T20:54:42Z with date 2024-02-21 by eliasbh2@illinois.edu.","U of I Only Restriction set for Item 95379 on 2022-02-21T20:54:56Z with date 2024-02-21 by eliasbh2@illinois.edu.","U of I Only Restriction set for Item 95379 on 2022-02-21T20:55:02Z with date 2024-02-21 by eliasbh2@illinois.edu.","Graduate College Thesis Office and IDEALS Team approved extension request from author to change restriction to U of I Access for a period of two years. Implemented by eliasbh2@illinois.edu on 2022-02-21 at 2:54 PM CDT","U of I Only"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Towards a deeper understanding of hybrid programming"]}]}],"canonical_facts":{"dc:contributor":["Gropp, William","Olson, Luke N."],"dc:creator":["Samfass, Philipp Johannes"],"dc:date":["2016-11-10T18:27:54Z","2024-02-21T06:00:00Z","2016-07-18","2016-08"],"dc:description":["With the end of Dennard scaling, future high performance computers are expected to consist of distributed nodes that comprise more cores with direct access to shared memory on a node. However, many parallel applications still use a pure message-passing programming model based on the message-passing interface (MPI). Thereby, they potentially do not make optimal use of shared memory resources. The pure message-passing approach---as argued in this work---is not necessarily the best fit to current and future supercomputing architectures. In this thesis, I therefore present a detailed performance analysis of so-called hybrid programming models that aim at improving performance by combining a shared memory model with the message-passing model on current symmetric multiprocessor (SMP) systems. First, inter-node communication performance is investigated in the context of (hybrid) message-passing programs. A novel performance model for estimating communication performance on current SMP nodes is presented. As is demonstrated, in contrast to the typically used classic postal performance model, the new model allows to more accurately predict inter-node communication performance in the presence of simultaneously communicating processes and saturation of the network interface controller on current multicore architectures. The implications of the new model on hybrid programs are discussed. In addition, I demonstrate the (current) difficulties of multithreaded MPI communication based on results obtained for a multithreaded ping pong benchmark. Moreover, I show how intra-node MPI communication performance can significantly be improved upon for small to medium size messages by saving message-passing overhead and/or superior cache usage. This is achieved through a direct copy in shared memory using either the hybrid MPI+MPI or the MPI+OpenMP programming method. Furthermore, I contrast and evaluate several (pure and hybrid) implementation options for a structured grid sparse matrix-vector multiplication in depth. These choices differ in how hybrid parallelism is exploited at the application level (coarse-grained vs. fine-grained problem decomposition) and with respect to the hybrid programming systems (pure MPI vs. MPI+MPI vs. MPI+OpenMP). I discuss their performance factors such as locality, overhead, efficient use of MPI's derived datatypes, and the serial fraction in Amdahl's law. Moreover, I experimentally demonstrate how a coarse-grained hybrid application design can be used to control these factors, resulting in significant performance improvements (compared to a pure MPI parallelization) in communication and/or synchronization for both the hybrid MPI+MPI and MPI+OpenMP parallel programming approaches for different grid decompositions.","Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2018-08-01","The student, Philipp Samfass, accepted the attached license on 2016-07-15 at 15:00.","The student, Philipp Samfass, submitted this Thesis for approval on 2016-07-15 at 15:14.","This Thesis was approved for publication on 2016-07-18 at 10:36.","DSpace SAF Submission Ingestion Package generated from Vireo submission #9967 on 2016-11-10 at 12:20:53","Made available in DSpace on 2016-11-10T18:27:54Z (GMT). No. of bitstreams: 2 SAMFASS-THESIS-2016.pdf: 2155481 bytes, checksum: aacd2529681a470b3da93cf0a53f3a89 (MD5) LICENSE.txt: 4221 bytes, checksum: d5d30dab0355066c5663edb8e59d34ff (MD5) Previous issue date: 2016-07-18","Embargo set by: Seth Robbins for item 95379 Lift date: 2018-11-10T18:28:02Z Reason: Author requested closed access (OA after 2yrs) in Vireo ETD system","U of I Only Restriction set for Item 95379 on 2018-08-08T16:35:25Z with date 2020-08-08 by astein@illinois.edu.","U of I Only Restriction set for Item 95379 on 2018-08-08T16:35:47Z with date 2020-08-08 by astein@illinois.edu.","U of I Only Restriction set for Item 95379 on 2020-07-23T17:55:31Z with date 2022-08-08 by lac7@illinois.edu.","U of I Only Restriction set for Item 95379 on 2020-07-23T17:55:42Z with date 2022-08-08 by lac7@illinois.edu.","U of I Only Restriction set for Item 95379 on 2020-07-23T17:55:55Z with date 2022-08-08 by lac7@illinois.edu.","U of I Only Restriction set for Item 95379 on 2022-02-21T20:54:42Z with date 2024-02-21 by eliasbh2@illinois.edu.","U of I Only Restriction set for Item 95379 on 2022-02-21T20:54:56Z with date 2024-02-21 by eliasbh2@illinois.edu.","U of I Only Restriction set for Item 95379 on 2022-02-21T20:55:02Z with date 2024-02-21 by eliasbh2@illinois.edu.","Graduate College Thesis Office and IDEALS Team approved extension request from author to change restriction to U of I Access for a period of two years. Implemented by eliasbh2@illinois.edu on 2022-02-21 at 2:54 PM CDT","U of I Only"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/92959"],"dc:language":["en"],"dc:rights":["Copyright 2016 Philipp Samfass"],"dc:subject":["hybrid programming models","performance modeling","ping pong benchmark","Message-passing interface (MPI)","OpenMP","MPI+X","MPI shared memory","parallel computing","sparse matrix-vector multiplication"],"dc:title":["Towards a deeper understanding of hybrid programming"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:35Z"}