Сборник докладов кемерово 2017 the ministry of education and science of the russian federation federal State Budgetary Educational Institution «Kemerovo State University»



страница1/14
Дата14.08.2018
Размер2.09 Mb.
#44474
ТипСборник
  1   2   3   4   5   6   7   8   9   ...   14

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное бюджетное образовательное учреждение

высшего образования

«Кемеровский государственный университет»

Администрация Кемеровской области







Международная конференция

«ВИЗУАЛЬНАЯ АНАЛИТИКА»

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

«Исследования и разработки по приоритетным направлениям развития научно-технологического

комплекса России на 2014–2020 годы»

28 ноября 2017 г.

Кемерово

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное бюджетное образовательное учреждение

высшего образования

«Кемеровский государственный университет»

Администрация Кемеровской области

ВИЗУАЛЬНАЯ АНАЛИТИКА

Международная конференция

(Кемерово, 28 ноября 2017 г.)

Сборник докладов

КЕМЕРОВО 2017

THE MINISTRY OF EDUCATION AND SCIENCE OF THE RUSSIAN FEDERATION

Federal State Budgetary Educational Institution «Kemerovo State University»

Kemerovo region administration

VISUAL ANALYTICS

International conference

(Kemerovo, 28 November 2017)

Collection of reports

KEMEROVO 2017

ББК З973.2-01я431

В 42

УДК 004.9 (063)



Печатается по решению редакционно-издательского совета Федерального государственного бюджетного образовательного учреждения высшего образования «Кемеровский государственный университет».

Конференция проведена в рамках участия в реализации федеральной целевой программы «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2014–2020 годы»

Редакционная коллегия:

Иванова С. А. (отв. редактор),

Павский В. А. (науч. ред.)

В 42 Визуальная аналитика : сборник докладов Международной конференции (28 ноября 2017 г.) / Кемеровский государственный университет ; редкол. : С. А. Иванова (отв. ред.), В. А. Павский (науч. ред.). – Кемерово : Кузбассвузиздат, 2017. – 126 с.

Сборник содержит доклады, представленные участниками Международной конференции «Визуальная аналитика», проводимой Кемеровским государственным университетом. В них отражены результаты новейших разработок по приоритетным направлениям развития научно-технологического комплекса России на 2014–2020 годы.

ББК З973.2-01я431

ISBN 978-5-8353-2187-2

ББК З973.2-01я431

© Авторы научных статей

© ФГБОУ ВО «Кемеровский государственный университет», 2017



СОДЕРЖАНИЕ

СЕКЦИЯ 1: РАСПРЕДЕЛЕННЫЕ ВЫЧИСЛИТЕЛЬНЫЕ И УПРАВЛЯЮЩИЕ СИСТЕМЫ………………………………………………………

5


Реализация алгоритма умножения матриц на основе стандарта OpenCL для графического процессора с архитектурой GCN (Божко В.Л.)……………………………………………………………………………………

5


Масштабируемость алгоритмов дифференцированных обменов стандарта MPI (Аненков А. Д.)…....................................................................................................................

10


Повышение надежности сетецентрических информационно-управляющих систем за счет применения принципов организации туманных вычислений (Мельник Э. В., Клименко А. Б.)...................................................................................

13


Математическое моделирование и оценки эффективности функционирования распределенных вычислительных систем при групповом восстановлении (Павский В. А., Павский К. В.) ……………………………………………………….

17


Распределенные вычислительные системы: параллельное программирование, эффективность функционирования (Павский В. А., Павский К. В., Иванова
С. А.)
……………………………………………………………………………………

20


Исследование масштабируемости централизованных методов контроля и диагностики в системах управления ресурсами вычислительных систем (Крамаренко К. Е., Курносов М. Г.)………………………………………………….

25


Анализ и оптимизация алгоритмов информационных обменов в вычислительных системах с массовым параллелизмом (Курносов
М. Г.)
……………………………………………………………………………………

28


