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

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

1 2 А.А. Внуков , М.А. Лисенков

'Кафедра кибернетики и мехатроники Российский университет дружбы народов ул. Орджоникидзе, 3, Москва, Россия, 117923

2Кафедра математического обеспечения систем обработки информации и управления Московский государственный институт электроники и математики Трехсвятительский пер., 3, Москва, Россия, 109028

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

Ключевые слова: параллельный алгоритм, динамика промышленного робота.

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

Большинство задач робототехники ряда дисциплин, среди которых механика и приводы роботов, информационные, электронные и вычислительные устройства роботов, методы искусственного интеллекта, управление сложными мехатронны-ми системами, моделирование и исследование робототехнических комплексов, обладают высокой вычислительной сложностью и интенсивностью, связанной с частым повторением, и требуют соответствующих высокопроизводительных вычислительных ресурсов. Одним из решений этой проблемы является распараллеливание вычислений, как на аппаратном, так и на программном уровне. Таким образом, функциональные и распределенные вычисления обладают огромной важностью в сфере робототехники.

В настоящее время робототехника является быстроразвивающимся направлением науки и техники, которое связано с созданием и применением роботов и робототехнических систем. Робот представляет собой универсальный автомат

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

Рис. 1. Промышленный робот-манипулятор ^ 360 450-2 PA

Вычислительные системы для роботов-манипуляторов могут быть многопроцессорными. Распараллеливание процессов выполнения и обработки данных может быть организовано по функциональному признаку, т.е. параллельно будут выполняться, например, системы технического зрения, система управления, система распознавания, а также информационная система. Также распараллеливание может производиться с целью сокращения времени выполнения алгоритмов этих и других систем.

Основные задачи исследования:

— разработка концепции многопроцессорной системы;

— разработка эффективного алгоритма параллельного вычисления для решения прямой и обратной задачи динамики промышленного манипулятора;

— разработка программного обеспечения, позволяющего реализовать и смоделировать поставленные задачи.

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

мени. При этом программа должна моделировать выполнение параллельного алгоритма в многопроцессорной системе и выполнение последовательного алгоритма на одном сложном процессоре.

Модель шестизвенного промышленного манипуляционного робота. Манипулятором называют разомкнутую механическую систему (цепь), состоящую из твердых тел, которые последовательно соединены между собой при помощи шарниров, или призматических (телескопических) сочленений, т.е. это исполнительный механизм промышленного робота, оснащенный приводами и рабочим органом, с помощью которого осуществляется выполнение рабочих функций. Способность воспроизводить движения, подобные движениям рук человека, достигается приданием манипулятору нескольких степеней свободы (рис. 2), по которым осуществляется управляемое движение с целью получения заданного движения рабочего органа — схвата. Число степеней свободы — это число возможных перемещений системы. Оно равно числу обобщенных координат, под которыми понимают независимые переменные, однозначно определяющие положение манипулятора в пространстве.

Фактически промышленный манипуляционный робот представляет манипулятор и блок управления с контроллером и ручным пультом. Манипулятор промышленного робота по своему функциональному назначению должен обеспечивать движение выходного звена и, закрепленного в нем, объекта манипулирования в рабочем пространстве по произвольной заданной траектории. При этом его захват должен находиться с заданными ориентацией и направлением подхода к промежуточным и конечной точкам перемещения. Для полного выполнения этого требования основной рычажный механизм манипулятора должен иметь не менее шести подвижностей (степеней свободы), причем движение по каждой из них должно быть управляемым.

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

Рис. 2. Робот-манипулятор с шестью степенями свободы

Динамическая модель манипуляционного робота. При рассмотрении динамической модели будем использовать уравнения динамики, необходимые для динамического управления роботами. Целью динамического управления является получение требуемого динамического отклика управляемого от ЭВМ манипулятора, чтобы этот отклик соответствовал некоторому заранее определенному множеству критериев. Эти критерии могут быть выражены через импульс и силы реакции и инерции, воздействующие на схват либо на объект. В общем случае проблема управления заключается в получении основных уравнений динамики робота-ма-нипулятора в форме динамической модели физического манипулятора и в последующем определении законов управления, позволяющих достичь желаемого динамического отклика.

