Реализация алгоритма Флойда-Уоршалла для программно-аппаратной платформы CUDA
Проведен анализ методики реализации алгоритма Флойда–Уоршалла для программно-аппаратной платформы CUDA. Выполнено сравнение времён работы алгоритма на видеоадаптере и центральном процессоре компьютера. Выявлены возможные пути сокращения времени работы алгоритма на видеоадаптере. An analysis of the m...
Gespeichert in:
| Veröffentlicht in: | Управляющие системы и машины |
|---|---|
| Datum: | 2011 |
| Hauptverfasser: | , , , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
2011
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/82966 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Реализация алгоритма Флойда-Уоршалла для программно-аппаратной платформы CUDA / С.Д. Погорелый, М.И. Трибрат, Ю.В. Бойко, Д.Б. Грязнов // Управляющие системы и машины. — 2011. — № 5. — С. 64-67, 72. — Бібліогр.: 9 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-82966 |
|---|---|
| record_format |
dspace |
| spelling |
Погорелый, С.Д. Трибрат, М.И. Бойко, Ю.В. Грязнов, Д.В. 2015-06-12T12:31:44Z 2015-06-12T12:31:44Z 2011 Реализация алгоритма Флойда-Уоршалла для программно-аппаратной платформы CUDA / С.Д. Погорелый, М.И. Трибрат, Ю.В. Бойко, Д.Б. Грязнов // Управляющие системы и машины. — 2011. — № 5. — С. 64-67, 72. — Бібліогр.: 9 назв. — рос. 0130-5395 https://nasplib.isofts.kiev.ua/handle/123456789/82966 004.3 Проведен анализ методики реализации алгоритма Флойда–Уоршалла для программно-аппаратной платформы CUDA. Выполнено сравнение времён работы алгоритма на видеоадаптере и центральном процессоре компьютера. Выявлены возможные пути сокращения времени работы алгоритма на видеоадаптере. An analysis of the methods of implementation of the Floyd–Warshall algorithm for the Software-Hardware platform CUDA is conducted. A comparison of the running time on the graphics card and a central processing unit is made. Possible ways to reduce the running time of the algorithm on the graphics card are exposed. Проведено аналіз методів реалізації алгоритму Флойда–Уоршалла для програмно-апаратної платформи CUDA. Виконано порівняння часу роботи алгоритму на відеоадаптері і центральному процесорі комп’ютера. Виявлено можливі шляхи скорочення часу роботи алгоритму на відеоадаптері. ru Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України Управляющие системы и машины Программная инженерия и программные средства Реализация алгоритма Флойда-Уоршалла для программно-аппаратной платформы CUDA The Implementation of the Floyd – Warshall Algorithm for the CUDA Software-Hardware Platform Реалізація алгоритму Флойда–Уоршалла для програмно-апаратної платформи CUDA Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Реализация алгоритма Флойда-Уоршалла для программно-аппаратной платформы CUDA |
| spellingShingle |
Реализация алгоритма Флойда-Уоршалла для программно-аппаратной платформы CUDA Погорелый, С.Д. Трибрат, М.И. Бойко, Ю.В. Грязнов, Д.В. Программная инженерия и программные средства |
| title_short |
Реализация алгоритма Флойда-Уоршалла для программно-аппаратной платформы CUDA |
| title_full |
Реализация алгоритма Флойда-Уоршалла для программно-аппаратной платформы CUDA |
| title_fullStr |
Реализация алгоритма Флойда-Уоршалла для программно-аппаратной платформы CUDA |
| title_full_unstemmed |
Реализация алгоритма Флойда-Уоршалла для программно-аппаратной платформы CUDA |
| title_sort |
реализация алгоритма флойда-уоршалла для программно-аппаратной платформы cuda |
| author |
Погорелый, С.Д. Трибрат, М.И. Бойко, Ю.В. Грязнов, Д.В. |
| author_facet |
Погорелый, С.Д. Трибрат, М.И. Бойко, Ю.В. Грязнов, Д.В. |
| topic |
Программная инженерия и программные средства |
| topic_facet |
Программная инженерия и программные средства |
| publishDate |
2011 |
| language |
Russian |
| container_title |
Управляющие системы и машины |
| publisher |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| format |
Article |
| title_alt |
The Implementation of the Floyd – Warshall Algorithm for the CUDA Software-Hardware Platform Реалізація алгоритму Флойда–Уоршалла для програмно-апаратної платформи CUDA |
| description |
Проведен анализ методики реализации алгоритма Флойда–Уоршалла для программно-аппаратной платформы CUDA. Выполнено сравнение времён работы алгоритма на видеоадаптере и центральном процессоре компьютера. Выявлены возможные пути сокращения времени работы алгоритма на видеоадаптере.
An analysis of the methods of implementation of the Floyd–Warshall algorithm for the Software-Hardware platform CUDA is conducted. A comparison of the running time on the graphics card and a central processing unit is made. Possible ways to reduce the running time of the algorithm on the graphics card are exposed.
Проведено аналіз методів реалізації алгоритму Флойда–Уоршалла для програмно-апаратної платформи CUDA. Виконано порівняння часу роботи алгоритму на відеоадаптері і центральному процесорі комп’ютера. Виявлено можливі шляхи скорочення часу роботи алгоритму на відеоадаптері.
|
| issn |
0130-5395 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/82966 |
| citation_txt |
Реализация алгоритма Флойда-Уоршалла для программно-аппаратной платформы CUDA / С.Д. Погорелый, М.И. Трибрат, Ю.В. Бойко, Д.Б. Грязнов // Управляющие системы и машины. — 2011. — № 5. — С. 64-67, 72. — Бібліогр.: 9 назв. — рос. |
| work_keys_str_mv |
AT pogorelyisd realizaciâalgoritmafloidauoršalladlâprogrammnoapparatnoiplatformycuda AT tribratmi realizaciâalgoritmafloidauoršalladlâprogrammnoapparatnoiplatformycuda AT boikoûv realizaciâalgoritmafloidauoršalladlâprogrammnoapparatnoiplatformycuda AT grâznovdv realizaciâalgoritmafloidauoršalladlâprogrammnoapparatnoiplatformycuda AT pogorelyisd theimplementationofthefloydwarshallalgorithmforthecudasoftwarehardwareplatform AT tribratmi theimplementationofthefloydwarshallalgorithmforthecudasoftwarehardwareplatform AT boikoûv theimplementationofthefloydwarshallalgorithmforthecudasoftwarehardwareplatform AT grâznovdv theimplementationofthefloydwarshallalgorithmforthecudasoftwarehardwareplatform AT pogorelyisd realízacíâalgoritmufloidauoršalladlâprogramnoaparatnoíplatformicuda AT tribratmi realízacíâalgoritmufloidauoršalladlâprogramnoaparatnoíplatformicuda AT boikoûv realízacíâalgoritmufloidauoršalladlâprogramnoaparatnoíplatformicuda AT grâznovdv realízacíâalgoritmufloidauoršalladlâprogramnoaparatnoíplatformicuda |
| first_indexed |
2025-11-25T22:20:07Z |
| last_indexed |
2025-11-25T22:20:07Z |
| _version_ |
1850562705288593408 |
| fulltext |
64 УСиМ, 2011, № 5
Программная инженерия и программные средства
УДК 004.3
С.Д. Погорелый, М.И. Трибрат, Ю.В. Бойко, Д.Б. Грязнов
Реализация алгоритма Флойда–Уоршалла
для программно-аппаратной платформы CUDA
Проведен анализ методики реализации алгоритма Флойда–Уоршалла для программно-аппаратной платформы CUDA. Выпол-
нено сравнение времён работы алгоритма на видеоадаптере и центральном процессоре компьютера. Выявлены возможные пу-
ти сокращения времени работы алгоритма на видеоадаптере.
An analysis of the methods of implementation of the Floyd–Warshall algorithm for the Software-Hardware platform CUDA is con-
ducted. A comparison of the running time on the graphics card and a central processing unit is made. Possible ways to reduce the run-
ning time of the algorithm on the graphics card are exposed.
Проведено аналіз методів реалізації алгоритму Флойда–Уоршалла для програмно-апаратної платформи CUDA. Виконано по-
рівняння часу роботи алгоритму на відеоадаптері і центральному процесорі комп’ютера. Виявлено можливі шляхи скорочення
часу роботи алгоритму на відеоадаптері.
Введение. Актуальная задача компьютерных се-
тей – задача маршрутизации и выбора оптималь-
ных маршрутов. Предлагаемый алгоритм был
разработан в 1962 году Р. Флойдом и С. Уоршал-
лом и предствляет собой динамический алго-
ритм для нахождения кратчайших расстояний
между всеми парами вершин взвешенного ори-
ентированного графа, эффективно работающий
на плотных графах и временную полиномиаль-
ную сложность его О(N3), где N – количество
вершин графа [1].
Актуальной задачей остается минимизация
времени работы алгоритма, так как процесс
маршрутизации запускается при любом изме-
нение топологии сети и в течение суток может
быть использован миллионы раз.
Цель исследования – реализация предлагае-
мого алгоритма с использованием новой про-
граммно-аппаратной платформы CUDA [2],
сравнение времени работы реализации на ви-
деоадаптере и центральном процессоре, выяв-
ление путей сокращения времени работы алго-
ритма на видеоадаптере и создание методик и
рекомендаций по реализации алгоритмов для
работы с графами. Метод исследования разра-
ботан и описан в [3].
Объектом исследования выступает не толь-
ко методика реализации алгоритма на про-
граммно-аппаратной платформе CUDA, а и ее
обобщение для реализации подобных алгорит-
мов на видеоадаптерах.
Современные программно-аппаратные плат-
формы позволяют значительно увеличить ско-
рость работы алгоритма, используя в том чис-
ле и распараллеливание его работы [4].
Формирование параллельной версии ал-
горитма
Процедура, выполняющая последователь-
ный алгоритм, выглядит так:
for (k = 0; k < N; k++)
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
D[i][j] = min(D[i][j], D[i][k] + D[k][j]),
(1)
где матрица D[i][j] содержит веса кратчайших
путей; i, j, k – параметры цикличных процессов.
Очевидно, что время выполнения алгоритма
равно О(N
3), однако, теоретически его можно
свести к О(N), реализовав один из подходов к
распараллеливанию.
Для корректной работы параллельной реа-
лизации алгоритма необходимо разделить вы-
числения на независимые одну от другой час-
ти, выделив информационные зависимости.
На k-й итерации элементы D[i][k] и D[k][j]
матрицы D[i][j] остаются неизменными. До-
пустим, в выражении (1) i = k, откуда следует:
D[k][j] = min (D[k][j], D[k][k] +
УСиМ, 2011, № 5 65
+ D[k][j]), D[k][j] = D[k][j] , (2)
так как D[k][k] = 0.
Аналогично для j = k в выражении (1) полу-
чим:
D[i][k] = min (D[i][k], D[i][k] +
+ D[k][k]), D[i][k] = D[i][k], (3)
так как D[k][k] = 0.
Используя программно-аппаратную платфор-
му CUDA, позволяющую запускать одновремен-
но тысячи потоков для математических расче-
тов на видеоадаптере, можно реализовать из-
ложенный подход к распараллеливанию рабо-
ты алгоритма.
Теоретически можно сократить время рабо-
ты алгоритма с О(N3) до О(N), заменив циклы
по i и j на значение двухмерного индекса каж-
дого потока (threadIdx.x, threadIdx.y) [5], оста-
вив только итерации по индексу k. При этом
каждый поток будет выполнять только одну опе-
рацию на итерации k:
D[i][j] = min(D[i][j], D[i][k] + D[k][j]). (4)
Увеличение размерности матрицы весов вле-
чет за собой увеличение количества потоков:
при размерности 10241024 число потоков бу-
дет 1048576 и т.д.
Экспериментальные результаты
Для экспериментального подтверждения
предложенного подхода использовался один
узел кластера [6] на основе процессора Intel
Core 2 Duo E6550 и видеоадаптера NVIDIA
GeForce 8600 GT (частота работы CPU и GPU
соответственно 2,33 GHz и 0,516 GHz). Алго-
ритм выполнялся сначала на GPU, затем, для
сравнения, на CPU.
С помощью генератора случайных чисел бы-
ла сгенерирована основная матрица весов, ко-
торая считывалась в глобальную память видео-
адаптера. Тестируемая матрица получалась пу-
тем вырезания части соответствующей размер-
ности из основной матрицы весов. Шаг выре-
зания тестируемой матрицы выбран равным
16, так как 16 потоков – это размер half warp.
Алгоритм реализован на использовании гло-
бальной памяти и разделяемой памяти видео-
адаптера. Глобальная память имеет наибольшие
размеры (для данного видеоадаптера 256 Мб),
необходимые для одноразовой загрузки, срав-
нения и изменения весов графа на итерации k.
Разделяемая память имеет значительно мень-
ший объем (для данного видеоадаптера 16 Кб),
однако скорость обмена информацией с GPU
значительно выше, чем скорость обмена GPU
и глобальной памяти.
Для синхронизации нитей в ядре программы
графического процессора на итерации k исполь-
зовалась явная синхронизация центральным про-
цессором (CPU explicit synchronization [7]).
В ходе эксперимента обнаружена существен-
ная особенность поведения стандартного CUDA
таймера для измерений. При старте таймера из-
мерения времени работы алгоритма на GPU
(CUDA timer GPU) непосредственно перед за-
пуском ядра программы (kernel) и остановки
сразу после выполнения расчетов (т.е. без учета
времени выделения памяти и копирования дан-
ных из оперативной памяти в глобальную па-
мять видеоадаптера и обратно), таймер выда-
вал некорректные результаты.
Некорректные результаты были выявлены
при анализе экспериментальных данных с тай-
меров, измерявших время копирования матри-
цы смежности на видеоадаптер и с него. Тай-
меры измерений времени работы частей алго-
ритма (рис. 1) таковы:
CUDA Total timer GPU – полное время ра-
боты алгоритма с учетом копирования матри-
цы смежности на видеоадаптер и с него;
CUDA timer to – время копирования мат-
рицы из оперативной памяти в глобальную па-
мять видеоадаптера;
CUDA timer GPU – время выполнения ал-
горитма на GPU;
CUDA timer from – время копирования ре-
зультата из глобальной памяти видеоадаптера
в оперативную память.
CUDA Total Timer GPU
CUDA
timer to
CUDA
timer GPU timer from
CUDA
Рис. 1. Порядок запуска таймеров измерения времени работы
частей параллельного алгоритма
66 УСиМ, 2011, № 5
Показатели времени копирования данных при
учете пропускной способности шины PCIe 16
[8] были необъяснимо велики, зависели от кон-
фигурации потоков и менялись в зависимости
от нагрузки на GPU, а также время выполне-
ния алгоритма на GPU слабо зависело от раз-
мерности матрицы.
Такие результаты категорически нельзя ис-
пользовать для дальнейшего анализа. Для из-
мерения времени работы программы только на
GPU (без накладных расходов на копирование,
выделение памяти и др.) необходимо исполь-
зовать таймер событий (CUDA event timer), кото-
рый в этом случае даст достоверные результаты.
Для достижения целей использовалось три
типа таймеров для измерений (рис. 2):
Таймер аппаратно-программной платфор-
мы (CUDA timer GPU и CUDA Total timer GPU);
Таймер событий аппаратно-программной
платформы (CUDA event timer GPU);
Стандартный таймер Windows (рис. 2).
Рис. 2. Измененный порядок запуска таймеров измерения вре-
мени работы частей параллельного алгоритма
Показатели таймеров представлены на рис. 3,
что и подтверждает корректность их работы, и,
соответственно, полученных результатов.
Как видно из рисунка, все три типа таймеров
показывают схожие результаты, однако при ма-
лых размерностях матрицы весов стандартный
таймер Windows показывает увеличенные зна-
чения временных интервалов в сравнении с ос-
тальными таймерами. При увеличении размер-
ности матрицы разницей в показании таймеров
можно пренебречь.
Поскольку цель работы – сравнение време-
ни выполнения алгоритма на CPU и GPU, то
сравнивалось время выполнения алгоритма на
CPU (tCPU) и полное время работы на GPU (tGPU)
с учетом копирования данных из оперативной
памяти в глобальную память видеоадаптера,
вычисления на графическом процессоре и ко-
пирования данных обратно в оперативную па-
мять узла кластера.
CUDA timer GPU
Windows timer
CUDA Event timer GPU
CUDA Total timer GPU
Рис. 3. Различие показаний разных типов таймеров на малых и
больших (верхний левый угол) размерностях матрицы
весов
Время считывания тестируемой матрицы ве-
сов с жесткого диска в оперативную память уз-
ла не учитывалось, так как оно одинаково как
для центрального процессора, так и для видео-
адаптера. Учитывая изложенное, были получе-
ны следующие результаты (рис. 4).
При размерности матрицы весов 208 208 и
больше время выполнения алгоритма на ви-
деоадаптере в 3,3 раза меньше, чем на цен-
тральном процессоре (рис. 5).
Анализ полученных экспериментальных ре-
зультатов показывает, что ожидаемое время вы-
полнения алгоритма О(N), практической реа-
лизацией не достигнуто. Это объясняется тем,
что каждый поток на итерации k обращается к
глобальной памяти видеоадаптера, которая са-
мая большая по объему, но заведомо наиболее
медленная.
Рис. 4. Полное время работы параллельной реализации алго-
ритма на видеоадаптере(tGPU) и время выполнения ал-
горитма на центральном процессоре(tCPU) (верхний ле-
вый угол – первые 14 с работы алгоритма)
УСиМ, 2011, № 5 67
Рис. 5. Отношение времени работы (tCPU)/(tGPU) на централь-
ном процессоре и параллельной реализации на видео-
адаптере
Увеличение времени выполнения алгоритма
на видеоадаптере с шагом увеличения размер-
ности матрицы весов, равным 128, объясняется
тем, что на конкретном видеоадаптере имеется
четыре мультипроцессора, каждый из которых
физически параллельно выполняет 32 потока
(один warp). При ситуации, когда одновременно
все потоки всех мультипроцессоров обращаются
к глобальной памяти, происходит возрастание
латентности и, соответственно, замедление дос-
тупа к данным в глобальной памяти (рис. 6). По-
добные пики будут наблюдаться и на других ви-
деоадаптерах, однако расстояние между ними
будет обусловлено количеством мультипроцес-
соров конкретного графического процессора.
Рис. 6. Изменение отношения времени работы на центральном
процессоре (tCPU)и параллельной реализации алгоритма
на видеоадаптере (tGPU)
Для сокращения времени выполнения алго-
ритма необходимо уменьшить количество об-
ращений к глобальной памяти и, по возможно-
сти, максимально использовать разделяемую па-
мять. Использование разделяемой памяти без
уменьшения обращений к глобальной памяти
только замедлит выполнение алгоритма, так как
данные будут по-прежнему копироваться каж-
дым потоком из глобальной в разделяемую па-
мять, которая в данном случае используется
как буфер (рис. 7) [9].
Рис. 7. Отношение времени выполнения алгоритма при использо-
вании разделяемой памяти в качестве буфера (TGPU) и
глобальной памяти (tGPU)
К накладным расходам можно отнести вре-
мя копирования матрицы весов из оперативной
памяти в глобальную память видеоадаптера
(рис. 8), а также время на явную синхрониза-
цию центральным процессором.
в глобальную
память
из глобальной
памяти
Рис. 8. Время копирования данных по шине PCI-e в глобаль-
ную память видеоадаптера и из нее
Заключение. В реализации алгоритма Флой-
да–Уоршалла для программно-аппаратной плат-
формы CUDA, для сокращения времени выпол-
нения алгоритма использован способ выделе-
ния информационных зависимостей, при кото-
ром теоритическое время выполнения алгорит-
ма сократилось с О(N3) до О(N) в результате со-
здания числа потоков, равного числу элемен-
тов матрицы весов графа.
Получено ускорение работы параллельного
алгоритма в 3,3 раза в сравнении с последова-
тельным алгоритмом, выполненным на CPU.
При конфигурировании программной реали-
зации таким образом, что все физически парал-
лельно исполняемые потоки (warp, 32 потока)
каждого мультипроцессора графического про-
цессора одновременно начнут обращаться к гло-
бальной памяти, время обращения к ней воз-
растет.
Окончание на стр. 72.
72 УСиМ, 2011, № 5
нормализованных цепочек, определению кото-
рых будет посвящена отдельная работа.
Обобщенный параметр К(А, В) равняется сум-
ме максимальных коэффициентов соответствия
термов цепочек А и В: К(А, В)
Ве
ek .
На основании приведенных свойств полу-
чена формула для представления :
=
M
k
Be
t
.
Заключение. Мера релевантности цепочек
А и В как произведение функций и , фигу-
рирующих в формуле, определяется так:
REL(А, В) = =
M
k
Be
t
.
2
)( NMhehl , h 0 .
Эта формула на самом деле учитывает опре-
деленные эффекты семантической близости ин-
формационно-языковых объектов, поэтому ее
можно применять как инструмент при анализе
ситуаций, возникающих при сравнении эталон-
ных (представленных в нормативных источни-
ках, в частности учебниках) формулировок по-
нятий и дефиниций предметной области с фак-
тическими их формулировками, которые есть
объектами оценивания, если и первые и вто-
рые представлены цепочками вида А и В.
Описанная модель была применена в процес-
се оценивания реальных ответов студентов кур-
са «Информатика и вычислительная техника».
1. Kinshuk D., Patel A. A conceptual framework for
Internet based intelligent tutoring systems. Knowledge
transfer (II) // Educational Technology & Society. –
P. 117–124. – http://ifets.ieee.org
2. Кириличев Б.В., Широков Л.А., Рабинович П.Д. Сис-
темный анализ проблемы создания интеллектуаль-
ных компьютерных обучающих комплексов: Сб.
науч. тр. МГИУ. – Г.: МГИУ. – 1996. – С. 166–171.
Поступила 28.12.2010
Тел. для справок: (067) 442-2688 (Киев)
E-mail: vada@ukr.net
© Л.Н. Бадёрина, 2011
Окончание статьи С.Д. Погорелого и др.
При учете всех накладных временных расходов на
выделение памяти видеоадаптера, копирование данных
на и от него, создание миллионов потоков, синхрониза-
цию потоков на k-й итерации центральным процессором,
предложенная параллельная реализация на видеоадапте-
ре минимум в два раза быстрее последовательной реа-
лизации на центральном процессоре.
Использование разделяемой памяти графического про-
цессора не дает преимуществ без снижения количества
обращений к глобальной памяти видеоадаптера, в кото-
рую копируется матрица весов графа.
Для дальнейшего сокращения времени выполнения ал-
горитма на видеоадаптере необходимо использовать иные
подходы к выделению информационных зависимостей, ко-
торые, возможно, теоретически дадут больше время вы-
полнения алгоритма, чем О(N), однако, при реализации,
используя программно-аппаратную платформу CUDA,
будут использовать разделяемую память и снизят число
обращений в глобальную память видеоадаптера.
1. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы, по-
строение и анализ. – М.: МЦНМО, 2000. – C. 719–725.
2. Анализ методов повышения производительности ком-
пьютеров с использованием графических процессо-
ров и программно-аппаратной платформы CUDA
/ С.Д. Погорелый, Ю.В. Бойко, М.И. Трибрат и др.
// Математичні машини та системи. – 2010. – № 1. –
C. 40–54.
3. Методика вимірювання обчислювальної потужнос-
ті відеоадаптера (платформа CUDA) / С.Д. Погорілий,
М.И. Трібрат, Ю.В. Бойко та ін. // ИКВТ (ДонНТУ),
2010. – № 11. – С. 94–98.
4. Погорілий С.Д., Камардіна О.О., Бавикін О.І. Про під-
хід до розпаралелювання алгоритму Флойда–Уор-
шала // Математичні машини і системи. 2005. –
№ 3. – С. 91–101.
5. NVIDIA CUDA Programming Guide 2.3. – http://deve-
loper.download.nvidia.com/compute/cuda/2_3/toolkit/
docs/NVIDIA_CUDA_Programming_Guide_2.3.pdf
6. Программное обеспечение UAClaster / В.А. Мар’я-
новский, С.Д. Погорелый, Ю.В. Бойко и др. // УСиМ. –
2009. – № 5. – С. 76–80.
7. Inter-Block GPU Communication via Fast Barrier Syn-
chronization. – http://www.nvidia.com/content/GTC/pos-
ters/ 73_Feng_Accelerating_Applications.pdf
8. PCI Express. –http://ru.wikipedia.org/wiki/PCI_Express
9. All-Pairs Shortest-Paths for Large Graphs on the GPU
/ G.J. Katz, J.T. Kider Jr. – http://www.seas.upenn.
edu/~kiderj/ research/papers/APSP-gh08-fin-T.pdf
Поступила 07.12.2010
Тел. для справок: (044) 526-0522 (Киев)
E-mail: sdp@univ.kiev.ua, mike3b@univ.kiev.ua,
boyko@univ.kiev.ua, dima@univ.kiev.ua
© С.Д. Погорелый, М.И. Трибрат, Ю.В. Бойко,
Д.Б. Грязнов, 2011
<<
/ASCII85EncodePages false
/AllowTransparency false
/AutoPositionEPSFiles true
/AutoRotatePages /None
/Binding /Left
/CalGrayProfile (Dot Gain 20%)
/CalRGBProfile (sRGB IEC61966-2.1)
/CalCMYKProfile (U.S. Web Coated \050SWOP\051 v2)
/sRGBProfile (sRGB IEC61966-2.1)
/CannotEmbedFontPolicy /Error
/CompatibilityLevel 1.4
/CompressObjects /Tags
/CompressPages true
/ConvertImagesToIndexed true
/PassThroughJPEGImages true
/CreateJobTicket false
/DefaultRenderingIntent /Default
/DetectBlends true
/DetectCurves 0.0000
/ColorConversionStrategy /CMYK
/DoThumbnails false
/EmbedAllFonts true
/EmbedOpenType false
/ParseICCProfilesInComments true
/EmbedJobOptions true
/DSCReportingLevel 0
/EmitDSCWarnings false
/EndPage -1
/ImageMemory 1048576
/LockDistillerParams false
/MaxSubsetPct 100
/Optimize true
/OPM 1
/ParseDSCComments true
/ParseDSCCommentsForDocInfo true
/PreserveCopyPage true
/PreserveDICMYKValues true
/PreserveEPSInfo true
/PreserveFlatness true
/PreserveHalftoneInfo false
/PreserveOPIComments true
/PreserveOverprintSettings true
/StartPage 1
/SubsetFonts true
/TransferFunctionInfo /Apply
/UCRandBGInfo /Preserve
/UsePrologue false
/ColorSettingsFile ()
/AlwaysEmbed [ true
]
/NeverEmbed [ true
]
/AntiAliasColorImages false
/CropColorImages true
/ColorImageMinResolution 300
/ColorImageMinResolutionPolicy /OK
/DownsampleColorImages true
/ColorImageDownsampleType /Bicubic
/ColorImageResolution 300
/ColorImageDepth -1
/ColorImageMinDownsampleDepth 1
/ColorImageDownsampleThreshold 1.50000
/EncodeColorImages true
/ColorImageFilter /DCTEncode
/AutoFilterColorImages true
/ColorImageAutoFilterStrategy /JPEG
/ColorACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/ColorImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000ColorACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000ColorImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasGrayImages false
/CropGrayImages true
/GrayImageMinResolution 300
/GrayImageMinResolutionPolicy /OK
/DownsampleGrayImages true
/GrayImageDownsampleType /Bicubic
/GrayImageResolution 300
/GrayImageDepth -1
/GrayImageMinDownsampleDepth 2
/GrayImageDownsampleThreshold 1.50000
/EncodeGrayImages true
/GrayImageFilter /DCTEncode
/AutoFilterGrayImages true
/GrayImageAutoFilterStrategy /JPEG
/GrayACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/GrayImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000GrayACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000GrayImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasMonoImages false
/CropMonoImages true
/MonoImageMinResolution 1200
/MonoImageMinResolutionPolicy /OK
/DownsampleMonoImages true
/MonoImageDownsampleType /Bicubic
/MonoImageResolution 1200
/MonoImageDepth -1
/MonoImageDownsampleThreshold 1.50000
/EncodeMonoImages true
/MonoImageFilter /CCITTFaxEncode
/MonoImageDict <<
/K -1
>>
/AllowPSXObjects false
/CheckCompliance [
/None
]
/PDFX1aCheck false
/PDFX3Check false
/PDFXCompliantPDFOnly false
/PDFXNoTrimBoxError true
/PDFXTrimBoxToMediaBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXSetBleedBoxToMediaBox true
/PDFXBleedBoxToTrimBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXOutputIntentProfile ()
/PDFXOutputConditionIdentifier ()
/PDFXOutputCondition ()
/PDFXRegistryName ()
/PDFXTrapped /False
/CreateJDFFile false
/Description <<
/ARA <FEFF06270633062A062E062F0645002006470630064700200627064406250639062F0627062F0627062A002006440625064606340627062100200648062B062706260642002000410064006F00620065002000500044004600200645062A064806270641064206290020064406440637062806270639062900200641064A00200627064406450637062706280639002006300627062A0020062F0631062C0627062A002006270644062C0648062F0629002006270644063906270644064A0629061B0020064A06450643064600200641062A062D00200648062B0627062606420020005000440046002006270644064506460634062306290020062806270633062A062E062F062706450020004100630072006F0062006100740020064800410064006F006200650020005200650061006400650072002006250635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E0635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E>
/BGR <FEFF04180437043f043e043b043704320430043904420435002004420435043704380020043d0430044104420440043e0439043a0438002c00200437043000200434043000200441044a0437043404300432043004420435002000410064006f00620065002000500044004600200434043e043a0443043c0435043d04420438002c0020043c0430043a04410438043c0430043b043d043e0020043f044004380433043e04340435043d04380020043704300020043204380441043e043a043e043a0430044704350441044204320435043d0020043f04350447043004420020043704300020043f044004350434043f0435044704300442043d04300020043f043e04340433043e0442043e0432043a0430002e002000200421044a04370434043004340435043d043804420435002000500044004600200434043e043a0443043c0435043d044204380020043c043e0433043004420020043404300020044104350020043e0442043204300440044f0442002004410020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200441043b0435043404320430044904380020043204350440044104380438002e>
/CHS <FEFF4f7f75288fd94e9b8bbe5b9a521b5efa7684002000410064006f006200650020005000440046002065876863900275284e8e9ad88d2891cf76845370524d53705237300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c676562535f00521b5efa768400200050004400460020658768633002>
/CHT <FEFF4f7f752890194e9b8a2d7f6e5efa7acb7684002000410064006f006200650020005000440046002065874ef69069752865bc9ad854c18cea76845370524d5370523786557406300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c4f86958b555f5df25efa7acb76840020005000440046002065874ef63002>
/CZE <FEFF005400610074006f0020006e006100730074006100760065006e00ed00200070006f0075017e0069006a007400650020006b0020007600790074007600e101590065006e00ed00200064006f006b0075006d0065006e0074016f002000410064006f006200650020005000440046002c0020006b00740065007200e90020007300650020006e0065006a006c00e90070006500200068006f006400ed002000700072006f0020006b00760061006c00690074006e00ed0020007400690073006b00200061002000700072006500700072006500730073002e002000200056007900740076006f01590065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f007400650076015900ed007400200076002000700072006f006700720061006d0065006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076011b006a016100ed00630068002e>
/DAN <FEFF004200720075006700200069006e0064007300740069006c006c0069006e006700650072006e0065002000740069006c0020006100740020006f007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400650072002c0020006400650072002000620065006400730074002000650067006e006500720020007300690067002000740069006c002000700072006500700072006500730073002d007500640073006b007200690076006e0069006e00670020006100660020006800f8006a0020006b00760061006c0069007400650074002e0020004400650020006f007000720065007400740065006400650020005000440046002d0064006f006b0075006d0065006e0074006500720020006b0061006e002000e50062006e00650073002000690020004100630072006f00620061007400200065006c006c006500720020004100630072006f006200610074002000520065006100640065007200200035002e00300020006f00670020006e0079006500720065002e>
/DEU <FEFF00560065007200770065006e00640065006e0020005300690065002000640069006500730065002000450069006e007300740065006c006c0075006e00670065006e0020007a0075006d002000450072007300740065006c006c0065006e00200076006f006e002000410064006f006200650020005000440046002d0044006f006b0075006d0065006e00740065006e002c00200076006f006e002000640065006e0065006e002000530069006500200068006f006300680077006500720074006900670065002000500072006500700072006500730073002d0044007200750063006b0065002000650072007a0065007500670065006e0020006d00f60063006800740065006e002e002000450072007300740065006c006c007400650020005000440046002d0044006f006b0075006d0065006e007400650020006b00f6006e006e0065006e0020006d006900740020004100630072006f00620061007400200075006e0064002000410064006f00620065002000520065006100640065007200200035002e00300020006f0064006500720020006800f600680065007200200067006500f600660066006e00650074002000770065007200640065006e002e>
/ESP <FEFF005500740069006c0069006300650020006500730074006100200063006f006e0066006900670075007200610063006900f3006e0020007000610072006100200063007200650061007200200064006f00630075006d0065006e0074006f00730020005000440046002000640065002000410064006f0062006500200061006400650063007500610064006f00730020007000610072006100200069006d0070007200650073006900f3006e0020007000720065002d0065006400690074006f007200690061006c00200064006500200061006c00740061002000630061006c0069006400610064002e002000530065002000700075006500640065006e00200061006200720069007200200064006f00630075006d0065006e0074006f00730020005000440046002000630072006500610064006f007300200063006f006e0020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e003000200079002000760065007200730069006f006e0065007300200070006f00730074006500720069006f007200650073002e>
/ETI <FEFF004b00610073007500740061006700650020006e0065006900640020007300e4007400740065006900640020006b00760061006c006900740065006500740073006500200074007200fc006b006900650065006c007300650020007000720069006e00740069006d0069007300650020006a0061006f006b007300200073006f00620069006c0069006b0065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740069006400650020006c006f006f006d006900730065006b0073002e00200020004c006f006f0064007500640020005000440046002d0064006f006b0075006d0065006e00740065002000730061006100740065002000610076006100640061002000700072006f006700720061006d006d006900640065006700610020004100630072006f0062006100740020006e0069006e0067002000410064006f00620065002000520065006100640065007200200035002e00300020006a00610020007500750065006d006100740065002000760065007200730069006f006f006e00690064006500670061002e000d000a>
/FRA <FEFF005500740069006c006900730065007a00200063006500730020006f007000740069006f006e00730020006100660069006e00200064006500200063007200e900650072002000640065007300200064006f00630075006d0065006e00740073002000410064006f00620065002000500044004600200070006f0075007200200075006e00650020007100750061006c0069007400e90020006400270069006d007000720065007300730069006f006e00200070007200e9007000720065007300730065002e0020004c0065007300200064006f00630075006d0065006e00740073002000500044004600200063007200e900e90073002000700065007500760065006e0074002000ea0074007200650020006f007500760065007200740073002000640061006e00730020004100630072006f006200610074002c002000610069006e00730069002000710075002700410064006f00620065002000520065006100640065007200200035002e0030002000650074002000760065007200730069006f006e007300200075006c007400e90072006900650075007200650073002e>
/GRE <FEFF03a703c103b703c303b903bc03bf03c003bf03b903ae03c303c403b5002003b103c503c403ad03c2002003c403b903c2002003c103c503b803bc03af03c303b503b903c2002003b303b903b1002003bd03b1002003b403b703bc03b903bf03c503c103b303ae03c303b503c403b5002003ad03b303b303c103b103c603b1002000410064006f006200650020005000440046002003c003bf03c5002003b503af03bd03b103b9002003ba03b103c42019002003b503be03bf03c703ae03bd002003ba03b103c403ac03bb03bb03b703bb03b1002003b303b903b1002003c003c103bf002d03b503ba03c403c503c003c903c403b903ba03ad03c2002003b503c103b303b103c303af03b503c2002003c503c803b703bb03ae03c2002003c003bf03b903cc03c403b703c403b103c2002e0020002003a403b10020005000440046002003ad03b303b303c103b103c603b1002003c003bf03c5002003ad03c703b503c403b5002003b403b703bc03b903bf03c503c103b303ae03c303b503b9002003bc03c003bf03c103bf03cd03bd002003bd03b1002003b103bd03bf03b903c703c403bf03cd03bd002003bc03b5002003c403bf0020004100630072006f006200610074002c002003c403bf002000410064006f00620065002000520065006100640065007200200035002e0030002003ba03b103b9002003bc03b503c403b103b303b503bd03ad03c303c403b503c103b503c2002003b503ba03b403cc03c303b503b903c2002e>
/HEB <FEFF05D405E905EA05DE05E905D5002005D105D405D205D305E805D505EA002005D005DC05D4002005DB05D305D9002005DC05D905E605D505E8002005DE05E105DE05DB05D9002000410064006F006200650020005000440046002005D405DE05D505EA05D005DE05D905DD002005DC05D405D305E405E105EA002005E705D305DD002D05D305E405D505E1002005D005D905DB05D505EA05D905EA002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E05D005DE05D905DD002005DC002D005000440046002F0058002D0033002C002005E205D905D905E005D5002005D105DE05D305E805D905DA002005DC05DE05E905EA05DE05E9002005E905DC0020004100630072006F006200610074002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E>
/HRV (Za stvaranje Adobe PDF dokumenata najpogodnijih za visokokvalitetni ispis prije tiskanja koristite ove postavke. Stvoreni PDF dokumenti mogu se otvoriti Acrobat i Adobe Reader 5.0 i kasnijim verzijama.)
/HUN <FEFF004b0069007600e1006c00f30020006d0069006e0151007300e9006701710020006e0079006f006d00640061006900200065006c0151006b00e90073007a00ed007401510020006e0079006f006d00740061007400e100730068006f007a0020006c006500670069006e006b00e1006200620020006d0065006700660065006c0065006c0151002000410064006f00620065002000500044004600200064006f006b0075006d0065006e00740075006d006f006b0061007400200065007a0065006b006b0065006c0020006100200062006500e1006c006c00ed007400e10073006f006b006b0061006c0020006b00e90073007a00ed0074006800650074002e0020002000410020006c00e90074007200650068006f007a006f00740074002000500044004600200064006f006b0075006d0065006e00740075006d006f006b00200061007a0020004100630072006f006200610074002000e9007300200061007a002000410064006f00620065002000520065006100640065007200200035002e0030002c0020007600610067007900200061007a002000610074007400f3006c0020006b00e9007301510062006200690020007600650072007a006900f3006b006b0061006c0020006e00790069007400680061007400f3006b0020006d00650067002e>
/ITA <FEFF005500740069006c0069007a007a006100720065002000710075006500730074006500200069006d0070006f007300740061007a0069006f006e00690020007000650072002000630072006500610072006500200064006f00630075006d0065006e00740069002000410064006f00620065002000500044004600200070006900f900200061006400610074007400690020006100200075006e00610020007000720065007300740061006d0070006100200064006900200061006c007400610020007100750061006c0069007400e0002e0020004900200064006f00630075006d0065006e007400690020005000440046002000630072006500610074006900200070006f00730073006f006e006f0020006500730073006500720065002000610070006500720074006900200063006f006e0020004100630072006f00620061007400200065002000410064006f00620065002000520065006100640065007200200035002e003000200065002000760065007200730069006f006e006900200073007500630063006500730073006900760065002e>
/JPN <FEFF9ad854c18cea306a30d730ea30d730ec30b951fa529b7528002000410064006f0062006500200050004400460020658766f8306e4f5c6210306b4f7f75283057307e305930023053306e8a2d5b9a30674f5c62103055308c305f0020005000440046002030d530a130a430eb306f3001004100630072006f0062006100740020304a30883073002000410064006f00620065002000520065006100640065007200200035002e003000204ee5964d3067958b304f30533068304c3067304d307e305930023053306e8a2d5b9a306b306f30d530a930f330c8306e57cb30818fbc307f304c5fc59808306730593002>
/KOR <FEFFc7740020c124c815c7440020c0acc6a9d558c5ec0020ace0d488c9c80020c2dcd5d80020c778c1c4c5d00020ac00c7a50020c801d569d55c002000410064006f0062006500200050004400460020bb38c11cb97c0020c791c131d569b2c8b2e4002e0020c774b807ac8c0020c791c131b41c00200050004400460020bb38c11cb2940020004100630072006f0062006100740020bc0f002000410064006f00620065002000520065006100640065007200200035002e00300020c774c0c1c5d0c11c0020c5f40020c2180020c788c2b5b2c8b2e4002e>
/LTH <FEFF004e006100750064006f006b0069007400650020016100690075006f007300200070006100720061006d006500740072007500730020006e006f0072011700640061006d00690020006b0075007200740069002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b00750072006900650020006c0061006200690061007500730069006100690020007000720069007400610069006b007900740069002000610075006b01610074006f00730020006b006f006b007900620117007300200070006100720065006e006700740069006e00690061006d00200073007000610075007300640069006e0069006d00750069002e0020002000530075006b0075007200740069002000500044004600200064006f006b0075006d0065006e007400610069002000670061006c006900200062016b007400690020006100740069006400610072006f006d00690020004100630072006f006200610074002000690072002000410064006f00620065002000520065006100640065007200200035002e0030002000610072002000760117006c00650073006e0117006d00690073002000760065007200730069006a006f006d00690073002e>
/LVI <FEFF0049007a006d0061006e0074006f006a00690065007400200161006f00730020006900650073007400610074012b006a0075006d00750073002c0020006c0061006900200076006500690064006f00740075002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006100730020006900720020012b00700061016100690020007000690065006d01130072006f00740069002000610075006700730074006100730020006b00760061006c0069007401010074006500730020007000690072006d007300690065007300700069006501610061006e006100730020006400720075006b00610069002e00200049007a0076006500690064006f006a006900650074002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006f002000760061007200200061007400760113007200740020006100720020004100630072006f00620061007400200075006e002000410064006f00620065002000520065006100640065007200200035002e0030002c0020006b0101002000610072012b00200074006f0020006a00610075006e0101006b0101006d002000760065007200730069006a0101006d002e>
/NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken die zijn geoptimaliseerd voor prepress-afdrukken van hoge kwaliteit. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.)
/NOR <FEFF004200720075006b00200064006900730073006500200069006e006e007300740069006c006c0069006e00670065006e0065002000740069006c002000e50020006f0070007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740065007200200073006f006d00200065007200200062006500730074002000650067006e0065007400200066006f00720020006600f80072007400720079006b006b0073007500740073006b00720069006600740020006100760020006800f800790020006b00760061006c0069007400650074002e0020005000440046002d0064006f006b0075006d0065006e00740065006e00650020006b0061006e002000e50070006e00650073002000690020004100630072006f00620061007400200065006c006c00650072002000410064006f00620065002000520065006100640065007200200035002e003000200065006c006c00650072002000730065006e006500720065002e>
/POL <FEFF0055007300740061007700690065006e0069006100200064006f002000740077006f0072007a0065006e0069006100200064006f006b0075006d0065006e007400f300770020005000440046002000700072007a0065007a006e00610063007a006f006e00790063006800200064006f002000770079006400720075006b00f30077002000770020007700790073006f006b00690065006a0020006a0061006b006f015b00630069002e002000200044006f006b0075006d0065006e0074007900200050004400460020006d006f017c006e00610020006f007400770069006500720061010700200077002000700072006f006700720061006d006900650020004100630072006f00620061007400200069002000410064006f00620065002000520065006100640065007200200035002e0030002000690020006e006f00770073007a0079006d002e>
/PTB <FEFF005500740069006c0069007a006500200065007300730061007300200063006f006e00660069006700750072006100e700f50065007300200064006500200066006f0072006d00610020006100200063007200690061007200200064006f00630075006d0065006e0074006f0073002000410064006f0062006500200050004400460020006d00610069007300200061006400650071007500610064006f00730020007000610072006100200070007200e9002d0069006d0070007200650073007300f50065007300200064006500200061006c007400610020007100750061006c00690064006100640065002e0020004f007300200064006f00630075006d0065006e0074006f00730020005000440046002000630072006900610064006f007300200070006f00640065006d0020007300650072002000610062006500720074006f007300200063006f006d0020006f0020004100630072006f006200610074002000650020006f002000410064006f00620065002000520065006100640065007200200035002e0030002000650020007600650072007300f50065007300200070006f00730074006500720069006f007200650073002e>
/RUM <FEFF005500740069006c0069007a00610163006900200061006300650073007400650020007300650074010300720069002000700065006e007400720075002000610020006300720065006100200064006f00630075006d0065006e00740065002000410064006f006200650020005000440046002000610064006500630076006100740065002000700065006e0074007200750020007400690070010300720069007200650061002000700072006500700072006500730073002000640065002000630061006c006900740061007400650020007300750070006500720069006f006100720103002e002000200044006f00630075006d0065006e00740065006c00650020005000440046002000630072006500610074006500200070006f00740020006600690020006400650073006300680069007300650020006300750020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e00300020015f00690020007600650072007300690075006e0069006c006500200075006c0074006500720069006f006100720065002e>
/RUS <FEFF04180441043f043e043b044c04370443043904420435002004340430043d043d044b04350020043d0430044104420440043e0439043a043800200434043b044f00200441043e043704340430043d0438044f00200434043e043a0443043c0435043d0442043e0432002000410064006f006200650020005000440046002c0020043c0430043a04410438043c0430043b044c043d043e0020043f043e04340445043e0434044f04490438044500200434043b044f00200432044b0441043e043a043e043a0430044704350441044204320435043d043d043e0433043e00200434043e043f0435044704300442043d043e0433043e00200432044b0432043e04340430002e002000200421043e043704340430043d043d044b04350020005000440046002d0434043e043a0443043c0435043d0442044b0020043c043e0436043d043e0020043e0442043a0440044b043204300442044c002004410020043f043e043c043e0449044c044e0020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200431043e043b043504350020043f043e04370434043d043804450020043204350440044104380439002e>
/SKY <FEFF0054006900650074006f0020006e006100730074006100760065006e0069006100200070006f0075017e0069007400650020006e00610020007600790074007600e100720061006e0069006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b0074006f007200e90020007300610020006e0061006a006c0065007001610069006500200068006f0064006900610020006e00610020006b00760061006c00690074006e00fa00200074006c0061010d00200061002000700072006500700072006500730073002e00200056007900740076006f00720065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f00740076006f00720069016500200076002000700072006f006700720061006d006f006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076016100ed00630068002e>
/SLV <FEFF005400650020006e006100730074006100760069007400760065002000750070006f0072006100620069007400650020007a00610020007500730074007600610072006a0061006e006a006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b006900200073006f0020006e0061006a007000720069006d00650072006e0065006a016100690020007a00610020006b0061006b006f0076006f00730074006e006f0020007400690073006b0061006e006a00650020007300200070007200690070007200610076006f0020006e00610020007400690073006b002e00200020005500730074007600610072006a0065006e006500200064006f006b0075006d0065006e0074006500200050004400460020006a00650020006d006f0067006f010d00650020006f0064007000720065007400690020007a0020004100630072006f00620061007400200069006e002000410064006f00620065002000520065006100640065007200200035002e003000200069006e0020006e006f00760065006a01610069006d002e>
/SUO <FEFF004b00e40079007400e40020006e00e40069007400e4002000610073006500740075006b007300690061002c0020006b0075006e0020006c0075006f00740020006c00e400680069006e006e00e4002000760061006100740069007600610061006e0020007000610069006e006100740075006b00730065006e002000760061006c006d0069007300740065006c00750074007900f6006800f6006e00200073006f00700069007600690061002000410064006f0062006500200050004400460020002d0064006f006b0075006d0065006e007400740065006a0061002e0020004c0075006f0064007500740020005000440046002d0064006f006b0075006d0065006e00740069007400200076006f0069006400610061006e0020006100760061007400610020004100630072006f0062006100740069006c006c00610020006a0061002000410064006f00620065002000520065006100640065007200200035002e0030003a006c006c00610020006a006100200075007500640065006d006d0069006c006c0061002e>
/SVE <FEFF0041006e007600e4006e00640020006400650020006800e4007200200069006e0073007400e4006c006c006e0069006e006700610072006e00610020006f006d002000640075002000760069006c006c00200073006b006100700061002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400200073006f006d002000e400720020006c00e4006d0070006c0069006700610020006600f60072002000700072006500700072006500730073002d007500740073006b00720069006600740020006d006500640020006800f600670020006b00760061006c0069007400650074002e002000200053006b006100700061006400650020005000440046002d0064006f006b0075006d0065006e00740020006b0061006e002000f600700070006e00610073002000690020004100630072006f0062006100740020006f00630068002000410064006f00620065002000520065006100640065007200200035002e00300020006f00630068002000730065006e006100720065002e>
/TUR <FEFF005900fc006b00730065006b0020006b0061006c006900740065006c0069002000f6006e002000790061007a006401310072006d00610020006200610073006b013100730131006e006100200065006e0020006900790069002000750079006100620069006c006500630065006b002000410064006f006200650020005000440046002000620065006c00670065006c0065007200690020006f006c0075015f007400750072006d0061006b0020006900e70069006e00200062007500200061007900610072006c0061007201310020006b0075006c006c0061006e0131006e002e00200020004f006c0075015f0074007500720075006c0061006e0020005000440046002000620065006c00670065006c0065007200690020004100630072006f006200610074002000760065002000410064006f00620065002000520065006100640065007200200035002e003000200076006500200073006f006e0072006100730131006e00640061006b00690020007300fc007200fc006d006c00650072006c00650020006100e70131006c006100620069006c00690072002e>
/UKR <FEFF04120438043a043e0440043804410442043e043204430439044204350020044604560020043f043004400430043c043504420440043800200434043b044f0020044104420432043e04400435043d043d044f00200434043e043a0443043c0435043d044204560432002000410064006f006200650020005000440046002c0020044f043a04560020043d04300439043a04400430044904350020043f045604340445043e0434044f0442044c00200434043b044f0020043204380441043e043a043e044f043a04560441043d043e0433043e0020043f0435044004350434043404400443043a043e0432043e0433043e0020043404400443043a0443002e00200020042104420432043e04400435043d045600200434043e043a0443043c0435043d0442043800200050004400460020043c043e0436043d04300020043204560434043a0440043804420438002004430020004100630072006f006200610074002004420430002000410064006f00620065002000520065006100640065007200200035002e0030002004300431043e0020043f04560437043d04560448043e04570020043204350440044104560457002e>
/ENU (Use these settings to create Adobe PDF documents best suited for high-quality prepress printing. Created PDF documents can be opened with Acrobat and Adobe Reader 5.0 and later.)
>>
/Namespace [
(Adobe)
(Common)
(1.0)
]
/OtherNamespaces [
<<
/AsReaderSpreads false
/CropImagesToFrames true
/ErrorControl /WarnAndContinue
/FlattenerIgnoreSpreadOverrides false
/IncludeGuidesGrids false
/IncludeNonPrinting false
/IncludeSlug false
/Namespace [
(Adobe)
(InDesign)
(4.0)
]
/OmitPlacedBitmaps false
/OmitPlacedEPS false
/OmitPlacedPDF false
/SimulateOverprint /Legacy
>>
<<
/AddBleedMarks false
/AddColorBars false
/AddCropMarks false
/AddPageInfo false
/AddRegMarks false
/ConvertColors /ConvertToCMYK
/DestinationProfileName ()
/DestinationProfileSelector /DocumentCMYK
/Downsample16BitImages true
/FlattenerPreset <<
/PresetSelector /MediumResolution
>>
/FormElements false
/GenerateStructure false
/IncludeBookmarks false
/IncludeHyperlinks false
/IncludeInteractive false
/IncludeLayers false
/IncludeProfiles false
/MultimediaHandling /UseObjectSettings
/Namespace [
(Adobe)
(CreativeSuite)
(2.0)
]
/PDFXOutputIntentProfileSelector /DocumentCMYK
/PreserveEditing true
/UntaggedCMYKHandling /LeaveUntagged
/UntaggedRGBHandling /UseDocumentProfile
/UseDocumentBleed false
>>
]
>> setdistillerparams
<<
/HWResolution [2400 2400]
/PageSize [612.000 792.000]
>> setpagedevice
|