Построение схемного решения по алгоритмическому представлению вычислительного процесса

В.А. Тихомиров, Т.И. Козырев, С.Г. Тимофеев

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

Успехи развития многопроцессорных вычислительных систем обеспечиваются в основном за счет роста технологических возможностей, в частности за счет уменьшения топологических размеров при изготовлении кремниевых микросхем, вследствие чего повышается плотность компоновки вентилей на одном кристалле и возрастает скорость работы процессоров. Помимо технологических путей повышения производительности вычислительных систем существуют алгоритмические, программные и архитектурные методы. Алгоритмические методы сводятся к построению более эффективных математических методов решения задач. Программные методы состоят в разработке программ, обеспечивающих эффективное использование вычислительных систем. Наконец, важнейшим направлением повышения производительности вычислительных систем являются архитектурные методы. Специалистами ведущих фирм мира за последние полвека были реализованы конвейерные, векторные, векторно-конвейерные, матричные, тороидальные, гиперкубовые, иерархические, кластерные и множество иных архитектур вычислительных систем. На данный момент лидирующие позиции в области высокопроизводительных систем занимают системы с кластерной архитектурой. Кластерная архитектура представляет собой объединение множества традиционных коммерчески доступных процессорных узлов с помощью стандартных сетевых решений. Однако данная архитектура имеет существенные недостатки, обусловленные относительно низкой скоростью процедур межпроцессорного обмена, недостаточной пропускной способностью сети передачи данных и необходимостью синхронизации множества взаимосвязанных последовательных процессов, каждый из которых выполняется на отдельном процессоре. Все это приводит к тому, что высокую реальную производительность кластерная архитектура демонстрирует, в основном, только при решении «слабосвязанных» задач, не требующих интенсивного обмена данными между процессорными узлами, в то время как при решении «сильносвязных» задач их реальная производительность не превышает 5-10% от прогнозируемой. При этом увеличение числа процессорных узлов в системе зачастую не только не повышает ее реальную производительность, а наоборот, ведет к её снижению, поскольку организация параллельного вычислительного процесса требует больше времени, чем его исполнение. Данное положение характерно для большинства из существующих архитектур многопроцессорных вычислительных систем, то есть, если на некоторых классах задач при конкретной архитектуре достигается производительность, близкая к пиковой, то при решении других классов задач производительность той же вычислительной системы может резко падать, уменьшаясь на порядок или даже на несколько порядков.

