[發明專利]存儲地址分配方法和裝置

有效

• 申請號: 200910077490.4
• 申請日: 2009-02-13
• 公開（公告）號: CN101488919A
• 公開（公告）日: 2009-07-22
• 發明（設計）人: 韓新偉;林云;寧乃東
• 申請（專利權）人: 華為技術有限公司
• 主分類號: H04L12/56
• 分類號: H04L12/56;H04L29/12
• 代理公司: 北京同立鈞成知識產權代理有限公司
• 代理人: 劉 芳

技術領域

本發明涉及通信技術領域，特別涉及一種存儲地址分配方法和裝置。

背景技術

緩存管理是對芯片外掛或內嵌的共享RAM資源進行分配和回收的管理，尤其是在基于存儲轉發數據結構的網絡設備和芯片中，緩存管理的應用都十分廣泛，緩存管理既要保證分配回收的正確性又要保證充足的地址分配回收帶寬，目前比較成熟的緩存管理實現方案有先入先出(First-In?First-out，以下簡稱：FIFO)式緩存管理或比特圖(BITMAP)式緩存管理。

對于FIFO式緩存管理，其原理是使用FIFO存儲緩存地址，初始化時寫入所有的可分配緩存地址，在數據的接收端讀取FIFO頭存儲的地址用于存儲接收數據，在數據的發送端將釋放的地址寫入FIFO進行地址的回收。在緩存地址數目為n時，消耗的內存資源為r＝n·log₂n，單位為比特。

比特圖式緩存管理的原理是用一種位映射的思想將緩存地址映射至一定寬度(如512bit或1Kbit)比特圖中的某一個比特位上，通過搜索比特圖的空閑位來分配空間地址。比特圖式緩存管理在緩存單元很多的時候，如何實現快速搜索是個問題。一種改進的方案是利用BITMAP+FIFO的方式，即在接收到數據時，首先讀取FIFO中的BITMAP的索引，并利用該索引找到對應的BITMAP，然后通過譯碼邏輯電路對BITMAP中未分配地址進行分配。在數據的發送端，首先將釋放的物理地址譯碼為BITMAP信息寫入RAM，如果RAM中某一BITMAP中所有比特全部釋放完畢，則將該BITMAP對應的索引信息寫回FIFO完成地址回收。采用BITMAP+FIFO的緩存管理方式時，若緩存地址總數為n＝x·y，則消耗的總的資源為r＝n+y·log₂y，其中n為總RAM資源數，x為BITMAP的寬度，y·log₂y為FIFO資源數，單位為比特。

發明人在實現本發明的過程中發現，現有技術至少存在如下技術問題：BITMAP緩存管理方式在進行緩存地址分配時的速度慢，造成的延遲時間大，可能不滿足某些應用的要求。

發明內容

本發明實施例的目的是提供一種存儲地址分配方法和裝置，以實現在進行存儲地址管理時提高存儲地址管理速度。

本發明實施例提供了一種存儲地址分配方法，包括：

接收存儲地址分配請求；

對分級比特圖中的第二級比特圖進行雙向搜索；所述分級比特圖包括N個第一級比特圖和所述第二級比特圖，每個第一級比特圖包括M個比特位，第一級比特圖的每個比特位對應一個存儲地址并用于表示對應的存儲地址的空閑狀態；所述第二級比特圖包括與N個第一級比特圖對應的N個比特位，第二級比特圖的每個比特位用于表示對應的第一級比特圖是否存在空閑的存儲地址；M、N均為大于1的整數；

根據對第二級比特圖的雙向搜索結果輸出一個空閑比特位；

根據輸出的第二級比特圖的空閑比特位獲取對應的存儲地址并進行分配。

本發明實施例還提供了一種存儲地址分配裝置，包括：

第一接收模塊，用于接收存儲地址分配請求；

分級比特圖，所述分級比特圖包括N個第一級比特圖和所述第二級比特圖，每個第一級比特圖包括M個比特位，第一級比特圖的每個比特位對應一個存儲地址并用于表示對應的存儲地址的空閑狀態；所述第二級比特圖包括與N個第一級比特圖對應的N個比特位，第二級比特圖的每個比特位用于表示對應的第一級比特圖是否存在空閑的存儲地址；M、N均為大于1的整數；

第一搜索模塊，用于對分級比特圖中的第二級比特圖進行雙向搜索以獲取一個空閑比特位；

分配模塊，用于根據輸出的第二級比特圖的空閑比特位獲取對應的存儲地址并進行分配。

本發明實施例提供的存儲地址分配方法和裝置，采用分級的比特圖，在接收到緩存分配請求時，通過對第二級比特圖進行雙向搜索獲取空閑地址并分配。本實施例提供的基于分級比特圖，利用雙向搜索方法對比特圖進行搜索以獲取儲存地址的技術方案，能夠提高存儲地址的管理速度。

附圖說明

為了更清楚地說明本發明實施例或現有技術中的技術方案，下面將對實施例或現有技術描述中所需要使用的附圖作簡單地介紹，顯而易見地，下面描述中的附圖僅僅是本發明的一些實施例，對于本領域普通技術人員來講，在不付出創造性勞動性的前提下，還可以根據這些附圖獲得其他的附圖。

圖1為本發明存儲地址分配方法實施例的流程示意圖；

圖2為本發明實施例中分級比特圖緩存管理結構示意圖；