tag:blogger.com,1999:blog-11807812.post5825711712712930534..comments2023-05-29T08:58:13.381-04:00Comments on Recycled Knowledge: Concurrency vs. parallelismJohn Cowanhttp://www.blogger.com/profile/11452247999156925669noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-11807812.post-8345907010754598742014-08-08T22:50:19.857-04:002014-08-08T22:50:19.857-04:00Now you have me completely confused. Take everyone...Now you have me completely confused. Take everyone's favourite parallel program: quicksort. What do you consider its concurrency, and why is it trivial?<br />Anonymoushttps://www.blogger.com/profile/07475966336949108276noreply@blogger.comtag:blogger.com,1999:blog-11807812.post-85912592757594540032014-08-08T22:47:13.839-04:002014-08-08T22:47:13.839-04:00Rigor is not my department.
Parallel programs are...Rigor is not my department.<br /><br />Parallel programs are technically concurrent, but for the most part, their concurrency is trivial. John Cowanhttps://www.blogger.com/profile/11452247999156925669noreply@blogger.comtag:blogger.com,1999:blog-11807812.post-3227609922209168212014-08-08T15:37:53.632-04:002014-08-08T15:37:53.632-04:00I'm not sure that that answers my question.
I...I'm not sure that that answers my question.<br /><br />Is parallelism a subset of concurrency? Is it the other way around?<br /><br />Can you define either concept? <br /><br />I think those nouns are not definable, but we can define the adjectives "concurrent" and "parallel". But I'm not sure what they apply to. Is an algorithm concurrent? Is a program concurrent? Is the execution of a program concurrent?<br /><br />I would really appreciate a sort-of rigorous definition.Anonymoushttps://www.blogger.com/profile/07475966336949108276noreply@blogger.comtag:blogger.com,1999:blog-11807812.post-81414887147070223022014-08-08T15:15:02.576-04:002014-08-08T15:15:02.576-04:00Actually, you'd get only trivial speedup or no...Actually, you'd get only trivial speedup or none at all at all unless the files were on different disks attached to different disk controllers. If so, that would be the source of the parallelism. Assuming the files were on the same disk, the only gain would be from avoidance of context-swapping on the single CPU, which might be overwhelmed by the cost of locking communication buffers. Pipelines can always be executed in parallel, but only some of them gain thereby: consider a similar three-stage pipeline in which the middle stage reverses the order of inputs.<br /><br />It is not known whether any problems are inherently sequential, but it's suspected that addition of arbitrarily large integers is. It could be performed concurrently with one process per digit, but each digit must feed a carry into the next digit to the left, making parallel execution useless.John Cowanhttps://www.blogger.com/profile/11452247999156925669noreply@blogger.comtag:blogger.com,1999:blog-11807812.post-4469594050780486122014-08-08T15:04:06.757-04:002014-08-08T15:04:06.757-04:00Your pipeline could also be executed by three proc...Your pipeline could also be executed by three processes running in parallel. After a little startup for filling the pipeline you'd get a decent speedup, of course depending on the granularity of the three activities.<br /><br />So that example does not distinguish between concurrency and parallelism.<br /><br />You say that regular expression matching is not parallel. Is it concurrent? I'm guessing not.<br /><br />So I still don't see the difference between concurrent and parallel. Every parallel program is concurrent, and every concurrent program can be done in parallel, right?Anonymoushttps://www.blogger.com/profile/07475966336949108276noreply@blogger.comtag:blogger.com,1999:blog-11807812.post-36016673812653673962014-08-08T14:55:24.965-04:002014-08-08T14:55:24.965-04:00By "conceptually simultaneous" I mean th...By "conceptually simultaneous" I mean that we understand or imagine concurrent processes as if they executed truly simultaneously. Consider a simple pipeline of three stages: one that reads from a file and breaks it into lines, writing each line to its output, one that changes all upper-case letters in each input line to lower case, and one that writes its input lines to a file. These can execute serially on a single processor, but constitute a concurrent program with three loops. It would be possible to write this program without concurrency, for example by using an event loop handling events like "Block successfully read from file" and "Block successfully written to file", but it would be far harder to understand.<br /><br />Consider adding up the rows of a matrix of size 8 x N on an 8-core CPU. This can execute entirely in parallel because of the limited form its concurrency takes; it is a so-called <i>embarrassingly parallel problem</i>. In particular, there would be no point in making it concurrent if parallel executing engines were not available. The upper casing example above can be executed in parallel as well by taking separate parts of the input and writing to separate parts of the output, with a gain in speed (which is the point of parallelism).<br /><br />Some problems gain no speedup from parallelization: matching regular expressions is one of them.John Cowanhttps://www.blogger.com/profile/11452247999156925669noreply@blogger.comtag:blogger.com,1999:blog-11807812.post-19570420552658513992014-08-08T14:31:40.895-04:002014-08-08T14:31:40.895-04:00Can you define your terms?
"Concurrency ref...Can you define your terms? <br /><br />"Concurrency refers to conceptually simultaneous execution." What does "conceptually simultaneous" mean? <br /><br />"We usually speak of concurrency when there is interaction between the concurrent components." Any but the most trivial parallel programs have interaction between the components. How does this distinguish parallel from concurrent?<br /><br />Can you give an example of a parallel program that is not concurrent? One that is concurrent but not parallel?Anonymoushttps://www.blogger.com/profile/07475966336949108276noreply@blogger.comtag:blogger.com,1999:blog-11807812.post-69606998106545073622012-04-06T23:54:19.699-04:002012-04-06T23:54:19.699-04:00Juggling is completely deterministic.Juggling is completely deterministic.John Cowanhttps://www.blogger.com/profile/11452247999156925669noreply@blogger.comtag:blogger.com,1999:blog-11807812.post-684992405556081942012-04-05T17:17:15.782-04:002012-04-05T17:17:15.782-04:00Some will not accept your definitions until you al...Some will not accept your definitions until you also include non-determinism; specifically, that concurrency is inherently non-deterministic.Barry Kellyhttps://www.blogger.com/profile/10559947643606684495noreply@blogger.com