偷工減料

Question

爲什麼我們需要偷工減料？ （例如在Cilk）主人在頂端工作，小偷從底部偷竊。爲什麼它有用？

我們可能會有多個盜賊從底部偷竊。那麼，我們不需要鎖嗎？ 我讀過一些地方，大型作業（例如在樹中創建）被添加到底部。所以，從底部偷竊更有效率（減少溝通，因爲竊賊通過竊取他們變得更加忙碌）。是嗎？

Answer 1

該協議的細節了「的Cilk-5多線程語言的實現」，這是從MIT第5節描述：http://supertech.csail.mit.edu/papers/cilk5.pdf

Answer 2

你並不需要爲工作竊取一個deque。這是可能的（並且人們已經做到了）使用併發數據結構來存儲任務池。但問題是，來自工人的推/拉操作和來自盜賊的竊取請求都必須同步。由於搶斷預計會是相對罕見的事件，因此可以設計一個數據結構，以便在竊取嘗試期間同時進行同步化，甚至在可能存在衝突的情況下彈出一個來自數據結構。這就是爲什麼在Cilk中使用deques的原因 - 儘量減少同步。工作人員將自己的deques視爲堆棧，從底部推送和彈出線程，但將另一個繁忙工作人員的雙端隊列當作隊列處理，只有在沒有本地線程執行的情況下才從頂端竊取線程。由於竊取操作是同步的，所以多個盜賊試圖從同一個受害者那裏竊取是可以的。

在分而治之風格算法中添加較大的作業是常見的，但不是全部。有很多策略適用於在偷竊過程中做什麼。偷一項任務，幾項任務，一半任務等等。這些變體中的每一個都適用於某些應用程序，其他應用程序不太適合。

Answer 3

工作偷竊實際上確實需要一個雙殼。在原始論文中，他們已經證明了在具有P處理器的系統上使用的最大內存。限制由任何堆棧的最大大小乘以處理器數量給出。這實際上只能遵循忙葉定理。此外，偷工作的另一個重要特徵是： 當工作人員做出產卵時，它立即將產卵器保存在雙側器上並開始對孩子進行工作。有關他們的證據的更多信息，請閱讀他們的原始文件，他們在其中解釋我所說的一切。 http://supertech.csail.mit.edu/papers/steal.pdf

工作中的併發控制竊取deque訪問與工作竊取調度程序無關，實際上，已經對從deque（通過使用無鎖結構）中移除鎖進行了大量研究，並且最小化爲儘可能多的記憶障礙。例如在本文中（如果無法訪問，我很抱歉，但是您可以閱讀摘要以獲得想法）：http://dl.acm.org/citation.cfm?id=1073974作者爲改進上述方面創建了一個新的雙端隊列。

由於可能有以下幾個原因，該工作人員沒有在工作的一側進行搶斷： 由於每個工作人員（雙側工作人員）都是作爲一個堆棧工作，所以「較大」的工作應該在最上面（你可以通過閱讀文章瞭解）。當我說更大的時候，我想表示那些可能會有更多的計算要做。此外，另一個重要方面是通過這樣做（偷取老闆的對面工作方）可以減少爭用，因爲在一些新的雙層舞者中，受害者和小偷可能同時在同一個雙層舞臺上工作。