Структурно-функциональный анализ компонентов GRID-систем
Запропоновано реалізацію системного підходу до побудови та аналізу функціонування Gridсистем. Побудовано ієрархічну структурну модель Gridсистеми спостереження Землі, що об’єднує декілька регіональних та спеціалізованихGridсистем. На основі проведеного структурнофункціонального аналізу слабо формал...
Збережено в:
| Дата: | 2007 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2007
|
| Назва видання: | Проблемы управления и информатики |
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/207129 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Структурно-функциональный анализ компонентов GRID-систем / А.Ю. Шелестов // Проблемы управления и информатики. — 2007. — № 5. — С. 119-132. — Бібліогр.: 9 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-207129 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-2071292025-09-30T00:15:19Z Структурно-функциональный анализ компонентов GRID-систем Структурно-функціональний аналіз компонентів GRID-систем Structural-functional analysis of the Grid-system components Шелестов, А.Ю. Методы обработки информации Запропоновано реалізацію системного підходу до побудови та аналізу функціонування Gridсистем. Побудовано ієрархічну структурну модель Gridсистеми спостереження Землі, що об’єднує декілька регіональних та спеціалізованихGridсистем. На основі проведеного структурнофункціонального аналізу слабо формалізовану задачу оптимізації структури та продуктивності вузла складної ієрархічної системи зведено до ряду задач дискретної оптимізації. Запропонований підхід апробовано при побудові реальної Gridсистеми спостереження Землі. Запропоновано реалізацію системного підходу до побудови та аналізу функціонування Gridсистем. Побудовано ієрархічну структурну модель Gridсистеми спостереження Землі, що об’єднує декілька регіональних та спеціалізованихGridсистем. На основі проведеного структурнофункціонального аналізу слабо формалізовану задачу оптимізації структури та продуктивності вузла складної ієрархічної системи зведено до ряду задач дискретної оптимізації. Запропонований підхід апробовано при побудові реальної Gridсистеми спостереження Землі. Работа выполнена при поддержке проектов № 3872 «Разработка эффективных Grid-технологий экологического мониторинга на основе спутниковых данных» и INTAS-CNES-NSAU «Data Fusion Grid Infrastructure»(Ref. Nr 06-1000024-9154) Украинского научно-технологического центра. 2007 Article Структурно-функциональный анализ компонентов GRID-систем / А.Ю. Шелестов // Проблемы управления и информатики. — 2007. — № 5. — С. 119-132. — Бібліогр.: 9 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/207129 681.51 ru Проблемы управления и информатики application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Методы обработки информации Методы обработки информации |
| spellingShingle |
Методы обработки информации Методы обработки информации Шелестов, А.Ю. Структурно-функциональный анализ компонентов GRID-систем Проблемы управления и информатики |
| description |
Запропоновано реалізацію системного підходу до побудови та аналізу функціонування Gridсистем. Побудовано ієрархічну структурну модель Gridсистеми спостереження Землі, що об’єднує декілька регіональних та спеціалізованихGridсистем. На основі проведеного структурнофункціонального аналізу слабо формалізовану задачу оптимізації структури та продуктивності вузла складної ієрархічної системи зведено до ряду задач дискретної оптимізації. Запропонований підхід апробовано при побудові реальної Gridсистеми спостереження Землі. |
| format |
Article |
| author |
Шелестов, А.Ю. |
| author_facet |
Шелестов, А.Ю. |
| author_sort |
Шелестов, А.Ю. |
| title |
Структурно-функциональный анализ компонентов GRID-систем |
| title_short |
Структурно-функциональный анализ компонентов GRID-систем |
| title_full |
Структурно-функциональный анализ компонентов GRID-систем |
| title_fullStr |
Структурно-функциональный анализ компонентов GRID-систем |
| title_full_unstemmed |
Структурно-функциональный анализ компонентов GRID-систем |
| title_sort |
структурно-функциональный анализ компонентов grid-систем |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2007 |
| topic_facet |
Методы обработки информации |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/207129 |
| citation_txt |
Структурно-функциональный анализ компонентов GRID-систем / А.Ю. Шелестов // Проблемы управления и информатики. — 2007. — № 5. — С. 119-132. — Бібліогр.: 9 назв. — рос. |
| series |
Проблемы управления и информатики |
| work_keys_str_mv |
AT šelestovaû strukturnofunkcionalʹnyjanalizkomponentovgridsistem AT šelestovaû strukturnofunkcíonalʹnijanalízkomponentívgridsistem AT šelestovaû structuralfunctionalanalysisofthegridsystemcomponents |
| first_indexed |
2025-09-30T01:29:16Z |
| last_indexed |
2025-10-01T01:26:10Z |
| _version_ |
1844740851479085056 |
| fulltext |
© А.Ю. ШЕЛЕСТОВ, 2007
Проблемы управления и информатики, 2007, № 5 119
УДК 681.51
А.Ю. Шелестов
СТРУКТУРНО-ФУНКЦИОНАЛЬНЫЙ
АНАЛИЗ КОМПОНЕНТОВ GRID-СИСТЕМ
Введение
Современный уровень информатизации общества характеризуется бурным
развитием сложных распределенных систем (виртуальных организаций), включа-
ющих высокопроизводительную вычислительную технику и хранилища данных
больших объемов. Многие из этих систем активно функционируют и базируются
на Grid-технологии, обеспечивающей для пользователя легкий («прозрачный»)
доступ к ресурсам виртуальной организации. Наблюдаются тенденции интегра-
ции отдельных систем в еще более сложные структуры. При этом возникает мно-
жество плохо формализуемых задач оптимизации затрат и производительности,
поэтому сегодня актуальной является не просто задача построения очередной
Grid-системы, а создания эффективной Интер-Grid инфраструктуры, объединяю-
щей несколько работающих или вновь создаваемых региональных или специали-
зированных Grid-систем. Особый интерес исследователей в последнее время вы-
зывают Grid-системы наблюдения Земли из космоса (Earth Observation Grid —
EO Grid), поскольку они представляют собой не просто высокопроизводительные
вычислительные системы, а Grid-системы смешанного типа и включают распре-
деленные хранилища с большими объемами информации. Проблемам создания
таких систем посвящен специальный проект DEGREE (http://www.eu-degree.eu/) в
рамках программы EGEE-2.
В таких условиях на первый план выступают задачи моделирования Grid-сис-
тем и оценки их производительности. Учитывая сложность задачи, авторы много-
численных работ, в частности [1–3], приходят к общему мнению о невозможности
построения единой модели такой системы, описывающей все разнообразие аспек-
тов ее структуры и поведения. В литературе предлагаются конкретные модели,
описывающие с помощью определенного математического аппарата (операцион-
ного анализа, теории массового обслуживания, теории графов и т.п.) один из ра-
курсов системы. Обзор моделей разного уровня абстракции содержится в [2].
Единственно возможным подходом, обеспечивающим адекватное представление
сложных иерархических систем на разных уровнях конкретизации, является си-
стемный анализ [1, 3].
В данной работе предложенный в [1] метод структурно-функционального
анализа (СФА) применяется к предметной области Grid-систем и развивается для
Grid-систем наблюдения Земли из космоса.
Постановка задачи структурно-функционального
анализа сложных иерархических систем
Учитывая высокую стоимость создания распределенных систем на основе
высокопроизводительной техники, к их разработке требуется подходить с пози-
ций системного анализа, в частности метода СФА. Согласно [1, с. 432] содержа-
Работа выполнена при поддержке проектов № 3872 «Разработка эффективных Grid-технологий эко-
логического мониторинга на основе спутниковых данных» и INTAS-CNES-NSAU «Data Fusion Grid
Infrastructure» (Ref. Nr 06-1000024-9154) Украинского научно-технологического центра.
120 ISSN 0572-2691
тельная формулировка задачи структурно-функционального анализа сводится к
следующему. Известны назначение, общие характеристики и свойства системы
EO Grid, а также требования к структурным, функциональным, эксплуатацион-
ным и экономическим показателям.
Конкретнее, система EO Grid предназначена для решения задач экологиче-
ского мониторинга, оценки рисков и прогнозирования последствий экологических
и техногенных чрезвычайных ситуаций, поддержки принятия решений в интере-
сах устойчивого развития на основе интеграции данных наземных и аэрокосмиче-
ских наблюдений, а также данных моделирования. В зависимости от перечня за-
дач, решаемых в конкретной системе, можно определить конкретные требования
или реализованные свойства перечисленных выше категорий.
Требуется определить структуру EO Grid как сложной иерархической систе-
мы, обосновать требования к каждому сегменту, узлу и функциональному эле-
менту (ФЭ) всех иерархических уровней.
Заметим, что структурно-функциональный анализ может выполняться на
разных стадиях жизненного цикла системы: как на этапе ее проектирования, так и
в процессе ее эксплуатации. В первом случае формулируется перечень требова-
ний к системе, во втором — набор свойств (существующих или желаемых в зави-
симости от постановки задачи), поэтому без ограничения общности термины
«требования» и «свойства» будем рассматривать как синонимы.
Формализация задачи структурно-функционального анализа
Перейдем к формализации задачи структурно-функционального анализа си-
стемы EO Grid. Согласно выражению (7.1) из [1, с. 433] множество требований
(свойств) рассматриваемой системы представляется в виде упорядоченной по зна-
чимости структуры классов (категорий):
},,1{ 10 miBB i ==
(1)
где 0B — множество свойств системы, iB — i-й класс (категория) свойств
).5( 1 =m
Для систем EO Grid выделим следующее множество классов: B1 — класс
структурных свойств (требований), характеризующих структуру системы и ее
элементов; B2 — класс функциональных свойств, определяющих перечень функ-
ций системы и количественные показатели их выполнения; B3 — класс эксплуа-
тационных свойств, определяющих удобство эксплуатации системы и требования
к внешним условиям; B4 — класс свойств безопасности; B5 — класс экономиче-
ских свойств, определяющих требования к стоимости построения и эксплуатации
системы.
Каждая категория Bi определяется набором свойств bij:
}.,1{ iiji mjbB ==
(2)
Рассмотрим каждую категорию в отдельности. Если множество B1 представ-
ляет класс структурных свойств },,1{ 111 mjbB j == то 91 =m и к данному клас-
су относятся следующие количественные свойства: b11 — число узлов в системе,
b12 — число процессоров, b13 — пропускная способность каналов связи, b14 —
объем памяти для хранения данных, b15 — объем оперативной памяти.
Проблемы управления и информатики, 2007, № 5 121
К качественным (не количественным) свойствам (требованиям к структуре
системы) относятся: b16 — гетерогенность (гомогенность), b17 — межузловая то-
пология, b18 — требования к интерфейсам, b19 — сервисная ориентированность,
или соответствие стандартам WSRF (Web Service Resource Framework).
Множество 2B функциональных свойств },1{ 222 mjbB j == характеризу-
ется следующим набором параметров: b21 — поддержка запросов пользователей
на выполнение задач в заданном виде; b22 — поддержка запросов пользователей
на высокоуровневый доступ, передачу и репликацию данных; b23 — поддержка
единой регистрации; b24 — балансировка нагрузки; b25 — сбор статистики; b26 —
наблюдаемость (наличие информации о состоянии системы и ее элементов);
b27 — управляемость (возможность целенаправленно изменять состояние ФЭ (уз-
лов) для достижения заданного критерия); b28 — адаптируемость (возможность
перенастройки системы в соответствии с изменением внешней среды, например,
появлением новых задач или узлов системы).
Множество 3B эксплуатационных свойств },1{ 333 mjbB j == характеризу-
ется следующим набором параметров: b31 — наличие определенного программного
обеспечения; b32 — дружественный интерфейс; b33 — Quality of Service (QoS) —
гарантированное время ожидания до начала выполнения задач; b34 — должна
поддерживать расширяемость без остановки работы.
Множество 4B свойств безопасности },1{ 444 mjbB j == согласно [4] со-
держит следующие элементы: b41 — конфиденциальность (доверительная, адми-
нистративная, повторное использование объектов, анализ скрытых каналов, кон-
фиденциальность при обмене); b42 — целостность (доверительная, админи-
стративная, откат, целостность при обмене); b43 — доступность (использование
ресурсов, устойчивость к отказам, горячая замена, восстановление после сбоев);
b44 — наблюдаемость (регистрация, достоверный канал, идентификация и аутен-
тификация, целостность системы безопасности, распределение полномочий,
самотестирование, аутентификация при обмене, аутентификация отправителя,
аутентификация получателя); b45 — уровни гарантий (Г1–Г7).
Множество 5B экономических свойств },1{ 555 mjbB j == содержит сле-
дующие элементы: b51 — стоимость оборудования; b52 — стоимость эксплуата-
ции (TCO — Total Cost Ownership); b53 — стоимость услуг, предоставляемых си-
стемой.
Каждое свойство ijb класса iB характеризуется набором показателей
},,1{ ijijkij mkyY == (3)
где ijm — количество показателей для свойства ,ijb которые могут иметь как ко-
личественное, так и качественное представление.
Так, для параметра 21b из множества функциональных свойств 2B будем
иметь следующий набор показателей: y211 — число запросов в минуту; y212 —за-
держка на выполнение запроса (не более чем); y213 — если число запросов больше
заданного (y213), часть запросов отклоняется.
122 ISSN 0572-2691
Требования к количественным показателям задаются с помощью интерваль-
ных оценок вида
,ijkijkijk
yyy (4)
а требования к качественным показателям удобно задать с помощью нечетких
термов [5].
Структурная модель Grid-системы наблюдения Земли
Формализуем описание иерархической системы EO Grid. Результат струк-
турной декомпозиции системы показан на рисунке.
Система
Сегмент 1 Сегмент 2 Сегмент K
Узел
Коммуни-
кационная
сеть
Управля-
ющий узел
Интерконнект
Процессоры
Память
Дисковая Оперативная
Планировщик
Узел
Коммуни-
кационная
сеть
Управля-
ющий узел
Интерконнект
Процессоры
Память
Дисковая Оперативная
Активное
оборудование
Планировщик
Пассивное
оборудование
Активное
оборудование
Пассивное
оборудование
Укрупненно можно выделить следующие уровни иерархии системы EO Grid:
системы, сегментов, узлов и компонентов.
Такое деление на иерархические уровни объясняется следующими соображе-
ниями. Современное состояние развития Grid характеризуется интеграцией от-
дельных региональных или специализированных Grid-систем в более крупные
инфраструктуры, обеспечивающие решение более сложных задач или требующие
использования ресурсов (информационных, вычислительных и т.п.), относящихся
к различным Grid-системам. Поэтому на современном этапе глобализации в каче-
стве системы целесообразно рассматривать Grid-систему, объединяющую различ-
ные специализированные или региональные Grid-системы, которые выступают
в качестве элементов уровня сегментов. К уровню узлов относятся узлы (вычис-
лительные узлы и хранилища), управляющие узлы и коммуникации. В [6] дана
несколько другая классификация элементов Grid-систем, выделены вычислитель-
ные узлы, хранилища данных и коммуникации. Однако опыт автора по разработ-
ке Grid-систем подтверждает целесообразность объединения вычислительных
узлов и хранилищ в одну категорию, поскольку и те, и другие характеризуются
одинаковыми показателями: производительностью процессора, объемом памяти
(дисковой и оперативной) и скоростью работы интерконнекта. Кроме того, пред-
ставляется целесообразным отдельно выделить управляющие узлы, поскольку пе-
речисленные показатели для них не играют существенной роли, а их производи-
тельность определяется эффективностью реализованных алгоритмов планирова-
ния, т.е. зависит не от физических показателей, а от показателей более высокого
(программного) уровня.
В качестве примера можно привести систему WAG (Wide Area Grid), которая
объединяет Grid-системы Института космических исследований (ИКИ) НАН
Украины и НКА Украины, французского космического агентства CNES, Grid Ев-
Проблемы управления и информатики, 2007, № 5 123
ропейского космического агентства (ESA) EO Grid On-Demand, а также китай-
скую Grid-систему наблюдения Земли Spatial Information Grid (SIG). Одной из
прикладных задач, которая ставится в рамках этого проекта, является задача мо-
ниторинга и прогнозирования затоплений (в частности, для территорий Украины
и Китая). Для этого необходимо адаптировать и настроить существующие гидро-
логические и гидравлические модели (каскады моделей) для соответствующих
территорий, что требует использования разнородных данных. При этом исполь-
зуются данные численного моделирования погоды, предоставляемые ИКИ НАН
Украины и НКА Украины; спутниковые радарные данные (Envisat/ASAR), предо-
ставляемые ESA, и созданные на их основе продукты (влажность грунтов, осадки,
маска наводнений); наземные наблюдения (осадки, температура, влажность грун-
тов и т.д.). Кроме того, сам процесс адаптации представляет собой достаточно
сложный поток выполнения (workflow), в рамках которого необходимо решить
сложные задачи оптимизации. Все это влечет за собой необходимость совместно-
го использования вычислительных и информационных ресурсов участвующих ор-
ганизаций и их объединения в Inter-Grid инфраструктуру.
Поскольку каждый сегмент также является Grid-системой, то практически
все свойства системы проявляются на уровне сегментов. Новыми свойствами си-
стемы, возникающими на уровне системы и характеризующими ее эмерджент-
ность, являются:
— гетерогенность (даже если каждый сегмент гомогенен), что на порядок
усложняет взаимодействие между ее компонентами;
— новая, более сложная топология, требующая более сложных алгоритмов
планирования распределения задач;
— возможность решения усложненных глобальных задач на основе интегра-
ции разнородных географически распределенных данных из разных источников,
например создание мозаики спутниковых данных, которые соответствуют разным
географическим регионам и хранятся в архивах разных организаций.
Первые два свойства выдвигают более жесткие требования к управлению по-
добными системами, а последнее определяет несомненные преимущества, оправ-
дывающие ресурсозатраты на реализацию этих жестких требований.
Каждый q-й уровень иерархии состоит из qP функциональных элементов.
Тогда множество всех ФЭ системы можно описать следующим образом:
},,1,,1{ qqp PpNqVV === (5)
где N — общее число уровней иерархии; qpV — p-й ФЭ q-го иерархического
уровня.
Каждый ФЭ qpV системы характеризуется следующим вектором показателей:
),,1( qpqpjqp njx ==x (6)
где qpn — количество показателей ФЭ ,qpV выполняющего набор функций
).,1( qpqpkqp mkf == (7)
Каждая из функций qpkf в (7) зависит от значений показателей вектора qpx
)( qpqpkqpk ff x= (8)
и влияет на реализацию требований, предъявляемых к ФЭ и системе в целом.
124 ISSN 0572-2691
Согласно [1, с. 435] состав и вид функций (7), (8) определяются в процессе
системного анализа.
Пусть
},1,,1,{ NqPpX qqp === x (9)
— обобщенное множество показателей. Для простоты изложения откажемся от
тройной индексации. Будем считать, что общее число показателей всех ФЭ всех
иерархических уровней системы равно .0N Тогда обобщенный вектор показате-
лей можно представить в виде
.,),,,( 0
0
T
21
N
Nxxx Rxx = (10)
Одной из главных задач структурно-функционального анализа является
определение преобразования
YXF →: (11)
из множества Х допустимых показателей системы в пространство Y требуемых
свойств по набору количественных требований, заданных в виде (4), и качествен-
ных требований, заданных в виде нечетких термов.
При этом требуется решить задачу структурно-параметрической идентифи-
кации, позволяющей одновременно определить структуру иерархической си-
стемы в целом, структуру ФЭ всех иерархических уровней, а также вид преоб-
разования (11).
Построение функций производительности
для функциональных элементов EO Grid уровня узлов
Определим векторы показателей для элементов системы уровня компонентов
иерархической Grid-системы EO Grid. Вектор показателей procx для процессоров
будет иметь следующий вид:
),,,( loadfreqarchproc xxx=x (12)
где archx — архитектура процессора, freqx — его частота, loadx — загруженность
процессора (средняя за некоторый период времени).
Функцией производительности процессора будем считать число операций в
секунду, определяемое соотношением
),1()()( loadfreqarchprocproc xxxCf −=x (13)
где )( archxC — некоторая константа, зависящая от архитектуры процессора.
Для оперативной памяти вектор показателей будет иметь вид
),,,( ratevol_totalvolmem xxxx = (14)
где volx — объем свободной памяти в данный момент времени, vol_totalx — общий
объем памяти, ratex — скорость доступа к памяти на чтение и запись.
Введем показатель использования оперативной памяти:
.),(
vol_total
vol
vol_totalvolitymem_usabil
x
x
xxf = (15)
Проблемы управления и информатики, 2007, № 5 125
Тогда функцией эффективности оперативной памяти будем считать величину
)).,(1()( vol_totalvolitymem_usabilratememmem xxfxf −=x (16)
Для дисковых хранилищ вектор показателей имеет следующий вид:
),,,,( vol_totalvolparseqstorage xxxxx = (17)
где xseq — вектор, характеризующий зависимость пропускной способности хра-
нилища от числа одновременных запросов для последовательного (потокового)
доступа, xpar — вектор, характеризующий зависимость пропускной способности
хранилища от числа одновременных запросов для параллельного доступа, xvol —
объем свободного пространства на хранилище в данный момент времени,
vol_totalx — общий объем хранилища.
Аналогично (15) введем показатель использования хранилища:
.),(
vol_total
vol
vol_totalvollitystor_usabi
x
x
xxf = (18)
Пусть queryn ⎯ количество одновременных запросов к хранилищу. Тогда
функция эффективности для хранилища будет иметь следующий вид:
=)( storstor xf
−−−
−−−
=
доступ,ыйпараллельн)),(1]([
доступ,потоковый)),(1]([
vol_totalvollitystor_usabiquerypar
vol_totalvollitystor_usabiqueryseq
xxfnx
xxfnx
(19)
где ][ queryseq nx и ][ querypar nx ⎯ соответствующие компоненты векторов seqx и
parx для заданного количества запросов .queryn
Функция производительности узла, содержащего процессоры, память и ин-
терконнект, мультипликативно зависит от соответствующих функций ФЭ более
низкого уровня:
=)( nodenode xf
−−
−−
=
,хранилища для)()()(
узла, ьноговычислител для)()()(
procconconstorstorprocproc
procconconmemmemprocproc
nfff
nfff
xxx
xxx
(20)
где )( procproc xf — производительность процессора, определяемая выражени-
ем (13); )( memmem xf — функция эффективности оперативной памяти, определя-
емая выражением (16); )( storstor xf — функция эффективности хранилища, опре-
деляемая выражением (19); )()( conconcon xx Cf = — в простейшем случае (при
несущественном обмене данными между процессорами) — некоторая константа,
определяющая влияние интерконнекта на производительность процессоров
(0 С 1); procn — количество процессоров в узле.
Для управляющего узла будем иметь следующий вектор показателей:
,),,,( queuenode_loadnodenode_queuecontrol xxxxx = (21)
126 ISSN 0572-2691
где ),,,( 21node_queue kxxx =x — длина очереди задач на подконтрольных уз-
лах; queuex — длина очереди на управляющем узле; k=nodex — число подкон-
трольных узлов; node_loadx — распределение загруженности подконтрольных уз-
лов (среднее за некоторый период времени).
Тогда функция производительности управляющего узла
)()( controlshedulercontrolcontrol xx Ff = (22)
определяет среднее время обработки запроса. Поскольку управляющие узлы вы-
полняют преимущественно задачи планирования нагрузки в распределенных си-
стемах, функция Fscheduler() зависит от типа выбранного планировщика. В общем
случае задача планирования для вычислительных Grid-систем с репликацией дан-
ных является NP-полной и решается полным перебором вариантов [7], поэтому на
практике вводят некоторые упрощения и используют эвристики. Следовательно,
вычислительная сложность и вид нелинейности функции Fscheduler() определяются
для каждой конкретной системы.
Соотношения (12)–(22) обеспечивают конструктивное представление пре-
образования (11) в соответствии с (4), (6)–(8), но без учета специфики решаемых
задач.
Учитывая высокую стоимость создания Grid-систем, в процессе СФА необ-
ходимо обеспечить рациональный компромисс двух противоречивых целей: до-
биться максимальной производительности системы при минимально возможной
стоимости ее ФЭ. При этом задача нахождения допустимого решения, удовлетво-
ряющего (11), является задачей рационального выбора, поскольку это решение —
лишь одно из возможных решений множества Парето. Для определения наилуч-
ших по некоторому критерию (или набору критериев) характеристик системы
необходимо сформулировать задачу оптимизации.
Сделаем это в общем виде. Пусть индекс i — те показатели свойств, которые
необходимо максимизировать (например, производительность узла, памяти) или
минимизировать (например, стоимость), а j — те показатели, которые должны
удовлетворять некоторым ограничениям. Тогда обобщенная задача оптимизации
формально ставится следующим образом:
extr)( →Xxi xy для каждого ,iy (23)
.)( jXxjj
yxyy (24)
СФА узла с учетом типов решаемых задач
Рассмотрим пример задачи СФА для узла сегмента, решающего в Grid-сис-
теме задачи определенных типов. Введем множество типов программного кода K,
а также индикатор типа для кода: если d — код (последовательность инструкций),
то type(d) ⎯ его тип. Вся задача состоит из частей программного кода различного
типа. Экспериментально можно построить функцию эффективности процессора
при обработке кода определенного типа RArchKw →:1 , где Arch ⎯ архитек-
тура процессора, а R ⎯ множество действительных чисел. Существуют организа-
ции, которые предоставляют таблицы значений таких функций для эталонных за-
дач, которые стали общепризнанными стандартами для оценки производительно-
сти компьютерных систем. Так, организация производителей компьютеров SPEC
(System Performance Evaluation Corporation) [8] публикует результаты исследова-
Проблемы управления и информатики, 2007, № 5 127
ний производительности процессоров, мультипроцессорных систем, файловых
серверов и т.д. При этом в качестве эталонных задач могут использоваться про-
граммы, выполняющие только базовые операции (подобные сложению и умно-
жению, например, программа Dhrystone), модельные задачи (например, решето
Эратосфена и Ханойские башни), ядра (например, программа Linpack) или реаль-
ные прикладные задачи (например, модель численного прогнозирования погоды
Weather Research and Forecasting (WRF)) [2].
Тогда с учетом (13) производительность процессора с частотой rf при за-
грузке z для кода типа k и архитектуры arch равна
)1(),(1cpu zfarchkwf r −= . (25)
Рассмотрим узел, содержащий N процессоров. Пусть производительность
интерконнекта (количество информации, передаваемой между процессорами за
единицу времени) равна .intf Поскольку обработанную процессором информацию
необходимо передавать другим процессорам, при использовании N процессоров
производительность узла не увеличится ровно в N раз. Пусть RArchKw →:2 ⎯
функция, определяющая часть данных, которые необходимо передать между про-
цессорами во время вычислений при выполнении кода единичной (эталонной) дли-
ны типа K. Таблицу значений этой функции можно построить для каждой задачи,
решаемой в системе. Тогда при обработке информации объема C необходимо пере-
дать информацию объема .),(2 =CarchkCw При этом для вычисления производи-
тельности узла (равная количеству обработанных данных) требуется более сложная
формула, чем (20). Количество информации C сначала будет обработано процессо-
ром за время ,/ cpufC затем эта информация должна быть передана другому про-
цессору или узлу за время .intfC Общее время составит .// intcpu fCfC +
Тогда производительность узла с N процессорами, будет иметь следующий вид:
.
1
//
1
intcpuintcpu
proc_ N
fffCfC
CN
fN
−
+=
+
= (26)
Коэффициент требуемой оперативной памяти )(11 Kmm = показывает, сколько
оперативной памяти необходимо использовать для вычисления задачи типа K
единичной длины. Тогда суммарный объем требуемой оперативной памяти, не-
обходимый для решения задачи, равен )),())(((max 1
1
ii
Ii
dsizedtypemS
= где id ⎯
i-я последовательность инструкций кода, )( idsize ⎯ размер кода .id Если такой
объем свободной памяти отсутствует, необходимо использовать виртуальную па-
мять, т.е. память жесткого диска. Соответственно введем коэффициент требуемой
памяти жесткого диска ).(22 Kmm =
Производительность оперативной памяти считается постоянной .constRAM =f
Для вычисления производительности жесткого диска (виртуальной памяти) ис-
пользуем следующий подход. Известно, что производительность жестких дисков
сильно зависит от порядка считывания с него информации. В случае последова-
тельного считывания производительность максимальна, а в случае случайного до-
ступа она может уменьшиться в десятки раз. Очевидно, что расположение данных
на диске и порядок считывания зависят от типизации кода. Таким образом, произ-
водительность жесткого диска является функцией типа кода. Следовательно, полез-
ную производительность памяти определим как ),( prodHDDHDD kxff = ⎯ коли-
чество данных, которое может быть записано/считано с жесткого диска, учитывая
особенности этих запросов и характеристик конкретного диска.
128 ISSN 0572-2691
Вычислим теперь полезную производительность узла. Учитывая, что время ,
потраченное на вычисления, суммируется со временем, потраченным на чте-
ние/запись, получаем, что полезная производительность при обработке кода типа
K равна (как сумма обратных величин)
,
1
1
HDD
2
HDD2
1
HDD1
RAM
2
RAM2
1
RAM1
proc_
node
−
+
+
+
+=
f
mm
f
mm
f
f
N
(27)
где коэффициенты
2,1
RAM и
2,1
HDD иллюстрируют, как используется память. Ко-
эффициент 1
HDD показывает, какая часть данных, которые должны храниться в
оперативной памяти, запишется на диск, 2
HDD — какая часть данных будет хра-
ниться на жестком диске (как и запланировано), 1
RAM — какая часть данных бу-
дет храниться в оперативной памяти (как и запланировано), 2
RAM — какая часть
данных, предназначенных для хранения на жестком диске, будет храниться в опе-
ративной памяти (при использовании кэширования). Таким образом, учитывается
возможность использования виртуальной памяти и кэширования. При этом
11
HDD
1
RAM =+ и .12
HDD
2
RAM =+
Постановка задач оптимизации
На основе полученных аналитических соотношений для показателей и про-
изводительности ФЭ разных иерархических уровней сформулируем некоторые
возможные задачи оптимизации производительности и структуры EO Grid.
Детерминированная формулировка прямой задачи. Дано:
— конечное множество пар ,),( 1
n
iii KS = представляющее деление кода на
участки с одинаковой типизацией;
— вектор показателей X и функции производительности узла (всех его
функциональных элементов) f.
Необходимо определить максимальную производительность данного узла
для данной нагрузки (типов решаемых задач) и соответствующее распределение
памяти при этом.
Формально эту задачу можно представить в виде задачи оптимизации функ-
ции производительности узла:
max))(1(
)(
)()()()(
)(
)()()()(
)(
1
1
HDD
2
HDD2
1
HDD1
RAM
2
RAM2
1
RAM1
1
node
→
−
+
+
+
+
+=
−
=
iq
if
iimiim
if
iimiim
if
f
n
i
или в эквивалентном виде
+
+
+
= )(
)()()()(
)(
1
RAM
2
RAM2
1
RAM1
1 if
iimiim
if
n
i
min))(1(
)(
)()()()(
HDD
2
HDD2
1
HDD1 →−
+
+ iq
if
iimiim
(28)
Проблемы управления и информатики, 2007, № 5 129
при следующих ограничениях для каждого :,1 ni =
,1)()( 1
HDD
1
RAM =+ ii dd (29)
,1)()( 2
HDD
2
RAM =+ ii dd (30)
,1)(0 1
RAM id (31)
,1)(0 1
HDD id (32)
,1)(0 2 iRAM d (33)
,1)(0 2 iHDD d (34)
где q(i) ⎯ поправка на пространственную распределенность данных, используе-
мых при исполнении участков кода id и 1−id (предполагается ).0)0( =q Поправ-
ка возникает из-за того, что часть данных, используемых на участке ,id занесена
в память на участке .1−id Важно также помнить, что )(iq зависит не только от
)(2,1
RAM
i и ),(2,1
HDD i но и от ),1(2,1
RAM − i и ).1(2,1
HDD − i
После решения задачи оптимизации получаем значения коэффициентов
2,1
RAM и ,2,1
HDD которые определяют наиболее эффективное использование ре-
сурсов памяти узла, а само значение nodef является искомым значением произво-
дительности узла.
Учитывая физические ограничения на минимально возможный сегмент исполь-
зуемой памяти и дискретный характер разбиения дискового пространства, можно
заключить, что задача (28) при ограничениях (29)–(34) является задачей дискрет-
ной оптимизации. Для решения таких задач разработан специальный математиче-
ский аппарат. Хорошие результаты при решении задач дискретной оптимизации
дают эволюционные вычисления, в частности генетические алгоритмы [9].
Вероятностная формулировка прямой задачи. Пусть дано некоторое ко-
нечное множество задач, выполняемых в Grid-системе. На этом множестве задано
распределение, определяющее вероятность запуска той или иной задачи. Пусть
такое распределение реализуется некоторой случайной величиной . Тогда веро-
ятность запуска задачи j равна .,1,}{ mjpjP j ===
Дано:
— случайная дискретная величина с функцией распределения ,}{ jpjP ==
;,1 mj =
— множество пар ,}),{( 1
)(
1,,
m
j
jn
ijiji KS ==
представляющее деление кода на
участки с одинаковой типизацией;
— вектор показателей X и функции производительности узла (всех его
функциональных элементов) f.
Необходимо определить оптимальное значение производительности данного
узла для заданной случайной программной загрузки.
130 ISSN 0572-2691
Формально задача сводится к задаче оптимизации:
max,)(
1
nodnode →=
=
m
j
je pjff (35)
при следующих ограничениях для каждого :)(,1 jni =
,1)()( ,
1
HDD,
1
RAM =+ jiji dd (36)
,1)()( ,
2
HDD,
2
RAM =+ jiji dd (37)
,1)(0 ,
1
RAM jid (38)
,1)(0 ,
1
HDD jid (39)
,1)(0 ,
2
RAM jid (40)
.1)(0 ,
2
HDD jid (41)
Здесь
+
+
+=
= )(
)()()()(
)(
1
)(
RAM
2
RAM2
1
RAM1
)(
1
node
lf
llmllm
lf
jf
jn
i
,))(1(
)(
)()()()(
1
HDD
2
HDD2
1
HDD1
−
−
+
+ lq
lf
llmllm
(42)
а под l следует понимать запись ).,( ji
Решение задачи оптимизации nodef и определяет искомое значение произ-
водительности узла, а точнее, его математическое ожидание.
Формулировка обратной задачи. В обратной задаче требуется определить
конфигурацию самого дешевого вычислительного узла, производительность ко-
торого не меньше заданной. Для начала определим стоимость узла. Как было по-
казано ранее, узел содержит память (жесткий диск, оперативную память), процес-
соры, а также интерконнект. Для каждой составляющей определена функция сто-
имости price(). Стоимость узла можно считать равной сумме стоимостей его
компонентов (несущественные элементы, в частности, корпус, можно не учи-
тывать). Будем считать, что компоненты выбираются из заранее заданного
списка, в котором хранятся функциональные характеристики и стоимость. Не
стоит забывать, что не все возможные комбинации ФЭ реализуемы. Для этого
введем проверку совместимости компонентов в виде булевой функции
},1,0{: →Zc принимающей значение 1, если данная конфигурация из множества
Z возможна, и 0 ⎯ в противном случае. Значения функциональных элементов вы-
числяются с помощью функции .: XZv → При этом множество Z характеризует
возможные типы компонентов.
Пусть заданы множества компонентов M1 (оперативная память), M2 (жесткие
диски или другие накопители), P (процессоры), I (интерконнекты). Введем опера-
Проблемы управления и информатики, 2007, № 5 131
цию AAAAU = }{ . Тогда .21 IPMMZ UUU = Введем множе-
ство подходящих конфигураций },))((,1)(,{)( node xzvfzcZzzxG == где x ⎯
заданная (предельная) производительность узла. Тогда для решения обратной за-
дачи необходимо минимизировать функцию
price(z) → min при ).(xGz (43)
При этом значение
))((minarg
)(
zpricez
xGz
= (44)
определяет искомую конфигурацию узла.
Очевидно, что данная задача тоже является задачей дискретной оптимизации,
поэтому ее удобно решать с помощью эволюционных вычислений, в частности
генетических алгоритмов [9].
Недетерминированный случай легко получить, заменяя nodef на nodef .
Выводы
В данной статье реализован системный подход к построению и анализу
функционирования Grid-систем. Построена иерархическая структурная модель
Grid-системы наблюдения Земли, объединяющей несколько региональных и спе-
циализированных Grid-систем. На основе структурно-функционального анализа
слабо формализованная задача оптимизации структуры и производительности уз-
ла сложной иерархической системы сведена к ряду задач дискретной оптимиза-
ции, имеющих конструктивное решение. Из-за высокой стоимости компонентов
Grid-систем такая формализация играет важную роль при разработке новых си-
стем и модернизации существующих, поскольку позволяет снизить уровень субъ-
ективизма при выборе конфигурации компонентов конкретных систем. Важным
преимуществом развиваемого подхода по сравнению с другими работами, посвя-
щенными моделированию и оценке производительности распределенных систем,
является системность, базирующаяся на методе СФА [1] и позволяющая рассмат-
ривать сложные иерархические системы на разных уровнях детализации одно-
временно.
Развиваемый подход апробирован при построении реальной Grid-системы
наблюдения Земли, разрабатываемой при непосредственном участии автора в
рамках научно-технических проектов НАН Украины и международных грантов.
В частности, на основе этого подхода определена конфигурация вычислительных
узлов и хранилища украинского сегмента вышеупомянутой системы WAG, объ-
единяющей ресурсы космических агентств Европы, Франции, Китая и Украины.
В дальнейшем этот подход планируется развить для других элементов уровня уз-
лов, а именно, для управляющих узлов и коммуникационной сети, а также для бо-
лее высоких иерархических уровней Grid-системы наблюдения Земли.
А.Ю. Шелестов
СТРУКТУРНО-ФУНКЦІОНАЛЬНИЙ АНАЛІЗ
КОМПОНЕНТІВ GRID-СИСТЕМ
Запропоновано реалізацію системного підходу до побудови та аналізу функціо-
нування Grid-систем. Побудовано ієрархічну структурну модель Grid-системи
спостереження Землі, що об’єднує декілька регіональних та спеціалізованих
132 ISSN 0572-2691
Grid-систем. На основі проведеного структурно-функціонального аналізу сла-
бо формалізовану задачу оптимізації структури та продуктивності вузла
складної ієрархічної системи зведено до ряду задач дискретної оптимізації.
Запропонований підхід апробовано при побудові реальної Grid-системи спо-
стереження Землі.
А.Yu. Shelestov
STRUCTURAL-FUNCTIONAL ANALYSIS
OF THE GRID-SYSTEM COMPONENTS
Implementation of the system approach to design and analysis of the Grid-system
functioning is proposed. It is constructed an hierarchical structural model of the Earth
observation Grid-system consisted of several regional and specialized Grid-systems.
On the basis of structural-functional analysis the weakly formalized problem of the
structure and productivity optimization of the node of complex hierarchical system is
reduced to a number of discrete optimization problems. Proposed approach was ap-
proved while real Earth observation Grid-system design.
1. Згуровский М.З., Панкратова Н.Д. Системный анализ: проблемы, методология, приложе-
ния. — Киев : Наук. думка, 2005. — 744 с.
2. Менаске Д., Алмейда В. Производительность Web-служб. Анализ, оценка и планирова-
ние. — Киев : ДиаСофт, 2003. — 480 с.
3. Шелестов А.Ю. Объектная модель задач в Grid-системе обработки спутниковых данных //
Сб. науч. тр. Донецкого нац. техн. ун-та «Інформатика, кібернетика і обчислювальна техні-
ка». — 2007. — Вып. 8. — С. 317–330.
4. НД ТЗІ 2.5-004-99 «Критерії оцінки захищеності інформації в комп’ютерних системах від
несанкціонованого доступу». — Київ : ДСТЗІ, 1999. — 20 c.
5. Zadeh L. Fuzzy sets // Inform. and Control. — 1965. — 8. — 338 p.
6. Krauter K., Buyya R., Maheswaran M. A taxonomy and survey of GRID resource management
systems and distributed computing // Software-Practice and Experience. — New York : John
Wiley & Sons, Ltd., 2001. — P. 1–10.
7. Desprez F., Vernois A. Simultaneous scheduling of replication and computation for data-intensive
applications on the Grid // J. of Grid Comput. — 2006. — 4. — P. 19–31.
8. System performance evaluation corporation. — www.spec.org.
9. Fogel D.B. Evolutionary computation: toward a new philosophy of machine intelligence. — New
York : IEEE Press, 1995. — 272 p.
Получено 10.08.2007
http://www.spec.org/
|