聯想存儲器裝置的製作方法

2023-05-30 12:48:01

專利名稱：聯想存儲器裝置的製作方法
技術領域：
本發明一般涉及用於數據處理的聯想存儲器支持，更具體地說，涉及利用改進的聯想技術提供更快的數據處理速度和靈活性的存儲器引擎。
背景技術：
搜索由匹配給定或預定字符串符號的字符串符號組成的緩衝器或其他存儲設備是許多應用中都見到的基本操作，例如但不限於資料庫、通用信息的處理、數據壓縮和計算機語言的處理。通過在字符串中插入新序列或從其中刪除序列來修改字符串也是這些領域中的基本操作，這些字符串操作所花的時間直接影響主應用的執行時間。
當執行串行計算時，即匹配操作在包含M個符號的緩衝器中查找所有出現的N個符號的字符串，所需的步長的最大數量是N*M。當需要在緩衝器內插入字符時，需要將緩衝器中平均一半符號向右或向左移動一個單元，以便騰出用於新單元的空間。在此情況中，需要平均N/2個步長。
已提出許多串行算法來改進這些操作，這些算法是基於包括散列或樹數據結構的多種技術。散列是在如下情況中使用感興趣的字符串是固定長度的字。在此情況中，每個字與唯一編號相關聯，該唯一編號用作詞典中存儲的字的索引。該方法存在的缺點是，它僅在信息是靜態的而且在處理過程中不更改位置時非常有效。而且，生成該編號是成本高的操作，有時可能會將多個字與相同的編號關聯，這需要額外的工作來查找搜索的字。還可以利用後綴樹，後綴樹是其中存儲了緩衝器中存在的所有子字符串的樹結構。當希望查看給定字符串是否位於緩衝器中時，只需向下搜索該樹，一次搜索字符串的一個字符，直到找到該字符串或找不到為止。在這兩種情況中，如果字符串包含M個符號，需要最多M個步長來確定該字符串是否在長度為L的緩衝器中。雖然此搜索方法是快速的，但是構建後綴樹通常是計算成本高昂的。
內容可尋址存儲器或CAM是一種並行解決方案，用於在一次存儲器訪問中查找給定符號或字的位置。該方法對於固定長度的字非常有效，但是不容易擴充到可變長度符號字符串。當搜索能以並行方式在緩衝器中執行時，即當可以同時執行M個比較時，則步長數量減少到N。提出具有並行比較符和標記符的緩衝器存儲與給定符號的每次比較的結果，以便加速字符串搜索。例如參見Almy等人的美國專利號4,575,818；Mayer的美國專利號5,319,762；Eskandari-Gharnin等人的美國專利號5,602,764；或Satoh等人的美國專利號5,448,733。這些公知的設備通常將比較符與緩衝器的每個單元關聯，以及一位的標記符存儲上次執行比較的結果。比較符、存儲單元和標記符以如下方式工作將要在緩衝器查找的字符串的符號廣播到緩衝器的所有比較符。然後這些比較符將給定符號與它們關聯的存儲單元中存儲的符號比較。將比較結果存儲在與該比較符和存儲單元關聯的標記符中。
作為移位寄存器實現的緩衝器允許它們的內容並行地且同步地向左或向右移位一個時鐘信號。在此情況中，可以剛好將緩衝器的整個內容移位一個步長。但是這些緩衝器不提供要移位的其內容的僅一部分，而是僅提供全局移位操作。而且，對應於緩衝器的每個單元結合多個分離的比較符往往整體地增加設備的尺寸和複雜性，由此導致過高的成本和能量使用。
因此針對前面的問題和關注事宜，本發明嘗試利用一種存儲器裝置，它能夠實現非常快速的字符串搜索，插入和刪除，其中利用了一種新存儲器電路，稱為連接存儲器(Connex Memory)(CM)(下文稱為CM)。
具體來說，本發明提出一種連接存儲器裝置，它以聯想存儲器方式工作，但是還包括目前為止尚不是聯想存儲器裝置中公知的靈活性。
公知的數據處理系統大多數經常利用常規方式尋址的存儲器裝置。即，公知的數據系統利用其中包括定義的場所的存儲器裝置，每個場景具有各自特定化的地址。由此，如果系統處理器希望將存儲在地址A的值與存儲在地址B的值相加，則常規存儲器裝置將進入到存儲器裝置內特定定址的位置或單元，並經接口將這些值傳遞到可能執行相應求和處的處理器。在此類的這些系統中，對整個組件的特性和功能，即處理器和存儲器裝置的特性和功能進行了很好的定義，並且彼此不相同。
公知的還有，數據處理系統可以包括多於一個處理器和存儲器裝置，而且這些多個組件可以是執行指令流的系統的一部分。這些多指令流多數據流(MIMD)裝置可以視為緊密耦合的SISD裝置的大集合，其中系統中的每個處理器雖然在整體上結合其他集成的處理器一起工作，但是負責較大任務的一個特定部分。即，MIMD裝置的效用通常限於那些指定的場合，其中要解決的問題往往可拆分成多個相似且相對獨立的從屬問題。MIMD裝置的那些集成組件的特性和功能也進行了很好的定義，並且彼此不相同。
另一個公知的數據處理系統包括單指令多數據流(SIMD)裝置。這些SIMD裝置利用任意數量的處理器全部彼此同步執行相同的程序，但是每個處理器將當前指令指定的運算符應用於不同的運算數，並由此得到各自的結果。SIMD裝置中的處理器訪問集成的存儲器裝置以獲取運算數並存儲結果。同樣地，SIMD裝置的那些集成組件的特性和功能也進行了很好的定義，並且彼此不相同，因為通過計算由必須對存儲器裝置具有某種類型的訪問權以便執行它們的作業的處理器來執行。
雖然公知的數據處理系統因此而能夠處理大量數據，但是為這些處理器和存儲器裝置定義且不會更改的特性限制了可完成多種操作的速度和效率。
因此，還構造了多種體系結構，它們利用不是以常規方式尋址的另一類存儲器裝置。這些存儲器裝置通常描述為「聯想」存儲器裝置，如所指示的，它們不將相應的數據位按存儲器裝置內的物理位置編目。相反，聯想存儲器裝置按其中所存儲的信息的特性或固有性質來「尋址」它們的數據位。即，不由聯想存儲器裝置內的物理位置的名稱來標識聯想存儲器裝置內的數據，而是根據存儲器裝置的每個特定單元中存儲的數據的屬性來尋址。
將固定的或有限大小的關鍵字欄位與大多數聯想存儲器裝置中存儲的所有數據關聯。然後可以利用搜索關鍵字來選擇其關聯的關鍵字欄位與搜索關鍵字匹配的特定數據欄位或多個數據欄位而無論它們命名的位置，以便用於根據指向的指令進行後續處理。
在這些公知的聯想存儲器裝置中，其中存儲的所有數據包括關鍵字欄位和對應的數據欄位。公知的聯想搜索和數據操作技術檢查聯想存儲器內的關鍵字欄位以確定哪個對應的數據欄位包含對於預定命令特別感興趣的數據。一旦識別出，則可以通過更改相應關鍵字欄位內的一個或多個位的狀態來「標出」或「標記」持續感興趣的任何數據欄位，由此餘留下關聯的數據欄位以供用於後續搜索或操作命令。
因此，公知聯想存儲器裝置依賴於能夠觀察關鍵字欄位的內容的控制器，以便識別那些感興趣的數據欄位。雖然這些公知的聯想系統在某種程度上是有用的，但是它們仍存在搜索體系結構上缺乏靈活性的問題，因此它們的效用相應地被降低，同時它們的處理時間卻增加了。
針對前面的問題和關注事宜，本發明嘗試增加公知聯想存儲器裝置的靈活性，以便增加它們的效用，同時減少它們的處理時間。

