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

ИСАДШШ НАУК СССР

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

На правах рукописи Нафгжов Ильдар Загитович

да 618.3

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

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

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

Новосибирск - 199Г

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

д.ф.-мли, директор УФ В1МШ статинформ Р.МД^уриев

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

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

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

Занята диссертации состоится " 17 " мая 1991 г, в _М_ час. 30 мин. на заседании Специализированного совета ¡(003.93.01 по защите диссертаций на соискание ученой степени кандидата наук при И01 СО АН СССР.

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

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

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

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

Автореферат разослан "_"__199 ' г.

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

СлЬги^^

В.К.Сабельфельд,£

:: ,;,..,» ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

I

^ертдции!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

СОДЕРЖАНИЕ ДИССЕРТАЩОНКОЯ РАБОТЫ

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

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

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

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

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

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

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

б

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

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

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

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

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

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

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

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

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

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

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

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

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

и (I-1»...- I ») •

(Р,,...РШ)€Р 1 . го

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

С1 С1 С1

где к-ый элемент сшска

Алгоритм И! для модуля М0 заключается в просмотре в указанном порядке всех комбинаций элементов входных "списков с элементами фрагмента генерации капсул К=(1,,..- .г) с результатами просмотра г к передаче их модул» Мр

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

осуществляют "подкачку" фрагментов Г1.....1И_1 в модуль М0. По

сути дела, алгоритм "К, реализует конвейерный просмотр декартова• произведения 1,«...*1т.

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

в

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

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

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

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

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

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

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

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

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

правый модуль содержал й (т>й) элементов I ( т= ^ £ а°/п| у

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

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

1

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

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

Алгоритмом 114. Вначале элементы 1 в 'модулях сортируются одним из известных методов последовательной сортировки записей. Затем модули системы осуществляют чередующиеся четно-начетные взаимодействия. При этом в каждой царе взаимодействующих модулей фраументхГсписка 1 сортируются (например, слиянием), получившийся фрагмент % делится пополам так, что элементы 1 с меньшими ключами размещаются в модуле с меньшим номером.

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

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

Ю

полученного флага ФА (3<Ш-1) с минимальным номером элементов фрагмента сортируемого списка I, находящегося в модуле М . Если то флаг Фх передается дальше по

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заметал, что выбрать элемент о непустым'Е можно тогда и .только тогда, когда 1 - неупорядоченный. Будем полагать, что на каждом шаге I.алгоритма ЧЬ в позиции 3 находится маркер д тогда и только тогда, когда в модуле М на шаге г находится выбранный элемент е с непустым Е. На каздом шага г (01) алгоритма для маркера Д, не уничтоженного на ваге г-1, рассмотрим максимальный по числу элементов "интервал" на кольце модулей !,.=[^ , ^ Сто есть множество номеров модулей,' расположенных мевд 31-ым и 32-ым модулями при обходе кольца по часовой стрелке, включая номера ^и ' обладающий свойством РШ4): в модуле ¡2 есть хотя би 0ДШ! элемент есЕ. Здесь 3| - положение маркера Д перед шагом г. Для каждого 'С(т50) алгоритма имеем последовательность интервалов 10,1р...,1х , соответствующих выбранному элементу

eeZ и обладавших свойотеом P0U4). Последовательность этих интервалов мокно рассматривать как последовательность состояний некоторого динамического интервала 3=11,г) с изменявшимися границами 1 и г. Границе г сопоставим маркер v. По изменению положения этих маркеров в ходе работы алгоритма будем судить о "движении" границ интервала 3. Как оказалось, алгоритм '¡14, в конечном счете, сближает эти маркеры и на не- • котором шаге Men уничтожает их. Отсутствие маркеров на шаге N означает невозможность построения интервала 3, соответствующего выбранному элементу е«2 и обладающего указанным свойством Р(И4), то есть означает пустоту Е. Из произвольности выбора в следует справедливость доказываемого утверждения.

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

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

k+i

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

вместо 2 ). Здесь flog^] , n - число модулей в системе, 0«х<1.

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

d= шах im°>- mtn to°>,d = шах On.}- mUi Cm }. 0 Osycn-1 .J • i Oiiei-1 3 (ХЗ«п-1 3

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

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

t0<t«0+n и ckdp.

Тесрэыа 2.3. Пусть т° - число элементов списка I в

модуле с номером i ((Kioi-I), n= 2 n>°/nj • ТогДа не ОоЛ0е'

чем через 2(п+1) шагов алгоритма 1Г3 в кавдом модуле системы

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

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

• Показано, что для произвольного распределения оперативной памяти модуля под списки ^,...,1 число обращений к ВЗУ модулем при просмотре декартова произведения

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

Би п г1+Ь2г2+...+Ьтгт,

где 1^2...!^, если г^Я, и при (1к - число элементов списка ).

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

списки I,.....выделяется память размером не больше мак>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

С. 130.

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