r/computerscience • • Sep 29 '20

Help Learning Multithreaded Algorithms. Can somebody please explain to me what the continuation edges represent?

Post image
184 Upvotes

15 comments sorted by

15

u/[deleted] Sep 29 '20

Continuation edges represent the continuation of the procedural call function for the threads befor the return calls so if the procedure continues without another spawn or fork then it will return right after? P.S: please stay inside πŸ˜‚πŸ˜‰

8

u/meloly4 Sep 29 '20

So does it represent that the return statement comes after sync?

4

u/[deleted] Sep 29 '20

Yeah I think that's what it is it represents the syncing of threads

3

u/meloly4 Sep 29 '20

Do you know what's the span of the computation in this case?

3

u/[deleted] Sep 29 '20

8

It says it in the text above its the connecting circles with the highlighted edges.

22

u/Realteamjon Sep 29 '20

This could give aspirin a headache

0

u/[deleted] Sep 29 '20

[deleted]

2

u/[deleted] Sep 30 '20

[removed] β€” view removed comment

1

u/DreadedMonkey Sep 30 '20

I wouldn't. When it takes a 1000 words (or a slab of text as big as the diagram itself) to explain a diagram you're doing something wrong. It's hard not to rant at this kind of thing which is unfortunately prevelant in academia.

But if you're desperate then use tikz. Some folk use packages such as inkscape and export to svg. There's a latex sub and stackoverflow too.

5

u/thetrailofthedead Sep 29 '20

Can someone explain the concept to a 2nd year student who has never seen this type of thing?

It looks like a recursive function, one that "splits" off 2 more calls that can be executed simultaneously before "meeting" back up where they are called from?

The critical path is simply the longest continguous chain that must be executed?

How do you write something like this?

31

u/the123king-reddit Sep 29 '20

Can someone explain this to a CS graduate of 10 years?

6

u/LabLambReddit Sep 29 '20

You use a threading API of given language, some might not have it. I don’t know how to write that in Assembly, though.

2

u/Abchid Sep 29 '20

Based only on the fact that under every box it says fib-x, and it seems connected to lower numbers when you move downwards, I think it's a way to represent the Fibonacci formula, but I can't understand how it's supposed to be read, so I can't give an explanation

4

u/[deleted] Sep 29 '20

Book name ?

7

u/pseudopodia_ Sep 29 '20

"Introduction to Algorithms" commonly called CLRS

2

u/[deleted] Sep 30 '20

Seems like continuation edge represents creation of thread which can be run parallely. For example, continuation edge for P-Fib(4) represents creation of thread which will execute P-Fib(2). The spawn edge from that shaded circle represents actual execution of P-Fib(2)