https://scholars.lib.ntu.edu.tw/handle/123456789/581418
標題: | Parallel Asynchronous Stochastic Dual Coordinate Descent Algorithms for High Efficiency and Stable Convergence | 作者: | Chen Y.-C Liu P Wu J.-J. PANGFENG LIU |
關鍵字: | Efficiency; Software testing; Stochastic systems; Convergence issues; Coordinate descent; Hybrid algorithms; Number of threads; Parallel executions; Sequential programs; Shared memory system; Stable convergence; Stochastic models | 公開日期: | 2021 | 起(迄)頁: | 44-53 | 來源出版物: | Proceedings - 29th Euromicro International Conference on Parallel, Distributed and Network-Based Processing, PDP 2021 | 摘要: | Parallel asynchronous stochastic dual coordinate descent algorithm (PASSCoDe) is an efficient method to train linear models in multi-core shared-memory systems. PASSCoDe enjoys a good speedup when the number of threads is less than 8 on sparse datasets, i.e., the percentage of nonzero elements in the training data is relatively small. However, due to the memory conflict and delayed parameter access problem in parallel execution, it often diverges or does not converge to the best accuracy as a serial dual coordinate descent algorithm does. In this paper, we propose two algorithms - Adaptive Hybrid algorithm and Lazy-Sync algorithm, to overcome the convergence issues in parallel execution. Both algorithms use the current accuracy to guide the execution and strike a balance between accuracy and efficiency. Experimental results indicate that both algorithms converge to the same high accuracy as a sequential program does on all datasets tested except on an extremely small one. On the other hand, PASSCoDe sometimes converges to a less accurate value or does not converge at all on some datasets. Our methods also outperform PASSCoDe-Fix, an improved version of PASSCoDe, in stable convergence, execution speed, and scalability. For example, the Adaptive Hybrid algorithm runs up to 2.8 times faster than PASSCoDe-Fix, and the Lazy-Sync algorithm runs 11 times faster than PASSCoDe-Fix on dataset covtype with 10 threads. ? 2021 IEEE. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-85105484100&doi=10.1109%2fPDP52278.2021.00016&partnerID=40&md5=a7d13fdbcde9f8ab389c7e0fa8c4a4a1 https://scholars.lib.ntu.edu.tw/handle/123456789/581418 |
DOI: | 10.1109/PDP52278.2021.00016 |
顯示於: | 資訊工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。