Введение к работе
Актуальность проблемы'. Снижение цеп па микропроцессоры и с широкое применение открывает есв новые и новые сферы пользования вычислительных машин. Есть основания ожидать, "о наиболее широкое применение и одновремешо сильнейшее гияние микро-ЭВМ будет наблюдаться при решении задач автома-[зации учреждений. На необходимость автоматизации конторской іботн и внедрение учрежденческих информационных систем ука-вает множество факторов как, технического, так и тонического характера.
В учреждениях приходится иметь дело с возрастающим ъемом данных са>шх различных видов. Поэтому для того, чтобы рэвденческие системы могли обеспечить выполнение обходимой работы, все виды данных должны храниться и рабатываться совместно. Представляется естественным отдель-з микро-ЭВМ объединить в систему, а обработку всех данных зличных видов производить во многих узлах этой системы.
Эффективность обработки деловой информации во многом висит от выбора архитектуры системы, на которой будет проводиться эта обработка.
Наиболее распространенной в практике .формой представле-я деловой информации являются таблицы - множества данных (іяционного типа. Табличный способ описания данных дает шожность,' в частности, распре деленно хранить данные, ісоединять (или исключать) новые элементы данных, записей, ізей без изменения существующих подсхем, а также )аллельно обрабатывать падтаблйцы. Методологический анализ >блем параллельной обработки деловой информации показал, ) наилучшим образом эти возможности реализуются на одно-даой кольцевой системе с локальными связями- Узлами такой дамы являются вычислительные модули, каздый из которых ідинен о двумя соседіпіми по пріпщипу "точка-точка". Кроме о-, для обеспечения живучести в системо предусмотрены до-шитэлыше "хордовые" линии связей - порез один модуль.
Эти системы обладают рядом особенностей:
простотой архитектуры и, вследствие этого, небольшой стоимостью: для соединения п модулей требуется 2п линий связи
отсутствием "узких" мест таких, как разделяемая общая память или общая шина связи, которые требуют организации взаимодействия конкурирующих процессов;
сравнительно небольшими потерями технических ресурсов при исключении из системы неисправного модуля с сохранением исходной топологии (кольца);
возможностью организации асинхронных взаимодействий модулей.
В отличие от известной системы Cambridge ring е архитектуре рассматриваемой вычислительной системы каздй элемент кольца сам является кольцом трех процессоров, поддерживающих соответственно функции интеллектуального диска, интеллектуального терминала и вычислителя. При этом связь менаду модулями "большого" кольца осуществляется через интеллектуальный диск.
Данная диссертационная работа является составной частью теоретических исследований в области программных средств организации децентрализованного управления однородной кольцевой вычислительной системой с локальными взаимодействиями для эффективной обработки деловой информации, выполненными под руководством Р.М.Нуриева в рамках научно-исследовательского проекта создания операционной среды ГНОМ. Главной особенностью операционной среда ГНОДО . является припцш равномерного распределения данных по модулям и децентрализованного управления обработкой. Описание обработки дэлоео! информации (представляющей собой таблицы) осуществляется і виде системы вложенных циклов с жесткой подачей строк STKX таблиц, то есть таблицы обрабатываются как списки строк. Такие системы циклов называются регулярным узлом.
Целью работы является разработка и исследовав» алгоритма функционирования многопроцессорной системы кольцевой архитектуры для параллельной обработки нескольких спис ков, заданной в виде регулярного узла.
Научная новизна работы.
-
Разработан алгоритм децентрализованной параллельной обработки нескольких списков в системах вложенных циклов с жесткой выборкой данных. Установлено, что проблема управления процессом такой обработки сводится к решеїшю трех задач -перекрещивания, выравнивания и сортировки списков. В отличив от ранее известных решений этих трех задач в данной работе все процессы - перекрещивания, выравнивания, и сортировки -протекают совместно и направлены на достижение одной цели -эффективного исполнения регулярного узла.
-
Разработан метод доказательства корректности и оценки временной сложности решений перечисленных задач, являющийся общим для децентрализованного решения этих задач, основанного на четно-нечетных взаимодействиях.
Практическая ценность работы. Предложенные в диссертации алгоритм и процедуры нашли свое применение в разработке процессора данных и в.организации файловой системі операционной среда ГНОМ для обработки деловой информации в Уральском филиале ВШПИстатинформ, что подтвврвдается справкой; о внедрении, алгоритмы включены в ОАП МЭП. Предложенный метод доказательства может быть использован при доказательстве корректности децентрализованных алгоритмов, основанных на чвтно-нечетйкх взаимодействиях модулей кольцевой системы.
Апробация. Основные результаты обсуждались на"семинарах лаборатории теории программирования Отдела фязшси и математики БФ АН СССР, семинаре системного программирования Л7У, Всесоюзной школе-семинаре "Многопроцессорные системы и іараллельное программирование" (Уфа, 1984), Всесоюзной <овфбренции "Вычислительные сети-коммутации пакетов" (Рига, [981), Всесоюзной школе-семинаре "Параллельное программирование и высокопроизводительные системы" (Бердянск, 1986), всесоюзной конференции "Формальные модели параллельных вимелений (Новосибирск, 1987).
Структура и объем работы. Диссертация состоит из зведення, трех глав, заключения, списка литературы из 52 наи-іенований и приложения. Общий объем диссертации ІСб стр.
