我開始了解到有一些線性時間排序演算法不能通過像基數排序這樣的比較來運行。我希望有一個排序演算法，它可以在線性時間內運行，但也可以通過為 n 個元素運行 n 個執行緒來以恒定時間運行。根據我所做的研究，這在 PRAM CRCW 機器上似乎是可行的，但我發現關于在 PRAM CRCW 機器上運行的演算法是否可以在相同的恒定時間內在標準消費計算機上運行的資訊相互矛盾。
僅供參考，有問題的演算法在這里。這也很有趣。
是否可以？
uj5u.com熱心網友回復：
問： “是否有可能（在消費級處理器上實施 PRAM CRCW）？”
答：
讓我們先澄清事實。我們可以就什么是“消費者”處理器達成一致意見——最常見的COTS術語是正確的——一個定制的——即架式的處理器，任何人都可以去購買。任何此類 COTS 硬體的屬性集也是如此，由在此類處理器“內部”預制的硅結構預先定義。
相反，CRCW PRAM 術語是有意和有意的高度抽象的，最終理想化的任何此類處理器架構的屬性，可以（沒有任何時間限制或其他妥協）當前讀取（在任何和所有級別的并行性下） ) 并且C oncurrently 寫入（在任何和所有并行級別下）一次從/寫入任何記憶體位置（“地址”），添加一些額外的 créme-a-la-créme 屬性，例如執行所有的總和連續波-s，在實際存盤這樣的結果值之前。這些抽象屬性的任何這樣的物理實作，在任何情況下都能滿足它們，在完全并行模式下沒有例外，可以稱為 CRCW PRAM，而不是其他的。
這就是說，在當前的任何 COTS 處理器硬體芯片中，CRCW PRAM 架構目前還沒有得到滿足，甚至沒有接近它。
根據定義，這樣的問題導致實際上無法實作的愿望是通過使用架構 B 來“實作”架構 A（即使組合了許多這樣的 COTS 處理器（如定義）到一些相互關聯的宏觀結構中，這可能會使一些 COTS 硬體屬性更“接近”CRCW PRAM，但會以如此嚴重的不利成本或操作速度緩慢，以至于這種嘗試可能會導致一些超昂貴的東西 超低功耗 超慢（大約N 2 ~ 3次采樣，并且需要人為地“等待”所有最慢的部分以實作全寬的并行度以物理完成，如果從宏觀結構的觀點）。
使用任意數量的超標量、M 路流水線、無序執行 CISC 芯片來實作宏觀結構拓撲技巧，僅用于模擬“減速”的 CRCW PRAM，恕我直言，技術上不是正確的方法（如果我們想享受一個相當實用的O(k)分揀機）。
如果使用當前級別的 QPU 處理器，我們可能會“以某種方式”享受恒定時間 QUBO（當前 D-WAVE 系統機器系列中的單個硬體指令量子處理器），我會猶豫考慮這種極端情況（拓撲設定為承受“初始”狀態并讓自然（物理定律）“執行”量子退火“演算法”以產生結果的統計分布，在恒定時間內回答問題解決方案）COTS ，它不是，是嗎？
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/424329.html