13 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 ...
Shadow Template's 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 ...
Wandering Logic's 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 ...
Shubham Singh rawat's user avatar
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 ...
Wandering Logic's user avatar
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 ...
Kai's user avatar
  • 865
5 votes

Understanding pipeline stalls (bubbles) based on stage

A CPU pipeline has a number of stages. The exact stages vary between CPUs and some CPUs have very many stages, but obviously the first stage must be Instruction Fetch (IF) and the second stage must ...
Johan's user avatar
  • 1,080
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 ...
John L.'s user avatar
  • 39k
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 ...
Bulat's user avatar
  • 1,873
5 votes

What does "associative" exactly mean in "n-way set-associative cache"?

An n-way set associative cache is a cache that is chopped up in sections called sets. And each set can hold n-blocks. A cache-address can be broken up up in 3 parts. the offset within the block the ...
pveentjer's user avatar
  • 319
5 votes
Accepted

What is a cache write miss?

My understanding is that a write-miss occurs when we want to write data to a location in main memory whose data is not currently in its corresponding cache block. This is similar to a read miss: if ...
Nathan Litzinger's user avatar
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 ...
NeverBehave's 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} ...
Akash Mahapatra's 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 ...
Erik Eidt's user avatar
  • 451
4 votes

Is CPU Registers part of Primary Memory?

CPU registers are often counted as part of primary memory (since they are directly accessed by the CPU - see Wikipedia) and are often volatile, so it seems likely that the expected answer is (1). ...
gandalf61's user avatar
  • 1,589
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 ...
gnasher729's user avatar
3 votes

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

Stack based algorithms implies that a set of n pages will be a subset of n+1 pages. Why? In LRU every time a page is referenced it is moved at the top of the stack, therefore the top n pages of the ...
Divyang Vashi's user avatar
3 votes
Accepted

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

"Blocked matrix multiplication" is one way to optimize matrix multiplication for memory access. From "Using Blocking to Increase Temporal Locality" by Bryant and O’Hallaron (2012): Blocking a ...
rphv's user avatar
  • 1,624
3 votes
Accepted

Identifying system events affecting timing behavior of an application

You forgot the most obvious factor: the input of the program. The time taken by a program heavily depends on the input unless it does not have any input or the input comes from a small fixed set. ...
Sarvottamananda's user avatar
3 votes

Calculating the set field of associative cache

The memory has $128$M words = $2^{7+20}$ = $2^{27}$ words. Hence it needs needs $27$ bits for address space. Each block has $64$ words, so the block offset = $2^6$ words. So Block offset field can be ...
Sagnik's user avatar
  • 894
3 votes
Accepted

how os can calculate cpu cache size?

It's not clear to me what you want. An OS can query the processor about its cache structure as long as the processor have the feature (for instance, X86 has this possibility tied with the CPUID ...
AProgrammer's user avatar
  • 3,069
3 votes

What is the difference between caching, buffering and paging? Expecting a detailed answer on the OS level

Paging, caching, and buffering are too broad topics to cover in a single post. Briefly, they serve different purposes: Operating systems use paging as a memory management scheme. A computer stores ...
fade2black's user avatar
  • 9,837
3 votes
Accepted

Slowdown when accessing data at page boundaries?

Go to Agner manuals page and download them all, you will find tons of interesting info there. In particular, microarchitecture.pdf says There is a false dependence between memory addresses with ...
Bulat's user avatar
  • 1,873
3 votes

Is PREFETCH an asynchronous operation?

If it is implemented in hardware, prefetching is typically done asynchronously. It's also possible for a compiler to insert extra prefetch instructions into the code. Thus, the initiation of the ...
D.W.'s user avatar
  • 159k
3 votes

What is a cache write miss?

This is an old question, but I don't think any of the other answers quite explain what the text is saying. A word is typically smaller than a cache line; a system might, for example, have words that ...
Pseudonym's user avatar
  • 22.1k
3 votes
Accepted

How can an instruction be fetched every cycle?

So, how does the CPU fetch a new instruction every cycle, if it takes more than one cycle to even fetch an instruction? It could be done by starting the next fetch before the previous one completed. ...
harold's user avatar
  • 2,053
3 votes
Accepted

Are really only ~1% of the physical CPU space used for computing

I don't have any numbers for you, but that's partly because I don't know what Herb Sutter meant by "actual processing". What I think he meant is, essentially, ALUs. So you have to consider ...
Pseudonym's user avatar
  • 22.1k
2 votes

Identifying system events affecting timing behavior of an application

I'd agree that your list includes many items that can cause execution to lengthen. But those are all directly related to the execution of the application code itself. Also consider events which ...
Brian Hibbert's user avatar
2 votes

Computer cache - data removing

The simple (possibly, overly simplified) answer is that you need to remove entries whenever a new entry is to be written to the cache, but the cache is full. That is, if there is a memory access ...
Ran G.'s user avatar
  • 20.7k
2 votes
Accepted

In a $k$-way set associative cache,main memory block mapping in range?

Number of sets in cache = v. So, main memory block j will be mapped to set (j mod v), which will be any one of the cache lines from (j mod v) * k to (j mod v) * k + (k-1). (Associativity plays no ...
Alwyn Mathew's user avatar

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