From: musiphil@bawi.org   
      
   On 2012-07-07 13:00, sizil.krishna23@gmail.com wrote:   
   >   
   > I am working on code to multiply matrices of higher dimensions eg.   
   10000x10000.   
   > Code is working, but i want to reduce the time elapsed as much as possible.   
   >   
   > So i used Cannon's Matrix Multiplication algorithm, (In this algorithm   
   > Matrix is divided into partitions of smaller size, as 5,10,20,100 or whatever   
   > we want). I have a doubt that whenever i access any partition(element) of   
   > that 2d array, Does the whole row or column of that 2d array is fetched   
   > to memory or cpu ? Or only that specific partition(element) is fetched ?   
   >   
   > If the whole row or column is fetched. Suggest some ways to fetch only   
   > that specific partition(element). Can vectors do that? Or i have to create   
   > N smaller 2d matrices (N = number of partitions) and copy data of matrix   
   > into smaller matrices.   
      
   All that can be said from the the C++ language point-of-view is that   
   an N-dimensional array is really an array of (N-1)-dimensional arrays;   
   e.g. given "T A[M][N];", A is an array of M arrays of N T's, and it   
   follows that each set of N T-objects should be consecutive. That is,   
   given a matrix implemented with a two-dimensional array, each row has   
   consecutive columns, while each column does NOT have consecutive rows.   
   Std::vectors are not any different in this regard.   
      
   With regards to (pre-)fetching, what usually happens is the CPU fetches   
   several consecutive words as a unit, and there's no language rule that   
   a whole row or a whole column should be fetched together. Given "double   
   A[10000][10000];", when you access A[5][2] it is likely that A[5][1] or   
   A[5][3] will be prefetched, but it is unlikely that any of A[5][9999] or   
   A[4][2] or A[6][2] will be prefetched.   
      
   If you work on an algorithm that works on submatrices, it may be advisable   
   that you divide the matrix into many small arrays each of which fits better   
   in a single cache line.   
      
   --   
   Seungbeom Kim   
      
      
         [ See http://www.gotw.ca/resources/clcm.htm for info about ]   
         [ comp.lang.c++.moderated.    First time posters: Do this! ]   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)