автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Децентрализованное функционирование кольцевой мультипроцессорной системы для параллельной обработки деловой информации

АКАДЕМИЯ НАУК СССР

ОРДЕНА ЛЕНИНА СИБИРСКОЕ ОТДЕЛЕНИЕ ■ Институт систем информатики

На правах рукописи

Нафиков Ильдар Загитович

УДК 618.3

■ ДЕЦЕНТРАЛИЗОВАННОЕ ФУНКЦИОНИРОВАНИЕ КОЛЬЦЕВОЙ МУЛЬТИПРОЦЕССОРНОЙ СИСТЕМЫ ДЛЯ ПАРАЛЛЕЛЬНОЙ ОБРАБОТКИ ДЕЛОВОЙ ИНФОРМАЦИИ

05.13.II. - математическое и программное обеспеченна вычислительных машин, комплексов, систем и сетей

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Новосибирск - 1991

V . . ,

/ 'V /

Работа выполнена в совместной лаборатории теории программирования Института математики, с ВЦ Уральского отделения АН СССР и Уральского филиала ВШПИстатинформ. •

Научный руководитель : Официальные оппоненты:

д.ф.-м.н., директор УФ ВНИПИ статинформ Р.М.Е^уриев

д.ф.-м.н., зав.отделом Щ СО АН СССР Н.Н.Миренков

к.ф.-м.н., ведущий научный сотрудник ИСИ СО АН СССР В.И.Константинов

Ведущая организация:

Институт кибернетики АН. УССР

Защита диссертации состоится " 17 " мая. 1991 г. в 14 час. 30 мин. на заседании Специализированного совета 1TOQ3.93.0I по залдате диссертаций на соискание ученой степени кандидата наук при ИСИ СО АН СССР.

Отзывы в двух экземплярах, заверенные печатью, просим посылать по адресу: Новосибирск, пр.-Ак.Лаврентьева, 6.

С диссертацией мокно ознакомиться в читальном зало ГГЩГБ (пр. Ait. Лаврентьева, 6).

Автореферат разослан

V

»/■/" -I" 1991 г.

Ученый секретарь Специализированного совета к.ф.-м.н.

В.К.Сабельфельд.. «

ОБЩАЯ ХАРАКТЕРИСТИКА. РАБОТЫ

Актуальность проблемы'. Снижение цеп па микропроцессоры и с широкое применение открывает есо новые и новые сферы ¡пользования вычислительных машин. Есть основания ожидать, •о наиболее широкое применение и одновремешо сильнейшее сияние микро-ЭВМ будет наблюдаться при решении задач автома-[зации учреждений. На необходимость автоматизации конторской |боты и внедрение учрежденческих информационных систем укапает множество факторов как, технического, так и тонического характера.

В учреждениях приходится иметь дело с возрастающим ъемом данных самых различных видов. Поэтому для того, чтобы ревденческие системы могли обеспечить выполнение обходимой работы, все виды данных должны храниться и рабатываться совместно. Представляется естественным отдель-з микро-ЭВМ объединить в систему, а обработку всех данных зличных видов производить во многих узлах этой системы.

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

Наиболее распространенной в практике .формой представле-я деловой информации являются таблицы - множества данных пяционного типа. Табличный способ описания данных дает шожность,' в частности, распре деленно хранить данные, юоединять (или исключать) новые элементы данных, записей, 1зей без изменения существующих подсхем, а также заллельно обрабатывать подтаблицы. Методологический анализ >блем параллельной обработки деловой информации показал, > наилучшим образогд эти возможности реализуются на одно-даой кольцевой системе с локальными связями- Узлами такой ¡темы являются вычислительные модули, каздый из которых |динен о двумя соседними по принципу "точка-точка". Кроме ■с, для обеспечения живучести в системе предусмотрены до-шитэлыше "хордовне" линии связей - порез один модуль.

Эти системы обладают рядом особенностей: i

- простотой архитектуры и, вследствие этого, небольшой стоимостью: для соединения п модулей требуется 2п линий связи

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

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

