yungyuc / nsd

Numerical Software Development

Numerical Software Development Course Notes

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.

Course design

• 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.

How to study

• 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

Course schedule

• 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

1. Part 1: What is numerical software
   1. Why develop numerical software
   2. Hybrid architecture
   3. Numerical software = C++ + Python
2. Part 2: What to learn in this course
   1. Term project
   2. How to write a proposal
   3. Term project grading guideline
   4. Online discussion
3. Part 3: Runtime and course marterials
   1. Runtime environment: Linux and AWS
   2. Jupyter notebook

Unit 2 Fundamental engineering practices

A large chunk of efforts is spent in the infrastructure for coding. The key to the engineering system is automation.

1. Automation
   1. Bash scripting
   2. Makefile
   3. Cmake (cross-platform, multi-language automation)
2. Version control and regression
   1. Git version control system
   2. Automatic testing: author and run with google-test and py.test
   3. Wrap to Python and test there: pybind11
   4. Continuous integration to avoid regression
3. Work that cannot be automated
   1. Code review (use github for demonstration)
   2. Timing to debug for performance
      1. Wall time and CPU cycles
      2. System time and user time
      3. 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.

1. Organize Python modules
   1. Scripts
   2. Modules
   3. Packages
2. Use numpy for array-oriented code
   1. Data type
   2. Construction
   3. Multi-dimensional arrays
   4. Selection
   5. Broadcasting
3. Use tools for numerical analysis
   1. Matplotlib
   2. Linear algebra using numpy and scipy
   3. Package management wtih conda and pip

Unit 4 C++ and computer architecture

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.

1. Fundamental data types
   1. Command-line interface for compiler tools
      1. Compiler, linker
      2. Multiple source files, separation of declaration and definition, external libraries
      3. Build multiple binaries and shared objects (dynamically linked libraries)
   2. Integer, signness, pointer, array indexing
   3. Floating-point, rounding, exception handling
   4. Numeric limit
2. Object-oriented programming
   1. Class, encapsulation, accessor, reference type
   2. Constructor and destructor
   3. Polymorphism and RTTI
   4. CRTP
3. Standard template library (STL)
   1. std::vector, its internal and why the buffer address is dangerous
   2. std::array, std::list
   3. 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.

1. POD arrays and majoring
   1. Vector: 1D array
   2. Matrix: 2D array
   3. Row- and column-majoring
   4. A simple class for matrix
2. Matrix-vector and matrix-matrix operations
   1. Matrix-vector multiplication
   2. Matrix-matrix multiplication
3. Linear algebra
   1. Linear system solution
   2. Eigenvalue and singular value problems
   3. Least square problems

Unit 6 Cache optimization

How cache works, its importance to performance, and optimization with cache.

1. Memory hierarchy
2. How cache works
   1. Cache block (line) size determines speed
   2. Locality
   3. Matrix population in C++
   4. Array majoring in numpy
3. Tiling

Unit 7 SIMD

Parallelism and x86 assembly for SIMD.

1. Types of parallelism
   1. Shared-memory parallelism
   2. Distributed-memory parallelism
   3. Vector processing
2. SIMD instructions
   1. CPU capabilities
   2. x86 intrinsic functions
   3. Symbol table
   4. 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.

1. Linux memory model: stack, heap, and memory map
2. C memory management API
3. C++ memory management API
4. STL allocator API
5. Object counter

Unit 9 Ownership and smart pointers

Ownership and memory management using C++ smart pointers.

1. Pointers and ownership
   1. Raw pointer
   2. Reference
   3. Ownership
   4. Smart pointers
      1. unique_ptr
      2. shared_ptr
2. Revisit shared pointer
   1. Make Data exclusively managed by shared_ptr
   2. Get shared_ptr from this
   3. Cyclic reference and weak_ptr

Unit 10 Modern C++

Copy elision and move semantics. Variadic template and perfect forwarding. Closure.

1. Copy elision / return value optimization
   1. Make a tracker class for copy construction
   2. Show the copy elision in action
   3. Inspect the assembly
2. Move semantics and copy elision
   1. Forced move is a bad idea
3. Data concatenation
   1. Style 1: return vector
   2. Style 2: use output vector
   3. Style 3: use a class for both return and output argument
