Dynamic multi phase scheduling for heterogeneous clusters. Ciorba, F. M., Andronikos, T., Riakiotakis, I., Chronopoulos, A. T., & Papakonstantinou, G. In Proceedings of the 20th IEEE International Parallel and Distributed Processing Symposium (IPDPS 2006), pages 10–18, April, 2006. doi abstract bibtex Distributed computing systems are a viable and less expensive alternative to parallel computers. However, concurrent programming methods in distributed systems have not been studied as extensively as for parallel computers. Some of the main research issues are how to deal with scheduling and load balancing of such a system, which may consist of heterogeneous computers. In the past, a variety of dynamic scheduling schemes suitable for parallel loops (with independent iterations) on heterogeneous computer clusters have been obtained and studied. However, no study of dynamic schemes for loops with iteration dependencies has been reported so far. In this work we study the problem of scheduling loops with iteration dependencies for heterogeneous (dedicated and non-dedicated) clusters. The presence of iteration dependencies incurs an extra degree of difficulty and makes the development of such schemes quite a challenge. We extend three well known dynamic schemes (CSS, TSS and DTSS) by introducing synchronization points at certain intervals so that processors compute in pipelined fashion. Our scheme is called dynamic multi-phase scheduling (DMPS) and we apply it to loops with iteration dependencies. We implemented our new scheme on a network of heterogeneous computers and studied its performance. Through extensive testing on two real-life applications (the heat equation and the Floyd-Steinberg algorithm), we show that the proposed method is efficient for parallelizing nested loops with dependencies on heterogeneous systems.
@inproceedings{ciorba:2006,
Abstract = {Distributed computing systems are a viable and less expensive alternative to parallel computers. However, concurrent programming methods in distributed systems have not been studied as extensively as for parallel computers. Some of the main research issues are how to deal with scheduling and load balancing of such a system, which may consist of heterogeneous computers. In the past, a variety of dynamic scheduling schemes suitable for parallel loops (with independent iterations) on heterogeneous computer clusters have been obtained and studied. However, no study of dynamic schemes for loops with iteration dependencies has been reported so far. In this work we study the problem of scheduling loops with iteration dependencies for heterogeneous (dedicated and non-dedicated) clusters. The presence of iteration dependencies incurs an extra degree of difficulty and makes the development of such schemes quite a challenge. We extend three well known dynamic schemes (CSS, TSS and DTSS) by introducing synchronization points at certain intervals so that processors compute in pipelined fashion. Our scheme is called dynamic multi-phase scheduling (DMPS) and we apply it to loops with iteration dependencies. We implemented our new scheme on a network of heterogeneous computers and studied its performance. Through extensive testing on two real-life applications (the heat equation and the Floyd-Steinberg algorithm), we show that the proposed method is efficient for parallelizing nested loops with dependencies on heterogeneous systems.},
Author = {Ciorba, Florina M. and Andronikos, Theodore and Riakiotakis, Ioannis and Chronopoulos, Anthony T. and Papakonstantinou, George},
Booktitle = {Proceedings of the 20th IEEE International Parallel and Distributed Processing Symposium (IPDPS 2006)},
Date-Added = {2016-01-06 13:06:20 +0000},
Date-Modified = {2016-01-06 13:07:46 +0000},
Doi = {10.1109/IPDPS.2006.1639308},
Keywords = {2006; parallel architectures;parallel programming;pipeline processing;processor scheduling;program control structures;workstation clusters;concurrent programming;distributed computing systems;dynamic multiphase scheduling;heterogeneous clusters;iteration dependencies;load balancing;loop scheduling;pipelining;synchronization points;Application software;Cascading style sheets;Computer networks;Concurrent computing;Distributed computing;Dynamic scheduling;Load management;Parallel programming;Processor scheduling;System testing},
Month = {April},
Pages = {10--18},
Title = {{Dynamic multi phase scheduling for heterogeneous clusters}},
Year = {2006},
Bdsk-Url-1 = {http://dx.doi.org/10.1109/IPDPS.2006.1639308}}
%% This BibTeX bibliography file was created using BibDesk.
%% http://bibdesk.sourceforge.net/
%% Created for Florina M. Ciorba at 2016-01-06 12:57:44 +0100
%% Saved with string encoding Unicode (UTF-8)
Downloads: 0
{"_id":{"_str":"538590720e577e1d6b002317"},"__v":57,"authorIDs":["54658f19bc7d6a460d0005a8"],"author_short":["Ciorba, F. M.","Andronikos, T.","Riakiotakis, I.","Chronopoulos, A. T.","Papakonstantinou, G."],"bibbaseid":"ciorba-andronikos-riakiotakis-chronopoulos-papakonstantinou-dynamicmultiphaseschedulingforheterogeneousclusters-2006","bibdata":{"bibtype":"inproceedings","type":"inproceedings","abstract":"Distributed computing systems are a viable and less expensive alternative to parallel computers. However, concurrent programming methods in distributed systems have not been studied as extensively as for parallel computers. Some of the main research issues are how to deal with scheduling and load balancing of such a system, which may consist of heterogeneous computers. In the past, a variety of dynamic scheduling schemes suitable for parallel loops (with independent iterations) on heterogeneous computer clusters have been obtained and studied. However, no study of dynamic schemes for loops with iteration dependencies has been reported so far. In this work we study the problem of scheduling loops with iteration dependencies for heterogeneous (dedicated and non-dedicated) clusters. The presence of iteration dependencies incurs an extra degree of difficulty and makes the development of such schemes quite a challenge. We extend three well known dynamic schemes (CSS, TSS and DTSS) by introducing synchronization points at certain intervals so that processors compute in pipelined fashion. Our scheme is called dynamic multi-phase scheduling (DMPS) and we apply it to loops with iteration dependencies. We implemented our new scheme on a network of heterogeneous computers and studied its performance. Through extensive testing on two real-life applications (the heat equation and the Floyd-Steinberg algorithm), we show that the proposed method is efficient for parallelizing nested loops with dependencies on heterogeneous systems.","author":[{"propositions":[],"lastnames":["Ciorba"],"firstnames":["Florina","M."],"suffixes":[]},{"propositions":[],"lastnames":["Andronikos"],"firstnames":["Theodore"],"suffixes":[]},{"propositions":[],"lastnames":["Riakiotakis"],"firstnames":["Ioannis"],"suffixes":[]},{"propositions":[],"lastnames":["Chronopoulos"],"firstnames":["Anthony","T."],"suffixes":[]},{"propositions":[],"lastnames":["Papakonstantinou"],"firstnames":["George"],"suffixes":[]}],"booktitle":"Proceedings of the 20th IEEE International Parallel and Distributed Processing Symposium (IPDPS 2006)","date-added":"2016-01-06 13:06:20 +0000","date-modified":"2016-01-06 13:07:46 +0000","doi":"10.1109/IPDPS.2006.1639308","keywords":"2006; parallel architectures;parallel programming;pipeline processing;processor scheduling;program control structures;workstation clusters;concurrent programming;distributed computing systems;dynamic multiphase scheduling;heterogeneous clusters;iteration dependencies;load balancing;loop scheduling;pipelining;synchronization points;Application software;Cascading style sheets;Computer networks;Concurrent computing;Distributed computing;Dynamic scheduling;Load management;Parallel programming;Processor scheduling;System testing","month":"April","pages":"10–18","title":"Dynamic multi phase scheduling for heterogeneous clusters","year":"2006","bdsk-url-1":"http://dx.doi.org/10.1109/IPDPS.2006.1639308","bibtex":"@inproceedings{ciorba:2006,\n\tAbstract = {Distributed computing systems are a viable and less expensive alternative to parallel computers. However, concurrent programming methods in distributed systems have not been studied as extensively as for parallel computers. Some of the main research issues are how to deal with scheduling and load balancing of such a system, which may consist of heterogeneous computers. In the past, a variety of dynamic scheduling schemes suitable for parallel loops (with independent iterations) on heterogeneous computer clusters have been obtained and studied. However, no study of dynamic schemes for loops with iteration dependencies has been reported so far. In this work we study the problem of scheduling loops with iteration dependencies for heterogeneous (dedicated and non-dedicated) clusters. The presence of iteration dependencies incurs an extra degree of difficulty and makes the development of such schemes quite a challenge. We extend three well known dynamic schemes (CSS, TSS and DTSS) by introducing synchronization points at certain intervals so that processors compute in pipelined fashion. Our scheme is called dynamic multi-phase scheduling (DMPS) and we apply it to loops with iteration dependencies. We implemented our new scheme on a network of heterogeneous computers and studied its performance. Through extensive testing on two real-life applications (the heat equation and the Floyd-Steinberg algorithm), we show that the proposed method is efficient for parallelizing nested loops with dependencies on heterogeneous systems.},\n\tAuthor = {Ciorba, Florina M. and Andronikos, Theodore and Riakiotakis, Ioannis and Chronopoulos, Anthony T. and Papakonstantinou, George},\n\tBooktitle = {Proceedings of the 20th IEEE International Parallel and Distributed Processing Symposium (IPDPS 2006)},\n\tDate-Added = {2016-01-06 13:06:20 +0000},\n\tDate-Modified = {2016-01-06 13:07:46 +0000},\n\tDoi = {10.1109/IPDPS.2006.1639308},\n\tKeywords = {2006; parallel architectures;parallel programming;pipeline processing;processor scheduling;program control structures;workstation clusters;concurrent programming;distributed computing systems;dynamic multiphase scheduling;heterogeneous clusters;iteration dependencies;load balancing;loop scheduling;pipelining;synchronization points;Application software;Cascading style sheets;Computer networks;Concurrent computing;Distributed computing;Dynamic scheduling;Load management;Parallel programming;Processor scheduling;System testing},\n\tMonth = {April},\n\tPages = {10--18},\n\tTitle = {{Dynamic multi phase scheduling for heterogeneous clusters}},\n\tYear = {2006},\n\tBdsk-Url-1 = {http://dx.doi.org/10.1109/IPDPS.2006.1639308}}\n\n%% This BibTeX bibliography file was created using BibDesk.\n%% http://bibdesk.sourceforge.net/\n\n%% Created for Florina M. Ciorba at 2016-01-06 12:57:44 +0100 \n\n\n%% Saved with string encoding Unicode (UTF-8) \n\n\n\n","author_short":["Ciorba, F. M.","Andronikos, T.","Riakiotakis, I.","Chronopoulos, A. T.","Papakonstantinou, G."],"bibbaseid":"ciorba-andronikos-riakiotakis-chronopoulos-papakonstantinou-dynamicmultiphaseschedulingforheterogeneousclusters-2006","role":"author","urls":{},"keyword":["2006; parallel architectures;parallel programming;pipeline processing;processor scheduling;program control structures;workstation clusters;concurrent programming;distributed computing systems;dynamic multiphase scheduling;heterogeneous clusters;iteration dependencies;load balancing;loop scheduling;pipelining;synchronization points;Application software;Cascading style sheets;Computer networks;Concurrent computing;Distributed computing;Dynamic scheduling;Load management;Parallel programming;Processor scheduling;System testing"],"metadata":{"authorlinks":{}}},"bibtype":"inproceedings","biburl":"https://bibbase.org/f/5soafvAi5dxziNqBd/conferences.bib","downloads":0,"keywords":["2006; parallel architectures;parallel programming;pipeline processing;processor scheduling;program control structures;workstation clusters;concurrent programming;distributed computing systems;dynamic multiphase scheduling;heterogeneous clusters;iteration dependencies;load balancing;loop scheduling;pipelining;synchronization points;application software;cascading style sheets;computer networks;concurrent computing;distributed computing;dynamic scheduling;load management;parallel programming;processor scheduling;system testing"],"search_terms":["dynamic","multi","phase","scheduling","heterogeneous","clusters","ciorba","andronikos","riakiotakis","chronopoulos","papakonstantinou"],"title":"Dynamic multi phase scheduling for heterogeneous clusters","year":2006,"dataSources":["gXaEZgfAnH6LvDp7P","yquS8QakKCWDYDAk9","aMnnnpEwMvMZwRFdC","we4PjHBkvY3ihPaQy","yezXfWaY6nTQG2nAv","pWKBSwppQZXZa3qnh"]}