Математическое моделирование, численные методы и комплексы программ
Басавин Д.А., аспирант Поршнев С.В., доктор технических наук, профессор, зав. кафедрой (Уральский федеральный университет им. первого Президента Б.Н. Ельцина)
ПАРАЛЛЕЛЬНАЯ ГИБРИДНАЯ ЖИДКОСТНАЯ МОДЕЛЬ ВЫСОКОСКОРОСТНЫХ ИНФОРМАЦИОННЫХ ПОТОКОВ В МАГИСТРАЛЬНЫХ ИНТЕРНЕТ-КАНАЛАХ
Рассмотрена параллельная реализация гибридной жидкостной модели высокоскоростных информационных потоков в магистральных интернет-каналах на графических процессорах с применением платформы OpenCL. Проведено сравнение платформ параллельных вычислений на графических процессорах. Представлены результаты тестирования модели на центральных и графическом процессорах различных типов. Выявлены те части гибридной жидкостной модели, которые в распараллеленном варианте выполняются недостаточно эффективно, а потому требуется их дальнейшая оптимизация.
Ключевые слова: гибридная жидкостная модель, параллельные вычисления, графические процессоры, технология OpenCL.
PARALLEL HYBRID FLUID MODEL OF HIGH-SPEED INFORMATION FLOWS
IN THE MAIN INTERNET LINKS
The parallel realization of a hybrid fluid model of high-speed information flows in the main Internet links on graphic processors with the use of OpenCL platform is considered. Comparison ofparallel computing platforms on graphic processors is carried out. Results of model testing on central and graphic processors of various types are given. Those parts of a hybrid fluid model which are performed insufficiently effectively in a parallelized variant are revealed, and therefore their further optimization is required.
Keywords: hybrid fluid model, parallel computations, graphic processors, OpenCL technology.
1. Введение
Сегодня технологии параллельных вычислений на базе графических процессоров (Graphics Processor Unit - GPU) [1], несмотря на известные ограничения, существующие, в частности, при работе с памятью, позволяют решать множество сложных вычислительных задач, что исключает использование ресурсов дорогостоящих суперкомпьютеров.
Необходимость решения подобных задач существует, в том числе, и в сфере телекоммуникационных технологий, современное состояние которой характеризуется стремительным ростом скоростей передачи данных (до десятков и сотен Гбит/c) и, соответствующим увеличением количества передаваемых в информационных каналах потоках. В этой ситуации, закономерно, что задача создания высокопроизводительных систем моделирования, предназначенных для поддержки принимаемых технических и конструкторских решений и имеющих относительно невысокую стоимость, является актуальной [2].
Следует отметить, что известные пакетные симуляторы трафика позволяют создавать математические модели только каналов передачи данных с умеренной пропускной способностью (до 10 Мбит/с). В этой связи для моделирования высокоскоростных Интернет-каналов (100 Мбит и более) в последние годы был предложен принципиально иной подход, в котором используется аналогия между потоком данных в Интернет-канале и течением жидкости
[3]. Математическая модель, реализующая данный подход, представляет собой следующую систему дифференциальных уравнений (СДУ) с запаздыванием:
1МИ
¡елт,
(1)
(2) )
где /=1,...,# - номер клиента (потока); Wг■ -текущий размер окна передачи данных передачи данных по протоколу ТСР по /-му потоку1; - длина очереди на входе 1-го канала; -функция Хевисайда:
(3)
К^) - время оборота /-го потока; Х^) - скорость потери пакетов /-го потока, С1 - пропускная способность 1-го канала, который обслуживается данным маршрутизатором; А\(() -скорость передачи /-го потока по 1-му каналу:
А(*) =
= Щ (*)
* С)
(4)
Отметим, что как в базовой жидкостной модели Интернет-трафика, так и в ее известных модификациях, используется упрощенное описанием источников трафика, как следствие, оценки его количественных характеристик оказываются весьма грубыми.
Для устранения отмеченного выше недостатка жидкостных моделей в [4] предложена гибридная жидкостная модель информационных потоков в магистральном Интернет-канале, представляющая собой комбинацию жидкостной модели [2] и статистического варианта модели абстрактных источников трафика. Гибридная модель позволяет описывать трафик в мультисервисных сетях с учетом присущего протоколу ТСР механизма обратного влияния загрузки сети на работу источника, а также учитывать современные политики управления скоростью доступа к сети Интернет отдельных пользователей.
Среди абстрактных источников трафика (пользователей) выделены следующие основные классы [4]:
1. «Слоны»: количество ~10 % от полного числа активных пользователей [4], активность -в течение всего времени моделирования, скорость скачивания информации - максимально возможная. Так как время жизни потоков, отнесенных к классу «слонов», превышает время моделирования (на практике используются временные интервалы 1-10 мин, достаточные для выявления выбросов), неравномерность загрузки сети, обусловленную этими потоками, можно учесть, разыгрывая число активных потоков данного класса, считая при этом, что общее количество потоков постоянно в течение всего времени моделирования и они работают при определен-
1 В рассматриваемой математической модели можно учесть механизмы и работы и других протоколов, используемых для передачи данных в сети Интернет, а также взаимное влияние информационных потоков, передаваемых по различным протоколам друг на друга. Однако это с неизбежностью приведет к существенному усложнению модели при относительно небольшом увеличении ее точности, так как Сети доминирует трафик, передаваемый по протоколу ТСР. По литературным данным доля Интернет-трафика, передаваемого в соответствие с протоколом ТСР, составляет свыше 90 % от общего объема информации, передаваемой в сети Интернет (см., например, Олифер В.Г., Олифер Н.А. Компьютерные сети. СПб.: Питер, 2007.)
ном значении выделяемой им со стороны Интернет-провайдера скорости доступа.
2. «Мулы»: количество ~30 % от полного числа активных пользователей, активность -в соответствии со статистическими характеристиками используемых On - Off источников. Для описания «мулов» в процессе моделирования используются следующие параметры:
(a) Распределение времен активации потока (вызовов по терминологии теории массового обслуживания или времени обдумывания). Согласно ряду работ (например, [6]) для этой цели хорошо подходит экспоненциальное распределение с параметром 0.1-1.0 1/с (соответственно, среднее время ожидания вызова 1-10 с).
(b) Распределение размеров скачиваемых файлов, напрямую влияющих на время активности потоков (можно использовать логнормальное распределение [7]).
3. «Мыши»: принимая во внимание типичную длительность активности «мышей», можно считать, что, с физической точки зрения они представляют собой случайную последовательности импульсов с крайне малой продолжительностью. Вероятность одновременного совпадения двух импульсов оказывается относительно небольшой, в связи с чем флуктуацией потока «мышей» в Интернет-канале можно пренебречь. Следовательно, «мыши» не являются причиной интересующих нас выбросов загрузки магистрального канала (на уровне десятков процентов), они просто (постоянно) занимают некоторую (небольшую) долю пропускной способности канала.
Алгоритм расчета гибридной жидкостной модели, предложенный в [4], представлен на рисунке 1. Отметим, что здесь сценарии активности пользователей зависят от типов самих пользователей, описанных выше, а параметры размер окна данных W и длина очереди q рассчитываются для соответствующего пользователя на каждом шаге интегрирования независимо друг от друга.
Рис. 1. Блок-схема алгоритма расчета Интернет-трафика в соответствие с гибридной жидкостной моделью
Анализ блок-схемы гибридной жидкостной модели позволяет выдвинуть гипотезу о возможности распараллеливания вычислений при практической реализации модели, используя для этого, например, графические процессоры (GPU), типичная архитектура которых представлена на рисунке 2. (Напомним, что изначально GPU были созданы задач визуализации графических изображений, основная особенность которых состоит в том, что в процессе их решения
приходится выполнять один и тот же алгоритм независимо для различных фрагментов исходных
1
данных.). Из рисунка 2 видно, что графический процессор состоит из большого числа SIMD ядер, каждое из которых выполняет одну и ту же микропрограмму над разными данными [8].
Графический процессор
Мультиядро 1
Локальная память ~16KB
Мультиядро n
Локальная память ~16KB
t
Видеопамять ~1GB
Центральный процессор
'Ядро^ f Ядро
L1 кеш ~32KB
L1 кеш ~32KB
L2 кеш ~8MB
t
Оперативная память ~4GB
p
p
p
p
p
p
m
m
Рис. 2. Архитектура графического процессора
Отметим, что GPU являются примером потокового процессора, который использует явный параллелизм по данным для увеличения скорости вычислений и уменьшения зависимости от задержек доступа к памяти. За последние десять лет GPU эволюционировали от устройств с фиксированной функциональностью для ускорения примитивных графических операций до программируемых процессоров, превосходящих обычные CPU при выполнении векторизуемых операций [9, 10].
2. Распараллеливание модели
Для эффективной реализации параллельных вычислений в базовом (последовательном) алгоритме необходимо выделить участки, подходящие для распараллеливания, то есть провести его декомпозицию - выделение в алгоритме наборов действий, которые могут быть осуществлены одновременно, независимо друг от друга. Напомним, что согласно [11], существует 2 вида декомпозиции базового алгоритма:
1. декомпозиция по данным;
2. декомпозиция по вычислениям (функциональная декомпозиция).
Под декомпозицией по данным понимают подход, заключающийся в выделении в алгоритме больших объемов данных, обрабатывающихся сходным образом, которые можно разделить на такие части, каждая из которых допускает независимую обработку отдельным исполнителем. Под функциональной декомпозицией - разделение вычислений на зоны ответственности для их выполнения на разных исполнителях (процессорах) и определение дан
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.