Copyright 2021, Yung-Yu Chen [email protected]. All rights reserved.
Objectives: This course discusses the art to build numerical software, i.e., computer programs applying numerical methods for solving mathematical or physical problems. We will be using the combination of Python and C++ and related tools (e.g., bash, git, make, etc.) to learn the modern development processes. By completing this course, students will acquire the fundamental skills for developing modern numerical software.
Prerequisites: This is a graduate or senior level course open to students who have taken computer architecture, engineering mathematics or equivalents. Working knowledge of Linux and Unix-like is required. Prior knowledge to numerical methods is recommended. The instructor uses English in the lectures and discussions.
- You are expected to learn programming languages yourself. Python is never a problem, but you could find it challenging to self-teach C++. Students are encouraged to form study groups for practicing C++, and discuss with the instructor and/or the teaching assistant.
- Grading: homework 30%, mid-term exam: 30%, term project: 40%.
- There are 12 lectures for the subjects of numerical software developing using Python and C++.
- There will be 6 homework assignments for you to exercise. Programming in Python and/or C++ is required.
- Mid-term examination will be conducted to assess students' understandings to the analytical materials.
- Term project will be used to assess students' overall coding skills. Presentation is required. Failure to present results in 0 point for this part. Check the term project page before you start.
- This is a practical course. No textbook is available for this specific interdisciplinary subject.
- To study the subject, students are required to research with online documents and source code, and write programs to practice.
- In-class instruction and course notes (github) are provided for guidance.
- References:
- Computer Systems: A Programmer's Perspective, Randal E. Bryant and David R. O'Hallaron: https://csapp.cs.cmu.edu/
- Python documentation: https://docs.python.org/3/
- Cppreference: https://en.cppreference.com/
- Effective Modern C++, Scott Meyer, O'Reilly, 2014
- Source code: cpython, numpy, xtensor, and pybind11
- W1 (2/22) Unit 1 and Unit 2: Introduction and fundamental engineering practices (homework #1)
- W2 (3/1) Skip meeting (peace memorial day)
- W3 (3/8) Unit 3: Python and numpy (term project proposal start)
- W4 (3/15) Unit 4: C++ and computer architecture (homework #2)
- W5 (3/22) Unit 5: Matrix operations
- W6 (3/29) Unit 6: Cache optimization (homework #3)
- W7 (4/5) Skip meeting (spring holiday) (term project proposal due)
- M8 (4/12) Unit 7: SIMD
- W9 (4/19) Mid-term examination
- W10 (4/26) Unit 8: Memory management (homework #4)
- W11 (5/3) Unit 9: Ownership and smart pointers
- W12 (5/10) Unit 10: Modern C++ (homework #5)
- W13 (5/17) Unit 11: C++ and C for Python
- W14 (5/24) Unit 12: Array code in C++ (homework #6)
- W15 (5/31) Unit 13: Advanced Python
- W16 (6/7) Term project presentation
- W17 (6/14) No meeting
- W18 (6/21) No meeting
Unit 1 Introduction
- Part 1: What is numerical software
- Why develop numerical software
- Hybrid architecture
- Numerical software = C++ + Python
- Part 2: What to learn in this course
- Term project
- How to write a proposal
- Term project grading guideline
- Online discussion
- Part 3: Runtime and course marterials
- Runtime environment: Linux and AWS
- Jupyter notebook
A large chunk of efforts is spent in the infrastructure for coding. The key to the engineering system is automation.
- Automation
- Bash scripting
- Makefile
- Cmake (cross-platform, multi-language automation)
- Version control and regression
- Git version control system
- Automatic testing: author and run with google-test and py.test
- Wrap to Python and test there: pybind11
- Continuous integration to avoid regression
- Work that cannot be automated
- Code review (use github for demonstration)
- Timing to debug for performance
- Wall time and CPU cycles
- System time and user time
- Python timing tools
Unit 3 Python and numpy
Python is a popular choice for the scripting engine that makes the numerical software work as a platform.
The platform works like a library providing data structures and helpers to solve problems. The users will use Python to build applications.
- Organize Python modules
- Scripts
- Modules
- Packages
- Use numpy for array-oriented code
- Data type
- Construction
- Multi-dimensional arrays
- Selection
- Broadcasting
- Use tools for numerical analysis
- Matplotlib
- Linear algebra using numpy and scipy
- Package management wtih conda and pip
The low-level code of numerical software must be high-performance. The industries chose C++ because it can take advantage of everything that a hardware architecture offers while using any level of abstraction.
- Fundamental data types
- Command-line interface for compiler tools
- Compiler, linker
- Multiple source files, separation of declaration and definition, external libraries
- Build multiple binaries and shared objects (dynamically linked libraries)
- Integer, signness, pointer, array indexing
- Floating-point, rounding, exception handling
- Numeric limit
- Command-line interface for compiler tools
- Object-oriented programming
- Class, encapsulation, accessor, reference type
- Constructor and destructor
- Polymorphism and RTTI
- CRTP
- Standard template library (STL)
- std::vector, its internal and why the buffer address is dangerous
- std::array, std::list
- std::map, std::set, std::unordered_map, std::unordered_set
Unit 5 Matrix operations
Matrices are everywhere in numerical analysis. Arrays are the fundamental data structure and used for matrix-vector, matrix-matrix, and other linear algebraic operations.
- POD arrays and majoring
- Vector: 1D array
- Matrix: 2D array
- Row- and column-majoring
- A simple class for matrix
- Matrix-vector and matrix-matrix operations
- Matrix-vector multiplication
- Matrix-matrix multiplication
- Linear algebra
- Linear system solution
- Eigenvalue and singular value problems
- Least square problems
Unit 6 Cache optimization
How cache works, its importance to performance, and optimization with cache.
- Memory hierarchy
- How cache works
- Cache block (line) size determines speed
- Locality
- Matrix population in C++
- Array majoring in numpy
- Tiling
Unit 7 SIMD
Parallelism and x86 assembly for SIMD.
- Types of parallelism
- Shared-memory parallelism
- Distributed-memory parallelism
- Vector processing
- SIMD instructions
- CPU capabilities
- x86 intrinsic functions
- Symbol table
- Inspect assembly: 1, 3, 5 multiplications
Unit 8 Memory management
Numerical software tends to use as much memory as a workstation has. The memory has two major uses: (i) to hold the required huge amount of data, and (ii) to gain speed.
- Linux memory model: stack, heap, and memory map
- C memory management API
- C++ memory management API
- STL allocator API
- Object counter
Unit 9 Ownership and smart pointers
Ownership and memory management using C++ smart pointers.
- Pointers and ownership
- Raw pointer
- Reference
- Ownership
- Smart pointers
unique_ptr
shared_ptr
- Revisit shared pointer
- Make Data exclusively managed by
shared_ptr
- Get
shared_ptr
fromthis
- Cyclic reference and
weak_ptr
- Make Data exclusively managed by
Unit 10 Modern C++
Copy elision and move semantics. Variadic template and perfect forwarding. Closure.
- Copy elision / return value optimization
- Make a tracker class for copy construction
- Show the copy elision in action
- Inspect the assembly
- Move semantics and copy elision
- Forced move is a bad idea
- Data concatenation
- Style 1: return
vector
- Style 2: use output
vector
- Style 3: use a class for both return and output argument
- Style 1: return
- Variadic template
- Perfect forwarding
- Lambda expression
- Keep a lambda in a local variable
- Difference between
auto
andstd::function
- Closure
- Comments on functional style
Unit 11 C++ and C for Python
Use C++ and C to control the CPython interpreter.
- Expectation from Python
- Linear wave
- The inviscid Burgers equation
- Pybind11 build system
- Setuptools
- Cmake with a sub-directory
- Cmake with install pybind11
- Additional wrapping layer for customization
- Wrapping API
- Functions and property
- Named ane keyword arguments
- What happens in Python stays in Python (or pybind11)
- Manipulate Python objects in C++
- Python containers
tuple
list
dict
- Use cpython API with pybind11
PyObject
reference counting
- Built-in types
- Cached value
- Attribute access
- Function call
- Tuple
- Dictionary
- List
- Useful operations
- Import
- Exception
- Python memory management
- PyMem interface
- Small memory optimization
- Tracemalloc
Unit 12 Array code in C++
Dissect the array-based code and element-based code and when to use them. Software architecture that take advantage of array-based code.
- Python is slow but easy to write
- Speed up by using numpy (still in Python)
- Xtensor: write iterative code in C++ speed using arrays
- Effect of house-keeping code
- Design interface with arrays
- Conversion between dynamic and static semantics
- Insert profiling code
Unit 12 Array-oriented design
Software architecture that take advantage of array-based code.
- Design interface with arrays
- Conversion between dynamic and static semantics
- Insert profiling code
Unit 13 Advanced Python
Advanced topics in Python programming.
- Iterator
- List comprehension
- Generator
- Generator expression
- Stack frame
frame
object
- Customizing module import with
sys.meta_path
- Descriptor
- Keep data on the instance
- Metaclass
- Type introspection and abstract base class (abc)
- Method resolution order (mro)
- Abstract base class (abc)
- Abstract method
- Readthedocs version: https://yyc.solvcon.net/en/latest/nsd/ (with cross reference).
- NYCU syllabus link: https://timetable.nycu.edu.tw/?r=main/crsoutline&Acy=109&Sem=2&CrsNo=5301
- 2020 autumn at NCTU: notebook/20au_nctu/.
- 2020 spring at NCTU: notebook/20sp_nctu/.
- 2019 autumn at NCTU: notebook/19au_nctu/.
Command to bootstrap a server on AWS:
curl -s https://raw.githubusercontent.com/yungyuc/nsd/master/contrib/install.sh | bash -s setup_aws