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

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

,гс.

Ромм Яков Евсеевич

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

С/ Специальности:

05.13.17 - Теоретические основы информатики 05.13.13 - Вычислительные машины, комплексы, системы н сети

АВТОРЕФЕРАТ

диссертации на соискание ученой степени доктора технических паук

Таганрог - 1998

'I и - г

Работа выполнена в Таганрогском государственном педагогическом институте

Научные консультанты:

Доктор технических наук, профессор, действительный член РАЕН, Заслуженный деятель науки и техники РФ Л.С. БЕРШТЕЙН

Доктор физико-математических наук, профессор, член-корреспондент РАЕ,

Заслуженный деятель науки РФ В.Т. ФОМЕНКО

Официальные оппоненты: Доктор технических наук, профессор

Доктор технических наук, профессор П.П. КРАВЧЕНКО

Доктор технических наук, профессор Н.Н. ЛЯБАХ

Ведущая организация: Вычислительный центр РГУ, г. Ростов-на-Дону.

Защита состоится 1999 г. в часов на заседа-

нии специализированного совета Д 4)63/3.01 в Таганрогском государственном радиотехническом университете по адресу : 347915, г. Таганрог, пер. Некрасовский, 44, ауд. Д-406.

С диссертацией можно < ; университета.

А.Н. ГУДА

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

А.Г. Чефранов

Актуальность проблемы. В настоящее время интенсивность разработок и сследований в области архитектуры, программного обеспечения параллельных С (суперкомпьютеров) и методов параллельной обработки такова, что лишь еречисление действующих разновидностей суперкомпьютеров заняло бы не-юлько страниц. Область применения параллельных ВС охватывает обработку эрокосмических данных, радиолокационных и гидроакустических сигналов, а шже системы управления атомной энергетикой, автоматикой космических гстем, управления оружием; она включает использование в АСУ и в информа-ионных системах, в системах виртуальной реальности и распознавания обра->в и т.д. Эта область непрерывно расширяется, включая отрасли от геологии, гфтедобычи, метеорологии и сейсмической обработки до организации лесного ззяйства и финансовых расчетов доя школ и промышленных, учреждений, бъем продаж суперкомпьютеров на мировом рынке к 2000-му году составит 50 млрд. долл. Вместе с тем тематика параллельных вычислений сохраняет ряд ^решенных проблем. Актуальной остается проблема зависимости эффективно-Т1 пользовательских программ от архитектуры параллельных ВС. Параллель-зе программирование остается сложным; для достижения эффективности со-■авляемой программы, помимо программирования десятков (сотен и тысяч) фаллельных компонент, требуется согласовать выполнение соответственных эограммных компонент между собой, притом с учетом особенностей архитек-ры единой системы. В существенной мере сложность и эффективность парал-шыюго программирования определяется способами организации обмена, руктурой и уровнем их аппаратной поддержки. В общей постановке глубина зоблемы заключается в алгоритмическом несоответствии индетерминизма гераций обмена и детерминированности управляющей параллельной про->аммы. Приемлемое разрешение трудности имеет место лишь в случае узкой юблемной ориентации параллельной ВС. В общем случае данное несоответ-■вие влечет замедление текущего шага параллельной обработки и снижение её зфективности в целом, поэтому задача эффективной организации обмена со-»аняет значительную актуальность. Для её решения требуется организовать »гическое разделение операций и адресов обмена, а также физическое разде-■ние линий связи, по которым передаются сигналы обмена при выполнении ловия минимизации времени обмена и параллельной обработки в целом. На ювне микроопераций такая постановка вопроса также сохраняет смысл, ей со-встствует, в частности, задача исключения более одного переноса в любой из зрядов в любой момент времени выполнения произвольных арифметико-ягических операций. При этом, как и выше, сохраняется требование минями-ции времени обработки в целом. Для решения этой задачи требуется логиче-ое и физическое разделение битовых операций, включая операции переноса, а кже физическое разделение линий связи в процессе арифметико-логической работки, причем должен иметь место максимальный параллелизм обработки зрядных срезов всех доступных операндов. В рамках данного подхода естест-нно опираться на принципы вертикальной обработки, поэтому актуальна за-

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

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

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

Цель достигается на оснозе постановки и решения следующих задач.

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

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

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

Поставленную задачу можно кратко сформулировать следующим образом.

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

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

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

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

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

5. Дополнительно расширить банк устойчивых параллельных алгоритмов, реализуемых в рамках рассматриваемой архитектуры, включив в неё алгоритмы из области приближенных численных методов линейной алгебры, анализа и решения обыкновенных дифференциальных уравнений. В частности, разработать устойчивый приближенный метод параллельного вычисления элементарных функций и их суперпозиций за время <3(1) при произвольно заданной границе погрешности приближения;

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

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

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

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

