20160912_msu_yak_02b (1185581)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Базовые алгоритмы. Часть 2ПараллельныевысокопроизводительныевычисленияЯкобовский М.В., проф., д.ф.-м.н.СКИ МГУ,Институт прикладной математикиим. М.В.Келдыша РАН, МоскваМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.1Содержание лекцииМетоды построения параллельных алгоритмов иих свойства:– Статическая балансировка• метод сдваивания• геометрический параллелизм• конвейерный параллелизм– Динамическая балансировка• коллективное решение• диффузная балансировка загрузкиМосква, 2016 г.Параллельные высокопроизводительные вычисления.

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

Базовые алгоритмы© Якобовский М.В.5Найти самую глубокую скважинуМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.6Найти самую глубокую скважинуМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.7Найти самую глубокую скважинуМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.8Найти самую глубокую скважинуМосква, 2016 г.Параллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.9Найти самую глубокую скважинуМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.10Найти самую глубокую скважинуМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.11Найти самую глубокую скважинуМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.12Найти самую глубокую скважинуМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.13Найти самую глубокую скважинуМосква, 2016 г.Параллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.14Метод коллективного решенияNTp = (τ c + τ s )pτcτsmasterpmaxМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.τc=τs15Пример модельной задачи: Укладка паркетаT1 (kn) = τ c knT p (kn) =Число порцийОбработка порцииkn(rτ c + τ s )rp2Обмен данными rτ c 11S rτ c (kn) = = pmaxp=1 τ s  1 + rτ cτs1+pmaxτsEp=rτ cτs(kn) =1τs1+rτ cМосква, 2016 г.pmax =rτ cτsr – размер порцииПараллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.16Как правильно?r – размер порцииpmax =rτ cτsилиpmaxrτ c τ c==rτ s τ sЗависит ли время передачи данных от размера порции (задания)?Москва, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.17Вычисление определенного интегралаSend(ai); Send(ai+1); Recv(s);BI = ∫ f ( x )dx = ∑iAai +1∫ f (x )dxaiT p = τ s + max τ iiaiМосква, 2016 г.τ1ai+1τ2Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.18Метод конвейерного параллелизмаkn+?T1 (kn) = τ c kn Tp (kn) = τ cpМосква, 2016 г.Параллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.19Метод конвейерного параллелизмаT1 (kn) = τ c knS p (kn) = pМосква, 2016 г.1τs1+τcnkn+ k τsT p (kn) = τ cpp1E p (kn) =τs1+τcПараллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.20Метод геометрического параллелизмаT1 (kn) = τ c kn1S p (kn) = pp τs1+ 4n τcМосква, 2016 г.kn+ 4kτ sTp (kn) = τ cp1E p (kn) =p τs1+ 4n τcПараллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.21Метод конвейерного параллелизмаfor(t=0; t<tmax; t+=dt){fnew[0]=g(t);for(i=1; i<n; i++)fnew[i]= fnew[i-1]+f[i]for(i=0;i<n;i++)f[i] = fnew [i]fnew[i]}f[i]0Москва, 2016 г.123456Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.722Метод конвейерного параллелизмапроцессор 0Москва, 2016 г.процессор 1процессор 2процессор 3Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.23Метод конвейерного параллелизмапроцессор 0Москва, 2016 г.процессор 1процессор 2процессор 3Параллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.24Метод конвейерного параллелизмапроцессор 0Москва, 2016 г.процессор 1процессор 2процессор 3Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.25Метод конвейерного параллелизмапроцессор 0Москва, 2016 г.процессор 1процессор 2процессор 3Параллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.26Метод конвейерного параллелизмапроцессор 0Москва, 2016 г.процессор 1процессор 2процессор 3Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.27Метод конвейерного параллелизмапроцессор 0Москва, 2016 г.процессор 1процессор 2процессор 3Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.28Метод конвейерного параллелизмапроцессор 0Москва, 2016 г.процессор 1процессор 2процессор 3Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.29Метод конвейерного параллелизмапроцессор 0Москва, 2016 г.процессор 1процессор 2процессор 3Параллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.30Метод конвейерного параллелизмапроцессор 0Москва, 2016 г.процессор 1процессор 2процессор 3Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.31Метод конвейерного параллелизмапроцессор 0Москва, 2016 г.процессор 1процессор 2процессор 3Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.32Метод конвейерного параллелизмапроцессор 0Москва, 2016 г.процессор 1процессор 2процессор 3Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.33Метод конвейерного параллелизмаT1 (kn) = τ c knS p (kn) = pМосква, 2016 г.1τs1+τcnkn+ k τsT p (kn) = τ cpp1E p (kn) =τs1+τcПараллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.34Метод конвейерного параллелизмапроцессор 0процессор 1процессор 2T1 (kn) = τ c kn1S p (kn) = pp τs1+ 2n τcМосква, 2016 г.процессор 3kn+ 2kτ sTp (kn) = τ cp1E p (kn) =p τs1+ 2n τcПараллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.35Объём хранимых данныхпроцессор 0процессор 1процессор 2T1 (kn) = τ c kn1S p (kn) = pp τs1+ 2n τcМосква, 2016 г.процессор 3kn+ 2kτ sTp (kn) = τ cp1E p (kn) =p τs1+ 2n τcПараллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.36Учет стартовых и финальных затратпроцессор 0Москва, 2016 г.процессор 1процессор 2процессор 3Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.37Учет стартовых и финальных затратМосква, 2016 г.Параллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.38Учет стартовых и финальных затратМетод эффективен приМаксимальная степень параллелизма:Максимальное ускорение:Москва, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.39Диффузная балансировкаПричины дисбаланса вычислительной нагрузки– Разные процессоры– Внешнее воздействие– Разная вычислительная сложность заданийРезультат дисбаланса– Эффективная производительность определяетсясамым медленным процессоромМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.40Медленный процессорКакой объем работ забрать у среднегопроцессора и кому его передать?Москва, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.41Метод геометрического параллелизмаМосква, 2016 г.Параллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.42Метод геометрического параллелизмаМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.43Диффузная балансировка загрузкиМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.44Диффузная балансировка загрузкиМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.45Диффузная балансировка загрузкиМосква, 2016 г.Параллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.46Статическое распределениеМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.47Постановка задачи диффузной балансировкиДано:• Количество точек – N• Количество процессоров – p• Процессор i обработал ni точек за время ti• Для обработки любой точки требуется одинаковое числооперацийТребуется:• Найти количества точек n’i , которое следует обработатьпроцессорам на следующем шаге• Определить сколько точек каждый из процессоров долженпередать соседним процессорамМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.48Диффузная балансировкаn =N'initip −1∑j =0njtjВ предположении одинаковой трудоёмкости обработки каждой из точекМосква, 2016 г.Параллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.49Диффузная балансировкаn =N'initip −1∑j =0njtjВ предположении одинаковой трудоёмкости обработки каждой из точекМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.50Простые алгоритмыСтатическая и динамическая балансировказагрузки процессоров– Статическая балансировка• метод сдваивания• геометрический параллелизм• конвейерный параллелизм– Динамическая балансировка• коллективное решение• диффузная балансировкаМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.51ЗаключениеОтмечена важность использования простых слогической точки зрения алгоритмов Рассмотрен метод коллективного решения,относящийся к классу методов динамическойбалансировки загрузки процессоров Рассмотрены методы динамическойбалансировки загрузки процессоров:– метод коллективного решения– метод диффузной балансировки загрузкиРассмотрен метод конвейерного параллелизмаМосква, 2016 г.Параллельные высокопроизводительные вычисления.

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

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций