Questions tagged [cpu-cache]

A fast memory limited in space close to the CPU. A cache is designed to reduce the average time to access memory.

Filter by
Sorted by
Tagged with
63 votes
2 answers
27k views

What happens to the cache contents on a context switch?

In a multicore processor, what happens to the contents of a core's cache (say L1) when a context switch occurs on that cache? Is the behaviour dependent on the architecture or is it a general ...
user avatar
  • 1,287
38 votes
2 answers
2k views

Are generational garbage collectors inherently cache-friendly?

A typical generational garbage collector keeps recently allocated data in a separate memory region. In typical programs, a lot of data is short-lived, so collecting young garbage (a minor GC cycle) ...
user avatar
28 votes
3 answers
7k views

What does the processor do while waiting for a main memory fetch

Assuming l1 and l2 cache requests result in a miss, does the processor stall until main memory has been accessed? I heard about the idea of switching to another thread, if so what is used to wake up ...
user avatar
24 votes
5 answers
303k views

How to calculate the number of tag, index and offset bits of different caches?

Specifically: 1) A direct-mapped cache with 4096 blocks/lines in which each block has 8 32-bit words. How many bits are needed for the tag and index fields, assuming a 32-bit address? 2) Same ...
user avatar
  • 403
18 votes
3 answers
695 views

Parallelising random reads seems to work well — why?

Consider the following very simple computer program: for i = 1 to n: y[i] = x[p[i]] Here $x$ and $y$ are $n$-element arrays of bytes, and $p$ is an $n$-...
user avatar
18 votes
1 answer
18k views

Memory Consistency vs Cache Coherence

Is it true that Sequential Consistency is a stronger property than Cache Coherence? According to Sorin, Daniel J; Hill, Mark D; Wood, David A: A Primer on Memory Consistency and Cache Coherence, ...
user avatar
  • 1,016
15 votes
1 answer
21k views

How does a TLB and data cache work?

I'm trying to study for an exam and I realized I'm confused about how the TLB and data cache work. I understand that the TLB is essentially a cache of most recently used physical addresses. However, ...
user avatar
14 votes
1 answer
395 views

Research on evaluating the performance of cache-obliviousness in practice

Cache-oblivious algorithms and data structures are a rather new thing, introduced by Frigo et al. in Cache-oblivious algorithms, 1999. Prokop's thesis from the same year introduces the early ideas as ...
user avatar
  • 22.1k
10 votes
3 answers
3k views

CPU Cache is managed by which software component?

CPU caches are used by exploiting temporal and spatial locality. My question is who is responsible for managing these caches? Is this Operating system that identifies a particular access pattern and ...
user avatar
  • 1,719
10 votes
2 answers
54k views

Cache Direct Map (Index, tag, hit/miss)

Alright, I thought I understood this concept but now I am confused. I looked up similar problems and their solutions to practice, and that's what threw me off. The question is a homework problem which ...
user avatar
  • 273
9 votes
1 answer
2k views

Why is quiescent consistency compositional, but sequential consistency is not

I'm having trouble in comparing these two memory consistency models. Essentially for sequential consistency I think of real code like this: ...
user avatar
  • 193
9 votes
2 answers
7k views

Does the aliasing problem show up in a virtually indexed physically tagged cache?

Basically, and as a simple method, we can access cache with Physical Address which is from the TLB. But, as another method, we can access cache with Virtual Address. But, in this case, if the cache ...
user avatar
  • 235
7 votes
1 answer
22k views

Tag, index and offset of associative cache

My main issue of a homework problem is trying to figure out the different parts of the chart. I have a 3 way set associative cache with 2 word blocks, total size of 24 words. I am given $3, 180, 43, 2,...
user avatar
  • 273
7 votes
3 answers
2k views

Write Serialization for Cache Coherence in the presence of Store Buffers

One of the requirements for a coherent memory system is write serialization - "two writes to address X by any two processors are observed in the same order by all processors". I am not sure how this ...
user avatar
  • 71
6 votes
3 answers
5k views

Finding cache block transfer time in a 3 level memory system

Following question was asked in one of entrance exams for a graduation programme. Please help me try to solve it : A computer system has an L1 cache, an L2 cache, and a main memory unity connected as ...
user avatar
  • 1,443
6 votes
1 answer
532 views

Why can L3 caches hold only shared blocks?

