@article{riakiotakis:2012,
	Abstract = {Loops are the richest source of parallelism in scientific applications. A large number of loop scheduling schemes have therefore been devised for loops with and without data dependencies (modeled as dependence distance vectors) on heterogeneous clusters. The loops with data dependencies require synchronization via cross-node communication. Synchronization requires fine-tuning to overcome the communication overhead and to yield the best possible overall performance. In this paper, a theoretical model is presented to determine the granularity of synchronization that minimizes the parallel execution time of loops with data dependencies when these are parallelized on heterogeneous systems using dynamic self-scheduling algorithms. New formulas are proposed for estimating the total number of scheduling steps when a threshold for the minimum work assigned to a processor is assumed. The proposed model uses these formulas to determine the synchronization granularity that minimizes the estimated parallel execution time. The accuracy of the proposed model is verified and validated via extensive experiments on a heterogeneous computing system. The results show that the theoretically optimal synchronization granularity, as determined by the proposed model, is very close to the experimentally observed optimal synchronization granularity, with no deviation in the best case, and within 38.4% in the worst case. Copyright {\copyright} 2012 John Wiley & Sons, Ltd.},
	Author = {Riakiotakis, Ioannis. and Ciorba, Florina M. and Andronikos, Theodore and Papakonstantinou, George and Chronopoulos, Anthony T.},
	Date-Added = {2016-01-06 12:13:42 +0000},
	Date-Modified = {2016-01-06 12:16:39 +0000},
	Doi = {10.1002/cpe.2812},
	Issn = {1532-0634},
	Journal = {Concurrency and Computation: Practice and Experience},
	Keywords = {2012; loops with data dependencies, pipelined computations, dynamic load balancing, communication model, performance prediction, performance evaluation, inter-processor communication, synchronization, heterogeneous systems},
	Number = {18},
	Pages = {2302--2327},
	Publisher = {John Wiley & Sons, Ltd},
	Title = {{Towards the optimal synchronization granularity for dynamic scheduling of pipelined computations on heterogeneous computing systems}},
	Url = {http://dx.doi.org/10.1002/cpe.2812},
	Volume = {24},
	Year = {2012},
	Bdsk-Url-1 = {http://dx.doi.org/10.1002/cpe.2812}}

%% This BibTeX bibliography file was created using BibDesk.
%% http://bibdesk.sourceforge.net/

%% Created for Florina M. Ciorba at 2020-01-04 21:30:16 +0100 


%% Saved with string encoding Unicode (UTF-8)

{"_id":{"_str":"538590720e577e1d6b002316"},"__v":56,"authorIDs":["54658f19bc7d6a460d0005a8"],"author_short":["Riakiotakis, I.","Ciorba, F. M.","Andronikos, T.","Papakonstantinou, G.","Chronopoulos, A. T."],"bibbaseid":"riakiotakis-ciorba-andronikos-papakonstantinou-chronopoulos-towardstheoptimalsynchronizationgranularityfordynamicschedulingofpipelinedcomputationsonheterogeneouscomputingsystems-2012","bibdata":{"bibtype":"article","type":"article","abstract":"Loops are the richest source of parallelism in scientific applications. A large number of loop scheduling schemes have therefore been devised for loops with and without data dependencies (modeled as dependence distance vectors) on heterogeneous clusters. The loops with data dependencies require synchronization via cross-node communication. Synchronization requires fine-tuning to overcome the communication overhead and to yield the best possible overall performance. In this paper, a theoretical model is presented to determine the granularity of synchronization that minimizes the parallel execution time of loops with data dependencies when these are parallelized on heterogeneous systems using dynamic self-scheduling algorithms. New formulas are proposed for estimating the total number of scheduling steps when a threshold for the minimum work assigned to a processor is assumed. The proposed model uses these formulas to determine the synchronization granularity that minimizes the estimated parallel execution time. The accuracy of the proposed model is verified and validated via extensive experiments on a heterogeneous computing system. The results show that the theoretically optimal synchronization granularity, as determined by the proposed model, is very close to the experimentally observed optimal synchronization granularity, with no deviation in the best case, and within 38.4% in the worst case. Copyright © 2012 John Wiley & Sons, Ltd.","author":[{"propositions":[],"lastnames":["Riakiotakis"],"firstnames":["Ioannis."],"suffixes":[]},{"propositions":[],"lastnames":["Ciorba"],"firstnames":["Florina","M."],"suffixes":[]},{"propositions":[],"lastnames":["Andronikos"],"firstnames":["Theodore"],"suffixes":[]},{"propositions":[],"lastnames":["Papakonstantinou"],"firstnames":["George"],"suffixes":[]},{"propositions":[],"lastnames":["Chronopoulos"],"firstnames":["Anthony","T."],"suffixes":[]}],"date-added":"2016-01-06 12:13:42 +0000","date-modified":"2016-01-06 12:16:39 +0000","doi":"10.1002/cpe.2812","issn":"1532-0634","journal":"Concurrency and Computation: Practice and Experience","keywords":"2012; loops with data dependencies, pipelined computations, dynamic load balancing, communication model, performance prediction, performance evaluation, inter-processor communication, synchronization, heterogeneous systems","number":"18","pages":"2302–2327","publisher":"John Wiley & Sons, Ltd","title":"Towards the optimal synchronization granularity for dynamic scheduling of pipelined computations on heterogeneous computing systems","url":"http://dx.doi.org/10.1002/cpe.2812","volume":"24","year":"2012","bdsk-url-1":"http://dx.doi.org/10.1002/cpe.2812","bibtex":"@article{riakiotakis:2012,\n\tAbstract = {Loops are the richest source of parallelism in scientific applications. A large number of loop scheduling schemes have therefore been devised for loops with and without data dependencies (modeled as dependence distance vectors) on heterogeneous clusters. The loops with data dependencies require synchronization via cross-node communication. Synchronization requires fine-tuning to overcome the communication overhead and to yield the best possible overall performance. In this paper, a theoretical model is presented to determine the granularity of synchronization that minimizes the parallel execution time of loops with data dependencies when these are parallelized on heterogeneous systems using dynamic self-scheduling algorithms. New formulas are proposed for estimating the total number of scheduling steps when a threshold for the minimum work assigned to a processor is assumed. The proposed model uses these formulas to determine the synchronization granularity that minimizes the estimated parallel execution time. The accuracy of the proposed model is verified and validated via extensive experiments on a heterogeneous computing system. The results show that the theoretically optimal synchronization granularity, as determined by the proposed model, is very close to the experimentally observed optimal synchronization granularity, with no deviation in the best case, and within 38.4% in the worst case. Copyright {\\copyright} 2012 John Wiley & Sons, Ltd.},\n\tAuthor = {Riakiotakis, Ioannis. and Ciorba, Florina M. and Andronikos, Theodore and Papakonstantinou, George and Chronopoulos, Anthony T.},\n\tDate-Added = {2016-01-06 12:13:42 +0000},\n\tDate-Modified = {2016-01-06 12:16:39 +0000},\n\tDoi = {10.1002/cpe.2812},\n\tIssn = {1532-0634},\n\tJournal = {Concurrency and Computation: Practice and Experience},\n\tKeywords = {2012; loops with data dependencies, pipelined computations, dynamic load balancing, communication model, performance prediction, performance evaluation, inter-processor communication, synchronization, heterogeneous systems},\n\tNumber = {18},\n\tPages = {2302--2327},\n\tPublisher = {John Wiley & Sons, Ltd},\n\tTitle = {{Towards the optimal synchronization granularity for dynamic scheduling of pipelined computations on heterogeneous computing systems}},\n\tUrl = {http://dx.doi.org/10.1002/cpe.2812},\n\tVolume = {24},\n\tYear = {2012},\n\tBdsk-Url-1 = {http://dx.doi.org/10.1002/cpe.2812}}\n\n%% This BibTeX bibliography file was created using BibDesk.\n%% http://bibdesk.sourceforge.net/\n\n%% Created for Florina M. Ciorba at 2020-01-04 21:30:16 +0100 \n\n\n%% Saved with string encoding Unicode (UTF-8) \n\n\n\n","author_short":["Riakiotakis, I.","Ciorba, F. M.","Andronikos, T.","Papakonstantinou, G.","Chronopoulos, A. T."],"bibbaseid":"riakiotakis-ciorba-andronikos-papakonstantinou-chronopoulos-towardstheoptimalsynchronizationgranularityfordynamicschedulingofpipelinedcomputationsonheterogeneouscomputingsystems-2012","role":"author","urls":{"Paper":"http://dx.doi.org/10.1002/cpe.2812"},"keyword":["2012; loops with data dependencies","pipelined computations","dynamic load balancing","communication model","performance prediction","performance evaluation","inter-processor communication","synchronization","heterogeneous systems"],"metadata":{"authorlinks":{}}},"bibtype":"article","biburl":"https://bibbase.org/f/5soafvAi5dxziNqBd/journals.bib","downloads":1,"keywords":["2012; loops with data dependencies","pipelined computations","dynamic load balancing","communication model","performance prediction","performance evaluation","inter-processor communication","synchronization","heterogeneous systems"],"search_terms":["towards","optimal","synchronization","granularity","dynamic","scheduling","pipelined","computations","heterogeneous","computing","systems","riakiotakis","ciorba","andronikos","papakonstantinou","chronopoulos"],"title":"Towards the optimal synchronization granularity for dynamic scheduling of pipelined computations on heterogeneous computing systems","year":2012,"dataSources":["gXaEZgfAnH6LvDp7P","ZBYxsBTKoa48bvWLJ","Bz2EX92b3rMNrcBL6"]}