{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,3]],"date-time":"2025-03-03T05:46:19Z","timestamp":1740980779690,"version":"3.38.0"},"reference-count":54,"publisher":"SAGE Publications","issue":"4","license":[{"start":{"date-parts":[[2014,5,8]],"date-time":"2014-05-08T00:00:00Z","timestamp":1399507200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["The International Journal of High Performance Computing Applications"],"published-print":{"date-parts":[[2015,11]]},"abstract":"<jats:p> Distributed compute clusters allow the computing power of heterogeneous (and homogeneous) resources to be utilised to solve large-scale science and engineering problems. One class of problem that has attractive scalability properties, and is therefore often implemented using compute clusters, is task farming (or parameter sweep) applications. A typical characteristic of such applications is that no communication is needed between distributed subtasks during the overall computation. However, interesting large-scale task farming problem instances that do require global communication between subtask sets also exist. We propose a framework called semi-synchronised task farming in order to address problems requiring distributed formulations containing subtasks that alternate between independence and synchronisation. We apply this framework to several large-scale contemporary computer vision problems and present a detailed performance analysis to demonstrate framework scalability. <\/jats:p><jats:p> Semi-synchronised task farming splits a given problem into a number of stages. Each stage involves firstly distributing independent subtasks to be completed in parallel. Following subtask set completion, a set of synchronised global decisions, based on information retrieved from the distributed results, is made. The results influence the following subtask distribution stage. This subtask distribution followed by result collation process is iterated until overall problem solutions are obtained. We construct a simplified Bulk Synchronous Parallel (BSP) model to formalise this framework and with this formalisation, we develop a predictive model for overall task completion time. We present experimental benchmark results comparing the performance observed by applying our framework to solve real-world problems on compute clusters with that of solving the tasks in a serial fashion. Furthermore by assessing the predicted time savings that our framework provides in simulation and validating these predictions on a range of complex problems drawn from real-world computer vision tasks, we are able to reliably predict the performance gain obtained when using a compute cluster to tackle resource intensive computer vision tasks. <\/jats:p>","DOI":"10.1177\/1094342014532965","type":"journal-article","created":{"date-parts":[[2014,5,9]],"date-time":"2014-05-09T07:10:45Z","timestamp":1399619445000},"page":"437-460","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":0,"title":["Applying semi-synchronised task farming to large-scale computer vision problems"],"prefix":"10.1177","volume":"29","author":[{"given":"Steven","family":"McDonagh","sequence":"first","affiliation":[{"name":"University of Edinburgh, UK"}]},{"given":"Cigdem","family":"Beyan","sequence":"additional","affiliation":[{"name":"University of Edinburgh, UK"}]},{"given":"Phoenix X","family":"Huang","sequence":"additional","affiliation":[{"name":"University of Edinburgh, UK"}]},{"given":"Robert B","family":"Fisher","sequence":"additional","affiliation":[{"name":"University of Edinburgh, UK"}]}],"member":"179","published-online":{"date-parts":[[2014,5,8]]},"reference":[{"key":"bibr1-1094342014532965","doi-asserted-by":"crossref","unstructured":"Abdelzaher T, Thaker G, Lardieri P (2004) A feasible region for meeting aperiodic end-to-end deadlines in resource pipelines. In: Proceedings of the 24th international conference on distributed computing systems (ICDCS\u201904), Tokyo, 23\u201326 March 2004, pp.436\u2013445. Washington DC: IEEE Computer Society. Available at: http:\/\/dl.acm.org\/citation.cfm?id=977400.977975.","DOI":"10.1109\/ICDCS.2004.1281610"},{"key":"bibr2-1094342014532965","doi-asserted-by":"publisher","DOI":"10.1109\/32.881716"},{"key":"bibr3-1094342014532965","first-page":"25","author":"Baker M","year":"2006","journal-title":"IEEE international conference on cluster computing (Cluster 2006)"},{"key":"bibr4-1094342014532965","doi-asserted-by":"publisher","DOI":"10.1007\/s00530-006-0024-2"},{"key":"bibr5-1094342014532965","first-page":"1476","author":"Beyan C","year":"2013","journal-title":"Proceedings of the IEEE international conference on image processing"},{"key":"bibr6-1094342014532965","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(97)00063-5"},{"key":"bibr7-1094342014532965","unstructured":"Buyya R, Murshed M, Abramson D (2002) A deadline and budget constrained cost\u2013time optimisation algorithm for scheduling task farming applications on global grids. Technical report, Monash University. Available at: Available at: http:\/\/http:\/\/arxiv.org\/pdf\/cs\/0203020.pdf."},{"key":"bibr8-1094342014532965","first-page":"78","author":"Cai L","year":"2004","journal-title":"Proceedings of the 13th ACM international conference on information and knowledge management"},{"key":"bibr9-1094342014532965","doi-asserted-by":"publisher","DOI":"10.1177\/109434209901300306"},{"key":"bibr10-1094342014532965","doi-asserted-by":"crossref","unstructured":"Casanova H, Obertelli G, Berman F, (2000) The AppLeS parameter sweep template: User-level middleware for the grid. In: Proceedings of the 2000 ACM\/IEEE conference on supercomputing (Supercomputing \u201800), Rhode Island, NY, 4\u201310 November 2000, p.60. Washington, DC, USA: IEEE Computer Society. Available at: http:\/\/dl.acm.org\/citation.cfm?id=370049.370499 .","DOI":"10.1109\/SC.2000.10061"},{"key":"bibr11-1094342014532965","doi-asserted-by":"publisher","DOI":"10.1145\/1961189.1961199"},{"volume-title":"Algorithmic Skeletons: Structured Management of Parallel Computation","year":"1991","author":"Cole M","key":"bibr12-1094342014532965"},{"key":"bibr13-1094342014532965","doi-asserted-by":"publisher","DOI":"10.1007\/BF00994018"},{"key":"bibr14-1094342014532965","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"bibr15-1094342014532965","doi-asserted-by":"publisher","DOI":"10.1007\/11494683_28"},{"key":"bibr16-1094342014532965","doi-asserted-by":"publisher","DOI":"10.1109\/12.21127"},{"key":"bibr17-1094342014532965","doi-asserted-by":"publisher","DOI":"10.1109\/CCGRID.2001.923184"},{"key":"bibr18-1094342014532965","doi-asserted-by":"publisher","DOI":"10.1109\/M-PDT.1994.329794"},{"key":"bibr19-1094342014532965","doi-asserted-by":"publisher","DOI":"10.1145\/263764.263803"},{"key":"bibr20-1094342014532965","doi-asserted-by":"publisher","DOI":"10.1109\/CCGRID.2001.923173"},{"key":"bibr21-1094342014532965","first-page":"346","author":"Guo G","year":"2003","journal-title":"Proceedings of the IEEE conference on computer vision and pattern recognition"},{"key":"bibr22-1094342014532965","doi-asserted-by":"publisher","DOI":"10.4108\/ICST.SIMUTOOLS2009.5753"},{"key":"bibr23-1094342014532965","first-page":"33","author":"Hammond S","year":"2009","journal-title":"The IEEE 23rd international conference on advanced information networking and applications (AINA-09)"},{"key":"bibr24-1094342014532965","doi-asserted-by":"publisher","DOI":"10.1145\/7902.7903"},{"key":"bibr25-1094342014532965","doi-asserted-by":"publisher","DOI":"10.1109\/COGINF.2006.365681"},{"key":"bibr26-1094342014532965","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-37331-2_32"},{"key":"bibr27-1094342014532965","doi-asserted-by":"publisher","DOI":"10.1145\/1272996.1273005"},{"key":"bibr28-1094342014532965","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626405002301"},{"key":"bibr29-1094342014532965","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(97)00043-X"},{"key":"bibr30-1094342014532965","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(96)00094-4"},{"key":"bibr31-1094342014532965","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2005.66"},{"key":"bibr32-1094342014532965","first-page":"595","author":"Liwicki M","year":"2006","journal-title":"Proceedings of the 10th international workshop on frontiers in handwriting recognition"},{"key":"bibr33-1094342014532965","first-page":"337","volume-title":"Lectures on Parallel Computation","author":"McColl W","year":"1993"},{"key":"bibr34-1094342014532965","first-page":"31","author":"McDonagh S","year":"2013","journal-title":"Under review"},{"key":"bibr35-1094342014532965","first-page":"164","author":"McDonagh S","year":"2008","journal-title":"Proceedings of Medical Image Understanding and Analysis"},{"key":"bibr36-1094342014532965","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2008.4536243"},{"key":"bibr37-1094342014532965","doi-asserted-by":"publisher","DOI":"10.1177\/109434200001400306"},{"key":"bibr38-1094342014532965","doi-asserted-by":"publisher","DOI":"10.1109\/ICPPW.2005.72"},{"key":"bibr39-1094342014532965","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626408003260"},{"key":"bibr40-1094342014532965","first-page":"265","author":"Pottmann H","year":"2002","journal-title":"Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences"},{"key":"bibr41-1094342014532965","unstructured":"Revenga P, S\u00e9rot J, L\u00e1zaro J, (2003) A Beowulf-class architecture proposal for real-time embedded vision. In: Proceedings of the 17th International Symposium on Parallel and Distributed Processing (IPDPS \u201803), Nice, France, 22\u201326 April 2003, pp.8\u201316. Washington, DC: IEEE Computer Society. Available at: http:\/\/dl.acm.org\/citation.cfm?id=838237.838308."},{"issue":"3175","key":"bibr42-1094342014532965","first-page":"9","author":"Roth V","year":"2004","journal-title":"Pattern Recognition"},{"key":"bibr43-1094342014532965","first-page":"923","author":"Silva L","year":"1993","journal-title":"Proceedings of the world transputer congress"},{"key":"bibr44-1094342014532965","doi-asserted-by":"publisher","DOI":"10.1155\/1997\/532130"},{"key":"bibr45-1094342014532965","doi-asserted-by":"publisher","DOI":"10.1049\/ip-cdt:20030280"},{"key":"bibr46-1094342014532965","doi-asserted-by":"publisher","DOI":"10.1109\/ICPR.2004.1334093"},{"key":"bibr47-1094342014532965","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.938"},{"journal-title":"Proceedings of the conference on 3D proceedings, visualization and transmission","year":"2010","author":"Toldo R","key":"bibr48-1094342014532965"},{"key":"bibr49-1094342014532965","first-page":"2441","author":"Torsello A","year":"2011","journal-title":"IEEE conference on computer vision and pattern recognition"},{"key":"bibr50-1094342014532965","doi-asserted-by":"publisher","DOI":"10.1145\/79173.79181"},{"key":"bibr51-1094342014532965","doi-asserted-by":"publisher","DOI":"10.1109\/NABIC.2009.5393596"},{"key":"bibr52-1094342014532965","first-page":"3281","author":"Wang Y","year":"2009","journal-title":"Proceedings of the international joint conference on neural networks (IJCNN)"},{"key":"bibr53-1094342014532965","unstructured":"Weston J, Mukherjee S, Chapelle O, (2000) Feature selection for SVMs. Advances in Neural Information Processing Systems 13: 668\u2013674. Available at: http:\/\/citeseer.ist.psu.edu\/viewdoc\/summary?doi=10.1.1.102.7476."},{"journal-title":"UC Berkeley Tech Report UCB\/EECS-2007-99","year":"2007","author":"Yang A","key":"bibr54-1094342014532965"}],"container-title":["The International Journal of High Performance Computing Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/1094342014532965","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/1094342014532965","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/1094342014532965","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,3]],"date-time":"2025-03-03T04:35:57Z","timestamp":1740976557000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/1094342014532965"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,5,8]]},"references-count":54,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,11]]}},"alternative-id":["10.1177\/1094342014532965"],"URL":"https:\/\/doi.org\/10.1177\/1094342014532965","relation":{},"ISSN":["1094-3420","1741-2846"],"issn-type":[{"type":"print","value":"1094-3420"},{"type":"electronic","value":"1741-2846"}],"subject":[],"published":{"date-parts":[[2014,5,8]]}}}