跨度和并行循环

Question

我在理解动态多线程时遇到了问题.我有以下算法:

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

在文中他们说"对于nxn矩阵上的MAT-VEC,第3-4行中的并行初始化循环具有跨越theta(lg n)"

我的问题是为什么？我糊涂了.因此,如果有人能解释他们的意思,那将是一个很大的帮助.

Answer 1

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

为了运行具有N次迭代的循环,最简单的方法是生成线程,直到你有N个,然后让每个N个线程执行一个工作单元.以下是如何生成8个线程:

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

这需要3个单位时间,并行运行所有内容以创建8个线程.因为lg(8) = 3,算法的跨度是Θ(lg n).