代做CS 230 Winter 2024 Assignment 6代做回归

CS 230 Winter 2024

Assignment 6

Coverage: Caching, Finite Automata and Regular Expressions, Grammars and Parsing

Due Date: Friday, April 5, 11:59 p.m. 

• All submissions are to be completed through MarkUs (https://markus.student.cs.uwaterloo.ca/markus_cs230_w/en/assignments)

• Read the policy described in Learn regarding late submissions.

Check MarkUs to see how many 12-hour grace periods you have remaining.

• Double check your submissions in MarkUs after you have uploaded them. It is your responsibility to ensure that the uploaded version is readable in MarkUs.

• Solutions for assignments will not be posted.

• Question 3 will have approximately 4/3 the weight of Question 2.

Questions 1 and 2 are approximately equally weighted.

1. Assume a memory model with the following specification:

• memory is byte addressable

• there is a single level, 4-block cache

• the cache block size is 16 bytes

• the range of memory addresses in main memory is 0 through 255 inclusive

• the processor has a clock speed of 4 GHz

For each of the following parts, assume the cache is empty to begin, and you have the following sequence of memory accesses:

152, 37, 190, 42, 210, 152, 16, 30, 191, 48, 31, 32, 152, 29

(a) What addresses would be in the same block as address 210 in main memory?

(b) Assume that the processor uses a direct-mapped cache. For each of the memory accesses, indicate if it would result in a cache hit or a cache miss when the program is executed. Justify your answers by creating a table that includes the following headings:

Address

Block ID

Cache Index

Tag

Hit/Miss

The Block ID, Cache Index, and Tag should all be bit sequences.

The Address should be the number from the original sequence of memory accesses.

(c) Draw a cache diagram, with the same format as Slide 71 of Module 3, indicating which block of main memory has been loaded into each block of the cache after all the above memory access are complete. The Data column should have the Block ID for the Mem[ ] values. You can use the work you have done in the previous part as justification for your answer.

(d) Assume that the processor uses a 2-way set associative cache with a LRU eviction strategy.

i. Identify the first address access that would be a miss in the direct-mapped cache and a hit in the set associative cache.

ii. Identify the first address access that would be a hit in the direct mapped cache but a miss in the set associative cache.

Briefly justify your answers.

(e) Assume that the processor uses a fully associative cache with a LRU eviction strategy. How many fewer evictions would take place with a fully associative cache compared to the direct-mapped cache? Justify your answer by identifying the memory accesses that cause evictions in each case.

(f) Assume that the hit time for a cache hit is 1 cycle, and the penalty for a cache miss is 20 cycles. Calculate the Average Memory Access Time (AMAT) for the the direct-mapped cache. Show your work.

Submit the file a6q1.pdf.

2. (a) Using only the symbols described in the lecture slides, write a regular expression that describes all strings over the alphabet Σ = {0, 1} that are at are at least five bits long and begin and end with the same two bit pattern.

For example, these strings would be accepted: 11011, 0111101, 100110, and these strings would be rejected: 0101, 10001

(b) Draw a DFA, that accepts strings strings over the alphabet Σ = {0, 1} such that if you read the string from left to right, the difference between the number of 0s and 1s read up to any point in the string is never more than 2. For example, 10100111 and the ε (the empty string) would be accepted. However, 111000 would be rejected because it starts with 3 occurrences of a 1 before seeing a 0, and 01001101001001 would be rejected because when reading the last 0 in the string, that is the 8^th occurrence of a 0 and only the 5^th occurrence of a 1 at that point. The difference in this case is 3.

Your solution must read all bits from the string. In other words, each state in the DFA must have a transition labelled with a 0 and a transition labelled with a 1. The DFA may not have any more than 10 states, although it may have fewer than 10 states.

(c) Draw a finite state machine, either a DFA or an NFA, over the alphabet Σ = {a, b, c, d} that matches this regular expression:

a? b? c+ ( a* | b* ) d ( b | c )*

Note that there are no spaces in this alphabet. The spaces are included in the regular expression for readability. Also, you are not required to read a whole string that would be rejected. In other words, a correct solution may contain states that do not have transitions for all possible inputs.

Submit the file a6q2.pdf.

3. Consider the following grammar representing simplified Racket expressions. The non-terminal <expr> is the start symbol for the grammar.

 

<expr>	→	<atom> | <list>
<atom>	→	number | symbol
<list>	→	’( <expr-seq> )
<expr-seq> Notes:	→	<expr-seq> <expr> | <expr>

• The two characters ’( should be considered a single terminal value

• A number is defined by the regular expression: [0-9]

• A symbol is defined by the regular expression: [a-z]

• Ignore any spaces in the expressions

(a) Write a leftmost derivation of the expression: ’( x ’( y 5 ’( z 6 )) ’( w )) The derivation should start with the start symbol of the language and end with terminals identified in the language specification.

(b) Draw a parse tree for the expression: ’( ’( a ’( y ) z ) ’( c 1 ) )

Notes:

• All internal nodes should be non-terminal values.

• The leaf nodes of the tree should be characters that appear in the original expression.

Submit the file a6q3.pdf.