在CRCW線程模型中實現併發寫入

Question

並行計算的PRAM模型主要有三種：EREW，CREW，CRCW。

我可以理解EREW，CREW如何在多核機器上實現。但是如何在多核CPU上實現CRCW模型呢？它甚至是一個實用的模型，因爲併發寫入是不可能的，並且每個基本的並行編程課程 都會針對競爭條件進行詳細描述。

從本質上講，這意味着試圖避免競爭狀態，並試圖實現併發 寫有兩個對立的目標。

Answer 1

首先：我們知道PRAM是一個理論上的或抽象的機器。有幾種簡化方法可用於分析/設計並行算法。

Next，讓我們來討論一下可以做'併發寫入'有意義的方法。

併發寫存儲器通常分爲子的基礎上，他們的言行舉止：基於CW

1. 優先級 - 處理器有一個任務，如果多個併發寫入同一個位置到達，來自具有最高優先級的處理器的寫入被提交給內存。

2. 仲裁CW - 一個處理器的寫入任意選擇提交。

3. 常見CW - 多併發寫入到同一位置致力於只有值被寫入是相同的。即所有寫入處理器必須同意寫入的值。

4. 減少CW - 將減少操作符應用於正在寫入的多個值。例如總和，其中對同一位置的多個併發寫入導致被寫入的值的總和被提交給存儲器。

這些子類導致一些有趣的算法。一些我從類記得實例是：

1. 甲CRCW-PRAM，其中並行寫入被實現爲求和可以在單個時間步長總結任意大量的整數。輸入數組中的每個整數都有一個處理器。所有處理器將其值寫入相同的位置。完成。

2. 想象一下，只有當所有處理器寫入的值是相同時，內存才提交併發寫入的CRCW-PRAM。現在想象一下N號碼A[1] ... A[N]，它們的最大值需要查找。這裏是你會怎麼做：

步驟1.

ň^2個處理器將每個值進行相互比較值，並將結果寫入到一個二維數組：

parallel_for i in [1,N] 
    parallel_for j in [1,N] 
    if (A[i] >= A[j]) 
     B[i,j] = 1 
    else 
     B[i,j] = 0 

所以在這個二維數組中，對應於最大數字的列將全部爲1。

第2步：

找到只有1的列。並將相應的值存儲爲最大值。

parallel_for i in [1,N] 
    M[i] = 1 
    parallel_for j in [1,N] 
    if (B[i,j] = 0) 
     M[i] = 0    // multiple concurrent writes of *same* value 
    if M[i] 
    max = A[i] 

最後，是有可能實現真正的？

是的，這是可能的。設計一個寄存器文件或一個存儲器和相關的邏輯，它具有多個寫入端口，並且可以以有意義的方式仲裁併行寫入同一地址（就像我上面描述的那樣）。你可能已經可以看到基於我提到的子類。不管它是否實用，我都不能說。我可以說，在我對計算機的有限經驗（主要涉及通用硬件，比如目前我正在使用的Core Duo機器）方面，我在實踐中還沒有看到過。

編輯：我沒有找到一個CRCW實現。關於PRAM的維基百科文章描述了一個CRCW機器，它可以在2個時鐘週期內找到陣列的最大值（使用與上面相同的算法）。 The description is in SystemVerilog and can be implemented in an FPGA.