Эффективность централизованной и распределенной архитектуры памя


Кызылординский государственный университет имени Коркыт Ата

УДК 004.2.:004.242 на правах рукописи

ТАЖИКОВА ГУЛЬШАРА ДУЙСЕНБАЕВНА

ЭФФЕКТИВНОСТЬ ЦЕНТРАЛИЗОВАННОЙ И РАСПРЕДЕЛЕННОЙ

АРХИТЕКТУРЫ ПАМЯТИ ДЛЯ ПАРАЛЛЕЛЬНОЙ ОБРАБОТКИ СИСТЕМ

РЕФЕРАТ

диссертации на соискание академической степени

магистра техники и технологии по специальности

6М070400 – Вычислительная техника и программное обеспечение

Кызылорда, 2013 г.

Диссертационная работа была выполнена в политехническом институте Кызылординского государственного университета имени Коркыт Ата.

Научный руководитель: кандидат физико-математических наук Айтимова У.Ж.

Оппонент: кандидат технических наук, профессор Свечников В.В.

Защита будет проходить _____часов «__» ___________ 2013 года в Кызылординском государственном университете имени Коркыт Ата (адрес: 120014, город Кызылорда, Политехнический институт, учебный корпус № 5, ____ ауд.)

С диссертацией можно будет ознакомиться в научно-технической библиотеке Кызылординского государственного университета имени Коркыт Ата.

Введение

Объем и структура диссертации: Диссертация исследовательской работы состоит из 113 страниц, в том числе в нее входит: введение, 3 главы, заключение, список использованной литературы и приложение.

В диссертационную работу входит 29 иллюстративных рисунков, 3 таблицы и 82 использованных литературных источников.

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

Актуальность работы: Постоянные исследования в области разработки и создания высокопроизводительных вычислительных средств позволяют решать фундаментальные и прикладные задачи. Производительности современных ЭВМ недостаточно для обеспечения нужного решения многих задач. Один из наиболее эффективных способов повышения производительности заключается в распараллеливании вычислений в распределенных и параллельных структурах. Вследствие чего, применение параллельных вычислительных систем является довольно важным направлением развития вычислительной техники.

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

В настоящее время существует большое количество задач, требующих применения мощных вычислительных систем, среди которых задачи моделирования работы систем массового обслуживания и управления, распределённых систем, сложные вычислительные задачи, и др. Для решения таких задач всё шире используются параллельные системы, которые становятся общедоступными и относительно недорогими  HYPERLINK «http://ru.wikipedia.org/wiki/%D0%90%D0%BF%D0%BF%D0%B0%D1%80%D0%B0%D1%82%D0%BD%D0%B0%D1%8F_%D0%BF%D0%BB%D0%B0%D1%82%D1%84%D0%BE%D1%80%D0%BC%D0%B0_%D0%BA%D0%BE%D0%BC%D0%BF%D1%8C%D1%8E%D1%82%D0%B5%D1%80%D0%B0» аппаратными средствами для высокопроизводительных вычислений.

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

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

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

Предмет исследования: поиск закономерностей повышения эффективности централизованной и распределенной архитектуры памяти различной конфигурации в зависимости от структурно-топологических характеристик модели организации распределенных вычислений.

Основные задачи диссертационного исследования.

1) Обзор технологий централизованных, распределенных и параллельных систем управления базами данных для обеспечения управления сложными системами, выделение отличительных черт и выявление схожих признаков.

2) Выявление проблемы для разработки эффективной реализации распределенных параллельных вычислений декомпозиционной модели в классе распределенных параллельных вычислений на уровне взаимосвязанной совокупности выделяемых подзадач.

3) Аналитическое исследование эффективности распределенных систем для параллельной обработки в зависимости от структурно-топологических характеристик модели и параметров вычислительной среды.

4) Исследование и анализ класса компьютерной архитектуры для систем параллельной обработки данных.

5) Нахождение возможных путей достижения параллелизма.

6) Разработка модели.

Научная новизна: работы заключается в следующем:

1) Разработана модель в классе распределенных параллельных вычислений на уровне взаимосвязанной совокупности выделяемых подзадач;

2) Определены варианты организации параллельных систем, предусматривающие согласованное масштабирование вычислительного ресурса;

3) разработана модель параллельной вычислительной системы с распределенными дисками для оценки эффективности его работы.

Практическая ценность: полученных результатов заключается в следующем:

1. Проведено сопоставление возможных классов централизованных и рапределенных систем для паралллельной обработки систем рассмотренным методам с точки зрения эффективности её реализации по введённому показателю качества.

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

3. Высокая эффективность программной реализации метода параллельных вычислений подтверждена на примере построения модели.

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

Основное содержание работы

Современные программные приложения и информационные системы достигли такого уровня развития, что термин «архитектура» в применении к ним уже давно не новость для нас. Грамотно построить информационную систему, эффективно и надежно функционирующую не проще, чем построить и возвести современное многофункциональное здание.

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

Термин «архитектура системы» часто употребляется как в узком, так и в широком смысле этого слова. В узком смысле под архитектурой понимается архитектура набора команд, т.е. то, какой машина предоставляется программисту.

Централизованная архитектура

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

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

HYPERLINK «http://citforum.ru/database/classics/distr_and_paral_sdb/» \l «part_3»Технологии распределенных и параллельных баз данных

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

Поэтому в первой главе представлен обзор технологий распределенных и параллельных СУБД, выделены их отличительные черты, отмечены схожие признаки. Цель обзора – помочь в осмыслении уникальной роли систем каждого из этих двух типов и их взаимодополняемости в решении задач управления данными.

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

Размещение данных

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

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

Классификация параллельных компьютерных систем

Одним из наиболее распространенных способов классификации ЭВМ является систематика Флинна (Flynn), в рамках которой основное внимание при анализе архитектуры вычислительных систем уделяется способам взаимодействия последовательностей (потоков) выполняемых команд и обрабатываемых данных.

В основе классификации лежат понятия потоков команд и потоков данных. Поток команд соответствует счетчику команд. Система с n процессорами имеет n счетчиков команд и, следовательно, n потоков команд. Отток данных состоит из набора операндов.

Можно выделить четыре основных типа архитектуры систем параллельной обработки:

1) Конвейерная и векторная обработка.

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

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

2) Машины типа SIMD.

SIMD компьютер имеет N идентичных процессоров, N потоков данных и один поток команд. Каждый процессор обладает собственной локальной памятью. Процессоры интерпретируют адреса данных либо как локальные адреса собственной памяти, либо как глобальные адреса, возможно, модифицированные добавлением локального базового адреса. Процессоры получают команды от одного центрального контроллера команд и работают синхронно, то есть на каждом шаге все процессоры выполняют одну и ту же команду над данными из собственной локальной памяти рисунке 1.

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

Рисунок 1 — Машины типа SIMD

Такая архитектура с распределенной памятью часто упоминается как архитектура с параллелизмом данных(data-parallel), так как параллельность достигается при наличии одиночного потока команд, действующего одновременно на несколько частей данных. Сеть, соединяющая процессоры, обычно имеет регулярную топологию такую как кольцо SLAP рисунке 2:

Рисунок 2. — Сеть с топологией кольцо

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

Модели вычислений на векторных и матричных ЭВМ настолько схожи, что эти ЭВМ часто обсуждаются как эквивалентные.

3) Машины типа MIMD.

MIMD компьютер имеет N процессоров, независимо исполняющих N потоков команд и обрабатывающих N потоков данных. Каждый процессор функционирует под управлением собственного потока команд, то есть MIMD компьютер может параллельно выполнять совершенно разные программы (рисунок 3).

Рисунок 3. — Машины типа MIMD.

MIMD архитектуры далее классифицируются в зависимости от физической организации памяти, то есть имеет ли процессор свою собственную локальную память и обращается к другим блокам памяти, используя коммутирующую сеть, или коммутирующая сеть подсоединяет все процессоры к общедоступной памяти. Исходя из организации памяти, различают следующие типы параллельных архитектур:

• Компьютеры с распределенной памятью (Distributed memory) (рисунок 4).

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

Рисунок 4. — Компьютеры с распределенной памятью

• Компьютеры с общей (разделяемой) памятью (True shared memory)

