Go backward to Parallel Algorithm
Go up to Parallel Resultant Computation
Go forward to Benchmark Results
|
Go backward to Parallel Algorithm Go up to Parallel Resultant Computation Go forward to Benchmark Results |
|
We have implemented above algorithm for r=2 using
the Distributed Maple constructs dist[start] and
dist[wait]. Furthermore, we have replaced the Maple function
resultant/bivariate (which is called by Maple
for computing the resultants of bivariate polynomials) by a version that uses
our parallel implementation if the degrees of both input polynomials in the
main variable are are greater than five and the degree of one input polynomial
is greater than ten. All other cases are still solved by sequential methods.
The implementation differs from above algorithm in that each task computes multiple modular resultants respectively multiple coefficients of the integer resultant. By adjusting the number of elements computed by a task we can effectively control its grain size.
For estimating the execution time of a "ResultantModular" task we use the complexity bound [12]
where degreei(P) denotes the degree of P in the i-th variable. Based on this bound (multiplied by an experimentally determined constant that represents the processor speed) our implementation adjusts the number of modular images per task such that each task is expected to execute roughly 10 seconds. Smaller grain sizes unduly increase the execution overhead while larger grain sizes may cause significant load imbalances.
(1+max(degreer(A), degreer(B))) *PRODi=1r(1+max(degreei(A), degreei(B))) *SUMi=1r(1+max(degreei(A), degreei(B)))
We also adjust the number of coefficients computed per "ChineseRemainderCoeff" task such that it processes for any input a constant number of modular coefficients. We have experimentally determined a value for this constant (1800) such that the execution time of a the task roughly matches the execution time of a "ResultantModular" task.
The first four modular resultants are actually computed sequentially in order to derive an improved value for the degree bound such that fewer coefficients have to be considered in the rest of the algorithm.