Введение к работе
Актуальность проблемы. В настоящее время интенсивность разработок и сследований в области архитектуры, программного обеспечения параллельных С (суперкомпьютеров) и методов параллельной обработки такова, что лишь еречисление действующих разновидностей суперкомпьютеров заняло бы не-солько страниц. Область применения параллельных ВС охватывает обработку эрокосмических данных, радиолокационных и гидроакустических сигналов, а нсже системы управления атомной энергетикой, автоматикой космических істем, управления оружием; она включает использование в АСУ и в ииформа-июнных системах, в системах виртуальной реальности и распознавания обра-)в и т.д. Эта область непрерывно расширяется, включая отрасли от геологии, гфтедобычи, метеорологии и сейсмической обработки до организации лесного ззяйства и финансовых расчетов для школ и промышленных, учреждений, бъем продаж суперкомпьютеров на мировом рынке к 2000-му году составит 50 млрд. долл. Вместе с тем тематика параллельных вычислений сохраняет ряд ;ретённых проблем. Актуальной остается проблема зависимости эффективно-лі пользовательских программ от архитектуры параллельных ВС. Параллель-зе программирование остается сложным; для достижения эффективности со-авляемой программы, помимо программирования десятков (сотен и тысяч) юаллельных компонент, требуется согласовать выполнение соответственных юграммных компонент между собой, притом с учетом особенностей архитек-гры единой системы. В существенной мере сложность и эффективность паралельного программирования определяется способами организации обмена, руктурой и уровнем их аппаратной поддержки. В общей постановке глубина зоблемы заключается в алгоритмическом несоответствии индетерминизма іераций обмена и детерминированности управляющей параллельной про-іаммьі. Приемлемое разрешение трудности имеет место лишь в случае узкой юблемной ориентации параллельной ВС. В общем случае данное несоответ-вие влечет замедление текущего шага параллельной обработки и снижение её зфективности в целом, поэтому задача эффективной организации обмена со->аняет значительную актуальность. Для её решения требуется организовать >гическое разделение операций и адресов обмена, а также физическое разде-:ние линий связи, по которым передаются сигналы обмена при выполнении ловия минимизации времени обмена и параллельной обработки в целом. На ювне микроопераций такая постановка вопроса также сохраняет смысл, ей со-ветствует, в частности, задача исключения более одного переноса в любой из зрядов в любой момент времени выполнения произвольных арифметико-ігических операций. При этом, как и выше, сохраняется требование минями-ции времени обработки в целом. Для решения этой задачи требуется логиче-ое и физическое разделение битовых операций, включая операции переноса, а кже физическое разделение линий связи в процессе арифметико-логической работки, причем должен иметь место максимальный параллелизм обработки зрядных срезов всех доступных операндов. В рамках данного подхода естест-нно опираться на принципы вертикальной обработки, поэтому актуальна за-
дача эффективного соединения вертикальной и горизонтальной схем обработки при формальной неограниченности дайны разрядной сетки. Обе эти задачи включаются в общую цель построения бесконфликтных методов параллельной обработки на уровне макро- и микроопераций. Хорошо известна зависимость эффективности параллельной обработки от связи архитектуры параллельной ВС с конструкцией базовых узлов и, одновременно, со структурой и качеством параллельных алгоритмов. В первом отношении актуально совокупное решение охарактеризованных задач и построение совместимой с этими архитектурными решениями системы программного обеспечения. Во втором отношении актуально создание банка параллельных алгоритмов, ориентированных на реализацию в рамках разрабатываемой архитектуры. Ввиду исторически сложившейся последовательной конструкции алгоритмов создание и расширение банка параллельных алгоритмов актуально само но себе. При этом особой остротой отличается проблема их вычислительной устойчивости. Представляется целесообразным рассматривать эту проблему в контексте обсуждаемой связи алгоритмов, архитектуры и структуры параллельной ВС. Основные архитектурные решения можно ограничить предположением проблемной ориентации ВС на класс задач вычислительной математики, вместе с тем целесообразно исследовать возможность расширения области проблемной ориентации для включения в неё методов информационно-логической обработки и распознавания образов. Искомые методы будут опираться на параллельную сортировку, актуальность их построения определяется актуальностью проблемы разработки эффективных алгоритмов сортировки, а также актуальностью проблем распознавания образов.
Цель диссертационной работы заключается в том, чтобы создать архитектуру параллельной ВС, сконструировать методы параллельной обработки и обмена, в которых конфликты исключаются на физическом и алгоритмическом уровне. При этом управление выполнением произвольного параллельного алгоритма (из области проблемной ориентации) в ВС должно быть детерминированным, время его выполнения должно оцениваться как минимальное. Поставленную цель можно сформулировать иначе со следующими уточнениями. Архитектура конструируемой параллельной ВС должна сохранять взаимную независимость выполнения не. только для всех вычислительных операций входного параллельного алгоритма, но, одновременно с тем, и взаимную независимость выполнения всех операций обмена. Эта независимость должна иметь место для процесса обработки и обмена на уровне крупных (групповых) операций, на уровне бинарных операций, а также на уровне микроопераций. Взаимная независимость всех операций вычисления и обмена должна обеспечиваться физическим взаимным различием средств обработки, хранения и линий связи, которые при этом используются. Аналогично, взаимная независимость должна иметь место в алгоритмическом смысле, адекватном соответственному физическому различию. При таком максимальном параллелизме обработки, хранения и перемещения информации должно удовлетворяться требование минимальности
"ч
эемени выполнения произвольного входного алгоритма из области проблем-зй ориентации ВС. За первоначальную область проблемной ориентации ВС отнимаются методы решения задач вычислительной математики. Цель работы нтолнительно включает расширение банка существующих параллельных алго-гтаов за счет разработки устойчивых параллельных алгоритмов, совместимых предлагаемой архитектурой параллельной ВС.
Цель достигается на оснозе постановки и решения следующих задач.
1. Разработать архитектуру параллельной вычислительной системы с такой
>ганизацией параллельной обработки и обмена, при которой исключены коп
иисты на физическом и на алгоритмическом уровне. При этом время парал-
шьного выполнения каждого конкретного алгоритма должно измеряться
ммпгстически минимальной величиной. Предполагается, что вычислительная
[стема с данной архитектурой проблемно ориентирована на решение задач
тчислительвой математики. Вместе о тем должна исследоваться возможность
юширения области проблемной ориентации.
Для достижения математически гарантированного минимума времени вы-мгнения параллельного алгоритма требуется учет готовности значений пере-яшых и адресов обмена, причем формально такой учет необходим в рамках терминированной программы на весь период выполнения входного алгорит-1.
Применительно к коммутационной сети требование бесконфликтности обжа при условии минимизации его времени означает исключение взаимных юкировок коммутационных элементов. Построение таких сетей будет рас-іатриваться з единой системе с построением архитектуры параллельной ВС. золочение взаимных блокировок должно достигаться физическим разделени-[ линий связи, по которым идет обмен данными, и детерминированием адре-в обмена.
Поставленную задачу можно кратко сформулировать следующим образом.
Требуется разработать реконфигурируемую архитектуру параллельной ВС минимизированными по времени обработкой и бесконфликтным обменом, ні этом параллельная программа обработки и обмена должна быть детерми-[рованной и хранимой на весь период решения произвольной задачи из класса цач вычислительной математики.
2. С целью ускорения базовых операций в рамках конструируемой архитек-
ры параллельной ВС разработать следующий метод аппаратизации потоковой
работки. Для параллельного арифметического устройства исключение кон-
[иктов при условии синхронности обработки разрядных срезов группы опе-
ндов будет пониматься как исключение прихода в один разряд двух или более
реносов независимо от числа разрядов операндов и независимо от числа оне-
ндов. Задача построения максимально параллельного метода групповой обра-
тки с данным качеством эквивалентна задаче организации вертикальной по-
ковой групповой арифметической обработки с максимальным параллелизмом
товых операций по всем разрядным срезам одновременно всей текущей
группы с произвольным числом операндов. При этом требуется полностью исключить конфликты в процессе параллельной обработки и обмена на уровнях макро- и микроопераций. Иными словами, требуется построить метод вертикальной арифметической обработки потока групповых и бинарных данных. полностью исключающий операцию вычисления переноса как на стадии обработки потока, так и на стадии завершения произвольной бинарной операции При этом все разрядные срезы всех операндов должны обрабатываться синхронно и взаимно независимо, - формально при произвольном фиксировании длины разрядной сетки и при произвольном делении потока на конечные группы операндов.
-
С целью расширения области проблемной ориентации предложенной архитектуры до круга задач информационно-логической обработки требуется сконструировать класс параллельных сортировок и методов слияния, реализуемых в рамках данной архитектуры при соответственных вариантах её реконфигурации. Сортировки при этом должны обладать минимальными для заданного числа процессоров оценками временной сложности, параллельная программа их выполнения должна быть детерминированной, обмен - бесконфликтным. Для обеспечения искомьк характеристик процессы слюшия и сортировки должны базироваться ка максимальном параллелизме операций сравнения и детерминированном задании адресов обмена (вставок) в явной форме.
-
С той же целью, а также с целью расширения банка устойчивых параллельных алгоритмов применить сконструированные сортировки к распознаванию образов и к вычислению нулей и экстремумов функций. Для распознавания образов при этом должна использоваться адресность сортировки с формированием на ее основе подстановки из индексов входных и выходных элементов Для вычисления экстремумов (с предварительным их распознаванием), помимо того, следует опираться на отсутствие накопления погрешности во взаимно независимых бинарных сравнениях алгоритма сортировки. В частности, с помощью конструируемых сортировок требуется получить устойчивую распараллеливаемую локализацию и распараллеливаемое вычисление с повышенной точностью нулей нелинейных функций (как минимумов модуля этих функций), включая локализацию и вычисление всех корней многочлена произвольно фиксированной степени.
-
Дополнительно расширить банк устойчивых параллельных алгоритмов, реализуемых в рамках рассматриваемой архитектуры, включив в неё алгоритмы из области приближенных численных методов линейной алгебры, анализа и решения обыкновенных дифференциальных уравнений. В частности, разработать устойчивый приближенный метод параллельного вычисления элементарных функций и их суперпозиций за время 0(1) при произвольно заданной границе погрешности приближения;
преобразовать линейные итерационные методы решения систем линейных алгебраических уравнений к параллельной форме с экспоненциальным сокращением числа итераций при условии максимального распараллеливания каждой итерации;
перенести полученный метод на случай приближенного решения систем інєйньгх дифференциальных уравнений с постоянной матрицей и сконструи-вать на этой основе машинный метод анализа устойчивости в смысле Ляпу->ва решений таких уравнений;
с использованием вычисления корней многочленов на основе сортировки зработать устойчивые параллельные варианты метода Леверье решения лол-'й проблемы собственных значений, полученные при этом оценки вычисли-льной устойчивости требуется, по возможности, перенести на линейные ите-ционные методы.
В работе использован аппарат теории вычислительных машин и систем, ории алгоритмов, теории сложности, математического анализа, вычислитель-IX методов линейной алгебры, обратного анализа, приближенных методов шения и качественной теории обыкновенных дифференциальных уравнений.
Научная новизна Предложена архитектура реконфигурируемой парал-лыюй ВС с детерминированной параллельной программой обработки и бес-нфликтного обмена, которая обеспечиваег асимптотический минимум време-выполнения произвольного алгоритма из области решения задач вьгчисли-иьной математики. Область проблемной ориентации включает основной на-шный класс задач, а также, дополнительно, методы информационно-гической обработки и распознавания образов. Предложенная архитектура со-ветствует концепции виртуальной машины фон Кеймана, отлхтчаясь от анало-з конкретными алгоритмігческими механизмами и схемными решениями в ^чае выполнения отдельно взятого алгоритма рассматриваемого класса. Наи-лее принципиальное отличие заключается в детерминированности управ-ющей параллельной программы, наиболее характерное - в пошаговой (или этично пошаговой) организации бесконфликтного обмена с использованием гциачьной коммутационной сети из О(Jog2 ^элементов с временем передать сигналов <9(log2 N), включая время настройки. В зависимости от варианта ганизации вычислений, может использоваться сеть из 0{N2)элементов, - с л же временем передачи сигаалов в условиях однозначности адресов переда-; сеть, помимо того, способна выполнять внутреннюю сортировку N ключей с і же временной оценкой. По сравнению с существующими архитектурами эаллельных ВС два первых предложенных варианта содержат два существен-х упрощения. Одно из них - аппаратное - заключается в упрощении цен-шьного устройства управления, роль которого сводится к выдаче синхронизующих импульсов параллельным компонентам ВС. Второе - программное -зощает пользовательское программирование: во входной программе пользо-елю достаточно идентифицировать только математический параллелизм, -і учета архитектуры ВС.
Предложен метод вертикальной обрабогки потока групповых и бинарных шых, который в случае арифметической обработки полностью исключает грации вычисления переноса в условиях синхронной и взаимно независимой заботки всех разрядных срезов одновременно всех операндов текущей груп-
пы. В частном случае бинарного сложения, и-разрядных двоичных чисел на основе метода синтезируется параллельный сумматор с временем сложения 0(Г для произвольно фиксированного п. Все переносы синхронно распространяете; по взаимно независимым линиям связи; в случае знашразрядных числовых кодов сумматор состоит из 0(п) элементов; в случае бинарного сложения двоичных чисел с положительными коэффициентами количество элементов ИМЄЄ1 сценку 0(л1+Е), где є - произвольно мало, но фиксировано. Существующш методы параллельного суммирования ускоряются в 0(log2Ar) раз. Суммато обнаруживает способность эффективно суммировать одноразрядные двоичньк числа, п из которых он складывает за время 0(iog2 и). При этом число его эле ментов в О (л) меньше числа элементов аналогичных устройств. На базе топ же способа время параллельного умножения ускоряется пропорционально ускорению завершающего суммирования. Метод вкладывается в предложеннук архитектуру параллельной ВС, формируемое на его основе арифметическое устройство способно реконфигурироваться в эффективную сортирующую сеть. Разработано видоизменение соргировки слиянием, использующее матриць параллельных сравнений. С использованием матриц сравнения получен клас< адресных параллельных сортировок, которые совместимы с предложенной архитектурой параллельной ВС. Параллельная программа выполнения каждой и: них в такой ВС может быть детерминированной, обмен в процессе выполнена - бесконфликтным. По сравнению с существующими полученные алгоритмь параллельных сортировок отличаются максимально параллельной конструкцией схемы слияния, а также улучшенными оценками временной сложности прі равном количестве процессоров, В частности, одномерный массив из N элементов на N процессорах упорядочивается за время Г = log2 N О (bg2 log2 N), н
JV2 /4 процессорах - за время Т = 0(1) . Тем самым сортировка Батчера при равном числе процессоров ускоряется в C(log2 N) раз; с увеличением числ;
процессоров в 0(N) та же сортировка ускоряется в 0(log27V). Слияние дву упорядоченных массивов из N элементов на N процессорах выполняется за время О (log2 log2 N), на Nz процессорах - за время 0(1). Адресность предложенных соргировок позвояяег локализовать путем распознавания характерные особенности образа, представленного на входе массивом элементов (в частности, -массивом координат), и затем их идентифицировать. На основе такого распознавания экстремальных особенностей функции, заданной массивом координат на равномерной сетке, удастся организовать устойчивый процесс локализации её нулей и экстремумов, а затем выполнить их вычисление с повышенной точностью. Этот метод сохраняет работоспособность в случае плохой отделённостн нулей и экстремумов; процесс распознавания, локализации и вычисления допускает максимально параллельную форму. Организация данного процесса на основе сортировки отличает предложенный метод от известных численных СХе»к! в данной области.
Предложены устойчивые разноввдности методов приближенных парал-гльных вычислений из области анализа, линейной алгебры и решения обыкно-ягаых дифференциальных уравнений. К их числу относятся:
метод параллельного вычисления элементарных функций и их суперло-щий за время (9(1) при произвольно заданной границе погрешности прибли-ения; от аналогов метод отличается регулярностью и общим видом конструк-аи, повышенной точностью вычисления, применимостью к приближенному япению функциональных уравнений, а также к приближенному вычислению хшзводных высшего порядка и к машишюму численному интегрированию с лсокой точностью;
параллельное преобразование линейных итерационных методов решения ютем линейных алгебраических уравнений с экспоненциальным сокращением ісла итераций при максимальном распараллеливании каждой итерации; от іалогов метод отличается улучшенными ( с экспоненциальным сокращением іемеии) оценками временной сложности, общностью схемы, включающей ме-ід итерации, метод Зейделя, методы Ричардсона, метод обращения матрицы и >.; существенное отличие представляет вычислительная устойчивость предло-гнных итерационных параллельных схем;
предложен перенос этого же преобразования на разностные схемы прижженного решения систем линейных дифференциальных уравнений с постовой матрицей коэффициентов и построение на данной основе машинного меда анализа устойчивости в смысле Ляпунова решения таких уравнений; метод ) построению отличается от известных теоретических приемов анализа устой-[вости по Ляпунову; в частности, метод не использует вычисление или оценки рактеристических чисел матрицы, ко по виду входной матрицы с элементар-ш ее преобразованием организует вывод норм преобразованной матрицы в следовательности пошаговой схемы приближенного решения, - поведение следовательности норм адекватно соответствует асимптотическому поведе-10 разности между возмущенным и невозмущенным решениями;
-предложены устойчивые параллельные разноввдности метода Леверье гчисления коэффициентов характеристического многочлена матрицы; в со-инении с параллельной схемой вычисления корней многочлена на основе ртировки получен устойчивый параллельный метод приближенного решения лной проблемы собственных значений; по сравнению с известными методами едложенный имеет равные оценки временной сложности, но отличается вы-слительной устойчивостью, достигаемой на основе отличной от существую-IX мультипликативной параллельной схемы решения треугольных систем ли-йньгх алгебраических уравнений.
Практическая цешгость. Даны последовательные программные варианты едложенных параллельных алгоритмов, в такой форме они использованы в je законченных хоздоговорных и бюджетных работ, выполнявшихся в НИИ ЗС, НКБ "Миус", ИК АН УССР им.В.М.Глушкова, а также в некоторых дру-< предприятиях и организациях. Эти же результаты и, помимо того, предло-
женные архитектуры параллельных ВС, сортирующие и коммутационные сети, а также методы и схемы устройств вертикальной обработки потока групповых данных использовались в договорных работах организаций из числа названных, и в учебном процессе ВУЗов. В учебном процессе ТГПИ используются предложенные прямые и итерационные методы линейной алгебры, а также алгоритмы адресных сортировок.
Анробздая работы. Работа апробирована на рабочих и постоянно действующих семинарах ТРТУ, ТГПИ, РГУ, НКБ "Миус", НИИ МВС, Института кибернетики им. В.М.Глушкова НАН Украины, ВЦ и ИМ СО АН СССР, на региональных семинарах и меясвузовских конференциях ТРТУ и НКБ "Миус", на всесоюзном семинаре "Параллельные машины и параллельная математика" в г. Киеве в 1978 г., на всесоюзной школе-семинаре "Автоматизация проектирования средств вычислительной техники и перспективы применения микропроцессоров" в г.Минске в 1978 г., на всесоюзных школах-семинарах "Распараллеливание обработки информации" в г.Верховине в 1983 г., в г.Косове в 1985 г., на "Шестом республиканском семинаре по однородным вычислительным средам и систолическим структурам" в г.Львове в 1987 г., на Втором всесоюзном совещании "Конвейерные вычислительные системы" в г.Киеве в 1988 г., на международной конференции молодых ученых "Проблемы проектирования и применения дискретных систем в управлении" в г.Минске в 1977 г., на международной конференции "Математические модели физических процессов и их свойства" в г.Таганроге в 1997 г., на международной конференции "Математика в индустрии" в г.Таганроге в 1998 г.
Публикации. По теме диссертации опубликовано около 90 научных работ, общим объемом я 95 п.л., основные из них вышли в журналах "Известия СКНЦВШ", "Многопроцессорные структуры", "УС и М", "АВ и Т" (3 публикации), "Кибернетика" (3 публикации), "Кибернетика и системный анализ " (5 публикаций объемом к 11.5 п.л.), в трудах международной конференции "Математика в индустрии" (2 публикации), а также в авторской монографии "Параллельная соргировка слиянием. Приложение к вычислению нулей, экстремумов функций и распознаванию образов" объемом » 12 п.л.. Имеется 6 авторских свидетельств по теме работы.
Структура работы. Диссертация состоит из введения, 3 глав, заключения и приложения, также включающего 3 главы; содержит 352 страницы основного текста, 194 страницы приложения, 32 рисунка в основной части и 1 рисунок приложения, 14 таблиц приложения, списка литературы из 297 названий основной части, 112 названий приложения.
