mpcache.c

体系机构仿真

/*
 * mpcache.c - multiprocessor cache simulation code with graphic visualization
 *
 * This file is used in conjunction with the SimpleScalar tool suite
 * originally written by Todd M. Austin for the Multiscalar Research Project
 * at the University of Wisconsin-Madison.
 *
 * The file was created by Naraig Manjikian at Queen's University,
 * Kingston, Ontario, Canada.
 *
 * Copyright (C) 2000 by Naraig Manjikian
 *
 * This source file is distributed "as is" in the hope that it will be
 * useful.  The tool set comes with no warranty, and no author or
 * distributor accepts any responsibility for the consequences of its
 * use. 
 * 
 * Everyone is granted permission to copy, modify and redistribute
 * this tool set under the following conditions:
 * 
 *    This source code is distributed for non-commercial use only. 
 *    Please contact the maintainer for restrictions applying to 
 *    commercial use.
 *
 *    Permission is granted to anyone to make or distribute copies
 *    of this source code, either as received or modified, in any
 *    medium, provided that all copyright notices, permission and
 *    nonwarranty notices are preserved, and that the distributor
 *    grants the recipient permission for further redistribution as
 *    permitted by this document.
 *
 *    Permission is granted to distribute this file in compiled
 *    or executable form under the same conditions that apply for
 *    source code, provided that either:
 *
 *    A. it is accompanied by the corresponding machine-readable
 *       source code,
 *    B. it is accompanied by a written offer, with no time limit,
 *       to give anyone a machine-readable copy of the corresponding
 *       source code in return for reimbursement of the cost of
 *       distribution.  This written offer must permit verbatim
 *       duplication by anyone, or
 *    C. it is distributed by someone who received only the
 *       executable form, and is accompanied by a copy of the
 *       written offer of source code that they received concurrently.
 *
 * In other words, you are welcome to use, share and improve this
 * source file.  You are forbidden to forbid anyone else to use, share
 * and improve what you give them.
 */

#include <stdlib.h>
#include <math.h>

#include "ss.h"
#include "sim.h"
#include "misc.h"

#ifdef GRAPHICS
#include "graphics.h"
#endif /* GRAPHICS */

/* cache line states */
enum {UNTOUCHED = 0, INVALID, SHARED, EXCLUSIVE, MODIFIED, MODIFIED_ABOVE};

/* bus request types */
enum {READ, READ_EX, UPGRADE};

static int	L1_cache_line_size, L2_cache_line_size;
static int	L1_cache_size,      L2_cache_size;
static int	L1_num_lines,       L2_num_lines;
static int	L1_line_shift,      L2_line_shift;
static int	L1_line_mask,       L2_line_mask; /* mask after line shift */
static int	L1_tag_shift,       L2_tag_shift;

static int	L2_to_L1_line_size_ratio;	/* should be a power of 2 */

/* arrays for storing tags and states for L1 and L2 caches of each processor */
static unsigned int	*L1_tags[MAX_PROCS];
static unsigned int	*L1_states[MAX_PROCS];
static unsigned int	*L2_tags[MAX_PROCS];
static unsigned int	*L2_states[MAX_PROCS];

typedef	struct	_mpcachestats
{
    unsigned int	num_instructions,
			L1_accesses,
			L1_stores,
			L1_hits,
			L1_misses;
    double		L1_miss_ratio;
    unsigned int	L1_upgrades;
    double 		L1_upgrade_miss_ratio;
    unsigned int	L2_writebacks,
			L2_accesses,
			L2_hits,
			L2_misses;
    double		L2_miss_ratio;
    unsigned int	L2_upgrades;
    double		L2_upgrade_miss_ratio,
			mem_writebacks,
			exclusive_to_modified_changes,
			read_requests,
			exclusive_data_returns,
			read_excl_requests,
			upgrade_requests,
			external_bus_requests,
			snoop_hits;
    double		snoop_hit_ratio;
    unsigned int	exclusive_to_shared_changes,
			shared_data_responses,
			exclusive_data_responses,
			external_invalidations;
} MPCacheStats;

static	char	*stat_names[] =
{
    "Instructions",
    "L1_accesses",
    "L1_stores",
    "L1_hits",
    "L1_misses",
    "L1_miss_ratio",
    "L1_upgrades",
    "L1_upgrade_miss_ratio",
    "L2_writebacks",
    "L2_accesses",
    "L2_hits",
    "L2_misses",
    "L2_miss_ratio",
    "L2_upgrades",
    "L2_upgrade_miss_ratio",
    "mem_writebacks",
    "excl_to_mod_changes",
    "read_requests",
    "excl_data_returns",
    "read_excl_requests",
    "upgrade_requests",
    "external_bus_requests",
    "snoop_hits",
    "snoop_hit_ratio",
    "excl_to_shrd_changes",
    "shrd_data_responses",
    "excl_data_responses",
    "external_invalidations"
};