In a recent CACM article [1], the authors present a way to improve scalability of shared and coherent caches. The core ingredient is assuming the caches are inclusive, that is higher-level caches (e....
user avatar
  • 70.9k
6 votes
1 answer
136 views

How does cache partitioning prevent covert/side-channel attacks?

In a report on an open-source separation kernel (Muen kernel) I was reading, in the future work section, it says that cache coloring can be implemented to prevent covert/side-channel attacks. It is ...
user avatar
  • 163
6 votes
1 answer
132 views

How to compute $\mathbf{X}^T \mathbf{X}$ efficiently for large $\mathbf{X}$?

Let $\mathbf{X}$ be a $n \times n$ matrix. Given that we can only keep $k$ rows ($k << n$) or columns of the matrix in memory, how can we compute $\mathbf{X}^T \mathbf{X}$ while minimizing the ...
user avatar
5 votes
3 answers
981 views

Depth first or breadth first ordering in binary search trees?

Let's say that I make a binary search tree and store it in an array so that I end up with an array that is more cache friendly to binary search compared to a sorted array. The binary tree is full on ...
user avatar
  • 1,320
5 votes
1 answer
826 views

Are cache contents specific to a process? [duplicate]

Suppose the L1 cache is filled up with data from some process. Now CPU loads another process. Does the new process share cache contents? Or the cache has to be invalidated completely in each context ...
user avatar
5 votes
3 answers
2k views

Why we need to read memory on a write-miss?

I noticed that in write-back caches, when the cpu wants to write to a block, it fetches the block from memory and then updates it. If the block is going to be overwritten and changed by processor, why ...
user avatar
  • 181
5 votes
1 answer
3k views

Direct mapping cache with LRU

I'm studying computer architecture and I'm doing an experiment. Does LRU make sense in a direct mapping cache? I'm quite confused. Thank you.
user avatar
  • 51
4 votes
1 answer
4k views

How does the OS know the physical address of a process' first memory page?

If I have a program, its instructions are stored on the hard drive. When I double-click the executable the pages of memory for this process must get loaded in to RAM. However, for the pages to get ...
user avatar
4 votes
1 answer
940 views

L1 and Ln cache: when are they written?

I have been following the "High Performance Computer Architecture" course from Georgia Tech (also on YouTube), and unless I've missed something, I cannot see where the following has been explained: ...
user avatar
  • 143
4 votes
2 answers
17k views

Cache effective access time calculation

In order to calculate the effective access time of a memory sub-system, I see some different approaches, a.k.a formulas. All are reasonable, but I don't know how they differ and what is the correct ...
user avatar
  • 145
4 votes
1 answer
4k views

What is the difference between LRU implemented for a cache and for page replacement?

I have read that true LRU page replacement requires significant hardware support, so only approximation of LRU is implemented for page replacement. So I wanted to contrast LRU that is implemented for ...
user avatar
4 votes
1 answer
6k views

Performance of row- vs. column-wise matrix traversal

Scott Meyers describes here that traversing a symmetric matrix row-wise performes significantly better over traversing it column-wise - which is also significantly counter-intuitive. The reasoning ...
user avatar
  • 337
4 votes
1 answer
3k views

Understanding pipeline stalls (bubbles) based on stage

I'm currently reading through x86 Assembly Language and C Fundamentals and came across this statement in the second chapter of the book: If the instruction required is not available in the cache, ...
user avatar
  • 141
4 votes
1 answer
4k views

What problem does cache coloring solve?

According to what I have read from two different sources, cache coloring is (was?) required in order to: Counter the problem of aliasing: Prevent two different virtual addresses with the same ...
user avatar
  • 259
4 votes
2 answers
772 views

How to avoid column wise access in matrix multiplication?

I know when we access elements in rows it will be much faster than if it is accessed column wise. In matrix multiplication one of the matrices must be accessed column wise. In GPUs with CUDA/OpenCL ...
user avatar
  • 1,719
3 votes
2 answers
82 views

Cache strategies, what reference article could I study?

So as to optimize an application, I must implement data caching: not to recompute some data - those heavy on cpu but that don't change often. When playing with the idea, I imagined something like the ...
user avatar
3 votes
2 answers
116 views

Identifying system events affecting timing behavior of an application

Q: What are those events (system level and architecture level) that can cause an application to take longer to terminate and complete the job? My question is purely in the context of Worst Case ...
user avatar
  • 67
3 votes
1 answer
2k views

How do stack-based cache algorithms avoid Belady's anomaly?

I was going through page replacement algorithms from Galvin's Operating System book. I encountered this line about LRU: A stack algorithm is one in which the pages kept in memory for a frame set ...
user avatar
  • 274
3 votes
1 answer
91 views

Is PREFETCH an asynchronous operation?

I often hear Prefetching as a technique for speeding up, for example, sequential memory access pattern. The prefetch should occur sufficiently far ahead in time to mitigate the latency of memory ...
user avatar
  • 131
3 votes
1 answer
877 views

CPU cache - retrieving data from memory

Regarding CPU cache, if the CPU does not find the data it needs in the cache, I understand it then looks for it in the main memory (RAM). (Let's assume we have only one level of cache in order to keep ...
user avatar
  • 133
3 votes
1 answer
1k views

What if block sizes are not equal among caches?

In all the books, packets of slides and similar I read, cache miss is always explained by assuming that blocks of different caches (or cache and RAM) are always of the same size. It's pretty clear how ...
user avatar
3 votes
1 answer
2k views

Back invalidation to maintain inclusion in inclusive cache

For an L2 cache that is strictly inclusive of the L1 cache, if a block to be evicted is also present in L1, then back invalidation is required to maintain the inclusion property. I am interested in ...
user avatar
  • 131
3 votes
1 answer
2k views

Understanding the basic concepts in memory organisation

(Before actually proceeding to the question, I want to confess that this is a homework question, please do consider it and help me in improving my understanding a bit more.) I have recently started ...
user avatar
3 votes
2 answers
3k views

Finding hit ratio of a cache

Consider an array A[100] & each element occupies 4 word. A 32 word cache is used and divided into 8 word blocks. What is the hit ratio for the following statement. Assume one block is read into ...
user avatar
  • 1,443
3 votes
2 answers
478 views

How is parallel tag checking achieved in associative Mapping?

I originally posted this question on stack overflow and then realised it was better suited to computer science . In the book on computer organization and architecture by William stallings , in the ...
user avatar
  • 133
3 votes
1 answer
1k views

What happens if the associativity level is greater than the cache size?

I am working on a computer organization caching problem The Problem: What happens if the associativity level is greater than the cache size? I know that associativity level is how many blocks are ...
user avatar
3 votes
0 answers
230 views

Is it possible to figure out cache size and associativity using the length of offset, index, tag fields?

I have a question where I am asked to find the size of a cache. I am given the following info: a) the length of a memory address b) the number of bits for offset, index, and tag fields. I know I ...
user avatar
3 votes
0 answers
83 views

