2011年12月7日 星期三

motivation 12/8

motivation
在發表過的幾篇將simple pattern實作在TCAM的paper中,
是根據TCAM的特性:
1. ternary,也就是可以用*的表示
2. 架構中(使用TCAM以及SRAM),讓有相同input character以及destination state的state可以盡量用*合併在一起,以達到使用更少的TCAM entry。
最後,使用TCAM就會衍生出對state assign ternary code的問題。

使用TCAM另一個目標也是要減少TCAM的entry數,降低power consumption
多數的paper都是藉由第2點的特性,讓TCAM entry可以represent多個不同states由同樣的input character到達destination state
另外在cool-CAM這篇paper,雖然是做ip lookup,提到可藉由分group的方法,降低TCAM的power consumption。

在D2FA中,
本來作者的想法是透過default transition,解決DFA的memory comsunmption問題,
實際上,會建立出default transition的原因是在:
找出2個或是多個states之間,大部份的transition是相同的,讓其中一個state來"代表"其他的state,進而取代其他state的transition,而其他state就會多出default transtion到可"代表"的state。
但d2fa使得memory access的次數增加,在基本的二維的transition table,也是依然要用symbol表示default transition存在,

綜合以上的觀點,
1.找出states可以default到的state(原D2FA paper稱之為 root of the default transition tree)
2.找到多個default root,所以可藉由這樣的方法分group,
3.各個group之中,可由default root取代group之間的transition,也就是會有TCAM的第2個特性,
3.a 在group之中,大部份的states其實也是擁有同樣的transition,
一樣可以用第2個特性來進一步的減少TCAM entry
4.可減少d2fa的memory access次數到與DFA相同的 1 per every input character。