int L1lookup(u_int32_t address) { ///// IMPLEMENT THIS ///// return 0; } int L2lookup(u_int32_t address) { ///// IMPLEMENT THIS ///// return 0; }
int L1lookup(u_int32_t address) { ///// IMPLEMENT THIS ///// return 0; } int L2lookup(u_int32_t address) { ///// IMPLEMENT THIS ///// return 0; }
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
Related questions
Topic Video
Question
instruction is in the first picture
please give me only implementation of int L1lookup(u_int32_t address) and int L2lookup(u_int32_t address)
cacheSim.h
#include<stdlib.h>
#include<stdio.h>
#define DRAM_SIZE 1048576
typedef struct cb_struct {
unsigned char data[16]; // One cache block is 16 bytes.
u_int32_t tag;
u_int32_t timeStamp; /// This is used to determine what to evict. You can update the timestamp using cycles.
}cacheBlock;
typedef struct access {
int readWrite; // 0 for read, 1 for write
u_int32_t address;
u_int32_t data; // If this is a read access, value here is 0
}cacheAccess;
// This is our dummy DRAM. You can initialize this in anyway you want to test.
unsigned char * DRAM;
cacheBlock L1_cache[2][2]; // Our 2-way, 64 byte cache
cacheBlock L2_cache[4][4]; // Our 4-way, 256 byte cache
// Trace points to a series of cache accesses.
FILE *trace;
long cycles;
void init_DRAM();
// This function print the content of the cache in the following format for an N-way cache with M Sets
// Set 0 : CB1 | CB2 | CB 3 | ... | CB N
// Set 1 : CB1 | CB2 | CB 3 | ... | CB N
// ...
// Set M-1 : CB1 | CB2 | CB 3 | ... | CB N
void printCache();
////// Part 1: Checking if the address is in the cache /////
// These functions perform a cache lookup to the associated cache levels. Return 0 if the address is not in the cache (cache miss) and 1 if the address is in the cache (cache hit)
int L1lookup(u_int32_t address);
int L2lookup(u_int32_t address);
// This function returns a setID given an address
unsigned int getL1SetID(u_int32_t address);
unsigned int getL2SetID(u_int32_t address);
// This function returns a tag given an address
unsigned int getL1Tag(u_int32_t address);
unsigned int getL2Tag(u_int32_t address);
////// Part 2: FIFO cache //////
// This function performs a read to a cache content. Return the 4-byte data content given by the address. Please note that the read access MUST evict existing cache block correctly based on the FIFO policy and insert the new cache block correctly into the cache.
u_int32_t read_fifo(u_int32_t address);
// EPart 3: handle write. Assuming a write-through cache. This is the only place you actually modify the data in the cache and DRAM
void write(u_int32_t address, u_int32_t data);
#include<stdio.h>
#define DRAM_SIZE 1048576
typedef struct cb_struct {
unsigned char data[16]; // One cache block is 16 bytes.
u_int32_t tag;
u_int32_t timeStamp; /// This is used to determine what to evict. You can update the timestamp using cycles.
}cacheBlock;
typedef struct access {
int readWrite; // 0 for read, 1 for write
u_int32_t address;
u_int32_t data; // If this is a read access, value here is 0
}cacheAccess;
// This is our dummy DRAM. You can initialize this in anyway you want to test.
unsigned char * DRAM;
cacheBlock L1_cache[2][2]; // Our 2-way, 64 byte cache
cacheBlock L2_cache[4][4]; // Our 4-way, 256 byte cache
// Trace points to a series of cache accesses.
FILE *trace;
long cycles;
void init_DRAM();
// This function print the content of the cache in the following format for an N-way cache with M Sets
// Set 0 : CB1 | CB2 | CB 3 | ... | CB N
// Set 1 : CB1 | CB2 | CB 3 | ... | CB N
// ...
// Set M-1 : CB1 | CB2 | CB 3 | ... | CB N
void printCache();
////// Part 1: Checking if the address is in the cache /////
// These functions perform a cache lookup to the associated cache levels. Return 0 if the address is not in the cache (cache miss) and 1 if the address is in the cache (cache hit)
int L1lookup(u_int32_t address);
int L2lookup(u_int32_t address);
// This function returns a setID given an address
unsigned int getL1SetID(u_int32_t address);
unsigned int getL2SetID(u_int32_t address);
// This function returns a tag given an address
unsigned int getL1Tag(u_int32_t address);
unsigned int getL2Tag(u_int32_t address);
////// Part 2: FIFO cache //////
// This function performs a read to a cache content. Return the 4-byte data content given by the address. Please note that the read access MUST evict existing cache block correctly based on the FIFO policy and insert the new cache block correctly into the cache.
u_int32_t read_fifo(u_int32_t address);
// EPart 3: handle write. Assuming a write-through cache. This is the only place you actually modify the data in the cache and DRAM
void write(u_int32_t address, u_int32_t data);
cacheSim.C
#include "cacheSim.h"
// In this question, we will assume DRAM will take a 4-byte values starting from 0 to
void init_DRAM()
{
unsigned int i=0;
DRAM = malloc(sizeof(char) * DRAM_SIZE);
for(i=0;i<DRAM_SIZE/4;i++)
{
*((unsigned int*)DRAM+i) = i;
}
}
void printCache()
{
int i,j,k;
printf("===== L1 Cache Content =====\n");
for(i=0;i<2;i++)
{
printf("Set %d :", i);
for(j=0;j<2;j++)
{
printf(" {(TAG: 0x%x)", (unsigned int)(L1_cache[i][j].tag));
for(k=0;k<16;k++)
printf(" 0x%x,", (unsigned int)(L1_cache[i][j].data[k]));
printf(" |");
}
printf("\n");
}
printf("===== L2 Cache Content =====\n");
for(i=0;i<4;i++)
{
printf("Set %d :", i);
for(j=0;j<4;j++)
{
printf(" {(TAG: 0x%x)", (unsigned int)(L2_cache[i][j].tag));
for(k=0;k<16;k++)
printf(" 0x%x,", (unsigned int)(L2_cache[i][j].data[k]));
printf(" |");
}
printf("\n");
}
}
u_int32_t read_fifo(u_int32_t address)
{
///// IMPLEMENT THIS /////
return 0;
}
int L1lookup(u_int32_t address)
{
///// IMPLEMENT THIS /////
return 0;
}
int L2lookup(u_int32_t address)
{
///// IMPLEMENT THIS /////
return 0;
}
unsigned int getL1SetID(u_int32_t address)
{
///// IMPLEMENT THIS /////
return 0;
}
unsigned int getL2SetID(u_int32_t address)
{
///// IMPLEMENT THIS /////
return 0;
}
unsigned int getL1Tag(u_int32_t address)
{
///// IMPLEMENT THIS /////
return 0;
}
unsigned int getL2Tag(u_int32_t address)
{
///// IMPLEMENT THIS /////
return 0;
}
void write(u_int32_t address, u_int32_t data)
{
///// REPLACE THIS /////
read_fifo(address);
return;
}
int main()
{
init_DRAM();
cacheAccess buffer;
int timeTaken=0;
FILE *trace = fopen("input.trace","r");
int L1hit = 0;
int L2hit = 0;
cycles = 0;
while(!feof(trace))
{
fscanf(trace,"%d %x %x", &buffer.readWrite, &buffer.address, &buffer.data);
printf("Processing the request for [R/W] = %d, Address = %x, data = %x\n", buffer.readWrite, buffer.address, buffer.data);
// Checking whether the current access is a hit or miss so that we can advance time correctly
if(L1lookup(buffer.address))// Cache hit
{
timeTaken = 1;
L1hit++;
}
else if(L2lookup(buffer.address))// L2 Cache Hit
{
L2hit++;
timeTaken = 5;
}
else timeTaken = 50;
if (buffer.readWrite) write(buffer.address, buffer.data);
else read_fifo(buffer.address);
cycles+=timeTaken;
}
printCache();
printf("Total cycles used = %ld\nL1 hits = %d, L2 hits = %d", cycles, L1hit, L2hit);
fclose(trace);
free(DRAM);
return 0;
}
// In this question, we will assume DRAM will take a 4-byte values starting from 0 to
void init_DRAM()
{
unsigned int i=0;
DRAM = malloc(sizeof(char) * DRAM_SIZE);
for(i=0;i<DRAM_SIZE/4;i++)
{
*((unsigned int*)DRAM+i) = i;
}
}
void printCache()
{
int i,j,k;
printf("===== L1 Cache Content =====\n");
for(i=0;i<2;i++)
{
printf("Set %d :", i);
for(j=0;j<2;j++)
{
printf(" {(TAG: 0x%x)", (unsigned int)(L1_cache[i][j].tag));
for(k=0;k<16;k++)
printf(" 0x%x,", (unsigned int)(L1_cache[i][j].data[k]));
printf(" |");
}
printf("\n");
}
printf("===== L2 Cache Content =====\n");
for(i=0;i<4;i++)
{
printf("Set %d :", i);
for(j=0;j<4;j++)
{
printf(" {(TAG: 0x%x)", (unsigned int)(L2_cache[i][j].tag));
for(k=0;k<16;k++)
printf(" 0x%x,", (unsigned int)(L2_cache[i][j].data[k]));
printf(" |");
}
printf("\n");
}
}
u_int32_t read_fifo(u_int32_t address)
{
///// IMPLEMENT THIS /////
return 0;
}
int L1lookup(u_int32_t address)
{
///// IMPLEMENT THIS /////
return 0;
}
int L2lookup(u_int32_t address)
{
///// IMPLEMENT THIS /////
return 0;
}
unsigned int getL1SetID(u_int32_t address)
{
///// IMPLEMENT THIS /////
return 0;
}
unsigned int getL2SetID(u_int32_t address)
{
///// IMPLEMENT THIS /////
return 0;
}
unsigned int getL1Tag(u_int32_t address)
{
///// IMPLEMENT THIS /////
return 0;
}
unsigned int getL2Tag(u_int32_t address)
{
///// IMPLEMENT THIS /////
return 0;
}
void write(u_int32_t address, u_int32_t data)
{
///// REPLACE THIS /////
read_fifo(address);
return;
}
int main()
{
init_DRAM();
cacheAccess buffer;
int timeTaken=0;
FILE *trace = fopen("input.trace","r");
int L1hit = 0;
int L2hit = 0;
cycles = 0;
while(!feof(trace))
{
fscanf(trace,"%d %x %x", &buffer.readWrite, &buffer.address, &buffer.data);
printf("Processing the request for [R/W] = %d, Address = %x, data = %x\n", buffer.readWrite, buffer.address, buffer.data);
// Checking whether the current access is a hit or miss so that we can advance time correctly
if(L1lookup(buffer.address))// Cache hit
{
timeTaken = 1;
L1hit++;
}
else if(L2lookup(buffer.address))// L2 Cache Hit
{
L2hit++;
timeTaken = 5;
}
else timeTaken = 50;
if (buffer.readWrite) write(buffer.address, buffer.data);
else read_fifo(buffer.address);
cycles+=timeTaken;
}
printCache();
printf("Total cycles used = %ld\nL1 hits = %d, L2 hits = %d", cycles, L1hit, L2hit);
fclose(trace);
free(DRAM);
return 0;
}
![1 CacheLab
The purpose of this assignment is to become more familiar with how cache works.
1.1 Handout Instructions
You will need a starter package, which ships in the form of a tar file. On syskill, you can find cacheLab-handout. ta
at
/handout/a5/cacheLab-handout.tar.gz
You can extract everything using the tar command in a similar fashion as assignment 3.
Once extracted, you will find three files: cacheSim.h, cacheSim.c and input.trace.
Inside cacheSim.c, we have provided the skeleton code for our simple cache, which has the following
properties:
• The cache has two levels
• A cache block is 16 bytes.
• Each address is accessing 1 bytes of data.
• The L1 cache is a 64 Bytes, 2-way set associative cache.
• The L2 cache is a 256 Bytes, 4-way set associative cache.
• The cache is inclusive, which mean that data in L1 cache will also remain in the L2 cache. In other
word, the data in L1 is a subset of the data in L2 (This assumption simplify your design).
• The cache is using a first-in-first-out cache replacement policy. Note that this is simpler to
implement than the LRU policy.
Your task is to build a cache simulator using the skeleton code we provided. To help you with the
task, we have provided you with the following functions
●
input. trace captures the trace of cache accesses. Each line in this file will contain three items:
[0/1] [address] [data], where 0/1 is a single number (0 means this is a read request and 1 means
this is a write request), [address] is a hexadecimal representation of the address of this particular
cache access, and [data] is either 0 or the actual data the cache access need to write to (Note
that a read request does not care about what the data is and you can ignore it. This piece of
information is specifically for the write request). Please note that you can also create your own
trace to test out your code. Testing your code is a part of this assignment, and I am going to test
your implementation using traces that I collect from real programs.
• The main () function is where the simulator handle reading the input trace. You do not need to
touch this except for the line that open the trace file (you should use your own trace file to test
your cache).
●
init_DRAM() initializes the value of DRAM. Please do not touch this.
●
• printCache() prints the content of the cache, which you can call at any time to test your code.
• readInput () reads one line of the input trace. This function is used in tandem with the main
function and you do not have to touch this.
2
1.2 Part 1: Getting Tags, SetID and Performing a Cache Lookup
For the first part, you are going to write six functions.
• unsigned int getL1SetID(uint32_t address) returns the setID assocated with the input
address for L1 cache.
• unsigned int getL1Tag(uint32_t address) returns the tag assocated with the input ad-
dress for L1 cache.
• unsigned int getL2SetID(uint32_t address) returns the setID assocated with the input
address for L2 cache.
• unsigned int getL2Tag(uint32_t address) returns the tag assocated with the input ad-
dress for L2 cache.
• int L1lookup(uint32_t address) performs a L1 cache lookup. This function returns 1 if the
input address is in the cache and 0 otherwise. Please note that this function DOES NOT perform
any actual insertion or eviction.
• int L2lookup (uint32_t address) performs a L2 cache lookup. This function returns 1 if the
input address is in the cache and 0 otherwise. Please note that this function DOES NOT perform
any actual insertion or eviction.
1.3 Part 2: A Simple FIFO-cache
For this part, you are going to implement the cache insertion and eviction based on a FIFO replacement
policy. The FIFO cache replacement policy choose to evict the cache block that was inserted first
(literally, first-in first-out). Please note that this policy is different and simpler (and likely to be worse)
than the LRU policy we covered in class.
You are going to write another three functions.
• uint32_t_read_fifo(uint32_t address) processes a read request by properly going though
the cache and updating the cache content based on the FIFO replacement policy. The function
should return the data you are reading.
Be careful: The input request can go to a 4-byte address that spans two cache blocks. Note that the
compiler will usually break this particular data access into two different requests, but we are simplifying
the cache here so we will assume that every request is for a 4-byte data and address can start at any byte.
1.4 Part 3: Handling Writes
After you correctly handle read requests (and assume that all write requests behave like a read request),
your next task is to handle write requests. For this assignment, we assume a write-through cache, which
performs a write to all cache levels (i.e., if there is a write to address addr, this new value should be
updated for all the cache levels as well as in the DRAM).
Specifically, you need to finish up the following function:
void write(uint32_t address, uint32_t data), which performs a write to address by up-
dating the byte at our address with data.
Hint 1: When you have a write hit, please carefully check which bytes in the cache block should be
updated.
Hint 2: You can reuse most of the cache eviction code from part 2 in order to both update the data
and insert/evict cache blocks at the same time.](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Ff97c0725-689e-40d7-87a0-46553d65cfc3%2F6fc74441-f5d8-49b0-9fe4-e501887a9668%2F64p6x44_processed.jpeg&w=3840&q=75)
Transcribed Image Text:1 CacheLab
The purpose of this assignment is to become more familiar with how cache works.
1.1 Handout Instructions
You will need a starter package, which ships in the form of a tar file. On syskill, you can find cacheLab-handout. ta
at
/handout/a5/cacheLab-handout.tar.gz
You can extract everything using the tar command in a similar fashion as assignment 3.
Once extracted, you will find three files: cacheSim.h, cacheSim.c and input.trace.
Inside cacheSim.c, we have provided the skeleton code for our simple cache, which has the following
properties:
• The cache has two levels
• A cache block is 16 bytes.
• Each address is accessing 1 bytes of data.
• The L1 cache is a 64 Bytes, 2-way set associative cache.
• The L2 cache is a 256 Bytes, 4-way set associative cache.
• The cache is inclusive, which mean that data in L1 cache will also remain in the L2 cache. In other
word, the data in L1 is a subset of the data in L2 (This assumption simplify your design).
• The cache is using a first-in-first-out cache replacement policy. Note that this is simpler to
implement than the LRU policy.
Your task is to build a cache simulator using the skeleton code we provided. To help you with the
task, we have provided you with the following functions
●
input. trace captures the trace of cache accesses. Each line in this file will contain three items:
[0/1] [address] [data], where 0/1 is a single number (0 means this is a read request and 1 means
this is a write request), [address] is a hexadecimal representation of the address of this particular
cache access, and [data] is either 0 or the actual data the cache access need to write to (Note
that a read request does not care about what the data is and you can ignore it. This piece of
information is specifically for the write request). Please note that you can also create your own
trace to test out your code. Testing your code is a part of this assignment, and I am going to test
your implementation using traces that I collect from real programs.
• The main () function is where the simulator handle reading the input trace. You do not need to
touch this except for the line that open the trace file (you should use your own trace file to test
your cache).
●
init_DRAM() initializes the value of DRAM. Please do not touch this.
●
• printCache() prints the content of the cache, which you can call at any time to test your code.
• readInput () reads one line of the input trace. This function is used in tandem with the main
function and you do not have to touch this.
2
1.2 Part 1: Getting Tags, SetID and Performing a Cache Lookup
For the first part, you are going to write six functions.
• unsigned int getL1SetID(uint32_t address) returns the setID assocated with the input
address for L1 cache.
• unsigned int getL1Tag(uint32_t address) returns the tag assocated with the input ad-
dress for L1 cache.
• unsigned int getL2SetID(uint32_t address) returns the setID assocated with the input
address for L2 cache.
• unsigned int getL2Tag(uint32_t address) returns the tag assocated with the input ad-
dress for L2 cache.
• int L1lookup(uint32_t address) performs a L1 cache lookup. This function returns 1 if the
input address is in the cache and 0 otherwise. Please note that this function DOES NOT perform
any actual insertion or eviction.
• int L2lookup (uint32_t address) performs a L2 cache lookup. This function returns 1 if the
input address is in the cache and 0 otherwise. Please note that this function DOES NOT perform
any actual insertion or eviction.
1.3 Part 2: A Simple FIFO-cache
For this part, you are going to implement the cache insertion and eviction based on a FIFO replacement
policy. The FIFO cache replacement policy choose to evict the cache block that was inserted first
(literally, first-in first-out). Please note that this policy is different and simpler (and likely to be worse)
than the LRU policy we covered in class.
You are going to write another three functions.
• uint32_t_read_fifo(uint32_t address) processes a read request by properly going though
the cache and updating the cache content based on the FIFO replacement policy. The function
should return the data you are reading.
Be careful: The input request can go to a 4-byte address that spans two cache blocks. Note that the
compiler will usually break this particular data access into two different requests, but we are simplifying
the cache here so we will assume that every request is for a 4-byte data and address can start at any byte.
1.4 Part 3: Handling Writes
After you correctly handle read requests (and assume that all write requests behave like a read request),
your next task is to handle write requests. For this assignment, we assume a write-through cache, which
performs a write to all cache levels (i.e., if there is a write to address addr, this new value should be
updated for all the cache levels as well as in the DRAM).
Specifically, you need to finish up the following function:
void write(uint32_t address, uint32_t data), which performs a write to address by up-
dating the byte at our address with data.
Hint 1: When you have a write hit, please carefully check which bytes in the cache block should be
updated.
Hint 2: You can reuse most of the cache eviction code from part 2 in order to both update the data
and insert/evict cache blocks at the same time.
Transcribed Image Text:input.trace
ไฟล์ แก้ไข มุมมอง
0 1300 1
0 1304 2
0 1308 3
0 130c 4
0 1310 5
0 1314 6
0 1318 7
0 131c 8
0 1320 9
1 130c 100
1 13F0 101
0 139c 199
0 13F0 101
0 139c 199
0 13F0 101
1 1dec 199
0 1eF8 181
1 1314 101
1 1dec 199
0 1eF8 181
X
+
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 3 steps
Follow-up Questions
Read through expert solutions to related follow-up questions below.
Follow-up Question
please give implementation of
unsigned int getL1SetID(u_int32_t address)
{
///// IMPLEMENT THIS /////
return 0;
}
unsigned int getL2SetID(u_int32_t address)
{
///// IMPLEMENT THIS /////
return 0;
}
unsigned int getL1Tag(u_int32_t address)
{
///// IMPLEMENT THIS /////
return 0;
}
unsigned int getL2Tag(u_int32_t address)
{
///// IMPLEMENT THIS /////
return 0;
}
Solution
by Bartleby ExpertFollow-up Question
please give implementation of
void write(u_int32_t address, u_int32_t data)
{
///// REPLACE THIS /////
read_fifo(address);
return;
}
Solution
by Bartleby ExpertKnowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.Recommended textbooks for you
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education