Franz Franchetti

Course Syllabus
18-847G: Special Topics in Computer Systems: Computational Problem Solving for Engineers
Spring 2020

Location: DH 1117
Class Lecture: Tuesday and Thursday, 10:30am–11:50am
Number of Units: 12
Recommended pre-requisites: 18-213/613, 18-202 or equivalent

Overview:

Computing platforms used in engineering span an incredible dynamic range from embedded and wearable processors through handhelds/laptops to high performance computing servers and the cloud. Similar engineering and AI/ML problems need to be solved across the entire dynamic range. When developing algorithms or solving R&D problems, one usually starts with Matlab and Python using frameworks like Torch, Spark, and TensorFlow, and resorts to C/C++ only when needed. This course covers how to solve AI/ML and engineering research and development problems across the entire range of machines in a productive and performant way. It discusses how to scale problems from the initial concept stage usually executed on a laptop to more powerful computing systems like enterprise or HPC servers, GPU accelerated systems, and cloud computing platforms.

This course addresses a wide range of computational and informatics problem families from traditional numerical simulation and symbolic data processing to AI and machine learning problems. It covers the most important scalable parallel algorithms used in engineering computing, and discusses frameworks providing problem-specific and general implementation templates. It covers algorithm analysis from the numerical and complexity perspective, parallelization approaches and scalability, algorithm optimization, evaluation and analysis of results.

Students in this course learn to productively solve AI/ML and engineering research and development problems on advanced computer systems across the dynamic range of computing systems. Further, they learn to carry algorithms from the concept stage to efficient-enough scaled-up implementations necessary to solve large scale problem instances, or squeeze them into the small footprint of embedded and wearable devices. PhD students will use their own research problem as case study while MS students will solve assigned homeworks and do a final project.

Prof. Franchetti office hours: Tuesdays 2:00pm–3:00pm or by appointment
Zoom instead of HH A312: https://cmu.zoom.us/j/3201808397
email: franzf@ece.cmu.edu
web: http://www.ece.cmu.edu/~franzf

TA Sanil Rao office hours: Mondays 1:00pm–2:00pm.
Zoom instead of HH 1305
email: sanilr@andrew.cmu.edu

ECE IT Helpdesk: HH A204 walk-in Monday–Friday 8:00am–5:00pm
email: help@ece.cmu.edu

Course Canvas link: https://canvas.cmu.edu/courses/13266

Tentative Course Calendar

Date	Day	Class Activity
January
14	Tues.	State of computing: What is the current state of the art from embedded devices through desktops, servers, and consumer systems all the way to cloud, HPC, and supercomputing
16	Thurs.	The ECE Computing Environment: number cluster, Andrew systems, capability machines, GPU access, cloud access, Pittsburgh Supercomputing Center and XSEDE
21	Tues.	Computer architecture: Relevant computer architecture concepts
23	Thurs.	Software stack: ISA, operating system, virtualization, messaging, containers
28	Tues.	Mathematics for Engineers: The central role of numerical linear algebra
30	Thurs.	Algorithm analysis, scalability, complexity: Getting answers in time
February
4	Tues.	Field trip: ECE Computing/Cyert Hall
6	Thurs.	Parallelization: Sequential vs. parallel algorithms, scalability vs. performance
11	Tues.	Need for speed: Principles of code optimization, when and how to optimize code
13	Thurs.	Cloud computing and HPC: Amazon EC2/Windows Azure/Google Cloud, Computational Grids, Scientific Workflows, Computing Centers
18	Tues.	Numerical Analysis: How good are your answers? How to make them better?
20	Thurs.	Guest Lecture: Quantum Computing and Quantum Algorithms
25	Tues.	Scalable algorithms: Dense numerical linear algebra, CNNs/DNNs/ FFTs
27	Thurs.	Scalable algorithms: Graph algorithms and sparse numerical linear algebra
March
3	Tues.	Scalable algorithms: ODE and PDE solvers, stencils, filters, discretization
5	Thurs.	Scalable algorithms: Discrete and continuous optimization, ML training
6	Fri.	Mid-Semester Break; No Classes
9-13		Spring Break; No Classes
17	Tues.	Cancelled. Switching to Zoom online lectures. From now on: https://cmu.zoom.us/j/3201808397
19	Thurs.	Scalable algorithms: Informatics, symbolic computing, higher level AI algorithms
24	Tues.	Scalable algorithms: Statistics: Monte Carlo, MCMC, statistical machine learning
26	Thurs.	Data and Visualization: Data sets, data visualization and tables, data bases
31	Tues.	Modern CPUs: Super-Scalar Out-of-order, multicore, ISA extensions
April
2	Thurs.	Modern CPUs—Vector Extensions: How to double/quadruple your peak performance quickly
7	Tues.	Hardware Acceleration: GPUs, FPGAs, TPU, Tensor Cores, . . .
9	Thurs.	From productivity to performance: C++, OpenMP, MPI, CUDA, Autotuning
14	Tues.	Homework—Lessons learned: What we learned and found strange
16-17		No Classes; Spring Carnival
21	Tues.	Research Talk: SPIRAL: Formal Software Synthesis of Computational Kernels
23	Thurs.	PhD Student Project Presentations
28	Thurs.	Guest Lecture: Pittsburgh Supercomputing Center and Usable HPC and High Performance AI/ML
30	Tues.	Summary: What we have learned and where to go from here