Анализ эффективности векторизации алгоритма умножения матриц
(Молдованова О. В., Кулагин И. И., Курносов М. Г.)………………………………...

32


Анализ эффективности применения технологий GPGPU при реализации эвристических алгоритмов в задачах на графах (Попов Д. В., Ватутин Э. И.) ….

37


Расчёт напряжённого состояния геологических структур для нахождения преимущественной ориентации трещин (Сибиряков Е. Б.).………………………..

40


Алгоритмическая оптимизация программной реализации процедуры получения множества трансверсалей для латинских квадратов (Ватутин Э. И., Кочемазов С. Е., Заикин О. С.) …………………………………………………………………...

Метод минимизации для решения задач высокой размерности (Крутиков В. Н., Самойленко Н. С.)……………………………………………………………………………..

Масштабируемые алгоритмы выполнения критических секций в параллельных PGAS-программах на вычислительных системах с иерархической структурой (Пазников А. А.)………………………………………………………………………………...


44
50

54


Диагностика распределенных информационно-управляющих систем за счет применения обобщенной когнитивной модели (Коробкин В. В.,
Колоденкова А. Е.)……………………………………………………………………………...


59


Моделирование конкурентного разделения каналов связи при реализации параллельных программ на мультиархитектурных вычислительных системах (Перышкова Е. Н., Курносов М. Г.)…………………………………………………

62


СЕКЦИЯ 2: BIGDATA, ПРОБЛЕМЫ И ПЕРСПЕКТИВЫ………………………

66

Использование Big Data в ГИС (Степанов И. Ю., Гудов А. М.)……………………

66

Аналитика как часть корпоративной культуры (Асякина Л. К., Гармашов С. Ю.).

69

Как беспилотные летательные аппараты меняют нашу жизнь? Большие задачи для маленького самолета (Дышлюк Л. С., Башкирцева Н. А.)……………………...

72


Современные презентации: типы, решаемые задачи, алгоритм построения, роль инфографики (Котов Р. М., Носкова С. Ю.)………………………………………….

74


Четвертая промышленная революция (Пискаева А. И., Сухих С. А.)………………

77

СЕКЦИЯ 3: ВИЗУАЛИЗАЦИЯ ДАННЫХ И КОМПЬЮТЕРНОЕ ЗРЕНИЕ…………………………………………………………………………………...

80


Анализ опыта мировых компаний по выводу на рынок домашних приборов физиотерапии (Бюллер А. К.)………………………………………………………….

80


Стадии разработки инновационного проекта (Васильева Ю. Д.)…………………..

84

Использование франчайзинга в качестве инструмента продвижения технических проектов (Абабий Н. С.)……………………………………………………………….

87


Особенности маркетинга в интернете на примере российских социальных сетей (Зернин И. Ф.)…………………………………………………………………………….

89


Управление проектами как инструмент, способствующий достижению целей в проектах по визуальной аналитике (Кизеев В. М.)………………………………….

92


Этапы выведения инновационного продукта на международный рынок
(Яковлев Д.)…………………………………………………………………………….

94


Маркетинг инновационного продукта (Локотош Я.)………………………………

97

Тестирование жизнеспособности идеи технического проекта (Сенченко М.)…….

100

Понятие маркетинга инноваций и его особенности (Трубицын Е.)………………..

105

Взаимодействие маркетинга онлайн и офлайн (Туяков Т.)………………………..

108

Изучение подхода к визуализации процессов на основе сетей Петри при обучении магистрантов в вузе (Мешечкин В. В.)……………………………………

110


Применение современных технологий визуализации данных при разработке геоинформационных систем (Бурмин Л. Н., Бычков А. Г.)…………………………

113


Маркетинг на разных этапах жизненного цикла инновационного продукта (Шульгин Д.)…………………………………………………………………………...

117


Web-инструментарий для решения научных и инженерных задач (Сотников
И. Ю., Завозкин С. Ю.) ………………………………………………………………………..

121


Распознавание позвоночника по рентгеновским снимкам в проекциях (Григорьева И. В., Тоцкий А. А.)………………………………………………………

