Not logged in. Login

Compiler Technology for SIMD Parallel Programming

Course Synopsis

The most significant changes to modern instruction set architecture are the deployment of additional single-instruction, multiple-data (SIMD) parallel programming capabilities. For example, Intel Haswell chips have recently incorporated AVX and AVX2 technology for simultaneously processing 256 bits of data at a time, arranged as 4 64-bit doubles or long long integers, 8 32-bit floats or integers, 16 16-bit integers, 32 bytes or 256 bits. General purpose programming on GPUs can similarly exploit the SIMT (single-instruction, multiple thread) model. Parallel programming using such capabilities can dramatically increase software performance, but at a significant cost in programmer productivity. In order to increase both performance and productivity, new SIMD and SIMT programming facilities are needed to automate the generation of high-quality software. In this course, students will study the development of new parallel programming facilities implemented using the LLVM compiler infrastructure as well as the Parabix parallel bit stream technology developed at Simon Fraser University. Students will implement at least one significant compiler component using the LLVM and/or Parabix framework.

Course Structure

CMPT 489/886 is a combined undergraduate/graduate research seminar course. Grading is based on in-class participation including quizzes and exercises (50%) and a final project (50%). Graduate student projects have higher expectations, including both a 30-minute in-class presentation and a formal literature review as part of their final project submission.

Readings and Weekly Quizzes

  • There will be lightweight weekly quizzes based on assigned readings. Your best grades (dropping the two lowest grades) on these quizzes count 40% of your class participation mark (that, is 20% of the total mark).

SIMD Architecture

Several reading assignments will be given based on the following text:

Christopher J. Hughes, "Single-Instruction Multiple-Data Execution," in Margaret Martonosi (ed.), Synthesis Lectures on Computer Architecture, Morgan and Claypool, 2015. Available online through the SFU Library.

LLVM Readings

  • LLVM for Grad Students
  • Asher, Yosi Ben Asher and Nadav Rotem, "Hybrid Type Legalization for a Sparse SIMD Instruction Set," ACM Transactions on Architecture and Code Optimization, 10(3), September 2013, Article 11. Available online through the SFU Library. - Quiz Wednesday February 28 2018

Additional LLVM Resources

Reading/Quiz Schedule

  • Hughes, Chapter 1: Data Parallelism - Quiz Wednesday January 10 2018
  • Sampson, LLVM for Grad Students - Quiz Wednesday January 17 2018
  • Hughes, Chapter 2: Exploiting Data Parallelism with SIMD Execution - Quiz Friday January 26 2018
  • Hughes, Chapter 3: Computation and Control Flow - Quiz Wednesday February 07 2018
  • Asher and Rotem, "Hybrid Type Legalization for a Sparse SIMD Instruction Set," ACM Transactions on Architecture and Code Optimization, 10(3), September 2013, Article 11. Available online through the SFU Library. - Quiz Wednesday February 28 2018
  • Hughes, Chapter 5: Horizontal Operations - Quiz Wednesday March 07 2018
  • Hughes, Chapter 4: Memory Operations - Quiz Wednesday March 14 2018

Assignments

Project Definition Week: Week 6

Reading Break/Week 7

The reading assignment for the break and week 7 is to read and understand the introductory examples of all groups in the class. Quiz Wednesday February 28 2018.

Course Project Overview

All students are expected to participate in a course project involving SIMD Compiler technology within an existing open source framework. Students will be expected to make a significant, high-quality source-code contribution to the overall framework together with a set of test cases that demonstrate the contribution.

Possible projects include:

  • Target-independent SIMD abstractions implemented as LLVM IR transformation passes (LLVM framework).
  • Target-dependent SIMD code-generation for a particular back-end instruction set architecture (LLVM framework).
  • Contributions or novel applications of the Parabix-LLVM framework based on bitwise data parallelism.
  • Contributions to the Intel SPMD Compiler.

Project Requirements

  • Project Updates Wednesday March 14 2018, Friday March 23 2018, Wednesday April 04 2018
    • Groups present updates on their projects
    • Group grades based on presentation
    • Individual grades based on class participation
  • Final Project Group Report (Tuesday April 10 2018)
    • Introduction
    • Design
    • Implementation Details
    • Implementation Evaluation
    • Conclusion: Lessons Learned and Further Work
    • Appendixes: Source Code, Scripts, Sample Data
  • Individual Write-up (Saturday April 14 2018)
    • Description of Role in Overall Project
    • Graduate students: Related Literature and Research Contribution
  • Final Group Poster Presentation (Sunday April 15 2018, 15:30)
  • Poster Review (Sunday April 15 2018, 17:30)
    • Your individual comments/feedback on each project/poster.

Contact Info and Office Hours

  • Professor
    • Rob Cameron
    • email @sfu.ca: cameron
    • Burnaby office: TASC1 room 8225
    • Office hours (Burnaby): Monday 1030-1130, Wednesday 1430-1530
    • Surrey office: Galleria 4178
    • Surrey lab: Galleria 4120
    • Open lab hours (Surrey): Tuesday/Thursday 1100-1230, 1300-1430

Course Notes

Updated Mon March 12 2018, 09:22 by cameron.