Parallelism: Single-Instruction-Multiple-Data (SIMD) and SSE

• "Pipelining" is just a way to break up a long series of tasks into smaller pieces that can be executed simultaneously.  Machines have been pipelined since the 386.
  
• "Superscalar" machines use fancy lookahead and scheduling algorithms to try to execute several instructions in parallel.  All modern machines since about the Pentium era are superscalar.
• "Out-of-order" machines will actually analyze dependencies and execute instructions that have their data available before previous instructions have even finished.  The Pentium II and subsequent machine execute out-of-order.
• "Load buffers" and "store buffers" allow memory reads and writes to proceed simultaneously with other processing.  The Pentium 4 has a 24-entry store buffer, which means the processor can have 24 store instructions "in flight" at once!

for (int i=0;i<n_vals;i++) { 
        vals[i]=vals[i]*a+b;
}

for all i simultaneously
	vals[i]=vals[i]*a+b;

for (int i=1;i<n_vals;i++) { 
        vals[i]=vals[i-1]*a+b;
}

• The problems we want to solve often (but not always) have an obvious, trivially parallel structure.
• The code we write to solve the problem is written using the inherently sequential, one-thing-after-another model of all assembly language, C, C++, Java, etc.
• The machine we run the code on then goes to great lengths to rediscover the original parallelism, and hence execute our sequential code in parallel.
  

• People that write "parallelizing compilers" (e.g., OpenMP) either automatically recognize "parallel loops" or allow you to provide hints in your source code as to which loops can be parallelized.  These attempts are somewhat hamstrung by the fact that they're still based on inherently sequential languages, which prevents many of the kind of transformations you want to make for performance (e.g., load balancing).
  
• People that write "parallel languages" (e.g., Parallel Prolog) attempt to describe the entire problem in an inherently parallel way.  This is really tough for people to do, and usually isn't a good match to modern sequential-centric machines.
• People have added "parallel arithmetic" to virtually all modern hardware.  This is a low-benefit but low-cost way to capture more parallelism.

SIMD: Parallel Arithmetic

• Up to a 4x speedup over normal sequential code.  Note that 4 32-bit floats is 128 bits, so you can impress people by saying you've got a "128-bit machine", which is true in some sense.
  
• 4 elements is perfect for doing calculations on colors (Red-Green-Blue-Alpha), 3D locations (XYZW), or 4-channel stereo.
  
• Easy to implement in hardware, because the hardware doesn't have to *recognize* all 4 operations are independent, it's just *told* they are.

• The "4" is hardcoded into the hardware and source code.  For higher levels of parallelism, you're back to pipelining and chasing dependencies.
  
• Sometimes it's tricky to get exactly 4 copies of what you need--sometimes you need to add extra padding.
  

• x86: SSE, SSE2, SSE3.  "MMX" is the integer version.
• PowerPC: AltiVec
• Cell Processor
• All graphics cards (see next lecture)
  

x86 SSE Interface

• GCC 3.x under linux.  Be sure to compile with "-msse", or the header will whine.
  
• Visual C++ 7.0 under Windows.
  
• Intel C/C++ compiler under Linux or Windows. Makes bogus complaint about "no EMMS instruction before return", although the annoying emms() call is thankfully only needed with MMX, not SSE.
  

	__m128 va=_mm_load_ps1(&a); /* va contains 4 copies of a */
	__m128 vb=_mm_load_ps1(&b); /* vb contains 4 copies of b */
	for (int i=0;i<n_vals;i+=4) { /* careful!  n_vals must be multiple of 4! */
		__m128 v=_mm_load_ps(&vals[i]); /* careful about alignment! */
		v=_mm_mul_ps(v,va);
		v=_mm_add_ps(v,vb);
		_mm_store_ps(&vals[i],v);
	}