В связи с тем, что для построения модели динамики переходных процессов и дальнейшего анализа полученных уравнений необходима аналитическая форма, решено использовать для получения уравнений динамики метод Лагранжа—Эйлера. Основные уравнения:

= т,

V дС) VдС )

где Ь = Ь (, с[1, ?) = Т - V — функция Лагранжа; Т = Т (, с[1,*) — полная кинетическая энергия сиситемы; V = V (, I) — полная потенциальная энергия сиситемы; — обоб-

щенные координаты (0^; т1 — обобщенные силы и моменты.

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

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

Основное уравнение Лагранжа II рода в матричной записи выглядит следующим образом:

£

I=] к=1 1=] к=1 I=1 1= ]

При решении прямой задачи обобщенные координаты с (?) — известные

функции времени. Дифференцируя их, можно получить С1 и с . Зная с, С1, С[1,

можно вычислить все величины входящие в левую часть уравнения (1). Следовательно, можно вычислить обобщенные силы Qj . Этим и определяется алгоритм

решения первой задачи динамики.

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

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

Итак, здесь известными считаются обобщенные силы QJ ^) и значения обобщенных координат и их скоростей в начальный момент ^, т.е. С (?0) и С1 (?0). Подставляя в (1) величины с^0), С^0) и Qj^0), можно привести это уравнение к следующему виду:

П

£ а к](^ ск(^=Р ] (to), (]=1,2..., п),

к=1

где ак] (?0) и в ] (?0) — известные числа.

Аргумент ?0 означает, что эти числа определены для момента ?0 и, следовательно, зависят от выбора этого момента. Фактически они зависят от с (?0), С (^0), Qj (^0). Из п уравнений (1) можно найти п неизвестных величин: Ск (?0), к =

= 1, 2, ..., п. Решение уравнений удобно записать в матричной форме. Для этого введем матрицу а размером п х п с элементами а^, матрицу-столбец в с элементами в] и матрицу столбец С с элементами Ск . Система уравнений (1) примет вид

ад = в, а ее решением будет С = а-1в = у.

Найти закон движения манипулятора — значит найти функции с (?) или в матричном виде — С (?), где д — матрица-столбец с элементами с. Чтобы найти ц^0), необходимо проинтегрировать дифференциальное уравнение. В этом