static	int	double_flags[] =
{
    0,	/* Instructions */
    0,	/* L1_accesses */
    0,	/* L1_stores */
    0,	/* L1_hits */
    0,	/* L1_misses */
    1,	/* L1_miss_ratio */
    0,	/* L1_upgrades */
    1,	/* L1_upgrade_miss_ratio */
    0,	/* L2_writebacks */
    0,	/* L2_accesses */
    0,	/* L2_hits */
    0,	/* L2_misses */
    1,	/* L2_miss_ratio */
    0,	/* L2_upgrades */
    1,	/* L2_upgrade_miss_ratio */
    0,	/* mem_writebacks */
    0,	/* excl_to_mod_changes */
    0,	/* read_requests */
    0,	/* excl_data_returns */
    0,	/* read_excl_requests */
    0,	/* upgrade_requests */
    0,	/* external_bus_requests */
    0,	/* snoop_hits */
    1,	/* snoop_hit_ratio */
    0,	/* excl_to_shrd_changes */
    0,	/* shrd_data_responses */
    0,	/* excl_data_responses */
    0,	/* external_invalidation */
};

/* compute number of statistics in a clever manner
   using ratio of array size and array element size
   (if new statistics are added, all arrays should be updated properly!) */
#define NUM_STATISTICS (sizeof (stat_names) / sizeof (char *))

/* array of per-processor statistic structures */
static	MPCacheStats mpcachestats[MAX_PROCS];

/* global statistics */
static	double		invalidation_set_size_sum;
static	unsigned int	invalidation_set_size_samples;
static	unsigned int	invalidation_set_size_histogram[MAX_PROCS];

/* total processes created --- defined externally */
extern	volatile int	num_created_processes;


#ifdef GRAPHICS
/*--------------------------------------------------------------------
|
| Start of conditionally-compiled definitions for graphics
|                                                                   */ 

/* how many processors to display on screen */
#define NUM_DISPLAYED_PROCESSORS 8

/* these are constants and macros used for the graphical display */

#define WIN_WIDTH  640
#define WIN_HEIGHT 480

#define DISPLAY_WIDTH 580

#define P_WIDTH  64
#define P_HEIGHT 32

#define P_Y	100
#define P_X	 10

#define C_X	 P_X
#define C_Y	(P_Y+P_HEIGHT+10)

#define C_L1_WIDTH 32
#define C_L2_WIDTH 64

#define C_L1_HEIGHT 32

#define	BAR_WIDTH 10

/* This macros computes a processor-specific horizontal offset.
   i = processor id
   w = width of object within the space for the processor
       (used to center object within the space) */
#define OFFSET(i,w) ((i)*(DISPLAY_WIDTH/NUM_DISPLAYED_PROCESSORS)+ \
		     (DISPLAY_WIDTH/NUM_DISPLAYED_PROCESSORS-(w))/2)

/* This macros computes a processor-specific horizontal offset,
   similar to the above macro, but divides the space into quarters.
   i = processor id
   w = width of object to be positioned within the space
   q = which quarter (0-3) in which to center */
#define Q_OFFSET(i,w,q) ((i)*(DISPLAY_WIDTH/NUM_DISPLAYED_PROCESSORS)+ \
		         (q*DISPLAY_WIDTH/NUM_DISPLAYED_PROCESSORS/4 \
			  +(DISPLAY_WIDTH/NUM_DISPLAYED_PROCESSORS/4-(w))/2))

/* variables to keep track of most recent L1 & L2 references/misses
   per processor to display bar graphs of miss ratios */

static	int	ref_count[MAX_PROCS];
static	int	L1_miss_count[MAX_PROCS];
static	int	L2_miss_count[MAX_PROCS];
static	int	L1_last_miss_ratio[MAX_PROCS];
static	int	L2_last_miss_ratio[MAX_PROCS];

/* defines how many calls to graphical cache line state change function
   before display is flushed to update screen */
#define	FLUSH_INTERVAL 255

/* defines how many memory accesses between updates to miss ratio bar graphs */
#define MISS_INTERVAL 10000

/* defines how many memory accesses between checking for X window events */
#define WINDOW_EVENT_INTERVAL 10000

/* flag for controlling whether graphics are used */
static	int	graphics_flag;

/* parameter to control display speed */
static	int	graphics_speed;

/* flag indicating whether window is mapped to screen (i.e., visible) */
static	int	mapped = 1;	/* assume initially mapped once
				   window is created */

/*
|
| End of conditionally-compiled definitions for graphics
|                                                                    
--------------------------------------------------------------------*/
#endif /* GRAPHICS */


/* macros for setting cache line states; these can be overridden
   to call other functions, such as for graphical display */

#ifdef GRAPHICS
#define SET_L1_STATE(pid,line,state) \
	((L1_states[pid][line]=state), (graphics_flag) ? \
					LineStateChange (pid, 1, line, state) \
					: 0)