Данный факт обусловлен противоречием, вытекающим из неадекватности конкретной архитектуры многопроцессорной системы и внутренней структуры решаемой задачи. Снятие данного противоречия возможно на основе разработки систем с реконфигурируемой архитектурой, у которых в отличие от многопроцессорных вычислительных систем с «жесткой» архитектурой, архитектура имеет возможность изменяться от задачи к задаче. Таким образом, концепция реконфигурируемых архитектур обеспечивает возможность адаптации архитектуры вычислительной системы под структуру решаемой проблемы. Проведенные исследования показали [ 1 ], что реализация данной концепции обеспечивает высокую реальную производительность многопроцессорной вычислительной системы, близкую к пиковой, на широком классе задач (в том числе при решении «сильносвязанных» задач), а также практически линейный рост производительности при увеличении числа процессоров в системе. Специалисты, применяющие программируемые логические интегральные схемы (ПЛИС), считают, что применение данных кристаллов обеспечивает более чем на два порядка большую производительность систем в сравнении с производительностями систем, реализованными на стандартных микропроцессорах, и с аналогичной потребляемой мощностью, а также стоимостью [ 2 ]. Особенно актуально применение данного подхода при создании встраиваемых бортовых вычислительных систем. Также следует отметить, что концепция построения реконфигурируемых вычислительных структур открывает широкие перспективы использования ПЛИС в качестве элементной базы для создания больших вычислительных полей, в рамках которых могут создаваться проблемно-ориентированные вычислительные системы, адаптируемые под структуру решаемой задачи. Возможность создания систем под структуру задачи обеспечит максимум эффективности системы при решении конкретной вычислительной задачи. Однако это только одна сторона медали. Другую сторону формируют проблемы связанные с необходимостью привлечения высококвалифицированных специалистов, специфичностью и сложностью программирования в ходе разработки таких систем. Процедура реализации таких систем требует программирования не только каждого отдельного процессорного элемента, но и структуры связей между ними в соответствии с информационным графом решаемой задачи. Это требует больших временных затрат и связано с необходимостью применения нестандартных средств программирования, а также высокой квалификации программистов, разработчиков архитектурных решений. Именно это объясняет то, что реконфигурируемые вычислительные системы до сих пор они не нашли широкого применения. При этом использовать реконфигурируемые вычислительные системы для решения часто меняющихся задач с одиночным вектором входных данных оказывается малоэффективно, но положение дел резко меняется для класса задач, при решении которых преимущества реконфигурируемых мультиконвейерных вычислительных систем проявляются в полной мере. Это задачи обработки больших массивов (потоков) данных по одному алгоритму. Примерами таких задач могут служить задачи математической физики, цифровой обработки сигналов, криптографии и т.д. Не нарушая общности рассуждений рассмотрим потоковую задачу, сформулированную следующем образом: существует некоторое упорядоченное множество векторов данных Vin = V1,V2,…Vn; каждый элемент которого должен быть обработан по фиксированному алгоритму A; задача потоковой обработки заключается в преобразовании множества (потока) векторов входных данных Vin во множество (поток) векторов выходных данных Vout. В простейшем случае решение подобных задач связано с применением последовательной вычислительной системы, основным элементом которой является процессор P. Для этого процессор предварительно необходимо запрограммировать на последовательное выполнение всех операций алгоритма, и затем подать на вход последовательность векторов. Считая, что время обработки одного вектора на процессоре P равно PA, время, затраченное на последовательную обработку всего потока входных данных, равно n*PA. Самым очевидным путем сокращения времени обработки потока входных векторов является распараллеливание процесса обработки.

В простейшем случае параллельный способ подразумевает наличие нескольких процессоров (P1=P2=…=Pm=P), каждый из которых может работать независимо от других. В этом случае время решения, то есть время обработки всего множества векторов входных данных, будет равно (n/m)*PA, то есть сократится в m раз.

Сократить время решения можно и другим способом, который принято называть конвейерной обработкой. Предположим, что обработка каждого входного вектора проходит несколько стадий A=A1,A2…Am и в системе имеется несколько процессоров, соединенных последовательно, причем каждый из процессоров реализует соответствующую стадию общего алгоритма. Время обработки массива данных на конвейере процессоров будет зависеть от временем работы самой медленной ступени конвейера (обозначим её PAi), тогда время обработки всего потока данных будет n*PAi. Существенным преимуществом конвейерного способа обработки перед параллельным способом является сокращение числа входных и выходных информационных каналов. Рассмотренные способы оптимизации применимы для схемного представления вычислительной задачи. В рамках существующей парадигмы работы вычислительных систем на следующем шаге необходимо отображение схемного представления вычислительной задачи в алгоритмическое. Для решения данной проблемной задачи предлагается методика, позволяющая транслировать языки программирования высокого уровня в языки описания аппаратуры.

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

Gw = <O, W, In, Out>,

где: O – множество операций нижнего уровня (они представляются операторами языка программирования),
W – множество рёбер, соответствующих последовательности выполнения операций,
In – начальная операция,
Out – множество всех возможных завершающих операций.

