Повышение производительности гетерогенных компьютерных систем обработки данных

А. А. Колпаков 
Ю. А. Кропотов 

ПОВЫШЕНИЕ 
ПРОИЗВОДИТЕЛЬНОСТИ 
ГЕТЕРОГЕННЫХ 
КОМПЬЮТЕРНЫХ СИСТЕМ 
ОБРАБОТКИ ДАННЫХ 

Монография 

Москва 
Берлин 
2019 

УДК 004.021 
ББК 32.972.11 
  К61 

Рецензенты: 
Петров А. Б. — зав. кафедрой «Корпоративных информационных систем» 
ФГБОУ ВО Московский технологический университет, д-р техн. наук, профессор; 
Пащенко Д. В. — зав. кафедрой «Вычислительной техники» 
ФГБОУ ВО «Пензенский государственный университет», 
д-р техн. наук, профессор 

Колпаков, А. А.

Б73
Повышение производительности гетерогенных компьютер-

ных систем обработки данных: монография / А. А. Колпаков, 
Ю. А. Кропотов — Москва ; Берлин : Директ-Медиа, 2019. — 
121 с.

ISBN 978-5-4475-8156-5 

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

УДК 004.021 
ББК 32.972.11 

ISBN 978-5-4475-8156-5
© Колпаков А. А., Кропотов Ю. А. текст, 2019
© Издательство «Директ-Медиа», оформление 2019

ОГЛАВЛЕНИЕ 

Введение ................................................................................................................................. 5 

Глава 1 Методы повышения производительности 
вычислительных процессов в компьютерных системах 
обработки данных ............................................................................................................ 7 
1.1 Структура производительных многопроцессорных 
вычислительных систем ......................................................................................... 7 
1.2 Аналитические модели параллельных вычислений .................. 14 
1.3 Математические методы анализа и обработки данных ........... 19 
1.4 Структурные методы повышения производительности 
вычислительных систем ...................................................................................... 25 
1.5 Выводы и постановка задачи исследований ................................... 31 

Глава 2 Модели параллельных вычислений с использованием 
специализированных вычислительных модулей ..................................... 33 
2.1 Многоканальная система обработки дискретных 
последовательностей ............................................................................................. 33 
2.2. Исследование ускорения вычислений в системе 
из специализированных вычислительных модулей.......................... 37 
2.3 Исследование и разработка структурной схемы 
архитектуры гетерогенной системы «CPU-GPU» .................................. 42 
2.4 Модель PRAM с учетом архитектуры гетерогенной 
системы «CPU-GPU» ................................................................................................. 44 
2.5 Выводы .................................................................................................................... 46 

Глава 3 Алгоритмы повышения производительности 
вычислений в гетерогенных многопроцессорных  
вычислительных компьютерных системах ................................................... 47 
3.1 Алгоритм повышения производительности 
гетерогенной многопроцессорной системы............................................ 47 
3.2 Методы и алгоритмы декомпозиции задачи 
при выполнении параллельных вычислений в гетерогенной 
многопроцессорной вычислительной системе ..................................... 49 

3.3 Методы уменьшения времени выполнения алгоритма 
путем уменьшения потока данных между оперативной 
памятью и GRAM ....................................................................................................... 54 
3.4 Алгоритм принятия решения о переносе вычислений 
на графический процессор и использовании кэширования 
данных ............................................................................................................................. 55 
3.5 Выводы .................................................................................................................... 61 

Глава 4 Программное обеспечение гетерогенных 
компьютерных систем и структуры систем обработки данных ......... 62 
4.1 Технологии программирования графических 
процессоров .................................................................................................................. 62 
4.1.1 Программирование графического процессора 
на основе вершинных и пиксельных программ .............................. 62 
4.1.2. Программирование графического процессора 
на основе библиотеки CUDA ......................................................................... 64 
4.1.3 Программирование графического процессора 
на основе библиотеки OpenCL .................................................................... 67 
4.2 Разработка и исследование структурной схемы 
программного обеспечения гетерогенной компьютерной 
системы обработки данных ............................................................................... 73 
4.3 Разработка модуля обработки программного кода .................... 75 
4.4 Экспериментальная оценка эффективности работы 
алгоритма повышения производительности гетерогенной 
компьютерной системы ....................................................................................... 92 
4.5 Алгоритм обработки данных и аудио-видео информации 
в микропроцессорной вычислительной системе 
с применением графических процессоров в системе 
телекоммуникации .................................................................................................. 96 
4.6 Выводы ..................................................................................................................107 

