Р. Г. Стронгина. Ниж- ний Новгород: Изд-во Нижегородского университета, 2002, 217 с

 
71 
процессорами  определяет  коэффициенты  неравенства,  при  которых 
выполняется (1).  
Теорема 4 Существует алгоритм A
4
, который по произвольному 
объекту c 
∈ HALFSPACE
k
2
, используя не более 6 log (k
−1)+4 обраще-
ний  к  оракулу  и  O(log k)  арифметических  операций,  на  машине 
UPRAM с 
√ k процессорами определяет коэффициенты неравенства, 
при которых выполняется (1).  
Результаты,  относящиеся  к  идентификации  объектов  из  класса 
HALFSPACE
k
n
 для n > 2, см. в [5, 6, 7].  
Обозначим  через  m
−HALFSPACE
k
2
  множество  объектов  c 
⊆  E
k
2
, 
для каждого из которых найдутся действительные числа a
10
, a
11
, a
12
, ..., 
a
m0
, a
m1
, a
m2
, такие, что  
 
 
c = {x 
∈ E
k
n
: a
11
x
1
 + a
12
 x
2
 
≤ a
10
, ...,  a
m1
 x
1
 + a
m2
 x
2
 
≤ a
m0
}. (2) 
 
Теорема 5 [8] Существует алгоритм A
5
, который по произволь-
ному объекту c 
∈ m
−HALFSPACE
k
2
 и произвольной тройке неколлине-
арных точек из c, используя не более (10m + 1) log (k
−1) + 34 вопросов 
и O(log k) арифметических операций, на машине UPRAM с 1 процес-
сором определяет коэффициенты a
10
, a
11
, a
12
, ..., a
m0
, a
m1
, a
m2
, при ко-
торых выполняется равенство (2).  
Теорема 6 Существует алгоритм A
6
, который по произвольному 
объекту c 
∈ m
−HALFSPACE
k
2
 и произвольной тройке неколлинеарных 
точек из c, используя не более (11m+1) log (k
−1)+12 вопросов и O(log k) 
арифметических операций, на машине UPRAM с m процессорами оп-
ределяет коэффициенты a
10
, a
11
, a
12
, ..., a
m0
, a
m1
, a
m2
, при которых вы-
полняется равенство (2).  
Обозначим через BOX
k
n
 множество объектов c 
⊆ E
k
n
, для каждого 
из которых найдутся числа a
1
, ..., a
n
 и b
1
, ... , b
n
, такие, что 
 
 
c = {x 
∈ E
k
n
: a
1
 
≤ x
1
 
≤ b
1
, ... ,  a
n
 
≤ x
n
 
≤ b
n
 }. 
(3) 
 
Теорема 7 Существует алгоритм A
7
, который по произвольному 
объекту  c 
∈ BOX
k
n
  и  произвольной  точке  x 
∈  c,  используя  не  более 
2n log (k
−1) вопросов и O(n log k) арифметических операций, на маши-
не  UPRAM  с 1 процессором  находит  числа  a
1
, ..., a
n
  и  b
1
, ... , b
n
,  при 
которых выполняется равенство (3).  
Теорема 8 Существует алгоритм A
8
, который по произвольному 
объекту  c 
∈ BOX
k
n
  и  произвольной  точке  x 
∈  c,  используя  не  более 

72 
log (k
−1) вопросов и O(n log k) арифметических операций, на машине 
UPRAM с 2n процессорами находит числа a
1
, ..., a
n
 и b
1
, ... , b
n
, при ко-
торых выполняется равенство (3).  
Обозначим через BALL
k
n
 множество объектов c 
