«Вітчизняна наука: сучасний стан, актуальні проблеми та перспективи розвитку»

296 
«Проблемы и перспективы развития науки в начале третьего тысячелетия в странах СНГ»
 
 
 
 
Гибридті  бұлт  (Hybrid  cloud).
 
Бірегей  нысандары  бар,  алайда  бір
-
бірімен  стандартталған  немесе  жеке 
технологияларымен  байланысқан  компонеттер  арасында  деректерді  және
 
қолданбаларды  жіберу  функциясына 
ие  (мысалы,  бұлттар  арасында  жүктің  балансы  үшін)  екі  немесе  бірнеше  әртүрлі  инфрақұрылымды  бұлттардан 
тұратын (жеке, қоғамдық немесе мемлекеттік) бұлтты инфрақұрылым. 
 
Бұлтты есептеулердің
 
артықшылақтары: 
 

 
дербес компьютердің есептеу қуаты талаптарына төмендейді;
 

 
қабылдамауға тұрақтылық
; 

 
қауіпсіздік;
 

 
деректердің өңдеуінің жоғары жылдамдығы;
 

 
аппаратты  және  бағдарламалық  қамтамасыз  етуге,  қызметке  және  электроэнергияға  шығындарды 
азайту; 
 

 
дисктік аумаққа үнемділік 
(
деректер де, бағдарламалар да интернетте сақталады
).  

 
кәсіпорынның ішкі бизнес
-
процестерін құжаттандыруды автоматтандыру;
 

 
кәсіпорынның құрылымдық бөлімшелерінің арасындағы айқын өзара қарым
-
қатынас;
 

 
құжаттарды іздестіруге және редакциялауға жұмсалатын уақытты, еңбекті айтарлықтай азайту;
 

 
қағазды  үнемдеу,  құжаттарды  сақтауға  және  өңдеуге  арналған  шығыстарды  азайту,  почталық 
шығындарды қысқарту.
 
Бұлтты есептеулердің
 
кемшіліктері:
  

 
тұтынушылар деректерін сақтауға 
cloud computing 
қызметін беруші ұйымдарға тәуелділік 
; 

 
жаңа («бұлттық»)
 
монополистердің пайда болуы.
  
Қорытынды 
 
Деректердің өсуінің мынандай қарқынымен бұлтты жүйелердің өсуі де жоғары дәрежеде болады. Архивті 
деректердің саны қазіргі таңда тез өсуде. Осы деректерді бұлтты сақтаған өте тиімді болады, себебі бұлтта орын 
көп, дерекке қатынау тез, қауіпсіз және шығыны аз болып келеді. Бұлтты есептеулердiң бүгiнгi танымалдылығы 
тек  технологиялардың  дамуы  ғана  емес,  ол  бiрлескен  программаларды  әзiрлеуiнің  дамуымен  танымал. 
Болашақта бұлтты технологиямен жұмыс арта түседі.
 
 
Қолданылған әдебиеттер тізімі:
 
1.  http://idcrussia.com/ru/ [1
, 2 бет
]  
2. 
Ник
 
Карр
 
(Nick Carr) «Does IT Matter?» 
[2
, 2 бет
] 
3. 
Василий Леонов «Google Docs, Windows Live и другие облачные технологии» 
[
3, 3 бет
] 
4. 
Клементьев И. П. Устинов В. А.
 
«Введение в Облачные вычисления»
 
5. 
Питер Фингар. «DOT.CLOUD. Облачные вычисления 
- 
бизнес
-
платформа XXI века»
  
 
Ғылыми жетекшім:
 
Баенова Гульмира Мусаевна. 
 
 
 
Айгуль Мименбаева, Самал Жумасеитова 
 
(Астана, Казахстан)
 
 
ОСОБЕННОСТИ РЕАЛИЗАЦИИ
 
ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ 
 
ДЛЯ МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ
 
 
Многопроцессорные вычислительные системы (вычислительные кластеры) находят в последнее время 
широкое  применение  –
 
это  и  многопроцессорные  серверы  с  масштабируемыми  СУБД,  и  суперкомпьютеры, 
используемые  для  организации  трудоемких  вычислительных  экспериментов,  и  Intranet
-
сети  масштаба 
предприятия, позволяющие разделять информационные и вычислительные ресурсы. 
 
Если  считать,  что  тактовая  частота  работы  процессоров  приблизительно  соответствует  их 
производительности,  то  в  настоящее  время  около  10
3 
млн.  операций  в  секунду  (МОПС)
 
–
 
