Основы рекуррентно-параллельных вычислений в комбинаторном алгоритме CОМВІ МГУА

Разработаны теоретические основы распараллеливания операций в комбинаторном алгоритме COMBI МГУА с рекуррентным вычислением параметров моделей. Представлена теоретическая оценка эффективности разработанной схемы. Проведено экспериментальное исследование эффективности применения предложенной схемы....

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2014
Автори:	Ефименко, С.Н., Степашко, В.С.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України 2014
Назва видання:	Управляющие системы и машины
Теми:	Новые методы в информатике
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/83536
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Основы рекуррентно-параллельных вычислений в комбинаторном алгоритме CОМВІ МГУА / С.Н. Ефименко, В.С. Степашко // Управляющие системы и машины. — 2014. — № 6. — С. 27-33. — Бібліогр.: 6 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-83536
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-835362025-02-09T13:46:47Z Основы рекуррентно-параллельных вычислений в комбинаторном алгоритме CОМВІ МГУА Principles of recurrent and parallel computing in COMBI GMDH combinatorial algorithm Основи рекурентно-паралельних обчислень в комбінаторному алгоритмі COMBI МГУА Ефименко, С.Н. Степашко, В.С. Новые методы в информатике Разработаны теоретические основы распараллеливания операций в комбинаторном алгоритме COMBI МГУА с рекуррентным вычислением параметров моделей. Представлена теоретическая оценка эффективности разработанной схемы. Проведено экспериментальное исследование эффективности применения предложенной схемы. Theoretical grounds of operations paralleling in COMBI GMDH combinatorial algorithm with recurrent parameters estimation are developed. Theoretical estimate of constructed scheme efficiency is proposed. The results of experimental investigation are presented. Розроблено теоретичні основи розпаралелювання операцій в комбінаторному алгоритмі COMBI МГУА з рекурентним обчисленням параметрів моделей. Представлено теоретичну оцінку ефективності розробленої схеми. Проведено експериментальне дослідження ефективності застосування запропонованої схеми. 2014 Article Основы рекуррентно-параллельных вычислений в комбинаторном алгоритме CОМВІ МГУА / С.Н. Ефименко, В.С. Степашко // Управляющие системы и машины. — 2014. — № 6. — С. 27-33. — Бібліогр.: 6 назв. — рос. 0130-5395 https://nasplib.isofts.kiev.ua/handle/123456789/83536 519.254 + 519.163 ru Управляющие системы и машины application/pdf Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Новые методы в информатике Новые методы в информатике
spellingShingle	Новые методы в информатике Новые методы в информатике Ефименко, С.Н. Степашко, В.С. Основы рекуррентно-параллельных вычислений в комбинаторном алгоритме CОМВІ МГУА Управляющие системы и машины
description	Разработаны теоретические основы распараллеливания операций в комбинаторном алгоритме COMBI МГУА с рекуррентным вычислением параметров моделей. Представлена теоретическая оценка эффективности разработанной схемы. Проведено экспериментальное исследование эффективности применения предложенной схемы.
format	Article
author	Ефименко, С.Н. Степашко, В.С.
author_facet	Ефименко, С.Н. Степашко, В.С.
author_sort	Ефименко, С.Н.
title	Основы рекуррентно-параллельных вычислений в комбинаторном алгоритме CОМВІ МГУА
title_short	Основы рекуррентно-параллельных вычислений в комбинаторном алгоритме CОМВІ МГУА
title_full	Основы рекуррентно-параллельных вычислений в комбинаторном алгоритме CОМВІ МГУА
title_fullStr	Основы рекуррентно-параллельных вычислений в комбинаторном алгоритме CОМВІ МГУА
title_full_unstemmed	Основы рекуррентно-параллельных вычислений в комбинаторном алгоритме CОМВІ МГУА
title_sort	основы рекуррентно-параллельных вычислений в комбинаторном алгоритме cомві мгуа
publisher	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
publishDate	2014
topic_facet	Новые методы в информатике
url	https://nasplib.isofts.kiev.ua/handle/123456789/83536
citation_txt	Основы рекуррентно-параллельных вычислений в комбинаторном алгоритме CОМВІ МГУА / С.Н. Ефименко, В.С. Степашко // Управляющие системы и машины. — 2014. — № 6. — С. 27-33. — Бібліогр.: 6 назв. — рос.
series	Управляющие системы и машины
work_keys_str_mv	AT efimenkosn osnovyrekurrentnoparallelʹnyhvyčislenijvkombinatornomalgoritmecomvímgua AT stepaškovs osnovyrekurrentnoparallelʹnyhvyčislenijvkombinatornomalgoritmecomvímgua AT efimenkosn principlesofrecurrentandparallelcomputingincombigmdhcombinatorialalgorithm AT stepaškovs principlesofrecurrentandparallelcomputingincombigmdhcombinatorialalgorithm AT efimenkosn osnovirekurentnoparalelʹnihobčislenʹvkombínatornomualgoritmícombimgua AT stepaškovs osnovirekurentnoparalelʹnihobčislenʹvkombínatornomualgoritmícombimgua
first_indexed	2025-11-26T11:38:25Z
last_indexed	2025-11-26T11:38:25Z
_version_	1849852810635509760
fulltext	УСиМ, 2014, № 6 27 УДК 519.254 + 519.163 С.Н. Ефименко, В.С. Степашко Основы рекуррентно-параллельных вычислений в комбинаторном алгоритме COMBI МГУА Разработаны теоретические основы распараллеливания операций в комбинаторном алгоритме COMBI МГУА с рекуррентным вычислением параметров моделей. Представлена теоретическая оценка эффективности разработанной схемы. Проведено экс- периментальное исследование эффективности применения предложенной схемы. Theoretical grounds of operations paralleling in COMBI GMDH combinatorial algorithm with recurrent parameters estimation are de- veloped. Theoretical estimate of constructed scheme efficiency is proposed. The results of experimental investigation are presented. Розроблено теоретичні основи розпаралелювання операцій в комбінаторному алгоритмі COMBI МГУА з рекурентним обчис- ленням параметрів моделей. Представлено теоретичну оцінку ефективності розробленої схеми. Проведено експериментальне дослідження ефективності застосування запропонованої схеми. Введение. Метод группового учета аргументов (МГУА) [1] как основной инструмент теории индуктивного моделирования принадлежит к самым современным методам вычислительно- го интеллекта и мягких вычислений. Этот ме- тод, разработанный академиком А.Г. Ивахнен- ко, – оригинальное и эффективное средство ре- шения широкого спектра задач искусственного интеллекта, в том числе идентификации и про- гнозирования, распознавания образов и кла- стеризации, интеллектуального анализа дан- ных и поиска закономерностей. Важным критерием эффективности програм- мных средств, базирующихся на методах ин- дуктивного моделирования, есть время полу- чения результата моделирования. Наиболее эф- фективными средствами достижения высокой производительности таких программных про- дуктов считаются рекуррентные вычисления и распараллеливание операций. Высокопродуктивные средства на основе как рекуррентных, так и параллельных вычислений разработаны и продемонстрировали свою эф- фективность [1–5]. Цель данной статьи – объе- динение двух видов операций в единую пара- дигму параллельно-рекуррентных вычислений для перехода на более высокий уровень эффек- тивности программных средств индуктивного моделирования. Задача структурно-параметрической иден- тификации В общем случае задача структурно-парамет- рической идентификации состоит в формиро- вании по данным выборки некоторого множе- ства моделей различной структуры вида ),( ff Xfy   (1) и поиске оптимальной модели согласно условию )),,(,(minarg* f f XfyCRf    (2) где оценки параметров в (2) для каждой моде- ли f есть решением еще одной экстремаль- ной задачи вида ),,,(minarg ff R f sXyQR fs f    , (3) где sf называется сложностью модели f и рав- няется числу ненулевых компонент в модели (2); QR – критерий качества решения задачи параметрической идентификации каждой от- дельной модели, которая генерируется в задаче структурной идентификации, где модели срав- ниваются по критерию CR. При этом критерии QR и CR должны быть различными, поскольку две соответствующие задачи по своей природе разные: (2) есть задачей дискретной, а (3) – не- прерывной оптимизации. Комбинаторный алгоритм COMBI МГУА Комбинаторный алгоритм COMBI [1], пред- назначенный для решения задачи (1–3), т.е. для поиска (путем полного перебора всех возмож- ных вариантов) лучшей регрессионной моде- ли, содержащей наиболее информативное под- множество входных переменных (регрессоров), состоит из таких основных блоков:  преобразования данных в соответствии с выбранным базисным классом моделей, линей- ных по параметрам; 28 УСиМ, 2014, № 6  формирования моделей различной слож- ности;  вычисления значений внешних критериев качества и отбор лучших моделей;  оценки качества полученных моделей. В случае линейного объекта с m входами в процессе полного перебора сравниваются все возможные модели вида 12...,,1,  m vvv vXy  , (4) где десятичному числу  соответствует двоич- ное число d , единичные элементы которого указывают на включение в модель регрессоров с соответствующими номерами, а нулевые – на исключение. Соответственно, формирование структур частных моделей формализируется с помощью двоичного структурного вектора  mdddd ,...,, 21 ,  1;0kd , mk ,1 . Изменение состояний вектора d можно ор- ганизовать различными способами. Достаточ- но удобна для полного перебора схема изме- нения вектора d по принципу двоичного счет- чика, в последний разряд которого добавляется единица. При этом существует однозначное соответствие между десятичным порядковым номером очередной модели и состоянием дво- ичного структурного вектора. При переборе сложность частных моделей из- меняется от единицы до m. Общее число вари- антов при полном переборе составляет 2m – 1 различных структур, т.е. зависимость объема перебора от числа аргументов/регрессоров m – экспоненциальна. Это обстоятельство ставит са- мые высокие требования к организации вычис- лительных операций в таких алгоритмах с уче- том их максимального ускорения. В табл. 1 приведены оценки зависимости вре- мени моделирования с помощью самого быст- рого варианта комбинаторного алгоритма (без распараллеливания вычислений) от количества аргументов при полном переборе. В принципе целесообразно рассматривать возможность по- строения модели на компьютере с одним про- цессором за приемлемое время при m не более 30. При количестве аргументов больше 35 пе- ребор всех вариантов за допустимое время на персональном компьютере становится нецеле- сообразным. Задача повышения вычислительной эффек- тивности комбинаторного алгоритма может быть решена с использованием как быстродей- ствующих методов оценивания параметров, ба- зирующихся на рекуррентных алгоритмах ре- шения систем линейных алгебраических урав- нений, так и с применением распараллелива- ния вычислений с помощью многопроцессор- ных кластерных систем. Т а б л и ц а 1. Время полного перебора Количество аргументов Количество моделей Время моделирования 20 1 048 576 1 с 21 2 097 152 2 с 22 4 194 304 4 с … … … 30 ~ 1E + 9 ~ 20 м … … … 36 ~7E + 10 ~ 1 день … … … 45 ~4E + 13 ~ 1 год Рекуррентное оценивание параметров Задача оценивания параметров – наиболее трудоемкая в комбинаторном алгоритме МГУА. Поскольку в случае моделей, линейных по па- раметрам, в этой задаче применяется метод наи- меньших квадратов (МНК), фактически речь идет об ускорении решения систем линейных уравнений. Традиционным и эффективным рекуррент- ным методом есть метод окаймления [1, 2]. Идея этого алгоритма – модификации МНК – состоит в пошаговом рекуррентном вычислении и кор- ректировании оценок параметров моделей воз- растающей сложности с рекуррентным вычисле- нием элементов обратной матрицы системы нор- мальных уравнений. В [3] были также предложены эффективные рекуррентные модификации классических ал- горитмов Гаусса и Грамма–Шмидта, причем рекуррентный вариант метода Гаусса оказался весьма полезным для применения в параллель- ном комбинаторном алгоритме, поэтому при- ведем здесь его краткое описание. Вычислительная суть модификации алго- ритма Гаусса состоит в следующем. На s-м ша- УСиМ, 2014, № 6 29 ге ( ms ,1 ) нормальная матрица s T ss XXH  (для известной формулы оценки параметров по МНК yXXX TT 1)(ˆ  ) размерности s×s сво- дится к верхнему треугольному виду вычисле- нием элементов 1,2,  sihs si и sihs is ,2,  , в то время как элементы вложенной матрицы Hs–1 размерности (s – 1) × (s – 1), сведенной к верх- нему треугольному виду на прежнем шаге, ос- таются неизменными. Таким образом, на s-м шаге выполняется вычисление «окаймления» к элементам расширенной матрицы системы нормальных уравнений, вычисленным на пре- дыдущем шаге, и соответствующего элемента yXg T ss  этой матрицы: h11 h12 h13 … h1s-1 h1s … h1m g1 h21 h22 h23 … h2s-1 h2s … h2m g2 h31 h32 h33 … h3s-1 h3s … h3m g3 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... hs-1,1 h s-1,2 h s-1,3 … h s-1,s-1 h s-1,s … h s-1,m g s-1 hs1 hs2 hs3 … hs,s-1 hss … hsm gs ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... hm1 hm2 hm3 … hm,s-1 hms … hmm gm . На рис. 1 в графическом виде представлено сравнение показателей трудоемкости (количе- ства элементарных арифметических операций) вычисления параметров при включении в мо- дель, содержащую s – 1 аргументов, s-го аргу- мента. Такая зависимость трудоемкости про- порциональна второй степени сложности мо- дели для любого рекуррентного алгоритма и третьей степени – для нерекуррентного. Количество операций 0 2000 4000 6000 2 4 6 8 10 12 14 16 18 Сложность модели, s Рекуррентный Нерекуррентный Рис. 1. Количество операций для рекуррентного и нерекур- рентного алгоритмов Распараллеливание вычислений Метод оптимального распараллеливания операций в комбинаторном алгоритме МГУА с нерекуррентным оцениванием параметров на основе алгоритма генерации последовательно усложняемых структур, обеспечивающий оди- наковое суммарное количество как моделей, так и оцениваемых параметров, приходящихся на каждый процессор, предложен в [4]. При этом последовательно строятся все модели с одним аргументом, затем с двумя, тремя и т.д., что гарантированно обеспечивает равномерную вычислительную нагрузку на любое заданное количество процессоров кластерного комплек- са и дает возможность достаточно просто ав- томатизировать формирование задания на вы- полнение процесса распараллеливания. С помощью тестового эксперимента (табл. 2) была подтверждена высокая эффективность раз- работанной схемы распараллеливания. Т а б л и ц а 2. Эффективность схемы распараллеливания ком- бинаторного алгоритма Количество аргументов 20 21 22 23 24 Количество процессоров Эффективность, % 1 100 100 100 100 100 2 100 99 100 100 99 4 100 100 100 98 99 8 100 99 100 98 99 16 99 98 98 100 100 Здесь эффективность определялась по фор- муле 4,0,2%,1001    ik Tk T E i k k , (5) где T1 – время выполнения алгоритма на одном процессоре, Tk – время выполнения на k про- цессорах. Сравнение эффективности рекуррентных и параллельных вычислений Сравнить между собой эффективность двух описанных способов увеличения производи- тельности комбинаторного алгоритма МГУА позволяет эксперимент, описанный в [5]. Цель эксперимента состояла в сравнении времени выполнения полного перебора с использовани- ем комбинаторного алгоритма:  с нерекуррентным оцениванием парамет- ров и распараллеливанием операций;  с рекуррентным оцениванием параметров без распараллеливания вычислений. 30 УСиМ, 2014, № 6 На рис. 2 представлена зависимость времени выполнения программ от количества аргументов и процессоров кластерной системы. Последние (правые) столбцы диаграммы соответствуют ал- горитму с рекуррентным оцениванием парамет- ров на одном процессоре. 1 2 4 8 21 23 25 0 20 40 60 80 100 Время, с Процессоры Аргументы 21 22 23 24 25 рек, 1 проц. Рис. 2. Время выполнения комбинаторного алгоритма Эффективность рекуррентного оценивания параметров определялась как отношение вре- мени выполнения программ COMBI (с нере- куррентным и рекуррентным оцениванием па- раметров на одном процессоре) для количества аргументов от 21 до 25: rec nonrec rec T T E  . (6) Результат эксперимента, представленный на рис. 3, показывает рост значения Erec с увеличе- нием числа аргументов, а также позволяет сде- лать вывод о том, что полный перебор всех воз- можных моделей различной сложности по алго- ритму COMBI с рекуррентным оцениванием па- раметров будет более эффективным (по времени выполнения) на персональных компьютерах с многоядерными процессорами (вплоть до четы- рех ядер), чем распараллеливание нерекуррент- ных вычислений на таких вычислительных уст- ройствах. Очевидно, что в случае построения мо- делей на кластерных многопроцессорных ком- плексах использование распараллеливания опе- раций представляется более предпочтительным. Поскольку и рекуррентные, и параллельные вычисления в отдельности обеспечивают су- щественное уменьшение количества операций, затрачиваемых на процесс оценивания пара- метров, то сочетание этих двух мощных аппа- ратов позволяет получить эффект в виде не- достижимого ранее повышения производи- тельности алгоритмов МГУА. 3,6 3,8 4 4,2 4,4 4,6 21 22 23 24 25 Рис. 3. Эффективность алгоритма с рекуррентными вычисле- ниями Комбинаторный алгоритм COMBI МГУА на основе рекуррентно-параллельных вычи- слений Комбинаторный алгоритм имеет важную осо- бенность, позволяющую сделать вывод о вы- сокой эффективности его распараллеливания. Так, все блоки алгоритма могут выполняться каждым процессором автономно, без необхо- димости межпроцессорного взаимодействия. Главный процессор собирает результаты от- дельных процессоров и отбирает лучшую мо- дель. Далее описывается разработанная схема рас- параллеливания комбинаторного алгоритма с рекуррентным вычислением параметров мо- делей с помощью модифицированного алго- ритма Гаусcа [6] решения систем линейных уравнений. Схема использует генерацию двоичных чи- сел, отвечающих последовательным десятич- ным числам. Все возможные комбинации и по- следовательность двоичных структурных век- торов для случая трех аргументов можно запи- сать следующим образом: {0, 0, 0}; {0, 0, 1}; {0, 1, 0}; {0, 1, 1}; {1, 0, 0}; {1, 0, 1}; {1, 1, 0}; {1, 1, 1}. УСиМ, 2014, № 6 31 Эту схему предлагается использовать для распараллеливания комбинаторного алгоритма на кластерные системы следующим образом. Очевидно, что первая половина полной по- следовательности двоичных структурных век- торов есть зеркальным отображением второй половины, в которой выполняется инвертиро- вание элементов (нулевые элементы заменя- ются на единичные и наоборот). Так, для упо- мянутого ранее случая трех аргументов перво- му вектору {0, 0, 0} отвечает последний {1, 1, 1}, второму {0, 0, 1} – предпоследний {1, 1, 0} и т.д. Такая закономерность сохраняется для случая любой сложности моделей (общего ко- личества аргументов) и позволяет решить за- дачу равномерного распределения количества моделей, а также обеспечить одинаковое сум- марное количество аргументов на заданное ко- личество процессоров кластерной системы. Покажем, как можно распараллелить задачу для случая полного перебора из трех аргумен- тов на кластерной системе, состоящей из двух процессоров. Получим модели с двоичными структурными векторами {0, 0, 0}; {0, 0, 1}; {1, 1, 0}; {1, 1, 1}, которые строит первый про- цессор (четыре модели с общим количеством аргументов, равным шести) и модели со струк- турными векторами {0, 1, 0}; {0, 1, 1}; {1, 0, 0}; {1, 0, 1}, строящие второй процессор (так- же получаем четыре модели с общим количе- ством аргументов, равным шести). Запишем алгоритм нахождения последова- тельного набора двоичных структурных векто- ров при количестве аргументов, равном m, для к-го процессора кластерной системы ( Kk ,1 ) в виде последовательности шагов. Ш а г 1. По формуле m m s s mCmP 2)( 1    вы- числяем общее количество моделей, строящих- ся комбинаторным алгоритмом. Ш а г 2. Находим количество моделей, ко- торые будет строить каждый процессор: ( )kP m  ( ) /P m K . В случае если P(m) не делится на- цело на К, на первый процессор будет прихо- диться повышенная вычислительная нагрузка, отличающаяся от остальных процессоров не более чем на К дополнительных моделей. Ш а г 3. Генерируем 2/)(mPк последова- тельных структур, начиная с той, которая от- вечает десятичному числу 2/)()1( mPк к и заканчивая – отвечающей десятичному числу ( 1) ( )кк P m / 2 ( ) / 2 ( ) / 2к кP m кР m  . Ш а г 4. Находим структуру, инвертирован- ную к той, которая отвечает десятичному чис- лу 2/)(mкРк (все единицы в двоичном пред- ставлении числа 2/)(mкРк заменяем нулями и наоборот). Ш а г 5. Генерируем 2/)(mPк последователь- ных структур, начиная с полученной на пре- дыдущем шаге. Оценка эффективности распараллелива- ния рекуррентных вычислений Найдем теоретическую оценку эффективно- сти разработанной схемы распараллеливания комбинаторного алгоритма с рекуррентным оце- ниванием параметров. Пусть имеем m аргументов для полного пе- ребора 2m моделей на 2k процессорах кластер- ной системы. Тогда на каждый процессор при- ходится дополнительная нагрузка, обусловлен- ная необходимостью оценивать параметры пер- вой модели нерекуррентно, в виде не более чем m моделей для первой половины последова- тельности двоичных структурных векторов и не более чем m моделей для второй половины последовательности, которая получается ин- вертированием предыдущих (см. шаги 4 и 5 приведенного алгоритма). Каждый процессор построит 2m – k моделей рекуррентно и дополнительно не более чем 2m моделей, что составляет 2m/2m – k = m / 2m – k – 1 часть нагрузки. При заданном количестве аргументов и рас- тущем количестве процессоров теоретическая эффективность распараллеливания будет умень- шаться. Так, для m = 25 аргументов (для мень- шего количества аргументов нет смысла распа- раллеливать алгоритм) и 27 = 128 процессоров будем иметь 0,0002 (или 0,02 процента) потерь, т.е. теоретическая эффективность будет состав- 32 УСиМ, 2014, № 6 лять 99,98 процентов. При большем количестве аргументов она будет еще выше. Кроме того, дополнительные потери будет иметь первый процессор в виде не более чем 2k + 1 дополнительных моделей (см. шаг 2 ал- горитма). Это означает дополнительную на- грузку на него, что составляет 2k + 1/2m – k = = 22k – m + 1 часть. Для случая m = 25 аргумен- тов и 27 = 128 процессоров будем иметь,0,001 (или 0,1 процента) потерь, т.е. общая теоре- тическая эффективность будет составлять 99,88 процентов. Результаты экспериментов по рекуррент- но-параллельным вычислениям С целью экспериментального определения эффективности разработанной схемы комби- наторного алгоритма на основе рекуррентно- параллельных вычислений проведен тестовый эксперимент по решению задачи структурно- параметрической идентификации с помощью комбинаторного алгоритма с рекуррентно-па- раллельными вычислениями (для количества аргументов, равного 25) по разбиению всех вы- числений на пять потоков и последовательным их выполнением на одном процессоре. Результат этого эксперимента приближен к теоретическому, поскольку в нем исключено межпроцессорное взаимодействие – а в алго- ритме СОМВI, как было описано, такое взаи- модействие отсутствует. Эксперимент выполнялся следующим обра- зом: генерировалась матрица плана X размером 45 × 25 (45 точек для 25 аргументов) для систе- мы условных уравнений X y  . Вектор y фор- мировался в виде линейной комбинации пяти аргументов: 1514131211 xxxxxy  . Вы- полнялась структурно-параметрическая иденти- фикация с выбором лучшей модели по критерию регулярности [1], а также измерялось время мо- делирования при распараллеливании на разное количество потоков. Результат, представленный на рис. 4 в виде диаграммы времени выполнения, демонстрирует эффективность использования разработанной схемы. Эффективность распараллеливания Е достиг- ла 99,7 процентов, а равномерность нагрузки Р равнялась 99,2 процентам, которые определя- лись по формулам: %100 5 max5 1    T T E , (7) %100)1( max5 min5max5    T TT P , (8) где T1 – время выполнения алгоритма с одним потоком (т.е. без распараллеливания), T5max – время выполнения алгоритма с распараллели- ванием на пять потоков (определяется как мак- симальное среди пяти потоков время выполне- ния программы), T5min – минимальное среди пяти потоков время выполнения программы. 48,4 9,7 9,7 9,7 9,7 9,6 0 10 20 30 40 50 Без расп. 1-й 2-й 3-й 4-й 5-й Рис. 4. Время (секунды) выполнения алгоритма COMBI на основе рекуррентно-параллельных вычислений Исходя из теоретически двукратного увели- чения времени моделирования при добавлении одного дополнительного аргумента для полного перебора и зная время выполнения алгоритма COMBI с рекуррентными вычислениями для оп- ределенного количества аргументов, можно оце- нить время моделирования на произвольном за- данном количестве процессоров, что, естествен- но, целесообразно сделать до начала моделиро- вания. Такие оценки для количества аргументов от тридцати до сорока приведены на рис. 5 и 6. Как видим, эффективность распараллеливания равна количеству процессоров (в нашем слу- чае – стократная). Заключение. Исследован процесс распарал- леливания операций в комбинаторном алго- ритме COMBI МГУА с рекуррентным вычис- лением параметров моделей. Разработана схе- ма распараллеливания, базирующаяся на основе УСиМ, 2014, № 6 33 алгоритма генерации стандартного двоичного счетчика, который отвечает последовательным десятичным числам. 0 50 100 150 200 250 Время, час 30 31 32 33 34 35 36 37 38 39 40 Аргументы Рис. 5. Оценка времени выполнения комбинаторного алгоритма с рекуррентными вычислениями на одном процессоре 0 0,5 1 1,5 2 2,5 Время, час 30 31 32 33 34 35 36 37 38 39 40 Аргументы Рис. 6. Оценка времени выполнения комбинаторного алгорит- ма с рекуррентными вычислениями на ста процессорах Особенность схемы состоит в том, что пе- ред началом моделирования каждый процессор вычислительного кластера самостоятельно рас- считывает начальный и конечный структурный вектор для каждой сложности моделей, чем обеспечивается практически равномерная на- грузка на все элементы кластерной системы в целом и отпадает необходимость в межпроцес- сорном взаимодействии. Для задачи оценива- ния параметров по МНК использована рекур- рентная модификация алгоритма Гаусса реше- ния систем линейных уравнений. С помощью тестового эксперимента показа- но, что использование предложенной схемы обеспечивает практически одинаковое суммарное количество моделей и оцениваемых параметров, которые приходятся на каждый процесс. Эффек- тивность применения схемы при количестве про- цессов, равном пяти, и количестве аргументов, равном 25, составляет 99,7 процентов, а равно- мерность нагрузки достигает 99,2 процента. С увеличением количества аргументов эф- фективность комбинаторного алгоритма с ре- куррентно-параллельными вычислениями по отношению к параллельному алгоритму с не- рекуррентным оцениванием параметров растет практически линейно. 1. Ивахненко А.Г., Степашко В.С. Помехоустойчивость моделирования. – Киев: Наук. думка, 1985. – 216 с. 2. Себер Дж. Линейный регрессионный анализ. – М.: Мир, 1980. – 456 с. 3. Степашко В.С., Ефименко С.Н. О последователь- ном оценивании параметров регрессионных моде- лей // Кибернетика и системный анализ. – 2005. – № 4. – С. 184–187. 4. Stepashko V., Yefimenko S. Parallel algorithms for sol- ving combinatorial macromodelling problems // Prze- gląd Elektrotechniczny (Electrical Review). – 2009. – 85, N 4. – P. 98–99. 5. Yefimenko S. Comparative Effectiveness of Parallel and Recurrent Calculations in Combinatorial Algorithms of Inductive Modelling // Proc. of the 4th Int. Conf. on In- ductive Modelling ICIM’2013. – Kyiv, 2013. – P. 231– 234. 6. Єфименко С.М., Степашко В.С. Рекурентний ал- горитм методу Гаусса для розв’язання систем лі- нійних рівнянь у задачі оцінювання параметрів ре- гресійних моделей // Відбір і обробка інформації: Міжв. зб. наук. пр. – 2012. – № 36 (112). – С. 48–55. Поступила 30.10.2014 Тел. для справок: 044 526-3028, 097 105-8796 (Киев) E-mail: syefim@uk.net © С.Н. Ефименко, В.С. Степашко, 2014  << /ASCII85EncodePages false /AllowTransparency false /AutoPositionEPSFiles true /AutoRotatePages /None /Binding /Left /CalGrayProfile (Dot Gain 20%) /CalRGBProfile (sRGB IEC61966-2.1) /CalCMYKProfile (U.S. Web Coated \050SWOP\051 v2) /sRGBProfile (sRGB IEC61966-2.1) /CannotEmbedFontPolicy /Error /CompatibilityLevel 1.4 /CompressObjects /Tags /CompressPages true /ConvertImagesToIndexed true /PassThroughJPEGImages true /CreateJobTicket false /DefaultRenderingIntent /Default /DetectBlends true /DetectCurves 0.0000 /ColorConversionStrategy /CMYK /DoThumbnails false /EmbedAllFonts true /EmbedOpenType false /ParseICCProfilesInComments true /EmbedJobOptions true /DSCReportingLevel 0 /EmitDSCWarnings false /EndPage -1 /ImageMemory 1048576 /LockDistillerParams false /MaxSubsetPct 100 /Optimize true /OPM 1 /ParseDSCComments true /ParseDSCCommentsForDocInfo true /PreserveCopyPage true /PreserveDICMYKValues true /PreserveEPSInfo true /PreserveFlatness true /PreserveHalftoneInfo false /PreserveOPIComments true /PreserveOverprintSettings true /StartPage 1 /SubsetFonts true /TransferFunctionInfo /Apply /UCRandBGInfo /Preserve /UsePrologue false /ColorSettingsFile () /AlwaysEmbed [ true ] /NeverEmbed [ true ] /AntiAliasColorImages false /CropColorImages true /ColorImageMinResolution 300 /ColorImageMinResolutionPolicy /OK /DownsampleColorImages true /ColorImageDownsampleType /Bicubic /ColorImageResolution 300 /ColorImageDepth -1 /ColorImageMinDownsampleDepth 1 /ColorImageDownsampleThreshold 1.50000 /EncodeColorImages true /ColorImageFilter /DCTEncode /AutoFilterColorImages true /ColorImageAutoFilterStrategy /JPEG /ColorACSImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /ColorImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /JPEG2000ColorACSImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /JPEG2000ColorImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /AntiAliasGrayImages false /CropGrayImages true /GrayImageMinResolution 300 /GrayImageMinResolutionPolicy /OK /DownsampleGrayImages true /GrayImageDownsampleType /Bicubic /GrayImageResolution 300 /GrayImageDepth -1 /GrayImageMinDownsampleDepth 2 /GrayImageDownsampleThreshold 1.50000 /EncodeGrayImages true /GrayImageFilter /DCTEncode /AutoFilterGrayImages true /GrayImageAutoFilterStrategy /JPEG /GrayACSImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /GrayImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /JPEG2000GrayACSImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /JPEG2000GrayImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /AntiAliasMonoImages false /CropMonoImages true /MonoImageMinResolution 1200 /MonoImageMinResolutionPolicy /OK /DownsampleMonoImages true /MonoImageDownsampleType /Bicubic /MonoImageResolution 1200 /MonoImageDepth -1 /MonoImageDownsampleThreshold 1.50000 /EncodeMonoImages true /MonoImageFilter /CCITTFaxEncode /MonoImageDict << /K -1 >> /AllowPSXObjects false /CheckCompliance [ /None ] /PDFX1aCheck false /PDFX3Check false /PDFXCompliantPDFOnly false /PDFXNoTrimBoxError true /PDFXTrimBoxToMediaBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXSetBleedBoxToMediaBox true /PDFXBleedBoxToTrimBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXOutputIntentProfile () /PDFXOutputConditionIdentifier () /PDFXOutputCondition () /PDFXRegistryName () /PDFXTrapped /False /CreateJDFFile false /Description << /ARA <FEFF06270633062A062E062F0645002006470630064700200627064406250639062F0627062F0627062A002006440625064606340627062100200648062B062706260642002000410064006F00620065002000500044004600200645062A064806270641064206290020064406440637062806270639062900200641064A00200627064406450637062706280639002006300627062A0020062F0631062C0627062A002006270644062C0648062F0629002006270644063906270644064A0629061B0020064A06450643064600200641062A062D00200648062B0627062606420020005000440046002006270644064506460634062306290020062806270633062A062E062F062706450020004100630072006F0062006100740020064800410064006F006200650020005200650061006400650072002006250635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E0635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E> /BGR <FEFF04180437043f043e043b043704320430043904420435002004420435043704380020043d0430044104420440043e0439043a0438002c00200437043000200434043000200441044a0437043404300432043004420435002000410064006f00620065002000500044004600200434043e043a0443043c0435043d04420438002c0020043c0430043a04410438043c0430043b043d043e0020043f044004380433043e04340435043d04380020043704300020043204380441043e043a043e043a0430044704350441044204320435043d0020043f04350447043004420020043704300020043f044004350434043f0435044704300442043d04300020043f043e04340433043e0442043e0432043a0430002e002000200421044a04370434043004340435043d043804420435002000500044004600200434043e043a0443043c0435043d044204380020043c043e0433043004420020043404300020044104350020043e0442043204300440044f0442002004410020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200441043b0435043404320430044904380020043204350440044104380438002e> /CHS <FEFF4f7f75288fd94e9b8bbe5b9a521b5efa7684002000410064006f006200650020005000440046002065876863900275284e8e9ad88d2891cf76845370524d53705237300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c676562535f00521b5efa768400200050004400460020658768633002> /CHT <FEFF4f7f752890194e9b8a2d7f6e5efa7acb7684002000410064006f006200650020005000440046002065874ef69069752865bc9ad854c18cea76845370524d5370523786557406300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c4f86958b555f5df25efa7acb76840020005000440046002065874ef63002> /CZE <FEFF005400610074006f0020006e006100730074006100760065006e00ed00200070006f0075017e0069006a007400650020006b0020007600790074007600e101590065006e00ed00200064006f006b0075006d0065006e0074016f002000410064006f006200650020005000440046002c0020006b00740065007200e90020007300650020006e0065006a006c00e90070006500200068006f006400ed002000700072006f0020006b00760061006c00690074006e00ed0020007400690073006b00200061002000700072006500700072006500730073002e002000200056007900740076006f01590065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f007400650076015900ed007400200076002000700072006f006700720061006d0065006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076011b006a016100ed00630068002e> /DAN <FEFF004200720075006700200069006e0064007300740069006c006c0069006e006700650072006e0065002000740069006c0020006100740020006f007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400650072002c0020006400650072002000620065006400730074002000650067006e006500720020007300690067002000740069006c002000700072006500700072006500730073002d007500640073006b007200690076006e0069006e00670020006100660020006800f8006a0020006b00760061006c0069007400650074002e0020004400650020006f007000720065007400740065006400650020005000440046002d0064006f006b0075006d0065006e0074006500720020006b0061006e002000e50062006e00650073002000690020004100630072006f00620061007400200065006c006c006500720020004100630072006f006200610074002000520065006100640065007200200035002e00300020006f00670020006e0079006500720065002e> /DEU <FEFF00560065007200770065006e00640065006e0020005300690065002000640069006500730065002000450069006e007300740065006c006c0075006e00670065006e0020007a0075006d002000450072007300740065006c006c0065006e00200076006f006e002000410064006f006200650020005000440046002d0044006f006b0075006d0065006e00740065006e002c00200076006f006e002000640065006e0065006e002000530069006500200068006f006300680077006500720074006900670065002000500072006500700072006500730073002d0044007200750063006b0065002000650072007a0065007500670065006e0020006d00f60063006800740065006e002e002000450072007300740065006c006c007400650020005000440046002d0044006f006b0075006d0065006e007400650020006b00f6006e006e0065006e0020006d006900740020004100630072006f00620061007400200075006e0064002000410064006f00620065002000520065006100640065007200200035002e00300020006f0064006500720020006800f600680065007200200067006500f600660066006e00650074002000770065007200640065006e002e> /ESP <FEFF005500740069006c0069006300650020006500730074006100200063006f006e0066006900670075007200610063006900f3006e0020007000610072006100200063007200650061007200200064006f00630075006d0065006e0074006f00730020005000440046002000640065002000410064006f0062006500200061006400650063007500610064006f00730020007000610072006100200069006d0070007200650073006900f3006e0020007000720065002d0065006400690074006f007200690061006c00200064006500200061006c00740061002000630061006c0069006400610064002e002000530065002000700075006500640065006e00200061006200720069007200200064006f00630075006d0065006e0074006f00730020005000440046002000630072006500610064006f007300200063006f006e0020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e003000200079002000760065007200730069006f006e0065007300200070006f00730074006500720069006f007200650073002e> /ETI <FEFF004b00610073007500740061006700650020006e0065006900640020007300e4007400740065006900640020006b00760061006c006900740065006500740073006500200074007200fc006b006900650065006c007300650020007000720069006e00740069006d0069007300650020006a0061006f006b007300200073006f00620069006c0069006b0065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740069006400650020006c006f006f006d006900730065006b0073002e00200020004c006f006f0064007500640020005000440046002d0064006f006b0075006d0065006e00740065002000730061006100740065002000610076006100640061002000700072006f006700720061006d006d006900640065006700610020004100630072006f0062006100740020006e0069006e0067002000410064006f00620065002000520065006100640065007200200035002e00300020006a00610020007500750065006d006100740065002000760065007200730069006f006f006e00690064006500670061002e000d000a> /FRA <FEFF005500740069006c006900730065007a00200063006500730020006f007000740069006f006e00730020006100660069006e00200064006500200063007200e900650072002000640065007300200064006f00630075006d0065006e00740073002000410064006f00620065002000500044004600200070006f0075007200200075006e00650020007100750061006c0069007400e90020006400270069006d007000720065007300730069006f006e00200070007200e9007000720065007300730065002e0020004c0065007300200064006f00630075006d0065006e00740073002000500044004600200063007200e900e90073002000700065007500760065006e0074002000ea0074007200650020006f007500760065007200740073002000640061006e00730020004100630072006f006200610074002c002000610069006e00730069002000710075002700410064006f00620065002000520065006100640065007200200035002e0030002000650074002000760065007200730069006f006e007300200075006c007400e90072006900650075007200650073002e> /GRE <FEFF03a703c103b703c303b903bc03bf03c003bf03b903ae03c303c403b5002003b103c503c403ad03c2002003c403b903c2002003c103c503b803bc03af03c303b503b903c2002003b303b903b1002003bd03b1002003b403b703bc03b903bf03c503c103b303ae03c303b503c403b5002003ad03b303b303c103b103c603b1002000410064006f006200650020005000440046002003c003bf03c5002003b503af03bd03b103b9002003ba03b103c42019002003b503be03bf03c703ae03bd002003ba03b103c403ac03bb03bb03b703bb03b1002003b303b903b1002003c003c103bf002d03b503ba03c403c503c003c903c403b903ba03ad03c2002003b503c103b303b103c303af03b503c2002003c503c803b703bb03ae03c2002003c003bf03b903cc03c403b703c403b103c2002e0020002003a403b10020005000440046002003ad03b303b303c103b103c603b1002003c003bf03c5002003ad03c703b503c403b5002003b403b703bc03b903bf03c503c103b303ae03c303b503b9002003bc03c003bf03c103bf03cd03bd002003bd03b1002003b103bd03bf03b903c703c403bf03cd03bd002003bc03b5002003c403bf0020004100630072006f006200610074002c002003c403bf002000410064006f00620065002000520065006100640065007200200035002e0030002003ba03b103b9002003bc03b503c403b103b303b503bd03ad03c303c403b503c103b503c2002003b503ba03b403cc03c303b503b903c2002e> /HEB <FEFF05D405E905EA05DE05E905D5002005D105D405D205D305E805D505EA002005D005DC05D4002005DB05D305D9002005DC05D905E605D505E8002005DE05E105DE05DB05D9002000410064006F006200650020005000440046002005D405DE05D505EA05D005DE05D905DD002005DC05D405D305E405E105EA002005E705D305DD002D05D305E405D505E1002005D005D905DB05D505EA05D905EA002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E05D005DE05D905DD002005DC002D005000440046002F0058002D0033002C002005E205D905D905E005D5002005D105DE05D305E805D905DA002005DC05DE05E905EA05DE05E9002005E905DC0020004100630072006F006200610074002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E> /HRV (Za stvaranje Adobe PDF dokumenata najpogodnijih za visokokvalitetni ispis prije tiskanja koristite ove postavke. Stvoreni PDF dokumenti mogu se otvoriti Acrobat i Adobe Reader 5.0 i kasnijim verzijama.) /HUN <FEFF004b0069007600e1006c00f30020006d0069006e0151007300e9006701710020006e0079006f006d00640061006900200065006c0151006b00e90073007a00ed007401510020006e0079006f006d00740061007400e100730068006f007a0020006c006500670069006e006b00e1006200620020006d0065006700660065006c0065006c0151002000410064006f00620065002000500044004600200064006f006b0075006d0065006e00740075006d006f006b0061007400200065007a0065006b006b0065006c0020006100200062006500e1006c006c00ed007400e10073006f006b006b0061006c0020006b00e90073007a00ed0074006800650074002e0020002000410020006c00e90074007200650068006f007a006f00740074002000500044004600200064006f006b0075006d0065006e00740075006d006f006b00200061007a0020004100630072006f006200610074002000e9007300200061007a002000410064006f00620065002000520065006100640065007200200035002e0030002c0020007600610067007900200061007a002000610074007400f3006c0020006b00e9007301510062006200690020007600650072007a006900f3006b006b0061006c0020006e00790069007400680061007400f3006b0020006d00650067002e> /ITA <FEFF005500740069006c0069007a007a006100720065002000710075006500730074006500200069006d0070006f007300740061007a0069006f006e00690020007000650072002000630072006500610072006500200064006f00630075006d0065006e00740069002000410064006f00620065002000500044004600200070006900f900200061006400610074007400690020006100200075006e00610020007000720065007300740061006d0070006100200064006900200061006c007400610020007100750061006c0069007400e0002e0020004900200064006f00630075006d0065006e007400690020005000440046002000630072006500610074006900200070006f00730073006f006e006f0020006500730073006500720065002000610070006500720074006900200063006f006e0020004100630072006f00620061007400200065002000410064006f00620065002000520065006100640065007200200035002e003000200065002000760065007200730069006f006e006900200073007500630063006500730073006900760065002e> /JPN <FEFF9ad854c18cea306a30d730ea30d730ec30b951fa529b7528002000410064006f0062006500200050004400460020658766f8306e4f5c6210306b4f7f75283057307e305930023053306e8a2d5b9a30674f5c62103055308c305f0020005000440046002030d530a130a430eb306f3001004100630072006f0062006100740020304a30883073002000410064006f00620065002000520065006100640065007200200035002e003000204ee5964d3067958b304f30533068304c3067304d307e305930023053306e8a2d5b9a306b306f30d530a930f330c8306e57cb30818fbc307f304c5fc59808306730593002> /KOR <FEFFc7740020c124c815c7440020c0acc6a9d558c5ec0020ace0d488c9c80020c2dcd5d80020c778c1c4c5d00020ac00c7a50020c801d569d55c002000410064006f0062006500200050004400460020bb38c11cb97c0020c791c131d569b2c8b2e4002e0020c774b807ac8c0020c791c131b41c00200050004400460020bb38c11cb2940020004100630072006f0062006100740020bc0f002000410064006f00620065002000520065006100640065007200200035002e00300020c774c0c1c5d0c11c0020c5f40020c2180020c788c2b5b2c8b2e4002e> /LTH <FEFF004e006100750064006f006b0069007400650020016100690075006f007300200070006100720061006d006500740072007500730020006e006f0072011700640061006d00690020006b0075007200740069002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b00750072006900650020006c0061006200690061007500730069006100690020007000720069007400610069006b007900740069002000610075006b01610074006f00730020006b006f006b007900620117007300200070006100720065006e006700740069006e00690061006d00200073007000610075007300640069006e0069006d00750069002e0020002000530075006b0075007200740069002000500044004600200064006f006b0075006d0065006e007400610069002000670061006c006900200062016b007400690020006100740069006400610072006f006d00690020004100630072006f006200610074002000690072002000410064006f00620065002000520065006100640065007200200035002e0030002000610072002000760117006c00650073006e0117006d00690073002000760065007200730069006a006f006d00690073002e> /LVI <FEFF0049007a006d0061006e0074006f006a00690065007400200161006f00730020006900650073007400610074012b006a0075006d00750073002c0020006c0061006900200076006500690064006f00740075002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006100730020006900720020012b00700061016100690020007000690065006d01130072006f00740069002000610075006700730074006100730020006b00760061006c0069007401010074006500730020007000690072006d007300690065007300700069006501610061006e006100730020006400720075006b00610069002e00200049007a0076006500690064006f006a006900650074002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006f002000760061007200200061007400760113007200740020006100720020004100630072006f00620061007400200075006e002000410064006f00620065002000520065006100640065007200200035002e0030002c0020006b0101002000610072012b00200074006f0020006a00610075006e0101006b0101006d002000760065007200730069006a0101006d002e> /NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken die zijn geoptimaliseerd voor prepress-afdrukken van hoge kwaliteit. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.) /NOR <FEFF004200720075006b00200064006900730073006500200069006e006e007300740069006c006c0069006e00670065006e0065002000740069006c002000e50020006f0070007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740065007200200073006f006d00200065007200200062006500730074002000650067006e0065007400200066006f00720020006600f80072007400720079006b006b0073007500740073006b00720069006600740020006100760020006800f800790020006b00760061006c0069007400650074002e0020005000440046002d0064006f006b0075006d0065006e00740065006e00650020006b0061006e002000e50070006e00650073002000690020004100630072006f00620061007400200065006c006c00650072002000410064006f00620065002000520065006100640065007200200035002e003000200065006c006c00650072002000730065006e006500720065002e> /POL <FEFF0055007300740061007700690065006e0069006100200064006f002000740077006f0072007a0065006e0069006100200064006f006b0075006d0065006e007400f300770020005000440046002000700072007a0065007a006e00610063007a006f006e00790063006800200064006f002000770079006400720075006b00f30077002000770020007700790073006f006b00690065006a0020006a0061006b006f015b00630069002e002000200044006f006b0075006d0065006e0074007900200050004400460020006d006f017c006e00610020006f007400770069006500720061010700200077002000700072006f006700720061006d006900650020004100630072006f00620061007400200069002000410064006f00620065002000520065006100640065007200200035002e0030002000690020006e006f00770073007a0079006d002e> /PTB <FEFF005500740069006c0069007a006500200065007300730061007300200063006f006e00660069006700750072006100e700f50065007300200064006500200066006f0072006d00610020006100200063007200690061007200200064006f00630075006d0065006e0074006f0073002000410064006f0062006500200050004400460020006d00610069007300200061006400650071007500610064006f00730020007000610072006100200070007200e9002d0069006d0070007200650073007300f50065007300200064006500200061006c007400610020007100750061006c00690064006100640065002e0020004f007300200064006f00630075006d0065006e0074006f00730020005000440046002000630072006900610064006f007300200070006f00640065006d0020007300650072002000610062006500720074006f007300200063006f006d0020006f0020004100630072006f006200610074002000650020006f002000410064006f00620065002000520065006100640065007200200035002e0030002000650020007600650072007300f50065007300200070006f00730074006500720069006f007200650073002e> /RUM <FEFF005500740069006c0069007a00610163006900200061006300650073007400650020007300650074010300720069002000700065006e007400720075002000610020006300720065006100200064006f00630075006d0065006e00740065002000410064006f006200650020005000440046002000610064006500630076006100740065002000700065006e0074007200750020007400690070010300720069007200650061002000700072006500700072006500730073002000640065002000630061006c006900740061007400650020007300750070006500720069006f006100720103002e002000200044006f00630075006d0065006e00740065006c00650020005000440046002000630072006500610074006500200070006f00740020006600690020006400650073006300680069007300650020006300750020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e00300020015f00690020007600650072007300690075006e0069006c006500200075006c0074006500720069006f006100720065002e> /RUS <FEFF04180441043f043e043b044c04370443043904420435002004340430043d043d044b04350020043d0430044104420440043e0439043a043800200434043b044f00200441043e043704340430043d0438044f00200434043e043a0443043c0435043d0442043e0432002000410064006f006200650020005000440046002c0020043c0430043a04410438043c0430043b044c043d043e0020043f043e04340445043e0434044f04490438044500200434043b044f00200432044b0441043e043a043e043a0430044704350441044204320435043d043d043e0433043e00200434043e043f0435044704300442043d043e0433043e00200432044b0432043e04340430002e002000200421043e043704340430043d043d044b04350020005000440046002d0434043e043a0443043c0435043d0442044b0020043c043e0436043d043e0020043e0442043a0440044b043204300442044c002004410020043f043e043c043e0449044c044e0020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200431043e043b043504350020043f043e04370434043d043804450020043204350440044104380439002e> /SKY <FEFF0054006900650074006f0020006e006100730074006100760065006e0069006100200070006f0075017e0069007400650020006e00610020007600790074007600e100720061006e0069006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b0074006f007200e90020007300610020006e0061006a006c0065007001610069006500200068006f0064006900610020006e00610020006b00760061006c00690074006e00fa00200074006c0061010d00200061002000700072006500700072006500730073002e00200056007900740076006f00720065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f00740076006f00720069016500200076002000700072006f006700720061006d006f006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076016100ed00630068002e> /SLV <FEFF005400650020006e006100730074006100760069007400760065002000750070006f0072006100620069007400650020007a00610020007500730074007600610072006a0061006e006a006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b006900200073006f0020006e0061006a007000720069006d00650072006e0065006a016100690020007a00610020006b0061006b006f0076006f00730074006e006f0020007400690073006b0061006e006a00650020007300200070007200690070007200610076006f0020006e00610020007400690073006b002e00200020005500730074007600610072006a0065006e006500200064006f006b0075006d0065006e0074006500200050004400460020006a00650020006d006f0067006f010d00650020006f0064007000720065007400690020007a0020004100630072006f00620061007400200069006e002000410064006f00620065002000520065006100640065007200200035002e003000200069006e0020006e006f00760065006a01610069006d002e> /SUO <FEFF004b00e40079007400e40020006e00e40069007400e4002000610073006500740075006b007300690061002c0020006b0075006e0020006c0075006f00740020006c00e400680069006e006e00e4002000760061006100740069007600610061006e0020007000610069006e006100740075006b00730065006e002000760061006c006d0069007300740065006c00750074007900f6006800f6006e00200073006f00700069007600690061002000410064006f0062006500200050004400460020002d0064006f006b0075006d0065006e007400740065006a0061002e0020004c0075006f0064007500740020005000440046002d0064006f006b0075006d0065006e00740069007400200076006f0069006400610061006e0020006100760061007400610020004100630072006f0062006100740069006c006c00610020006a0061002000410064006f00620065002000520065006100640065007200200035002e0030003a006c006c00610020006a006100200075007500640065006d006d0069006c006c0061002e> /SVE <FEFF0041006e007600e4006e00640020006400650020006800e4007200200069006e0073007400e4006c006c006e0069006e006700610072006e00610020006f006d002000640075002000760069006c006c00200073006b006100700061002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400200073006f006d002000e400720020006c00e4006d0070006c0069006700610020006600f60072002000700072006500700072006500730073002d007500740073006b00720069006600740020006d006500640020006800f600670020006b00760061006c0069007400650074002e002000200053006b006100700061006400650020005000440046002d0064006f006b0075006d0065006e00740020006b0061006e002000f600700070006e00610073002000690020004100630072006f0062006100740020006f00630068002000410064006f00620065002000520065006100640065007200200035002e00300020006f00630068002000730065006e006100720065002e> /TUR <FEFF005900fc006b00730065006b0020006b0061006c006900740065006c0069002000f6006e002000790061007a006401310072006d00610020006200610073006b013100730131006e006100200065006e0020006900790069002000750079006100620069006c006500630065006b002000410064006f006200650020005000440046002000620065006c00670065006c0065007200690020006f006c0075015f007400750072006d0061006b0020006900e70069006e00200062007500200061007900610072006c0061007201310020006b0075006c006c0061006e0131006e002e00200020004f006c0075015f0074007500720075006c0061006e0020005000440046002000620065006c00670065006c0065007200690020004100630072006f006200610074002000760065002000410064006f00620065002000520065006100640065007200200035002e003000200076006500200073006f006e0072006100730131006e00640061006b00690020007300fc007200fc006d006c00650072006c00650020006100e70131006c006100620069006c00690072002e> /UKR <FEFF04120438043a043e0440043804410442043e043204430439044204350020044604560020043f043004400430043c043504420440043800200434043b044f0020044104420432043e04400435043d043d044f00200434043e043a0443043c0435043d044204560432002000410064006f006200650020005000440046002c0020044f043a04560020043d04300439043a04400430044904350020043f045604340445043e0434044f0442044c00200434043b044f0020043204380441043e043a043e044f043a04560441043d043e0433043e0020043f0435044004350434043404400443043a043e0432043e0433043e0020043404400443043a0443002e00200020042104420432043e04400435043d045600200434043e043a0443043c0435043d0442043800200050004400460020043c043e0436043d04300020043204560434043a0440043804420438002004430020004100630072006f006200610074002004420430002000410064006f00620065002000520065006100640065007200200035002e0030002004300431043e0020043f04560437043d04560448043e04570020043204350440044104560457002e> /ENU (Use these settings to create Adobe PDF documents best suited for high-quality prepress printing. Created PDF documents can be opened with Acrobat and Adobe Reader 5.0 and later.) >> /Namespace [ (Adobe) (Common) (1.0) ] /OtherNamespaces [ << /AsReaderSpreads false /CropImagesToFrames true /ErrorControl /WarnAndContinue /FlattenerIgnoreSpreadOverrides false /IncludeGuidesGrids false /IncludeNonPrinting false /IncludeSlug false /Namespace [ (Adobe) (InDesign) (4.0) ] /OmitPlacedBitmaps false /OmitPlacedEPS false /OmitPlacedPDF false /SimulateOverprint /Legacy >> << /AddBleedMarks false /AddColorBars false /AddCropMarks false /AddPageInfo false /AddRegMarks false /ConvertColors /ConvertToCMYK /DestinationProfileName () /DestinationProfileSelector /DocumentCMYK /Downsample16BitImages true /FlattenerPreset << /PresetSelector /MediumResolution >> /FormElements false /GenerateStructure false /IncludeBookmarks false /IncludeHyperlinks false /IncludeInteractive false /IncludeLayers false /IncludeProfiles false /MultimediaHandling /UseObjectSettings /Namespace [ (Adobe) (CreativeSuite) (2.0) ] /PDFXOutputIntentProfileSelector /DocumentCMYK /PreserveEditing true /UntaggedCMYKHandling /LeaveUntagged /UntaggedRGBHandling /UseDocumentProfile /UseDocumentBleed false >> ] >> setdistillerparams << /HWResolution [2400 2400] /PageSize [612.000 792.000] >> setpagedevice

Основы рекуррентно-параллельных вычислений в комбинаторном алгоритме CОМВІ МГУА

Репозитарії

Схожі ресурси