уравнении матрица у может быть вычислена для любого момента t, если для этого момента известны матрицы-столбцы д, С, Q (элементы матрицы С — это С1, а элементы матрицы Q — это QJ ). Способ вычисления у(^ тот же, что и способ

вычисления у(^), описанный выше.

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

Используем для интегрирования дифференциального уравнения алгоритм Эйлера. Будем двигаться по оси времени малыми шагами At, начиная с ^. На каждом шаге будем считать постоянными матрицы С, с[. Тогда на шаге номер т получим:

С (т+1)= С(т)+ д{т)^,

С(т+1)= С(т)+ С (т)Аи

Для шага т = 0 правые части известны, что позволяет вычислить С(1) и с(1). После этого делается следующий шаг (т = 1), на котором правые части также известны, и т.д. В результате С, С, С становятся известными в дискретных точках оси времени, разделенных интервалами А^ Чем меньше At, тем меньше погрешность расчета, но выше его трудоемкость. В нашем случае из-за равноускоренного движения С вычисляется только в начальный момент.

Разработка модели многопроцессорной вычислительной системы. Для наиболее эффективной реализации алгоритмов решения задач динамики была разработана вычислительная архитектура (ВА) на СБИС (сверхбольшая интегральная схема). Данная ВА представляет собой совокупность процессорных элементов (ПЭ), которые имеют постоянные неизменяемые соединения между собой и, таким образом, обеспечивается вычислительная сеть. В качестве ПЭ могут использоваться систолические чипы, транспьютеры и подобные им цифровые сигнальные процессоры (ЦСП).

Процессорное поле состоит из одинаковых типов ПЭ, которые имеют одинаковые внешние интерфейсы для передачи и приема данных. Такое процессорное поле будет однородным. В нем не требуется использование между ПЭ дополнительных устройств и интерфейсных схем для согласования форматов данных и характеристик электротехнических сигналов, это упрощает (удешевляет) процессорную сеть, делает ее более надежной и быстрой, так как отсутствуют дополнительные промежуточные устройства. Расстояние между ПЭ должны быть одинаковыми или желательно, чтобы были практически одинаковыми. В этом случае время на передачу данных и электрических сигналов между всеми ПЭ сети на процессорной плате или кристалле заказной СБИС будет одинаковым. Процессорный элемент является определенным с точки зрения его топологических характеристик, входных и выходных потоков данных (входов и выходов ПЭ) и процессорных функций (операции, которые выполняет ПЭ), которые в данном случае являются одинаковыми для всех ПЭ.

Процессорное поле определяется глобальной вычисляемой моделью, а каждый ПЭ, определяется локальной моделью. В общем случае обобщенная вычисляемая модель процессорного поля описывается тройкой (О, Е, Т), где специфицирующей О-геометрию процессорной сети, т.е. определяет глобальную модель, Е — процессорную функцию для О (глобальной модели), т.е. определяет глобальную модель и Т — время выполнения для Е (локальная модель), т.е. определяет модель управления процессорным полем. Для модели управления задаются длительности фаз коммуникации, вычислений и иногда длительность собственно фазы управления, во время которой на процессорное поле подается один поток команд. Один поток команд — это команды, которые поступают разом на все ПЭ. Геометрия процессорной сети составляет глобальную модель процессорного поля и есть не что иное, как соединение ПЭ между собой. Локальная модель Е процессорного поля определяется процессорной функцией для каждого ПЭ.

Таким образом, топологические особенности ПЭ, входные и выходные потоки данных для каждого ПЭ, процессорная функция для каждого ПЭ — эта совокупность является заданием глобальной и локальной моделей процессорного поля.

Для подключения платы процессорного поля к вычислительной или технической системе необходима интерфейсная система. Интерфейсная система рассматривается главной вычислительной системой, как внешнее устройство. Главная вычислительная система и интерфейсная система могут функционировать одновременно. Необходима специализированная интерфейсная система. Такой интерфейс поддерживает работу одного или нескольких процессорных полей и обеспечивает минимальные потери времени, не связанные с вычислительным процессом. Для организации правильного пространственно-временного потока данных на процессорном поле нужно иметь:

— специальным образом организованную память (на основе модели магазинной памяти);

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

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

Требуется:

— разработать специализированный вычислитель;

— использовать его в универсальной вычислительной структуре как сопроцессор или вычислительное устройство;

— использовать в технической системе в качестве встраиваемой платы.

Некоторые этапы разработки макета вычислителя:

1) выбираем правильный шестиугольник в качестве топологии ПЭ (вместо реальной);

2) задаем процессорную функцию следующим образом (рис. 3):

а = а Ь = Ь

с = а * Ь + с

с

3) задаем входные и выходные потоки и их направления (рис. 4):

с

4) нужно задать примерную длительность фазы коммуникации и вычисления на основе времени выполнения соответствующих команд ПЭ, выбрав их несколько большими, чем это требуется для коммуникации и вычислений для их корректного завершения;

5) математическая постановка задачи умножения матриц. Зададим операцию А*В=С, где матрицы (4x4) имеют вид:

й!11 й!12 ^3 ^4 Ь11 Ь12 Ь13 Ь14 Сц ^2 ^3 ^4

a2l ^2 a2з ^4 X Ь21 Ь22 Ь23 Ь24 <^21 <^22 ^3 ^4

0 ^з ^4 0 Ь32 3 3 -О 4 3 -О 0 ^2 ^3 ^4

_ 0 0 0 1 _ 0 0 0 1 _ 0 0 0 1

Матрицы А, В — это пятидиагональные ленточные матрицы; С — шестидиагональная ленточная матрица. На рисунке 5 показано использование общей памяти (ОЗУ) и буферной памяти для хранения промежуточного результата.

Рис. 5. Организация вычислительной среды

