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

d04scarp_p4ds 2/13/08 11:47 AM Page 23 Perforce of text at the same time. Consequently, they can share a single program control structure. This is a great advantage. We can fuse multiple DFAs in single, long basic blocks, which are crucial for performance on SPEs—they mitigate branch overhead and give the compiler enough elbow room during instruction scheduling. This results in reduced stalls, hiding of load/store latencies, better dual pipeline exploitation, and lower clock Cycles Per Instruction (CPI) values. The Cell is so different from traditional processors that you can’t get the best out of it unless your code explicitly takes advantage of its hardware Fast Software Configuration Management Our Fast Solution The smaller the dictionary, the smaller the corresponding State Transition Table (STT). If the STT is small enough, we can keep it entirely in the local store rather than in main memory. This speeds up the algorithm because main memory accesses are slow. Our fast implementation is based on the simple idea of keeping the STT in the local store. As we anticipated, a single automaton poorly utilizes the SPE hardware. Its implementation uses only four registers out of the 127 available, and no SIMD instructions. Moreover, an SPE has two pipelines and could issue two instructions at the same time if they do not conflict, but this implementation does not exploit this feature. As a result, the CPI is high (2.6) and throughput is low (1.35 Gbps). But if we fuse together 16 automata, things improve a lot, because with SIMD instructions our code can process data from four automata at the same time. This implementation better exploits the registers (40 out of 127) and the two pipelines (43.8 percent of the issues are dual), reaching a CPI of 0.67. This is a big improvement, but the code still stalls 7.4 percent of the cycles. To get rid of these stalls, we unroll the code manually, creating longer basic blocks. This gives the compiler more freedom to reschedule instruc- 200,000 developers rely on Perforce to manage their code. Here’s what they’re saying “Perforce is absolutely the only tool I would trust to manage our source code.” tions and fill the stalls. We found experimentally that the best conditions happen when we unroll the main loop three times. The resulting code uses almost all the registers (124 out of 127) without spilling, it has a high dual-issue rate, and no stalls. This leads to a remarkable throughput of 5.11 Gbps. Loading text from memory is not in the way: We adopt a double buffering scheme to load the next chunk while the current one is processed. This completely hides the load latency, because transfers happen asynchronously and take less time than processing. In fact, loading a 16-KB text chunk takes 5.94 microseconds, whereas processing it takes 25.64 microseconds. All this happens on a single SPE. To unleash all of the Cell’s power, the remaining seven SPEs can be put to work, too. We can do this in two ways: • When they operate in parallel, all the SPEs have identical STTs, but they Nick Triantos NVIDIA “Perforce has been a breath of fresh air; a product which does what it's supposed to do and does it well.” Scott Buchholz Sybase “Perforce is the cornerstone of Monster’s software production lines.” Mark Conway Monster Worldwide “The bottom line is that Perforce has proven itself to be a reliable platform for global development at Symantec.” Russell Jackson Symantec See for yourself Free evaluation at www.perforce.com Figure 2: Processing power and memory subsystem. April 2008 l www.ddj.com l Dr. Dobb’s Journal 23 http://www.perforce.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.