237
Распараллеливание вычислений в задаче подготовки кадра
Большинство выпускаемых современных процессоров оснащено двумя или более ядрами. Дальнейшее
развитие ориентировано именно на увеличение количества ядер, чем на наращивание мощности отдельного ядра
[5].
Для подзадачи подготовки кадра в задаче отображения трехмерной анимации дактильной азбуки жестов
был рассмотрим алгоритм распараллеливания вычислений, поскольку по своей сути подготовка одного кадра
является
функцией от модели руки и параметров модели, т.е. не зависит от результата вычислений других
кадров и от момента вычисления. Такой подход имеет место, когда вычисление нового кадра является
ресурсоемкой задачей, например,
проведение скининга на процессоре. Для этого был разработан алгоритм,
состоящий из 2
+ n
потоков, где
n
количество ядер процессора: основной поток, поток анимации,
n
потоков
вычисления кадров. Используется тот факт, что вычисление различных кадров является равносильной задачей в
терминах процессорного времени независимо от параметров модели. Поэтому вычисление
k
кадров можно
разбить на
n
потоков максимально равномерно таким способом: каждый -й поток обрабатывает кадры с тем
номером, остаток от деления которого на
n
равен .
Основной поток (поток интерфейса) инициирует создание
n
потоков вычислений и потока анимации. Поток
анимации показывает с заданным промежутком подготовленные кадры, освобождает память после их показа.
Поскольку на момент начала анимации должна быть уверенность, что каждый кадр будет готов перед его
показом, то поток информации запускается приостановленным, а его запуск делегируется на один из потоков
вычисления кадров, в частности, на поток с индексом 0. В дальнейшем, этот поток будем называть
ведущим.
Каждый поток вычисления кадров в начале получает остаток от деления и начинает цикл вычислений.
Также проводится обновление счетчика вычисленных кадров.
Ведущий поток также фиксирует момент времени начала вычислений. После того как было вычислено 5
кадров, он аппроксимирует момент времени окончания вычислений всех кадров. Поскольку длительность
анимации известна изначально, то возможно определить, будет ли подготовка кадров выполнена вовремя для
непрерывного отображения анимации. Когда аппроксимированного времени до конца завершения вычислений
становится меньше продолжительности анимации, ведущий поток запускает поток анимации и прекращает
прогнозирование завершения.
Задача распределения потоков на каждое ядро выполняется операционной системой. Но часто бывают
ситуации, когда ядра заняты посторонними процессами. Это привело бы к тому, что потоки предобработки
получили бы различные кванты процессорного времени, а как следствие, кадры вычислялись неравномерно.
Например, возможна была бы такая ситуация (в примере используется двухъядерный процессор):
№ кадра
0
1
2
3
4
5
6
7
Состояние
+
+
+
-
+
-
+
-
Где состояние «+» означает, что кадр подготовлен, «-» - не подготовлен.
Для решения данной
проблемы был применен подход с использованием семафоров [6,7]: каждый поток
проассоциирован одним семафором, который инициализирован единицей. В начале вычисления кадра поток
уменьшает свой семафор на единицу, после завершения кадра он увеличивает семафор следующего потока на
единицу (последний поток увеличивает семафор нулевого потока). Таким образом, вычисление кадров одного
потока не опережает остальные более чем на единицу.
По особенностям своего назначения, семафор не может принимать значения меньше нуля. По своему
назначению, значение семафора не может изменяться меньше нуля. Семафор является объектом ядра
операционной системы, который отвечает за совместный доступ нескольких потоков к общим ресурсам. У этого
объекта две операции - увеличить (на единицу), уменьшить (на единицу). Если значение семафора - ноль, а
поток выполняет операцию "уменьшить", выполнение его приостанавливается операционной системой, а значит,
становится доступным дополнительное процессорное время. Операционная система ведет учет всех потоков,
которые были приостановлены вследствие попытки уменьшить семафор. Когда некоторый другой поток делает
операцию "увеличить", то другой поток из списка приостановленных продолжает выполнение.
На практике, такой подход означает следующее: каждый поток анимации в начале работы алгоритма
"может" вычислить 1 кадр, за что отвечает значение его семафора. После вычисления своего кадра, он позволит
вычисления другому потоку и будет приостановленным, пока поток не увеличит соответствующий семафор.
Таким образом, ядра процессора максимально загружены, а кадры вычисляются постепенно. Такой может быть
один из
способов распознавания жестов.
Список литературы
1. Кульбіда С. В. Українська дактилологія. К.: Педагогічна думка, 2007. — 255 c. — ISBN 978-966-644-076-4.
2. Воскресенский А. Л., Халагин Г. К. От звучащей речи к жестовой // Речевые технологии. — 2009. — № 1. — С.
99—106.
3. Gesture-Based Communication in Human-Computer Interaction. 5th In ternational Workshop, GW 2003, Genova,
Italy, April 15-17, 2003.
4. Воскресенский А. Л., Ильин С.Н., Zelezny «О распознавании жестов языка глухих», 2010.
5.Ю. Крак, Ю. Кривонос, Б. Троценко. Исследование информационных процессов для эффективного
воспроизведения дактильного жестового языка //InformationModelsofKnowledge// ITHEA. KIEV – SOFIA. 2010 С.
262-271
238
УДК 517.95
О ПРЕДЕЛЬНОМ ЗНАЧЕНИИ ПАРАМЕТРА ДЛЯ СУЩЕСТВОВАНИЯ
СТАЦИОНАРНЫХ РЕШЕНИЙ СИСТЕМЫ СО МНОГИМИ СТЕПЕНЯМИ СВОБОДЫ С МЕДЛЕННО
МЕНЯЮЩИМСЯ КОЭФФИЦИЕНТАМИ,
ПО ЧЛЕНАМ ВЫСШИХ ПОРЯДКОВ
Махатова В.Е., Камматов К.К., Батырханов А.Ғ., Қожабай Ж.Қ.
Атырауский государственный университет им.Х.Досмухамедова
г.Атырау
В статье «Необходимые и достаточные условия существования колебаний квазилинейных систем
с медленно меняющимися коэффициентами» рассматривалась система с
n
- степенями свободы, вида
...
)
,
,
(
)
,
(
...,
)
,
,
(
)
,
(
)
(
)
(
)
(
,
)
(
s
s
m
si
s
s
m
so
s
s
s
m
i
s
s
m
so
s
y
x
Y
y
x
Y
y
y
x
X
y
x
X
x
i
o
i
o
(1)
Здесь
,...)
2
,
1
,
0
(
,
)
(
)
(
i
Y
X
i
i
m
si
m
si
- многочлены сколь угодно высокой, но конечной степени, а
,...)
2
,
1
,
0
(
,
)
(
)
(
i
Y
X
o
o
m
so
m
so
- однородные многочлены, не содержащие линейных членов относительно
s
s
y
x ,
,
причем
o
o
o
o
o
o
m
o
p
m
o
p
p
s
p
m
s
sp
s
s
m
so
p
s
p
m
s
sp
s
s
m
so
y
x
B
y
x
Y
y
x
A
y
x
X
,
)
,
(
,
)
,
(
)
(
i
o
i
n
i
i
n
i
i
n
i
i
n
i
i
n
i
i
i
m
m
e
e
k
k
e
n
e
k
n
k
e
k
si
s
s
m
si
y
y
x
x
A
y
x
X
1
...
...
1
1
)
,...,
(
)
(
)
(
)
(
1
)
(
)
(
1
)
(
)
(
1
)
(
)
(
1
)
(
)
(
1
,
...
...
)
(
)
,
,
(
i
o
i
n
i
i
i
n
i
i
i
n
i
i
n
i
n
i
i
m
m
e
e
k
k
e
n
e
i
k
n
e
k
si
s
s
m
si
y
y
x
B
y
x
Y
1
...
...
)
,...,
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
1
)
(
)
(
)
(
1
,
...
)
(
)
,
,
(
Правые части системы (1) обращаются в нуль только при
0
s
s
y
x
. В связи с этим каждое
слагаемое
,...)
3
,
2
,
1
(
,
i
Y
X
si
si
должно содержать
s
x
или
s
y
, причем в степени не ниже
1
o
m
, а
t
-
медленное время, многочлены
)
,
,
(
),
,
,
(
s
s
si
s
s
si
y
x
Y
y
x
X
с коэффицентами, являющимися ограниченными по
с ограниченными по
первыми производными, причем указанные
коэффициенты и производные
достигают своих точных верхних и нижних границ в интервале
,
0
.
Для системы (1) в [4] при некоторых ограничениях получены необходимые и достаточные
условия существования решений и
способы их построений.
В связи с этим данная работа является естественным продолжением статьи [4], посвященной
этому же вопросу.
Таким образом, как следует из доказанной теоремы в [4], для существования стационарного
решения необходимо, чтобы
k
.
Определим то предельное значение
, равное
, при котором
n
менее которого
стациональные решения системы (1) продолжают существовать независимо от членов
)
1
(
-го и выше
порядка, если эта система имеет их по
-тому порядку и при достаточно малых значениях
.
1
2
)
(
1
,
1
1
1
0
)
,
,
,
(
)
)
(
(
)
(
)
(
)
(
)
(
k
s
s
i
s
s
s
i
sk
sk
r
k
s
k
s
S
k
Q
A
, (2)
1
)
(
1
,
1
2
2
0
)
,
,
,
(
)
)
(
(
)
(
)
(
)
(
k
s
sk
i
s
s
s
i
sk
sk
s
r
k
s
k
s
S
k
Q
A
(3)
Для определения такого значения
, при котором эти условия еще выполняются, заменим
выражения
1
,
s
Q
в (2) наибольшим, а в (3) наименьшим значениями, которые они могут принимать при
).
,...,
3
,
2
,
1
(
,
2
0
n
s
Q
s
Затем, заменяя неравенства (2) и (3) соответствующими равенствами,
получим: