Алгоритмы формирования вычислительного процесса в распределенных системах реального времени

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

ГНЦ РФ ОАО «Концерн «ЦНИИ «Электроприбор», Санкт-Петербург

Алгоритмы формирования вычислительного процесса в распределенных системах реального времени

Ю.М. Скородумов

Обычно под формированием вычислительного процесса понимается распределение ресурсов, таких как процессоры, каналы обмена, память и т.п. между исполняемыми задачами (программами) во времени [1]. Таким образом, можно выделить две основных проблемы: назначение и планирование. Содержание процедуры назначения состоит в соотнесении с каждым процессором некоторого списка решаемых на нем задач. Она предшествует любым вычислениям в многопроцессорных системах. Под планированием понимается поиск наилучшей упорядоченности для выполняемых заданий, удовлетворяющей заданному критерию. Следует отметить, что решение задачи назначения и планирования может производиться как одновременно, так и поэтапно. В случае поэтапного решения этих задач сначала производится назначение задач на процессоры, а затем их планирование (так называемая задача shop-scheduling). [2]

Для систем реального времени при решении задачи планирования дополнительно должно учитываться ограничение, вызванное периодичностью входного потока данных [1] и требующего учета производительности процессоров и пропускной способности каналов обмена на периоде. Оптимальное решение проблемы планирования может быть получено в рамках любого из обозначенных подходов переборными алгоритмами [2, 3], однако все они характеризуются экспоненциальной вычислительной сложностью, и в силу этого их применение в целом ряде приложений оказывается невозможным. По этой причине широкое распространение на практике получили субоптимальные алгоритмы, среди которых алгоритмы с конструктивными эвристиками [4, 5] и ненаправленного поиска [6]. В настоящем докладе обсуждается первая группа алгоритмов.

Алгоритмы, основанные на разрешимых классах систем

Эти алгоритмы [1, 5] планирования предназначены для использования в рамках двухэтапного подхода, когда проблема назначения уже решена. При этом предполагается, что рассматриваемое множество задач разбито на независимые группы задач, связанных отношением предшествования (далее задания). Планированию подлежат m независимых заданий , обрабатывающих входные данные, поступающие с периодом T. Каждое задание j-е задание состоит из задач длительностью . Все процессоры используемые процессоры из множества P имеют одинаковую производительность. Произведенное назначение заданий соответствует случаю flow shop [1], т.е. имеется m изоморфизмов , где - граф межзадачных связей j-го задания, - множество ребер, - множество вершин (задач), - граф межпроцессорных связей, - множество ребер, отражающих межпроцессорное взаимодействие, - множество процессоров. Вводится отношение доминирования на множестве P. На практике случай flow shop обычно возникает, когда в распределенной системе решается совокупность заданий, каждое из которых использует информацию со своего набора датчиков.

Определение. Процессор доминирует над процессором (), если .

С использованием этого отношения вводятся так называемые разрешимые классы систем (РКС), для которых существуют беспереборные оптимальные алгоритмы (ОА) линейной сложности для 3-х разрешимых классов, а также субоптимальный алгоритм (СА) для 4-го класса. На этих алгоритмах основывается предложенный автором приближенный алгоритм планирования на основе РКС для систем общего вида, характеризующийся также линейной сложностью [7]. На рисунке 1 приведена блок схема этого алгоритма.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рис. 1. Приближенный алгоритм планирования на основе РКС

Алгоритмы, основанные на методах сетевого упорядочивания

В случае, когда не ставится цель минимизации числа используемых процессоров, проблема планирования (назначения и планирования) может быть решена совместно, например, методами сетевого упорядочивания [4], когда на один процессор назначаются лишь задачи, связанные отношением предшествования. Подобная процедура может быть алгоритмизована, например, следующим образом.

Алгоритм 1

Определить критический вычислительный путь (КВП) в графе задания и сформировать конвейер процессоров (КП), реализующих критический путь, с учетом их загруженности E на периоде поступления информации T: E ? T.

Определить вершины слияния КВП с другими вычислительными путями (), определить директивные сроки для отрезков вычислительных путей, сливающихся с критическим.

Последовательно проанализировать вершины слияния: сопоставить с соответствующим , т.е. назначить на этот задачи .

Такой подход к организации вычислений позволяет добиться минимума времени выполнения вычислений в распределенных вычислительных системах, при этом пренебрегая затратами на необходимые вычислительные ресурсы.

Комбинированный алгоритм планирования

На практике возможна ситуация, когда в целях сокращения числа используемых процессоров оказывается целесообразным на фоне независимого размещения заданий на процессорах также и размещение некоторых фрагментов разных заданий на общих процессорах в соответствии с концепцией flow shop. Тогда предлагается использовать алгоритм планирования, представляющий собой комбинацию процедур из разделов 1 и 2. Алгоритм можно представить как состоящий из двух этапов. На первом этапе осуществляется распределение вычислительных ресурсов для независимо выполняемых фрагментов заданий методами сетевого упорядочивания. Одним из результатов этого этапа будет формирование директивных сроков для совместно реализованных фрагментов заданий. На втором этапе при помощи алгоритмов планирования для flow shop составляется расписание для фрагментов заданий, расположенных совместно Алгоритм 2 представляет собой такую организацию вычислений.

Алгоритм 2

Определить критический вычислительный путь (КВП) в графе задания и сформировать конвейер процессоров (КП), реализующих критический путь, с учетом их загруженности E на периоде поступления информации T: E ? T.

Определить вершины слияния КВП с другими вычислительными путями (), определить директивные сроки для отрезков вычислительных путей, сливающихся с критическим.

Последовательно проанализировать вершины слияния: сопоставить с соответствующими , т.е. назначить на этот задачи .

Назначить на этот задачи из других путей в соответствии с концепцией flow shop.

Составить расписание совместно назначенных фрагментов заданий при помощий приближенного алгоритма.

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

Литература

процессор пропускной канал

1. Колесов Н.В., Толмачева М.В., Юхта П.В. Системы реального времени. Планирование, анализ, диагностирование. СПб.: ОАО "Концерн "ЦНИИ "Электроприбор", 2014. 185 с.

2. Drozdowski M. Scheduling for Parallel Processing - Springer, 2009.

3. Burkard R.E., Dell'Amico M., Martello S. Assignment problems. Philadelphia: Society for Industrial and Applied Mathematics. 2009.

4. Altenbernd P., Hansson H. The Slack Method: A New Method for Static Allocation of Hard Real-Time Tasks // Real-Time Systems, 15, 1998, p. 103-130.

5. Колесов, Н.В. Планирование вычислительного процесса в распределенных системах реального времени с неопределенными длительностями решения задач систем / Н.В. Колесов, М.В. Толмачева, П.В. Юхта // ТиСУ - 2012. - № 4. - С. 5-12.

6. Зорин Д.А., Костенко В.А. Алгоритм синтеза архитектуры вычислительной системы реального времени с учетом требований к надежности // ТиСУ - 2012. - № 2. - С. 45-54.

7. Скородумов Ю.М., Грузликов А.М Использование динамических моделей при мониторинге распределений вычислений // Материалы XVI конференции молодых ученых «Навигация и управление движением», 2014, СПб: ГНЦ РФ ЦНИИ “Электроприбор”.

Размещено на Allbest.ru