Prefetching data

Only by allocating, that I can think of. You can always put memory on the stack by allocating it and then using it later. I''m not sure what good "I will need addresses 0x... through 0x..." would do anyway other than in that context.

-fel

AMD had a paper on this recently. They had a macro that wrapped loading your data into an array on the heap.

The paper should still be on their site, it was only a few months ago.

Cheers
Chris

fel: the question is not allocating memory; he wants to give an optimization hint to the processor, that a (obviously already allocated) memory range will be accessed for reading/writing soon. This can make a huge difference, because memory access latency is large compared to processor speed.

It is enough to simply loop over your buffer, and ''touch'' (read) one location per cache line - when going to main memory, the processor reads the entire line. The size depends on data bus width and the memory controller''s programmed burst transfer length (hehe, all hell would break loose if it''s changed ); it''s 64 bytes on my DDR Athlon system and P4s, and usually 32 bytes otherwise. The processor cannot ignore these reads, so you better know what you''re doing, or this may actually slow things down. AMD gives a rule of thumb prefetch distance formula of 200 * (stride / # clocks with L1 hit).

An alternative is the prefetchXX instruction; XX are usage hints (cache level, or non-temporal). It''s part of SSE, therefore available on PIIIs and Athlon XP. There is also a similar 3DNow! instruction for Athlons. These instructions can be ignored by the processor, and IIRC, there can only be 3 prefetches in-flight at a time.

quote:

---

Original post by Jan Wassenberg
...It is enough to simply loop over your buffer, and ''touch'' (read) one location per cache line - when going to main memory, the processor reads the entire line....

---

Err, the rest of your post looks great, but I don''t see how this would provide any speedup... would the process be able to continue as the processor continues to copy normal ram into cache? That would explain it... but I would have assumed that the processor would wait for the entire block to load first? If it did block, then you''d just be blocking ahead of time instead of when it''s needed.

Even if this was in a seperate thread, I don''t think it''d provide a boost... since the system would loose most of the cached data when it worked on a seperate thread or application.

You probably understand it better than I do, I''m just trying to understand better .

A good question. To understand why, we need to dig even deeper:
modern CPUs split the x86 instructions into RISC-style µops. Example: add [eax], ebx -> load, exec, store. When a load or store µop is encountered, it goes into a queue waiting to access L1 cache; execution continues immediately. 2 of these requests can be taken out of the queue per clock; either they are satisfied by the L1 cache, or they go into a larger queue waiting on L2. If that''s a miss as well, a request is sent to the memory controller for the cache line containing the desired data. The point is, such requests are ordered (needed for program correctness), but asynchronous - unless a following instruction is dependent on the data, execution continues directly. In our case, we are basically spewing out requests to read data into a register; the actual data is discarded after it is read into cache (our goal).
Secondly: the latency from the time the request is sent to when the data is on the bus is variable - it depends on whether the correct DRAM bank and page is already ''open''. In simple terms, more locality = less latency. We gain from prefetching if the actual calculation involves other data, much like 2 reads from the hard drive are slower than 2x one, because of the seek time (a large part of the latency in a read). In the DRAM case, what is causing the delay is ''precharge'' (unavoidable; basic turnaround time between 2 accesses), and worse, changing row address.

In short, prefetches do not stall execution (*), and can actually read the data faster than scattered accesses.

Side note: even with unoptimized code, where a dependency chain is stalled waiting for a load to complete, the processor tries to keep busy by executing independent code. It has a fairly large window of the following code it sees (144 instruction reorder buffer, IIRC), but this can run out; ordering code helps in this case.