memorytraffic.java

金融资产定价,随机过程,MONTE CARLO 模拟 JAVA 程序和文档资料

/* WARANTY NOTICE AND COPYRIGHT
This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.

Copyright (C) Michael J. Meyer

[e-mail]
[e-mail]

*/


/*
 * MemoryTraffic.java
 *
 * Created on September 7, 2002, 12:04 AM
 */

package Examples.Array;

import Statistics.Random;
import RandomVariables.*;


/** <p>Checks how the geometry of memory access in two dimensional arrays
 *  (row by row, column by column, random) impacts execution time.
 *  We allocate an <code>M by N</code> array with <code>M=5,000</code> and
 *  <code>N=1000</code> doubles for a total of 40MB. We then traverse the array
 * in one of three ways incrementing each element by one:</p>
 * <ul>
 * <li>1. We run through the array row by row in an orderly manner in 
 *     the same way the array is stacked in memory.</li>
 * <li>2. We run through the array moving down the columns in an orderly 
 *     manner but not in the way the array is stacked in memory.</li>
 * <li>3. We run through the array completely randomly addressing
 *       elements with a random number generator.</li>
 * </ul>
 * Array elements will be accessed <code>N*M</code> times in each loop
 * and execution will be timed.</p>
 *
 * <p>Since the array is much bigger than the cache, memory 
 * traffic and the geometry of memory access plays an important role.
 * The expectation is that 1. will run faster than 2. which will run faster 
 * than 3. To keep things fair we include two random
 * number generator calls for each array access (one for each index) in all 
 * loops. We want to know how big the penalty is for jumping around in memory.
 * </p>
 *
 * <p><b>Results:</b> the calls to the random number generator consume 95%
 * of the time and <i>yet row by row access is nearly twice as fast</i> as 2. 
 * and 3. which are equally slow. Column by column access is just as bad as
 * completely random access. Without random number generation <i>row by row 
 * access is nearly <strong>10 times faster</strong> than column by column 
 * access</i>.</p>
 *
 * <p><b>In the L2-cache:</b> next we slim the arrays down to a size which fits
 * into the L2-cache but loop through them more often so that the number of
 * array element accesses remains the same. This should speed up things since 
 * it eliminates memory to cache traffic. The experiment is conducted only for
 * row by row and column by column access, no random number generation.</p>
 *
 * <p><b>Results:</b> row by row access is 50% faster than column by column
 * access and is about 2.5 times faster than the row by row access to main
 * memory.</p>
 *
 *
 * @author  Michael J. Meyer
 */
public class MemoryTraffic {
    
    
    static final int N=5000, M=1000;
    static final double[][] big=new double[N][M];
    
    static final int n=N/20, m=M/20;
    static final double[][] small=new double[n][m];
  
    static final edu.cornell.lassp.houle.RngPack.RandomElement 
    RE= new MersenneTwisterRandomElement();
  
    
    public static void main(String[] args){
        
       String message="TIMING LOOPS THROUGH LARGE TWO DIMENSIONAL ARRAYS:\n\n";
       System.out.println(message);
  
       double before, after, time;
    
       // MEMORY TO CACHE
       
       // ROW BY ROW
       before=System.currentTimeMillis();
       for(int i=0;i<N;i++)
       for(int j=0;j<M;j++){
        
           //RE.choose(0,N-1);
           //RE.choose(0,M-1);
           big[i][j]++;
       }
       after=System.currentTimeMillis();
       time=(after-before);
       System.out.println("Main memory, ow by row, time="+time);
        
       // COLUMN BY COLUMN
       before=System.currentTimeMillis();
       for(int j=0;j<M;j++)
       for(int i=0;i<N;i++){
        
           //RE.choose(0,N-1);
           //RE.choose(0,M-1);
           big[i][j]++;
       }
       after=System.currentTimeMillis();
       time=(after-before);
       System.out.println("Main memory, column by column, time="+time);
        
       /*
       // RANDOMLY
       before=System.currentTimeMillis();
       for(int j=0;j<M;j++)
       for(int i=0;i<N;i++)big[RE.choose(0,N-1)][RE.choose(0,M-1)]++;

       after=System.currentTimeMillis();
       time=(after-before);
       System.out.println("Main memory, random access, time="+time);
       */
       
       
       // LIFE IN THE L2-CACHE
       
       // ROW BY ROW
       before=System.currentTimeMillis();
       for(int c=0;c<400;c++)
       for(int i=0;i<n;i++)
       for(int j=0;j<m;j++)big[i][j]++;
     
       after=System.currentTimeMillis();
       time=(after-before);
       System.out.println("L2-cache, row by row, time="+time);
        
       // COLUMN BY COLUMN
       before=System.currentTimeMillis();
       for(int c=0;c<400;c++)
       for(int j=0;j<m;j++)
       for(int i=0;i<n;i++)big[i][j]++;
     
       after=System.currentTimeMillis();
       time=(after-before);
       System.out.println("L2-cache, column by column, time="+time);
       
    } // end main
    
    
  
    
} // end MemoryTraffic