Distributed-Memory Load Balancing With Cyclic Token-Based Work-Stealing Applied to Reverse Time Migration
Reverse time migration (RTM) is a prominent technique in seismic imaging. Its resulting subsurface images are used in the industry to investigate with higher confidence the existence and the conditions of oil and gas reservoirs. Because of its high computational cost, RTM must make use of parallel c...
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2019-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/8822671/ |
| _version_ | 1828908835893411840 |
|---|---|
| author | Italo A. S. Assis Antonio D. S. Oliveira Tiago Barros Idalmis M. Sardina Calebe P. Bianchini Samuel Xavier De-Souza |
| author_facet | Italo A. S. Assis Antonio D. S. Oliveira Tiago Barros Idalmis M. Sardina Calebe P. Bianchini Samuel Xavier De-Souza |
| author_sort | Italo A. S. Assis |
| collection | DOAJ |
| description | Reverse time migration (RTM) is a prominent technique in seismic imaging. Its resulting subsurface images are used in the industry to investigate with higher confidence the existence and the conditions of oil and gas reservoirs. Because of its high computational cost, RTM must make use of parallel computers. Balancing the workload distribution of an RTM is a growing challenge in distributed computing systems. The competition for shared resources and the differently-sized tasks of the RTM are some of the possible sources of load imbalance. Although many load balancing techniques exist, scaling up for large problems and large systems remains a challenge because synchronization overhead also scales. This paper proposes a cyclic token-based work-stealing (CTWS) algorithm for distributed memory systems applied to RTM. The novel cyclic token approach reduces the number of failed steals, avoids communication overhead, and simplifies the victim selection and the termination strategy. The proposed method is implemented as a C library using the one-sided communication feature of the message passing interface (MPI) standard. Results obtained by applying the proposed technique to balance the workload of a 3D RTM system present a factor of 14.1% speedup and reductions of the load imbalance of 78.4% when compared to the conventional static distribution. |
| first_indexed | 2024-12-13T18:17:11Z |
| format | Article |
| id | doaj.art-9b47d35dde874352a6b573fcacc6b277 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-12-13T18:17:11Z |
| publishDate | 2019-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-9b47d35dde874352a6b573fcacc6b2772022-12-21T23:35:49ZengIEEEIEEE Access2169-35362019-01-01712841912843010.1109/ACCESS.2019.29391008822671Distributed-Memory Load Balancing With Cyclic Token-Based Work-Stealing Applied to Reverse Time MigrationItalo A. S. Assis0https://orcid.org/0000-0003-4122-3115Antonio D. S. Oliveira1Tiago Barros2Idalmis M. Sardina3Calebe P. Bianchini4https://orcid.org/0000-0001-7683-3437Samuel Xavier De-Souza5Departamento de Engenharia de Computação e Automação, Universidade Federal do Rio Grande do Norte, Natal, RN, BrazilDepartamento de Engenharia de Computação e Automação, Universidade Federal do Rio Grande do Norte, Natal, RN, BrazilDepartamento de Engenharia de Computação e Automação, Universidade Federal do Rio Grande do Norte, Natal, RN, BrazilEscola de Ciências e Tecnologia, Universidade Federal do Rio Grande do Norte, Natal, RN, BrazilFaculdade de Computação e Informática, Universidade Presbiteriana Mackenzie, São Paulo, SP, BrazilDepartamento de Engenharia de Computação e Automação, Universidade Federal do Rio Grande do Norte, Natal, RN, BrazilReverse time migration (RTM) is a prominent technique in seismic imaging. Its resulting subsurface images are used in the industry to investigate with higher confidence the existence and the conditions of oil and gas reservoirs. Because of its high computational cost, RTM must make use of parallel computers. Balancing the workload distribution of an RTM is a growing challenge in distributed computing systems. The competition for shared resources and the differently-sized tasks of the RTM are some of the possible sources of load imbalance. Although many load balancing techniques exist, scaling up for large problems and large systems remains a challenge because synchronization overhead also scales. This paper proposes a cyclic token-based work-stealing (CTWS) algorithm for distributed memory systems applied to RTM. The novel cyclic token approach reduces the number of failed steals, avoids communication overhead, and simplifies the victim selection and the termination strategy. The proposed method is implemented as a C library using the one-sided communication feature of the message passing interface (MPI) standard. Results obtained by applying the proposed technique to balance the workload of a 3D RTM system present a factor of 14.1% speedup and reductions of the load imbalance of 78.4% when compared to the conventional static distribution.https://ieeexplore.ieee.org/document/8822671/Load balancingreverse time migrationwork-stealingone-sided communicationdistributed memory |
| spellingShingle | Italo A. S. Assis Antonio D. S. Oliveira Tiago Barros Idalmis M. Sardina Calebe P. Bianchini Samuel Xavier De-Souza Distributed-Memory Load Balancing With Cyclic Token-Based Work-Stealing Applied to Reverse Time Migration IEEE Access Load balancing reverse time migration work-stealing one-sided communication distributed memory |
| title | Distributed-Memory Load Balancing With Cyclic Token-Based Work-Stealing Applied to Reverse Time Migration |
| title_full | Distributed-Memory Load Balancing With Cyclic Token-Based Work-Stealing Applied to Reverse Time Migration |
| title_fullStr | Distributed-Memory Load Balancing With Cyclic Token-Based Work-Stealing Applied to Reverse Time Migration |
| title_full_unstemmed | Distributed-Memory Load Balancing With Cyclic Token-Based Work-Stealing Applied to Reverse Time Migration |
| title_short | Distributed-Memory Load Balancing With Cyclic Token-Based Work-Stealing Applied to Reverse Time Migration |
| title_sort | distributed memory load balancing with cyclic token based work stealing applied to reverse time migration |
| topic | Load balancing reverse time migration work-stealing one-sided communication distributed memory |
| url | https://ieeexplore.ieee.org/document/8822671/ |
| work_keys_str_mv | AT italoasassis distributedmemoryloadbalancingwithcyclictokenbasedworkstealingappliedtoreversetimemigration AT antoniodsoliveira distributedmemoryloadbalancingwithcyclictokenbasedworkstealingappliedtoreversetimemigration AT tiagobarros distributedmemoryloadbalancingwithcyclictokenbasedworkstealingappliedtoreversetimemigration AT idalmismsardina distributedmemoryloadbalancingwithcyclictokenbasedworkstealingappliedtoreversetimemigration AT calebepbianchini distributedmemoryloadbalancingwithcyclictokenbasedworkstealingappliedtoreversetimemigration AT samuelxavierdesouza distributedmemoryloadbalancingwithcyclictokenbasedworkstealingappliedtoreversetimemigration |