\documentclass{article}

\usepackage[utf8]{inputenc}
\usepackage[TS1,T2A]{fontenc}
\usepackage[russian]{babel}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{tikz}
\usepackage{multirow}
\usepackage[pdfborder={0 0 0}, colorlinks=true, urlcolor=blue, linkcolor=blue]{hyperref}

\hoffset=-3cm
\textwidth=18cm
\voffset=-3cm
\textheight=24.5cm

\date{2012-02-08}
\title{Параллельное программирование}
\author{Зайцев Вадим, ФИТ НГУ, 9204}

\makeindex

\begin{document}

%\maketitle

\section{Постановка задачи}

Реализация алгоритма умножения двух матриц с использованием POSIX threads: необходимо вычислить 
произведение двух квадратных матриц $A$ и $B$ размера $n$: в результате чего получается матрица \
$C = A \times B$, $ \displaystyle c_{i, j} = \sum_{k = 1}^n a_{i, k} \cdot b_{k, j} $.

\section{Подход к распараллеливанию}

\subsection{Простая реазиация}

Статически распределяем задачу между потоками: при запуске каждый поток в качестве аргумента 
принимает интерал строк [$start_i$; $end_i$) ($i$ = $0$ \ldots $T$-$1$, $end_i = start_{i+1}$ для 
$i$ = $0$ \ldots $T$-$2$, где $T$ - количество потоков) результирующей матрицы, которые ему надо 
посчитать. Т. к. все потоки вычисляют различные элементы матрицы $C$, то синхронизация не требуется.

\subsection{Блочное умножение}

Аналогично предыдущему, за исключением того, что каждый поток принимает номера блоков, которые ему 
надо посчитать.

\subsection{Наибольший параллелизм}

Из определения умножения следует, что для вычисления матрицы $C$ необходимо произвести $n^3$
умножений. Распределим умножения между всеми потоками: занумеруем все умножения числами от $0$ до 
$n^3$-1 и аналогично предыдущим реализациям будем в каждый поток передавать интервал [$start_i$; 
$end_i$) -- номера умножений, которые надо посчитать. 

При данном подходе разные потоки могут считать одни элементы матрицы $C$, поэтому для каждого из них
создаём отдельуную матрицу $C_i$, т. о. синхронизация по-прежнему не требуется. Итоговая матрица
$C$ = $\displaystyle \sum_i^{T-1} C_i$.

\section{Реузльтаты тестирования}

Измерение времени осуществлялось с помощью системной команды \textsf{time}.
Размер матрицы $n = 2000$.
\newline
\newline
\begin{tabular}{|l|c|r|r|r|} \hline
\multirow{2}{*}{\textbf{Реализация}} & 
\multirow{2}{*}{\textbf{Кол-во потоков}} & 
\multicolumn{3}{|c|}{\textbf{Время}} \\ \cline{3-5}
& & обычное & блочное (100) & необычное \\ \hline
\multicolumn{2}{|l|}{Однопоточная} & 19.209 & 20.520 &       - \\ \hline
Многопоточная                  & 1 & 19.148 & 20.520 &  19.182 \\ \hline
Многопоточная                  & 2 & 10.685 & 11.275 &  10.849 \\ \hline
Многопоточная                  & 3 &  7.887 &  8.241 &  8.203  \\ \hline
Многопоточная                  & 4 &  6.913 &  6.706 &  8.463  \\ \hline
Многопоточная                  & 5 &  7.858 &  7.644 &  7.941  \\ \hline
Многопоточная                  & 6 &  7.181 &  6.797 &  7.807  \\ \hline
\end{tabular}




\end{document}
