| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include <string> | ||
| 4 | #include <tuple> | ||
| 5 | #include <vector> | ||
| 6 | |||
| 7 | #include "task/include/task.hpp" | ||
| 8 | |||
| 9 | namespace sabirov_s_hypercube { | ||
| 10 | |||
| 11 | /// @brief Структура входных данных для топологии гиперкуба | ||
| 12 | ✗ | struct HypercubeInput { | |
| 13 | int dimension{0}; ///< Размерность гиперкуба (n), количество процессов = 2^n | ||
| 14 | int source_rank{0}; ///< Ранг процесса-источника | ||
| 15 | int dest_rank{0}; ///< Ранг процесса-получателя | ||
| 16 | std::vector<int> data; ///< Данные для передачи | ||
| 17 | }; | ||
| 18 | |||
| 19 | /// @brief Структура выходных данных для топологии гиперкуба | ||
| 20 | struct HypercubeOutput { | ||
| 21 | std::vector<int> received_data; ///< Полученные данные на процессе-получателе | ||
| 22 | std::vector<int> route; ///< Маршрут передачи (последовательность рангов) | ||
| 23 | bool success; ///< Флаг успешности передачи | ||
| 24 | }; | ||
| 25 | |||
| 26 | using InType = HypercubeInput; | ||
| 27 | using OutType = HypercubeOutput; | ||
| 28 | using TestType = std::tuple<int, std::string>; | ||
| 29 | using BaseTask = ppc::task::Task<InType, OutType>; | ||
| 30 | |||
| 31 | /// @brief Проверяет, является ли число степенью двойки | ||
| 32 | /// @param n Число для проверки | ||
| 33 | /// @return true если n = 2^k для некоторого k >= 0 | ||
| 34 | inline bool IsPowerOfTwo(int n) { | ||
| 35 | return n > 0 && (n & (n - 1)) == 0; | ||
| 36 | } | ||
| 37 | |||
| 38 | /// @brief Вычисляет логарифм по основанию 2 (размерность гиперкуба) | ||
| 39 | /// @param n Количество узлов (должно быть степенью двойки) | ||
| 40 | /// @return Размерность гиперкуба | ||
| 41 | inline int Log2(int n) { | ||
| 42 | int result = 0; | ||
| 43 | ✗ | while (n > 1) { | |
| 44 | ✗ | n >>= 1; | |
| 45 | ✗ | result++; | |
| 46 | } | ||
| 47 | return result; | ||
| 48 | } | ||
| 49 | |||
| 50 | /// @brief Получает соседа узла в заданном измерении | ||
| 51 | /// @param rank Ранг узла | ||
| 52 | /// @param dimension Номер измерения (0 до n-1) | ||
| 53 | /// @return Ранг соседа | ||
| 54 | inline int GetNeighbor(int rank, int dimension) { | ||
| 55 | ✗ | return rank ^ (1 << dimension); | |
| 56 | } | ||
| 57 | |||
| 58 | /// @brief Вычисляет расстояние Хэмминга между двумя узлами | ||
| 59 | /// @param a Первый узел | ||
| 60 | /// @param b Второй узел | ||
| 61 | /// @return Количество различающихся бит (минимальное расстояние в гиперкубе) | ||
| 62 | inline int HammingDistance(int a, int b) { | ||
| 63 | ✗ | int diff = a ^ b; | |
| 64 | int count = 0; | ||
| 65 | ✗ | while (diff != 0) { | |
| 66 | ✗ | count += diff & 1; | |
| 67 | ✗ | diff >>= 1; | |
| 68 | } | ||
| 69 | return count; | ||
| 70 | } | ||
| 71 | |||
| 72 | /// @brief Строит маршрут от источника к получателю в гиперкубе | ||
| 73 | /// @param source Ранг источника | ||
| 74 | /// @param dest Ранг получателя | ||
| 75 | /// @return Вектор рангов, представляющий маршрут (включая source и dest) | ||
| 76 | ✗ | inline std::vector<int> BuildRoute(int source, int dest) { | |
| 77 | ✗ | std::vector<int> route; | |
| 78 | route.push_back(source); | ||
| 79 | |||
| 80 | ✗ | int current = source; | |
| 81 | ✗ | int diff = source ^ dest; | |
| 82 | |||
| 83 | // Идем по биту за раз, исправляя отличающиеся биты | ||
| 84 | int bit = 0; | ||
| 85 | ✗ | while (diff != 0) { | |
| 86 | ✗ | if ((diff & 1) != 0) { | |
| 87 | ✗ | current = GetNeighbor(current, bit); | |
| 88 | route.push_back(current); | ||
| 89 | } | ||
| 90 | ✗ | diff >>= 1; | |
| 91 | ✗ | bit++; | |
| 92 | } | ||
| 93 | |||
| 94 | ✗ | return route; | |
| 95 | } | ||
| 96 | |||
| 97 | } // namespace sabirov_s_hypercube | ||
| 98 |