[petsc-users] Question about matrix permutation

[Barry Smith]

On Jan 29, 2010, at 2:46 PM, Jed Brown wrote:

> On Fri, 29 Jan 2010 13:48:57 -0600, Barry Smith <bsmith at mcs.anl.gov>  
> wrote:
>>    **If you have a matrix with say block size of 4 and store it with
>> BAIJ and do factorizations and solvers and it takes N seconds then
>> solve the same system with factorization and solvers with AIJ it will
>> take at least 1.5 * N seconds.
>
> If the AIJ system uses full blocks, then it's much less clear since
> inodes would be used.

    This is why I have the 1.5 there instead of 2.5 or 3 or more you  
might see without inodes.

>  I've still found this number to be about right,
> but not due to the standard "memory bandwidth required for the matrix
> entries and column indices" performance model.  I have a hard time
> explaining it since the vector access is almost identical.  Perhaps it
> is due to poor prefetch of matrix entries?

   If you look at the code, for example, MatMult_SeqAIJ_Inode() you  
will see a couple of things that keep it from being as good as the  
block version. The "blocking" of column indices is only taken  
advantage of for the rows, not for columns. So if the block size is 4,  
with BAIJ there is one column index loaded per block while with Inodes  
there are 4. (without inodes there are 16). In additional all the  
"extra" column entries are still stored in the a->j array. Thus when  
we move to each new set of rows we skip over those entries, thus  
partial cache lines of a->i are constantly wasted. With BAIJ the a->i  
array is accessed sequentially and linearly and all entries are used.

   Whenever someone suggests the performance loss is possibly coming  
from "poor prefetch", it is clear they don't understand enough about  
the details of the data access, in my experience prefetch is or lack  
there of is purely an academic exercise and never really happens :-)

   Barry

inodes are essentially blocking in one direction only, while BAIJ does  
in both.


>
> Jed