[發明專利]用于執行穩定和短等待時間排序操作的裝置和方法

在審

• 申請號: 202011501474.6
• 申請日: 2020-12-17
• 公開（公告）號: CN113496540A
• 公開（公告）日: 2021-10-12
• 發明（設計）人: S·曼達爾;P·薩蒂;S·沃普
• 申請（專利權）人: 英特爾公司
• 主分類號: G06T15/06
• 分類號: G06T15/06;G06T1/20
• 代理公司: 上海專利商標事務所有限公司 31100
• 代理人: 陳依心;何焜

1.一種處理器，包括：

輸入電路，用于接收要被排序為排序順序的N個輸入值的集合；

比較電路，用于并行地將每個輸入值與所有其他輸入值進行比較以生成至少N*(N-1)/2個比較結果值；

矩陣生成電路和/或邏輯，用于生成結果矩陣，所述結果矩陣具有與每個輸入值相關聯的行，每一行中的多個位包括指示與其他輸入值的比較的結果的比較結果值，其中所述結果矩陣的第一區域用于存儲包括所述N*(N-1)/2個比較結果值的位的第一集合，并且所述結果矩陣的與所述第一區域相對的第二區域用于存儲包括所述N*(N-1)/2個比較結果值的反轉的位的第二集合；

并行加法器電路，用于執行每一行中的位的并行加法以生成N個唯一結果值；以及

排序電路，用于對所述N個唯一結果值索引以返回所述排序順序。

2.如權利要求1所述的處理器，其中，所述比較電路包括N*(N-1)/2個比較器，用于執行N*(N-1)/2個并行比較以生成所述至少N*(N-1)/2個比較結果值。

3.如權利要求2所述的處理器，其中，所述N*(N-1)/2個比較包括大于或等于比較，并且其中每個比較結果值包括在第一輸入值大于或等于第二輸入值的情況下被設置為1、或者在所述第一輸入值不大于且不等于所述第二輸入值的情況下被設置為0的位。

4.如權利要求1至3中任一項所述的處理器，其中，所述N個輸入值中的每一個包括與N個包圍體層級結構BVH節點相關聯的距離值，其中所述排序電路用于基于所述比較結果值生成所述BVH節點的排序順序。

5.如權利要求4所述的處理器，進一步包括：

棧管理電路和/或邏輯，用于按所述排序順序將所述N個BVH節點入棧。

6.如權利要求1所述的處理器，其中，所述結果矩陣的所述第一區域包括右上區域，并且所述結果矩陣的所述第二區域包括左下區域，所述結果矩陣的所述第一區域和所述第二區域由所述矩陣中的、將所述結果矩陣的左上角與所述結果矩陣的右下角相連接的對角線位的位置的集合分開。

7.如權利要求1所述的處理器，其中，所述結果矩陣的所述第一區域包括左上區域，并且所述結果矩陣的所述第二區域包括右下區域，所述結果矩陣的所述第一區域和所述第二區域由所述矩陣中的、將所述結果矩陣的左下角與所述結果矩陣的右上角相連接的對角線位的位置的集合分開。

8.如權利要求1至7中任一項所述的處理器，其中，所述N個輸入值的集合的值N可變到高達閾值，并且其中，無論至多到所述閾值的值N如何，在相同數量的處理器周期中，所述比較電路都用于生成所述比較結果值，并且所述矩陣生成電路都用于生成所述結果矩陣。

9.一種方法，包括：

接收要被排序為排序順序的N個輸入值的集合；

并行地將每個輸入值與所有其他輸入值進行比較以生成至少N*(N-1)/2個比較結果值；

生成結果矩陣，所述結果矩陣具有與每個輸入值相關聯的行，每一行中的多個位包括指示與其他輸入值的比較的結果的比較結果值，其中所述結果矩陣的第一區域用于存儲包括所述N*(N-1)/2個比較結果值的位的第一集合，并且所述結果矩陣的與所述第一區域相對的第二區域用于存儲包括所述N*(N-1)/2個比較結果值的反轉的位的第二集合；

執行每一行中的位的并行加法以生成N個唯一結果值；以及

對所述N個唯一結果值索引以返回所述排序順序。

10.如權利要求9所述的方法，其中，所述N*(N-1)/2個并行比較由N*(N-1)/2個比較器執行以生成所述至少N*(N-1)/2個比較結果值。