Процессор для параллельной обработки графовых структур данных

Процессор для параллельной

обработки графовых структур данных

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

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

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

Часто используется классификация Флинна, согласно которой компьютеры подразде­ляются на группы в соответствии с числом потоков инструкций и числом потоков данных. Оказывается, что наиболее популярными в па­раллельных системах являются группы ОКМД (одиночный поток команд, множество потоков данных) и МКМД (множество потоков команд, множество потоков данных).

Параллельная машина с ОКМД-архитектурой состоит из устройства управления, N процессоров, N модулей памяти и коммутационной сети. Устройство управления рассылает команды процессорам и все активные процессоры выполняют одновременно одну и ту же команду, т. е. один поток команд. Каждый активный процессор выполняет команду над данными из своего модуля памяти. Это формирует множество потоков данных. Коммутационная, или перестраиваемая сеть используется для обмена информацией между процессорами и модулями памяти.

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

Архитектура компьютеров с систологическими массивами ПЭ представляет наиболее высокий уровень параллелизма в вычислениях, достигнутый на аппа­ратном уровне. Согласно концепции этой архитектуры, разработанной Кунгом, она охватывает совокупность регулярных ячеек — ПЭ, где данные распространяются в различных направлениях. Число ячеек в массиве и орга­низация массива изменяются таким образом, чтобы сбалансировать требования к вводу-выводу данных. Подобные архитектуры находят широкое применение при обработке изображений и в нейронных сетях.

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

Тесно связанные массивы ПЭ, объединяемые в структуры в виде матрицы, образуют подкласс высокоинтегрированных компьютеров. Каждый ПЭ в такой структуре может быть связан с четырьмя (или восемью) соседними ПЭ. Часто такие структуры объединяются в многоразмерные сети с петлеобразными. Особенностью матричных процессоров (МПр) является массовый параллелизм, обеспечиваемый большим числом параллельно работающих ПЭ. Для достижения максимума параллелизма и плотности размещения на кристалле ПЭ матричных ЭВМ очень сильно упрощаются путем использования бит-последовательного АЛУ и памяти.

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

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

Программа – это последовательность инструкций, выполняемых каждым процессорным элементом (ПЭ).

Данными в ГП является кодированная информация о графе, представленная в виде непосредственного кодирования структуры ГП.

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

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

Основная часть

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

1.  Поиск в ширину.

2.  Поиск в глубину.

3.  Топологическая сортировка

4.  Определение сильносвязных компонент.

5.  Точки раздела, мосты.

6.  Кратчайшие пути.

Наиболее интересным видится вариант аппаратной реализации поиска

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

Попытки аппаратной реализации подобной системы неизбежно сталкиваются со следующими проблемами:

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

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

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

Первоначально планировалось решить задачу разработки графового процессора (ГП) «в лоб». Т. е каждый процессорный элемент ГП – представлял вершину графа.

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

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

Рис. 1. Первоначальная структурная модель графового процессора.

Основные принципы положенные в основу данной модели следующие:

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

Рис. 2. Структурная схема предлагаемой модели ГП.

Данные представляются следующим образом: вершины – таблица 1, дуги – таблица 2.

Идентификатор вершины

№ вершины

Вес 1

Вес N

Тип

Таблица 1. Представление вершин.

Идентификатор дуги

Начальная вершины

Конечная вершина

Тип

Таблица 2. представление дуг.

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

Процессорный ресурс представляет собой набор (до 32) ПЭ. Каждому ПЭ ставится в соответствие не одна вершина графа, а несколько вершин. Усложнив устройство управления, мы добились увеличения количества вершин, который одновременно может обрабатывать ГП.

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

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

Рис. 3. Процессорный ресурс и среда коммутации. ПЭ1…ПЭN – процессорные элементы (общее количество N штук); КМ1…КМN – коммутаторы, обеспечивающие коммутацию ПЭ с общей памятью и между собой. Структура ПЭ: АЛУ – арифметико-логическое устройство; УУ – внутрипроцессорное устройство управления; ОП – оперативная (локальная) память; ЧО – блок чтения операнда; ЧК – блок чтения команды.

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

Функции центрального устройства управления:

1.  Выборка текущей команды из памяти команд.

2.  Дешифрация команды.

