跨度和并行回路 [英] span and parallel loop

问题描述

了解动态多线程问题我有问题。我有以下算法：

第16页，MAT-VEC
http://mitpress.mit.edu/books/chapters/0262033844chap27.pdf

在文中他们说for MAT-VEC在nxn矩阵中，第3-4行中的并行初始化循环具有跨度theta（lg n）

我的问题是为什么？我很困惑。那么如果有人能解释什么意思，那将是一个很大的帮助。

解决方案

首先，span的定义对于那些不了解它的人来说，关键路径。如果您拥有无限数量的CPU，则跨度定义了完成算法所需的最短时间。

为了运行具有N次迭代的循环最简单的方法是产生线程，直到有N个线程，然后N个线程中的每一个执行一个工作单元。以下是如何产生8个线程：

 
时间0：thread0生成thread1 
时间1：thread0 spawns thread2，thread1生成线程3 
时间2：线程0生成线程4，线程1生成线程5，线程2生成线程6，线程3生成线程7 
时间3：所有8个线程执行其任务
 

这需要3个单位的时间，并行运行并创建8个线程。由于 lg（8）= 3 ，算法的范围是&＃x398;（lg n）。 >

I have problems understanding dynamic multithreading. I have this 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(lg n)"

And my question is why? I'm confused. So if somebody could explain what they mean, it will be a big help.

解决方案

First of all, the definition of "span", for those who don't know it, is the length of the critical path. If you had an infinite number of CPUs, the span defines the minimum amount of time it could take to finish the algorithm.

In order to run a loop which has N iterations, the shortest way to do it is to spawn threads until you have N of them, then have each of the N threads perform one unit of work. Here's how it would work to spawn 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 running in parallel to create 8 threads. Since lg(8) = 3, the algorithm's span is Θ(lg n).

这篇关于跨度和并行回路的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！