[發明專利]針對查找樹的緩存著色內存分配方法和裝置

在審

• 申請號: 201610805579.8
• 申請日: 2016-09-06
• 公開（公告）號: CN107797941A
• 公開（公告）日: 2018-03-13
• 發明（設計）人: 賀鵬;楊馥榕;謝高崗
• 申請（專利權）人: 華為技術有限公司;中國科學院計算技術研究所
• 主分類號: G06F12/0871
• 分類號: G06F12/0871
• 代理公司: 北京同立鈞成知識產權代理有限公司11205
• 代理人: 宋揚,劉芳

本發明實施例提供一種針對查找樹的緩存著色內存分配方法和裝置，此方法包括：構造第一查找樹；確定第一查找樹具有N層結點；獲取N層結點中每層中具有的結點的個數；根據N層結點中每層中具有的結點的個數，從內存的著色顏色中為每層結點分配對應的顏色；各層結點所分配的對應的顏色各不相同；根據每層結點對應的顏色和顏色對應的內存，生成緩存著色后的第二查找樹。根據第二查找樹中每層結點對應的顏色在為每層結點的結點分配內存時，只分配會被映射到對應著色顏色的內存，由于內存與Cache之間存在映射關系，可以保證不同層結點的結點之間不會相互競爭Cache，從而提高了查找性能。

技術領域

本發明實施例涉及存儲技術領域，尤其涉及一種針對查找樹的緩存著色內存分配方法和裝置。

背景技術

在現代計算機層次化的存儲結構中，Cache是位于主存和CPU寄存器之間的一層緩存。Cache通常由容量較小、速度較快的SRAM構成，通過緩存CPU所需要的熱點數據，減少CPU對于主存的訪問，提高訪存的效率、彌補CPU計算速度和主存訪問速度之間的差距，有利于提升計算機系統的整體性能。為了減少主存與Cache之間數據交換的開銷，并且充分利用計算機程序的空間局部性(Spatial Locality)，Cache和主存之間數據交換的單位通常是多個連續的字節組成的Cache行(Cache Line)，比如64字節、128字節等等，所以從Cache的視角考慮，可以認為Cache Line是Cache和主存的基本組成單位。Cache中存放的數據是主存數據的一份拷貝，所以需要一種機制來標識Cache中存放的數據與主存數據的對應關系，即Cache與主存的映射關系。由于Cache的容量往往遠小于主存，所以不能將主存中所有的數據同時緩存在Cache中，當主存中有新的Cache Line需要緩存到Cache中，而所有能緩存該Cache Line的位置全被占用時，就需要將某一個位置的Cache Line替換出去，留出空閑的位置來緩存新的Cache Line；因此，使得數據查找性能下降。

發明內容

本發明實施例提供一種針對查找樹的緩存著色內存分配方法和裝置，用于提高查找性能。

第一方面，本發明實施例提供一種針對查找樹的緩存著色內存分配方法，包括：

構造第一查找樹；

確定所述第一查找樹具有N層結點，所述N為大于或等于1的整數；

獲取所述N層結點中每層中具有的結點的個數；

根據所述N層結點中每層中具有的結點的個數，從內存的著色顏色中為所述每層結點分配對應的顏色；所述N層結點分配對應的顏色的種類數之和為內存的著色顏色的種類數之和；各層結點所分配的對應的顏色各不相同；

根據所述每層結點對應的顏色和所述顏色對應的內存，生成緩存著色后的第二查找樹。

可選地，每層結點分配的對應的顏色的種類數為至少一種，其中，所述至少一種顏色在所述內存的著色顏色中是連續的。

可選地，相鄰各層分配的對應的顏色在所述內存的著色顏色中是連續的。

可選地，所述根據所述N層結點中每層中具有的結點的個數，從內存的著色顏色中為所述每層結點分配對應的顏色，包括：

獲取所述N層結點中的結點的個數之和為X；

根據第k層結點中的結點的個數為X_k，確定為第k層結點分配的顏色的種類數為Y_k，所述Y_k＝(X_k/X)×Y，其中，所述Y為內存的著色顏色的種類數之和；所述k為大于等于1且小于等于所述N的整數；

從所述內存的著色顏色中獲取連續的Y_k種顏色為所述第k層結點分配的對應的顏色。