Timeline for Parallel prefix sum/scan on trees
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 22 at 19:25 | history | edited | Patrick Nicodemus | CC BY-SA 4.0 |
Made the question more focused and specific
|
| Feb 22 at 5:14 | answer | added | Gaslight Deceive Subvert | timeline score: 1 | |
| Feb 21 at 21:49 | comment | added | Patrick Nicodemus | @StandwithGaza That is correct, $T^*$ is the same shape/structure as $T$. I meant to convey this in the question with the wording "$T^*$ is isomorphic to $T$" but I apologize if this was unclear. | |
| Feb 21 at 15:42 | comment | added | Gaslight Deceive Subvert | What shape does $T^*$ have? Isn't it the same structure as $T$ just with other node values? It seems to me that you "just" want the prefix sum of the bottom-up traversal of the tree. | |
| Feb 20 at 22:49 | comment | added | Patrick Nicodemus | I don't know. Thank you for the suggestion, I will look into it, heeding your caveat that it may not be applicable after all. | |
| Feb 20 at 22:22 | comment | added | D.W.♦ | Can this be formulated as a job scheduling problem, i.e., $P|p_i=1,\text{tree}|C_\max$? See e.g. Hu's algorithm. This doesn't take into account the memory hierarchy or locality, though, so might be unhelpful in practice. I don't know much about this topic so I apologize if this direction is not useful or is missing the point. | |
| Feb 20 at 19:03 | comment | added | Patrick Nicodemus | We have a fixed graph $G$ and $T$ is a spanning tree for $G$. The algorithm operates in stages, at each stage $T$ is replaced with a better solution $T'$. We know the number of nodes and edges of $T$ at compile time but the topology of $T$ changes every iteration of the loop. $T'$ differs from $T$ only by severing one edge and joining another, so if a representation of $T$ carries additional information about its topology such as the depth of each node or a given traversal it may be possible to compute that of $T'$ efficiently from this. | |
| Feb 20 at 18:21 | comment | added | D.W.♦ | Is the shape of $T$ known at compile time or only at runtime? (i.e., does it change each time you want to run the algorithm?) | |
| Feb 20 at 18:14 | history | asked | Patrick Nicodemus | CC BY-SA 4.0 |