4. Variadic template
5. Perfect forwarding
6. Lambda expression
   1. Keep a lambda in a local variable
   2. Difference between auto and std::function
7. Closure
   1. Comments on functional style

Unit 11 C++ and C for Python

Use C++ and C to control the CPython interpreter.

1. Expectation from Python
   1. Linear wave
   2. The inviscid Burgers equation
2. Pybind11 build system
   1. Setuptools
   2. Cmake with a sub-directory
   3. Cmake with install pybind11
3. Additional wrapping layer for customization
4. Wrapping API
   1. Functions and property
   2. Named ane keyword arguments
   3. What happens in Python stays in Python (or pybind11)
5. Manipulate Python objects in C++
6. Python containers
   1. tuple
   2. list
   3. dict
7. Use cpython API with pybind11
   1. PyObject reference counting
8. Built-in types
   1. Cached value
   2. Attribute access
   3. Function call
   4. Tuple
   5. Dictionary
   6. List
9. Useful operations
   1. Import
   2. Exception
10. Python memory management
    1. PyMem interface
    2. Small memory optimization
    3. 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.

1. Python is slow but easy to write
2. Speed up by using numpy (still in Python)
3. Xtensor: write iterative code in C++ speed using arrays
4. Effect of house-keeping code
5. Design interface with arrays
6. Conversion between dynamic and static semantics
7. Insert profiling code

Unit 12 Array-oriented design

Software architecture that take advantage of array-based code.

1. Design interface with arrays
2. Conversion between dynamic and static semantics
3. Insert profiling code

Unit 13 Advanced Python

Advanced topics in Python programming.

1. Iterator
   1. List comprehension
   2. Generator
   3. Generator expression
2. Stack frame
   1. frame object
3. Customizing module import with sys.meta_path
4. Descriptor
   1. Keep data on the instance
5. Metaclass
6. Type introspection and abstract base class (abc)
   1. Method resolution order (mro)
   2. Abstract base class (abc)
   3. Abstract method

Miscellaneous

• 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

nsd's Issues

Question about the meaning of Exercise2,3

I'm solved the exercise2 and 3, but not sure my direction is correct.

2. Port "step0.py" to use bash.
3. Modify the script "step0.py" so that it reads the environment variable named "PYTHON_BIN" that specifies the location of the Python executable for the script. Hint: play a trick using bash.

Does the exercise2 ask us to translate the python script into bash script ?

And the execution flow of exercise3 is

• export PYTHON_BIN=...
• ./step0.py
• Interpret step0.py as the language of PYTHON_BIN

Or can you give a more detail explanations about the exercise2 and 3 ?

Apple ARM CPU M1 can't support mkl

Apple unleashes m1
The new Macbook using M1 CPU definately not support Intel® Math Kernel Library.
It should not work with a docker image either. The only solution is running program on AWS.

Makefile: implicit rule -> pattern rule

What is discussed here in the tutorial is actually makefile's "pattern rule" rather than "implicit rule".
I suggest changing the section title.

Add more information on README

With more information on README, it would probably be easier to share this course on the Internet. cc @yungyuc

Question about the Section "Polymorphism" in Lecture 4 "C++ and computer architecture"

The first paragraph says that:

C++ detects the type of the polymorphic object in runtime, and use the type information to find the associated member function.

But I have the impression that the virtual function is implemented by the vtable mechanism and vtable is just a static array of function pointers set at compile time which doesn't need to be checked at runtime.

As a result, I did some researches on this and I found this article explaining the vtable mechanism and I also did an experiment on Compiler Explorer. The experiment shows that the assembly for the function call on a virtual function is emitted in the form of taking the pointer of vtable and then just using the right offset to get the correct function pointer, which doesn't contain a check mentioned in that paragraph.

I remember that you mentioned vtable in the course this Monday, so does the "using the type information" mean using vtable? If so, I think it's a bit misleading and maybe it can be rewritten to something like:

C++ detects the type of the polymorphic object in runtime if necessary (e.g., dynamic_cast), and uses the vtable to find the associated member function when we need a virtual function call.

Correct me if I'm wrong. Thanks!

[Lecture 12] There are "unknown character" in formula

In Lecture 12 Array code in C++, there are "unknown character" in document. Such as:

Update nsd AMI for 20sp