[發(fā)明專利]具有溢出FIFO的計(jì)數(shù)器及其方法

有效

• 申請?zhí)枺?/td>: 201510253417.3
• 申請日: 2015-05-18
• 公開（公告）號: CN105278912B
• 公開（公告）日: 2021-03-12
• 發(fā)明（設(shè)計(jì)）人: 王煒煌;S·阿特魯里
• 申請（專利權(quán)）人: 馬維爾亞洲私人有限公司
• 主分類號: G06F5/06
• 分類號: G06F5/06
• 代理公司: 北京市金杜律師事務(wù)所 11256
• 代理人: 王茂華

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

本發(fā)明涉及在高速網(wǎng)絡(luò)交換機(jī)中的計(jì)數(shù)器。更特別地，本發(fā)明涉及具有溢出FIFO的計(jì)數(shù)器及其方法。

背景技術(shù)

統(tǒng)計(jì)計(jì)數(shù)器被用于在高速網(wǎng)絡(luò)設(shè)備中執(zhí)行數(shù)據(jù)分析。為了有用，需要一種架構(gòu)來存儲大量的計(jì)數(shù)器。盡管可以使用片外DRAM(動態(tài)隨機(jī)存取存儲器)，但其不能容納高速計(jì)數(shù)器更新。片上SRAM(靜態(tài)隨機(jī)存取存儲器)允許更大速度，但非常昂貴。由于存儲器是SOC(片上系統(tǒng))中最昂貴的資源之一，高效地并靈活地利用存儲器是至關(guān)重要的。當(dāng)處理存儲多個(gè)計(jì)數(shù)器時(shí)，存在更少的較大計(jì)數(shù)器或更多的較小計(jì)數(shù)器之間的權(quán)衡。理想地，每個(gè)計(jì)數(shù)器足夠長以避免整數(shù)溢出，計(jì)數(shù)器的環(huán)繞。然而，在標(biāo)準(zhǔn)的實(shí)踐中，這會導(dǎo)致超量配置，為所有計(jì)數(shù)器分配最差情況數(shù)量的比特。

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

本發(fā)明的實(shí)施例涉及通過針對平均情況配置每個(gè)計(jì)數(shù)器來延長計(jì)數(shù)器壽命，以及經(jīng)由溢出FIFO和對監(jiān)控計(jì)數(shù)器的過程的中斷來處理溢出的架構(gòu)。該架構(gòu)解決了一般的優(yōu)化問題，該一般的優(yōu)化問題可以被陳述為，給定N個(gè)計(jì)數(shù)器，對于某個(gè)CPU讀取間隔T，怎樣使存儲和操作該N個(gè)計(jì)數(shù)器所需要的存儲比特的數(shù)量最小化。等同地，該一般的優(yōu)化問題也可以被陳述為，給定N個(gè)計(jì)數(shù)器和某數(shù)量的存儲比特，怎樣優(yōu)化和增大CPU讀取間隔T。該架構(gòu)使計(jì)數(shù)器CPU讀取間隔隨溢出FIFO的深度線性地延長。

在一個(gè)方面，提供了一種計(jì)數(shù)器架構(gòu)。該計(jì)數(shù)器架構(gòu)通常被實(shí)施在網(wǎng)絡(luò)設(shè)備中，諸如網(wǎng)絡(luò)交換機(jī)。該計(jì)數(shù)器架構(gòu)包括N個(gè)環(huán)繞式計(jì)數(shù)器。N個(gè)環(huán)繞式計(jì)數(shù)器的每個(gè)環(huán)繞式計(jì)數(shù)器與計(jì)數(shù)器標(biāo)識相關(guān)聯(lián)。在一些實(shí)施例中，N個(gè)環(huán)繞式計(jì)數(shù)器的每個(gè)環(huán)繞式計(jì)數(shù)器是w比特寬。在一些實(shí)施例中，N個(gè)環(huán)繞式計(jì)數(shù)器是在片上SRAM存儲器中。

該計(jì)數(shù)器架構(gòu)還包括溢出FIFO，該溢出FIFO由N個(gè)環(huán)繞式計(jì)數(shù)器使用和共享。該溢出FIFO通常存儲正在溢出的所有計(jì)數(shù)器的相關(guān)聯(lián)的計(jì)數(shù)器標(biāo)識。

