Dr. Dobb's Journal - April 2008 - (Page 27)

d04scarp_p4ds 2/13/08 11:49 AM Page 27 We designed a first implementation respecting these ideal conditions, and evaluated it in four scenarios: full-text search, network content monitoring, network intrusion detection, and virus scanning (see Figure 4). To our disappointment, performance was largely below the theoretical bound (the curve in red in the figure) and scalability was poor. This degradation is due to congestion in the memory subsystem, caused by a nonuniform state hit distribution. In fact, a tiny percentage of the states are responsible for the last majority of the hits. For example, the states immediately reachable from the initial state are between 0.1–0.5 percent of all the states, but they receive between 46.8–89.8 percent of all hits. Concurrent accesses to the same or adjacent states by multiple automata cause hot spots in the memory subsystem, which show up as longer gaps and lower throughput. To fight congestion, we employ a combination of state caching, replication, and shuffling. First, we cache in the LS those states that are closest to the initial one, thus completely avoiding memory access for the states that are accessed most frequently. Given the limited size of the LS, we can cache only 180 states out of the 50,000 of the examples considered. Then we shuffle the states by randomly renumbering them. This redistributes hot spots among the memory banks, ensuring that all of them are subject to the same pressure, but it does not relieve the impact of each single hot spot. For that, we replicate the most frequently hit of the noncached states, such that different automata access different replica of the same STT entry. This way, each replica receives only a fraction of the accesses of the original state. As a draw- back, replication causes the STT to grow from approximately 50 to 800 MB. But these optimizations only solve half of the problem. In fact, if you see the STT as a row/column table, where each row corresponds to a state and each column to an input character, the above optimizations balance pressure only on the rows but not on the columns. Pressure on the columns is unbalanced, especially with English text patterns, because most hits fall on lowercase a–z characters, while almost none fall on characters 128–255. To counter this unbalance, we also shuffle the alphabet space. The offsets at which next states are written in an STT entry are hashed, with a hash function that depends on the stat number, too. With these optimizations, the aggregate throughput reaches 3.3–4.3 Gbps depending on the scenario (see Figure 5). This suggests that a system composed of three double-Cell blades, each with 1 GB of RAM, can be employed to match traffic at 10 Gbps, against a dictionary comprising at least 5000–25,000 patterns with an average length of 16 bytes. DDJ Figure 5: Aggregate throughput. April 2008 l www.ddj.com l Dr. Dobb’s Journal 27 http://www.programmingresearch.com http://www.programmingresearch.com http://www.ddj.com

Table of Contents Feed for the Digital Edition of Dr. Dobb's Journal - April 2008

Dr. Dobb's Journal - April 2008 Contents Hmmmm Alia Vox Developer Diaries Dr. Dobb's Excellence in Programming Award Conversations Fast String Search on Multicore Processors The Byzantine Generals Problem Optimizing Math-Intensive Applications with Fixed-Point Arithmetic Random Numbers in a Range Using Generic Programming The Agile Edge Effective Concurrency Swaine's Flames

Dr. Dobb's Journal - April 2008

For optimal viewing of this digital publication, please enable JavaScript and then refresh the page. If you would like to try to load the digital publication without using Flash Player detection, please click here.