ҒЫЛЫМ, БІЛІМ БЕРУ ЖӘНЕ ПРАКТИКАДА АҚПАРАТТЫҚ  ТЕХНОЛОГИЯЛАРДЫҢ

ПЕРСПЕКТИВЫ РАЗВИТИЯ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ В НАУКЕ,  
ОБРАЗОВАНИИ И ПРАКТИКЕ 
 
 
60
значению  индекса
j
.  Индексы 
k
j
i ,...,
,
 имеют  значения  из  набора  чисел 
1
,
2
,...,
n
..  Некоторые 
значения  из  указанного  набора  могут  отсутствовать  в  выражении  (1),  некоторые –  могут  встретиться 
более  одного  раза.  Число  множителей  в  изометрии 
i
j
k



...
 равно  числу  звеньев  (вершин) 
бильярдной траектории. 
Определенному  звену  замкнутой  бильярдной  траектории  соответствует  изометрия 
i
j
k



...
 
с  определенной  последовательностью  значений  индексов 
k
j
i ,...,
,
.  Указанное  звено  траектории 
лежит на прямой, инвариантной относительно изометрии
i
j
k



...
.  
Для 
других 
звеньев 
траектории 
соответствующая 
изометрия 
представляет 
произведение 
(композицию) 
симметрий 
изометрии 
i
j
k



...
 посредством 
циклической 
перестановки  множителей 
k
j
i



,...,
,
.  Изометрия 
k
j
i



...
,  обратная  изометрии 
i
j
k



...
, 
соответствует обходу траектории в обратном направлении.[1, с.78] 
Соответствующий  изометрии  вектор  параллельного  переноса  имеет  абсолютное  значение, 
равное длине бильярдной траектории. 
Если число симметрий в выражении (1) чётно, то есть изометрия (1) является параллельным 
переносом, и многоугольник имеет соответствующую этой изометрии бильярдную траекторию, то она 
не  единственна.  Таких  траекторий  в  многоугольнике  бесконечно  много  и  они  “параллельны”.  Такие 
траектории будем называть траекториями первого рода. 
Если  же  число  симметрий  в  выражении  (1)  нечётно,  то  есть  изометрия  (1)  является 
скользящей симметрией, то соответствующая замкнутая траектория в заданном многоугольнике (если 
она  существует)  единственна.  Такие  траектории  будем  называть  траекториями  второго  рода.  Если 
многоугольник  имеет  замкнутую  бильярдную  траекторию  второго  рода,  то  вместе  с  ней  он  имеет 
бесконечно  много  “параллельных”  ей  траекторий  первого  рода.  Эти  траектории  будем  называть 
траекториями первого рода, сопутствующими траектории второго рода. При рассмотрении траекторий 
в  виде  вписанных  многоугольников  такие  траектории  мы  называли  траекториями  с  двумя  обходами 
сторон  заданного  многоугольника.  Эти  траектории  соответствуют  квадрату  изометрии 
i
j
k



...
.      
[2, с.25] 
Обоснование  утверждения  о  существовании  таких  траекторий  проводится  аналогично 
тому,  как  это  делалось  в  случае  траекторий  в  виде  вписанных  многоугольников  в 
многоугольниках  с  нечётным  числом  сторон.  Опишем  подробнее  появление  траекторий  первого 
рода, сопутствующих траектории второго рода.  
Пусть 
k
 звеньев  траектории  второго  рода  лежат  на  прямых 
k
L
L
L
,...,
,
2
1
.  Прямые 


k
i
L
i
,...,
2
,
1

 удовлетворяют соотношениям типа  
i
i
i
L
L
S

, 
Пусть  теперь 
i
l
 –  прямая,  параллельная 
i
L
,  а 
i
l
–  прямая,  симметричная  ей  относительно 
прямой
i
L
. Так  как 
i
S
 есть преобразование  скользящей симметрии  относительно прямой
i
L
,  то связь 
между 
i
l
 и 
i
l
 выразится равенством: 
i
i
i
l
S
l


