[發(fā)明專利]排序系統(tǒng)及數(shù)據(jù)處理方法

有效

• 申請?zhí)枺?/td>: 201811231441.7
• 申請日: 2018-10-22
• 公開（公告）號(hào): CN109460210B
• 公開（公告）日: 2020-11-03
• 發(fā)明（設(shè)計(jì)）人: 周曦;冉超
• 申請（專利權(quán)）人: 重慶中科云從科技有限公司
• 主分類號(hào): G06F7/24
• 分類號(hào): G06F7/24;G06F7/02
• 代理公司: 上海光華專利事務(wù)所(普通合伙) 31219
• 代理人: 尹麗云

本發(fā)明實(shí)施例提供一種排序系統(tǒng)及數(shù)據(jù)處理方法，該排序系統(tǒng)用于從數(shù)據(jù)量為N的輸入數(shù)據(jù)中篩選出排名前K的K個(gè)目標(biāo)數(shù)據(jù)，該系統(tǒng)包括依次連接的K個(gè)處理單元；任一個(gè)處理單元包括：寄存器，用于存儲(chǔ)當(dāng)前位置的目標(biāo)數(shù)據(jù)；比較器，用于按照預(yù)設(shè)條件比較輸入數(shù)據(jù)、所述寄存器存儲(chǔ)的目標(biāo)數(shù)據(jù)以得到比較結(jié)果；三路選擇器，包括選擇輸出端、三路輸入端、兩個(gè)選擇端，該三路輸入端分別用于接收輸入數(shù)據(jù)、當(dāng)前位置的目標(biāo)數(shù)據(jù)、前一個(gè)處理單元存儲(chǔ)的目標(biāo)數(shù)據(jù)，該兩個(gè)選擇端分別用于接收比較器的比較結(jié)果、前一個(gè)處理單元中比較器的比較結(jié)果，該選擇輸出端用于向寄存器輸出選擇結(jié)果。使用時(shí)，K個(gè)比較器同時(shí)進(jìn)行比較，K個(gè)寄存器分別存儲(chǔ)K個(gè)目標(biāo)數(shù)據(jù)。

技術(shù)領(lǐng)域

本發(fā)明涉及數(shù)據(jù)處理領(lǐng)域，具體而言，涉及一種排序系統(tǒng)及數(shù)據(jù)處理方法。

背景技術(shù)

隨著人工智能的興起，圖像識(shí)別等技術(shù)在實(shí)際生活中的應(yīng)用越來越廣泛。在圖像分類、人臉識(shí)別等圖像處理任務(wù)中，需要對最終的結(jié)果進(jìn)行排序，得到TOP_K。

在實(shí)際應(yīng)用中，往往需要對大量數(shù)據(jù)(N個(gè))進(jìn)行排序得到TOP_K(從數(shù)據(jù)量為N的大規(guī)模數(shù)據(jù)中，尋找排名前K的元素)，并且隨著K以及N的增加，算法復(fù)雜度會(huì)隨之增加。目前基于CPU(Central Processing Unit，中央處理器)的TOP_K算法的時(shí)間復(fù)雜度最優(yōu)為N*O(log₂(K))，會(huì)占用大量存儲(chǔ)資源。

發(fā)明內(nèi)容

為克服現(xiàn)有技術(shù)中存在的技術(shù)問題，本發(fā)明實(shí)施例的目的在于提供一種排序系統(tǒng)及數(shù)據(jù)處理方法。

第一方面，本發(fā)明實(shí)施例提供一種排序系統(tǒng)，用于從數(shù)據(jù)量為N的輸入數(shù)據(jù)中篩選出排名前K的K個(gè)目標(biāo)數(shù)據(jù)，所述系統(tǒng)包括依次連接的K個(gè)處理單元；

任一個(gè)處理單元包括：

寄存器，用于存儲(chǔ)當(dāng)前位置的目標(biāo)數(shù)據(jù)；

比較器，用于按照預(yù)設(shè)條件比較輸入數(shù)據(jù)、所述寄存器存儲(chǔ)的目標(biāo)數(shù)據(jù)，以得到比較結(jié)果；

三路選擇器，包括三路輸入端、兩個(gè)選擇端及一個(gè)選擇輸出端，該三路輸入端分別用于接收所述輸入數(shù)據(jù)、所述當(dāng)前位置的目標(biāo)數(shù)據(jù)、前一個(gè)處理單元存儲(chǔ)的目標(biāo)數(shù)據(jù)，該兩個(gè)選擇端分別用于接收所述比較器的比較結(jié)果、前一個(gè)處理單元中所述比較器的比較結(jié)果，該選擇輸出端用于向所述寄存器輸出選擇結(jié)果；

使用時(shí)，所述K個(gè)處理單元中，K個(gè)所述比較器同時(shí)進(jìn)行比較，K個(gè)所述寄存器分別用于存儲(chǔ)K個(gè)所述目標(biāo)數(shù)據(jù)。

第二方面，本發(fā)明實(shí)施例提供一種數(shù)據(jù)處理方法，用于從數(shù)據(jù)量為N的輸入數(shù)據(jù)中篩選出排名前K的K個(gè)目標(biāo)數(shù)據(jù)，所述方法包括：

在接收到觸發(fā)信號(hào)時(shí)，利用K個(gè)比較器分別對當(dāng)前輸入數(shù)據(jù)、K個(gè)寄存器中存儲(chǔ)的K個(gè)數(shù)據(jù)進(jìn)行比較，得到K個(gè)比較結(jié)果；

根據(jù)該K個(gè)比較結(jié)果對K個(gè)所述寄存器中的數(shù)據(jù)進(jìn)行并行更新，得到K個(gè)所述目標(biāo)數(shù)據(jù)。

與現(xiàn)有技術(shù)相比，本發(fā)明實(shí)施例的排序系統(tǒng)及數(shù)據(jù)處理方法，可用于在數(shù)據(jù)量為N的大規(guī)模數(shù)據(jù)中篩選出排名前K的數(shù)據(jù)，在該排序系統(tǒng)中，可以通過K個(gè)處理單元同時(shí)進(jìn)行數(shù)據(jù)處理。其中，K個(gè)處理單元中的K個(gè)寄存器分別用于存儲(chǔ)排名前K的目標(biāo)數(shù)據(jù)，由于K個(gè)比較器同時(shí)存在于K個(gè)處理單元中，且能夠同時(shí)接收輸入數(shù)據(jù)，因此可以實(shí)現(xiàn)同時(shí)對于一個(gè)輸入數(shù)據(jù)進(jìn)行多次比較，一次性完成對于多個(gè)寄存器的數(shù)據(jù)更新。在整個(gè)數(shù)據(jù)處理過程中，可以實(shí)現(xiàn)數(shù)據(jù)的并行處理，只需占用K個(gè)寄存器及K個(gè)比較器。在利用上述排序系統(tǒng)及數(shù)據(jù)處理方法實(shí)現(xiàn)TOP_K算法時(shí)，能夠避免現(xiàn)有技術(shù)中由于CPU的硬件結(jié)構(gòu)限制帶來的串行處理弊端，可以使空間復(fù)雜度為N，且時(shí)間復(fù)雜度不會(huì)大幅度增長，即在時(shí)間復(fù)雜度低的情況下降低空間復(fù)雜度。

為使本發(fā)明的上述目的、特征和優(yōu)點(diǎn)能更明顯易懂，下文特舉實(shí)施例，并配合所附附圖，作詳細(xì)說明如下。

附圖說明