BC/NW 2012; №2 (21):10.1

РЕШЕНИЕ ЗАДАЧИ СОРТИРОВКИ НА МНОГОМАШИННОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЕ С ДРЕВОВИДНОЙ СТРУКТУРОЙ

Дерюгин А.А., Рознюк В.М.

Особенность задач сортировки массива целых чисел состоит в том, что их распараллеливание ограничено. В данной работе задача сортировки решается с помощью алгоритма с использованием регулярного набора образцов [1].

Предполагается, для сортировки применяются многомашинные вычислительные системы (ММВС) в виде сжатых древовидных структур с «тонкими» и «толстыми» связями [2]. Связь между вычислительными модулями в ММВС осуществляется с помощью коммутатора. Коммутатор древовидной ММВС является многоярусным, причём каждый ярус состоит из нескольких однотипных коммутационных модулей, а вычислительные модули, также однотипные группируются по , штук и занимают место листьев дерева.

Целью работы является исследование зависимости времени решения задачи сортировки, выраженного в тактах процессора, от параметров ММВС: числа вычислительных модулей в ММВС N, числа вычислительных модулей в группе ширины шины данных W, толщины связей между ярусами коммутатора H, числа ярусов в коммутаторе ММВС.

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

Алгоритм сортировки разделяется на этапы, и для каждого этапа определяется время его выполнения по разработанным аналитическим выражениям. Этапов девять, из них шесть — это этапы вычислений, а три — этапы передач данных. Среди этапов вычислений могут быть выделены два, которые выполняются последовательно, и четыре, которые выполняются параллельно на всех вычислительных модулях. Среди этапов передач два выполняются последовательно и один – параллельно.

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

С помощью программной модели были исследованы следующие зависимости.

1. Зависимость времени решения задачи от числа вычислительных модулей в ММВС. Для сравнения были выбраны структуры с 3-ярусным коммутатором [2]. Графики зависимости времени решения задачи сортировки от числа вычислительных модулей в ММВС для трёх массивов размером в М чисел представлены на рис. 1.

Рис. 1. Зависимость времени решения задачи от числа вычислительных
модулей в ММВС (= 8, W = 1 байт, = = 1)
1 – M = 250000, 2 – M =500000, 3 – M = 1000000

Отдельно были рассмотрены зависимости времён вычислений и передач от числа вычислительных модулей в ММВС. Полученные зависимости показали, что с увеличением числа вычислительных модулей в ММВС время последовательных этапов вычислений и передач увеличивается, а время параллельных — уменьшается, Этим объясняется наличие минимумов на приведенных графиках.

2. Зависимость времени решения задачи от числа вычислительных модулей в группе . Изменение числа вычислительных модулей в группе оказывает влияние только на время этапов передач, причем с увеличением время решения задачи увеличивается.

Анализ показывает, что с увеличением увеличивается число пакетов, передача которых осуществляется на первом уровне коммутации, и уменьшается число пакетов, которые одновременно могут быть переданы на верхних уровнях коммутации. Уменьшение числа пакетов, одновременно передаваемых на верхних уровнях коммутации, оказывает более существенное влияние на время решения задачи, что и приводит к его увеличению. Например, при увеличении числа вычислительных модулей в группе с четырёх до восьми время решения задачи сортировки увеличивается на 40%.

3. Зависимость времени решения задачи от ширины шины данных. Анализ показывает, что увеличение ширины шины данных в 2 раза уменьшает время передачи одного пакета в 2 раза, следовательно, общее время этапов передач уменьшается пропорционально увеличению ширины шины данных, а время вычислений остается постоянным. Общее время решения задачи при этом уменьшается. Например, при увеличении ширины шины данных в 2 раза время решения задачи уменьшается на 50%.

4. Зависимость времени решения задачи от толщины связей. Увеличение толщины связей между ярусами в коммутаторе ММВС влияет на время этапов параллельных передач. Время этапов последовательных передач и время этапов вычислений не зависит от толщины связей между ярусами. Общее время решения задачи при этом уменьшается. Например, при увеличении толщины связей между ярусами коммутатора ММВС в 2 раза (с Н = 1 до Н = 2) время решения уменьшается на 35%.

Также рассматривалась задача выбора наиболее рациональной структуры ММВС на основании значений времени решения задачи сортировки и затрат оборудования на построение коммутатора ММВС. При этом определялись параметры всех возможных вариантов структур коммутаторов ММВС, из которых выделялись варианты, образующие область Парето.

Литература

1. Ши Х., Шеффер Д. Параллельная сортировка с использованием регулярного набора образцов. — Эдмонтон, Канада. — 39 с.

2. http://webdocs.cs.ualberta.ca/~jonathan/publications/parrallel_computing_publications/psrs1.pdf

3. Дерюгин А.А. Коммутаторы вычислительных систем: учебное пособие. — М.: Издательский дом МЭИ, 2008. – 112 с.