.  
Отсюда, очевидно, имеем также соответствия: 
i
i
i
l
l
S

2
, 
i
i
i
l
l
S



2
 
Прямые 
k
k
l
l
l
l
l
l



,...,
,
,
,...,
,
2
1
2
1
,  связанные  симметриями  относительно  сторон  исходного 
многоугольника,  образуют  бильярдные  траектории  первого  рода  с  числом  звеньев,  равным 
k
2
. 
Выбирая  прямые 
i
l
 и 
i
l
 на  различном  (но  возможном)  расстоянии  от  прямой 
i
L
,  можно  получить 
бесчисленное множество “параллельных” траекторий первого рода. Ясно, что длина такой траектории 
в два раза больше длины исходной траектории второго рода. 
 
Разделение замкнутых бильярдных траекторий на два рода в зависимости от чётности или не-
чётности числа симметрий, образующих соответствующую изометрию, носит общий характер. Любой 
замкнутой бильярдной траектории в многоугольнике (в зависимости от чётности или нечётности числа 
её  вершин)  соответствует  одно  из  двух  преобразований  –  либо  параллельный  перенос,  либо 
скользящая  симметрия.  Подчеркнём,  что  множество  траекторий,  описываемых  определённой 
изометрией  I  рода  (преобразованием  параллельного  переноса)  имеет  мощность  континуума,  в  то 
время как всякая траектория, описываемая изометрией II рода (скользящей симметрией) в заданном 

ҒЫЛЫМ, БІЛІМ БЕРУ ЖӘНЕ ПРАКТИКАДА АҚПАРАТТЫҚ  ТЕХНОЛОГИЯЛАРДЫҢ  
ДАМУ ЖОЛДАРЫ 
 
 
61
многоугольнике единственна. 
Изложенное  в  этом  разделе  поясним  на  одном  примере  замкнутой  траектории  в 
многоугольнике. 
Рассмотрим замкнутую бильярдную траекторию 
5
2
1
...P
P
P
 в пятиугольнике 
5
2
1
...A
A
A
 (рис. 
1a).  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Замкнутую ломаную типа 
5
2
1
...P
P
P
 будем называть многоугольником с самопересечением. 
Как имеющая нечётное число вершин траектория 
5
2
1
...P
P
P
 является траекторией второго рода. 
Введем 
для 
симметрий 
относительно 
прямых 
1
5
3
2
2
1
,...
,
A
A
A
A
A
A
 соответственно 
обозначения
5
2
1
,...,
,



.  Прямые,  на  которых  лежат  звенья  траектории 
5
4
2
1
1
5
,...,
,
P
P
P
P
P
P
, 
обозначим  соответственно  через 
5
2
1
,...,
,
L
L
L
.  Легко  проверить,  что  прямая 
1
L
 инвариантна 
относительно  изометрии 
1
2
3
5
3
1






S
: 
1
1
1
2
3
5
3
L
L 





.  Для  прямой 
3
L
,  к  примеру, 
можно записать: 
3
3
3
5
3
1
2
L
L 





. 
Скользящую симметрию 
1
S
 можно представить в явном виде: 
1
1
1
a
t
s
S


, 
где 
1
s
–  симметрия  относительно  прямой 
1
,
1
a
t
L

–  перенос  на  вектор 
1
a

,  параллельный  прямой
1
L
, 
длина вектора 
1
a

 равна длине траектории
5
2
1
...P
P
P
. 
Траектории 
5
2
1
...P
P
P
 сопутствует бесчисленное множество “параллельных” ей траекторий 
первого рода c 10 звеньями. На рис. 1b изображена одна из них 



5
2
1
5
2
1
...
...
R
R
R
R
R
R
. Её звено 
1
5
R
R

 
лежит на прямой 
1
l
, параллельной прямой 
1
L
. Прямая 
1
l
 инвариантна относительно квадрата 
изометрии 
:
1
2
3
5
3
1






S
 