- возможностью организации асинхронных взаимодействий модулей.

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

Данная диссертационная работа является составной частью теоретических исследований в области программных средств организации децентрализованного управления однородной кольцевой вычислительной системой с локальными взаимодействиями для эффективной обработки деловой информации, выполненными под руководством Р.М.Нуриева в рамках научно-исследовательского проекта создания операционной среда ГНОМ. Главной особенностью операционной среда ГЩЛ . является принцга равномерного распределения данных по модулям и децентрализованного управления обработкой. Описание обработки деловой информации (представляющей собой таблицы) осуществляется i виде системы вложенных циклов с жесткой подачей строк этих таблиц, то есть таблицы обрабатываются как списки строк. Такие системы циклов называются регулярным узлом.

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

Научная новизна работы.

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

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

Практическая ценность работы. Предложенные в диссертации алгоритмы и процедуры нашли свое применение в разработке процессора данных и в.организации файловой системы операционной среды ГНОМ для обработки деловой информации в Уральском филиала ВШПИстаташформ, что подтверждается справкой о внедрении, алгоритмы включены в ОЛП МЗП. Предложенный метод доказательства может быть использован при доказательстве корректности децентрализованных алгоритмов, основанных на четно-нечетных взаимодействиях модулей кольцевой системы.

Апробация. Основные результаты обсуждались на"семинарах лаборатории теории программирования Отдела физики и математики БФ АН СССР, семинаре системного программирования ¿ГУ, Всесоюзной школе-семинаре "Многопроцессорные системы и тараллельное программирование" (Уфа, 1984), Всесоюзной <онференции "Вычислительные сети-коммутации пакетов" (Рига, [981), Всесоюзной школе-семинаре "Параллельное программирование и высокопроизводительные системы" (Бердянск, 1986), всесоюзной конференции "Формальные модели параллельных выделений (Новосибирск, 1987).

Структура и объем работа. Диссертация состоит из ¡ведения, трех глав, заключения, списка литературы из 52 наи-юнований и приложения. Общий объем диссертации i'С.-5 стр.

СОДЕРЖАНИЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

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

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

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

Обеспечение исполнения вышеупомянутой схемы определяет ря 'задач функционирования кольцевой системы:

- равномерное распределение входных и выходных списков, поскольку неравномерность может привести к постепенно нарастаю щему различию объемов вычислений различных модулей системы;

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

- сортировка списков;

- обеспечение надежности системы

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

Предполагается, что модуль представляет собой отдельную микро-ЭВМ, хотя он может состоять из нескольких процессоров, мэкду которыми также тлеется' локальная кольцева'я связь.

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

- связи локальные, то есть каждый модуль связан с определенным количеством соседей; в каждый момент времени он мокет взаимодействовать с одним из них;

- направление - обмена информацией выбирается программным путем самим модулем;

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

- скорость обмена имеет тот ¡яе порядок, что и скорость переписи соответствующей порции из оперативной памяти в оперативнуп -'память.

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

Р^Ч

При этом предполагается, что войдя в состояние обмена р (или я), модуль ожидает перехода соседнего модуля в соответствующее состояние q (или р).

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

Алгоритм ^ просмотра декартова произведения входных списков основывается на следующем. Произведение «I может быть представлено в виде

и (I'....« I 2) •

(Р,....РШ)€Р . »

где Р - множество всех векторов длины т, составленных из элементов множества Ш.....п-1), - фрагмент списка хранящийся в р^-ом модуле. При этом лексикографический порядок следования элементов,указанного объединения может быть описан следующей цепочкой:

