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.
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.
AbdelzaherTThakerGLardieriP (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’04), Tokyo, 23–26 March 2004, pp.436–445. Washington DC: IEEE Computer Society. Available at: http://dl.acm.org/citation.cfm?id=977400.977975.
2.
AdveVBagrodiaRBrowneJ. (2000) POEMS: End-to-end performance design of large parallel adaptive computational systems. Software Engineering26(11): 1027–1048.
3.
BakerMCarpenterBShafiA (2006) MPJ express: Towards thread safe Java HPC. In: IEEE international conference on cluster computing (Cluster 2006), Barcelona, Spain, 25–28 September 2006, pp.25–28.
4.
BashirFKhokharASchonfeldD (2006) View-invariant motion trajectory based activity classification and recognition. Multimedia Systems12(1): 45–54.
5.
BeyanCFisherR (2013) Detecting abnormal fish trajectories using clustered and labelled data. Proceedings of the IEEE international conference on image processing. Melbourne, Australia, 15–18 September 2013, pp. 1476–1480.
6.
BlumALangleyP (1997) Selection of relevant features and examples in machine learning. Artificial Intelligence97(1–2): 245–271.
7.
BuyyaRMurshedMAbramsonD (2002) A deadline and budget constrained cost–time 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.
8.
CaiLHofmannT (2004) Hierarchical document categorization with support vector machines. Proceedings of the 13th ACM international conference on information and knowledge management, pp.78–87.
9.
CasanovaHKimMPlankJ. (1999) Adaptive scheduling for task farming with grid middleware. International Journal of High Performance Computing13(3): 231–240.
10.
CasanovaHObertelliGBermanF. (2000) The AppLeS parameter sweep template: User-level middleware for the grid. In: Proceedings of the 2000 ACM/IEEE conference on supercomputing (Supercomputing ‘00), Rhode Island, NY, 4–10 November 2000, p.60. Washington, DC, USA: IEEE Computer Society. Available at: http://dl.acm.org/citation.cfm?id=370049.370499 .
11.
ChangCLinC (2011) LIBSVM: A Library for support vector machines. ACM Transactions on Intelligent Systems and Technology2(3): 1–27.
12.
ColeM (1991) Algorithmic Skeletons: Structured Management of Parallel Computation. Cambridge, MA: MIT Press.
DeanJGhemawatS (2008) MapReduce: Simplified data processing on large clusters. Communications of the ACM51(1): 107–113. doi: 10.1145/1327452.1327492.
15.
DuanKSathiyaK (2005) Which is the best multiclass SVM method? An empirical study. In: Proceedings of the 6th international conference on multiple classifier systems (MCS’05), Seaside, CA, USA, 13–15 June, 2005, pp.278–285.
16.
EagerDZahorjanJLazowskaE (1989) Speedup versus efficiency in parallel systems. IEEE Transactions on Computers38(3): 408–423. doi: 10.1109/12.21127.
17.
ElwasifWPlankJWolskiR (2001) Data staging effects in wide area task farming applications. In: Proceedings of IEEE international symposium on cluster computing and the grid, Brisbane, Australia15–18 May, 2001, pp. 122–129.
18.
FosterI (1994) Task parallelism and high-performance languages. IEEE Parallel Distribution Technology2(3): 27–36. doi: 10.1109/M-PDT.1994.329794 .
19.
FrankMAgarwalAVernonM (1997) LoPC: modeling contention in parallel algorithms. In: Proceedings of the 6th ACM SIGPLAN symposium on the principles and practice of parallel programming (PPOPP ‘97), pp.276–287. New York, NY: ACM. Las Vegas, NV, USA 18–21 June 1997.
20.
GentzschW (2001) Sun Grid Engine: Towards creating a compute power grid. In: Proceedings of the 1st international symposium on cluster computing and the grid (CCGRID ‘01), Brisbane, Australia, 15–18 May, 2001, pp.35–43. Washington, DC: IEEE Computer Society.
21.
GuoGDyerC (2003) Simultaneous feature selection and classifier training via linear programming: A case study for face expression recognition. Proceedings of the IEEE conference on computer vision and pattern recognition, Wisconsin, USA, 16–22 June 2003, pp.346–352.
22.
HammondSMudaligeGSmithJ. (2009) WARPP: A toolkit for simulating high-performance parallel scientific codes. In: Proceedings of the 2nd international ICST conference on simulation tools and techniques. Rome, Italy, 02-06 March 2009, pp. 19:1–19:10 ACM. doi: 10.4108/ICST.SIMUTOOLS2009.5753.
23.
HammondSSmithJMudaligeG. (2009) Predictive simulation of HPC applications. In: The IEEE 23rd international conference on advanced information networking and applications (AINA-09), Bradford, UK, 26–29 May 2009, pp. 33–40.
24.
HillisWSteeleJGuyL (1986) Data parallel algorithms. Communications of the ACM29(12): 1170–1183. doi: 10.1145/7902.7903 .
25.
HuangJCaiYXuX (2006) A filter approach to feature selection based on mutual information. Proceedings of the IEEE international conference on cognitive informatics, Beijing, China, 17–19 July 2006. pp.84–89.
26.
HuangPBoomBHeJ. (2012) Underwater live fish recognition using balance-guaranteed optimized tree. In: Proceedings of the 11th Asian conference on computer vision (ACCV 2012), Vol. 7724, Daejeon, Korea, 5–9 November 2012, pp.422–433.
27.
IsardMBudiuandMYuY. (2007) Dryad: Distributed data-parallel programs from sequential building blocks. In: Proceedings of the 2nd ACM SIGOPS/EuroSys European conference on computer systems 2007 (EuroSys ‘07), Lisbon, Portugal, 21–23 March 2007, pp.59–72. New York: ACM. doi: 10.1145/1272996.1273005 .
28.
KerbysonDHoisieAWassermanH (2005) Use of predictive performance modeling during large-scale system installation. Parallel Processing Letters15(04): 387–395. doi: 10.1142/S0129626405002301.
29.
KohaviRJohnG (1997) Wrappers for feature subset selection. Artificial Intelligence97(1–2): 273–324.
30.
LabartaJGironaSCortesT (1997) Analysing scheduling policies using DIMEMAS. Parallel Computing23(1) pp. 23–34.
31.
LiuHSr (2005) Toward integrating feature selection algorithms for classification and clustering. IEEE Transactions on Knowledge and Data Engineering17(4): 491–502.
32.
LiwickiMBunkeH (2006) HMM-based on-line recognition of handwritten whiteboard notes. Paris, France, 17–20 May 2010. Proceedings of the 10th international workshop on frontiers in handwriting recognition, La Baule, France, 23–26 October 2006 pp.595–599.
33.
McCollW (1993) General purpose parallel computing. GibbonsAMSpirakisP (eds) Lectures on Parallel Computation (Cambridge International Series on Parallel Computation). Cambridge; New York: Cambridge University Press: 337–391.
34.
McDonaghSFisherR (2013) Simultaneous registration of multi-view range images with adaptive kernel density estimation. Under review : 14th IMA Conference on Mathematics of Surfaces Birmingham, England, 11–13 September 2013, pp 31–62.
35.
McDonaghSFisherRReesJ (2008) Using 3D information for classification of non-melanoma skin lesions. In: Proceedings of Medical Image Understanding and Analysis, Dundee, Conference, Dundee, Scotland, 2–3 July 2008, pp.164–168.
36.
MudaligeGVernonMJarvisS (2008) A plug-and-play model for evaluating wavefront computations on parallel architectures. In: Proceedings of the IEEE International Symposium on Parallel and Distributed Processing (IPDPS 2008), Miami, Florida, USA, 14–18 April 2008, pp.1–14. doi: 10.1109/IPDPS.2008.4536243.
37.
NuddGKerbysonDPapaefstathiouE. (2000) PACE: A toolset for the performance prediction of parallel and distributed systems. International Journal High Performance Computing Applications14(3): 228–251.
38.
PllanaSFahringerT (2005) Performance prophet: A performance modeling and prediction tool for parallel and distributed programs. In: Proceedings of the 2005 international conference on parallel processing (ICPP-05), Oslo, 14–17 June 2005, 26(11): 509–516.
39.
PoldnerMKuchenH (2008) On implementing the farm skeleton. Parallel Processing Letters18(1), 117–131.
40.
PottmannHLeopoldsederSHoferM (2002) Simultaneous registration of multiple views of a 3D object. Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences: Graz, Austria, 9–13 September 2002, 265–270.
41.
RevengaPSérotJLázaroJ. (2003) A Beowulf-class architecture proposal for real-time embedded vision. In: Proceedings of the 17th International Symposium on Parallel and Distributed Processing (IPDPS ‘03), Nice, France, 22–26 April 2003, pp.8–16. Washington, DC: IEEE Computer Society. Available at: http://dl.acm.org/citation.cfm?id=838237.838308.
SilvaLVeerBSilvaJ (1993) How to get a fault-tolerant farm. In: Proceedings of the world transputer congress, Aachen, Germany, 20–22 September 1993, pp.923–938.
44.
SkillicornDHillJMcCollW (1997) Questions and Answers about BSP. Scientific Programming6: 249–274.
45.
SpoonerDJarvisSCaoJ. (2003) Local grid scheduling techniques using performance prediction. IEEE Proceedings – Computers and Digital Techniques150: 87–96(9).
46.
SukTFlusserJ (2004) Graph method for generating affine moment invariants. Proceedings of the international conference on pattern recognition, Cambridge, UK, 23–26 August 2004, pp.192–195.
47.
ThainDTannenbaumTLivnyM (2005) Distributed computing in practice: The Condor experience. Concurrency and Computation: Practice and Experience17(2–4): 323–356. doi: 10.1002/cpe.938.
48.
ToldoRBeinatACrosillaF (2010) Global registration of multiple point clouds embedding the generalized procrustes analysis into an ICP framework. In: Proceedings of the conference on 3D proceedings, visualization and transmission,
49.
TorselloARodolaEAlbarelliA (2011) Multi-view registration via graph diffusion of dual quaternions. In: IEEE conference on computer vision and pattern recognition, Colorado Springs, USA, 21–23 June 2011, pp.2441–2448.
50.
ValiantG (1990) A bridging model for parallel computation. Communications of the ACM33(8): 103–111. doi: 10.1145/79173.79181.
51.
WangQLiBHuJ (2009) Feature selection for human resource selection based on affinity propagation and SVM sensitivity analysis. In: Proceedings of the world congress on nature and biologically inspired computing (NaBIC 09), Coimbatore, India, 9–11 December 2009, pp.31–36. doi: 10.1109/NABIC.2009.5393596.
52.
WangYCasasentD (2009) A support vector hierarchical method for multi-class classification and rejection. In: Proceedings of the international joint conference on neural networks (IJCNN), Atlanta, Georgia, USA, 14–19 June 2009, pp.3281–3288.
