The 11 reference contexts in paper V. Podol'skii E., В. Подольский Э. (2016) “Об организации параллельной работы некоторых алгоритмов поиска кратчайшего пути на графе в вычислительной системе с многими потоками команд и одним потоком данных // On the Organization of Parallel Operation of Some Algorithms for Finding the Shortest Path on a Graph on a Computer System with Multiple Instruction Stream and Single Data Stream” / spz:neicon:technomag:y:2015:i:4:p:189-214

  1. Start
    1837
    Prefix
    поток данных, МКОД, процессор обработки структур Введение Класс алгоритмов поиска кратчайшего пути от одной вершины графа до другой вершины находит широкое применение при решении различного рода транспортных задач. В частности, серьёзная роль отводится алгоритмам поиска кратчайшего пути на графе при планировании и организации перемещения робототехнических комплексов (РТК)
    Exact
    [1-3]
    Suffix
    . Несмотря на то, что управление РТК может осуществляться оператором РТК удалённо (например, за счёт средств дистанционного управления), подобная практика имеет ряд недостатков, включающих ненадёжность каналов связи в условиях пересечённой местности, к примеру, городской, а также слабую защищённость канала управления роботом.
    (check this in PDF content)

  2. Start
    4192
    Prefix
    Глобальный граф на плане (затемненные прямоугольники – препятствия) Обзор ранних работ показал, что было разработано большое количество последовательных вариантов алгоритмов поиска кратчайшего пути в графе
    Exact
    [4-6]
    Suffix
    . Последовательные версии данных алгоритмов не использовали весь потенциал параллелизма, заложенный в алгоритмах обработкой структур данных, а потому показывали недостаточную для оперативного решения многих задач реального времени производительность [7].
    (check this in PDF content)

  3. Start
    4461
    Prefix
    Последовательные версии данных алгоритмов не использовали весь потенциал параллелизма, заложенный в алгоритмах обработкой структур данных, а потому показывали недостаточную для оперативного решения многих задач реального времени производительность
    Exact
    [7]
    Suffix
    . Тем не менее, отдельные алгоритмы на графах были модифицированы для параллельной архитектуры ЭВМ МКОД [8,9]. В частности, алгоритм Дейкстры показал весьма хорошую способность к распараллеливанию на несколько потоков команд при условии обработки одного потока данных на двух процессорах [8].
    (check this in PDF content)

  4. Start
    4580
    Prefix
    Последовательные версии данных алгоритмов не использовали весь потенциал параллелизма, заложенный в алгоритмах обработкой структур данных, а потому показывали недостаточную для оперативного решения многих задач реального времени производительность [7]. Тем не менее, отдельные алгоритмы на графах были модифицированы для параллельной архитектуры ЭВМ МКОД
    Exact
    [8,9]
    Suffix
    . В частности, алгоритм Дейкстры показал весьма хорошую способность к распараллеливанию на несколько потоков команд при условии обработки одного потока данных на двух процессорах [8].
    (check this in PDF content)

  5. Start
    4783
    Prefix
    Тем не менее, отдельные алгоритмы на графах были модифицированы для параллельной архитектуры ЭВМ МКОД [8,9]. В частности, алгоритм Дейкстры показал весьма хорошую способность к распараллеливанию на несколько потоков команд при условии обработки одного потока данных на двух процессорах
    Exact
    [8]
    Suffix
    . Настоящая работа призвана продолжить научные изыскания в сфере поиска и модификации для архитектуры ЭВМ МКОД последовательных алгоритмов, в которых происходит интенсивная обработка структур данных.
    (check this in PDF content)

  6. Start
    5708
    Prefix
    Беллмана-Форда и Ли) для архитектуры ЭВМ со многими потоками команд и одним потоком данных (ЭВМ МКОД) с процессором обработки структур (далее – СП), а также в выявлении путей оптимизации процесса модификации алгоритмов для ЭВМ МКОД. Эффективность ЭВМ МКОД с процессором обработки структур при решении подобных задач ранее была продемонстрирована на примере алгоритмов Дейкстры
    Exact
    [8]
    Suffix
    и Форда-Фалкерсона [9]. Научная новизна настоящей работы состоит в том, что алгоритмы поиска кратчайшего пути в графе от одной вершины до другой (в том числе алгоритмы БеллманаФорда и Ли) никогда прежде не были адаптированы для ЭВМ с многими потоками команд и одним потоком данных.
    (check this in PDF content)

  7. Start
    5731
    Prefix
    Ли) для архитектуры ЭВМ со многими потоками команд и одним потоком данных (ЭВМ МКОД) с процессором обработки структур (далее – СП), а также в выявлении путей оптимизации процесса модификации алгоритмов для ЭВМ МКОД. Эффективность ЭВМ МКОД с процессором обработки структур при решении подобных задач ранее была продемонстрирована на примере алгоритмов Дейкстры [8] и Форда-Фалкерсона
    Exact
    [9]
    Suffix
    . Научная новизна настоящей работы состоит в том, что алгоритмы поиска кратчайшего пути в графе от одной вершины до другой (в том числе алгоритмы БеллманаФорда и Ли) никогда прежде не были адаптированы для ЭВМ с многими потоками команд и одним потоком данных.
    (check this in PDF content)

  8. Start
    6750
    Prefix
    Алгоритмы поиска кратчайшего пути в графе Задача поиска кратчайшего пути — задача поиска самого короткого пути (цепи) между двумя точками (вершинами) на графе, в которой минимизируется сумма весов ребер, составляющих путь
    Exact
    [10,11]
    Suffix
    . Для решения задачи поиска кратчайшего пути в графе разработан ряд алгоритмов, отличающихся вычислительной сложностью и отдельными особенностями функционирования и представления результатов:  алгоритм Дейкстры (находит кратчайший путь от одной из вершин графа до всех остальных, но выдаёт корректный результат только для графов без рёбер отрицательного веса);  алгоритм Беллмана — Ф
    (check this in PDF content)

  9. Start
    17338
    Prefix
    Алгоритмы поиска кратчайшего пути в графе для выполнения в режиме сопроцессора ЭВМ МКОД Используемая в настоящей работе методика модификации алгоритмов для реализации возможности их выполнения на ЭВМ МКОД приведена в
    Exact
    [9]
    Suffix
    . 2.1. Модифицированный алгоритм Беллмана-Форда для режима сопроцессора ЭВМ МКОД На первом этапе распараллеливания модифицированного алгоритма БеллманаФорда для ЭВМ МКОД необходимо определить то, как будут представлены графы и массивы в виде структур данных для хранения в памяти структур ЭВМ МКОД.
    (check this in PDF content)

  10. Start
    20016
    Prefix
    Пример представления списка path.KEY path.DATA 0 1 ... ... В ходе выполнения второго этапа методики, алгоритм должен быть представлен в базисе операций над структурами данных. Для МКОД системы было выделено 15 команд обработки множеств и структур данных
    Exact
    [9]
    Suffix
    . Модифицированный алгоритм БеллманаФорда может быть представлен в базисе этих операций над структурами данных. В частности, для этого потребуются такие операции, как: SEARCH (поиск), INSERT (добавление), POWER (мощность), DELSTR (удаление структуры), JT (переход по тегу).
    (check this in PDF content)

  11. Start
    35265
    Prefix
    Направления развития методики модификации алгоритмов для ЭВМ МКОД Методика модификации алгоритмов для ЭВМ МКОД хотя и позволяет получить работоспособные алгоритмы для ЭВМ МКОД, имеет ряд ограничений, выявленных в процессе применения методики
    Exact
    [9]
    Suffix
    к алгоритмам Беллмана-Форда и Ли поиска кратчайшего пути в графе:  необходимость вручную определять наиболее оптимальное представление структур данных (с точки зрения соотношения объёма памяти/скорости выполнения операций);  большие затраты времени на доработку псевдокода алгоритма до псевдокода режима сопроцессора СП;  большие затраты времени на распараллелива
    (check this in PDF content)