[go: up one dir, main page]

TWI479342B - 用於型樣辨識處理器之多階層式路由矩陣 - Google Patents

用於型樣辨識處理器之多階層式路由矩陣 Download PDF

Info

Publication number
TWI479342B
TWI479342B TW099144023A TW99144023A TWI479342B TW I479342 B TWI479342 B TW I479342B TW 099144023 A TW099144023 A TW 099144023A TW 99144023 A TW99144023 A TW 99144023A TW I479342 B TWI479342 B TW I479342B
Authority
TW
Taiwan
Prior art keywords
connections
cells
programmable
routing
coupled
Prior art date
Application number
TW099144023A
Other languages
English (en)
Other versions
TW201131404A (en
Inventor
哈洛德Ｂ 諾耶思
大衛Ｒ 布朗
Original Assignee
美光科技公司
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 美光科技公司 filed Critical 美光科技公司
Publication of TW201131404A publication Critical patent/TW201131404A/zh
Application granted granted Critical
Publication of TWI479342B publication Critical patent/TWI479342B/zh

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F18/00—Pattern recognition
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F15/00—Digital computers in general; Data processing equipment in general
    • G06F15/76—Architectures of general purpose stored program computers
    • G06F15/80—Architectures of general purpose stored program computers comprising an array of processing units with common control, e.g. single instruction multiple data processors
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/30—Information retrieval; Database structures therefor; File system structures therefor of unstructured textual data
    • G06F16/33—Querying
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/90—Details of database functions independent of the retrieved data types
    • G06F16/903—Querying
    • G06F16/90335—Query processing
    • G06F16/90344—Query processing by using string matching techniques
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N5/00—Computing arrangements using knowledge-based models
    • G06N5/01—Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06V—IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
    • G06V10/00—Arrangements for image or video recognition or understanding
    • G06V10/70—Arrangements for image or video recognition or understanding using pattern recognition or machine learning
    • G06V10/768—Arrangements for image or video recognition or understanding using pattern recognition or machine learning using context analysis, e.g. recognition aided by known co-occurring patterns
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06V—IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
    • G06V10/00—Arrangements for image or video recognition or understanding
    • G06V10/94—Hardware or software architectures specially adapted for image or video understanding
    • G06V10/955—Hardware or software architectures specially adapted for image or video understanding using specific electronic processors
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03K—PULSE TECHNIQUE
    • H03K19/00—Logic circuits, i.e. having at least two inputs acting on one output; Inverting circuits
    • H03K19/02—Logic circuits, i.e. having at least two inputs acting on one output; Inverting circuits using specified components
    • H03K19/173—Logic circuits, i.e. having at least two inputs acting on one output; Inverting circuits using specified components using elementary logic circuits as components
    • H03K19/177—Logic circuits, i.e. having at least two inputs acting on one output; Inverting circuits using specified components using elementary logic circuits as components arranged in matrix form
    • H03K19/17724—Structural details of logic blocks
    • H03K19/17728—Reconfigurable logic blocks, e.g. lookup tables
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2218/00—Aspects of pattern recognition specially adapted for signal processing

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • Databases & Information Systems (AREA)
  • Data Mining & Analysis (AREA)
  • Computing Systems (AREA)
  • Software Systems (AREA)
  • Computer Hardware Design (AREA)
  • Computational Linguistics (AREA)
  • Artificial Intelligence (AREA)
  • Evolutionary Computation (AREA)
  • Mathematical Physics (AREA)
  • Multimedia (AREA)
  • Computer Vision & Pattern Recognition (AREA)
  • Medical Informatics (AREA)
  • Health & Medical Sciences (AREA)
  • General Health & Medical Sciences (AREA)
  • Evolutionary Biology (AREA)
  • Bioinformatics & Computational Biology (AREA)
  • Bioinformatics & Cheminformatics (AREA)
  • Life Sciences & Earth Sciences (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
  • Image Processing (AREA)
  • Character Discrimination (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)
  • Image Analysis (AREA)

Description

用於型樣辨識處理器之多階層式路由矩陣
本發明之實施例大體而言係關於型樣辨識處理器，且更具體而言，在某些實施例中，係關於此等處理器之連接架構。
在計算領域中，型樣辨識任務越來越具有挑戰性。電腦之間發射之資料量不斷增大，且使用者希望識別之型樣數目日益增加。舉例而言，通常藉由搜尋一資料串流中之型樣(例如，特定片語或片段程式碼)來偵測垃圾郵件或惡意軟體。型樣數目隨著垃圾郵件及惡意軟體之變化而增加，此乃因可實施新型樣以搜尋新變體。針對此等型樣中之每一者對一資料串流進行搜尋可形成一計算瓶頸。通常，在接收資料串流時，針對每一型樣對其進行搜尋，一次一個。在系統準備對該資料串流之下一部分進行搜尋之前的延遲隨著型樣之數目增加。因此，型樣辨識可使資料之接收減慢。
此等型樣辨識處理器可包含在處理輸入時以逐一狀態之方式(from state to state)移動之大量有限狀態機(FSM)。習用處理器之內部連接依賴於連接至一正反器或其他記憶體元件之實體導線。然而，此等連接可係不能夠符合一型樣搜尋處理器之效能。此外，此等連接通常不可組態為或不能夠符合一期望之功能性。用矽實施一型樣辨識處理器中之該等連接之距離、速度及可組態性可能具有挑戰性。
圖1繪示對一資料串流12進行搜尋之一系統10之一實例。系統10可包含一型樣辨識處理器14，該型樣辨識處理器根據搜尋準則16來對資料串流12進行搜尋。
每一搜尋準則可規定一個或多個目標表達(亦即，型樣)。片語「目標表達」係指型樣辨識處理器14正搜尋之一資料序列。目標表達之實例包含拼寫某一字之一字元序列、規定一基因之一遺傳鹼基對序列、形成一影像之一部分之一圖片或視訊檔案中之一位元序列、形成一程式之一部分之一可執行檔案中之一位元序列或形成一歌曲或一口語片語之一部分之一音訊檔案中之一位元序列。
一搜尋準則可規定多於一個之目標表達。舉例而言，一搜尋準則可規定以字母序列「cl」開頭之所有五個字母之字、以字母序列「cl」開頭之任一字、包含字「cloud」多於三次之一段落等。目標表達之可能組之數目係任意大，例如，可存在與資料串流可呈現之資料排列一樣多之目標表達。搜尋準則可以多種格式來表達，包含規則表達、簡明地規定目標表達組而不必列舉每一目標表達之一程式化語言。
每一搜尋準則可由一個或多個搜尋項構成。因此，一搜尋準則之每一目標表達可包含一個或多個搜尋項且某些目標表達可使用共同搜尋項。如本文中所用，片語「搜尋項」係指在一單個搜尋循環期間所搜尋之一資料序列。該資料序列可包含呈二進制格式或其他格式(例如，十進位、ASCII等)之多個資料位元。該序列可用一單個數位或多個數位(例如，數個二進制數位)對資料進行編碼。舉例而言，型樣辨識處理器14可一次一個字元地對一文字資料串流12進行搜尋，且搜尋項可規定一組單個字元，例如，字母「a」，字母「a」或「e」，或規定一組所有單個字元之一通配符搜尋項。
搜尋項可小於或大於規定一字元(或其他字形─亦即，資料串流所表達之資訊之基礎單元，例如，一音符、一遺傳鹼基對、10進位數位或一子像素)之位元之數目。舉例而言，一搜尋項可係8個位元且一單個字元可係16個位元，在此情形下，兩個連續搜尋項可規定一單個字元。
搜尋準則16可由一編譯器18進行格式化以用於型樣辨識處理器14。格式化可包含自該等搜尋準則解構搜尋項。舉例而言，若資料串流12所表達之字形大於該等搜尋項，則該編譯器可將搜尋準則解構成多個搜尋項以搜尋一單個字形。類似地，若資料串流12所表達之字形小於該等搜尋項，則編譯器18可為每一單獨字形提供具有不使用之位元之一單個搜尋項。編譯器18亦可格式化搜尋準則16以支援未由型樣辨識處理器14本機支援之各種規則表達運算子。
型樣辨識處理器14可藉由評估來自資料串流12之每一新項來對資料串流12進行搜尋。此處，字「項」係指可匹配一搜尋項之資料量。在一搜尋循環期間，型樣辨識處理器14可判定當前所呈現之項是否匹配搜尋準則中之當前搜尋項。若該項匹配該搜尋項，則「推進」評估，亦即，將下一項與搜尋準則中之下一搜尋項相比較。若該項不匹配，則將下一項與搜尋準則中之第一項相比較，藉此重設該搜尋。
可將每一搜尋準則編譯至型樣辨識處理器14中之一不同有限狀態機(FSM)中。該等有限狀態機可並行運行，從而根據搜尋準則16對資料串流12進行搜尋。當資料串流12匹配在前搜尋項時，該等有限狀態機可步進穿過一搜尋準則中之每一接連搜尋項，或若不匹配該搜尋項，則該等有限狀態機可開始搜尋該搜尋準則之第一搜尋項。
型樣辨識處理器14可(例如)在一單個裝置循環期間在約相同時間根據數個搜尋準則及其各別搜尋項來評估每一新項。該等並行有限狀態機可各自在約相同時間接收來自資料串流12之項，且該等並行有限狀態機中之每一者可判定該項是否將該並行有限狀態機推進至其搜尋準則中之下一搜尋項。該等並行有限狀態機可根據一相對大數目個搜尋準則(例如，多於100、多於1000或多於10,000)來評估項。由於其等並行操作，因此其等可將該等搜尋準則應用至具有一相對高頻寬之一資料串流12(例如，大於或大體等於每秒64 MB或每秒128 MB之一資料串流12)，而不使該資料串流減慢。在某些實施例中，搜尋循環持續時間不隨搜尋準則之數目按比例縮放，因此搜尋準則之數目對型樣辨識處理器14之效能可幾乎沒有影響。
當滿足一搜尋準則時(亦即，在推進至最後一個搜尋項且與其匹配之後)，型樣辨識處理器14可將對該準則之滿足報告給一處理單元，諸如，一中央處理單元(CPU)20。中央處理單元20可控制型樣辨識處理器14及系統10之其他部分。
系統10可係對一資料串流進行搜尋之各種系統或裝置中之任一者。舉例而言，系統10可係對資料串流12進行搜尋之一桌上型電腦、膝上型電腦、手持式或其他類型之電腦。系統10亦可係一網路節點，例如，一路由器、一伺服器或一用戶端(例如，先前所述類型之電腦中之一者)。系統10可係某一其他類別之電子裝置，例如，一複印機、一掃描器、一印表機、一遊戲控制臺、一電視機、一機上視訊散佈或記錄系統、一電纜盒、一個人數位媒體播放器、一工廠自動化系統、一汽車電腦系統或一醫療裝置。(用以闡述系統之此等各種實例之術語(如同本文中所用之諸多其他術語)可共享某些參照物，且因此不應狹隘地憑藉所列舉之其他物項來理解)。
資料串流12可係一使用者或其他實體可希望搜尋之各種類型之資料串流中之一者或多者。舉例而言，資料串流12可係經由一網路接收之一資料串流，諸如，經由網際網路接收之封包或經由一蜂巢式網路接收之語音或資料。資料串流12可係自與系統10通信之一感測器(諸如，一成像感測器、一溫度感測器、一加速計或類似物，或其組合)接收之資料。資料串流12可由系統10接收作為一串列資料串流，其中資料係以具有意義之一次序(諸如，以一顯著的時間、詞法或語義次序)被接收。或者，資料串流12可平行地或無序地被接收，且然後(例如)藉由重新排序經由網際網路接收之封包來轉換成一串列資料串流。在某些實施例中，資料串流12可以串列方式呈現項，但表達該等項中之每一者之位元可並行地被接收。資料串流12可係自系統10外部之一源被接收，或可藉由訊問一記憶體裝置並由所儲存之資料形成資料串流12來形成。
端視資料串流12中之資料之類型，一設計者可挑選不同類型之搜尋準則。舉例而言，搜尋準則16可係一病毒定義檔案。可表徵病毒或其他惡意軟體，且可使用惡意軟體之態樣來形成指示資料串流12是否可能正在遞送惡意軟體之搜尋準則。可將所得搜尋準則儲存於一伺服器上，且一用戶端系統之一操作者可預訂將該等搜尋準則下載至系統10之一服務。在不同類型之惡意軟體出現時，搜尋準則16可自該伺服器週期性地更新。該等搜尋準則亦可用以規定可經由一網路接收之不期望之內容，舉例而言，不需要之電子郵件(通常稱作垃圾郵件)或一使用者所反感之其他內容。
資料串流12可由對系統10正在接收之資料感興趣之一第三方來搜尋。舉例而言，可針對在一版權作品中出現之文字、一音訊序列或一視訊序列來對資料串流12進行搜尋。可針對與一刑事調查或民事訴訟有關或一雇主感興趣之言論來對資料串流12進行搜尋。在其他實施例中，針對感興趣之資料監視一資料串流可係搜尋之一實例。
搜尋準則16亦可包含資料串流12中之型樣，例如，在可由CPU 20或型樣辨識處理器14定址之記憶體中可得到該等型樣之一轉譯。舉例而言，搜尋準則16可各自規定一英語字，針對該英語字，一對應西班牙語字儲存於記憶體中。在另一實例中，搜尋準則16可規定資料串流12之經編碼版本(例如，MP3、MPEG 4、FLAC、Ogg Vorbis等)，針對該等經編碼版本，可得到資料串流12之一經解碼版本，或反之亦然。
型樣辨識處理器14可係與CPU 20一起整合至一單個組件(諸如，一單個裝置)中之硬體或可形成為一單獨組件。舉例而言，型樣辨識處理器14可係一單獨積體電路。型樣辨識處理器14可稱為一「協同處理器」或一「型樣辨識協同處理器」。
圖2繪示型樣辨識處理器14之一實例。型樣辨識處理器14可包含一辨識模組22及一彙總模組24。辨識模組22可經組態以將所接收之項與搜尋項相比較，且辨識模組22與彙總模組24兩者可協作以判定將一項與一搜尋項匹配是否滿足一搜尋準則。
辨識模組22可包含一列解碼器28及複數個特徵胞30。每一特徵胞30可規定一搜尋項，且特徵胞30群組可形成一並行有限狀態機，該並行有限狀態機形成一搜尋準則。特徵胞30之組件可形成一搜尋項陣列32、一偵測陣列34及一啟動路由矩陣36。搜尋項陣列32可包含複數個輸入導體37，其每一者可使特徵胞30中之每一者與列解碼器28通信。
列解碼器28可基於資料串流12之內容而在複數個輸入導體37中選擇特定導體。舉例而言，列解碼器28可係基於可表示一個項之一所接收位元組之值而啟動256個列中之一者之一個位元組對256列之一解碼器。一位元組項0000 0000可對應於該複數個輸入導體37中之頂部列，且一位元組項1111 1111可對應於該複數個輸入導體37中之底部列。因此，端視自資料串流12接收哪些項，可選擇不同輸入導體37。在接收不同項時，列解碼器28可撤銷啟動對應於先前項之列且啟動對應於新項之列。
偵測陣列34可耦合至一偵測匯流排38，該偵測匯流排將指示完全或部分滿足搜尋準則之信號輸出至彙總模組24。啟動路由矩陣36可基於(舉例而言)一搜尋準則中之已被匹配之搜尋項之數目而選擇性地啟動及撤銷啟動特徵胞30。
彙總模組24可包含一鎖存器矩陣40、一彙總路由矩陣42、一臨限邏輯矩陣44、一邏輯積矩陣46、一邏輯和矩陣48及一初始化路由矩陣50。
鎖存器矩陣40可實施某些搜尋準則之部分。某些搜尋準則(例如，某些規則表達)僅計數一匹配或一匹配群組之第一次發生。鎖存器矩陣40可包含記錄是否已發生一匹配之鎖存器。當判定滿足或不可進一步滿足搜尋準則時─亦即，一較早搜尋項可需要在可滿足該搜尋準則之前進行再次匹配，該等鎖存器可在初始化期間被清除，且在操作期間被週期性地重新初始化。
彙總路由矩陣42可類似於啟動路由矩陣36發揮作用。彙總路由矩陣42可在偵測匯流排38上接收指示匹配之信號且可將該等信號路由至連接至臨限邏輯矩陣44之不同群組邏輯線53。彙總路由矩陣42亦可將初始化路由矩陣50之輸出路由至偵測陣列34以當判定滿足或不可進一步滿足一搜尋準則時重設偵測陣列34之部分。
臨限邏輯矩陣44可包含複數個計數器，例如，經組態以遞增計數或遞減計數之32位元計數器。臨限邏輯矩陣44可載入有一初始計數且其可基於由辨識模組發訊之匹配而自該計數遞增計數或遞減計數。舉例而言，臨限邏輯矩陣44可計數一字在某一長度之文字中出現之數目。
臨限邏輯矩陣44之輸出可係邏輯積矩陣46之輸入。邏輯積矩陣46可選擇性地產生「積」結果(例如，布林邏輯(Boolean logic)中之「及(AND)」函數)。邏輯積矩陣46可實施為一正方形矩陣，其中輸出積之數目等於來自臨限邏輯矩陣44之輸入線之數目，或邏輯積矩陣46可具有不同於輸出之數目之輸入。可將所得積值輸出至邏輯和矩陣48。
邏輯和矩陣48可選擇性地產生和(例如，布林邏輯中之「或(OR)」函數)。邏輯和矩陣48亦可係一正方形矩陣，或邏輯和矩陣48可具有不同於輸出之數目之輸入。由於該等輸入係邏輯積，因此邏輯和矩陣48之輸出可係積的邏輯和(例如，布林邏輯之積的和(SOP)形式)。邏輯和矩陣48之輸出可由初始化路由矩陣50接收。
初始化路由矩陣50可經由彙總路由矩陣42重設偵測陣列34及彙總模組24之部分。初始化路由矩陣50亦可實施為一正方形矩陣，或初始化路由矩陣50可具有不同於輸出之數目之輸入。(諸如)當滿足一搜尋準則或判定不可進一步滿足該搜尋準則時，初始化路由矩陣50可回應於來自邏輯和矩陣48之信號且重新初始化型樣辨識處理器14之其他部分。
彙總模組24可包含一輸出緩衝器51，其接收臨限邏輯矩陣44、彙總路由矩陣42及邏輯和矩陣48之輸出。彙總模組24之輸出可在輸出匯流排26上自輸出緩衝器51發射至CPU 20(圖1)。在某些實施例中，一輸出多工器可對來自此等組件42、44及48之信號進行多工且將指示滿足準則或匹配搜尋項之信號輸出至CPU 20(圖1)。在其他實施例中，可在不透過該輸出多工器發射該等信號之情形下報告來自型樣辨識處理器14之結果，此並非暗示亦不可省略本文中所述之任一其他特徵。舉例而言，可在輸出匯流排26上將來自臨限邏輯矩陣44、邏輯積矩陣46、邏輯和矩陣48或初始化路由矩陣50之信號並行發射至該CPU。
圖3圖解說明搜尋項陣列32(圖2)中之一單個特徵胞30之一部分(本文中稱為一搜尋項胞54之一組件)。搜尋項胞54可包含一輸出導體56及複數個記憶體胞58。記憶體胞58中之每一者可耦合至輸出導體56及複數個輸入導體37中之導體中之一者兩者。回應於選擇其輸入導體37，記憶體胞58中之每一者可輸出指示其所儲存值之一值，從而透過輸出導體56輸出資料。在某些實施例中，複數個輸入導體37可稱為「字線」，且輸出導體56可稱為一「資料線」。
記憶體胞58可包含各種類型之記憶體胞中之任一類型。舉例而言，記憶體胞58可係揮發性記憶體，諸如，具有一電晶體及一電容器之動態隨機存取記憶體(DRAM)胞。該電晶體之源極及汲極可分別連接至該電容器之一板及輸出導體56，且該電晶體之閘極可連接至輸入導體37中之一者。在揮發性記憶體之另一實例中，記憶體胞58中之每一者可包含一靜態隨機存取記憶體(SRAM)胞。該SRAM胞可具有一輸出，該輸出藉由受輸入導體37中之一者控制之一存取電晶體選擇性地耦合至輸出導體56。記憶體胞58亦可包含非揮發性記憶體，諸如，相變記憶體(例如，一雙向(ovonic)裝置)、快閃記憶體、矽-氧化物-氮化物-氧化物-矽(SONOS)記憶體、磁阻式記憶體或其他類型之非揮發性記憶體。記憶體胞58亦可包含正反器(例如，由邏輯閘極製成之記憶體胞)。
圖4及圖5繪示操作中之搜尋項胞54之一實例。圖4圖解說明搜尋項胞54接收不匹配該胞之搜尋項之一項，且圖5圖解說明一匹配。
如圖4所圖解說明，搜尋項胞54可經組態以藉由將資料儲存於記憶體胞58中來搜尋一個或多個項。記憶體胞58可各自表示資料串流12可呈現之一項，例如，在圖3中，每一記憶體胞58表示一單個字母或數字，以字母「a」開始且以數字「9」結束。表示滿足搜尋項之項之記憶體胞58可經程式化以儲存一第一值，且不表示滿足搜尋項之項之記憶體胞58可經程式化以儲存一不同值。在所圖解說明之實例中，搜尋項胞54經組態以搜尋字母「b」。表示「b」之記憶體胞58可儲存1或邏輯高，且不表示「b」之記憶體胞58可經程式化以儲存0或邏輯低。
為將來自資料串流12之一項與搜尋項相比較，列解碼器28可選擇耦合至表示所接收項之記憶體胞58之輸入導體37。在圖4中，資料串流12呈現一小寫「e」。此項可由資料串流12以八位元ASCII程式碼之形式呈現，且列解碼器28可將此位元組解譯為一列位址，從而藉由給導體60通電而在其上輸出一信號。
作為回應，由導體60控制之記憶體胞58可輸出指示記憶體胞58所儲存之資料之一信號，且該信號可由輸出導體56輸送。在此情形下，由於字母「e」不係由搜尋項胞54規定之項中之一者，因此其不匹配搜尋項，且搜尋項胞54輸出0值，從而指示未發現匹配。
在圖5中，資料串流12呈現一字元「b」。另外，列解碼器28可將此項解譯為一位址，且列解碼器28可選擇導體62。作為回應，表示字母「b」之記憶體胞58輸出其所儲存之值，在此情形下該值係1，從而指示一匹配。
搜尋項胞54可經組態以一次搜尋多於一個項。多個記憶體胞58可經程式化以儲存1，從而規定與多於一個項匹配之一搜尋項。舉例而言，表示小寫字母「a」及大寫字母「A」之記憶體胞58可經程式化以儲存1，且搜尋項胞54可搜尋任一項。在另一實例中，搜尋項胞54可經組態以在接收任一字元之情形下輸出一匹配。所有記憶體胞58可經程式化以儲存1，以使得搜尋項胞54可充當一搜尋準則中之一通配符項。
圖6至圖8繪示辨識模組22根據一多項搜尋準則(例如)搜尋一字。具體而言，圖6圖解說明辨識模組22偵測一字之第一字母，圖7圖解說明第二字母之偵測，且圖8圖解說明最後一個字母之偵測。
如圖6所圖解說明，辨識模組22可經組態以搜尋字「big」。圖解說明三個毗鄰特徵胞63、64及66。特徵胞63經組態以偵測字母「b」。特徵胞64經組態以偵測字母「i」。且特徵胞66經組態以既偵測字母「g」又指示滿足搜尋準則。
圖6亦繪示偵測陣列34之額外細節。偵測陣列34可包含特徵胞63、64及66中之每一者中之一偵測胞68。偵測胞68中之每一者皆可包含一記憶體胞70(諸如，上文所述之記憶體胞之類型中之一者(例如，一正反器))，其指示特徵胞63、64或66是作用中的還是非作用中的。偵測胞68可經組態以將既指示該偵測胞是否係作用中的又指示是否已自其相關聯搜尋項胞54接收指示一匹配之一信號之一信號輸出至啟動路由矩陣36。非作用中特徵胞63、64及66可忽視匹配。偵測胞68中之每一者可包含一「及」閘，其具有來自記憶體胞70及輸出導體56之輸入。可將該「及」閘之輸出路由至偵測匯流排38及啟動路由矩陣36兩者或者一者或另一者。
啟動路由矩陣36又可藉由寫入至偵測陣列34中之記憶體胞70來選擇性地啟動特徵胞63、64及66。啟動路由矩陣36可根據搜尋準則及接下來正在資料串流12中搜尋哪一搜尋項來啟動特徵胞63、64或66。
在圖6中，資料串流12呈現字母「b」。作為回應，特徵胞63、64及66中之每一者可在其等輸出導體56上輸出指示儲存於連接至導體62之記憶體胞58(其表示字母「b」)中之值之一信號。然後，偵測胞68可各自判定其等是否已接收指示一匹配之一信號及其等是否係作用中的。由於特徵胞63經組態以偵測字母「b」且係作用中的(如其記憶體胞70所指示)，因此特徵胞63中之偵測胞68可將指示已匹配搜尋準則之第一搜尋項之一信號輸出至啟動路由矩陣36。
如圖7所圖解說明，在匹配第一搜尋項之後，啟動路由矩陣36可藉由將1寫入至其偵測胞68中之記憶體胞70來啟動下一特徵胞64。在下一項滿足第一搜尋項之情況下(例如，若接收項序列「bbig」)，啟動路由矩陣36亦可維持特徵胞63之作用中狀態。在搜尋資料串流12期間之一部分時間或大致所有時間期間，搜尋準則之第一搜尋項可維持處於一作用中狀態中。
在圖7中，資料串流12將字母「i」呈現給辨識模組22。作為回應，特徵胞63、64及66中之每一者可在其輸出導體56上輸出指示儲存於連接至導體72之記憶體胞58(其表示字母「i」)中之值之一信號。然後，偵測胞68可各自判定其等是否已接收指示一匹配之一信號及其等是否係作用中的。由於特徵胞64經組態以偵測字母「i」且係作用中的(如其記憶體胞70所指示)，因此特徵胞64中之偵測胞68可 將指示已匹配其搜尋準則之下一搜尋項之一信號輸出至啟動路由矩陣36。
接下來，啟動路由矩陣36可啟動特徵胞66，如圖8所圖解說明。在評估下一項之前，可撤銷啟動特徵胞64。可藉由特徵胞64之偵測胞68在偵測循環之間重設其記憶體胞70來撤銷啟動特徵胞64，或啟動路由矩陣36可撤銷啟動特徵胞64，舉例而言。
在圖8中，資料串流12將項「g」呈現給列解碼器28，該列解碼器選擇表示項「g」之導體74。作為回應，特徵胞63、64及66中之每一者可在其等輸出導體56上輸出指示儲存於連接至導體74之記憶體胞58(其表示字母「g」)中之值之一信號。然後，偵測胞68可各自判定其等是否已接收指示一匹配之一信號及其等是否係作用中的。由於特徵胞66經組態以偵測字母「g」且係作用中的(如其記憶體胞70所指示)，因此特徵胞66中之偵測胞68可將指示已匹配其搜尋準則之最後一個搜尋項之一信號輸出至啟動路由矩陣36。
一搜尋準則之末端或一搜尋準則之一部分可由啟動路由矩陣36或偵測胞68來識別。此等組件36或68可包含指示其等特徵胞63、64或66是規定一搜尋準則之最後一個搜尋項還是一搜尋準則之一組件之記憶體。舉例而言，一搜尋準則可規定其中字「cattle」出現兩次之所有句子，且辨識模組可將指示「cattle」在一句子內之每一出現之一信號輸出至彙總模組，該彙總模組可計數該等出現以判定是否滿足該搜尋準則。
特徵胞63、64或66可在數個條件下被啟動。一特徵胞63、64或66可係「始終作用中的」，此意指其在一搜尋之全部或大致全部期間保持作用中。一始終作用中特徵胞63、64或66之一實例係搜尋準則之第一特徵胞(例如，特徵胞63)。
一特徵胞63、64或66可係「在請求時作用中」，此意指特徵胞63、64或66在匹配某一在前條件時(例如，在匹配一搜尋準則中之在前搜尋項時)係作用中的。一實例係在由圖6至圖8中之特徵胞63請求時係作用中的之特徵胞64及在由特徵胞64請求時係作用中的之特徵胞66。
一特徵胞63、64或66可係「自啟動」，此意指一旦其被啟動，則只要匹配其搜尋項其即啟動其自身。舉例而言，具有由任一數值數位匹配之一搜尋項之一自啟動特徵胞可在序列「123456xy」中保持作用中直至到達字母「x」。每當匹配該自啟動特徵胞之搜尋項時，其可啟動搜尋準則中之下一特徵胞。因此，一始終作用中特徵胞可由一自啟動特徵胞及一當請求時作用中之特徵胞形成：該自啟動特徵胞可經程式化而其所有記憶體胞58皆儲存1，且其可在每一項之後重複啟動該當請求時作用中之特徵胞。在某些實施例中，每一特徵胞63、64及66可在其偵測胞68中或在啟動路由矩陣36中包含規定該特徵胞是否係始終作用中之一記憶體胞，藉此由一單個特徵胞形成一始終作用中特徵胞。
圖9繪示經組態以根據一第一搜尋準則75及一第二搜尋準則76並行進行搜尋之一辨識模組22之一實例。在此實例中，第一搜尋準則75規定字「big」，且第二搜尋準則76規定字「cab」。指示來自資料串流12之當前項之一信號可在大體相同時間傳達至每一搜尋準則75及76中之特徵胞。輸入導體37中之每一者跨越搜尋準則75及76兩者。因此，在某些實施例中，搜尋準則75及76兩者可大體同時評估當前項。據信，此加速對搜尋準則之評估。其他實施例可包含經組態以並行評估更多搜尋準則之更多特徵胞。舉例而言，某些實施例可包含並行操作之多於100、500、1000、5000、或10,000個特徵胞。此等特徵胞可大體同時評估數百個或數千個搜尋準則。
具有不同數目之搜尋項之搜尋準則可藉由將更多或更少之特徵胞分配至該等搜尋準則來形成。簡單搜尋準則可消耗比複雜搜尋準則更少之呈特徵胞形式之資源。據信，相對於具有大量大體相同核心之處理器(全部經組態以評估複雜搜尋準則)，此降低型樣辨識處理器14(圖2)之成本。
圖10至圖12繪示一更複雜搜尋準則之一實例及啟動路由矩陣36之特徵兩者。啟動路由矩陣36可包含複數個啟動路由胞78，其群組可與特徵胞63、64、66、80、82、84及86中之每一者相關聯。舉例而言，該等特徵胞中之每一者可包含5、10、20、50個或更多個啟動路由胞78。啟動路由胞78可經組態以在匹配一在前搜尋項時將啟動信號發射至一搜尋準則中之下一搜尋項。啟動路由胞78可經組態以將啟動信號路由至毗鄰特徵胞或相同特徵胞內之其他啟動路由胞78。啟動路由胞78可包含指示哪些特徵胞對應於一搜尋準則中之下一搜尋項之記憶體。
如圖10至圖12所圖解說明，辨識模組22可經組態以根據複雜搜尋準則而非規定單個字之準則進行搜尋。suffix舉例而言，辨識模組22可經組態以搜尋以一首碼88開頭且以兩個尾碼90或92中之一者結束之字。所圖解說明之搜尋準則規定以呈序列之字母「c」及「l」開頭且以字母序列「ap」或字母序列「oud」結束之字。此係規定多個目標表達(例如，字「clap」或字「cloud」)之一搜尋準則之一實例。
在圖10中，資料串流12將字母「c」呈現給辨識模組22，且特徵胞63既係作用中的又偵測一匹配。作為回應，啟動路由矩陣36可啟動下一特徵胞64。啟動路由矩陣36亦可維持特徵胞63之作用中狀態，此乃因特徵胞63係搜尋準則中之第一搜尋項。
在圖11中，資料串流12呈現一字母「l」，且特徵胞64辨識一匹配且係作用中的。作為回應，啟動路由矩陣36可將一啟動信號發射至第一尾碼90之第一特徵胞66及第二尾碼92之第一特徵胞82兩者。在其他實例中，可啟動更多尾碼，或多個首碼可啟動一個或多個尾碼。
接下來，如圖12所圖解說明，資料串流12將字母「o」呈現給辨識模組22，且第二尾碼92之特徵胞82偵測一匹配且係作用中的。作為回應，啟動路由矩陣36可啟動第二尾碼92之下一特徵胞84。在允許特徵胞66變為非作用中時，針對第一尾碼90之搜尋可停止。圖10至圖12所圖解說明之步驟可繼續經過字母「u」及「d」，或該搜尋可停止直至下一次匹配首碼88。
型樣辨識處理器14之實施例可包含特徵胞30之任一配置。圖13至圖16繪示根據本發明之一實施例之特徵胞30之一階層式配置。在一項實施例中，如圖13中所繪示，一階層之一第一層級可包含特徵胞30，其配置成兩個特徵胞30(特徵胞1與特徵胞0)之群組94。每一特徵胞30可接收一輸入(例如，一啟用狀態信號)且可將一下一狀態信號輸出至特徵胞之另一群組。群組94中之每一特徵胞30可耦合至基於每一特徵胞30之輸出而自群組94提供一輸出之一輸出驅動選擇96。舉例而言，在一項實施例中，輸出驅動選擇96可經組態以輸出自特徵胞30所接收之一下一狀態輸出「0」信號、一下一狀態輸出「1」信號或兩個下一狀態輸出信號之邏輯「或」。
如圖14中所示，一第二階層層級可包含特徵胞之每一群組94，其配置成群組94之一列98。每一列98可包含特徵胞30之任一數目個群組94。舉例而言，在圖14中所示之實施例中，列98可包含兩個特徵胞30之八個群組94，例如，群組0至群組7。
如圖15中所示，一階層之一第三層級可包含聚集至區塊100中之多個列98，其中每一區塊100包含一個或多個列98。在處理器14之一項實施例中，每一區塊100可包含16個列98，例如，列0至列15。然後，型樣辨識處理器14可包含用於實施上文所述之該等經程式化狀態機及型樣搜尋之任一數目個區塊100。如圖16中所示，在一項實施例中，型樣辨識處理器14可包含512個區塊，例如，區塊0至區塊512。
上文所圖解說明之群組94、列98及區塊100闡述特徵胞之一階層式配置。一經程式化狀態機可包含任一數目個特徵胞30。因此，每一群組、列或區塊可包含多個經程式化狀態機。在型樣辨識處理器14之操作期間，諸如在上文所述之搜尋循環期間，藉由自每一特徵胞30輸出且由每一群組94之輸出驅動選擇96選擇之下一狀態信號將一經程式化狀態機(例如，一個或多個特徵胞)之每一狀態路由至該經程式化狀態機之下一狀態(稱為「下一狀態路由」)。
圖17至圖21闡述根據本發明之一實施例提供下一狀態路由、可程式化性及高輸送量之一多階層式路由矩陣。如本文中所用，術語「路由矩陣」係指用於型樣辨識處理器14之組件之間的路由通信之複數個連接。下文所述之「路由矩陣」可在功能上不同於上文在圖1至圖12中所述之矩陣。如下文進一步闡述，路由矩陣可提供在上文所述之型樣辨識處理器14之階層之每一層級處、每一層級中及每一層級之間的可程式化及/或不可程式化連接。該等連接可連接型樣辨識處理器14之特徵胞、群組、列及區塊之間的路由線。該等連接可包含，但不限於以下類型之連接：可程式化及不可程式化；單向及雙向；邏輯組合(「或」、「及」、「互斥或」等等)；選擇器(例如，諸多中之一者)；及隔離器(阻斷至一線之連接)。一可程式化連接可經組態以執行上文所列舉之功能性中之任一者。舉例而言，一可程式化連接可程式化為單向、雙向、任一邏輯組合、選擇器、分離器等等。一不可程式化連接可執行上文所述之功能性中之任一者，但不能夠程式化有一不同功能性。
下文在表1中所概括之連接符號繪示圖17至圖21中之連接：
圖17繪示包含上文在圖13中所述之特徵胞30之群組94且根據本發明之一實施例之一階層層級。如上文所提及，每一特徵胞30可接收啟用特徵胞作為下一狀態之一輸入。亦如上文所提及，基於對照程式化於特徵胞30中之搜尋準則所執行之型樣匹配，特徵胞30可產生啟用下一作用中狀態(下一狀態信號)之一輸出。
特徵胞30之輸入及輸出信號之路由係由該等連接判定。群組94之特徵胞30可由本端路由線102(本端路由0及本端路由1)來互連。群組94之特徵胞30之輸出由輸出連接104耦合至本端路由線102及輸出驅動選擇96。舉例而言，特徵胞0由一第一輸出連接104A耦合至本端路由線0且特徵胞1由一第二輸出連接104B耦合至本端路由線1。如圖17中所繪示，在一項實施例中，輸出連接係不可程式化之「第一層級」連接。在此一實施例中，連接104係不可移除的且係不可組態的。在其他實施例中，輸出連接104可係可程式化的。
輸出驅動選擇96可經程式化以驅動來自特徵胞30之所接收輸出之任一數目或類型之信號。如上文所提及，在一項實施例中，輸出驅動選擇96可經組態以輸出以下三個可能邏輯輸出中之一者：「下一狀態輸出0」；「下一狀態輸出1」；或兩個下一狀態輸出信號之邏輯「或」。在其他實施例中，輸出驅動選擇96可經組態以輸出其他邏輯組合，諸如「及」、「非或」及/或「互斥或」。
本端路由線102可由輸入連接106耦合至特徵胞30之輸入105(其可表示一個或多個輸入信號)。舉例而言，特徵胞0可分別由輸入連接106A及106B耦合至本端路由線0及1。類似地，特徵胞1可分別由輸入連接106C及106D耦合至本端路由線0及本端路由線1。如圖17中所繪示，輸入連接106可係可程式化之「第1層級」連接。在此一實施例中，輸入連接106可經組態以提供連接輸入105中之任一者之一邏輯「或」。
圖18繪示具有如上文在圖14中所述之群組94之列98且根據本發明之一實施例之一階層層級。如上文所提及，每一列98可包含特徵胞30之任一數目個群組94，例如，圖18中所示之群組0至群組7。列98之群組可由列路由線108來互連。在一項實施例中，可為區塊100之每一列提供列路由線108。因此，在每區塊100具有16個列98之一實施例中，可提供16個列路由線，例如，列路由線0至列路由線15。
自每一群組94之輸出驅動選擇96之輸出可由輸出連接110耦合至每一列路由線108。在一項實施例中，該等輸出連接可係可程式化「第2層級」連接。如圖18中所示，舉例而言，群組0可分別由輸出連接110A及110B耦合至列路由線0及15。群組7可分別由輸出連接110C及110D耦合至列路由線0及15。所有其他列路由線(圖中未展示)可由輸出連接110耦合至群組0至群組7之輸出驅動選擇。輸出連接110可經組態以使得一群組94之輸出驅動選擇96能夠驅動或不驅動一特定列路由線108。
另外，列路由線108可由輸入連接112耦合至每一特徵胞30之輸入105。在一項實施例中，輸入連接112可係可程式化之「第2層級」連接。舉例而言，列路由線108可由輸入連接112A及112B耦合至群組0之特徵胞0之輸入，且列路由線108可由輸入連接112C及112D耦合至群組0之特徵胞1之輸入。類似地，亦如圖18中所示，列路由線108可由輸入連接112E及112F耦合至群組7之特徵胞0之輸入，且列路由線108可由輸入連接112G及112H耦合至群組7之特徵胞1。其他列路由線(圖中未展示)可耦合至列98之每一群組94之每一特徵胞30之輸入。在此一實施例中，輸入連接112可程式化為特徵胞30之任何所連接輸入之一邏輯「或」。在其他實施例中，該等連接可係不可程式化及/或雙向連接。
接下來，圖19繪示具有如上文在圖15中所述之多個列98且根據本發明之一實施例之一區塊100之一階層層級。如上文所述，區塊100可包含任一數目個列98，例如，列0至列15。區塊100之列98可由區塊內部路由線114來連接。區塊內部路由線114可由雙向連接116耦合至列路由線112。在一項實施例中，該等雙向連接可係可程式化之「第3層級」連接。舉例而言，區塊內部線路由線0可由雙向連接116A耦合至列0之列路由線0且由雙向連接116B耦合至列0之列路由線15。區塊內部線路由線0可由雙向連接116C耦合至列15之列路由線0且由雙向連接116D耦合至列15之列路由線15。類似地，區塊內部路由線23可由雙向連接116E耦合至列0之列路由線0且由雙向連接116F耦合至列0之列路由線15。此外，亦如圖19中所示，區塊內部路由線23可由雙向連接116G耦合至列15之列路由線0且由雙向連接116H耦合至列15之列路由線15。其他區塊內部線(圖中未展示)可由雙向連接116耦合至每一列98之每一列路由線112。
如上文中所述，雙向連接116可係可程式化的。因此，雙向連接116可經程式化以使得區塊內部路由線114中一者或多者能夠驅動一各別列路由線112或使得一個或多個列路由線112能夠驅動一各別區塊內部路由線114。可個別地程式化每一雙向連接116，從而基於逐條線達成列路由線112與區塊內部路由線114之間的連接之組態。在其他實施例中，該等連接可係不可程式化及/或單向連接。
圖20繪示根據本發明之一實施例之具有區塊100之路由矩陣之一頂部階層層級117。在一項實施例中，如圖20中所示，頂部層級117可包含512個區塊100，例如區塊0至區塊511。區塊100可由頂部層級路由線118來互連。頂部層級路由線118可由雙向連接120連接至區塊內部路由線114。因此，如圖20中所示，頂部層級路由線0可分別由雙向連接120A及120B耦合至區塊0之區塊內部路由線0及區塊內部路由線23。類似地，頂部部層級路由線0可分別由雙向連接120C及120D耦合至區塊511之區塊內部線0及區塊內部線23。如圖20中所示，頂部層級路由線23可分別由雙向連接120E及120F耦合至區塊0之區塊內部路由線0及區塊內部路由線23。此外，頂部層級路由線23可分別由雙向連接120G及120H耦合至區塊511之區塊內部線0及區塊內部線23。所有其他頂部層級路由線(圖中未展示)可由雙向連接120耦合至區塊100之區塊內部線114。
如圖20中所示，雙向連接120可係可程式化之「第4層級連接」。雙向連接可經程式化以使得一個或多個區塊內部路由線114能夠驅動一各別頂部層級路由線118或使得一個或多個頂部層級路由線118能夠驅動一各別區塊內部路由線114。因此，連接120可係基於逐條線而程式化及組態。在其他實施例中，該等連接可係不可程式化及/或單向連接。
有利地，上文所述之多階層式路由矩陣可提供裝置之可程式化性之規則性、用於改良生產及製造良率之冗餘實施方案、不同應用之可變性、及邏輯改變之更容易之可視化及實施方案。
如上文所提及，該等連接可係能夠「阻斷」一線以使得無信號在一線上路由從而使得能夠停用型樣辨識處理器14之一冗餘區段之隔離器。圖21繪示根據本發明之一實施例之型樣辨識處理器14之一個或多個特徵胞30之隔離。舉例而言，型樣辨識處理器14可包含特徵胞30之一區塊130，其提供比型樣辨識處理器14所用之容量更多之容量。亦即，在製造期間，為增加良率，一型樣辨識處理器14可製造有比針對處理器14之功能所規定之容量過量之記憶體容量(過量之特徵胞30)。在處理器14之製造及測試期間，可藉由移除可用於由處理器14所用之經程式化狀態機之特徵胞來「停用」過量之特徵胞30。某些實施例可不使用特徵胞30之所有區塊。在此等實施例中，可停用不使用之區塊。經停用之區塊可不被「啟動」及/或「通電」且在更新循環期間可不被更新。
區塊130可由頂部層級路由線與區塊內部路由線之間的連接132耦合至型樣辨識處理器14之其他部分。在此一實施例中，連接132可係可程式化之「第4層級連接」，其可程式化至任何所期望之功能性。因此，若區塊130提供過量之容量，則連接132可經程式化以將區塊130與該等路由線之剩餘部分隔離。因此，可程式化連接132可「阻斷」頂部層級路由線118與區塊內部路由線114之間的連接。區塊130可稱為「停用的」。另外，(諸如)可藉由在區塊130中設定一適當程式化位元來使不使用之區塊130「斷電」。
相比而言，用以提供用於型樣辨識處理器14之經程式化狀態機之記憶體容量之其他區塊可透過頂部層級路由線118及區塊內部路由線114進行存取。舉例而言，如圖21中所示，區塊134亦由連接136連接至與停用區塊132相同之頂部層級路由線118。如圖21中所示，連接136可係可程式化之第4層級連接。然而，連接136可經程式化以(諸如)藉由允許頂部層級路由線驅動區塊內部路由線(或反之亦然)來使得能夠存取至由區塊134提供之記憶體容量。在其他實施例中，特徵胞30可(諸如)藉由程式化區塊內部路由線114與列路由線112之間的連接138來在列層級處停用，及/或(諸如)藉由程式化列路由線112與本端路由線102之間的連接140來在群組層級處停用。
此外，在其他實施例中，上文所述之多階層式路由矩陣可基於型樣辨識處理器14中所實施之型樣匹配功能性而在層級、連接等方面不同。舉例而言，其他實施例可在階層中包含一不同數目個層級，及/或在層級、群組、列及/或區塊之間包含不同數目個連接。另外，其他實施例可包含可用於可程式化連接之不同可程式化功能、階層中之不同類型之連接及不同點、計劃性地將連接線阻斷成多個線之能力及在階層中之不同層級處添加及/或刪除不同功能性之能力。
圖22繪示根據本發明之一實施例之上文所述多階層式路由矩陣之組態之一過程142。在型樣辨識處理器14之組態期間，可以任一次序程式化階層之每一層級處及每一層級之間的連接。此外，可基於型樣辨識處理器14中所期望之具體型樣匹配實施方案而手動地或自動地程式化此等連接。亦應瞭解，矩陣之層級處或層級之間的連接之程式化可相依於程式化至矩陣之其他層級中之功能性。首先，可程式化第一階層層級處之連接(方塊144)。舉例而言，此可包含程式化特徵胞30之輸出與本端路由線102及程式化特徵胞30之輸入與本端路由線102之間的連接，諸如程式化上文在圖17中所述之連接106。在某些實施例中，自特徵胞30之輸入及/或輸出連接可係不可程式化連接且可不被程式化。舉例而言，亦如上文在圖17中所述，在一項實施例中，輸出連接104可係不可程式化連接。
接下來，可程式化在該階層之一第二層級處之連接(方塊146)。在一項實施例中，此程式化可包含程式化列路由線108與一群組94之間的輸入連接，如上文在圖18中所述。舉例而言，特徵胞30之輸入與列路由線108之間的連接112可程式化為特徵胞30之輸入105之一邏輯「或」(或其他功能)。類似地，輸出連接110可經程式化以提供列路由線與群組94之輸出驅動選擇96之間的所期望之功能性。
另外，可程式化階層式路由矩陣之一第三層級處之連接(方塊148)。如上文在圖19中所論述，在一項實施例中，可程式化列路由線112與區塊內部路由線114之間的連接116。舉例而言，連接116可經程式化以提供區塊內部路由線114與列路由線112之間的所期望之功能性以隔離(停用)某些特徵胞或提供任一其他可程式化功能。
接下來，可程式化一第四階層層級處之連接(方塊150)。在上文圖20中所繪示之實施例中，此程式化可包含程式化區塊內部路由線114與頂部層級路由線118之間的連接。舉例而言，上文在圖20中所示之連接120可經程式化以提供頂部層級路由線118與區塊內部路由線114之間的所期望之功能性。亦如上文在圖21中所論述，在某些實施例中，此程式化可包含停用型樣辨識處理器14之冗餘容量(例如，特徵胞)。如圖22中所示，對連接之此程式化可繼續直至路由矩陣之第n層級(方塊152)。藉由程式化路由矩陣之該等連接，型樣辨識處理器14可經組態以提供特徵胞(及狀態機)之間的所期望之邏輯及下一狀態路由。如上文所提及，對該等連接之程式化提供對型樣辨識處理器14之組態之瞭解亦又提供針對不同實施方案之路由靈活性及可變性。
10．．．系統
12．．．資料串流
14．．．型樣辨識處理器
16．．．搜尋準則
18．．．編譯器
20．．．中央處理單元
22．．．辨識模組
24．．．彙總模組
26．．．輸出匯流排
28．．．列解碼器
30．．．特徵胞
32．．．搜尋項陣列
34．．．偵測陣列
36．．．啟動路由矩陣
37．．．輸入導體
38．．．偵測匯流排
40．．．鎖存器矩陣
42．．．彙總路由矩陣
44．．．臨限邏輯矩陣
46．．．邏輯積矩陣
48．．．邏輯和矩陣
50．．．初始化路由矩陣
51．．．輸出緩衝器
53．．．群組邏輯線
54．．．搜尋項胞
56．．．輸出導體
58．．．記憶體胞
60．．．導體
62．．．導體
63．．．特徵胞
64．．．特徵胞
66．．．特徵胞
68．．．偵測胞
70．．．記憶體胞
72．．．導體
74．．．導體
75．．．第一搜尋準則
76．．．第二搜尋準則
78．．．啟動路由胞
80．．．特徵胞
82．．．特徵胞
84．．．特徵胞
86．．．特徵胞
88．．．首碼
90．．．尾碼
92．．．尾碼
94．．．群組
96．．．輸出驅動選擇
98．．．列
100．．．區塊
102．．．本端路由線
104A．．．第一輸出連接
104B．．．第二輸出連接
105．．．輸入
106A．．．輸入連接
106B．．．輸入連接
106C．．．輸入連接
106D．．．輸入連接
108．．．列路由線
110A．．．輸出連接
110B．．．輸出連接
110C．．．輸出連接
110D．．．輸出連接
112．．．輸入連接
112A．．．輸入連接
112B．．．輸入連接
112C．．．輸入連接
112D．．．輸入連接
112E．．．輸入連接
112F．．．輸入連接
112G．．．輸入連接
112H．．．輸入連接
114．．．區塊內部路由線
116A．．．雙向連接
116B．．．雙向連接
116C．．．雙向連接
116D．．．雙向連接
116E．．．雙向連接
116F．．．雙向連接
116G．．．雙向連接
116H．．．雙向連接
117．．．頂部階層層級
118．．．經層級路由線
120A．．．雙向連接
120B．．．雙向連接
120C．．．雙向連接
120D．．．雙向連接
120E．．．雙向連接
120F．．．雙向連接
120G．．．雙向連接
120H．．．雙向連接
130．．．區塊
132．．．連接(停用區塊)
134．．．區塊
136．．．連接
138．．．連接
140．．．連接
圖1繪示對一資料串流進行搜尋之系統之一實例；
圖2繪示圖1之系統中之一型樣辨識處理器之一實例；
圖3繪示圖2之型樣辨識處理器中之一搜尋項胞之一實例；
圖4及圖5繪示針對一單個字元對資料串流進行搜尋之圖3之搜尋項胞；
圖6至圖8繪示針對一字對資料串流進行搜尋之包含數個搜尋項胞之一辨識模組；
圖9繪示經組態以針對兩個字對資料串流進行並行搜尋之辨識模組；
圖10至圖12繪示辨識模組根據規定具有相同首碼之多個字之一搜尋準則進行搜尋；
圖13至圖16繪示根據本發明之一實施例之一型樣辨識處理器之特徵胞之一階層式配置；
圖17至圖20繪示根據本發明之一實施例之一型樣辨識處理器之一多階層式路由矩陣；
圖21繪示根據本發明之一實施例停用一型樣辨識處理器之特徵胞之一部分；且
圖22係根據本發明之一實施例之用於程式化一多階層式路由矩陣之連接之一過程之一流程圖。
30．．．特徵胞
94．．．群組
96．．．輸出驅動選擇
98．．．列
100．．．區塊

Claims (31)

  1. 一種用於型樣辨識之裝置，其包括：一型樣辨識處理器，其包括：複數個邏輯群組，其中每一邏輯群組包括多個第一路由線及一個或多個特徵胞，其中該一個或多個特徵胞之每一特徵胞包含用於啟用(enable)該特徵胞之一啟用輸入及用於啟用另一特徵胞之一啟用輸出，其中每一邏輯群組之該一個或多個特徵胞由多個第一連接選擇性地耦合至該等第一路由線，且其中該等第一連接包含啟用輸入連接以及啟用輸出連接，該等啟用輸入連接將該一個或多個特徵胞之每一特徵胞之該啟用輸入藉由經組態以被程式化以執行複數個功能之任何一者之一可程式化連結而耦合至該等第一路由線，該等啟用輸出連接將該一個或多個特徵胞之每一特徵胞之該啟用輸出藉由無法被程式化以執行多於該複數個功能之特定一者之一不可程式化連結而耦合至該等第一路由線；複數個邏輯列，其中每一邏輯列包括該複數個邏輯群組中之一者或多者，其中每一邏輯列之該一個或多個邏輯群組由多個第二連接耦合至多個第二路由線，其中該等第二路由線由該等第二連接選擇性地耦合至該啟用輸入；及複數個邏輯區塊，其中每一邏輯區塊包括該複數個邏輯列中之一者或多者，其中每一邏輯區塊之該一個或多個邏輯列由第三連接耦合至第三路由線； 其中該複數個邏輯區塊由第四連接耦合至第四路由線。
  2. 如請求項1之裝置，其中該複數個邏輯群組中之每一邏輯群組進一步包括耦合至各別邏輯群組之該一個或多個特徵胞之一輸出驅動選擇器。
  3. 如請求項2之裝置，其中該輸出驅動選擇器經組態以基於該各別群組之該一個或多個特徵胞之輸出而提供一輸出。
  4. 如請求項2之裝置，其中該輸出驅動選擇器經組態以輸出該各別邏輯群組之該一個或多個特徵胞中之一者之一輸出或該邏輯群組之該一個或多個特徵胞之該等輸出之一邏輯組合。
  5. 如請求項2之裝置，其中每一邏輯群組之該一個或多個特徵胞中之每一者由一不可程式化連接耦合至一各別輸出驅動選擇器。
  6. 如請求項1之裝置，其中該複數個邏輯群組中之每一者包括兩個特徵胞。
  7. 如請求項1之裝置，其中該複數個特徵胞中之每一者經組態以接收一個或多個輸入並輸出一下一狀態信號。
  8. 如請求項7之裝置，其中該等第一連接包括第一可程式化連接。
  9. 如請求項8之裝置，其中該等第一可程式化連接經組態以提供該等特徵胞中之一各別者之該一個或多個輸入之一邏輯組合。
  10. 如請求項2之裝置，其中每一邏輯群組之該輸出驅動選擇器由該等第二連接中之各別者耦合至該等第二路由線，其中該等第二連接中之該等各別者包括可程式化連接。
  11. 如請求項1之裝置，其中每一邏輯群組之該一個或多個特徵胞各自由可程式化連接耦合至該等第二路由線。
  12. 如請求項1之裝置，其中每一邏輯區塊之該一個或多個邏輯列各自由可程式化連接耦合至該等第三路由線。
  13. 如請求項1之裝置，其中該等第四連接係可程式化連接。
  14. 一種用於型樣辨識之裝置，其包括：一型樣辨識處理器，其包括：一階層式路由矩陣，該矩陣包括：一第一層級，其包括一個或多個特徵胞，其中該一個或多個特徵胞之每一特徵胞包括用於啟用該特徵胞之一啟用輸入及用於啟用另一特徵胞之一啟用輸出，其中每一特徵胞耦合至一個或多個第一可程式化連接及一不可程式化連接，該一個或多個可程式化連接經組態以被程式化以執行複數個功能，該不可程化連接不可被程式化以執行多於該複數個功能之特定一者，且其中該一個或多個第一可程式化連接被耦合至該一個或多個特徵胞每一特徵胞之該啟用輸入，其中該不可程式化連接被耦合至該一個或多個特徵胞每一特徵胞之該啟用輸出；一第二層級，其包括特徵胞之一個或多個群組，其 中該等群組經由一個或多個第二可程式化連接耦合至一個或多個列路由線，其中該一個或多個列路由線由該一個或多個第二連接耦合至該啟用輸入；一第三層級，其包括群組之一個或多個列，其中該等列耦合至一個或多個第三可程式化連接；及一第四層級，其包括列之一個或多個區塊，其中該等區塊耦合至一個或多個第四可程式化連接。
  15. 如請求項14之裝置，其中該階層式路由矩陣經組態以提供該一個或多個特徵胞之間的下一狀態路由。
  16. 如請求項14之裝置，其中每一群組之該一個或多個特徵胞耦合至一個或多個各別不可程式化連接。
  17. 如請求項16之裝置，其中該一個或多個群組中之每一者包括由該各別一個或多個不可程式化連接耦合至該一個或多個特徵胞之一輸出。
  18. 如請求項16之裝置，其中該一個或多個第二可程式化連接中之一各別者經組態以使得該等群組中之一各別者之一輸出能夠驅動或不驅動一列路由線。
  19. 如請求項16之裝置，其中該一個或多個第三可程式化連接中之一各別者經組態以使得一列路由線能夠驅動一區塊內部路由線或使得一區塊內部路由線能夠驅動一列路由線。
  20. 如請求項16之裝置，其中該等第四可程式化連接中之一各別者經組態以使得一區塊內部路由線能夠驅動一頂部層級路由線或使得一頂部層級路由線能夠驅動一區塊內 部路由線。
  21. 一種型樣辨識處理器，其包括：複數個路由線，其中該複數個路由線經組態以在該處理器之多個特徵胞之間路由，其中該等特徵胞之每一特徵胞包括用於啟用該特徵胞之一啟用輸入及用於啟用另一特徵胞之一啟用輸出；複數個可程式化連接，其等耦合至該複數個路由線中之一第一一者或多者，其中該複數個可程式化連接之每一者經組態以被程式化以執行複數個功能之任意一者；及複數個不可程式化連接，其耦合至該複數個路由線之一第二一者或多者，其中每一不可程式化連接無法被程式化以執行多於該複數個功能之特定一者。
  22. 如請求項21之型樣辨識處理器，其中該複數個可程式化連接中之一者或多者包括單向或雙向連接。
  23. 如請求項21之型樣辨識處理器，其中該複數個可程式化連接中之一者或多者經組態以提供單向或雙向連接。
  24. 如請求項21之型樣辨識處理器，其中該複數個可程式化連接中之一者或多者經組態以提供一邏輯「或」、一邏輯「及」或一邏輯「互斥或」。
  25. 如請求項21之型樣辨識處理器，其中該複數個可程式化連接中之一者或多者經組態以提供一選擇器。
  26. 如請求項21之型樣辨識處理器，其中該複數個可程式化連接中之一者或多者經組態以提供一隔離器。
  27. 一種用於型樣辨識之方法，其包括：程式化一型樣辨識處理器之複數個路由連接中之一個或多個第一可程式化連接，其中該等第一可程式化連接經組態以被程式化以執行複數個功能之任意一者並被耦合至包括經由一個或多個本端路由線互連之一個或多個特徵胞之一第一層級，其中該一個或多個特徵胞之每一特徵胞包括用於啟用該特徵胞之一啟用輸入以及藉由無法被程式化以執行多於該複數個功能之特定一者之一不可程式化連結而用於啟用另一特徵胞之一啟用輸出；及程式化該型樣辨識處理器之該複數個路由連接中之一個或多個第二可程式化連接，其中該等第二可程式化連接耦合至包括該一個或多個特徵胞之一個或多個群組之一第二層級。
  28. 如請求項27之方法，其包括程式化該型樣辨識處理器之該複數個路由連接中之一個或多個第三可程式化連接，其中該等第三可程式化連接耦合至包括該一個或多個群組之一個或多個列之一第三層級。
  29. 如請求項27之方法，其包括程式化該型樣辨識處理器之該複數個路由連接中之一個或多個第四可程式化連接，其中該等第四可程式化連接耦合至包括該一個或多個列之一個或多個區塊之一第四層級。
  30. 如請求項29之方法，其包括程式化該等第一可程式化連接、第二可程式化連接、第三可程式化連接或第四可程式化連接或其任一組合以停用該型樣辨識處理器之一個 或多個特徵胞。
  31. 一種用於型樣辨識之系統，其包括：用於一型樣辨識處理器之一路由矩陣，該矩陣包括：複數個可程式化連接，其等介於該型樣辨識處理器之兩個或兩個以上組件之間，其中該複數個可程式化連接之每一者經組態以被程式化以執行複數個功能之任意一者；及複數個不可程式化連接，其等介於該型樣辨識處理器之兩個或兩個以上組件之間，其中每一不可程式化連接無法被程式化以執行多於該複數個功能之特定一者；其中該等組件包括經組態以各自搜尋一資料串流之至少一部份之特徵胞、該等特徵胞之邏輯配置及/或其任一組合，其中該等特徵胞之每一特徵胞包括用於啟用該特徵胞之一啟用輸入及用於啟用另一特徵胞之一啟用輸出。
TW099144023A 2009-12-15 2010-12-15 用於型樣辨識處理器之多階層式路由矩陣 TWI479342B (zh)

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
US12/638,759 US9323994B2 (en) 2009-12-15 2009-12-15 Multi-level hierarchical routing matrices for pattern-recognition processors

Publications (2)

Publication Number Publication Date
TW201131404A TW201131404A (en) 2011-09-16
TWI479342B true TWI479342B (zh) 2015-04-01

Family

ID=44070678

Family Applications (1)

Application Number Title Priority Date Filing Date
TW099144023A TWI479342B (zh) 2009-12-15 2010-12-15 用於型樣辨識處理器之多階層式路由矩陣

Country Status (7)

Country Link
US (5) US9323994B2 (zh)
EP (1) EP2513839B1 (zh)
JP (1) JP5753190B2 (zh)
KR (1) KR101960101B1 (zh)
CN (2) CN102713936A (zh)
TW (1) TWI479342B (zh)
WO (1) WO2011081799A2 (zh)

Families Citing this family (36)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20100138575A1 (en) 2008-12-01 2010-06-03 Micron Technology, Inc. Devices, systems, and methods to synchronize simultaneous dma parallel processing of a single data stream by multiple devices
US20100174887A1 (en) 2009-01-07 2010-07-08 Micron Technology Inc. Buses for Pattern-Recognition Processors
US9323994B2 (en) 2009-12-15 2016-04-26 Micron Technology, Inc. Multi-level hierarchical routing matrices for pattern-recognition processors
US8766666B2 (en) 2010-06-10 2014-07-01 Micron Technology, Inc. Programmable device, hierarchical parallel machines, and methods for providing state information
US8601013B2 (en) 2010-06-10 2013-12-03 Micron Technology, Inc. Analyzing data using a hierarchical structure
EP2668574B1 (en) 2011-01-25 2021-11-24 Micron Technology, INC. Utilizing special purpose elements to implement a fsm
WO2012103151A2 (en) 2011-01-25 2012-08-02 Micron Technology, Inc. State grouping for element utilization
KR101607736B1 (ko) 2011-01-25 2016-03-30 마이크론 테크놀로지, 인크. 오토마톤의 진입 차수 및/또는 진출 차수를 제어하기 위한 양화 언롤링
CN103547998B (zh) 2011-01-25 2016-11-09 美光科技公司 用于编译正则表达式的方法和设备
US9443156B2 (en) * 2011-12-15 2016-09-13 Micron Technology, Inc. Methods and systems for data analysis in a state machine
US8680888B2 (en) 2011-12-15 2014-03-25 Micron Technologies, Inc. Methods and systems for routing in a state machine
US8648621B2 (en) 2011-12-15 2014-02-11 Micron Technology, Inc. Counter operation in a state machine lattice
US8782624B2 (en) 2011-12-15 2014-07-15 Micron Technology, Inc. Methods and systems for detection in a state machine
US8593175B2 (en) * 2011-12-15 2013-11-26 Micron Technology, Inc. Boolean logic in a state machine lattice
US20130275709A1 (en) 2012-04-12 2013-10-17 Micron Technology, Inc. Methods for reading data from a storage buffer including delaying activation of a column select
US9524248B2 (en) 2012-07-18 2016-12-20 Micron Technology, Inc. Memory management for a hierarchical memory system
US9235798B2 (en) 2012-07-18 2016-01-12 Micron Technology, Inc. Methods and systems for handling data received by a state machine engine
US9389841B2 (en) 2012-07-18 2016-07-12 Micron Technology, Inc. Methods and systems for using state vector data in a state machine engine
US9304968B2 (en) 2012-07-18 2016-04-05 Micron Technology, Inc. Methods and devices for programming a state machine engine
US9075428B2 (en) 2012-08-31 2015-07-07 Micron Technology, Inc. Results generation for state machine engines
US9501131B2 (en) 2012-08-31 2016-11-22 Micron Technology, Inc. Methods and systems for power management in a pattern recognition processing system
US9448965B2 (en) 2013-03-15 2016-09-20 Micron Technology, Inc. Receiving data streams in parallel and providing a first portion of data to a first state machine engine and a second portion to a second state machine
US9703574B2 (en) 2013-03-15 2017-07-11 Micron Technology, Inc. Overflow detection and correction in state machine engines
TWI509441B (zh) * 2014-12-16 2015-11-21 Can flexibly set the data width of the multi-character string alignment device
WO2016109570A1 (en) 2014-12-30 2016-07-07 Micron Technology, Inc Systems and devices for accessing a state machine
US11366675B2 (en) 2014-12-30 2022-06-21 Micron Technology, Inc. Systems and devices for accessing a state machine
WO2016109571A1 (en) 2014-12-30 2016-07-07 Micron Technology, Inc Devices for time division multiplexing of state machine engine signals
US10977309B2 (en) 2015-10-06 2021-04-13 Micron Technology, Inc. Methods and systems for creating networks
US10846103B2 (en) 2015-10-06 2020-11-24 Micron Technology, Inc. Methods and systems for representing processing resources
US10691964B2 (en) 2015-10-06 2020-06-23 Micron Technology, Inc. Methods and systems for event reporting
US10146555B2 (en) 2016-07-21 2018-12-04 Micron Technology, Inc. Adaptive routing to avoid non-repairable memory and logic defects on automata processor
US10268602B2 (en) 2016-09-29 2019-04-23 Micron Technology, Inc. System and method for individual addressing
US10019311B2 (en) 2016-09-29 2018-07-10 Micron Technology, Inc. Validation of a symbol response memory
US12197510B2 (en) 2016-10-20 2025-01-14 Micron Technology, Inc. Traversal of S portion of a graph problem to be solved using automata processor
US10592450B2 (en) 2016-10-20 2020-03-17 Micron Technology, Inc. Custom compute cores in integrated circuit devices
US10929764B2 (en) 2016-10-20 2021-02-23 Micron Technology, Inc. Boolean satisfiability

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5784298A (en) * 1993-10-15 1998-07-21 International Business Machines Corporation Apparatus and method for using finite state machines (FSMs) to monitor a serial data stream for characteristic patterns
TW200422860A (en) * 2002-12-10 2004-11-01 Ibm Apparatus and methods for co-location and offloading of web site traffic based on traffic pattern recognition
US20070127482A1 (en) * 2005-02-12 2007-06-07 Curtis L. Harris General Purpose Set Theoretic Processor

Family Cites Families (178)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
IL38603A (en) 1972-01-21 1975-10-15 Bar Lev H Automatic pattern recognition method and apparatus particularly for optically recognizing alphanumeric characters
JPS4891935A (zh) 1972-03-08 1973-11-29
US4011547A (en) 1972-07-17 1977-03-08 International Business Machines Corporation Data processor for pattern recognition and the like
GB1518093A (en) 1974-10-04 1978-07-19 Mullard Ltd Mark detection apparatus
JPS51112236A (en) 1975-03-28 1976-10-04 Hitachi Ltd Shape position recognizer unit
JPS5313840A (en) 1976-07-23 1978-02-07 Hitachi Ltd Analogy calculator
US4204193A (en) 1978-11-03 1980-05-20 International Business Machines Corporation Adaptive alignment for pattern recognition system
US4414685A (en) 1979-09-10 1983-11-08 Sternberg Stanley R Method and apparatus for pattern recognition and detection
US4748674A (en) 1986-10-07 1988-05-31 The Regents Of The University Of Calif. Pattern learning and recognition device
US5014327A (en) 1987-06-15 1991-05-07 Digital Equipment Corporation Parallel associative memory having improved selection and decision mechanisms for recognizing and sorting relevant patterns
US5216748A (en) 1988-11-30 1993-06-01 Bull, S.A. Integrated dynamic programming circuit
US6253307B1 (en) 1989-05-04 2001-06-26 Texas Instruments Incorporated Data processing device with mask and status bits for selecting a set of status conditions
JP2833062B2 (ja) 1989-10-30 1998-12-09 株式会社日立製作所 キャッシュメモリ制御方法とこのキャッシュメモリ制御方法を用いたプロセッサおよび情報処理装置
US5028821A (en) 1990-03-01 1991-07-02 Plus Logic, Inc. Programmable logic device with programmable inverters at input/output pads
US5377129A (en) 1990-07-12 1994-12-27 Massachusetts Institute Of Technology Particle interaction processing system
DE69029390T2 (de) 1990-09-15 1997-06-12 Ibm Programmierbare Schaltung für eine neurale Logik
US5287523A (en) 1990-10-09 1994-02-15 Motorola, Inc. Method for servicing a peripheral interrupt request in a microcontroller
AU8966391A (en) 1990-12-24 1992-06-25 Ball Corporation System for analysis of embedded computer systems
US6400996B1 (en) 1999-02-01 2002-06-04 Steven M. Hoffberg Adaptive pattern recognition based control system and method
US5331227A (en) * 1992-05-15 1994-07-19 Micron Semiconductor, Inc. Programmable logic device macrocell with an exclusive feedback line and an exclusive external input line
US5300830A (en) * 1992-05-15 1994-04-05 Micron Semiconductor, Inc. Programmable logic device macrocell with an exclusive feedback and exclusive external input lines for registered and combinatorial modes using a dedicated product term for control
US5291482A (en) 1992-07-24 1994-03-01 At&T Bell Laboratories High bandwidth packet switch
US5357512A (en) 1992-12-30 1994-10-18 Intel Corporation Conditional carry scheduler for round robin scheduling
US5459798A (en) 1993-03-19 1995-10-17 Intel Corporation System and method of pattern recognition employing a multiprocessing pipelined apparatus with private pattern memory
US5825921A (en) 1993-03-19 1998-10-20 Intel Corporation Memory transfer apparatus and method useful within a pattern recognition system
US5457410A (en) * 1993-08-03 1995-10-10 Btr, Inc. Architecture and interconnect scheme for programmable logic circuits
CA2145361C (en) 1994-03-24 1999-09-07 Martin William Sotheran Buffer manager
US20050251638A1 (en) 1994-08-19 2005-11-10 Frederic Boutaud Devices, systems and methods for conditional instructions
JP3345515B2 (ja) 1994-08-31 2002-11-18 アイワ株式会社 ピークシフト補正回路およびそれを使用した磁気記録媒体再生装置
US5615237A (en) 1994-09-16 1997-03-25 Transwitch Corp. Telecommunications framer utilizing state machine
JPH0887462A (ja) 1994-09-20 1996-04-02 Fujitsu Ltd ステートマシン及び通信制御方式
US5790531A (en) 1994-12-23 1998-08-04 Applied Digital Access, Inc. Method and apparatus for determining the origin of a remote alarm indication signal
US6279128B1 (en) 1994-12-29 2001-08-21 International Business Machines Corporation Autonomous system for recognition of patterns formed by stored data during computer memory scrubbing
US5794062A (en) 1995-04-17 1998-08-11 Ricoh Company Ltd. System and method for dynamically reconfigurable computing using a processing unit having changeable internal hardware organization
US5659551A (en) 1995-05-31 1997-08-19 International Business Machines Corporation Programmable computer system element with built-in self test method and apparatus for repair during power-on
US5818254A (en) * 1995-06-02 1998-10-06 Advanced Micro Devices, Inc. Multi-tiered hierarchical high speed switch matrix structure for very high-density complex programmable logic devices
US5723984A (en) 1996-06-07 1998-03-03 Advanced Micro Devices, Inc. Field programmable gate array (FPGA) with interconnect encoding
US5680640A (en) 1995-09-01 1997-10-21 Emc Corporation System for migrating data by selecting a first or second transfer means based on the status of a data element map initialized to a predetermined state
US5754878A (en) 1996-03-18 1998-05-19 Advanced Micro Devices, Inc. CPU with DSP function preprocessor having pattern recognition detector that uses table for translating instruction sequences intended to perform DSP function into DSP macros
JPH10111862A (ja) 1996-08-13 1998-04-28 Fujitsu Ltd 再帰型ニューラルネットワークに基づく時系列解析装置および方法
JPH1069459A (ja) 1996-08-29 1998-03-10 Hitachi Ltd シリアルインタフェース制御装置およびその制御方法
US6300794B1 (en) * 1996-10-10 2001-10-09 Altera Corporation Programmable logic device with hierarchical interconnection resources
US6034963A (en) 1996-10-31 2000-03-07 Iready Corporation Multiple network protocol encoder/decoder and data processor
JP2940496B2 (ja) 1996-11-05 1999-08-25 日本電気株式会社 パタンマッチング符号化装置及び方法
US6317427B1 (en) 1997-04-24 2001-11-13 Cabletron Systems, Inc. Method and apparatus for adaptive port buffering
US6011407A (en) 1997-06-13 2000-01-04 Xilinx, Inc. Field programmable gate array with dedicated computer bus interface and method for configuring both
US6362868B1 (en) 1997-07-15 2002-03-26 Silverbrook Research Pty Ltd. Print media roll and ink replaceable cartridge
US6097212A (en) 1997-10-09 2000-08-01 Lattice Semiconductor Corporation Variable grain architecture for FPGA integrated circuits
US6041405A (en) 1997-12-18 2000-03-21 Advanced Micro Devices, Inc. Instruction length prediction using an instruction length pattern detector
DE19861088A1 (de) 1997-12-22 2000-02-10 Pact Inf Tech Gmbh Verfahren zur Reparatur von integrierten Schaltkreisen
US6219776B1 (en) 1998-03-10 2001-04-17 Billions Of Operations Per Second Merged array controller and processing element
EP0943995A3 (en) 1998-03-20 2000-12-06 Texas Instruments Incorporated Processor having real-time external instruction insertion for debug functions without a debug monitor
US6151644A (en) 1998-04-17 2000-11-21 I-Cube, Inc. Dynamically configurable buffer for a computer network
US6052766A (en) 1998-07-07 2000-04-18 Lucent Technologies Inc. Pointer register indirectly addressing a second register in the processor core of a digital processor
US9195784B2 (en) 1998-08-31 2015-11-24 Cadence Design Systems, Inc. Common shared memory in a verification system
US7430171B2 (en) 1998-11-19 2008-09-30 Broadcom Corporation Fibre channel arbitrated loop bufferless switch circuitry to increase bandwidth without significant increase in cost
US7899052B1 (en) 1999-01-27 2011-03-01 Broadcom Corporation Memory structure for resolving addresses in a packet-based network switch
US6412057B1 (en) 1999-02-08 2002-06-25 Kabushiki Kaisha Toshiba Microprocessor with virtual-to-physical address translation using flags
US6636483B1 (en) 1999-02-25 2003-10-21 Fairchild Semiconductor Corporation Network switch with zero latency flow control
US6317849B1 (en) 1999-04-28 2001-11-13 Intel Corporation Method and apparatus for controlling available capabilities of a device
JP2000347708A (ja) 1999-06-02 2000-12-15 Nippon Telegr & Teleph Corp <Ntt> ニューラルネットよる動的システムの制御方法及び装置及びニューラルネットよる動的システムの制御プログラムを格納した記憶媒体
US6880087B1 (en) * 1999-10-08 2005-04-12 Cisco Technology, Inc. Binary state machine system and method for REGEX processing of a data stream in an intrusion detection system
WO2001038978A1 (en) 1999-11-24 2001-05-31 Z-Force Corporation Configurable state machine driver and methods of use
EP1107107A1 (en) * 1999-12-10 2001-06-13 Koninklijke Philips Electronics N.V. Parallel data processing and shuffling
EP1109118A1 (en) * 1999-12-16 2001-06-20 Robert S. Lenzie Circuit configuration
US6640262B1 (en) 1999-12-20 2003-10-28 3Com Corporation Method and apparatus for automatically configuring a configurable integrated circuit
US6625740B1 (en) 2000-01-13 2003-09-23 Cirrus Logic, Inc. Dynamically activating and deactivating selected circuit blocks of a data processing integrated circuit during execution of instructions according to power code bits appended to selected instructions
US6614703B2 (en) 2000-01-13 2003-09-02 Texas Instruments Incorporated Method and system for configuring integrated systems on a chip
US7080359B2 (en) 2002-01-16 2006-07-18 International Business Machines Corporation Stack unique signatures for program procedures and methods
US6240003B1 (en) * 2000-05-01 2001-05-29 Micron Technology, Inc. DRAM content addressable memory using part of the content as an address
US6977897B1 (en) 2000-05-08 2005-12-20 Crossroads Systems, Inc. System and method for jitter compensation in data transfers
US6476636B1 (en) 2000-09-02 2002-11-05 Actel Corporation Tileable field-programmable gate array architecture
US6384627B1 (en) * 2001-02-16 2002-05-07 Xilinx, Inc. Logic block used as dynamically configurable logic function
CN1559072A (zh) 2001-09-30 2004-12-29 ÷ķ�����������ι�˾ 逆向搜索系统及方法
US6888371B2 (en) 2001-10-29 2005-05-03 Leopard Logic, Inc. Programmable interface for field programmable gate array cores
US7333580B2 (en) 2002-01-28 2008-02-19 Broadcom Corporation Pipelined parallel processing of feedback loops in a digital circuit
US6925510B2 (en) 2002-02-22 2005-08-02 Winbond Electronics, Corp. Peripheral or memory device having a combined ISA bus and LPC bus
US6650142B1 (en) * 2002-08-13 2003-11-18 Lattice Semiconductor Corporation Enhanced CPLD macrocell module having selectable bypass of steering-based resource allocation and methods of use
US7146643B2 (en) * 2002-10-29 2006-12-05 Lockheed Martin Corporation Intrusion detection accelerator
US7349416B2 (en) 2002-11-26 2008-03-25 Cisco Technology, Inc. Apparatus and method for distributing buffer status information in a switching fabric
US7292572B2 (en) 2002-12-11 2007-11-06 Lsi Corporation Multi-level register bank based configurable ethernet frame parser
US7089352B2 (en) * 2002-12-23 2006-08-08 Micron Technology, Inc. CAM modified to be used for statistic calculation in network switches and routers
US6944710B2 (en) * 2002-12-30 2005-09-13 Micron Technology, Inc. Multiple category CAM
US6800884B1 (en) * 2002-12-30 2004-10-05 Actel Corporation Inter-tile buffer system for a field programmable gate array
US6880146B2 (en) 2003-01-31 2005-04-12 Hewlett-Packard Development Company, L.P. Molecular-wire-based restorative multiplexer, and method for constructing a multiplexer based on a configurable, molecular-junction-nanowire crossbar
US7305047B1 (en) 2003-03-12 2007-12-04 Lattice Semiconductor Corporation Automatic lane assignment for a receiver
US7366352B2 (en) 2003-03-20 2008-04-29 International Business Machines Corporation Method and apparatus for performing fast closest match in pattern recognition
AU2004241602B2 (en) 2003-05-20 2008-05-08 Syndiant, Inc. Digital backplane
US7010639B2 (en) 2003-06-12 2006-03-07 Hewlett-Packard Development Company, L.P. Inter integrated circuit bus router for preventing communication to an unauthorized port
US6906938B2 (en) * 2003-08-15 2005-06-14 Micron Technology, Inc. CAM memory architecture and a method of forming and operating a device according to a CAM memory architecture
DE102004045527B4 (de) 2003-10-08 2009-12-03 Siemens Ag Konfigurierbare Logikschaltungsanordnung
US7860915B2 (en) 2003-12-29 2010-12-28 Xilinx, Inc. Digital signal processing circuit having a pattern circuit for determining termination conditions
US7849119B2 (en) 2003-12-29 2010-12-07 Xilinx, Inc. Digital signal processing circuit having a pattern detector circuit
US7243165B2 (en) 2004-01-14 2007-07-10 International Business Machines Corporation Parallel pattern detection engine
US7487542B2 (en) * 2004-01-14 2009-02-03 International Business Machines Corporation Intrusion detection using a network processor and a parallel pattern detection engine
JP4546775B2 (ja) 2004-06-30 2010-09-15 富士通株式会社 時分割多重処理可能なリコンフィギュラブル回路
GB0415850D0 (en) 2004-07-15 2004-08-18 Imagination Tech Ltd Memory management system
US7716455B2 (en) 2004-12-03 2010-05-11 Stmicroelectronics, Inc. Processor with automatic scheduling of operations
US7176717B2 (en) 2005-01-14 2007-02-13 Velogix, Inc. Programmable logic and routing blocks with dedicated lines
US7358761B1 (en) 2005-01-21 2008-04-15 Csitch Corporation Versatile multiplexer-structures in programmable logic using serial chaining and novel selection schemes
US7499464B2 (en) 2005-04-06 2009-03-03 Robert Ayrapetian Buffered crossbar switch with a linear buffer to port relationship that supports cells and packets of variable size
US7672529B2 (en) 2005-05-10 2010-03-02 Intel Corporation Techniques to detect Gaussian noise
US7804719B1 (en) 2005-06-14 2010-09-28 Xilinx, Inc. Programmable logic block having reduced output delay during RAM write processes when programmed to function in RAM mode
US7276934B1 (en) 2005-06-14 2007-10-02 Xilinx, Inc. Integrated circuit with programmable routing structure including diagonal interconnect lines
US20080126690A1 (en) 2006-02-09 2008-05-29 Rajan Suresh N Memory module with memory stack
US7376782B2 (en) 2005-06-29 2008-05-20 Intel Corporation Index/data register pair for indirect register access
FR2891075B1 (fr) * 2005-09-21 2008-04-04 St Microelectronics Sa Circuit de memoire pour automate de reconnaissance de caracteres de type aho-corasick et procede de memorisation de donnees dans un tel circuit
US7360063B2 (en) 2006-03-02 2008-04-15 International Business Machines Corporation Method for SIMD-oriented management of register maps for map-based indirect register-file access
US7512634B2 (en) * 2006-06-05 2009-03-31 Tarari, Inc. Systems and methods for processing regular expressions
US7725510B2 (en) 2006-08-01 2010-05-25 Alcatel-Lucent Usa Inc. Method and system for multi-character multi-pattern pattern matching
JP5183049B2 (ja) 2006-09-20 2013-04-17 高砂香料工業株式会社 染毛剤用安定化剤
US8065249B1 (en) * 2006-10-13 2011-11-22 Harris Curtis L GPSTP with enhanced aggregation functionality
US7774286B1 (en) * 2006-10-24 2010-08-10 Harris Curtis L GPSTP with multiple thread functionality
US7890923B2 (en) 2006-12-01 2011-02-15 International Business Machines Corporation Configurable pattern detection method and apparatus
US7899976B2 (en) 2006-12-08 2011-03-01 Pandya Ashish A FSA extension architecture for programmable intelligent search memory
KR100866604B1 (ko) 2007-01-23 2008-11-03 삼성전자주식회사 전원제어 장치 및 전원제어 방법
US7797521B2 (en) 2007-04-12 2010-09-14 International Business Machines Corporation Method, system, and computer program product for path-correlated indirect address predictions
KR20080097573A (ko) 2007-05-02 2008-11-06 삼성전자주식회사 가상 메모리 접근 방법
US20080320053A1 (en) 2007-06-21 2008-12-25 Michio Iijima Data management method for accessing data storage area based on characteristic of stored data
US8397014B2 (en) 2008-02-04 2013-03-12 Apple Inc. Memory mapping restore and garbage collection operations
US7886089B2 (en) 2008-02-13 2011-02-08 International Business Machines Corporation Method, system and computer program product for enhanced shared store buffer management scheme for differing buffer sizes with limited resources for optimized performance
WO2009104324A1 (ja) 2008-02-22 2009-08-27 日本電気株式会社 能動計量学習装置、能動計量学習方法およびプログラム
US7735045B1 (en) 2008-03-12 2010-06-08 Xilinx, Inc. Method and apparatus for mapping flip-flop logic onto shift register logic
US8015530B1 (en) 2008-08-05 2011-09-06 Xilinx, Inc. Method of enabling the generation of reset signals in an integrated circuit
US8938590B2 (en) 2008-10-18 2015-01-20 Micron Technology, Inc. Indirect register access method and system
US8209521B2 (en) 2008-10-18 2012-06-26 Micron Technology, Inc. Methods of indirect register access including automatic modification of a directly accessible address register
US7917684B2 (en) 2008-11-05 2011-03-29 Micron Technology, Inc. Bus translator
US7970964B2 (en) 2008-11-05 2011-06-28 Micron Technology, Inc. Methods and systems to accomplish variable width data input
US9639493B2 (en) 2008-11-05 2017-05-02 Micron Technology, Inc. Pattern-recognition processor with results buffer
US8402188B2 (en) 2008-11-10 2013-03-19 Micron Technology, Inc. Methods and systems for devices with a self-selecting bus decoder
US20100118425A1 (en) 2008-11-11 2010-05-13 Menachem Rafaelof Disturbance rejection in a servo control loop using pressure-based disc mode sensor
US9164945B2 (en) 2008-12-01 2015-10-20 Micron Technology, Inc. Devices, systems, and methods to synchronize parallel processing of a single data stream
US10007486B2 (en) 2008-12-01 2018-06-26 Micron Technology, Inc. Systems and methods to enable identification of different data sets
US20100138575A1 (en) 2008-12-01 2010-06-03 Micron Technology, Inc. Devices, systems, and methods to synchronize simultaneous dma parallel processing of a single data stream by multiple devices
US9348784B2 (en) 2008-12-01 2016-05-24 Micron Technology, Inc. Systems and methods for managing endian mode of a device
DE102008060719B4 (de) 2008-12-05 2018-09-20 Siemens Healthcare Gmbh Verfahren zur Steuerung des Aufnahmebetriebs einer Magnetresonanzeinrichtung bei der Aufnahme von Magnetresonanzdaten eines Patienten sowie zugehörige Magnetresonanzeinrichtung
FR2939928B1 (fr) 2008-12-15 2012-08-03 Snecma Standardisation de donnees utilisees pour la surveillance d'un moteur d'aeronef
US8140780B2 (en) 2008-12-31 2012-03-20 Micron Technology, Inc. Systems, methods, and devices for configuring a device
US20100174887A1 (en) 2009-01-07 2010-07-08 Micron Technology Inc. Buses for Pattern-Recognition Processors
US8214672B2 (en) * 2009-01-07 2012-07-03 Micron Technology, Inc. Method and systems for power consumption management of a pattern-recognition processor
US8281395B2 (en) 2009-01-07 2012-10-02 Micron Technology, Inc. Pattern-recognition processor with matching-data reporting module
US8843523B2 (en) 2009-01-12 2014-09-23 Micron Technology, Inc. Devices, systems, and methods for communicating pattern matching results of a parallel pattern search engine
US8146040B1 (en) 2009-06-11 2012-03-27 Xilinx, Inc. Method of evaluating an architecture for an integrated circuit device
US20100325352A1 (en) 2009-06-19 2010-12-23 Ocz Technology Group, Inc. Hierarchically structured mass storage device and method
US9836555B2 (en) 2009-06-26 2017-12-05 Micron Technology, Inc. Methods and devices for saving and/or restoring a state of a pattern-recognition processor
US20110014527A1 (en) 2009-07-17 2011-01-20 Leroy James Ohlsen Polyoxometalate flow-cell power system
US8159900B2 (en) 2009-08-06 2012-04-17 Unisyn Medical Technologies, Inc. Acoustic system quality assurance and testing
US7916510B1 (en) * 2009-08-10 2011-03-29 Netlogic Microsystems, Inc. Reformulating regular expressions into architecture-dependent bit groups
US8489534B2 (en) 2009-12-15 2013-07-16 Paul D. Dlugosch Adaptive content inspection
US9501705B2 (en) 2009-12-15 2016-11-22 Micron Technology, Inc. Methods and apparatuses for reducing power consumption in a pattern recognition processor
US9323994B2 (en) 2009-12-15 2016-04-26 Micron Technology, Inc. Multi-level hierarchical routing matrices for pattern-recognition processors
US20110161620A1 (en) 2009-12-29 2011-06-30 Advanced Micro Devices, Inc. Systems and methods implementing shared page tables for sharing memory resources managed by a main operating system with accelerator devices
US20110208900A1 (en) 2010-02-23 2011-08-25 Ocz Technology Group, Inc. Methods and systems utilizing nonvolatile memory in a computer system main memory
GB2478727B (en) 2010-03-15 2013-07-17 Advanced Risc Mach Ltd Translation table control
US8601013B2 (en) * 2010-06-10 2013-12-03 Micron Technology, Inc. Analyzing data using a hierarchical structure
US8766666B2 (en) * 2010-06-10 2014-07-01 Micron Technology, Inc. Programmable device, hierarchical parallel machines, and methods for providing state information
US9195623B2 (en) 2010-06-23 2015-11-24 International Business Machines Corporation Multiple address spaces per adapter with address translation
US8294490B1 (en) 2010-10-01 2012-10-23 Xilinx, Inc. Integrated circuit and method of asynchronously routing data in an integrated circuit
WO2012103151A2 (en) * 2011-01-25 2012-08-02 Micron Technology, Inc. State grouping for element utilization
CN103547998B (zh) * 2011-01-25 2016-11-09 美光科技公司 用于编译正则表达式的方法和设备
EP2668574B1 (en) * 2011-01-25 2021-11-24 Micron Technology, INC. Utilizing special purpose elements to implement a fsm
KR101607736B1 (ko) * 2011-01-25 2016-03-30 마이크론 테크놀로지, 인크. 오토마톤의 진입 차수 및/또는 진출 차수를 제어하기 위한 양화 언롤링
US8659415B2 (en) 2011-07-15 2014-02-25 General Electric Company Alarm management
US8648621B2 (en) 2011-12-15 2014-02-11 Micron Technology, Inc. Counter operation in a state machine lattice
US8680888B2 (en) 2011-12-15 2014-03-25 Micron Technologies, Inc. Methods and systems for routing in a state machine
US8593175B2 (en) 2011-12-15 2013-11-26 Micron Technology, Inc. Boolean logic in a state machine lattice
US9443156B2 (en) 2011-12-15 2016-09-13 Micron Technology, Inc. Methods and systems for data analysis in a state machine
US8782624B2 (en) 2011-12-15 2014-07-15 Micron Technology, Inc. Methods and systems for detection in a state machine
US20130275709A1 (en) 2012-04-12 2013-10-17 Micron Technology, Inc. Methods for reading data from a storage buffer including delaying activation of a column select
US8536896B1 (en) 2012-05-31 2013-09-17 Xilinx, Inc. Programmable interconnect element and method of implementing a programmable interconnect element
US9304968B2 (en) 2012-07-18 2016-04-05 Micron Technology, Inc. Methods and devices for programming a state machine engine
US9235798B2 (en) 2012-07-18 2016-01-12 Micron Technology, Inc. Methods and systems for handling data received by a state machine engine
US9524248B2 (en) 2012-07-18 2016-12-20 Micron Technology, Inc. Memory management for a hierarchical memory system
US9063532B2 (en) 2012-08-31 2015-06-23 Micron Technology, Inc. Instruction insertion in state machine engines
US9501131B2 (en) 2012-08-31 2016-11-22 Micron Technology, Inc. Methods and systems for power management in a pattern recognition processing system
US9075428B2 (en) 2012-08-31 2015-07-07 Micron Technology, Inc. Results generation for state machine engines
KR102029055B1 (ko) 2013-02-08 2019-10-07 삼성전자주식회사 고차원 데이터의 시각화 방법 및 장치
US9448965B2 (en) 2013-03-15 2016-09-20 Micron Technology, Inc. Receiving data streams in parallel and providing a first portion of data to a first state machine engine and a second portion to a second state machine

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5784298A (en) * 1993-10-15 1998-07-21 International Business Machines Corporation Apparatus and method for using finite state machines (FSMs) to monitor a serial data stream for characteristic patterns
TW200422860A (en) * 2002-12-10 2004-11-01 Ibm Apparatus and methods for co-location and offloading of web site traffic based on traffic pattern recognition
US20070127482A1 (en) * 2005-02-12 2007-06-07 Curtis L. Harris General Purpose Set Theoretic Processor

Also Published As

Publication number Publication date
CN106919959A (zh) 2017-07-04
US20220100700A1 (en) 2022-03-31
US20160239462A1 (en) 2016-08-18
EP2513839A2 (en) 2012-10-24
KR101960101B1 (ko) 2019-03-19
JP5753190B2 (ja) 2015-07-22
US10684983B2 (en) 2020-06-16
US11226926B2 (en) 2022-01-18
US9323994B2 (en) 2016-04-26
US20240012787A1 (en) 2024-01-11
US20110145544A1 (en) 2011-06-16
CN106919959B (zh) 2021-07-02
TW201131404A (en) 2011-09-16
KR20120108987A (ko) 2012-10-05
US11768798B2 (en) 2023-09-26
WO2011081799A2 (en) 2011-07-07
US20250165429A1 (en) 2025-05-22
EP2513839B1 (en) 2020-02-26
US20200285604A1 (en) 2020-09-10
WO2011081799A3 (en) 2011-09-01
JP2013513894A (ja) 2013-04-22
CN102713936A (zh) 2012-10-03

Similar Documents

Publication Publication Date Title
TWI479342B (zh) 用於型樣辨識處理器之多階層式路由矩陣
TWI488108B (zh) 用以同步一單一資料串流之平行處理的裝置、系統及方法
TWI465945B (zh) 用於型樣辨識處理器中降低電力消耗之方法及裝置
TWI416332B (zh) 藉由多個裝置同步化單一資料串流之同時直接記憶體存取平行處理之裝置、系統及方法
TWI507977B (zh) 啟用不同資料集之識別之系統及方法
TWI414998B (zh) 型樣辨識處理器之電力消耗管理之方法及系統
TWI419002B (zh) 具有資料匹配報告模組之型樣辨識處理器
TWI590059B (zh) 用於型樣辨識處理器之匯流排
TWI436271B (zh) 具有結果緩衝器之型樣辨識處理器
TWI409695B (zh) 用於配置裝置之系統、方法及裝置
TWI524203B (zh) 用於保存及／或復原圖型辨識處理器之狀態之方法及裝置