Aggregation of clans to speed-up solving linear systems on parallel architectures. Issue 2 (4th March 2022)

• Record Type: Journal Article
• Authors: Zaitsev, Dmitry A.; Shmeleva, Tatiana R.; Luszczek, Piotr
• Is Part Of: International journal of parallel, emergent and distributed systems. Volume 37:Issue 2(2022)
• Page Start: 198
• Page End: 219
• Publication Date: 2022-03-04
• Subjects: Linear system -- parallel architecture -- clan composition -- graph partitioning -- speed-up -- load balancing; Parallel computers -- Periodicals; Electronic data processing -- Distributed processing -- Periodicals; Computer algorithms -- Periodicals; 004.35
• DOI: 10.1080/17445760.2021.2004412
• Languages: English
• ISSNs: 1744-5760

Abstract

Abstract : The paper further refines the clan composition technique that is considered a way of matrix partitioning into a union of block-diagonal and block-column matrices. This enables solving the individual systems for each horizontal block on a separate computing node, followed by solving the composition system. The size of minimal clans, obtained as a result of matrix decomposition, varies considerably. For load balancing, early versions of ParAd software were using dynamic scheduling of jobs. The present paper studies a task of static balancing the clan size. Rather good results are obtained using a fast bin packing algorithm with the first fit on a sorted array which are considerably improved applying a multi-objective graph partitioning with software package METIS. Aggregation of clans allows us to obtain up to three times extra speed-up, including systems over fields of real numbers, on matrices from Model Checking Contest and Matrix Market.