Кафедра вычислительных систем
Допустить к защите
зав. кафедрой д.т.н. доцент
___________ Курносов М.Г.
Федеральное агентство связи
Федеральное государственное бюджетное образовательное учреждение высшего образования
«Сибирский государственный университет телекоммуникаций и информатики»
(СибГУТИ)
ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА БАКАЛАВРА
Разработка средств визуализации выполнения алгоритмов коллективных обменов в вычислительных системах
Пояснительная записка
Студент: Чернецов В.С.
Факультет ИВТ Группа ИС-341
Руководитель д.т.н. доцент Курносов М.Г.
Новосибирск - 2017
Содержание
1 Введение 4
2цели и задачи дипломного проекта 6
2.1 Цели 6
2.2 Постановка задачи 6
3используемые средства разработки 8
3.1 Технология Canvas 8
3.2 Язык программирования JavaScript 9
4Стандарт MPI 11
1Описание MPI 11
2Операции MPI 12
3Анализ алгоритмов 15
средство визуализации 17
4Проектирование приложения 17
5Реализация функциональной части приложения 18
6Тестирование приложения 24
Заключение 25
Приложение А 26
Приложение Б 27
1 Введение
Важной задачей в разработке параллельных программ является выбор средств их программной реализации и исследования.
Эффективное исследование многопроцессорных вычислительных комплексов требует наличия средств разработки параллельных программ. Такие средства включают в себя языки параллельного программирования, библиотеки функций и подпрограмм, средства отладки и оценки производительности.
В настоящее время созданы десятки систем параллельного программирования. Среди них можно назвать следующие: OpenMP, Pthreads, MPI.
MPI (Message Passing Interface) – интерфейс передачи сообщений.
MPI реализует модель передачи сообщений, содержат функции и подпрограммы для стандартных языков программирования, таких как C, C++, FORTRAN, обеспечивают взаимодействия «точка – точка» и коллективный обмен.
Стандарт на программный интерфейс передачи сообщений MPI был разработан в 1994 г. группой MPI FORUM. В настоящее время принята новая версия стандарта MPI-3.1
-
цели и задачи дипломного проекта
2.1 Цели
Цель данной квалификационной работы – разработка средств визуализации выполнения алгоритмов коллективных обменов в вычислительных системах.
С помощью разработанного ПО можно получить следующую информацию:
Информацию о работе алгоритма.
Оценочное время работы алгоритма.
Анимацию выполнения алгоритма.
2.2 Постановка задачи
Разработать средства визуализации выполнения алгоритмов коллективных обменов в вычислительных системах. Средство визуализации должно содержать следующие возможности:
Просмотр описания алгоритмов
Видеть все этапы выполнения алгоритмов
Увидеть оценку времени выполнения алгоритм
Требования к приложению:
Работа в среде Web-браузера
Функционирование без настройки Web-сервера
Кроссбраузерность
-
используемые средства разработки
3.1 Технология Canvas
Canvas – элемент HTML 5, предназначенный для создания растрового изображения при помощь скриптов, написанных на языке JavaScript. Начало отсчета блока находится слева сверху. От него строится каждый элемент блока. Размер пространства не обязательно отражает размер фактической отображаемой площади.
Используется, как правило для отрисовки графиков, в некоторых случаях используется в браузерных играх. Также используется для встраивания видео контента на страницу.
Основные возможности элемента Canvas
Позволяет разместить – изображение, видео, текст.
Залить все сплошным цветов.
Добавление теней, похожих на свойство CSS3 box-shadow.
Отрисовка фигур с помощью указанных контрольных точек.
Большинство браузеров самостоятельно оптимизируют анимацию, идущую одновременно, уменьшив число вызовов reflow и repaint до одного, что в свою очередь приведет к повышению точности анимации. Например, анимации на JavaScript, синхронизированные с CSS transition. Плюс ко всему если выполняется анимация в другой вкладке, браузер не будет продолжать отрисовку для меньшего использования CPU, GPU, памяти.
Преимущества Canvas
В отличии от SVG гораздо удобнее иметь дело с большим числом элементов.
Имеет аппаратное ускорение.
Есть возможность манипулировать каждым пикселем.
Можно применять фильтры обработки изображений.
Существует большое множество библиотек для работы с Canvas.
Недостатки Canvas
Чрезмерно нагружает процессор и оперативную память.
Из-за ограничения сборщика нет возможности очистить память.
Необходимо обрабатывать события с объектами.
Плохая производительность при высоком разрешении.
Отрисовка каждого элемента происходит отдельно.
Поддержка элемента Canvas различными браузерами представлена в таблице 1.
Таблица 1 - Поддержка Canvas различными браузерами
Браузер
|
Поддержка
|
Chrome
|
От 1.0 и выше
|
Firefox
|
От 1.5 и выше
|
IE
|
Не поддерживается
|
Opera
|
От 9.0 и выше
|
Safari
|
От 1.3 и выше
|
Листинг 1 - Пример добавления элемента Canvas на страницу
3.2 Язык программирования JavaScript
JavaScript-мультипарадигменный язык программирования. Поддерживает ООП и функциональный стили. Является реализацией языка ECMAScript.
JavaScript обычно используется как встраиваемый язык для программного доступа к объектам приложений. Наиболее широкое применение находит в браузерах как язык сценариев для придания интерактивности веб-страницам.
Основные характеристики JavaScript
Динамическая типизация
Слабая типизация
Автоматическое управление памятью
Прототипное программирование
Функции как объекты класса
Структурно JavaScript можно представить в виде объединения трех четко различимых друг от друга частей:
Ядро (ECMAScript)
Объектная модель браузера (BOM)
Объектная модель документа (DOM)
ECMAScript не является браузерным языком программирования и в нем не определяются методы ввода и вывода информации. Это основа для построения скриптовых языков. Спецификация ECMAScript описывает типы данных, инструкции, ключевые и зарезервированные слова, операторы, объекты, регулярные выражения.
Основное предназначение объектной модели браузера – управление окнами браузера и обеспечение их взаимодействия. Каждое окно представляется объектом window, центральным объектом DOM. Помимо управления окнами также обеспечивается поддержка следующих сущностей:
Управление фреймами
Поддержка задержки в исполнение кода и зацикливания с задержкой
Системные диалоги
Управление адресов открытой страницы
Управление информации о браузере
Управление информацией о параметрах монитора
Ограниченной управление историей просмотра страниц
Поддержка работы с HTTP cooki
Интерфейс программирования приложений для HTML и XML документов. Согласно DOM, документ может быть представлен в виде дерева объектов, обладающих рядом свойств, которые позволяют производить с ним различные манипуляции, такие как:
Генерация и добавление узлов
Получение узлов
Изменение узлов
Изменение связей между узлами
Удаление узлов
В данной квалификационной работе использовался стандарт ES6.
Основные возможности ES6
Блочная модель видимости – переменные объявленные с ключевым словом var будут видны в любом месте функции, а переменные объявленные с ключевым словом let, будут видны только внутри блока.
Значения параметров по умолчанию – в функциях добавилась возможность объявлять значения по умолчанию
Классы – в ES6 появились классы, в привычном их виде, пример класса представлен в листинге 2.
Листинг 2 – Пример класса спецификации ES6
class MyClass {
constructor(variable) {
this.variable = variable;
}
setVariable(newVariable) {
this.variable = newVariable;
}
getVariable () {
return this.variable;
}
}
-
Стандарт MPI
1Описание MPI
MPI (Message Passing Interface) – интерфейс передачи сообщений, используется в системах с распределенной памятью. Возник в 1994 году как решение проблемы разнообразия архитектур параллельных вычислительных систем и обеспечение возможности создания переносимых между различными компьютерными платформами программ. Наличие такого стандарта позволило разработать MPI – библиотеки в которых оказалось возможным скрыть большинство архитектурных особенностей параллельных вычислительных систем и, как результат существенно упростить проблему создания параллельных программ. Более того, стандартизация базового системного уровня позволила в значительной степени обеспечить переносимость параллельных программ, поскольку в настоящее время реализации MPI стандарта имеются для большинства компьютерных платформ.
Основной целью спецификации MPI является сочетание в рамках единого подхода переносимых, эффективных и развитых средств передачи данных. Формально использование MPI основано на включении в программные модули заголовочных файлов и загрузчика параллельно исполняемого кода в вычислительные узлы. Подобные библиотеки имеются практически для всех платформ, поэтому написанные с использованием технологии MPI взаимодействия ветвей параллельного приложения программы независимы от машинной архитектуры, от расположения ветвей и от API конкретной операционной системы.
Основу MPI составляют операции передачи сообщений. Среди предусмотренных в составе MPI функций различаются парные («point-to-point») операции между двумя процессами и коллективные – коммуникационные действия для одновременного взаимодействия нескольких процессов.
Для выполнения парных операций могут использоваться разные режимы передачи, среди которых синхронный, блокирующий, режим передачи по готовности.
Процессы параллельной программы объединяются в группы. Под коммуникатором в MPI понимается специально создаваемый служебный объект, объединяющий в своем составе группу процессов и ряд дополнительных параметров, используемых при выполнении операций передачи данных. Как правило, парные операции передачи данных выполняются для процессов, принадлежащих одному и тому же коммуникатору. Коллективные операции применяются одновременно для всех процессов коммуникатора. Как результат, указание используемого коммуникатора является обязательным для операции передачи данных в MPI. В ходе вычислений могут создаваться новые и удаляться существующие группы процессов и коммуникаторы. Один и тот же процесс может принадлежать разным группам и коммуникаторам.
Все имеющиеся в параллельной программе процессы входят в состав создаваемого по умолчанию коммуникатора MPI_COMM_WORLD.
2Операции MPI
Рассмотрим подробнее режимы передачи данных, о которых было сказано выше
Синхронный – завершение функции отправки сообщения происходит только при получении от процесса-получателя подтверждения о начале приема отправленного сообщения, отправленное сообщение или полностью принято процессом-получателем или находится в состоянии приема.
Буферизованный – предполагает использование дополнительных системных буферов для копирования в них отправляемых сообщений. Как результат, функция отправки сообщения завершается сразу же после копирования сообщения в системный буфер.
Режим передачи по готовности – может быть использован только, если операция приема сообщения уже инициирована. Буфер сообщения после завершения функции отправки сообщения может быть повторно использован.
Для отправки сообщения для режимов используются следующие функции:
MPI_Ssend – отправка в синхронном режиме
MPI_Bsend – отправка в буферизованном режиме
MPI_Rsend – отправка в режиме по готовности
Одной из часто выполняемых форм информационного взаимодействия в параллельных программах является обмен данных между процессами, когда для продолжения вычислений процессам необходимо отправить данные одним процессам и, в то же время, получить сообщения от других процессов. Простейший вариант этой ситуации состоит, например, в обмене данными между двумя процессами. Реализация таких обменов при помощи обычных парных операций передачи данных неэффективна и достаточно трудоемка. Кроме того, такая реализация должна гарантировать отсутствие тупиковых ситуаций, которые могут возникать, например, когда два процесса начинают передавать сообщения друг другу и использованием блокирующих функций передачи данных. Достижение эффективного и гарантированного одновременного выполнения операций передачи и приема данных может быть обеспечено при помощи функции MPI_Sendrecv
Под коллективными операциями в MPI понимаются операции над данными, в которых принимают участие все процессы используемого коммуникатора.
Передача данных от одного процесса всем процессам программы
int MPI_Bcast (void *buf, int count, MPI_Datatype type, int root, MPI_Comm comm)
Пример работы операции показан на рисунке 1.
Передача данных от всех процессов одному процессу
int MPI_Reduce (void *sendbuf, void *recvbuf, int count, MPI_Datatype type, MPI_Op op, int root, MPI_Comm comm)
Пример работы операции показан на рисунке 2.
Обобщенная передача данных от одного процесса всем процессам
int MPI_Scatter (void *sbuf, int scount, MPI_Datatype stype, void *rbuf, int rcount, MPI_Datatype type, int root, MPI_Comm comm)
Пример работы операции показан на рисунке 3.
Обобщенная передача данных от всех процессов одному процессу
int MPI_Gather (void *sbuf, int scount, MPI_Datatype type, void *rbuf, int rcount, MPI_Datatype rtype, int root, MPI_Comm comm)
Пример работы операции показан на рисунке 5.
Общая передача данных от всех процессов всем процессам
int MPI_Alltoall (void *sbuf, int scount, MPI_Datatype stype, void *rbuf, int rcount, MPI_Datatype rtype, MPI_Comm comm)
Пример работы операции показан на рисунке 5.
Рисунок 1. Общая схема передачи данных от одного процесса всем процессам
Рисунок 2. Общая схема сбора и обработки на одном процессе данных от всех процессов
Рисунок 3. Общая схема операции обобщенной передачи данных от одного процесса всем процессам
Рисунок 4. Общая схема операции обобщенной передачи данных от всех процессов одному процессу
Рисунок 5. Общая схема операции передачи данных от всех процессов всем процессам
Таблица 2 - Сводный перечень коллективных операций MPI
Вид коллективной операции
|
Функция MPI
|
Широковещательная рассылка
|
MPI_Bcast
|
Редукция данных
|
MPI_Reduce
|
Редукция данных с рассылкой всем процессам
|
MPI_Allreduce
MPI_Reduce_scatter
|
Редукция данных с получением частичных результатов обработки
|
MPI_Scan
|
Распределение данных
|
MPI_Scatter
MPI_Scatterv
|
Сбор данных
|
MPI_Gather
MPI_Gatherv
|
Сбор данных с рассылкой результатов всем процессам
|
MPI_Allgather
MPI_Allgatherv
|
Общая передача данных от всех процессов всем процессам
|
MPI_Alltoall
MPI_Alltoallv
|
3Анализ алгоритмов
Кольцевой алгоритм (Ring) – на первом этапе каждый процесс отправляет свои данные следующему процессу и принимает данные от предыдущего. На втором шаге каждый процесс отправляет данные следующему процессу, полученные от предыдущего процесса на предыдущем шаге.
Оценочное время выполнения
для операции MPI_Allreduce. Где p – число процессов,  – время ожидания,  – время передачи одного байта,  – количество переданных байт,  – время вычисления одного байта,  – размер сообщения.
для операции MPI_Reduce.
Где p – число процессов, – время ожидания, – время передачи одного байта, – количество переданных байт, – время вычисления одного байта, – размер сообщения,  / – время затраченное на передачу данных.
Рекурсивное удвоение – на первом шаге соседние процессы обмениваются своими данными. На втором шаге процессы, находящиеся на расстоянии 2 друг от друга обмениваются своими данными, а также данными полученными на предыдущем шаге. На третьем шаге процессы, находящиеся на расстоянии 4 друг от друга обмениваются своими данными, а также данными полученными на предыдущих шагах. Таким образов, для числа процессов равным степени двойки, все процессы получают данные за  шагов.
Оценочное время выполнения
Где p – число процессов, – время ожидания, – время передачи одного байта, – количество переданных байт, – время вычисления одного байта, – размер сообщения.
Алгоритм Брука – алгоритм начинает свою работу с копирования данных каждого процесса во входной буфер. На каждом шаге k процесс i отправляет рангу (i – 2k) все данные которые у него есть и сохраняет данные полученные от процесса с рангом (i + 2k) в конец буфера к уже имеющимся данным. Алгоритм выполняется за шагов. Если количество процессов не равно степени двойки, то необходим дополнительный шаг, где каждый процесс отправляет все данные процессу с ( ) рангом.
Оценочное время выполнения алгоритма
Где p – число процессов, – время ожидания, – время передачи одного байта, – количество переданных байт, – время вычисления одного байта.
Рекурсивное деление пополам – алгоритм, аналогичный рекурсивному удвоению. Этот алгоритм используется в операции MPI_Allgather. На первом шаге все процессы на находящиеся на расстоянии p / 2 друг от друга, где p – это число процессов, посылают сообщения всем процессам во второй половине. И выполняют операцию MPI_Reduce для полученных данных. На втором шаге, операция MPI_Reduce выполняется для процессов, находящихся на расстоянии p / 4 друг от друга, где p – число процессов.
Оценочное время выполнения
Где p – число процессов, – время ожидания, – время передачи одного байта, – количество переданных байт, – время вычисления одного байта.
средство визуализации
4Проектирование приложения
На этапе проектирования закладываются основы взаимодействия элементов приложения и функционирование приложения в целом. Сначала необходимо спроектировать общий механизм взаимодействия, затем проработать более мелкие детали.
Перед проектированием был произведен анализ аналогичных приложений и сформулированы основные требования.
Главными требованиями являются удобство пользования и наглядность анимации.
На рисунке 7 показан пример взаимодействия с пользователем.
Удобство пользования прежде это прежде всего возможность быстрого доступа ко всей необходимой информации. Это решается путем обеспечения понятного пользователю интерфейса и реализации удобной системы навигации
Рисунок 7. Общая схема пользовательского интерфейса
5Реализация функциональной части приложения
При выборе алгоритма и ввода количества процессов запускается обработчик событий, где происходит валидация введенного значения и, если это значение корректное, оно отправляется в функцию визуализации. Исходный код представлен в листинге 3
Листинг 3 – Функция выбора алгоритма
let startAlgorithm = function(idAlgorithm, objectCanvas) {
switch (idAlgorithm) {
case '1':
if (checkPowerOfTwo(parseInt($("#proc").val())) !== false)
recursiveDoubling(parseInt($("#proc").val()), objectCanvas);
else
alert('Количество процессов не является степенью двойки');
break;
case '2':
ringAlgorithm(parseInt($("#proc").val()), objectCanvas);
break;
case '3':
if (checkPowerOfTwo(parseInt($('#proc').val())) !== false)
recursiveHalving(parseInt($('#proc').val()), objectCanvas);
else
alert('Количество процессов не является степенью двойки');
}
};
Рассмотрим подробнее каждую из функций.
startAlgorithm – вызывается при вводе пользователем количества числа процессов.
checkPowerOfTwo - проверка на то что, число процессов является степенью двойки показана в листинге 4.
Листинг 4 – Функция валидации количества процессов
-
-
-
let checkPowerOfTwo = function (num) {
if (num <= 0)
return false;
while ((num % 2) === 0) {
if ((num /= 2) === 1)
return true;
}
return false;
};
|
recursiveDoubling – запускается процесс визуализации алгоритма рекурсивного удвоения. Пример работы визуализации алгоритма представлен на рисунке 8.
На первом шаге запускается функция отрисовки процессов с периодичностью 300мс, до тех пор, пока количество процессов не равно значению, которое ввел пользователь, исходный код рисования процессов представлен в листинге 5. В листинге 6 представлен первый шаг алгоритма.
Листинг 5 – Отрисовка процессов
let drawCircle = function(objectCanvas, x, y, procNumber) {
let image = new Image();
image.src = 'circle_1.png';
image.width = 30;
image.height = 30;
image.onload = function() {
objectCanvas.drawImage(image, x, y, 50, 70);
objectCanvas.font = "20px Arial";
objectCanvas.strokeText(procNumber, x + 19, y);
};
};
Листинг 6 – Первый шаг алгоритма рекурсивного удвоения
for (let i = 0; i < tempStep1.length; ++i) {
drawLine(objectCanvas, tempStep1[i][0].x, tempStep1[i][0].y, tempStep1[i][1].x, tempStep1[i][1].y, 50, 300, 'red')
}
Здесь исходный граф разбивается на пары процессов и между этими процессами рисуется линия, обозначающая обмена разбиение, отвечает метод chunk. Исходный код метода представлен в листинге 7.
Листинг 7 – Функция, разбивающая массив на пары
Array.prototype.chunk = function (pieces) {
pieces = pieces || 2;
let len = this.length;
let mid = (len/pieces);
let chunks = [];
let start = 0;
for(let i = 0; i < pieces; i++) {
let last = start + mid;
if (!len % pieces >= i) {
last = last - 1
}
chunks.push(this.slice(start, last + 1) || []);
start = last + 1;
}
return chunks;
};
Затем граф разбивается на группы по 2 процесса и между процессами с расстоянием 2 рисуется линия, обозначающая обмен, показано в листинге 8.
Листинг 8 – Второй шаг алгоритма рекурсивного удвоения
let tempStep2 = chunkArray4(step1);
for (let i = 0; i < tempStep2.length; ++i) {
drawLine(objectCanvas, tempStep2[i][0].x + 20, tempStep2[i][0].y, tempStep2[i][2].x + 20, tempStep2[i][2].y, 100, 400, 'green');
drawLine(objectCanvas, tempStep2[i][1].x + 20, tempStep2[i][1].y, tempStep2[i][3].x + 20, tempStep2[i][3].y, 100, 400, 'green');
}
И на последнем шаге граф разбивается на группы по 8 процессов и между элементами с расстоянием друг от друга 4 рисуются линии, обозначающие обмен, исходный код третьего шага представлен в листинге 9.
Листинг 9 – Третий шаг алгоритма рекурсивного удвоения
if (count < 8) {
let tempStep3_small = chunkArray4(step1);
for (let i = 0; i < tempStep2.length; ++i) {
drawLine(objectCanvas, tempStep3_small[i][0].x + 10, tempStep3_small[i][0].y, tempStep3_small[i][3].x + 10, tempStep3_small[i][3].y, 150, 500, 'blue');
}
} else {
for (let i = 0; i < tempStep3.length; ++i) {
drawLine(objectCanvas, tempStep3[i][0].x + 50, tempStep3[i][0].y, tempStep3[i][4].x + 50, tempStep3[i][4].y, 200, 500, 'blue');
drawLine(objectCanvas, tempStep3[i][1].x + 50, tempStep3[i][1].y, tempStep3[i][5].x + 50, tempStep3[i][5].y, 200, 500, 'blue');
drawLine(objectCanvas, tempStep3[i][2].x + 50, tempStep3[i][2].y, tempStep3[i][6].x + 50, tempStep3[i][6].y, 200, 500, 'blue');
drawLine(objectCanvas, tempStep3[i][3].x + 50, tempStep3[i][3].y, tempStep3[i][7].x + 50, tempStep3[i][7].y, 200, 500, 'blue');
}
ringAlgorithm – запускается процесс визуализации кольцевого алгоритма, исходный код представлен в листинге 10. Пример работы программы представлен на рисунке 9.
Листинг 10 – Визуализация кольцевого алгоритма.
let ringAlgorithm = function(proccessesCount, objectCanvas) {
let params = {
radius: 300,
speed: 500
};
let f = 0, s = 2 * Math.PI / proccessesCount, i = 0;
let ring = [];
let descRing = setInterval(function () {
let x = 600 + params.radius * Math.sin(f);
let y = 400 + params.radius * Math.cos(f);
f += s;
drawCircle(objectCanvas, x, y, i);
if (proccessesCount === i) {
clearInterval(descRing);
ring.push(ring[0]);
let j = 0;
let descLine = setInterval(function() {
drawLineCircle(objectCanvas, ring[j].x + 20, ring[j].y + 20, ring[j + 1].x + 20, ring[j + 1].y + 20, 'green');
j++;
if (j === ring.length - 1)
clearInterval(descLine);
}, 300);
}
ring.push({x: x, y: y});
i++;
x = 600 + params.radius * Math.sin(f);
y = 400 + params.radius * Math.cos(f);
}, params.speed);
};
recursiveHalving – запускается процесс визуализации алгоритма рекурсивного деления пополам. На первом шаге запускается функция отрисовки процессов с периодичностью 300мс, до тех пор, пока количество процессов не равно значению, которое ввел пользователь, исходный код первого шага представлен в листинге 11. Пример работы представлен на рисунке 10.
Листинг 11 – Первый шаг алгоритма рекурсивного деления пополам
let tempStep1 = chunkArray8(step1);
for (let i = 0; i < tempStep1.length; ++i) {
drawLine(objectCanvas, tempStep1[i][0].x + 50, tempStep1[i][0].y, tempStep1[i][4].x + 50, tempStep1[i][4].y, 200, 500, 'blue');
drawLine(objectCanvas, tempStep1[i][1].x + 50, tempStep1[i][1].y, tempStep1[i][5].x + 50, tempStep1[i][5].y, 200, 500, 'blue');
drawLine(objectCanvas, tempStep1[i][2].x + 50, tempStep1[i][2].y, tempStep1[i][6].x + 50, tempStep1[i][6].y, 200, 500, 'blue');
drawLine(objectCanvas, tempStep1[i][3].x + 50, tempStep1[i][3].y, tempStep1[i][7].x + 50, tempStep1[i][7].y, 200, 500, 'blue');
}
Затем граф разбивается на группы по 2 процесса и между процессами с расстоянием 2 рисуется линия, обозначающая обмен, пример кода представлен в листинге 12.
Листинг 12 – Второй шаг алгоритма рекурсивного деления пополам
let tempStep2 = chunkArray4(step1);
for (let i = 0; i < tempStep2.length; ++i) {
drawLine(objectCanvas, tempStep2[i][0].x + 20, tempStep2[i][0].y, tempStep2[i][2].x + 20, tempStep2[i][2].y, 100, 400, 'green');
drawLine(objectCanvas, tempStep2[i][1].x + 20, tempStep2[i][1].y, tempStep2[i][3].x + 20, tempStep2[i][3].y, 100, 400, 'green');
}
И на последнем шаге, граф разбивается на пары процессов и между ними рисуются линии, обозначающие обмен. Исходный код представлен в листинге 13.
Листинг 13 – Третий шаг алгоритма рекурсивного деления пополам
if (proccessCount < 8) {
let tempStep3_small = chunkArray4(step1);
for (let i = 0; i < tempStep2.length; ++i) {
drawLine(objectCanvas, tempStep3_small[i][0].x + 10, tempStep3_small[i][0].y, tempStep3_small[i][3].x + 10, tempStep3_small[i][3].y, 150, 500, 'blue');
}
} else {
for (let i = 0; i < tempStep3.length; ++i) {
drawLine(objectCanvas, tempStep3[i][0].x, tempStep3[i][0].y, tempStep3[i][1].x, tempStep3[i][1].y, 50, 450, 'red');
}
}
Рисунок 8. Пример работы алгоритма рекурсивного удвоения.
Рисунок 8. Пример работы кольцевого алгоритма
Рисунок 10. Пример работы алгоритма рекурсивного деления пополам
6Тестирование приложения
Тестирование проводилось в различных браузерах и различных ОС. Результаты можно увидеть в таблице 3.
Таблица 3. Результаты тестирования приложения
Браузер
|
Версия браузера
|
Корректность отображения
|
Google Chrome
|
58.0.3029.110 (64 bit)
|
Корректно
|
Opera
|
41.0.2353 (64 bit)
|
Корректно
|
Internet Explorer
|
9
|
Корректно
|
Microsoft Edge
|
38.14393.1066.0
|
Корректно
|
Safari
|
10.0.3
|
Корректно
|
Заключение
В качестве квалификационной работы было разработано средство визуализации алгоритмов, используемых в операциях коллективного обмена MPI. И также исследована работа этих алгоритмов.
Программный продукт выполнен с учетом стандартов кодирования, что существенно облегчает его дальнейшую поддержку и модификацию программы.
На этапе тестирования возникшие ошибки были оперативно исправлены. ПО готово к дальнейшему использованию.
Цель, поставленная перед началом работы, была достигнута.
Приложение А
(справочное)
Библиография
Хорошевский, В.Г. Архитектура вычислительных систем: Учеб. пособие – 2-е изд., перераб. и доп. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2008. – 520 с.
Флэнаган, Д. JavaScript. Подобное руководство. 6 изд., дополнено. Изд-во «O’Reilly» 2013. – 1080с.
Симпсон, К. ES6 и не только. 2 изд. Дополнено. Изд-во «O’Reilly» 2017. - 336с.
Роббинс, Дж.Н. HTML5, CSS3 и JavaScript. Исчерпывающее руководство. 3 изд., переработано. Изд-во «Эксмо» 2014. -528с.
Thakur, R., Rabenseifner, R., Gropp, W. Optimization of Collective Communication Operation in MPICH. URL: http://www.mcs.anl.gov/~thakur/papers/ijhpca-coll.pdf
Гергель, В.П. Введение в технологии параллельного программирования. «МГУ» 2015. -154с.
24
Приложение Б
(рекомендуемое)
Наиболее употребляемые текстовые сокращения
ВС – вычислительная система
ПЗ – пояснительная записка
ВУ – вычислительный узел
JS - JavaScript
|
СибГУТИ – Сибирский государственный университет телекоммуникаций и информатики
|
|
