亚洲av成人无遮挡网站在线观看,少妇性bbb搡bbb爽爽爽,亚洲av日韩精品久久久久久,兔费看少妇性l交大片免费,无码少妇一区二区三区

Chinaunix

標題: 想實現(xiàn)硬件regex匹配 [打印本頁]

作者: cjaizss 時間: 2008-08-11 17:21
標題: 想實現(xiàn)硬件regex匹配
想用在項目里，作為將來擴展的設計。不過確實有點困難，無論怎么搞，試試看吧。

作者: wuchuanren 時間: 2008-08-11 18:16
沙發(fā)一下……
對偶來說軟件實現(xiàn)一個NFA都沒感去想
支持

作者: cjaizss 時間: 2008-08-12 15:41
確實有難度，因為我需要運算的盡量快。暫時不想去接受所有的regex,而是只去處理DFA限定在一定范圍內(nèi)regex。
不過這也還是先等硬件架構(gòu)設計完之后再考慮了，呵呵

作者: cjaizss 時間: 2008-08-13 12:56
為了快速匹配以及避免難度，我的思路是準備構(gòu)造一個狀態(tài)機的架子，然后把regex等價的狀態(tài)機往這個架子里填。只要regex的狀態(tài)機的規(guī)模不超過我設置的這個規(guī)模（其實我設置的這個規(guī)模也不會是很大的，一個很簡單的regex的狀態(tài)機就會很夸張了），那么我就可以填進去

作者: freearth 時間: 2008-08-13 13:21
個人覺得可以這樣考慮：
不要試圖一次提供一個完整的DFA，這樣很難確定應該有多少個狀態(tài)。狀態(tài)少的話可能會限制很多應用。

建議采用另外一種思路：設計一套包含十幾條指令的專用指令系統(tǒng)，將狀態(tài)編號以整數(shù)的形式存在主存中（當然，運行時在cache中，速度還是夠的）。這樣設計也許對于很小的DFA而言，不如直接用硬件實現(xiàn)快，但是這樣更加靈活，應用面更廣，幾乎可以應用所有的DFA。

這個設計的關鍵部分就是指令系統(tǒng)怎么設計。
這個指令系統(tǒng)至少要包含構(gòu)造正則表達式的幾個常用的操作。
1、原子表達式。
2、連接、選擇、重復

一、原子表達式可以這樣設計
   match arg
   其中arg是一個字母或者數(shù)字，該指令表示匹配這個字母或數(shù)字

二、連接
   con addr1, addr2
   首先執(zhí)行addr1中的指令，再執(zhí)行addr2中的指令。addr1和addr2中是另外兩個正則表達式匹配代碼
   選擇和重復的實現(xiàn)類似

三、輔助操作
   ldr rbase，arg
   rbase寄存器存放待匹配的字符串的首地址，字符串以0結(jié)束

   begin rend, addr2
   使用addr2中的指令進行匹配字符串，將匹配到的字符串的最后一個字符的下一個地址放到寄存器rend中

   end
   標志一個指令序列的結(jié)束

等等。

上面的東西只是提供一個思路，具體設計還要更加仔細的考慮。
另外，樓主的“項目”具體是什么？

原帖由 cjaizss 于 2008-8-13 12:56 發(fā)表
為了快速匹配以及避免難度，我的思路是準備構(gòu)造一個狀態(tài)機的架子，然后把regex等價的狀態(tài)機往這個架子里填。只要regex的狀態(tài)機的規(guī)模不超過我設置的這個規(guī)模（其實我設置的這個規(guī)模也不會是很大的，一個很簡單的 ...

作者: cjaizss 時間: 2008-08-13 14:09
標題: 回復 #5 freearth 的帖子
這個方法不符合我想追求高速度處理的目標，肯定不會采用。
我要做的是一個硬件平臺，用于網(wǎng)絡設備。
一個clock的節(jié)省帶來的收益也是可觀的。
如果引入指令集，我還不如用CPU

作者: ArsenalSrch 時間: 2011-12-15 20:38
對這個話題很感興趣，不知道樓主有進展否

歡迎光臨 Chinaunix (http://72891.cn/)