<p>Consider computation represented as a DAG, without if-then-else conditions, where nodes represent tasks and edges represent data dependencies. For example, A-&gt;B-&gt;C means that there are 3 tasks and B and C depend on A and B, respectively. The graph can be more complicated and may admit to parallel computation, such as the following:</p>
<p><a href="https://i.sstatic.net/4BzE1.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/4BzE1.png" alt="enter image description here" /></a></p>
<p>This is fine. Now, in the <a href="https://eprint.iacr.org/2013/525.pdf" rel="nofollow noreferrer">paper</a> that introduces the Catena password hashing scheme, it's said that:</p>
<p><a href="https://i.sstatic.net/zd6Zd.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/zd6Zd.png" alt="enter image description here" /></a></p>
<p>If the shared memory already contains vertices that correspond to edges which connect the <span class="math-container">$\pi$</span> graphs, then, the DAG can be computed in parallel.</p>
<p>However, to compute the vertices of those cross-edges, a sequential pass over some of the subgraphs may be necessary - if we take a graph A-&gt;B-&gt;C-&gt;D-&gt;E and split it into A-&gt;B-&gt;C and D-&gt;E to try to compute it in parallel on two CPUs, the first step (as outlined by the paragraph) will require computing C and placing it in the shared memory. However, at that point, the parallel computation doesn't appear to provide any benefit, can we really talk about the ability of computing that DAG in parallel? The time is already spent to compute C and the time spent is basically the same as if it was computed sequentially on a single CPU. What am I missing here?</p>

CC BY-SA 4.0
2022-12-01T06:00:02.400Z
1. Please provide a proper citation for the paper you are copying from.  2. I assume you are aware of the distinction between the latency to receive an answer vs the total amount of work/energy spent?
D.W.
CC BY-SA 4.0
2022-12-01T14:23:55.023Z
Edited to include the full reference to the paper. I am vaguely aware of the distinction between latency and total energy spent, but notions such as the AT cost is not fully clear to me, I'm not sure if that plays a role here though.
anon2328
CC BY-SA 4.0
2022-12-03T00:42:52.967Z
Looking at this again, I believe this is more about "sequential memory hardness" (as defined in the original scrypt paper) than about the usual notion of parallel computation: "Catena can be at least partially computed in parallel, which is a contradiction to the def. of sequential mem. hardness"
anon2328
<directed-acyclic-graph><parallel>
Unclear explanation of basic parallel DAG computation
anon2328
# Unclear explanation of basic parallel DAG computation

(Asked by: username_0 on 2022-12-01)

Consider computation represented as a DAG, without if-then-else conditions, where nodes represent tasks and edges represent data dependencies. For example, A->B->C means that there are 3 tasks and B and C depend on A and B, respectively. The graph can be more complicated and may admit to parallel computation, such as the following:

[![enter image description here](https://i.sstatic.net/4BzE1.png)](https://i.sstatic.net/4BzE1.png)

This is fine. Now, in the [paper](https://eprint.iacr.org/2013/525.pdf) that introduces the Catena password hashing scheme, it's said that:

[![enter image description here](https://i.sstatic.net/zd6Zd.png)](https://i.sstatic.net/zd6Zd.png)

If the shared memory already contains vertices that correspond to edges which connect the $\pi$ graphs, then, the DAG can be computed in parallel.

However, to compute the vertices of those cross-edges, a sequential pass over some of the subgraphs may be necessary - if we take a graph A->B->C->D->E and split it into A->B->C and D->E to try to compute it in parallel on two CPUs, the first step (as outlined by the paragraph) will require computing C and placing it in the shared memory. However, at that point, the parallel computation doesn't appear to provide any benefit, can we really talk about the ability of computing that DAG in parallel? The time is already spent to compute C and the time spent is basically the same as if it was computed sequentially on a single CPU. What am I missing here?

**Tags:** directed-acyclic-graph, parallel
> **Comments:**
> **username_1**: 1. Please provide a proper citation for the paper you are copying from.  2. I assume you are aware of the distinction between the latency to receive an answer vs the total amount of work/energy spent?  
> **username_0**: Edited to include the full reference to the paper. I am vaguely aware of the distinction between latency and total energy spent, but notions such as the AT cost is not fully clear to me, I'm not sure if that plays a role here though.  
> **username_0**: Looking at this again, I believe this is more about "sequential memory hardness" (as defined in the original scrypt paper) than about the usual notion of parallel computation: "Catena can be at least partially computed in parallel, which is a contradiction to the def. of sequential mem. hardness"  

---

## 0 answers

