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:
- 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).
- 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)).
- 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).
- 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