發明內容
本發明的目的在於提供一種有效率的數據處理系統。
本發明的另一個重要方面是，以增加數據處理速度和效率的方式，提供一種用於數據處理系統的實現有源聯想存儲器的蜂窩引擎或聯想引擎裝置。
本發明的另一個重要方面是，提供一種用於數據處理系統的實現有源聯想存儲器的蜂窩引擎或聯想引擎裝置，它能夠通用地利用關鍵字欄位或數據欄位中的任何單元。
本發明的另一個重要方面是，提出一種用於數據處理系統的實現有源聯想存儲器裝置的蜂窩引擎或聯想引擎，其中在預定命令的執行期間聯想存儲器裝置的關鍵字欄位和數據欄位之間沒有區分。
本發明的另一個重要方面是，提供一種用於數據處理系統的實現有源聯想存儲器裝置的蜂窩引擎或聯想引擎，其各個單元都可以在單個時鐘周期內基於其各自狀態選擇性地並行處理給定指令。
本發明的另一個重要方面是，提供一種用於數據處理系統的實現有源存儲器裝置的蜂窩引擎或其結構是同性質的蜂窩引擎，因此在執行程序期間在不同時間允許存儲在存儲器中的完全相同的信息片段作為關鍵字欄位或數據欄位(的一部分)。
本發明的另一個目的在於提供一種用於有效率的數據處理系統的蜂窩引擎，它允許動態地限制有源聯想存儲器裝置內的搜索空間。
根據本發明的一個實施例，一種用於數據處理系統的聯想存儲器支持包括含n個單元的聯想存儲器裝置。設有控制器用於向聯想存儲器裝置發出指令。時鐘裝置輸出同步時鐘信號，該同步時鐘信號包括每秒預定數量的時鐘周期，該時鐘裝置將同步時鐘信號輸出到聯想存儲器裝置和控制器。控制器在這些時鐘周期的其中之一內全局性地將指令同時傳送到所有n個單元，並將指令同等地應用於n個單元的每一個單元。
通過作為整體來考慮說明書、權利要求和附圖，本發明及其優選實施例的這些和其他目的將變得顯而易見。


