Князьков В. С. 4(2017)

УДК 004.421

В. С. Князьков, Т. В. Князькова

СИНТЕЗ АЛГОРИТМОВ МАССИВНЫХ ВЫЧИСЛЕНИЙ

ДЛЯ МНОГОЯДЕРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СТРУКТУР

      В статье рассматривается подход к синтезу алгоритмов массивных вычислений на базе пространственной алгебры (S-алгебры),  который ориентирован на создание оптимальных с точки зрения временной и пространственной  сложности реализации  алгоритмов массивной обработки данных  в   многоядерных процессорных пространствах. Предлагаемый подход к синтезу позволяет формально построить оптимальную с точки зрения выбранного критерия сложности  схему  обработки данных   для той процессорной среды, в которой будет выполняться  данный алгоритм. Концептуально  такие многоядерные процессорные среды представляют массивы битовых процессорных элементов, связанных между собой битовыми каналами обмена данными через коммутационные элементы.

      Приводится пример синтеза алгоритма решения задачи поиска максимального числа в массиве положительных целых чисел  M разрядности из N  элементов. Показана оценка временной сложности синтезируемых алгоритмов, причем оценку  временной сложности реализации процедуры поиска максимального числа  можно было получить из выражения общей оценки операций данного класса  до разработки конкретного алгоритма.

      Ключевые слова: массивные вычисления, многоядерные вычислительные структуры, синтез алгоритмов, оценка сложности.