效率的問題 - 在搜索上並行線程

陣列我碰到一個面試問題，詢問效率的問題 - 在搜索上並行線程

而線程，其方法是比較有效搜索中使用2- perallel陣列的值

（1）讀在不同的線程（在一半劈裂它）（2）讀出在奇數和偶數場所陣列（一個線程讀取奇數場所
和一個讀取偶數位陣列中）的陣列的每個一半。

我不明白爲什麼一個人會更高效，然後其他 appricate它，如果有人會爲我清除這個在此先感謝。

來源

2011-12-01 eran otzap

這可能與緩存性能有關。 – thiton

你的意思是因爲兩個線程都將從相同的起始地址中讀取，所以當讀取數組的第二部分時，緩存不會讀取更多的重新數據？ –

是的。做一個自我回答，這可能是正確的。 – thiton

分割一半的陣列幾乎可以肯定是要走的路。它幾乎不會變慢，並且可能會更快。

原因很簡單：當你從內存中讀取數據，處理器通常會一次讀取整個高速緩存行。不同處理器之間的確切大小有所不同，但並不重要（儘管如此，如果你在意的話，像64字節這樣的東西將會在大腦中） - 重點在於它一次讀取幾個字節的連續塊。

這意味着與奇數/偶數版本，兩個處理器運行兩個線程將不得不讀取所有的數據。通過將數據分成兩半，每個核心將只讀取一半的數據。如果您的拆分不是在緩存行邊界處，則每個都會讀取一些額外的內容（它需要四捨五入到緩存行的大小）。平均而言，這將爲每個需要讀取的內容添加一半的緩存行。

如果「處理器」涉及的是真的在同一個處理器芯片兩個核心，有機會，它不會讓整個很大的差異，雖然兩種方式。在這種情況下，瓶頸通常會將數據從主存儲器讀取到最低級處理器緩存中。即使只有一個線程，您也可能（可能）能夠以儘可能快的速度搜索數據，並且可以從內存中讀取數據，並且添加更多線程（無論您如何安排數據的使用）不會改善很多事情（如果有的話）。

來源

2011-12-01 17:00:44

這聽起來相當正確，我上面評論的現在聽起來有點愚蠢，因爲兩個處理器都會讀取適合緩存行的數據量，如果某些數據對於該過程是多餘的，則無論如何都無關緊要。 –

不同的是，在半分割的情況下，存儲器線性每個線程訪問的從左至右，從索引0搜索 - > N/2和N/2 - >Ñ分別最大化高速緩衝存儲器用法，因爲預取內存是線性提前完成的。

在第二種情況下（甚至奇數），緩存性能會更差，不僅因爲您會預取未使用的項目（線程0採用元素0,1等，而僅使用元素的一半），但也因爲緩存乒乓效應（在寫入的情況下，但這不是在你的例子中）。

來源

2011-12-01 17:01:02 Tudor

效率的問題 - 在搜索上並行線程

回答

相關問題