124



СЕКЦИЯ 1: РАСПРЕДЕЛЕННЫЕ ВЫЧИСЛИТЕЛЬНЫЕ И УПРАВЛЯЮЩИЕ СИСТЕМЫ
Божко В. Л., Сибирский государственный университет телекоммуникаций и информатики; Факультет информатики

и вычислительной техники, студент
РЕАЛИЗАЦИЯ АЛГОРИТМА УМНОЖЕНИЯ МАТРИЦ НА ОСНОВЕ СТАНДАРТА OpenCL ДЛЯ ГРАФИЧЕСКОГО ПРОЦЕССОРА
С АРХИТЕКТУРОЙ GCN

Целью данной работы является сравнение эффективности выполнения вычислений графическим сопроцессором и универсальным процессором на примере умножения матриц. В работе приведено описание реализации алгоритмa на OpenCL и OpenMP, а также, показаны результаты экспериментов. Для проведения экспериментального исследования эффективности предложенной реализации в качестве графического ускорителя использовалась видеокарта AMD Radeon R7 M265, обладающая архитектурой GCN. В качестве центрального процессора использовался Intel Core i5 – 4200U. Максимальное ускорение по сравнению с последовательной версией составило 27,2 раза для OpenCL-реализации алгоритма умножения матриц и 2.06 раза для OpenMP-реализации.

Техника использования графического процессора для проведения вычислений свойственных центральному процессору получила название GPGPU (General-purpose computing on graphics processing units). Необходимость выполнять вычисления общего назначения, характерные для центрального процессора, на графических процессорах поспособствовала появлению новых видов архитектур графических ускорителей. Так, компания AMD развивает архитектуру Graphics Core Next (GCN), NVidia – такие архитектуры как Fermi, Kepler и Pascal.

Развитие GPGPU обусловило появление средств разработки для графических ускорителей. Условно их можно разделить на те, что предоставляют директивы компилятора для распараллеливания участков кода (OpenACC, OpenMP начиная с версии 4.0), и те, что предоставляют интерфейс программирования приложений (CUDA, OpenCL). Доступные модели программирования позволяют выражать как параллелизм уровня данных, так и параллелизм уровня задач [1, 2].

Несмотря на все преимущества, GPGPU имеет и недостатки. Наличие большого количество вычислительных ядер достигается путем упрощения архитектуры. Ядра графических ускорителей имеют простую микроархитектуру, малый объем кэша, и небольшой набор инструкций. Как следствие, отдельно взятое ядро графического сопроцессора выполняет инструкции медленнее, чем ядро универсального процессора. Ускорение же достигается за счёт наличия большого количества вычислительных ядер. Для разработки эффективных параллельных программ с использование графического процессора требуется эффективное распараллеливание алгоритма и учёт архитектурных особенностей используемого графического ускорителя.

В архитектуре GCN основой графического процессора является Compute Unit или вычислительный блок. Вычислительный блок содержит 64 арифметико-логических устройства (АЛУ), которые разделены между четырьмя отдельными векторными SIMD-модулями. Каждый такой модуль содержит 16 АЛУ и может выполнять одну программную операцию над разными данными, как следствие вычислительный блок может одновременно выполнять до четырёх векторных команд. Каждый блок содержит аппаратный планировщик, позволяющий выполнять динамическое распределение нагрузки между векторными SIMD-модулями, скалярный модуль, предназначенный для выполнения разовых операций, а также для контроля исполнения программы, четыре 64 Кбайт регистровых файла, блок ветвлений и сообщений, 8 Кбайт RF, кэш данных, кэш инструкций, общий для всех векторных SIMD-модулей 16 Кбайт Кэш L1, блок выборки данных и декодирования команд [3].

Рисунок 1. Структура блока Compute Unit в архитектуре GCN
В OpenMP реализации умножение происходит в трёх, вложенных друг в друга, циклах. Внешний цикл выполняет проход по строкам, вложенный в него — по столбцам, в третьем цикле умножаются элементы матриц и в ответствующем элементе результирующей матрицы накапливается результат. Внешний цикл распараллеливается с помощью директивы #pragma parallel for. Время выполнения замеряется от начала и до конца внешнего цикла.

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




