Parallel Processing of First Order Linear Recurrence on SMP Machines |
| |
Authors: | Hong-soog Kim Young-ha Yoon Dong-soo Han |
| |
Affiliation: | (1) School of Engineering, Information and Communications University, PO Box 77, Yusong, Daejeon, 305-600, Korea |
| |
Abstract: | In this paper, we propose a new algorithm that analyzes the data dependency pattern in the first-order linear recurrence (FOLR) and transforms it into algebraically equivalent expanded form so that it can be processed in parallel using the threads on symmetric multiprocessor (SMP) machines. The transformation aims to eliminate the data dependencies in the naive nested form of the FOLR. However, as this transformation may result in extra multiplication operations, our algorithm examines the immanent overhead of the expanded form of the FOLR and generates a new hybrid form of the FOLR. The hybrid form combines nested and appropriately expanded form in order to make it suitable for parallel processing. The parallel algorithm based on the hybrid form of the FOLR is analytically examined and tested through implementation on SMP machines. The implementation details, such as the workload balancing between processors and the optimization of cache performance, are also discussed. The experimental results show that the parallel algorithm based on the hybrid form of the FOLR considerably improves the performance on SMP machines that have three of more processors. |
| |
Keywords: | parallel processing first-order linear recurrence operation SMP machine thread |
本文献已被 SpringerLink 等数据库收录! |
|