Polyhedrisches Modell für parallele Compiler in der Informatik (grundlegende Frage)

Question

Aufgabe:

Es geht weniger um eine Aufgabe und mehr um eine kleine allgemeine Verständnisfrage die für euch Mathematiker bestimmt total einfach zu beantworten, sozusagen trivial ist. Und zwar: was bedeuten die 2x2 bzw 2x4 Matritzen (aus 1 bzw. -1 bestehend). Ich verstehe nicht so recht was die da zu suchen haben....

for (i = 0; i <= n; i++) { 
   ...
}

$$\left\{i \in Z ;\left[\begin{array}{cc}{-1} & {1} \\ {1} & {0}\end{array}\right]\left[\begin{array}{l}{i} \\ {n}\end{array}\right] \geq\left[\begin{array}{l}{0} \\ {0}\end{array}\right]\right\}$$

In general:

\( P=\left\{\vec{x} \in K^{n} ; A \cdot \vec{x} \leq B \cdot \vec{n}+\vec{b}\right\} \)

Iteration space:

$$\begin{array}{l}{P=\left\{\vec{x} \in K^{n} ; A \cdot \vec{x} \leq \vec{b}\right\}} \\ {P=\left\{\vec{x} \in Z^{2} ; A \cdot \vec{x} \leq \vec{b} \right\} }\end{array} = \left\{ (i, j)^{T} \in Z^{2} ;\left[\begin{array}{cc}{1} & {0} \\ {-1} & {0} \\ {0} & {1} \\ {1} & {-1}\end{array}\right]\left[\begin{array}{c}{i} \\ {j}\end{array}\right] \leq\left[\begin{array}{c}{N-1} \\ {0} \\ {N-1} \\ {0}\end{array}\right] \right \}$$

For locality: Sweep vertically

for (i = 0; i <= 5; ++i)
  for (j = i; j <= 7; ++j)
    Z[j][i] = 0;

Polyhedron:

$$\left[\begin{array}{cc}{1} & {0} \\ {-1} & {0} \\ {-1} & {1} \\ {0} & {-1}\end{array}\right]\left[\begin{array}{l}{i} \\ {j}\end{array}\right]+\left[\begin{array}{l}{0} \\ {5} \\ {0} \\ {7}\end{array}\right] \geq\left[\begin{array}{l}{0} \\ {0} \\ {0} \\ {0}\end{array}\right]$$

Answer 1

Hier wurden die Bedingungen im Schleifenkopf als Matrixungleichung geschrieben.

Bei der ersten for(int i=0; i <= n; i++) fängst du mit i = 0 an und inkrementierst dann solange bis i = n. Also gilt

$$ 0≤i \text{ und } i≤n$$

bzw

$$ 0≤i \text{ und } 0≤n-i$$

Das kannst du auch schreiben als

$$ \begin{pmatrix}-1&1\\1&0\end{pmatrix} \begin{pmatrix} i \\ n \end{pmatrix} ≥ \begin{pmatrix}0\\0\end{pmatrix}$$

Bei der zweiten Schleife genauso.

Comments

Danke - dann muss ich mir nochmal genau vor Augen führen wie das funktioniert - sinngemäß ist es aber schon mal eine große Hilfe. Danke für die Antwort.

---

Naja wenn du die linke Seite ausmultiplizierst dann steht da:

$$\begin{pmatrix}-i+n\\i\end{pmatrix}≥ \begin{pmatrix}0\\0\end{pmatrix} $$

Und jetzt die beiden Zeilen einzeln lesen. Dann bekommst du genau die beiden Bedingungen oben.

Bei der zweiten Matrix erhältst du

i ≥ 0, -i+5≥0, -i+j≥0, -j+7≥0

Diese vier Ungleichen beschreiben eindeutig die im Schleifenkopf durchlaufenen (i,j)

---

Eigentlich sehr logisch. Wäre ohne dich aber nicht darauf gekommen. Vielen Dank für deine Bemühungen!