Все процессоры совместно обращаются к общей памяти, обычно, через шину или иерархию шин. В идеализированной PRAM (Parallel Random Access Machine — параллельная машина с произвольным доступом) модели, часто используемой в теоретических исследованиях параллельных алгоритмов, любой процессор может обращаться к любой ячейке памяти за одно и то же время. На практике масштабируемость этой архитектуры обычно приводит к некоторой форме иерархии памяти. Частота обращений к общей памяти может быть уменьшена за счет сохранения копий часто используемых данных в кэш-памяти, связанной с каждым процессором. Доступ к этому кэш-памяти намного быстрее, чем непосредственно доступ к общей памяти.

• Компьютеры с виртуальной общей (разделяемой) памятью (Virtual shared memory)

Общая память как таковая отсутствует. Каждый процессор имеет собственную локальную память и может обращаться к локальной памяти других процессоров, используя «глобальный адрес». Если «глобальный адрес» указывает не на локальную память, то доступ к памяти реализуется с помощью сообщений, пересылаемых по коммуникационной сети.

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

Рисунок 6. Сеть с топологией Рисунок 7. — Сеть с топологией

2D решетка(тор) 2D гиперкуб (тор)

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

Базовой моделью вычислений на MIMD-мультипроцессоре является совокупность независимых процессов, эпизодически обращающихся к разделяемым данным. Существует большое количество вариантов этой модели. На одном конце спектра — модель распределенных вычислений, в которой программа делится на довольно большое число параллельных задач, состоящих из множества подпрограмм. На другом конце спектра — модель потоковых вычислений, в которых каждая операция в программе может рассматриваться как отдельный процесс. Такая операция ждет своих входных данных (операндов), которые должны быть переданы ей другими процессами. По их получении операция выполняется, и полученное значение передается тем процессам, которые в нем нуждаются. В потоковых моделях вычислений с большим и средним уровнем гранулярности, процессы содержат большое число операций и выполняются в потоковой манере.

4) Многопроцессорные машины с SIMD-процессорами.

Многие современные супер-ЭВМ представляют собой многопроцессорные системы, в которых в качестве процессоров используются векторные процессоры или процессоры типа SIMD. Такие машины относятся к машинам класса MSIMD.

Языки программирования и соответствующие компиляторы для машин типа MSIMD обычно обеспечивают языковые конструкции, которые позволяют программисту описывать «крупнозернистый» параллелизм. В пределах каждой задачи компилятор автоматически векторизует подходящие циклы. Машины типа MSIMD, как можно себе представить, дают возможность использовать лучший из этих двух принципов декомпозиции: векторные операции («мелкозернистый» параллелизм) для тех частей программы, которые подходят для этого, и гибкие возможности MIMD-архитектуры для других частей программы.

Интерес к архитектурам MIMD

Многопроцессорные системы за годы развития вычислительной техники претерпели ряд этапов своего развития. Исторически первой стала осваиваться технология SIMD. Однако в настоящее время наметился устойчивый интерес к архитектурам MIMD. Этот интерес главным образом определяется двумя факторами:

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

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

Таким образом, существующие MIMD-машины распадаются на два основных класса в зависимости от количества объединяемых процессоров, которое определяет и способ организации памяти и методику их межсоединений.

К первой группе относятся машины с общей (разделяемой) основной памятью, объединяющие до нескольких десятков (обычно менее 32) процессоров. Сравнительно небольшое количество процессоров в таких машинах позволяет иметь одну централизованную общую память и объединить процессоры и память с помощью одной шины. При наличии у процессоров кэш-памяти достаточного объема высокопроизводительная шина и общая память могут удовлетворить обращения к памяти, поступающие от нескольких процессоров. Поскольку имеется единственная память с одним и тем же временем доступа, эти машины иногда называются UMA (Uniform Memory Access), которые мы рассматривали раньше. Такой способ организации со сравнительно небольшой разделяемой памятью в настоящее время является наиболее популярным. Структура подобной системы представлена на рис. 8.

Рисунок 8. — Типовая архитектура мультипроцессорной системы с общей памятью

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



Рисунок 9 — Типовая архитектура машины с распределенной памятью

Эти два преимущества еще больше сокращают количество процессоров, для которых архитектура с распределенной памятью имеет смысл.

Параллельные вычислительные системы

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

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

