Algorithmus zur Abdeckung von Speicherbereichen?

Question

Ich habe eine Reihe von Bereichen wie {(2-8), (13-22), (380-7931), (40032-63278)}. Der Einfachheit halber können wir annehmen, dass sie sich nicht überschneiden (überlappende Bereiche wurden bereits zusammengeführt).

Mein Ziel ist es, diese Bereiche mit Kombinationen aus einer gegebenen Menge von "Längen" wie {4, 64, 1024, 16384} zu "bedecken". Ich bin gezwungen, höchstens N Längen zu verwenden, wie N = 32. Es ist mir egal, wie viele "Längen" ich verwende, solange ich unter meinem Maximum liege, aber ich möchte den gesamten "zusätzlichen" Bereich minimieren - Zahlen, die von Längen "bedeckt" sind, die nicht in der anfänglichen Reihe von Bereichen sind.

Beispiel {(2-8)} von (2-66) abgedeckt (eine Länge von 64 verwendet) hat 58 "Extra" -Zahlen. {(2-8)}, die von {(2-6), (6-10)} (zwei Längen von 4) bedeckt sind, hat nur 2 "extra" -Zahlen und ist vorzuziehen.

Meine reale Anwendung beinhaltet die Vorprogrammierung eines festen MMU-TLB, um sicherzustellen, dass nur bestimmte Bereiche von Speicheradressen zugänglich sind (TLB-Misses stellen somit einen verbotenen Zugriff dar) & kann entsprechend behandelt werden). Ich möchte die Bereiche so eng wie möglich abdecken, damit Verletzungen eher früher als später aufgedeckt werden, aber ich habe nur 32 Steckplätze und 4 feste Seitengrößen. Ich kann meinen Code von Hand auf ein angemessenes Leistungsniveau einstellen, aber ich bin neugierig, ob es eine elegantere/allgemeinere Lösung für das Problem gibt. Es scheint mit dem Rucksackproblem verwandt zu sein, aber es ist schwierig genug zu suchen.

Answer 1

Dies kann als Variation von Shortest path problem formuliert werden.

Wir brauchen einen Satz von Bereiche der Gesamtlänge M mit höchstens NSeiten abzudecken. Seiten können L verschiedene Längen haben, sie sind nicht ausgerichtet (kann an jeder Adresse platziert werden).Der Unterschied zwischen dem gesamten "Extra" -Bereich und der Gesamtlänge von Seiten ist gleich der Konstante M, die es erlaubt, die Gesamtlänge von Seiten zu minimieren.

Lassen Sie uns ein Diagramm erstellen, das zu diesem Problem gehört. Jede Speicheradresse in einem Bereich hat einen entsprechenden Eckpunkt in der Grafik. Jeder Scheitelpunkt hat L ausgehende Kanten, entsprechend LSeiten, beginnend bei gegebener Adresse. Länge jeder Kante ist gleich Seite Länge. Jede Kante kommt zu einem gewissen Scheitelpunkt in dem Graphen, je nachdem, wo entsprechenden Seite Ende:

1. Seite in einiger nicht besetzten Position endet. Edge kommt an den Scheitelpunkt, entsprechend der Startadresse des ersten Bereichs nach dieser Position.
2. Seite endet in einigen Bereich. Edge kommt an den Scheitelpunkt, der der Endadresse der Seite entspricht.
3. Seite endet in unbelegter Position, mit Adresse, größer als Adresse von Bereich. Edge kommt zu Ziel Vertex. (Die Anfangsadresse des allerersten Bereichs entspricht Quelle Scheitelpunkt, und wir sollten den kürzesten Weg zwischen diesen beiden Scheitelpunkten finden).

Da das resultierende Graph ist ein DAG kann kürzesten Weg in linearer Zeit gefunden werden, durch Verarbeiten der Vertices in einem topologischen Reihenfolge (oder, noch einfacher, um Speicheradressen von entsprechenden).

Für jeden Scheitelpunkt ein Array von N Paaren {Pfadlänge, Rückwärtspfeil}. Während der Algorithmus für den kürzesten Pfad einen beliebigen Scheitelpunkt besucht, indexieren Sie dieses Array mit der Anzahl der Hops im Pfad. Wenn der Pfad kürzer als die gespeicherte Pfadlänge ist, ersetzen Sie {Pfadlänge, Rückwärtspfeil}. Wenn jeder Vertex bearbeitet ist, suchen Sie den kürzesten Pfad in dem Array von Paaren, die zu Ziel Vertex gehören, und rekonstruieren Sie dann den Pfad mithilfe von Rückzeigern. Dieser Pfad beschreibt die optimale Abdeckung.

Worst-Case-Zeit Komplexität O (L * M * N) wird durch maximale Anzahl der Kanten (L * M) und Anzahl der Elemente in der Anordnung bestimmt, die zu jedem Eckpunkt (N) gehören. Wenn Bereiche spärlich sind, kommen die meisten Kanten zur Anfangsadresse einiger Bereich, die meisten Vertices, die internen Adressen entsprechen, werden nicht verwendet, und die Zeitkomplexität ist viel weniger.

Dieser Algorithmus benötigt O (M * N) Raum, aber für spärlich Bereiche dies sein kann deutlich verringert, wenn wir alle Graphen Eckpunkte setzen (oder vielleicht alle Länge/Zeigerpaare) in einen Hash-Map.

Answer 2

Beachten Sie, dass die Bereiche, die Sie abdecken möchten, sehr niedrige Intervalle sind (nennen Sie sie "Bereiche") und die Lücken (nennen sie "Extras") sind sehr kostspielige Intervalle. Jetzt wollen wir die Gesamtkosten mit höchstens N Intervallen (Call "Covers") minimieren, die alle "Bereiche" abdecken und einige "Extras" enthalten können. Der folgende Algorithmus ist in der Natur gierig.

Zuerst nehmen Sie alle Intervalle, die Sie abdecken möchten ("Bereiche") und auch die "Extras" dazwischen.

1) Bedecken Sie sie mit einem großen Intervall von min bis max der "Bereiche".

2) Iterieren und entfernen Sie die teuersten "Extras" (dh größte Spannweite) zwischen dann und zählen Sie auch die Abteilung als Erstellen einer zusätzlichen "Abdeckung", bis die Anzahl der Abdeckungen N wird oder Sie aus der teure "Extras".

Answer 3

Bottom-up gierig Ansatz, der funktioniert, wenn jede Länge ein Vielfaches der letzte ist:

Beginnen Sie mit einer Reihe von Mindestlängen-Intervalle, die alle Bereiche minimal decken. Verknüpfen Sie die längsten Läufe iterativ, bis Sie unter die maximale Anzahl der Bereiche fallen.

In Ihrem Fall, auf einem TLB, haben Sie wahrscheinlich Ausrichtung Einschränkungen, die das Problem ein wenig komplizierter machen wird.