Оптимальное распараллеливание задач диспетчеризации в распределенных энергоограниченных компьютерных системах на базе мсu / fрgа модулей

Тип работы:
Реферат
Предмет:
ТЕХНИЧЕСКИЕ НАУКИ


Узнать стоимость

Детальная информация о работе

Выдержка из работы

УДК 004. 75
ОПТИМАЛЬНОЕ РАСПАРАЛЛЕЛИВАНИЕ ЗАДАЧ ДИСПЕТЧЕРИЗАЦИИ В РАСПРЕДЕЛЕННЫХ ЭНЕРГООГРАНИЧЕННЫХ КОМПЬЮТЕРНЫХ СИСТЕМАХ
НА БАЗЕ MCU/FPGA МОДУЛЕЙ
© 2014
М. П. Мусиенко, доктор технических наук, профессор, заведующий кафедрой информационных технологий и программных систем
В. Ю. Савинов, аспирант Я. М. Крайнык, аспирант
Черноморский государственный университет имени Петра Могилы, Николаев (Украина)
Ключевые слова: распределенные компьютерные системы- оптимальное распараллеливание- диспетчеризация- MCU и FPGA модули- энергопитание.
Аннотация: В статье рассмотрена задача эффективного распределения энерго- и информационных ресурсов в распределенных энергоограниченных компьютерных системах на основе микроконтроллеров и программируемых вентильных матриц за счет оптимального распараллеливания задач диспетчеризации. Рассмотрен пример распараллеливания вычислительных ресурсов между двумя модулями для решения задач оптимального управления станком с 3D позиционированием.
Миниатюризация электронной техники приводит к широкому использованию вычислительных элементов (микроконтроллеров, вентильных матриц, SoC и пр.) в различных удаленных узлах: датчиках, актуато-рах и прочих исполнительных элементах. В этом случае особо остро стает задача эффективного энергопотребления, так как удаленные узлы, как правило, питаются от автономных источников энергии. Решение данной проблемы возможно за счет эффективной диспетчеризации выполняемых заданий, оптимального распараллеливания потоков данных и команд между всеми вычислительными модулями системы. Таким образом, задача оптимального распараллеливания задач диспетчеризации в распределенных энергоограниченных компьютерных системах является весьма важной и актуальной проблемой.
На сегодняшний день существует множество различных решений в этой области. Например, использование подхода EDF (earliest deadline first) — минимизация возможных запаздываний за счет выбора частоты процессора [1]- методы диспетчеризации задач в распределенных компьютерных системах на основе гибридного метода, который представляет собой сочетаний жадных и алгоритмов и усовершенствованного эволюционного метода [2] и многие другие. Однако основным недостатком всех этих методов является то, что при их разработке не учитывался критерий ограниченного энергопотребления системы. Кроме того, в этих методах не рассматривался принцип распараллеливания, который широко используется для решения множества задач.
Целью данной работы является решение задачи эффективного распределения энерго- и информационных ресурсов в распределенных энергоограниченных компьютерных системах на основе микроконтроллеров (MCU — Micro Controller Unit) и программируемых вентильных матриц (FPGA — Field-Programmable Gate Array) за счет оптимального распараллеливания задач диспетчеризации.
Для беспрерывной работы удаленного модуля необходимо выполнение условия:
ЕЗАП+ЕПОСУП'-ЕЭК-ЕПРОЦ& gt-0>-
где Езап — запасенная энергия- ЕПОСУП — энергия поступления от сторонних источников (например, регенерируемых источников энергии) — ЕЭК — энергия потребления электронных компонентов (АЦП, датчиков, усилителей и др.) — ЕПРОЦ — энергия потребления микропроцессором.
Для увеличения срока беспрерывной работы в статье рассматривается метод оптимальной диспетчеризации, которая позволит уменьшить величину энергии потребления процессора ЕПРОЦ.
При использовании подхода EDF запаздывание всех задач, поступивших на выполнение, будет минимальным. Режим работы sk процессора для г-ой работы с наивысшим приоритетом находится следующим образом:
Sk = max& quot-*^, где uk i — текущий коэффициент загрузки процессора:
i
uk, i = X ek, p 1 dkii, p=1
ek p — оставшееся время выполнения p-го задания, i=1. Пк,
к — номер набора работ, n — число работ в наборе к.
Обозначим множество режимов работ как R = {r1. rz}. Частота процессора fi при выполнении г-ой
работы будет определяться из выражения:
fi = minz=1 {rz I rz ^ sk } X fmax ,
где y — количество режимов, fmax — максимальная частота процессора.
Таким образом, энергопотребление процессора при выполнении г-ой работы будет равным
E = CU? f,
где С — динамическая емкость-
и — напряжение на процессоре при выполнении /'--ой работы.
Постановку задачи диспетчеризации задач в распределенных энергоограниченных системах осуществим используя известные методы [2]. Пусть в момент времени / в распределенную систему, состоящую из п распределенных модулей, для решения поступило некоторое число задач т, где п и т — некоторые натуральные числа. Каждый модуль имеет свое значение мощности N у, у = 1, п. Каждое задание имеет свой весовой коэффициент длительности, а, г = 1, т со значением мощности для ее выполнения N°. В задании необходимо распределить все задачи для решения в вычислительной системе таким образом, чтобы вычислительные и энергетические ресурсы были использованы максимально эффективно.
Зададим это значение через Ц, которое определяется как:

