All geek questions in one place

Range and parallel loop

I have problems understanding dynamic multithreading. I have the following algorithm:

Page 16, MAT-VEC http://mitpress.mit.edu/books/chapters/0262033844chap27.pdf

And in the text they say that "for MAT-VEC on an nxn matrix, the parallel initialization loop in lines 3-4 has span theta (log n)"

And why my question? I'm confused. Therefore, if someone can explain what they mean, it will be a big help.

+6
source share
1 answer

First of all, the definition of "span" for those who do not know this is the length of the critical path. If you had an infinite number of processors, the range determines the minimum amount of time that it may take to complete the algorithm.

To start a loop that has N iterations, the shortest way to do this is to spawn threads until there are N of them, then each of N threads will do one unit of work. Here's how it works to create 8 threads:

  time 0: thread0 spawns thread1
 time 1: thread0 spawns thread2, thread1 spawns thread3
 time 2: thread0 spawns thread4, thread1 spawns thread5, thread2 spawns thread6, thread3 spawns thread7
 time 3: all 8 threads perform their task

This took 3 units of time, with everything working in parallel to create 8 threads. Since lg(8) = 3 , the interval of the algorithm is Θ(lg n) .

+6
source

Source: https://habr.com/ru/post/887496/

More articles:


All Articles