Jean Christophe Beyler

ESODYP

Downloading

• The stride version is the basic version. This is actually the first version of the system and handles the modelization of memory strides in a program. The system automatically creates the Markov model and prefetches data when the current behavior is predictable.
• The address version is a second version and only has a slight modification compared to the first version. Instead of modelizing memory strides, this version modelizes absolute addresses. Like the first system, it creates the Markov model and prefetches data when the current behavior is predictable.
• The structure version is a more complex version. It uses a structure to define the elements that are modelized which gives the user the chance to modify the structure and handle any type of data. The user only has to define a few functions to modify the internal representation of the modeled elements.
• The manager version gives the programmer the chance to easily test different parameters in order to find the best parameters for a particular program and memory behavior. It uses the stride version of the ESODYP framework.

Installing

//inline prefetch function
inline void Markov_PrefetchItNoReally(void* x)
{
    //only lfetch
    __asm__ __volatile__ (
	      "lfetch [%0]\n"
	      ::"r" (x)
	      );

}

//inline prefetch function
inline void Markov_PrefetchItNoReally(void* x)
{
    //only lfetch
    __asm__ __volatile__ (
            "prefetchnta (%0)\n"
            ::"r" (x)
            );
}

Integrating the ESODYP model in your program

#include <stdio.h>
#include <stdlib.h>

#define L 90
#define M 50000
#define N 40

int main(void)
{
    int t[M][N];
    int sum =0;
    int h,i,j;

    /* Init */
    for(i=0;i<M;i++) {
        for(j=0;j<N;j++) {
            t[i][j] = i*j;
        }
    }

    /* Sum */
    for(h=0;h<L;h++) {
        for(j=0;j<N;j++) {
            for(i=0;i<M;i++) {
                sum += t[i][j];
            }
        }
    }

    printf("Sum %d \n", sum);
    return EXIT_SUCCESS;
}

Including the header

#include "Markov_stride.h"

Initialization

    //Initialize memory
    SMarkov* m = Markov_Initialize();

                sum += t[i][j];

		m->fct(m, &(t[i][j]));
                sum += t[i][j];

Parameters

    Markov_Set(m,2,M_CONSDEPTH); //Set depth of construction

void Markov_Set(SMarkov *m, int v, int mask);                   //Set certain attributes

• M_CONSDEPTH: order, or depth of construction, of the model. This value determines how many elements are to be used to calculate a prediction. The default value is 2;
• M_ERRMAX: number of consecutive miss predictions before the model is flushed and a new one is constructed. The lower the number, the more models will be constructed during the execution of the program if the behavior is not very predictable. However, if the number is too high, it will take a lot of miss predictions before the model is updated. The default value is 20;
• M_CONSTTL: time-to-live of the construction. This parameter determines the number of elements used to construct the model before starting to prefetch. The default value is 30;
• M_PREFDIST: prefetch distance of the system. This gives the model the number of elements between the predicted element and the current one. The default value is 3;

Clearing the model

    Markov_Clear(m);

Going even further

Manually resetting the model

void Markov_Reset(SMarkov *m);                          //Reset the model

Resetting the current address

void Markov_SetAddress(SMarkov* m, void *address);

Outputting information about the graph

int Markov_OutputGraph(SMarkov *m);                     //Output graph to terminal
int Markov_OutputGraphDot(SMarkov *m, const char *fname);               //Output graph to .dot format

digraph {
size="8,8";
3084730456 [label="(0)\n 160",shape=box,color=red,style=filled]
3084730456 -> 3084730508 [fontcolor=blue,label ="3599"]
3084730508 [label="(1)\n 160"]
3084730508 -> 3084730508 [fontcolor=blue,label ="179989170"]
}

        for(j=0;j<N;j++) {
            for(i=0;i<M;i++) {
                sum += t[(3*i+4)%M][(2*i+5*j)%N];
                m->fct(m,&(t[(3*i+4)%M][(2*i+5*j)%N]));
            }
        }

Modifying the base behavior

• __DEBUG__: this is a verbose mode. Use it if you want to understand what is happening;
• __NORMAL_VERB__: this is a semi-verbose mode. It gives less information than in debug mode;
• __OPT_VERIF__: this option sets a verification of the model and prints out information about the prediction accuracy;
• __PREFETCH__: sets prefetching on. Otherwise the model simply modelizes the behavior and does not try to optimize the program. Generally used to calculate the overhead;
• __DRAW_DOT_FILES__: automatically creates two dot files. One at the end of the construction and one if the model was cleared.

The structured version

Redefining the structure

/*Instead of having a single stride as information, we'll do an abstraction using a structure */
typedef struct sGlobalAdd {
    u_int32_t high;
    u_int32_t low;
} SGlobalAdd;

Modifying the dependent functions

static void INFO_print(SGlobalAdd* info)
static void INFO_reset(SGlobalAdd* info)
static int INFO_isNull(SGlobalAdd* info)
static void INFO_OutputFile(FILE* f,SGlobalAdd* info)
static int INFO_compare(SGlobalAdd* a, SGlobalAdd* b)

• INFO_print(a): prints out the information from structure a to the terminal;
• INFO_reset(a): sets the fields from structure a to a Null setting. Basically, with the settings put in place when INFO_reset is called, INFO_isNull should return 1. If something is changed in the structure, INFO_isNull should return 0;
• INFO_isNull(a): function returns 1 if the structure a represents the Null structure (reference point). It returns 0 otherwise;
• INFO_OutputFile(f,a): outputs information from structure a into a file f. This function can have the same output as the INFO_print function;
• INFO_simplecompare(a,b): function returns 0 if the elements a and b are not equal, returns 1 otherwise;
• INFO_compare(a,b): function works like strcmp. Returns -1, 0 or 1 if a is respectively considered less than, equal to or greater than b.

PREFETCH_FUNCTION

Conclusion