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

Nauka i Obrazovanie

关键词: граф;    много потоков команд и один поток данных;    процессор обработки структур;    алгоритм поиска в ширину;    алгоритм поиска в глубину;    обход графа;   

DOI  :  10.7463/1015.0820736

来源: DOAJ

【 摘 要 】

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

【 授权许可】

Unknown