(1 {1 {1

.....—

где к-ый элемент списка (1<к

Алгоритм Ч1| для модуля М0 заключается в просмотре в указанном порядке всех комбинаций элементов входных списков с элементами фрагмента 1°, генерации капсул К= (11,. • .2) с результатами просмотра г и передаче их модули М|.

Любой другой модуль, получив капсулу, обрабатывает комбинации элементов 11,..-,1т_1 с влементами фрагмента 1т, находящегося в данном модуле, и передает капсулу К (возможно, с измененным г) соседнему справа модулю. Кроме того, все модули осуществляют "подкачку" фрагментов I.,,...,1И_1 в модуль По сути дела, алгоритм реализует конвейерный просмотр декартова: произведения 11«...«1ш. .

Поскольку при наличии параллелизма уровня 1 (уровня

вложенности независимых циклов регулярного узла) порядок обработки элементов множества }«З*^«.. .«I несущественен Л<1), алгоритм ^ обеспечивает лишь соблюдение порядка просмотра множеств I.,« .. .,«11_1 *{11>»11+1«.. .«1т. Алгоритм описывается конечным автоматом с 4 входами и 19 состояниями. Нетрудно показать, что просмотр декартова произведения входных списков на системе из п (п>1) модулей по алгоритму ^ при наличии параллелизма уровня 1 осуществляется в п раз быстрее, чем в одном модуле.

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

Алгоритм 1Г2 заключается в следующем. В кольце осуществляются чередующиеся четно-нечетные взаимодействия модулой. При этом в кавдой паре взаимодействующих модулей производится перераспределение . элементов списка I таким образом, чтобы ' '•• в результате этого шага алгоритма число эдементов списка I в каздом из этих модулей различалось не более, чем на I. Если общее число элементов в этих модулях нечетно, то больнее на I число элементов размотается в правом модуле. Перед каждом шагом алгоритма все модули система обмениваются "по кругу" флажками:

< номер модуля; число элементов I в данном модуле >

Алгоритм ^ завершает работу, когда для любых двух модулей системы число элементов фрагментов списка I , находящихся в этих модулях, отличается не более, чем на I.

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

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

Алгоритм состоит из двух этапов.

Этап I. Модули системы осуществляют чередующиеся четно-нечетные взаимодействия. При этом в каадой паре взаимодействующих модулей производится перераспределение элементов списка I следующим образом: если перед этим шагом алгоритма

правый модуль содержал т (т>т) элементов Г ( ш=

[ 2 7

то на данном шаге ( ш-ш ) элементов I передаются в левый модуль. Наряду с "основной" информацией модули передают флажки с номером модуля-генератора флага; получение модулем "своего" флага является критерием окончания первого этапа алгоритма

Зтеп 2 выполняется в случае, когда ш < £ т°/п.

1 1

Этог этап аналогичен первому с той лишь разницей, что в правом модуле остается т+1 элементов I,

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

Алторитиоа Ч14. Вначале элементы I в 'модулях сортируются одним из известных методов последовательной сортировки записей. Затем модули системы осуществляют чередующиеся четно-нечетные взаимодействия. При этом в каадой паре взаимодействующих модулей фра^ментЕГ списка Z сортируются (например, слиянием), получившийся фрагмент Ъ делится пополам так, что элементы Ъ с меньшими ключами размещаются в модуле с меньшим номером.

Для определения момента окончания алгоритма сортировки после каждого шага алгоритма модули обмениваются "по кругу" флажками: < номер модуля-генератора флага; максимальный номер' элемента фрагмента сортируемого списка 2, находящегося в данном модуле >.

При этом каждый модуль М (0€3<п-1) сравнивает номер К1 из

полученного флага Фх с минимальным номером

элементов фрагмента сортируемого списка I, находящегося в модуле М^. Если то флаг Ф± передается дальше по

кольцу модулей. В противном случае модуль М уничтокзет флаг Ф± и вместо него передает флаг Ф продолжения алгоритма II 4 сортировки; модуль, получивший Ф, переходит к следующему шагу алгоритма И4. Получение модулем М^ "своего" флага Ф^ говорит о том, ■ что для любого элемента сортируемого списка Ъ нет элемента с меньшим номером, находящегося правее выбранного.

Надежность работа системы обеспечивается:

1) процедурой обмена флагами для выявления неисправного модуля системы: получение "своего" флага означает работоспособность всех модулей системы;

2) дублированием необходимой информации в соседнем (например.справа) модуле: при выходе из строя соседнего (слеЕа) модуля данный модуль инициирует выравнивание (например, алгоритмом резервной информации;'

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

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

Алгоритм И5 состоит из двух этапов.

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

Этап 2 (собственно выравнивание). Выполняется алгоритм Причем I этап алгоритма 113 выполняется против часовой

стрелки, а 2 этап - по часовой стрелке.

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

Пусть п - число модулей в системе и п - четное.

Теореыа 2.1. После п иагов 2 этапа алгоритма ЧГ4 заданный равномерно распределенный по модулям список Ъ будет 'отсортирован, причем элементы списка с меньшими ключам! будут находиться в модуле с меньшим номером и с наибольшими - в модуле с максимальным номером.

Идея доказательства состоит в следующем.

Выбирается произвольный элемент еег. Пусть пзред первым пагом алгоритма он находился в модуле с номером 0С<п-1. Рассматривается^множество Е элементов, меньших е, но находящихся справа от е в модулях с номерами 3+1,,'..,п-1.

Заметил, что выбрать элемент ее2 с непустым Е можно тогда и .только тогда, когда 2 - неупорядоченный. Будем полагать, что на кавдом шаге алгоритма в позиции 3 находится маркер А тогда и только тогда, 'когда в модуле М^ на шаге X находится выбранный элемент е с непуртым Е. На каждом шаге г (Ш) алгоритма «И4 для маркера Л, не уничтоженного на шаге г-1, рассмотрим максимальный по числу элементов "интервал" на кольце модулей I =£ ] (то есть множество номеров модулей,' расположенных между 3|-ым и 32-ым модулями при обходе кольца по часовой стрелке, включая номера ^и обладашцЛ свойством Р(3?4): в модуле Л2 есть хотя 0и элемент ёсЕ. Здесь ^ - положение маркера Д перед шагом г. Для каждого алгоритма имеем последовательность

интервалов 10,1{,-■• Дт , соответствующих выбранному элементу

eZ и обладавших свойством Р(<и4). Последовательность этих нтервалов можно рассматривать как последовательность состо-лий некоторого динамического интервала 3=11, г] с вменяющимися границами 1 и г. Грашще г сопоставим маркер v. о изменению положения этих маркеров в ходе работы алгоритма удем судить о "движении" границ интервала 3. Как: оказалось, лгоритм М4, в конечном счете, сближает эти маркеры и на не- ■ оторсм шаге N€n уничтожает их. Отсутствие маркэроз на шаге N значает невозможность построения интервала 3, соответствую-эго выбранному элементу eeZ и обладающего указанным свойст-зм Р(1Г4), то есть означает пустоту Е. Из произвольности вы-эра е следует справедливость доказываемого утверждения.

Следствие. Для выбранной архитектуры системы алгоритм этно-нечетной сортировки "на хуаэ" алгоритма параллельной эртировки Бзтчера, поскольку, несмотря на меньшее, чем в пгоритме Ч14число слияний сортируемых отрезков (k(k+l )/2 ¿-а

пияний вместо 2 ), алгоритм Бэтчера "проигрывает" в числе

к+1

фесылок сортируемых отрезков (больше (к-2)2 пересылок it.+1-a

лесто 2 ). Здесь k-flogen] , п - число модулей в системе, $а<1.

Пусть и т^ - число элементов I в J-см модуле (CKJ^n-I) ответственно на шагах tQ и t алгоритма lig. Обозначим

= шах Cm?}- rain {m°},d = max Си.)- min Cm,}. 5 0<J«i-1 . i 0«J«i-1 3 0CJ€n~1 3 O^Jöi-1 3

