МИНОБРНАУКИ РОССИИ
Санкт-Петербургский государственный
электротехнический университет
«ЛЭТИ» им. В.И. Ульянова (Ленина)
Кафедра вычислительной техники
Отчет по лабораторной работе №1
по дисциплине «Параллельные алгоритмы и системы»
Студент гр. |
|
Преподаватель |
Пазников А.А. |
Тема: Алгоритм поиска кратчайших путей (Дейкстра)
Цель работы: создать программу с нуля и максимально её оптимизировать. Изучить основные приемы оптимизации кода
Эксперименты были произведены на ПК с AMD Ryzen 5 4600H с 12 логическими ядрами
В качестве метрик будут использоваться время выполнения процессора (в секундах), IPС (instructions per cycle), cache-misses
При замерах не были запущены какие-либо другие приложения и программы.
Также при компиляции были использованы флаги –O0 (без встроенной оптимизации) и –O2 («безопасная» оптимизация, которая не затрагивает форматирование процессов, которые могут повредиться при выполнении программы)
Хочу обратить внимание, что при запуске профайлера ожидаемое время выполнения будет больше заявленного в таблице, т.к. в том случае запускается только программа. Он запускался без флагов оптимизации и при компиляции на GCC.
В этой лабораторной не использован замер "реального времени", т.к. его нужно учитывать только при многопоточности
Решение этой задачи методом многопоточности крайне сложное хотя бы по той причине, что могут возникать коллизии из-за того, что нельзя один и тот же ресурс (например, массив посещенных вершин) раздавать нескольким потокам одновременно.
Для генерации графа был использован генератор псевдослучайных чисел для того, чтобы не вводить огромный массив с руки или из файла: для генерации одного и того же графа при каждой компиляции достаточно закомментировать строку srand(time(NULL)); при каждой компиляции вводится: число вершин – 26, начальная вершина – v, конечная вершина – а
Пример исполнения программы
По выведенной таблице видно, что от v до а уже есть ребро, но алгоритм всегда ищет путь, по которому можно добраться до вершины с меньшей стоимостью. Если сложить пути, можно увидеть, что итоговая стоимость пути вышла меньше изначальной, что означает, что программа работает корректно.
Теория
Задача поиска кратчайшего пути— задача поиска самого короткого пути между двумя точками (вершинами) на графе, в которой минимизируется сумма весов рёбер, составляющих путь.
Алгоритмы решения этой задачи являются неотъемлемой частью программного обеспечения современных GPS-навигаторов, различных геоинформационных систем, которые применяются во многих отраслях науки и техники.
В качестве структуры данных для хранения графа использован двумерный динамический массив: можно было использовать фибоначчиеву кучу, однако ее реализации нет в Си, и это тема отдельной курсовой работы.
Путь в ориентированном графе — это такая последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.
Алгоритм Дейкстры выполняется за время 𝑂(𝑁^2) и является асимптотически быстрейшим из известных последовательных алгоритмов для данного класса задач.
Подсчет стоимости пути без оптимизаций
Изначальная программа была написана на С++, поэтому для этой версии программы используются компиляторы g++ и clang++; вторая программа была переделана под Си для использования различных оптимизаций
Время исполнения будет представлено в таблице после экспериментов, а код будет предоставлен в Приложении
Программа компилируется строкой
g++ Dijkstra.cpp –o Dijkstra –O0
Посмотрим, что скажет профайлер
> sudo perf record ./Dijkstra
...
[ perf record: Woken up 21 times to write data ]
[ perf record: Captured and wrote 5.630 MB perf.data (147113 samples) ]
> sudo perf stat -B -e task-clock,context-switches,cpu-migrations,cycles,instructions,cache-references,cache-misses,branches,branch-misses,migrations,page-faults ./Dijkstra
...
Performance counter stats for './Dijkstra':
37,207.74 msec task-clock # 0.833 CPUs utilized
3,813 context-switches # 102.479 /sec
61 cpu-migrations # 1.639 /sec
130,879,845,926 cycles # 3.518 GHz (83.33%)
345,848,604,949 instructions # 2.64 insn per cycle (83.34%)
98,160,833 cache-references # 2.638 M/sec (83.33%)
844,904 cache-misses # 0.861 % of all cache refs (83.33%)
55,975,253,722 branches # 1.504 G/sec (83.33%)
100,965,754 branch-misses # 0.18% of all branches (83.33%)
61 migrations # 1.639 /sec
128 page-faults # 3.440 /sec
44.651619163 seconds time elapsed
32.605835000 seconds user
4.599029000 seconds sys
IPC = 2.64, cache-misses = 0.861%
Подсчет стоимости пути с различными оптимизациями
Для оптимизации предыдущей программы были предприняты следующие шаги:
Убрано ООП
Стало меньше обращения к памяти (итераторы создаются до циклов, а элементы структур данных сохраняются во временные переменные)
Умножения заменены на сложение (там, где это возможно)
Размотка циклов (там, где это возможно)
Итераторы заменены с с++ на ++с
Выделение памяти вынесено из функции выполнения алгоритма, теперь вместо выделения память там просто обнуляется
Условия, не зависящие от элементов в итерации, вынесены за циклы
Программа компилируется строкой
gcc Dijkstra_2.c –o Dijkstra_2 –O0
Посмотрим, что скажет профайлер
> sudo perf stat -B -e task-clock,context-switches,cpu-migrations,cycles,instructions,cache-references,cache-misses,branches,branch-misses,migrations,page-faults ./Dijkstra_2
...
Performance counter stats for './Dijkstra_2':
30,220.81 msec task-clock # 0.886 CPUs utilized
2,867 context-switches # 94.868 /sec
13 cpu-migrations # 0.430 /sec
103,213,021,911 cycles # 3.415 GHz (83.33%)
331,999,463,220 instructions # 3.22 insn per cycle (83.33%)
12,364,150 cache-references # 409.127 K/sec (83.33%)
758,998 cache-misses # 6.139 % of all cache refs (83.33%)
37,193,576,790 branches # 1.231 G/sec (83.33%)
725,192 branch-misses # 0.00% of all branches (83.34%)
13 migrations # 0.430 /sec
72 page-faults # 2.382 /sec
34.092373351 seconds time elapsed
30.214710000 seconds user
0.003997000 seconds sys
IPC = 3.22, cache-misses = 6.139%
Замеры
Замеры времени приведены в таблице ниже (clang –O2 не учитывается, т.к. его время и так слишком большое)
|
g++ Dijkstra |
clang++ Dijkstra |
gcc Dijkstra_2 |
clang Dijkstra_2 |
||
-O0 |
31.962 |
33.5727 |
25.043 |
27.632 |
||
-O2 |
18.94 |
Не учитывается |
13.806 |
Не учитывается |
||
|
IPC |
Cache-misses |
||||
Dijkstra.cpp |
2.64 |
0.861 |
||||
Lab2_2 |
3.22 |
6.139 |
||||