Comp 222 Computer Organization

Assignment 2: Cache

Dr. George Lazik

Page 1 of 9

Revision B: 10/14/18

Programming Assignment 2

Cache Memory

Objective:

To write a C program that simulates reading and writing to a custom-sized

direct-mapped

cache

, involving a custom-sized main memory.

The program will read ALL VALUES from a file named prg2_data.txt which should be

located in the same directory as your program.

Main Menu Options:

The program simulates reading from and writing to a cache based on choosing from a menu

of choices, where each choice calls the appropriate procedure, where the choices are:

Your Full Name

(each time, this must appear above the menu)

1) Enter Configuration Parameters

2) Read from Cache

3) Write to Cache

4) Quit Program

Note that when you read from a text file, the input values may not be displayed on the

screen as they are in the sample run at the end of this document.

Inputs:

Enter Parameters

o

The total size of accessible main memory (in words)

o

The total size of the cache (in words)

o

The block size (words/block)

Read from Cache

o

The main memory address to read from

Write to Cache

o

The contents of the address for writing to the cache

Comp 222 Computer Organization

Assignment 2: Cache

Dr. George Lazik

Page 2 of 9

Revision B: 10/14/18

Input Value Checks:

All of the above values must be powers of 2.

The block size must never be larger than the size of accessible main memory.

The total cache size must be some multiple of the block size.

Your program should verify that all input variables are within limits as they are entered.

PROLOGUE MESSAGE

When the program begins execution, the first lines it should display on the STDOUT comprise a

prologue:

*** Program Written by George Lazik

*** Prog 2 Cache Simulation

*** Class Meeting Time: 8:00 9:15

*** Comp 222 Fall 2018

Then the program begins reading values from the data file, starting by looking for Option 1, Enter

Parameters.

Output Messages:

All required messages are shown below in the sample run. Each has a blank horizontal

line between the messages. Some messages consist of two lines.

o

Data Accepted Message

is comprised of two lines:

All Input Parameters Accepted. Starting to Process Write/Read

Requests

o

Error Messages

(two possible messages)

Cache Size is not a Power of 2! Returning to Main Menu

Block Size is Larger than Cache Size! Returning to Main Menu

Whenever one of these errors occurs, the program should loop back to the Main Menu

to read all the input parameters again.

The following are the other expected output messages.

o

Content Message

resulting from reading/writing to the cache

Word WW of Cache Line LL with Tag TT contains Value VV

This message should appear after all successful reads or writes

o

Read Messages

(two possible messages)

Read Miss... Load Block from Memory!

followed

by the Content

Message

Cache Hit

followed

by the Content Message

Comp 222 Computer Organization

Assignment 2: Cache

Dr. George Lazik

Page 3 of 9

Revision B: 10/14/18

o

Write Messages

Write Miss... First Load Block from Memory!

followed

by the Content

Message

Cache Hit

followed

by the Content Message

o

Quit Program Message

o

When option 4 is entered, the memory should be freed up and the message

Memory Freed Up Program Terminated Normally

, followed by a blank

line, should be displayed before exiting the program.

All messages should be display

EXACTLY

as shown below in the sample run in

bold; that is, prefixed by two asterisks and a space and followed by a blank new

line after the text of the message

.

Program Requirements:

Use the

FILE

type declaration and

fscanf( )

function to read all input from a file named

prg2_data.txt.

Use a

structure

(struct) to represent a cache line consisting of a tag (integer) and a

block (integer pointer). Define the cache to be a

pointer

to the struct.

Upon entering the parameters, the main memory and cache are to be

dynamically

allocated

(use

malloc

) based on their respective total sizes.

Each word

i

of main memory is initialized with the value

M

i

, where

M

is

the size of main memory in words. So memory location 0 will contain the

address of the last memory location and the last memory location will

contain the address of the first memory location (i.e. 0).

Reading/writing from/to a new block in the cache results in dynamically allocating the

block based on the block size.

Prologue & comments:

At the very beginning of your source code (the very first lines), please include a prologue

which looks like the following:

/*

Dr. George Lazik

(use your full name not mine)

Programming Assignment 2: Cache Simulation

Comp 222 Fall 2018

Meeting Time: 0800-0915

(your meeting time)

*/

Comp 222 Computer Organization

Assignment 2: Cache

Dr. George Lazik

Page 4 of 9

Revision B: 10/14/18

Include simple (

brief

) comments strategically placed throughout your program so that

someone else can readily follow what you are doing, but dont overdo it. Examples

might look like these:

// Reading input values from the data file

// Determining the contents of memory

What to turn in:

Softcopy

of

source code

submitted to the Assignment on Canvas. Be sure to name

your source code:

prg2.c

. When your submission is downloaded from Canvas,

your full name and other information is automatically appended to it so I know

which is your program.

You can use any editor and/or compiler of your choice, but

make sure

your code

compiles error free (

NO WARNINGS OR OTHER MESSAGES

) with the

gcc

compiler and runs under the Linux environment on

k200.ecs.csun.edu

; otherwise

you may receive 0 points for compilation errors and execution failures.

In particular, look out for the C99 error message related to declaring the

iteration variable inside the FOR statement.

Hardcopy

printed listing of your program. Please place this on the Professors

desk at the beginning of class on day the assignment is due.

Make sure your full name appears on each page of the listing and that all pages are

stapled together in their correct order

BEFORE

you come to class.

Test Data File:

A test data file is included with this assignments material on Canvas. It was created with

Notepad. You should test your program, using it, to ensure that it is operating properly.

Once you are satisfied it is working as expected, it is recommended you make up your own

