Высокопроизводительные вычисления и облачные технологии

 

 

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ  
РОССИЙСКОЙ ФЕДЕРАЦИИ 
НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ  

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ 
 
 
 
 
 
 
Д.В. Дружинин 
 
ВЫСОКОПРОИЗВОДИТЕЛЬНЫЕ 
ВЫЧИСЛЕНИЯ  
И ОБЛАЧНЫЕ ТЕХНОЛОГИИ  
 
Учебное пособие 
 
 
 
 
 
 
 
Томск 
Издательство Томского государственного университета 
2020 

УДК 004.272 
ББК 32.973 
        Д76 
 
Дружинин Д.В. 
Д76 
Высокопроизводительные вычисления и облачные  
технологии : учеб. пособие. – Томск : Издательство  
Томского государственного университета, 2020. – 94 с. 

ISBN 978-5-94621-921-1 
 
В работе дано описание основных технологий облачной обработки 
данных. Рассмотрены различные аспекты создания программ для высокопроизводительных вычислительных систем, освещены проблемы, возникающие на этом пути, и основные способы их решения. 
Для студентов вузов, обучающихся по направлению «01.04.02 – Прикладная математика и информатика» на магистерской программе «Интеллектуальный анализ больших данных». Материал, представленный в 
учебном пособии, будет интересен всем, кто изучает облачные технологии 
и параллельное программирование. 
 
УДК 004.272 
ББК 32.973 
 
Рецензенты: 
В.Л. Баденко, доктор технических наук, профессор; 
С.В. Аксёнов, кандидат технических наук, доцент 
 
 
 
 
 
 
 
 
 
 
© Томский государственный университет, 2020 
ISBN 978-5-94621-921-1 
© Дружинин Д.В., 2020 

 
 

ОГЛАВЛЕНИЕ 

 

Список условных обозначений  и сокращений ....................................................... 5 

Введение .................................................................................................................. 6 

1. Параллелизм компьютерных вычислений ........................................................... 8 

2. Архитектура вычислительных систем ............................................................... 11 

2.1. Классификация вычислительных систем ................................................... 11 

2.2. Классификация MIMD систем.................................................................... 12 

3. Грид-системы и облачные технологии .............................................................. 17 

3.1. Понятие и свойства грид-системы ............................................................. 17 

3.2. Концепция облачных технологий .............................................................. 18 

3.3. Сеть доставки содержимого ....................................................................... 22 

3.4. Обнаружение ресурсов в грид-системах .................................................... 22 

3.4.1. Подход, основанный на взаимодействии 
виртуальных организаций ............................................................................ 24 

3.4.2. Scalable Wide-Area Overlay-based Resource Discover (SWORD) ......... 26 

3.5. Соответствие виртуальной топологии  и аппаратной архитектуры ........... 29 

3.6. Справедливое распределение ресурсов  между приложениями................. 34 

3.7. MapReduce .................................................................................................. 40 

4. Распределённые файловые системы .................................................................. 44 

4.1. Google File System ...................................................................................... 45 

4.2. Hadoop distributed file system ...................................................................... 52 

5. Универсальные вычисления  на видеокарте ...................................................... 59 

5.1. Архитектура современных видеокарт ........................................................ 59 

5.2. Обзор программных интерфейсов .............................................................. 60 

5.3. Nvidia CUDA .............................................................................................. 62 

6. Программирование  для высокопроизводительных вычислений ...................... 68 

6.1. Показатели качества параллельных алгоритмов ........................................ 68 

6.2. Методология проектирования  параллельных алгоритмов ........................ 71 

6.2.1. Параллелизм данных ........................................................................... 71 

6.2.2. Параллелизм команд ........................................................................... 73 

6.3. Балансировка нагрузки в гетерогенных кластерах ..................................... 75 

6.3.1. Однородное разбиение ........................................................................ 75 

6.3.2. Константная модель производительности  
(англ. Constant Performance Model, CPM) ..................................................... 76 

6.3.3. Функциональная модель производительности  
(ФМП, англ. Functional Performance Model, FPM) ....................................... 76 

6.3.4. Частичная аппроксимация  функциональной модели 
производительности ..................................................................................... 81 

6.3.5. Применение функциональной модели  производительности  
в кластерах с иерархической структурой ..................................................... 84 

6.4. Шаблоны эффективной работы с памятью ................................................ 85 

