一組互斥任務的線程級並行性

我在使用C++處理流數據時遇到了問題。數據來自條目，每個條目的大小相對較小，處理每個條目的任務不需要太多時間。但是每個條目以及處理該條目的任務都被分配給類（一個概念，而不是C++類），其中只有一個屬於同一類的任務可以一次執行。一組互斥任務的線程級並行性

此外，還有數十億的條目和一千萬個類，並且條目隨機分類。

我發現很難將這些任務並行化。任何關於如何加快這一過程的建議都將非常有幫助！

真的非常感謝！

來源

2014-01-23 Tim

這是一個非常混亂的要求。你能提供更多細節嗎？也許我們可以考慮一些解決方法。數千萬個信號量的陣列聽起來並不樂觀：（ –

嘗試擁有一個隊列池，每個隊列不活躍或保存一個類的項目，每個隊列由它自己的線程提供服務 –

每個條目都是一行SQL表格，它保證有一列代表一個用戶，因此'class'實際上是一個用戶ID – Tim

將工作條目放入一組特定於類的工作隊列中。使用隊列大小作爲優先級較高的大小優先於較小的大小。設置一個priority queue（隊列）來根據它們的大小作爲優先級來保存類別特定的工作隊列。

如果沒有人正在處理該隊列，則將工作條目輸入到其相應的隊列中。

設置一個大小與您擁有的CPU數量大小相同的線程池。

每個線程都會詢問優先級隊列以獲取最高優先級的工作隊列，這是可以持有最多工作量的隊列。線程從優先級隊列中刪除類隊列。然後處理該隊列中的所有元素，而不鎖定它;這使得每個單元的開銷很小。

如果該類的新成員在此期間出現，它們會被添加到該類的新隊列中，但不會放入優先隊列中。工作線程使用當前隊列，檢查相同類的新隊列，並處理該隊列（如果存在）。

來源

2014-01-23 15:11:48

數以百萬計的隊列？ –

OP有數千萬個對象。爲什麼數千萬的隊列打擾他呢？實際上，他只需要排隊等待沒有處理的成員的課程。您可能需要一個包含null的數組或每個類有一個插槽的隊列指針。這是40Mb。 Pfft。 –

假設CPU至少有一點涉及，你會希望每個硬件處理器有一個任務處理器。

每個處理器都會鎖定一組活動類，在給定當前設置狀態的情況下，將一堆作業從隊列的前面甩出，將這些作業標記爲正在使用中，解鎖集和隊列，以及流程。

每個工作流的作業數，作業數，處理器數以及它們對集羣和延遲的敏感程度有所不同。

飢餓應該是不可能的，因爲一旦課堂可以自由處理，無污染的元素應該是高級的。

批量工作以保持設置和隊列低的爭用：理想情況下根據爭用，空閒和延遲信息動態更改批量大小。

這使開銷保持與處理器的數量成正比，而不是與任務類的數量成正比。

來源

2014-01-23 16:24:50 Yakk

我嘗試了類似的方法，但事實證明，每個處理器都必須有一個任務隊列，並且當從隊列中推送和彈出時是不可避免的。爲了緩解這種情況，我設法使用了一個鎖定比天真實現少的隊列。我已經發布在https://gist.github.com/zxytim/8611754。但儘管我已經完成了這種優化，儘管處理器使用的數量很多，但它仍然比順序的要慢。 – Tim

@Tim我不明白爲什麼給定的處理器線程的內部隊列需要涉及到鎖定：它只能從線程內部訪問。 – Yakk

但是隊列中的條目來自哪裏？它來自另一個線程不斷讀取輸入，推送到相應的隊列。請注意，不能有多個線程同時讀取輸入並且處理輸入不相關（因爲輸入是隨機類輸入的） – Tim

一組互斥任務的線程級並行性

回答

相關問題