20160912_msu_yak_02a (Лекции), страница 2

Базовые алгоритмы© Якобовский М.В.5⇐>=25kn+ 4kτ sTp (kn) = τ cp?for(шаг=0;шаг<k;шаг++){for(кирпич=rank*n/p;кирпич<(rank+1)*n/p;кирпич++)Уложить(кирпич)if(rank>0)if(rank<p-1)if(rank<p-1)if(rank>0)Send(rank-1,Recv(rank+1,Send(rank+1,Recv(rank-1,кирпич уложен!место готово?кирпич уложен!место готово?))))}0=<⇒Москва, 2016 г.1⇐=<⇒>=2⇐=<⇒>=3⇐=<⇒>=4⇐=<⇒>=Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.5⇐>=26kn+ 4kτ sTp (kn) = τ cp?012345=<⇒⇐=<⇒>=⇐=<⇒>=⇐=<⇒>=⇐=<⇒>=⇐>=Москва, 2016 г.Параллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.27kn+ 1kτ sTp (kn) = τ cp01=<⇒⇐=<⇒>=Москва, 2016 г.!2345⇐=<⇒>=⇐=<⇒>=⇐=<⇒>=⇐>=Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.28kn+ 2kτ sTp (kn) = τ cp01=<⇐=<⇒>=⇒Москва, 2016 г.!2⇐=<⇒>=345⇐=<⇒>=⇐=<⇒>=⇐>=Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.29knT p (kn) = τ c+ 3kτ sp01=<⇐=<⇒⇒>=Москва, 2016 г.!2⇐=<⇒>=3⇐=<⇒>=45⇐=<⇒>=⇐>=Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.30kn+ 4kτ sTp (kn) = τ cp01=<⇐=<⇒⇒>=Москва, 2016 г.!2⇐=<⇒>=3⇐=<⇒>=45⇐=<⇒>=⇐>=Параллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.31knT p (kn) = τ c+ pkτ sp01=<⇐=<⇒⇒>=Москва, 2016 г.!2⇐=<⇒>=3⇐=<⇒>=45⇐=<⇒>=⇐>=Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.32knT p (kn) = τ c+ ( p + 1)kτ sp01=<⇐=<⇒⇒>=Москва, 2016 г.2⇐=<⇒>=!3⇐=<⇒>=45⇐=<⇒>=⇐>=Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.33kn+ ( p + 2)kτ sT p (kn) = τ cp01=<⇐=<⇒⇒>=Москва, 2016 г.2⇐=<⇒>=!3⇐=<⇒>=45⇐=<⇒>=⇐>=Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.34kn+ ( p + 3)kτ sTp (kn) = τ cp01=<⇐=<⇒⇒>=Москва, 2016 г.2⇐=<⇒>=!3⇐=<⇒>=45⇐=<⇒>=⇐>=Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.35kn+ ( p + 4)kτ sT p (kn) = τ cp01=<⇐=<⇒⇒>=Москва, 2016 г.2⇐=<⇒>=!3⇐=<⇒>=45⇐=<⇒>=⇐>=Параллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.36kn+ 2 pkτ sT p (kn) = τ cp01=<⇐=<⇒⇒>=Москва, 2016 г.2⇐=<⇒>=!3⇐=<⇒>=45⇐=<⇒>=⇐>=Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.37kn+ 4kτ sTp (kn) = τ cp!012345=<⇒⇐>==<⇒=<⇒⇐>=⇐>==<⇒=<⇒⇐>=⇐>=Москва, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.38kn+ 4kτ sTp (kn) = τ cp!for(шаг=0;шаг<k;шаг++){for(кирпич=rank*n/p;кирпич<(rank+1)*n/p;кирпич++)Уложить(кирпич)if(rank%2){if(rank>0)if(rank>0)if(rank<p-1)if(rank<p-1)}else{if(rank<p-1)if(rank<p-1)if(rank>0)if(rank>0)}}Москва, 2016 г.Send(rank-1,Recv(rank-1,Recv(rank+1,Send(rank+1,кирпич уложен!место готово?место готово?кирпич уложен!))))Recv(rank+1,Send(rank+1,Send(rank-1,Recv(rank-1,место готово?кирпич уложен!кирпич уложен!место готово?))))Параллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.39Метод коллективного решенияРешение множества независимых друг от другазадач:––––Табулирование функцийРешение задач методами Монте-КарлоЧисленное интегрирование многомерных функций…Москва, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.40Последовательность ФибоначчиМосква, 2016 г.Параллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.41Последовательный алгоритмМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.42А1: РекурсияF(n){if(n<2) return 1;return F(n-2)+F(n-1);}Сколько потребуется операций?Москва, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.43А1: РекурсияМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.44РекурсияМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.45Рекурсия: распараллелить можно, но…Москва, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.46Параллельная рекурсияF(n){if(n<2) return 1;Процессор 1a= F(n-2)Процессор 2b= F(n-1)return a+b;}Сколько времени потребуется на выполнение?Москва, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.47Быстрее, чем за O(n)Москва, 2016 г.Параллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.48Быстрее, чем за O(n)Москва, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.49А4: Последовательный матричныйалгоритмМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.50А5: Параллельный матричныйалгоритмМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.51Москва, 2016 г.Параллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.52Москва, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.53ЗаключениеОтмечена важность использования логическипростых алгоритмов Рассмотрены основные причины потерь временипри выполнении параллельных алгоритмов Рассмотрены методы сдваивания игеометрического параллелизма, относящиеся кклассу методов статической балансировкизагрузки процессоровМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.54Якобовский М.В.проф., д.ф.-м.н.,зав. сектором «Программного обеспечениявычислительных систем и сетей»Института прикладной математики им.М.В.Келдыша Российской академии наукmail: lira@imamod.ruweb: http://lira.imamod.ruМосква, 2016 г.Параллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.55.