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

This 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 ten grades on these quizzes count 40% of your class participation mark (that, is 20% of the total mark).

Weeks 1 through 5

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.

• Chapter 1: Data Parallelism - Quiz Thursday January 07 2016
• Chapter 2: Exploiting Data Parallelism with SIMD Execution - Quiz Thursday January 14 2016
• Chapter 3: Computation and Control Flow - Quiz Thursday January 21 2016
• Chapter 5: Horizontal Operations - Quiz Thursday January 28 2016
• Chapter 4: Memory Operations - Quiz Thursday February 04 2016

Reading Break/Week 6

The reading assignment for the break and week 6 is to read and understand the introductory examples of all groups in the class. Quiz Thursday February 18 2016.

LLVM Readings

• LLVM for Grad Students - Quiz Thursday February 25 2016
• 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 Thursday March 10 2016

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 Progress Report (March 31) (Groups)
• Assignment 3: Progress Report Feedback (individual)
  • Provide constructive feedback for all six other projects, such as suggestions for identified problems, related resources or literature, questions to consider.
  • Approximately two-written pages as a PDF.

• Final Project Group Report
  • Introduction
  • Design
  • Implementation Details
  • Implementation Evaluation
  • Conclusion: Lessons Learned and Further Work
  • Appendixes: Source Code, Scripts, Sample Data
• Individual Write-up
  • Description of Role in Overall Project
  • Graduate students: Related Literature and Research Contribution
• Final Group Poster Presentation

Notes

• Jan. 7
  • Overview of SIMD Instruction Set Architectures
  • Introduction to LLVM

• Jan. 12
  • Regular Expression Matching with Bitwise Data Parallelism

• Jan. 14
  • Explorations in SIMD
  • Shuffle Vector Project

• Jan. 19
  • The Python Parabix Tool Chain

• Jan. 26
  • Project Selection

• Jan. 28
  • Horizontal SIMD Operations with LLVM

• Feb. 2/4
  • Project Discussion
  • Introductory Project Example

• Feb. 6: Project Intros
  • Parabix Parser Generator
  • Data Parallel Hashing using Pablo and Scatter/Gather
  • Cyrillic to Latin transcoding
  • Intrinsic Hoisting
  • Improved Parabix Regular Expression Processing
  • LLVM-SWAR: SWAR processing with LLVM
  • LLVM-Backend: Back-end SIMD Optimization for AVX-512

• Feb. 25
  • Assignment 2: Write an LLVM Pass

• Mar. 8
  • The Parabix Character Class Compilers

• Mar. 15
  • Parallel Deletion