Software & Systems

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

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

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

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

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

Вопросы организации и анализа эффективности многопроцессорных вычислительных систем, ориентированных на обработку таких потоков со связями общего вида, в технической и математической литературе проработаны недостаточно. Укажем некоторые технические решения, относящиеся к затрагиваемой проблеме, но имеющие определенные архитектурные ограничения. В работе [2] описана структура соответствующей системы, которая ориентирована на потоки, характеризующиеся наличием только линейных связей между компонентами потока. Система, представленная в [3], оказывается неэффективной при обработке потоков со сложной структурой внутренних взаимосвязей ввиду архитектурных и структурных ограничений по распараллеливанию входного потока.

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

Структура вычислительной системы

Предлагаемая структура вычислительной системы потоковой обработки данных представлена на рисунке 2. Система ориентирована на обработку потока взаимосвязанных данных и может логически адаптироваться к структуре и параметрам входного потока данных.

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

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

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

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

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

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

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

Эффективность вычислительной системы

Показателем эффективности вычислительных систем обычно выступает их производительность – количество эталонных задач (алгоритмов), выполняемых в единицу времени. Оценка вычислительных систем потоковой обработки по их производительности должна учитывать случайный характер процесса поступления задач и длительность их обработки [4].

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

Технический эффект от использования предлагаемого решения удобно рассматривать в сравнении с известной системой [3]. При этом полагается, что на вход системы поступает поток задач сложной структуры, фрагмент которого показан на рисунке 1.

Каждая из задач этого потока реализуется модулями обработки. При возможности разбиения задачи на параллельные подзадачи последние выполняются одновременно (параллельно) на нескольких процессорах модуля обработки. В случае разбиения задачи на последовательные подзадачи они выполняются друг за другом (в конвейере) на нескольких процессорах модуля обработки. Структура задач и возможность их разбиения на отдельные подзадачи определяют порядок формирования и обработки заявок на выполнение задачи.

Рассматриваемый поток задач сложной структуры имеет высокую степень связанности между исполняемыми задачами Si . Каждая связь характеризуется объемом vi данных, передаваемых от задачи к задаче в потоке.

Пусть в потоке каждая задача Si  характеризуется двумя параметрами обработки: средним временем tср выполнения задачи на одном модуле обработки и средним объемом vср промежуточных данных от одного модуля обработки, порождаемых задачей при ее выполнении.

Среднее общее время выполнения одной задачи в системе при этом теоретически составит tср+tср, где tср – среднее время передачи промежуточных данных одной задачи, зависящее от структуры системы.

В вычислительной системе потоковой обработки теоретическая предельная пропускная способность с учетом затрат на передачу промежуточных результатов обработки определяется выражением  (задач/с).

Реальная пропускная способность зависит от структуры системы.

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

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

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

На выходную магистраль выдается общий объем передаваемых данных 16vср. При этом среднее общее время, необходимое на выполнение задачи и передачу данных по выходной магистрали, составит , если передачи выполнять последовательно после некоторого процесса одновременной обработки задач в модулях.

Учитывая, что передачи обычно статистически совмещены с выполнением некоторых задач в модулях, это время будет гораздо меньше и его можно оценить по формуле , где k1»0,1, …, 0,4 – уменьшающий коэффициент за счет совмещения передач данных по магистрали с выполнением задач. При этом реальная пропускная способность известной системы составит  (задач/с).

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

В предлагаемой авторами системе число конфликтов передачи данных значительно меньше за счет использования нескольких выходных магистралей.

На каждую выходную магистраль выдается общий объем передаваемых данных 4vср. При этом с учетом коэффициента совмещения k1»0,1, …, 0,4 среднее общее время, необходимое на выполнение задачи и передачу данных, составит . Реальная пропускная способность предлагаемой системы составит

 (задач/с).

Особенность потоковых задач в том, что время tср, затрачиваемое на передачу данных объемом vср от одной задачи S, обычно составляет tср=k2tср, где k2»0,1, …, 0,3. Это объясняется тем, что с целью повышения пропускной способности системы задачи обработки реализуются достаточно короткими. С учетом этого выигрыш в пропускной способности от применения предлагаемой системы составит: .

Численное значение выигрыша от применения предлагаемой системы в зависимости от значения коэффициентов k1 и k2 представлено в таблице.

Пропускная способность системы на рассмотренном фрагменте потока задач в 1,12–1,97 раза выше, чем в известной системе [3] при одинаковых заданных коэффициентах k1 и k2. При этом организация исполнения задач в линейках обработки должна соответствовать структуре потока, то есть структура системы и процесс выполнения задач должны быть настроены на структуру входного потока задач.

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

Литература

1.   Каляев И.А. [и др.]. Реконфигурируемые мультиконвейерные вычислительные структуры; [под общ. ред. И.А. Каляева]. Р-н-Д: Изд-во ЮНЦ РАН, 2009. 344 с.

2.   Поздняков В.А. Особенности языка программирования, предназначенного для описания модулей в рамках универсальной системы обработки потоков данных // Наука и образование. 2008. № 12. URL: http://technomag.edu.ru/doc/ 111599.html (дата обращения: 12.03.2011).

3.   Курчидис В.А. Организация мультимикроконвейерной системы обработки потоков данных сложной структуры // Электронная техника. 1988. Вып. 3 (69). Сер. 10 (Микроэлектронные устройства).

4.   Липаев В.В. Распределение ресурсов в вычислительных системах. М.: Статистика, 1979.