Difference between revisions of "BSTE:HighPerformanceComputing"
Jump to navigation
Jump to search
I.konyukhov (talk | contribs) (Created page with "= High Performance Computing = == Course Characteristics == === Key concepts of the class === * Multivariate calculus: derivatives, differentials, maxima and minima * Multi...") |
I.konyukhov (talk | contribs) |
||
| (4 intermediate revisions by the same user not shown) | |||
| Line 5: | Line 5: | ||
=== Key concepts of the class === |
=== Key concepts of the class === |
||
| + | * MIMD and SIMD architectures |
||
| − | * Multivariate calculus: derivatives, differentials, maxima and minima |
||
| + | * OpenMP, OpenCL, CUDA |
||
| − | * Multivariate integration |
||
| + | * Algorithms of computationam mathematics |
||
| − | * Functional series. Fourier series |
||
| + | * Parallelism |
||
| − | * Integrals with parameters |
||
=== What is the purpose of this course? === |
=== What is the purpose of this course? === |
||
| + | The course outlines some well-known numerical algorithms and discusses a range of problems related to their parallelization. |
||
| − | The goal of the course is to study basic mathematical concepts that will be required in further studies. The course is based on Mathematical Analysis I, and the concepts studied there are widely used in this course. The course covers differentiation and integration of functions of several variables. Some more advanced concepts, as uniform convergence of series and integrals, are also considered, since they are important for understanding applicability of many theorems of mathematical analysis. In the end of the course some useful applications are covered, such as gamma-function, beta-function, and Fourier transform. |
||
| + | Direct methods for solving systems of linear algebraic equations with matrices of both general and special types (Gauss exclusion method, Cholesky decomposition, run-through method), iterative methods for solving systems of linear equations (methods of simple iteration and upper relaxation, conjugate gradient method), sparse algebra problems, methods for parallel solution of systems of ordinary differential equations and partial differential equations, digital signal processing, Monte Carlo methods are considered. |
||
| + | === Prerequisites === |
||
| − | === Course objectives based on Bloom’s taxonomy === |
||
| + | * Introduction to Programming (C++ programming language), |
||
| − | === - What should a student remember at the end of the course? === |
||
| + | * Computer Architecture, |
||
| + | * Calculus, |
||
| + | * Linear Algebra, |
||
| + | * Differential Equations |
||
| + | * Digital signal processing |
||
| + | === Resources and reference material === |
||
| − | By the end of the course, the students should be able to: |
||
| + | * Sanders, J., Kandrot, E. (2010) CUDA by example : an introduction to general-purpose GPU programming, Addison-Weslye |
||
| − | * find partial and directional derivatives of functions of several variables; |
||
| + | * Scarpino, M. (2011) OpenCL in Action: How to Accelerate Graphics and Computations, Manning. |
||
| − | * find maxima and minima for a function of several variables |
||
| + | * Banger, R., Bhattacharyya, K. (2013) OpenCL Programming by Example, Packt Publishing. |
||
| − | * use Fubini’s theorem for calculating multiple integrals |
||
| − | * calculate line and path integrals |
||
| − | * distinguish between point wise and uniform convergence of series and improper integrals |
||
| − | * decompose a function into Fourier series |
||
| − | * calculate Fourier transform of a function |
||
| + | == Course Sections == |
||
| − | === - What should a student be able to understand at the end of the course? === |
||
| − | + | The main sections of the course and approximate hour distribution between them is as follows: |
|
| + | * Introduction to OpenMP, OpenCL and CUDA |
||
| − | * how to find minima and maxima of a function subject to a constraint |
||
| + | * Basic parallel algorithms of Linear Algebra |
||
| − | * how to represent double integrals as iterated integrals and vice versa |
||
| − | * |
+ | * Parallel methods of solving the systems of ordinary differential equations |
| + | * Parallel methods of solving partial differential equations |
||
| − | * properties of uniformly convergent series and improper integrals |
||
| + | * Parallelism in Digital Signal Processing |
||
| − | * beta-function, gamma-function and their properties |
||
| + | * Parallel Monte-Carlo methods |
||
| − | * how to find Fourier transform of a function |
||
| + | ==== Section title: ==== |
||
| − | === - What should a student be able to apply at the end of the course? === |
||
| + | Introduction to OpenMP and OpenCL |
||
| − | By the end of the course, the students should be able to ... |
||
| + | === Topics covered in this section: === |
||
| − | * find multiple, path, surface integrals |
||
| − | * find the range of a function in a given domain |
||
| − | * decompose a function into Fourier series |
||
| + | * Existing multicore systems |
||
| − | === Resources and reference material === |
||
| + | * MIMD and SIMD programming models |
||
| + | * Massively parallel accelerators |
||
| + | * Memory hierarchy |
||
| + | ==== Section title: ==== |
||
| − | * Robert A. Adams, Christopher Essex (2017) Calculus. A Complete Course, Pearson |
||
| − | * Jerrold Marsden, Alan Weinstein (1985) Calculus (in three volumes; volumes 2 and 3), Springer |
||
| + | Basic parallel algorithms of Linear Algebra |
||
| − | == Course Sections == |
||
| + | === Topics covered in this section: === |
||
| − | The main sections of the course and approximate hour distribution between them is as follows: |
||
| − | |||
| − | {| |
||
| − | |+ Course Sections |
||
| − | !align="center"| '''Section''' |
||
| − | ! '''Section Title''' |
||
| − | !align="center"| '''Teaching Hours''' |
||
| − | |- |
||
| − | |align="center"| 1 |
||
| − | | Differential Analysis of Functions of Several Variables |
||
| − | |align="center"| 24 |
||
| − | |- |
||
| − | |align="center"| 2 |
||
| − | | Integration of Functions of Several Variables |
||
| − | |align="center"| 30 |
||
| − | |- |
||
| − | |align="center"| 3 |
||
| − | | Uniform Convergence of Functional Series. Fourier Series |
||
| − | |align="center"| 18 |
||
| − | |- |
||
| − | |align="center"| 4 |
||
| − | | Integrals with Parameter(s) |
||
| − | |align="center"| 18 |
||
| − | |- |
||
| − | |align="center"| hline |
||
| − | | |
||
| − | |align="center"| |
||
| − | |} |
||
| + | * Matrix multiplication (demonstration of optimization based on different types of device's memory) |
||
| − | === Section 1 === |
||
| + | * Direct methods of solving SLAE |
||
| + | - Gaussian elimination |
||
| + | - Cholessky decomposition |
||
| + | - Sweep methods |
||
| + | * Iterative methods of solving SLAE |
||
| + | - Solution of sparse SLAE by iterative methods in the problem of heat propagation in a plate |
||
| + | - Solution of symmetric sparse SLAE by upper relaxation method with Chebyshev acceleration |
||
| + | - Solution of symmetric sparse SLAE by conjugate gradients with preconditioning |
||
| + | - Solution of sparse SLAE by generalized minimal residuals with preconditioning |
||
==== Section title: ==== |
==== Section title: ==== |
||
| + | Parallel methods of solving the systems of ODE |
||
| − | Differential Analysis of Functions of Several Variables |
||
=== Topics covered in this section: === |
=== Topics covered in this section: === |
||
| + | * Integration of a stochastic differential equation in the problem of calculating the fair price of an option of the European type |
||
| − | * Limits of functions of several variables |
||
| + | * Integration of a system of differential equations in the problem of modeling processes in a neural network |
||
| − | * Partial and directional derivatives of functions of several variables. Gradient |
||
| − | * Differentials of functions of several variables. Taylor formula |
||
| − | * Maxima and minima for functions of several variables |
||
| − | * Maxima and minima for functions of several variables subject to a constraint |
||
| − | |||
| − | === Section 2 === |
||
==== Section title: ==== |
==== Section title: ==== |
||
| + | Parallel methods of solving partial differential equations |
||
| − | Differential Analysis of Functions of Several Variables |
||
=== Topics covered in this section: === |
=== Topics covered in this section: === |
||
| + | * Solution of the wave equation |
||
| − | * Limits of functions of several variables |
||
| + | * Solution of the problem of thermal conductivity |
||
| − | * Partial and directional derivatives of functions of several variables. Gradient |
||
| + | * Solution of the Dirichlet problem for the Poisson equation |
||
| − | * Differentials of functions of several variables. Taylor formula |
||
| + | * Solution using Fast Fourier Transform |
||
| − | * Maxima and minima for functions of several variables |
||
| + | * Solving partial differential equations on the example of the problem of calculating the fair price of a composite option |
||
| − | * Maxima and minima for functions of several variables subject to a constraint |
||
| + | * Using the fast Fourier transform to solve the problem of heat propagation in the plate |
||
| − | |||
| − | === Section 3 === |
||
==== Section title: ==== |
==== Section title: ==== |
||
| + | Parallelism in Digital Signal Processing |
||
| − | Differential Analysis of Functions of Several Variables |
||
=== Topics covered in this section: === |
=== Topics covered in this section: === |
||
| + | * Simple color transformation |
||
| − | * Limits of functions of several variables |
||
| + | * Filtration, convolution |
||
| − | * Partial and directional derivatives of functions of several variables. Gradient |
||
| + | * Boundaries detection |
||
| − | * Differentials of functions of several variables. Taylor formula |
||
| + | * Images scaling |
||
| − | * Maxima and minima for functions of several variables |
||
| − | * Maxima and minima for functions of several variables subject to a constraint |
||
| − | |||
| − | === Section 4 === |
||
==== Section title: ==== |
==== Section title: ==== |
||
| + | Parallel Monte-Carlo methods |
||
| − | Differential Analysis of Functions of Several Variables |
||
=== Topics covered in this section: === |
=== Topics covered in this section: === |
||
| + | * Calculation of definite integrals |
||
| − | * Limits of functions of several variables |
||
| + | * Ways to reduce the variance |
||
| − | * Partial and directional derivatives of functions of several variables. Gradient |
||
| + | * Pseudorandom number generators |
||
| − | * Differentials of functions of several variables. Taylor formula |
||
| + | * Approaches to parallelization of Monte Carlo methods |
||
| − | * Maxima and minima for functions of several variables |
||
| + | * Parallel Monte Carlo methods in the problem of calculating the fair price of an option of the European type |
||
| − | * Maxima and minima for functions of several variables subject to a constraint |
||
Latest revision as of 10:15, 18 October 2021
High Performance Computing
Course Characteristics
Key concepts of the class
- MIMD and SIMD architectures
- OpenMP, OpenCL, CUDA
- Algorithms of computationam mathematics
- Parallelism
What is the purpose of this course?
The course outlines some well-known numerical algorithms and discusses a range of problems related to their parallelization. Direct methods for solving systems of linear algebraic equations with matrices of both general and special types (Gauss exclusion method, Cholesky decomposition, run-through method), iterative methods for solving systems of linear equations (methods of simple iteration and upper relaxation, conjugate gradient method), sparse algebra problems, methods for parallel solution of systems of ordinary differential equations and partial differential equations, digital signal processing, Monte Carlo methods are considered.
Prerequisites
- Introduction to Programming (C++ programming language),
- Computer Architecture,
- Calculus,
- Linear Algebra,
- Differential Equations
- Digital signal processing
Resources and reference material
- Sanders, J., Kandrot, E. (2010) CUDA by example : an introduction to general-purpose GPU programming, Addison-Weslye
- Scarpino, M. (2011) OpenCL in Action: How to Accelerate Graphics and Computations, Manning.
- Banger, R., Bhattacharyya, K. (2013) OpenCL Programming by Example, Packt Publishing.
Course Sections
The main sections of the course and approximate hour distribution between them is as follows:
- Introduction to OpenMP, OpenCL and CUDA
- Basic parallel algorithms of Linear Algebra
- Parallel methods of solving the systems of ordinary differential equations
- Parallel methods of solving partial differential equations
- Parallelism in Digital Signal Processing
- Parallel Monte-Carlo methods
Section title:
Introduction to OpenMP and OpenCL
Topics covered in this section:
- Existing multicore systems
- MIMD and SIMD programming models
- Massively parallel accelerators
- Memory hierarchy
Section title:
Basic parallel algorithms of Linear Algebra
Topics covered in this section:
- Matrix multiplication (demonstration of optimization based on different types of device's memory)
- Direct methods of solving SLAE
- Gaussian elimination - Cholessky decomposition - Sweep methods
- Iterative methods of solving SLAE
- Solution of sparse SLAE by iterative methods in the problem of heat propagation in a plate - Solution of symmetric sparse SLAE by upper relaxation method with Chebyshev acceleration - Solution of symmetric sparse SLAE by conjugate gradients with preconditioning - Solution of sparse SLAE by generalized minimal residuals with preconditioning
Section title:
Parallel methods of solving the systems of ODE
Topics covered in this section:
- Integration of a stochastic differential equation in the problem of calculating the fair price of an option of the European type
- Integration of a system of differential equations in the problem of modeling processes in a neural network
Section title:
Parallel methods of solving partial differential equations
Topics covered in this section:
- Solution of the wave equation
- Solution of the problem of thermal conductivity
- Solution of the Dirichlet problem for the Poisson equation
- Solution using Fast Fourier Transform
- Solving partial differential equations on the example of the problem of calculating the fair price of a composite option
- Using the fast Fourier transform to solve the problem of heat propagation in the plate
Section title:
Parallelism in Digital Signal Processing
Topics covered in this section:
- Simple color transformation
- Filtration, convolution
- Boundaries detection
- Images scaling
Section title:
Parallel Monte-Carlo methods
Topics covered in this section:
- Calculation of definite integrals
- Ways to reduce the variance
- Pseudorandom number generators
- Approaches to parallelization of Monte Carlo methods
- Parallel Monte Carlo methods in the problem of calculating the fair price of an option of the European type