Рисунок 2. Схема распределения данных между потоками для алгоритма
умножения матриц
Проведено экспериментальное исследование предложенных реализаций алгоритма умножения матриц на персональном компьютере, оборудованном процессором
Intel Core i5 – 4200U и видеокартой AMD Radeon R7 M265. Для OpenCL реализации в качестве устройства для вычислений использовалась видеокарта, количество запускаемых потоков выбиралось исходя из максимально допустимого числа, которые можно запустить на одном вычислительном блоке (Compute Unit) видеокарты (256 потоков - 6 узлов, всего 1536 потоков). Размер входных данных выбирался исходя из объема доступной памяти (2 Гбайт, тип данных double).

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







a)

б)

Рисунок 3. Зависимость времени выполнения параллельной программы от количества потоков: a) OpenMP-реализация, процессор Intel Core i5 — 4200U б) OpenCL-реализация, графический процессор видеокарты AMD Radeon R7 M265



Литература


  1. David A. Patterson and John L. Hennessey. Computer Organization and Design: the Hardware / Software Interface, 2nd Edition // Morgan Kaufmann Publishers, Inc., San Francisco, California, 1998, P. 751.

  2. Herlihy M., Shavit N. The Art of Multiprocessor Programming // Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2008. P. 508.

  3. Michael Mantor, Mike Houston. AMD Graphic Core Next [Электронный ресурс] // AMD Fusion Developer Summit 11, 2011, P. 8–18. URL: http://developer.amd.com/wordpress/media/2013/06/2620_final.pdf (дата обращения: 20.01.2017).



Аненков А. Д., Сибирский государственный университет

телекоммуникаций и информатики,

Кафедра вычислительных систем, инженер, аспирант
МАСШТАБИРУЕМОСТЬ АЛГОРИТМОВ ДИФФЕРЕНЦИРОВАННЫХ ОБМЕНОВ СТАНДАРТА MPI
Алгоритмы дифференцированного обмена (point-to-point communication) в библиотеках, реализующих стандарт MPI, являются наиболее простой и распространенной формой коммуникации на многопроцессорных вычислительных системах [1]. В данном виде обмена индивидуальные пары MPI-процессов [0, P – 1] с изолированным адресным пространством (SPMD) выполняют операции передачи и приёма сообщений. Помимо прямого обмена между двумя индивидуальными MPI-процессами, стандарт MPI позволяет нескольким процессам участвовать в коллективных обменах. Основу всех реализаций алгоритмов дифференцированного и коллективного обменов составляют неблокирующие функции – MPI_Isend() (передача) и MPI_Irecv() (приём).

Неблокирующие функции дифференцированного обмена в библиотеках стандарта MPI реализуются в виде многоуровневой процедуры, задача которой состоит в совмещении процесса обмена сообщениями с процессом вычислений в ветвях параллельной программы. Вызов неблокирующей функции только инициализирует соответствующую операцию, но не выполняет её. Непосредственная передача одного или нескольких сообщений будет выполнена позднее при вызове функций MPI_Wait(), MPI_WaitAll(), MPI_Test(), проверяющих состояние обмена. Данное решение обеспечивает наиболее быстрый возврат к дальнейшему выполнению кода параллельной программы [2].


описание: описание: описание: рисунок2
Рисунок 1. Подсистема реализации обменов
В библиотеках стандарта MPI можно выделить абстрактный уровень – подсистему реализации обменов (the progress engine). Данная подсистема решает задачу непосредственного осуществления дифференцированного обмена сообщениями между MPI-процессами и имеет в своём составе три очереди для хранения сообщений (запросов): очередь запросов на передачу сообщений (SRQ), очередь запросов на приём сообщений (PRQ – posted receive queue) и очередь для неожиданных сообщений (UMQ – unexpected messages queue). Алгоритмы работы подсистемы с данными очередями заключаются в выполнении операций помещения сообщения в очередь, извлечения сообщения из очереди, поиск сообщения в очереди от старых к новым. Цель подсистемы – передать сообщение из пользовательского буфера от одного процесса к другому.

