Programming Lab #4

Cardiac Electrophysiology Simulation

with SSE Vector Intrinsics

Changelog

Contents

• The provided starter code
• Vectorizing your code
• Testing your code
• Assignment Checklist
• Turning in your assignment
• Grading
• SSE Documentation
• Frequently asked questions

Part 0. The Assignment

In this assignment you'll re-implement the heart electrophysiology simulator from Assignment #3 using SSE intrinsics, and conduct experiments on Bang to assess performance. The assignment includes a brief report, and the requirements for your report are described at the end of this writeup.

Your grade will based on 4 factors: performance attained by your implementation; correctness; well-displayed results; descriptive comments in the code and in your repository.

In the spirit of friendly competition, post your performance results to the HW4 Piazza folder.

☞ Due Friday3/4/16 @ 9PM

‣ ‣ ‣ Required solution files: solve.cpp helper.cpp

This means that these files, containing your solution to the assignment, must be turned in by the deadline.

You may develop your code anywhere, but you must ensure that it compiles and runs correctly on Bang because that’s where we’ll be testing it.

The background for the cardiac simulator is the same as for Assignment #3

In doing this assignment, it's your responsibility to understand the course rules for integrity of scholarship.

Part 1. Getting Started with GitLab

All assignments will be turned in using UCSD's GitLab. The turnin procedure is described below in the section "Turning in your assignment". You must follow these steps to get the starter code and to get set up to do assignment 4.

Refer to the link below for instructions on how to obtain the starter code to get started on your assignment

A4 Git Instructions

We've provided you with starter code that implements the Aliev-Panfilov solver as well as an executable so that you may assess performance with a known reference. The provided starter source code is virtually identical to that of the previous assignment, but there are some new instructions, so be sure to look them over. The binary reference is new, since it has been vectorized with SSE intrinsics. You can find this reference in $PUB/HW/A4/apf-sse-ref on Bang. It may be possible to improve on the performance of the reference, since it doesn't include any significant optimizations to conserve memory locality.

All of your changes will made to just two files:

solve.cpp       helper.cpp

Solve.cpp contains the solver, helper.cpp provides various helper functions such as storage allocation. (You may therefore change the storage allocation scheme if you wish.) The solver is computationally intensive, and so the focus of vectorization and performance programming effort will be on this routine.

The code and Makefile have been set up to enable you to compile with or without the flags needed to support SSE vector intrinsics. The default is to compile without the intrinsics. To compile with intrinsics, specify following make command line argument to Make:

vec=1 

This setting defines the SSE_VEC macro which you can use to enable selected code to be conditionally compiled. To take advantage of this feature in any code you write, follow the convention used in the provided starter code. (The code also prints out a message tell ling you when you are building code with SSE intrinsics).

As with the previous assignments, build your code using the provided Makefile, which sets the appropriate flags for the compiler via the "arch" file located in $(PUB)/Arch/arch.gnu-c++11.generic. The Makefile produces a target called apf. Do not change the name of this target. While you may modify any files not listed above, remember that we will substitute fresh copies when we grade your assignment, so don't really on any custom changes as they will be lost during the grading process.

We have also provided one batch script, batch_job.sh. This script runs the serial provided code., and you'll need to modify it to run your multithreaded code.

The simulator has various options, controlled via command line arguments (parsed in in cmdLine.cpp), with default values set in apf.cpp. These are the same as in the previous assignment, however, the -t option is not used.

Part 3. Vectorizing your code

Use the SSE intrinsics discussed in class to nearly double the speed of your code. Note that, the compiler will attempt to vectorize certain code and will succeed in this endeavor, as the optimization is enabled by -O3. However, the quality of the generated code won't match that obtained via hand vectorization with SSE intrinsics.

Although several loops in solver.cpp are amenable to optimization, you should ignore loops that consume insignificant amounts of the application's running time such as initialization. Focus on the remaining code. Your efforts will be much more rewarding if you focus on the PDE and ODE code. Vectorize these two parts one at a time. We have set up a simple vectorization example to help get you started. The code resides in $PUB/Examples/SSE/Vec. However, in the example code the stencils are one dimensional and there are no alignment issues. In the PDE and ODE loops, you'll have two dimensional stencils and array strides are not integral powers of two in length.

Your code will be tested for correctness and performance against various combinations of the N and niter. Note that for this assignment, N will always be an odd even number; the provided reference will get a Segmentation Fault on even odd numbers. This is due to how vectorization is handled on the Bang's Clovertown processor. Verify that results are independent of whether or not the code was vectorized, for various (legal) values of N. While you can catch some obvious errors using the graphical output (as in the previous assignment) a more precise test is to compare two summary quantities reported by the simulator: the L₂ norm and the L_∞ norm, the maximum value (magnitude) of the excitation variable, which are included in the 1 line of performance output. These are described in the the Testing part of the writeup for A3.

Part 5. Assignment Checklist

1. Vectorize your code using the SSE intrinsics. to obtain a performance improvement of about 60% for an input size of N=256. As you increase N, this performance improvement will shrink. We will use this public test case to validate your code's performance, as well as tests that won't be made public.
   Remember: N must be an even number.


2. Try to make the code go as fast as you can. There may be other ways of improving performance of your code, that optimize for memory locality, especially for large values of N (a few thousand)

   We will award 10% extra credit if you can run 15% or more faster than the provided reference binary.

