效率问题-在并行线程上搜索数组 [英] efficiency issue - searching an array on parallel threads

问题描述

我碰到一个面试问题

使用2个perallel线程在数组中搜索值时 哪种方法会更有效

while searching a value in an array using 2 perallel threads which method would be more efficent

(1)在不同的线程上读取数组的每一半(将其分成两半) (2)在奇数和偶数位置读取数组(读取奇数位置的线程
还有一个读取数组中的偶数位.)

(1) read each half of the array on a different thread (spliting it in half) (2) reading the array on odd and even places (a thread which reads the odd places
and one which reads the even places in the array ).

我不明白为什么一个比另一个更有效 如果有人可以帮我澄清一下 预先感谢.

i don't understand why one would be more efficent then the other appricate it if someone would clearify this for me thanks in advance.

推荐答案

将数组拆分为一半几乎是肯定的方法.它几乎永远不会变慢，甚至可能会快得多.

Splitting the array in half is almost certainly the way to go. It will almost never be slower, and may be substantially faster.

原因很简单:当您从内存中读取数据时，处理器通常一次会读取整个缓存行.确切的大小因处理器而异，但并没有多大关系(不过，如果您在乎的话，大概会有64个字节)–关键是它一次读取几个字节的连续块

The reason is fairly simple: when you're reading data from memory, the processor will normally read an entire cache line at a time. The exact size varies between processors, but doesn't matter a whole lot (though, in case you care, something like 64 bytes would be in the ballpark) -- the point is that it reads a contiguous chunk of several bytes at a time.

这意味着对于奇/偶版本，运行两个线程的两个处理器都必须读取 all 数据.通过将数据分成两半，每个内核将仅读取一半的数据.如果您的拆分并非恰好位于缓存行边界，则每个拆分都会读取一些额外内容(需要将其四舍五入到缓存行的大小).平均而言，这将为每个需要读取的内容增加一半的缓存行.

That means with the odd/even version, both processors running both threads will have to read all the data. By splitting the data in half, each core will read only half the data. If your split doesn't happen to be at a cache line boundary, each will read a little extra (what it needs rounded up to the size of a cache line). On average that will add half a cache line to what each needs to read though.

如果所涉及的处理器"实际上是同一处理器芯片上的两个内核，则很可能它不会以任何方式产生很大的不同.在这种情况下，瓶颈通常是将数据从主内存读取到最低级别的处理器缓存中.即使只有一个线程，您(也可能)将能够像从内存中读取数据一样快速地搜索数据，并且添加更多线程(无论如何安排对数据的使用)都不会改善很多(如果有的话).

If the "processors" involved are really two cores on the same processor die, chances are that it won't make a whole lot of difference either way though. In this case, the bottleneck will normally be reading the data from main memory into the lowest-level processor cache. Even with only one thread, you'll (probably) be able to search through the data as fast as you can read it from memory, and adding more threads (no matter how you arrange their use of the data) isn't going to improve things much (if at all).

这篇关于效率问题-在并行线程上搜索数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！