#define SET_L2_STATE(pid,line,state) \
	((L2_states[pid][line]=state), (graphics_flag) ? \
					LineStateChange (pid, 2, line, state) \
					: 0)
#else /* ! GRAPHICS */
#define SET_L1_STATE(pid,line,state) (L1_states[pid][line]=state)
#define SET_L2_STATE(pid,line,state) (L2_states[pid][line]=state)
#endif /* GRAPHICS */

/*------------------------------------------------------------------*/

#ifdef GRAPHICS
static	void	LineStateChange (int pid, int level, int line, int new_state)
{
    static unsigned int flush_count = 0;
    int	g_width, x, y;
    int	color;

    if (! mapped)	/* don't bother with plotting if window not mapped */
	return;
    
    g_width = (level == 1) ? C_L1_WIDTH : C_L2_WIDTH;
    y = line / g_width;
    x = line % g_width;
	    
    switch (new_state)
    {
	case INVALID:
	    color = BLACK;
	    break;
	case SHARED:
	    color = GREEN;
	    break;
	case EXCLUSIVE:
	    color = YELLOW;
	    break;
	case MODIFIED:
	    color = RED;
	    break;
	case MODIFIED_ABOVE:
	    color = CYAN;
	    break;
    }
    SetColor (color);
    SetPoint (C_X + OFFSET (pid, g_width) + x,
	      C_Y + (level - 1) * C_L1_HEIGHT + y);

    /* force a flush for X windows with appropriate interval of calls here */
    if (++flush_count == FLUSH_INTERVAL)
    {
	flush_count = 0;

	/* delay for the amount that corresponds to the animation speed
	   (in units of speed * 10 msec) */
	if (graphics_speed != 10)
	    usleep ((10-graphics_speed) * 10000);
	FlushWindow ();
    }
}
#endif /* GRAPHICS */

/*------------------------------------------------------------------*/

#ifdef GRAPHICS
static	void	DrawBackground (void)
{
    int	pid;

    SetColor (BLACK);

    for (pid = 0; pid < NUM_DISPLAYED_PROCESSORS; pid++)
    {
	int	x, y, width, height, level;
	char P_Name[16];

	/* processor */
	P_Name[2] = 0;
	P_Name[1] = '0' + pid;
	P_Name[0] = 'P';

	DrawRectangle (P_X + OFFSET(pid,P_WIDTH), P_Y,
		       P_WIDTH, P_HEIGHT);
	DrawString (P_Name, P_X+OFFSET(pid,0), P_Y + P_HEIGHT/2);

	/* caches */
	for (level = 1; level <= 2; level++)
	{
	    width = (level == 1) ? 32 : 64;
	    height = (level == 1) ? (L1_num_lines / width)
		: (L2_num_lines / width);
	    x = C_X + OFFSET (pid, width) - 1;
	    y = C_Y + (level - 1) * 32 - 1;
	    width += 1;
	    height += 1;
	    DrawRectangle (x, y, width, height);
	}

	/* scale for miss ratio */
	DrawString ("100%", DISPLAY_WIDTH,9);
	DrawString ("50%", DISPLAY_WIDTH, 56);
	DrawString ("0%", DISPLAY_WIDTH, 98);
	DrawString ("miss", DISPLAY_WIDTH+40, 50);
	DrawString ("ratio", DISPLAY_WIDTH+40, 50+10);

	/* labels for L1 and L2 caches */
	DrawString ("L1", DISPLAY_WIDTH+30, C_Y + 10);
	DrawString ("L2", DISPLAY_WIDTH+30, C_Y + 120);
    }
}
#endif /* GRAPHICS */

/*------------------------------------------------------------------*/

void	MPCacheInit (int L1_line_size, int L1_size,
		     int L2_line_size, int L2_size,
		     int gr_flag, int gr_speed)
{
    int	pid;

#ifdef GRAPHICS    
    graphics_flag = gr_flag;
    graphics_speed = gr_speed;
#endif /* GRAPHICS */

    /* save line and cache sizes from function arguments */
    L1_cache_line_size	= L1_line_size;
    L1_cache_size	= L1_size;
    L2_cache_line_size	= L2_line_size;
    L2_cache_size	= L2_size;
    
    L2_to_L1_line_size_ratio = L2_cache_line_size / L1_cache_line_size;

    /* compute necessary information for maintaining caches */
    L1_num_lines  = L1_cache_size / L1_cache_line_size;
    L1_line_shift = log_base2 (L1_cache_line_size);
    L1_line_mask  = L1_num_lines - 1;
    L1_tag_shift  = L1_line_shift + log_base2 (L1_num_lines);
    
    L2_num_lines  = L2_cache_size / L2_cache_line_size;
    L2_line_shift = log_base2 (L2_cache_line_size);
    L2_line_mask  = L2_num_lines - 1;
    L2_tag_shift  = L2_line_shift + log_base2 (L2_num_lines);