nullECE 353
Lab 1: Cache SimulationECE 353
Lab 1: Cache SimulationPurposePurposeIntroduce C programming by means of a simple example
Reinforce your knowledge of set associative cachesCachesCachesMotivation: The speed differential between main memory and processors is increasing. Main memory may take over a hundred CPU cycles to access.
Aim: Achieve the speed of high-speed memory, while keeping the cost per bit close to that of low-speed memory
Exploits locality:
Temporal locality
Spatial locality
Many machines have two levels of cacheUnits of MovementUnits of MovementThe contents of
Main memory: Organized into pages.
Cache: Organized into blocks or lines.
Material brought into main memory is moved in these units
Cache Blocks or LinesCache Blocks or LinesEach memory address belongs to a cache block.
The cache block address is the byte address with the rightmost lg B bits removed, where B is the size of the blockParts of a CacheParts of a CacheDirectory: Where the tags associated with the cache contents are stored.
Each directory entry corresponds to a matching line in the cache
When looking for an item in cache, we seek to match the tag of the desired item against the contents of the directory.
In addition to the tag, we also have a valid bit. Only return values from the cache if the tag matches and the valid bit indicates the line is valid.
Data Array: Where the contents of the cache are stored.Fully Associative CacheFully Associative CacheAny block can be placed anywhere in the cache
This flexibility may reduce the miss rate
When looking for an item, we need to search through the entire directory looking for a tag match
This parallel search can increase hardware complexity and the time taken to execute the matchDirect-Mapped CacheDirect-Mapped CacheEach cache set consists of exactly one line
This reduces flexibility, which may increase the miss rate
To check if the desired item is in the cache,
Identify the set that the item maps to
Check the contents of the single directory entry corresponding to that set.
Only one match needs to be done: can be done faster.K-way CachesK-way CachesEach set consists of K lines
When looking for an item in cache,
Identify the set to which it belongs
Do a parallel search among all the K tags in the directory corresponding to the K lines in that set Set Associative OrganizationSet Associative Organization© 2004 Morgan-Kaufman PublishersTypical PerformanceTypical Performance
Use split caches because there is more spatial locality in code: © 2004 Morgan-Kaufman PublishersCache SimulationCache SimulationUsed to determine the miss rate for a given trace and cache configuration.
The trace is a sequence of memory addresses
The cache configuration is
Data capacity of the cache
Number of lines (or blocks) per set
Number of bytes per lineCCMany of the constructs are very similar to those found in Java
In many other respects, C is more primitive:
Not object-oriented
Lacks inbuilt garbage collection, some checks (e.g. array bounds)
C carries out implicit type conversions when appropriateSome C ConstructsSome C ConstructsRelational, logical
<, <=, >, >=, ==, !=
&&, ||, !
Arithmetic
+, -, *, /, %
C Constructs (contd.)C Constructs (contd.)Some control constructs:
while( ) { };
if ( ) { };
for (i=0; i<100; i++) { };
Data TypesData Typesint
char
float
double
long
shortArraysArraysx[1000] is a linear array of 1000 elements
Y[100][100] is a two-dimensional 100x100 array
Variable names (like other things in C) are case-sensitive: Y is not the same as y.Example Example #include
#include
#define SIZE 100
main(){
int iter;
int a[SIZE], b[SIZE], c[SIZE];
for (iter=0; iter
main(){
int x, y;
FILE *ifp; //Pointer to a file is declared
ifp = fopen(“trace.txt”, “r”); // ifp points to file
// trace.txt, opened for
// reading
while (!feof(ifp) { // exit if end-of-file reached
fscanf(ifp, “%d %x”, &x, &y); // read next line
printf(“Address read = %x\n”, y);// print as required
}
fclose(ifp); // Close file
}If individual file lines consist of an integer followed by a hex quantity, and we
want to print out the hex quantity:Opening and Writing into Files: ExampleOpening and Writing into Files: Example#include
#include
main(){
int a[100], i;
FILE *output;
for (i=0; i<100; i++) a[i]=i;
output=fopen(“example.txt”,”w”);
for (i=0; i<100; i++)
fprintf(output, “%5d\n”, a[i]);
fclose(output)
} Cache Simulation (contd.)Cache Simulation (contd.)Given the following:
Cache parameters
Memory access trace
Obtain:
Cache hit rateSimulationSimulationMaintain the cache directory and LRU status of the lines within each set
When an access is made, update LRU status.
If a hit, record it as such
If a miss, update the contents of the directoryCache DirectoryCache DirectoryImplementation 1: Implement the directory as an array, with array entries corresponding to directory entries.
Advantage: Simpler to program if you don’t have much C experience
Disadvantage: Array sizes are static. The array would have to be large enough to accommodate the largest sized directory that the simulator is designed for
Cache Directory (contd.)Cache Directory (contd.)Implementation 2: Use pointers and malloc
Advantage: Is flexible and assigns memory dynamically.
Disadvantage: If this is your first non-trivial C program, assigning and freeing memory dynamically can be difficult.
malloc: Dynamically assigns memory.
The call malloc(b)
Allocates memory that is sufficient to hold b bytes.
Returns a pointer to the starting address of that chunk of memory
To allocate memory sufficient to hold b integers, use
malloc(b*sizeof(int))
Example of malloc Example of malloc int *dir_ptr;
int k; //value of k can change
dir_ptr = (int *) malloc(k * sizeof(int));
Freeing MemoryFreeing MemoryMemory that is allocated using malloc must be freed once it is no longer needed.
To free the memory that was allocated in the previous example, set dir_ptr to point to the starting point of the allocated chunk and do the call
free(dir_ptr)
本文档为【cache simulation】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。