NotationNotation for graphs: KMW call as dependence graph, what we now know as RDG. KMW donot give a name to EDG. KMW call a path as pi. It could be used to define a cycle and simple cycle. Also, its length could be inf if its length is infinite. The cycle and simple cycle are defined only for paths whose length is not inf. (We have to be a little careful about undefined and inf here.)
Other Notations: From KMW KMW use the functions: T, S, F, F_n (they are different), phi_s. S is any schedule. T is the free schedule, the fastest possible schedule. F is defined to test for presence of free schedule. F_n is the positive orthant in the n dimensional Euclidean space. From the book, the notations are: T for any schedule, T_f is the free schedule and F is defined for presence of free schedule, F_n is the positive orthant. phi_s (see later for a proper definition and a possible intuition).
More notices from the notation department: Gamma and EDG in DV and KMW are (slightly) different: The Gamma that KMW define is an EDG with dependence edges. The EDG that Darte-Vivien define has edges that mean data flows. The difference in definitions means changes in simple things like whether the longest path has source or sink of a vertex (k,p) in the EDG. Sticking to the notations in the book seems to be useful.
RDG having depenendence edges/data-flow edges
The equations being defined by a_j = ... a_k(z - w) ... or a_j = ... a_k(z+w)
Relation between Brent's theorem (1974) and KMW's statement of computability:
Computability
Conditions for computability: KMW give both the necessary and sufficient conditions for computability of a RDG. The intuitive definition: An SURE is computable if there exists a schedule for it. In other words, an SURE is computable if every vertex in its EDG is computable.
Computability of a SURE over a bounded domain: Since we usually deal with bounded domains, the computability problem boils down to testing for acyclicity of the EDG. This works, but it is very costly and input size dependent (ala Ford-Fulkerson algorithm for maxflow). Further, this method cannot be applied to unbounded domains.
A note fom Quinton-Saouter-1203 (QS): When the domain is allowed to be unbounded, the SURE is (trivially) incomputable. This result was proved by Joinnault. Most realistic algorithms have bounded domains. QS say that the result may not be that useful and that the interesting cases are the computability questions of SUREs defined over domains of bounded size. Also, QS give the condition for incomputability of Parametrized Uniform Recurrence Equations PUREs and PAREs. (See the nice figures at the end of QS-paper for figures of PUREs which are computable and which are not. The difference being a change in the value of a parameter.)
EDG: Assume we use the Darte-Vivien's notation of edges in the EDG meaning data flow. An EDG is computable iff for all points (i,p) in the EDG, all paths ending at (i,p) are of finite length.
Size of Domain: unbounded and entire positive orthant: Darte-Vivien (chapter 4, theorem 17) give the condition for computability of a SURE defined over entire positive orthant (which is an unbounded domain). It seems that the notion of unboundedness is limited to equations defined over positive orthant (not the entire space: I donot know why and its implications). If a SURE is defined over unbounded domain (meaning positive orthant), then it is computable iff G there is no nonpositive weight cycle in it (where G is its RDG).
Size of domain is bounded: Darte-Vivien (chapter4, theorem 18) give the relationship between the computability and the zero-weight cycles in any SURE defined over bounded domains. Basically, they show that a SURE defined over a bounded domain is computable iff G has no cycle of zero-weight. The phrase "All systems of uniform recurrence equations defined from a RDG G" makes more sense once we understand the definition of a RDG is (quite) independent of the domain of the underlying SURE (the usual definition of a RDG does not encode the domains of the variables). So a RDG can induce many SUREs, each in a bounded domain.
Fat domains: The computability of a SURE defined over bounded domain makes sense iff the domain is sufficiently fat. Read more about this.
Schedule
Schedule: A valid schedule respects the dependences of the SURE. If an SURE does not have such a schedule, then it is said to be incomputable. Examples are either a node in the EDG depending on itself, or a node in the EDG at the end of infinite path before its operands are ready.
Free schedule vs. Linear schedule: KMW donot use the concept of linear schedule (it seems that they donot even use the term: I did a text search). They use a concept of free schedule. Darte-Vivien show that free schedule could beat the fastest linear schedule by a constant, independent of the size of the domain.
Questions: What do KMW mean by bounded and unbounded parallelism? What about the notions of tube (which intuitively means bounded along a dimension)? What about the storage requirements?
Questions on definitions of Schedule S(k,p): As defined on page 566, A schedule seems to be similar to that of a 1-d schedule as we know now. This is because, they talk about every vertex of the EDG getting a 'single time stamp'. But, that does not preclude many vertices getting the same time stamp (right?).
Free Schedule T(k,p) If a vertex of EDG does is free, we evaluate it at time 1. If all the operands of a vertex of the EDG are available at time t, we evaluate the point at time t+1.
Machinery on page 566 involving T and F: From the outside, T and F seem so similar. T gives us a recursive definition and F looks like the expansion of the recursive definition given by T. However, there is a critical there exists clause in the definition of F. That is very crucial to understand that length of a path could go on to undefined values as given by the definition of T. Is there something we need to act here??????
=============================
Section 3: Lemma 1 notes
[Also refer to notes from Berge. This is the link.]
Lemma 1: premise: Number of edges directed out of each vertex is finite. C1: If there is no upper bound on the lengths of paths directed out of vertex v, C2: there exists an infinite path directed out of v.
Strategy to prove that the premise is required: P => (A=>B) is the given structure of lemma. Why is the premise required? The necessity of the premise can be proved by assuming that it is false, i.e., NOT(P) is true. In that case, if we find that the clause (A=>B) is false, we are done. in other words, we should prove that NOT(P) is true and NOT(A=>B) is true. or, that NOT(P) is true and NOT(NOT(A) OR B) is true. or, that NOT(P) is true and A AND NOT(B) is true.
An infinite graph has a vertex w such that outdegree(w) is unbounded. There are two interesting cases: either there exists a path from w to v or there exists a path from v to w. Let us prove for the case when there is a path from v to w(the other case: when there exists a path from w to v can be proved with a similar argument. The third case: when there does not exist a path between v and w blows away the negation of the premise).
There exists a path from v to w. Also, There is no upper bound on the lengths of paths directed out of vertex v. Also, there does not exist an infinite path directed out of v.
Should we give a example or prove the fact? If we give an example, which would be a counter example to the fact that the premise is not required, we are done.
Proof of the Lemma and related notes:
====================
Lemma 1: Let H be a directed graph in the edges directed out each vertex is finite. Then, if there is a no upper bound on the lengths of paths directed out of vertex v, there exists an infinite path directed of v.
Proof strategy: A => B => C. Assume A. Assume NOT(C). If it leads to NOT(B), then we have a contradiction. which proves that B => C.
Proof: Assume the premise. Assume that there does not exist an infinite path directed out of vertex v. Then the longest path directed out of v is the function 1 + max{}. This function is a recursive function defined with peano arithmetic. So, there exists an upper bound on the lengths of paths directed out of vertex v. This is a contradiction with the hypothesis.
Proof 2: The graph is progressively finite. Prove that it is progressively bounded. [The key idea is to get that a finite set has an upper bound.] The set of its descendants is finite.
Proof for the premise: prove that if the graph is progressively finite and not progressevely bounded, there exists a vertex whose outdegree is not finite. This will be contradiction.
The statement actually says that if A (as usual, Gamma-finite), then if it is not progressively bounded, it is not progressively finite. This is the same as saying that if it is progressively finite, it is progressively bounded. (same as if it is (not progressively finite) or (progressively bounded)).
To prove the premise, we have to say that, if it is progressively finite and (not progressively bounded), there exists a vertex whose outdegree is infinite.
Given that there exists no infinite paths and that there is no upper bound on any paths, k*Gamma(x)
=========================
Why do we need the premise? Contrary to the premise, assume that there exists a vertex w which has infinite number of edges out of it. Case 1: If there exists a path from vertex v to vertex w -- regardless of the number of edges out of vertex v -- there exist infinite number of paths out of vertex v. This is because, a path from vertex v to vertex w is all we need (this is why we started from the assumption that the graph is connected). The set of infinite edges out of vertex w lead to infinite number of paths out of vertex w: they are the following: {[v->w,w1],[v->w,w2],[v->w,w3],...,[v->w,wk],...inf}. Case 2: If there exists no path from vertex v to vertex w (or any vertex u which has infinite number of edges out of it), then the premise is not needed for the lemma. Is this right?
Counter example: So a counter example would be an infinite graph (finite graphs are not that interesting) with the folllowing properties.
To remove some of these owes, we can assume that the graph is a connected graph.
In all the proofs here, we assume the premise and prove the lemma.
Proof by deduction:Assume the premise. also assume C1, that there is no upper bound on the lengths of paths directed out of vertex v. for a vertex v, let us define a set S_v, which is the set of all paths from the vertex v. Define L(S_v) as a function, which returns a set L_v, each of whose elements are integers denoting the lengths of paths of elements of S_v.
Since there is no upper bound, the function must return inf. Which is another way of stating C2. Is this right?
Proof by deduction: Assume the premise. also assume C1, that there is no upper bound on the lengths of paths directed out of vertex v. There exists two cases, when the graph is finite (|X| is finite) or not (|X|=inf). case1: the graph is finite: As there is no upper bound on the length of paths out of vertex v, v participates in a circuit. This means that we can obtain paths of *any* length and without bound from v. This means that we can obtain a path of infinite length from v. Q.E.D (???check this proof for circularity???)
Proof by contradiction: Assume premise, assume C1 and negation(C2): case 1: the graph is finite (|X| < inf): NOT(C2) => there is no inf path directed out of v => all paths out of v are of finite (but possibly unbounded) length => there exists a vertex w which is at a maximum distance from v. Let us call this distance k. => all paths out of v are of length <= k. This means that there is a upper bound on the lengths of paths. A contradiction. case 2 (|X|=inf): If the graph is connected (there exists a path between every two vertices), every vertex participates in a path of unbounded length. Which means that the statement is obviously true. If the graph consists of more than one connected component, we can apply the argument of case 1 to the component which contains v.
Assume premise, assume C1, assume NOT(C2): NOT(C2) means that there exists no path of infinite length out of vertex v. Since vertex v has finite outdegree (premise), there does not exist a path of infinite length out of each vertices belonging to the set Gamma(x). This means that ......... ..........
We have to use the fact that v does not praticipate in a path of infinite length. Let us assume for now that an infinite path length is obtained by a circuit. from premise, let us assume that w1,...,wn are the vertices adjacent to v. None of w1,...,wn have a path back to v. This means that the set Gamma(W) is strictly greater than Gamma(v). This means that Gamma^hat(v) is an unbounded set. What do we do with these sets...
proof by contradiction: Assume premise. Assume negation(C1) and C2: NOT(C1) => there exists an upper bound on the lengths of paths directed out of vertex v. => All paths through v are of length <= l. This means that there is no path of length inf thro v. A contrtadiction with C2.
Proof by induction
proving an iff by contradiction of the if and only if part is kind of funny ...
=================================
Explicitly Defined vs. Computability: KMW use explicitly defined for a variable a_j(p) instead of talking about its computability. An SURE is said to have a schedule if each of its variables is explicitly defined (page 566 in the paper and cor.3 in the book). This also means that, an SURE is computable if each of its variables is explicitly defined. (we are using the relationship between computability and the existence of a schedule.)
Bounded Parallelism (page 566): phi_s(s,tau): Given a schedule function for every vertex of the EDG (k,p) (if S(k,p)=tau) phi_s(s,tau) is the cardinality of the inverse of the schedule function S.
Intuitive explanation of phi_s: Given a k and p, it is the number of
Intuition behind phi_s: A given schedule maps the vertices of the EDG into N (as it associates a timestamp with every vertex in the EDG). Given a variable of the SURE, phi_s is the cardinality of the number of vertices of the EDG of that type that have the same mapping???? Also read section 4 for another explanation of phi
It is not clear why phi_s should be parametrized on k also. If what we are interested is bounded parallelism, why not just talk about the cardinality of phi_s(tau) = || p | S(k,p) = tau || k = 1...m and tau = 1,2,...
May be they mean that. This opinion is because, the next line, they say 'for all k and tau'. So the notion of bounded parallelism has nothing to do with the 'type of vertices'. OTOH, the definition of phi_s can be general enough that it can encapsulate other ideas??
=============================================
Section 3:Conditions for a function to be explicitly defined
[With Lemma 1, the stage is set about infinite graphs and relationship between existance of upper bound on the length of the path and presence of a infinite length path. The theorem 1 gives a definition of computability.]
Notation: non+ve: A vector q is nonpositive if q_i <= 0.
Difference between nonpositive (defined on page 567) and semi-positive (defined on page 569): A vector in 2-dimensions, is nonpositive if it belongs to the (i) third quadrant, or (ii) -ve y-axis or (iii) -ve x-axis or (iii) is the zero-vector. A vector in 2-dimensions is said to be semi-positive if is belongs to the (i) first quadrant or (ii) +ve x axis or (iii) +ve y-axis.
Note: The regions are mutually exclusive. There exists vectors which are neither. The following "picture" encapsulates all the above ideas.
^
|
ssssssssssss
ssssssssssss
ssssssssssss
ssssssssssss
ssssssssssss
ssssssssssss
<-nnnnnnnnnnnnsssssssssss->
nnnnnnnnnnnn
nnnnnnnnnnnn
nnnnnnnnnnnn
nnnnnnnnnnnn
nnnnnnnnnnnn
nnnnnnnnnnnn
|
v
[The computability of a SURE and its relation to the presence of positive weight cycles.]
KMW-Theorem 1 statement: Let G be a dependence graph [meaning RDG] specifying a SURE defined over F_n [the positive orthant]. Then the function a_k(p) is explicitly defined iff G does not have a path from v_k to any vertex v_l contained in a nonpositive cycle.
Ambiguity in the statement of theorem1 (in KMW): The statement of the theorem is a little ambiguous and cannot be disambiguated easily in particular, by reading the statement without context. The first meaning is obtained by associating the clause "contained in a nonpositive cycle" with path in the following way: "... G does not have a path, from v_k to any vertex v_l contained in a nonpositive cycle". The other interpretation is to associate the clause "contained in a nonpositive cycle" with the vertex v_l in the following way: "... iff G does not have a path from v_k to any vertex v_l contained in a nonpositive cycle".
Disambiguation of the statement of theorem 1 (in KMW): Method 1: just reading the statement: If we associate the clause with "path", then v_l seems to be redundant in the theorem. On the other hand, if we associate the clause with vertex v_l, then everything falls into place, there is no redundancy in the definition, and there is a more precise definition of the path. Method 2:reading the first line of the proof: The first line of the proof says "Suppose there is a path pi from v_k to v_l and a nonpositive cycle C including v_l as shown in ....". This means that (i) v_l is in a nonpositive cycle (ii) there is a path from v_k to such v_l.
A possible better wording for theorem1: If you donot like the statement of theorem because of the above ambiguity and also the idea of a cycle being 'out of a vertex' is kind of ugly, use the word: reachable. However, it is more precise talking about the explicit-definition of a vertex, rather than the computability of a system. The reason is that some of the vertices of the RDG may not be explicitly defined, but others may be explicitly defined. rewording: A variable a_k of the SURE is said to be explicitly defined if in the RDG of the SURE, no cycle of non-positive weight is reachable from the vertex corresponding to a_k.
[A better statement would be the following: Any vertex which 'participates' in a non-positive-weight cycle is not explicitly defined. Any vertex that has a path to another vetex that 'participates' in such a cycle is not explicitly defined. The maiincrib about this statement is the use of the word 'participate'.]
[Darte-Vivien divide the theorem into two parts, corollary 3 and theorem 17.]
The different kinds of statements of computability from DV/KMW -- The equivalence of three (many?) things: There equivalence of the following things is being talked about: (i) cycle of nonpositive weights in RDG G (ii) incomputability of the SURE S (iii) path of infinite length directed out of vertex (i,p) in EDG Gamma (iv) not every variable of the SURE to be explicitly defined (v) absence of a schedule.
Darte-Vivien's equivalences: In DV, the equivalence of (ii) and (iii) is by definition (and the existence) of free schedule and also by corollary 3. What about the equivalence of rest of the things in DV?
KMW's equivalences: In KMW, the equivalence of (iv) and (ii) is by definition of computability (remember, KMW donot use the word computability). Also, the equivalence of (v) and (ii) is also by definition of computability and schedule. KMW bring lemmma 1 into context because, it gives the equivalence of "absence of explicit " and "presence of infinite length paths": namely the equivalence of (iv) (or even (v)) and (iii).
[All this is required? Yes. The equations are a simple description of the input. We have some associated questions on the input which we want to answer in finite time. The computability problem of the SUREs maps directly to checking for intinite length paths in the EDG. Direct checking is not a feasible way. We map the problem to checking for positive weight cycles in the RDG.]
DV: Corollary 3: The equivalence between (ii) and (iii) is made. The statement: "A SURE is computable iff whatever the vertex (i,p) in Gamma, there is no infinite path in Gamma directed to (i,p). "
Darte-Vivien's statement of the theorem 17: Let G be the RDG of a SURE S defined over F_n (the +ve orthant as domain for all variables). S is computable iff G has no cycle of non+ve weight i.e., w(C) <= 0.
KMW's proof strategy: The theorem statement talks about equivalence of (i) and (iv). KMW have however stated on page 566, the equivalence between the existence of a schedule and each variable of the SURE being explicitly defined (meaning they have the equivalence of ??? ). So they prove theorem 1 by proving the equivalence of (i) and (iii).
Darte-Vivien's proof strategy: The theorem statement talks about equivalence of (i) and (ii). Darte-Vivien have however proved in corollary 3, the equivalence of (ii) and (iii). So they prove theorem 3 by proving the equivalence of (i) and (iii).
KMW statement of corollary 1/2: From the outside, it may look that KMW's cor.1/2 and the statement of Theorem 18 from DVR are different. Howwver, They are the same and KMW donot miss any trick.
Corollary 1: In corollary 1, KMW say that
[just to remember: we are proving the equivalence of (i) = "absence of a cycle of nonpositive weight in G" and (iii) = "absence of a path of infinite length directed out of vertex (i,p) in Gamma". Actually, we are proving the contrapositive: (i)="presence of a cycle of nonpositive weight in G" and (iii)="presence of a path of infinite length directed out of vertex (i,p) in Gamma".]
The proof: (i) => (iii): method induction: If there exists a cycle of nonpositive weight in G, then exists a path of infinite length directed out of some vertex (i,p) in Gamma. Assumption: p, p-w_j for all 1 <= j <= k are in G_n (all these are valid labels for lattice points in the positive orthant). Given: there exists a cycle of nonpositive weight in G => Let i and j be two (not necessarily different) vertices in G. Let the weight of the cycle be w1 as i to j and w2 from j to i. w1 + w2 is a nonpositive vector. Now, ......??? ?????
[Punch line of the proof: w(C)<=0 which means that there exists a ll such that (ll,p-w(C)) is reachable from (i,p). So we can repeat the above procedure ad-infinitum, or give an inductive proof.]
[The statement of the only-if part talks about (iv)=>(i). KMW use the definition of explicit-definition of a variable to say that (iv) is equivalent to (iii). Also, they use lemma 1 to show that (iii) is equivalent to the existance of a specific infinite path.]
The proof: (iii) => (i): There exist an infinite path. We can select a infinite subsequence of the infinite path (i,p) such that the 'p' is non-decreasing, first in the first coordinate, next in the second coordinate etc. This is a list of infinite length [this is because, if it were not, the list is of finite size: ]. It is a cycle, as the coordinates 'i' have to repeat, by pegion-hole principle. This is a cycle of +ve weight, as the p is non+ve.
Possible bug in Darte-Vivien's statement/proof of theorem 17: Darte-Vivien use n differently in the proof of theorem 3: In the theorem statement, n is used as a superscript of mathcal{N} signifying the dimension of the input. In the inductive proof for the "if part", DV use n again -- this time as a variable for induction -- which could result in confusion. A better way is to use alpha, as KMW use.
===========================
My statement of the above theorems: Let S be a SURE. with G as its RDG and its Gamma as its EDG (with dependence edges). The following are equivalent: (A) S is computable. (B) G does not have a vertex v which belongs to a path of infinite length (or every vertex of G is explicitly defined) (C) No vertex in the EDG Gamma has a path of infinite path out of it (into it?).
============================
Proof of Darte-Vivien's theorem17: if part (suppose there is a cycle of non+ve weight. then the SURE has an infinite path ending in ......)
Comment about DV's theorem's 17-18 (or even KMW's theorem 1 and corollary's): Though the statement for the incomputability of a SURE defined over F_n is relatively more interesting, the pragmatic view seems to be to talk about the computability of a SURE defined over a bounded domain (so that we restrict our discussion on just for loops here: see the remark about while loops later). In order to remove the cases when the RDG is computable for some domain sizes and not for others, its better to talk about the incomputability of SURE over any bounded domain. DV and KMW differ here a little. DV talk about the computability of a SURE defined over the families of any finite size domains.OTOH KMW talk about the computability of SUREs defined over strips of F_n (intuitive meaning defined below).
[corollary 1 of KMW talks about the extension of theorem1 to strips of F_n]
Meaning of strips: KMW use the notation Q_t * F_{n-t} to mean the following. (The implicit assumption is that t <= n.) In each of the t dimensions, the set of coordinates in those t dimensions is from a finite set. In the other n-t dimensions, the sizes of the coordinates is not of a finite set.
[idea of KMW's proof of corollary1: Draw a RDG G' in which the vertices are from {1, ... , n} * Q_t. This is a finite graph and can work as the RDG. Now apply theorem1 to the EDG induced by this RDG.]
Corollary 2:
Question about the strips and the scheduling of while loops (n-t while loops out of n dimensional space): Given a n dimensional SURE with only t dimensions are from a fiite set, can the loops be scheduled so that the performance of the overall code be improved? What is the best schedule for the code? What is the best memory allocation for the code?
[KMW talk about strips of F_n in corollary 1 and 2. Darte-Vivien's statement of theorem and its proof are the same as that when t = n; or, when the SURE is defined in a finite domain.]
KMW's corollary 1 of theorem1: Let G be the dependence graph of a SURE defined over R=Q_t * F_{n-t}. Then a_k(p) is explicitly defined iff there donot exist l in {1, ... , m} and p,q,r in R such that (i) (k,p) -> (l,q) -> (l,r) (ii) the vector q - r is zero in the coordinates corresponding to Q_t and nonpositive in the coordinates corresponding to F_{n-t}.
Ambiguity in the statement of KMW-corollary 1: As stated in KMW, corollary (i) talks about the SURE, the EDG and the RDG at the same time. OTOH, corollary 2 talks about only the SURE and the RDG, just as in the spirit of theorem 1. Darte-Vivien remove the need for this type of reasoning by giving "their corollary 3" apriori.
[See the reasoning above which states that the statement of theorem1 is ambiguous. In the samw way, corollary 2 also is ambiguous.]
Questions about strips: Give a statement of computability of an EDG defined over a skewed strip like {i-j <= 10; i-j >= 5; i >= 0; j <= 0}
Variant of theorem about UREs for bounded domains
=======================================
Section 4: The theorems for URE
Notation: Semi positive: a vector q is semi positive if q != 0 and q_i >=0.
Theorem 2: It gives the conditions for the computability of a URE. Basically, it frames the computability problem of a URE as a LP problem and some statements of the theorem are equivalent by Farkas lemma.
In more detail, (i) and (ii) are equivalent by theorem1. Rest by Farkas lemma and duality of the LP.
Examples of separating hyperplanes on page 570:
page 571: for a URE, we can index the function T by just T: m(p) and T(p): remember that
Theorem 4:
Amount of Parallelism (the same as phi_s(tau)): There exists a schedule S such that sup_tau phi_s(tau) = inf.
Intuitive meaning of amount of parallelism:
Notation: sup and inf: According to this link, supremum (aka sup) means least upper bound. infimum (aka inf) means the greatest lower bound. (sup and inf are defined for sets.) The supremum and infimum of a set need not belong to the set.
Storage Requirements for a URE:
sigma_s (secondary objective function??) For an URE, it is the number of computed values that have to be retained at a computation time tau so that other points are computed.
Theorem 5: Memory optimization for a URE: If there exist two (dependence) vectors w_i and w_j which are linearly independent, then there can be no optimization of memory. This is a strong statement because, it applies for any schedule.
What if the dependences are the set (0,1) and (1,0)?
Intuitive meaning of the amount of storage requirements (taken from page 575): Except for special cases, the amount of storage required to compute the function a(p) is unbounded.
=========================
Algorithm not given? (page 580): foot note about constuction of G' It seems that KMW do not give an explcit algorithm for the constuction of G'. They also donot give the running time of the algorithm. I doubt that the method of measuring algorithm by their running time (by Karp/Edmonds/Hartmanis) completed by then?
Page 582: Parallelism: What do KMW mean when they say that they have not solved the problem completely.
Section 5: SUREs
Amount of Parallelism of SUREs when compared with UREs (p577): As shown in theorem The main idea is that there exist explicitly defined systems with n>1 for which free schedule has bounded parallelism. It is not vert clear why only one point of the iteration space can be computed at any time.
Questions about example 6, page 578: Why is are self-dependence loops labelled in a strange way? Also why do KMW seem to imply that this fig.5 can have only sequential schedules? Also, look at their notes for the example when they talk about the free schedule.
Theorem 7: Properties of the subgraph similar to the theorems in DV.
Theorem 8 (page 583):
Storage of SUREs: p 584:
Section 6 (p 588): Implicit schedules
Implicit schedules Vs. Explicit Schedules (page 588):
A Simple preprocessing step (using Euler's theorem) : The KMW decomposition algorithm is searching for union of cycles. We have Euler's theorem that a connected directed graph has a Eulerian Cycle iff each vertex has equal in and out degrees. We can apply this theorem and remove any node v whose indegree is not equal to its outdegree. IS THIS RIGHT? What do do with the hypergraph? What to do with the bipartite graph? What to do with non-simple cycles(remember, Euler;s theorem applies to simple cycles)?
Should we try for free schedule of the hypergraph?
Posts
No comments:
Post a Comment