6) создаем диаграмму, которая показывает направление потоков данных и определяет длительность фаз коммуникаций и вычислений (рис. 6). Таким образом, диаграмма представляет собой уже готовую структуру будущего процессорного поля. Достаточно произвести замену узловых точек на «шестиугольные» ПЭ (рис. 7).

Момент поступления в сеть

Момент поступления в сеть

Рис. 6. Диаграмма следования элементов матриц в потоках данных с отчетами времени

На рисунке 6 отсчеты времени определяют моменты времени поступления или выхода элементов потоков данных для процессорного поля.

Рис. 7. Вычислительное поле, состоящее из 20 ПЭ

Разработка программного обеспечения для решения прямой и обратной задачи динамики

Программа обеспечивает повышение производительности и точности в распределенных вычислениях. Она состоит из нескольких вычислительных блоков, включающих блок моделирования многопроцессорной обработки данных (рис. 8). Данный блок моделирует параллельное выполнение арифметических операций на различных процессорных элементах.

Рис. 8. Структурная схема программы

Последовательность выполнения программного приложения:

1) задание матриц A0 ... A5, матрицы-строки GT (ускорения свободного падения), матриц А для вращательного и поступательного видов звеньев;

2) задание координат центров тяжести звеньев манипулятора и других параметров для нахождение матриц H0 ... H5;

3) задание матриц-столбцов R0 ... R5;

4) нахождение матриц Ui^(^0 ... ^5);

5) нахождение матриц Uijk(^м ... ^55);

6) нахождение Q0 ... Q5: для каждого Q решаются уравнения Лагранжа II рода, т.е., вычисляются левые части каждого уравнения. Таким образом, находятся Qi. При этом в программе формируются элементы матриц а и в, которые записываются в файл и являются входными данными для программы, решающей обратную задачу динамики;

7) задается матрица а (считывается из памяти);

8) определитель данной матрицы проверяется на равенство нулю;

9) если определитель не равен 0, вычисляется обратная матрица а-1;

10) задается матрица-столбец в (считывается из памяти);

11) вычисляется матрица У - а 1 в (т.е. вычисляется столбец д в начальный момент времени);

12) задаются начальные условия для системы уравнений;

13) задаются промежутки времени А? (предусмотрена проверка на неотрицательность А?);

14) находятся д, д. Нахождение д, д производится в шести точках (результаты выводятся на экран).

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

Ускорение работы последовательного алгоритма осуществляется с помощью создания специального высокопроизводительного вычислительного блока. На основе разработанной структуры можно собрать заказную СБИС, в которой будет реализовано процессорное поле с 20 ПЭ с постоянными соединениями, как показано на рис. 7.

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

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

Сравнительная оценка эффективности последовательного и параллельного алгоритмов. Последовательный алгоритм выполнит умножение шести матриц преобразования Аг размерности

пересылки данных между ЦП и ОЗУ в зависимости от системы команд (с командой операции умножения с накоплением или без нее).

Время выполнения параллельного и последовательного алгоритма с учетом операций умножения (х), сложения (+), пересылки (^) можно оценить: Тпаралл = 75

(х, +) + (16 ~ 32) (внешняя ^); Тпосл = 320 (х, +) + (256 ~ 384) (внутренняя ^).

Эти оценки являются оценками сверху для времени выполнения.

Таким образом, оценка ускорения выполнения параллельного алгоритма, по сравнению с последовательным алгоритмом, выполненным на одном сложном процессоре, составит, примерно, величину (320)/(75) = 4,266 без учета затрат времени на выполнение операций внешней и внутренней передачи данных.

Инициализация матриц А1

ЪовЭ/ -соє а,- э1п Э, вігі а,- вігі 9, а,- соэ 3,

біпЗ,- соб а,- сое 3, —біп а,- соэ 9, а,- эт 9,

О БІпа/ соє а,- Э,

эт а, О

1

і— А1

Г Г Г г > г

А2 АЗ А4 А5 А6

Вычислительный

блок

Процессорное поле

Вычислительный

блок

Вычислительный

блок

Вычислительный

блок

и

Вычислительный блок

Т = А1*А2*

*А6

