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

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

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

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

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

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

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

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

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

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

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