We investigate the usefulness of gossip-based reduction algorithms in a high-performance computing (HPC) context. We compare them to state-of-the-art deterministic parallel reduction algorithms in terms of fault tolerance and resilience against silent data corruption (SDC) as well as in terms of performance and scalability. New gossip-based reduction algorithms are proposed, which significantly improve the state-of-the-art in terms of resilience against SDC. Moreover, a new gossip-inspired reduction algorithm is proposed, which promises a much more competitive runtime performance in an HPC context than classical gossip-based algorithms, in particular for low accuracy requirements.
BlandWBouteillerAHeraultT. (2013) Post-failure recovery of MPI communication capability: design and rationale. The International Journal of High Performance Computing Applications27(3): 244–254.
3.
BottouL (2010) Large-scale machine learning with stochastic gradient descent. In: Proceedings of COMPSTAT’2010: 19th International Conference on Computational Statistics (eds LechevallierYSaportaG), Paris France, 22–27 August 2010, pp. 177–186, Heidelberg: Physica-Verlag HD
4.
BoydSGhoshAPrabhakarB. (2006) Randomized gossip algorithms. IEEE Transactions on Information Theory52(6): 2508–2530.
ChanEHeimlichMPurkayasthaA. (2007) Collective communication: theory, practice, and experience. Concurrency and Computation Practice and Experience19(13): 1749–1783.
7.
Commonwealth Scientific and Industrial Research Organization (CSIRO) (2014) Scientific computing user manual. Available at: https://wiki.csiro.au/display/ASC/User+Manual (accessed 2 March 2018).
8.
DeanJCorradoGSMongaR. (2012) Large scale distributed deep networks. In: Proceedings of the 25th international conference on neural information processing systems, NIPS’12, Lake Tahoe, Nevada, 3–6 December 2012, pp. 1223–1231. Curran Associates Inc.
9.
DennardRHGaensslenFHYuH. (1974) Design of ion-implanted mosfets with very small physical dimensions. IEEE Journal of Solid-State Circuits9(5): 256–268.
10.
DimakisASarwateAWainwrightM (2008) Geographic gossip: efficient averaging for sensor networks. IEEE Transactions on Signal Processing56(3): 1205–1216.
11.
EyalIKeidarIRomR (2011) LiMoSense—Live monitoring in dynamic sensor networks. In: Proceedings of the 7th international symposium on algorithms for sensor systems, wireless ad hoc networks and autonomous mobile entities ALGOSENSORS (eds ErlebachTNikoletseasSOrponenP), Germany, 8–9 September 2011, pp. 72–85. Berlin, Heidelberg: Springer.
12.
EyalIKeidarIRomR (2014) LiMoSense: live monitoring in dynamic sensor networks. Distributed Computing27(5): 313–328.
13.
FerreiraKBBridgesPBrightwellR (2008) Characterizing application sensitivity to OS interference using kernel-level noise injection. In: Proceedings of the 2008 ACM/IEEE conference on supercomputing, SC ‘08, Austin, Texas, 15–21 November 2008, pp. 19:1–19:12. IEEE Press.
14.
GanstererWNNiederbruckerGStrakováH. (2013) Scalable and fault tolerant orthogonalization based on randomized distributed data aggregation. Journal of Computational Science4(6): 480–488.
15.
GuptaSAgrawalAGopalakrishnanK. (2015) Deep learning with limited numerical precision. In: Proceedings of the 32nd international conference on machine learning, ICML’15 (eds BachFBleiD), Lille, France, 6–11 July 2015, Vol. 37, pp. 1737–1746. http://JMLR.org.
16.
HadjicostisCDominguez-GarciaAVaidyaN (2012) Resilient average consensus in the presence of heterogeneous packet dropping links. In: 51st annual conference on decision and control, Maui, HI, USA10–13 December 2012, pp. 106–111. CDC.
17.
HeraultTBouteillerABosilcaG. (2015) Practical scalable consensus for pseudo-synchronous distributed systems. In: Proceedings of the international conference for high performance computing, networking, storage and analysis, SC ’15 (eds. JackieKVetterJS), Austin, Texas, USA, 15–20 November 2015, pp. 31:1–31:12. New York, NY, USA: ACM.
18.
HoeflerTGottschlingPLumsdaineA. (2007) Optimizing a conjugate gradient solver with non-blocking collective operations. Parallel Computing33(9): 624–633.
19.
JanecekAGanstererWN (2016) ACO-inspired acceleration of gossip averaging. In: Proceedings of the genetic and evolutionary computation conference (eds. FriedrichTNeumannFSuttonAM), 20–24 July 2016, pp. 21–28, GECCO ‘16. New York, NY, USA: ACM.
20.
JesusPBaqueroCAlmeidaPS (2009) Fault-Tolerant aggregation by flow updating. In: Proceedings of the international conference on distributed applications and interoperable systems (eds. SenivongseTRuiO), 9–11 June 2009, pp. 73–86. Berlin, Heidelberg: Springer.
21.
JesusPBaqueroCAlmeidaPS (2010) Fault-Tolerant aggregation for dynamic networks. In: Proceedings of the 29th IEEE symposiumon reliable distributed systems, New Delhi, India, 31 October–3 November 2010, pp. 37–43.
22.
JesusPBaqueroCAlmeidaPS (2015) Flow updating: faulttolerant aggregation for dynamic networks. Journal of Parallel and Distributed Computing78: 53–64.
23.
JinPHYuanQIandolaFN. (2016) How to scale distributed deep learning? CoRR abs/1611.04581. Available at: http://arxiv.org/abs/1611.04581(accessed 11 March 2018).
24.
KattiADi FattaGNaughtonT. (2015) Scalable and fault tolerant failure detection and consensus. In: Proceedings of the 22nd European MPI users’ group meeting (eds. DongarraJJDenisAGoglinB), EuroMPI ‘15, Bordeaux, France, 21–23 September 2015, pp. 13:1–13:9. New York, NY, USA: ACM.
25.
KempeDDobraAGehrkeJ (2003) Gossip-based computation of aggregate information. In: Proceedings of the 44th annual IEEE symposium on foundations of computer science, Cambridge, MA, USA, 11–14 October 2003, pp. 482–491. Washington, DC, USA: IEEE Computer Society.
26.
LesserBMückeMGanstererWN (2011) Effects of reduced precision on floating-point SVM classification accuracy. Procedia Computer Science4: 508–517.
27.
MPI Forum (2012) MPI: a message-passing interface standard version 3.0. Available at: http://mpi-forum.org/docs/ (accessed 11 March 2018).
28.
NicholsBButtlarDFarrellJP (1996) Pthreads Programming. Sebastopol, CA, USA: O’Reilly & Associates, Inc.
29.
NiederbruckerGGanstererWN (2013) Robust gossip-based aggregation: a practical point of view. In: 2013 Proceedings of the fifteenth meeting on algorithm engineering and experiments (ALENEX) (eds SandersPZehZ), New Orleans, Louisiana, USA, 7 January 2013, pp. 133–147. Philadelphia, PA, USA: SIAM.
30.
NiederbruckerGStrakováHGanstererWN (2012) Improving fault tolerance and accuracy of a distributed reduction algorithm. In: Proceedings third workshop on latest advances in scalable algorithms for large-scale systems, Salt Lake City, UT, USA, 10–16 November 2012, pp. 643–651. IEEE.
SeifertNGillBJahinuzzamanS. (2012) Soft error susceptibilities of 22 nm tri-gate devices. IEEE Transactions of Nuclear Science59(6): 2666–2673.
33.
Sidiroglou-DouskosSMisailovicSHoffmannH. (2011) Managing performance vs. accuracy trade-offs with loop perforation. In: Proceedings of the 19th ACM SIGSOFT Symposium and the 13th European conference on foundations of software engineering (eds. GyimóthyTZellerA), ESEC/FSE ’11, Szeged, Hungary, 5–9 September 2011, pp. 124–134. New York, NY, USA: ACM.
34.
ThakurRGroppWD (2003) Improving the performance of collective operations in MPICH. In: DongarraJLaforenzaDOrlandoS (eds) Recent Advances in Parallel Virtual Machine and Message Passing Interface, Lecture Notes in Computer Science, Vol. 2840. Berlin, Heidelberg: Springer, pp. 257–267.
35.
Top500List (2018) TOP500 Supercomputers. Available at: http://www.top500.org (accessed 11 March 2018).
36.
VáňaFDübenPLangS. (2017) Single precision in weather forecasting models: an evaluation with the IFS. Monthly Weather Review145(2): 495–502.
