Prozessor-Cache und Rückwärtsdurchlauf von Daten
-
rapso schrieb:
ja es ist sehr unguenstig, DRam und die controller sind meist so aufgebaut, dass sie erwarten, dass du als naechstes auch die naechste speicherbank liesst, tust du das nicht, so muss jedesmal eine andere bank gesetzt werden.
aber da is doch sowieso noch die Abbildung virtuelle->physische Adressen drin? Kontinuierliche Adressen liegen damit garnicht zwangsläufig auch physisch in dieser Reihenfolge vor.
-
Jester schrieb:
hustbaer schrieb:
Es gibt allerdings schlaue Cache Manager die sequentielle Zugriffe erkennen, und entsprechend schon die nächste Cache Line laden während das Programm noch in der alten rummacht.
Auf welchen Architekturen kommt sowas denn zum Einsatz?
allen die dram verwenden.
-
Jester schrieb:
rapso schrieb:
ja es ist sehr unguenstig, DRam und die controller sind meist so aufgebaut, dass sie erwarten, dass du als naechstes auch die naechste speicherbank liesst, tust du das nicht, so muss jedesmal eine andere bank gesetzt werden.
aber da is doch sowieso noch die Abbildung virtuelle->physische Adressen drin? Kontinuierliche Adressen liegen damit garnicht zwangsläufig auch physisch in dieser Reihenfolge vor.
nicht zwangslaeufig aber oft doch, meist 4kb, manchmal haben die OS auch pools fuer verschieden grosse allokationen, somit bekommt man kontinuirlichen speicher (manchmal muss man dafuer spezielle funktionen im OS aufrufen).
-
rapso schrieb:
Jester schrieb:
hustbaer schrieb:
Es gibt allerdings schlaue Cache Manager die sequentielle Zugriffe erkennen, und entsprechend schon die nächste Cache Line laden während das Programm noch in der alten rummacht.
Auf welchen Architekturen kommt sowas denn zum Einsatz?
allen die dram verwenden.
Hast Du nen Link dazu?
-
"Alle die DRAM verwenden" ist wohl eine kleine Übertreibung
Data Prefetch macht z.B. der Pentium III ab dem Tualatin Core, und natürlich spätere Pentium/Core/Core 2 CPUs von Intel.
Was virtuelle vs. physikalische Adressen angeht: die Prefetch Logik in der CPU wird wohl mit virtuellen Adressen arbeiten (hoffe ich mal), daher egal. Der Memory Controller arbeitet natürlich mit physikalische Adressen, aber der spielt da denke ich nicht so arg mit rein wenn die CPU "schlau genug" Prefetch macht. Davon abgesehen enthält bei 128 Byte Cachelines eine 4BK Page immer noch 32 Cachlines, d.h. es sind sowieso nur knapp 3,2% aller Zugriffe betroffen (wenn die Adresse von Page zu Page immer "springen" sollte).
Sogesehen ist das denke ich ziemlich egal wie das OS das mapping virtuelle -> physikalische Adressen macht.
-
Hardware Prefetching für Daten gibt es von Intel ab dem Pentium 4 (und möglicherweise späten P3-Cores, das müsste ich nochmal extra schauen)
Intel 64 and IA-32 Architectures Optimization Reference Manual schrieb:
9.2 HARDWARE PREFETCHING OF DATA
Pentium M, Intel Core Solo, and Intel Core Duo processors and processors based on Intel Core microarchitecture and Intel NetBurst microarchitecture provide hardware data prefetch mechanisms which monitor application data access patterns and prefetches data automatically. This behavior is automatic and does not require programmer intervention.
For processors based on Intel NetBurst microarchitecture, characteristics of the hardware data prefetcher are:
1. It requires two successive cache misses in the last level cache to trigger the mechanism; these two cache misses must satisfy the condition that strides of the cache misses are less than the trigger distance of the hardware prefetch mechanism (see Table 2-6).
2. Attempts to stay 256 bytes ahead of current data access locations.
3. Follows only one stream per 4-KByte page (load or store).
4. Can prefetch up to 8 simultaneous, independent streams from eight different 4-KByte regions
5. Does not prefetch across 4-KByte boundary. This is independent of paging modes.
6. Fetches data into second/third-level cache.
7. Does not prefetch UC or WC memory types.
8. Follows load and store streams. Issues Read For Ownership (RFO) transactions for store streams and Data Reads for load streams.
Other than items 2 and 4 discussed above, most other characteristics also apply to Pentium M, Intel Core Solo and Intel Core Duo processors. The hardware prefetcher implemented in the Pentium M processor fetches data to a second level cache. It can track 12 independent streams in the forward direction and 4 independent streams in the backward direction. The hardware prefetcher of Intel Core Solo processor can track 16 forward streams and 4 backward streams. On the Intel Core Duo processor, the hardware prefetcher in each core fetches data independently.Table 2-6. Trigger Threshold and CPUID Signatures for Processor Families Trigger Threshold Distance (Bytes) Extended Model ID Extended Family ID Family ID Model ID 512 0 0 15 3, 4, 6 (Prescott+) 256 0 0 15 0, 1, 2 (Willamette, Northwood) 256 0 0 6 9, 13, 14 (Pentium M, Core Solo/Duo) Data is fetched 64 bytes at a time; the instruction and data translation lookaside buffers support 128 entries. See Table 2-7 for processor cache parameters. Table 2-7. Cache Parameters of Pentium M, Intel Core Solo, and Intel Core Duo Processors Level Capacity Associativity (ways) Line Size (bytes) Access Latency (clocks) Write Update Policy First 32 KByte 8 64 3 Writeback Instruction 32 KByte 8 N/A N/A N/A Second (model 9) 1 MByte 8 64 9 Writeback (Pentium M) Second (model 13) 2 MByte 8 64 10 Writeback (Pentium M) Second (model 14) 2 MByte 8 64 14 Writeback (Core Solo/Duo)Hinsichtlich der Diskussion düften Punkte 3 und 5 relevant sein. Wenn Interesse besteht, kann ich noch entsprechende Daten bei AMD heraussuchen.
-
hustbaer schrieb:
"Alle die DRAM verwenden" ist wohl eine kleine Übertreibung
Data Prefetch macht z.B. der Pentium III ab dem Tualatin Core, und natürlich spätere Pentium/Core/Core 2 CPUs von Intel.
Was virtuelle vs. physikalische Adressen angeht: die Prefetch Logik in der CPU wird wohl mit virtuellen Adressen arbeiten (hoffe ich mal), daher egal. Der Memory Controller arbeitet natürlich mit physikalische Adressen, aber der spielt da denke ich nicht so arg mit rein wenn die CPU "schlau genug" Prefetch macht. Davon abgesehen enthält bei 128 Byte Cachelines eine 4BK Page immer noch 32 Cachlines, d.h. es sind sowieso nur knapp 3,2% aller Zugriffe betroffen (wenn die Adresse von Page zu Page immer "springen" sollte).
Sogesehen ist das denke ich ziemlich egal wie das OS das mapping virtuelle -> physikalische Adressen macht.wie ich schon sagte ist diese funktionalitaet (schon zu pentium1 zeit soweit ich weiss) teil des memorycontrollers. Es gab frueher EDO-RAM, das wurde speziell dafuer konstruiert kontinuirlich zu lesen und wurde dann aber ziemlich teuer das in jeden riegel einzubauen, also stieg man auf DRAM um und integrierte mehr logic in den controller. diese konnten dann schon immer im vorr aus die naechste bank setzen, so umging man viel latenz. zudem konnten die controller teiladressen setzen, statt komplett neu zu "indizieren", das alles um latenz zu senken.
bei controllern laeuft das ganze auf den "richtigen" adressen ab, bei CPUs auf den virtuellen.
-
@rapso:
Ich weiss nicht ganz worauf du hinaus willst. Ich zumindest spreche hier vom Prefetching der CPU, also dass die sich Daten in den Cache holt bevor sie gebraucht werden. Das hat mit dem Memory Controller garnix zu tun, das ist wie gesagt in der CPU verankert. Siehe dazu das Posting von camper.@camper: Laut dem was ich gefunden habe ab Pentium III mit dem "Tualatin" Core.
@OP: Wie's aussieht können zumindest neuere CPUs auch "rückwärts" prefetchen, sollte also egal sein wenn du deine Daten "rückwärts" durchgehst.
-
hustbaer schrieb:
@rapso:
Ich weiss nicht ganz worauf du hinaus willst. Ich zumindest spreche hier vom Prefetching der CPU, also dass die sich Daten in den Cache holt bevor sie gebraucht werden. Das hat mit dem Memory Controller garnix zu tun, das ist wie gesagt in der CPU verankert. Siehe dazu das Posting von camper.da mein linker hier gerade wieder 10min braucht, nehm ich mir die zeit dich aufzuklaeren.
ich sage : schlauer speichermanager lesen schon die naechste ram-bank im voraus
jester sagt: seit wann
ich sage : seit dram
du sagst : das ist ubertrieben
ich sage : seit dem nachfolger von edoram, naemlich dram, wird das so von den speichermanagern (auch controller auf english genannt) so gemacht.ich hoffe du kannst dem folgen, ansonsten lese bitte nochmal meine laengeren eklaerungen oben (auch falls ich um 3am nicht mehr so wohlformuliert schreibe
)
-
Lies du es nochmal, Jester hat auf mein Posting (wo es um Prefetching seitens der CPU ging und nicht um (D)RAM Controller) geantwortet.
-
AMD Athlon
Processor x86 Code Optimization Guide schrieb:Some AMD Athlon processors implement a hardware prefetch mechanism. This feature was implemented beginning with AMD Athlon processor Model 6. The data is loaded into the L2 cache. The hardware prefetcher works most efficiently when data is accessed on a cache-line-by-cache-line basis (that is, without skipping cache lines). Cache lines on current AMD Athlon processors are 64 bytes, but cache line size is implementation dependent.
Athlon Model 6 heißt ab Athlon XP.
Software Optimization Guide for AMD64 Processors schrieb:
Hardware Prefetching
The AMD Athlon 64 and AMD Opteron processors implement a hardware prefetching mechanism. The prefetched data is loaded into the L2 cache. The hardware prefetcher works most efficiently when data is accessed on a cache-line-by-cache-line basis (that is, without skipping cache lines). Cache lines on current AMD Athlon 64 and AMD Opteron processors are 64 bytes, but cache-line size is implementation dependent.
The hardware prefetcher prefetches data that is accessed in an ascending or descending order on a cache-line-by-cache-line basis. For example, when the hardware prefetcher detects an access to cache line l followed by an access to cache line l + 1, it initiates a prefetch of cache line l + 3. Accessing data in increments larger than 64 bytes may fail to trigger the hardware prefetcher because cache lines are skipped. In these cases, software-prefetch instructions should be employed. Note that in some earlier revisions of the AMD Athlon 64 and AMD Opteron processors the hardware prefetcher would only detect ascending accesses.Ich vermute mal, beim Athlon XP ist Hardware Prefetching auch nur in Vorwärtsrichtung implementiert. Die erwähnten frühen Revisionen des Athlon 64 dürften den Hammer meinen.
Als Fazit gilt wohl, dass man Arrays nach Möglichkeit immer in Richtung aufsteigender Adressen durchlaufen sollte, nur wenn sich der Algorithmus dadurch vereinfacht, ist die umgekehrte Richtung angezeigt. Denn selbst beim Core wird die Vorwärtsrichtung bevorzugt und dieser kann ja nur einen Strom je Seite verfolgen (und dieser Mechanismus ist dann möglicherweise wegen anderer Daten auf dieser Seite bereits aktiv).
