--- > **Условие задачи:** Перемножить 2 квадратные матрицы размера 1024x1024 с элементами типа double. > > Исходные матрицы генерируются в программе (случайным образом либо по определенной формуле) либо считываются из заранее подготовленного файла. > > Оценить сложность алгоритма по формуле c = 2 n3, где n - размерность матрицы. > > Оценить производительность в MFlops, p = c/t*10-6, где t - время в секундах работы алгоритма. > > Выполнить 3 варианта перемножения и их анализ и сравнение: > > - 1-й вариант перемножения - по формуле из линейной алгебры. > - 2-й вариант перемножения - результат работы функции cblas_dgemm из библиотеки BLAS (рекомендуемая реализация из Intel MKL) > - 3-й вариант перемножения - оптимизированный алгоритм по вашему выбору, написанный вами, производительность должна быть не ниже 30% от 2-го варианта ---

Инструкция по запуску

Для запуска программы нужно обязательно установить компилятор [Rust](https://rust-lang.org/tools/install/) ```sh git clone https://gitverse.ru/vladikBelkov/NPI_DataStructures_Labs/ cd NPI_DataStructures_Labs/task_2 cargo build --release # Обязательно указываем флаг release, чтобы компилятор оптимизировал программу и она стала работать быстрее ./target/release/target/task_2 ``` ---

Детали выполнения задания

Изначально структуру поле data в структуре Matrix я представлял как вложенный вектор(`Vec>`), что сильно сказывалось на производительности программы(фрагментация памяти, количество обращений к памяти). И если при работе над первым вариантов на это можно было закрыть глаза, то на втором, при котором работа с BLAS требовала в качестве аргумента именно ПЛОСКИЕ вектора, и третьем, где работа со вложенными векторами существенно снижала эффективность параллелизма, от такой архитектуры пришлось отказаться. ### double - это f64 Прямым аналогом double (64-битного числа с плавающей запятой) в Rust является тип f64. Он обеспечивает двойную точность, аналогичную типу double. ### Структура Matrix ```rust #[derive(Debug)] // Атрибут, необходим для вывода в консоль pub struct Matrix { pub rows: usize, pub cols: usize, pub data: Vec, } ``` ### Как был реализован третий вариант Третий вариант я решил реализовать через использование потоковых вычислений, в частности - через крейт rayon. Результаты измерения приведены на скриншоте. Note: это не панацея, и существующий вариант можно было улучшить через использование со связкой "пул потоков" + AVX. ```rust use crate::standart::Matrix; impl Matrix { fn transpose_optimized(&self, mat: &Matrix) -> Vec { let rows = mat.rows; let cols = mat.cols; let mut result = vec![0.0; rows * cols]; // Блочное транспонирование для кэш-локальности let block_size = 32; for i in (0..rows).step_by(block_size) { let i_end = (i + block_size).min(rows); for j in (0..cols).step_by(block_size) { let j_end = (j + block_size).min(cols); for ii in i..i_end { let src_start = ii * cols + j; let dst_start = j * rows + ii; for jj in j..j_end { result[dst_start + (jj - j) * rows] = mat.data[src_start + (jj - j)]; } } } } result } } impl Matrix { pub fn parallel_high_level_multiply(&self, other: &Matrix) -> Matrix { use rayon::prelude::*; assert_eq!(self.cols, other.rows); let n = self.rows; let m = self.cols; let p = other.cols; let b_t = self.transpose_optimized(other); let result: Vec = (0..n) .into_par_iter() .flat_map_iter(|i| { let mut row = vec![0.0; p]; let a_row = &self.data[i * m..(i + 1) * m]; for k in 0..m { let a_val = a_row[k]; if a_val != 0.0 { let b_row = &b_t[k * p..(k + 1) * p]; for j in 0..p { row[j] += a_val * b_row[j]; } } } row }) .collect(); Matrix { rows: n, cols: p, data: result, } } } ``` ---