На правах рукописи
Щербак Максим Павлович
Моделирование системы абсолютно жестких тел и односторонних
податливых связей на компьютере с параллельной архитектурой
Специальность 05.13.18 — «Математическое моделирование,
численные методы и комплексы программ»
АВТОРЕФЕРАТ
диссертации на соискание ученой степени кандидата технических наук
Петрозаводск 2006
Работа выполнена в государственном образовательном учреждении высшего профессионального образования
ПЕТРОЗАВОДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
Научный руководитель: кандидат технических наук, профессор Гольдштейн Юрий Борисович, Офицальные оппоненты: доктор технических наук, профессор Сливкер Владимир Исаевич кандидат физико-математических наук, доцент Соколов Андрей Владимирович
Ведущая организация: Санкт-Петербургский государственный архитектурно-строительный университет (СПбГАСУ)
Защита состоится 2 ноября 2006 в 14:00 на заседании диссертационного совета Д 212.190.03 при Петрозаводском государственном университете.
С диссертацией можно ознакомиться в библиотеке Петрозаводского государственного университета.
Автореферат разослан « » 2006 г.
Ученый секретарь диссертационного совета Поляков В. В.
1.
Общая характеристика работы
Актуальность Среди механических и биомеханических систем, напряженно-деформированное состояние которых подлежит изучению, встречаются системы, содержащие элементы с существенно отличающимися жесткостями. Примеры подобных систем можно найти в различных областях. Например, в мостостроении часто используются фермы, в которых сечение одного из поясов намного массивнее сечений остальных элементов. В технике примерами могут служить различные рычажные устройства с гидро- и пневмоприводами. Ярким представителем обсуждаемых систем является скелетно-мышечная система опорно-двигательного аппарата позвоночных. Жесткость костей скелета на несколько порядков выше жесткости мышц и сухожилий — элементов, которые воспринимают растяжение и практически не сопротивляются сжатию.
Необходимость анализа подобных механических систем возникает довольно часто в различных областях, подчас весьма далеких друг от друга. Например, такой анализ требуется в медицине при лечении травм и протезировании, в авиакосмической промышленности и в автомобилестроении при проектировании систем безопасности, в робототехнике при проектировании разного рода манипуляторов.
Определение усилий и перемещений в обсуждаемых механических системах с помощью современных программных расчетных комплексов затруднено по ряду причин. Одна из них связана с наличием в рассчитываемой системе сопряженных элементов с существенно отличающимися жесткостями. Это обстоятельство негативно влияет на точность расчетов в программах, использующих тот или иной метод решения задачи в перемещениях.
Сказанное относится и к методу конечных элементов, который положен в основу почти всех современных коммерческих программ, предназначенных для расчетов на прочность.
Наличие односторонних связей в обсуждаемых механических системах — это другая причина, затрудняющая, а иногда и делающая невозможным применение промышленных программ. Определяющими соотношениями задачи расчета механической системы с односторонними связями в предположении физической и геометрической линейности являются линейные алгебраические уравнения, коэффициенты которых зависят от искомого решения. Эти зависимости представляют из себя функции, терпящие разрыв, что делает задачу еще и сингулярной. Все современные универсальные расчетные комплексы, использующиеся для расчета механических систем, построены на традиционных алгоритмах, которые предполагают решение систем линейных алгебраических уравнений с детерминированными коэффициентами. Описанная задача плохо укладывается в рамки этих алгоритмов, поэтому почти во всех современных программах поддержка расчетов систем с односторонними связями либо отсутствует, либо реализована слабо. Сказанное относится и к протестированным нами пакетам COSMOS 2.9, ANSYS 9.0, SCAD 7.31.R5.
Этот недостаток довольно существенен, поскольку к задачам указанного рода в настоящее время испытывается повышенный интерес, что было выявлено нами при анализе публикаций, в том числе и самых последних, в области механики и биомеханики.
Для ухода от сингулярности предлагается решать задачу в пространстве состояний с заданной энергетической метрикой, что позволяет свести ее к задаче квадратичного программирования. Вычисления выполнялись при помощи специализированного варианта метода Вулфа, который, хотя и является одним из наиболее эффективных методов, все же требует выполнения большого объема опреаций, многократно перекрывающего все другие вычислительные затраты. Поиск путей снижения затрат времени на выполнение вычислительных операций привел к идее использования параллельных вычислений. В результате был разработан параллельный вариант алгоритма метода Вулфа, предназначенный для кластеров — наиболее доступного класса параллельных компьютеров.
Цель диссертационной работы 1. Создание математической модели систем абсолютно жестких тел, сопрягаемых друг с другом при помощи различных, в том числе и односторонних связей.
2. Разработка алгоритма расчета описанной механической системы, реализующей параллельные вычисления.
3. Разработка программного комплекса, реализующего полученные алгоритмы и позволяющего выполнять расчет рассматриваемых механических систем.
4. Численное исследование мехнической системы жестких тел и податливых односторонних связей, для которой имеются данные натурного эксперимента. Сравнение расчетных и экспериментальных результатов.
5. Анализ эффективности предложенного параллельного алгоритма.
Основные задачи
исследований 1. Определение набора элементов математической модели системы абсолютно жестких тел и связывающих их устройств (двусторонних связей), а также способа описания этих элементов. Формулировка и анализ полной системы уравнений, описывающих равновесное состояние модели, с целью определения усилий и перемещений в элементах последней от статических и кинематических воздействий.
2. Построение второй математической модели, топологически идеинтичной предыдущей, но предусматривающей наличие односторонних связей. Получение разрешающих (определяющих) соотношений, описывающих равновесное состояние модели. Сравнительный анализ существующих численных методов решения определяющих уравнений с целью выбора наиболее приемлемого метода и, в случае необходимости, модификации одного из них.
3. Проверка адекватности разработанных алгоритмов на примере расчета одной из биомеханических систем.
4. Разработка параллельного алгоритма для решения рассматриваемой задачи как задачи математического программирования и демонстрация возможности создания на основе этого алгоритма эффективных компьютерных программ.
Методы исследования 1. Для создания обеих математических моделей применялись методы строительной механики, аппарат линейной алгебры и элементы теории графов. Эти же методы использовались и при выводе полной системы уравнений задачи.
2. При создании вычислительных алгоритмов использовались методы математического, в частности квадратичного, программирования и численные методы линейной алгебры.
3. При построении параллельного алгоритма метода Вулфа использовалась теория информационной структуры программ и алгоритмов1.
4. Для создания программного комплекса использовался пакет свободно распространяемых средств разработки gcc в среде Linux, а также коммуникационные библиотеки MPICH.
1 См.монографии: Воеводин В. В. Параллельные вычисления / В. В. Воеводин, Вл. В. Воеводин. СПб.:
БХВ-Петербург, 2002. 608 с. и Ершов А. П. Современное состояние теории схем программ / А. П. Ершов // Проблемы кибернетики. M., 1973. №27. C. 87–110.
Основные научные положения, выносимые на защиту 1. Механо-математическая модель системы абсолютно жестких тел, изолированных узлов, абсолютно жестких стержней и податливых односторонних связей.
2. Полная система уравнений, описывающих равновесное состояние предложенной модели, и вытекающие из нее разрешающие уравнения.
3. Предложеный метод расчета систем с односторонними связями, названный методом вариации жесткостей связей.
4. Алгоритмы численного решения задачи, в том числе и алгоритм вариации жесткостей связей.
5. Параллельный алгоритм метода Вулфа, предназначенный для решения задач квадратичного программирования.
Достоверность и обоснованность положений, выводов и рекомендаций Достоверность обеспечивается корректным последовательным применением методов механики твердого деформируемого тела и математических методов. Результаты моделирования, полученные с помощью численных экспериментов, согласуются с результатами, установленными другими методами, а также с данными натурных измерений.
Научная новизна исследований 1. Предложена модель системы абсолютно жестких тел, изолированных узлов, абсолютно жестких стержней и податливых связей.
2. Предложена модель топологически идеинтичная предыдущей, но предусматривающая наличие односторонних связей.
3. Разработан параллельный алгоритм метода Вулфа для суперкомпьютеров с распределенной памятью (кластеров).
4. Разработан инженерный метод расчета систем с односторонними связями — метод вариации жесткостей связей.
Практическое значение работы 1. Предложена модель системы жестких тел и податливых связей.
2. Разработаны вычислительные алгоритмы, включая и алгоритм вариации жесткостей связей.
3. Предложен параллельный алгоритм метода Вулфа, который может быть применен для решения любых задач квадратичного программирования, а не только для расчета рассматриваемых механических и биомеханических систем. Алгоритм создан для кластеров, однако, с небольшими изменениями, он может быть применен для других типов параллельных компьютеров, например в многоядерных системах.
4. Создан программный расчетный комплекс, позволяющий выполнять расчет механических систем рассматриваемого типа.
Личный вклад автора 1. Формулирование разрешающих соотношений модели, учитывающей односторонние связи.
2. Анализ предложенных моделей, выбор методов их решения и разработка алгоритмов.
3. Разработка параллельного алгоритма метода Вулфа для параллельных компьютеров с распределенной памятью.
4. Создание программного комплекса, реализующего предложенные методы и алгоритмы.
5. Постановка и решение задачи биомеханики с помошью разработанного программного комплекса.
6. Проведение численных экспериментов над параллельным алгоритмом, с целью определить основные показатели его эффективности.
7. Автором был предложен метод вариации жесткостей связей.
Апробация работы и публикации Результаты настоящей работы были представлены на 20-й Международной конференции «Математическое моделирование в механике сплошных сред.
Методы граничных и конечных элементов» (Санкт-Петербург, сентябрь 2003).
Основные положения данной работы были изложены в четырех научных публикациях.
Структура и объем диссертации Диссертация состоит из введения, четырех глав, заключения, а также списка цитируемой литературы. Она изложена на 113 станицах и включает в себя 28 рисунков и 8 таблиц. Библиографический список содержит 81 ссылку.
2. Содержание работы Во введении обсуждаются актуальность работы, ее цели и задачи. Приведены краткие исторические справки о развитии и современном состоянии методов строительной механики, а также о применяемой в расчетах аппаратной базе.
Первая глава посвящена математической модели линейной механической системы, состоящей из набора абсолютно жестких тел, изолированных узлов и соединяющих их стержней, которые могут быть жесткими или податливыми. Ставится задача отыскания усилий и перемещений во всех элементах системы при заданном внешнем воздействии.
В этой главе даются основные определения и оговаривается используемая система обозначений. Из рассмотрения равновесного состояния предложенной модели получена полная система уравнений. Как и обычно, она состоит из статических, кинематических и физических соотношений.
Жесткое тело моделируется набором точек в пространстве, расстояние между которыми остается неизменным. Частным случаем жесткого тела является жесткий стержень, он представляет из себя пару точек, находящихся друг от друга на фиксированном расстоянии. Податливая связь моделируется также двумя точками в пространстве, однако расстояние между ними может меняться. Оно зависит от силы, приложенной по концам стержня (к точкам) и направленной вдоль его оси.
Под системой (конструкцией) понимается набор из абсолютно жестких тел и изолированных узлов, которые соединяются между собой различными устройствами. Ими могут быть сферические шарниры, а также жесткие и податливые стержни-связи. Сферический шарнир моделируется заданием общей точки на двух элементах. Она жестко связывает линейные перемещения двух точек разных объектов, не ограничивая при этом их взаимный поворот. При наличии общей точки для трех и более стержней вводится объект, называемый изолированным узлом.
К любой точке системы может быть приложено внешнее воздействие, которое может быть либо силой, либо задаваемым смещением. Второй тип нагружения в строительной механике называют кинематическим воздействием. Податливые стержни могут быть подвергнуты изменению температуры, вызывающему изменение их начальных длин. В таком случае говорят, что к системе приложено температурное воздействие. Комбинируя три перечисленных типа загружения, можно задать любую статическую нагрузку на систему.
Конструкция может содержать абсолютно жесткие тела, изолированные узлы, жесткие стержни, податливые связи, сферические шарниры и опорные точки. Чтобы полностью описать такую систему, необходимо указать координаты всех характерных точек, т. е. задать положение всех шарниров системы, всех изолированных узлов и всех точек крепления стержней.
Для приведенных выше математических объектов, моделирующих механическую систему, составлены уравнения, описывающие взаимные перемещения ее элементов (кинематические соотношения) и условия равновесия этих же элементов (статические уравнения). Кроме этого, для податливых элементов записаны физические уравнения, следующие из закона Гука. Перечисленные уравнения образуют систему размерностью m, которую в механике твердого деформируемого тела называют полной системой уравнений.
Ее неизвестными являются усилия во всех стержнях и шарнирах, а также перемещения жестких тел и изолированых узлов.
Если исходная конструкция неизменяема и не содержит избыточных абсолютно жестких стержней-связей, то матрица полной системы уравнений имеет обратную. Однако непосредственное решение полной системы уравнений сопряжено с рядом неудобств. Во-первых, полная система уравнений обладает большими размерами и содержит в качестве неизвестных все параметры состояния механической системы. Обычно же требуется определить только часть этих параметров, например только усилия. Во-вторых, матрица этой системы уравнений не обладает положительной определенностью.
Для преодоления этих неудобств были получены так называемые канонические уравнения метода сил, неизвестными в которых выступают n параметров, имеющих смысл реакций определенных связей. Достигается это путем преобразования полной системы уравнений относительно оставшихся m n неизвестных.
Матрица a уравнений метода сил является симметричной положительно определенной матрицей с размерами n n. Вектор A свободных членов содержит n элементов. По вектору X однозначно устанавливаются остальные параметры состояния модели.
В конце первой главы приведен иллюстративный пример.
Вторая глава посвящена модели, предусматривающей наличие односторонних связей. Здесь обсуждается специфика, которую привносит в модель, рассмотренную в главе 1, учет односторонней работы всех или части связей системы.
Как уже отмечалось, определяющими (разрешающими) соотношениями модели является система линейных уравнений, коэффициенты которой зависят от ее решения. Зависимости эти представляют собой функции с разрывом, что делает задачу сингулярной. Во второй главе рассмотрены два подхода к ее решению. Первый, традиционный для механики, основан на итерационном процессе решения системы уравнений и подборе коэффициентов. И хотя для этого способа не существует доказательств сходимости, он применяется в инженерной практике чаще других. Второй подход предполагает свести исходную задачу к задаче квадратичного программирования и тем самым уйти от сингулярности. Определяющими в этом случае становятся соотношения Куна-Таккера.
В рамках первого подхода в диссертации предложен новый инженерный метод расчета систем с односторонними связями — метод вариации жесткостей связей. В рамках второго подхода рассмотрены два метода решения задачи оптимизации: метод Монте-Карло и один из точных методов квадратичного программирования — метод Вулфа.
Появление односторонних связей в механической системе требует введения неравенств в ее математическую модель. Эти неравенства отражают специфику работы односторонней связи: она препятствует перемещению в одном направлении и не сопротивляется перемещению в противоположном направлении, усилие (реакция) в ней возможно только одного знака. Обычная нить — яркий пример подобной связи: она не препятствует сближению концов, а усилие в ней может быть только растягивающим. При обозначении Zi и Xi для допустимого перемещения по направлению односторонней связи и ее реакции, ограничения имеют вид:
Эти условия определяют состояние односторонней связи. Всего их может быть два: активное, когда Zi = 0, Xi > 0, и неактивное при Zi 0, Xi = 0. В активном состоянии связь воспринимает усилие, т. е. в ней возникает ненулевая реакция. Напротив, в неактивном состоянии связь усилия не воспринимает, что отражается на коэффициентах в определяющих соотношениях.
На поиске всех неактивных связей основан современный инженерный подход к расчету систем с односторонними связями. Принцип его заключается в итерационном процессе расчета механической системы, в которой все односторонние связи считаются двусторонними. На каждом шаге с помощью зависисмостей (2) определяется список неактивных связей, которые затем временно исключаются из системы. Итерационный процесс считается завершенным, если по результатам очередного расчета изменений в списке активных связей не произойдет. Расчетную схему, которая использовалась в последнем шаге, называют рабочей системой. Все связи в ней заведомо активны и поэтому могут трактоваться как двусторонние, что позволяет применять к рабочей системе обычные методы строительной механики.
Самым известным алгоритмом поиска рабочей системы является алгоритм И. М. Рабиновича1. Однако, несмотря на свою известность, названный алгоритм не всегда приводит к решению, даже если оно существует. Это демонстрируют известные тестовые задачи2.
В настоящей диссертационнной работе предложен альтернативный вариант метода поиска рабочей системы, названный методом вариации жесткостей связей. Основное его отличие от традиционного метода в том, что неактивные связи не удаляются из системы, но жесткость их уменьшается.
Это позволило улучшить сходимость и расширить класс решаемых задач. С помощью предложенного метода были решены тестовые задачи, компрометирующие метод И. М. Рабиновича.
Метод вариации жесткостей связей имеет то достоинство, что он «физически очевиден», кроме того, при его применении топология конструкции сохраняется в процессе вычислений, и он менее громоздок, чем любой метод математического программирования. Главный недостаток метода заключен в том, что он не имеет строгого математического обоснования.
Подобного недостатка лишены методы, основанные на минимизации энергетической функции, нацеленные на использование аппарата математического программирования. С помощью равенства (1) и условий (2), а также принципов метода сил были получены соотношения:
которые являются условиями Куна-Таккера для следующей квадратичной задачи:
Здесь a, A — компоненты системы (1), X — вектор базисных усилий в односторонних связях, состоящий из n элементов, N — вектор небазисных усилий в односторонних связях.
Программа (5) есть задача минимизации квадратичной энергетической функции = 2 X a X + X A при линейных ограничениях. Матрица a в этой 1 См.:Рабинович И. М. Курс строительной механики / И. М. Рабинович. М.: Стройиздат, 1954. ч. II. 544 с.
2 См.Перельмутер А. В. Расчетные модели сооруженний и возможность их анализа / А. В. Перельмутер, В. И. Сливкер. Киев: ВПП «Компас», 2001. 448 c.
функции является симметричной положительно определенной, поэтому выбор методов для отыскания минимума функции широк. Наиболее удобный из них — это метод Вулфа.
При решении задачи (5) с помощью общего алгоритма Вулфа необходимо сначала отыскать одну из точек на опорном плане (найти допустимое базисное решение), что связано с большим объемом вычислений. Однако этих вычислений можно избежать, если учесть специфику решаемой задачи. Как было показано А. В. Перельмутером1, при расчете систем с односторонними связями задачу квадратичного программирования можно поставить так, чтобы выход на опорный план обеспечивался автоматически. Для этого в программе (5) заменяют функцию цели и переходят от задачи минимизации энергетической функции к задаче максимизации параметра загружения, в качестве которого выступает скалярный множитель p [0; 1] перед вектором нагрузки. Полученная таким образом программа имеет вид:
Условия Куна-Таккера для нее таковы:
Компоненты векторов A0 и S 0 — суть неотрицательные величины, поэтому при нулевых значениях базисных переменных X, и p ни одно из условий (7), (8) не будет нарушено. Это означает, что первое нулевое решение программы будет допустимым базисным решением. Таким образом, сразу же становится возможным переходить к третьему этапу2 метода Вулфа.
В третьей главе обсуждается применимость предложенной модели для расчетов биомеханических систем. Возможность подобного использования модели устанавливается при помощи расчета одной из таких систем и сравнением результатов с имеющимися экспериментальными данными.
1 См.:Перельмутер А. В. Использование методов квадратичного программирования для систем с односторонними связями / А. В. Перельмутер // Исследования по теории сооружений. М.: Стройиздат, 1972. Вып. XIX.
C. 138–147.
2 В изложении Кюнци (см.: Кюнци Г.П., Крелле В. Нелинейное программирование. «Советское радио», 1965. 303 c.) Рассматривается фрагмент скелетно-мышечной системы человека, включающий бедренные кости и таз, соединенные тазобедренными суставами и мышцами. Необходимо определить усилия, возникающие в тазобедренном суставе при медленной ходьбе. Эта задача выбрана потому, что экспериментальные исследования нагрузок на тазобедренные суставы уже были проведены1 и существует возможность сравнения получаемых теоретически результатов с данными натурных измерений. Речь идет об исследованиях, проведеных в конце 80-х годов прошлого века в лаборатории биомеханики Берлинского медицинского университета. Данные об усилиях в суставе получены снятием показаний с тензометров, вмонтированных в эндопротез головки бедренной кости. Для сравнения с результатами расчета выбраны данные об усилиях в тазобедренном суставе, полученные у одного из пациентов при медленной ходьбе со скоростью 2 км/ч.
Расчет выполнялся следующим образом. Время полного цикла шага от одного касания правой ногой опоры до другого был разбит на 8 равных интервалов. Началу каждого временного отрезка соответствовало определенное положение тела, которое устанавливалось по видеозаписи идущего медленным шагом человека. Соответствующие фазы движения показаны на рис. 1. Для каждого положения строилась своя расчетная схема и выполнялся статический расчет.
На рис. 2a показаны графики измеренных усилий в тазобедренном суставе пациента. По оси абсцисс отложены фазы движения, выраженные в процентах. По оси ординат отложены усилия, возникающие в правом тазобедренном суставе, отнесенные к массе тела и также выраженные в проценСм. статью Bergmann G. Hip Joint Forces During Walking and Running, Measured in Two Patients / G.
Bergmann, F. Graichen, A. Rohlmann // J. Biomechanics. 1993. Vol. 26. pp. 969–990.
Рис. 2. Графики усилий, возникающих в тазобедреном суставе в различных фазах шага, % от массы тела. a) — экспериментальный, b) — расчетный тах. Кривые расчетных значений аналогичных показателей представлены на рис. 2b. Особый интерес вызывает сравнение графиков полных усилий, так как они не зависят от системы координат. Максимальные усилия в суставе приходятся на одноопорную фазу ходьбы (25%–50%), что согласуется с результатами наблюдений. Полное максимальное усилие, полученное расчетом, меньше измеренного на 10,7%. Это и понятно — в расчетах не учитывалась динамика процесса. Очертания графика вычисленных усилий в целом соответствуют экспериментальной кривой.
С помощью предложенной модели удалось выполнить расчет биомеханической системы с довольно большой для биомеханики точностью. Помимо усилий в тазобедренном суставе, были получены и усилия в мышцах, окружающих его, — те усилия, которые не удалось измерить экспериментально. Эту дополнительную информацию можно использовать в других расчетах, например в расчете бедренной кости методом конечных элементов.
Четвертая глава посвящена вопросам применения параллельных вычислений. Здесь предлагается специальный алгоритм метода квадратичного программирования, а именно метода Вулфа, предназначенный для параллельных компьютеров с распределенной памятью (кластеров) и использующий интерфейс MPI. В этой главе приводятся результаты измерения производительности, показанной реализацией этого алгоритма на разных конфигурациях кластера, а также выполнен анализ полученных результатов.
Разработанные в предыдущих главах алгоритмы были реализованы в виде программного комплекса для обычного последовательного компьютера.
С помощью этой программы был проведен ряд численных экспериментов.
Так, на компьютере с процессором AMD Duron 750 для определения усилий в системе с 2000 односторонних связяей на вычисления потребовалось 3 минуты. Для единственного расчета это вполне приемлемо, однако, когда выполняется серия расчетов, подобные временные затраты становятся существенными. Увеличить скорость вычислений предлагается с помощью параллельных вычислений.
Наиболее доступный и распространенный класс параллельных компьютеров — это кластеры. Кластер представляет собой параллельный компьютер с распределенной памятью, который состоит из набора персональных компьютеров, объединенных коммуникационной средой. Обычно коммуникационная среда основана на обмене сообщениями через высокоскоростную сеть. Стандартом de facto среди современных систем обмена сообщениями является коммуникационный интерфейс MPI (Message Passing Interface).
Поэтому параллельный алгоритм разрабатывался нами для кластеров с использованием коммуникационной библиотеки MPI.
Профилировка программы показала, что «узкое место» в ней — операция жорданова исключения, которая является вычислительным ядром метода Вулфа. При решении различных задач на эту операцию тратилось более 90% всего времени расчета. Причем с увеличением размерности решаемой задачи этот показатель увеличивался еще больше. Поэтому было решено применять параллельные вычисления только в алгоритме по методу Вулфа, включающему в себя многократные операции поиска ведущего элемента и процедуры исключения Гаусса-Жордана.
Основная идея предлагаемого параллельного алгоритма состоит в следующем. Симплексная таблица метода Вулфа разбивается на блоки-столбцы по числу вычислительных узлов. Каждый из таких блоков хранится на отдельном узле, а все операции над ним производятся локально. Вычисления на всех узлах согласуются друг с другом при помощи обмена данными через коммуникационную среду (ЛВС).
Операция исключения Гаусса-Жордана выполняется многократно над одной и той же матрицей. Алгоритм этой операции таков:
Порядок выполнения операций внутри каждой записи никак не регламентиj l рован, что позволяет выполнять их параллельно.
Порядок выполнения локальных операций, т. е. операций, выполняемых на каждом отдельном узле над локальными данными, во многом зависит от выбранной схемы распределенного хранения основной таблицы метода Вулфа. В предлагаемом алгоритме используется схема разбиения таблицы по блокам-столбцам. На рис. 3 показана схема хранения данных, совмещенная с графом информационных зависимостей алгоритма (9). На схеме видно, что межузловой обмен сфокусирован только на одном столбце — столбце l, содержащем ведущий элемент akl. Чтобы максимально локализовать вычисления, предлагается на каждом узле хранить копию этого столбца, который рассылается по сети широковещательно до начала операции жорданова исключения. Сама эта операция выполняется локально на каждом узле по алгоритму:
Если l < m p1 или l > m p, то Перед каждой операцией жорданова исключения метод Вулфа предполагает выполнение процедуры поиска исключаемого (ведущего) элемента.
Эта процедура была видоизменена для учета специфики распределенного хранения данных.
Целиком блок-схема предлагаемого параллельного алгоритма метода Вулфа представлена на рис. 5. Левая ветвь относится к единственному процессу с номером 0, который, кроме вычислений, выполняет также и функцию диспетчера. Он получает данные со всех узлов и определяет дальнейший ход вычислений. Левая ветвь относится ко всем остальным процессам. Штриховыми стрелками показаны межузловые обмены информацией, над ними даны названия используемых коммуникационных функций.
MFLOPS
MFLOPS
Рис. 4. a) — ускорение вычислений для различных конфигураций кластера в зависимости от размера задачи, b) — график масштабируемости кластера.Численные эксперименты над алгоритмом проводились на кластере, созданном на базе одного из компьютерных классов Петрозаводского университета, все компьютеры которого одинаково оборудованы и имеют процессор Intel Celeron 2100. Были протестированы конфигурации кластера, включающего 2, 4 и 6 вычислительных узлов. Во всех тестах определялись усилия в односторонних связях, прикрепляющих к опорам жесткое тело, к которому приложена произвольная нагрузка. Связи общим числом n устанавливались случайным образом. Всего было сгенерировано 9 задач с разным числом односторонних связей, и каждая из них была рассчитана на двух-, четырех- и шестиузловом кластере.
Выяснилось, что при расчете систем с числом связей более 2000 алгоритм показал хорошую масштабируемость. Например, производительность шестиузлового кластера была на 75% меньше максимально возможной скорости вычислений (суммы производительностей его узлов). Подобный покаMPI_INIT Анализ исходных данных задачи и подготовка данных для алгоритма Вулфа результатов расчета
MPI_FINALIZE
затель был достигнут на оборудовании, не предназначенном для построения кластеров, что указывает на высокие «параллельные качества» алгоритма.Применение современной аппаратной базы позволит использовать эти качества в полной мере и сделает возможным применение предложенного алгоритма для решения задач очень большого размера.
В заключении приведены основные результаты и выводы работы.
Список публикаций 1. Параллельный алгоритм метода Вулфа для суперкомпьютеров кластерной архитектуры. / М. П. Щербак // Деп. в ВИНИТИ 17.12.05, №1609В2005. 20 с.
2. Разрешающие уравнения для системы жестких тел и податливых связей.
/ Ю. Б. Гольдштейн, М. П. Щербак // Деп. в ВИНИТИ 02.04.03, 587В2003. 45 с. (степень авторского участия 50%) 3. Механика системы абсолютно жестких тел и односторонних податливых связей. / Ю. Б. Гольдштейн, М. П. Щербак // Математическое моделирование в механике сплошных сред. Методы граничных и конечных элементов. Труды 20-й Международной конференции. Т. 2. СПб., 2003.
С. 140–145. (степень авторского участия 60%) 4. Механика системы абсолютно жестких тел и односторонних податливых связей. / Ю. Б. Гольдштейн, М. П. Щербак // Математическое моделирование в механике сплошных сред. Методы граничных и конечных элементов. Тезисы докладов 20-й Международной конференции. СПб., 2003. С. 55–57. (степень авторского участия 60%) Подписано в печать 15.09.2006. Формат 60 84/16.
Государственное образовательное учреждение высшего профессионального образования