1#!/usr/bin/env python3
2#
3# Copyright (c) 2010-2024 Antmicro
4#
5# This file is licensed under the MIT License.
6# Full license text is available in 'licenses/MIT.txt'.
7#
8
9from cache import Cache
10from typing import Dict
11
12
13class TestLogInterface:
14    def __init__(self):
15        # Statistics
16        self.count_insn_read = 0
17        self.count_mem_read = 0
18        self.count_mem_write = 0
19        self.count_io_read = 0
20        self.count_io_write = 0
21
22    def configure_caches(self, cache: Cache) -> None:
23        self.cache = cache
24
25    def simulate(self, data: list[Dict[str, int]]):
26        for access in data:
27            for type, addr in access.items():
28                match type:
29                    case 'mw':
30                        self.count_mem_write += 1
31                        self.cache.write(addr)
32                    case 'mr':
33                        self.count_mem_read += 1
34                        self.cache.read(addr)
35                    case 'ior':
36                        self.count_io_write += 1
37                    case 'iow':
38                        self.cache.flush()
39                        self.count_io_read += 1
40                    case _:
41                        raise ValueError('Unsupported memory operation!')
42
43
44def tag_in_cache(cache: Cache, tag: int) -> bool:
45    return any(line.tag == tag for line in cache._lines)
46
47
48def test_fully_associative():
49    ''' Test scenario: fully associative cache
50
51    CPU Address space: 1024 bytes (1KiB)
52
53    cache:
54    * msize:  1024 bytes
55    * csize:  64 bytes
56    * bsize:  4 bytes
57    * clines: 16
58    * csets:  1 (16 lines per set)
59
60    Widths:
61    * tag: 8 bits
62    * set: 0 bits
63    * block: 2 bits
64    '''
65    cache = Cache(
66        name='fully_associative',
67        cache_width=6,
68        block_width=2,
69        memory_width=10,
70        lines_per_set=-1,
71        replacement_policy='FIFO',
72    )
73
74    test = TestLogInterface()
75    test.configure_caches(cache)
76
77    '''
78    Fill all cache lines (16 different tags)
79
80    Expected outcome:
81    * misses += 16
82    '''
83    test.simulate([
84        {'mr': 0b00000000_00},
85        {'mr': 0b00000001_00},
86        {'mr': 0b00000010_00},
87        {'mr': 0b00000011_00},
88        {'mr': 0b00000100_00},
89        {'mr': 0b00000101_00},
90        {'mr': 0b00000110_00},
91        {'mr': 0b00000111_00},
92        {'mr': 0b00001000_00},
93        {'mr': 0b00001001_00},
94        {'mr': 0b00001010_00},
95        {'mr': 0b00001011_00},
96        {'mr': 0b00001100_00},
97        {'mr': 0b00001101_00},
98        {'mr': 0b00001110_00},
99        {'mr': 0b00001111_00},
100    ]
101    )
102    assert test.cache.hits == 0
103    assert test.cache.misses == 16
104    assert test.cache.invalidations == 0
105
106    '''
107    Read memory from cached lines
108
109    Expected outcome:
110    * hits += 16
111    '''
112    test.simulate([
113        {'mr': 0b00000000_11},
114        {'mr': 0b00000001_11},
115        {'mr': 0b00000010_11},
116        {'mr': 0b00000011_11},
117        {'mr': 0b00000100_11},
118        {'mr': 0b00000101_11},
119        {'mr': 0b00000110_11},
120        {'mr': 0b00000111_11},
121        {'mr': 0b00001000_11},
122        {'mr': 0b00001001_11},
123        {'mr': 0b00001010_11},
124        {'mr': 0b00001011_11},
125        {'mr': 0b00001100_11},
126        {'mr': 0b00001101_11},
127        {'mr': 0b00001110_11},
128        {'mr': 0b00001111_11},
129    ]
130    )
131    assert test.cache.hits == 16
132    assert test.cache.misses == 16
133    assert test.cache.invalidations == 0
134
135    '''
136    Read memory from non-cached addresses
137
138    Expected outcome:
139    * misses += 16
140    * invalidations += 16
141    '''
142    test.simulate([
143        {'mr': 0b10000000_00},
144        {'mr': 0b10000001_00},
145        {'mr': 0b10000010_00},
146        {'mr': 0b10000011_00},
147        {'mr': 0b10000100_00},
148        {'mr': 0b10000101_00},
149        {'mr': 0b10000110_00},
150        {'mr': 0b10000111_00},
151        {'mr': 0b10001000_00},
152        {'mr': 0b10001001_00},
153        {'mr': 0b10001010_00},
154        {'mr': 0b10001011_00},
155        {'mr': 0b10001100_00},
156        {'mr': 0b10001101_00},
157        {'mr': 0b10001110_00},
158        {'mr': 0b10001111_00},
159    ]
160    )
161    assert test.cache.hits == 16
162    assert test.cache.misses == 32
163    assert test.cache.invalidations == 16
164
165    '''
166    IO writes should flush cache:
167
168    Expected outcome:
169    * hits += 2
170    * missess += 1
171    * invalidations should not change (flush != line eviction)
172    '''
173    test.simulate([
174        {'iow': 0b00000000_00},  # invalidate all cache
175        {'mr': 0b10000000_00},   # miss
176        {'mr': 0b10000000_00},   # hit
177        {'mr': 0b10000000_00},   # hit
178    ]
179    )
180    assert test.cache.hits == 18
181    assert test.cache.misses == 33
182    assert test.cache.invalidations == 16
183
184    '''
185    Writes to addresses with cache miss should load data into cache block.
186
187    Expected outcome:
188    * hits += 2
189    * missess += 1
190    '''
191    test.simulate([
192        {'mw': 0b01000000_00},  # miss
193        {'mr': 0b01000000_00},  # hit
194        {'mr': 0b01000000_00},  # hit
195    ]
196    )
197    assert test.cache.hits == 20
198    assert test.cache.misses == 34
199    assert test.cache.invalidations == 16
200
201    print('Fully associative cache test success!')
202
203
204def test_set_associative():
205    ''' Test scenario: set associative cache
206
207    CPU Address space: 1024 bytes (1KiB)
208
209    cache:
210    * msize:  1024 bytes
211    * csize:  64 bytes
212    * bsize:  4 bytes
213    * clines: 16
214    * csets:  4 (4 lines per set)
215
216    Widths:
217    * tag: 8 bits
218    * set: 2 bits
219    * block: 2 bits
220    '''
221    cache = Cache(
222        name='set_associative',
223        cache_width=6,
224        block_width=2,
225        memory_width=10,
226        lines_per_set=4,
227        replacement_policy='FIFO',
228    )
229
230    test = TestLogInterface()
231    test.configure_caches(cache)
232
233    '''
234    Load one cache line into each set
235
236    Expected outcome:
237    * misses += 4
238    '''
239    test.simulate([
240        {'mr': 0b000000_00_00},  # Set 0
241        {'mr': 0b000000_01_00},  # Set 1
242        {'mr': 0b000000_10_00},  # Set 2
243        {'mr': 0b000000_11_00},  # Set 3
244    ])
245    assert test.cache.hits == 0
246    assert test.cache.misses == 4
247    assert test.cache.invalidations == 0
248
249    '''
250    Try to load data blocks from loaded cache lines
251
252    Expected outcome:
253    * hits += 4
254    '''
255    test.simulate([
256        {'mr': 0b000000_00_11},  # Set 0
257        {'mr': 0b000000_01_11},  # Set 1
258        {'mr': 0b000000_10_11},  # Set 2
259        {'mr': 0b000000_11_11},  # Set 3
260    ])
261    assert test.cache.hits == 4
262    assert test.cache.misses == 4
263    assert test.cache.invalidations == 0
264
265    '''
266    Try to access data from aliased cache lines
267
268    Expected outcome:
269    * misses += 4
270    * invalidations += 1
271    '''
272    test.simulate([
273        {'mr': 0b000001_00_00},  # Set 0 (alias 1)
274        {'mr': 0b000010_00_00},  # Set 0 (alias 2)
275        {'mr': 0b000011_00_00},  # Set 0 (alias 3)
276        {'mr': 0b000100_00_00},  # Set 0 (alias 4)
277    ])
278    assert test.cache.hits == 4
279    assert test.cache.misses == 8
280    assert test.cache.invalidations == 1
281
282    print('Set associative cache test success!')
283
284
285def test_direct_mapped():
286    ''' Test scenario: direct mapped cache
287
288    CPU Address space: 1024 bytes (1KiB)
289
290    cache:
291    * msize:  1024 bytes
292    * csize:  64 bytes
293    * bsize:  4 bytes
294    * clines: 16
295    * csets:  16 (1 line per set)
296
297    Widths:
298    * tag: 6 bits
299    * set: 4 bits
300    * block: 2 bits
301    '''
302    cache = Cache(
303        name='direct_mapped',
304        cache_width=6,
305        block_width=2,
306        memory_width=10,
307        lines_per_set=1,
308    )
309
310    test = TestLogInterface()
311    test.configure_caches(cache)
312
313    '''
314    Fill each cache line uniquely
315
316    Expected outcome:
317    * misses += 16
318    '''
319    test.simulate([
320        {'mr': 0b0000_0000_00},
321        {'mr': 0b0000_0001_00},
322        {'mr': 0b0000_0010_00},
323        {'mr': 0b0000_0011_00},
324        {'mr': 0b0000_0100_00},
325        {'mr': 0b0000_0101_00},
326        {'mr': 0b0000_0110_00},
327        {'mr': 0b0000_0111_00},
328        {'mr': 0b0000_1000_00},
329        {'mr': 0b0000_1001_00},
330        {'mr': 0b0000_1010_00},
331        {'mr': 0b0000_1011_00},
332        {'mr': 0b0000_1100_00},
333        {'mr': 0b0000_1101_00},
334        {'mr': 0b0000_1110_00},
335        {'mr': 0b0000_1111_00},
336    ])
337    assert test.cache.hits == 0
338    assert test.cache.misses == 16
339    assert test.cache.invalidations == 0
340
341    '''
342    Re-access each address to verify direct mapping
343
344    Expected outcome:
345    * hits += 16
346    '''
347    test.simulate([
348        {'mr': 0b0000_0000_11},
349        {'mr': 0b0000_0001_11},
350        {'mr': 0b0000_0010_11},
351        {'mr': 0b0000_0011_11},
352        {'mr': 0b0000_0100_11},
353        {'mr': 0b0000_0101_11},
354        {'mr': 0b0000_0110_11},
355        {'mr': 0b0000_0111_11},
356        {'mr': 0b0000_1000_11},
357        {'mr': 0b0000_1001_11},
358        {'mr': 0b0000_1010_11},
359        {'mr': 0b0000_1011_11},
360        {'mr': 0b0000_1100_11},
361        {'mr': 0b0000_1101_11},
362        {'mr': 0b0000_1110_11},
363        {'mr': 0b0000_1111_11},
364    ])
365    assert test.cache.hits == 16
366    assert test.cache.misses == 16
367    assert test.cache.invalidations == 0
368
369    '''
370    Access every alias - trash cache
371
372    Expected outcome:
373    * invalidations += 16
374    * missess += 16
375    '''
376    test.simulate([
377        {'mr': 0b0001_0000_11},
378        {'mr': 0b0001_0001_11},
379        {'mr': 0b0001_0010_11},
380        {'mr': 0b0001_0011_11},
381        {'mr': 0b0001_0100_11},
382        {'mr': 0b0001_0101_11},
383        {'mr': 0b0001_0110_11},
384        {'mr': 0b0001_0111_11},
385        {'mr': 0b0001_1000_11},
386        {'mr': 0b0001_1001_11},
387        {'mr': 0b0001_1010_11},
388        {'mr': 0b0001_1011_11},
389        {'mr': 0b0001_1100_11},
390        {'mr': 0b0001_1101_11},
391        {'mr': 0b0001_1110_11},
392        {'mr': 0b0001_1111_11},
393    ])
394    assert test.cache.hits == 16
395    assert test.cache.misses == 32
396    assert test.cache.invalidations == 16
397
398    print('Direct mapped cache test success!')
399
400
401def test_fifo_cache():
402    ''' Test scenario: FIFO cache replacement policy '''
403    cache = Cache(
404        name='fifo_cache',
405        cache_width=4,
406        block_width=2,
407        memory_width=10,
408        lines_per_set=4,
409        replacement_policy='FIFO',
410    )
411
412    test = TestLogInterface()
413    test.configure_caches(cache)
414
415    # Fill all cache lines
416    test.simulate([
417        {'mr': 0b00000000_00},  # tag 00
418        {'mr': 0b00000001_00},  # tag 01
419        {'mr': 0b00000010_00},  # tag 10
420        {'mr': 0b00000011_00},  # tag 11
421    ])
422    for tag in [0b00, 0b01, 0b10, 0b11]:
423        assert tag_in_cache(test.cache, tag)
424        assert tag_in_cache(test.cache, tag)
425        assert tag_in_cache(test.cache, tag)
426        assert tag_in_cache(test.cache, tag)
427
428    # Access to force FIFO replacement
429    test.simulate([
430        {'mr': 0b00000100_00},  # FIFO replace tag 00 with tag 100
431        {'mr': 0b00000101_00},  # FIFO replace tag 01 with tag 101
432    ])
433    for tag in [0b100, 0b101, 0b10, 0b11]:
434        assert tag_in_cache(test.cache, tag)
435        assert tag_in_cache(test.cache, tag)
436        assert tag_in_cache(test.cache, tag)
437        assert tag_in_cache(test.cache, tag)
438
439    print('FIFO cache test success!')
440
441
442def test_lfu_cache():
443    ''' Test scenario: LFU cache replacement policy '''
444    cache = Cache(
445        name='lfu_cache',
446        cache_width=4,
447        block_width=2,
448        memory_width=10,
449        lines_per_set=4,
450        replacement_policy='LFU',
451    )
452
453    test = TestLogInterface()
454    test.configure_caches(cache)
455
456    # Fill all cache lines
457    test.simulate([
458        {'mr': 0b00000000_00},  # tag 00
459        {'mr': 0b00000001_00},  # tag 01
460        {'mr': 0b00000010_00},  # tag 10
461        {'mr': 0b00000011_00},  # tag 11
462    ])
463    for tag in [0b00, 0b01, 0b10, 0b11]:
464        assert tag_in_cache(test.cache, tag)
465        assert tag_in_cache(test.cache, tag)
466        assert tag_in_cache(test.cache, tag)
467        assert tag_in_cache(test.cache, tag)
468
469    # Increment usage counters
470    test.simulate([
471        {'mr': 0b00000001_00},  # access tag 01 (2 times)
472        {'mr': 0b00000001_00},
473
474        {'mr': 0b00000000_00},  # access tag 00 (3 times)
475        {'mr': 0b00000000_00},
476        {'mr': 0b00000000_00},
477
478        {'mr': 0b00000011_00},  # access tag 11 (1 time)
479
480        {'mr': 0b00000010_00},  # access tag 10 (4 times)
481        {'mr': 0b00000010_00},
482        {'mr': 0b00000010_00},
483        {'mr': 0b00000010_00},
484    ])
485
486    # Load a new line into the cache. Tag 11 has the lowest usage
487    # count, and will be replaced with the tag 100
488    test.simulate([
489        {'mr': 0b00000100_00},  # LFU replace tag 11 with tag 100
490    ])
491    for tag in [0b00, 0b01, 0b10, 0b100]:
492        assert tag_in_cache(test.cache, tag)
493        assert tag_in_cache(test.cache, tag)
494        assert tag_in_cache(test.cache, tag)
495        assert tag_in_cache(test.cache, tag)
496
497    print('LFU cache test success!')
498
499
500def test_lru_cache():
501    ''' Test scenario: LRU cache replacement policy '''
502    cache = Cache(
503        name='lru_cache',
504        cache_width=4,
505        block_width=2,
506        memory_width=10,
507        lines_per_set=4,
508        replacement_policy='LRU',
509    )
510
511    test = TestLogInterface()
512    test.configure_caches(cache)
513
514    # Fill all cache lines
515    test.simulate([
516        {'mr': 0b00000000_00},  # tag 00
517        {'mr': 0b00000001_00},  # tag 01
518        {'mr': 0b00000010_00},  # tag 10
519        {'mr': 0b00000011_00},  # tag 11
520    ])
521    for tag in [0b00, 0b01, 0b10, 0b11]:
522        assert tag_in_cache(test.cache, tag)
523        assert tag_in_cache(test.cache, tag)
524        assert tag_in_cache(test.cache, tag)
525        assert tag_in_cache(test.cache, tag)
526
527    # Simulate accessess to update last access time
528    test.simulate([
529        {'mr': 0b00000001_00},  # access tag 01
530        {'mr': 0b00000000_00},  # access tag 00
531        {'mr': 0b00000011_00},  # access tag 11
532        {'mr': 0b00000010_00},  # access tag 10
533    ])
534
535    # Load a new line into the cache. Tag 01 has is
536    # least recently used, and will be replaced with the tag 100
537    test.simulate([
538        {'mr': 0b00000100_00},  # LFU replace tag 01 with tag 100
539    ])
540    for tag in [0b00, 0b10, 0b11, 0b100]:
541        assert tag_in_cache(test.cache, tag)
542        assert tag_in_cache(test.cache, tag)
543        assert tag_in_cache(test.cache, tag)
544        assert tag_in_cache(test.cache, tag)
545
546    print('LRU cache test success!')
547
548
549if __name__ == '__main__':
550    test_fully_associative()
551    test_set_associative()
552    test_direct_mapped()
553
554    test_fifo_cache()
555    test_lfu_cache()
556    test_lru_cache()
557