Анализ результатов применения метода случайного перебора в задаче поиска разбиений граф-схем параллельных алгоритмов

УДК 681.3

Э.И. Ватутин, Д.В. Колясников, В.С. Титов

АНАЛИЗ РЕЗУЛЬТАТОВ ПРИМЕНЕНИЯ МЕТОДА СЛУЧАЙНОГО ПЕРЕБОРА В ЗАДАЧЕ ПОИСКА РАЗБИЕНИЙ ГРАФ-СХЕМ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ*

Приведено описание метода случайного перебора в задаче построения субоптимальных разбиений параллельных алгоритмов логического управления, возникающей при проектировании однородных многомодульных мультисистем (систем логического управления в базисе логических мультиконтроллеров). С использованием разработанной программной реализации, работающей в составе программной среды PAE, выполнен ряд вычислительных экспериментов, на базе которых произведена оценка скорости сходимости предложенного метода, приведены результаты сопоставления качества оптимизации частных показателей качества с известными эвристическими последовательными методами, показывающие, что при достаточном количестве итераций (1000-10 000) качество решений является приемлемым, однако затраты необходимого вычислительного времени на один-два порядка выше. Полученные результаты позволяют сделать вывод о том, что при ряде сочетаний размерности задачи и силы технологических ограничений предложенный метод имеет преимущество по ряду частных показателей качества, проигрывая по интегральному показателю. Отмечено, что метод случайного перебора является легко распараллеливаемым, что позволяет его исполнение на широком спектре современных параллельных вычислительных средств.

Дискретная комбинаторная оптимизация; эвристические методы; проектирование мультиконтроллеров; граф-схемы параллельных алгоритмов; разбиения.

E.I. Vatutin, D.V. Kolyasnikov, V.S. Titov

ANALYSIS OF THE RESULTS OF APPLYING THE RANDOM SEARCH METHOD IN THE PROBLEM OF BUILDING SEPARATIONS OF PARALLEL LOGIC CONTROL ALGORITHMS

The article describes the random search method in the problem of constructing suboptimal separations of parallel logic control algorithms within homogeneous multi-module multisystems design (logic control systems based on logical multicontrollers). Using developed program system PAE a number of computational experiments are organized. The analysis of the convergence rate and results of a comparison with the known quality optimization heuristic methods are given. Showed that a sufficient number of iterations (1000-10 000) provide acceptable quality of solutions but computing time costs increased by 10-100 times. The obtained results allow us to conclude that in a number of combinations of the problem dimension and power of technological limitations proposed method has the advantage in a number of private quality indicators, losing by a integral indicator. The random search method is well parallelized that allows using a wide range of modern parallel computing resources.

Discrete combinatorial optimization; heuristic methods; multicontrollers design; graph-schemes of algorithms; separations.

Построение параллельных однородных многомодульных систем логического управления (СЛУ), именуемых также логическими мультиконтроллерами, является важной задачей, так как указанные мультисистемы могут быть оперативно настроены на выполнение любого параллельного алгоритма логического управления путем отыскания его разбиения на последовательные блоки ограниченной сложно-

* Работа проведена в рамках выполнения государственного задания для Юго-Западного государственного университета на 2014-2017 гг., номер НИР 2246, а также в рамках научной школы НШ-2357.2014.8.

сти с их размещением в соответствующих модулях [1—4]. Асимптотическая временная сложность задачи поиска оптимального разбиения определяется числом Белла [5], что не позволяет отыскать оптимальные решения для большинства практически важных случаев (граф-схемы алгоритмов с А^ >10 вершинами) и вынуждает довольствоваться субоптимальными решениями, полученныи с использованием различных эвристических методов [6-11]. Поставленная задача относится к классу задач дискретной комбинаторной многокритериальной оптимизации, а полученные решения оцениваются по ряду частных показателей качества, к которым относятся среднее число блоков в составе разбиения у Н , средние

степени дублирования сигналов логических условий и микроопераций у X и у У , средние значения сложности сети межблочных связей у су, и интенсивности межблочных взаимодействий у б . В ряде случаев удобно рассмотрение

интегрального показателя качества у J , представляющего собой взвешенную