'сть äQ>I. Тогда верна следующая

Теорема 2.2. Существует шаг t алгоритма Ч12 такой, что

t0<t«t0+n и ¿kd^.

Теорема 2,3. Пусть - число элементов списка I в

¡дуле с номером i (O^isi-I), m= 2 m°/nj . Тогда не более,

im через 2(n+I) шагов алгоритма в какдом модуле системы

будет находиться либо к, либо ш+1 элементов списка I.

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

Показано, что для произвольного распределения операт5гвной памяти модуля под списки число

обращений к ВЗУ модулем при просмотре декартова произведения

11»...«1т по алгоритму ч^ равно

Зш = г1+Ь2г2+---+Ьтгш-

где » ес™ ^>1» и ^=1 при ^¡=1 (1к - число

элементов списка ).

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

списки 11.....1т_1 выделяется память размером не больше мак*-

симальной длины одного элемента списка; вся остальная память выделяется под список 1т. Такое распределение памяти названо начальный.

Далее предлагается эффективная процедура построения оптимального распределения из начального распределения памяти для случая, когда и длины (размеры) элементов, и число элементов списков - величины постоянные. Идея процедуры: не меняя величины гт, перераспределением памяти под списки последовательно уменьшить, насколько'возможно , величины гП1_1, гга_2,..., г1. .

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

