This site uses cookies.
Some of these cookies are essential to the operation of the site,
while others help to improve your experience by providing insights into how the site is being used.
For more information, please see the ProZ.com privacy policy.
This person has a SecurePRO™ card. Because this person is not a ProZ.com Plus subscriber, to view his or her SecurePRO™ card you must be a ProZ.com Business member or Plus subscriber.
Affiliations
This person is not affiliated with any business or Blue Board record at ProZ.com.
Russian to English: Optimization algorithm for an information graph for an amount of communications. General field: Tech/Engineering Detailed field: Computers (general)
Source text - Russian Алгоритм оптимизации информационного графа по объёму коммуникаций
Введение
Благодаря широкому распространению высокопроизводительных кластерных вычислительных систем стало актуальным использование процессоров с распределенной памятью. Вычисления в распределенной памяти отличны от вычислений в общей памяти тем, что в распределенной памяти для взаимодействия процессоров используется интерфейс передачи сообщений. Системы с распределенной памятью являются архитектурно более сложными устройствами, чем системы с общей памятью.
Для подобных систем, прежде чем создавать параллельную программу, необходимо знать общую архитектуру параллельной машины и топологию межпроцессорных связей, которая существенна для программирования. Это связано с отсутствием автоматического распараллеливания, которое позволяло бы превращать любую последовательную программу в параллельную и обеспечивало бы ее высокую производительность [26]. Нужно в явном виде увязывать структуру алгоритма решаемой задачи со структурой вычислительной системы и обеспечивать правильность взаимодействия множества параллельно независимых друг от друга процессов. [1]
В последнее время параллельным вычислениям было посвящено много работ. В целом все эти работы можно было бы условно разделить на ряд основных категорий: работы в области исследования параллельных алгоритмов, их структуры и качества [4, 6, 10]; развитие общей теории параллельного программирования [3, 5, 16]; решение частных прикладных задач [27]; работы, посвященные построению параллельных алгоритмов для задач узкого класса из некоторой области с примерами параллельных алгоритмов вычислительной математики [11]; работы, в которых были предложены формальные модели, позволяющие описывать функционирование последовательных процессов, исполняющихся параллельно[2, 9, 20]; решение проблем планирования вычислительного процесса [15, 18, 23] и др.
Достичь увеличения скорости вычислений, как известно, можно двумя путями. Первый способ: с помощью выбора высокоскоростной модификации архитектуры ЭВМ. Но возможности данного способа ограничены в силу своих физических особенностей. Второй способ – программный. При этом способе разработчику параллельной программы необходимо выбрать модель архитектуры, допускающее параллельную реализацию алгоритма и решить важный вопрос: как создать параллельную программу.
Сегодня разработчики параллельных программ разделились на два основных класса: тех, кто считает, что параллельную программу надо создавать «с нуля», без опоры на последовательные аналоги и тех, кто полагается на накопленных десятилетиями багаж последовательных программ.
И тот и другой подходы имеют свои достоинства и недостатки. Но оба подхода едины в одном: в необходимости проведения анализа структуры алгоритма на предмет эффективного использования вычислительных ресурсов и поиска возможностей ускорения процессов вычисления. Этот анализ может проводиться как предварительно в случае создания параллельного алгоритма на основе последовательного, промежуточно для получения информации об успешности параллельного выполнения, заключительно – для сравнения алгоритмов и их реализаций между собой.
Моделированию последовательных и параллельных алгоритмов уделяется достаточно внимания в последние несколько десятилетий.
В целом разработанные на сегодняшний день методы построения параллельных алгоритмов на многопроцессорных вычислительных системах [7, 8, 12, 14, 17, 24] не позволяют построить достаточно эффективные и быстродействующие программы, т.к. их отличительной особенностью является адаптация на конкретные задачи с конкретной архитектурой вычислительной системы.
Среди методов, позволяющих получить формальное и наглядное представление о возможных параллельных ветвях в алгоритмах можно выделить следующие методы: метод поиска взаимно независимых работ [13], метод определения ранних и поздних сроков выполнения операций алгоритма [13], методы составления расписаний, основанные на списках следования [22].
Последний из методов является наименее трудоемким. В этом методе существующий алгоритм разбивается на операции, строится информационный граф [25] и определяются характеристики: высота и ширина алгоритма (время и число процессоров, задействованных в вычислениях). Как у любого метода последний метод [22] обладает своими недостатками (необходимостью разбивать алгоритм на отдельные операции и строить граф информационных зависимостей между операциями) и своими достоинствами: в результате исследователь может однозначно увидеть объем вычислительных единиц, необходимых для распараллеливания, эффективность использования вычислительных единиц и самое главное, возможность параллельной реализации исследуемого метода в виде конкретного алгоритма.
Хочется отметить, что в зависимости от результата анализа структуры алгоритма, исследователь в любом случае, получит для себя ценную информацию:
- если алгоритм идеально распараллеливается при заданных ограничениях на время и объем вычислительных ресурсов, то исследователь получает модель будущей параллельной программы вместе с расписанием ее выполнения в заданной вычислительной среде.
- если алгоритм возможно распараллелить, но в исходном виде он имеет узкие места, такие как, например, простои вычислительных единиц или требование вычислительных ресурсов в большем объеме, чем они имеются в наличии, то на основе полученных метаданных исследователь может применить существующие алгоритмы оптимизации параллельных алгоритмов и получить желаемую модель будущей параллельной программы.
- если результаты анализа наихудшие, т.е. алгоритм практически не распараллеливается, то исследователь как минимум экономит средства на разработку неэффективной параллельной программы, как максимум исследователь получает информацию о существующих проблемах в алгоритме и направлениях их решения.
Одним из показателей качества параллельной программы является плотность загрузки вычислительных узлов. Временные задержки при передаче данных по каналам связи от одного процессора к другому приводят к суммарно длительным простоям процессоров и увеличению в целом времени работы алгоритма.
В данной статье предлагается метод построения эффективного алгоритма по числу использованных процессоров, времени выполнения алгоритма и объему межпроцессорных передач. Данный метод может быть применен как к последовательным алгоритмам для получения их параллельного аналога, так и к параллельным алгоритмам с целью повышения их качества.
Постановка задачи
Любой алгоритм последовательный или параллельный представляет собой сложную многосвязную систему с целым набором параметров, влияющих на качество работы этой системы. Оптимизировать работу алгоритма сразу по многим параметрам – не легкая задача, но задача, которая может быть поэтапно решена.
В данной статье приведены результаты первого этапа решения задачи получения расписания выполнения алгоритма, соответствующего заданному информационному графу. Алгоритм должен быть оптимальным по объему межпроцессорных передач при следующих ограничениях на оптимизируемый алгоритм и вычислительную систему:
- вычислительная система неограниченна по количеству процессоров (ядер);
- каждая операция обладает одинаковым объемом входных данных;
- все операции выполняются за одинаковое время, условно равное 1 ед.;
- время передачи данных между двумя любыми процессорами является постоянным, условно равным 1 ед.
Очевидно, что на практике, алгоритмов и вычислительных систем с такими характеристиками не существует, но эта модель параллельного алгоритма является начальной стартовой моделью для получения метода оптимизации параллельных алгоритмов по времени выполнения с учетом совокупности метаданных самого алгоритма и вычислительной среды.
Рассмотрим пример. Пусть задан информационный граф алгоритма (рис.1).
Рисунок 1. – Информационный граф алгоритма
После распределения вершин графа по ярусам с применением метода оптимизации информационного графа по ширине на основе матрицы смежности или списков смежности [22] получим следующие соответствующие ярусам начальные группы вершин графа (рис.2):
Рисунок 2. – Начальное расписание алгоритма
Если по полученным группам мы построим расписание выполнения алгоритма на вычислительной системе с учетом межпроцессорных передач данных, то оно будет следующим (рис.3):
Рисунок 3. – Временная диаграмма алгоритма с учетом времени межпроцессорной передачи данных.
где Pi – номер процессора, i=(1,6) ̅; символ подчеркивания ‘_’ – простой процессора («пузырь») в ожидании получения входных данных от других операций.
В соответствии с этим расписанием общее время работы алгоритма t=10, число процессоров n=6, суммарный объем простоев p=16.
С целью определения возможности выровнять плотности вычислений процессоров определим теоретическую минимальную ширину информационного графа: Dmin=4.
В нашем случае, ширина информационного графа после начального распределения вершин по ярусам, соответствует максимальному числу вершин по группам, и равна 6. Следовательно, существует возможность оптимизировать данный граф по ширине.
Применяя алгоритм оптимизации по ширине (по числу процессоров), получим группы, размер которых соответствует оптимальному параметру Dmin=4 (минимальной ширине информационного графа):
Следует отметить, что это не единственный вариант разбиения множества вершин по группам. Возможны и другие варианты. Всё зависит от выбранного метода оптимизации по ширине.
Преобразуем в соответствии с полученными группами временную диаграмму алгоритма (рис.4):
Рисунок 4. – Временная диаграмма алгоритма после оптимизации по ширине.
При этом расписание изменится следующим образом:
В соответствии с этим расписанием общее время работы алгоритма t=10, число процессоров n=4, суммарный объем простоев p=12.
Полученное расписание лучше начального (см.рис.3), т.к. позволяет для реализации алгоритма использовать вычислительную систему с меньшим числом процессоров, сохранив при этом общее время выполнения алгоритма и сократив простои процессоров.
Метод оптимизации алгоритма по объему коммуникаций
По приведенным диаграммам видно, что время, затрачиваемое на передачу данных, увеличивает время работы процессоров и суммарное время работы алгоритма.
Приведенные примеры согласуются с известным фактом, что функция ускорения вычислений алгоритма на системе из n вычислительных устройств F(n) имеет график нормального распределения (рис.5):
Рисунок 5. – График зависимости ускорения вычислений от числа процессоров, где K – ускорение, n - процессоры.
Начиная с некоторого n, ускорение вычислений падает за счет роста объема передачи данных. А для некоторых алгоритмов эта зависимость является линейной убывающей функцией, например параллельный вариант алгоритма пузырьковой сортировки работает медленнее исходного последовательного метода, т.к. объем передаваемых данных между процессорами является достаточно большим и сопоставим с количеством выполняемых вычислительных операций (и этот дисбаланс объема вычислений и сложности операций передачи данных увеличивается с ростом числа процессоров) (рис.6) [13].
Рисунок 6. – График зависимости ускорения вычислений от числа процессоров для алгоритма пузырьковой сортировки.
Следовательно, следующим шагом на пути получения оптимального по времени выполнения алгоритма является уменьшение объема межпроцессорных передач.
Предлагаемый авторами Метод оптимизации информационного графа по объёму коммуникаций заключается в следующем:
Положить за основу группы вершин, соответствующих ярусам, полученные произвольным способом. Лучше, если эти группы будут получены формализованным способом, например, методом оптимизации информационного графа по ширине с помощью матрицы или списка смежности.
Процесс перестановки вершин начинается с последней группы. Допустим всего групп m, тогда номер очередной группы k=m.
В первую очередь необходимо в расписание поставить (с учётом групп) вершины у которых бинарная связь. И только потом расставлять вершины с множественными связями, т.к., в этом случае существование пузыря неизбежно.
В k-й группе выбрать первую вершину. Считать номер позиции этой вершины в группе равным 1: i=1.
Сравнить вершину Mki (где i – номер позиции вершины в группе) с вершинами предыдущей (k -1)-й группы. Если в (k -1)-й группе существует вершина (Mk-1j, где j – номер позиции вершины в группе, j>=i ) напрямую связанная в информационном графе ребром с данной вершиной, то вершину Mk-1j, необходимо переместить в своей группе в i-ю позицию. Если в (k -1)-й группе нет вершины, связанной с вершиной Mki, то шаг 6.
Если k >2, то k= k-1 и шаг 4
Если в m-й группе перебраны еще не все вершины, то k=m, i=i+1 и шаг 4.
Если в последней группе перебраны все вершины и m >2, то m =m-1 и шаг 6.
Если m =1, то конец метода.
Пример. Для информационного графа с рис. 1 возьмем за основу группы, полученные после оптимизации графа по ширине:
После применения метода оптимизации расписания по объему коммуникаций, получим следующие группы для каждого яруса:
Временная диаграмма для полученных групп с учетом информационного графа (рис.1) примет вид (рис.7):
Рисунок 7. – Временная диаграмма оптимизированного алгоритма по объему коммуникаций.
При этом расписание изменится следующим образом:
Пересчитав объём коммуникаций получим, что время, затрачиваемое на передачу данных с одного процессора на другой, уменьшилось в два раза и стало равным 8 ед., против 16 ед. начальных.
Суммарное время работы алгоритма уменьшилось с 10 до 9.
Оценка времени выполнения алгоритма с учетом степени связности вершин информационного графа
Любая модификация алгоритма занимает время, которое можно было бы с пользой потратить на решение других более значимых задач. Поэтому, прежде чем, проводить оптимизацию алгоритма, всегда хотелось бы знать ответ на такой вопрос как: что исследователь получит в результате оптимизации, будет ли новый алгоритм лучше прежнего.
В процессе исследования коммуникационных зависимостей и их влияния на общее время алгоритма нам удалось получить оценку минимального общего времени выполнения алгоритма, которая вычисляется по следующей формуле:
t_min=∑_(k=1)^m▒M+2∑_(k=1)^m▒M_c . (1)
где, t_min - минимальное общее время алгоритма, которое может быть достигнуто при оптимизации расписания по объему межпроцессорных коммуникаций, k = (1,m) ̅., m – число групп графа, M – число групп, содержащих вершины только с бинарными связями входных данных, M_c – число групп, в которых хотя бы одна вершина имеет более одного входящего в нее ребра (множественные связи).
Пример: для упрощения расчетов поставим в соответствии каждой вершине вес, т.е. число: 0 – если вершина имеет только одно, входящее в нее ребро, 1 – более одного входящего ребра. Получим таблицу:
№ вершины 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
вес 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 1
Поставим в соответствии каждой группе вес: 0 – если в группе только вершины с весом 0, т.е. с одной входящей вершиной и 1 – в противном случае:
Для расписания, соответствующего рис.2, получим:
№ группы 1 2 3 4 5 6
вес 0 0 1 1 1 1
Теперь рассчитаем время выполнения алгоритма по формуле 1:
t_min=∑_(k=1)^m▒M+2∑_(k=1)^m▒M_c .=2+2∙4=10
Таким образом, без построения диаграммы, только по данным, полученным с информационного графа мы можем судить о времени работы алгоритма.
Для расписания, соответствующего диаграмме с рис.7, время выполнения составит:
t_min=∑_(k=1)^m▒M+2∑_(k=1)^m▒〖M_c=3+2∙3=9〗.
С помощью формулы 1 можно рассчитать и теоретически возможное время выполнения алгоритма: вершин с весами, равными 1 всего 6. Значит в идеальном расписании их можно уложить в две группы, которые также будут иметь веса, равные 1. Значит, оставшиеся 4 группы будут иметь веса, равные 0. Подставив в формулу 1 значения М=4 и Мс=2, получим, что время работы алгоритма, теоретически возможно уменьшить до 8 ед.:
t_min=∑_(k=1)^m▒M+2∑_(k=1)^m▒〖M_c=4+2∙2=8〗.
К сожалению, информационные зависимости между вершинами не всегда позволяют получить идеальное время работы алгоритма.
Укрупнение операций
Казалось бы, что логичным решением является предоптимизационное укрупнение операций с целью уменьшения общего числа операций с весом, равным 0. Это позволит избежать случайного разбивания линейной цепочки операторов по разным процессорам и появления новых пузырей.
Возьмем за основу информационный граф с рис.1 и укрупним его операции путем слияния вершин с весом 1, непосредственно связанных друг с другом. В результате получим следующую совокупность вершин:
где: номер вершины i’ – это новый номер, а совокупность вершин, заключенных в квадратные скобки – это прежние вершины, которые были объединены в одну новую вершину.
В результате информационный граф с рис.1 примет вид:
Рисунок 8. – Информационный граф алгоритма с укрупненными вершинами
Построив для этого графы группы вершин, получим следующие результаты: количество необходимых процессоров – 4, количество групп - тоже 4:
Этим группам будет соответствовать временная диаграмма (рис.9):
Рисунок 9. – Временная диаграмма алгоритма после укрупнения операций.
При этом расписание изменится следующим образом:
В соответствии с этим расписанием общее время работы алгоритма t=10, число процессоров n=4, суммарный объем простоев p=6.
Оптимизация по ширине и по коммуникациям в данном случае к уменьшению числа процессоров и времени работы алгоритма не приводит, но позволяет несколько сократить объем пузырей.
Выводы
Метод оптимизации информационного графа по объему коммуникаций позволяет уменьшить объём коммуникаций между процессорами и соответственно сократить время выполнения всего алгоритма.
Достоинствами данного метода являются:
- Низкая временная трудоемкость O(md2), где m – число групп, d – ширина графа.
- Возможность работы не с разреженной матрицей смежности, а со списком смежности, что значительно ускоряет процесс расчета расписаний и экономит память.
- Сохранение информационных зависимостей.
- Сохранение начальной ширины информационного графа.
- Возможность комбинирования данного метода с другими методами оптимизации.
Метод оптимизации алгоритма по объему межпроцессорных передачи данных эффективно применять в соответствии со следующей методикой:
Разбить алгоритм на операции.
Построить информационный граф алгоритма.
Построить параллельную форму информационного графа и временную диаграмму алгоритма.
Провести оптимизацию по ширине (по числу процессоров).
Провести оптимизацию по межпроцессорным коммуникациям.
Провести укрупнение операций.
Применение метода оптимизации алгоритма по объему межпроцессорных передачи позволяет достичь более высокого уровня производительности, эффективности и высокоскоростной обработки параллельных программ.
Следует также отметить, что данный метод является отправной точкой при создании более совершенного метода, учитывающего не только объем входящих в заданную вершину ребер, но и непосредственно объем передаваемых данных, длину пути, время работы каждой операции.
Translation - English Optimization algorithm for an information graph for an amount of communications.
Introduction
The use of distributed memory processors has become of current concern due to the wide spreading of high-performance cluster computing systems. The computing in a distributed memory is different from the computing in a shared memory, because in a distributed memory a message passing interface is used. Distributed memory systems are more architecturally complicated devices than shared memory systems.
For such systems it is necessary to have knowledge of a parallel computer general architecture and the essential for the programming topology of interprocessor communications before the creation of a parallel program. This is because of the absence of an automatic parallelization that affords to turn any sequential program into a parallel one and maintains its high performance [26]. The structure of an algorithm of the current task has to be connected explicitly with structure of a computing system and the communication among many parallel, independent processes has to be valid. [1]
In recent times many researches were devoted to parallel computing. As a whole, these researches may be conventionally divide into the range of main categories: researches of parallel algorithms, their structure and quality [4, 6, 10]; the development of the general theory of parallel programming [3, 5, 16]; handling of applied partial problems [27]; researches devoted to the development of parallel algorithms for restrictive class tasks of some area, with parallel algorithms of computing mathematics examples [11]; researches those include formal models letting to describe the functioning of sequential processes executed simultaneously [2, 9, 20]; resolving problems of sequencing [15, 18, 23] etc.
As is known, the computing speed may be increased in two ways. The first way is to choose the high-speed modification of computer architecture. But this way is of the little scope because of its physical features. The second way is program. The program builder using this way has to choose the architecture model that allows the parallel algorithm realization and to settle the important issue of the creation of a parallel program.
Nowadays parallel programs builders divides into two clauses: those who thinks that a parallel program has to be built from the ground up without using of sequential analogues, and those who depends upon accumulated for decades bundle of sequential programs.
Both approaches have their advantages and disadvantages. But both approaches are united in one issue: the necessity of the analysis of the algorithm structure for the effective use of computing resources and the looking for opportunities for the speed-up of computing processes. This analysis may be conducted whether previously in the case of the creation of a parallel algorithm on the base of sequential one, or in an intermediate way for the obtaining of the information on the success of parallel execution, or finally for the comparison of algorithms and their implementation against each other.
In the past few decades the modeling of sequential and parallel algorithms are the object of intense interest.
As a whole, worked out nowadays methods of the building of parallel algorithms on multiprocessing systems [7, 8, 12, 14, 17, 24] do not let to built rather effective and high-performance programs, because their feature is the adaptation for concrete tasks with a concrete architecture of a computing system.
Among methods those let to get the proper idea of possible parallel branches of algorithms the following may be mentioned: the method of the search of mutually independent activities [13], the method of the definition of early and old terms of the execution of operations of an algorithm [13], methods of timetabling based on a movement list [22].
The last method is the least laborious. In according with this method, the existing algorithm has to be subdivided into operation, the information graph has to be built [25], features (height and width of algorithm (the time and the quantity of processors, used in calculations) have to be defined. As every method, the last one [22] has its disadvantages (the necessity to subdivide algorithm into separate operations and to build the graph of information dependences between operations) and its advantages: the researcher can observe the amount of locales those are necessary for the paralleling, the effectiveness of the use of locales and ultimately the possibility of the parallel realization of the suspected method, used in the shape of a concrete algorithm.
The remarkable thing is that depending on the result of the analysis of the algorithm structure, a researcher will get valuable information anyway:
- if the algorithm can be paralleled ideally at prescribed constraints of the time and the amount of computing resources, the researcher will get the model of the future parallel program with the timetable of its execution in the prescribed computing environment.
- if the algorithm may be paralleled, but it has headaches in original shape as, for example, downtimes of locales or the requirement for computing resources in amount, more than available, the researcher will can use existed algorithms of the optimization of parallel algorithms on the base of obtained metadata and to get the desirable model of a future parallel program.
- if results of the analysis is the worst i.e. the algorithm cannot be paralleled scarcely, the researcher will economize funds on the building of ineffective parallel program at least, and will get the information on existing problems in the algorithm and ways of its correction as maximum.
One of quality parameters of a parallel program is the loading density of compute nodes. Time delays at data channeling from one processor to another one leads to summarily length processors downtimes and increasing of the whole algorithm execution.
In the present article the method of the development of the effective algorithm of used processors quantity, algorithm execution time and the scope of interprocessor transitions is devised. This method can be used not only for sequential algorithms for the obtaining of their parallel analogous, but for parallel algorithms for the improvement of their quality.
Problem description
Any sequential or parallel algorithm is a complicated multicoupling system with a set of parameters having an impact on the operating quality of this system. Multiparameter optimization of the performance of the algorithm is a rather complicated task, but the task that may be completed gradually.
In this article results of the first stage of the completion of the task of the obtaining of the timetable of the execution of the algorithm of an indicated information graph are presented. The algorithm has to be optimal for the interprocessor transfer size at following restrictions of optimized algorithm and computing system:
- The quantity of processors (bases) of the computing system is unrestrained;
- Input data of each operation are equal;
- All operations have the same time of execution conventionally equal to 1 item;
- Time of the data transfer between any two processors is constant and conventionally equal to 1 item.
Obviously that there are no algorithms and computing systems of such characteristics in practice, but this model of parallel algorithm is a start model for the obtaining of the method of parallel algorithms execution time optimization with account of the metadata package of the algorithm itself and the computing system.
Consider the following example. Suppose this information graph of the algorithm is defined (fig.1).
Figure 1. – Information graph of the algorithm
After the distribution of graphs points over tiers with the application of the method of the optimization of the graph for the width on the base of the connectivity matrix or adjacency lists [22] we shall following following according to tiers initial groups of points of the graph (fig.2):
Figure 2. – Initial timetable of the algorithm
If we build the timetable of the algorithm by obtained groups on the computing system with account of interprocessor data transfer, it will be of the following shape (fig.3):
Figure 3. – Timing diagram of the algorithm with account of the duration of the interprocessor data transfer,
where Pi is the number of the processor, i=(1,6) ̅; the symbol of the underlining ‘_’ is the down time of the processor (the “bubble”) waiting for obtaining of new input data from other operations.
In accordance with this timetable, the whole duration of the activity of the algorithm t=10, the quantity of processors n=6, total amount of down time p=16.
For the definition of the possibility to fit the compute density of processors, we shall define hypothetically minimal width of the informational graph: Dmin=4.
In our case, after the initial distribution of points over tiers, width of the information graph corresponds to the maximal quantity of points groupwise and is equal to 6. Therefore, there is the possibility to optimize this graph for the width.
If we use the algorithm of the optimization for the width (for the quantity of processors), there will be groups those sizes correspond to the optimal parameter Dmin=4 (the minimal width of the information graph):
It should be noted that it is not the only variant of the subdivision of the set of points into groups. Other variants are possible two. This depends on the chosen method of the optimization for the width.
Let us transfer the timing diagram of the algorithm in conformity with obtained groups (fig.4):
Figure 4. – Timing diagram of the algorithm after the optimization for the width.
At that, the timetable will change in the following way:
According to this timetable, the whole duration of the activity of the algorithm t=10, the quantity of processors n=4, the whole down time p=12.
The obtained timetable is better than initial one (ref. fig.3), because it lets to use computing system of less quantity of processors for the implementation of the algorithm while keeping the whole duration of the implementation of the algorithm and decreasing the downtime of processors.
Method of the algorithm optimization for the amount of communications.
It is clear from provided diagrams that the time sent for the data transfer increases the duration of processors activity and the whole duration of the activity of the algorithm.
Provided examples are consistent with the known fact that the function of the computational speedup of the algorithm on the system of n computing devices F(n) has the following normal probability plot (fig.5):
Figure 5. – Graph of the dependency of computation speedup on the quantity of processors, where K is the speedup, n is processors.
The computation speedup begins from some n and droops due to the increase of the amount of data transfer. For some algorithms this dependency is the linear decreasing function; for example, the parallel version of the bubblesort acts slower than the initial sequential method because the amount of data transferred between processors is rather large and is comparable with the quantity of executable computing operations (and this unbalance of the amount of computing and complexity of data transfer operations increases with the growth of the quantity of processors) (fig.6) [13].
Figure 6. – Graph of the dependency of computing speedup on the quantity of processors for the bubblesort algorithm.
Therefore, the next step towards the obtaining of the optimal to the execution time algorithm is the decrease of the amount of data transfers between processors.
The offered by authors method of information graph optimization for the amount of communications consists of following:
To place at the center the group of points corresponded to tiers, obtained in arbitrary way. It will be better if these groups are obtained in a formalized way, for example, by the method of the optimization of the information graph for the width by means of a matrix or an adjacency list.
The process of the replacement of points begins with the last group. Assume that there are m groups, then the number of the subsequent group will be k=m.
Primarily, it is necessary to put points with binary relationships into the timetable (with account of groups). And only after that we have to allocate points with multiple relationships because in this case the presence of the bubble is inevitable.
In the k-th group to chose the first point. The number of the position of this point in the group to consider to be equal to 1: i=1.
To compare the point Mki (where i is the number of the position of the point in the group) with points of the previous (k -1)-th group. If in the (k -1)-th group there is the point (Mk-1j, where j is the number of the position of the point in the group, j>=i ) connected with the assigned point directly by the edge in the information graph , it will be necessary to move the point Mk-1j to the i-th position in its group. If in the (k -1)-th group there is no point, connected with the point Mki then ref. step 6.
If k >2 then k= k-1 and ref. step 4
If in the m-th group there are points those have not been analyzed, then k=m, i=i+1 and ref. step 4.
If in the last group all points have been analyzed and m>2, then m =m-1 and ref. step 6.
If m =1 then the method is ended.
Example: for the information graph of the fig. 1 let us base on groups obtained after the optimization of the graph for the width:
After the use of the method of the timetable optimization for the amount of communication, we shall obtain following groups for each tier:
The timing diagram of obtained groups with account of the information graph (fig.1) will be of the following shape (fig.7):
Figure 7. – Timing diagram of the algorithm optimized to the amount of communications.
At that the timetable will change as follows:
If we recalculate the amount of communications, we shall recognize that the lost of the time of the data transfer between processors has grown twice less and become equal to 8 items instead of initial 16 items
The total execution time of the algorithm has grown less from 10 to 9.
Estimate of the execution time of the algorithm with account of the degree of the continuity of information graph points.
Any modification of the algorithm takes a time that may be spent for the solution to other, more important problems. That’s why, before the algorithm optimization it would be desirable to know what shall a researcher obtain as a result of the optimization and will the new algorithm be better than previous one.
While researching communication dependencies and their influence on the algorithm whole execution time, we managed to get the estimation of the minimal algorithm whole execution time that should be calculated from the following formula:
t_min=∑_(k=1)^m▒M+2∑_(k=1)^m▒M_c . (1)
where t_min is the minimal algorithm whole execution time that may be achieved by the optimizing of the timetable for the amount of communication between processors, k = (1,m) ̅., m is the quantity of groups of the graph, M is the quantity of groups containing points with input data binary relationships only, M_c is the quantity of groups, where even one point has more than one edge in it (multiple relationships).
Example: for the approximation of calculation, let us assign the weight to each point, i.e. the figure 0 for a point with only one edge in it and the figure 1 for a point with more edges in it. The following table will be created:
No. of the point 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
weight 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 1
Let us assign the weight to each group: the figure 0 for a group with points of the weight 0 i.e. with only one input point in it and the figure 1 otherwise:
For the timetable corresponded to the fig.2, the following table will be created:
No. of the group 1 2 3 4 5 6
weight 0 0 1 1 1 1
Let us calculate the algorithm execution time using the formula 1:
t_min=∑_(k=1)^m▒M+2∑_(k=1)^m▒M_c .=2+2∙4=10
Therefore, we can make assertions about the algorithm execution time on the base of data from the information graph only, without the construction of a diagram.
For the timetable corresponded to the diagram of the fig.7 the time of the execution may be calculated using the following formula:
t_min=∑_(k=1)^m▒M+2∑_(k=1)^m▒〖M_c=3+2∙3=9〗.
Using the formula1, theoretically possible algorithm execution time may be calculated. There are 6 points of the weight equal to 1. Therefore, in an ideal timetable they may be subdivided into two groups of weights equal to 1. Therefore, the rest 4 groups are of the weight equal to 0. If we substitute values М=4 and Мс=2 to the formulae 1, we shall discover that theoretically the algorithm execution time may be reduced to 8 items:
t_min=∑_(k=1)^m▒M+2∑_(k=1)^m▒〖M_c=4+2∙2=8〗.
Unfortunately, information dependencies between points do not let to obtain ideal algorithm execution time always.
Upsizing of operations
Upsizing of operations before the optimization for the reducing of the quantity of operations of the weight equal to 0 seems to be the logical decision. This lets to escape an accidental break of a linear chain of operators between different processors and appearance of new bubbles.
Let us take as a basis the information graph of the fig.1 and upsize its operations by the joining of directly interrelated points of the weight of 1. As a result, we shall obtain the following collection of points:
where: the number of the point i’ is the new number and the collection of points in square brackets is previous points those were joined into one new point.
As a result, the information graph of the fig.1 shall assume the following shape:
Figure 8. – Information graph of the algorithm with upsized points.
If we build groups of point for this graph, we shall obtain following results: the quantity of necessary processors is 4, the quantity of groups is 4 too.
The timing diagram will correspond to these groups (fig.9):
Figure 9. – Timing diagram of the algorithm after the upsize of operations.
At that the timetable shall change as follows:
In conformity with this timetable, the whole algorithm execution time t=10, the quantity of processors n=4, total down time amount p=6.
In this case, the optimization for the width and communications does not lead to the reduction of the quantity of processors and algorithm execution time but allows to decrease slightly the amount of bubbles.
Conclusion
The method of information graph optimization for the amount of communications allows to reduce the amount of communications between processors and, therefore, to reduce the whole algorithm execution time.
Advantages of this method are:
- Low timing labor content O (md2), where m is the quantity of groups, d is the width of the graph.
- The possibility to work not with the sparse connectivity matrix, but with the adjacency list. This possibility speeds up the process of the timetable calculation process and economizes a memory.
- Preservation of information dependencies.
- Preservation of the initial width of the information graph.
- Possibility to combine this method with other optimization methods.
It would be effective to use the method of an algorithm optimization for the amount of data transfer between processors in accordance with the following methodology:
To subdivide the algorithm into operations.
To build an information graph of the algorithm.
To build the parallel form of the information graph and the timing diagram of the algorithm.
To realize the optimization for the width (the quantity of processors).
To realize the optimization for interprocessor communications.
To realize the upsizing of operations.
The use of the method of an algorithm optimization for the amount of interpocessor data transfer allows achieving the higher level of performance, effectiveness and high-speed processing of parallel programs.
It is to be noted that this method is the starting point for the creation of a higher-end method considering not only the amount of edges in the specified point, but, immediately, amount of transferred data, length of the way, and duration of the execution of each operation.
More
Less
Experience
Years of experience: 12. Registered at ProZ.com: Oct 2013.
Russian to English (The Moscow Institute of Linguistics, Moscow, Russi)
Memberships
N/A
Software
Adobe Acrobat, Adobe Photoshop, IBM CAT tool, Idiom, LogiTerm, Microsoft Excel, Microsoft Word, Mymemory Tstream Editor, Adobe (Premiere, Audition, Passolo, SDLX, Trados Studio
Portfolio