[發(fā)明專利]散列沖突降低系統(tǒng)

有效

• 申請(qǐng)?zhí)枺?/td>: 201310168101.5
• 申請(qǐng)日: 2013-05-06
• 公開（公告）號(hào): CN103425725B
• 公開（公告）日: 2017-04-12
• 發(fā)明（設(shè)計(jì)）人: J·L·卡爾維尼亞克;C·M·德卡塞提斯;F·J·韋普蘭肯;D·溫德
• 申請(qǐng)（專利權(quán)）人: 國際商業(yè)機(jī)器公司
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 北京市中咨律師事務(wù)所11247
• 代理人: 張亞非,于靜

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

本發(fā)明涉及計(jì)算機(jī)系統(tǒng)領(lǐng)域，且更具體地，涉及用于非常大的表和非常高吞吐量的計(jì)算機(jī)實(shí)現(xiàn)的包查找機(jī)制。

背景技術(shù)

以太網(wǎng)端口可提供計(jì)算機(jī)和計(jì)算機(jī)網(wǎng)絡(luò)間的連接。對(duì)于100Gbps以太網(wǎng)端口，最小的64字節(jié)的包持續(xù)時(shí)間是6.7納秒，其在500Mhz僅給出3個(gè)時(shí)鐘周期以用于執(zhí)行查找的邏輯。

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

根據(jù)本發(fā)明的一個(gè)實(shí)施例，一種改進(jìn)的計(jì)算機(jī)系統(tǒng)可以包括具有計(jì)算機(jī)處理器的控制器，在與引入到控制器的新組件對(duì)接時(shí)，該控制器降低插入次數(shù)和/或沖突。該系統(tǒng)還可以包括沖突避免裝置，其通過使用多個(gè)表以及每個(gè)桶多個(gè)鍵來降低散列沖突。該系統(tǒng)還可以包括與控制器通信的散列裝置，以將所述多個(gè)鍵映射到所述多個(gè)表，其中，該散列裝置使用單個(gè)散列邏輯在一個(gè)鍵改變時(shí)提供雪崩效應(yīng)（avalanche?effect），所述一個(gè)鍵改變導(dǎo)致多個(gè)表中的將近一半位改變。

所述單個(gè)散列邏輯可以基于Cuckoo算法。所述單個(gè)散列邏輯可以包括可配置的循環(huán)冗余檢查多項(xiàng)式。所述散列裝置可以基于雪崩效應(yīng)來提供所述多個(gè)表的并行表查找。

雪崩效應(yīng)可以基于用于所述多個(gè)表中的每個(gè)的正交散列函數(shù)，并且所述單個(gè)散列邏輯實(shí)現(xiàn)每個(gè)正交散列函數(shù)。所述單個(gè)散列邏輯的每位輸出可以包括鍵位的匯集（funneled）結(jié)果。

所述匯集結(jié)果可以由異或函數(shù)產(chǎn)生。所述多個(gè)表可以是可配置的。通過控制單個(gè)散列邏輯輸出的位數(shù)，所述多個(gè)表的全局負(fù)載可以是可配置的。

本方面的另一方面是一種用于改進(jìn)計(jì)算機(jī)系統(tǒng)的方法。該方法可以包括，當(dāng)新組件被引入到包含計(jì)算機(jī)處理器的控制器時(shí)，降低插入次數(shù)和/或散列沖突。該方法還可以包括由沖突避免裝置通過使用多個(gè)表和每個(gè)桶多個(gè)鍵來降低散列沖突。該方法還可以包括使用與控制器通信的散列裝置將所述多個(gè)鍵映射到多個(gè)表，該散列裝置使用單個(gè)散列邏輯在一個(gè)鍵改變時(shí)提供雪崩效應(yīng)，所述一個(gè)鍵改變導(dǎo)致多個(gè)表中的將近一半位改變。

