# Tag Info

28

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 useful work to do to fill the latency during an L1 cache hit, but usually runs out of useful work after 10 or 20 cycles or so. There have been several attempts to ...

23

I think I see your confusion. The TLB and the data cache are two separate mechanisms. They are both caches of a sort, but they cache different things: The TLB is a cache for the virtual address to physical address lookup. The page tables provide a way to map virtualaddress $\mapsto$ physicaladdress, by looking up the virtual address in the page tables. ...

21

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 after the fold. Cache A cache is just a faster, yet smaller, memory. It might take a long time to access data in the main memory, but it is very fast to ...

16

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 the current task and other task are competing for space in the cache, switching to the other task may itself require a main memory access, and so may switching ...

12

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 consistency. A model has this property if operations appear to take effect in program order. In other words, the order in which lines of code are executed is the one ...

11

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 property than coherence. That is: every system that is sequentially consistent is also coherent at every memory location. The opposite is not true, a memory ...

10

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 different things in different operating systems. Inside the Linux kernel, for example, it is a linked list of memory-region objects and some kind of index (e.g. a ...

9

Forget for a moment all of the issues related to the access to main memory and level 3 cache. From a parallel perspective, ignoring these issues, the program parallelize perfectly when using $p$ processors (or cores), owing to the fact that, once you partition the work to be done through domain decomposition, each core must process either \$\left\lfloor {\...

8

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 register), then you will need to read 8 bits from 2000h and 8 bits from 2001h. This is why the operation needs to read "2 cells". Note that the term "cell" is not ...

7

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 virtual memory, so it doesn't matter which process is accessing the cache: all processes share all cache entries. Some caches, known as VIVT (virtually indexed, ...

7

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), and then the tag is everything left over (on the left side). One way to think of a direct mapped cache is as a table with rows and columns. The index tells ...

7

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 consistency standpoint you need to be more careful. (Consistency is the global ordering of memory operations to different addresses.) The way consistency is handled in ...

7

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 will point to the same index position in the cache and aliasing will be solved. For example consider 32-bit virtual address 0xFFFF FFFF , this system uses a ...

6

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 question here. A block is transferred from L2 to L1. And L1 block size being 4 words and data bandwidth being 4 bytes, it requires 1 L2 access (for read) and 1 L1 ...

6

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 if the CPU is shut down to save its state to RAM... When all the ways of the cache are already used for the requested line. In a write-through cache, new data ...

5

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 set.) For four-way and eight-way associativity, binary tree pseudo-LRU is commonly used, though some embedded systems might implement true LRU as such is easier ...

5

In today's standard architectures, the cache uses what is called "spatial-locality". This is the intuitive idea that if you call some cell in the memory, it is likely that you will want to read cells that are "close by". Indeed, this is what happens when you read 1D arrays. Now, consider how a matrix is represented in the memory: a 2D matrix is simply ...

5

I decided to try out __builtin_prefetch() myself. I'm posting it here as answer in case others want to test it on their machines. The results are close to what Jukka describes: About a 20% decrease in running time when prefetching 20 elements ahead versus prefetching 0 elements ahead. Results: prefetch = 0, time = 1.58000 prefetch = 1, time = 1.47000 ...

5

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 approach taken by every architecture. In some architectures, each thread scheduled on a CPU has its own independent register file, so the processor may simply ...

5

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 "conventionally-sized" L1, when run on such a processor, would have more overhead in transferring cache blocks from L2 to L1 and (if writeback) dirty blocks from L1 to ...

5

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 big that they can't fit into memory caches. When that happens, if you've laid out the memory in a BFS order, then going from one layer to the next will almost ...

5

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 best. The reasons are fairly complex, since things like simple address arithmetic and branch predictability combine with memory prefetch and processor ...

5

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 by all other cores. Common techniques for enforcing sequential consistency for certain memory locations include fence instructions and bus locking. How these ...

5

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 be (roughly) clear to you. It is a question about how we translate the our understanding using appropriate, generally accepted terminologies. It is a question ...

5

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 the entire hierarchy. There are also mixed strategies. Also, some CPUs have "victim cache", which is extra cache level which gets ONLY data moved out of LLC (...

5

"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 processor needs to stall the issuing of the next instruction because of a RAW, WAW, or WAR dependence, it can't issue any other instruction during the stall. In ...

4

DDR3 access is indeed pipelined. http://www.eng.utah.edu/~cs7810/pres/dram-cs7810-protocolx2.pdf slides 20 and 24 show what happens in the memory bus during pipelined read operations. (partially wrong, see below) Multiple threads are not necessary if the CPU architecture supports cache prefetch. Modern x86 and ARM as well as many other architectures have an ...

4

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 loaded into the cache at a time, namely whenever a miss occurs. So if we initially assume the cache is empty (or "cold"), then the first access will be a miss. ...

4

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} Block Number has further 2 parts : the index part and the tag. The memory is assumed to be logically divided into many blocks. A block may contain more than one words in it ( which is indicated by ...

4

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 bytes = 32k total bytes. Cache indexes: 32k total bytes / 8 way set associative = 215 / 23 = 212 index positions in the cache line-set array. Main memory: 1024 ...

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