3.  Определение элементов графа на которые эта команда распространяется.

4.  Выбор процессорных элементов.

5.  Выбор данных из памяти данных.

6.  Пересылка данных в процессорные элементы.

7.  Выполнение команд.

8.  Пересылка результатов выполнения.

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

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

Непосредственно сама программа хранится в определенной памяти программ и оттуда поступает на ЦУУ, которое осуществляет непосредственное управление каждым ПЭ.

Заключение

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

Приложение

Алгоритм поиска в ширину.

Пусть задан граф G=(V, E) и фиксирована начальная вершина s. Алгоритм поиска в ширину перечисляет все достижимые из s (если идти по рёбрам) вершины в порядке возрастрания расстояния от s. Расстоянием считается длина (число рёбер) кратчайшего пути. В процессе поиска из графа выделяется часть, называемая «деревом поиска в ширину» с корнем s. Оно содердит все достижимые из s вершины (и только их). Для каждой из них путь из корня в дереве поиска будет одним из кратчайших путей (из начальной вершины) в графе. Алгоритм применим и к ориентированным, и к неориентированным графам.

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

1.  for (для) каждой вершины u € V[G] – {s}

2.  do color[u] ← БЕЛЫЙ

3.  d[u] ← ∞

4.  Π[u] ← NIL

5.  color[s] ← СЕРЫЙ

6.  d[s] ← 0

7.  Π[s] ← NIL

8.  Q ← {s}

9.  while Q ≠ O

10.  do u ← head[Q]

11.  for (для) всех v € Adj[u]

12.  do if color[v] = БЕЛЫЙ

13.  then color[v] ← СЕРЫЙ

14.  d[v] ← d[u] + 1

15.  Π[u] ← u

16.  Enqueue(Q, v)

17.  Dequeue(Q)

18.  color[u] ← ЧЕРНЫЙ

Поиск в ширину использует представления графа G=(V, E) списками смежных вершин. s – начальная вершина. Для каждой вершины u графа дополнительно хранятся её цвет color[u] и её предшественник Π[u]. Расстояние от s до u записывается в поле d[u]. Процедура также использует очередь Q для хранения множества серых вершин. Процедура Enqueue() добавляет вершину в очередь, а процедура Dequeue() удаляет элемент из очереди.

Поиск в глубину.

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

Помимо этого поиск в глубину ставит на вершинах метки времени. Каждая вершина имеет две метки: в d[v] записано, когда эта вершина была обнаружена (и сделана серой), а в f[v] – когда была закончена обработка списка смежных с v вершин (и v стала чёрной).

Исходный граф может быть ориентированным или неориентированным. Переменная time – глобальная переменная текущего времени, используемого для пометок.

1.  for (для) всех вершин u € V[G]

2.  do color[u] ← БЕЛЫЙ

3.  Π[u] ← NIL

4.  time ← 0

5.  for (для) всех вершин u € V[G]

6.  do if color[u] = БЕЛЫЙ

7.  then DFS-Visit(u)

DFS-Visit(u)

1.  color[u] ← СЕРЫЙ

2.  d[u] ← time ← time + 1

3.  for (для) всех v € Adj[u]

4.  do if color[v] = БЕЛЫЙ

5.  then Π[v] ← u

6.  DFS-Visit(v)

7.  color[u] ← ЧЁРНЫЙ

8.  f[u] ← time ← time + 1



Подпишитесь на рассылку:

Проекты по теме:

Основные порталы, построенные редакторами

Домашний очаг

ДомДачаСадоводствоДетиАктивность ребенкаИгрыКрасотаЖенщины(Беременность)СемьяХобби
Здоровье: • АнатомияБолезниВредные привычкиДиагностикаНародная медицинаПервая помощьПитаниеФармацевтика
История: СССРИстория РоссииРоссийская Империя
Окружающий мир: Животный мирДомашние животныеНасекомыеРастенияПриродаКатаклизмыКосмосКлиматСтихийные бедствия

Справочная информация

