[prev in list] [next in list] [prev in thread] [next in thread]
List: gmp-devel
Subject: Iterative Cache Optimized Karatsuba-Ofman multiplication algorithm
From: tg () swox ! com (Torbjorn Granlund)
Date: 2004-02-25 14:02:11
Message-ID: 86eksj9usu.fsf () king ! swox ! se
[Download RAW message or body]
Josh Liu <zliu2@student.gsu.edu> writes:
I'm currently working on an iterative cache optimized Karatsuba-Ofman
multiplication algorithm. The premise behind the algorithm is that one
performs the basecase multiplies in the first part of the non-recursive
function and then the interpolation stage operates next. The algorithm will
not use an explicit stack structure because it will be based primarily on
loops. The cache optimized part comes from the fact that the operands to the
basecase multiplies will be ordered in such a way that they are lined up in
spatially with regards to the execution order. The basecase multiplies will
be deconstructed so that the products will be computed simultaneously
because the lines of the a group products will be formed together. I have
the indices of the basecase multiplies currently and I will work on the
interpolation stage later. I hope to be finished in two to three weeks.
This is interesting work. Please make provisions for using the
assembly-based mpn_mul_basecase for your basecase code, if at all
possible.
--
Torbj?rn
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic