Wednesday, June 15, 2005

Some questions on KMW and TUM matrices

These are some questions related on KMW and TUM.
  • The uniformization problem of Darte-Vivien: Take a PRDG with possibly non-uniform dependences and uniformize the graph so that all dependences in the graph are uniform (constant vectors). How can you answer the computability and scheduling problems of the original graph using the transformed graph?
  • The unitarization problem: Suppose we unitarize the input PRDG so that all components of dependence vectors are from the set {+1,-1,0}? How can you answer the computability/scheduling queries of the original graph using the unitarized graph? How can you use TUM property for this? How is the presence of null weight cycles in the new PRDG related to its TUMness? The size of the unitarized graph, measured in number of nodes/edges, could be exponential in the number of bits used to encode the problem!!! This is because its size dependences on the weights of the original graph, not just the nodes or vertices of the original graph. The proposed unitarization may not be the only way in which we obtain a resultant unitarized-PRDG. We may be able to compress it. Can we just look at the actual nodes of the program, keeping aside the virtual nodes and reason about the computability? Since the depencence distances are in the set {+1,-1,0}, what we have is a kind lattice with edges of unit distance. Even if we forget that its size is large, how do you determine its computability? Let M be the matrix. The computability question is answered very simply by answering the question "Is Mx = 0 for all x?
    --
    This question is exactly equivalent to asking:"Is M a TUM matrix?" this does not seem right
  • How do you frame the problem of looking for null weight cycles as searching of the matrix is TUM?
  • Darte-Vivien's block matrix B has two parts, the top part describing the graph without dependences and the bottom part describing just dependences without directions on the edges. The top part is clearly TUM. How to get a TUM graph from the bottom part?
  • Or, how to reason about TUMness of B?
  • The self loops can be handled by adding dummy variables.
  • What has unschedulability of SURE with mono-dim time scheduling have to do with TUMity?
  • What has strongly and weakly separating hyperplanes got to do with TUMity?
  • What does null weight cycle mean for TUM?
  • What does the dual of the matrix mean in terms of TUM?
  • What does longest path mean in terms of TUM?
  • No comments: