Finding exemplars in dense data with affinity propagation on clusters of GPUs. (10th December 2012)

• Record Type: Journal Article
• Authors: Kurdziel, Marcin; Boryczko, Krzysztof; Hidalgo, Jose Ignacio; Fernández‐de‐Vega, Francisco; Amor, Margarita; Doallo, Ramón; Fraguela, Basilio B.; Herrero, José R.; Quintana‐Ortí, Enrique S.; Strzodka, Robert
• Is Part Of: Concurrency and computation. Volume 25:Number 8(2013:Jun.)
• Page Start: 1137
• Page End: 1152
• Publication Date: 2012-12-10
• Subjects: Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.2962
• Languages: English
• ISSNs: 1532-0626

Abstract

<abstract abstract-type="main" id="cpe2962-abs-0001"> <title>SUMMARY</title> <p id="cpe2962-para-0001">This work presents an efficient implementation of affinity propagation (AP) on clusters of graphical processing units (GPUs). AP is a state‐of‐the‐art method for finding exemplars in data sets described by similarity matrices. It is typically employed in crisp clustering applications. However, when finding exemplars in an <italic>n</italic>‐pattern data set with dense, non‐metric similarities, AP performs iterative processing of three <italic>n</italic> × <italic>n</italic> floating point matrices. One of them stores the similarities, and the other two store the values that will ultimately pinpoint the exemplars. For large similarity matrices, AP is therefore computationally expensive. Although matrix operations of AP are well suited for GPUs, its memory footprint limits the size of tasks that can be solved on one unit. We present, however, a decomposition scheme for AP that distributes the calculations over multiple GPUs, with low communication‐to‐computation ratio. Because of this favorable communication pattern, our implementation finds exemplars in large, dense similarity data efficiently, even when GPUs are connected by a slow network. Furthermore, by combining global device memory of multiple GPUs, it can solve problems that would not fit in a single unit. Copyright © 2012 John Wiley &amp; Sons, Ltd.</p> </abstract>