30 votes
Accepted

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

Memory latency is one of the fundamental problems studied in computer architecture research. Speculative Execution Speculative execution with out-of-order instruction issue is often able to find ...
user avatar
21 votes

Tag, index and offset of associative cache

Before getting to your question, let's recall what set-associativity means, and how one can figure out how to split the address into tag, index and offset. If you prefer to learn by examples, jump to ...
user avatar
  • 20.4k
16 votes

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

The short answer is: nothing, the processor stalls. There aren't so many possibilities. Switching to a different task isn't really an option for two reasons. That's an expensive operation, and since ...
user avatar
13 votes
Accepted

Memory Consistency vs Cache Coherence

As you pointed out, coherence is a property of an individual memory location while consistency refers to the order of accesses to all memory locations. Sequential consistency is a strictly stronger ...
12 votes
Accepted

Why is quiescent consistency compositional, but sequential consistency is not

Sorry for the late reply, but I've just found the question (questions, indeed). I am studying concurrency as well and I'll try to share some ideas with you. First, let's start with sequential ...
user avatar
10 votes

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

The operating system performs a lot of work before executing the first instruction. The OS must set up at least two data structures, the page table and the region map. The region map is called ...
user avatar
8 votes
Accepted

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

For a direct mapped cache the general rule is: first figure out the bits of the offset (the right-most bits of the address), then figure out the bits of the index (the next-to right-most address bits),...
user avatar
8 votes

How exactly MOV AX will load data from RAM?

I am not sure if this is actually on-topic here, but anyway. The main memory in x86 architectures is addressed byte-wise. If you want to retrieve 16 bits from address 2000h (note that AX is a 16 ...
user avatar
  • 2,682
7 votes
Accepted

Are cache contents specific to a process?

It depends, there are several kinds of caches. Some caches, known as PIPT (physically indexed, physically tagged) operate entirely on the physical address. The cache subsystem is independent of ...
user avatar
7 votes

Write Serialization for Cache Coherence in the presence of Store Buffers

From a coherence perspective, I think your example is coherent. All processors believe that the write and read from A happened first, then the write and read from B happened later. From a ...
user avatar
7 votes

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

The Aliasing problem can be solved if we select the cache size small enough. If cache size is such that the bits for indexing the cache all come from the page offset bits , multiple virtual address ...
user avatar
6 votes

Finding cache block transfer time in a 3 level memory system

I guess you got the access time wrong. Access time means time to locate a data on a memory. So, whoever accesses the memory (be it CPU or some other device) it will be the same. Coming to first ...
user avatar
6 votes
Accepted

Computer cache - data removing

Cache lines are evicted : When the OS requests it, it may occur for example in non cache-coherent systems when a peripheral does a DMA transfer (direct transfer from a peripheral to main memory), or ...
user avatar
  • 1,766
6 votes
Accepted

How does software prefetching work with in order processors?

"In-order" processors only issue instructions in order. Completion is out-of-order even on most processors that are called "in-order". "in-order" just means: if the ...
user avatar
5 votes

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

The answer to this question will vary with the architecture in question. While many CPUs will stall (ARM, x86 w/o hyperthreading, etc.) because it takes them too long to switch threads, that's not the ...
user avatar
  • 230
5 votes

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

LRU is most commonly used in 2-way associative caches, where it only requires a single bit that is set or cleared depending on the way accessed. (True LRU requires log2(N!) bits for N ways for each ...
user avatar
5 votes
Accepted

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

Whether a shallower memory hierarchy provides better performance depends on the workload, the microarchitecture, and the implementation technology. A workload that has a high miss rate for a "...
user avatar
5 votes

Depth first or breadth first ordering in binary search trees?

Think about what happens when you move from one layer in the tree to the next. When you start getting to layers with progressively more nodes, you'll eventually get to a spot where the layers are so ...
user avatar
5 votes
Accepted

Depth first or breadth first ordering in binary search trees?

There's a paper on this: Khuong and Morin. Array Layouts For Comparison-Based Searching They compare the Eytzinger, B-Tree, Van Emde Boas, and sorted array layouts and conclude that Eytzinger works ...
user avatar
  • 1,254
5 votes

Write Serialization for Cache Coherence in the presence of Store Buffers

Situations like the one you describe are the reason why processor manuals for architectures with store buffers such as intel tend to state that two stores by cores i and j are seen in the same order ...
user avatar
  • 392
5 votes
Accepted

Cache effective access time calculation

This is the kind of case where all you need to do is to find and follow the definitions. There is nothing more you need to know semantically. What is actually happening in the physically world should ...
user avatar
  • 34.1k
5 votes
Accepted

L1 and Ln cache: when are they written?

1) Usually any accessed data are saved into L1, independent whether they were previously available in L1, L2... or memory only. For exclusive cache, data are stored ONLY in L1, for inclusive one, in ...
user avatar
  • 1,805
4 votes
Accepted

Calculating miss rates of word-addressable and direct-mapped cache

It seems you don't understand how cache lines work. A cache line is a contiguous chunk of memory. In this example, the cache line size is 32 bytes. This means that 32 contiguous bytes are always ...
user avatar
  • 2,190
4 votes

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

The accepted answer clear most of the doubt, and I wanna make a note here (for comp org student). The addresses are not byte addressable (as mentioned in the question, they are word addresses). The ...
user avatar
4 votes
Accepted

Understanding Cache Mapping and Access (Computer Architecture)

Any physical address consists of two parts : one part is the block offset and the other part is the block number. Physical Address { Block number, Block Offset} ...
user avatar
4 votes
Accepted

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

First, I'm going to do everything in bytes. A 64-bit word means 8 bytes. Line size: 8 words in a line, means 8 x 8 bytes = 64 bytes in a line = 26 bytes. Cache size: 4k words, meaning 4096 x 8 ...
user avatar
  • 451
4 votes
Accepted

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

Most L2 (and L3) caches are indexed with the physical (not virtual) address modulo a power of two that is larger than the page size. This allows different physical address colors to map to different ...
user avatar
4 votes
Accepted

Cache Miss and Processor Speed

Yes, that's correct. Assuming the speed of the cache doesn't change, a cache miss takes a fixed amount of time, and if the number of instructions per time unit increases, then more instructions get ...
user avatar
  • 25.2k
3 votes
Accepted

What problem does cache coloring solve?

Both avoiding aliases and avoiding excessive cache conflicts are valid reasons for using page coloring. Requiring page coloring to avoid aliases is unpopular because it places a mandatory constraint ...
user avatar
3 votes
Accepted

Calculating cache memory based on LRU algorithm

Least recently used cache do the following things: we add the numbers to the top(front) representing that it is the "most recent" and thus the end of this will be the number which is least recent. If ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible