[МУЗЫКА] [МУЗЫКА] Здравствуйте, уважаемые слушатели. Мы с вами уже познакомились с частью функций библиотеки MPI, которые позволяют нам распределять вычислительную работу по процессам и организовывать взаимосвязь между этими процессами. А теперь давайте познакомимся с алгоритмом построения параллельных программ. Этот алгоритм включает в себя 4 основных этапа: декомпозиция, планирование коммуникаций, укрупнение и планирование вычислений. На этапе декомпозиции задача анализируется, производится оценка возможностей ее распараллеливания. Если задача поддается распараллеливанию, то она делится на более мелкие части фундаментальной подзадачи. Это, как правило, либо структуры данных более мелкие, либо более мелкие фрагменты алгоритма. В качестве примера можно рассматривать алгоритм вычисления скалярного произведения двух векторов a и b. Здесь, в качестве фундаментальной подзадачи, можно рассматривать произведение i-той компоненты вектора a и i-той компоненты вектора b. В общем случае количество фундаментальных подзадач должно быть хотя бы на порядок больше планируемого числа используемых процессов. При этом все фундаментальные подзадачи, по возможности, должны быть примерно одинакового размера. Так же желательно, чтобы при увеличения размера задачи увеличивался бы не размер фундаментальных подзадач, а их количество. Тогда мы сможем использовать большее количество процессов при распараллеливании. Важно, что на этом этапе не учитывается архитектура многопроцессорной вычислительной системы, для которой мы пишем программу, а анализируется только сам алгоритм. Декомпозиции бывают двух видов: функциональная декомпозиция и декомпозиция по данным. Рассмотрим пример функциональной декомпозиции. Пусть у нас есть два вектора a и b, и нам нужно вычислить их сумму, разность и скалярное произведение. Нулевому процессу мы дадим вычисление их суммы, первому процессу дадим вычисление их разности, а второму процессу дадим вычисление их скалярного произведения. Таким образом, каждый процесс будет занят решением своей задачи. Это у нас есть функциональная декомпозиция. Например, декомпозиция по данным — это наша задача с вычислением скалярного произведения. Продолжим. Следующий этап построения параллельной программы — это планирование коммуникаций. Здесь мы должны установить взаимосвязь между нашими фундаментальными подзадачами. И здесь преимущество имеют те алгоритмы, когда у нас у каждой подзадачи количество связей с другими подзадачами не очень велико. Желательно добиться, чтобы выполнялись следующие требования на связи между фундаментальными подзадачами. Во-первых, у каждой подзадачи должно быть примерно одинаковое количество связей с другими фундаментальными подзадачами. А во-вторых, объем передаваемых данных тоже должен быть примерно одинаков для каждой фундаментальной подзадачи. На этом этапе также не учитывается архитектура многопроцессорной вычислительной системы, а анализируются только свойства самого алгоритма. Нужно отметить, что упомянутые выше требования возникают из простых рассуждений. При распараллеливании мы всю вычислительную работу делим на имеющееся количество процессов. Допустим, их у нас p. Тогда мы ожидаем, что наша программа будет работать в p раз быстрее. Однако на практике мы часто будем сталкиваться, что между подзадачами нам нужно осуществлять обмены, и вот эти обмены мы должны подчинять упомянутым выше требованиям. Тогда у нас обмены будут требовать минимального количества времени. Для нашего примера со скалярным произведением все подзадачи связаны между собой линейно. Так как для получения общего результата, мы должны просуммировать все результаты, полученные в рамках фундаментальных подзадач. Следующий этап — это укрупнение. На этом этапе мы объединяем наши фундаментальные подзадачи в более крупные блоки. И здесь мы следуем одному простому правилу: мы стараемся самые связанные подзадачи определить в более крупный блок, и чтобы крупные блоки между собой были слабо связаны. На этом этапе мы уже учитываем архитектуру многопроцессорной вычислительной системы, а именно, количество укрупненных подзадач у нас должно совпадать с количеством имеющихся процессоров или вычислительных ядер. Для задачи вычисления скалярного произведение укрупнение происходит по следующей схеме, где n — это длина вектора, а p — это количество укрупненных подзадач. На этапе планирования вычислений осуществляется распределение укрупненных подзадач по процессорам. И есть две основные схемы распределения подзадач: это «хозяин–работник» и «децентрализованная» схема. В стратегии «хозяин–работник» главный процесс распределяет вычислительную работу или укрупненные подзадачи по процессам. Также главный процесс ответственен за сбор результатов решения. В «децентрализованной» схеме главный или управляющий процесс отсутствует, а все вычисления происходят по некоторой схеме. Мы свои учебные программы будем писать именно как децентрализованные. Таким образом, мы рассмотрели алгоритм построения параллельной программы. На практике, когда вы будете разрабатывать параллельный алгоритм, вы должны взять свою задачу и пройти все эти этапы. При прохождении этапов выделить фундаментальные подзадачи, посмотреть, как они связаны, и тогда вы сможете определить перспективность разработки параллельной программы именно для вашего алгоритма. На этом мы заканчиваем с темой введения в MPI. В рамках следующей темы мы будем более детально знакомиться с функциями библиотеки MPI и выяснять все особенности их использования. Спасибо за внимание и до следующей встречи.