如何计算线程有效性的Amadahl定律 [英] How to calculate Amadahl's Law for threading effectiveness
问题描述
它很容易找到和理解阿玛达尔定律的函数定义,但我能找到的所有工作实例对于我的小豌豆大脑来说太模糊或太学术/缺乏了解。
Amadahl定律接受参数: F
,无法通过多线程改进的任务的%,
如何查看一段代码并确定是否会通过多线程改进?/ p>
很容易说出你的代码的哪些部分肯定不会受益于多线程:顺序部分。如果你必须按顺序执行一系列小步骤,多线程将不会有帮助,因为你总是需要等待一个步骤才能开始下一步。许多常见任务在这个意义上不是(必然)顺序的:例如,在列表中搜索多个项目。如果要从列表中提取每个红色项目,您可以在多个线程之间共享列表的部分,并将每个部分的所有红色项目收集到最终结果列表中。并发编程的困难在于找到有效的方法来解决这个问题。
在较低级别,您可以谈论数据依赖性:如果特定指令或块使用该块自身计算的结果,则依赖于前一个块。所以(伪代码):
块1:
将r1加载到r2
中将r1添加到r3到r4
块二:
将r4加载到r1
中将r4加入r4
块二取决于块一:它们必须按顺序执行。在此:
封锁一:
载入r1至r2
将r1加入r3至r4
块二:
将r1加载到r3
将3加入r1到r1
那不是这样的。这不是直接用于并发,但希望它更具体地说明了这一点。它还说明了处理并发的另一个问题:作为抽象块功能,这两个可以并行运行,但在这里给出的具体示例中,它们正在读/写一些相同的寄存器,因此编译器/管道线程/做更多的工作,使他们一起运行。这一切都非常复杂,但在 http://www.amazon.com/Computer- Architecture-Quantitative-Approach-Edition / dp / 1558605967 。
其他哪些部分不受益于多线程取决于您的编程环境和机器架构。
至于如何获得一个百分比,在一个实际案例中可能有一些手艺 - 我怀疑你会得到一个精确的数字。如果你把你的代码分成功能单元,并分析每个的执行时间,这将给你一个大致适当的权重。如果一个占用90%执行时间的部分可以通过多线程来改进,那么你说你的90%的任务可以这么改进。
Its easy to find and understand the function definition for Amadahl's Law, but all of the working examples I was able to find were either too vague or too academic/cerebreal for my tiny pea brain to understand.
Amadahl's Law takes to parameters: F
, the % of a task that cannot be improved via multi-threading, and N
, the number of threads to use.
How does one calculate F
with any degree of accuracy?
How do you look at a piece of code and determine whether that will be improved by multi-threading?
It's relatively easy to say which parts of your code certainly won't benefit from multi-threading: sequential parts. If you have to carry out a series of small steps in order, muli-threading won't help because you always need to wait for one step to be done before starting the next. Many common tasks aren't (necessarily) sequential in this sense: for example, searching a list for a number of items. If you want to extract every red item from a list, you can share parts of the list among several threads and collect all the red items from each part into a final result list. The difficulty in concurrent programming lies in finding efficient ways of doing this for real problems.
At a lower level you can talk about data dependency: a particular instruction or block depends on a previous block if it uses the results of that block's calculations in its own. So (pseudocode):
Block one:
load r1 into r2
add r1 to r3 into r4
Block two:
load r4 into r1
add 3 to r4 into r4
block two depends on block one: they must be executed in order. Here:
Block one:
load r1 into r2
add r1 to r3 into r4
Block two:
load r1 into r3
add 3 to r1 into r1
that isn't the case. This isn't directly useful for concurrency, but hopefully it illustrates the point more concretely. It also illustrates another problem in handling concurrency: as abstract blocks functionality these two can be run in parallel, but in the concrete example given here they're reading/writing some of the same registers, so a compiler/pipeliner/whatever would have to do more work to make them run together. This is all very complex, but is covered beautifully in http://www.amazon.com/Computer-Architecture-Quantitative-Approach-Edition/dp/1558605967.
Which other parts don't benefit from multi-threading depends on your programming environment and machine architecture.
As for how to get a percentage, there's probably some hand-waving involved in a practical case - I doubt you'll ever get a precise number. If you divide your code up into functional units and profile the execution time in each, that would give you a roughly appropriate weighting. Then if one part that takes up 90% of the execution time can be improved with multi-threading, you say that 90% of your 'task' can be so improved.
这篇关于如何计算线程有效性的Amadahl定律的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!