сумму нормированных значений частных показателей [12]. Различные эвристические методы характеризуются существенно различным качеством минимизации частных показателей качества [13-17] в зависимости от значений технологических ограничений (области пространства параметров), к которым относятся ограничения на число принимаемых контроллером сигналов логических условий X и

емкость памяти контроллера . Минимизация указанных показателей качества

необходима для снижения аппаратной сложности проектируемых СЛУ в совокупности с повышением их быстродействия.

В работе [18] приведены результаты применения метода случайного перебора в известной задаче поиска кратчайших путей в графе, а в работе [19] приведено детальное описание алгоритма случайного перебора применительно к рассматриваемой задаче построения разбиений граф-схем параллельных алгоритмов логического управления. Алгоритм основан на том, что для очередной нерассмотренной вершины, выбираемой случайно, определяется множество блоков, в которые она может быть включена без нарушения ограничений, вероятность попадания вершины в один из них вычисляется пропорционально значению 0 < (х < 1 (настроечный параметр алгоритма). Также выбранная вершина может образовать собой новый блок разбиения с вероятнстью 1 — а. Из множества возможных включений случайным образом пропорционально указанным вероятностям выбирается одно из включений, вершина добавляется в выбранный блок и исключается из дальнейшего рассмотрения. По завершении рассмотрения всех вершин сформировано искомое случайное разбиение. Повторяя описанный процесс С раз, возможно получение С различных разбиений, из которых по интегральному показателю 3 выбирается лучшее и возвращается в качестве результата.

Следует ожидать, что полученное качество результирующего разбиения будет сильно зависеть как от значения вероятности попадания вершины в существующий блок О., так и от выполненного числа итераций перебора С. Малое значение вероятности Ос способствует образованию избыточных блоков разбиения и, как следствие, ухудшает остальные частные показатели качества, что подтверждают результаты (рис. 1) соответствующего вычислительного эксперимента, выполненного в разработанной программной системе РАЕ [20, 21].

Рис. 1. Зависимости частных показателей качества от вероятности попадания вершины в существующий блок СУ,, число вершин в граф-схемах алгоритмов N = 100, объем выборки граф-схем К = 1000, без ограничений, С = 1

В соответствии с приведенными на рис. 1 результатами вычислительного эксперимента можно сделать вывод о том, что наилучшие показатели достигаются при а —» 1. Однако при этом необходимо выполнение условия о < 1. так как при а = 1 невозможно образование новых блоков разбиения (соответствующая вероятность равна нулю). В области значения СИ вблизи 1 был проведен дополнительный эксперимент, который не выявил каких-либо существенных отклонений в тенденциях изменения частных показателей качества, поэтому эмпирически было выбрано оптимальное значение а =0,999, используемое в дальнейших экспериментах.

Известно [18], что с ростом числа итераций С значения частных показателей качества монотонно уменьшаются, асимптотически стремясь к некоторому минимуму, а затраты вычислительного времени линейно растут. При этом выбор оптимального значения С необходимо проводить исходя либо из соображений дальнейшего незначительного уменьшения значений частных показателей качества, либо из ограничения на затраты вычислительного времени. Итерационный процесс допускает тривиальное распараллеливание с использованием широкого спектра современного аппаратного обеспечения (многоядерные процессоры, многопроцессорные машины, кластеры, суперкомпьютеры, грид-системы) в связи с отсутствием зависимостей по управлению и информации между отдельными подзадачами.

Результаты соответствующего вычислительного эксперимента, анализирующего тенденции изменения частных показателей качества с ростом С, приведены на рис. 2.

<1 о

Рис. 2. Зависимости частных показателей качества от числа итераций С, N = 100, К = 1000, без ограничений

При С = 10 000 затраты на выполнение вычислительного эксперимента составляют порядка 6 часов вычислительного времени одного ядра процессора Intel Core i7 4770 @ 3,4 ГГц (Haswell). Зависимости, приведенные на рис. 2, показывают, что по ряду частных показателей качества у X , у К , у с\ , у Ь кривые

не достигают насыщения и целесообразно дальнейшее увеличение числа итераций, однако для этого потребуются большие затраты вычислительного времени (как минимум в 10-100 раз). В то же время число блоков разбиения у H практически не уменьшается начиная с С — 1000 • Таким образом, разумным минимумом

числа итераций случайного перебора в рассматриваемой задаче следует считать значение С = 1000, однако по возможности оно может быть увеличено на 2-3 порядка с соответствующим дополнительным уменьшением частных показателей качества разбиений как минимум в пределах нескольких десятков процентов.

Приведенные выше графики были получены при отсутствующих технологических ограничениях X =W = оо • Ниже в табл. 1 и 2 приведены количе-

Ш ЭХ Ш ЭХ

ственные результаты, полученные для случаев наличия различных ограничений. Кроме того, в таблицах приведены данные, позволяющие сопоставить полученные количественные значения частных показателей качества для метода случайного перебора (сокращенно RS) при различном числе итераций C с соответствующими значениями для решений, полученных с использованием известных подходов (метода С.И. Баранова [6, 7], сокращенно B; жадной стратегии с ограничением на смежность [8, 9], сокращенно AB; метода параллельно-последовательной декомпозиции [10, 11], сокращенно P).

Таблица 1

Зависимости частных показателей качества и времени на поиск решения от числа итераций С, N = 100, К —1000, IV =15

Метод Y H Y X Y Y Y OL Y 6 Y J t

AB 15,417 9,456 57,361 46,082 38,267 2,690 5,9 мс

B 15,518 8,710 53,481 45,301 51,898 2,672 3,4 мс

P 14,989 8,178 49,490 47,597 36,279 2,492 11,8 мс

RS, С = 1 15,197 11,483 64,137 61,378 46,506 2,993 2,2 мс

RS, С = 10 14,913 +1,9% 10,563 +8,0% 60,893 +5,1% 56,455 +8,0% 44,934 +3,4% 2,851 +4,7% 21,0 мс

RS, 14,859 9,643 58,728 53,994 43,872 2,763 207 мс

с=ю2 +0,4% +8,7% +2,7% +4,4% +2,4% +3,1%

RS, 14,847 9,020 57,161 52,270 43,194 2,704 2,1 с

С = 103 +0,1% +6,4% +2,7% +3,2% +1,5% +2,1%

RS, 14,841 8,513 55,651 50,963 42,590 2,654 20,9 с

с = ю4 +0,04% +5,6% +2,7% +2,5% +1,4% +1,8%

*Жирным выделены лучшие решения, в процентах указано улучшение значения частного показателя для метода К8 при увеличении числа итераций в 10 раз

Анализ тенденций изменения частных показателей приводит к подтверждению сформулированного выше утверждения о том, что дальнейшее увеличение числа итераций С должно дополнительно позитивно сказаться на качестве минимизации частных показателей.

Таблица 2

Зависимости частных показателей качества и времени на поиск решения от числа итераций С, N = 100, К = 1000, X =10

Метод Y H Y X Y Y Y OL Y б Y J t

AB 15,025 8,099 50,733 41,459 35,699 2,464 6,3 мс

B 14,930 7,264 51,586 41,125 35,731 2,451 3,9 мс

P 14,876 7,626 47,578 45,792 36,045 2,422 11,8 мс

RS, С = 1 15,157 11,431 63,864 61,021 46,424 2,978 2,2 мс

RS, С = 10 14,888 10,295 60,349 55,878 44,676 2,825 25 мс

RS, С = 102 14,854 9,399 57,831 53,269 43,602 2,733 220 мс

RS, С = 103 14,839 8,606 56,131 51,314 42,572 2,664 2,2 с

RS, С = 104 14,841 8,014 54,770 49,455 41,764 2,608 20,8 с

*Жирным выделены лучшие решения.

Приведенные результаты показывают, что метод случайного перебора в ряде случаев обеспечивает меньшее число блоков в разбиениях (в среднем на 1,0 % и 0,2% для проведенных экспериментов соответственно) при больших значениях

средней степени дублирования логических условий на 4,1 % и 10,3 % соответственно, степени дублирования микроопераций на 12,5 % и 15,1 % соответственно, сложности сети межблочных связей на 12,5 % и 20,2 % соответственно и интенсивности межблочных взаимодействий на 17,4 % и 17,0 % соответственно.

В табл. 3 приведены результаты вычислительного эксперимента для случая с большим числом вершин в составе граф-схем алгоритмов управления и отсутствующих ограничений (затраты вычислительного времени - 4 часа).

Таблица 3

Зависимости частных показателей качества и времени на поиск решения от числа итераций С, N = 500, К = 10, без ограничений

Метод Y H Y X Y Y у а, у 6 Y J t

AB 57,5 80,9 279,5 226,6 107,950 7,177 0,6 мс

B 57,6 81,8 282,6 225,1 108,415 7,247 0,3 мс

P 57,6 83,3 257,8 282,2 114,004 6,954 0,9 мс

RS, C = 1 59,9 116,7 377,8 395,4 144,166 9,644 0,14 мс

RS, C = 10 59,1 113,0 364,2 384,2 141,881 9,336 1,3 с

RS, C = 102 58,9 112,6 354,0 382,4 142,347 9,171 13,2 с

RS, C = 103 58,5 110,6 350,8 378,3 142,107 9,072 2,2 мин

RS, C = 104 58,6 (-1,9%) 108,6 (-34,2%) 347,5 (-34,8%) 377,8 (-67,8) 141,716 (-31,2%) 8,986 (-29,3%) 23,3 мин

*Жирным выделены лучшие решения, в скобках указано отставание в процентах от лучшего решения.

Анализ приведенных данных позволяет сделать вывод о том, что с ростом размерности задачи эффективность метода случайного перебора падает по сравнению с другими подходами, что, по-видимому, вызвано существенным увеличением числа возможных решений (ветвей комбинаторного дерева) по сравнению с числом перебираемых в ходе случайного перебора.

Следует ожидать, что метод случайного перебора будет обеспечивать решения неплохого качества при построении разбиений сравнительно небольших граф-схем алгоритмов. Для подтверждения данного тезиса необходима организация более масштабного вычислительного эксперимента, аналогичного рассмотренному в [15-17].

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Зотов И.В. и др. Организация и синтез микропрограммных мультимикроконтроллеров.

- Курск: Изд-во «Курск», 1999. - 368 с.

2. Емельянов С.Г., Зотов И.В., Титов В.С. Архитектура параллельных логических мульти-контроллеров. - М.: Высшая школа, 2009. - 233 с.

3. Ватутин Э.И., Зотов И.В., Титов В.С. и др. Комбинаторно-логические задачи синтеза разбиений параллельных алгоритмов логического управления при проектировании логических мультиконтроллеров. - Курск: Изд-во "Курск", 2010. - 200 с.

4. Ватутин Э.И. Проектирование логических мультиконтроллеров. Синтез разбиений параллельных граф-схем алгоритмов. - Saarbrücken: Lambert Academic Publishing, 2011.

- 292 с.

5. https://ru.wikipedia. org/wiki/Числа_Белла.

6. Баранов С.И., Журавина Л.Н., Песчанский В.А. Обобщенный метод декомпозиции граф-схем алгоритмов // А и ВТ. - 1982. - № 5. - С. 43-51.

7. Ватутин Э.И. Библиотека функций построения разбиений методом С.И. Баранова с жадным последовательным формированием блоков // Свидетельство о государственной регистрации программы для ЭВМ № 2010612902 от 28.04.10.

8. Ватутин Э.И., Леонов М.Е. Использование смежной окрестности при жадном последовательном формировании блоков разбиения граф-схем параллельных алгоритмов // Известия высших учебных заведений. Приборостроение. - 2013. - Т. 56, № 6. - С. 30-35.

9. Ватутин Э.И., Титов В.С. Библиотека функций для построения разбиений с использованием смежной жадной стратегии и последовательным формированием блоков // Свидетельство о государственной регистрации программы для ЭВМ № 2013619395 от 03.10.13.

10. Ватутин Э.И., Зотов И.В. Метод формирования субоптимальных разбиений параллельных управляющих алгоритмов // Параллельные вычисления и задачи управления (PACO'04). - М.: ИПУ РАН, 2004. - С. 884-917.

11. Ватутин Э.И., Зотов И.В. Параллельно-последовательный метод формирования субоптимальных разбиений параллельных управляющих алгоритмов // Свидетельство об официальной регистрации программы для ЭВМ № 2005613091 от 28.11.05.

12. Ватутин Э.И. Оценка качества разбиений параллельных управляющих алгоритмов на последовательные подалгоритмы с использованием весовой функции // Интеллектуальные и информационные системы (Интеллект-2005). - Тула, 2005. - С. 29-30.

13. Ватутин Э.И., Волобуев С.В., Зотов И.В. Комплексная сравнительная оценка методов выбора разбиений при проектировании логических мультиконтроллеров // Идентификация систем и задачи управления (SICPRO'08). - М.: ИПУ РАН, 2008. - С. 1917-1940.

14. Ватутин Э.И., Волобуев С.В., Зотов И.В. Комплексный сравнительный анализ качества разбиений при синтезе логических мультиконтроллеров в условиях присутствия технологических ограничений // Параллельные вычисления и задачи управления (PACO'08).

- М.: ИПУ РАН, 2008. - С. 643-685.

15. Ватутин Э.И., Титов В.С. Сравнение методов синтеза разбиений параллельных алгоритмов логического управления с использованием двухпараметрических диаграмм // Распознавание. - 2012. - С. 138-140.

16. Ватутин Э.И., Титов В.С. Сравнение методов синтеза разбиений граф-схем параллельных алгоритмов с использованием двумерных диаграмм // Известия Юго-Западного государственного университета. - 2012. - № 3 (42). - С. 66-74.

17. Ватутин Э.И., Титов В.С. Использование добровольных распределенных вычислений на платформе BOINC для анализа качества разбиений граф-схем параллельных алгоритмов // Параллельные вычисления и задачи управления (PACO'12). - М.: ИПУ РАН, 2012. - Т. 2. - С. 37-54.

18. Ватутин Э.И., Дремов Е.Н., Мартынов И.А., Титов В.С. Метод взвешенного случайного перебора для решения задач дискретной комбинаторной оптимизации // Известия ВолГТУ. Серия: Электроника, измерительная техника, радиотехника и связь. - 2014.

- № 10 (137). - Вып. 9. - С. 59-64.

19. Ватутин Э.И., Колясников Д.В., Мартынов И.А., Титов В.С. Метод случайного перебора в задаче построения разбиений граф-схем параллельных алгоритмов // Многоядерные процессоры, параллельное программирование, ПЛИС, системы обработки сигналов.

- Барнаул: Барнаул, 2014. - С. 115-125.

20. Ватутин Э.И., Зотов И.В. Программная система для построения разбиений параллельных управляющих алгоритмов // Труды V Международной конференции «Идентификация систем и задачи управления (SICPRO'06)». - М.: Институт проблем управления им. В.А. Трапезникова РАН, 2006. - С. 2239-2250.

21. Ватутин Э.И., Зотов И.В. Визуальная среда синтеза разбиений параллельных алгоритмов логического управления // Свидетельство об официальной регистрации программы для ЭВМ № 2007613222 от 30.07.07.

REFERENCES

1. Zotov I. V. i dr. Organizatsiya i sintez mikroprogrammnykh mul'timikrokontrollerov [Organization and synthesis firmware multimilliondollar]. Kursk: Izd-vo «Kursk», 1999, 368 p.

2. Emel'yanov S.G., Zotov I.V., Titov V.S. Arkhitektura parallel'nykh logicheskikh mul'tikontrollerov [Architecture of parallel logical Multicontroller]. Moscow: Vysshaya shkola, 2009, 233 p.

3. Vatutin E.I., Zotov I.V., Titov V.S. i dr. Kombinatorno-logicheskie zadachi sinteza razbieniy parallel'nykh algoritmov logicheskogo upravleniya pri proektirovanii logicheskikh mul'tikontrollerov [Combinatorial logic synthesis problem splits parallel logic control algorithms when designing logical Multicontroller]. Kursk: Izd-vo "Kursk", 2010, 200 p.

4. Vatutin E.I. Proektirovanie logicheskikh mul'tikontrollerov. Sintez razbieniy parallel'nykh graf-skhem algoritmov[Designing logical Multicontroller. Synthesis of separations of parallel graph-schemes of algorithms]. Saarbrücken: Lambert Academic Publishing, 2011, 292 p.

5. Available at: https://ru.wikipedia.org/wiki/HHcna_Benna.

6. Baranov S.I., Zhuravina L.N., Peschanskiy V.A. Obobshchennyy metod dekompozitsii graf-skhem algoritmov [Generalized method of decomposition graph-schemes of algorithms], A i VT [Automation and Computer Engineering], 1982, No. 5, pp. 43-51.

7. Vatutin E.I. Biblioteka funktsiy postroeniya razbieniy metodom S.I. Baranova s zhadnym posledovatel'nym formirovaniem blokov [Library functions separations of method C. I. Baranova with greedy sequential formation of blocks], Svidetel'stvo o gosudarstvennoy registratsiiprogrammy dlya EVM№ 2010612902 ot 28.04.10.

8. Vatutin E.I., Leonov M.E. Ispol'zovanie smezhnoy okrestnosti pri zhadnom posledovatel'nom formirovanii blokov razbieniya graf-skhem parallel'nykh algoritmov [Using an adjacent neighborhood with greedy sequential formation of blocks of the partition graph-schemes of parallel algorithms], Izvestiya vysshikh uchebnykh zavedeniy. Priborostroenie [News of higher educational institutions. Instrumentation], 2013, Vol. 56, No. 6, pp. 30-35.

9. Vatutin E.I., Titov V.S. Biblioteka funktsiy dlya postroeniya razbieniy s ispol'zovaniem smezhnoy zhadnoy strategii i posledovatel'nym formirovaniem blokov [Library of functions for building partitions using adjacent greedy strategy and sequential formation of blocks], Svidetel'stvo o gosudarstvennoy registratsii programmy dlya EVM № 2013619395 ot 03.10.13.

10. Vatutin E.I., Zotov I.V. Metod formirovaniya suboptimal'nykh razbieniy parallel'nykh upravlyayushchikh algoritmov [A method of forming a suboptimal splits parallel logic control algorithms], Parallel'nye vychisleniya i zadachi upravleniya (PACO'04) [Parallel computing and control problems (PAC0'04)]. Moscow: IPU RAN, 2004, pp. 884-917.

11. Vatutin E.I., Zotov I.V. Parallel'no-posledovatel'nyy metod formirovaniya subop-timal'nykh razbieniy parallel'nykh upravlyayushchikh algoritmov [Parallel-sequential method of forming a suboptimal splits parallel logic control algorithms], Svidetel'stvo ob ofitsial'noy registratsii programmy dlya EVM № 2005613091 ot 28.11.05.

12. Vatutin E.I. Otsenka kachestva razbieniy parallel'nykh upravlyayushchikh algoritmov na posledovatel'nye podalgoritmy s ispol'zovaniem vesovoy funktsii [Assessment of the quality of the separations of parallel logic control algorithms on serial Podgorica using the weighting function], Intellektual'nye i informatsionnye sistemy (Intellekt-2005) [Intellectual and information system (Mind 2005)]. Tula, 2005, pp. 29-30.

13. Vatutin E.I., Volobuev S.V., Zotov I.V. Kompleksnaya sravnitel'naya otsenka metodov vybora razbieniy pri proektirovanii logicheskikh mul'tikontrollerov [Comprehensive comparative evaluation of selection methods breaks when designing logical Multicontroller], Identifikatsiya sistem i zadachi upravleniya (SICPRO'08) [Systems identification and control problems (SICPR0'08)]. Moscow: IPU RAN, 2008, pp. 1917-1940.

14. Vatutin E.I., Volobuev S.V., Zotov I.V. Kompleksnyy sravnitel'nyy analiz kachestva razbieniy pri sinteze logicheskikh mul'tikontrollerov v usloviyakh prisutstviya tekhnologicheskikh ogranicheniy [A comprehensive comparative analysis of quality criteria in the synthesis of logical Multicontroller in the presence of technological constraints], Parallel'nye vychisleniya i zadachi upravleniya (PACO'08) [Parallelnye computing and control problems (PAC0'08)]. Moscow: IPU RAN, 2008, pp. 643-685.

15. Vatutin E.I., Titov V.S. Sravnenie metodov sinteza razbieniy parallel'nykh algo-ritmov logicheskogo upravleniya s ispol'zovaniem dvukhparametricheskikh diagramm [Comparison of methods for the synthesis of separations of parallel logic control algorithms using two-parameter diagrams], Raspoznavanie [Detection], 2012, pp. 138-140.

16. Vatutin E.I., Titov V.S. Sravnenie metodov sinteza razbieniy graf-skhem parallel'-nykh algoritmov s ispol'zovaniem dvumernykh diagramm [Comparison of methods for the synthesis of partitions of a graph-schemes of parallel algorithms using a two-dimensional charts], Izvestiya Yugo-Zapadnogo gosudarstvennogo universiteta [News of the South-Western state University], 2012, No. 3 (42), pp. 66-74.

17. Vatutin E.I., Titov V.S. Ispol'zovanie dobrovol'nykh raspredelennykh vychisleniy na platforme BOINC dlya analiza kachestva razbieniy graf-skhem parallel'nykh algoritmov [The use of voluntary distributed computing on the BOINC platform to analyze the quality of the splits graph-schemes of parallel algorithms], Parallel'nye vychisleniya i zadachi upravleniya (PACO'12) [Parallel computing and control problems (PACO'12)]. Moscow: IPU RAN, 2012, Vol. 2, pp. 37-54.

18. Vatutin E.I., Dremov E.N., Martynov I.A., Titov V.S. Metod vzveshennogo sluchaynogo perebora dlya resheniya zadach diskretnoy kombinatornoy optimizatsii [The method of weighted random search for solving problems of discrete combinatorial optimization], Izvestiya VolGTU. Seriya: Elektronika, izmeritel'naya tekhnika, radiotekhnika i svyaz' [News of Volgograd state technical University. Series: electronics and instrumentation engineering, radio engineering and communication], 2014, No. 10 (137), Issue 9, pp. 59-64.

19. Vatutin E.I., Kolyasnikov D.V., Martynov I.A., Titov V.S. Metod sluchaynogo perebora v zadache postroeniya razbieniy graf-skhem parallel'nykh algoritmov [The method of random search in the task of building a splits graph-schemes of parallel algorithms], Mnogoyadernye protsessory, parallel'noe programmirovanie, PLIS, sistemy obrabotki signalov [Multi-core processors, parallel programming, FPGA, signal-processing system]. Barnaul: Barnaul, 2014, pp. 115-125.

20. Vatutin E.I., Zotov I.V. Programmnaya sistema dlya postroeniya razbieniy parallel'nykh upravlyayushchikh algoritmov [A software system for separations of parallel logic control algorithms], Trudy V mezhdunarodnoy konferentsii «Identifikatsiya sistem i zadachi upravleniya (SICPR006)» [Proceedings of the V International conference "system Identification and control problems (SICPR0'06)"]. Moscow: Institut problem upravleniya im. V.A. Trapeznikova RAN, 2006, pp. 2239-2250.

