Können Compiler abwechselnde Zugriffe auf Arrays erkennen und im Speicher verschachteln?

Ist es möglich, einen Compiler zu entwerfen, der eine Schleife optimiert, in der auf Arrays auf alternative Weise zugegriffen wird? Zum Beispiel so:

// int[] a,b
int sum = 0;
for(int i = 0; i < n; i++)
{
  sum += a[i] + b[i];
}

Mit dem üblichen sequentiellen Array-Speicher a[i]und b[i]kann im Speicher weit voneinander entfernt sein. Daher denke ich, dass eine gute Compileroptimierung dies erkennen a[i]und b[i]immer zur "gleichen" Zeit a[0] b[0] a[1] b[1] ...zugreifen und die verschachtelten Arrays speichern würde, dh, dass ein Speicherzugriff beide a[i]und abrufen kann b[i].

compilers arrays program-optimization memory-management Krammer
quelle

Herzlich willkommen! Ich habe versucht, Ihre Frage zu klären. Bitte überprüfen Sie, ob ich es nicht verstümmelt habe. In Bezug auf den Inhalt bin ich sicher, dass Compiler einfache Fälle erkennen können, aber ich bezweifle, dass im Allgemeinen viele Arrays nur auf diese eine Weise verwendet werden. Außerdem sollte es in einem RAM zeitlich nicht effizienter sein, das Array auf diese Weise zu speichern. Es können andere Effekte im Spiel sein, wie Daves Hinweis zu vermuten scheint.

Raphael

Ich bin mir nicht sicher, ob die zugrunde liegende Annahme hier für die moderne Caching-Architektur zutrifft. Solange der Cache geräumig genug ist, um einen signifikanten Teil beider Arrays aufzunehmen (und natürlich nicht von anderen Prozessen beeinflusst wird), sollte der Zugriff auf das naive Layout effizient sein.

dmckee --- Ex-Moderator Kätzchen

@ Raphael: Ich denke, Ihre Bearbeitung hat der Frage unerwartete Anforderungen hinzugefügt. Ich denke nicht, dass dies erforderlich ist a[i]und b[i]mit einer Speicheroperation abgerufen werden muss, sondern dass sie sich für eine bessere Cache-Leistung in der Nähe des Speichers befinden.

Dave Clarke

@ DaveClarke eigentlich mit einem Aspekt der Frage wollte ich die entsprechenden Werte von a und b mit einer Speicheroperation abrufen.

Krammer

Ich finde keine Referenz zur Bestätigung. Sun hat vor etwa 10 bis 15 Jahren die Spezifikationsbenchmarks 179.art und 171.swim "gebrochen" (dh durch Optimierung wurden bessere Werte erzielt, als dies durch ihre Hardware gerechtfertigt ist). ISTR, dass es mit verwandten Optimierungen war.

AProgrammer

Antworten:

Es wurden einige Arbeiten durchgeführt, die Ihrer Beschreibung entsprechen. Zum Beispiel:

Compiler-gesteuertes Array-Interleaving zur Reduzierung der Energie in Multi-Bank-Speichern. von Delaluz, V. Design Automation Conference, 2002. Proceedings of ASP-DAC 2002. 7. Asien und Südpazifik und 15. Internationale Konferenz über VLSI Design. Verfahren.

beschreibt eine solche Optimierung.

Dave Clarke
quelle

Vielen Dank. Gibt es eine Methode für Architektur mit vektorisierten Schleifen?

Krammer

Im Beispiel des OP kann ein Compiler, der eine solche Optimierung durchführt, auch das Blockieren verwenden, um SIMD zu unterstützen. Eine solche Transformation ist möglicherweise keine Optimierung, da einige Hardware-Prefetcher keine Seitengrenzen überschreiten. Dies interagiert auch mit der Speicherorganisation und vermeidet möglicherweise DRAM-Bankkonflikte (Bankkonflikte können die Bandbreite verringern sowie den Energieverbrauch erhöhen) oder nutzt nicht mehrere Speicherkanäle aus.

Paul A. Clayton

Die kurze Antwort in diesem Fall lautet, dass die Parallelität auf Speicherebene normalerweise ausreicht, um mehrere separate Speicherblöcke in einer solchen Schleife abzudecken. Das Verschachteln in einen einzelnen Stream würde den Prozess tatsächlich verlangsamen. Viele Caching- und externe Speicheralgorithmen setzen einen solchen Grad an Parallelität voraus.

Die längere, theoretischere Antwort lautet, dass das Caching wie eine Reihe von Aspekten der Programmausführung ist, die einfach erscheinen, sich aber im Allgemeinen als schwer vorhersehbar erweisen. Beispielsweise muss ein Cache-Block möglicherweise nur abgerufen werden, wenn ein bestimmter Prozess angehalten wird. Ein Compiler, der das vorhersagen könnte, wäre gelinde gesagt interessant.

Der einfachere Fall der Optimierung einer bekannten Folge von Zugriffen (ohne sie vorhersagen zu müssen) ist selbst NP-schwer:

Angenommen, man erhält eine Folge von Speicherzugriffen und muss die Daten im Speicher ablegen, um die Anzahl der Cache-Fehlschläge für diese Folge zu minimieren. Wir zeigen, dass wenn P ≠ NP ist, man die optimale Lösung selbst bis zu einem sehr liberalen Approximationsverhältnis nicht effizient approximieren kann.

Petrank und Rawitz, Die Härte der cachebewussten Datenplatzierung

KWillets
quelle

-1

Ihr Beispiel ist nicht vollständig, die Arrays werden nirgendwo deklariert und nirgendwo initialisiert.

Ich vermute, in einem allgemeinen Programmierkontext wäre diese Art der Optimierung "mehr Ärger als es wert ist". Auf die meisten Arrays wird von mehr als einem Ort aus zugegriffen, sodass ein Compiler häufig erraten muss, welcher Ort der wichtigste ist. Auch viele Arrays könnten auf diese Weise nicht geändert werden, da sie die Grenzen der Kompilierungseinheiten entweder als Parameter an Funktionen oder als globale Variablen übergeben. Schließlich würde es Debug-Informationen komplexer machen.

Peter Green
quelle

Zu Absatz 1: Diese Website befasst sich mit Informatik, nicht mit Programmierung. Zu Absatz 2: Können Sie ein bestimmtes Beispiel nennen oder Referenzen zitieren?

Raphael