Параллельные алгоритмы обработки больших данных иммитационного моделирования (стр. 1 )

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«КУБАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

(ФГБОУ ВПО «КубГУ»)

Кафедра вычислительных технологий

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

Краснодар 2014

СОДЕРЖАНИЕ

Введение....................................................................................................................3

1 Обработка больших данных.................................................................................5

  1.1 Технология MapReduce..................................................................................7

  1.2 Фреимворк Apache Hadoop............................................................................14

2 Источники больших данных в системах моделирования..................................22

  2.1 Процессы порождения информации в системах имитационного моделирования..........................................................................................................24

  2.2 Вычислительные алгоритмы обработки последовательностей..................27

  2.3 Паттерны в последовательностях..................................................................29

  2.4 Онлайновые алгоритмы обработки последовательностей..........................34

3 Параллельные алгоритмы обработки больших данных имитационного моделирования...........................................................................................................38

  3.1 Алгоритм поиска расстояния Хемминга.......................................................39

  3.2 Алгоритм поиска частного паттерна..............................................................42

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

Список использованных источников.......................................................................48

ВВЕДЕНИЕ

В ряде областей современной науки (физике, химии, астрономии, биологии, фармацевтике и др.) накапливаются громадные (пентабайтные и более) объемы данных. Большие объемы данных возникают и вне науки, например, в сети Интернет. Например, компьютеры Google обрабатывают около 1 петабайта в час. Эти данные нуждаются в обработке для извлечения из них знаний (определенных закономерностей).

Проблема состоит в том, что упомянутые наборы данных не статичны, они постоянно растут, т. е. скорость потока новых данных «соревнуется» с возможной скоростью их обработки. Но не все данные в потоке равноценны: вместе с данными, из которых действительно можно извлечь новые закономерности (знания), имеется большое количество данных, лишь подтверждающих уже выявленные закономерности, или данных, вообще не имеющих отношения к исследуемой проблеме (шумы).

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

Одним из методов научных исследований является имитационное моделирование. Имитационная модель порождает большое количество данных во время сеанса имитационного моделирования. Это события, происходящие в модели, изменения состояний модели. Если производится исследование модели однопроцессорного компьютера, работающего с тактовой частотой 1 ГГц, и системное время изменяется на одну секунду, следовательно, в модели происходит не менее 1 миллиарда событий. Если с каждым событием связано изменение 1000 байт данных (а реально может быть гораздо больше), то получаем объем данный 1012 байт = 103 Гбайт, т. е. около Терабайта. При моделировании вычислительной сети из 1000 компьютеров получаем уже около Петабайта информации за секунду системного времени. Большие объемы получаются при моделировании многопроцессорных ЭВМ.

Если моделируется только аппаратура компьютера, то могут рассматриваться более короткие промежутки системного времени, соответственно, будут получаться меньшие объемы информации. Но если моделируется взаимодействие компьютера и внешней среды, то нужно рассматривать процессы в реальном времени, которое может составлять минуты и часы.

Такой объем данных трудно не только обработать, но и сохранить для последующей обработки.

Возникает проблема сжатия данных. Какие именно из возникающих данных можно обработать сразу, какие данные следует сохранять?

Это можно сделать с помощью информационных процедур – инструмента исследователя, позволяющего управлять потоком данных.

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

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

Цель курсовой работы -  разработать библиотеку параллельных алгоритмов обработки больших данных имитационного моделирования.

       1. Обработка больших данных.

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

               Методы и техники анализа, применимые к большим данным:

методы класса Data Mining: обучение ассоциативным правилам, классификация (методы категоризации новых данных на основе принципов, ранее применённых к уже наличествующим данным), кластерный анализ, регрессионный анализ; краудсорсинг — категоризация и обогащение данных силами широкого, неопределённого круга лиц, привлечённых на основании публичной оферты, без вступления в трудовые отношения; смешение и интеграция данных — набор техник, позволяющих интегрировать разнородные данные из разнообразных источников для возможности глубинного анализа, в качестве примеров таких техник, составляющих этот класс методов приводятся цифровая обработка сигналов и обработка естественного языка; машинное обучение, включая обучение с учителем и без учителя — использование моделей, построенных на базе статистического анализа или машинного обучения для получения комплексных прогнозов на основе базовых моделей; искусственные нейронные сети, сетевой анализ, оптимизация, в том числе генетические алгоритмы; распознавание образов; прогнозная аналитика; имитационное моделирование; пространственный анализ — класс методов, использующих топологическую, геометрическую и географическую информацию в данных; статистический анализ, в качестве примеров методов приводятся A/B-тестирование и анализ временных рядов;

       1.1 Технология MapReduce

       Фреимворк MapReduce разработан в компании Google. Целью их работы было упростить написание распределенных программ, и улучшить их масштабируемость, используя преимущества функциональных языков программирования. Статья, описывающая эту разработку была опубликована в 2004 году, в 2010 году корпорация Google предоставила права на использование MapReduce компании Apache Software Foundation. 

               Абстракция MapReduce изначально ориентирована на архитектуру с большим количеством узлов небольшой вычислительной мощности, однако с успехом применяется на многоядерных машинах и гетерогенных кластерах, что говорит о большой адаптивности фреймворка. Основные преимущества MapReduce –  программа может быть ускорена простым добавлением вычислительных узлов. Написание программы сводится к описанию двух функций. Функция map размечает данные и выдаёт пары вида (ключ, значение). Результаты работы всех map функций, сортируются в списке по ключу, и подаются на вход reduce.

        Вы сможете применить MapReduce, если соответствующим образом перепишите свой алгоритм. С другой стороны, если  у вас имеется последовательный алгоритм, который нужно применить к большому количеству данных, вы можете разбить эти данные на небольшие части и применить к ним несколько операций map и reduce, связанных в цепочку. Таким образом, мы получаем распределение по данным. Узким местом фреймворка является необходимость отработки map над всеми данными, прежде, чем начнется этап reduce. Это связано с тем, что  на вход одной reduce задачи могут подаваться выходные данные нескольких map функций. Простым решением этой проблемы является выявление тормозящих данных (например, записанных в некорректном формате), и их выброска из обработки. При условии, что это не повлияет на результат, скорость выполнения программы может быть существенно увеличена.

       MapReduce легко приспособить для обработки больших графовых структур. В частности, в компании Google MapReduce используется для решения таких графовых задач, как PageRanking — алгоритм ссылочного ранжирования. В этой задаче важность узла зависит от вероятности, что он будет включен в произвольный путь через граф.  Однако, существующие открытые шаблоны обработки больших графов, имеют ряд существенных недостатков, влияющих на производительность. 

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