Slideshow Title

Slideshow Title SSE and Conway's Game of Life By Mike Lewis Outline (for 5 minutes)

What's SSE(2)
Making GCC use SSE via intrinsics
Conway's game of Life
Basic Optimizations

Inlining
Avoiding branching
Reducing memory bandwidth

Not-so-basic bit packing

Super quick demo

What is SSE?

"Streaming SIMD Extensions"
Math with 128 bit XMM registers
SSE==FP math
SSE2==Integer math (as well as double precision FP)
lots of math at once

16 byte math operations at once!

Lots more too
AltiVec is comparable

How to get GCC to generate SSE2 instructions

it may automatically vectorize some loops by default depending on your system and code
Optimizing by hand is generally faster


#include <emmintrin.h>

IA-32 programmer's handbook is friend Conway's game of life Blah Inlining static inline func( void ) { asdf } put in header if you're going to use a lot
usually better than macros Minimizing memory bandwidth

Number of cores growing almost exponentially
Memory bandwidth and FSB speeds are not

Solutions (in Life at least):

bit pack data and make the processor do a bit more work.
Align memory oncache lines
Use explicit aligned loads

not-so-basic bit packing

Not enough time to get into this.
Packs and unpacks in 3 instructions.

static inline __m128i unpack( __m128i A, int row ) {
    const __m128i onemask = _mm_set1_epi8( 0x01 );
    __m128i shift = _mm_srli_epi32( A, row );
    return _mm_and_si128( shift, onemask );
}

// MAKE SURE A IS IN THE FORM (0xFF) not (0x01
// ( a | mask ) | ( ~mask & b )
static inline __m128i pack( __m128i A, int row ) {
    const __m128i onemask = _mm_set1_epi8( 0x01 );
    A = _mm_and_si128( onemask, A );
    return _mm_slli_epi32(A, row);
}

Stop! It's demo time I can has optimizations?

trac for life: trac.lolrus.org/life
best optimization guides in existance: http://www.agner.org/optimize/