Для обоснования распараллеливания алгоритма выполним примерную оценку ее временной сложности.
Если записать структуру циклов для выполнения этапа вычисления центров кластеров на псевдокоде, получим:
Для каждого кластера{.
Для каждого терма кластера{.
Для каждого объекта{.
}.
}.
}.
Время выполнения линейно зависит от количества кластеров, количества термов и количества объектов. Для разбиения массива данных из 100 документов, 1000 уникальных термов на 10 кластеров потребуется 10· 1000·100=1·106 итераций. Для разбиения на 15 кластеров для этого же набора объектов потребуется уже 15· 1000·100=1.5·106. Количество итераций возрастает линейно.
Структура циклов для этапа вычисления матрицы принадлежности:
для каждого объекта {.
для каждого кластера {.
для каждого кластера {.
для каждого терма {.
}.
}.
}.
}.
Как видно из этого кода, время его выполнения линейно зависит от количества объектов и термов и имеет квадратичную зависимость от числа кластеров. Для выполнения этого этапа необходимы вложенные циклы до третьего уровня. Таким образом, например, для разбиения массива данных из 100 документов, 1000 уникальных термов на 10 кластеров потребуется 1000· 10·10·100=1·107 итераций. Для разбиения на 15 кластеров для этого же набора объектов потребуется уже 1000· 15·15·100=2.25·107. Количество итераций возрастает более чем в 2 раза.
И, наконец, вычисление целевой функции:
Для каждого кластера{.
Для каждого ресурса{.
Для каждого терма{.
}.
}.
}.
Время выполнения линейно зависит от количества кластеров, количества объектов.
Как видно из приведенных выше формул в каждом из этапов присутствуют вложенные циклы до 3-го — 4-го уровня вложенности. Для больших массивов данных при запуске алгоритма на компьютере с многоядерном процессором или на вычислительном кластере имеет смысл выполнять эти итерации в отдельных потоках, сокращая тем самым временную сложность алгоритма.
Как известно, на создание и запуск потока системе требуется довольно много ресурсов, что также будет «тормозить» выполнение основной задачи. Во избежание этого в начале выполнения алгоритма создается пул потоков фиксированного размера. Размер этого пула (количество потоков) задает сам пользователь приложения. Самым оптимальным будет размер равный количеству доступных ядер или процессоров на компьютере или в вычислительном кластере.
Каждый этап алгоритма делится на потоки. Пул потоков позволяет не заботиться о количестве одновременно запускаемых задач. Если в настоящий момент нет свободных для выполнения задачи потоков, то они ожидают в очереди. Для подтверждения целесообразности распараллеливания данного алгоритма был проведен эксперимент.