References on memory subsystems

I took a typical computer architecture class a long time ago as an undergrad and since then I've done a fair amount of low-level systems programming down to the assembly level and worked on OS kernels....
user avatar
  • 31
3 votes
0 answers
32 views

How do you compare algorithms based on scaling of their cache misses? [duplicate]

We all know how to use “Big O” notation to show how CPU instructions run increase as the size of the dataset increases. E.g. a quick sort is O(n log n). However for the last few years, ...
user avatar
3 votes
1 answer
295 views

L1 and L2 cache

I cannot find a to-the-point reference for my question. Am I correct in assuming that if you have an L1 and an L2 cache, typically the L2 cache linesize is larger? For the following, let's assume a ...
user avatar
2 votes
2 answers
410 views

Does having one large L1 cache instead of L1 and L2 cache makes computation faster?

Does having one larger L1 cache instead of L1 and L2 cache makes computation faster? Also will this make the CPU more expensive to make?
user avatar
  • 23
2 votes
1 answer
63 views

How does software prefetching work with in order processors?

From prof. Onut Mutlu's slides on prefetching, this example has been shown as software prefetching: ...
user avatar
2 votes
3 answers
979 views

Does exploiting a spatial Locality in Cache always leads to a lower miss rate?

I've read that, incorporating many words(spatial locality) per cache blocks leads to lower miss rate. Is it the case always? One possibility of such approach is to make a single cache block of size ...
user avatar
  • 55
2 votes
1 answer
21k views

A cache memory has a line size of eight 64-bit words and a capacity of 4K words

A cache memory has a line size of eight 64-bit words and a capacity of 4K words. The main memory size that is cacheable is 1024 Mbits. Assuming that the addressing is done at the byte level, show ...
user avatar
2 votes
2 answers
313 views

Spatial Locality in Cache - Which addresses are loaded?

I don't quite understand the concept of spatial locality in cacheing. I understand that on a cache miss, not only the specific address we want is loaded into the cache, but also "nearby addresses" are ...
user avatar
  • 315

1
2 3 4 5