⊆ E
k
n
, для каждого 
из которых найдутся точка y 
∈ E
k
n
 и целое число r, такие, что  
 
}.
)
(
:
{
r
y
x
E
x 
c
n
j
j
j
n
k
≤
−
∈
=
∑
=
1
2
. (3) 
Теорема 9 [8]  Существует  алгоритм  A
9
,  который  по  произволь-
ному  объекту  c 
∈ BALL
k
n
  и  произвольной  точке  x 
∈  c,  используя 
O(n log k) вопросов, находит y и r, при которых выполняется равенст-
во (4).  
Часть результатов для случая n = 2 сведем в таблицу:  
 
Класс 
Число про-
цессоров 
Сложность алгоритма 
1 
6 log(k
−1) + 4 
2 
3 log(k
−1) + 2 
4 
2 log(k
−1) + 1 
√ k log(k−1) + 4 
k 
3 
HALFPLANE
k
2
 
k
2
 
1 
1 
(10m + 1) log (k
−1)+34 
m
−HALFPLANE
k
2
 
m 
11 log(k
−1)+12 
1 
4 log(k
−1) − 4 
2 
2 log(k
−1) − 2 
4 
log(k
−1) − 1 
BOX
k
2
 
k 
2 
BALL
k
n
 1 
O(log 
k) 
Литература 
1.  Шевченко В. Н.  Качественные  вопросы  целочисленного  програм-
мирования. М.: Физматлит, 1995. 192 с.  

 
73 
2.  Bshouty N.H., Cleve R. On the exact learning of formulas in parallel // 
Proc. of the 33rd Symposium on the Foundations of Comp. Sci. IEEE 
Computer Society Press, Los Alamitos, CA, 1992. P. 513–522. 
3.  Золотых Н. Ю.  Пороговые  функции,  зависящие  от  двух  перемен-
ных: сложность расшифровки и мощность разрешающего множе-
ства // Материалы четвертой молодежной научной школы по дис-
кретной  математике  и  ее  приложениям.  М.:  Изд-во  механико-
математического факультета МГУ, 2000. С. 48–54.  
4.  Веселов С. И.  Расшифровка  одного  класса  функций // Материалы 
XI  Межгосударственной  школы-семинара ``Синтез  и  сложность 
управляющих систем''. Часть I. М.: Изд-во центра прикладных ис-
следований при механико-математическом факультета МГУ, 2001. 
С. 39–40.  
5.  Шевченко В.Н., Золотых Н.Ю. О сложности расшифровки порого-
вых  функций  k-значной  логики // Доклады  Академии  наук. 1998. 
Т. 362, 5. C. 606–608.  
6.  Золотых  Н.Ю.,  Шевченко  В.Н.  О  нижней  оценке  сложности  рас-
шифровки пороговых функций k-значной логики // Журнал вычис-
лительной  математики  и  математической  физики. 1999. Т. 39,  2. 
С. 346–352.  
7.  Shevchenko V.N., Zolotykh N.Y. Lower bounds for the complexity of 
learning half-spaces with membership queries // Proc. of the 9th Inter-
national Conference on Algorithmic Learning Theory – ALT'98. V. 
1501 Lecture Notes in Artificial Intelligence, Springer-Verlag, 1998, P. 
61–71.  
8.  Веселов С. И.,  Золотых Н. Ю.  Идентификация  геометрических 
образов  на  целочисленной  решетке // Материалы 7-ой  междуна-
родной  конференции  по  дискретной  математике  и  ее  приложени-
ям. В печати. 

74 
ОРГАНИЗАЦИЯ ВЫСОКОПРОИЗВОДИТЕЛЬНЫХ ВЫЧИСЛЕНИЙ  
НА КЛАСТЕРЕ PARC УДМУРТСКОГО ГОСУНИВЕРСИТЕТА 
Г.Г. Исламов, С.А. Мельчуков, 
 М.А. Клочков, О.В. Бабич, Д.А. Сивков 
Удмуртский государственный университет, г.Ижевск 
С момента появления в 1971 году первого микропроцессора i4004 
фирмы Intel и  создания  на  его  основе  микропроцессорных  вычисли-
тельных устройств развитие вычислительной техники сделало гигант-
ский скачок. Основной прирост вычислительной мощности компьюте-
ров  достигался  как  за  счет  улучшения  технологических  норм  произ-
водства  (и,  как  следствие,  тактовых  частот),  так  и  за  счет  улучшения 
архитектурной  организации  микропроцессоров  и  периферийных  уст-
ройств.  При  этом,  начиная с начальных тактовых частот порядка 750 
КГц  микропроцессора i4004, микропроцессоры  достигли  тактовых 
частот в 1700–2000 МГц. Однако, дальнейшее увеличение производи-
тельности  за  счет  повышения  тактовых  частот  становится  несколько 
затруднительным, так как практически достигнуты минимальные раз-
меры  транзисторов  на  кристалле  и  появились  другие  сдерживающие 
факторы.  Поэтому  современная  вычислительная  техника  все  более 
отходит от традиционной архитектуры и создаются новые направления 
повышения производительности вычислительных систем. 
Достигнутый уровень технологии производства надежных высоко-
скоростных шин и мощных процессоров, сетевого оборудования и раз-
витое  программное обеспечение распределенных и параллельных вы-
числений  позволяют  создавать  кластеры  высокопроизводительных 
компьютеров,  способные обеспечить эффективные расчеты широкого 
класса научных и технических задач, а также планомерную подготовку 
специалистов  в  области  высокопроизводительных  вычислений.  В  но-
ябре 2000 г.  по  инициативе  ректора  Удмуртского  госуниверситета 
профессора В. А. Журавлева был создан кластер PARC, состоящий из 
пяти  двухпроцессорных  компьютеров.  Общая  характеристика  этому 
кластеру  дана  в  учебно-методическом  пособии [1], описывающем ос-
новные особенности и правила работы на кластере PARC. 
На  примере  модельной  задачи  управления  температурой  тонкого 
стержня мы решаем учебно-методические вопросы организации высо-
копроизводительных вычислений на кластере PARC. 

 
75 
Рассмотрим в течение времени T процесс изменения температуры 
u(x,t)  в  тонком  стержне  длины  l  с  коэффициентом  теплопроводности 
k(x) при воздействии на него тепловыми источниками и стоками плот-
ности  F(x,t)=b(x)v(t)  в  точке  x
∈ [0,l]  в  момент  t∈[0,T].  Известно,  что 
температура u(x,t) должна удовлетворять дифференциальному уравне-
нию теплопроводности 
 
)
(
)
(
)
,
(
)
(
)
,
(
)
(
t
v
x
b
x
t
x
u
x
k
x
t
t
x
u
x
c
+






∂
∂
∂
∂
=
∂
∂
ρ
, 
)
,
(
)
,
(
)
,
(
T
l
t
x
0
0
×
∈
. (1) 
Здесь  c – удельная  теплоемкость, 
ρ(x) – функция  плотности  рас-
пределения массы стержня. 
С  помощью  двух  функций 
α(x,t) и β(x,t) (α (x,t) ≤ β (x,t)) зададим 
диапазон изменения температуры 
 
 
α(x,t) ≤ u(x,t)  ≤ β(x,t). (2) 
 
Задачу  управления  поставим  следующим  образом.  Требуется  по-
строить 
такое 
кусочно-постоянное 
управление 
v=v(t) 
(
)
]
[
,T
,  t
|v(t)|
0
1
∈
≤
,  при  котором  уравнение (1) имеет  гладкое  реше-
ние u(x,t), удовлетворяющее граничным условиям 
 
)
(
)
,
(
t
t
u
µ
=
0
,  
)
(
)
,
(
t
v
t
l
u
=
 
и дополнительному ограничению (2) в каждый фиксированный момент 
времени t = t
i
 (0 
≤ t
1
 < t
2
 < ... <t
m
 
≤ T). 
По  обычной  схеме  дискретизации  пространственной  переменной 
получается конечномерная управляемая система: 
)
(
)
(
)
,
(
)
,
(
)
,
(
)
,
(
)
,
(
)
(
t
v
x
b
h
t
u
t
x
u
a
h
t
x
u
t
x
u
a
h
t
t
x
u
x
c
1
1
1
1
2
2
1
1
0
1
+






−
−
−
=
∂
∂
ρ
, 
,
,....
),
(
)
(
)
,
(
)
,
(
)
,
(
)
,
(
)
,
(
)
(
2
2
1
1
1
1
−
=
+
+






−
−
−
=
∂
∂
ρ
−
+
+
N
i
t
v
x
b
h
t
x
u
t
x
u
a
h
t
x
u
t
x
u
a
h
t
t
x
u
x
c
i
i
i
i
i
i
i
i
i
 
),
(
)
(
)
,
(
)
,
(
)
,
(
)
,
(
)
,
(
)
(
t
v
x
b
h
t
x
u
t
x
u
a
h
t
x
u
t
l
u
a
h
t
t
x
u
x
c
N
N
N
N
N
N
N
N
1
2
1
1
1
1
1
1
−
−
−
−
−
−
−
+






−
−
−
=
∂
∂
ρ
 
граничные условия для которой имеют следующий вид: 
 
α (x
i
 , t
j
)  
≤ u(x
i
 , t
j
)  
≤ β (x
i
 , t
j
),   j = 1,…m,  i = 1,…N–1 

76 
Для описания свойств требуемого управления данной конечномер-
ной  задачи  сформулирован  принцип  максимума,  позволяющий  опре-
делить точки переключения. 
В  работе  получен  конструктивный  параллельный  алгоритм  по-
строения  оптимального  кусочно-постоянного  управления,  опираю-
щийся  на  описанный  ранее  принцип  максимума.  Вводятся  основные 
понятия,  необходимые  при  описании  и  построении  параллельных  ал-
горитмов,  рассматривается  решение  данной  модельной  задачи  с  при-
влечением различных вычислительных средств, используемых на кла-
стере PARC: сетевые возможности ОС Linux, средства параллельного 
программирования,  использующие  механизмы  разделяемой (Pthreads) 
и распределенной (PVM, MPI) памяти. 
Литература 
1. PARC – кластер  высокопроизводительных  компьютеров  /Исламов 
Г.Г.,  Мельчуков  С.А.,  Клочков  М.А.,  Бабич  О.В.,  Сивков  Д.А. 
Учебно-методическое пособие. Ижевск: УдГУ, 2001. 66 с. 

жүктеу/скачать 1,64 Mb.

Достарыңызбен бөлісу: