О модификации алгоритма распределения программы пользователя для реализации его на ПЛИС
Рассмотрен алгоритм распределения программы пользователя по процессорам PIM-системы и предложена модификация модулей данного алгоритма для дальнейшей реализации на ПЛИС. Розглянуто алгоритм розподілу програми користувача по процесорам PIM-системи і запропонована модифікація модулів даного алгоритму...
Збережено в:
| Опубліковано в: : | Комп’ютерні засоби, мережі та системи |
|---|---|
| Дата: | 2016 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2016
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/122865 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | О модификации алгоритма распределения программы пользователя для реализации его на ПЛИС / Е.В. Елисеева // Комп’ютерні засоби, мережі та системи.— 2016.— № 15.— С. 67-73.— Бібліогр.: 5 назв.— рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860253863934689280 |
|---|---|
| author | Елисеева, Е.В. |
| author_facet | Елисеева, Е.В. |
| citation_txt | О модификации алгоритма распределения программы пользователя для реализации его на ПЛИС / Е.В. Елисеева // Комп’ютерні засоби, мережі та системи.— 2016.— № 15.— С. 67-73.— Бібліогр.: 5 назв.— рос. |
| collection | DSpace DC |
| container_title | Комп’ютерні засоби, мережі та системи |
| description | Рассмотрен алгоритм распределения программы пользователя по процессорам PIM-системы и предложена модификация модулей данного алгоритма для дальнейшей реализации на ПЛИС.
Розглянуто алгоритм розподілу програми користувача по процесорам PIM-системи і запропонована модифікація модулів даного алгоритму з метою подальшої реалізації на ПЛІС.
It was considered the user program allocation algorithm for PIM-processor system and proposed a modification of the algorithm modules for further implementation on CPLD.
|
| first_indexed | 2025-12-07T18:46:41Z |
| format | Article |
| fulltext |
Комп’ютерні засоби, мережі та системи. 2016, № 15 67
E. Eliseeva
ABOUT MODIFICATION
OF THE ALGORITHM USER
DISTRIBUTION PROGRAM
FOR IMPLEMENTATION
ITS ON СPLD
It was considered the user program
allocation algorithm for PIM-
processor system and proposed a
modification of the algorithm mod-
ules for further implementation on
CPLD.
Key words: PIM-system, CPLD,
scheduling algorithm.
Розглянуто алгоритм розподілу
програми користувача по про-
цесорам PIM-системи і запропо-
нована модифікація модулів да-
ного алгоритму з метою подаль-
шої реалізації на ПЛІС.
Ключові слова: PIM-система,
ПЛІС, алгоритм розподілу.
Рассмотрен алгоритм распре-
деления программы пользователя
по процессорам PIM-системы и
предложена модификация моду-
лей данного алгоритма для даль-
нейшей реализации на ПЛИС.
Ключевые слова: PIM-система,
ПЛИС, алгоритм распределения.
Е.В. Елисеева, 2016
УДК 004.2; 004.272.43
Е.В. ЕЛИСЕЕВА
О МОДИФИКАЦИИ АЛГОРИТМА
РАСПРЕДЕЛЕНИЯ ПРОГРАММЫ
ПОЛЬЗОВАТЕЛЯ ДЛЯ РЕАЛИЗАЦИИ
ЕГО НА ПЛИС
Предпосылками для оптимизации алгоритма
посредством реализации отдельных его час-
тей на ПЛИС являются: многочисленное вы-
полнение одних и тех же операций над мно-
жеством данных; возможность выделить в
алгоритме отдельные фрагменты, несвязан-
ные по данным, которые могут выполняться
независимо друг от друга.
Для оптимизации рассмотрен алгоритм
распределения блоков программы поль-
зователя по процессорам PIM-системы
[1–5] и выделены ряд фрагментов алгорит-
ма, которые можно модифицировать для
последующей реализации на ПЛИС.
В частности модуль для оценки веса бло-
ков содержит многократные обращения к
системе команд ведущего процессора
(СК VP) и системе команд процессорного
ядра (СК PYA) с целью найти совпадение
кода операции из блока программы пользо-
вателя и кода команды из СК VP и СК PYA
для вычисления времени выполнения опе-
рации или, чтобы сделать вывод о невоз-
можности выполнения этой операции на
некотором процессоре системы. С другой
стороны информация о СК VP и СК PYa
хранится отдельно, следовательно, такой по-
иск в каждой из них можно организовать
независимо друг от друга (отдельно для СК
PYa и СК VP). Кроме того, поскольку про-
грамма пользователя разделена на незави-
симые по данным блоки, т. е. возможность
вести оценку веса параллельно сразу для не-
скольких блоков.
Е.В. ЕЛИСЕЕВА
Комп’ютерні засоби, мережі та системи. 2016, № 15 68
Исходный фрагмент алгоритма распределения приложения по процессо-
рам PIM-системы (модуль оценки веса каждого блока программы пользователя)
приведен в [4].
Укрупненная блок-схема алгоритма работы модуля оценки веса одного бло-
ка программы пользователя после модификации с целью параллельной реализа-
ции частей данного алгоритма на ПЛИС показана на рис. 1. Закрашенными
стрелками отмечены части алгоритма, где осуществляется обмен данными и ре-
зультатами вычислений с ПЛИС.
Здесь рассмотрен алгоритм оценки веса одного блока программы пользова-
теля. Результатом работы данного алгоритма будет: вес блока для VP, вес для
PYa, если возможно выполнение на PYa, и сигналы ТЕG_1 и ТЕG_2, которые
необходимы для работы последующих модулей программы распределения. Их
возможные значения приведены в табл. 1.
Для каждого блока программы пользователя предварительно проводится
лексический анализ содержимого блока, он заключается в посимвольном считы-
вании кода и выделении лексем (последовательностей допустимых символов,
понятных компилятору языка программирования). В результате лексического
анализа выдается список токенов, входящих в данный блок. Токены представ-
ляются в виде структуры, состоящей из кода токена, указывающего на тип лек-
семы (например, число, операция и т. д.) и самой лексемы. Осуществляется про-
смотр всего списка токенов, и для каждого токена выполняется проверка, соот-
ветствует ли этот токен какой-либо операции.
Если рассматриваемый токен соответствует операции, то на входы ПЛИС
передается значение кода этой операции COPs_BPr_q(7:0) и выполняются под-
программы А (рис. 2) или B (рис. 3), в зависимости от значения flagPYa, кото-
рый указывает может ли рассматриваемый блок программы пользователя вы-
полнится на PYa. Изначально, flagPYa равен 1, и сбрасывается в 0 в подпро-
грамме B сразу, как только будет найдена хотя бы одна операция, код которой
отсутствует СК PYa и, следовательно, она не может быть выполнена на PYa.
Это значит, что и весь блок программы пользователя, содержащий данную опе-
рацию, не может выполняться на PYa, поэтому нет смысла проводить поиск для
остальных операций из блока в СК PYa.
Заметим, что при реализации алгоритма предполагалось, что СК PYa явля-
ется подмножеством СК VP, поскольку в силу архитектурных особенностей
PIM-системы PYa имеют урезанную систему команд по сравнению с VP, и про-
грамма пользователя не содержит «недопустимых» операций, т. е. тех, которые
не могут быть выполнены на VP.
В подпрограмме A осуществляется поиск соответствующей команды в
СК VP, на ПЛИС при этом задействуется для сравнения только канал VP из
BLOCK_ANALIZ [5]. Если найдено совпадение кодов операции из блока про-
граммы пользователя и кода команды из СК VP, то в этом случае начинает работу
блок суммирования BLOCK_SUM_T_VP/PYa на ПЛИС [5], который перемножает
полученные значения Tr_VP_sq(7:0) (вес команды) и Repit_Ts_BPr_VP_q(7:0) (ко-
личество повторений), и накапливает результат. Переход к следующим шагам ал-
О МОДИФИКАЦИИ АЛГОРИТМА РАСПРЕДЕЛЕНИЯ ПРОГРАММЫ ПОЛЬЗОВАТЕЛЯ …
Комп’ютерні засоби, мережі та системи. 2016, № 15 69
flagPYa=1
Взять очередной
токен из списка
токенов
Получен признак
конца списка
токенов?
Да
Нет
Код токена
соответствует коду
операции?
Команды программы
Команды программы
Передать на входы
ПЛИС COPs BPr
q(7:0)
Да Нет
B
flagPYa=1
Да
flagPYa=0
Получить с выходов ПЛИС
Tq_Sum_P_BPr_(15:0)
Tq_Sum_V_BPr_(15:0) и
Тег_1, Тег_2
Команды программы
Aк / о т П Л И С
к П Л И С
к / о т П Л И С
о т П Л И С
РИС. 1. Укрупненная блок-схема модуля оценки веса модифицированного алгоритма
распределения блоков программы пользователя по процессорам PIM-системы c
указанием входов и выходов на ПЛИС
Е.В. ЕЛИСЕЕВА
Комп’ютерні засоби, мережі та системи. 2016, № 15 70
ТАБЛИЦА 1. Значения ТЕG_1 и ТЕG_2
Обозначение T(PYa) < T(VP) T(PYa) > T(VP) T(PYa) = T(VP)
Тег_1 0 1 1
Тег_2 1 0 1
i - счетчик команд из
системы команд VP
i=1
F
i≤K1
K1 – количество
команд в системе
команд VP
Да
Передать на входы
ПЛИС
и COMr_VP_q(7:0)
Передать на входы
ПЛИС сигналы
START_BLOCK_AN,
Id_VP
Принять с выходов
ПЛИС cигнал
Equil_VP
Начало подпрограммы А
Конец подпрограммы А
РИС. 2. Подпрограмма A. Определение веса для VP очередной операции в блоке для случая,
если блок может выполняться только на VP
О МОДИФИКАЦИИ АЛГОРИТМА РАСПРЕДЕЛЕНИЯ ПРОГРАММЫ ПОЛЬЗОВАТЕЛЯ …
Комп’ютерні засоби, мережі та системи. 2016, № 15 71
j – счетчик команд из системы
команд PYa
i - счетчик команд из системы
команд VP
Fl - определяет какой из каналов
(VP или PYa) будет задействован
Fl=0; i=1; j=1
Fl=0 C
Да
Fl=2 E
Да
Fl=1 D
Да
(i≤K1) ИЛИ (j≤K2)
K1 и K2 – количество
команд в системе
команд VP и PYa
соответственно
Да
Начало подпрограммы B
Конец подпрограммы B
РИС. 3. Подпрограмма B. Поиск соответствия в системах команд соответствующих
процессоров и определение веса операции для PYa и VP
горитма происходит без ожидания результата выполнения умножения с
накоплением от ПЛИС, тем самым обеспечивается возможность параллельной
работы программы оценки веса и вычислений на ПЛИС.
Подпрограмма B будет выполняться в случае, если flagPYa=1, т. е. если все
рассмотренные ранее операции в блоке могут быть выполнены на PYa или же
рассматривается самая первая операция в блоке. Просмотр СК VP, СК PYa и
поиск в них совпадении кодов операций блока программы пользователя с
кодами команд из СК VP и СК PYa осуществляется в цикле, выход из которого
возможен только тогда, когда будут найдены совпадения для обоих процессоров
или только для VP, но при этом будет установлена невозможность выполнения
некоторой операции на PYa. Здесь возможны следующие варианты: 1) вес
рассматриваемой операции еще не оценен ни для одного из процессоров, в этом
случае параллельно на ПЛИС можно осуществить сравнение кода операции с
очередными кодами команд из СК VP и СК PYa, т. е. возможна параллельная
Е.В. ЕЛИСЕЕВА
Комп’ютерні засоби, мережі та системи. 2016, № 15 72
работа на ПЛИС двух каналов VP и PYa; 2) вес рассматриваемой операции уже
оценен для одного из процессоров, тогда поиск совпадений осуществляется
только в системе команд другого процессора. Чтобы определить какой из
вариантов необходимо выбрать в цикле используется значение флага Fl,
который можно получить в зависимости от значений сигналов Equal_VP и
Equal_PYa (табл. 2).
ТАБЛИЦА 2. Значения флага Fl в зависимости от значений Equal_PYa и Equal_VP
Equal_ VP Equal_ PYa Fl = Equal_ VP <<1+ Equal_ PYa
0 0 0
0 1 1
1 0 2
1 1 3
Если значение Fl = 0, это значит, что для оцениваемой операции из блока
программы пользователя не найдено пока совпадений ни в СК VP, ни в СК
PYa. В этом случае управление переходит к подпрограмме C, в которой парал-
лельно задействуются каналы VP и PYa на ПЛИС для поиска в СК PYa и СК
VP.
При необходимости задействуется только один канал PYa или VP. Это
происходит в том случае, если блок вообще не может быть выполнен на PYa или
уже получен вес команды для одного из процессоров во время предыдущей
итерации цикла, показанного на рис. 3. Таким образом, если значение флага Fl
равно 1 или 2, то выполняется одна из подпрограмм D или E соответственно.
В каждой из подпрограмм С, D, E вычисляется новое значение флага Fl,
чтобы иметь возможность использовать его при следующей итерации цикла, по-
казанного на рис. 3.
В каждой из подпрограмм С, D, E в зависимости от результатов, полученных
с ПЛИС, проводится анализ сигналов Equal_VP и Equal_PYa. Значение
Equal_VP показывает было ли совпадение кода операции из блока программы
пользователя с кодом рассматриваемой команды из СК_VP. Аналогично,
значение Equal_PYa показывает было ли совпадение кода операции с кодом
рассматриваемой команды из СК PYa.
Если значение Equal_VP или Equal_PYa равно нулю, то совпадения для
СК_VP или СК_PYa соответсвенно не было. В этом случае увеличивается на
единицу значение соответствующего счетчика i (счетчик команд из СК_VP) или
j (счетчик команд из СК_PYa). Значения этих счетчиков используются в
качестве критериев для выполнения итераций в цикле, который представлен в
подпрограмме B на рис. 3.
Если значение Equal_VP или Equal_PYa равно единице, то совпадение в
СК_VP или СК_PYa имело место и рассматриваемой операции присваивается
такой же вес для VP или PYa, как и вес соответствующей ей команды из СК_VP
или СК_PYa в зависимости от того, где было найдено совпадение. На ПЛИС
передаются сигналы запускающие вычисление суммы с накоплением
О МОДИФИКАЦИИ АЛГОРИТМА РАСПРЕДЕЛЕНИЯ ПРОГРАММЫ ПОЛЬЗОВАТЕЛЯ …
Комп’ютерні засоби, мережі та системи. 2016, № 15 73
(добавление веса соответствующей операции к весу всего блока) для разных
процессоров. На ПЛИС так же передаются значения найденного веса для VP –
Tr_VP_sq(7:0) или же Tj_PYa_sq(7:0), если речь идет о весе для PYa и значение
Repit_Ts_BPr_VP(PYa)_q(7:0), которое соответствует количеству повторений
данной операции в рассматриваемом блоке программы пользователя.
При этом не ожидается возвращение результата с ПЛИС и могут
выполняться последующие команды алгоритма. Результат в виде суммы с
накоплением будет затребован с ПЛИС позже, когда будут рассмотрены и
оценены все операции из заданного блока программы пользователя (по
завершению работы цикла рис. 3). В этом случае результатом будут значения
веса (времени выполнения) заданного блока для различных процессоров VP и
PYa – на рис. 1 эти значения обозначены соответственно Tq_Sum_P_BPr_(15:0)
и Tq_Sum_V_BPr_(15:0), что позволяет убрать из алгоритма, приведенного в [4]
часть связанную с вычислением значений веса всего блока для VP и PYa. Значе-
ния ТЕG_1 и ТЕG_2, возвращаемые с ПЛИС, дают возможность оценить вес
блока для VP и PYa не прибегая к дополнительным сравнениям этих весов при
распределении блоков программы пользователя по процессорам PIM-системы,
т. е. сокращают время работы последующих модулей алгоритма распределения
программы пользователя, который рассмотрен в [4].
Полученная модификация алгоритма оценки веса блока программы
пользователя с реализацией отдельных его фрагментов на ПЛИС дает ускорение
оценки веса блока программы пользователя приблизительно в 1,5–2 раза (в
зависимости от содержимого блока) за счет параллельного выполнения
некоторых вычислений на ПЛИС, возможности параллельного выполнения ко-
манд программы распределения и вычислений на ПЛИС, а также за счет
переноса части вычислений на ПЛИС, где они выполняются быстрее.
1. Яковлев Ю.С., Елисеева Е.В. О реализации распределения приложения для параллельного
выполнения на PIM-системе. Інформаційні технології та комп’ютерна інженерія. 2011.
№ 3. С. 53–59.
2. Пат. на винахід 103535 Україна, МПК G06F 9/44, G06F 9/45. Спосіб розподілу програми
користувача для комп'ютерної системи / Сергієнко І.В., Палагін О.В., Боюн В.П.,
Яковлєв Ю.С., Єлісєєва О.В.; Інститут кібернетики імені В.М. Глушкова НАН України;
заявл. 03.01.2012; опубл. 25.10.2013, Бюл. № 20.
3. Пат.на винахід 104039 Україна, МПК G06F 9/44, G06F 9/45. Система для розподілу
програми користувача / Сергієнко І. В. Палагін О. В., Боюн В. П., Яковлєв Ю. С.,
Єлісєєва О. В.; Інститут кібернетики ім. В.М. Глушкова НАН України; заявл. 27.02.2012;
опубл. 25.12.2013, Бюл. № 24.
4. Елисеева Е.В. О распараллеливании пользовательских задач в распределенных
компьютерных системах типа “процессор-в-памяти”. Математические системы и
машины. 2010. № 4. С. 68–81.
5. Яковлев Ю.С., Елисеева Е.В. Применение ПЛИС для схемной реализации модулей
программы распределения приложений для PIM-системы. Математичні машини і
системи. 2015. № 2. С. 28–39.
Получено 01.11.2016
|
| id | nasplib_isofts_kiev_ua-123456789-122865 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1817-9908 |
| language | Russian |
| last_indexed | 2025-12-07T18:46:41Z |
| publishDate | 2016 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Елисеева, Е.В. 2017-07-21T10:39:07Z 2017-07-21T10:39:07Z 2016 О модификации алгоритма распределения программы пользователя для реализации его на ПЛИС / Е.В. Елисеева // Комп’ютерні засоби, мережі та системи.— 2016.— № 15.— С. 67-73.— Бібліогр.: 5 назв.— рос. 1817-9908 https://nasplib.isofts.kiev.ua/handle/123456789/122865 004.2; 004.272.43 Рассмотрен алгоритм распределения программы пользователя по процессорам PIM-системы и предложена модификация модулей данного алгоритма для дальнейшей реализации на ПЛИС. Розглянуто алгоритм розподілу програми користувача по процесорам PIM-системи і запропонована модифікація модулів даного алгоритму з метою подальшої реалізації на ПЛІС. It was considered the user program allocation algorithm for PIM-processor system and proposed a modification of the algorithm modules for further implementation on CPLD. ru Інститут кібернетики ім. В.М. Глушкова НАН України Комп’ютерні засоби, мережі та системи О модификации алгоритма распределения программы пользователя для реализации его на ПЛИС About modification of the algorithm user distribution program for implementation its on CPLD Article published earlier |
| spellingShingle | О модификации алгоритма распределения программы пользователя для реализации его на ПЛИС Елисеева, Е.В. |
| title | О модификации алгоритма распределения программы пользователя для реализации его на ПЛИС |
| title_alt | About modification of the algorithm user distribution program for implementation its on CPLD |
| title_full | О модификации алгоритма распределения программы пользователя для реализации его на ПЛИС |
| title_fullStr | О модификации алгоритма распределения программы пользователя для реализации его на ПЛИС |
| title_full_unstemmed | О модификации алгоритма распределения программы пользователя для реализации его на ПЛИС |
| title_short | О модификации алгоритма распределения программы пользователя для реализации его на ПЛИС |
| title_sort | о модификации алгоритма распределения программы пользователя для реализации его на плис |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/122865 |
| work_keys_str_mv | AT eliseevaev omodifikaciialgoritmaraspredeleniâprogrammypolʹzovatelâdlârealizaciiegonaplis AT eliseevaev aboutmodificationofthealgorithmuserdistributionprogramforimplementationitsoncpld |