Недостаток такого представления в том, что вычислительная система, построенная на основе такого графа, не может начать выполнение операции до тех пор, пока не закончится выполнение предыдущей, что соответствует последовательному выполнению алгоритма. Поэтом если определить на том же множестве O информационную зависимость операций, то получаем представление процесса, отражающее граф информационной зависимость операций Gd. Такое представление вычислительного процесса определяет последовательность выполнения операций, зависящую от данных, необходимых для выполнения операции и является исходным, для построения схемного описания вычислительной системы для реконфигурируемой вычислительной системы. Построенный граф информационной зависимости процесса вычисления обладает двумя свойствами:

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

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

Вариант построения графа временной зависимости по исходному коду на языке высокого уровня может быть реализован по следующей схеме. Проводится препроцессорная обработка, лексический, синтаксический и семантический анализы исходного текста, в результате чего строится дерево синтаксического разбора. Классический компилятор, описанный в [ 3 ], успешно выполняет эти стадии. Этот компилятор имеет модульную архитектуру, в которой каждая стадия выполняется отдельным модулем. Модули препроцессора, лексического анализатора и синтаксического анализатора зависимы от исходного языка программирования. При обработке добавляемого языка программирования эти модули должны быть написаны и заменить собой соответствующие модули. Модуль семантического анализа независим от исходного языка программирования и может использоваться для любого поддерживаемого языка программирования. Такая архитектура позволяет обрабатывать большой класс исходных языков программирования за счёт взаимозаменяемости модулей, зависимых от исходного языка программирования. Стадии, зависимые от исходного языка программирования, абстрагируют исходный код до описания алгоритма (дерево синтаксического разбора), которое является независимым от исходного языка программирования. Построение графа вычислительного процесса Gw по дереву синтаксического разбора реализуется рекурсивным обходом, в ходе которого сначала выделяются операции, а затем определяются связи, отражающие передачу управления между операциями.

Детализацию методики осуществим на примере реализации алгоритма решения квадратного уравнения. На первом шаге осуществляется описание алгоритма на псеводязыке:

Программа РешениеКвадратногоУравнения;
Начало

{ вводится значение параметра a }
ПолучитьПараметр (a);
{ вводится значение параметра b }
ПолучитьПараметр (b);
{ вводится значение параметра c }
ПолучитьПараметр (c);
{ вычисляется дискриминант }
Дискриминант = bb-4ac;
{ вычисляется квадратный корень из дискриминанта }
Переменная1 = КвадратныйКорень (Дискриминант);
{ вычисляется первый корень }
Ответ1 = (-b - Переменная1)/(2a);
{ Вывод первого корня }
Вывести (Ответ1);
{ вычисляется второй корень }
Ответ2 = (-b + Переменная1)/(2*a);
{ Вывод второго корня }
Вывести (Ответ2);

Конец.

На втором шаге строится граф Gw (рисунок 1), реализующий приведенный псевдокод.

Далее построенный граф процесса вычисления отражает последовательность выполнения действий алгоритма. У каждой операции есть входные и выходные данные, соответствующие передаче управления блоку и завершению его работы. Затем осуществляется переход от графа временной зависимости Gw к графу информационной зависимости Gd . При этом смещает акцент с потока управления на поток данных, что позволяет начать выполнение действия в любой момент после того, как появятся все необходимые для его выполнения данные. Переход реализуется следующим алгоритмом: 1. определяются входные данные; 2. на первый слой графа помещаются операции, зависящие только от входных данных; 3. на каждый следующий слой помещаются операции, информационно зависящие от исходных данных и результов выполнения операций на предыдущих слоях.

Пример графа Gd, построенного по графу Gw, представлен на рисунке 2.

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

1. Каляев А.В., Левин И.И. Модульно-наращиваемые многопроцессорные системы со структурно-процедурной организацией вычислений. - М.: Янус-К, 2003, 380.
2. Левин И.И. Методы и программно-аппаратные средства параллельных структурно-процедурных вычислений. Дисс. на соискание ученой степени докт. техн. Наук. - Таганрог, 2004, 363.
3. Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman. ISBN0-201-10088-6. Compilers Principles, Techniques, and Tools.