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/980 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 each Tuesday 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 Tuesday June 22 2021

Additional LLVM Resources

• Implementing a JIT Compiled Language with Haskell and LLVM

Reading/Quiz Schedule

• Hughes, Chapter 1: Data Parallelism - Quiz Tuesday May 25 2021
• Sampson, LLVM for Grad Students - Quiz Tuesday June 01 2021
• Hughes, Chapter 2: Exploiting Data Parallelism with SIMD Execution - Quiz Tuesday June 08 2021
• Hughes, Chapter 3: Computation and Control Flow - Quiz Tuesday June 15 2021
• 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 Tuesday June 22 2021
• Hughes, Chapter 5: Horizontal Operations - Quiz Tuesday June 29 2021
• Hughes, Chapter 4: Memory Operations - Quiz Tuesday July 06 2021

Project Definition

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
  • Groups present updates on their projects
  • Prepare, present and submit a 2-page PDF.
  • Grades based on participation.

• Final Project Group Report (Monday August 16 2021)
  • Introduction
  • Design
  • Implementation Details
  • Implementation Evaluation
  • Conclusion: Lessons Learned and Further Work
  • Appendixes: Source Code, Scripts, Sample Data
• Individual Write-up (Wednesday August 18 2021)
  • Description of Role in Overall Project
  • Graduate students: Related Literature and Research Contribution
• Final Group Poster Presentation (Friday August 20 2021, 12:30)
  • 5-8 page PDF presentation/slide show.
• Poster Review (Saturday August 21 2021, 23:30)
  • Your individual comments/feedback on each project/poster.

Contact Info and Office Hours

• Professor
  • Rob Cameron
  • email @sfu.ca: cameron

• Teaching Assistant
  • Chintana Parabhu
  • email @sfu.ca: chintana_prabhu

Course Notes

• May 14
  • Introduction to icgrep
  • Parabix Git Repository
• May 18
  • LLVM Overview
  • SIMD Overview
• May 21
  • Introduction to Parabix*
• May 25
  • SIMD Code Generation in the LLVM Back-End
• May 28
  • Introduction to Parabix Programming - wc
• June 1
  • Kernels + StreamSets = Programs
  • A Parabix CSV-to-JSON Application
• June 4
  • Project Definition
• June 8
  • Parabix Transform - Horizontal SIMD
• June 11
  • SWAR Support for LLVM
• June 15
  • Autovectorization with LLVM
• June 22
  • Scalable Vectorization for LLVM
• June 25
  • Parabix Character Class Compilers
• July 6
  • Supporting Vector Programming on a Bi-Endian Processor Architecture
• July 9
  • Project Update 1
• July 13
  • Parallel Deletion
• July 16
  • Project Update 2
• July 20
  • Shuffle Pattern Library
• July 23
  • Project Update 3
• July 27
  • Superoptimizing LLVM