это  максимально 
возможная производительность, которая достижима на одном процессоре. Поскольку ежегодно тактовая частота 
выпускаемых  процессоров  возрастает,  можно  надеяться  на  увеличение  максимальной  производительности 
примерно  до  10
6
–
10
8 
МОПС.  Однако  эти  процессы  не  имеют  линейной  экстраполяции  во  времени  в  силу 
молекулярных  ограничений.  Процессоры  с  производительностью  более  10
8 
МОПС  либо  будут  иметь 
принципиально  иную  архитектуру  по  сравнению  с  современными  процессорами,  либо  вообще  невозможны.  Из 
этого  следует,  что  единственной  стратегией  развития  вычислительной  техники  является  создание 
многопроцессорных  вычислителей.  Получается,  что  параллельные  алгоритмы  –
 
единственный  перспективный 
способ повышения производительности при решении будущих задач.
 
Как  бы  ни  были  устроены  параллельные  вычислительные  системы,  все  они  обладают  одной  общей 
особенностью.  Именно,  в  каждый
 
момент  времени  преобразование  информации  может  осуществляться
 
одновременно  на  многих  функциональных  устройствах,  причем  на
 
каждом  устройстве  информация  в  данный 
момент  преобразуется  независимо  от  остальных.  Это  означает,  что  для  того,  чтобы  алгоритм
 
мог  быть 
реализуем на параллельной системе, он должен быть представим в виде последовательности групп операций. 
Все  операции
 
одной  группы  должны  быть  независимыми  и  обладать  возможностью
 
быть  выполненными 
одновременно на имеющихся в системе функциональных устройствах.
 
Пусть операции алгоритма разбиты на группы, упорядоченные
 
так, что каждая операция любой группы 
зависит  либо  от  начальных
 
данных  алгоритма,  либо  от  результатов  выполнения  операций,  находящихся  в 
предыдущих группах. Представление алгоритма в подобном виде называется параллельной формой алгоритма. 
Каждая
 
группа операций называется ярусом параллельной формы, число
 
групп –
 
высотой параллельной формы, 
максимальное число операций в ярусе –
 
шириной параллельной формы.
 

«Проблемы и перспективы развития науки в начале третьего тысячелетия в странах СНГ»
 
297 
 
 
 
Если  известна  параллельная  форма  алгоритма,  то  сам  алгоритм  можно  реализовать  на  параллельной 
вычислительной  системе  по  шагам  последовательно  ярус  за  ярусом.  Если  состав  функциональных  устройств 
системы  таков,  что  параллельно  могут  выполняться  все  операции  любого  яруса,  то  при  подходящим  образом 
организованной  коммуникационной  сети  алгоритм  может  быть  реализован  на  параллельной
 
системе за  время, 
пропорциональное высоте параллельной формы.
 
Естественно,  что  один  и  тот  же  алгоритм  может  иметь  много  параллельных  форм,  различающихся  как 
высотой,  так  и  шириной.  Среди  всех  параллельных  форм  имеется  одна  или  несколько  форм  минимальной 
высоты. Такие параллельные формы алгоритма называются максимальными, а их высота называется высотой 
алгоритма. 
 
Пусть  требуется  вычислить  выражение 
,  соблюдая  лишь  тот  порядок 
выполнения  операций,  который  фиксирован  формой  записи.  Это  можно  осуществить  многими  способами.  По 
существу, здесь фиксирован не один алгоритм, а несколько математически эквивалентных. Различные порядки 
выполнения операций и различные разбиения операций на группы порождают различные параллельные формы.
 
Одна из них такая:
 
Данные
 
 
Ярус
 1 
 
 
 
Ярус 2 
+ 
 
+
 
Ярус 3
 
 
Высота  этой  параллельной  формы  равна  трем,  ширина  –
 
четырем.  Она  может  быть  реализована  на 
параллельной  системе,  имеющей  четыре  процессора,  способных  выполнять  операции  умножения  и  сложения. 
Сначала выполняются четыре операции умножения,соответствующие ярусу 1, затем две операции сложения из 
яруса 2 и, наконец, одна операция умножения, соответствующая ярусу 3.
 
При этом мы не обращаем внимания ни на какие другие аспекты реализации, кроме того, чтобы число 
процессоров совпадало с шириной схемы и сами процессоры имели возможность выполнять операции каждого 
яруса.  Заметим,  что  в  рассмотренной  схеме  все  четыре  процессора  задействованы  только  на  первом  шаге, 
затем  работают  только  два  процессора  и  на  третьем  шаге  лишь  один  процессор  загружен  выполнением 
полезной  работы,  а  все  остальные  простаивают.  Поэтому  можно  попытаться  построить  другие  параллельные 
формы,  в  которых  высота,  конечно,  будет  больше,  но  зато  число  операций  будет  изменяться  от  яруса  к  ярусу 
меньше. Рассмотрим две такие формы. Одна из них следующая:
 
