Організація нечіткого логічного виведення на основі багаторівневого паралелізму
In this paper, a method for constructing hierarchical systems of fuzzy inference based on multilevel parallelism, in particular, second-level parallelism, is developed, theoretically substantiated and implemented. This approach is designed to accelerate the computation of hierarchical fuzzy systems...
Збережено в:
| Дата: | 2018 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2018
|
| Теми: | |
| Онлайн доступ: | https://journal.iasa.kpi.ua/article/view/150221 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | System research and information technologies |
| Завантажити файл: |  |
Репозитарії
System research and information technologies| _version_ | 1866391910450462720 |
|---|---|
| author | Ponomarenko, Roman M. |
| author_facet | Ponomarenko, Roman M. |
| author_sort | Ponomarenko, Roman M. |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2019-01-17T13:31:43Z |
| description | In this paper, a method for constructing hierarchical systems of fuzzy inference based on multilevel parallelism, in particular, second-level parallelism, is developed, theoretically substantiated and implemented. This approach is designed to accelerate the computation of hierarchical fuzzy systems having complex dependency graphs between blocks of fuzzy rules. The concept of multilevel parallelism is formulated and presented. The notion of the level of parallelism is introduced. The theorem is formulated and proved, and a method for theoretical estimation of the maximum possible acceleration for systems constructed on the basis of parallelism of the level n is developed. An approach to designing hierarchical fuzzy systems based on multilevel parallelism for NVIDIA graphics accelerators is developed. Using NVIDIA CUDA technology, an experimental software system was designed for hierarchical systems of fuzzy inference based on multilevel parallelism for systems having complex graphs of dependencies between blocks of fuzzy rules. Experimental estimates of the acceleration are obtained. Also, based on the developed method, theoretical estimates of the maximum possible acceleration are found. A comparative characteristic of the theoretical and experimental estimates of the acceleration of hierarchical fuzzy systems is given. |
| doi_str_mv | 10.20535/SRIT.2308-8893.2018.3.09 |
| first_indexed | 2025-07-17T10:24:13Z |
| format | Article |
| fulltext |
Р.Н. Пономаренко, 2018
98 ISSN 1681–6048 System Research & Information Technologies, 2018, № 3
УДК 681.3.06
DOI: 10.20535/SRIT.2308-8893.2018.3.09
ОРГАНИЗАЦИЯ НЕЧЕТКОГО ЛОГИЧЕСКОГО ВЫВОДА
НА ОСНОВЕ МНОГОУРОВНЕВОГО ПАРАЛЛЕЛИЗМА
Р.Н. ПОНОМАРЕНКО
Аннотация. Разработан, теоретически обоснован и реализован метод построе-
ния иерархических систем нечеткого логического вывода на основе много-
уровневого параллелизма, в частности параллелизма второго уровня. Сформу-
лирована концепция многоуровневого параллелизма, введено понятие уровня
параллелизма. Сформулирована и доказана теорема, разработан метод теоре-
тической оценки максимально возможного ускорения для систем, построен-
ных на базе параллелизма уровня n, а также подход к проектированию иерар-
хических нечетких систем на основе многоуровневого параллелизма для
графических ускорителей NVIDIA. Спроектирована экспериментальная про-
граммная система для иерархических нечетких систем на основе многоуровне-
вого параллелизма и технологии CUDA, имеющих сложные графы зависимо-
стей между блоками нечетких правил. На основе разработанного метода
вычислены теоретические оценки максимального ускорения; получены экспе-
риментальные оценки ускорения для иерархических сложных систем нечетко-
го логического вывода.
Ключевые слова: нечеткий логический вывод, многоуровневый параллелизм,
ускорение, нечеткие системы типа Такаги–Сугено, теоретическая оценка уско-
рения.
ВСТУПЛЕНИЕ
Математический аппарат нечеткой логики [1] зарекомендовал себя в тех
системах, где существует неопределенность в той или иной степени, и при-
меняется все шире в ряде направлений: наука, медицина, принятие решений
в условиях неопределенности и т. д. В основе нечетких систем лежит нечет-
кий логический вывод, который позволяет применять нечеткую логику для
построения интеллектуальных и экспертных систем, существенно расширяя
круг решаемых задач.
При проектировании масштабных систем нечеткого логического выво-
да главной проблемой является необходимость существенного расширения
нечеткой базы знаний, возникающая при увеличении количества входящих
посылок (входных переменных). При увеличении количества входных пе-
ременных в рамках элементарной нечеткой системы количество правил рас-
тет экспоненциально [2]. Количество нечетких правил в пределах элемен-
тарной системы нечеткого логического вывода, которее должен написать
эксперт [2]
KMN ,
где K — количество нечетких входных переменных элементарной нечеткой
системы; M — количество термов для каждой нечеткой переменной.
Организация нечеткого логического вывода на основе многоуровневого параллелизма
Системні дослідження та інформаційні технології, 2018, № 3 99
Единственным эффективным способом борьбы с количеством правил
является декомпозиция на уровне входных переменных. Такие системы на-
зываются иерархическими системами нечеткого логического вывода, где в
качестве посылок одних систем могут выступать заключения других систем,
нижележащих по иерархии [3–6]. Таким образом, с увеличением количества
элементарных систем суммарное количество правил при масштабировании
иерархической системы увеличивается в арифметической прогрессии, давая
возможность строить нечеткие системы с неограниченным количеством
входных переменных. Так возник вопрос о повышении производительности
вычислений иерархических систем нечеткого логического вывода.
Цель данной работы — предоставить теоретическую базу и способы
реализации иерархических систем нечеткого логического вывода на основе
концепции многоуровневого параллелизма с целью повышения быстродейс-
твия таких систем в масштабируемых задачах, имеющих сложные иерархи-
ческие зависимости между блоками нечетких правил.
За основу взят нечеткий логический вывод типа Такаги–Сугено, однако
не исключается (как и не утверждается) распространение представленной
теории на нечеткие системы другого типа, базы знаний которых состоят из
блоков нечетких правил.
НЕЧЕТКИЙ ЛОГИЧЕСКИЙ ВЫВОД ТАКАГИ–СУГЕНО
Система нечеткого логического вывода типа Такаги–Сугено основывается
на блоках нечетких предикатных правил ЕСЛИ–ТО [7]:
,,...,2,1),,...,,(ТО
естьИ...ИестьИестьЕСЛИ:
21
2211
Njxxxgy
AxAxAxR
njj
njnjjj
,
где функция нахождения подзаключения правила ),...,,( 21 nj xxxg
nn xxx ...22110 — линейная функциональная зависимость от
четких величин входных посылок нечеткой системы; N — общее количество
правил в пределах блока. Вычисление общего заключения нечеткой системы
типа Такаги–Сугено имеет вид:
N
j
iij
m
i
N
j
iij
m
i
j
x
xg
y
T
T
j
j
1 1
1 1
)(
)(
, (1)
где )( iij x — функция принадлежности входных посылок нечеткому терму;
T — Т-норма, в которой в качестве конъюнкции обычно используется опе-
рация нахождения минимума.
КОНЦЕПЦИЯ МНОГОУРОВНЕВОГО ПАРАЛЛЕЛИЗМА
Любой параллельный алгоритм можно представить в виде ярусно-
параллельной вычислительной формы [8]. То есть представить в виде дерева
Р.Н. Пономаренко
ISSN 1681–6048 System Research & Information Technologies, 2018, № 3 100
операций, вершины которого означают множество операций, а дуги – ин-
формационные зависимости между операциями (рис. 1). Пусть имеется
ациклический ориентированный мультиграф G = {V, E}, где V — множество
операций (множество вершин); E — множество зависимостей между опера-
циями (множество дуг). Приведем понятие яруса [8].
Пусть s, q — вершины с индексами i, j соответственно, где s — опера-
ция приемник данных; q — операция поставщик данных. Тогда, если индек-
сы i, j номера соответствующих ярусов, то всегда i > j. В этом случае мно-
жество вершин, имеющих одинаковый индекс, является ярусом ярусно-
параллельной формы вычислений. Количество систем в пределах одного
яруса называется шириной данного яруса. Естественно, чем шире ярусы ал-
горитма, тем выше его степень параллелизма и, как следствие, возможности
для распараллеливания. Степень параллелизма определяет соотношение ко-
личества вершин к количеству ярусов алгоритма.
Для обеспечения доступа к вершинам ярусно-параллельной схемы ав-
тором разработан метод, позволяющий, используя для хранения графа од-
номерный массив вершин, получать доступ к любой вершине любого яруса
графа. Используемая структура данных состоит из двух одномерных масси-
вов данных: массива вершин и массива номеров вершин.
Представим метод обеспечения доступа к вершинам каждого яруса [9].
Пусть N — количество вершин графа (количество блоков правил в ярусе),
s — количество ярусов. Тогда, если количество систем в і-м ярусе ,il si ,1 ,
то имеем следующее соотношение:
s
i
i Nl
1
.
Пусть V — множество вершин; M — множество номеров вершин графа.
Определим для каждого яруса i-ю группу вершин i
i
pi lpdD ,1},{ )( на
множестве V. Тогда каждую вершину i-го яруса на множестве V можно най-
ти по формуле
i
k
k
i
pz
i
p lpzMd i
p 1
)()( ,)( , (2)
где i — номер яруса; p — номер вершины в i-м ярусе; )(i
pz — индекс номера
вершины p i-го яруса на множестве M; )(i
pz
M — найденный индекс вершины
)(i
pd на множестве V.
Операции
Информационные
зависимости
Ярус 1
Ярус 2
Ярус 3
Рис. 1. Ярусно-параллельная форма вычислений
Организация нечеткого логического вывода на основе многоуровневого параллелизма
Системні дослідження та інформаційні технології, 2018, № 3 101
При этом операции рассматриваются как элементарные, однако опера-
циями чаще всего являются именно блоки операций, примерно равные меж-
ду собой по количеству атомарных вычислений и контексту логических
действий. Концепция многоуровневого параллелизма предполагает рас-
смотрение вершин графа в качестве сложных операционных блоков. Такие
блоки, притом, что имеют подобно элементарной операции один вход –
один выход, могут иметь возможности внутреннего распараллеливания.
Пример отдельного яруса ярусно-параллельной схемы вычислений, верши-
ны которой рассматриваются как вычислительные блоки и обладают внут-
ренним параллелизмом, показан на рис. 2.
Введем понятие уровня параллелизма. Пусть имеется граф алгоритма
),( EVG , где V — множество операций; E — множество зависимостей
между операциями. В общем виде множество операций MivV i ,1},{ ,
обозначает операции именно элементарные, где M — количество операций.
Однако каждая отдельно взятая операция iv также может подразумевать
блок операций. То есть можно утверждать, что в этом случае },{ WQvi ,
где Q — множество операций блока iv ; W — множество зависимостей опе-
раций блока iv .
Пусть k — количество ярусов блока операций iv ; M — количество
операций блока iv . Тогда можно утверждать, что уровень параллелизма
возрастает на единицу, если соблюдаются следующие условия:
MkM ,2 . Иными словами, количество операций блока iv должно быть
не менее двух, а количество ярусов меньше общего количества вершин
множества iv . Алгоритм, все операции которого выполняются строго по-
следовательно (последовательный алгоритм), является алгоритмом нулевого
уровня параллелизма.
Примем изначально весь алгоритм G как единый блок операций. По-
скольку уровни параллелизма начинают исчисление с нулевого уровня
(уровня последовательной программы), то начальный уровень алгоритма G
будет также нулевым. Таким образом, если NsN ,2 , тогда наблюдается
параллелизм первого уровня, а если MkM ,2 , то параллелизм второго
уровня. При дальнейшем исследовании алгоритма количество уровней па-
Операционные
блоки яруса
Внутренний
параллелизм
Рис. 2. Пример яруса вычислительной ярусно-параллельной схемы с внутренним
параллелизмом
Р.Н. Пономаренко
ISSN 1681–6048 System Research & Information Technologies, 2018, № 3 102
раллелизма может возрасти до некоего максимального значения. Это значе-
ние назовем верхней границой параллелизма и обозначим .
В работе сформулирована теорема [9] для нахождения теоретической
оценки максимально возможного ускорения для вычислительных систем,
имеющим параллелизм уровня больше единицы.
Теорема. Для параллелизма уровня n, суммарное максимально воз-
можное ускорение вычисляется как произведение максимально возможных
ускорений каждого из уровней:
n
i
i
p
n
pppP in
ssssS
1
21sum ...
21
, (3)
где sum
PS — суммарное ускорение параллелизма уровня n; i
pi
s — ускорение
уровня i при условии использования на данном уровне количества процес-
соров равном ip .
Следует уточнить, что в формуле (3) присутствует также нулевой уро-
вень 1, 0
0
0
ps p (последовательный вариант), который в большинстве случа-
ев полагается равным единице и может быть опущен при вычислении теоре-
тической оценки максимального ускорения. Однако теоретически не
исключается использованиее для нулевого уровня значения, отличного от
единицы ( 10
0
ps ). Таким примером может послужить случай, когда ускоре-
ние возможно за счет использования более быстрой памяти. Таким образом,
обозначив нулевой уровень, формула (3) примет вид:
n
i
i
p
n
ppppP in
sssssS
0
210sum ...
210
.
Доказательство. Максимально возможное ускорение в пределах па-
раллелизма первого уровня можно вычислить за законом Амдала [8], кото-
рый находит теоретическую оценку ускорения с учетом того, какая доля
вычислений выполняется строго последовательно:
ap
p
p
pS
11
1
, (4)
где p — количество используемых процессоров; — доля вычислений,
выполняющихся строго последовательно. При вычислении обычно слож-
ную структуру разбивают на вычислительные блоки примерно одинакового
размера для нахождения доли блоков, выполняющихся последовательно.
При этом, в свою очередь, каждый из блоков может иметь свой внутренний
параллелизм, который невозможно достичь между блоками, однако достига-
ется в пределах блока (рис. 2).
Из изложенного следует, что переменная будет также иметь коэф-
фициент внутреннего ускорения, который при строго последовательном вы-
полнении операций блока будет равняться единице и не рассматривается.
Введем новый коэффициент при , обозначив его как коэффициент
внутреннего ускорения. Тогда формула (4) примет вид
Организация нечеткого логического вывода на основе многоуровневого параллелизма
Системні дослідження та інформаційні технології, 2018, № 3 103
p
p
pS
1
1 )1(
1
1
1
.
Поскольку каждый блок можно рассматривать как отдельную подсис-
тему, то коэффициент также будет вычисляться по формуле (4). При этом
уровень параллелизма будет увеличен на единицу. Тогда, применяя метод
математической индукции для доказательства данной теоремы, получим
выражение при параллелизме уровня 2n :
1
1
2
2
2
11
2
2
2
1
sum
1
1
)1(
1
1
1
p
p
p
SP
1
12
11
12
1
1
12
112
1
)()1()(
1
)()1(
)(
1
222
2 p
SpS
p
S
S ppp
p
.
1)())1(( 1
21
111
1
2
12
111
1
21
2
2
n
i
i
ppp
p
p
i
sSS
pa
pS
Sp
p
Теорема доказана.
ИЕРАРХИЧЕСКИЕ СИСТЕМЫ НЕЧЕТКОГО ЛОГИЧЕСКОГО ВЫВОДА
Иерархические нечеткие системы строятся на основе ярусно-параллельной
схемы вычислений [8] и информационных зависимостей между элементар-
ными нечеткими системами. Под информационной зависимостью имеется в
виду зависимость входных параметров одних нечетких систем (приемников
данных) от выходных значений других (поставщиков данных).
Представим иерархическую нечеткую систему по аналогии с ярусно-
параллельной формой в виде ациклического ориентированного мультиграфа
G = {V, E}, где V — множество элементарных нечетких систем; E — мно-
жество информационных зависимостей между элементарными нечеткими
системами. Общая схема иерархических систем нечеткого логического вы-
вода представлена на рис. 3. Прямоугольниками обозначены элементарные
нечеткие системы (FS), где верхний индекс — номер яруса; нижний индекс
— номер системы в данном ярусе. Типы иерархических структур нечеткого
логического вывода приведены в работе [2].
Р.Н. Пономаренко
ISSN 1681–6048 System Research & Information Technologies, 2018, № 3 104
ПАРАЛЛЕЛИЗМ НЕЧЕТКИХ СИСТЕМ ПЕРВОГО УРОВНЯ
Параллелизм первого уровня в иерархических нечетких системах — это па-
раллелизм на уровне иерархической связки нечетких систем между собой.
Под операцией понимается элементарная нечеткая система. Непосредствен-
но параллельное исполнение операций происходит в пределах яруса, т.е.
осуществляется последовательная обработка параллельно исполняемых яру-
сов. Представим всю иерархию элементарных систем множеством
LdyY d ,1},{ , где L — общее количество нечетких систем. Также пред-
ставим подмножество множества Y нечетких систем в пределах яруса в виде
PqyQ q ,1},{ , где P — количество нечетких систем в пределах одного
яруса. Тогда в пределах яруса Q присутствует параллелизм, где доступ к
элементарным системам параллельно исполняемого яруса Q будет происхо-
дить в соответствии с (2).
Представим множество потоков для параллелизма первого уровня
множеством KtpPL t ,1},{1 , где K — общее количество доступных по-
токов первого уровня. Каждый элемент tp содержит номера обрабатывае-
мых элементарных нечетких систем. Номера этих систем для каждого пото-
ка
KP
K
P
rKt
KPq
p
r
t
если,,...,0,
если,
. (5)
Следовательно, каждый параллельный поток tp выполняет вычис-
ления:
1
1FS
2
1FS 2
2FS 2
3FS
mFS1 mFS2
1
2
2
2
1
1 ... nxxx ... npxx 2
1
1 ...
Рис. 3. Схема иерархической системы нечеткого логического вывода
Организация нечеткого логического вывода на основе многоуровневого параллелизма
Системні дослідження та інформаційні технології, 2018, № 3 105
q
q
N
j
q
j
N
j
q
j
q
j
q
w
wg
y
1
1 ,
где q — индекс элементарной нечеткой системы яруса Q, рассчитанный по
формуле (5).
ПАРАЛЛЕЛИЗМ НЕЧЕТКИХ СИСТЕМ ВТОРОГО УРОВНЯ
Параллелизм второго уровня является ускорителем на уровне элементарной
нечеткой системы. Как упоминалось выше, элементарная нечеткая система
состоит из блока нечетких предикатных правил NjRRB j ,1},{ . Нахож-
дение заключения нечеткой системы предполагает последовательную обра-
ботку всего множества правил блока. Причем не играет роли последова-
тельность обработки данного множества, каждый элемент которого является
независимым. Представим множество потоков для параллелизма второго
уровня множеством MlpPL l ,1},{2 , где M – общее доступное количест-
во потоков второго уровня. Каждый элемент lp содержит номера обрабаты-
ваемых правил. Номера этих правил для каждого потока lp определяются
согласно формуле:
MN
M
N
kMl
MNj
p
k
l
если,,...,0,
;если,
. (6)
Следовательно, каждый параллельный поток lp выполняет следующие
вычисления:
)(
1
iij
m
i
xT
j
— активацию предусловий нечеткого правила;
),...,,( 21 nj xxxg — нахождение подзаключения нечеткого правила в
случае успешной его активации (если 0)(min
,...,2,1
iij
mi
x
j
),
где j — индекс правила в блоке нечетких правил, рассчитанный согласно
выражению (6).
Важно отметить, что после синхронизированной обработки всего мно-
жества нечетких правил следует нахождение заключения по формуле (1),
что несколько снижает эффективность параллелизма, так как данная опера-
ция выполняется строго последовательно относительно параллельной обра-
ботки правил [10]. Нахождение заключения в большинстве случаев полага-
ется на первый поток параллельной вычислительной системы.
Р.Н. Пономаренко
ISSN 1681–6048 System Research & Information Technologies, 2018, № 3 106
МНОГОУРОВНЕВЫЙ ПАРАЛЛЕЛИЗМ НА БАЗЕ ТЕХНОЛОГИИ
NVIDIA CUDA
Многоуровневый параллелизм предполагает, что для каждого из уровней
должно быть зарезервировано n параллельных потоков. Это количество не
обязательно должно удовлетворять степень параллелизма, однако от этого
количества зависят возможности распараллеливания. Еще одна задача реа-
лизации многоуровневого параллелизма — организация взаимодействия
потоков. При увеличении уровня параллелизма хотя бы до второго уровня
размер блоков операций на этом уровне заметно падает. Исходя из этого,
распределенные системы типа MPI, действующие на основе обмена сооб-
щениями между процессорами, являются неэффективными. Время вычисле-
ний замедляется учащающейся передачей данных. Также стоит отметить
сложную индексацию процессов в распределенных системах.
Технология NVIDIA CUDA относится к технологиям мелкозернистого
параллельного программирования с использованием в качестве вычислите-
льного устройства видеокарты. Отметим, что графические ускорители при-
званы решать масштабные вычислительные задачи, которые имеют высо-
кую степень параллелизма. Главными достоинствами CUDA, отмеченными
при реализации многоуровневого параллелизма, являются: наличие общей
памяти, трехмерная индексация, большое количество параллельных пото-
ков.
Элементарной вычислительной единицей на графических ускорителях
NVIDIA являются нити. Нити собираются в блоки, блоки, в свою очередь, в
сетку (рис. 4). Такая вычислительная архитектура, позволяет использовать
более мелкие вычислительные единицы для реализации параллелизма по-
следующих уровней. Пример реализации многоуровневого параллелизма
второго уровня на базе технологии графических ускорителей NVIDIA про-
иллюстрирован на рис. 4. Блоки (blocks) в пределах сетки (grid) реализуют
параллелизм первого уровня, тогда как нити (threads) — параллелизм второ-
го уровня (рис. 4). Построение иерархических систем нечеткого логического
вывода на основе графических ускорителей изложено в работах [9–11].
Блок (0, 0) Блок (1, 0) Блок (L, 0)
Блок (0, 1) Блок (1, 1) Блок (L, K)
Сетка 1
Операции параллелизма первого уровня
… … …
Нить (0, 0) Нить (1, 0) Нить (N, 0)
Нить (0, 1) Нить (1, 1) Нить (N, M)
… … …
Операции параллелизма второго уровня
Рис. 4. Организация параллелизма второго уровня на графических ускорителях
NVIDIA CUDA
Организация нечеткого логического вывода на основе многоуровневого параллелизма
Системні дослідження та інформаційні технології, 2018, № 3 107
ИНТЕЛЛЕКТУАЛЬНЫЕ ПРОГРАММНЫЕ СИСТЕМЫ НА ОСНОВЕ
МНОГОУРОВНЕВОГО ПАРАЛЛЕЛИЗМА И ТЕХНОЛОГИИ
ПАРАЛЛЕЛЬНОГО ПРОГРАММИРОВАНИЯ CUDA
В работах [10–12] автором было разработано и спроектировано несколько
иерархических параллельных интеллектуальных систем нечеткого логиче-
ского вывода с применением разных уровней параллелизма и способов рас-
параллеливания [11]. Среди таких систем целесообразно отметить работы
«Интеллектуальная система оценивания качества научных работ, что пода-
ются на конференцию» [11, 12] и «Интеллектуальная система оценивания
привлекательности стартапов» [10].
С целью исследования свойств параллельных иерархических нечетких
систем следует рассмотреть результаты ускорения иерархических нечетких
систем второго уровня параллелизма на основе технологии графических ус-
корителей NVIDIA CUDA [10]. Для этого была спроектирована эксперимен-
тальная программная система, генерирующая иерархию систем нечеткого
логического вывода по заданным критериям. Полученные результаты срав-
ним с теоретической оценкой максимально возможного ускорения, восполь-
зовавшись сформулированной теоремой (3). Проведем теоретическую оцен-
ку ускорения для параллелизма второго уровня системы на 1000 блоков
нечетких правил согласно этой теореме. В качестве эксперимента была сге-
нерирована система, обладающая следующими свойствами: количество яру-
сов, зададим равным 20, количество входов для каждой элементарной сис-
темы — 3, количество нечетких правил в пределах блока — 27, количество
параллельных CUDA-потоков для 1-го и 2-го уровней параллелизма выбра-
но 100 и 27 соответственно.
Согласно формуле (4) вычислим оценку максимально возможного ус-
корения на каждом из уровней. Далее по формуле (3) найдем суммарное ус-
корение для всех уровней одновременно:
;27;100
;
21
21sum
21
pp
ssS ppP
;01,0;02,01000/20/ 21 Ms
;33
100
02,01
02,0
1
1
1
1
1
1
1
1
p
s p
;22
27
01,01
01,0
1
1
1
2
2
2
2
2
p
s p
,726223321sum
21
ppP ssS
где M — количество элементарных нечетких систем; s — количество ярусов
графа зависимостей между блоками нечетких правил.
Р.Н. Пономаренко
ISSN 1681–6048 System Research & Information Technologies, 2018, № 3 108
Экспериментальные оценки ускорения иерархических систем нечетко-
го логического вывода второго уровня параллелизма в сравнении с теорети-
ческими оценками ускорения, а также с экспериментальными оценками ус-
корения таких же систем для первого уровня параллелизма (использовалась
технология параллельных вычислений с распределенной памятью MPI [11,
12]) показаны на рис. 5. Оценки ускорения получены для разного количест-
ва элементарных нечетких систем.
Экспериментальная оценка ускорения несколько ниже теоретической,
что обусловлено накладными расходами при работе с глобальной памятью
графических ускорителей. Однако в целом наблюдается тенденция наращи-
вания продуктивности вычислений с увеличением количества блоков нечет-
ких правил. Таким образом, в пределах 1000 блоков нечетких правил реше-
на проблема скорости вычислений при проектировании сложных
иерархических нечетких систем.
ЗАКЛЮЧЕНИЕ
В работе сформулирована концепция многоуровневого параллелизма на ос-
нове внутреннего распараллеливания, которая позволяет значительно уско-
рить выполнение сложных высоконагруженных вычислений. Введено и
обосновано понятие уровня параллелизма. Разработан метод нахождения
теоретической оценки ускорения для параллельных вычислений уровня n, а
также метод распараллеливания иерархических нечетких систем до второго
уровня параллелизма на примере элементарных нечетких систем типа Така-
ги–Сугено. Спроектирована экспериментальная программная система для
исследования высоконагруженных иерархических систем нечеткого логиче-
ского вывода на основе многоуровневого параллелизма второго уровня
с поддержкой вычислений на графических ускорителях NVIDIA.
Рис. 5. Сравнительная характеристика теоретической и экспериментальных оценок
ускорения для иерархических нечетких систем
Теоретическая оценка ускорения 2-го ур. параллелизма
Параллелизм 1-го ур. — MPI 24 процессора
Параллелизм 2-го ур. — NVidia CUDA Pascal 6.1
У
ск
ор
ен
ие
,
ра
з
n
Организация нечеткого логического вывода на основе многоуровневого параллелизма
Системні дослідження та інформаційні технології, 2018, № 3 109
Полученные оценки ускорения демонстрируют, что параллельная схе-
ма второго уровня параллелизма при одних и тех же экспериментальных
данных дает ускорение значительно больше, нежели распараллеливание
первого уровня.
ЛИТЕРАТУРА
1. Zadeh L.A. The concept of a linguistic variable and its application to approximate
reasoning / L.A. Zadeh // Information Sciences. — 1975. — Vol. 8, N 8. —
P. 199–249, 301–357.
2. Wang D. A survay of hierarchical fuzzy systems (invited paper) / D. Wang, X. Zeng,
J.A. Keane // International journal of computational cognition. — 2006. —
Vol. 4, N 1. — P.18–29.
3. Ершов С.В. Принципы построения нечетких мультиагентных систем в распре-
деленной среде / С.В. Ершов // Компьютерная математика. — 2009. —
№ 2. — C. 54–61.
4. Yager R.R. On a hierarchical structure for fuzzy modeling and control / R.R. Yager //
IEEE Trans. Syst. Man Cybern. — 1993. — N 23. — P. 1189–1197.
5. Cordon O. Linguistic modeling by hierarchical systems of linguistic rules / O. Cor-
don, F. Herrera, I. Zwir // IEEE Trans. Fuzzy Syst. — 2002. — N 10. — P. 2–20.
6. Torra V.A. review of the construction of hierarchical fuzzy systems / V.A. Torra //
Int. J. Intell. Syst. — 2002. — N 17. — P. 531–543.
7. Леоненков А.В. Нечеткое моделирование в среде MATLAB и fuzzyTECH /
А.В. Леоненков. — СПб.: БХВ, 2005. — 736 с.
8. Воеводин В.В. Параллельные вычисления / В.В. Воеводин, Вл.В. Воеводин. —
СПб.: БХВ-Петербург, 2002. — 608 с.
9. Пономаренко Р.М. Моделі паралельних ієрархічних систем для нечіткого
логічного виведення / Р.М. Пономаренко // Комп’ютерна математика. —
2017. — № 2. — С. 37–45.
10. Єршов С.В. Метод побудови паралельних систем нечіткого логічного виведен-
ня на основі графічних прискорювачів / С.В. Єршов, Р.М. Пономаренко //
Проблеми програмування. — 2017. — № 4. — С. 3–15.
11. Єршов С.В. Паралельні моделі багаторівневих нечітких систем Такагі-Сугено /
С.В. Єршов, Р.М. Пономаренко // Проблеми програмування. — 2016. —
№ 1. — С. 141–149.
12. Єршов С.В. Ярусно-паралельна модель обчислень для логічного виведення
у нечітких багаторівневих системах / С.В. Єршов, Р.М. Пономаренко //
Комп’ютерна математика. — 2016. — № 1. — С. 28–36.
Поступила 03.09.2018
|
| id | journaliasakpiua-article-150221 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Russian |
| last_indexed | 2025-07-17T10:24:13Z |
| publishDate | 2018 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/8e/f83bb6358893c91f9ccc7f99b363568e.pdf |
| spelling | journaliasakpiua-article-1502212019-01-17T13:31:43Z Organizing the fuzzy inference based on multilevel parallelism Организация нечеткого логического вывода на основе многоуровневого параллелизма Організація нечіткого логічного виведення на основі багаторівневого паралелізму Ponomarenko, Roman M. fuzzy inference multilevel parallelism speed-up fuzzy Takagi-Sugeno systems acceleration estimation нечеткий логический вывод многоуровневый параллелизм ускорение нечеткие системы типа Такаги-Сугено теоретическая оценка ускорения нечітке логічне виведення багаторівневий паралелізм прискорення нечіткі системи типу Такагі-Сугено теоретична оцінка прискорення In this paper, a method for constructing hierarchical systems of fuzzy inference based on multilevel parallelism, in particular, second-level parallelism, is developed, theoretically substantiated and implemented. This approach is designed to accelerate the computation of hierarchical fuzzy systems having complex dependency graphs between blocks of fuzzy rules. The concept of multilevel parallelism is formulated and presented. The notion of the level of parallelism is introduced. The theorem is formulated and proved, and a method for theoretical estimation of the maximum possible acceleration for systems constructed on the basis of parallelism of the level n is developed. An approach to designing hierarchical fuzzy systems based on multilevel parallelism for NVIDIA graphics accelerators is developed. Using NVIDIA CUDA technology, an experimental software system was designed for hierarchical systems of fuzzy inference based on multilevel parallelism for systems having complex graphs of dependencies between blocks of fuzzy rules. Experimental estimates of the acceleration are obtained. Also, based on the developed method, theoretical estimates of the maximum possible acceleration are found. A comparative characteristic of the theoretical and experimental estimates of the acceleration of hierarchical fuzzy systems is given. Разработан, теоретически обоснован и реализован метод построения иерархических систем нечеткого логического вывода на основе многоуровневого параллелизма, в частности параллелизма второго уровня. Сформулирована концепция многоуровневого параллелизма, введено понятие уровня параллелизма. Сформулирована и доказана теорема, разработан метод теоретической оценки максимально возможного ускорения для систем, построенных на базе параллелизма уровня n, а также подход к проектированию иерархических нечетких систем на основе многоуровневого параллелизма для графических ускорителей NVIDIA. Спроектирована экспериментальная программная система для иерархических нечетких систем на основе многоуровневого параллелизма и технологии CUDA, имеющих сложные графы зависимостей между блоками нечетких правил. На основе разработанного метода вычислены теоретические оценки максимального ускорения; получены экспериментальные оценки ускорения для иерархических сложных систем нечеткого логического вывода. Розроблено, теоретично обґрунтовано і реалізовано метод побудови ієрархічних систем нечіткого логічного виведення на основі багаторівневого паралелізму, зокрема паралелізму другого рівня. Сформульовано концепцію багаторівневого паралелізму, уведено поняття рівня паралелізму. Сформульовано і доведено теорему, розроблено метод теоретичного оцінювання максимально можливого пришвидшення для систем, побудованих на базі паралелізму рівня n, а також підхід до проектування ієрархічних нечітких систем на основі багаторівневого паралелізму для графічних прискорювачів NVIDIA. Запроектовано експериментальну програмну систему для ієрархічних нечітких систем на основі багаторівневого паралелізму і технології CUDA, що мають складні графи залежностей між блоками нечітких правил. На підставі розробленого методу обчислено теоретичні оцінки максимального пришвидшення та отримано експериментальні оцінки пришвидшення для ієрархічних складних систем нечіткого логічного виведення. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2018-10-16 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/150221 10.20535/SRIT.2308-8893.2018.3.09 System research and information technologies; No. 3 (2018); 98-109 Системные исследования и информационные технологии; № 3 (2018); 98-109 Системні дослідження та інформаційні технології; № 3 (2018); 98-109 2308-8893 1681-6048 ru https://journal.iasa.kpi.ua/article/view/150221/149358 Copyright (c) 2021 System research and information technologies |
| spellingShingle | нечітке логічне виведення багаторівневий паралелізм прискорення нечіткі системи типу Такагі-Сугено теоретична оцінка прискорення Ponomarenko, Roman M. Організація нечіткого логічного виведення на основі багаторівневого паралелізму |
| title | Організація нечіткого логічного виведення на основі багаторівневого паралелізму |
| title_alt | Organizing the fuzzy inference based on multilevel parallelism Организация нечеткого логического вывода на основе многоуровневого параллелизма |
| title_full | Організація нечіткого логічного виведення на основі багаторівневого паралелізму |
| title_fullStr | Організація нечіткого логічного виведення на основі багаторівневого паралелізму |
| title_full_unstemmed | Організація нечіткого логічного виведення на основі багаторівневого паралелізму |
| title_short | Організація нечіткого логічного виведення на основі багаторівневого паралелізму |
| title_sort | організація нечіткого логічного виведення на основі багаторівневого паралелізму |
| topic | нечітке логічне виведення багаторівневий паралелізм прискорення нечіткі системи типу Такагі-Сугено теоретична оцінка прискорення |
| topic_facet | fuzzy inference multilevel parallelism speed-up fuzzy Takagi-Sugeno systems acceleration estimation нечеткий логический вывод многоуровневый параллелизм ускорение нечеткие системы типа Такаги-Сугено теоретическая оценка ускорения нечітке логічне виведення багаторівневий паралелізм прискорення нечіткі системи типу Такагі-Сугено теоретична оцінка прискорення |
| url | https://journal.iasa.kpi.ua/article/view/150221 |
| work_keys_str_mv | AT ponomarenkoromanm organizingthefuzzyinferencebasedonmultilevelparallelism AT ponomarenkoromanm organizaciânečetkogologičeskogovyvodanaosnovemnogourovnevogoparallelizma AT ponomarenkoromanm organízacíânečítkogologíčnogovivedennânaosnovíbagatorívnevogoparalelízmu |