Стронгин Р.Г (ред.) Высокопроизводительные параллельные вычисления на кластерных системах
Подождите немного. Документ загружается.
121
аналитический подход – основан на выводе точной формулы
зависимости выходных параметров группы, от её входов (из
геометрических соображений);
численный подход – выводится уравнение или система
нелинейных алгебраических уравнений относительно
неизвестных параметров структурной группы, которая затем
решается численно, путём минимизации невязки этой
системы.
Система проектирования рычажных механизмов “Mechanics
Studio .NET”
Разработанная автором система автоматизированного
проектирования рычажных пространственных механизмов “Mechanics
Studio .NET” [1] (веб-сайт программы http://www.mechstd.narod.ru)
решает некоторые из описанных проблем:
1.
Конструирование модели механизма с визуализацией его
структурной схемы на 4-х пространственных проекциях.
2.
Разбиение множества пар на группы нулевой подвижности.
3.
Проверка корректности структуры механизма с диагностикой
ошибок.
4.
Кинематический расчет движения всего механизма при
заданном движении входных звеньев и воспроизведение
движения.
5.
Вычисление геометрических характеристик механизма
(расстояния и углы между точками, прямыми и осями) при
промежуточных положениях с построением графиков.
Задача параметрической оптимизации рычажных механизмов
Процесс проектирования машины начинается с формулировки
задачи и определения условий её функционирования. Кроме того,
определяются число, вид, передаточные функции и характеристики
механизмов, входящих в состав машины. Выходными параметрами
механизма являются законы движения его звеньев, определяемые их
размерами (длины L
1
, L
2
,.. L
N
и направления осей пар
ψ
i
=
∠
(u
i
, ej)) –
внутренними параметрами и внешними параметрами – законами
движения входных звеньев (
ϕ
j
(t) – функции изменения углов или
перемещений от времени). Каждому из перечисленных выходных
параметров соответствует свой критерий оптимальности: точность
воспроизведения заданной траектории, наилучшее прохождение
122
препятствий, КПД, и т.п. [3]. Задача оптимизации механизма по внешним
параметрам имеет смысл лишь в том случае, если механизм имеет больше
одной степени подвижности. Синтез механизма заключается в поиске
оптимальной совокупности значений его внутренних параметров.
Чтобы обеспечить корректный, с точки зрения конструктора,
синтез механизма, при постановке задач оптимизации вводят
различные
ограничения, определяющие как область варьируемых
параметров, так и некоторые дополнительные условия. Можно
выделить следующие типы параметрических ограничений: на длины
звеньев (L
i
min
≤
L
i
≤
L
i
max
), на углы поворота осей u
i
(
ψ
l
min
≤
ψ
l
≤
ψ
l
max
) и
на функции изменения обобщённых координат входных звеньев
(
∀
t
∈
[t
0
,t
n
]
ϕ
j
min
≤
ϕ
j
(t)
≤
ϕ
j
max
, |
ϕ
’
j
(t)|
≤
ϕ
*, |
ϕ
’’
j
(t)|
≤
ϕ
**). Среди
функциональных ограничений рассматривают: ограничения на
расстояния между точками и прямыми звеньев (
∀
t
∈
[t
0
,t
n
]
ρ
i,j
min
≤
ρ
(P
i
(t), P
j
(t))
≤
ρ
i,j
max
или
ρ
i,j
min
≤
ρ
(P
i
(t), L
j
(t))
≤
ρ
i,j
max
, где P
i
–
точка звена механизма, а L
j
– прямая, соединяющая две точки звена),
на углы между звеньями (
∀
t
∈
[t
0
,t
n
]
γ
i,j
min
≤
γ
(L
i
(t), L
j
(t))
≤
γ
i,j
max
),
ограничения непересечения звеньев с заданными пространственными
препятствиями R
i
(
∀
t
∈
[t
0
,t
n
],
ρ
(R
i
, L
j
(t))
≥
δ
i
, i=1..M, j=1..N).
Функциональные ограничения также могут становиться
критериальными в случае выбора в качестве критерия
соответствующей функции. Все обозначения показаны на примере
механизма закрылок (рис. 4).
Рис. 4
Проблема оптимального синтеза механизма, решаемая
конструктором, выражается в выборе целевого критерия оптимизации
123
и варьируемых параметров. Рассмотрим некоторые типы целевых
критериев.
Критерий воспроизведения заданных скалярных функций задаёт
целевую скалярную функцию f*(t), определяющую желаемое
поведение некоторой кинематической характеристики механизма
f(t,
α
) (например, угла между звеньями или расстояния между точками
звеньев). Необходимо за счёт выбора вектора варьируемых параметров
α
*
∈
П обеспечить максимальную близость характеристики f к
целевой функции f* с учётом заданных ограничений, т.е.:
()
()
() {}()
mldtgcni
tftf
lilln
n
i
ii
I
,..,1,,,..,0:,..,
min,)(),(
1
0
2
*
=≤≤∈∀Π∈=
⎯⎯→⎯−=Φ
Π∈
=
∑
αααα
αα
α
rr
rr
r
Критерий воспроизведения целевого движения требует
прохождения некоторой точки P(t,
α
) механизма через заданный набор
положений (P
*
1
, P
*
2
, …, P
*
k
) в определённые моменты времени
(t
*
1
, t
*
2
, …, t
*
k
). Т.е. за счёт выбора вектора варьируемых параметров
α
*
∈
П необходимо минимизировать наибольшую невязку между
точками P(t
*
i
,
α
*) и P
*
i
при всех i=1..k с учётом заданных ограничений:
()
{}
(
)
() {}()
mldtgcni
PtP
lilln
ii
ki
II
,..,1,,,..,0:,..,
min,,max
1
**
..1
=≤≤∈∀Π∈=
⎯⎯→⎯−=Φ
Π∈
∈
αααα
αα
α
rr
r
r
r
r
r
Параллельное вычисление целевых критериев для механизмов
на GPGPU
Нетрудно видеть, что вычисление одного значения функции
целевого критерия Ф
I
или Ф
II
требует вычисления целой серии
положений механизма в некоторых дискретных моментах времени
i=1..k. При работе алгоритма поисковой оптимизации для решения
задачи может потребоваться большое количество значений целевого
критерия – например, s. Это приведёт к необходимости выполнить k×s
вычислений положения, что может негативно сказаться на времени
решения задачи. Очевидно, что положения механизма в
моменты
времени i, необходимые для вычисления целевого критерия, можно
считать параллельно. Кроме того, параллельные вычисления могут
применяться и в самом алгоритме оптимизации, что ускорит решение
задачи, как минимум в k раз.
На сегодняшний день существует несколько типов общедоступных
аппаратных средств для выполнения параллельных вычислений – это
124
кластерные системы, многопроцессорные или многоядерные системы
и графические карты GPU, которые недавно стали использоваться для
вычислений общего назначения (GP GPU) [5]. Кластерные и
многопроцессорные системы достаточно дороги, а графические карты,
напротив, широко распространены в настольных компьютерах и
имеют огромный потенциал для параллельных векторных вычислений.
Программирование на графических картах осуществляется с помощью
языков шейдеров, использовать
которые для общих вычислений не
всегда удобно. Реализовать вычисление положений механизмов на
графической карте планируется с помощью технологии NVidia CUDA
(http://developer.nvidia.com/cuda), позволяющей писать программы для
GPU на C++.
Литература
1. Городецкий Е.С., Система проектирования кинематики
пространственных механизмов Mechanics Studio .NET на
основе Managed DirectX – Технологии Microsoft в теории и
практике программирования: Материалы конференции.
Н. Новгород: Изд-во Нижегородского госуниверситета, 2007.
С. 48-52.
2.
Фролов К.В., Попов С.А., Мусатов А.К. и др. Теория
механизмов и машин: Учеб. для вузов / Под ред. К.В. Фролова
– М.: Высш. шк., 1987. – 496с.
3.
Теория механизмов и машин: Учеб. для вузов / К.И.
Заблонский, И.М. Белоконев, Б.М. Щекин.- Киев: Вища шк.
Головное изд-во, 1989.- 376с.
4.
Турлапов В.Е. Задача о положениях и классификация
одноконтурных структурных групп пространственных
рычажных механизмов // Электронный ж. "Прикладная
геометрия". Вып.2. №2. МАИ. 2000. C.1-22.
5.
John D. Owens, David Luebke, Naga Govindaraju. A Survey of
General-Purpose Computation on Graphics Hardware // Computer
Graphics Forum. Vol. 26 (2007). Number 1. Pp. 80–113.
125
ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ МНОГОЭКСТРЕМАЛЬНОЙ
ОПТИМИЗАЦИИ В ОБЛАСТЯХ С ВЫЧИСЛИМОЙ ГРАНИЦЕЙ
В.А. Гришагин
Нижегородский государственный университет
Рассматривается конечномерная задача оптимизации (задача
нелинейного программирования)
N
RYyyf ⊆∈→ inf,)(
, (1)
}1,0)(:{ mjygDyY
j
≤
≤
≤
∈=
, (2)
}1],,[:{ NibayRyD
iii
N
≤≤∈∈=
, (3)
т.е. задача отыскания экстремальных значений целевой
(минимизируемой) функции
)( yf
в области
Y
, задаваемой
координатными (3) и функциональными (2) ограничениями на выбор
допустимых точек (векторов)
),...,,(
21 N
yyyy
=
, где величины
ii
ba ,
,
Ni ≤≤1
, задающие границы изменения варьируемых параметров
задачи (координат вектора
y
), суть константы.
Предметом рассмотрения настоящей работы являются
многоэкстремальные задачи оптимизации, т.е. задачи, в которых
целевая функция
)( yf
в допустимой области
Y
имеет экстремум, а
ограничения
mjyg
j
≤
≤
1),(
могут иметь несколько локальных
экстремумов. Задачи данного класса обладают высокой
вычислительной трудоемкостью, обусловливаемой как
многоэкстремальностью целевой функции в сочетании с размерностью
(так называемое "проклятие размерности"), так и сложностью
допустимой области, порождаемой многоэкстремальностью
ограничений. В частности, в задачах данного класса область
Y
может
быть невыпуклой, неодносвязной и даже несвязной.
Для решения задач вида (1)-(3) широко применяются подходы,
основанные на методологии редукции сложности, когда решение
исходной задачи заменяется решением одной или нескольких более
простых задач. Например, используются схемы редукции размерности,
сводящие многомерную задачу к эквивалентной одномерной задаче
посредством отображения многомерного гиперпараллелепипеда
D
в
отрезок вещественной оси с помощью кривых Пеано, либо схемы
вложенной оптимизации, заменяющей решение многомерной задачи
126
решением семейства рекурсивно связанных одномерных подзадач
[1, 2].
Применение идеи редукции сложности к учету ограничений
связано с построением задачи без функциональных ограничений,
эквивалентной исходной условной задаче (эквивалентность
понимается в смысле совпадения – или близости – решений исходной
и редуцированной задач). Классическим подходом в этом направлении
является метод штрафных функций. К сожалению, его практическая
реализация
сопряжена с рядом трудностей, одной из которых является
необходимость подбора параметров метода (константы штрафа и
выравнивающих коэффициентов при ограничениях). Преодолеть
трудности такого рода удается в индексном методе учета ограничений
[1, 3], не содержащем настроечных параметров. Вместе с тем оба
подхода, решая редуцированную задачу в гиперпараллелепипеде
D
,
неизбежно проводят испытания (вычисления функционалов задачи) не
только в допустимой области, но и вне ее. Однако можно выделить
класс задач, в которых использование схемы вложенной оптимизации
позволяет добиться проведения испытаний только в допустимой
области. Задачи такого рода называются задачами оптимизации в
области с вычислимой границей. В настоящей работе обсуждаются
методы
распараллеливания процесса решения задач данного типа.
Предположим, что все функции-ограничения
)( yg
j
,
mj
≤
≤
1
,
являются непрерывными, а область
D
- ограниченной, что
обеспечивает компактность области
Y
.
Введем непрерывную функцию, определенную в области
D
,
такую, что
YyyG
YyyG
∉>
∈≤
,0)(
,0)(
(4)
В качестве
)( yG
можно взять, например,
)}(),...,(max{)(
1
ygygyG
m
=
(5)
или
)}(),...,(;0max{)(
1
ygygyG
m
=
(6)
Последняя функция тождественно равна нулю в области
Y
.
Введем обозначения
),,...,(
1 ii
yyu = ),,...,(
1 Nii
yyv
+
=
(7)
127
позволяющие при
11
−
≤
≤
Ni
записать вектор
y
в виде пары
),(
ii
vuy =
, и примем, что
0
vy
=
при
0
=
i
и
N
uy
=
при
Ni
=
.
Положим
)()( yGyG
N
≡
и построим семейство функций
]},,[:),(min{)(
1111
1
++++
+
∈=
iiiii
i
i
i
bayyuGuG
11
−
≤
≤
Ni
, (8)
определенных в соответствующих проекциях
}1],,[:{ ijbayRuD
jjj
i
ii
≤≤∈∈=
(9)
множества
D
из (3) на координатные оси
i
yy ,...,
1
, причем, по
определению,
DD
N
=
.
В силу непрерывности функции
)()( yGyG
N
≡
и компактности
области
D
функция
)(
1
1
−
−
N
N
uG
существует и непрерывна в
1−N
D
, что
влечет существование и непрерывность функции
)(
2
2
−
−
N
N
uG
и т.д.
определяет существование и непрерывность всех функций семейства
(8).
Построим множества
},0),(:],[{)(
1
1
1111
≤∈=Π
+
+
++++ ii
i
iiiii
yuGbayu
10
−
≤
≤
Ni
. (10)
Предположим теперь непрерывность функции
)( yf
и, положив по
определению
)()( yfyf
N
≡
, построим семейство функций
)}(:),(min{)(
111
1
iiiii
i
i
i
uyyufuf
+++
+
Π∈=
,
11
−
≤
≤
Ni
, (11)
определенных на соответствующих областях
}0)(:{ ≤∈=
i
ii
ii
uGRuY
.
Тогда имеет место основное соотношение
)(min...minmin)(min
)()(
112211
yfyf
NNN
uyuyyYy
−
Π∈Π∈Π∈∈
=
. (12)
Как следует из (11), (12), для решения задачи (1) – (3) достаточно
решить одномерную задачу
min)(
1
1
→yf
,
1
11
Ry ⊆Π∈
, (13)
}0)(:],[{
1
1
1111
≤∈=Π yGbay
. (14)
При этом каждое вычисление функции
)(
1
1
yf
в некоторой
фиксированной точке
11
Π
∈
y
представляет собой, согласно (12),
решение одномерной задачи
128
min),(
21
2
→yyf
,
1
122
)( Ryy ⊆Π∈
, (15)
}0),(:],[{)(
21
2
22212
≤∈=Π yyGbayy
. (16)
Эта задача является одномерной задачей минимизации по
2
y
, т.к.
1
y
фиксировано.
В свою очередь, каждое вычисление значения функции
),(
21
2
yyf
при фиксированных
1
y
,
2
y
требует решения одномерной задачи
min),(
32
3
→yuf
,
)(
233
uy
Π
∈
(17)
и т.д. вплоть до решения задачи
min),(),(
11
→=
−− NNNN
N
yufyuf
,
)(
1−
Π
∈
NNN
uy
(18)
при фиксированном
1−N
u
.
Окончательно решение задачи (1) – (3) сводится к решению
семейства "вложенных" одномерных подзадач
min),(
1
→
− ii
i
yuf
,
)(
1−
Π
∈
iii
uy
, (19)
где фиксированный вектор
11 −−
∈
ii
Yu
.
Решение исходной многомерной задачи (1) – (3) через решение
системы взаимосвязанных одномерных подзадач (19) называется
схемой вложенной оптимизации или многошаговой схемой редукции
размерности.
Непрерывность функции
),(
1 ii
i
yuG
−
позволяет утверждать, что
область одномерной оптимизации
)(
1−
Π
ii
u
представляет собой
систему отрезков:
U
i
q
j
j
i
j
iii
bau
1
1
],[)(
=
−
=Π
, (20)
где количество отрезков
i
q
и их границы
j
i
j
i
ba ,
,
i
qj
≤
≤
1
, зависят от
вектора
1−i
u
, т.е.
)(
1−
=
iii
uqq
,
)(
1−
=
i
j
i
j
i
uaa
,
)(
1−
=
i
j
i
j
i
ubb
. (21)
Если область
Y
такова, что для всех
Ni
≤
≤
1
удается указать
явные (аналитические) выражения для величин
i
q
,
j
i
j
i
ba ,
как функций
11 −−
∈
ii
Yu
, тогда область
Y
называется областью с вычислимой
границей. Для построения данных областей необходимо, например,
129
уметь аналитически находить корни функций
),(
1 ii
i
yuG
−
по
соответствующим координатам
i
y
.
Приведем простой пример неодносвязной области с вычислимой
границей:
,4,4:{
21
2
≤≤−∈= yyRyY
,04
2
2
2
1
≤−+ yy }01
2
2
2
1
≤−− yy
(22)
(кольцо). Для этой области
]2,2[
1
−=Π
,
⎪
⎩
⎪
⎨
⎧
−∈−−−−−−
−−∈−−−
=Π
U
U
].1,1[],4,1[]1,4[
;]2,1[]1,2[],4,4[
)(
1
2
1
2
1
2
1
2
1
1
2
1
2
1
12
yyyyy
yyy
y
Очевидный способ распараллеливания для областей вида (20) при
1>
i
q
состоит в одновременном решении
i
q
задач
,1],,[min,),(
1 i
j
i
j
iiii
i
qjbayyuf ≤≤∈→
−
(каждый процессор решает задачу на одном отрезке). К сожалению, в
этом случае происходит существенная потеря информации об
исходной задаче (19), поскольку отдельный процессор не учитывает
результаты испытаний, выполненных другими процессорами, что
приводит к значительной избыточности вычислений.
Более эффективным в этом случае является применение
характеристических параллельных алгоритмов [4], в которых
реализуется распараллеливание решающего
правила на единой
области оптимизации, что позволяет учесть при планировании поиска
результаты испытаний, полученные всеми используемыми
процессорами.
Для описания базовой схемы одномерного параллельного
алгоритма, относящегося к семейству информационно-статистических
методов [1, 2], перепишем задачу (19) в более простой стандартной
форме:
min)( →x
ϕ
,
q
Sx
∈
, (23)
U
q
j
jj
q
baS
1
],[
=
=
,
(24)
причем
.11,,1,
1
−≤≤<≤≤<
+
qjabqjba
jjjj
Тогда общая схема метода состоит в следующем.
130
Этап 1 (инициализация). Первые
q2
испытаний (вычислений
значений функции)
q
xxx
221
,,, K
проводятся в граничных точках
qjba
jj
≤≤1,,
, причем для параллельного проведения испытаний
можно использовать до
q2
процессоров. Вычисляются значения
qixz
ii
21),( ≤≤=
ϕ
. Количество проведенных испытаний
k
полагается равным
q2
, а номер
n
текущей параллельной итерации
устанавливается в единицу (
1
=
n
).
Отметим, что граничные точки области (24) разбивают отрезок
],[
1 q
ba
на
12 −q
интервалов,
1
−
q
из которых не входят в область
поиска (являются "запрещенными").
Этап 2 (начало параллельной итерации). Координаты
проведенных испытаний
k
xxx ,,,
21
K
,
)(nkk =
, перенумеровываются
нижним индексом в порядке возрастания, т.е.
q
bxxxxa
=
<
<
<
<=
−
ττ
1101
K
(25)
где
1)( −= nk
τ
, и каждой точке
i
x
множества (25) ставится в
соответствие значение
i
z
функции (23), т.е.
τ
ϕ
≤
≤
=
ixz
ii
0),(
.
Этап 3 (индексация разрешенных интервалов). Упорядоченные
координаты
i
x
из (25) задают систему интервалов
τ
≤
≤
−
ixx
ii
1),,(
1
.
Считая номером интервала
),(
1 ii
xx
−
индекс
i
его правого конца,
вводим множество
k
I
номеров "разрешенных" интервалов, а именно:
k
Ii ∈
, если существует
j
такой, что
qjbaxx
jj
ii
≤≤⊆
−
1],,[),(
1
.
Этап 4 (вычисление оценки константы Липшица). Вычисляется
величина
⎩
⎨
⎧
=
>
=
0 ,1
,0 ,
k
kk
M
MrM
m
(26)
где
1>
r
- параметр метода, а
1
1
max
−
−
∈
−
−
=
ii
ii
Ii
k
xx
zz
M
k
. (27)
Этап 5 (вычисление характеристик). Каждому интервалу
,),,(
1 kii
Iixx ∈
−
ставится в соответствие число
)(2
)(
)(
)()(
1
1
2
1
1 −
−
−
−
+−
−
−
+−=
ii
ii
ii
ii
zz
xxm
zz
xxmiR
(28)