圖1是示出根據本發明一個實施例的存儲器引擎的一般性體系結構的框圖，存儲器引擎中包括外部控制器和時鐘部件。
圖2是圖示圖1的存儲器引擎結合不同的總線的框圖，這些總線允許在存儲器引擎的組成部件之間交換信息。
圖3是圖示圖1的存儲器引擎的一般性操作的一個實施例的流程圖。
圖4是圖示圖1的存儲器引擎的一般性操作的另一個實施例的流程圖。
圖5是圖示圖1的存儲器引擎處理「c-find」命令的流程圖。
圖6是圖示圖1的存儲器引擎處理「read」命令的流程圖。
圖7是圖示圖1的存儲器引擎處理「inserf」命令的流程圖。
圖8是圖示圖1的存儲器引擎處理「delete」命令的流程圖。
圖9是圖示圖1的存儲器引擎處理「nexf」命令的流程圖。
圖10是圖示圖1的存儲器引擎處理「jump」命令的流程圖。
圖11是示出將存儲器引擎的存儲器裝置與它的環境實現接口以及將多個存儲器裝置連接在一起所需的輸入和輸出信號的框圖。
圖12是圖示存儲器裝置的內部結構的一個實施例的框圖，其中通過兩個代碼轉換器電路使靜態或動態存儲單元的二維陣列可訪問。
圖13是示出將動態存儲單元與它的環境實現接口所需的輸入和輸出信號的框圖。
圖14是圖示根據本發明一個實施例包括用於符號及其關聯的標記符的存儲裝置的存儲單元的內部體系結構的電路圖，通過存儲單元可以將符號及其關聯的標記符存儲到廣播符號中、從廣播符號中讀取符號或將該符號與廣播符號比較。
圖15是圖示根據本發明一個實施例的圖12所示的代碼轉換器電路的內部體系結構的電路圖，通過該代碼轉換器電路可以訪問二維陣列的存儲單元，並允許生成第一個或最後一個標記的單元的地址。
圖16是圖示作為隨機存取存儲器(RAM)和RAM控制器的組合的緩衝器存儲器的內容的電路圖。
圖17是圖示圖16所示的RAM控制器的內部結構的電路圖。
圖18是示出圖1所示的存儲器引擎的更詳細視圖的框圖。
圖19圖示典型聯想存儲器裝置的內容。
圖20圖示移除了關鍵字欄位和數據欄位之間的傳統區分的聯想存儲器裝置。
具體實施例方式
CM是對均從有限存儲器符號集中提取值的字的字符串的物理支持，通過「設置」附加位將每個字增加，由此使字具有兩個狀態的其中之一已標記或未標記。本文中將術語「存儲器符號」解釋為表示固定長度的連續位的集合，其長度取決於具體應用且不設置先驗值。
本發明的結構允許在一個時鐘周期中執行所有CM命令，且附有約兩倍於目前高速緩衝存儲器技術中通常遇到的延遲的延遲。本文所描述的結構屬於單設的電路，也可以在更精密的電路中複製它。圖1圖示根據本發明一個實施例的存儲器引擎205的一般性體系結構、以及它與外部控制器255和同步時鐘電路256的操作關係。將容易認識到的是，外部控制器255和存儲器引擎的操作是通過利用從時鐘電路256發出的公共時鐘信號來協調的。而且，在不背離本發明較廣泛的方面的情況下，本發明設想外部控制器255可以具有任何數量的電路專用的配置，只要外部控制器255能夠向存儲器引擎205發出命令和從其中接收數據即可。
如圖2所示，CM 206與組織為緩衝器池的線路存儲器隨機存取裝置200相關聯，緩衝器均具有與CM 206的大小相等的大小，且由存儲器引擎205(下文稱為連接引擎(Connex Engine)(CE))控制。這些緩衝器(也稱為線路)的目的是能夠對長於CM 206內可容納的字符串的字符串執行搜索、插入和刪除操作，以及提供較低的實現成本和降低的功耗，稍後將對此予以更詳細的論述。
圖3圖示CE 205的一般性應用，開始於框302，其中將先前選定用於由控制器255檢查的字符串加載到聯想線路存儲器206中。字符串由數據符號的集合構成，出於圖示的目的，將其加載到線路存儲器200中的一個或多個緩衝器中直到完全存儲在其中為止。由此，線路存儲器200中的每個緩衝器包含字符串的不同部分，每個部分具有等於CM 206的大小的大小，如先前所論述的。
如圖3的框304所示，CE 205經數據RAM總線100將要檢查的第一緩衝器的內容從線路存儲器200加載到CM 206。CM 206然後根據從控制器255輸入的命令對字符串的已加載部分執行期望的字符串操作或檢查，如圖中框306所示。CM 206然後在框308確定是否應該在字符串的已檢查部分設置一個或多個數據標記符(datamarker)，選擇性地在框307設置此類標記符並在框309復位該標記符。將容易認識到的是，有關是否應該在已經移到CM 206的字符串的給定部分內設置一個或多個數據標記符的決策將取決於控制器255輸入的具體命令，稍後將對此予以更詳細的論述。
在CM 206中檢查字符串的一部分之後，而且在有必要的情況下，在其中設置一個或多個標記符，CE 205然後將CM 206的內容存儲回線路存儲器200的第一緩衝器，加載第二緩衝器的內容並執行相同的操作。CE 205繼續這樣的模式將緩衝器加載到CM 206，在CM 206中執行字符串處理並將CM 206的內容存儲回緩衝器，直到處理了整個字符串為止。因為搜索的符號字符串中存在的局部性等級的原因，加載到CM 206中的緩衝器的數量隨著搜索操作次數不斷累積而降低，從而快速將批量操作限於少量的緩衝器中。
因此，本發明的重要方面在於響應從控制器255發出的命令，無需重複檢查線路存儲器200的緩衝器中存儲的字符串數據的整體，因為設置的標記符的存在(或不存在)使某些緩衝器可以免於後續複查。例如，如果控制器255發出的命令指示對給定一組數據元素進行搜索(稍後將對此予以更詳細的描述)，CM 206將首先遍歷線路存儲器200中的每個緩衝器中的每個字符串，並且它在搜索數據元素的第一個時且適合的情況下設置標記符。然後對線路存儲器200中的緩衝器的後續檢查將限於包含設置的標記符的那些緩衝器，而排除沒有設置的標記符的那些。由此，本發明的CM 206無需重複地搜索不可能包含要搜索的數據元素的所有組成部分的那些緩衝器，由此顯著且漸進地消除了大量數據的複查，因此加速了響應時間。
本發明的另一個重要方面在於CM 206能夠在一個時鐘周期內全部彼此並行地執行許多操作。因此，具體來說參考圖3和框306、307、308和309，CM 206允許在一個時鐘周期內並行處理這些框。因此將容易認識到的是，圖3以及本發明的其他框圖所含的各個框不應解釋為在它們執行時在時間上是順序的，相反CM 206允許一個時鐘周期內並行處理許多框，如先前所論述的。
下一部分結合控制器255發出的具體命令更詳細地描述CM 206的操作和CE 205的操作。
CM 206通過一般從控制器255接收命令和數據來操作。當命令需要數據運算數時，例如查找CM 206中當前存儲的字符或符號、字符串中所有出現的給定符號或數據元素的「find」命令，將命令和符號同時饋送到CM 206。CM 206支持多種類型的命令，這些命令分成兩個主要類別正向命令和逆向命令。每個類別組包含三種類型的命令設置或復位與單元相關聯的標記符的命令，訪問設置了標記符的單元中存儲的字的命令，以及修改設置了標記符的單元中存儲的字的命令。雖然本發明支持與每個存儲字關聯的一位標記符，但是可以使用多個位來對每個字的狀態進行編碼而不會背離本發明的更廣泛的方面。
我們首先描述屬於正向命令組的命令。在逆向組中的指令表現為鏡像-映像方式，稍後將對此予以描述。在下文的論述中，術語符號表示任何位邏輯塊。對於一些應用，8位字節可以是優選的實現。在其他應用中，例如染色體字符串的生物處理中，符號可以是4位實體。
正向命令為了執行字符串search(搜索)和insert(插入)操作，一次一個符號輸入的數據字符串連同命令饋送到CM 206。當命令是搜索時，將每個符號同時與CM 206中當前存儲的所有符號比較。還可以執行兩種類型的比較有條件和無條件的比較。無條件搜索字符串的第一個符號，而在CM 206中已發現前一個符號的基礎上有條件地搜索後續符號。
當操作是插入時，CM 206中位於插入點右手邊的符號向右移位一個位置，並將新符號存儲在插入點處。在本發明的一個實施例中，插入點是設有標記符的第一個符號的位置。
本發明的另一個重要目的在於，由於CE 205系統體系結構的效率的原因，搜索和插入操作僅在一個時鐘周期內執行，如先前所論述的。
對於字符串delete(刪除)操作，從CM 206中的刪除點讀取連續的符號，然後將該點右邊的所有符號向左移位一個位置。同樣地，刪除點是具有設置的標記符的第一個或最後一個存儲單元的位置。該操作的讀取和移位組成部分同時執行，且僅耗用一個時鐘周期。
現在將解釋實現上述操作的命令的描述。
find和cfind命令是訪問命令。如圖3和圖4的流程圖所示，可以經控制器255將「find」命令連同CM 206以聯想方式與它的M個存儲單元中所含的所有符號進行比較的符號一起饋送到CM 206。該命令的結果是對其內容與該給定符號匹配的單元之後的所有單元設置標記符。所有其他標記符被復位。圖3的框302-314說明一般性意義上的所有命令的執行，而圖4的框304′、303和305說明根據本發明另一個實施例、在加載的字符串可以整體容納在CM 206的那些情況(這裡是圖3中的步驟304和圖4中的對應步驟304』)中find命令的具體實現，稍後將對此予以更詳細的論述。如圖4所示，find命令的執行在一個時鐘周期內發生，其中參考字母E表示在圖4的find命令執行之後返回到圖3的一般性流程圖。例如，假定本發明表示符號，通過在該符號周圍加設括號來設置標記符，還假定字符串「RONAND ROBERT」當前存儲在CM 206中。將命令find(R)發到CM 206的結果是使它的內容更改成「R[O]N AND R[O]BERT」。設置兩個O符號的標記符是因為它們都在含作為要查找的符號的「R」的單元之後，如圖3的框308中所示。
用於「有條件查找」的cfind命令的工作方式與find相似，因為也將符號連同命令饋送到CM 206，然後CM 206執行該符號的聯想搜索，但是在此情況中，比較中僅涉及線路存儲器200中具有先前設置的標記符的單元或緩衝器，如圖5的框322所示。結果是出現匹配的單元之後的單元被設置標記符。所有其他標記符被復位。使用上面相同的示例，並假定兩個「O」符號仍設置了它們的標記符，則命令cfind(O)將聯想比較限制於僅標記的單元。因為它們都包含「O」，所以兩個比較都成功，並且在含有「O」的單元的右邊的單元的標記符設置為「RO[N]AND RO[B]ERT」。假定現在執行cfind(B)，則僅第二個標記的單元顯示出成功比較，E符號的標記符設置為「RON AND ROB[E]RT」。該過程繼續直到搜索了所有符號或數據元素為止，為此將成功(或非成功的)匹配輸出到控制器255，如圖5的框324-326所示。
如本文所解釋的，將容易認識到的是，圖3圖示一般可應用於所有輸入的命令的本發明的基本功能實施。因此，結合例如框302描述的「字符串」可以包含一個或多個數據元素，具體取決於所發出的命令以及正在操縱或檢查的特定數據的特性。而且，雖然圖3假定加載的字符串大於CM 206中可容納的大小，因此需要將相同的字符串分開從線路存儲器200移到CM 206以便檢查，但是可能情況並不總是如此。如圖4所示，備選方法包括將具有CM 206能夠容納的大小的那些字符串直接加載到CM 206中，如框301所示。然後根據具體的命令，加載到CM 206中的字符串的檢查將在框303中執行，而框305將按需要設置或復位標記符。
將容易地認識到的是，在CM 206可以容納要檢查的數據的那些情況中，通過選擇性地旁路CE 205和線路存儲器200，可以相應地節省處理時間和花費的能量。
另一個提出的命令是read-forward(正向讀)命令。read-forward命令使CM 206返回第一個單元、即設有標記符的最左邊的單元中存儲的符號。在呈示的方案中，根據接受的實踐，CM 206的最左邊符號具有地址0，最右邊符號具有地址M-1，假定M個符號的存儲容量。
一旦執行了讀取操作，則復位剛讀取的單元的標記符，並且剛讀取的單元的下一個單元的標記符變為被設置。假定CM也包含「RO[N]AND RO[B]ERT」。read-forward命令的結果是CM輸出的符號「N」，最左邊的標記符更改為如下「RON[]AND RO[B]ERT」。現在標記空格符號。圖6將該過程圖示為框330，當發出read-forward命令時，其操作可以包括在圖3的框308中。
另一個提出的命令是insert(插入)命令。insert命令與符號X一起應用於CM 206。該命令僅對CM 206的第一個單元或最左邊的標記的單元生效。當插入符號X時，第一個標記的單元右邊的所有單元的內容和狀態(包括標記符)都向右移位一個位置，並將符號X存儲在第一個標記的單元的先前位置中。將剛接收到新符號的單元的標記符復位。設置該單元右邊的單元的標記符例如，假定CM 206包含「R[O]N AND R[O]BERT」則insert(X)使CM 206的內容成為「RX[O]NAND R[O]BERT」。圖7將該過程圖示為框332，當發出insert命令並且字符串大於CM 206內最初可容納的大小時，其操作可以在圖3的框308中完成。
另一個提出的命令是delete(刪除)命令。delete命令通過如下方式工作移除第一個標記的單元中存儲的符號，然後將所有單元的所有內容向左移到該單元的右邊。假定CM包含「RO[N]ANDRO[B]ERT」，則在delete命令生效之後，CM包含「RO[]ANDRO[B]ERT」。圖8將該過程圖示為框334，當發出delete命令並且字符串大於CM 206內最初可容納的大小時，其操作可以在圖3的框308中完成。
另一個提出的命令是next(下一個)命令。next命令沒有參數，將第一個或最左邊的標記的單元的標記符復位。這樣，當設置多個標記符時，可以重複使用該命令以允許訪問CM 206的所有標記的單元。例如，假定CM 206包含「R[O]N AND R[O]BERT」則next的執行使CM 206的內容成為「RON AND R[O]BERT」。圖9將該過程圖示為框335，當發出next命令並且字符串大於CM 206內最初可容納的大小時，其操作可以在圖3的框308中完成。
簡要回顧圖1，index(索引)輸出13攜帶CM 206中的第一個標記的單元的線性地址。例如，如果CM 206的第一個或最左邊的單元設置了其標記符，則index返回0。如果第二個單元被標記，則index返回1。假定CM 206包含字符串「RO[N]AND RO[B]ERT」，且CM 206的最左邊的單元中存儲字符串「RON」，則index返回2，因為符號「N」存儲在CM 206的地址2處。
另一個提出的命令是write-one(寫一次)命令。將write-one命令連同符號S應用於CM 206，該符號S被寫入到CM 206的第一個或最左邊的標記的單元。該單元的標記符被復位，並設置該單元之後的單元的標記符。
另一個提出的命令是write-all(全寫)命令。將write-all命令連同符號S應用於CM 206，該符號S被同時且在一個時鐘周期內寫入到CM 206中設有標記符的所有單元。這些單元的標記符被復位，並設置這些單元之後的單元的標記符。
另一個提出的命令是write(寫)命令。將write命令連同地址A和符號S應用於CM 206，該符號S被存儲在CM 206中地址A的單元中。該命令與隨機存取存儲器中的寫操作相似。與地址A的單元關聯的標記符被復位，並設置該單元之後的單元的標記符。
將read(讀)命令連同地址A應用於CM 206，並使CM 206輸出位於地址A處的單元的內容。該命令與隨機存取存儲器中的讀操作相似。不修改該操作訪問的單元的標記符。
另一個提出的命令的是jump(跳轉)命令。將jump命令應用於CM206，以解決如下那些情況CM 206中存儲長度變化的字符串，其中具有完全相同的前綴和後綴(即以相同的序列開始兩個字符串，並以相同的序列結束兩個字符串)，但是具有不同的中間部分，即可能長度不同，而且如果所有字符串的前綴的最後一個符號是被標記，則CM 206支持稱為jump的操作，該操作取一個運算數，並且其行為通過一個示例最好地說明。
假定CM 206在其存儲器的不同部分包含兩個字符串「AAA％BB％CCCC」和「AAA％DDD％CCCC」，其中「％」表示用作將來的具體應用的定界符的唯一符號。而且假定AAA前綴之後與「％」關聯的標記符已被設置，例如通過執行命令find(A)、cfind(A)、cfind(A)「AAA[％]BB％CCCC」和「AAA[％]DDD％CCCC」。jump(s)命令的目的(其中s是符號)是要將這些標記符從它們當前的位置遷移到在CCCC後綴之前的未標記的「％」符號，並以s符號替代它們。
例如，在命令jump($)的第一實例化之後，上面示例的CM 206中的兩個字符串將如下更改「AAA％[B]B％CCCC」和「AAA％[D]DD％CCCC」。在發出第二個jump($)命令之後，字符串變成「AAA％B[B]％CCCC」和「AAA％D[D]D％CCCC」。第三個jump($)命令之後「AAA％BB$CCCC」和「AAA％DD[D]％CCCC」。第四個jump($)命令之後「AAA％BB$CCCC」和「AAA％DDD$CCCC」。因此，響應jump命令，CM 206執行如下動作設置了標記符的所有單元將它們的符號與特殊的定界符符號(在我們的示例中為％符號)比較。如果發現匹配，則將該特殊定界符替換為與命令一起提供的符號s(在我們的示例中為$符號)並將該單元的標記符復位。否則，如果未出現匹配，則將該單元的標記符復位，並將單元的標記符直接設置到右邊，實際使標記符向右移動一個位置。圖10的框336圖示在如下那些情況中jump命令的特定實現加載的字符串可以整體容納在CM 206內(這裡是圖3中的步驟304和圖10中的對應步驟304』)，其中參考字母E表示執行圖10的jump命令之後返回到圖3的一般性流程圖。
jump命令在資料庫應用中是重要的，其中符號的字符串包含多對欄位標識符，或定界符和數據值，其中標識符具有固定長度，但是包含數據值的欄位不具有固定長度。如此，本發明有利地提出一種用於檢查字符串內的欄位的方法，每個欄位包含隨機大小的數據值，而同時標記字符串中的特定數據欄位而不管它們的內容。而且，因為對字符串中標記的單元的每次比較在一個時鐘周期內執行，所以可以快速且有效率的方式完成字符串的檢查。
本發明的另一個重要方面在於jump命令使用預定定位符符號替換字符串中的定界符符號。因此可以利用定位符符號來標記特定數據欄位的結尾，而不管長度，或者可以利用它來使搜索的數據欄位之後的數據欄位能夠被標記。
如上文所描述的，jump命令允許並行地檢查CM 206中存儲的多個字符串，因此允許並行地識別每個字符串中的定界符符號，其中定界符符號的每次識別和選擇性地替換在一個時鐘周期內發生。
逆向命令迄今描述的搜索(search)、插入(insert)和刪除(delete)機制總是應用於CM 206的第一個標記的單元，並且當它們作用於其他單元時，將那些機製作用於第一個標記的單元的右邊。CM 206還支持向後或逆向查找(find)、插入(insert)、刪除(delete)、下一個(next)和索引(index)操作，其中這些操作應用於CM 206的最後一個標記的單元。它們的行為鏡像上文描述的正向查找(forward find)、插入(insert)、刪除(delete)、下一個(next)和索引(index)操作的行為。
reverse-find(逆向查找)命令是連同符號s一起被饋送到CM 206的命令，該命令設置包含符號s的單元的左邊的單元的標記符。所有其他標記符被復位。如果CM 206包含「JOHN AND JOHNNY」，則reverse-find(N)將按如下設置這些標記符「JO[H]N[A]NDJO[H][N]NY」。
Reverse-cfind命令是逆向的有條件查找的命令，它與符號s一起被饋送到CM 206，並且CM 206以聯想方式僅搜索標記的單元。包含符號s的副本的所有此類單元得以設置了它們左鄰的標記符。復位所有其他的標記符。假定CM 206包含「JO[H]N[A]NDJO[H][N]NY」，則reverse-cfind(H)將這些標記符更改為「J[O]HNAND J[O]HNNY」。
Reverse-insert(逆向插入)命令是連同符號s一起被饋送到CM 206的命令。將最左邊標記的單元以及其線性右邊的所有單元的內容向右移一個位置，並將符號s存儲在最左邊的標記的單元。該單元的標記符不更改。例如，在「JO[H]N AND JO[H]NNY」中逆向插入「X1」得到新的CM 206的內容「JO[X]HN AND JO[H]NNY」。
Reverse-delete(逆向刪除)命令是通過讀取或移除最左邊單元中的符號，並將其右邊的所有單元的內容向左移一個位置。最左邊標記的單元的標記符被復位，並設置其左邊的單元的標記符。例如CM 206包含「JO[H]N AND JO[H]NNY」，則逆向刪除的結果是「J[O]N ANDJO[H]NNY」。
限制範圍的命令如先前所指示的，CM 206還支持一些操作，這些操作僅作用於其地址大於兩個附加命令可以設置的某個編號的單元。其操作域限於地址大於限制的單元的命令稱為受限命令。在此情況中，搜索(search)、insert(插入)和刪除(delete)操作不是CM 206中的全部M個字，而是它的較小部分。在此情況中，當執行查找(find)、cfind、插入(insert)或刪除(delete)操作時，僅作用於CM 206的連續單元塊中的單元。該單元塊由位於CM 206的地址解碼部分中的特殊地址寄存器在左邊定界，延伸到CM 206的最後一個單元，即最右邊單元。
Set-limit(設限)是將受限命令的下限地址設置為第一個或最左邊的標記的單元的命令。例如，如果CM 206包含字符串「RO[N]ANDRO[B]ERT」，則設限命令將限制地址設為2，因為最左邊的標記的符號是「N」，在CM 206中地址2處。
Set-limit-address(設限地址)是連同地址A一起應用於CM 206的命令，而且該命令將此地址存儲在保存限制地址所在的內部存儲器中。
Limited-find(受限查找)、limited-cfind、limited-reverse-find(受限逆向查找)和limited-reverse-cfind都是受限命令，它們以與find(查找)、cfind、reverse-find(逆向查找)和reverse-cfind命令相似的方式工作，只是僅應用於其地址大於或等於限制地址的單元。
limited-write-all(受限全寫)命令連同符號s一起被應用於CM206，並且以與write-all(全寫)命令一致的方式工作。它將符號s寫入其地址大於或等於限制地址的標記的單元中。
CM 206輸出多個布爾信號以反映其標記的單元的狀態。
1)如果在CM 206中至少有一個標記的單元，則CM 206將一個信號設為1，否則設為零。
2)如果在整個CM 206中剛好有一個標記的單元，則CM 206將一個信號設為1，否則設為零。
3)如果上次有條件查找(conditional-find)類型命令(正向、逆向或受限)不成功(沒有設置任何標記符)，則將一個信號設為1，CM 206自動返回到查找類型操作，這可能會設置一些標記符。
4)如果具有預定二進位模式的一個或多個字符設置它們關聯的標記符，則將一個信號設為1。這些字符用於表示空或無效符號的位置，正在由操作設置的其標記符表示必須由外部控制器255尋址的非常條件。
5)CE將一個信號設為1，以指示緩衝器都不包含設置了標記符的符號或RAM控制器將所有緩衝器加載在CM中，以及沒有餘下緩衝器要加載。
連接引擎如前文所提及的，圖2中圖示了連接引擎(CE)205。它是利用隨機存取存儲器實現的、管理存儲在CM 206和線路存儲器200的緩衝器(也稱為線路)中的符號的字符串的電路。每個線路具有容量等於CM206的容量，包含M個(N+1)位的字。CE 205在如計算機或處理器的外部實體的控制下，允許交換要寫入包含線路或緩衝器的線路存儲器200(LM)或從其中讀取的CM 206的全部內容。寫操作將線路的內容寫入到CM 206中。讀操作將CM 206的內容存儲在線路中。這兩個操作都耗用一個周期。外部處理器可以使用insert(插入)或write(寫)命令將信息寫入到CM 206中，並經數據輸入總線10饋送符號。可以經兩條路徑從CE 205讀取符號一條是經由CM 206，例如通過在命令線14上發出讀命令，並在數據輸出總線11上捕獲符號。另一條路徑是根據具體實現直接從LM 200中的線路讀取含有一到多個符號的字。在此情況中，經字地址總線203將字的地址發送到CE 205，從數據字總線204獲取這些字。data-ram總線100允許將CM 206的內容存儲在LM 200的給定線路中或從中讀取該內容。該總線包含M*(N+1)條導線並允許在一個時鐘周期內讀取或寫入整個CM 206。
圖16示出構成LM的兩個組件的框圖。一個是其中存儲線路的隨機存放存儲器(RAM)130，另一個是RAM控制器120。RAM控制器的目的是將線路快速地饋送到CM 206，以便可以快速處理RAM中的線路集合中存儲的符號的字符串。為此，RAM控制器執行經RAM的審查通過(pass)，其中它掃描存儲在RAM中的線路的集合併將選擇的子集發送到CM 206以供處理。RAM控制器為RAM中的每個線路保留存儲器的兩位。第一位指示是否應該在當前審查通過期間，將它關聯的線路發送到CM 206。RAM控制器自動且在恆定的時間內生成其第一位設為1的線路的連續地址，並允許將它們的內容存儲在CM 206中以供處理，以及從CM 206中寫回來。當CM 206將剛處理的線路存儲回RAM時，將No-flag(無標誌)信號15的值存儲在RAM控制器管理的該線路的第二位。在當前審查通過結束時，RAM控制器將與所有線路關聯的所有第二位的值複製到它們關聯的第一位。該新的位集合指示哪些線路得以設置標記符，並應該在下一個審查通過中處理。
在RAM中不是所有線路而是小部分包含有效信息的情況中，其中所有線路是連續存儲的，且在線路地址0處開始，可以將最後一個有效線路的地址指定到RAM控制器以將它的初始審查通過限於該有效線路組。由外部處理裝置使用限制地址207信號將該地址饋送到RAM控制器。
可以在包含CM206的同一個矽晶片上或使用現有的存儲器電路在矽晶片外實現L個線路集合的LM 200。在這兩種情況中，CE 205用於通過如下方式管理存儲在L個線路中的信息將存儲在線路中的信息送到CM 206中，在CM 206中執行諸如先前部分中描述的那些命令的字符串命令，將CM 206的內容送回線路，允許在比CM 206的M個符號的存儲容量長得多的字符串中執行字符串操作。
當需要insert(插入)和delete(刪除)操作時，不以符號將線路填充到容量極限，而是僅部分填充，以便允許按這些操作在CM 206中擴大和縮小符號的字符串。在此類情況中，以正在被處理的字符串中未發現的預定二進位模式來初始化未包含有效符號的CM 206的單元。CM 206生成稱為中斷的外部處理實體的信號，在圖2中標為101。當包含該特殊二進位模式的CM 206的一個或多個單元設置它們的標記符時，激活該信號。
CM 206及其外部連接我們區分一下兩種類型的連接。一種類型對應於CM 206與它的環境的互連，另一種類型對應於電路的擴展所需的信號，即多個CM206電路連接在一起以增加存儲量的情況。
在下文中，我們假定基本CM 206塊可以存儲存儲器的M個字，以及每個字長度為N+1位，N位用於符號和1位用於標記符。
下面列出了圖11所示的CM 206的系統連接。圓括號(如果存在的話)中的數字表示每個信號的位數。當使用對數函數時，假定它是以2為對數的底。
·Data-in(M)用於在CM 206中輸入符號的N位字的數據輸入10。
·Data-out(M)用於從CM 206讀取符號的N位字的數據輸出11。
·Address(log(N))log(N)位的地址輸入12，其中log是以2為對數的底。
·Data-RamM*(N+1)位的雙向數據輸入100和輸出，允許將存儲緩衝器或線路的其中之一的內容寫入到RAM 200中的線路中或從其中讀取內容。
·Index(log(M))log(M)位的輸出13，根據上次執行正向還是逆向操作，它保存第一個或最後一個標記的單元的地址。
·Interrupt(1)該信號由CM 206為外部處理實體生成，它指示包含用於指示空或無效條件的預定義特殊二進位配置的一個或多個單元設置其標記符。
·Command(5)命令代碼的5位輸入14，表示CM 206要執行的操作。
·No-flag(1)二進位輸出信號15，指示CM 206不包含任何標記的單元。
·No-eq(1)二進位輸出信號16，指示上次有條件查找(conditional-find)系列命令(正向、逆向或受限cfind)未設置任何標記符。
·One-flag二進位輸出信號17，指示CM 206剛好包含一個標記的單元。
·clock時鐘信號的輸入信號24，它控制CM 206的操作。
信號data-in、addr和com相對於有效時鐘沿具有關聯的建立和保持時間。信號data-out、index、no-flag、no-eq、one-flag在與訪問存儲器關聯的延遲之後變得穩定。該延遲是相對於時鐘信號的有效沿來測量的。
當多個CM 206電路或模塊在一維陣列中連接在一起，從而擴展內部移位寄存器時，使用多個信號以線性方式將CM 206模塊連結在一起。圖11中示出這些信號，並描述如下。
·Data-left-in(N+2)從前一個模塊接收的信號26且攜帶符號(M位)、其關聯的標記符(1位)和與該標記符(1位)關聯的比較符的輸出的二進位表示。
·Data-left-out(N+2)生成到前一個模塊的信號25且攜帶符號(M位)、其關聯的標記符(1位)和與該標記符(1位)關聯的比較符的輸出的二進位表示。
·Data-right-in(N+2)從下一個模塊接收的信號19且攜帶符號(M位)、其關聯的標記符(1位)和與該標記符關聯的比較符的輸出的二進位表示。
·Data-right-out(N+2)生成到下一個模塊的信號18且攜帶符號(M位)、其關聯的標記符(1位)和與該標記符關聯的比較符的輸出的二進位表示。
·Line-in(2)從X代碼轉換器電路接收且用於擴展結構的兩個信號23。
·Line-out(1)為X代碼轉換器電路生成的信號22。
·Column-in從Y代碼轉換器電路接收且用於擴展結構的兩個信號20。
·Column-out為Y代碼轉換器電路生成的信號21。
標題為「內部結構」的部分中更詳細地定義了前四個信號組。如果這8個連結不用於擴展存儲器，則必須使用常規技術正確地連接和/或中止它們，以便允許CM 206系統的正確操作。
CM 206的內部結構圖12是示出包括CM 206的單元30的二維陣列的框圖，使用信號將它與其他CM 206或CE 205電路實現接合，這些電路允許選擇單元並報告有關標記的單元的位置的狀態信息。單元陣列由按二維陣列組織的M個N+1位單元組成。選擇二維是出於兩個原因。第一，為了使矽區域的利用最大化，其次，為了使CM 206中傳播信號相關的延遲最小化。不使用RAM電路中常見的典型解碼器，CM 206而是使用代碼轉換器電路，因為需要根據執行的命令將地址編碼、解碼和轉碼。二維方法要求使用兩個代碼轉換器電路，每個維對應一個。
將容易地認識到的是，或者可以一維陣列的存儲單元形式構成CM 206，而不會背離本發明的更廣泛的方面。
圖12所示的CM 206的內部結構包括如下子系統·符號單元用於符號的存儲器或動態存儲器、單元由M個單元的二維陣列30構成，這些單元各用於存儲器中所含的每個符號(第一個單元位於第一線路以及2維陣列的第一列中)。出於呈示的目的，在表1(如下)中將這些線路從下向上按升序編號，而將列按從左向右按升序編號。
·Data-RamM*(N+1)位的雙向總線100，它允許將存儲器線路中存儲的M個符號及其關聯的標記符(這裡假定位於符號單元區域(30)中)寫入到外部數據存儲器或從其中讀取。選擇此傳輸中涉及的線路由X代碼轉換器電路39生成的line-select 106信號來執行。
·Interrupt(中斷)該1位信號由CM 206中一個或多個單元生成，這一個或多個單元包含用於表示空單元或含有無效符號的單元的預定義唯一二進位模式，使得一個或多個單元設置它們關聯的標記符。
·X代碼轉換器該電路39包含結合Y代碼轉換器電路40用於尋址和訪問CM 206中的單元的邏輯。
·Y代碼轉換器該電路40包含結合X代碼轉換器電路39用於尋址和訪問單元陣列中的信息所需的邏輯。
·兩輸入AND門門34接收兩個代碼轉換器電路生成的eq信號36和41，並生成信號one-flag(1標誌)35。
·這兩個代碼轉換器電路將CM 206的內容劃分成三個區域位於第一個標記的單元之前的單元的集合，第一個標記的單元和開始於第一個標記的單元的單元的集合。
下文列出的信號對CM 206電路的內部部分操作。因為包含M個單元的二維陣列的原因以及因為必須計算最低或最高地址標記的單元的地址，所以代碼轉換器電路的操作依賴於幾個關鍵信號line-out、line-in、column-out和column-in。
·Line-outline-out信號42的數量是 將line-out信號的每一個與二維單元陣列的一行關聯，如果該行包含標記的單元則處於有效狀態，否則處於無效狀態。
·Column-out相似地，在數量上編號 的column-out信號44對應於二維單元陣列的每個列。如果它對應的列包含第一活動線路上標記的單元，則column-out組的信號處於有效狀態，否則處於無效狀態。
·Line-inline-in信號43的數量是 二維陣列的每個行從X代碼轉換器接收兩個信號line-in[1]和line-in
，它們表示如下條件·該行是否是包含標記的單元的第一行；以及·該行是否高於或等於包含標記的單元的第一行。
例如，假定有8×8的二維單元陣列，內容如下所示，其中括號包括標記的單元中的符號。最上一行和第一列的數字表示用於訪問CM 206的行和列的編號系統，它們不是存儲在陣列中的符號。
0 1 2 3 4 5 6 70 X X X X X X X X1 X X X X X X X X2 X X X X X X X X3 X X X X X X X X4 X X [X] X X X [X] X5 X X X X X X X X6 [X] X X X [X] X X X
7 X X X X X X X [X]表I然後按行0、1、2至7的次序列出的line-out信號42等於00001011。按相同的次序，line-in信號43的line-in[1]信號是00001000，line-in信號43的line-in
信號是00001111。
·Column-in 45將Y代碼轉換器電路的每個列與兩個輸出信號column-in
和column-in[1]關聯，這兩個輸出信號指示如下條件·該列是否包含二維陣列的第一標記的單元。
·該列是否等於包含第一標記的單元的列或它是否屬於更高地址。
使用上面所示的8×8二維陣列的相同示例，並列出與編號為7下至0的列關聯的信號，column-in信號45包含值00100000和00111111。
CM 206的單元的內部結構除了已經呈示的data-in、data-out和com信號外，下列信號將含有符號和標記符的基本單元與其環境關聯，如圖13和14所示。
·Data-left-outN+2位信號25承載向前一個單元傳播的信息，並且N+2位信號25由N+1位left-cell-out信號及其關聯的標記符位組成，這些left-cell-out信號承載存儲在單元中的符號。
·Left-eq-out(1)單元內的比較符55生成的輸出信號54。
·Data-right-out(N+2)N+2位信號承載向下一個單元傳播的信息，並且N+2位信號由N+1位right-cell-out信號及其關聯的標記符位組成，這些right-cell-out信號承載存儲在單元中的符號。
·Right-eq-out(1)單元內的比較符的輸出信號55。
·Data-left-in(N+2)N+2位信號承載從前一個單元接收的信息，N+2位信號由N+l位left-cell-in信號52和1位信號left-eq-in 53組成，這些left-cell-in信號承載存儲在前一個單元中的符號及其關聯的標記符位，1位信號left-eq-in 53承載前一個單元內的比較符55的輸出。
·Data-right-in(N+2)這些N+2位信號承載從下一個單元接收的信息，N+2位信號由N+1位right-cell-in信號58和1位信號right-eq-in 56組成，這些right-cell-in信號承載存儲在下一個單元中的符號及其關聯的標記符位，1位信號right-eq-in 56是下一個單元內的比較符55的輸出。
·Line-out(1)是生成標記符的反相值的開漏輸出。它以並行方式連接來自二維陣列的相同線路上的所有其他單元的所有line-out信號42，並成為X代碼轉換器電路39的輸入的其中之一。
·Column-out(1)是1位信號44，並且是僅在含標記的單元的第一線路上生成標記符的反相值的開漏輸出。它以並行方式連接來自二維陣列的相同列上的單元的所有column-out信號，並成為Y代碼轉換器電路40的輸入的其中之一。
·Line-in(2)line-in[1]和line-in
構成line-in信號43，它們由X代碼轉換器電路39生成，並能夠表示如下條件·line-in[1]該單元屬於包含二維陣列的第一標記的單元的線路。
·line-in該單元屬於等於包含陣列的第一標記的單元的線路或是具有更高地址的線路的線路。
·Column-in(2)column-in[1]和column-in
構成column-in信號45，並且它們由Y代碼轉換器電路40生成。它們表示如下條件·column-in[1]該單元屬於包含第一標記的單元的列。
·column-in該單元屬於起始於含第一標記的單元的列。
·No-eq此開漏輸出16在該單元中「發明內容」部分中描述的cfind類型的命令成功時處於低電平有效。
·Symbol-data(N+1)這些雙向信號106允許將單元的內容(N位符號加1位標記符)寫入到外部存儲位置或從外部存儲位置讀取。
·Interrupt 101此信號是在設置了標記符的情況下由單元生成的，並且所存儲的符號是預定義且唯一的二進位模式，表示無效符號或指示該單元為空。此信號由開漏驅動器生成，將陣列中的M個單元生成的所有M個中斷信號一起執行或運算，以生成圖3中的中斷101。
單元的內部結構圖14示出單元的內部結構，它包括如下電路·REG電路60是包含存儲在單元中的值及其關聯的標記符位的值的(N+1)位寄存器。
·MUX1電路61是N個四輸入多路復用器的集合，它們允許根據稱為c1和c2的選擇碼65和66將多個值的其中之一存儲在REG中。多路復用器61的可能選擇是·data-in信號10上存在的外部值，·symbol-data信號106上存在的外部值，·left-cell-out信號51承載的來自前一個單元的值，·right-cell-in信號58承載的來自下一個單元的值，或·存儲在寄存器REG 60中的值，它允許寄存器的動態實現。
·MUX2電路62是四輸入多路復用器，它允許根據稱為c3和c4的選擇碼67和68將四個位的其中之一存儲在REG中的最高有效位中。多路復用器62的可能選擇是·PLA 63生成的標記符，·symbol-data信號106中存在的標記符位，·信號left-eq-in 53承載的來自前一個單元的標記符，·信號right-eq-in 56承載的來自下一個單元的標記符，或·存儲在寄存器REG 60中的標記符，它允許該位的動態實現。
·COMP電路55是組合電路，它僅在data-in輸入信號10上存在的符號等於該單元的N位內容時在其1位輸出上生成1，並且它們由信號right-cell-out 59承載。
·Symbol-data(N+1)這些信號106承載來自給定線路的單元的內容，或將REG中CM 206單元的內容承載到外部存儲實體。傳輸方向由R/W信號112控制。
·PLA電路63是一個組合電路，它可以由可編程邏輯陣列實現，並生成在單元內使用的稱為c1、c2、c3、c4、c5、c6、c7和c8的命令位65、66、67、68、69、107、109和111，以及no-eq信號16的反相值和column-out信號44。開漏反相器20驅動信號np-eq 16。反相器70驅動column-out信號144。PLA 63接收多個輸入信號·command信號14，它承載要由CM 206執行的命令(find、cfind、index等)的二進位表示，·寄存器REG 60的值，·由信號left-eq-in 53導致的前一個單元中的比較符55的輸出，·由信號right-eq-in 56導致的下一個單元中的比較符55的輸出，·信號no-eq 16，·X代碼轉換器生成的line-in信號43和Y代碼轉換器電路生成的column-in信號45。
PLA 63生成interrupt信號15，該中斷信號15在寄存器60包含用於標記未使用或無效單元的預定義符號時以及在設置了與寄存器關聯的標記符時被激活。
寄存器60的表示存儲在其中的符號的N位輸出被信號c5 69控制的N三態反相驅動器71反相，它們變成信號data-out 11。開漏反相器64將寄存器REG 60中存儲的標記符位反相，並生成信號line-out42。開漏反相器生成信號no-eq 16，它來自PLA 63。開漏反相器70生成信號column-out信號44。理論上來說，來自二維陣列中的不同單元的所有data-out 11和no-eq 16輸出連接在一起，屬於線路的所有line-out 42輸出也連接在一起，相同列上的單元的所有column-out信號44也連接在一起。
代碼轉換器圖15圖示兩個代碼轉換器電路39和40的組織。X代碼轉換器電路接收如下信號·line-out信號包含 位這些信號(各來自二維單元陣列的每個線路)用於指示這些線路上標記的單元的存在。
·Address-high信號96包含log(N)/2位，表示饋送到CM 206的地址的上半部，並它用於選出二維陣列中的 個線路的其中之一。
·5位command信號14僅用於如下一些輔助命令的實現set-limit、set-limit-address、limited-find、limited-cfind、limited-reverse-find、limited-reverse-cfind、limited-write-all、ram-read和ram-write。
Y代碼轉換器電路40接收如下信號· 位的column-outs信號44(各來自二維單元陣列的每個列)，它指示關聯的列上標記的單元的出現，該標記的單元是它所屬線路的第一個單元。
· 位的address-low信號97，它表示用於選擇給定線路的地址的下半部。
·5位command信號僅用於先前列出的輔助命令的實現。
兩種代碼轉換器都包含如下電路·解碼器DCD 83，用於將X代碼轉換器39中的地址信號的上半部或Y代碼轉換器中的地址信號的下半部解碼。
·多路復用器MUX-3電路82，由 個雙向多路復用器組成，並且使用c6信號92作為選擇信號。
·用於執行邏輯函數OR的前綴網絡PN-OR電路91。
·LATCH(閂鎖)電路85，它鎖住PN-OR信號的輸出，並用於為受限操作界定CM 206的有效部分。它使用c7信號93作為加載命令。
·MUX-4多路復用器電路87具有與MUX-3 82電路相同的結構，並使用c8信號94作為選擇信號。
· xor門的線性網絡XOR-1 86用於確定MUX-4電路87輸出的二進位配置中1的第一次出現。
·用於對X代碼轉換器中的line-outs 42或Y代碼轉換器中的column-outs信號44進行編碼的優先級編碼器PE 80，這兩個信號在X代碼轉換器中生成索引欄位的上半部index-high 38和在Y代碼轉換器中生成下半部index-low 46。
·RPE優先級編碼器81接收與PE優先級編碼器80相同的輸入，但是相反的次序，使得它可以生成c-index欄位的上半部和下半部。
·PLA電路84是一個小組合電路，它可以由可編程邏輯陣列實現，並對命令欄位14解碼以生成用於控制代碼轉換器電路的c9位92、c10位93、e11位94和c12位95。
·XOR-2電路89生成p/2位值，該值被饋送到p/2輸入AND門88，並生成eq信號36。此eq信號是將索引的上半部index-high 98與X代碼轉換器39中的RPE電路81生成的逆向索引的上部內容比較的結果，或是將索引的下半部index-low 99與Y代碼轉換器40中的RPE電路81生成的逆向索引的下部內容比較的結果。
RAM控制器圖16圖示RAM控制器12的實現，而圖17是圖示RAM控制器12的內部結構的電路圖。RAM控制器為存儲在RAM中的每個線路保存兩個存儲位。第一位存儲在包含L位的寄存器AR 208中，RAM中的每個線路對應於一位。將L位的內容饋送到優先級編碼器P-ENC210，優先級編碼器P-ENC 210輸出最低權值設為1的位的二進位表示。優先級編碼器210的輸出是line-address 201，並且是RAM中要為下次CM 206讀或寫操作選擇的線路的地址。例如，如果AR包含00101110，則P-ENC在line-address上輸出010，這是AR中設為1的最低有效位的地址。還將Line-address 201饋送到多路復用器MUX-7213的0輸入，多路復用器MUX-7 213在被相應選定時將line-address信號的內容饋送到解碼器ADCD 214。該解碼器具有L個輸出，1個有效的和L-1個無效。該有效輸出具有與AR 208中其權值或地址由P-ENC 210輸出的最低有效1位相同的權值。例如，如果line-address是010，則ADCD 214輸出00000010，其中設為1的位具有權值2。由L個xor門215將ADCD 214輸出的L個信號與AR 208輸出的L位執行xor，以生成AR中存儲的相同二進位模式，但是其中AR中的最低有效1位現在被設為0。使用相同的示例，如果AR包含00101110，則P-ENC輸出010，它被饋送到ADCD變成00000010，00000010與00101110執行xor得到00101100，粗體的0位指示AR的內容與XOR門215的輸出之間的差。將XOR門215的輸出經多路復用器MUX-6 209饋送到寄存器AR，其中當step-enable信號222處於有效狀態時在下一個時鐘周期存儲它們。該信號是信號202的com組的一部分，而且是在控制CE 205的外部處理實體的控制下。
AR、P-ENC、MUX-7、ADCD、L個XOR門以及MUX-6的組合構成一個電路，該電路以二進位形式存儲在AR中的數字K開始時，在line-address上輸出和等於K的2的連續冪。而且，在step-enable信號的控制下，此電路在連續的時間上生成2的每個冪。當所有1位從AR寄存器消失時，優先級編碼器檢測到該情況，並激活信號stop221，該信號被外部處理實體測為當前階段中沒有線路再需要處理的標誌。在循環中，該裝置自動生成所有位設為二進位數1的連續權值，並且每個權值的輸出僅耗用一個周期。
在寄存器AR中的1連續消失的同時，CM 206中處理線路並執行字符串操作。這些操作結束時，當CM 206的內容被存儲回線路時，no-flag信號15被反相併與init信號224執行or運算的值記錄在屬於L個D型觸發器218的其中之一的D型觸發器中。L觸發器組中選擇的觸發器的地址與該線路在RAM中的地址相同，觸發器的選擇利用ADCD電路214的輸出來執行，下文將對此予以描述。這些L個觸發器包含新模式的1和0，表示在下一次通過驗證操作中必須處理的下一組線路。
RAM控制器的初始化需要以如下方式將1存儲在AR的位中RAM中需要處理的線路將它們關聯的AR為設為1。這些有效線路以連續的塊存儲在RAM中的連續地址處，使得將該塊的最低地址設為0。例如，如果RAM中僅三個線路有效，則AR寄存器的最低3位必須設為1，其餘設為0。在此情況中，最高地址線路的地址是2，因為有效線路具有地址0、1和2。在此情況中，控制外部實體在limit-address 207信號上將最高線路的地址發送到RAM控制器，並激活init信號224。所導致的動作是，通過多路復用器MUX-7的limit-address信號上的log(L)地址被ADCD解碼成L個信號，其中除了權值等於limit-address的內容的信號外全為0。
然後將MUX-7的輸出饋送到前綴OR電路OR-PN 216，前綴OR電路OR-PN 216將值為0且權值小於其輸入中僅1位的權值的所有位變換為1。例如，如果OR-PN電路接收00000100，其中1位的權值是2，則其輸出是00000111。然後將這L個信號傳送通過L個OR門219並饋送到L個D型觸發器218的D輸入。L個D型觸發器218分別由ADCD電路生成的L個信號使能，並分別與init信號224執行OR運算。然後通過激活控制多路復用器MUX-6 209的啟動信號將其中每個輸出為1對應於RAM中的有效線路的這L個觸發器的內容加載到寄存器AR 208。
如圖18所示，CE 205由有效單元或處理部件的陣列構成，實施為連接存儲器(CM)206和包含多個矢量400的RAM(隨機存取存儲器)，每個矢量具有與CM 206相同的存儲容量並因此能夠選擇性地存儲CM 206的整個內容。即，CE 205包括具有n個單元的CM 206和關聯的矢量存儲器400的CM 206，CM 206受控制器255的控制。在本發明的一個實施例中，存儲器矢量400的目的是允許對比CM 206內可容納的字符串長的字符串執行搜索、插入和刪除操作，並且提供較低的實現成本和降低的功耗，稍後將對此予以更詳細的論述。
提供到CE 205的代碼的執行由控制器255驅動。CE 205/控制器255接口利用四個特殊寄存器，也如圖18所示·「INR」402-數據輸入寄存器；在一個實施例中，所有CE 205指令從INR(控制器205提供的)得到它們(直接)數據變元(如果有的話)；·「OUTR」404-數據輸出-包含「no_mark」位和值。如果標記單元的至少其中之一，則OUTR包含0、後面是第一標記的單元中所含的值；否則OUTR包含1、後面是實現相關的特殊值，如11...1；·「OPR」406-指令寄存器，它包含用於當前CE 205指令的操作代碼(該源是控制器255指令中的專用欄位)；·「VAR」408-矢量存儲器的地址寄存器。VAR 408寄存器由特殊控制器255指令更新，並用作明確地操作矢量的指令的變元；VAR408寄存器還用於所有操作的執行，包括與單元相關的普通寄存器。
再如圖18所表示的，可以選擇性地利用輸入/輸出線410來訪問CM 206的兩個端。正如所利用的，輸入/輸出線410具有如下含義·「left_in」412＝{w，mark，eq，first}，預設情況下全部為0(eq＝1意味著該單元中的兩個運算數相等；first＝1意味著該單元是第一標記的單元)；·「left_out」414＝{w，mark，eq，first}，來自第一單元；將容易認識到的是，在不背離本發明較廣泛的方面的情況下，本發明設想CE 205可以具有任何數量的電路專用的配置，只要控制器255能夠向CE 205發出命令和從其中接收數據即可。因此，本發明的一個重要方面在於CM 206內的每個m位單元除了存儲數據外還能夠選擇性地處理數據。數據的處理可以在每個m位單元內執行，或通過作用於緊鄰預定單元左右的單元來執行。應該注意的是，通過以此方式增強CM 206內的每個m位單元的功能，本發明呈示更為複雜的系統級行為，因此超出其他數據處理系統的性能。
本發明的另一個重要方面在於通過能夠部分地「標記」每個單元(作為條件或預測的一部分)、指定它作為後續執行任務的單元或自行執行運算數或CM 206內的相鄰單元來實現CM 206內在單元級上選擇性地處理數據的能力。
本發明的數據處理系統的另一個固有優點包括蜂窩引擎內的每個單元不僅能夠在單個時鐘周期內同時執行指令，而且還能夠利用本地和全局狀態信息動態地限定執行這些全局廣播指令的那些單元。具體來說，通過在單個單元級上利用標記符位，聯想存儲器內的實際單元以迄今非公知的方式能夠作用於標記的單元左右的那些單元。因此，在系統級上，本發明提出通過聯想機制即通過CM 206內各個單元的內容的特徵或特性而非其中具體指定的位置地址來實施選擇性激活或變更標記的單元。
因此，本發明在非常緊密的級別上將處理和存儲器組合，這意味著CM 206的單個單元從不需要訪問分離的存儲器塊來執行其作業。而且，運算數在單元級上駐留在它們各自的本地空間中，因此結果本地保存，從而節省通信和處理時間、矽面積和功率。
還通過CM206能夠選擇性將其n個單元內存儲的位的任何位置表徵為關鍵字欄位或數據欄位的一部分來強化CM 206的更高靈活性。即，對比於其中嚴格定義關鍵字欄位和數據欄位的公知聯想存儲器體系結構，CM 206能夠根據所發出的命令和期望的操作的特徵來將它的存儲器內存儲的任何位視為關鍵字欄位位或數據欄位位。
圖19圖示典型聯想存儲器500的內容。將容易地認識到，圖19是具有一行包括12列的存儲器單元的聯想存儲器裝置的簡化表示。當然本發明並不局限於此類體系結構，並且實際上可設想更大且更複雜的單元陣列，圖19僅僅是利用來說明的。
如圖19所示，存在6列關鍵字欄位502和8列數據欄位504。雖然將容易設想到關鍵字欄位502和數據欄位504的實際長度或大小屬於設計選擇的問題，但是公知的聯想存儲器引擎這兩個欄位之間對於所有命令和操作仍存在區別。即，公知的聯想存儲器裝置在它們的關鍵字和數據欄位的特徵和大小方面是特定的。例如，假定使用聯想存儲器來實現快速資料庫，使得它的數據欄位表示具體的數據內容，例如有關僱員的信息，而關鍵字欄位表示僱員的姓氏。因此，根據簡化的命令，典型聯想存儲器中的控制器將利用包含潛在被查找數據的數據欄位504搜索關鍵字欄位502以便確定它是否與姓名「Smith」匹配，並「標出」與等於「Smith」的關鍵字關聯的所有數據欄位504，以便指示存在或不存在被查找的數據。注意在本示例中關鍵字從不長於6列。
但是在本發明的存儲器引擎中，去除了關鍵字欄位與數據欄位之間的區分，因此對於控制器來說可以響應發出的命令全局性地將欄位502或欄位504內包含的任何單元作為關鍵字的一部分來考慮和評估。
應該注意，公知聯想數據處理系統和本發明之間的區分不屬於結構方面的，而屬於軟體和發出的命令的實現。即，根據本發明，控制器可以根據發出的特定命令選擇性地考慮將聯想存儲器裝置內的所有單元作為「關鍵字」的一部分或「數據」的一部分。因此，任何特定單元的「關鍵字」或「數據」屬性在命令本身中表示，而不是聯想存儲器裝置的結構性組織的功能。
如圖20所示，控制器結合具體命令可以在具有14個單元行的14個單元的聯想存儲器510中的單元2中(即其他方面被視為傳統關鍵字欄位(虛線所示)的那個單元內)定位被查找的數據，或它可以將單元9(即其他方面被視為傳統數據欄位(虛線所示)的那個單元內)作為關鍵字的一部分。因此，將容易認識到本發明的聯想存儲器引擎呈現出遠比公知聯想存儲器引擎更大的靈活性。
實際上，因為本發明有效地消除了聯想存儲器裝置內關鍵字欄位與數據欄位之間的傳統區分，所以顯著地增加了存儲器引擎的編程能力。
返回到有關僱員姓氏的上面示例，公知聯想存儲器系統通常是針對具體使用的或對於具體使用專門設計的，因此無法搜索或標識具有完全不同結構的數據(例如16列的關鍵字和1024列的數據)。差別較大地，因為本發明不識別關鍵字欄位和數據欄位之間的區分，實際上因為本發明結合每個分開的命令選擇性地重新定義被視為「關鍵字」的內容的特徵，所以本發明能夠實現基本通用的聯想存儲器系統。
作為示例，可以利用例如5單元關鍵字來控制根據本發明對數據處理的聯想存儲器支持以標識所有僱員的姓氏。然後可以利用控制器發出的下一個命令基於例如2單元關鍵字等定位另一種類型的數據。因此，本發明避免了像公知聯想存儲器系統的情況中那樣對每個具體使用重新設計或專門調整機器的需要。相比之下，本發明能夠根據所發出的命令單獨處理每個關鍵字，能使本發明支持僅可利用選擇的長度和內容針對特定化的數據選擇性地採掘的非專門的聯想存儲器。
就此而言，應該容易地認識到，先前結合圖3-10論述的命令的實現至少部分基於存儲器引擎可移除或忽略CM 206內的關鍵字欄位和數據欄位之間的傳統區分的獨一無二的能力。
還將容易地認識到控制器255能夠在一個時鐘周期內將預定的命令全局性地廣播到CM 206中的n個單元的每一個，以及n個單元的每一個能夠在一個時鐘周期內處理髮出的命令，這些能力同樣可應用於存儲器裝置能夠利用n個單元的每一個內的所有位，而無論它們的位置或關鍵字和數據欄位之間的任何區分，並且得到後面這種能力的支持。
雖然參考優選實施例描述了本發明，但是本領域技術人員將理解，在不背離本發明實質範圍的前提下可以進行多種形式的更改，並且能以等效物替代其部件。因此，本發明不應限於所公開的具體實施例，而是本發明包含落在所附權利要求的範圍內的所有實施例。
權利要求
1.一種用於數據處理系統的聯想存儲器支持，所述聯想存儲器支持包括包含n個單元的聯想存儲器裝置；用於向所述聯想存儲器裝置發出指令的控制器；用於輸出由每秒預定數量的時鐘周期組成的同步時鐘信號的時鐘裝置，所述時鐘裝置將所述同步時鐘信號輸出到所述聯想存儲器裝置和所述控制器；所述控制器在所述時鐘周期的其中之一內全局性地將所述指令同時傳送到所述n個單元的全部；以及其中所述指令同等地應用於所述n個單元的每一個。
2.一種用於數據處理系統的聯想存儲器支持，所述聯想存儲器支持包括包含n個單元的聯想存儲器裝置；用於向所述聯想存儲器裝置中的所述n個單元發出命令的控制器；其中所述命令定義用於標識所述n個單元內的數據的關鍵字欄位的組合。
3.一種用於數據處理系統的聯想存儲器支持，所述聯想存儲器支持包括包含n個單元的聯想存儲器裝置；用於向所述n個單元發出指令的控制器；以及其中所述指令定義在所述指令執行時所用的關鍵字欄位的大小和特徵。
4.如權利要求3所述的用於數據處理系統的聯想存儲器支持，其特徵在於所述關鍵字欄位應用於所述n個單元的全部。
全文摘要
一種用於數據處理系統的聯想存儲器支持包括含n個單元的聯想存儲器裝置。設有控制器用於向聯想存儲器裝置發出指令。時鐘裝置輸出同步時鐘信號，該同步時鐘信號包括每秒預定數量的時鐘周期，該時鐘裝置將同步時鐘信號輸出到聯想存儲器裝置和控制器。控制器在這些時鐘周期的其中之一內全局性地將指令同時傳送到所有n個單元，並將指令同等地應用於n個單元的每一個單元。
文檔編號G11C15/00GK101076787SQ200580022459
公開日2007年11月21日 申請日期2005年4月29日 優先權日2004年5月10日
發明者G·史蒂芬, D·蒂鮑特, D·託梅斯庫 申請人:亮標公司