ДокументыЗаконыИзвещенияУтверждения документовДоговораЗапросы предложенийТехнические заданияПланы развитияДокументоведениеАналитикаМероприятияКонкурсыИтогиАдминистрации городовПриказыКонтрактыВыполнение работПротоколы рассмотрения заявокАукционыПроектыПротоколыБюджетные организации
МуниципалитетыРайоныОбразованияПрограммы
Отчеты: • по упоминаниямДокументная базаЦенные бумаги
Положения: • Финансовые документы
Постановления: • Рубрикатор по темамФинансыгорода Российской Федерациирегионыпо точным датам
Регламенты
Термины: • Научная терминологияФинансоваяЭкономическая
Время: • Даты2015 год2016 год
Документы в финансовой сферев инвестиционнойФинансовые документы - программы

Техника

АвиацияАвтоВычислительная техникаОборудование(Электрооборудование)РадиоТехнологии(Аудио-видео)(Компьютеры)

Общество

БезопасностьГражданские права и свободыИскусство(Музыка)Культура(Этика)Мировые именаПолитика(Геополитика)(Идеологические конфликты)ВластьЗаговоры и переворотыГражданская позицияМиграцияРелигии и верования(Конфессии)ХристианствоМифологияРазвлеченияМасс МедиаСпорт (Боевые искусства)ТранспортТуризм
Войны и конфликты: АрмияВоенная техникаЗвания и награды

Образование и наука

Наука: Контрольные работыНаучно-технический прогрессПедагогикаРабочие программыФакультетыМетодические рекомендацииШколаПрофессиональное образованиеМотивация учащихся
Предметы: БиологияГеографияГеологияИсторияЛитератураЛитературные жанрыЛитературные героиМатематикаМедицинаМузыкаПравоЖилищное правоЗемельное правоУголовное правоКодексыПсихология (Логика) • Русский языкСоциологияФизикаФилологияФилософияХимияЮриспруденция

Мир

Регионы: АзияАмерикаАфрикаЕвропаПрибалтикаЕвропейская политикаОкеанияГорода мира
Россия: • МоскваКавказ
Регионы РоссииПрограммы регионовЭкономика

Бизнес и финансы

Бизнес: • БанкиБогатство и благосостояниеКоррупция(Преступность)МаркетингМенеджментИнвестицииЦенные бумаги: • УправлениеОткрытые акционерные обществаПроектыДокументыЦенные бумаги - контрольЦенные бумаги - оценкиОблигацииДолгиВалютаНедвижимость(Аренда)ПрофессииРаботаТорговляУслугиФинансыСтрахованиеБюджетФинансовые услугиКредитыКомпанииГосударственные предприятияЭкономикаМакроэкономикаМикроэкономикаНалогиАудит
Промышленность: • МеталлургияНефтьСельское хозяйствоЭнергетика
СтроительствоАрхитектураИнтерьерПолы и перекрытияПроцесс строительстваСтроительные материалыТеплоизоляцияЭкстерьерОрганизация и управление производством

Каталог авторов (частные аккаунты)

Авто

АвтосервисАвтозапчастиТовары для автоАвтотехцентрыАвтоаксессуарыавтозапчасти для иномарокКузовной ремонтАвторемонт и техобслуживаниеРемонт ходовой части автомобиляАвтохимиямаслатехцентрыРемонт бензиновых двигателейремонт автоэлектрикиремонт АКППШиномонтаж

Бизнес

Автоматизация бизнес-процессовИнтернет-магазиныСтроительствоТелефонная связьОптовые компании

Досуг

ДосугРазвлеченияТворчествоОбщественное питаниеРестораныБарыКафеКофейниНочные клубыЛитература

Технологии

Автоматизация производственных процессовИнтернетИнтернет-провайдерыСвязьИнформационные технологииIT-компанииWEB-студииПродвижение web-сайтовПродажа программного обеспеченияКоммутационное оборудованиеIP-телефония

Инфраструктура

ГородВластьАдминистрации районовСудыКоммунальные услугиПодростковые клубыОбщественные организацииГородские информационные сайты

Наука

ПедагогикаОбразованиеШколыОбучениеУчителя

Товары

Торговые компанииТоргово-сервисные компанииМобильные телефоныАксессуары к мобильным телефонамНавигационное оборудование

Услуги

Бытовые услугиТелекоммуникационные компанииДоставка готовых блюдОрганизация и проведение праздниковРемонт мобильных устройствАтелье швейныеХимчистки одеждыСервисные центрыФотоуслугиПраздничные агентства

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