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 ...
- 186
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 ...
- 17.6k
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 ...
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 ...
- 1,831
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 ...
- 17.6k
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 ...
- 1,264
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 ...
- 9,027
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 ...
- 1,040
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 ...
- 614
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 ...
- 38.5k
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 ...
- 1,825
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 ...
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 ...
- 41
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}
...
- 828
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 ...
- 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).
...
- 1,569
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 ...
- 27.8k
4
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 ...
- 299
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.
...
- 4,807
3
votes
Does having one large L1 cache instead of L1 and L2 cache makes computation faster?
Note: I first intended to make this a comment under Paul's answer, but it grew too big.
Does having one larger L1 cache instead of L1 and L2 cache... Also will this make the CPU more expensive to ...
- 3,024
3
votes
Direct mapping cache with LRU
LRU only applies if the cache is set-associative and you need a hint as to in which set you write new data. In a direct mapped cache, here is only one place to put data.
- 31
3
votes
Set Associative Cache - duplicate Tag
The CPU tests all caches ways and selects the one that is both valid and have a matching tag address. It may occur concurrently on all ways or be sequential (with a preferred way, depending on the ...
- 1,831
3
votes
Why we need to read memory on a write-miss?
While it would be possible to construct a 128-bit wide memory bus with a separate write-enable control for each octet (sixteen in all), doing so would generally be more expensive than designing the ...
- 1,253
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 ...
- 1,604
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 ...
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 ...
- 884
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 ...
- 3,024
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 ...
- 9,727
Only top scored, non community-wiki answers of a minimum length are eligible