РЕШАЕМЫЕ ЗАДАЧИ И ИХ КЛАССИФИКАЦИЯ

Дешифратор команд Устр-во управления

I

Арифметическое устройство

Дешифратор адресов

ПАМЯТЬ

МБ

МБ

(ПЭ) (ПЭ) 81 (ПЭ  (ПЭ) (ПЭ) мг (ПЭ

8ГМГ

МГМГ

81

82

(Г 8Г

ПЭ    ПЭ       ПЭ МГ

МГ8Г

Рис. 1.1. Последовательная и параллельные вычислительные системы.

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

Другая задача, которую обычно считают параллельной -это задача противоракетной обороны (ПРО), которая обычно сво­дится к опознаванию и слежению за целями, различению их между собой и их классификации. При этом машина должна инициировать отдельный файл для каждого обнаруженного объекта, связывать каждый отраженный сигнал, полученный локатором, с соответствующим файлом, обновлять содержимое файлов, производить над ним математические расчеты. Огра­ничения, накладываемые режимом реального времени, таковы, что в ответ на каждый отраженный сигнал (от нескольких сотен до нескольких тысяч таких сигналов в секунду) нужно сгенери­ровать и передать на локатор запрос на следующий сигнал, и сделать это нужно за заданный временной интервал (обычно от 25 до 200 мсек). Простой расчет показывает, что такая задача никоим образом не может быть решена на традиционных пос­ледовательных ЭВМ, даже на самых больших и мощных. Ре­зультаты измерений, выполняемых локатором, сравниваются сданными о цели, хранящимися в файле. Сравнение т отражен­ных сигналов с п целями при обычном способе сравнения тре­бует порядка тп операций, и только т операций, если сравне­ние производится ассоциативно. Такая ассоциативная память, поиск данных или манипулирование данными в которой произ­водится не по адресам, а по содержанию, используется в систе­ме РЕРЕ, применяемой для решения данной задачи.

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

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

К автономным не р-задачам относятся среди прочих: обра­ботка сигналов, в частности, быстрое преобразование Фурье, сортировка, поиск, оптимизация и задачи линейной алгебры.

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

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