1 АНАЛИТИЧЕСКИЙ ОБЗОР ЛИТЕРАТУРЫ
1.1 Анализ существующих методик управления распределёнными вычислениями и аналогов
Потребность в параллельных вычислениях возникла ещё на заре компьютерной техники, и к настоящему времени возникло множество подходов к параллелизации – от параллелизма на уровне инструкций до слабосвязанных гетерогенных распределённых систем. Существует несколько критериев классификации таких подходов.
Один из таких критериев – способ взаимодействия процессов в параллельной системе. С этой точки зрения различают два вида систем.
1) Системы с разделяемой памятью. К этой группе относятся многоядерные и многопроцессорные ЭВМ, каждый процессор которых имеет доступ к общему устройству памяти. Параллелизация в таких системах осуществляется в пределах одной машины и реализуется, как правило, многопоточными приложениями. Многопоточность означает, что процесс, запущенный в системе, может состоять из нескольких потоков выполнения, выполняющихся одновременно. Потоки в пределах одного процесса имеют доступ к одному адресному пространству. Это упрощает обмен данными между потоками, зато порождает ряд проблем, связанных с использованием общих данных, что требует специальных механизмов синхронизации.
2) Системы с распределённой памятью, в которых каждый процессор имеет доступ только к своему устройству памяти. Такие системы называют распределёнными, и они обычно представляют собой группу независимых ЭВМ, соединённых сетью. Для взаимодействия в таких системах используется механизм обмена сообщениями, который будет рассмотрен ниже.
При классификации параллельных вычислительных систем также часто применяют подход, известный под названием «Таксономия Флинна» [13]. Это общая классификация архитектур вычислительных систем по признакам наличия параллелизма в потоках команд и данных, предложенная в начале 1970-х профессором Стэндфордского университета Майклом Флинном. Всё разнообразие архитектур ЭВМ в этой классификации сводится к четырём классам:
1) SISD (Single Instruction stream over a Single Data stream) – вычислительная система с одиночным потоком команд и одиночным потоком данных. Соответствует традиционной архитектуре фон Неймана без параллелизации.
2) SIMD (Single Instruction, Multiple Data) – вычислительная система с одиночным потоком команд и множественным потоком данных. Типичные представители этой группы – векторные процессоры, у которых, в отличие от традиционных скалярных процессоров, каждая инструкция работает не с единственным значением (например, регистром), а с массивами значений.
3) MISD (Multiple Instruction, Single Data) – вычислительная система с множественным потоком команд и одиночным потоком данных. К классу MISD ряд исследователей относит конвейерные ЭВМ, однако это не нашло окончательного признания.
4) MIMD (Multiple Instruction, Multiple Data) – вычислительная система с множественным потоком команд и множественным потоком данных. Такие системы включают несколько процессоров, которые функционируют асинхронно и независимо. В любой момент, различные процессоры могут выполнять различные команды над различными частями данных. Именно к этой группе относятся широко применяемые многоядерные, многопроцессорные и распределённые системы. В рамках этой группы следует отметить такие архитектуры, как SMP и SPMD.
SMP (Symmetric Multiprocessing), или симметричная мультипроцессорность – это архитектура многопроцессорных компьютеров, в которой два или более одинаковых процессоров подключаются к общей памяти. SMP поддерживается большинством многоядерных и многопроцессорных ЭВМ и позволяет использовать в программе многопоточность – возможность одновременного выполнения в одном адресном пространстве нескольких последовательностей команд. Для программирования многопоточных приложений создан стандарт OpenMP (Open Multi-Processing), который описывает ряд библиотечных функций для создания потоков, синхронизации и распределения работы между потоками.
Другой MIMD-подход к параллелизации – это SPMD (single program, multiple data). В этой модели вычислительные процессы работают с разными данными на разных процессорах, но представляют собой разные ветви одной программы. Т.е. после запуска процесса начинаются выполняться различные части алгоритма в зависимости от того, на каком процессоре запущен исполняемый файл. SPMD, в отличие от SMP, обычно реализуется на основе полноценных процессов с независимыми адресными пространствами, а не потоков. Существует также подход MPMD (Multiple Program, Multiple Data), в котором на разных процессорах запускаются разные исполняемые файлы, каждый для решения своей задачи. Такой подход применяется реже и по своей схеме применения мало отличается от SPMD. Как правило, именно SPMD-модель используется при распределённых вычислениях, производимых на независимых машинах. Компьютеры при распределённых вычислениях объединены сетью: локальной, глобальной, а в некоторых суперкомпьютерах – с помощью специальных сетевых технологий. Группу компьютеров, использующуюся для распределённого решения одной задачи, часто называют кластером. Слабосвязанные кластеры, основанные на обычных пользовательских компьютерах и объединённых сетью Интернет, называют грид-системой, или виртуальным суперкомпьютером.
Машины в распределённой системе не имеют доступа к памяти друг друга, поэтому для синхронизации и обмена данными между процессами используется модель обмена сообщениями [14]. В это модели каждый процесс обладает уникальным идентификатором. Процессы взаимодействуют, посылая и получая сообщения. Под сообщением понимается пакет информации, который может означать вызов функции, данные, сигнал синхронизации и т.п. Модель обмена сообщениями используется также в объектно-ориентированном программировании, где посылкой сообщения является вызов метода у объекта.
В SPMD-модели обмен сообщениями обычно представляют собой передачу пакетов по сети. Все системы распределённых систем, включая данный дипломный проект, так или иначе используют обмен сообщениями, который может быть реализован с помощью различных технологий: RPC, CORBA, .Net Remoting, WCF или иным способом. Специально для распределённых вычислений были разработан стандарт обмена сообщениями MPI.
MPI (Message Passing Interface) – это спецификация программного интерфейса (API) для обмена сообщениями между компьютерами, параллельно решающими общую задачу [16]. Первая версия MPI была опубликована в 1994 году. Стандарт MPI описывает синтаксис и семантику процедур, функций и типов данных (независимо от языка программирования), которые могут быть использованы программами, осуществляющими обмен сообщениями. MPI – один из самых распространённых стандартов, применяемых при распределённых вычислениях. Реализации MPI часто применяются в суперкомпьютерах, например, в семействе суперкомпьютеров "СКИФ" в качестве базовой классической системы поддержки параллельных вычислений выбран MPI [6]. Существует ряд реализаций MPI для разных язков программирования и разных платформ, но наиболее распространены реализации для языков C, C++ и Fortran.
Основная задача MPI – предоставить инструменты для обмена информацией, синхронизации и управления виртуальной топологией сети для совокупности процессов, работающих на кластере. Процесс – базовое понятие при обмене сообщениями в MPI. Каждому процессу система назначает идентификатор, который затем используется при адресации сообщений. Процессы можно объединять в группы. Пользователь может определять, сколько процессов запускать на каждой машине системы, но общепринятая практика – создавать один процесс на каждый процессор или ядро многоядерного процессора.
Основная функциональность, предоставляемая MPI – это процедуры парного и коллективного межпроцессного взаимодействия.
1) Парное взаимодействие процессов (Point-To-Point Communication) – включает функции для обмена информацией между двумя определёнными процессами. Например, функция MPI_SEND позволяет одному процессу отправить сообщение другому процессу с указанным идентификатором, а MPI _RECV – получить сообщение от определённого процесса. Существуют блокирующие и неблокирующие варианты таких вызовов.
2) Коллективное взаимодействие (Collective Communication). Эта группа функций предоставляет функционал для взаимодействия между всеми процессами группы:
- широковещательная передача (broadcast) данных от одного процесса всем процессами группы (вызов MPI_BCAST);
- сбор данных из всех процессов группы в один процесс (вызовы MPI_GATHER, MPI_REDUCE);
- барьерная синхронизация всех процессов группы (MPI_BARRIER).
Также MPI включает различные методы для работы с сетью (получение количества доступных процессов, динамическое создание новых процессов и управление ими) и другие типы вызовов. Всего стандарт MPI-2 описывает более 500 различных функций.
Наиболее широко применяемые реализации MPI:
1) MPICH – бесплатная реализация, работает на UNIX-системах и Windows NT. Поддерживает языки C, C++, Fortran. На её основе, в свою очередь, были созданы многие другие библиотеки MPI.
2) LAM/MPI (Local Area Multicomputer) – бесплатная реализация, поддерживающая гетерогенные кластеры.
3) OpenMPI – реализация MPI-2, созданная как проект, объединяющий лучшие подходы нескольких реализаций MPI: LAM/MPI, FT-MPI и LA-MPI. OpenMPI сейчас применяется на многих современных суперкомпьютерах, таких как IBM Roadrunner и K computer, занявший в 2011 году первое место в рейтинге суперкомпьютеров TOP500.
4) CSWMPI – коммерческая реализация MPI для Windows.
5) MPJ – реализация MPI для Java.
Как видно из обзора функциональности MPI, задача библиотек, реализующих этот стандарт – предоставить пользователю достаточно низкоуровневые инструменты для межпроцессного взаимодействия в системах с распределённой памятью. На основе MPI можно решить практически любую задачу, но многие аспекты распределённых вычислений пользователю придётся решать самому. MPI не описывает методы развёртывания исполняемого кода на кластере, оптимального распределения нагрузки и т.д., он лишь даёт средства, с помощью которых программист может реализовать этот функционал. Задачи данного дипломного проекта несколько отличаются от задач реализаций MPI. Цель этого проекта – создать сервис, который позволял бы выполнять распределённые вычисления при минимальных трудозатратах программиста, он должен сам управлять разбиением задачи на подзадачи, выравниванием нагрузки, сбором результатов вычислений. Одну из реализаций MPI теоретически можно было бы использовать как основу при создании такого ПС, но так как стандарт ориентирован на использование в локальной сети, не существует подходящих реализаций, которые позволили бы использовать обмен сообщениями через Интернет. Возможность работы через Интернет является одним из требований, поставленных при разработке данного проекта, поэтому применение стандарта MPI в рамках этой задачи нецелесообразно. Однако подходы этого стандарта можно использовать в процессе разработки интерфейса обмена сообщениями в данном проекте.
Одним из основных конкурентом MPI считается система PVM.
PVM (Parallel Virtual Machine) – программный пакет, написанный на С, позволяющий объединять разнородный набор компьютеров под управлением Unix и Windows в общий вычислительный ресурс («виртуальную параллельную машину»). Первая версия PVM вышла в 1989 году.
Концепции PVM и MPI в целом схожи. Как и MPI, PVM предоставляет различные функции для обмена сообщениями, включая парный обмен и широковещательную передачу. Поддерживается также синхронизация действий в группе процессов и совместное выполнение процессами некоторых операций над распределенными данными (фрагменты обрабатываемых данных распределены между задачами – членами группы). PVM, как и MPI, работает с процессами, каждому процессу присваивая идентификатор. Имеется также и ряд отличий от MPI, которые нецелосообразно подробно рассматривать в рамках данного проекта, т.к. эти системы имеют общий подход к параллельному программированию. Самое существенное отличие в том, что MPI – это спецификация, независимая от языка, а PVM – это конкретное программное средство.
Система PVM состоит из двух частей. Первая часть – это программа-демон под названием pvmd, который устанавливается на все компьютеры, создающие виртуальную машину. Демон отвечает за коммуникацию между потоками и управление ими, включая порождение и завершение потоков. Все эти действия демонов инициируются приложениями пользователя путём соответствующих вызовов.
Вторая часть системы – это библиотека подпрограмм интерфейса PVM. Она содержит вызываемые пользователем подпрограммы для обмена сообщениями, порождения процессов, координирования задач.
Общая схема программирования с помощью PVM следующая. Сначала пишется исходный код программы, причём часто для решения задачи необходимо создать несколько приложений – основное, «инициирующее» приложение, управляющее запуском остальных, и ряд других приложений для решения отдельных частей задачи. Поддерживаются программы на C, C++ или Фортран. Затем необходимо скомпилировать исходный код и скопировать получившиеся исполняемые файлы на каждую машину кластера. Для выполнения приложения пользователь обычно запускает одну копию задачи («ведущая» или «инициирующая» задача) вручную на одной из машин. Этот процесс последовательно порождает другие задачи PVM; в конечном счете получается группа активных задач, оперирующих локально и обменивающихся сообщениями друг с другом для решения проблемы [12].
Эта схема использования близка к методике использования MPI и имеет такие же отличия от предполагаемой схемы применения данного дипломного проекта. Применение пакета PVM требует сравнительно долгой подготовки к решению каждой задачи и требует от пользователя дополнительных действий по распределению нагрузки. Поэтому он ориентирован на решение серьёзных, долгосрочных задач, например, научных, промышленных и медицинских проблем и малопригоден для решения повседневных, но вычислительно сложных проблем.
Существует ряд программных пакетов, которые выполняют задачи, схожие с поставленными в данном проекте – автоматическое разбиение задачи на составные части, которые будут выполняться параллельно, выполнение этих частей и объединение полученных результатов. Очень часто при таком подходе применяется парадигма MapReduce – универсальный метод гибкого управления распределёнными вычислениями.
MapReduce – это модель распределённых вычислений, разработанная и запатентованная Google в 2004 году, ориентированная на обработку сверхбольших массивов данных. Она позволяет, например, параллельно производить сортировку массива данных, который не помещается в памяти одной машины. В качестве примера таких данных можно привести информацию, полученную поисковыми роботами и различными краулерами, статистику, собранную с сайтов социальных сетей и т.п. Впервые эту технологию применил Google в одноименном фреймворке, который использовался поисковиком для индексирования Всемирной паутины [7]. Позже были созданы другие реализации концепции для разных платформ и языков программирования. MapReduce и его реализации – один из главных инструментов для обработки так называемых Больших Данных (англ. Big Data) – неструктурированных данных огромных объёмов и значительного многообразия.
В качестве исходных данных для алгоритма, кроме массива исходных данных, программист должен предоставить 2 функции: Map и Reduce. Эти функции названы по одноименным функциям высшего порядка (map –применить-ко-всем, reduce – свёртка списка), хотя фактически их семантика в данной модели несколько отличается.
1) На первом шаге работы алгоритма (фаза Map) для каждого элемента исходного массива вызывается функция Map. Она принимает элемент исходных данных, а возвращает список пар ключ-значение. Т.е. конвертирует один элемент начальных данных в ноль или более промежуточных элементов данных, каждый из которых снабжён ключом. Ключ вводится для того, чтобы алгоритм мог отсортировать этим промежуточные значения и сгруппировать их.
Рисунок 1.1 – Иллюстрация работы операции Map [8]
2) На втором шаге алгоритм выполняет параллельную сортировку полученных промежуточных пар ключ-значение и группирует их по ключу, чтобы на следующем шаге передать в операцию Reduce:
Рисунок 1.2 – Иллюстрация группировки промежуточных результатов
3) Функция Reduce получает список промежуточных значений и их общий ключ, а возвращает список окончательных значений (часто этот список состоит только из одного значения). Результаты работы всех вызовов Reduce объединяются и представляют собой результат работы алгоритма. Такую операцию называют свёрткой промежуточных значений.
Рисунок 1.3 – Иллюстрация работы операции Reduce
Простейший пример применения MapReduce – подсчёт частоты встречаемости слов в Википедии. Функция Map будет принимать текст одной статьи, разбивать её на слова и для каждого уникального в пределах статьи слова выдавать пары «ключ: слово, значение: количество_вхождений_слова_в_текст_статьи». Затем алгоритм отсортирует все полученные пары и объединит их в группы по ключу. Функция Reduce получит на входе слово и массив цифр, означающих количество вхождений этого слово в различные статьи. Ей остаётся только просуммировать элементы этого массива и выдать объект «слово, количество_вхождений».
Парадигма MapReduce имеет два больших достоинства. Первое – это параллельность. Операции Map и Reduce могут выполняться одновременно на разных компьютерах, так как каждая операция работает с независимым фрагментом данных (что обеспечивается группировкой значений по ключу). Промежуточные операции – сортировка и группировка – тоже могут выполняться частично параллельно.
Второе преимущество MapReduce – возможность обработки больших объёмов данных. Каждый узел одновременно работает только с небольшим фрагментов исходных данных, а сортировка промежуточных значений также не требует присутствия на одном узле большого количества элементов: обычно результаты работы Map сортируются предварительно на каждом узле, а затем при группировке они выбираются с разных узлов по алгоритму сортировки слиянием.
На рисунке 1.4 представлена схема работы MapReduce, описанная в статье Джеффри Дина и Санжая Гемавата из Google Research в 2004 году [9]. Схема демонстрирует, что фаза Map и фаза Reduce выполняются параллельно, и промежуточные данные распределены по локальным дискам различных компьютеров.
Рисунок 1.4 – Схема работы MapReduce, представленная Google в 2004г.
Модель MapReduce имеет и некоторые ограничения. Она ориентирована в первую очередь на параллелизм данных. Параллелизм данных (data parallelism) – подход к параллелизации, при котором массив исходных данных разделяется между процессами и затем все процессы выполняют одну и ту же операцию над своей порцией данных [15]. В отличие от этого подхода параллелизм задач (task parallelism) подразумевает, что вычислительная задача разбивается на несколько относительно самостоятельных подзадач и каждый процесс загружается своей собственной подзадачей. Концепция MapReduce предназначена главным образом для обработки, преобразования и сортировки данных, её использование для алгоритмов с параллелизмом задач затруднительно, хотя теоретически реализуемо. Программное средство, разрабатываемое в рамках данного дипломного проекта, должно обеспечивать поддержку обеих парадигм. Для поддержки параллелизма задач данное ПС должно позволять, например, запустить одну или несколько независимых долгосрочных задач, каждая из которых будет выполняться параллельно на отдельном узле. Для обеспечения параллелизма по данным нужно предоставить универсальные методы, схожие с концепцией MapReduce. Проблематично реализовать полный вариант модели MapReduce, так как она запатентована Google.
Даже в случае с алгоритмами, параллельными по данным, MapReduce не всегда является лучшим решением. Эту модель можно приспособить для очень широкого круга задач, в некоторых случаях она будет недостаточна для решения проблемы и придётся производить дополнительную обработку данных, а в некоторых – наоборот, слишком сложна и избыточна. Так, во многих случаях функция Reduce не делает ничего и просто транслирует входные данные на выход. В качестве примера можно привести задачу простой сортировки массива. Таким образом, хотя MapReduce и является очень универсальным подходом, иногда его применение не очень удобно и приходится приложить некоторые усилия для того, чтобы перейти от исходной постановки задачи к конкретным реализациям функций Map и Reduce. В отличие от существующих реализаций модели MapReduce, в задачи данного дипломного проекта входит предоставление пользователю простых инструментов для решения простых задач. В то же время проект должен обладать универсальностью, сравнимой с MapReduce. Целесообразно применить в рамках данного проекта некоторые принципы MapReduce, такие, например, как параллельное сведение данных.
Одна из наиболее распространённых реализаций MapReduce – проект Apache Hadoop. Это фреймворк для разработки и выполнения распределённых программ, обрабатывающих большие объёмы данных. Фреймворк написан на Java. Функционирование Hadoop основано на идеях MapReduce и Google File System.
Пользователь Hadoop предоставляет системе задачу, которая состоит в простейшем случае из исходных данных и реализаций функции Map и Reduce. Эта задача (Job) направляется на сервер JobTracker, который распределяет её среди рабочих узлов кластера (TaskTracker). Каждый TaskTracker может выполнять одновременно одну или несколько операций Map или Reduce. Для обмена данными между узлами используется обычно распределённая файловая система HDFS (Hadoop Distributed File System), хотя есть возможность использовать другие файловые системы и источники данных. HDFS предусматривает наличие центрального узла имён (Name Node), хранящего метаданные файловой системы и метаинформацию о распределении блоков, и серии узлов данных (англ. data node), непосредственно хранящих блоки файлов. Архитектура кластера Hadoop представлена на схеме:
Рисунок 1.5 – Архитектура кластера Hadoop
Hadoop широко распространён и используется для обработки данных и распределённых вычислениями такими компаниями, как Amazon.com, eBay, Apple, Last.fm и многими другими. В марте 2011 года Hadoop удостоен ежегодной инновационной награды медиагруппы Guardian.
В то же время Hadoop имеет несколько ограничений в применении.
- Ограничения, налагаемые самой концепцией MapReduce (рассмотрены выше).
- Недостаточная гибкость при распределении нагрузки. Узел JobTracker при выдаче подзадач не учитывает загрузку процессоров и объём свободной памяти рабочих узлов, он принимает во внимание только количество запущенных операций и доступность данных.
- Ограничения в сфере применения. Hadoop предназначен для локальных кластеров, объединённых сетью с высокой пропускной способностью, и не применяется для создания систем, объединённых глобальной сетью.
В числе других известных реализаций MapReduce:
- Qizmt – реализация MapReduce на C#, разработанная MySpace.
- Disco – реализация MapReduce на языке Erlang от Nokia. Приложения для Disco можно писать на языке Python.
Также подход MapReduce используется в некоторых NoSQL СУБД. Например, MongoDB позволяет использовать MapReduce для аггрегации и обработки хранящихся данных, причём эти действия могут выполняться параллельно на разных серверах.
|
