The extended GCD algorithm is very useful for data dependence tests, for example, the Power Test on supercomputers. We parallelize the extended GCD algorithm on a CREW SM MIMD computer with O(n) processors. We improve the sequential extended GCD algorithm and parallelize the extended GCD algorithm by two methods. We parallelize to triangularize the matrix by reducing elements in the same column simultaneously. This algorithm almost has no algorithmic redundancy, but has efficiency O(1/log/sub 2/n) where n is the number of variables. Second, some rows, which have been reduced at the current column in the above algorithm, can be reduced at the next column immediately. This algorithm has efficiency O(min(m, n-1)/n) where m is the number of linear diophantine equations, and is powerful when m is large. When m is equal to n-1, the efficiency of the algorithm is O(1).
展开▼
