我在理解动态多线程时遇到问题。我有以下算法:
第 16 页，MAT-VEC
http://mitpress.mit.edu/books/chapters/0262033844chap27.pdf
并且在文本中他们说“对于 nxn 矩阵上的 MAT-VEC，第 3-4 行中的并行初始化循环具有 span theta(lg n)”
我的问题是为什么？我糊涂了。所以如果有人能解释他们的意思，那将是一个很大的帮助。
最佳答案
首先，“跨度”的定义，对于不知道的人来说，就是关键路径的长度。如果您有无限数量的 CPU，则跨度定义了完成算法所需的最短时间。
为了运行一个有 N 次迭代的循环，最短的方法是产生线程直到你有 N 个线程，然后让 N 个线程中的每一个执行一个工作单元。以下是生成 8 个线程的工作方式:
时间 0:线程 0 产生线程 1
时间 1:线程 0 产生线程 2，线程 1 产生线程 3
时间 2:线程 0 产生线程 4，线程 1 产生线程 5，线程 2 产生线程 6，线程 3 产生线程 7
时间 3:所有 8 个线程都执行它们的任务
这花费了 3 个单位的时间，所有东西都并行运行以创建 8 个线程。自 lg(8) = 3 ，算法的跨度为 Θ(lg n) .
关于multithreading - 跨度和平行循环，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5918477/