Заключение ......................................................................................................................108 

Литература .......................................................................................................................109 

ВВЕДЕНИЕ 

Задача создания высокопроизводительных вычислительных 
комплексов на базе компьютерных систем является актуальной, так 
как объемы обрабатываемой информации, объемы выполняемых 
вычислений и исследований с большими массивами данных постоянно 
увеличиваются. В то же время существующие высокопроизводительные 
вычислительные машины имеют ограниченный доступ 
в связи с их использованием для осуществления приоритетных фундаментальных 
исследований и решения важных научно-технических 
задач, имеющих большое прикладное значение. Поэтому в 
настоящее время достаточно интенсивно исследуются и развиваются 
методы повышения производительности массовых вычислительных 
компьютерных систем. 
Для увеличения эффективности компьютерных вычислений часто 
применяется использование многопроцессорной архитектуры. 
Однако, как известно [Graham, R. Bound on multiprocessing timing 
anomalies. /R. Graham // SIAM Journal on Applied Mathematics. March 
1969 г.; Amdahl, G. Validity of the Single Processor Approach to Achieving 
Large-Scale Computing Capabilities./G. Amdahl //1967. AFIPS spring 
joing computer conference] производительность многопроцессорных 
вычислений за счет дальнейшего увеличения процессоров существенно 
не повышается при превышении их количества определенного 
предела. В то же время современные компьютерные системы в 
своем составе могут содержать, кроме центрального процессора, спе-
циализированные вычислительные модули. Поэтому для решения 
задачи повышения производительности компьютерных систем рас-
сматривается возможность распараллеливания программ на почти 
произвольное количество вычислений с использованием гетеро-
генной платформы на специализированных вычислительных моду-
лях. 
Существенным ограничением на повышение производительно-
сти вычислений с применением специализированных процессоров 
является наличие аппаратной поддержки чисел с плавающей точкой 
разрядностью не выше 32 бит. На последних моделях специализиро-
ванных процессоров и на профессиональных видеокартах возможна 
аппаратная поддержка чисел с большей разрядностью, но количе-
ственная оценка повышения производительности вычислений та-
ким методом требует дополнительных исследований. 

В данной работе исследования базируются на результатах работ 
в области параллельных вычислительных технологий таких учё-
ных, как: Е. П. Балашов, В. Б. Бетелин, В. С. Бурцев, В. В. Васильев, 
S. Cray, A. Tanenbaum, D. Feitelson. При решении проблем оптимиза-
ции функционирования многопроцессорных вычислительных си-
стем большую роль сыграли фундаментальные работы в области
математического программирования и исследований вычислитель-
ных операций таких учёных, как В. Л. Береснев, Э. Х. Гимади, В. Т. Де-
ментьев, R. Bellmann, D. Johnson. Развитию существующих моделей
параллельных вычислений посвящены работы S. Fortune, J Wyllie,
L. Valiant, B. B. Воеводина, B. C. Любченко. Специфика вычислений на
сопроцессорах и графических процессорах представлена в работах
S. Hong, H. Kim, W. W. Hwu, А. В.  Борескова, В. А. Фролова.
Повышение эффективности вычислительных компьютерных си-
стем в известных работах показано в зависимости от организации 
процесса решения задач. В общем случае задачи представляются па-
раллельными программами и описываются рядом параметров, в 
числе которых: количество ветвей, ранг необходимой подсистемы, 
время решения и т. п. Режим функционирования высокопроизводи-
тельных вычислительных систем формируется мультипрограмм-
ным методом или в некоторых вычислительных компьютерных си-
стемах используется частичное применение вычислительных 
модулей, что в недостаточной степени обеспечивает повышение 
производительности вычислений. 
В связи с этим в монографии рассмотрены и исследованы во-
просы повышения производительности компьютерных систем на 
основе модели архитектуры с использованием дополнительных вы-
числительных производительных модулей или с использованием 
однородных модулей на графических процессорах. 
Монография состоит из четырех глав, в первой главе рассматри-
вается состояние вопроса повышения производительности компью-
терных систем. Во второй главе показано, что исследуемые процессы 
можно аппроксимировать суммой многочленов, тем самым обосно-
вывается распараллеливание вычислительных процессов и процес-
сов обработки данных, что повышает производительность вычисле-
ний. В третьей главе исследуются алгоритмы функционирования 
многопроцессорной компьютерной вычислительной системы с ис-
пользованием специализированных вычислительных модулей в 
среде CPU-GPU. В четвертой главе исследуются методы тестирова-
ния и представлена разработка программных структур с повышен-
ной производительностью. 

ГЛАВА 1 
МЕТОДЫ ПОВЫШЕНИЯ 
ПРОИЗВОДИТЕЛЬНОСТИ ВЫЧИСЛИТЕЛЬНЫХ 
ПРОЦЕССОВ В КОМПЬЮТЕРНЫХ СИСТЕМАХ 
ОБРАБОТКИ ДАННЫХ 

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

При высоких требованиях к надежности и производительности 
вычислительных средств определяющим является требование низкой 
стоимости вычислительной системы. Это требование является 
одним из основных при создании массовой вычислительной техники, 
примерами которой являются микропроцессоры и микроЭВМ 
[67]. 
Микропроцессорные средства возникли в результате развития 
технологии и вычислительной техники [67]. При построении современных 
микропроцессорных систем используют, в основном, следующие 
принципы: микропрограммное управление, модульность построения, 
магистральный обмен информацией, наращиваемость 
вычислительной мощности [67]. 
Одной из наиболее важных характеристик вычислительной системы 
является ее быстродействие, определяемое как временная 
задержка выходных данных относительно входных, то есть промежуток 
времени между вводом информации, необходимой для решения 
задачи, и выдачей результата [67]. 
Из-за конечной скорости передачи информации между элементами 
вычислительной машины наступает предел производительности 
вычислений. Наличие теоретического предела производи-
тельности обусловлено моделью вычислений, положенной в основу 
построения средств вычислительной техники. В [20] рассматрива-
ются две основные модели вычислений, использующихся в настоя-
щее время: модель вычислителя и модель коллектива вычислите-
лей. 
Модель вычислителя использовалась при построении ЭВМ 
первых трех поколений, а также при построении простейших 
современных однопроцессорных ЭВМ. Наиболее существенный 

недостаток данной модели — наличие теоретического предела про-
изводительности вычислений. Это связано, в первую очередь, с по-
следовательным выполнением операций, а также с ограниченной 
скоростью передачи информации между элементами системы. 
Модель коллектива вычислителей была предложена для 
построения высокопроизводительных вычислительных систем и 
принципиально отличается от модели вычислителя тем, что подра-
зумевает выполнение коллективом вычислителей единой сложной 
задачи, при этом задача представляется в виде совокупности свя-
занных между собой частей. Выполнение каждой задачи приписы-
вается одному из использованных в модели вычислителей. Основ-
ные принципы построения модели коллектива вычислителей 
следующие. 
Вычислительные средства, построенные на основе модели кол-
лектива вычислителей, являются универсальными и позволяют ре-
шать сложные задачи. На основе подобной модели строятся совре-
менные персональные ЭВМ, а также высокопроизводительные 
многопроцессорные вычислительные системы [20, 64]. 
Многопроцессорные вычислительные системы. Система, содер-
жащая несколько процессоров, работающих на общем пространстве 
обрабатываемых данных, и управляемая одной общей операцион-
ной системой, называется многопроцессорной [20, 30, 55]. 
Разновидностью многопроцессорных систем является мульти-
процессорная система [20] — система, в которой могут быть актив-
ными сразу несколько процессоров. Пока процессоры выполняют 
обработку данных, они работают независимо друг от друга. Но в 
определенные моменты времени, обусловленные алгоритмом вы-
числения, процессоры должны синхронизировать свои действия [1]. 
По типам процессоров многопроцессорные системы могут быть 
разделены на однородные и неоднородные: однородные содержат 
однотипные процессоры, неоднородные состоят из различных спе-
циализированных процессоров [64]. Примером может служить си-
стема, содержащая центральный процессор и процессор ввода-вы-
вода [64]. Специализированный процессор выполняет операции 
строго определенного класса, в связи с этим задача распараллелива-
ния в неоднородных системах обычно сводится к распределению 
операций между процессорами в соответствии с их классами. В од-
нородных системах любая операция может быть выполнена на 

любом из имеющихся процессоров, поэтому задача распараллелива-
ния в однородных системах достаточно трудоемка. 
По количеству уровней многопроцессорные системы могут де-
литься на одноуровневые и иерархические (многоуровневые). 
В  первом случае процессоры системы образуют один общий уро-
вень обработки данных, во втором (рис. 1.1) система содержит от-
дельные процессоры для выполнения различных уровней обра-
ботки информации. Обычно менее мощный процессор выполняет 
ввод-вывод информации с различных терминалов и ее предвари-
тельную обработку. 

 

Рис. 1.1. Иерархическая многопроцессорная система 

Одноуровневые многопроцессорные системы могут быть клас-
сифицированы по типу связи процессоров с оперативной памятью 
данных. В соответствии с данной классификацией системы отно-
сятся к одному из трех типов [64]: 
С общей (равнодоступной) памятью данных. 
С индивидуальной (раздельной) памятью данных. 
С индивидуальной основной и общей вспомогательной опера-
тивной памятью данных. 
Наиболее распространенными представителями многопроцес-
сорных систем с общей модульной оперативной памятью данных 
является общая магистральная архитектура [4, 20, 30], которая 
представлена на рис. 1.2. 
Как видно из рис. 1.2, магистральная многопроцессорная си-
стема отличается тем, что несколько процессоров подключаются к 
одной магистрали, которая осуществляет связь между любыми про-
цессорами. Организация межпроцессорных связей на основе общей 

Центральный процессор

Вспомогательный процессор

ВЗУ
УВВ

магистрали является одним из распространенных способов постро-
ения многопроцессорных систем. Такая система является наиболее 
простой, дешевой и легко наращиваемой. В соответствии с данной 
структурой строятся универсальные микроЭВМ, в частности, ком-
пьютеры типа IBM PC [4, 30]. 
 

 

Рис. 1.2. Магистральная многопроцессорная система 

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

Рис. 1.3. Многопроцессорная система с индивидуальной памятью 

Как видно из рис. 1.3, каждый процессор обращается к своему 
модулю оперативной памяти. Однако возможен редкий обмен дан-
ными между процессорами, который обычно построен на основе по-
следовательных каналов передачи данных. В связи с этим учет за-
трат времени на межпроцессорный обмен ведется на основе объема 
передаваемых данных. 
Частным случаем подобного класса систем является многопро-
цессорная система с матричной структурой, которая представлена 
на рис. 1.4. 

 

Рис. 1.4. Матричная многопроцессорная система 

В матричной многопроцессорной системе (рис. 1.4) каналы 
связи организованы по принципу близкодействия: жесткие связи 
между собой имеют только соседние процессоры, а между отдален-
ными процессорами каналы связи отсутствуют. Обмен информа-
цией между ними возможен только через цепочку процессоров. 
Данная структура характерна для ЭВМ, построенных на базе 
транспьютеров [49]. Для организации связи с другими транспьюте-
рами, каждый транспьютер имеет несколько последовательных 
двунаправленных канала связи (линков). Благодаря прямому 
доступу к памяти обмен данными по каналам связи может осу-
ществляться одновременно с работой остальных устройств транс-
пьютера. Современные сигнальные процессоры, предназначенные 
для цифровой обработки сигналов, например ADSP21060 фирмы 
Analog Devices также оснащаются линками для объединения их в 
матричную схему [63, 71]. 
Многопроцессорная система с индивидуальной основной и общей 
вспомогательной оперативной памятью данных является эффективной 
для многопрограммной работы с коллективным использованием 
большого архива базовых данных. Ее схема изображена на 
рис. 1.5. 

 

Рис. 1.5. Многопроцессорная система с общей памятью данных 

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