Научная новизна Предложена архитектура реконфигурируемой парал-льной ВС с детерминированной параллельной программой обработки и бес-нфлнктного обмена, которая обеспечиваег асимптотический минимум време-выполнения произвольного алгоритма из области решения задач вьгчисли-иьной математики. Область проблемной ориентации включает основной на-шный класс задач, а также, дополнительно, методы информационно-гической обработки и распознавания образов. Предложенная архитектура со-ветствует концепции виртуальной машины фон Кеймана, отличаясь от анало-з конкретными алгоритмическими механизмами и схемными решениями в /чае выполнения отдельно взятого алгоритма рассматриваемого класса. Наи-лее принципиальное отличие заключается в детерминированности управ-ющей параллельной программы, наиболее характерное - в пошаговой (или лично пошаговой) организации бесконфликтного обмена с использованием гциачьной коммутационной сети из О (1о£? л')элементов с временем передала сигналов О(\о£2 'V), включая время настройки. В зависимости от варианта ганизации вычислений, может использоваться сеть из 0{К'2)элементов, - с л же временем передачи сигналов в условиях однозначности адресов переда; сеть, помимо того, способна выполнять внутреннюю сортировку N ключей с А же временной оценкой. По сравнению с существующими архитектурами эаллельных ВС два первых предложенных варианта содержат два существен-х упрощения. Одно из них - аппаратное - заключается в упрощении цен-шьного устройства управления, роль которого сводится к выдаче синхронизующих импульсов параллельным компонентам ВС. Второе - программное -зощает пользовательское программирование: во входной программе пользо-•ешо достаточно идентифицировать только математический параллелизм, -! учета архитектуры ВС.

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

пы. В частном случае бинарного сложения, и-разрядных двоичных чисел на основе метода синтезируется параллельный сумматор с временем сложения 0{\ для произвольно фиксированного п. Все переносы синхронно распространяют« по взаимно независимым линиям связи; в случае знакоразрядных числовых кодов сумматор состоит из 0(п) элементов; в случае бинарного сложения двоичных чисел с положительными коэффициентами количество элементов имеет сценку 0(п1+£), где е - произвольно мало, но фиксировано. Существующи« методы параллельного суммирования ускоряются в Oflog2AT) раз. Суммато обнаруживает способность эффективно суммировать одноразрядные двоичны« числа, п из которых он складывает за время 0(iog2 п). При этом число его эле ментов в О (п) меньше числа элементов аналогичных устройств. На базе топ же способа время параллельного умножения ускоряется пропорционально ускорению завершающего суммирования. Метод вкладывается в предложеннук архитектуру параллельной ВС, формируемое на его основе арифметическое устройство способно реконфигурироваться в эффективную сортирующую сеть.

Разработано видоизменение сортировки слиянием, использующее матриць параллельных сравнений. С использованием матриц сравнения получен клас< адресных параллельных сортировок, которые совместимы с предложенной архитектурой параллельной ВС. Параллельная программа выполнения каждой и: них в такой ВС может быть детерминированной, обмен в процессе выполнена - бесконфликтным. По сравнению с. существующими полученные алгоритмь параллельных сортировок отличаются максимально параллельной конструкцией схемы слияния, а также улучшенными оценками временной сложности npi равном количестве процессоров, В частности, одномерный массив из N элементов на N процессорах упорядочивается за время Г = log2 N • О (log2 log2 N), н

N2 /4 процессорах - за время Т - 0(1) . Тем самым сортировка Батчера при равном числе процессоров ускоряется в 0(log2 N) раз; с увеличением чисд:

процессоров в G(N) та же сортировка ускоряется в 0(Iog2 Л'). Слияние дву: упорядоченных массивов из N элементов на N процессорах выполняется за время 0(log2log2AT), на Nz процессорах - за время 0(1). Адресность предложенных соргировок позволяет локализовать путем распознавания характерные особенности образа, представленного на входе массивом элементов (в частности, -массивом координат), и затем их идентифицировать. На основе такого распознавания экстремальных особенностей функции, заданной массивом координат на равномерной сетке, удается организовать устойчивый процесс локализации её нулей и экстремумов, а затем выполнить их вычисление с повышенной точностью. Этот метод сохраняет работоспособность в случае плохой отделённости нулей и экстремумов; процесс распознавания, локализации и вычисления допускает максимально параллельную форму. Организация данного процесса на основе сортировки отличает предложенный метод от известных численных cxe.v в данной области.

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

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

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

- предложен перенос этого же преобразования на разностные схемы прижженного решения систем линейных дифференциальных уравнений с посто-¡ной матрицей коэффициентов и построение на данной основе машинного меда анализа устойчивости в смысле Ляпунова решения таких уравнений; метод > построению отличается от известных теоретических приемов анализа устой-[вости по Ляпунову; в частности, метод не использует вычисление или оценки рактеристических чисел матрицы, ко по виду входной матрицы с элементар-•ш ее преобразованием организует вывод норм преобразованной матрицы в следовательности пошаговой схемы приближенного решения, - поведение еледовательности норм адекватно соответствует асимптотическому поведе-ю разности между возмущенным и невозмущенным решениями;

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

Практическая цешгосп». Даны последовательные программные варианты едложенных параллельных алгоритмов, в такой форме они использованы в де законченных хоздоговорных и бюджетных работ, выполнявшихся в НИИ ЗС, НКБ "Миус", ЙК АН УССР им.В.М.Глушкова, а также в некоторых дру-< предприятиях и организациях. Эти же результаты и, помимо того, предло-

женные архитектуры параллельных ВС, сортирующие и коммутационные сети, а также методы и схемы устройств вертикальной обработки потока групповых данных использовались в договорных работах организаций из числа названных, и в учебном процессе ВУЗов. В учебном процессе ТГПИ используются предложенные прямые и итерационные методы линейной алгебры, а также алгоритмы адресных сортировок.

Апробация работы. Работа апробирована на рабочих и постоянно действующих семинарах ТРТУ, ТГПИ, РГУ, НКБ "Миус", НИИ МВС, Института кибернетики им. В.М.Глушкова HAH Украины, ВЦ и ИМ СО АН СССР, на региональных семинарах и межвузовских конференциях ТРТУ и НКБ "Миус", на всесоюзном семинаре "Параллельные машины и параллельная математика" в г. Киеве в 1978 г., на всесоюзной школе-семинаре "Автоматизация проектирования средств вычислительной техники и перспективы применения микропроцессоров" в г.Минске в 1978 г., на всесоюзных школах-семинарах "Распараллеливание обработки информации" в г.Верховине в 1983 г., в г.Косове в 1985 г., на "Шестом республиканском семинаре по однородным вычислительным средам и систолическим структурам" в г.Львове в 1987 г., на Втором всесоюзном совещании "Конвейерные вычислительные системы" в г.Киеве в 1988 г., на международной конференции молодых ученых "Проблемы проектирования и применения дискретных систем в управлении" в г.Минске в 1977 г., на международной конференции "Математические модели физических процессов и их свойства" в г.Таганроге в 1997 г., на международной конференции "Математика в индустрии" в г.Таганроге в 1998 г.

Публикации По теме диссертации опубликовано около 90 научных работ, общим объемом « 95 п.л., основные из них вышли в журналах "Известия СКНЦВШ", "Многопроцессорные структуры", "УС и М", "AB и Т" (3 публикации), "Кибернетика" (3 публикации), "Кибернетика и системный анализ " (5 публикаций объемом « 11.5 п.л.), в трудах международной конференции "Математика в индустрии" (2 публикации), а также в авторской монографии "Параллельная сортировка слиянием. Приложение к вычислению нулей, экстремумов функций и распознаванию образов" объемом и 12 п.л.. Имеется 6 авторских свидетельств по теме работы.

Структура работы. Диссертация состоит из введения, 3 глав, заключения н приложения, также включающего 3 главы; содержит 352 страницы основного текста, 194 страницы приложения, 32 рисунка в основной части и 1 рисунок приложения, 14 таблиц приложения, списка литературы из 297 названий основной части, 112 названий приложения.

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

В первой главе конструируется и исследуется класс параллельных сорти-зовок слиянием, алгоритмы выполнения которых опираются на использование матриц параллельных сравнений (МС). Описание метода дано для внутренних юртпровок по ключу. Упорядочение производится по отношению < в одномерном массиве из N элементов. При слиянии двух уже упорядоченных одномерных массивов

ь,

а1, =1, 2,... ,т-\,

Л*!*

/=1,2, ... , п-1,

(Л С строится как матрица вида

(аД

•де

/ = 0, 1,... ,и + 1 , у = 0,1, ... + 1; [ри этом элемент ау для 0 < /' < ?г + 1 , 0 < _/ < т + 1 определяется знаком равнения элементов <зу и ^

1, ^ < ,

О, ,

-1, >Яу,

заданы ограничители а„

*т+\ "=Ьп+\ = 0О> а0 = ¿0 =-СО'а00=а(п+1)(Пи1)=:0-

При слиянии в упорядочиваемый массив {с1 адрес вставки определятся соотношением

Гб,., если =-1, а;а+1)>0, |а]г если (Ху >0, а(1+1)/ =-1.

Пример МС:

^ =

(1)

-00 1 6 8 10 оо

-00 0 + + + + +

2 , - - + + + +

7 - - - + + +

14 - - - - - +

15 +

+00 0

0 1 2

3

4

5

0 12 3

Вставка, например, элемента 15 в соответствии с (1) определяется соотно-ением с4+4= с$ = ¿ы, вставка элемента 8 - соотношением сг+з ~ с5 = аъ.

Последовательный обход неотрицательных элементов МС влечёт разпо-[дность классической схемы слияния за время 0(п + т), где все адреса вста-к явно заданы; все элементы МС могут быть вычислены синхронно и взаимно зависимо за время одного бинарного сравнения, это приводит к схеме парал-

лельного слияния за время <9(1). Данные два простейших способа варьируются, приводя к различным параллельным алгоритмам, один из которых выполняет слияние двух упорядоченных массивов из N элементов за время <9 (log, log2 А') на N процессорах. Классическая схема сортировки слиянием, упорядочивающая в единый массив N12' массивов из 2' уже упорядоченных элементов на шаге i = 1, 2,..., log2/V, - сохраняется неизменной. В рамках этой схемы все слияния на каждом шаге выполняются параллельно и каждое из них в отдельности распараллеливается с помощью МС оговоренными способами. Три отмеченных выше способа дают оценки T(R) времени сортировки, где R - количество процессоров, соответственно, вида -

2"(1) = <9(Arlog,A0, ЦМ)= log2JV-0(log2log2AO, T(N2!A) =<9(log2iV).

Для фиксированного числа процессоров р = const, 1 <р <п, время слияния получает оценку О (log2 N + (IN -1 )/р), соответственное время сортировки -

rNlog2N^

Т{р)=0

bg2 Р ■

,Р

Одновременное слияние нескольких массивов с квадратичным числом МС также возможно выполнить за время <9(1) и с использованием такого слияния выполнение сортировки ускоряется до

Г

ГМ2Л

rN2 л

=0(1),

- =£?(1одиЛ0, т

где т - число одновременно сливаемых массивов; последняя оценка имеет место, в частности, при т ~ N, в этом случае она соответствует адресной параллельной разновидности сортировки подсчётом, вытекающей из общей схемы как частный случай слияния N массивов, из одного элемента каждый, с количеством МС, равным Л^2 (2. Все данные оценки при R>N улучшают оценку сортировки Батчера. При равном с другими известными методами количестве процессоров представленные в главе оценки либо улучшают оценки этих методов, либо совпадают с ними. Например, время <9(1) сортировки N элементов совпадает с известной оценкой СБС-сортировки (Г.Е.Цейтлин).

Все отмеченные временные оценки в главе даны в виде лемм к теорем с формальным выводом.

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

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

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

В частности, идентичным способом распознаются экстремальные значения ункций, заданных своими координатами на равномерной сетке. С помощью ггоритмического условия, циклически обрабатывающего адреса в массиве от-)ртированных элементов и сопоставленные им обратные адреса этих же эле-ентов во входном массиве, устойчиво локализуются все точки экстремумов в эоизвольно заданной конечной области. Затем с помощью сортировки на сетке сужаемой окрестности каждого локализованного значения организуется спуск юдъем) к точке экстремума. В сортировке используется адрес наименьшего [аибольшего) элемента и она нужна на данной стадии лишь как способ парал-•льного его вычисления. В последовательном варианте спуск (подъем) выпол-ются непосредственно к наименьшему (наибольшему) значению функции на ггке в сужаемой окрестности текущего приближения точки экстремума. Опи-!нная локализация устойчива, вычисление точек экстремума действительных дикций одной и двух переменных отличается повышенной точностью, процесс лчисления максимально распараллеливается, достигая оценки времени вьгчис-ния всех экстремумов в заданной конечной области порядка 0( 1о§2( ег/с )), ,е е - заданная граница погрешности, ео - минимальное расстояние между со-дними точками экстремума, число процессоров Я зависит от размеров облас-:. Вычисляя таким способом минимумы модуля функции, можно локализовать вычислить все её нули. В частности, так локализуются и вычисляются все йствительные и комплексные корни многочлена (как минимум квадрата его >дуля). Устойчивость локализации и точность вычисления характеризует при-:р вычисления без погрешности 33 двукратных комплексных корней много-ена бб-й степени, которые априори отделены друг от друга всего на 10"5. Дру-й пример - вычисление без погрешности всех нулей ( в количестве тридцати

одного) функции ]{х) = 1Xiа • i бш(1/х) !0/4, 0 < ос < 46.001 +1/3, в области точки сгущения на промежутке [ -10"4, -Ю"4 -10"6 ]; нули взаимно отделялись менее, чем на 1/3 • Ю"7. Пример можно существенно усилить. В главе приводятся тексты соответствующих программ общего вида и распечатки для данных и других примеров.

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

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

/Ю^рЮфь), г = 1,2,...,/4,

1=1

к = 1,2,...,К,

(2)

где к - номер последовательного шага; Кк, Ьк, Мы, МЛ( - индексные числовые параметры с определяемыми компилятором значениями; Р^ - идентификатор стандартной функции одной действительной переменной; каждая переменная Ь^ и, аналогично, к моменту выполнения шага к приобретает кон-

кретное числовое значение. Эти значения определяются в соответствии с принципом единственного присваивания и записываются в память посредством подстановки на место переменных в массивы, организуемые для каждого к в виде переменных и констант; выходные значения из (2) структурируются в двумерные массивы (а^). В главе приводится распараллеливаемый алгоритм перевода неветвящейся параллельной программы в форму (2), называемую, при включении в нее означенных массивов, ^-ЕП-программой. Алгоритм служит формальным доказательством теоремы о представимости произвольных невет-вящихся параллельных программ в форме ^-ЕП-программы с сохранением сильной эквивалентности. Для выполнения ^ХП-программы предложено три варианта архитектуры. Первый из них базируется на переводе текущего представления входного алгоритма из формы (2) в ярусно-параллельную форму. За-

;м организуется выполнение бинарных операций, составляющих ярусы, по-эедством заданной последовательности шашв. Каждый шаг детерминирует араллельную работу т = const процессоров, синхронно и взаимно независимо ;уществляющих все бинарные операции шага над уже подготовленными знаниями данных. При этом каждый такой шаг сопровождается шагом синхрон-эш параллельного обмена. Для взаимной независимости физического исполнил обменных операций на шаге сконструирована коммутационная сеть из >(¡?ilog2m) элементов, которая при рассматриваемой структуре данных рабо-1ет без взаимной блокировки коммутационных элементов и управляется де-¡рминированной параллельной программой. Эта программа состоит из т раз-;льных, сопоставленных входам, очередей настроечных кодов. В результате 1ждый шаг обмена выполняется бесконфликтно; время выполнения обменного ara <3(log2wi), включая время настройки сети. Такие характеристики (и пре-це всего - бесконфликтность) достигаются в силу той особенности рассматри-емой структуры данных, что на каждом шаге обмена адреса приемников вза-,шо однозначно соответствуют адресам передатчиков и обладают, помимо то-, монотонностью в числовом выражении. Настроечные коды формируются гмпилятором как эквивалентное преобразование адресов передачи данных на are. Адреса, в свою очередь, детерминированно задаются компилятором из доставления параметров (2) каждому шагу работы процессоров. Весь процесс шолнения к-го шага F-БП-программы происходит с асимптотически мини-[льной оценкой времени, - с точностью до постоянного коэффициента, зави-щего от технических параметров процессоров и коммутационных элементов, обы сохранить такую оценку при переходе от к к к+\ в (2), предлагается ис-льзовать дополнительно ортогональную матрицу из тг модулей памяти. За-:сь в эту память производится параллельно (синхронно и взаимно независимо) столбцам матрицы, считывание, аналогично, - параллельно по строкам. Де-рминизм и бесконфликтность такого обмена в рамках организованной струк-ры данных не нарушается. Возможны рациональные сокращения числа моду-й памяти в а2 - при замедлении рассматриваемой процедуры в а раз.

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

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

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

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

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

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

Третий вариант архитектуры, сохраняя детерминизм управления, бескон-фливсгность обмена, виртуальную неймановскую архитектуру ВС в целом и каждого процессора в отдельности, исключает дополнительную память из т2 модулей. Взамен усложняется коммутационная сеть, которая должна состоять в этом случае из 0(т2) элементов, но, как и в первом варианте архитектуры (а также на базе структуры данных первого варианта), сеть выполняет обмен бесконфликтно за время 0(от), обменом сопровождается каждый шаг параллельной обработки, производимой по схеме первого варианта архитектуры. Цена исключения из архитектуры т2 модулей памяти - отсутствие в общем случае математической гарантии минимальности времени обмена при переходе от к к к+ 1.

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

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

Особенность условных переходов в том, что они организуются по типу последовательных программ. В зависимости от результата проверки условия, выполняется переход по метке к помеченному блоку. Каждый блок представляет собой отдельную F-SII-программу, которой на момент вызова передаются все требуемые ресурсы ВС и программное управление ее работой. Значение метки (адрес перехода), вычисленное отдельным процессором, передается этим процессором в центральное устройство управления и оттуда размножается для всех процессоров, после чего они синхронно переходят к помеченному блоку. Таким образом, программное управление строится последовательно по цепочке условных переходов и параллельно внутри каждого неветвящегося блока. Исключение получения различных значений метки в один и тот же момент времени различными процессорами должно гарантироваться логической конструкцией входной программы (значение истинности условия после окончательного и, возможно, параллельного выполнения всех операций сравнения в условном выражении должен проверять один и только один процессор). Последнее заведомо выполнено, если в параллельно выполняемом фрагменте допускается не более одного условного перехода.

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

В третьей главе предлагается аппаратный способ ускоренного выполнения потока групповых операций вида (2). Способ базируется на методе вертикальной групповой обработки, который исключает операции вычисления переноса и позволяет организовать синхронное максимально параллельное распространение переноса по взаимно независимым, физически раздельным линиям связи в условиях максимально параллельной обработки всех разрядных срезов одновременно всей текущей группы из N «-разрядных операндов, причем, формально, - для произвольного N = const и при любом выборе числа разрядов п = const. Метод имеет две разновидности. Первая состоит в непрерывной обработке потока групповых операндов без выполнения завершающей бинарной операции. Этот вариант является обобщением способа бинарного сложения с запоминанием переноса на случай одновременного суммирования N операндов в текущей группе - без прерывания потока групп на завершение промежуточных

операций. Запоминанию подлежит текущий набор полноразрядных промежуточных слагаемых. Доказана теорема об ограниченности этого набора числом из О Ы) слагаемых при неограниченном продолжении обработки потока. Сконструирована разновидность метода для потоковой обработки групп операндов последовательно по разрядным срезам от младших разрядов к старшим и параллельно по всем операндам группы.

В аналогичной форме, с соответственно доказываемыми оценками, метод переносится на поток сомножителей, а также на поток групповых операций вида (2). Для выполнения вертикального суммирования N одноразрядных двоичных чисел предложены способы и устройства, не использующие операции вычисления переноса. Групповая операция (2) становится базовой операцией в архитектуре параллельной вычислительной системы, описанной в предыдущей главе, предложенный вертикальный метод составляют основу ее аппаратной реализации.

Вторая разновидность предлагаемого метода вертикальной обработки потока групповых данных опирается на способы и схемы устройств бинарного сложения и-разрядных двоичных чисел. Конструкция способов вытекает из изложенного предшествующего метода, она включает предварительный шаг вертикального суммирования. Для данной разновидности отпадает необходимость в запоминании промежуточных результатов - каждая групповая операция может доводиться до однорядного численного значения за время 0(1). Непосредственно сам способ бинарного сложед^ имеет две разновидности - с использованием знакоразрядного представления двоичных чисел и без него. В обеих разновидностях исключаются операции вычисления переноса. Первая разновидность имеет элементарную конструкцию и легко объясняется на приводимом ниже примере. При сложении двух двоичных чисел 11111 и 10101 параллельно по всем разрядам выполняется шаг вертикального сложения всех разрядных срезов:

1 1 1 1 Ц-1 —] 0 1 0 1 0

1 0 1 0 [у-1 => у| 0 1 0 1

Затем каждая ± единица верхней строки меняет знак на противоположный и, одновременно, в нижней строке по диагонали (со смещением на один разряд) записывается единица противоположного знака. Это соответствует товдеству ± 2' = ± (2,+1 - 2'). Остальные разряды не меняются:

2' = 2 - 2'.

0 -1 0 -1 0

1 1 1 1 1

4

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

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

1 1 0 1 0 0

0 0 0 0 0 0

Искомая сумма окончательно сформирована в верхней строке. Метод формально обосновывается с помощью соответствующих лемм и теорем. Время полноразрядного сложения Т (St) = О (\), число элементов сумматора Si-O(N). Согласно этому методу результат формируется, вообще говоря, в знакоразрядном коде и в нем можно вести всю обработку. Вместе с тем эти же преобразования можно использовать для получения результата в прямом двоичном коде. С этой целью знакоразрядные комбинации вида ... 100... 00 -1... требуется перевести в равное им значение ... 011... 11..., что соответствует тождеству

2' - 2* = 2"1 + 2'"2 +...+-2к, 0 < к < i.

Поскольку (как доказано) все такие комбинации взаимно отделены нулевыми разрядами, то все соответствующие им преобразования взаимно независимы и поэтому синхронно реализуемы на параллельно работающих схемах с физически раздельными линиями связи. В результате данных преобразований, осуществляемых с помощью несложно конструируемых схем, все переносы распространятся синхронно и бесконфликтно. По формальным оценкам время параллельного сложения двух л-разрядных двоичных чисел не зависит от числа разрядов п и измеряется единичным значением Т(Sl)-O{\)\ количество элементов сумматора при этом оценивается из соотношения Sl = 0(MUe), где s можно выбрать сколь угодно малым, но фиксированным, - с сохранением порядка данной временной оценки. Эти же сумматоры обнаруживают схемную особенность, связанную с предварительным вертикальным шагом, благодаря которой они могут использоваться для вертикальной обработки: они являются сумматорами п одноразрядных двоичных коэффициентов с временем сложения 0(log2«). Основанное на таких сумматорах арифметическое устройство совмещает режимы вертикальной и горизонтальной обработки, без принципиальных видоизменений оно приобретает функциональные возможности АЛУ; помимо того, на основе инвариантности обработки разрядных срезов, оно допускает реконфигурацию в набор параллельных процессорных элементов и в эффективную сортирующую сеть. В главе даны варианты организации последовательной, параллельной, конвейерной и параллельно-конвейерной архитектуры ВС с использованием данного метода. В силу отсутствия конфликтов при распространении переноса и группового характера потоковой вертикальной обработки, ВС на базе данного метода отличается максимальными оценками производительности, включая случай обработки в системе с плавающей точкой. С целью максимального параллелизма выполнения операций с плавающей точкой существенно используются методы параллельной сортировки, описанные в пер-

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

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

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

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

В частности, в первой главе приложения даны алгоритмические разработки и программные реализации распараллеливаемого метода вычисления элементарных функций, а также их суперпозиций за время 0(1) при произвольно заданной точности аппроксимации ( реализации включают диапазон границ абсолютной погрешности от 10"4 до 10 ~16). По ходу изложения дан реализованный программно распараллеливаемый матричный вариант формул Виета для восстановления коэффициентов полинома от одной переменной через значения его корней. Варианты общего метода строятся путем кусочно-полиномиальной аппроксимации функций с помощью интерполяционных полиномов Лагранжа, Чебышева, а также с помощью отрезков ряда Тейлора. В общем случае аппроксимирующие выражения приводятся к виду многочленов п-й степени с заданными числовыми значениями коэффициентов по схеме, инвариантной относительно и. На основе такой инвариантности для заданной границы погрешности приближения заданной функции на заданном промежутке осуществляется циклическая программная схема выбора наименьшего п для всей совокупности подынтервалов, составляющих разбиение исходного промежутка. Полином при этом строится отдельно на каждом подынтервале; подынтервалы берутся равной длины. Дополнительно, с целью выбора одного и того же значения п = const одновременно для всего (фиксированного) набора аппроксимируемых функций, число подынтервалов полагается переменным и программно минимизируется для поочередно фиксируемых п (начиная с = 1) при условии достижения заданной точности аппроксимации одновременно по всем подынтервалам для каждой из функций. Наименьшее из таких п выбирается пользователем из соображений максимального быстродействия при допустимости требуемых затрат

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

Вычисленные коэффициенты записываются в память в соответствии подынтервалам и каждой функции. Для произвольного аргумента х функции данное соответствие подынтервалу устанавливается по соотношению / = (х - х0 )div/i, где дго - левая граница промежутка, h - длина подынтервала; i интерпретируется как относительный адрес выборки соответственных коэффициентов. Такой способ хранения и выборки целесообразен для организации библиотеки стандартных подпрограмм вычисления элементарных функций. Время вычисления функции в этом случае пропорционально степени аппроксимирующего полинома, которая произвольно выбрана и зафиксирована. При выборе малого п = const время вычисления функции будет измеряться единичной оценкой Т -О (1). Канонический вид аппроксимирующего полинома и переменность числа подынтервалов в изначальной схеме позволяет отделить и приближенно вычислить (как нули полинома малой степени, например, п = 1, 2, на текущем подынтервале) все действительные нули функции на произвольно фиксированном промежутке. Схема распараллеливается по совокупности подынтервалов. Те же качества рассматриваемой кусочно-полиномиальной аппроксимации приводят к общей машинной схеме приближенного вычисления производных высшего порядка , а также к машинным схемам приближенного численного интегрирования, отличающимся высокими оценками точности приближения. Все рассматриваемые схемы вычислений обладают параллелизмом, в главе проводятся формальные оценки эффективности распараллеливания. Дополнительно обсуждается применимость предложенных разновидностей схем параллельного вычисления полиномов и параллельной полиномиальной аппроксимации.

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

Для метода итерации

хк = Ах,к_х +Ь, к- 1,2,...

решения системы

х = Ах+Ь

с матрицей А , пхп , dct (Е - А ) Ф 0 , || Л||<1, и начальным вектором хо имеет место эквивалентное преобразование

Аг = Аг-\ , xv = Ar.ixr-1 + brA , br = Аг.\Ьг-\ + br-\, г = 1,2,...

А0 = A, bo = Ь , которое дает совпадающие значения итераций хк и хг при

к = 24

ял и

/■ = 1ов2(* + 1). (3)

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

Г(Й)=1о82Ш(1о82и), (4)

где и - порядок матрицы, к ~ к{&) - число итераций метода в исходной классической форме, при которой искомое решение приближается с точностью до б. Это означает, что число итераций сокращается в геометрической прогрессии, сами итерации при этом усложняются, но допускают максимальное распараллеливание. Аналогичная схема применяется для обращения матрицы. В случае треугольной матрицы данные итерационные схемы переходят в точные методы обращения матрицы и решения системы с временной сложностью Т(К) = О «). Количество процессоров в данных схемах варьируется от одного до 0(п3). Все отмеченные верхние оценки временной сложности представлены в форме соответственно доказанных лемм и теорем для различного числа процессоров. Даны способы последовательной программной реализации базовых вариантов методов для случаев матриц и систем общего вида, а также для треугольных матриц.

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

/

Е

.(М'

к = 1,2,...,

где матрица В,их п, состоит из вектора Ь и п-1 нулевых столбцов размерности«

В =

ЬОО—Об

\

О - нулевые столбцы, I - вектор из единичных компонент, Е - единичная, О -нулевая матрицы. Отсюда

А В уО Е;

\к

.(0)

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

ч / Ал

Иг<*>-Х

де х - решение системы. Соответственную степень матрицы можно найти по-ледовательным возведением в квадрат:

А<°>=

О

А

0)

=(А(0))2,...А(Г) = (А (Г'»)2.

(5)

1исло шагов такой схемы оценивается из (3). Максимальное ее распараллелимте влечет оценку (4 ) для времени реализации данной схемы ,Я = п3 + п2.

В правой верхней клетке будет получаться (Е-Л) )тсюда

-1

, если положить В-Е.

де

Е

любой номер, начиная с (3). Степень матрицы вычисляется аналогично (5)

•Л)

-I

достаточно задать

l(°) =

и последовательно возводить в квадрат эту и затем текущую

ри В-Е. Чтобы вычислить по такой схеме (Е -ГА Е^

Е;

атрицу. Контроль точности достаточно проводить по сравненшо результатов зседних шагов, поскольку разность показателей в соотношении

->'-! о'

/ л

Se

звна 2е 1, она окажется больше любого наперед выбранного и зафиксирован-ого числа т, как только £~\> log2 т. Изложенная схема в главе реализована рограммно. Очевидно, целесообразной является уже ее последовательная реа-лзация. Даны варианты схемы и программа с подготовкой для обращения мат-ацы общего вида. Программа обращает в приближенном виде произвольную ^вырожденную матрицу. Аналогичные схемы приводятся для перечисленных пне линейных итерационных методов, исключая методы Ричардсона.

Сходным образом преобразуются разностные методы приближенного ре-ения систем линейных дифференциальных уравнений с достоянной матрицей >эффициентов. Это ускоряет параллельный процесс их приближенного реше-1Я, но число итераций в этом случае не сокращается, а в геометрической про->ессии возрастает удаленность аргумента вычисляемых значений решения от гаалыюй точки. Это влечет возможность машинной аппроксимации асимпто-[ческого поведенггя решения. На этой основе формируется программа анализа тойчивости по Ляпунову решения системы линейных дифференциальных »авнений с матрицей постоянных коэффициентов. Программа адекватно моде-

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

d-}- = BY (6)

dt

с постоянной матрицей В, п х п, и с начальными условиями

Г(/о)=Го

формально сводится к следующем}' ограничению. Пусть

t=t2l =t0+2kh, (7)

матрица А образуется из матрицы В путем добавления к единичной матрице Е матрицы В с множителем h

A = E+hB,- (8)

соответственно конструкции метода Эйлера

Тк+1 =Г, +hBYk = (Е +hB )Yk = АУк. Теорема. Для того, чтобы решение Y((,t0,F0) однородной системы (6) с постоянной матрицей коэффициентов В было устойчиво (справа) в смысле Ляпунова, необходимо и достаточно, чтобы матрица А из (8) удовлетворяла ограничению

I 9* И

| lim А \\<с - const I к-у>о II

на всем множестве точек t полупрямой [ t0, <к ). При этом h ,t0 , t и к связаны между собой соотношением (7). Для асимптотической устойчивости (справа) необходимо и достаточно, чтобы

lim А'

¿-»ос

->0.

Работа приводимой в главе программы сводится к последовательному умножению матрицы А на себя с вычислением нормы произведения; А берется порядка 10"14 . Адекватно утверждению теоремы при апробации программы текущая норма ограничена в случае устойчивости, стремится к нулю в случае асимптотической устойчивости, неограниченно возрастает при неустойчивости.

В последней (третьей) главе приложения доказывается вычислительная устойчивость предложенных параллельных схем.

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

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

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

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

параллельном варианте метода итерации происходит с оценкой

( „ |> Л

И

О-

е„ +

г <[1од2(&+!)_], к =1,2,..., где г,п =■■ яе, к- номер текущей итерации в исходной канонической схеме, начиная с которого решение приближается по норме с точностью до е, Ьг -точное значение вектора итерации, Ьг - возмущенное значение вектора той же итерации, взятые при хг, = Ь. Таким образом, накопление погрешности в предложенном преобразовании метода простой итерации имеет логарифмический характер. Это означает условную устойчивость данного параллельного метода с существенно малым накоплением погрешности. При этом учитывается только погрешность машинного округления на каждой текущей арифметической операции.

Собственно предлагаемые разновидности параллельной формы метода Ле-верье опираются на известную схему Ксанки и сохраняют оценку временной сложности этой схемы Т(Я) = О (1о^ л), Я ~ 0(п4). Различие состоит в других способах параллельного решения треугольной системы уравнений Ньютона, из которых вычисляются коэффициенты характеристического многочлена матрицы. Предложенные способы строятся в форме мультипликативных матричных операций. Чтобы показать их устойчивость, а также устойчивость всего предложенного параллельного видоизменения метода Леверье, выполнен ряд предварительных оценок накопления погрешности матричных произведений для случая неограниченного набора матриц-сомножителей, детально рассмотрен

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

Для одной из этих схем имеет место следующий характер накопления почетности вычисления вектора Р„ _ составленного из коэффициентов искомого характеристического многочлена матрицы А. Если |Л||<1, то

|р-,Рп||й(4г2|^|2 + 1б«||Л|2+(« + 4)|^|)-е„+^(е2) . (9)

Если IIАII < — , то

11 11 2 п

ря-фз.(|+^я+0-(в2). (10)

Если же, дополнительно, выполняется ограничение

а = соп^, а>0, (11)

то имеет место неравенство

Отсюда в случае а > 1 формально достигается безусловная вычислительная устойчивость предложенной схемы:

+ 03)

Однако, оценку (13) не следует понимать как означающую прямое уменьшение погрешности с ростом размера матрицы. Эта оценка будет выполняться при одновременном с ростом размера уменьшении элементов матрицы по норме, - согласно условию (11). Поэтому область применимости оценки (13) на практике ограничена конечностью длины разрядной сетки. Иначе с ростом п, в силу условия (11), могут теряться значащие цифры элементов переменной матрицы.

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

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

Известно, что на основе метода Леверье с использованием тождества Га-мильтона-Кэли строится прямой метод решения систем линейных алгебраических уравнений. Этот факт анализируется отдельно, дополнительно обсуждается практическая приложимость метода к построению жордановой формы и канонического базиса.

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

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

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

Новизна результатов следует из представленных выше характеристик. Эти характеристики можно дополнить краткой сводкой отличий предложенных базовых методов от известных.

Впервые для выполнения сортировок предложено использовать матрицы сравнения. На их основе достигается максимальный параллелизм, синхронность и взаимная независимость операций сравнения, а также адресность вставок. Класс новых сортировок получается по единой схеме, в рамках которой при равном числе компараторов сортировка Багчера для одномерного массива из N элементов ускоряется в 0( 1од2 7/) раз; с увеличением числа компараторов в N

раз ускорение той же сортировки достигает значения достигается

формально не улучшаемое время сортировки 0(1) и с такой же оценкой (превосходящей оценки аналогов) может быть выполнено слияние т упорядоченных одномерных массивов из N элементов в единый упорядоченный одномерный массив при условии т < N. Сортировка неограниченного массива на р - сортировщике достигает порядка оптимальной оценки Бейгеля и Гилла с малым значением коэффициента t(p) = log2 р. Впервые выполнено применение адресной сортировки в качестве конструктивной схемы распознавания; в частности, с ее помощью распознаются признаки экстремальных особенностей функций одной и двух переменных. На этой основе построен распараллеливаемый метод устойчивой локализации нулей и экстремумов функций и их вычисления с повышенной точностью. Метод существенно отличается от известных по конструкции, а также по характеристикам устойчивости, точности и универсальности.

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

Предложен метод вертикальной обработки, который в отличие от известных аналогов полностью исключает операции вычисления переноса на всех стадиях обработки потока групповых и бинарных данных для структур данных общего вида. Тем самым исключаются задержки потока для завершения промежуточных операций. В приложении к бинарным операциям ка основе метода впервые синтезирован параллельный сумматор с единичной (0(1)) оценкой времени сложения «-разрядных двоичных чисел при любом п = const. Данная оценка в 0(log2w) улучшает существующие оценки времени параллельного

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

По теме диссертации опубликовало свыше 90 печатных работ объемом эколо 95 п. л. Из них основными являются

1. Платонов В.А., РоммЯ.Е. Об одном признаке неустойчивости решения систем Шеннона. - В кн.: Однородные цифровые вычислительные и интегрирующие структуры. Вып. VI. - Таганрог, 1976. - С. 38 - 46.

2. Каляев A.B., Платонов В.А., Ромм Я.Е. О сходимости метода численного интегрирования по Стильтьесу дифференциальных систем Шеннона //Известия Северо-Кавказского научного центра высшей школы. Серия «Естественные науки», Ростов. - 1976. 4. - С. 35 - 37.

3. Пьявченко О.Н., Ромм Я.Е. Модификация таблично-интерполяционного метода вычисления элементарных функций в ЭВМ. - В кн.: Проблемы проектирования и применения дискретных систем в управлении (Минск, 1977): Тезисы докл. I международной конференции молодых ученых, Люберцы, ВИНИТИ, 1977. - С. 326 - 328.

4. Каляев A.B., Платонов В.А., РоммЯ.Е. Вопросы устойчивости при реализации функций и дифференциальных уравнений в ОЦИС. - В кн.: Проблемы проектирования и применения дискретных систем в управлении (Минск, 1977): Тезисы докл. I международной конференции молодых ученых, Люберцы, ВИНИТИ, 1977. - С. 270 - 273.

5. Пьявченко О.Н., Сурженко И.Ф., Ромм Я.Е. Метод распараллеливания схемы Горнера и его приложение к цифровым вычислительным устройствам // Автоматика и вычислительная техника. - Рига. - 1978, № 5. - С. 73 -78.

S. Пьявченко О.Н., Ромм Я.Е, Сурженко И.Ф. Распараллеливание некоторых численных алгоритмов и операций для мультипроцессорных мини- и микро -ЭВМ. - В кн.: Всесоюзная школа-семинар "Автоматизация проектирования средств вычислительной техники и перспективы применения микропроцессоров", Минск, 1978. -С. 67- 68. L Ромм Я.Е. Об одном алгоритме решения задач математической физики в мультимикропроцессорной ЭВМ. - В кн.: Специализированные и комбинированные устройства, Рязань, 1978, вып.6. - С. 133 - 137. 5. Ромм Я.Е. Применение некоторых методов распараллеливания для вычисления цепных и рациональных дробей // Многопроцессорные вычислительные структуры. - Таганрог. - 1979. - Вып. 1(Х). - С. 72 - 73.

9. Пьявченко О.Н., Ромм Я.Е ,Сурженко И.Ф.. Об одном математическом подходе к разработке мультимикропроцессорной ЭВМ с перестраиваемой структурой // Управляющие системы и машины. - Киев. - 1979. - № 4. - С. 106 -109.

10. Пьявченко О.Н., Ромм Я.Е., Сурженко И.Ф. О реализации параллельной полиномиальной аппроксимации в многопроцессорной струхтуре // Автоматика и вычислительная техника. -Рига. -1981. - № 4. - С. 33 - 40.

11. A.C. 813443. Устройство для вычисления полиномов / Пьявченко О.Н., Луконин A.A., Ромм Я.Е., Сурженко И.Ф. Опубл. в БИ, 1981, № 10.

12. Ромм Я.Е. О параллельной форме метода Гаусса. - В кн.: Специализированные и комбинированные вычислительные устройства, Рязань, 1981. - С. 15 -18.

13. Ромм Я.Е. Об ускорении линейных стационарных итерационных процессов в многопроцессорных ЭВМ. I // Кибернетика. - Киев - 1982. - № 1. - С. 47 -54.

14. Ромм Я.Е. Об ускорении линейных стационарных итерационных процессов в многопроцессорных ЭВМ. II // Кибернетика. - Киев - 1982. - № 3. - С. 64 -67.

15. A.C. № 929778 (СССР). Комбинированная вычислительная система / Авдеев

B.А., Ромм Я.Е. Опубл. в БИ 1982, № 14.

16. A.C. 1019456. Устройство для вычисления полиномов с фиксированными коэффициентами / Ковалев А.Н., Ромм Я.Е., Сурженко И.Ф, Чернов Е.И. Опубл. вБИ, 1983, №19.

17. Ромм Я.Е., Калиниченко И.Н. Об оценке погрешности параллельных вычислений в приложении к итерационным процессам линейной алгебры // Многопроцессорные вычислительные структуры. - Таганрог. - 1983. - № 5 (XIV). -

C. 33 - 36.

18. Пьявченко О.Н., Сурженко И.Ф., Ромм Я.Е. Параллельная обработка арифметических выражений в инвариантной форме. - В кн.: Распараллеливание обработки информации . Ч.З. Тез. докл. Всесоюзной школы-семинара, Львов, 1983. - С. 71 - 72.

19. A.C. 1153325. Устройство для вычисления полиномов / Ковалев А.Н., Ромм Я.Е., Сурженко И.Ф, Чернов Е.И. Опубл. в БИ, 1985, № 16.

20. Ромм Я.Е. Параллельный устойчивый вариант метода Леверье-Фаддеева / ТРТИ - Таганрог, 1985. - 57 с. Деп. в ВИНИТИ 12.07.85, № 5005-85 ДЕП.

21. Пьявченко О.Н., Сурженко И.Ф., Ромм Я.Е. Архитектурно-алгоритмическая организация параллельных вычислений. - В кн.: Распараллеливание обработки информации. Ч. 2. Тез. докл. Всесоюзной школы-семинара, Львов, 1985. -С. 29-30.

22. Пьявченко А.О., Ромм Я.Е. Некоторые способы синхронной передачи данных // Многопроцессорные вычислительные структуры. - Таганрог. - 1986. -Вып. 8(XYII). - С. 42-45.

23. Пьявченко О.Н., Сурженко И.Ф., Ромм Я.Е., Калиниченко КН. О вычислении функций в МВС // Многопроцессорные вычислительные структуры. - Таганрог,- 1987,- Вып. 9(XVIII). - С. 52 - 55.

24. A.C. № 13814994 (СССР). Устройство для вычисления корня n-н степени / Глотов М.И., Ромм Я.Е., Сурженко И.Ф., Хало В.В. Опубл. в БИ 1988, № 10.

25. Сурженко И.Ф., Ромм Я.Е. О машинной погрешности параллельных алгоритмов // Кибернетика. - Киев - 1988. - № 2. - С. 19 - 26.

26. Пьявченко О.Н., Блинова JI.M., Ромм Я.Е. Об организации вычислений в ¿л системе обработки потокового типа. - В кн.: Многопроцессорные комплексы ™ и системы. Тез. докл., Таганрог - 1988. - С. 43.

27. Блинова Л.М., Борисенко С.Н., Ромм Я.Е., Сапрунов В.Н. Об организации конвейерного режима вычислений в F-P-S-системе. - В кн.: Конвейерные вычислительные системы. Тез. докл. и сообщений 2-го Всесоюзного совещания. Киев. -1988. - С. 130-131.

28. Ромм Я.Е. Об организации групповых параллельно-конвейерных вычислений. - В кн.: Конвейерные вычислительные системы. Тез. докл. и сообщений 2-го Всесоюзного совещания. Киев. - 1988. - С. 115 - 117.

29. Никулина Г.С., Ромм Я.Е. Таблично-алгоритмический метод параллельного вычисления функций. - В кн.: Параллельные вычислительные системы. Препринт ИППММ АН УССР № 8-89. - Львов. - 1989. - С. 20 - 24.

30. A.C. № 1485261 (СССР). Устройство коммутации / Пьявченко А.О., Ромм Я.Е. Опубл. в БИ 1989, №21.

31. Пьявченко А.О., Ромм Я.Е. Коммутационная сеть для межпроцессорного обмена и сортировки // Автоматика и вычислительная техника. - Рига. - 1990. - № 1,-С. 70- 79.

32. Ромм Я.Е. Детерминированная организация параллельной числовой обработки по индексам данных // Кибернетика и системный анализ,- Киев - 1992. -№ 4.-С. 133- 152. ^

33. Ромм Я.Е. Параллельная сортировка слиянием по матрицам сравнений. Кибернетика и системный анализ. - Киев - 1994. - № 5. - С. 3 - 23.

34. Ромм Я.Е. Параллельная сортировка слиянием по матрицам сравнений . II // Кибернетика и системный анализ. - Киев - 1995. - № 4. - С. 13 - 37.

35. Ромм Я.Е. Устойчивая локализация и вычисление с повышенной точностью нулей функций при помощи адресной сортировки. - В кн.: Международная конференция «Математические модели физических процессов и их свойства» (30.5 - 2.6 - 1997 г.). - Тез. докл. - Таганрог. - С. 78 - 79.

36. Ромм Я.Е. Итерационный критерий устойчивости в смысле Ляпунова решения системы линейных дифференциальных уравнений с постоянными коэффициентами. - В кн.: Труды международной конференции "Математика в индустрии" (ICIM-98, Таганрог, 1998,29 июня - 3 июля). - Изд-во Таганрогского госуд. педагогич. ин-та.- Таганрог. - 1998. - С. 263 - 265.

37. Ромм Я.Е. Параллельная сортировка слиянием. Приложение к вычислению нулей, экстремумов функций и распознаванию образов,- Таганрог: Изд-во ТГПИ, 1998. - 190 с.

38. Ромм Я.Е., Тесленко О.В. Решение полной проблемы собственных значений и построение жордановой формы матрицы с использованием сортировки. - В кн.: Труды международной конференции "Математика в индустрии" (1С1М-98, Таганрог, 1998,29 июня - 3 июля). - Изд-во Таганрогского госуд. педаго-гич. ин-та.- Таганрог. - 1998. - С. 265 - 267.

39. Ромм Я.Е. Метод вертикальной обработки потока целочисленных групповых данных. I. Групповые арифметические операции // Кибернетика и системный

Алнализ,- Киев - 1998. - № 3. - С. 123 -151.

Ромм Я.Е. Метод вертикальной обработки потока целочисленных групповых данных. II. Приложение к бинарным операциям // Кибернетика и системный анализ. - Киев - 1998. - № 6. - С. 145 - 162.

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

Тип. ТРТУ. Зак.465. Тир.ЮО.