Писать программы для параллельных систем сложнее, чем для последовательных, так как конкуренция за ресурсы представляет новый класс потенциальных ошибок в программном обеспечении (багов), среди которых состояние гонки является самой распространённой. Взаимодействие и синхронизация между процессами представляют большой барьер для получения высокой производительности параллельных систем. В последние годы также стали рассматривать вопрос о потреблении электроэнергии параллельными компьютерами. Характер увеличения скорости программы в результате распараллеливания объясняется законом Амдала.

Типы параллелизма

Параллелизм на уровне битов

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

Исторически 4-битные микропроцессоры были заменены 8-битными, затем появились 16-битные и 32-битные. 32-битные процессоры долгое время были стандартом в повседневных вычислениях. С появлением технологии x86–64 для этих целей стали использовать 64-битные процессоры.

Параллелизм на уровне инструкций

Компьютерная программа – это, по существу, поток инструкций, выполняемых процессором. Но можно изменить порядок этих инструкций, распределить их по группам, которые будут выполняться параллельно, без изменения результата работы всей программы. Данный приём известен как параллелизм на уровне инструкций. Продвижения в развитии параллелизма на уровне инструкций в архитектуре компьютеров происходили с середины 1980-х до середины 1990-х.

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

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

Параллелизм задач (многопоточность)

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

Два уровня распараллеливания

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

Сложилось представление о двух основных уровнях, на которых в ВС применяются практические методы распараллеливания:

на уровне программ, процессов, процедур (первый уровень распараллеливания);

на уровне команд и операций (второй уровень распараллеливания).

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

Уровень команд и операций наиболее ярко представлен многофункциональными АЛУ и их обобщением — решающими полями, представляющими разделяемый вычислительный ресурс многих процессоров. Некоторые современные проекты ВС в разной степени предполагают такой ресурс. Здесь основная проблема — полная загрузка отдельных исполнительных устройств (ИУ) в процессе выполнения программы.

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

Под эффективностью работы устройства в составе ВС понимают степень его участия в общей работе ВС при решении конкретной задачи — коэффициент загрузки устройства. Распараллеливание работ оправдано, если приводит к существенному росту усредненного по всем устройствам коэффициента загрузки оборудования при решении задач. Это непосредственно сказывается на времени решения. Сегодня говорят не о специальном классе задач, а о задачах, ориентирующих ВС на универсальность, что обусловлено современными областями применения.

Пути достижения параллелизма

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

— независимость функционирования отдельных устройств ЭВМ — данное требование относится в равной степени ко всем основным компонентам вычислительной системы — к устройствам ввода-вывода, к обрабатывающим процессорам и к устройствам памяти;

— избыточность элементов вычислительной системы — организация избыточности может осуществляться в следующих основных формах:

— использование специализированных устройств таких, например, как отдельных процессоров для целочисленной и вещественной арифметики, устройств многоуровневой памяти (регистры, кэш);

— дублирование устройств ЭВМ путем использования, например, нескольких однотипных обрабатывающих процессоров или нескольких устройств оперативной памяти.

Моделирование и анализ параллельных вычислений

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

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

Показатели эффективности параллельного алгоритма

Ускорение, получаемое при использовании параллельного алгоритма для p процессоров, по сравнению с последовательным вариантом выполнения вычислений определяется

,

т.е. как отношение времени решения задач на скалярной ЭВМ к времени выполнения параллельного алгоритма (величинаn используется для параметризации вычислительной сложности решаемой задачи и может пониматься, например, как количество входных данных задачи).

Эффективность использования параллельным алгоритмом процессоров при решении задачи определяется соотношением:

(величина эффективности определяет среднюю долю времени выполнения алгоритма, в течение которой процессоры реально используются для решения задачи).

Как следует из приведенных соотношений, в наилучшем случае Sp(n) = p и Ep(n) = 1. В данном разделе данные показатели будут определены для ряда рассмотренных параллельных алгоритмов для решения типовых задач вычислительной математики.

Оценка коммуникационной трудоемкости параллельных алгоритмов

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

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

Матричное умножение

Приведенный параллельный метод матричного умножения приводит к равномерному распределению вычислительной нагрузки между процессорами

, .

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

Сортировка

Сортировка является одной из типовых проблем обработки данных, и обычно понимается как задача размещения элементов неупорядоченного набора значений

в порядке монотонного возрастания или убывания

(здесь и далее все пояснения для краткости будут даваться только на примере упорядочивания данных по возрастанию).

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



Страницы: 1 | 2 | Весь текст