減少隨機存取存儲器大小同時保持快速數據存取的方法和裝置的製作方法
2023-05-08 23:38:01
專利名稱：減少隨機存取存儲器大小同時保持快速數據存取的方法和裝置的製作方法
發明
背景技術：
領域本發明涉及電子線路。尤其是，本發明涉及一種新穎和改進的方法和裝置，用於在設備中減少RAM的需要而保持從較慢的非易失性存儲器中快速查找和檢索數據。
背景技術：
某些類型的電子存儲器用於幾乎所有的現代電子設備中。電子存儲器能採取軟盤、磁帶、硬碟和集成電路(IC)的形式。存儲器的每種形式具有其優點和缺點。軟盤使得大量數據在可攜式的介質上更新，但具有有限的容量和相當長的讀寫存取時間。磁帶和硬碟均有大量存儲容量的能力，但卻不便於隨身可帶，需要大量的支持硬體，且有慢的存取時間。保存在軟盤、硬碟和磁帶上的數據在存入該介質前常常先以軟體格式化為文件格式。當數據從存儲介質中恢復時，必須運行軟體文件程序以定位並提取所需的數據。這更減慢了數據存取過程。因為它在已經很慢的硬體存取的頂上又增加了軟體層。
IC存儲器通常使用在存儲器需要集成在便攜設備中的地方。改變IC的類型和數量就能調節存儲量。IC要求很小的支持硬體，並特別小，且能提供快速的讀寫訪問時間。某些IC存儲器能方便支持直接訪問而不需要軟體層。
可買到許多不同類型的IC存儲器，對各種設計要求提供解決方法。每種存儲器能滿足若干設計要求，但沒有一種存儲器類型能提供完全的設計解決方法。對任何特定應用選定的存儲器類型取決於計劃的用途及性能設計之間的折衷方案。
最普通類型的IC存儲器是只讀存儲器(ROM)。如名稱的含意所示，該存儲器只能讀訪問。ROM設備一旦經編程後就不能重寫。嵌入的軟體應用使用ROM存儲嵌入的程序碼及數據記錄。在嵌入軟體應用中的處理器從ROM檢索每條指令並執行之。依據在ROM中被編程信息的易失性可以得到不同類型的ROM。如果存在ROM中的信息不希望改變，且期望的設備容量是高的，則使用掩膜編程ROM。在管芯封裝之前此類ROM已掩膜編程。要編程的信息必需是高度穩定並不會修改的，因為編程信息的改變需要掩膜改變。使用掩膜編程ROM的好處對於高容量成熟產品來說在於其成本和時間的節省。對產品可採用其他類型的ROM，但它們不能保證產品容量或代碼的穩定性，這足以證明使用掩膜編程ROM是正確的。
可編程只讀存儲器(PROM)使得設備製造者能編程嵌入的代碼。它允許對代碼修改，但仍不允許ROM在編程以後的修改和擦除。用過時的代碼修改編程的設備仍使用過時的代碼修改，或丟棄之。
可擦除可編程只讀存儲器(EPROM)提供完全擦除程序部分的能力。EPROM的擦除是通過將管芯暴露在紫外(UV)光一段預定時間來實現。管芯能通過在EPROM封裝上的透明窗口暴露在紫外光下。一旦擦除，該EPROM能重新編程。EPROM通常只用於工程開發，在其中期望的代碼修改次數較高。與PROM相比，配置透明窗口的封裝類型的局限性是EPROM高得多的價格因素。雖然EPROM能擦除及重新編程，但對代碼的修改是完全在晶片基礎上做出。即使改變代碼中的一個位也需要完全擦除並重新編程。此局限性及擦除對紫外線的要求將更新EPROM的任務局限在原始設備製造商(OEM)身上。
能擦除選擇的內容並重新編程的設備是電子可擦除可編程只讀只讀存儲器(EEPROM)。傳統的EEPROM使數據能適當更新。即能擦除特定數據單元並且用新的數據改寫同一單元。從EEPROM能迅速讀出數據。但傳統EEPROM的寫周期比讀時間長几個數量級。使用傳統EEPROM的另一缺點產生於傳統EEPROM單元的內在結構。傳統EEPROM單元的結構與標準的PROM相比需要更多的電晶體。結構的增加導致存儲器容量減少且價格升高。這些缺點使得傳統的EEPROM不能在大多數消費電子應用中使用。
隨機存取存儲器(RAM)代表另一種替代存儲裝置。RAM允許有選擇的數據讀和寫。讀和寫能基於字節完成。在將新的數據寫入到以前寫過的字節以前不需要擦除周期。此外，不象EEPROM，RAM的讀和寫周期的時間幾乎相等。RAM的密度及容量可與ROM相比。使用RAM的主要缺點在於存儲數據的易失性。每當RAM掉電時，儲存在RAM中的信息就會丟失。這與ROM相反，後者是非易失性存儲器，即使該IC在供電周期之後存儲器的內容依然得以保存。為了維持RAM的內容，在晶片上必須一直維持電源。這需要對正常供電有電池後備。在電源供應斷開時，如果電源後備掉電，該RAM的內容將丟失。為此，RAM不用於嵌入的代碼而只用於動態存儲器。用於嵌入代碼的RAM易受電池掉電和供電故障的影響。此外，如果RAM用於嵌入的代碼，如蜂窩電話那樣的電池驅動設備，由於RAM的恆定電源要求而具有減少的電池壽命。在RAM用於動態存儲器時，該系統並不關心在供電周期之後內容是否丟失。這就減輕了對電池後備的需求。但是RAM的成本高於ROM的成本。
另一種存儲選擇是通常稱之為快閃記憶體的塊EEPROM。塊EEPROM是允許基於字節讀寫的非易失存儲設備。不象RAM，在塊EEPROM中，在改寫以前寫過的字節以前必須完成擦除操作。但是數據擦除不能按字節完成。擦除只能按塊完成，其中塊的大小由所選的特定存儲設備確定。可擦除塊的大小總是大於一個字節並能是約為64千字節。但是，擦除的次數不是無限的，而受最大周期壽命所限。對塊EEPROM通常推薦的擦除周期壽命是100,000周期。因而，對於在預期設備壽命周期中有大於100,000次的擦除周期需求的應用，就不應該使用塊EEPROM。在需要少於100,000次擦除和改寫周期的應用中，與其他類型可改寫存儲器比較，塊EEPROM具有優點。對於嵌入的代碼應用來說，塊EEPROM優於任何類型的ROM，因為塊EEPROM是非易失的。由於塊EEPROM能改寫電路中部分存儲器，因而，塊EEPROM更優於EPROM。塊EEPROM也不需要紫外光作晶片擦除。由於塊EEPROM設備的低價格和高密度，因此，塊EEPROM優於具有可比較的重寫限制的傳統的EEPROM。在可攜式電子設備中，塊EEPROM用於用戶可配置數據的非易失性存儲。
存在塊EEPROM的數據通常進行格式化以符合文件系統。文件格式規範部分地由塊尺寸的擦除周期決定。數據不是對特定單元的存儲映象，因為塊EEPROM中的數據不能在適當位置重寫。附加軟體開銷導致存儲器訪問時間大大增加。在多任務系統中，訪問時間將進一步增加。在多任務系統中，非易失性存儲器訪問可以由高優先級任務優先佔有。搶佔要求低優先級任務在處理以前等待較高優先級任務的完成。當軟體開銷包括在訪問時間的計算之中時，從塊EEPROM訪問數據的時間可能比對存在RAM設備中的數據的訪問時間要慢1000到10,000倍。
長訪問時間引起了用戶接口問題。在如無線電話那樣的可攜式電子設備中，非易失性用戶可配置的數據常常存入塊EEPROM中。如果訪問電話簿數據是即時發生的，用戶接口需加強，從塊EEPROM檢索數據導致在用戶輸入電話號碼與電話簿中的記錄比較時很慢的用戶響應。這是由於在處理文件系統時的軟體開銷，為了從塊EEPROM檢索任何數據這是必須啟動的。長訪問時間延遲使得在數據檢索必須在某個預定的時間窗內發生的實時系統中引起嚴重的問題。
對於塊EEPROM或任何其他非易失性存儲器的慢訪問時間的一個解決辦法是將所有數據從非易失數據記錄傳輸到RAM。數據記錄能在設備開啟時從非易失RAM傳輸。然後，所有數據能迅速從RAM檢索。這就大大加強了用戶接口。然而，此解決方法引起相當大的成本及空間的缺點。僅僅為了加強用戶接口就需要額外的RAM以冗餘存儲非易失失性存儲器的內容。人們需要一種方法和裝置，用於減少在訪問存儲在非易失存儲器中的數據時，為保持快速用戶接口所需的RAM的數量。
發明內容
本發明是一種新穎的改進的方法和裝置，用於減少支持從較慢的非易失存儲器中快速數據檢索所需的RAM的數量。使用RAM代替非易失存儲器大大減少了數據搜索時間。由於每次訪問非易失存儲器時必須執行的軟體開銷，RAM訪問比非易失存儲器訪問要快幾個數量級。
數據記錄集合能保存在非易失性存儲器。因為與非易失性存儲器訪問相關的軟體開銷，使得非易失性數據記錄的訪問緩慢。使用本發明能大大地增強對存儲在非易失性存儲器中的數據記錄的搜索。當必須搜索存儲在非易失性存儲器的數據記錄時，通常需要對非易失性存儲器的許多次訪問。本發明通過在RAM的預定位置上保存一系列計算的標籤值來減少對非易失性數據記錄的訪問次數。然後對保存在非易失性存儲器的數據記錄的搜索是通過首先搜遍預定的RAM單元尋找對應的標籤值，若找到匹配的標籤值再查找非易失性數據記錄。搜索在RAM中匹配的標籤值將通常搜索匹配數據記錄所需的非易失性存儲訪問次數減少到1。這與在傳統的非易失性數據記錄的搜索中需要多次非易失性記錄的檢索和比較形成對照。
在RAM中分配預定數目的存儲器單元，對應於保存在非易失存儲器中的數據記錄數。在RAM中分配的每個存儲器單元不需要大得能保存在非易失存儲器中存儲的數據記錄。在較佳實施例中對於在非易失存儲器中的每個數據記錄分配二個RAM字節。非易失性數據記錄可以任意長。定義標籤函數H(x)，使得每個非易失性記錄映射對應的標籤值。標籤函數H(x)不需要提供數據記錄到標籤值的1∶1映射。數據記錄到標籤值的1∶1映射將非易失性存儲器訪問數最小化到每次數據記錄搜索僅一次非易失性記錄訪問。
預定的RAM單元保存從對應的非易失性數據記錄的內容所確定的標籤值。當需要搜索特定數據記錄時，對被搜索的記錄計算標籤值。如果搜索到的記錄分配為y，則計算標籤值H(y)。然後，該標籤值H(y)與所有儲存在預定RAM單元中的標籤值比較。由於RAM快速的訪問能力，此步驟很快執行。如果在RAM中找到匹配的標籤值，對應的非易失性存儲器單元識別為對應於特定RAM單元的單元。檢索非易失性數據記錄的內容並與搜索到的記錄比較。如果兩者匹配，則搜索完成。如果檢索到的非易失性存儲器記錄和搜索的記錄不相同匹配，搜索RAM中餘下的標籤值，尋找與搜索到的記錄而計算的標籤值的匹配。搜索繼續進行，直到找到一個相等匹配，或者到達RAM標籤值的終點。
因為主要的搜索是使用RAM標籤表執行，因而，本發明在搜索數據記錄所佔用的時間量方面大大減少。非易失性存儲器記錄只在找到標籤值匹配時才訪問。對多數搜索只需要一次非易失性存儲器訪問。時間的節省提供了增強的用戶接口，同時RAM的減少提供了硬體成本的降低。
根據下面給出的詳細描述結合附圖，本發明的特徵、目標和優點變得更加明白。圖中相似的參考字符在所有圖中互相對應。其中圖1是分層存儲器實現的方框圖；圖2A-2B是方框圖，示出根據查找NV存儲器表的RAM的實現；和圖3A-3B是本發明的RAM實現的流程圖。
具體實施例方式
在任何電子設備中的存儲器和存儲設備按照希望的需求分配。在如無線電話那樣的電子設備中的存儲器通常為非易失性存儲器和RAM形式。非易失性存儲器可以是PROM和非易失性塊EEPROM的組合。在工業中所共知的一種非易失性塊EEPROM類型是快閃記憶體。
使用快閃記憶體的優點之一是其電可擦除和可改寫的能力。如上所述，快閃記憶體的缺點之一是它不能在適當位置更新數據。整個塊必須同時擦除。為了最有效地使用快閃記憶體空間，在快閃記憶體中保存的數據不存儲映象到特定單元，相反，它使用基於文件的存儲系統保存。相對比，存在RAM中的數據可以在適當位置更新且因此能分配一個存儲映象。
圖1示出如無線電話10那樣的一個電子設備的存儲器20的結構的方框圖。所有存入存儲器20的數據在資料庫110中進行管理。本質上易失或瞬時的數據存入RAM 120。可以分配存儲映象給RAM 120數據，因為RAM 120數據能在適當地方更新。然而，具有變化的長度或位置的其他數據片就使用文件系統130管理。文件系統130是軟體程序，該程序確定基於文件數據的格式、位置和大小。對其數據使用基於文件的結構的設備之一是非易失性存儲器140。存在非易失存儲器140中的所有數據必須首先在文件系統130中格式化。在文件系統130下層的分層非易失性存儲器140在訪問存儲在非易失性存儲器140中的任何數據時產生進一步的延遲。在訪問存儲在非易失性存儲器140中的數據時的延遲能產生不希望的延遲，其中數據必須從非易失性存儲器檢索作為用戶界面的一部分。在無線電話中經常應用的使用數據的一個例子是搜索用戶產生的電話簿。
無線電話通常具有保存用戶產生的電話簿記錄的能力。在保存在非易失性存儲器中的電子電話簿中用戶通常能具有超過100個電話號碼及對應的名字。記錄的實際數目只受設計者希望分配給電話簿的存儲器空間大小的限制。每個電話號及名字組成保存在非易失性存儲器中的數據記錄。每個電話號最多有32個字符長。此長度可容納區號、內部分機、接入號和個人識別號以便對指定的號碼自動撥號。對名字可分配任意數目字符，但為方便起見，假設為32字符長。如果我們假設允許有512個電話號碼及名字組合，則必須分配16K非易失性存儲器。當用戶輸入一個電話號碼或名字並希望搜索電話簿尋找對應的保存信息時，必須搜索存在非易失性存儲器中的數據記錄。
存在非易失性存儲器內的數據記錄只能通過文件系統130讀出。文件系統130是在資料庫110之下的層。在非易失性存儲器訪問頂部的多層對於任何對存在非易失性存儲器的數據記錄的訪問產生較大延遲。在傳統的搜索程序期間，從非易失性存儲器檢索數據記錄並與輸入數據比較。如果兩者匹配，就找到對應於此匹配的數據記錄。如果兩者不匹配，丟棄第一個檢索的數據記錄並從非易失性存儲器檢索下一個數據記錄。從非易失性存儲器檢索數據記錄並與輸入數據比較的步驟一直持續到找到匹配或搜索過非易失性存儲器中所有記錄為止。從非易失性存儲器檢索數據記錄之前必須經過的多個層提供延遲。當輸入數據必須與存在非易失存儲器中的大量內容相比較時，對用戶界面來說此延遲過長。輸入名字或電話號碼並希望檢索與此記錄有關的存儲信息的用戶不希望等待很長時間。用戶界面需要看來對用戶是無間隙且瞬時的。
增加與搜索非易失性數據記錄有關的速度的一個方法是在RAM中執行搜索。對存在RAM中數據記錄的訪問時間比從非易失存儲器檢索相等的數據記錄的訪問時間要快幾個數量級。訪問時間的差異歸因於文件系統。RAM不需要數據記錄格式化以及在文件系統下訪問。為了實現在RAM而不是非易失失性存儲器中搜索，可以將所有非易失性存儲器的數據記錄傳送到RAM。隨後，當需要搜索時，所有數據記錄在RAM中都可以得到。此方法具有缺點，就是使用了大量RAM僅僅為了冗餘地存儲在非易失性存儲器中可以得到數據記錄。額外的RAM的成本增加和物理尺寸的增加，使得該解決方法在如無線電話那樣的可攜式電子設備中實現並非理想。
在圖2A中示出一種替代實現方法，它改善了存儲在非易失性存儲器的數據記錄的搜索時間，而不必將整個非失性存儲器的內容保存在RAM中。在圖2A中不使用RAM保存在非易失存儲器中存儲的數據記錄。而是在RAM中定義RAM散列箱(hash bin)220。每個原始的非易失性(NV)記錄210輸入到散列函數。指向輸入NV記錄210的指針存入對應於輸出散列數的RAM散列箱220。散列函數不需要提供NV記錄210到RAM散列箱220的1∶1映射。但是散列函數的選擇是權衡RAM散列箱220的數目及訪問時間的因素進行折衷選擇。散列函數映射越單一，RAM散列箱220所需的空間越大。單獨的散列函數映射的優點是當搜索NV記錄210尋找匹配時，減少對非易失性存儲器的訪問次數。
在圖2A中所示的實現方法如下執行。在初始化電子設備後，每個NV記錄210輸入到散列函數。初始化可以在電子設備的任何情況引起。在無線電話中的初始化在上電時引起。散列函數的一個例子如下所示。
yN=(i=1N5(yi-1)+xi)/(65521)]]>在等式中xi表示輸入到散列函數的特定的NV數據記錄中第i個字節。yi表示處理在特定NV數據記錄中i個字節後散列函數的輸出。數N表示包括每個NV數據記錄輸入的字節數。在上述例子中，每個NV數據記錄是32位元組長。對上述例子中數據記錄長為N＝32。對實際應用使用整數算術執行計算。可以看到，當使用整數算術時從輸入到輸出的映射不是1∶1。
散列函數的輸出落入確定的RAM散列箱220中。指向用作到散列函數的輸入的NV記錄的指針222存入RAM散列箱220。與數據記錄相比較，指針使用較少存儲空間存儲。通常為指針分配4個字節。對具有512個輸入的非易失性數據記錄，需要2K存儲器容納所有指針。這就提供RAM存儲器空間可能的節省。
每個散列箱必須具有保存多於一個指針222的能力。因為散列函數不提供輸入到輸出1∶1的映射，因此，這是必須。在散列函數中缺少1∶1的映射產生了RAM存儲器分配問題。為了保證每個散列箱只有一個指針，就需要確定大量的散列箱。如果確定較少數量的散列箱，每個散列箱就可能需要存儲若干指針。
如果確定64K個散列箱，設計者能保證每個散列箱只有一個指針在其中。因為只需要2K個指針來識別所有數據記錄，很明顯大多數散列箱將含有空指針。分配64K散列箱明顯比將所有非易失性數據記錄加載到RAM中需要更大數量的RAM空間。因此，此解決方案是不可行的。為了減少RAM的需求，一個設計分配少於64K的散列箱。然而，減少散列箱的數目必然增加了任意一個散列箱將包含多於一個指針值的可能性。
為了尋找與某些輸入數據的數據記錄匹配，輸入數據首先要通過散列函數。隨後，散列函數的輸出將搜索程序導向特定的散列箱。如果分散列箱中未存入指針，則在非易失性數據記錄中找不到匹配。如果未找到匹配，這就大大減少了搜索時間。在傳統的搜索中，在判定不存在匹配之前必須要檢索在非易失存儲器中所有數據記錄，並與輸入比較，使用散列箱方法對非易失性存儲器的訪問在判定不存在匹配之前並不需要發生。
如果有指針存在散列箱中，從散列箱中獲得第一指針並檢索該指針指向的NV記錄。然後在輸入和檢索到的數據記錄之間執行全面比較。如果兩者等同，則找到匹配並能得到餘下的有關數據記錄。如果檢索的數據記錄不匹配，則如果存在的話，就檢索在散列箱中下一個指針。重複執行比較和從散列箱檢索指針，直到找到匹配或已經比較了由該散列箱指針指向的所有非易失性數據記錄為止。
在以前的實現中有多次訪問非易失性存儲器的可能性。對非易失性存儲器訪問的次數取決於存在每個散列箱中的指針數。所需的散列箱的數目與散列函數有關。單獨的散列箱的數目增加減少了非易失性存儲器訪問的次數。非易失性存儲器訪問次數的減少是以增加所需的RAM為代價的。
本發明使用一個實現方法，它減少數據記錄搜索次數並降低RAM的需求。本發明的一個方框圖示為圖2B。在本發明中，如前所述，NV記錄210包括數據記錄的集合。然而，在RAM中為標籤值230分配一個存儲器塊代替了在RAM中定義散列箱。如上例所述，存儲在非易失性存儲器中的每個數據記錄是32字符長。在非易失性存儲器內分配512個可用的記錄。這對應於16K的存儲器。本發明為在非易失存儲器中的每條數據記錄分配2位元組RAM空間。為容納512條數據記錄，需要分配1K字節的RAM。因為分配給每個非易失性存儲器記錄的RAM的字節數是常數，可指定RAM的地址單元來對應非易失性數據記錄。作為一個例子，第一非易失性數據記錄將對應於分配在RAM中的頭兩個字節。
分配給每個非易失性數據記錄的兩個RAM字節不足以保存整個數據記錄。而是，這兩個字節保存對應於該數據記錄的標籤值。使用上述同樣的散列函數產生標籤值。計算對應於非易失性存儲器中每個數據記錄的標籤值並存入RAM中預定的位置。因此，本發明使分配的RAM數量最小。為每條非易失性數據記錄分配在RAM中分配兩個字節，並且存在512個數據記錄。因此只需分配1K RAM。
當輸入值需要與非易失性存儲器數據記錄的內容進行比較時，該輸入值首先通過散列函數。然後，輸出散列值與存在RAM中的標籤值比較。當確定一個匹配標籤值，檢索對應於該標籤值位置的非易失性存儲器的內容並與原始的輸入值比較。如果兩者等同，則找到匹配。否則，繼續搜索下面的RAM標籤值，直到另一標籤值產生匹配的數據記錄或達到標籤值表的末端為止。以此方式，大部分的搜索在RAM中執行，訪問非易失性存儲器的唯一時間是在計算的輸入標籤值匹配以前存入的標籤值中一個時。如果散列函數不產生大量的複製標籤值，對非易失性存儲器的訪問數就最小。使用前述的散列函數，對非易失性存儲器的訪問數最小化到對於99％的數據搜索其訪問次數都為1次。
圖3A示出本發明的流程圖。程序從狀態301啟動。每當設備打開電源時程序都初始化。在無線電話的情況，每當用戶打開電話電源，程序啟動301。程序接著進到狀態304，在其中讀出在非易失性(NV)存儲器數據記錄中所有項。接著在狀態308，對NV存儲器項計算標籤值。使用如前述的散列函數那樣的函數對每個NV存儲器項計算標籤值。每個標籤值需兩個字節。
程序隨後進到狀態310，其中計算的標籤值存入預定RAM單元。每個RAM單元對應於在NV存儲器數據記錄集合中的一個項。作為例子，在RAM標籤值表中的第六項是對應於NV存儲器數據記錄中第六項的絕對地址，而不考慮在NV存儲器中實際駐留位置。
標籤值存入RAM以後，任何數據記錄的搜索主要在RAM中執行。狀態320假設項『y』需要與數據記錄的內容比較。在如無線電話那樣的電子設備中，項『y』可以對應於用戶輸入的電話號碼。數據記錄內容對應於與特定電話號碼相關的名字和信息。用戶能輸入電話號碼並希望檢索與此號碼有關的所有以前存儲的信息。
搜索的第一步在狀態322完成，其中計算對應於輸入『y』的標籤值。在狀態324，初始化在搜索中使用的變址計數器。流程接著進到點330。點330不是流程圖的功能單元，僅僅包括用於將在圖3A的流程圖的狀態連結到圖3B的流程圖的狀態。
圖3B從連接圖3A的流程圖到圖3B的流程圖的點330開始。程序從點330進入到狀態340。在狀態340，程序從RAM中檢索對應於變址計數器識別的單元上以前存入的標籤值。程序接著進入344，在那裡對應於項『y』的標籤值與檢索到的RAM標籤值比較。檢索和比較操作非常快發生，因為標籤值只有兩字節長且所有值均駐留在RAM中。如果程序判定兩個標籤值不匹配，程序進入狀態354以檢查在RAM中是否還有另外的標籤項要與輸入的標籤值比較。如果在狀態354，程序識別出在RAM中還有標籤值尚未比較，程序進入到狀態358，變址計數器加1。變址計數器加1以後，程序返回狀態340以檢索由變址計數器識別的下一個標籤值。
如果相反，在狀態354程序判定在RAM中沒有另外的標籤值未與項標籤值比較，程序進到狀態362，在其中程序得出結論，在存儲器中不存在與輸入項匹配的數據記錄。程序隨之結束。在沒有標籤值匹配輸入項的標籤值的情況時，必然沒有匹配該輸入項的數據記錄存儲在非易失性存儲器中。在本發明中，對此情況沒有對非易失存儲器的訪問。因此，搜索可以在甚至不必訪問非易失性存儲器的情況下，判定沒有非易失性數據記錄匹配。
如果在狀態344，程序恰恰判定檢索的標籤值匹配輸入項標籤值，程序進到狀態348。在狀態348，程序從非易失性存儲器檢索對應於以前從RAM檢索到的匹配的標籤值的數據記錄。因此，只有在存儲在非易失性存儲器的數據記錄的標籤值匹配輸入項的標籤值時，才訪問該數據記錄。
一旦實際數據記錄從非易失性存儲器檢索出，程序進到狀態350以執行與整個記錄的比較。整個記錄的比較是必需的，這是因為散列函數不提供從數據記錄到標籤值1∶1的映射。雖然，輸入項和非易失性數據記錄能產生相同的標籤值，但必須比較實際的數據記錄以便實際確認匹配。
如果檢索的非易失性存儲器數據記錄匹配輸入項，即完成成功的搜索。沒有進一步理由再繼續搜索程序，所以，終止程序並等待搜索新的輸入項。
如果在狀態350，程序判定檢索的非易失性存儲器數據記錄不匹配輸入項，如上所述，程序進到狀態354，判斷是否已經搜索了所有RAM標籤值。
圖3A和3B中的流程圖示出如何將最小的RAM數量用於快速搜索儲存在慢非易失性存儲器內的數據記錄。不必將非易失性存儲器數據記錄的整個內容加載到RAM，只需加載一組標籤值到RAM。當需要對一個輸入項搜索數據記錄時，首先使用輸入項產生標籤值，其方法是採用與以前用於產生存儲在RAM中的標籤值相同的散列函數。然後，該輸入項標籤值逐個與存儲在RAM中的標籤值比較。如果找到匹配的標籤值，從非易失性存儲器檢索對應的數據記錄。因此，僅當有較高概率檢索出匹配的數據記錄時，才訪問非易失性存儲器。然後，從非易失性存儲器檢索的數據記錄與輸出項比較。因為兩個記錄產生相同的標籤值，所以，有較高的可能性會獲得匹配。然而，如果檢索出的數據記錄與輸入項不匹配，就搜索餘下的RAM標籤值尋找其他與輸入項標籤值匹配的標籤值。因為散列函數提供輸入到標籤值的接近1∶1的映射，通常每次搜索只訪問非易失存儲器一次。因而在使實現本發明所需的RAM數量最小化的同時又使非易失存儲器訪問的次數最小化。
提供了較佳實施例的前面描述，使本專業的熟練人員能作出或使用本發明。這些實施例的各種修改對本專業的熟練人員是容易明白的，此處確定的一般原則可應用於其他實施例而不必使用創造性。因此本發明不是要局限在這裡所示的實施例，而是依據這裡揭示的原則和新穎特徵相一致的最廣範圍。
權利要求
1.一種用於使快速存儲器的需要量最小的快速數據存取方法，其特徵在於，所述方法包括產生單獨的數據記錄集合；將所述數據記錄集合存入存儲器；對該集合中的每個數據記錄產生標籤值；將這些標籤值存入快速存儲器的預定單元；接收請求搜索該數據記錄集合的輸入項；產生對應此輸入項的輸入項標籤值；該輸入項標籤值與儲存在快速存儲器中的標籤值比較；從數據記錄集合中檢索對應於與所述輸入項標籤值匹配的標籤值的數據記錄；和將檢索的數據記錄與輸入項進行比較。
2.如權利要求1所述的方法，其特徵在於，產生標籤值包括輸入數據記錄到散列函數並將散列函數據的輸出指定為標籤值。
3.如權利要求2所述的方法，其特徵在於，產生輸入項標籤值包括將輸入項輸入到散列函數並將散列函數輸出指定為輸入項的標籤值。
4.如權利要求1所述的方法，其特徵在於，所述數據記錄集合存儲在非易失性存儲器中。
5.如權利要求4所述的方法，其特徵在於，所述非易失性存儲器是快閃記憶體。
6.如利要求1所述的方法，其特徵在於，所述快速存儲器是RAM。
7.如權利要求1所述的方法，其特徵在於，還包括對所有對應於與輸入項標籤值匹配的標籤值的數據記錄重複數據記錄檢索及比較的步驟。
8.一種用於使快速存儲器的需要量最小的快速數據存取裝置，其特徵在於，所述裝置包括用於儲存確定為數據記錄集合的多個數據記錄的第一存儲器；數字處理器；和用於儲存由所述數字處理器計算出對應於存儲在第一存儲器中的每個數據記錄的標籤值的第二存儲器；其中，數字處理器響應為輸入項搜索所述數據記錄的請求，計算對應於該輸入項的輸入項標籤值，將輸入項標籤值與儲存在第二存儲器的每個標籤值比較，檢索對應於匹配該輸入項標籤值的標籤值的數據記錄，並將輸入項與檢索的數據記錄比較。
9.如權利要求8所述的裝置，其特徵在於，所述第一存儲器是非易失性存儲器。
10.如權利要求8所述的裝置，其特徵在於，所述第二存儲器是RAM。
11.如權利要求8所述的裝置，其特徵在於，所述的數據記錄包括在電子電話簿中的項。
12.如權利要求8所述的裝置，其特徵在於，所述標籤值是使用數據記錄作為散列函數的輸入而計算出的散列函數的輸出。
13.如權利要求12所述的裝置，其特徵在於，所述輸入項標籤值是使用曾用於計算所述標籤值的相同的散列函數來計算。
14.如權利要求8所述的裝置，其特徵在於，在所述第二存儲器中為存在所述第一存儲器的每條數據記錄分配兩個字節。
15.一種配置用於用較少的RAM需求來進行快速數據存取的電話，其特徵在於，所述電話包括用於存儲確定為數據集合的多個數據記錄的第一存儲器；數字處理器；和用於儲存由數字處理器計算出對應於存儲在第一存儲器中的每個數據記錄的標籤值的第二存儲器；其中，所述數字處理器響應為輸入項搜索該批記錄的請求，計算對應於所述輸入項的輸入項標籤值，將輸入項標籤值與儲存在第二存儲器的每個標籤值比較，檢索對應於匹配該輸入項標籤值的標籤值的數據記錄，並將輸入項與檢索的數據記錄進行比較。
16.如權利要求15所述的電話，其特徵在於，所述數據記錄集合是電子電話簿。
17.如權利要求15所述的電話，其特徵在於，所述第一存儲器是非易失性存儲器。
18.如權利要求15所述的電話，其特徵在於，所述第二存儲器是RAM。
19.如權利要求15所述的電話，其特徵在於，所述標籤值是使用數據記錄作為散列函數的輸入而計算出的散列函數的輸出。
20.如權利要求19所述的電話，其特徵在於，所述輸入項標籤值是使用曾用於計算所述標籤值的相同的散列函數來計算的。
全文摘要
一種用於減少所需的RAM數量同時保持快數據存取的方法與裝置。數據記錄常保存在非易失性存儲器以便即使在電路斷電時仍維持數據記錄的內容。在本發明中，每個在數據記錄的非易失性RAM集合中的每條記錄輸入到函數H(x)，後者輸出一標籤值。經計算的標籤值存入RAM中預定的存儲器單元。每個經計算的標籤長度上短於存儲在非易失性RAM中的記錄。因此與將整個數據記錄集合存儲在RAM中所需要的RAM相比，對每條數據記錄保存一個標籤值需要較少的RAM。當需要對應y的數據記錄項時，計算H(y)的值。然後該H(y)值與標籤值表中所有值比較。如果找到匹配，從其在非易失性RAM中的位置檢索對應的記錄，並與y比較。如果該值不匹配，搜索標籤值表尋找其他位置匹配H(y)。其結果是僅需要最小量的RAM，就能與非易失性RAM的內容進行非常快速的比較。
文檔編號G06F17/30GK1496523SQ01803840
公開日2004年5月12日 申請日期2001年1月19日 優先權日2000年1月19日
發明者梅幼松, E·J·列克文, 列克文 申請人:高通股份有限公司