= Ыг ¦ а.
Существует некоторая матрица оптимального распределения задач, в которой каждый элемент может принимать следующие значения:
Гху = 1, г — ое задание назначено у — му модулю-
I х у = 0, г — ое завдание не назначено у — му модулю.
Если вычислительные и энергетические ресурсы используются наиболее эффективно, максимальное время работы модуля по обработке задания будет минималь-

ным, т. е. max
Z xj • tv
V i=i /
^ min. Это означает, что
суммарное время решения всех задач в вычислительной системе минимально при времени вычисления на каждом из модулей системы максимально приближенном друг к другу. Для приближения к минимуму максимального среди реально полученных значений вводится огра-
ничения
Z
1=1
xij ¦ zi & lt- VJ
где zi — объем необходимой
оперативной памяти для /-го задания- V у — объем необходимой оперативной памяти у-го модуля (у = 1, п) [2].
Таким образом, общая математическая модель для решения задания оптимального распараллеливания задач диспетчеризации имеет вид:
(
max
Z xj ¦ tn
л
V 1=1
m
^ min, при Z Xj — z & lt- Vj, j = 1, n, i=1
ЕЗАП + ЕПОСТУП ЕЭК ЕПРОЦ & gt- 0,
k _
СZ Ui2fi ^ min, nPU f = minz=l (rz I rz & gt- sk } X f i =1
В качестве примера рассмотрим компьютерную систему управления позиционированием головки 3D-системы (принтера, станка с ЧПУ и пр.), построенную с использованием двух вычислительных ресурсов -одного MCU и одного модуля FPGA. Чаще всего такие системы строят на основе использования одного MCU, который, помимо выполнения расчетных операций, осуществляет выполнение и других функций: передачу управляющих импульсов- прием информации с датчиков с последующей ее обработкой- контроль состояния системы с учетом показателей точности и надежности. Несмотря на возможность использования механизма прямого доступа к памяти (DMA — Direct Memory Access), что позволяет снять определенную нагрузку с основного модуля, программная модель MCU, как правило, не предусматривает возможность параллельного выполнения инструкций.
В отличие от MCU, модули FPGA предоставляют возможность добиться параллельного выполнения инструкций, за счет чего скорость обработки данных FPGA во многих случаях превосходит скорость MCU: например, для задачи построения геометрических примитивов в 2D-пространстве FPGA использует всего 4 тактовых импульса на один цикл интерполяции, в то время как показатели MCU для линейной и, особенно, для круговой интерполяции значительно больше -десятки тактовых импульсов [3]. При расчетах для третьей оси координат ^D-модели) преимущество будет еще больше.
Одновременное же использование двух модулей позволяет получить значительный выигрыш в производительности по сравнению с использованием одного MCU для той же задачи. Основным вопросом остается определение, каким образом оптимальнее всего распараллелить вычислительные задачи между модулями.
При организации параллельного взаимодействия MCU и FPGA также возникает задача синхронизации, которую можно решить методом «рандеву», при котором управляющее устройство блокирует дальнейшие действия до получения сигнала от расчетного модуля [4].
Схематическое распределение задач между модулями показано на рис. 1.
Наибольшая эффективность всех системы будет достигаться при минимальных простоях вычислительных модулей. В данном случае это соответствует одновременному окончанию вычислительных расчетов обоих модулей в момент времени t2.
Введем показатель коэффициента полезной работы модуля:
Up
x = -^ -100%,
Ua
где U p — количество тактов, затрачиваемых на полезную работу-
U a — общее количество тактов, на измеряемом участке времени.
Для определения эффективности будем использовать показатель квадратичного отклонения a, который определяет, насколько равномерно распределена нагрузка между модулями.
Рис. 1. Распределение задач между модулями
10 20 30 40 50 60 70 80 90 100 Доля вычислений для FPGA, %
Рис. 2. График зависимости, а от доли вычислительной нагрузки для FPGA
В этом случае оптимальным решением будет выполнение условия:
с =
1 n -- V (xi — x) ^ min- n^
i=1
X ^ max- i = (1,2) — n = 2.
Для экспериментальных исследований в качестве MCU был использован микроконтроллер архитектуры ARM Cortex-M4 на базе отладочного модуля STM32F4 Discovery. В качестве модуля FPGA использована плата Xilinx Spartan 6. Для передачи данных между модулями использовался интерфейс SPI, обеспечивающий скорость передачи данных более 30 Мбит/с.
Полученные опытным путем результаты исследований приведены на рис. 2.
Как видно из рис. 2, оптимальное решение задачи, т. е. выполнение условия (9), выполняется при распределении вычислительных ресурсов между модулями FPGA и MCU равном 65% и 35% соответственно.
Таким образом, в работе предложено решение задачи эффективного распределения вычислительных ресурсов в распределенных энергоограниченных компьютерных системах на основе MCU и FPGA модулей, получено математическое выражение для условия оп-
тимального распараллеливания задач диспетчеризации. Рассмотрен пример распараллеливания вычислительных ресурсов между двумя модулями для решения задач оптимального управления станком с 3D позиционированием.
СПИСОК ЛИТЕРАТУРЫ
1. Манухин С. В., Сухонос М. И. Алгоритмы оптимизации энергопотребления и повышения эффективности процессоров с масштабированием частоты и напряжения гетерогенного кластера. / Манухин С. В., Сухонос М. И. // - Труды Международной конференции «Параллельные и распределенные вычислительные системы» PDCS 2013 (Украина, Харьков, 13−14 марта 2013 года).
2. Тягунова М. Ю. методы диспетчеризации задач в распределенных компьютерных системах: авто-реф. дис. на получение научной степени канд. техн. наук: спец. 05. 13. 05 «Компьютерные системы и компонетны» / М. Ю. Тягунова. — Кшв, 2010. — 18 с.
3. Денисов А. Применение FPGA и алгоритмов Бре-зенхема для повышения быстродействия в системах позиционирования. // Компоненты и технологии. -№ 10. — 2013. — с. 96−100.
4. Параллельные вычисления. [Электронный ресурс]. URL: http: //ru. wikipedia. org/wiki/Параллельные
вычисления
2
THE OPTIMAL PARALLELIZATION OF DISPATCH PROBLEMS IN ENERGY-RESTRICTED DISTRIBUTED COMPUTER SYSTEMS BASED
ON MCU/FPGA MODULES
© 2014
M.P. Musienko, doctor of technical sciences, professor, head of department of information technology and software systems, V.Y. Savinov, a graduate student Y. M Krainyk, a graduate student
The Black Sea State University named after Petro Mohyla, Nikolaev (Ukraine)
Keywords: the distributed computing system- the optimal parallelization- scheduling- MCU and FPGA modules- power consumption.
Annotation: In this article we consider the problem of energy-efficient distribution of information and resources in a distributed energy-restricted computer systems based on microcontrollers and FPGA through the optimal paralleliza-tion of tasks scheduling. An example of computing resources parallelization between two modules for solving optimal control of the machine with 3D positioning is given.

ПоказатьСвернуть
Заполнить форму текущей работой