In the Fibonacci example, the sync statement in line 5 is required before the return statement in line 6 to avoid the anomaly that would occur if x and y were summed before each had been computed. When all of its children return, execution of the procedure resumes at the point immediately following the sync statement. If any of its children have not completed when it executes a sync, the procedure suspends and does not resume until all of its children have completed. In general, the parent can continue to spawn off children, producing a high degree of parallelism.Ī procedure cannot safely use the return values of the children it has spawned until it executes a sync statement. In this case, the parent goes on to spawn Fibonacci(n-2). Unlike an ordinary function call, where the parent is not resumed until after its child returns, in the case of a spawn, the parent can continue to execute in parallel with the child. Spawn before the subroutine call in line 3 indicates that the subprocedure Fibonacci(n-1) can execute in parallel with the procedure Fibonacci(n) itself. The keyword spawn is the parallel analog of an ordinary subroutine call. I put the most important keywords in bold. (A thread is defined to be a maximal sequence of instructions not containing the parallel control statements spawn, sync, and return, not something like Java threads or Posix threads.) # classical algorithms that compute Fibonacci numbers # this is a really bad algorithm, because it's Here is a multithreaded algorithm that computes Fibonacci numbers:
It's easiest to understand this model with an example. The lecture starts with an introduction to a particular model of parallel computation called dynamic multithreading. It then goes into great detail to analyze the running time and parallelism of these algorithms.
Lecture twenty-one implements several multithreaded algorithms, such as n xn matrix addition, n xn matrix multiplication, and parallel merge-sort. Lecture twenty begins with a good overview of multithreaded programming paradigm, introduces to various concepts of parallel programming and at the end talks about the Cilk programming language. These lectures cover the basics of multithreaded programming and multithreaded algorithms.
#Strongsync review series#
This is the thirteenth post in an article series about MIT's lecture course " Introduction to Algorithms." In this post I will review lectures twenty and twenty-one on parallel algorithms.
0 kommentar(er)
