Способ выбора алгоритма разбиения графа для распределенных вычислений
Предложен способ определения потенциально наиболее эффективного алгоритма разбиения заданного графа для распределенных вычислений, который опирается на результаты анализа статистической зависимости величины получаемого разреза (для того или иного алгоритма разбиения графа) от метрик графа. Экспериме...
Saved in:
| Published in: | Математичні машини і системи |
|---|---|
| Date: | 2011 |
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем математичних машин і систем НАН України
2011
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/83622 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Способ выбора алгоритма разбиения графа для распределенных вычислений / В.А. Иващенко, Р.Ю. Лопаткин, В.В. Куприенко // Мат. машини і системи. — 2011. — № 4. — С. 31-38. — Бібліогр.: 8 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860265197839581184 |
|---|---|
| author | Иващенко, В.А. Лопаткин, Р.Ю. Куприенко, В.В. |
| author_facet | Иващенко, В.А. Лопаткин, Р.Ю. Куприенко, В.В. |
| citation_txt | Способ выбора алгоритма разбиения графа для распределенных вычислений / В.А. Иващенко, Р.Ю. Лопаткин, В.В. Куприенко // Мат. машини і системи. — 2011. — № 4. — С. 31-38. — Бібліогр.: 8 назв. — рос. |
| collection | DSpace DC |
| container_title | Математичні машини і системи |
| description | Предложен способ определения потенциально наиболее эффективного алгоритма разбиения заданного графа для распределенных вычислений, который опирается на результаты анализа статистической зависимости величины получаемого разреза (для того или иного алгоритма разбиения графа) от метрик графа. Эксперименты по использованию предложенного способа перед началом расчетов демонстрируют его эффективность в повышении быстродействия распределенной программы.
Запропоновано спосіб визначення потенційно найбільш ефективного алгоритму розбиття заданого графа для розподілених обчислень, який спирається на результати аналізу статистичної залежності величини розрізу, що отримується (для того або іншого алгоритму розбиття графа) від метрик графа. Експерименти щодо використання запропонованого способу перед початком розрахунків демонструють його ефективність у підвищенні швидкодії розподіленої програми.
A method of definition of the most effective partition algorithm of a specified graph for distributed calculation based on the analytical data of statistical dependence between the received value (for one or another graph partition algorithm) and graph metric is suggested. The experiments on the method mentioned above before the calculations demonstrate its efficiency in improving the performance of distributed applications.
|
| first_indexed | 2025-12-07T18:59:54Z |
| format | Article |
| fulltext |
© Иващенко В.А., Лопаткин Р.Ю., Куприенко В.В., 2011 31
ISSN 1028-9763. Математичні машини і системи, 2011, № 4
УДК 519.8, 519.6
В.А. ИВАЩЕНКО, Р.Ю. ЛОПАТКИН, В.В. КУПРИЕНКО
СПОСОБ ВЫБОРА АЛГОРИТМА РАЗБИЕНИЯ ГРАФА ДЛЯ РАСПРЕДЕЛЕННЫХ
ВЫЧИСЛЕНИЙ
Анотація. Запропоновано спосіб визначення потенційно найбільш ефективного алгоритму роз-
биття заданого графа для розподілених обчислень, який спирається на результати аналізу ста-
тистичної залежності величини розрізу, що отримується (для того або іншого алгоритму роз-
биття графа) від метрик графа. Експерименти щодо використання запропонованого способу пе-
ред початком розрахунків демонструють його ефективність у підвищенні швидкодії розподіленої
програми.
Ключові слова: прогнозування, оптимізація швидкодії, розбиття графа, метрики графів, розподі-
лені обчислення.
Аннотация. Предложен способ определения потенциально наиболее эффективного алгоритма
разбиения заданного графа для распределенных вычислений, который опирается на результаты
анализа статистической зависимости величины получаемого разреза (для того или иного алго-
ритма разбиения графа) от метрик графа. Эксперименты по использованию предложенного спо-
соба перед началом расчетов демонстрируют его эффективность в повышении быстродействия
распределенной программы.
Ключевые слова: прогнозирование, оптимизация производительности, разбиение графа, метрики
графов, распределенные вычисления.
Abstract. A method of definition of the most effective partition algorithm of a specified graph for distri-
buted calculation based on the analytical data of statistical dependence between the received value (for
one or another graph partition algorithm) and graph metric is suggested. The experiments on the method
mentioned above before the calculations demonstrate its efficiency in improving the performance of dis-
tributed applications.
Keywords: forecasting, performance optimizing, graph partition, graph metrics, distributed calculation.
1. Введение
Постановку задачи поиска минимального разбиения (иногда употребляется термин «ми-
нимальный разрез») графа можно сформулировать следующим образом. Пусть дан неори-
ентированный невзвешенный граф ),( EVG = , где V – множество его вершин, E – множе-
ство ребер этого графа. Необходимо разделить множество V на k непересекающихся
подмножеств ),...,( 1 kVVV = ( ∅=ji VV I , i∀ , kj ..1= , ji ≠ ; kVVV UU ...1= ) таким обра-
зом, чтобы выполнялось условие
→
≥
∑ +=−=
=∀
ji
ji
i
kijki
ki
VVcut
BB
,
*
,..1,1..1,
,..1,
min),(
)min(
(1)
где VVB ii /= ;
),( ji VVcut – метрика, обозначающая количество ребер, соединяющих вершины из мно-
жества iV с вершинами из множества jV (далее будем использовать термин «величина
разреза» для ее обозначения). Очевидно, что kB /10 * ≤≤ . Как правило, ставится строгое
ограничение kB /1* = , но допускается отклонение *B на малую величину от максимально
возможного: ]/1;/1[* kkB ε−∈ (например, если количество вершин графа нечетное, то пер-
вое условие выполнить невозможно).
32 ISSN 1028-9763. Математичні машини і системи, 2011, № 4
Рассмотрим только частный случай задачи (1) при 2=k , т.е. так называемую зада-
чу половинного разбиения графа (англ. Graph bipartition problem):
→
≈
.min),( 21
21 ,
VVcut
VV
Следует отметить, что решение более общей задачи )2( >k можно находить рекур-
сивно, используя половинное разбиение графа [1].
Задача (1) имеет важное практическое применение в области параллельных вычис-
лений, где особое внимание уделяется скорости вычислений, хотя, например, при проекти-
ровании печатных плат [2] фактор скорости не является критичным.
К сожалению, единственный известный алгоритм, позволяющий находить точное
решение рассматриваемой задачи (1), – это алгоритм решения путем перебора всех воз-
можных разбиений графа, сложность которого растет как ( )nkO , где k – количество ком-
понент, а n – размер компоненты [1, 3]. По этой причине разработано достаточно большое
количество эвристических алгоритмов, решающих задачу разбиения графа с определенной
точностью (качеством) за приемлемое время. Если говорить об абсолютной оценке точно-
сти, то это теоретическая оценка: cc −= *ε , где *c – точное значение минимального разре-
за графа, а c – величина разреза, полученного с помощью алгоритма. Но на практике, если
необходимо сравнить качество двух алгоритмов, то обычно сравнивают метрики, которые
характеризуют разбиения, получаемые с помощью каждого из этих алгоритмов [4]. На-
пример, это может быть величина разреза ∑=
ji
ji VVcutGc
,
),()( . Будем говорить, что один
алгоритм более качественный, чем другой, если для одного и того же графа он позволяет
найти разрез меньшей величины, чем другой алгоритм.
Естественно, что каждый алгоритм имеет свои характеристики, влияющие на каче-
ство получаемого разбиения (точность алгоритма) и его быстродействие [1]. Значения этих
характеристик варьируются для каждого из алгоритмов применительно к определенным
классам графов. Следовательно, выбранный алгоритм разбиения графа для распределен-
ных (параллельных) вычислений имеет существенное влияние на общее время выполнения
всей программы. Поэтому на практике возникает вопрос: выбор какого алгоритма обеспе-
чит наилучшее конечное быстродействие программы? Как правило, выбор алгоритма про-
исходит по каким-либо субъективным предпочтениям исследователя или подбирается эм-
пирическим путем, что не всегда приводит к наилучшему результату. Основная задача ис-
следования, описанного в данной статье, заключается в поиске критерия выбора опти-
мального алгоритма разбиения графа. Такой критерий можно получить на основе сравни-
тельного анализа математических моделей процессов выполнения параллельной програм-
мы при условии, что в каждом из них используется свой конкретный алгоритм разрезания
графа для распараллеливания вычислений.
Для решения поставленной задачи нами разработан способ определения потенци-
ально наиболее эффективного алгоритма разбиения для заданного графа. В нем использу-
ются результаты анализа статистической зависимости величины получаемого разреза (с
помощью того или иного алгоритма) от определенных метрик графа. На основании этих
данных имеется возможность прогнозирования ожидаемого разбиения графа, который в
свою очередь можно использовать как параметр модели для прогнозирования быстродей-
ствия распределенной программы.
ISSN 1028-9763. Математичні машини і системи, 2011, № 4 33
2. Обзор методов
Выделяют следующие основные классы методов прогнозирования быстродействия рас-
пределенной программы:
1. Аналитико-статистические методы. Это класс неточных методов, который ис-
пользуется скорее для грубой оценки времени выполнения программы (в виде подсказки).
2. Прогнозирование на основе профилирования. Эти методы предполагают сбор
данных о производительности программы во время ее выполнения и прогнозирование ее
быстродействия на основе этих данных.
3. Методы имитационного моделирования. Методы этой группы предполагают раз-
работку имитационной модели программы и прогнозирование быстродействия путем
«проигрывания» этой модели [5]. В этих методах может использоваться история статисти-
ческих данных времени вычислений.
4. LINPACK-тесты. Данные методы можно применить как для определения произ-
водительности вычислительной техники, так и для прогнозирования времени выполнения
параллельной программы.
Отметим, что точность методов прогноза растет в порядке их перечисления – от
первой до четвертой группы, однако их скорость, наоборот, уменьшается. Методы, кото-
рые используют в прогнозировании, данные времени вычислений однозначно не подходят
для решения рассматриваемой задачи из-за того, что выбор алгоритма необходимо сделать
еще до начала вычислений. В этом случае вполне подходящим может быть аналитико-
статистический метод, поскольку, во-первых, он позволяет делать прогноз быстродействия
программы до ее выполнения, а во-вторых, при сравнении производительности двух алго-
ритмов можно получить более точный ответ, чем при прогнозировании времени работы
каждого из них по отдельности. Это возможно за счет того, что в данном случае можно не
включать в модель некоторые (не влияющие на преимущество алгоритма) характеристики
вычислительной системы, что позволит также исключить их влияние на общую ошибку
вычислений.
Таким образом, данный подход обеспечит возможность быстро определять (осно-
вываясь на метриках графа, которые можно довольно быстро посчитать, возможно, в па-
раллельном потоке во время считывания графа), какой из алгоритмов для заданного графа
обеспечит наилучшее быстродействие всей параллельной программы.
3. Основная часть
Согласно [6], время выполнения параллельной программы можно представить в виде
функции от характеристик используемой вычислительной техники, среды исполнения и
характеристик самой параллельной программы. Поскольку в рассматриваемой задаче во-
прос состоит в том, чтобы выбрать лучший алгоритм разбиения графа (как составную
часть программы) для исполнения на одной и той же машине, то необходимо выбирать тот
алгоритм, для которого значение этой функции минимальное. Как будет показано дальше,
влияние некоторых величин имеет один и тот же вклад в случае использования любого из
алгоритмов и поэтому при сравнении может быть сокращено (исключено из модели), как
не влияющей на преимущество любого из алгоритмов.
Время работы параллельной программы с учетом затрат времени на разбиение гра-
фа можно представить в виде следующей модели:
∑+=+= imainpr TTTTT 00 , (2)
где prT – общее время работы программы;
0T – время, затраченное на разбиение графа (этап распараллеливания программы);
34 ISSN 1028-9763. Математичні машини і системи, 2011, № 4
Рис. 1. Зависимость быстродействия
параллельной программы от выбора
алгоритма разбиения графа
mainT – время работы основной части программы (собственно вычислений, для ускоре-
ния которых проводилось разбиение графа);
iT – время вычислений на i -м шаге основной программы.
Время, затрачиваемое на выполнение одного шага параллельной программы, можно
представить как [6]
,)()()( iwaiticalcicomi TTTT ++=
где )(icomT – суммарное время передачи и приема данных по каналам связи на i -м шаге;
)(icalcT – суммарное время, затраченное на пересчет всех вершин одним процессом;
)(iwaitT – суммарное время ожидания процессами друг друга на i -м шаге.
Более подробно распишем время, затрачиваемое на осуществление одного шага
программы, учитывая, что временем задержек можно пренебречь:
pxVwcvTTTT iwaiticalcicomi ⋅⋅+⋅=++= 2/)()()( , (3)
где v – объем передаваемых данных (байт), w – скорость передачи данных по каналу свя-
зи (б/с), p – производительность (оп/с), x – количество операций, выполняемых при пе-
ресчете одной вершины графа. То есть, произведем некоторые упрощения: будем считать,
что для пересчета любой из вершин необходимо выполнить одно и то же количество опе-
раций.
Рассмотрим два абстрактных алгоритма: 1A с характеристиками ),( 110 cT – время
выполнения и величина получаемого с его помощью разреза соответственно, 2A с харак-
теристиками ),( 220 cT . Допустим, что
2010 TT < , но 21 cc > . (4)
То есть, алгоритм 2A дает более качественный разрез, чем 1A , но за большее время.
Рассмотрим случай, когда constTi = . Тогда формула (2) принимает вид
ipr TNTT ⋅+= 0 , где N – количество шагов основной части программы. ipr TNTT 1101 ⋅+= –
время работы параллельной программы при условии использования алгоритма 1A , а
ipr TNTT 2202 ⋅+= – время работы параллельной программы при условии использования
алгоритма 2A .
Согласно (3), при выполнении условия (4) ii TT 21 > , что делает возможным выпол-
нение равенства ii TNTTNT 220110 ⋅+=⋅+ . Решая его
относительно переменной N , получаем
ii TT
TT
N
21
1020*
−
−= (5)
– номер шага, начиная с которого программа, где ис-
пользован более медленный, но более качественный
алгоритм разрезания графа, начинает опережать по
быстродействию программу, в которой использован
более быстрый, но менее качественный алгоритм
(рис. 1).
На данном рисунке 0N – нулевой шаг про-
граммы (время завершения алгоритма разбиения
ISSN 1028-9763. Математичні машини і системи, 2011, № 4 35
графа). В соответствии с данной моделью, в зависимости от количества итераций про-
граммы, имеет смысл выбрать тот или иной алгоритм.
Подставляя (3) в (5), получаем
)(
)(
)2/()2/( 21
1020
21
1020*
ccv
wTT
pxVwcvpxVwcv
TT
N
−
⋅−=
⋅⋅+⋅−⋅⋅+⋅
−= .
Согласно данной модели, *N зависит от разницы времени выполнения алгоритмов
разбиения графа, пропускной способности сети (канала коммуникации процессоров), объ-
ема передаваемых данных и разницы величин разрезов, получаемых с помощью этих алго-
ритмов. Время выполнения алгоритма зависит от производительности конкретной вычис-
лительной машины и может быть записано как poT /= , где o – оценка количества опе-
раций, совершаемых алгоритмом разбиения графа. Получаем
)(
)(
21
12*
ccvp
woo
N
−⋅
⋅−= . (6)
Чтобы иметь возможность прогнозировать *N , необходимо получить оценки вели-
чин 1o , 2o , 1c , 2c , а также характеристики вычислительной техники – w , p . Для получе-
ния эмпирических зависимостей величины разреза )(c и количества операций )(o от мет-
рических характеристик графа [7] необходимо сделать оценку математического ожидания
количества операций ][oM и получаемого разреза ][cM .
Чтобы найти эти оценки, было проведено по 60 экспериментов с использованием
каждого из двух алгоритмов Levelized Nested Dissection (LND) [1] и Greedy Graph Growing
Partitioning Algorithm (GGGP) [8]. (Такой выбор был не случайным, поскольку, как извест-
но, второй из них имеет более высокую сложность по сравнению с первым, но качество его
аппроксимации лучше). В экспериментах в качестве метрик использовались размер графа
Vsz = и средняя степень вершины (связность) графа ∑
=−⋅
=
szji
jiG
szsz
con
,1,
,)1(
1
[7]. По-
скольку остальные метрики графа, которые могут повлиять на результат, не рассматрива-
лись, то на экспериментальные данные был наложен ряд ограничений, сводящий к мини-
муму влияние других метрик:
1) равномерное распределение ребер графа;
2) равномерная связность: степень всех вершин графа должна быть примерно оди-
наковая.
Рис. 2. Усредненная зависимость величи-
ны получаемого разреза (c) от связности
(con) и размера графа (sz) для алгоритма
LND
Рис. 3. Преимущество алгоритма GGGP
над LND
36 ISSN 1028-9763. Математичні машини і системи, 2011, № 4
Результаты экспериментов для каждого из алгоритмов – это табличные данные
),( szconci . Область, в которой проводились эксперименты: }1,...,2.0,1.0{∈con U
}010mod],210;10[{ =∈∈ iisz . На рис. 2 на примере алгоритма LND показана усредненная
зависимость величины разреза от связности и размера графа.
Согласно этому графику, величина разреза c растет при росте размера графа sz и
его связности con .
На рис 3. показана зависимость ))(,,())(,,(),( 2121 GconVAcGconVAcAAd −= – раз-
ности усредненных значений разрезов от связности графа и его размера, получаемых с по-
мощью алгоритмов LND и GGGP.
Полученный результат можно объяснить тем, что если связность графа стремится к
нулю )0( →con , то и величина разреза, получаемого при использовании каждого из алго-
ритмов, стремится к нулю. А разница нулей равна нулю. Аналогично, если связность графа
стремится к единице )1( →con , то и величина нормированного разреза, получаемого при
помощи каждого из алгоритмов, тоже стремится к единице, поскольку, как известно, лю-
бой разрез полного графа равен максимальному разрезу этого графа. А разница единиц
равна нулю. Кроме того, имеет место рост разницы разрезов с ростом размера графа. Это
можно объяснить тем, что соотношение разрезов может оставаться приблизительно одина-
ковым, но при этом будет иметь место рост разницы ненормированных значений разрезов.
Таким образом, можно сделать вывод, что при максимально и минимально возможных
связностях все алгоритмы разбиения графов дают практически одинаковые результаты, а
также, чем больше размер графа, тем больший выигрыш в абсолютной величине разреза
получаем с помощью более качественного алгоритма.
После этого была осуществлена аппроксимация усредненных данных поверхностя-
ми, представляющими собой произведение полиномов. Выбирается именно суперпозиция
полиномов, поскольку по своей природе величина разреза зависит полиномиально как от
размера графа, так и от его связности. Для обоих рассмотренных алгоритмов аппроксима-
ция полиномом четвертого порядка обеспечивает достаточную точность приближения.
Например, 1c и 2c можно выразить в виде следующих полиномиальных оценок:
+⋅⋅+⋅⋅+⋅−⋅+⋅−= 22
1 236,0115,0355,0649,2986,3855,1),(~ conszszconszconconszconc
225225 107,225,0105,3 conszconszsz ⋅⋅⋅−⋅⋅+⋅⋅+ −− ,
−⋅⋅+⋅⋅−⋅−⋅−⋅+= 22
2 311,3305,30.26036.35136.2303.947),(~ conszszconszconconszconc
2222 018,0233,0002,0 conszconszsz ⋅⋅+⋅⋅+⋅− .
Значение каждой из них – прогноз ожидаемого разреза для графа размером sz вер-
шин и связностью con .
Аналогично были найдены оценки необходимого количества операций для каждого
рассмотренного алгоритма (рис. 4):
36,235577,20308,0946,0)(~ 23
1 +⋅−⋅−⋅= nnnno – оценка необходимого количества
операций для GGGP;
969,12868,12255,2)(~ 2
2 −⋅+⋅= nnno – оценка необходимого количества операций
для LND.
Итак, в качестве параметров модели используются:
1) метрики входного графа G ;
2) предполагаемое количество шагов основной программы – N .
При соблюдении описанных выше ограничений можно воспользоваться следующи-
ми правилами для выбора наиболее оптимального алгоритма разбиения графа:
ISSN 1028-9763. Математичні машини і системи, 2011, № 4 37
– если необходимо сделать выбор в пользу одного из двух алгоритмов, то можно
просто воспользоваться решением уравнения (6);
– если количество алгоритмов больше двух, то необходимо выбирать тот из них,
для которого значение )2/(00 pxVwcvNTTNT i ⋅⋅+⋅+=⋅+ минимальное. Причем в таком
случае часть этого выражения pxV ⋅⋅2 можно приравнять нулю, поскольку она вносит
одинаковый вклад для любого из алгоритмов.
Рис. 4. Зависимость количества операций, выполняемых алгоритмом разбиения
графа, от размера графа
4. Экспериментальная проверка
Была проведена проверка предло-
женного способа выбора алгоритма
на примере элементарной програм-
мы, реализованной с использовани-
ем MPI-технологии. Сначала вход-
ной граф был разбит с помощью
алгоритма LND и измерено время
выполнения параллельной про-
граммы, потом точно такие же дей-
ствия были выполнены с использо-
ванием алгоритма GGGP. Результат
одного из экспериментов с этой
программой показан на рис. 5.
Спрогнозированный момент
времени, когда программа, исполь-
зующая LND, опередит программу, использующую GGGP, равен 7,993. После серии экс-
периментов полученное экспериментальным путем и усредненное 7,429* =N , что доста-
точно хорошо согласуется с прогнозируемым результатом.
5. Выводы
Прогнозирование влияния выбранного алгоритма разбиения графа на время выполнения
параллельной программы является актуальной и важной практической задачей. Расчеты
показали, что основное влияние на общее время выполнения параллельной программы
0
20000
40000
60000
80000
1000
120000
0 50 100 150 20
0
250
o2(n)
n
0
1000000
2000000
3000000
4000000
5000000
6000000
7000000
8000000
9000000
0 50 1 150 200 250
1000000
0
o1(n)
n
Рис. 5. Сравнение быстродействия параллельной
программы при использовании различных
алгоритмов разбиения графа
38 ISSN 1028-9763. Математичні машини і системи, 2011, № 4
имеют две основные характеристики алгоритма разбиения графа: время его выполнения и
«качество» его работы. А для конкретного графа и алгоритма разбиения графа не очевидна
ни оценка этих характеристик, ни их влияние на общее время выполнения параллельной
программы.
По результатам исследований предложен способ выбора алгоритма разбиения графа
для распараллеливания вычислений в зависимости от метрических характеристик графа.
Основным достоинством и перспективностью применения такого подхода есть возмож-
ность прогнозирования эффективности выполнения параллельных программ без необхо-
димости их предварительного выполнения. Это, в свою очередь, позволяет ускорять время
работы этих программ за счет выбора оптимального алгоритма для разбиения задачи на
подзадачи.
На данный момент предложенный способ применим для узкого класса графов, у ко-
торых ограничением является равномерная связность (примерно одинаковая степень каж-
дой из вершин графа). В дальнейшем нами планируется расширить применимость предло-
женного способа путем введения дополнительных метрик, а также провести более глубо-
кие исследования точности предложенного подхода.
СПИСОК ЛИТЕРАТУРЫ
1. Schloegel K. Graph partitioning for high-performance scientific simulations / K. Schloegel, G. Karypis,
V. Kumar // Sourcebook of parallel computing. – Morgan Kaufmann Publishers Inc., 2003. – P. 491 –
541.
2. Caldwell A.E. Design and Implementation of the Fiduccia-Mattheyses Heuristic for VLSI Netlist
Partitioning / A.E. Caldwell, A.B. Kahng, I.L. Markov// Lecture Notes in Computer Science. – Springer,
1999. – Р. 182 – 198.
3. Srikant Y.N. The compiler design handbook: optimizations and machine code generation / Y.N. Srikant,
P. Shankar. – CRC Press, 2008. – 784 p.
4. Hendrickson В. Graph partitioning models for parallel computing / B. Hendrickson, T.G. Kolda // Par-
allel Computing. – 2000. – N 26 (12). – Р. 1519 – 1534.
5. Simulaton-based performance prediction for Large Parallel Machines / G. Zheng, T. Wilmarth,
P. Jagadishprasad [et al.] // International Journal of Parallel Programming. Special issue: The next
generation software program. – 2005. – Vol. 33, Is. 2. – Р. 183 – 207.
6. Performance Prediction Methods /A. Szymańska-Kwiecień, J. Kwiatkowski, M. Pawlik [et al.] // Proc.
of the International Multiconference on Computer Science and Information Technology. – Wisła, 2006. –
P. 363 – 370.
7. Субъективные метрики оценки онтологий / Т.А. Гаврилова, В.А. Горовой, Е.С. Болотникова
[и др.] // Материалы Всероссийской конф. с междунар. участием «Знания-Онтологии-Теории»
(ЗОНТ-2009). – Новосибирск: Институт математики СО РАН, 2009. – Т. 1. – С. 178 – 186.
8. Karypis G. A fast and high quality multilevel scheme for partitioning irregular graphs / G. Karypis,
V. Kumar // SIAM Journal on Scientific Computing. – 1999. – Vol. 20, N 1. – Р. 359 – 392.
Стаття надійшла до редакції 01.06.2011
|
| id | nasplib_isofts_kiev_ua-123456789-83622 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1028-9763 |
| language | Russian |
| last_indexed | 2025-12-07T18:59:54Z |
| publishDate | 2011 |
| publisher | Інститут проблем математичних машин і систем НАН України |
| record_format | dspace |
| spelling | Иващенко, В.А. Лопаткин, Р.Ю. Куприенко, В.В. 2015-06-21T10:02:30Z 2015-06-21T10:02:30Z 2011 Способ выбора алгоритма разбиения графа для распределенных вычислений / В.А. Иващенко, Р.Ю. Лопаткин, В.В. Куприенко // Мат. машини і системи. — 2011. — № 4. — С. 31-38. — Бібліогр.: 8 назв. — рос. 1028-9763 https://nasplib.isofts.kiev.ua/handle/123456789/83622 519.8, 519.6 Предложен способ определения потенциально наиболее эффективного алгоритма разбиения заданного графа для распределенных вычислений, который опирается на результаты анализа статистической зависимости величины получаемого разреза (для того или иного алгоритма разбиения графа) от метрик графа. Эксперименты по использованию предложенного способа перед началом расчетов демонстрируют его эффективность в повышении быстродействия распределенной программы. Запропоновано спосіб визначення потенційно найбільш ефективного алгоритму розбиття заданого графа для розподілених обчислень, який спирається на результати аналізу статистичної залежності величини розрізу, що отримується (для того або іншого алгоритму розбиття графа) від метрик графа. Експерименти щодо використання запропонованого способу перед початком розрахунків демонструють його ефективність у підвищенні швидкодії розподіленої програми. A method of definition of the most effective partition algorithm of a specified graph for distributed calculation based on the analytical data of statistical dependence between the received value (for one or another graph partition algorithm) and graph metric is suggested. The experiments on the method mentioned above before the calculations demonstrate its efficiency in improving the performance of distributed applications. ru Інститут проблем математичних машин і систем НАН України Математичні машини і системи Обчислювальні системи Способ выбора алгоритма разбиения графа для распределенных вычислений Спосіб вибору алгоритму розбиття графа для розподілених обчислень The method of choosing a graph partition algorithm for distributed calculation Article published earlier |
| spellingShingle | Способ выбора алгоритма разбиения графа для распределенных вычислений Иващенко, В.А. Лопаткин, Р.Ю. Куприенко, В.В. Обчислювальні системи |
| title | Способ выбора алгоритма разбиения графа для распределенных вычислений |
| title_alt | Спосіб вибору алгоритму розбиття графа для розподілених обчислень The method of choosing a graph partition algorithm for distributed calculation |
| title_full | Способ выбора алгоритма разбиения графа для распределенных вычислений |
| title_fullStr | Способ выбора алгоритма разбиения графа для распределенных вычислений |
| title_full_unstemmed | Способ выбора алгоритма разбиения графа для распределенных вычислений |
| title_short | Способ выбора алгоритма разбиения графа для распределенных вычислений |
| title_sort | способ выбора алгоритма разбиения графа для распределенных вычислений |
| topic | Обчислювальні системи |
| topic_facet | Обчислювальні системи |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/83622 |
| work_keys_str_mv | AT ivaŝenkova sposobvyboraalgoritmarazbieniâgrafadlâraspredelennyhvyčislenii AT lopatkinrû sposobvyboraalgoritmarazbieniâgrafadlâraspredelennyhvyčislenii AT kuprienkovv sposobvyboraalgoritmarazbieniâgrafadlâraspredelennyhvyčislenii AT ivaŝenkova sposíbviborualgoritmurozbittâgrafadlârozpodílenihobčislenʹ AT lopatkinrû sposíbviborualgoritmurozbittâgrafadlârozpodílenihobčislenʹ AT kuprienkovv sposíbviborualgoritmurozbittâgrafadlârozpodílenihobčislenʹ AT ivaŝenkova themethodofchoosingagraphpartitionalgorithmfordistributedcalculation AT lopatkinrû themethodofchoosingagraphpartitionalgorithmfordistributedcalculation AT kuprienkovv themethodofchoosingagraphpartitionalgorithmfordistributedcalculation |