Email	Print Reprint
	add to:
	Del.icio.us Digg Google Spurl	Slashdot Y! MyWeb Blink Furl
	TABLE OF CONTENTS String Searching Programming the Cell: Rethinking Bottom-Up Why Aho-Corasick and the Cell Make a Good Match The Heavy-Duty Solution

While your current PC may be dual- or quad-core, the one sitting on your desk in a couple of years will be a "many-core." Multicores are the future, and because programming them is so different than programming for traditional processors, you must prepare for the change now, especially in mapping basic algorithms efficiently onto the new hardware.

String searching is one of these basic algorithms. It has a host of applications, including search engines, network intrusion detection, virus scanners, spam filters, and DNA analysis, among others. The Cell processor, with its multiple cores, promises to speed-up string searching a lot.

In this article, we show how we mapped string searching efficiently on the Cell. We present two implementations:

• The fast implementation supports a small dictionary size (approximately 100 patterns) and provides a throughput of 40 Gbps, which is 100 times faster than reference implementations on x86 architectures.
• The heavy-duty implementation is slower (3.3-4.3 Gbps), but supports dictionaries with tens of thousands of strings.

This task is not trivial. We had to change our algorithm significantly to reach top performance. In particular, to exploit the memory subsystem at its best, we employ a pipelined parallelization strategy, and we shuffle the data layout to fight congestion—techniques that are unfamiliar to most programmers of traditional architectures. The source code that implements the techniques we present here is available electronically; see www.ddj.com/code/.

Why Is String Searching So Important?

The Internet is a dirty place, with malware, spyware, spam, and viruses trying to penetrate your systems through all possible vulnerabilities. Undesired traffic cannot be filtered anymore on the basis of header information. What's needed is"deep-packet inspection, which checks the payload against a database containing signatures of a large number of threats.

But with network links getting faster (10 Gbps Ethernet, for instance), performing on-the-fly deep-packet inspection isn't child's play. For example, running the Snort (www.snort.org) intrusion-detection system on a Pentium 4 PC only ensures a filtering throughput between 200-400 Mbps. This is why network appliance manufacturers often employ specialized hardware like Field-Programmable Gate Arrays (FPGAs) or Application-Specific Instruction Processors (ASIPs). The Cell processor is a new player in this field, with the potential to offer lots of computing power at low price. In fact, its large production volumes (it's used in the Sony PlayStation 3) contribute to keeping its price low.

1 String Searching | 2 Programming the Cell: Rethinking Bottom-Up | 3 Why Aho-Corasick and the Cell Make a Good Match | 4 The Heavy-Duty Solution Next Page

RELATED ARTICLES Climate Researchers Get New 76-Teraflop Supercomputer Game Solves Puzzles for Science MySpace Opens up Profile Data Winners of the 18th Jolt Product Excellence Awards & Recipients of the Jolt Productivity Awards Performance Portable C++		TOP 5 ARTICLES CUDA, Supercomputing for the Masses: Part 1 CUDA, Supercomputing for the Masses: Part 2 Scaling Scrum There Must be Contest Performance Portable C++