In Practical Foundation of Programming Languages by Harper (www.cs.cmu.edu/~rwh/pfpl/2nded.pdf),

37.3 Multiple Fork-Join

So far we have confined attention to binary fork/join parallelism induced by the parallel let construct. A generalizaton, called data parallelism, allows the simultaneous creation of any number of tasks that compute on the components of a data structure.

There are two expressions:

seq(e_0 , . . . ,e_{n−1} )     sequence
cat(e_1 ; e_2 )     concatenate

In the cost dynamics,

enter image description here enter image description here

  • (37.9a) indicate that evaluation of a seq expression (forming a sequence from the n elements e_i's) can be parallelized betwen the n elements.

  • (37.9f) , evaluation of a cat expression (concatenate two sequences e_1 and e_2) first evaluates e_1 and e_2 to two sequences, and then consolidate their elements into one result sequence. Why are evaluations of e_1 and e_2 to two sequences not in parallel with each other?


  • $\begingroup$ Reading the description it looks like it is modeling multiple fork and join. Hence seq is forking multiple tasks and cat acts as joining all those. Hence tasks in the first seq would all have to be completed before the tasks in second seq would be performed. Thus they cannot be in parallel. $\endgroup$ – Apoorv Ingle Nov 18 '19 at 17:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.