Исследование эффективности реализации параллельных вычислений на класстере МЭИ (статья Лю Ляна)

АВТОМАТИКА, ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА, ИНФОРМАТИКА 90 Исследование эффективности реализации параллельных вычислений на кластере МЭИ* Лян Лю Описаны результаты исследования эффективности параллельного решения зплач на кластере Московского знсргетического института (технического университета) (МЭИ). Рассмотрены различные методы параллельного перемножения матриц и решения сис- тем линейных уравнений с использованием средств МР! на языке С. Введение Вестник МЗИ. № 5.

7007 и Технической основой Центра суперкомпьютерных технологий (ЦСТ) в МЭИ является кластер, состоящий из 32 параллельно работающих двухъядерных процессоров АМ!) Ор!егоп с технологией передачи данных 1!чР1Н!ВАНР с пропускной способностью 10 Гбит/с и обеспечивающий пиковую производительность 281,6 ОР(,ОРЯ (порядка 3 10" операций в секунду) 111. Этот кластер стоит на сорок третьем месте в шестой редакции рейтинга Тор 50 самых мощных суперкомпьютеров в России и Содружестве Независимых Государств (СНГ) 12). На кластере установлено необходимое программное обеспечение, позволяющее пользователям решать сложные задачи с использованием современных средств параллельного программирования.

Сравнение параметров с параметрами существующих в России кластерных вычислительных систем 12, 41 показывает, что кластер МЭИ находится в одном ряду с аналогичными установками в ведущих вузах и научно-исследовательских институтах Российской Федерации. Статья поступила в редакцию 6.06.07. Работа поддержана РФФИ, проект 06-01-008!7. '!. Критерии эффективности организации параллельных вычислений на кластерах и основные параметры, влияющие на эффективность Для оценки эффективности организации параллельных вычислений на кластерах используются следующие критерии; 1) козффицнент ускорения С(К) = Тпссл/Тпар(К) где /ппсл — время последовательного выполнения программы без распараллеливания (один компьютер или процессор); Тп,р(К) — время параллельного выполнения программы на К компьютерах или процессорах.

В идеальном случае, т.е. при отсутствии накладных расходов на организацию параллелизма, коэффициент ускорения С(К) равен К. Но время выполнения параллельной программы любой сложности на кластере, почти всегда будет больше, чем время Г„пел/К, так как параллельные программы содержат не поддающиеся распараллеливанию участки, а обмен данными и управление также занимают дополнительное время. Согласно закону Амдала 1 С(К) < , где а — доля последовательа+ (1 — а)/К ных операций; (1 — а) — доля параллельных операций в программе.

Предельное значение С(К) при неограниченном увеличении К равно !/а; АВТОМАТИКА, ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА, ИНФОРМАТИКА 91 2) эффективность использования ресурсов Д(К) = = С(К)/К = Т„„я/(КТва (К)1, показывающая долю использования компьютеров или "процессоров; в идеальном случае ЯК) = 1. Далее приводим основные показатели, от которых зависят критерии эффективности: !) сложность задачи (при перемножении матриц М„„„= М'„„„х М"„„„— это н; при решении систем линейных уравнений — это количество уравнений; прн вычислении значений функции факториал от п — эта н и т.п.); 2) метод реп!ения задачи, способ распараллеливания, язык и качество параллельной программы; 3) количество компьютеров или/и процессоров кластера и их производительность; 4) пропускная способность коммуникаций; 5) ресурсы компьютера: объем памяти различных уровней, пропускная способность устройств ввода- вывода и др.

2. Исследование эффективности решения задач на кластере МЭИ Для исследования эффективности кластера МЭИ и его предельных возможностей были разработаны МР1-программы (известные н хорошо распараллеливаюшиеся программы перемножения матриц и решения систем линейных алгебраических уравнений различными методами).

Программы разрабатывалнсь в среде операционной системы Ь!лах с использованием средств МР! на языке С. Данный язык был выбран потому, что библиотеки средств МР! в стандартной поставке реализованы на языках С и Рог1гап, нз которых С является более предпочтительным языком программирования. Компиляция программы осуществлялась с помощью специального компилятора МР!СХХ, подготавливаю- щего программу для выполнения в среде МР1. Основная задача исследований состояла в получении экспериментальных данных, показывающих влнянис на указанные в 0 1 критерии эффективности параллельного решения задач.