該方法還可以包括基于雪崩效應(yīng)通過散列裝置來提供所述多個(gè)表的并行表查找。該方法還可以包括使雪崩效應(yīng)基于用于所述多個(gè)表中的每個(gè)的正交散列函數(shù)，并且所述單個(gè)散列邏輯實(shí)現(xiàn)每個(gè)正交散列函數(shù)。

該方法還可以包括匯集所述單個(gè)散列邏輯的每位輸出的鍵位的結(jié)果。該方法還可以包括使得所述多個(gè)表可配置。該方法還可以包括控制單個(gè)散列邏輯輸出的位數(shù)，從而所述多個(gè)表的全局負(fù)載是可配置的。

本方面的另一方面是計(jì)算機(jī)可讀程序代碼，其耦合到有形介質(zhì)以改進(jìn)計(jì)算機(jī)系統(tǒng)。所述計(jì)算機(jī)可讀程序代碼可被配置為使得程序在新組件被引入到包含計(jì)算機(jī)處理器的控制器時(shí)降低插入次數(shù)和/或散列沖突。所述計(jì)算機(jī)可讀程序代碼還可以由沖突避免裝置通過使用多個(gè)表和每個(gè)桶多個(gè)鍵來降低散列沖突。計(jì)算機(jī)可讀程序代碼還可以使用與控制器通信的散列裝置將所述多個(gè)鍵映射到所述多個(gè)表，該散列裝置使用單個(gè)散列邏輯在一個(gè)鍵改變時(shí)提供雪崩效應(yīng)，所述一個(gè)鍵改變導(dǎo)致多個(gè)表中的將近一半位改變。

所述計(jì)算機(jī)可讀程序代碼還可以基于雪崩效應(yīng)通過散列裝置來提供所述多個(gè)表的并行表查找。所述計(jì)算機(jī)可讀程序代碼還可以使雪崩效應(yīng)基于所述多個(gè)表中的每個(gè)的正交散列函數(shù)，并且所述單個(gè)散列邏輯實(shí)現(xiàn)每個(gè)正交散列函數(shù)。

所述計(jì)算機(jī)可讀程序代碼還可以匯集所述單個(gè)散列邏輯的每位輸出的鍵位的結(jié)果。所述計(jì)算機(jī)可讀程序代碼還可以使得所述多個(gè)表可配置。所述計(jì)算機(jī)可讀程序代碼還可以控制單個(gè)散列邏輯輸出的位數(shù)，從而所述多個(gè)表的全局負(fù)載是可配置的。

附圖說明

圖1是示出根據(jù)本發(fā)明的數(shù)據(jù)庫改進(jìn)系統(tǒng)的框圖。

圖2是示出根據(jù)本發(fā)明的方法方面的流程圖。

圖3是示出根據(jù)圖2的方法的方法方面的流程圖。

圖4是示出根據(jù)圖2的方法的方法方面的流程圖。

圖5是示出根據(jù)圖4的方法的方法方面的流程圖。

圖6是示出根據(jù)圖2的方法的方法方面的流程圖。

圖7是示出根據(jù)圖6的方法的方法方面的流程圖。

圖8示出了根據(jù)本發(fā)明的CCB表查詢引擎的高級(jí)結(jié)構(gòu)。

圖9示出了根據(jù)本發(fā)明的5模式可編程散列邏輯的高級(jí)結(jié)構(gòu)。

圖10示出了根據(jù)本發(fā)明的4到2例子。

圖11示出了根據(jù)本發(fā)明的異或矩陣的例子。

圖12示出了根據(jù)本發(fā)明的遠(yuǎn)程查找請(qǐng)求時(shí)序。

圖13示出了根據(jù)本發(fā)明的“即時(shí)”（on?the?fly）比較引擎。

具體實(shí)施方式

下面將參考附圖來更完整地描述本發(fā)明，附圖中示出了本發(fā)明的優(yōu)選實(shí)施例。在全文中相同的標(biāo)號(hào)表示相同的元件。