Очереди SRQ, PRQ, UMQ подсистемы реализации обменов в большинстве популярных библиотек стандарта MPI на сегодняшний день реализуются, как правило, на базе связных списков. Данная реализация представляет собой узкое место и проблему производительности при выполнении дифференцированных обменов на большемасштабных вычислительных системах. В подтверждение этому рассмотрим основные коммуникационные алгоритмы дифференцированного обмена, исполняемые подсистемой реализации обменов при работе с очередями, и построим асимптотические оценки худшего случая.



Алгоритм отправки сообщения. При вызове функции MPI_Isend() передаваемое сообщение помещается в конец очереди SRQ, откуда позже извлекается из начала и передается другому процессу MPI-программы при помощи вызова системных функций операционной системы. Помещение и извлечение сообщения из очереди требует фиксированного количества операций и не зависит от числа элементов в очереди. Таким образом, общая оценка асимптотической сложности на отправку сообщения в худшем случае имеет вид (1).

(1)

Алгоритм обработки входящих сообщений выполняется, если при опросе сетевого оборудования было получено новое сообщение. Для каждого входящего сообщения подсистема реализации обменов осуществляет поиск в очереди PRQ возможного подходящего запроса на получение данного сообщения. Вычислительная сложность поиска в очереди PRQ в худшем случае, при котором запрос будет найден в конце очереди, равна (2).

(2)

Однако возможна ситуация, при которой запроса на приём сообщения не окажется в очереди PRQ. В этом случае библиотеки стандарта MPI сохраняют входящее сообщение в очереди UMQ. Время на помещение сообщения в конец очереди равно (3).



(3)

Исходя из выше сказанного, в худшем случае общее время на обработку входящего сообщения складывается из времени работы с каждой из очередей (4).



(4)

Аналогичным образом рассмотрим алгоритм работы с очередями при выполнении вызова функции MPI_Irecv(). При вызове данной функции выполняется поиск сообщения сначала в очереди UMQ в предположении, что искомое сообщение могло поступить ранее.

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

(5)

Иначе, если сообщение в очереди UMQ не было найдено, производится помещение запроса на получение сообщения в очередь PRQ за время O(1). В этом случае общие затраты времени на помещение запроса сообщения составят (6).



(6)

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

Из приведенного простого асимптотического анализа можно сделать вывод, что размеры очередей UMQ и PRQ являются важным аспектом производительности MPI-программы. По мере увеличения размеров данных очередей, время поиска и, следовательно, латентность передачи сообщений увеличивается. Время поиска сообщений становится максимальным в случае, если все сообщения будут размещены в одной из очередей: UMQ или PRQ [4]. В работе [3] показано, что увеличение количества очередей сокращает время поиска. Данный подход применяется в библиотеке Open MPI, где очереди разделены по MPI-процессам.

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


Каталог: upload -> iblock -> 5e9
iblock -> Часы-смартфон
iblock -> Руководство пользователя для телефона Apple iPhone 6
iblock -> Руководство по эксплуатации Методика калибровки Технические характеристики. Минимальный радиус кривизны поверхностей контролируемых изделий, 6мм
iblock -> Технические требования
iblock -> Технологические карты
iblock -> Оптимизация процесса восстановления измененных и уничтоженных маркировочных обозначений на блоках двигателей транспортных средств
iblock -> Инструкция по эксплуатации Температурный gsm извещатель Grinson T7 Благодарим Вас за выбор температурного gsm извещателя Grinson T7
5e9 -> Рабочая программа дисциплины общая и неорганическая химия


Поделитесь с Вашими друзьями:
  1   2   3   4   5   6   7   8   9   ...   14




База данных защищена авторским правом ©vossta.ru 2022
обратиться к администрации

    Главная страница