Рис. 9. Параллельный алгоритм для решения прямой задачи динамики

Заключение. Для реализации параллельного алгоритма решения прямой и обратной задач динамики решено использовать процессорную структуру, разработанную в дипломном проекте (см. рис. 7). На основе разработанной структуры можно собрать заказную СБИС, в которой будет реализовано процессорное поле с 20 ПЭ с постоянными соединениями. Стоит отметить, что данная СБИС является универсальной и может использоваться не только в качестве блока робота-манипулятора, она может быть встроена в различные технические устройства для ускорения вычислений.

Результаты, полученные в данном проекте при экспериментальных измерениях времени функционирования последовательного и параллельного алгоритмов, позволяют разработать различные варианты аппаратного и программного обеспечения многопроцессорной вычислительной системы для блока управления промышленного манипуляционного робота. Также достигнуто ускорение вычислений равное 4,266 раза по сравнению с вычислениями на одном сложном процессоре.

Авторами статьи зарегистрировано в Реестре программ для ЭВМ 10 августа 2009 г. и получено Свидетельство о государственной регистрации программы для ЭВМ № 2009614169 «Параллельная обработка данных в многопроцессорных системах для решения задач динамики промышленных манипуляционных роботов».

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

ЛИТЕРАТУРА

[1] Лисенков М.А. Разработка и моделирование алгоритма параллельной обработки данных в многопроцессорных системах для решения задач динамики промышленных манипуляционных роботов: Дипл. раб. — М.: МИЭМ, 2009.

[2] Внуков А.А., Гайсина Л.Ф., Селескерова Е., Сударкина Е.В. Разработка спецвычислителя для прямого преобразования координат «Интеллектуальные системы» // Труды VII Международного симпозиума (Краснодар, 26 июня — 30 июня 2006 г.) / Под ред. К.А. Пупкова. — М.: РУСАКИ, 2006. — С. 507—510.

[3] Механика промышленных роботов. Т. 1: Кинематика и динамика / Под ред. К.В. Фролова, Е.И. Воробьева. — М.: Высшая школа, 1989.

[4] Шахинпур М. Курс робототехники / Под ред. С.Л. Зинкевича. — М.: Мир, 1990.

[5] Попов Е.П. Управление роботами-манипуляторами // Техника, кибернетика. — 1974. — № 6. — С. 51—56.

[6] Схемы параллельных алгоритмов задач: www.parallel.ru

[7] Шпаковский Г.И. Организация параллельных ЭВМ и суперскалярных процессоров. — Минск, 1996.

[8] Внуков А.А., Афонин М.С. Разработка и реализация режимов платы цифрового управления промышленным роботом с электроприводом // Вестник РУДН. Серия «Инженерные исследования». — 2007. — № 4. — С. 71—86.

[9] Внуков А.А., Зозулина А.С. Разработка методики разбиения связанных между собой подзадач для параллельного выполнения кинематических преобразований манипулятора // Вестник РУДН. Серия «Инженерные исследования». — 2009. — № 4. — С. 73—85.

DEVELOPMENT OF PARALLEL ALGORITHM OF DATA PROCESSING IN MULTIPROCESSOR SYSTEMS ON EXAMPLES OF TASKS OF DYNAMICS OF INDUSTRIAL MANIPULATION ROBOT

A.A. Vnukov1, M.A. Lisenkov2

Cybernetic and mechatronics department Peoples’ Friendship University of Russia Ordjonikidze str., 3, Moscow, Russia, 117923

Department of Mathematical data processing and control Moscow state institute of electronics and mathematics

B. Trehsvjetitelsky, 3, Moscow, Russia, 109028

In this article the model of the multiprocessing system which allows to significantly speed up the implementation of modular algorithms for solving of direct and reverse tasks of dynamics of the industrial manipulation robot is considered. A method for the implementation of these algorithms on the established structure of the processor with shared memory is offered. Development of specialized multiprocessor field used to accelerate calculations. Produced simulation of the hardware-software complex for the problems of dynamics and estimations of an overall performance of parallel algorithm are received.

Key words: parallel algorithm, robots, dynamics.