Process Characteristics

Algorithm Elements

CIS343

 

Preliminaries

w Use ExecutionTrace file produced by run of executor

w Retain only 1st memory reference of Syscall/Write

     v If this is via DMA, then it proceeds independently of ticking processor clock

     v If not, then we would need to tick processor clock on each memory reference

     v When we look at paging, we will need to bring those memory references back

          into consideration

 

Data Structures

w Structs:

     v MemRef

          X Address: Memory location referenced

          X TempLoc: Is this a case of temporal locality?

          X SpatLoc: Is this a case of spatial locality?

     v ClockTick

          X NumRefs: How many memory references occurred?

          X MemRef-1: a memory reference

          X MemRef-2: a memory reference

w Arrays:

     v ExecutionTrace: Memory location referenced

          X n elements, where n is the number of instruction executions

          X Each element: a clock tick

w Questions:

     v Why are there only 2 MemRef’s per clock tick?

     v How do you know what size to make the array?

 

Basic Algorithm  {For each trace}

w Note: It may be possible to combine some of the steps described below.

            They are presented separately for perspicuity

w Read execution trace data into array

     v Read value to "prime the pump"

          X This should be a -1 to indicate the first instruction execution

     v Enter reading loop

          X Increment array index

          X Read next value (this should be a non-negative number)

              Y Store this as MemRef-1

              Y Set NumRefs to 1.

          X Read next value (this could be either positive or 0 or negative)

              Y If it is negative, do nothing

              Y If it is non-negative

                    T Store this as MemRef-2

                    T Set NumRefs to 2

                    T Read values until negative number is read

     v Leave reading loop

          X Note: You will need to establish a test for end of file

w Step through array initializing values of TempLoc and SpatLoc

     v Mark all memory references as non-local

w Step through array marking instances of temporal locality

     v Let loctime be the temporally local time frame

     v For each memory reference, m, if there is another reference, r, to the same

          location within loctime units of time (clock ticks):

          X Mark TempLoc for both m and r to be true.

          X Note: Be sure to count each MemRef-1 and MemRef-2 separately!

w Step through array marking instances of spatial locality

     v Let loctime be the temporally local time frame

     v Let locspace be the spatially local distance frame

     v For each memory reference, m, if there is another reference, r, to a memory

          location within loctime units of time and locspace units of space:

          X Mark SpatLoc for both m and r to be true.

          X Note: Again, be sure to count each MemRef-1 and MemRef-2 separately!

w Tally up the results

     v Let totmemrefs be the total number of memory references

          X Question: How is this value obtained?

          X Hint: This number will be greater than the number of instruction executions.

     v Let tlmemrefs be the number of temporally local memory references

          X Question: How is this value obtained?

     v Let slmemrefs be the number of spatially local memory references

          X Question: How is this value obtained?

     v Calculate the degree of temporal locality

          X tlmemrefs / totmemrefs

     v Calculate the degree of spatial locality

          X slmemrefs / totmemrefs

w Question: The degrees of temporal and spatial locality are properties of something.

          Of what entity are they properties?

 

Testing Your Program

w Try out your algorithm on the execution trace on this web page.