Parallel Computing & Algorithms

"xxx."
-- xxx (yyyy-yyyy)

Goal

Multicore design is one of modern features of computer systems. You can easily see at least 4 cores in commercial CPUs in your desktop computers, laptops, even smart phones (for example, Apple A16 has one 6 cores CPU). However, the programming beginners rarely have opportunities to exploit the performance benefits of multi-core hardware, letting alone get a deep understanding of contemporary computer architecture. In recent years, Artificial Intelligence (AI) has become a prominent field, heavily relying on graphics processing units (GPUs) or accelerators for machine learning (ML). For example, the latest NVIDIA graphics card, the RTX 4090, has 16384 CUDA cores. Utilizing such an immense number of computational units has become a crucial challenge. This course shows you how to utilize these computing units (CPUs and GPUs) to unleash their computational performance. We will cover the following topics in ths course:

1. Modern computer architecture and job scheduling in operating systems
2. Multiprocessing & multithreading programming in Java, C#, and Python
3. Parallel algorithms
4. CUDA in C++

現今多核心設計的中央處理器 (central processing unit, CPU) 隨處可見 ，例如桌上型電腦、筆記型電腦甚至是智慧型手機，核心數至少 4 核心 (cores) 起跳，多可高達 96 核心 (例如 AMD EPYC 9654)，但初學程式設計的學員鮮少有機會利用到硬體多核所帶來的效能，甚至還沒有機會深入了解當代的電腦架構。近年人工智慧 (Artificial Intelligence, AI) 成為顯學，大量需要繪圖晶片 (graphics processing unit, GPU) 或者圖形加速器來進行機器學習 (machine learning, ML)，例如當前最新的 NVIDIA 顯示卡 RTX 4090 擁有 16384 顆 CUDA 核心，如何使用如此龐大的計算單元變成一個重要的課題。本課程將介紹平行程式與平行演算法，學員在課程中預計能夠學習到下列項目：

