ivdon3@bk.ru
В данной работе представлена адаптивная архитектура вычислительного конвейера, позволяющая повысить пропускную способность и снизить задержку при обработке потоковых данных в реальном времени как в одно-, так и в многопроцессорных системах. В отличие от преимущественно концептуальных моделей или узко ориентированных алгоритмов, практический эффект проявляется в достижении измеримого роста производительности за счёт уменьшения числа повторных копирований данных и синхронизационных издержек или гибкой настройки порядка входных и выходных данных. Архитектура использует разделяемую память для исключения дублирования буферов, применяет каналы передачи данных в зависимости от потребности в упорядочивании, а также предусматривает репликацию процессов внутри или между ядрами центрального процессора. Эксперименты показали, что предложенная архитектура обеспечивает как высокую пропускную способность, так и малые задержки, вводя минимальные накладные расходы на пересылку данных и синхронизацию процессов. Тем самым архитектура служит гибкой и масштабируемой основой для широкого круга приложений реального времени — от систем видеонаблюдения и робототехники до распределённых платформ обработки больших массивов данных.
Ключевые слова: параллелизм, многопроцессорные вычисления, вычислительный конвейер, масштабирование производительности, очереди, разделяемая память
Целью исследования является повышение эффективности алгоритма Дейкстры за счет использования модели разделяемой памяти с библиотекой OpenMP и работы по принципу параллельного выполнения при реализации алгоритма. Использование алгоритма Дейкстры для поиска кратчайшего пути между двумя узлами в графе довольно распространено. Однако временная сложность алгоритма возрастает с увеличением размера графа, что приводит к увеличению времени выполнения, поэтому параллельное выполнение является хорошим вариантом для решения проблемы временной сложности. В этой исследовательской работе предлагается метод параллельных вычислений для повышения эффективности алгоритма Дейкстры для больших графов. метод включает в себя разделение массива путей в алгоритме Дейкстры на указанное количество процессоров для параллельного выполнения. Мы предоставляем реализацию распараллеленного алгоритма Дейкстры и получаем доступ к его производительности, используя фактические наборы данных и с разным количеством узлов. Наши результаты показывают, что распараллеленный алгоритм Дейкстры может значительно ускорить процесс по сравнению с последовательной версией алгоритма, одновременно сокращая время выполнения и постоянно повышая эффективность процессора, что делает его полезным выбором для поиска кратчайших путей в больших графах.
Ключевые слова: Алгоритм Дейкстры, граф, кратчайшие пути, параллельный вычислений, модель общей памяти, библиотека OpenMP