# Tag Info

42

That depends both on the processor (not just the processor series, it can vary from model to model) and the operating systems, but there are general principles. Whether a processor is multicore has no direct impact on this aspect; the same process could be executing on multiple cores simultaneously (if it's multithreaded), and memory can be shared between ...

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 ...

22

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. ...

20

The question as stated is not quite answerable. A word has been defined to be 32-bits. We need to know whether the system is "byte-addressable" (you can access an 8-bit chunk of data) or "word-addressable" (smallest accessible chunk is 32-bits) or even "half-word addressable" (the smallest chunk of data you can access is 16-bits.) You need to know this to ...

19

Here are a few papers that talk about the cache implications of generational garbage collectors: Caching Considerations for Generational Garbage Collection The Effect of Garbage Collection on Cache Performance From what I can gather, the primary issue is that garbage collected systems trade off space in memory to avoid up front collection. The same thing ...

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 ...

13

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 ...

12

The CPU caches are operational from the very moment on when the CPU is powered up. Neither the BIOS nor an OS are strictly speaking “necessary” to control the caches. The BIOS and the OS can change cache configuration settings in the CPU but they don’t control the normal operation, this is all built into the CPU itself.

10

There is a very tricky aspect of all garbage collectors that might be glossed over in some descriptions, and that is the "full scan" or "full collect". Periodically, randomly, intermittently they must scan all objects. generational collectors are better at postponing the full scan and minimizing its duration, but it is still required. The generational ...

10

The cache is typically oblivious to a context switch. Only the sequence of memory addresses accessed determines which cache lines are replaced. The replacement policy is usually a heuristic dependent on the manufacturer and the particular microarchitecture. The problem is that the heuristic cannot predict the future, which address and therefore cache line ...

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 ...

10

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 ...

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 Perhaps I can shed some light on associativity. These caches aren't just open blocks of memory, so don't think of them as some kind of generic container. Each block of memory has a real address (whether this is physical or virtual doesn't matter, just assume it is a fixed address). At each level of cache this memory can only be cached at very specific ... 8 The CPU cache handles each and every access to memory, that is just too fast to be under software control. It is entirely built into the hardware, either on the CPU chip itself or on the motherboard. 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 Usermode to kernelmode: Wrong! ;-) Yes, interrupts are processed in kernel mode, and originally the way to enter kernel mode was by an interrupt forced somehow by software. On the DEC 2020 there was a set of UIOs (Unimplemented Instruction Opcodes), calling any of those caused a trap to the operating system. They included floating point instructions (if not ... 7 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 ... 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 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, ... 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 ... 6 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 ... 6 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 ... 5 You've already covered background research on cache-oblivious algorithms quite well. In terms of benchmarking and practical results, I see this recent paper by Intel as an interesting read: A Synergetic Approach to Throughput Computing on x86-based Multicore Desktops 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 It's the lower bound counterpart to O($\cdot$). Z is larger than some constant times$L^2\$

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

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

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

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 ...

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