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

Аннотация

Настоящая статья посвящена проектированию и реализации программной и аппаратной составляющих системы, реализующей алгоритм построения всех маршрутов в графе, описанный в терминах реляционной алгебры. Исходя из принадлежности рассматриваемой задачи к классу NP-полных и характеристик предлагаемого параллельного метода, в данной работе описывается способ разработки MIMD-системы, представленной в формате кластера, на вычислительных узлах которого выполняются требуемые операции над фрагментами исходных данных. Использование масштабируемой параллельной системы позволяет получить достаточный уровень производительности для проведения испытаний предлагаемого метода над графами с большим количеством вершин. Описанный в основной части настоящей статьи программно-аппаратный комплекс обладает свойством универсальности по отношению к используемым системам управления баз данных и количеству возможных выделенных процессов. Кроме того, для случая гетерогенной кластерной системы предлагается вариант балансировки вычислительных объемов в зависимости от технических характеристик узла, имеющих влияние на процесс выполнения алгоритма. Также в данной статье приводится описание экспериментального анализа разработанного программно-аппаратного комплекса, который проводился с целью проверки системы на предмет масштабируемости, то есть увеличения количества вычислительных узлов, выполняющих построение всех маршрутов в графе большой размерности. Данный этап выполняется на примере конкретной реализации с использованием сети однородных рабочих станций, выступающих в качестве узлов кластера с установленной СУБД MS SQL Server. Разбиение исходных данных на фрагменты, последующее их распределение, выделение процессов и отправка команд на выполнение хранимых процедур, реализующих предлагаемый алгоритм построения всех маршрутов в графе, производятся на отдельном ПК, являющемся хостом. При этом связь с экземплярами баз данных, установленных на вычислительных узлах кластера, реализована посредством технологии ADO.NET.