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

d04scarp_p4ds 2/13/08 11:48 AM Page 24 Core Technology STRING SEARCH ON MULTICORE PROCESSORS process distinct chunks of input text. This multiplies the combined throughput by 8, which is 40 Gbps. • Alternatively, we can put SPEs “in series.” The SPEs are all given the same chunk of input text, but they employ distinct STTs. Each SPE has an STT that represents a portion of the initial dictionary. This way, the available dictionary capacity is multiplied by a factor of 8. Thanks to the regularity of the DFA and absence of variable-latency operations, the throughput values reported above are independent from the input. This is highly desired in security applications, because it means immunity to content-based attacks. The main drawback is that the STT must be small enough to fit the local store. Ranging between 190–214 KB in size, each STT will contain between 1520 and 1712 states, assuming an alphabet of 32 characters. Such an STT may encode dictionaries of approximately 150 strings, of average length 10 (more, if many prefixes are common). The Heavy-Duty Solution The aforementioned solution is fast but lacks capacity. Even in the series configuration, it won’t support a dictionary larger than 1200 patterns. Additionally, it supports only 32 input symbols, which practically limits us to case-insensitive English text matching only. Instead, popular rule sets available for Snort comprise about 5000 rules, including both text and binary patterns, with a larger average length than 10 characters. And because the bad guys keep themselves busy, this rule set is expected to grow in the future. Because a solution with more dictionary capacity is needed, we move the STT to a roomier place—main memory. There is a drawback—accessing the STT costs more because each state transition requires a DMA transfer. We can still cache some frequently hit states in the LS, but optimization efforts need to focus on accessing the main memory, where the majority of the STT resides. We must rethink the algorithm “bottom-up” around this goal—making DMA accesses as fast as possible. Automata spend their lives performing state transitions. This breaks down into two phases: • Computation. Determining the address of the next state in the STT, depending on current state and input. • Data-transfer. Getting data from that address. Because the STT is now in main memory, the data transfer takes much more than computation—13 nanoseconds to compute and 250 to transfer. Again, a single automaton yields poor utilization of both the processing power and memory subsystem (see Figure 2). And again, we employ multiple automata to improve this. In our code, we statically schedule these automata to run cyclically. The first automaton waits for its transfer to complete, computes the transition, and starts the next data transfer. The second automaton does the same. Then the third, fourth, and so on, up to the last one. At this 24 Dr. Dobb’s Journal l www.ddj.com l April 2008 http://www.codejock.com http://www.codejock.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.