在一些實(shí)施例中，該計(jì)數(shù)器架構(gòu)還包括向CPU發(fā)送以讀取溢出FIFO和溢出的計(jì)數(shù)器中的一個(gè)溢出的計(jì)數(shù)器的至少一個(gè)中斷。

在一些實(shí)施例中，在計(jì)時(shí)間隔T中，計(jì)數(shù)器溢出的數(shù)量是M＝向上舍入(EPS*T/2^w)(M＝ceiling(EPS*T/2^w))，其中EPS是每秒的事件，并且w是每個(gè)計(jì)數(shù)器的比特寬度。在一些實(shí)施例中，EPS是針對分組計(jì)數(shù)的每秒的分組。備選地，EPS是針對字節(jié)計(jì)數(shù)的每秒的字節(jié)。

在一些實(shí)施例中，溢出FIFO是M深(M-deep)并且log₂N比特寬的以捕獲所有的計(jì)數(shù)器溢出。

在一些實(shí)施例中，計(jì)數(shù)器架構(gòu)要求w*N+M*log₂N的總存儲比特。

在另一方面，提供了一種計(jì)數(shù)器架構(gòu)的方法。該計(jì)數(shù)器架構(gòu)包括至少一個(gè)計(jì)數(shù)器。該方法包括遞增至少一個(gè)計(jì)數(shù)器中的計(jì)數(shù)。該至少一個(gè)計(jì)數(shù)器中的每個(gè)計(jì)數(shù)器通常與計(jì)數(shù)器標(biāo)識相關(guān)聯(lián)。在一些實(shí)施例中，該至少一個(gè)計(jì)數(shù)器是環(huán)繞式計(jì)數(shù)器。

該方法還包括，在至少一個(gè)計(jì)數(shù)器中的一個(gè)計(jì)數(shù)器溢出時(shí)，將溢出的計(jì)數(shù)器的計(jì)數(shù)器標(biāo)識存儲在隊(duì)列中。在一些實(shí)施例中，隊(duì)列是FIFO緩沖器。在一些實(shí)施例中，將計(jì)數(shù)器標(biāo)識存儲在隊(duì)列中向CPU發(fā)送中斷以從隊(duì)列和溢出的計(jì)數(shù)器讀取值。

在一些實(shí)施例中，該方法還包括從讀取的值計(jì)算溢出的計(jì)數(shù)器的實(shí)際值。

在一些實(shí)施例中，該方法還包括在讀取溢出的計(jì)數(shù)器之后，清空溢出的計(jì)數(shù)器。

在又一方面，提供了一種計(jì)數(shù)器架構(gòu)的方法。該計(jì)數(shù)器架構(gòu)包括多個(gè)環(huán)繞式計(jì)數(shù)器。該方法包括遞增多個(gè)環(huán)繞式計(jì)數(shù)器中的計(jì)數(shù)。通常地，多個(gè)計(jì)數(shù)器中的每個(gè)計(jì)數(shù)器與計(jì)數(shù)器標(biāo)識相關(guān)聯(lián)。該方法還包括在多個(gè)環(huán)繞式計(jì)數(shù)器中的一個(gè)環(huán)繞式計(jì)數(shù)器的溢出發(fā)生時(shí)，將計(jì)數(shù)器標(biāo)識存儲在溢出FIFO中，處理在溢出FIFO的頭部處的數(shù)據(jù)，通過在溢出FIFO的頭部處的數(shù)據(jù)來標(biāo)識環(huán)繞式計(jì)數(shù)器，讀取存儲在標(biāo)識的環(huán)繞式計(jì)數(shù)器中的值，以及清空標(biāo)識的環(huán)繞式計(jì)數(shù)器。

在一些實(shí)施例中，多個(gè)環(huán)繞式計(jì)數(shù)器中的每個(gè)環(huán)繞式計(jì)數(shù)器具有相同的寬度。

在一些實(shí)施例中，溢出FIFO由所述多個(gè)環(huán)繞式計(jì)數(shù)器共享。

在一些實(shí)施例中，計(jì)數(shù)器架構(gòu)被實(shí)施在網(wǎng)絡(luò)設(shè)備中。

在一些實(shí)施例中，該方法包括重復(fù)處理數(shù)據(jù)、讀取溢出FIFO只要其不為空、標(biāo)識環(huán)繞式計(jì)數(shù)器、讀取值以及清空標(biāo)識的環(huán)繞式計(jì)數(shù)器。