21. Vatutin E.I., Zotov I.V. Vizual'naya sreda sinteza razbieniy parallel'nykh algoritmov logicheskogo upravleniya [The visual environment of synthesis of separations of parallel logic control algorithms], Svidetel'stvo ob ofitsial'noy registratsii programmy dlya EVM № 2007613222 ot 30.07.07.

Статью рекомендовал к опубликованию д.т.н., профессор А.С. Сизов.

Ватутин Эдуард Игоревич - Юго-Западный государственный университет; e-mail: evatutin@rambler.ru; 305040, г. Курск, ул. 50 лет Октября, 94; тел.: 84712587105; кафедра вычислительной техники; к.т.н.; доцент.

Колясников Дмитрий Викторович - кафедра вычислительной техники; магистрант.

Титов Виталий Семенович - e-mail: titov-kstu@rambler.ru; тел.: 84712587112; кафедра вычислительной техники; зав. кафедрой д.т.н.; профессор.

Vatutin Eduard Igorevich - Southwest State University; e-mail: evatutin@rambler.ru; 94, 50 let Oktyabrya street, Kursk, 305040, Russia; phone: +74712587105; the department of computer engineering; cand. of eng. sci.; associate professor.

Kolyasnikov Dmitry Viktorovich - the department of computer engineering; master.

Titov Vitaly Semenovich - e-mail: titov-kstu@rambler.ru; phone: +74712587112; the department of computer engineering; head of department; dr. of eng. sc.; professor.