6.4.1. Архитектура ........................................................................................ 86 

6.4.2. Измерение стоимости и сложности .................................................... 87 

6.4.3. Измерение эффективности .................................................................. 88 

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

 

 
 

Список условных обозначений  
и сокращений 

ℕ – множество натуральных чисел. 

ℝ – множество действительных чисел. 

<< – намного меньше. 

– округление x к меньшему целому. 

∠(M, L) – угол между прямыми M и L. 

HPC – высокопроизводительные вычисления (англ. High Performance Computing). 

UMA – однородный доступ к памяти (англ. Uniform Memory 
Access) 

NUMA – неоднородный доступ к памяти (англ. Non-Uniform 
Memory Access). 
 
 

Введение 

Существует множество задач, требующих большого количества 
вычислительных ресурсов. К таким задачам относятся моделирование различных процессов, вычислительные задачи математической статистики и криптографии. Раздел прикладной информатики, занимающийся поиском путей решения задач, требующих 
большого количества вычислительных ресурсов, называется высокопроизводительные 
вычисления 
(англ. 
High 
Performance 
Computing, HPC) [2].  
Рассмотрим способы повышения производительности вычислительной системы. Наиболее очевидный способ – это повышение 
тактовой частоты процессора. Но на этом пути возникают технологические сложности принципиального характера, связанные с 
физическими основами работы процессора. Основная проблема 
здесь заключается в том, что для увеличения быстродействия требуется уменьшение размера процессора, а при малых размерах полупроводниковых элементов процессоров возникают квантовомеханические эффекты, вносящие элементы недетерминированности [1].  
Другой способ повышения производительности вычислительной системы состоит в использовании параллельных вычислений. 
Параллельные вычисления – это такой способ организации компьютерных вычислений, при котором программы разрабатываются 
как набор взаимодействующих вычислительных процессов, работающих параллельно (одновременно). Именно с использованием 
параллельных вычислений строятся современные высокопроизводительные вычислительные системы, в том числе грид-системы. 
В настоящее время также получили распространение облачные 
технологии, предполагающие децентрализацию управления при 
параллельной обработке данных. 
В настоящем учебном пособии рассмотрены различные аспекты 
создания программ для высокопроизводительных вычислительных 

систем, освещены проблемы, возникающие на этом пути, и основные способы их решения. 
При создании учебного пособия использованы материалы схожих учебных дисциплин Санкт-Петербургского государственного 
политехнического университета, Национального открытого университета ИНТУИТ. 
Данное учебное пособие создано на основе курса лекций, читаемого автором по учебной дисциплине «Технологии высокопроизводительной обработки данных» для магистров, обучающихся на 
кафедре Теоретических основ информатики Института прикладной математики и компьютерных наук Томского государственного 
университета. 
В первой главе рассмотрены причины возникновения и уровни 
параллелизма компьютерных вычислений. Во второй главе приведён обзор существующих архитектур вычислительных систем. 
Третья глава посвящена грид-системам, и, в частности, способам 
обнаружения ресурсов в них, методам балансировки нагрузки. 
В четвёртой главе даётся определение и обсуждаются свойства 
облачных технологий, рассмотрены технология обработки данных 
MapReduce и некоторые распределённые файловые системы. 
В пятой главе уделено внимание технологиям, позволяющим проводить универсальные вычисления на видеокарте. В шестой главе 
рассмотрены некоторые аспекты программирования для высокопроизводительных вычислений. 
Учебное пособие предназначено для студентов вузов, обучающихся по направлению «01.04.02 – Прикладная математика и информатика» на магистерской программе «Интеллектуальный анализ больших данных». Материал, представленный в учебном пособии, будет интересен всем, кто изучает облачные технологии и 
параллельное программирование. 
 

1. Параллелизм компьютерных вычислений 