3. Report and comment on your results. The general requirements for the document are described in §6.2.
   
   1. Plot the performance benefit of your code compared to the provided starter code, over the range of N=128 to N=1024. Adjust the number of iterations so that your runs last just a few seconds. For N=1024, a reasonable number of iterations (-i) is about 20, for N=128, several thousand. The work scales quadratically with N).
      
   2. Report any performance anomalies or outstanding issues in your code. Negative results can be a valuable means of learning, so we are giving you an incentive to explore this venue. We will provide some partial credit for test cases your code doesn't pass, if we receive a carefully documented description. What we are looking for is a discussion that offers insight into program errors or performance bottlenecks that prevented you from collecting all your data or that resulted in lower than expected performance.

Part 6. Turning in your assignment

6.1 Submission via GitLab

This procedure is the same as the previous assignment and is reproduced here:

Git Lab Submission

1. A PDF document that presents all requested performance data along with any addendum explaining negative results. Use the same format as in the previous assignments, e.g. A3-report-baden-powell.pdf. This report is worth 20% of your grade.

   Provide all data in both tabular and graphical form. Plot your data carefully, plotting only what's necessary to get your points across, and choosing log and linear plots carefully. Be sure to provide a caption for each table or plot that describes the experiment you conducted, e.g. "strong scaling."

   We encourage you to report negative results which are also valid especially valued if you can document them, with the underlying causes, or best guesses if the causes are not clear. So if results weren't as you expected, let us know why and we may be able to give you some partial credit. Include this discussion on the PDF containing your results.

2. Source code. Even though we will be substituting fresh copies of all but one source module, include all code files your worked with, in case we need to unravel a problem with your turnin. This could happen because you made changes to one of the files that we replaced. Also include your Makefile.
3. Team evaluation. Your turnin must must also contain a team evaluation, the file teameval.txt. This document must be filled in completely. If you don't turn in it in, your assignment will be considered late. (Minimum 10% lateness penalty).

There are 25 possible points on the assignment and your grade will depend on 4 factors: performance attained by your code, correctness, well-displayed results (including an explanation if you have negative results) and comments. You must not only put comments inside your code, but every time you commit to your repository. There should be a steady stream of comments that enable us to retrace your development steps. Your performance score will be based on the ability to scale strongly.

We will grade your code on Bang using our own Makefile with the same compilation flags as in the provided in starter code. To get full credit, design, style and comments (including gitlab commit comments) count.

SSE Documentation

• Intrinsics Guide This is a handy "cheat sheet," a complete reference to all SIMD intrinsics on Intel Architectures which you can filter by type, SSE version number. Bang supports SSE, SSE2 and SSE3 instruction sets but most of what you need is in SSE2.


• SSE Intrinsics Tutorial


• How to Write Fast Code SIMD Vectorization, Markus Püschel, CMU (2008). This presentation gives you a nice overview.


• SSE2 Preview, and MMX Primer, by Stefano Tommesani. (Many writeups on SSE accessible from this page.)


• x86 Assembly Wiki: https://en.wikibooks.org/wiki/X86_Assembly New


• Introduction to x64 Assembly (Intel, 2012) New


• Intel publishes complete reference guides and manuals. Save a tree and preview these electronically.
  • Intel 64 and IA-32 Architectures Software Developer Manuals
  • Intel Architecture Instruction Set Extensions Programming Reference, October 2014. This manual specifies the details behavior of machine instructions.


• An Introduction to GCC Compiler Intrinsics in Vector Processing, by George Koharchik and Kathy Jones, Linux Journal, Sep 21, 2012.


• SSE load/store memory transactions New
• Handling nearest neighbor values New


• Motion Estimation with Intel Streaming SIMD Extensions 4


• The Architecture of the Nehalem Processor Nehalem-EP SMP Platforms. This processor is newer than Bang’s CPUs, but most of the SSE discussions are relevant.


• GCC documentation - We are using GCC 4.8 on Bang, but this page documents older versions too. Look at the section entitled "Intel 386 and AMD x86-64 Options," especially the optimizations concerning SSE.

• Wikipedia entries on Vectorization and Streaming SIMD Extensions

• Automatic Intra-Register Vectorization for the Intel Architecture, A. Bik et al., Int. J. of Parallel Programming, 30(2):65-98 (2002). DOI (Required a UCSD network login)

SSE and Floating Point math New

• How to optimally do floating point arithmetic?
• What is going wrong when you do floating point math with SSE with respect to correctness? (How to minimize round-off errors?):
  • software.intel.com/en-us/articles/consistency-of-floating-point-results-using-the-intel-compiler
  • software.intel.com/en-us/articles/differences-in-floating-point-arithmetic-between-intel-xeon-processors-and-the-intel-xeon

To read further about other optimizations

• Optimizing Software in C++, Agner Fog, §12: pp 105-113 (skip §12.1, §12.2), 117-118, 122-123
• HPC Mac OS X. How to obtain software and documentation

Q. How can I use the statistics output (L2 and Linfo) to help me debug my code?

A. Your first step after partitioning the data structures and setting up the initial conditions is to make sure you get the statistics reporting to work, so that you will have diagnostic tests enabling you to compare your code with the provided reference. Having done this, you can test that you've set up the initial conditions correctly, and that your solver runs correctly on the local partitions.

Q. How can I get assembler output?.

A. Add asm=1 to the make command line as in

make asm=1 solve.o

[Wed Feb 17 18:50:30 PST 2016]