1. 當代硬體架構、作業系統 (以 Linux 為例)
2. 多程序與多執行緒的架構與實作 (以 Java、C#、Python 為例)
3. 平行演算法
4. CUDA (以 C++ 為例)

Instructor Information

• Instructor: Zheng-Liang Lu (Arthur)

Textbook

TBA

Programming Languages

• You can pick up programming languages like C, C++, C#, Java, and Python mentioned in this course.
• You can find installation instructions here.

Syllabus

Background Knowledge

Type of Parallelism

• Type fo tasks
  • CPU-bound tasks
  • I/O-bound tasks
    • For example, some operations of databases, web crawling.
• Parallelism in hardware
  • Parallelism in a uniprocessor
  • SIMD instructions, vector processors, GPUs
  • Multiprocessors
    • Symmetric shared-memory multiprocessors
    • Distributed-memory multiprocessors
    • Chip-multiprocessors a.k.a. multicores
  • Multicomputers a.k.a. clusters
• Parallelism in software
  • Instruction-level parallelism
  • Task-level parallelism
  • Data-level parallelism
  • Transaction level parallelis

Preliminary Knowledge about Hardware

• Multitasking/programming computer
  • Unlike mainframe computers which execute tasks in batches, personal computers (PC) need to perform multiple tasks simultaneously.
• Hardware acceleration
  • Instruction pipelining: fetch, decode, execution, write-back
    • https://en.wikipedia.org/wiki/Instruction_pipelining
  • Loop unrolling
    • https://en.wikipedia.org/wiki/Loop_unrolling#Simple_manual_example_in_C
  • Out-of-order execution
    • https://ocw.mit.edu/courses/6-823-computer-system-architecture-fall-2005/a984df22afeb4bd732058005861a70a4_l12_ooo_pipes.pdf
  • Register renaming
  • Branch prediction
    • https://en.wikipedia.org/wiki/Branch_predictor
  • Prefetching memory and files
    • For example, the used data/files will be cached in memory to avoid frequent I/O from slow devices. See https://www.linuxatemyram.com/.
• Cache design in modern processors
  • David Kuo, CPU Cache 原理探討
  • Jserv, 現代處理器設計：Cache 原理和實際影響
    • Chi-En Wu and Jim Huang (Jserv), 每位程式開發者都該有的記憶體知識
  • 老狼, Cache 是如何組織和運作的？ and L1, L2, L3 cache 究竟在哪裡？
  • Case study
    • Vadim Filanovsky and Harshad Sane, Seeing through hardware counters: a journey to threefold performance increase, Netflix Technology Blog, 2022-11-10
• Multi-core design
  • https://www.techspot.com/article/2363-multi-core-cpu/
    • In 2001 we saw the first true multi-core processor released by IBM under their Power4 architecture and as expected it was geared towards workstation and server applications.
    • In 2005, however, Intel released its first consumer focused dual-core processor which was a multi-core design and later that same year AMD released their version with the Athlon X2 architecture.
    • The first 1-qubit processors were announced not too long ago and yet a 54-Qubit processor was announced by Google in 2019 and claimed to have achieved quantum supremacy, which is a fancy way of saying their processor can do something a traditional CPU cannot do in a realistic amount of time.
  • Series aritcles for computer hardware development are listed as follows: personal computer, cpu, memory, graphic card, mother board, hard drive, ssd

Preliminary Knowledge about Software: Operating System

• Program vs. Process

  
  https://techdifferences.com/difference-between-program-and-process.html

• Job scheduling

  • Shortest job first
  • Round-Robin (RR) scheduling
  • Priority scheduling
  • Fair-share scheduling

• Thread

  • You may take a look at the implementation in Linux kernel: https://github.com/torvalds/linux/blob/master/include/linux/sched.h
  • Worth to read this article for Linux processes: https://hackmd.io/@sysprog/linux-process

• Parallelism and concurrency

  • Write to database in parallel or concurrently?
    • See atomicity of the ACID properties of database transactions.

• Race condition

  ​​​​    int x = 0;
  ​​​​    x++; // thread-safe?
  

  • For example, https://en.wikipedia.org/wiki/Java_bytecode

• Deadlock

  • Dining philosophers
    • Another issue: starvation
  • How to prevent the deadlock?
    • Try to eliminate the following four conditions:
      • Mutual exclusion
      • Non-preemption
      • Hold and wait
      • Circular wait
  • Producer-consumer model
    • https://www.cs.cornell.edu/courses/cs3110/2010fa/lectures/lec18.html
    • For example, publish-subscribe pattern.

• Amdhal's Law

  • Let
    $\alpha \mathrm{\%}$ be the parallelizable portion of one algorithm in percentage and
    $p$ be the number of processors (or computing units of any type).
  • For convenience, the timecost before parallelizing the algorithm is
    $T=100.$
  • Then the timecost of the algorithm of parallel version is
    $$T^{\prime }={\displaystyle \frac{\alpha }{p}}+100-\alpha .$$
  • The Amdhal's law states that the asymptotic limit of the speedup
    $\frac{T}{T^{\prime }}$ is
    $$\underset{p\to \mathrm{\infty }}{lim}\frac{T}{T^{\prime }}={\displaystyle \frac{100}{100-\alpha }}<\mathrm{\infty }.$$
  • This implies that you cannot reduce the execution time to zero even if you can fully parallelize the algorithm.
  • In conclusions,
    • Parallelism benefits reduction of execution time until the marginal improvement starts to degrade as the non-parallelizable portion dominates gradually, one example for the law of diminishing returns.
    • Instead of buying more machines, it's better to hire programmers who are good at parallel algorithms.

Parallel Modules/Packages in Programming Languages

• Linux

  • parallel
    • https://www.gnu.org/software/parallel/parallel_tutorial.html
    ​​​​​​​​time parallel --ungroup --jobs 1 unzip -qq {} -d ./dest ::: $(ls -d ./src/*.zip | tr "\n" " ")
    ​​​​​​​​# timecost: 0m33.277s
    ​​​​​​​​time parallel --ungroup --jobs $(nproc) unzip -qq {} -d ./dest ::: $(ls -d ./src/*.zip | tr "\n" " ")
    ​​​​​​​​# timecost: 0m1.359s with $(nproc) = 48
    

    • https://ulhpc-tutorials.readthedocs.io/en/latest/sequential/gnu-parallel/
  • More examples can be found here: https://www.gushiciku.cn/dc_tw/200046748

• Python

  • multiprocessing
    ​​​​​​​​from multiprocess import Pool
    
    ​​​​​​​​with Pool(multiprocessing.cpu_count()) as pool:
    ​​​​​​​​    results = pool.map(task, parameter_list)
    

    • One of my daily jobs is to compute on intraday market data. For TXO (台指選擇權), the number of transaction entries is more than 20M on daily basis to calculate the TAIWAN VIX (台指選擇權波動率指數).
      
      
  • threading
  • asyncio: asynchronous (nonblocking) programming
  • References
    • https://www.machinelearningplus.com/python/parallel-processing-python/

• Java sample code

  • Basic level: the Thread class and the Runnable interface.
    ​​​​​​​​...
    ​​​​​​​​    public static void main(String[] args) {
    ​​​​​​​​        
    ​​​​​​​​        Runnable task = () -> System.out.println("Hello, concurrency.");
    ​​​​​​​​        new Thread(task).start();
    ​​​​​​​​        new Thread(task).start();
    ​​​​​​​​        new Thread(task).start();
    ​​​​​​​​        
    ​​​​​​​​    }
    ​​​​​​​​...
    

  • Mid level: thread pool implemented by the Executors class and its associated members.
    • popcornylu, Java 多執行緒的基本知識
  ​​​​import java.util.List;
  ​​​​import java.util.ArrayList;
  ​​​​import java.util.concurrent.Executors;
  ​​​​import java.util.concurrent.ExecutorService;
  ​​​​import java.util.concurrent.Callable;
  ​​​​import java.util.concurrent.Future;
  
  ​​​​public class Test {
  
  ​​​​    public static void addAllTasks(List<Callable<String>> tasks) {
  
  ​​​​        tasks.add(() -> "Task 1");
  ​​​​        tasks.add(() -> "Task 2");
  ​​​​        tasks.add(() -> "Task 3");
  
  ​​​​    }
  
  ​​​​    public static void main(String... args) throws Exception {
  
  ​​​​        int numOfThread = 4;
  ​​​​        List<Callable<String>> tasks = new ArrayList<>();
  ​​​​        addAllTasks(tasks);
  ​​​​        ExecutorService pool = Executors.newFixedThreadPool(numOfThread);
  ​​​​        List<Future<String>> results = pool.invokeAll(tasks);
  ​​​​        results.forEach(System.out::println);
  ​​​​        pool.shutdown();
  
  ​​​​    }
  
  ​​​​}
  
  

  • Mid-level: fork-join pool implemented by the ForkJoinPool class with the ForkJoinTask interface.
  • Asynchronous programming in Java: see Callable, Future and CompletableFuture.

• Goroutine

  • https://gobyexample.com/goroutines
  • A Chinese explanation for goroutine: https://hoohoo.top/blog/golang-goroutine-above-fundamentals-and-structure/

• NVIDIA CUDA

  • Quick start: https://docs.nvidia.com/cuda/cuda-quick-start-guide/index.html
  • Benchmarks
    • TensorFlow 2 - CPU vs GPU Performance Comparison, 2019
    • Parallelizing across multiple CPU/GPUs to speed up deep learning inference at the edge, 2019
    • CPU vs GPU in Machine Learning Algorithms: Which is Better?, 2021
    • https://www.nvidia.com/en-us/data-center/resources/mlperf-benchmarks/
  • Supplementary materials
    • How CUDA Programming Works | GTC 2022

• C

  • OpenMP
  • POSIX Threads (aka pthread)
    • https://passlab.github.io/CSCE790/notes/lecture08_PThreads.pdf
    • https://passlab.github.io/CSE436536/notes/lecture09_pthread01.pdf
    • https://blog.gtwang.org/programming/pthread-multithreading-programming-in-c-tutorial/

• C++

  • OpenMP
  • Multithreaded programming
    • For example, https://www.geeksforgeeks.org/multithreading-in-cpp/
  • More articles about C++ parallel programming
    • Patrick Diehl, Advanced Parallel Programming in C++, 2021
    • 知乎：The Coroutine in C++ 20 协程初探

Parallel Algorithms

• https://www.dcc.fc.up.pt/~ricroc/aulas/1516/cp/apontamentos/slides_sorting.pdf
• https://www3.cs.stonybrook.edu/~rezaul/Spring-2012/CSE613/CSE613-lecture-9.pdf
• https://arxiv.org/ftp/arxiv/papers/1511/1511.03404.pdf

Practical Examples

Monte Carlo Simulation

• It is an example of embarrassingly (ideally) parallel algorithms.

need quantitative benchmark

Compression & Decompression

• Scenarios
  • Case 1: Decompressing 266 zip files for the TX futures. The total size of all csv files is 5.6 GB.
  • Case 2: Decompressing 254 zip files for all stocks in the Taiwan equity market. The total size of all csv files is 11 GB.
  • Case 3: Compressing nnnn csv files for all stocks in the Taiwan equity market.
    
    

    Scenario	Sequential (1T)	Parallel (48T)
    Case 1	36.915s	1.539s
    Case 2	1m13.223s	3.597s
    Case 3	TBA	TBA

Web Crawling

need quantitative benchmark

Complexity Analysis

Remarks

• Can parallism reduce the time complexity of one problem?
  • Definitely impossible unless you can supply processors/workers as many as the number of data size with a constant ratio.

Distributed Computing

• Message Passing Interface (MPI)
  • Lecture slides: https://people.sc.fsu.edu/~jburkardt/presentations/mpi_2013_acs2.pdf
  • Tech stack
    • Open MPI: Open Source High Performance Computing
    • MPI for Python
    • Using IPython for parallel computing
  • References
    • https://hpc.nmsu.edu/discovery/mpi/introduction/
    • https://wvuhpc.github.io/2018-Lesson_4/05-mpi/index.html
    • https://help.ubuntu.com/community/MpichCluster
    • https://medium.com/mpi-cluster-setup/mpi-clusters-within-a-lan-77168e0191b1

References

Books

• W. P. Petersen and P. Arbenz, Introduction to Parallel Computing, 2004
  
  
• Peter Pacheco and Matthew Malensek, An Introduction to Parallel Programming, 2/e, 2022
  
  
• Roman Trobec, Boštjan Slivnik, Patricio Bulić, and Borut Robič, Introduction to Parallel Computing: From Algorithms to Programming on State-of-the-Art Platforms, 2018
  
  

Operating Systems (OS)

• Abraham Silberschatz, Greg Gagne, Peter B. Galvin, Operating System Concepts, 10/e, 2021
  
  
• Andrew S. Tanenbaum and Herbert Bos, Modern Operating Systems, 4/e, 2015
  
  
• Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau, Operating Systems: Three Easy Pieces, 2018
  
  

Hardware Architectures

• Ulrich Drepper, What Every Programmer Should Know About Memory, 2007
• Maurice Herlihy, Nir Shavit, Victor Luchangco, and Michael Spear, The Art of Multiprocessor Programming, 2/e, 2020
  
  
• Randal Bryant and David O'Hallaron, Computer Systems: A Programmer's Perspective, 3/e, 2015
  
  

Parallel Algorithms

• Behrooz Parhami, Introduction to Parallel Processing: Algorithms and Architectures, 1999
  
  
• Frank Thomson Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes, 1991
  
  
• Michael McCool, James Reinders, and Arch Robison, Structured Parallel Programming: Patterns for Efficient Computation, 2012
  
  

CUDA

• Richard Ansorge, Programming in Parallel with CUDA, 2022
  
  
• NVidia, CUDA C++ Programming Guide

Distributed Computing

• Nicola Santoro, Design and Analysis of Distributed Algorithms, 2006
  
  

Courses

• Aydin Buluc and Jim Demmel, Applications of Parallel Computers, UC Berkeley, 2022
• Suresh Jagannathan, CS 353: Principles of Concurrency and Parallelism, Purdue University, 2022sp
• Brian Railing and Nathan Beckmann, 15-418/15-618: Parallel Computer Architecture and Programming, Carnegie Mellon University, 2021sp
• High Performance Computing For Science And Engineering (HPCSE) II, Swiss Federal Institute of Technology in Zurich
• Bei Yu, CMSC 5743 Efficient Computing of Deep Neural Networks, The Chinese University of Hong Kong, 2021
• Dan Garcia and Lisa Yan, Great Ideas in Computer Architecture (Machine Structures), UC Berkeley, 2022fa
• Yonghong Yan, CSCE 513 Computer Architecture, University of South Carolina, 2018fa
• Mike Giles and Wes Armour, Course on CUDA Programming on NVIDIA GPUs, 2023
• Sergio Martin, High Performance Computing for Science and Engineering, 2021: pdf
• Al Barr, GPU Programming, Caltech, 2022
• Jserv, Linux 核心設計: 記憶體管理

Youtubes

• Jserv, 作業系統概念: Concurrency (並行) 程式設計篇
• 极客湾 Geekerwan, 吹牛还是真牛？苹果M1全网最硬核评测 上 下

Game

• 7 Billion Humans
  
  

TODO

• Case study

  • Producer-consumer model
    • https://www.cs.cornell.edu/courses/cs3110/2010fa/lectures/lec18.html
  • Parallelism of Fibonacci numbers
    • https://classes.engineering.wustl.edu/cse231/core/index.php/Fibonacci
    • https://catonmat.net/mit-introduction-to-algorithms-part-thirteen
  • Single Instruction Multiple Data (SIMD)
    • The Intel® Compiler Auto Vectorization
      • https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html

• Supplementary materials

  • https://www.machinelearningplus.com/python/parallel-processing-python/
  • https://towardsdatascience.com/10x-faster-parallel-python-without-python-multiprocessing-e5017c93cce1