Данные 
 
Ярус 1
 
 
 
Ярус 2 
 
 
Ярус 3 
 
 
Ярус 4 
 
 
Другая имеет вид 
 
Данные 
 
Ярус 1
 
 
 
Ярус 2 
+ 
 
  
Ярус 3
 
 
Ярус 
4 
 
Ярус 5 
 
Высота второй параллельной формы равна четырем, третьей –пяти. Ширина этих форм равна двум.
 
Обе 
эти параллельные формы могут быть реализованы на параллельной системе с двумя процессорами. Во второй 
параллельной  форме  оба  процессора  работают  на  всех  шагах,  кроме  последнего.  На  третьей  параллельной 
форме хорошо видно, как неудачный выбор порядка выполнения операций на ярусе 2 привел к тому, что один из 
процессоров оказался вынужден простаивать на ярусах 3 и 4, и это увеличило высоту параллельной формы при 
сохранении ее ширины.
 
Этот  простой  пример  показывает  некоторые  из  проблем,  с  которыми  придется
 
встретиться  при 
реализации  алгоритмов  на  параллельных  вычислительных  системах.  Одной  из  них  является  проблема 
загруженности  процессоров.  По
-
видимому,  сложной  окажется  и  проблема  построения  параллельных  форм  с 
заданными свойствами.
 
Для решения одной и той же задачи могут применяться алгоритмы, имеющие различную параллельную 
сложность.  Среди  них  могут  быть  и  алгоритмы  наименьшей  высоты.  Рассмотрим  важный  пример  вычисления 
произведения 
n 
чисел 
c
1
, c
2
,
 
c
3
,c
4 
,…,
 
