Оценка времени обработки данных в кластерных системах
Рассмотрено влияние распараллеливания на время решения задач, связанных с обработкой больших объемов данных (баз данных
 или файлов). Полученные оценки позволяют оптимизировать архитектуру программы для исполнения в кластерной системе на
 основе небольшого числа экспериментов. The in...
Збережено в:
| Дата: | 2006 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут програмних систем НАН України
2006
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/1594 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Оценка времени обработки данных в кластерных системах / В.Г. Тульчинский, А.К. Чарута // Проблеми програмування. — 2006. — N 2-3. — С. 118-123. — Бібліогр.: 4 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860217416749940736 |
|---|---|
| author | Тульчинский, В.Г. Чарута, А.К. |
| author_facet | Тульчинский, В.Г. Чарута, А.К. |
| citation_txt | Оценка времени обработки данных в кластерных системах / В.Г. Тульчинский, А.К. Чарута // Проблеми програмування. — 2006. — N 2-3. — С. 118-123. — Бібліогр.: 4 назв. — рос. |
| collection | DSpace DC |
| description | Рассмотрено влияние распараллеливания на время решения задач, связанных с обработкой больших объемов данных (баз данных
или файлов). Полученные оценки позволяют оптимизировать архитектуру программы для исполнения в кластерной системе на
основе небольшого числа экспериментов.
The influence of parallel implementation of the data processing tasks on the task computation time is considered for databases and files.
Obtained estimations allow optimize the program architecture for execution in a cluster system on the base of few experiment results.
|
| first_indexed | 2025-12-07T18:16:31Z |
| format | Article |
| fulltext |
Паралельне програмування. Розподілені системи і мережі
© A.Ju. Shelestov, N.N. Kussul, S.V. Skakun, 2006
ISSN 1727-4907. Проблеми програмування. 2006 № 2-3. Спеціальний випуск 118
УДК 681.3
ОЦЕНКА ВРЕМЕНИ ОБРАБОТКИ ДАННЫХ
В КЛАСТЕРНЫХ СИСТЕМАХ
В.Г. Тульчинский, А.К. Чарута
Институт кибернетики им. В.М. Глушкова НАН Украины
03680, Киев 187, проспект Академика Глушкова, 40
факс: 526 7418, т.: 526 2008, e-mail:aik@public.icyb.kiev.ua
Рассмотрено влияние распараллеливания на время решения задач, связанных с обработкой больших объемов данных (баз данных
или файлов). Полученные оценки позволяют оптимизировать архитектуру программы для исполнения в кластерной системе на
основе небольшого числа экспериментов.
The influence of parallel implementation of the data processing tasks on the task computation time is considered for databases and files.
Obtained estimations allow optimize the program architecture for execution in a cluster system on the base of few experiment results.
Вступление
Современные параллельные вычислители с архитектурой МИМД (кластеры) предназначены для
выполнения с максимальной эффективностью объемных вычислений. Важнейшей особенностью вычислений
на кластере является максимальная концентрация вычислительных ресурсов всего кластера или его выделенной
части для решения одной задачи. В результате параметры системы остаются стабильны в течение всего
времени выполнения задачи. Приложение может быть заранее или в процессе работы оптимизировано с учетом
значений этих устойчивых параметров. Такая архитектура делает кластеры привлекательным объектом для
формального анализа и применения математических методов.
В работе рассматривается влияние способа распределения данных на производительность кластера в
задачах, требующих интенсивной обработки больших объемов информации.
Цель работы
Значительную часть практических задач, решаемых на кластерах, составляют задачи однородной
обработки больших массивов данных. Такие задачи, как правило, легко распараллеливаются, так как обладают
естественной параллельностью по данным. Мы будем рассматривать именно распараллеленные задачи. Их
особенность – синхронность полезных операций на всех узлах. Такие задачи возникают, в частности, в
геологии / геофизике (обработка результатов сейсмических исследований земной коры), при обработке
естественно-языковых текстов, изображений (например, результатов аэрофотосъемки и космоснимков земной
поверхности), при обработке видео, в задачах Data Mining и статистической обработки больших баз данных.
Цель работы – оптимизация распределения данных и операций над данными с целью минимизации
очередей и ускорения решения задачи всей системой.
Постановка задачи
Наиболее распространенная в наше время архитектура кластеров «Беовульф» [1], если отвлечься от
деталей реализации, представляет собой соединенный высокопроизводительной сетью набор однотипных узлов
– обычных ПК. Во многих случаях архитектура включает общее хранилище данных, например, дисковую
стойку. Вариант архитектуры с общим диском может быть реализован без дисковой памяти на узлах.
Управляются такие кластеры, как правило, ОС Linux, для обмена сообщениями используются
реализации MPI. (Можно запускать и программы, написанные под PVM, но PVM разработана для гетерогенных
кластеров и в однородной среде работает медленнее.) При старте программы MPI создает несколько
одинаковых процессов, как правило, по одному на каждый процессор каждого задействованного узла кластера.
Процессы знают свой номер и общее число процессов задачи и в зависимости от номера выбирают алгоритм
работы. Хотя MPI обеспечивает разнообразные способы передачи данных, включая широковещание и
асинхронный обмен, реализованные на кластерах параллельные алгоритмы главным образом основаны на
синхронном обмене. Процесс, посылающий данные, ожидает завершения их приема, а принимающий ожидает
посылки и передачи данных. Операция приема данных имеет две модификации: прием от одного конкретного
процесса или от любого процесса задачи.
Далее термин «процесс» используется в двух смыслах: как в информатике и как в математической
статистике. Это удобно, так как речь идет об одном объекте, а смысл конкретного употребления термина ясен
из контекста.
Рассмотрим классические стратегии распределения данных в кластерной системе [2]: централизация,
дублирование, расчленение, смешанная стратегия.
Паралельне програмування. Розподілені системи і мережі
119
Централизация означает, что единственная копия базы данных или файла управляется одним
процессом на одном узле кластера или в дисковой стойке. С ростом числа узлов кластера и интенсивности
обращений к данным централизованный доступ к данным становится узким местом системы.
Дублирование означает, что на всех или нескольких узлах расположены копии данных. На первый
взгляд, индивидуальная работа процессов со своими локальными данными может полностью убрать очереди.
Но это верно лишь для случаев полной независимости процессов по данным. Если же результаты, записанные
одним процессом, могут быть затребованы другими процессами, каждое обновление данных необходимо
распространить на все узлы. Кроме того, большие данные могут просто целиком не поместиться на одном узле.
Расчленение означает, что непересекающиеся подмножества данных управляются процессами на
разных узлах. Эта стратегия хороша, если данные обладают иерархической или блочной структурой. В случае
сложно структурированных данных ее реализация требует значительных усилий.
В наиболее популярной смешанной стратегии организуется несколько расчлененных копий данных.
Еще одна смешанная стратегия – сегментация (централизация с дублированием части данных). Известно, что 80
% обращений к базе данных приходятся только на 20 % записей данных. При сегментации на узлах
размещаются небольшие, но наиболее востребованные фрагменты данных.
При проектировании или настройке программы на параметры конкретной кластерной системы
приходится также выбирать между специализацией нескольких узлов на обслуживании обращений к данным и
сочетанием работы данными с вычислениями. Ясно, что оптимизация работы с данными в общем случае –
довольно трудная задача. Для ее решения предлагается оценить время выполнения параллельного вычислителя
заданного размера при решении задачи на основе небольшого числа экспериментально определяемых
параметров.
Рассмотрим следующую модель параллельной обработки большого объема данных на кластере, на
котором N процессов выполняются параллельно. Работа каждого из них может быть представлена в виде
чередования расчетов и обращений к данным для чтения или записи. Еще S процессов (СУБД или файловые
системы хранилища) обслуживают обращения к данным. Каждый из них ждет поступления запроса от одного
из вычислительных процессов, затем выполняет его. Пока обслуживающий процесс выполняет запрос, на него
могут поступить другие запросы. Все они ставятся в очередь неограниченной емкости и обслуживаются в
порядке поступления. В результате вычислительный процесс n представляется последовательностью
интервалов (неотрицательных действительных чисел) трех типов: расчет ( n
it ), ожидание освобождения
данных ( n
iδ ), чтение или запись данных ( n
iτ ).
Поведение такой системы зависит от соотношения между временем расчетов и временем доступа к
данным. Будем рассматривать два предельных случая: со слабой загрузкой, когда очередь запросов на доступ к
данным одной операции успевает рассосаться до начала следующей операции доступа к данным, и с полной
загрузкой, когда эта очередь, возникнув на первом шаге, не рассасывается до конца расчетов.
Условие слабой загрузки может быть сформулировано следующим образом: i∀ n
i
n
n
i t 1+<<∑τ . В случае
полной загрузки i∀ n
i
n
n
i t 1+≥∑τ .
Для рассматриваемых задач различием времени выполнения на i -м шаге расчета или обращения к
данным в зависимости от номера процесса можно пренебречь, поэтому опустим лишний индекс. Время, за
которое будет закончено i шагов процесса n , обозначаем ii
n
i
nnn
i tttt ++++++++++= τδτδτδγ ...2221110 .
Условия слабой и полной загрузки можно, соответственно, переписать как 1+<< ii tNτ и 1+≥ ii tNτ .
Случай слабой загрузки
В этом случае увеличение числа параллельно работающих процессов с одной стороны уменьшает
время расчетов it (в силу распараллеливания), а с другой – увеличивает число обращений к данным
пропорционально N . В результате очередь быстро перестает рассасываться. Однако случай слабой загрузки
наиболее интересен, так как после возникновения устойчивой очереди дальнейшее распараллеливание не имеет
практического смысла.
Централизованный доступ со слабой загрузкой. В случае централизованного доступа количество
обслуживающих процессов 1=S . Обозначим также накопленное к i -му шагу время ожидания процесса
n n
i
nnn
i δδδ ++=∆ ...21 . Так как 0≥n
iδ
n
i
n
i ∆≥∆ +1 . (1)
Для удобства, не снижая общности, будем считать, что вычислительные процессы упорядочены по
возрастанию 1δ : nn
1
1
1 δδ >+ . Тогда можем утверждать, что
ni
n
i τ≥∆ +1 . (2)
Паралельне програмування. Розподілені системи і мережі
120
Это утверждение легко доказывается по индукции, так как из правила упорядочения следует nn
1
1
1 γγ >+ ,
а очередь запросов гарантирует, что раньше пришедший запрос будет обработан раньше, т.е. i
n
i
n
i τγγ +≥+1 ,
после чего достаточно просуммировать по n и учесть, что 00 ≥∆ i .
Из утверждений (1) и (2) получаем { }ni
Ii
n
I τ
≤≤
+ ≥∆
1
1 max . Отметим, что небольшое изменение процедуры
формирования очереди обеспечивает
{ }ni
Ii
n
I τ
≤≤
+ =∆
1
1 max . (3)
Для этого достаточно только соблюдать порядок шагов и не выполнять 1+iτ до того, как выполнены все
iτ . Средствами MPI это делается элементарно: вместо ожидания сообщения от любого процесса ставится
команда ожидания сообщения от следующего процесса по модулю N .
Обозначим максимальное время выполнения обращения к памяти { }iττ maxmax = . В силу слабой
загрузки можно полагать 1+< ii tNτ , т.е. очередь не накапливается. Поэтому общее время выполнения задачи
Σγ вычисляется как время выполнения самого длинного потока: ( )∑ ∑ −++== max1ττγ NtT ii
N
IN .
С практической точки зрения эту формулу удобно переписать по-другому, чтобы параметры можно
было легко оценивать. Пусть при 1=N общие затраты на обработку данных ∑= iD τ , а расчеты выполняются
за время 11 DTC −= . Обозначим долю чистых расчетов 1TC=θ , а долю распараллеливаемой части расчетов
10 ≤<η . Тогда с учетом задержки (3) время работы программы на N процессов по формуле Амдала
составляет:
( ) ( ) max11 τηη −+++−= ND
N
C
CTN , откуда
( ) ( ) max1 11 τηθηθ −+
+−= NT
N
TN .
(4)
(5)
Параметр η определяется экспериментально по серии запусков одной задачи с разным числом
процессов N .
Дублирование данных со слабой загрузкой. Простейший случай дублирования без размножения
данных обобщает случай централизации. Пусть у нас есть S -процессорный сервер данных и на каждом
процессоре выполняется процесс СУБД, обслуживающий как в централизованном случае до SN
вычислительных процессов. Формула (5) преобразуется к виду
( ) ( ) max1 1
1
1 τ
θηθ
θη −+
−
++−=
SNT
SN
TN . (6)
Представляется, что размещение копий данных на всех узлах кластера может значительно уменьшить
очереди. Запросы на чтение данных будут в этом случае выполняться без задержек. Однако запись
промежуточных результатов потребует широковещательного оповещения всех узлов. В случае полного
дублирования обработка должна быть синхронной, т.е. процессу на узле нужно кроме своих данных записать
изменения на остальных 1−S обслуживающих процессах прежде, чем переходить к следующему шагу.
Поэтому, обозначив затраты на чтение Dρ и заменив D на ( )( )DS ρρ −+ 1 , формулу (4) можно преобразовать
к виду
( ) ( ) ( ) W
N ST
SN
T max1 1
1
1 τθρηθηρθρ −+
−++−+−= , (7)
где W
maxτ – максимальное время записи данных, необходимых более чем одному процессу. В общем
случае помимо NT нужно учесть затраты на начальное копирование данных на все узлы.
Расчленение данных со слабой загрузкой. В этой стратегии непересекающиеся подмножества данных
распределены по узлам кластера и управляются отдельными S процессами. Хотя пропорциональное
расчленение (да и вообще эффективное расчленение) не всегда возможно, оно часто встречается в
рассматриваемых задачах с естественной параллельностью. Пусть запросы выполняются в порядке
поступления, а вероятность обращения конкретного запроса к k -му обслуживающему процессу Spk 1= .
Рассмотрим процессы, описывающие входные запросы от N узлов кластера, как независимые. Хотя это не
Паралельне програмування. Розподілені системи і мережі
121
совсем так, при достаточно больших S и N длина очереди в момент запроса, а, следовательно, и время
ожидания будут случайным образом меняться. Предположим также, что все N процессов стационарны и
ординарны. В силу синхронности операций каждого процесса вероятность скопления запросов от одного
процесса равна нулю, т.е. все функции Пальма ( ) 1≡tkϕ . По той же причине интенсивность суммарного потока
Λ примерно постоянна, и, значит, интенсивности каждого из N одинаковых потоков λλ =n равномерно
сходится к нулю с ростом N . Тогда имеем дело с суперпозицией потоков малой интенсивности. По предельной
теореме теории массового обслуживания [3] на k -й обслуживающий процесс приходит простейший поток с
интенсивностью Nλ=Λ (по теореме Пальма). Для этого случая известно общее решение А.Я. Хинчина из
которого, в частности, среднее время ожидания
( ) ( )
( )τµ
τµ
α
αδµ
2
2
1 −= , (8)
где α – вероятность простоя обслуживающего процесса, т.е. среднее время ожидания вызовов за единицу
времени, µ – обозначение математического ожидания.
( ) ( ) ( ) ( )
( )τµ
τµ
α
αµηηµ
2
2
1
1
−+++−= I
S
D
N
C
CTN ,
( )( ) ( )( )ΣΣ −=⇒=− γµαγαµ SDSD 11 .
(9)
(10)
С учетом ( ) ( )( )τµµ SDI = , (9) и (10) получаем квадратное уравнение, неотрицательный корень которого
( ) ( )
( )
∆+Φ+∆+Φ=
2
2
22
1
2 τµ
τµµ SNSNN TT ,
(11)
где
+−=Φ
NN
ηηθ
1
2
,
SS
θ−=∆ 1
.
Формулу (11) легко модифицировать в зависимости от способа обработки данных для случаев NS = и
constNS =+ .
При выводе формулы (11) применялись оценки для предельного случая, а не для заданного числа
узлов, чтобы избежать решения системы уравнений и получить оценку в явном виде.
В отличие от случая дублирования в случае расчленения мы получили только среднюю оценку. Из
теории массового обслуживания известно, что дисперсия времени ожидания отдельного вызова превышает его
матожидание. Хотя общая дисперсия времени ожидания будет снижаться с увеличением времени работы (т.е.
числа запросов к данным), стохастический характер этой величины нужно учитывать в тех случаях, когда
программа запускается редко, или работает очень долго: максимальное время работы может быть важнее
среднего времени.
Случай полной загрузки
При достаточно большом N задача переходит в состояние полной загрузки. В этом случае время
работы задачи при расчленении данных
( ) ( ) D
S
N
ttT N
iN ++= 1
0µ . (12)
Для централизованного доступа
( ) D
S
N
ttT N
iN
++= 1
0 . (13)
При больших N ( ) ( ) ( )( ) constii
N
i ttt
N
tttt =−+≈
+−+≈+ ηηηµ 11 00
1
0 , причем для длинных задач
Dtconst << . Отсюда (12) и (13) сводятся в общую формулу
( ) ( ) constN tT
S
N
T +−≈ 11 θµ . (14)
Для дублирования данных оценка получается сложней, так как учитывает необходимость
дублирования записи во все обслуживающие процессы:
Паралельне програмування. Розподілені системи і мережі
122
( ) constN tDND
S
N
T +−+
≈ ρρ 1 . (15)
Оценки (14), (15) показывают, что в зоне полной загрузки (при достаточно больших N ) время работы
программы начинает линейно расти с ростом N .
Численный эксперимент
В численном эксперименте использовалась имитация процесса «чистых» расчетов в сочетании с
обращениями к данным для централизованного доступа (рис. 1, 2) и расчленения (рис. 3, 4). «Количество
процессоров» на графиках обозначает N ; «Эксперимент» – экспериментальные данные; «Слабая загрузка» –
расчет по формуле (5) для рис. 1, 2 и по формуле (11) для рис. 3, 4; «Полная загрузка» – расчет по формуле (14)
с 0=constt .
Испытания централизованного доступа проводились на кластере СКИТ–2, в Институте кибернетики
им. В.М. Глушкова НАН Украины, с общей дисковой памятью. Испытания расчленения данных проводились
на кластере ИНПАРКОМ-16 на киевском заводе «Электронмаш», имеющем отдельные диски на узлах.
0
500
1000
1500
2000
2500
3000
1 2 3 4 5 6 7 8 9 10
Количество процессов
В
р
е
м
я
, с
Эксперимент
Слабая загрузка
Полная загрузка
Рис. 1. 975.0=θ , 993.0=η , 15max =τ , 27941 =T
0
100
200
300
400
500
600
700
1 2 3 4 5 6 7
Количество процессов
В
р
ем
я
,с
Эксперимент
Слабая загрузка
Полная загрузка
Рис. 2. 884.0=θ , 96.0=η , 15max =τ , 5941 =T
0
200
400
600
800
1000
1200
1400
1600
2 3 4 5 6 7 8 9 10 11 12
Количество процессов
В
р
е
м
я
, с
Эксперимент
Слабая загрузка
Полная загрузка
Рис. 3. 4=S , 966.0=θ , 94.0=η ,
( ) 14=τµ , ( ) 2462 =τµ , 28211 =T
0
200
400
600
800
1000
1200
1400
1600
2 4 6 8 10 12 14 16 18
Количество процессов
В
р
ем
я,
с
Эксперимент
Слабая загрузка
Полная загрузка
Рис. 4. 2=S , 966.0=θ , 93.0=η ,
( ) 14=τµ , ( ) 2462 =τµ , 28211 =T
Паралельне програмування. Розподілені системи і мережі
123
Большие колебания экспериментального графика для расчленения данных связано со стохастическим
характером зависимости в этом случае. Некоторое занижение оценок полной загрузки для больших N вызвано
пренебрежением N
itt +1
0 и коммуникационными расходами.
Сравнение аналитических оценок с экспериментальными данными демонстрирует пригодность точки
пересечения графиков слабой и полной загрузки в качестве хорошего начального приближения точки перегиба
экспериментального графика производительности. Для ее уточнения достаточно провести экспериментальное
исследование в небольшой окрестности точки пересечения. Эксперименты также продемонстрировали
высокую точность оценок (6), (11) для слабой загрузки.
Выводы
Формулы (6), (7) и (11) в сочетании с формулой (14) позволяют по результатам небольшого числа
простых экспериментов:
- оптимизировать распределение данных между узлами кластера;
- подбирать наилучшее количество обслуживающих и вычислительных процессов для достижения
максимального быстродействия задачи.
За пределами рассмотрения остался смешанный случай и случай сегментации, возникающий как
комбинация централизации и дублирования, если данные целиком не помещаются на узлах. Оба эти варианты
могут быть оценены путем комбинирования и небольшой модификации полученных оценок. В работе
дополнены и уточнены оценки, полученные в [4].
1. Аладышев О.С., Савин Г.И., Телегин П.Н., Шабанов Б.М. Кластеры класса Беовульф // Научно-технический журнал “Известия
высших учебных заведений. Электроника”. – 2001, № 1. – С. 7 – 13. (http://www.jscc.ru/informat/ClusterBeoWulf.html)
2. Тиори Т., Фрай Дж. Проектирование структур баз данных: В 2-х кн. Кн. 1. Пер. с англ. – М.: Мир, 1985. – 287 с.
3. Хинчин А.Я. Работы по математической теории массового обслуживания. – М.: Физматгиз, 1963. – 236 с.
4. Тульчинский В.Г., Тульчинский П.Г. Обработка больших объемов данных в кластерных системах // Искусственный интеллект. – 2005,
№ 4. – С. 651 – 657.
|
| id | nasplib_isofts_kiev_ua-123456789-1594 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1727-4907 |
| language | Russian |
| last_indexed | 2025-12-07T18:16:31Z |
| publishDate | 2006 |
| publisher | Інститут програмних систем НАН України |
| record_format | dspace |
| spelling | Тульчинский, В.Г. Чарута, А.К. 2008-08-27T09:47:15Z 2008-08-27T09:47:15Z 2006 Оценка времени обработки данных в кластерных системах / В.Г. Тульчинский, А.К. Чарута // Проблеми програмування. — 2006. — N 2-3. — С. 118-123. — Бібліогр.: 4 назв. — рос. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/1594 681.3 Рассмотрено влияние распараллеливания на время решения задач, связанных с обработкой больших объемов данных (баз данных
 или файлов). Полученные оценки позволяют оптимизировать архитектуру программы для исполнения в кластерной системе на
 основе небольшого числа экспериментов. The influence of parallel implementation of the data processing tasks on the task computation time is considered for databases and files.
 Obtained estimations allow optimize the program architecture for execution in a cluster system on the base of few experiment results. ru Інститут програмних систем НАН України Паралельне програмування. Розподілені системи і мережі Оценка времени обработки данных в кластерных системах Estimation of data processing time for cluster systems Article published earlier |
| spellingShingle | Оценка времени обработки данных в кластерных системах Тульчинский, В.Г. Чарута, А.К. Паралельне програмування. Розподілені системи і мережі |
| title | Оценка времени обработки данных в кластерных системах |
| title_alt | Estimation of data processing time for cluster systems |
| title_full | Оценка времени обработки данных в кластерных системах |
| title_fullStr | Оценка времени обработки данных в кластерных системах |
| title_full_unstemmed | Оценка времени обработки данных в кластерных системах |
| title_short | Оценка времени обработки данных в кластерных системах |
| title_sort | оценка времени обработки данных в кластерных системах |
| topic | Паралельне програмування. Розподілені системи і мережі |
| topic_facet | Паралельне програмування. Розподілені системи і мережі |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/1594 |
| work_keys_str_mv | AT tulʹčinskiivg ocenkavremeniobrabotkidannyhvklasternyhsistemah AT čarutaak ocenkavremeniobrabotkidannyhvklasternyhsistemah AT tulʹčinskiivg estimationofdataprocessingtimeforclustersystems AT čarutaak estimationofdataprocessingtimeforclustersystems |