Параллельное программирование: Учебное пособие, страница 10

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

Суммарное время решения конкретной задачи более точно можно получить при ее пробном прогоне на машине. Как правило других непредвиденных затрат времени здесь не наблюдается.

Затраты времени на решение распараллеленных задач включают в себя, кроме названных выше, времена, затрачиваемые на взаимодействия посредством общих данных, и времена, потраченные процессами на ожидание готовности данных.

Так как основной целью применения методов параллельного программирования для многопроцессорных систем является ускорение вычислений по сравнению с вычислениями на однопроцессорной вычислительной машине, то возникает естественное желание оценить, во сколько раз уменьшится время решения конкретной задачи, если будет использовано  процессоров [5].

Ускорением параллельного алгоритма называют отношение

.

где       – минимально возможное время выполнения самого длительного процесса распараллеленной задачи, которое в сетевых графиках параллельно выполняемых работ называют критическим путем;

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

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

1.7  Зерна параллельных алгоритмов

Каждая математическая модель объекта исследования, подлежащая численной обработке, обычно представляется совокупностью различных систем уравнений, соотношений и выражений, полученных на основании физических, естественнонаучных, социологических и прочих законов и эмпирических закономерностей. Вычислительные модели представляются специальными алгоритмами и методиками преобразования данных, относящимися к конкретным частям общей математической модели. Как правило, это крупные образования (крупные зерна) в общей математической модели, которые решают свои задачи по своим исходным данным и формируют свои наборы исходных данных для других задач. В пределах своих активных фаз эти образования не взаимодействуют с другими себе подобными зернами. В структурных исследованиях совокупности таких задач каждое зерно удобно представлять неким абстрактным элементом с точкой входа, точкой выхода и некоторым комплексным параметром, характеризующим локальный вычислительный процесс.

В свою очередь, каждая задача, ее алгоритм решения представляется множеством вычислительных блоков, использующих, преобразующих и формирующих некоторые наборы своих и общих данных. Обычно блоки обладают некоторой внутренней структурой, образованной отдельными или составными операторами. Такие наборы операторов на момент начала вычислений обладают своим набором исходных данных. К концу своей работы они подготовят данные для других блоков. Таким образом, отдельные блоки, отдельные операторы, которые начинают свои процессы по готовности входных данных и занимаются лишь тем, что преобразуют и готовят данные для других процессов, мы также можем отождествлять с некоторой абстракцией – зерном, но более мелким.

Понятие зерна и зернистости удобно для представления такой характеристики параллельного процесса как степень параллелизма. Своим комплексным параметром зерно характеризует протяженность локального процесса от момента пуска  до момента останова , который обобщенно можно именовать операцией, не задумываясь о величине зерна.