Implementation and analysis of a class of algorithms for distributed convex optimization: Performance evaluation and tradeoffs in practical HPC clusters

Abstract

The significance of distributed optimization algorithms manifests through growing interest in various application domains. It finds its use in Big Data analytics, distributed machine learning, distributed control, vehicle networks and smart grid, inter alia. This thesis focuses on primal and dual distributed convex optimization methods. First, it introduces a general algorithmic framework of first and second order methods of primal type, that utilize the concepts of sparsified communications and computations across a connected graph of working nodes. Besides several already existing methods, the framework also includes novel variants that utilize unidirectional communication. Although there have been a remarkable amount of theory and theoretical advances in this field, practical evaluations of methods on real data and practical large scale and High Performance Computing (HPC) systems are of much smaller volume. Therefore, we developed the implementations and performed various numerical evaluations of the proposed methods in an actual, parallel programming environment. The implementations were developed using the Message Passing Interface (MPI) and tested on a High Performance Computing cluster. These empirical evaluations result with very useful insights and guidelines regarding performance and highlights the most important communication-computational tradeoffs in a real execution environment. As there exists a wide set of machine learning algorithms that can be viewed as optimization problems, distributed optimization plays a significant role in this area. The thesis also presents an algorithm for convex clustering, based on the dual method Alternating Direction Method of Multipliers (ADMM), that relies on COMPS Superscalar (COMPSs) framework for parallelization. We provide results of extensive numerical evaluations of the algorithm on a HPC cluster environment, to demonstrate the high degree of scalability and efficiency of the method, compared to existing alternative solvers for convex clustering. The program code for the developed algorithms is open-source and available in the corresponding repositories.

спарсификоване комуникације и израчунавања преко повезаног графа чворова. Поред неколико већ постојећих метода, појављују се и нове варијанте које користе једносмерну комуникацију. Иако у овој области постоји изузетно велика количина теорије и теоријског напретка, практичне евалуације метода над стварним подацима и практичним системима рачунара вискох перформанси (High Performance Computing — HPC) великих размера, су много мањег обима. Стога смо развили имплементације и извршили скуп различитих нумеричких евалуација предложених метода у стварном, паралелном програмском окружењу. Имплементације су развијене коришћењем технологије Message Passing Interface (MPI) и тестиране су на рачунарском кластеру високих перформанси. Ове емпиријске процене резултирају веома корисним увидима и смерницама у вези са перформансама и наглашавају најважније компромисе између комуникације и израчунавања, у стварном окружењу извршавања. С обзиром на постојање широког скупа алгоритама машинског учења који се могу посматрати као оптимизациони проблеми, дистрибуирана оптимизација има врло значајну улогу у овој области. У тези је такође представљен и алгоритам за конвексно кластеровање, заснован на дуалној методи Alternating Direction Method of Multipliers (ADMM), која се ослања на COMPS Superscalar (COMPSs) приступ за паралелизацију. Приказујемо резултате опсежних нумеричких евалуација алгоритма на HPC рачунарском кластеру, како бисмо демонстрирали висок степен скалабилности и ефикасности методе, у поређењу са постојећим алтернативним приступима за конвексно кластеровање. Програмски код за развијене алгоритме је софтвер отвореног кода, и доступан је у одговарајућим репозиторијумима.

sparsifikovane komunikacije i izračunavanja preko povezanog grafa čvorova. Pored nekoliko već postojećih metoda, pojavljuju se i nove varijante koje koriste jednosmernu komunikaciju. Iako u ovoj oblasti postoji izuzetno velika količina teorije i teorijskog napretka, praktične evaluacije metoda nad stvarnim podacima i praktičnim sistemima računara viskoh performansi (High Performance Computing — HPC) velikih razmera, su mnogo manjeg obima. Stoga smo razvili implementacije i izvršili skup različitih numeričkih evaluacija predloženih metoda u stvarnom, paralelnom programskom okruženju. Implementacije su razvijene korišćenjem tehnologije Message Passing Interface (MPI) i testirane su na računarskom klasteru visokih performansi. Ove empirijske procene rezultiraju veoma korisnim uvidima i smernicama u vezi sa performansama i naglašavaju najvažnije kompromise između komunikacije i izračunavanja, u stvarnom okruženju izvršavanja. S obzirom na postojanje širokog skupa algoritama mašinskog učenja koji se mogu posmatrati kao optimizacioni problemi, distribuirana optimizacija ima vrlo značajnu ulogu u ovoj oblasti. U tezi je takođe predstavljen i algoritam za konveksno klasterovanje, zasnovan na dualnoj metodi Alternating Direction Method of Multipliers (ADMM), koja se oslanja na COMPS Superscalar (COMPSs) pristup za paralelizaciju. Prikazujemo rezultate opsežnih numeričkih evaluacija algoritma na HPC računarskom klasteru, kako bismo demonstrirali visok stepen skalabilnosti i efikasnosti metode, u poređenju sa postojećim alternativnim pristupima za konveksno klasterovanje. Programski kod za razvijene algoritme je softver otvorenog koda, i dostupan je u odgovarajućim repozitorijumima.