c
n
, в котором отчетливо видна идея, играющая большую роль в построении 
алгоритмов малой высоты.
 
)
(
)
(
8
7
6
5
4
3
2
1
c
c
c
c
c
c
c
c


8
7
6
5
4
3
2
1
c
c
c
c
c
c
c
c
2
1
c
c
4
3
c
c
6
5
c
c
8
7
c
c
2
1
c
c
4
3
c
c
6
5
c
c
8
7
c
c
)
(
)
(
8
7
6
5
4
3
2
1
c
c
c
c
c
c
c
c


8
7
6
5
4
3
2
1
c
c
c
c
c
c
c
c
2
1
c
c
4
3
c
c
6
5
c
c
8
7
c
c
4
3
2
1
c
c
c
c

8
7
6
5
c
c
c
c

)
(
)
(
8
7
6
5
4
3
2
1
c
c
c
c
c
c
c
c


8
7
6
5
4
3
2
1
c
c
c
c
c
c
c
c
2
1
c
c
4
3
c
c
2
1
c
c
4
3
c
c
6
5
c
c
8
7
c
c
8
7
6
5
c
c
c
c

)
(
)
(
8
7
6
5
4
3
2
1
c
c
c
c
c
c
c
c



298 
«Проблемы и перспективы развития науки в начале третьего тысячелетия в странах СНГ»
 
 
 
 
Пусть 
n
=8. Обычная схема, реализующая процесс последовательного умножения, выглядит следующим 
образом:
 
Данные 
 
Ярус 1
 
 
Ярус 2 
 
Ярус 3 
 
Ярус 4 
 
Ярус 5 
 
Ярус 6 
  
Ярус 7 
 
Высота  параллельной  формы  равна  трем,  ширина  –
 
четырем.  Существенное  снижение  высоты 
произошло за счет более полной загруженности процессоров выполнением полезной работы. Последняя схема 
очевидным  образом  распространяется  на  случай  произвольного 
n
.  Для  ее  реализации  необходимо  на  каждом 
ярусе  осуществить  максимально  возможное  число  произведений  непересекающихся  пар  чисел,  взятых  на 
предыдущем
 
ярусе. В
 
общем
 
случае высота параллельной формы равна [
 log
2
n 
], где [
 
α ] означает ближайшее 
сверху  к  а  целое  число.  Эта  параллельная  форма  реализуется  на  [
  n/2 
]  процессорах,  но  в  ней  загруженность 
процессоров  уменьшается  от  яруса  к  ярусу.  Процесс  построения  чисел  каждого  яруса  по  описанной  схеме 
называется  процессом  сдваивания.  Очевидно,  что  с  его  помощью  можно  строить  параллельные  формы  с 
логарифмической высотой не только для операции умножения чисел, но и для любой ассоциативной операции, 
например сложения чисел, умножения матриц и т. п.
 
При  вычислении  произведения 
n 
чисел  часто  требуется  знать  не  только  этот  результат,  но  и  все 
частичные  произведения 
c
1
,  c
1
c
2
,  c
1
c
2
c
3 
и  т.  д.  Эта  задача  реализуется  по  схеме  сдваивания  исключительно 
эффективно. Снова рассмотрим ее для 
n=8: 
Данные 
 
Ярус 1
 
 
 
 
 
Ярус 2 
 
 
Ярус 3 
 
Высота параллельной формы равна трем, ширина –
 
четырем. Все процессоры на всех шагах загружены 
полностью.  На  этом  примере  можно  заметить  одну  характерную  особенность  параллельных  алгоритмов.  По 
сравнению  с  соответствующими  последовательными  алгоритмами  реализация  параллельных  алгоритмов 
требует  выполнения  «лишних»  операций,  и  их  число  может  быть  очень  большим.  В  рассмотренном  примере 
получено пять лишних чисел, которые в схеме подчеркнуты.
 
Обратим внимание еще на одну не заметную, но очень важную особенность параллельных алгоритмов. 
Анализируя  обе  схемы  вычисления  произведения 
n 
чисел,  нетрудно  видеть,  что  они  реализуют  разные 
алгоритмы.  Хотя  в  силу  ассоциативности  операции  оба  алгоритма  дают  одинаковые  результаты  в  условиях 
точных  вычислений,  они  будут  давать  разные  результаты  в  условиях  влияния  ошибок  округления.  Этот  факт 
обязательно  нужно  учитывать  при  конструировании  параллельных  алгоритмов.  Общая  ситуация  такова,  что 
устойчивость  параллельных  алгоритмов  при  большом  числе  процессоров  оказывается  хуже  устойчивости 
последовательных алгоритмов. По крайней мере области устойчивости для последовательных и параллельных 
алгоритмов оказываются различными. 
 
Пусть  с  помощью  бинарных  и  унарных  операций  вычисляется  некоторое  выражение,  существенным 
образом зависящее от переменных. Предположим, что имеется некоторый алгоритм высоты s, позволяющий это 
выражение вычислить. Не ограничивая общности, можно допустить, что каждая операция любого яруса хотя бы 
в  качестве  одного  аргумента  использует  результат  выполнения  какой
-
нибудь  операции,  находящейся  в 
предыдущем  ярусе,  и  каждый  результат,  кроме  последнего,
 
где
-
то  используется.  Так  как  результат  зависит  от 
всех входных переменных и число аргументов всех операций не больше двух, то число операций в каждом ярусе 
не более чем в два раза превышает число операций в следующем ярусе. Следовательно, результат вычисления 
выражения  при  s  ярусах  будет  зависеть  не  более  чем  от  2
s
 
входных  данных.  Отсюда  вытекает,  что
  s
≥[
log
2
n]  . 
Очевидно,  что  если  для  вычисления  выражения  используются  операции,  имеющие  не  более 
p 
аргументов,  то 
s
≥[
log
2
n].  
Таким  образом,  если  какая
-
нибудь
 
задача  определяется 
n 
входными  данными,  то  мы  не  можем 
рассчитывать в общем случае на существование алгоритма ее решения с высотой по порядку меньше log
n
. Если 
получен  алгоритм  высоты  порядка  log
a
n,  то  такой  алгоритм  мы  должны  считать  эффективным  с  точки  зрения 
времени  реализации  на  параллельной  вычислительной  системе,  если  не  принимать  во  внимание  все  другие 
аспекты реализации. В частности, высота порядка logn является оценкой снизу почти для всех задач линейной 
алгебры с матрицами порядка 
n. 
 
8
7
6
5
4
3
2
1
c
c
c
c
c
c
c
c
2
1
c
c
3
2
1
)
(
c
c
c
4
3
2
1
)
(
c
c
c
c
5
4
3
2
1
)
(
c
c
c
c
c
6
5
4
3
2
1
)
(
c
c
c
c
c
c
7
6
5
4
3
2
1
)
(
c
c
c
c
c
c
c
8
7
6
5
4
3
2
1
)
(
c
c
c
c
c
c
c
c
8
7
6
5
4
3
2
1
c
c
c
c
c
c
c
c
2
1
c
c
4
3
c
c
6
5
c
c
8
7
c
c
)
)(
(
)
(
)
)(
(
)
(
8
7
6
5
7
6
5
4
3
2
1
3
2
1
c
c
c
c
c
c
c
c
c
c
c
c
c
c
)
...
)(
...
(
)
)(
...
(
)
)(
...
(
)
...
(
8
5
4
1
7
6
5
4
1
6
5
4
1
5
4
1
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c

«Проблемы и перспективы развития науки в начале третьего тысячелетия в странах СНГ»
 
299 
 
 
 

жүктеу/скачать 9,75 Mb.

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