Предстваляет собой алгоритм нахождения длин кратчайших путей между всеми парами вершин во взвешенном ориентированном графе. Алгоритм работает за θ(n^3) времени и использует θ(n^2) памяти. Был разработан Робертом Флойдом и Стивеном Уоршеллом в 1962 году.
Дан взвешенный ориентированный граф G(V,E), в котором вершины пронумерованы от 1 до n.
Граф задан в виде матрицы, где на месте элемента (i,j) стоит расстояние между вершинами i и j в случае, если между ними есть ребро, и бесконечности в противном случае.
Требуется найти матрицу кратчайших расстояний, в которой элемент (i,j) либо равен длине кратчайшего пути из i в j, либо равен бесконечности, если вершина j не достижима из i.
Поскольку на этапе вычислений основная операция для каждого элемента - нахождение минимального среди двух значений (собственно самого элемента и суммы двух других), осуществлять данную операцию параллельно не имеет особого смысла вследствие ее простоты и наличия накладных расходов (например, на переключение потоков). Таким образом, имеет смысл осуществлять параллельную обработку каждой из строк матрицы. При этом "внешние" k-й циклы не могут осуществляться параллельно, поскольку на k итерации необходим результат k-1 итерации.
Итого, последовательно осуществляется прохождение каждого из k внешних циклов, при этом все i строк в матрице обрабатываются внутри каждой итерации параллельно. Также добавлены некоторые минорные улучшения для лучшей производительности (пропуск элементов k строки и k столбца, использование отдельных неизменяемых коллекций).
Путь к файлу с данными указывается в application.conf следующим образом (пример для файла matrix_data.txt):
input-data = "matrix_data.txt"
Сам файл представляет собой исходную матрицу для расстояний между вершинами графа. Для n вершин матрица имеет размер n на n, соответственно, в файле будет n строк, по n числовых значений в каждой строке. При этом значения не обязательно должны быть целыми числами, бесконечность указывается строкой "inf"
Пример файла для небольшой матрицы:
2.1 3
inf 11.02
Путь к файлу с выходными данными указывается в application.conf следующим образом (пример для файла matrix_result.txt):
output-data = "matrix_result.txt"
Данный параметр является опциональным - при отсутствии результат работы будет выведен в стандартный поток вывода.
- Scala 2.13.3 (см. файл build.sbt)
- SBT 1.4.1 (см. файл build.properties)
- Java 8+ (тестировалось на Java 11, AdoptOpenJDK)
Сборка:
sbt assembly
Запуск:
java -Dconfig.file=application.conf -Dlog4j.configurationFile=log4j2.xml -jar FloydWarshall-assembly-1.0.jar
В файле application.conf указывается максимальное число потоков выполнения программы следующим образом (пример для двух потоков):
max-threads = 2
Также возможно указание флага для печати времени работы алгоритма:
print-time = true
К проекту приложены файлы application.conf, а также matrix_data.txt с примером входных данных и matrix_result.txt с примером правильного результата дла таких данных.
Поскольку для выполнения программы может быть поставлен флаг печати времени работы алгоритма, была осуществлена проверка и проведено дальнейшее сравнение результатов для различного числа потоков. Для облегчения тестирования был написан скрипт matrix_generator.py, позволяющий получить файл с матрицей нужного размера и случайных значений из нужного диапазона. Важный момент: для упрощения скрипта и множественного заполнения "бесконечностью", был выбран простой метод - положительные значения записываются в матрицу, а вместо отрицательных пишется ноль. Рекомендуемое количество отрицательных чисел в диапазоне - 40-50%.
Было проведено тестирование производительности для матриц разных размерностей. Тестирование осуществлялось на процессоре Intel Core i5-7200U, по заявлениям производителя, обладающий двумя физическими и четыремя логическими ядрами. Таким образом, наиболее разумным вариантом выглядит проверка исполнения программы в 1, 2, 4 и 8 потоках.
Данные для матриц размерности 1000x1000 и 2000x2000 вынесены в таблицу и представлены в секундах (среднее значение 5 измерений).
| Число потоков/Размерность | N = 1000 | N = 2000 |
|---|---|---|
| 1 | 18 | 136 |
| 2 | 12.5 | 92 |
| 4 | 10.5 | 79 |
| 8 | 11.5 | 85 |
Некоторые выводы:
- Несмотря на то, что операций для матрицы с N=2000 примерно в 8 раз больше, чем для матрицы с N=1000, соотношение времени выполнения меньше 8 - это связано с тем, что матрицы относительно небольшие и каждая строка обрабатывается достаточно быстро, а значит затраты связанные с многопоточностью (переключение контекста, синхронизация потоков и тд) вносят весомый вклад
- Ожидаемо, наибольший скачек производительности происходит при использовании 2 потоков вместо 1. Для 4 рост по отношению к 2 незначителен, так как используются не разные физические ядра, а разные потоки в составе одного ядра, что обладает своими тонкостями
- При использовании 8 потоков производительность падает - также ожидаемый вывод, поскольку при реальных 4 потоках использование 8 не даст выигрыша (реально используется 4 потока, остальные ждут, внося далее дополнительный вклад в общее время из-за синхронизацию и переключения)