Associative version of the Ramalingam incremental algorithm for the dynamic single-source reachability problem.pdf В данной работе строится ассоциативная версия алгоритма Рамалингама для решения динамической проблемы достижимости в потоковых графах с одним источником при добавлении новой дуги. Эта задача возникает в различных приложениях, таких как компиляторы, системы верификации [1, 2], а также анализ и синтез информации в геоинформационных системах (ГИС) [3] и обработка запросов в базах данных с транзитивными отношениями [4]. С ростом объемов обрабатываемых данных возрастает необходимость разработки динамических алгоритмов. Такие алгоритмы позволяют после локального изменения в графе получать решение быстрее, чем перевычисление графа целиком после каждого изменения в нем самым быстрым статическим алгоритмом. Для решения динамической проблемы достижимости нами используется модель ассоциативных (контекстно-адресуемых) процессоров типа SIMD с вертикальной обработкой данных (STAR-машина). К основным достоинствам ассоциативных архитектур относятся параллелизм по данным на базовом уровне, использование двумерных таблиц в качестве структуры данных, параллельный поиск по содержимому памяти [5]. Такие архитектуры ориентированы на решение задач нечисловой обработки данных. В частности, сюда относятся реляционная алгебра, теория графов, обработка сейсмических данных. Прогресс в компьютерной индустрии и полупроводниковых технологиях за последние годы сделал ассоциативную обработку привлекательной. Приведем несколько современных результатов, подтверждающих это утверждение. В работе [6] исследуется ассоциативный процессор (AP), базирующийся на резистентной контекстно-адресуемой памяти. В статье показывается, что технология резистентной памяти предположительно позволяет масштабировать AP с нескольких миллионов до несколько сотен миллионов процессорных элементов на отдельный силиконовый кристалл. Более 86 Ассоциативная версия инкрементального алгоритма Рамалингама для решения проблемы достижимости того, резистентный AP позволяет получать большие масштабируемость и производительность по сравнению с популярными сегодня графическими ускорителями, также относящимися к типу SIMD. В работе [7] описана крупнейшая электронная система ATLAS Fast Tracker с использованием ассоциативной архитектуры, которая проектировалась как часть детектора ATLAS Большого Адронного Коллайдера (Large Hadron Collider, LHC), предназначенного для изучения процессов в физике высоких энергий. Задача системы - распознать и сохранить полезные события при значительном подавлении фоновых процессов (соотношение оценивается как 1 к 109). Fast Tracker использует аппаратную технологию с огромным параллелизмом, объединяя интегральные микросхемы ассоциативной памяти, FPGA (ПЛИСы) и высокоскоростные каналы связи. Тем не менее в настоящее время не существует общедоступных ассоциативных архитектур. В работах [8, 9] построена абстрактная модель типа SIMD (STAR-машина), которая моделирует работу систем вертикальной обработки. Эта модель использует группу элементарных операций, которые позволяют обрабатывать таблицы по содержимому памяти. Для представления ассоциативных параллельных алгоритмов был построен язык высокого уровня STAR. На STAR-машине ассоциативные параллельные алгоритмы представляются в виде соответствующих процедур, корректность которых доказывается. В [9] построена библиотека базовых ассоциативных параллельных алгоритмов. В работах [10-11] приведена эффективная реализация ассоциативных операций STAR-машины и библиотеки базовых ассоциативных параллельных алгоритмов на графических ускорителях, позволяющая использовать разработанные алгоритмы на практике. Для STAR-машины были построены как новые ассоциативные параллельные алгоритмы на графах, так и ассоциативные версии классических алгоритмов на графах. Кроме того, была построена группа динамических алгоритмов на графах, в частности ряд ассоциативных алгоритмов для динамической обработки кратчайших путей [12-15]. Вначале мы представим краткое описание STAR-машины. В разделе 2 приводится описание последовательного алгоритма Рамалингама. В разделе 3 описано представление динамических деревьев на STAR-машине, поскольку алгоритм Рамалингама использует эту структуру данных. В разделе 4 мы приводим ассоциативную версию алгоритма Рамалингама, доказываем ее корректность и перечисляем основные достоинства этой версии. В разделе 5 приводятся результаты тестирования инкрементального алгоритма на графическом ускорителе. Представленный алгоритм выполняется в несколько раз быстрее статического ассоциативного алгоритма на графах с различным числом достижимых вершин (общее число вершин до 5 000, число дуг до 90 000). И за счет обработки вершины вместе с исходящими ребрами число итераций ассоциативного инкрементального алгоритма может значительно сокращаться (~|E|/|V|) по сравнению с последовательным алгоритмом. 1. Модель ассоциативного параллельного процессора В данном разделе приведем краткое описание STAR-машины, которая моделирует работу систем c вертикальной обработкой данных. В модели используются свойства как машины Staran [16], так и отечественного ассоциативного процессора. В работе [17] приводится сравнение STAR-машины с другими моделями ассоциативной обработки. STAR-машина определяется как абстрактная модель типа SIMD с вертикальной обработкой информации (рис. 1); ее основными компонентами являются: последовательное устройство управления, в котором записаны программа и скалярные константы; устройство ассоциативной обработки, состоящее изp одноразрядных процессорных элементов; матричная память. Для обработки информации в матричной памяти STAR-машина использует типы данных slice, word и table. С помощью переменной типа slice моделируется доступ к таблице по столбцам, а с помощью типа word - доступ по строкам. С каждой переменной типа table ассоциируется матрица из n строк и k столбцов, где n

Скачать электронную версию публикации