-4
$\begingroup$

Given a DAG (which represents DDG – each node is a operation the in-edge/s show the operands from which inputs are taken) I want to obtain its compact representation of the graph, in such a way that:

  1. Each node is mapped to the cell.(To the some cell several nodes can be mapped) The communication is exists between cells in 4-neighbors(adjacency).
  2. In the example below node I get “results” (as operands) from nodes C and E and we can see that they were mapped in the proper way (4-neighbors(adjacency)).
  3. The result from each operation is transformed in 4-neighbors(adjacency). It means (in the below example) that after cell 1 has calculated C the operation result maybe used by cell 2 (And ofcourse it maybe used by cell 1 also).
  4. The motivation is to execute the operations in parallel in minimum time and in minimum cells.Each Cell can execute one node at a time

(The graph drawing I get using bary-center algorithm for cross-edges minimization, I think this information can help while the mapping is performed…)

4-neighbors(adjacency)-Only adjacent cells can use information from each other.So for example to do "I" task the cell that executed C and D should be adjacent. More at http://books.google.com/books?id=fGX8yC-4vXUC&lpg=PA24&dq=%2C4%20adjacency%2C&pg=PA23#v=onepage&q=%2C4%20adjacency%2C&f=false-

Can you give some advice for such mapping algorithm?

Thank you in advance alt text

Improve this question
$\endgroup$
19
  • 3
    $\begingroup$ Your question is bordering on incoherent, I'm sorry to say. What do you mean by a compact representation ? and how does the table you drew satisfy the requirements. While examples are helpful, they cannot replace a FORMAL description of the problem, and you don't have that. Please don't add more description - try to make your question PRECISE $\endgroup$
    – Suresh Venkat
    Commented Jan 17, 2011 at 18:35
  • $\begingroup$ But I have explained what do I mean by "compact" and table representation in 1,2,3.Could you explain what is not clear?.You may remove word "compact" it will not change the question $\endgroup$
    – YAKOVM
    Commented Jan 17, 2011 at 18:39
  • 3
    $\begingroup$ I'm recommending closing this question. It's not our job to divine user intent from am incoherent question, and there are numerous examples on the site of actual good questions. $\endgroup$
    – Suresh Venkat
    Commented Jan 17, 2011 at 20:50
  • 1
    $\begingroup$ I might have agreed with Jon if a calm and careful reading were really all that’s needed to understand this question. $\endgroup$
    – Tsuyoshi Ito
    Commented Jan 17, 2011 at 23:51
  • 1
    $\begingroup$ Nope. Still incoherent. In particular, the word "execute" still does not appear in the question, so my previous objection still stands. I honestly have no idea what "the operation result has transformed to the cell 2" is supposed to mean. @Jon: If a simple question really is hiding here, perhaps you could help @Yakov clarify it? $\endgroup$
    – Jeffε
    Commented Jan 18, 2011 at 22:57

1 Answer 1

Reset to default
5
$\begingroup$

This is simple. You have basically a Hasse diagram on which you need to perform a topological sort to determine the order in which to complete a set of tasks, some of which depend on others. Each subset of the tasks for which order is not significant can be executed in parallel. You can divide these into your "cells" (threads?) however you please.

So, for example, based on the graph you gave, you ought to get a list of sets:

{C, A, B}, {I, E, F, G}, {K, L, H, J}, {D}

Each set contains all tasks that must be completed to fulfill the prerequisites of the tasks in the next set, and all tasks in a set can be executed simultaneously.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Judging from the example in the question, I do not think that this is what is being asked. However, I have no idea what is being asked. $\endgroup$
    – Tsuyoshi Ito
    Commented Jan 17, 2011 at 23:38
  • $\begingroup$ @Tsuyoshi Ito: My reasoning about it comes from how he divided the tasks into cells. If you read first from Cell 1, then 2, then 3, then back to 1 and so on, you get (C, A, B, I, E, F, K, H, G, D, L, J), which is a valid topological sort of the graph. And the cells can easily represent threads, because each set of three tasks in that sort can be carried out in parallel. It doesn't work quite so neatly for all graphs, but still, that seems to be the fundamental problem at work here. $\endgroup$
    – Jon Purdy
    Commented Jan 18, 2011 at 3:58
  • $\begingroup$ @Jon.Thank you.Please could you explain how can I sort those tasks to the cells so it will answer my conditions(for ex. 4 neighbors ) $\endgroup$
    – YAKOVM
    Commented Jan 18, 2011 at 6:44
  • $\begingroup$ @Yakov: I'm afraid I still don't understand what you mean by "4-neighbours". Do you have a grid, some of whose cells are connected to form a graph, that puts some constraint on the order of the output? $\endgroup$
    – Jon Purdy
    Commented Jan 18, 2011 at 6:59
  • $\begingroup$ books.google.com/… Here is an explanation.Only adjacent cells can use information from each other.So for example to do "I" task the cell that exucuted C and D should be adjacent. $\endgroup$
    – YAKOVM
    Commented Jan 18, 2011 at 7:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.