文章基本信息

标题：A Load-Balanced Parallelization of AKS Algorithm
本地全文：下载
作者：Ardhi Wiratama Baskara Yudha ; Reza Pulungan
期刊名称：TELKOMNIKA (Telecommunication Computing Electronics and Control)
印刷版ISSN：2302-9293
出版年度：2017
卷号：15
期号：4
页码：1884-1893
DOI：10.12928/telkomnika.v15i4.6049
语种：English
出版社：Universitas Ahmad Dahlan
其他摘要：The best known deterministic polynomial-time algorithm for primality testing right now is due to Agrawal, Kayal, and Saxena. This algorithm has a time complexity O (log^{ 15 / 2} ( n )) . Although this algorithm is polynomial, its reliance on the congruence of large polynomials results in enormous computational requirement. In this paper, we propose a parallelization technique for this algorithm based on message-passing parallelism together with four workload-distribution strategies. We perform a series of experiments on an implementation of this algorithm in a high-performance computing system consisting of 15 nodes, each with 4 CPU cores. The experiments indicate that our proposed parallelization technique introduce a significant speedup on existing implementations. Furthermore, the dynamic workload-distribution strategy performs better than the others. Overall, the experiments show that the parallelization obtains up to 36 times speedup.