2020/09/30 by Lorenzo De Stefani, De Stefani, Lorenzo
Computer Science · #Advanced Data Storage Technologies #Complexity and Algorithms in Graphs #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #Parallel Computing and Optimization Techniques #Stochastic Gradient Optimization Techniques #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2009.14590
openalex publication_date 2020/09/30 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
We present COPSIM a parallel implementation of standard integer\nmultiplication for the distributed memory setting, and COPK a parallel\nimplementation of Karatsuba's fast integer multiplication algorithm for a\ndistributed memory setting. When using \P processors, each equipped\nwith a local non-shared memory, to compute the product of tho n-digits\ninteger numbers, under mild conditions, our algorithms achieve optimal speedup\nof the computational time. That is, \O\(n2/\P\)\nfor COPSIM, and \O\(n\log2 3/\P\) for COPK.\nThe total amount of memory required across the processors is\n\O\(n\), that is, within a constant factor of the minimum\nspace required to store the input values. We rigorously analyze the\nInput/Output (I/O) cost of the proposed algorithms. We show that their\nbandwidth cost (i.e., the number of memory words sent or received by at least\none processors) matches asymptotically corresponding known I/O lower bounds,\nand their latency (i.e., the number of messages sent or received in the\nalgorithm's critical execution path) is asymptotically within a multiplicative\nfactor \O\(\log22 \P\) of the corresponding\nknown I/O lower bounds. Hence, our algorithms are asymptotically optimal with\nrespect to the bandwidth cost and almost asymptotically optimal with respect to\nthe latency cost.\n