1
2
1
2
1
2
3
5
3
1
1
)
(
l
t
l
l
a








, 
где 
1
2 a
t

– преобразование, являющееся параллельным переносом на вектор 
1
2a

. Аналогичную запись 
можно сделать и для прямой 
1
l
, на которой лежит звено траектории 
1
5
R
R 
. Параллельные прямые 
1
l
 и 
1
l
 расположены симметричным образом относительно прямой 
1
L
. Более точно, они связаны 
соотношением 
1
2
3
5
3
1







l
1
l
, 
в котором 
1
2
3
5
3





 есть скользящая симметрия с осью 
1
L
. Длина траектории 
5
2
1
...R
R
R

 в два раза 
больше длины траектории 
5
2
1
...P
P
P
. 
 
 
б 
а 
Рис. 1 
5
R
 
4
R
 
3
R
 
R
5
 
R
4
 
R
3
 
2
R
 
R
2
 
1
R  
R
1
 
А
5
 
А
4
 
А
3
 
А
2
 
А
!
 
Р
5
 
Р
4
 
Р
3
 
Р
2
 
Р
1
 
А
5
 
А
4
 
А
3
 
А
2
 
А
1
 

ПЕРСПЕКТИВЫ РАЗВИТИЯ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ В НАУКЕ,  
ОБРАЗОВАНИИ И ПРАКТИКЕ 
 
 
62
Литература: 
1.  Фройденталь Г. Математика как педагогическая задача. Ч. I. Сокр. пер. с нем. Халамайзера А. 
Я. Под ред. Виленкина Н. Я.  – М.: Просвещение, 1982. 
2.  Кокстер Г.С. М. Введение в геометрию. Пер. с англ. Катка А. Б. и Каток С. Б. Под. ред. 
Розенфельда Б. А. и Яглома И. М. – М.: Наука, 1966. 
 
 
УДК 004.021 
 
ОПТИМИЗАЦИЯ ПРОГРАММ С ИСПОЛЬЗОВАНИЕМ ТЕХНОЛОГИИ CUDA. 
 
Кудубаева  С.А.  -  доцент,  к.т.н,  зав.  кафедры  информатики  и  математики,  Костанайский 
государственный университет им. А.Байтурсынова 
Шиманский Н.Д. – магистрант, Костанайский государственный университет им. А.Байтур-
сынова 
 
У  GPU  есть  ряд  особенностей,  используя которые  можно  многократно  увеличить  произво-
дительность  программы.  Используя  все  тонкости  технологии  GPU  можно  получить  действи-
тельно эффективные CUDA-программы. 
Ключевые слова: CPU, GPU, хост, алгоритмы, ядра CUDA. 
 
CUDA  (сокр.  от  англ.  Compute  Unified  Device  Architecture,  дословно  –  унифицированная 
вычислительная  архитектура  устройств)  –  архитектура  (совокупность  программных  и  аппаратных 
средств),  позволяющая  производить  на  GPU  вычисления  общего  назначения,  при  этом  GPU 
фактически выступает в роли мощного сопроцессора [1, с.2-3].  
Программа  на  CUDA  задействует  как  CPU,  так  и  GPU.  При  этом  обычный  (последовательный, 
то  есть  непараллельный)  код  выполняется  на  CPU,  а  для  массивно-параллельных  вычислений 
соответствующий код выполняется на GPU как набор одновременно выполняющихся нитей (потоков, 
threads). 
Таким  образом,  GPU  рассматривается  как  специализированное  вычислительное  устройство, 
которое: 
□ является сопроцессором к CPU; 
□ обладает собственной памятью; 
□ обладает возможностью параллельного выполнения огромного количества отдельных нитей. 
При  этом  очень  важно  понимать,  что  между  нитями  на  CPU  и  нитями  на  GPU  есть 
принципиальные различия [2, с.17]: 
□ нити  на  GPU  обладают  крайне  небольшой  стоимостью  создания,  управления  и  уничтожения 
(контекст нити минимален, все регистры распределены заранее); 
□ для эффективной загрузки GPU необходимо использовать много тысяч отдельных нитей, в то 
время как для CPU обычно достаточно 10-20 нитей. 
За счет того, что программы в CUDA пишутся фактически на обычном языке С (на самом деле 
для  частей,  выполняющихся  на  CPU,  можно  использовать  язык  C++),  в  который  добавлено 
небольшое  число  новых  конструкций  (спецификаторы  типа,  встроенные  переменные  и  типы, 
директива  запуска  ядра),  написание  программ  с  использованием  технологии  CUDA  оказывается 
заметно проще, чем при использовании традиционного GPGPU (то есть использующего графические 
API  для  доступа  GPU).  Кроме  того,  в  распоряжении  программиста  оказывается  гораздо  больше 
контроля и возможностей по работе с GPU [2, с.18]. 
Для  начала  определим  задачу,  которую  нам  необходимо  решить.  Найти  значение  следующей 
функции 
 
 
 
Решение данного примера сводится к выполнению следующих операций: 
□ выделение памяти на GPU для массивов A, B, C; 
□ копирование данные из памяти CPU в выделенную память GPU; 
□ осуществление запуска ядра(основной функции GPU); 
□ копирование результатов вычислений обратно в память CPU; 
□ освобождение выделенной памяти GPU. 
Функция  ядра  фактически  для  каждого  допустимого  индекса  входных  массивов  запускает  от-
дельную  нить  для  осуществления  нужных  вычислений.  Все  эти  нити  выполняются  параллельно,  и 

ҒЫЛЫМ, БІЛІМ БЕРУ ЖӘНЕ ПРАКТИКАДА АҚПАРАТТЫҚ  ТЕХНОЛОГИЯЛАРДЫҢ  
ДАМУ ЖОЛДАРЫ 
 
 
63
каждая нить может получить информацию о себе через встроенные переменные, показано на рисунке 
1. 
 
 
 
 
 
 
 
 
 
 
 
 
 
Рисунок 1. Разделение ядра на блоки и нити 
 
Для того чтобы можно было сравнить результаты вычислений на CPU и GPU приведем код для 
вычисления функции на CPU. 
// CPU ------------------------------------------------------------------- 
//заполнение массивов А и В 
for ( i=0; i < size * nStream; i++ ) 
{ 
  hA[i] = cosf ( (float)i*3.0f );  
  hB[i] = sinf ( (float)i - 2.0f ) ;  
  hC[i] = 0.0f; 
}  
start = clock (); 
for(i=0;i{ 
  ab = hA[i] * hB[i]; sum=0.f; 
  for ( j = ; j <= 100; j++) sum = sum + sinf( j + ab ); 
  hCC[i] = sum; 
} 
stop = clock ();  
 
Код программы на CUDA: 
unsigned int mem_size=sizeof(float)*size; 
hA = (float*) malloc (mem_size); 
hB = (float*) malloc (mem_size); 
hC = (float*) malloc (mem_size); 
for(i=0;i{ 
  hA[i]=1.0f/((i+1.0f)*(i+1.0f)); hB[i]=expf(1.0f/(i+1.0f)); hC[i]=0.0f; 
} 
cudaMalloc((void**) &dA, mem_size); 
cudaMalloc((void**) &dB, mem_size); 
cudaMalloc((void**) &dC, mem_size); 
if ((size % N_thread)==0) 
{ 
  N_blocks=size/N_thread; 
} 
else 
{ 
  N_blocks=(int)(size/N_thread)+1; 
} 
dim3 blocks(N_blocks,1); 
//GPU -------------------------------------------------------------------- 
start = clock(); 
cudaMemcpy(dA, hA, mem_size,cudaMemcpyHostToDevice); 
cudaMemcpy(dB, hB, mem_size,cudaMemcpyHostToDevice); 
Исходные данные
 
Блок 
           
Потоки 
Блок 
           
Потоки 
Блок 
           
Потоки 
Ядро (Kernel) 

ПЕРСПЕКТИВЫ РАЗВИТИЯ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ В НАУКЕ,  

жүктеу/скачать 39,72 Mb.

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