Известный специалист по архитектуре компьютеров М. Флинн 
первым обратил внимание на существование двух причин, порождающих вычислительный параллелизм – независимость потоков 
команд, одновременно существующих в системе, и несвязанность 
данных, обрабатываемых в одном потоке команд. Принцип независимости потоков команд реализован во многих современных 
операционных системах (ОС) в форме мультипроцессирования. 
Мультипроцессирование предполагает одновременное выполнение 
нескольких процессов ОС на процессорах (или ядрах процессора) 
вычислительной система. Простейшим типом параллелизма данных является последовательность из нескольких команд, обрабатывающих 
несвязанные 
между 
собой 
данные. 
Например, 
A = B + C; D = E × F.  
Результатом теоретического осмысления проблемы программного параллелизма стало создание нескольких классификаций видов такого параллелизма. Рассмотрим одну из наиболее известных 
классификаций такого рода, предложенную П. Треливеном, в соответствии с которой выделяется четыре основных уровня параллелизма (рис. 1.1). 
Параллелизм верхнего уровня в соответствии с приведённой 
классификацией достигается за счёт мультипроцессирования. 
Остальные виды параллелизма оперируют несвязанными потоками 
данных.  
Команда языка высокого уровня, как правило, разбивается на 
несколько стадий для выполнения на процессоре. Это позволяет 
большую часть вычислительного процесса производить в режиме 
совмещения выполнения команд в конвейере. Так обеспечивается 
параллелизм на уровне фаз отдельной команды. 
Рассмотрим для примера простой пятиуровневый конвейер в 
RISC-процессорах (рис. 1.2). Каждая команда здесь выполняется в 
пять стадий: 

 IF (Instruction Fetch) – получение инструкции; 
 ID (Instruction Decode) – раскодирование инструкции; 
 EX (Execute) – выполнение; 
 MEM (Memory access) – доступ к памяти; 
 WB (Register write back) – запись в регистр. 
 

 
 
Рис. 1.1. Классификация уровней параллелизма, предложенная П. Треливеном 

 

 
Рис. 1.2. Простой пятиуровневый конвейер в RISC-процессорах 

На пятом шаге, когда первая команда находится на последней 
стадии выполнения, достигается полная загрузка конвейера. 
Несвязанные операции выполняются с помощью набора самостоятельных арифметических устройств в составе центрального 
процессора (принцип многофункциональной обработки) [4]. Обычно набор таких устройств состоит из сложителя, умножителя, делителя, устройств выполнения логических и сдвиговых операций. 
Обработка параллелизма циклов реализуется в форме векторных операций. При этом увеличение скорости вычислений достигается за счёт сокращения количества выполняемых процессором 
команд, связанных с пересчётом индексов и условными переходами, а также за счёт параллелизма операций над векторами. Векторные команды поддерживаются в современных персональных 
компьютерах (ПК) в ограниченном объёме за счёт использования 
векторных расширений процессора. Так за один такт процессорного времени может обрабатываться значение размером в 64 (MMX) 
или 128 (SSE3) битов [19]. Более широкая поддержка векторных 
операций реализована в векторных суперкомпьютерах. 
 

2. Архитектура вычислительных систем 

2.1. Классификация вычислительных систем 

Рассмотрим классификацию вычислительных систем Флинна, 
основанную на анализе количества потоков команд и количества 
потоков данных (рис. 2.1). 
 

 
 
Рис. 2.1. Классификация вычислительных систем Флинна 
 
SISD (англ. Single Instruction, Single Data) – системы с одним 
потоком команд и одним потоком данных. Классическим примером является архитектура фон Неймана со строго последовательным выполнением команд. 
SIMD (англ. Single Instruction, Multiple Data) – системы с одним 
потоком команд и множеством потоков данных. Данная архитектура предполагает наличие управляющего устройства (контроллера) и набора процессорных элементов. Управляющий модуль принимает, анализирует и выполняет команды. Если в команде встречаются данные, контроллер рассылает на все процессорные элементы команду, и эта команда выполняется на нескольких или на 
всех процессорных элементах. Каждый процессорный элемент 
имеет свою собственную память для хранения данных. К этому 
типу систем относятся векторные компьютеры, в которых операн

дами некоторых команд могут выступать одномерные массивы 
данных (векторы). 
MISD (англ. Multiple Instruction, Single Data) – системы с множеством потоков команд и одним потоком данных. Самая простая 
и распространённая система этого класса – локальная вычислительная сеть (ЛВС) персональных компьютеров, работающая с 
единой базой данных [4]. 
MIMD (англ. Multiple Instruction, Multiple Data) – системы с 
множеством потоков команд и множеством потоков данных. К 
этому классу относится подавляющее большинство современных 
высокопроизводительных вычислительных систем. Рассмотрим 
классификацию таких систем. 

2.2. Классификация MIMD систем 

Классификация MIMD систем представлена на рис. 2.2. 
 

 
 

Рис. 2.2. Классификация MIMD систем