В частности, важно было оценить влияние на критерии эффективности сложности и метода параллельного решения задачи, количества используемых узлов и процессоров и интенсивности межузловых обменов. 2. 1. Перелн!озкение лгатриц Рассматривается .упрощенная задача умножения матрицы на вектор-столбец: М„„! = = М'„„„х М"и „1, где каждый элемент результирующей матрицы вычисляется по формуле н М1/! = ч~, М'(/, /г! х М" !/г! . Для распараллеливания 8=! вл 6000 ° 55 00 х 5000 у 4500 й 4 000 $ 25 00 й зооо $ 25 00 0 20 00 " "1500 х„10 ОО ~щ 500 а а 0 4 8 12 !6 20 24 28 32 Зб 40 44 48 52 56 60 64 К Рнс. !.

Зависимость времени перемножения матриц от ко- личества процессоров К 50 к 45 й 4О и" . зо х 25 ~й 2О „у 15 й!о 5 о о о о о а е о о о о а 4 8 12 16 20 24 28 22 Зб 40 44 48 52 56 60 64 К Рнс. 2. Зависимость времени обмена данными от количе- ства процессоров К 2.2. Реиление систем линейных алгебраических уравнений Система линейных алгебраических уравнений (СЛАУ) может быть представлена как матричное вычисление элементов результирующей матрицы разбивается равномерно на группы в зависимости от количества процессоров кластера К(н > К) по следующему принципу: сначала на каждый процессор распределяется для вычисления по 1 и/КГ (1 аà — целая часть а) элементов, а затем оставшиеся п — 1 н/К! хК элементов добавляются по одному к выделенным группам по очереди, пака не будут полностью исчерпаны. Например, для п = 23 и К = 4 на процессоры будут распределены элементы в количестве б, б, б н 5.

В табл. 1 приведены результаты эффективности выполнения параллельной программы на МР1, выполняющей перемножение матриц для н = 20 000 по описанному методу в зависимости от количества К выделенных процессоров кластера. Графики на рис. ! — 4 показывают, как изменяется время перемножения матриц, время обмена данными между узлами кластера, коэффициент ускорения н эффективность в зависимости от количества используемых процессоров кластера К.

АВТОМАТИКА, ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА, ИНФОРМАТИКА 92 Таблица 1 Количество процессоров К Время перемножения матриц, мс Коэффициент ускорения С(К) Время обмена лаиимми, мс Эффективность ЯК) Д(К) о 0,95 с 0,90 с с 42 39 зб 33 30 27 24 21 18 15 12 9 б 3 с е с О с о о 0,85 0,80 0,75 е о 0,70 0,65 О,бс О 4 8 12 16 20 24 28 32 Зб 40 44 48 52 56 бс 64 К О 4 8 12 16 20 24 28 32 36 40 44 48 52 56 бс 64К Рис. 4, Зависимость эффективности Д(К) от количества процессоров К Рис. 3, Зависимость коэффициента ускорения С(К) от ко- личества процессоров К уравнение Ах = Ь, где А — матрица коэффициентов; х — вектор-столбец переменных и Ь вЂ” вектор-столбец правых частей уравнений.

Если матрица А неособенная, то система имеет единственное решение. В частности, если можно получить матрицу А 1, обратную по отношению к А, то существует единственное решение х = А 'Ь. Существует два вида методов решения СЛАУ: точные (например, метод Гаусса, метод главных элементов, метод квадратных корней и др.) и итерационные (например, метод Якоби, метод Зейделя, метод релаксации и.др.) 13). Точные методы при отсутствии ошибок округления позволяют получить точное решение СЛАУ. В итерационных методах задается на- чальное приближение х,, где 1 = 1, ..., л, и строится О а последовательность (х ) -+ х., где К вЂ” номер ите' я-+ 1Т рации(8= 1,2 ...), ах! = — ( — ~а,"х, — Ь,). Итси /я! 8 рационный процесс прекращается, как только все х, становятся достаточно близкими к х, Итерационные методы привлекательнее с точки зрения распараллеливания вычислений, когда решаются системы большой размерности.

Эффективное применение итерационных методов существенно зависит от удачного выбора начального приближения и быстроты сходи- 1 2 4 3 !2 !б 20 24 28 32 36 40 44 48 52 56 60 64 5952,81601 2979,876041 !503,158092 755,830024 507,727032 384,499985 311,585182 263,626165 229,940083 205,380093 186,648903 173,350026 !63,0049!! 154,889155 149,40!1!5 145,701004 143,039133 141,245127 0 0,23!023 0,489093 1,59799 4,022085 6,39987 9,260105 !2,158871 15,04!925 19,20 !03! 22,287058 25,9! О! 09 29,43944 33,462962 36,571016 39,577055 42,707048 46,021938 ! 1,997672362 3,9602062! 7,875345056 11,72444175 15,48196682 19,10493937 22,58052045 25,88355293 28,98433657 31,3931208 34,33986223 36,51924334 38,43274896 39,84452198 40,8563329! 41,61669527 42,14523413 1 0,998336!8! 0,990051552 0,934418132 0,9770368!2 0,967622926 0,955246968 0,9408550!9 0,924591176 0,90576208 0,385920022 0,858496556 0,829932803 0,80068227 0,766240807 0,729578266 0,6936! 1538 0,653520065 93 АВТОМАТИКА, ВЪ|ЧИСЛИТЕЛЪНАЯ ТЕХНИКА, ИНФОРМАТИКА Таблица 2 Количество процессоров К Коэффициент ускорения С(К) Время обмена даннымн, мс Эффективность ЯК) Время решения СЛЛУ, мс мости процесса.

При небольших порядках СЛАУ используют точные методы либо точные методы в сочетании с итерационными методами. Ниже приводится результаты исследования параллельного решения СЛАУ на кластере МЭИ для двух методов: точного метода Гаусса и итерационного метода Якоби. ние на коэффициент агг и исключаем хг из всех 1 уравнений, начиная со второго и т.д, В результате последовательного исключения неизвестных система уравнений преобразуется в систему уравнений с тре/ / ! х,+ 'Г а,.х.=а,. „ь1, гле /=ив! угольной матрицей /=1, ...,и.

Совокупность вь ется точным ходом 2.2. /. Меи!од Гаусса шолненных вычислений называметода Гаусса. Из и-го уравнения системы определяем х„, из (и — 1)-го уравнения определяем х„! и т.д, до х!. Совокупность таких вычислений называют обратным ходом метода Гаусса, В исследуемой параллельной программе для решения СЛАУ методом Гаусса исходная матрица коэффициентов распределяется по К процессорам кластера циклическими горизонтальными полосами с шириной полосы в одну строку. Первая строка матрицы А помещается в процессор |, вторая строка — в процессор 2 н т. д., К-я строка — в процессор К. За~ем |К ч 1)-я строка снова помещается в процессор 1, (К+ 2)-я строка — в процессор 2 и тд.