ная длина фиксированного числа элементов списка. Эффективность этой процедуры подтверждается результатами моделирования.

И, наконец, в случае, когда и число элементов списка не постоянно, предлагается применять эвристическую процедуру "динамического" распределения памяти, по которой максимальный объем памяти выделяется под список с наибольшим числом считываний с ВЗУ.

Замечание. Поскольку в системе из п, п>1, модулей все списки распределены равномерно по модулям, и алгоритм просмотра декартова произведения списков отличается от одно-модульного варианта лишь "подкачкой" очередных фрагментов списков из соседних модулей, рассмотренные процедуры эффективны и для распределения оперативной пгмяти п модулей.

' ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

2. Разработан и обоснован алгоритм децентрализованного функционирования таких систем при параллельной обработке деловой информации. При этом

установлено," что для этого необходимо решить следующие задачи: перекрещивания (рандеву), выравнивания и сортировки списков;

алгоритмы децентрализованного решения этих задач основаны на четно-нечетных взаимодействиях модулей;

установлены критерии окончания работы этих алгоритмов при наличии в системе только локальной-информации и способы оповещения всех модулей об окончании определенной работы; .

предложены способы обеспечения надежности функционирования системы, основанные на дублировании необходимой

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

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

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

5. Алгоритм функционирования системы реализован в работающей операционной среде ГНОМ при организации процессора . данных и файловой системы и внедрен в ВНИПИстаи-шформ.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ '

1. И.З.Нафихов. Следящий алгоритм параллельной реализации в локально описашюй вычислительной системе/ЛГекоторые вопросы вычислительной математики и теоретических основ вычислительной техники. Уфа: БФ АН СССР, 1981. С.97-106.

2. И.З.Нафиков. Децентрализованная сортировка записей// БФ АН СССР. Уфа, 1984. Юс. Деп. В ВИНИТИ 31.10.84, №7007-84.

3. И.З.Нефиков, Р.М.Нуриев. Три задачи децентрализованного функционирования микропроцессорных систем кольцевой архитектуры//Программироваше. 1986. N1. С.76-86.

4. М.З.Нафгаков. Об оптимальном распределении оперативной там.чти модуля многопроцессорной вычислительной системы (Тезисы доклада )//ПршвН0ии0 ЭВМ в решении научно-технических. 1 народно-хозяйственных задач. У^а, 1988. С.36.

5. Р.М.Нуриев, И.З.Ивфяков. Организация. параллельных зычислений системы циклов на микропроцессорной системе с ло-сальными связями (Тезисы доклада)//Кийернетика. 1987. N1. 5.130.

. 6. Р.М.Цуривв, И.З.Нафикоз, И.Й.Гареев. Регулярные вы-шслэкия на системе кольцевой архитектурн//БВД Уро АН СССР, ■фа, 1988. 19с. Деп. В ВИНИТИ 28.06.88, Н5228-В88.