Bottleneck Time Minimization for Distributed Iterative Processes: Speeding Up Gossip-Based Federated Learning on Networked Computers
We present a novel task scheduling scheme for accelerating computational applications involving distributed iterative processes that are executed on networked computing resources. Such an application consists of multiple tasks, each of which outputs data at each iteration to be processed by neighbor...
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Article |
| Publié: |
2021
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2106.15048 http://arxiv.org/abs/2106.15048 |
| Tags: |
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1879173075315982336 |
|---|---|
| author | Kiamari, Mehrdad Krishnamachari, Bhaskar |
| author_browse | Kiamari, Mehrdad Krishnamachari, Bhaskar |
| author_facet | Kiamari, Mehrdad Krishnamachari, Bhaskar |
| author_sort | Kiamari, Mehrdad |
| building | arXiv |
| collection | Acceso abierto |
| description | We present a novel task scheduling scheme for accelerating computational applications involving distributed iterative processes that are executed on networked computing resources. Such an application consists of multiple tasks, each of which outputs data at each iteration to be processed by neighboring tasks; these dependencies between the tasks can be represented as a directed graph. We first mathematically formulate the problem as a Binary Quadratic Program (BQP), accounting for both computation and communication costs. We show that the problem is NP-hard. We then relax the problem as a Semi-Definite Program (SDP) and utilize a randomized rounding technique based on sampling from a suitably-formulated multi-variate Gaussian distribution. Furthermore, we derive the expected value of bottleneck time. Finally, we apply our proposed scheme on gossip-based federated learning as an application of iterative processes. Through numerical evaluations on the MNIST and CIFAR-10 datasets, we show that our proposed approach outperforms well-known scheduling techniques from distributed computing. In particular, for arbitrary settings, we show that it reduces bottleneck time by $91\%$ compared to HEFT and $84\%$ compared to throughput HEFT. |
| first_indexed | 2026-10-15T23:51:34Z |
| format | Article |
| fullrecord | <oai_dc:dc xmlns:oai_dc="http://www.openarchives.org/OAI/2.0/oai_dc/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/oai_dc/ https://www.openarchives.org/OAI/2.0/oai_dc.xsd"><identifier>arxiv-2106.15048</identifier><datestamp>2021-06-30</datestamp>
<dc:title>Bottleneck Time Minimization for Distributed Iterative Processes: Speeding Up Gossip-Based Federated Learning on Networked Computers</dc:title>
<dc:creator>Kiamari, Mehrdad</dc:creator>
<dc:creator>Krishnamachari, Bhaskar</dc:creator>
<dc:subject>Distributed, Parallel, and Cluster Computing</dc:subject>
<dc:description>We present a novel task scheduling scheme for accelerating computational applications involving distributed iterative processes that are executed on networked computing resources. Such an application consists of multiple tasks, each of which outputs data at each iteration to be processed by neighboring tasks; these dependencies between the tasks can be represented as a directed graph. We first mathematically formulate the problem as a Binary Quadratic Program (BQP), accounting for both computation and communication costs. We show that the problem is NP-hard. We then relax the problem as a Semi-Definite Program (SDP) and utilize a randomized rounding technique based on sampling from a suitably-formulated multi-variate Gaussian distribution. Furthermore, we derive the expected value of bottleneck time. Finally, we apply our proposed scheme on gossip-based federated learning as an application of iterative processes. Through numerical evaluations on the MNIST and CIFAR-10 datasets, we show that our proposed approach outperforms well-known scheduling techniques from distributed computing. In particular, for arbitrary settings, we show that it reduces bottleneck time by $91\%$ compared to HEFT and $84\%$ compared to throughput HEFT. </dc:description>
<dc:date>2021-06-29</dc:date>
<dc:type>text</dc:type>
<dc:identifier>https://arxiv.org/abs/2106.15048</dc:identifier>
<dc:identifier>http://arxiv.org/abs/2106.15048</dc:identifier>
</oai_dc:dc> |
| id | arxiv-2106.15048 |
| institution | arXiv |
| last_indexed | 2026-10-15T23:51:34Z |
| publishDate | 2021 |
| publishDateRange | 2021 |
| publishDateSort | 2021 |
| record_format | oai_dc |
| spelling | arxiv-2106.150482021-06-30 Bottleneck Time Minimization for Distributed Iterative Processes: Speeding Up Gossip-Based Federated Learning on Networked Computers Kiamari, Mehrdad Krishnamachari, Bhaskar Distributed, Parallel, and Cluster Computing We present a novel task scheduling scheme for accelerating computational applications involving distributed iterative processes that are executed on networked computing resources. Such an application consists of multiple tasks, each of which outputs data at each iteration to be processed by neighboring tasks; these dependencies between the tasks can be represented as a directed graph. We first mathematically formulate the problem as a Binary Quadratic Program (BQP), accounting for both computation and communication costs. We show that the problem is NP-hard. We then relax the problem as a Semi-Definite Program (SDP) and utilize a randomized rounding technique based on sampling from a suitably-formulated multi-variate Gaussian distribution. Furthermore, we derive the expected value of bottleneck time. Finally, we apply our proposed scheme on gossip-based federated learning as an application of iterative processes. Through numerical evaluations on the MNIST and CIFAR-10 datasets, we show that our proposed approach outperforms well-known scheduling techniques from distributed computing. In particular, for arbitrary settings, we show that it reduces bottleneck time by $91\%$ compared to HEFT and $84\%$ compared to throughput HEFT. 2021-06-29 text https://arxiv.org/abs/2106.15048 http://arxiv.org/abs/2106.15048 |
| spellingShingle | Distributed, Parallel, and Cluster Computing Kiamari, Mehrdad Krishnamachari, Bhaskar Bottleneck Time Minimization for Distributed Iterative Processes: Speeding Up Gossip-Based Federated Learning on Networked Computers |
| title | Bottleneck Time Minimization for Distributed Iterative Processes: Speeding Up Gossip-Based Federated Learning on Networked Computers |
| title_full | Bottleneck Time Minimization for Distributed Iterative Processes: Speeding Up Gossip-Based Federated Learning on Networked Computers |
| title_fullStr | Bottleneck Time Minimization for Distributed Iterative Processes: Speeding Up Gossip-Based Federated Learning on Networked Computers |
| title_full_unstemmed | Bottleneck Time Minimization for Distributed Iterative Processes: Speeding Up Gossip-Based Federated Learning on Networked Computers |
| title_short | Bottleneck Time Minimization for Distributed Iterative Processes: Speeding Up Gossip-Based Federated Learning on Networked Computers |
| title_sort | bottleneck time minimization for distributed iterative processes speeding up gossip based federated learning on networked computers |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2106.15048 http://arxiv.org/abs/2106.15048 |
| work_keys_str_mv | AT kiamarimehrdad bottlenecktimeminimizationfordistributediterativeprocessesspeedingupgossipbasedfederatedlearningonnetworkedcomputers AT krishnamacharibhaskar bottlenecktimeminimizationfordistributediterativeprocessesspeedingupgossipbasedfederatedlearningonnetworkedcomputers |