On Jan 25, 1:31 am, parisse <bernard.pari...@ujf-grenoble.fr> wrote:
> I also implemented parallel multiplication in giac, but with the > degree of the first variable to separate threads (that's easier to > implement than rebuilding one heap from several heaps). This work also > on distributed polynomials if the ordering is lex. I did however not > experience much (working on other topics for example multivariate > gcd), it certainly does not show a superlinear speedup, it is > sublinear (perhaps in part because the structure of the multiplication > is changed), something like time*1.3/number of threads. Parallel algorithms are often slower because communication and synchronization are overhead. The only way to get superlinear speedup is if the subproblems can be done in cache. Then it's a question of how far you can go, i.e. how sparse, because sparsity increases all the overhead costs. > do you believe it could be faster to split the problem to benefit > from cache effects even on a single processor? Maybe. It depends on what you do. For totally sparse problems the answer is no. You will write intermediate results to memory and it will be more work to read them back in than it would be to use a larger heap. For dense problems the answer is tentatively yes, however you can also shrink the size of the heap. See the "chaining" section in http://www.cecm.sfu.ca/~rpearcea/sdmp/sdmp_div.pdf The details of what may be faster or not will depend on your implementation. --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