MS Homework and PhD Project

Machines

In this course we will use a large variety of machines in the homeworks and projects:

Large Linux servers with direct ssh access. The machines we will access are the ECE number cluster and the data science cloud.
Large number of small Linux machines in high throughput mode via ECE's HTCondor.
HPC multicore nodes and multi-node configurations with and without GPUs via a batch system at PSC and CMU/MechE.
Hadoop/Spark/Tensorflow with and without GPUs at PSC.
Special hardware at PSC: Bridges AI multi-GPU resources (HPE Apollo and DGX-2) and large memory machines.
AWS instances with or without multicore and GPU support.

Software Platforms

In the course we will try out a number of high-level languages and libraries in these languages:

Python with NumPy, SciPy, and matplotlib
R with CRAN packages
Matlab
Mathematica
Haskell
Frameworks: Torch, Theano, OpenCV
High-end engineering software
C/C++ with HPC math/ML libraries

Algorithms

We will use algorithms covered in the lecture as simple examples to experiment across the machines and software platforms. Students either implement the algorithms themselves or find implementations online, and then run them on the target machines to perform scalability studies. Algorithm groups targeted in the homeworks are as following:

Dense numerical linear algebra, CNNs/DNNs/FFTs
Graph algorithms and sparse numerical linear algebra
ODE and PDE solvers, stencils, filters, discretization
Discrete and continuous optimization, ML training
Informatics, symbolic computing, higher level AI algorithms
Statistics: Monte Carlo, MCMC, statistical machine learning
Deep Learning, Big Data Analytics

MS Homework Deliverables

Homework 1 to 4 will have as deliverables examples that run the specified/chosen algorithms on the specified/chosen machines for a range of problem sizes. The homework submission consists of the following:

The source code for the algorithm, with source attribution as applicable
The necessary data files
All necessary scripts and make files
The captured output of the submission runs
Measurements in CSV files and performance plot
Homework Deliverables

MS Project Deliverables

Homework 5 has as deliverable a blog post addressing the following aspects of the problem:

Problem specification: explain what problem you are addressing and where it is used.
Algorithm: describe the algorithm you used.
Hardware and software: describe the hardware platform and software infrastructure you used.
Outcome: describe the result you obtained and how larger computing resources were necessary.
Scalability and complexity: describe the algorithm's complexity, how the algorithm scales with problem size, and how it scales number of processors/cores in strong and weak scaling sense.
Quality of the result: assess the numerical or approximation quality of your result.
Performance anyalysis: measure the runtime behavior, model fit it to the theoretical growth behavior, and assess the efficiency of the implementation.
Suggested performance optimization: Assume a limited engineering budget but the need for a faster solution. Suggest which parts of the algorithm one would optimize and what optimization approach and target hardware should be used.

PhD Project Deliverables

An (up to) 6-page paper in the IEEE HPEC style (http://www.ieee-hpec.org/cfp.htm) addressing the following aspects of the problem:

Problem specification: explain what problem you are addressing and where it is used.
Algorthm: describe the algorithm you used.
Hardware and software: describe the hardware platform and software infrastructure you used.
Outcome: describe the algorithm's complexity, how the algorithm scales with problem size, and how it scales number of processors/cores in strong and weak scaling sense.
Quality of the result: assess the numerical or approximation quality of your result.
Performance analysis: measure the runtime behavior, model fit it to the theoretical growth behavior, and assess the efficiency of the implementation.
Suggested performance optimization: Assume a limited engineering budget but the need for a faster solution. Suggest which parts of the algorithm one would optimize and what optimization approach and target hardware should be used.

The paper is expected to be a real HPEC paper that could reasonably be presented at the conference as poster or presentation. Projects with good results that fit the conference should be considered for actual submission to the conference if the advisor agrees. The conference submission deadline is May 22, 2020.

In addition to the paper a final presentation will be given on April 23. The presentation is expected to be about 10 minutes long and to cover the 8 items also addressed in the paper. The suggestion is to allocate one slide to each topic above, and maybe dive deeper for one or two of the topics in a second slide.

On February 13 all PhD students will present an initial project overview that covers the first four topics above (outcome is to be discussed as expected outcome).

PhD students should attend the instructor office hours to define their project and check in before the overview and the final presentation for sign-off.

Course Summary

Date	Details	Activity	Time
Thu Feb 20, 2020	Assignment	MS: Homework 1: Getting Started, Scalability of Linear Algebra	due by 11:59pm
Tue Mar 3, 2020	Assignment	MS: Homework 2: Parallelism, Scaling, Performance	due by 11:59pm
Tue Mar 24, 2020	Assignment	MS: Homework 3: CNNs, DNNs and Graph Algorithms	due by 11:59pm
Tue Apr 7, 2020	Assignment	MS: Homework 4: AI, ML, Statistics	due by 11:59pm
Wed Apr 22, 2020	Assignment	PhD: Final Presentation	due by 11:59pm
Tue Apr 28, 2020	Assignment	MS: Homework 5: Final Project: Blog Post	due by 11:59pm
Thu Apr 30, 2020	Assignment	PhD: Final Project	due by 11:59pm


home \| short cv \| projects \| publications \| professional activity \| courses \| students \| rockin’