test file (give it the same name as the one provided) to make sure your program handles

other kinds of simple input errors.

Comp 222 Computer Organization

Assignment 2: Cache

Dr. George Lazik

Page 5 of 9

Revision B: 10/14/18

Sample Run Using Input from a File

-ksh-4.1$ ./ prg2

Program Written by George Lazik

Programming Assignment 2: Cache Simulation

Comp 222 Fall 2018

Class Meeting Time: 8:00 9:15

Main Menu - Main Memory to Cache Memory Mapping

--------------------------------------

1 Enter Configuration Parameters

2 Read from cache

3 Write to cache

4 Exit

*** Starting to Read Data from the input file: prg2_data.txt

__________________________________________________________________________

*** Error - Cache Size is not a Power of 2! Returning to Main Menu

__________________________________________________________________________

*** Error - Block Size is Larger than Cache Size! Returning to Main Menu

__________________________________________________________________________

*** All Input Parameters Accepted. Starting to Process Write/Read Requests

__________________________________________________________________________

*** Write Miss... First load Block from Memory!

*** Word 15 of Cache Line 63 with Tag 63 contains Value 14

__________________________________________________________________________

*** Cache Hit

*** Word 15 of Cache Line 63 with Tag 63 contains Value 14

__________________________________________________________________________

*** Cache Hit

*** Word 14 of Cache Line 63 with Tag 63 contains Value 512

__________________________________________________________________________

*** Read Miss... Load Block from Memory!

*** Word 15 of Cache Line 63 with Tag 0 contains Value 64513

__________________________________________________________________________

*** Memory Freed Up - Program Terminated Normally

-ksh-4.1$

Comp 222 Computer Organization

Assignment 2: Cache

Dr. George Lazik

Page 6 of 9

Revision B: 10/14/18

Sample Test Run Using Manual Inputs

The sample below was run by manually typing in values.

Some students might also prefer to first test their program by manually by

entering data from the keyboard. In this case, comment out those lines in your

program that deal with files and use scanf() instead of fscanf() to manually type in

values. When you are satisfied the program is running correctly, remove the

comment lines and use fscanf().

Note that the menu is being displayed each time in this sample run, but in the

actual run, it may not get displayed because the values are eventually being read

from a data file. Whether or not they are displayed depends in part on how your

program is written. In other cases, the messages will be streamed, one after the

other.

-ksh-4.1$ ./prg2

Program Written by George Lazik

Programming Assignment 2: Cache Simulation

Comp 222 Fall 2018

Class Meeting Time: 8:00 9:15

Dr. George Lazik

Main memory to Cache memory mapping:

--------------------------------------

1) Enter Configuration Parameters

2) Read from cache

3) Write to cache

4) Exit

Enter selection: 1

Enter main memory size (words): 65536

Enter cache size (words): 1027

Enter block size (words/block): 16

*** Error Cache size is not a power of 2

Comp 222 Computer Organization

Assignment 2: Cache

Dr. George Lazik

Page 7 of 9

Revision B: 10/14/18

Dr. George Lazik

Main memory to Cache memory mapping:

--------------------------------------

1) Enter configuration parameters

2) Read from cache

3) Write to cache

4) Exit

Enter selection: 1

Enter main memory size (words): 65536

Enter cache size (words): 1024

Enter block size (words/block): 4096

*** Error Block size is larger than cache size

Dr. George Lazik

Main memory to Cache memory mapping:

--------------------------------------

1) Enter configuration parameters

2) Read from cache

3) Write to cache

4) Exit

Enter selection: 1

Enter main memory size (words): 65536

Enter cache size (words): 1024

Enter block size (words/block): 16

*** Data Accepted

Dr. George Lazik

Main memory to Cache memory mapping:

--------------------------------------

1) Enter configuration parameters

2) Read from cache

3) Write to cache

4) Exit

Comp 222 Computer Organization

Assignment 2: Cache

Dr. George Lazik

Page 8 of 9

Revision B: 10/14/18

Enter selection: 3

Enter main memory address to write to: 65535

Enter value to write: 14

*** Write Miss - First load block from memory

*** Word 15 of cache line 63 with tag 63 contains the value 14

Dr. George Lazik

Main memory to Cache memory mapping:

--------------------------------------

1) Enter configuration parameters

2) Read from cache

3) Write to cache

4) Exit

Enter selection: 2

Enter main memory address to read from: 65535

*** Cache Hit

*** Word 15 of cache line 63 with tag 63 contains the value 14

Dr. George Lazik

Main memory to Cache memory mapping:

--------------------------------------

1) Enter configuration parameters

2) Read from cache

3) Write to cache

4) Exit

Enter selection: 3

Enter main memory address to write to: 65534

Enter value to write: 512

*** Cache Hit

*** Word 14 of cache line 63 with tag 63 contains the value 512

Comp 222 Computer Organization

Assignment 2: Cache

Dr. George Lazik

Page 9 of 9

Revision B: 10/14/18

Dr. George Lazik

Main memory to Cache memory mapping:

--------------------------------------

1) Enter configuration parameters

2) Read from cache

3) Write to cache

4) Exit

Enter selection: 2

Enter main memory address to read from: 1023

*** Read Miss - First load block from memory

*** Word 15 of cache line 63 with tag 0 contains the value 64513

Dr. George Lazik

Main memory to Cache memory mapping:

--------------------------------------

1) Enter configuration parameters

2) Read from cache

3) Write to cache

4) Exit

Enter selection: 4

***

Memory Freed Up Program Terminated Normally

-ksh-4.1$