Введение к работе
Актуальность темы. Организация высокопараллельных вычислений на системах с массовым параллелизмом является в настоящее время предметом интенсивных научных исследований и инженерных экспериментов. Интерес к этой области диктуется прежде всего возможностью теоретически неограниченного увеличения быстродействия при решении многих практически важных задач за счет глубокого распараллеливания процессов вычислений. Рост сложности решения таких задач, связанный, как правило, с увеличением размерности входных данных, приводит к соответствующему увеличению степени возможного распараллеливания и, как следствие, к потенциальному увеличению быстродействия алгоритмов.
Существенный вклад по разработке теоретических и практических основ параллельной обработки внесли Б.А. Бабаян, В.В. Воеводин, В.М. Глушков, Э.В. Евреинов, В.П. Ильин, А.В. Каляев, Ю.Г. Косарев, Л.Н. Королев, В.Е. Котов, В.П. Кутепов, В.К. Левин, А.А. Летичсвский, В.А. Мельников, Н.Н. Миренков, P.M. Нуриев, Д.А. Поспелов, В.И. Прангишвилп, И.Д. Софронов, В.Г. Хорошевский и их школы.
Успехи в области сверхвысокой интеграции сделали практически осуществимым и экономически выгодным построение на базе сверхбольших интегральных схем (СБИС) проблемно-ориентированных вычислительных структур для непосредственного решения сложных задач, содержащих очень большое число процессорных элементов. Вместе с тем, интегральная технология предъявила ряд жестких технологических и схемотехнических требований, которые должны быть учтены при разработке эффективных СБИС-алгоритмов. Наряду с параллелизмом обработки первостепенное значение для СБИС приобретают такие свойства как локальность обмена данными, высокая однородность и регулярность вычислений и эффективность использования площади кристалла СБИС. Разработка высокопараллельных алгоритмов, удовлетворяющих требованиям интегральной технологии, является по существу проектированием проблемных СБИС-ориентированных вычислительных структур. При этом конкретизируются и получают новое содержание такие общезначимые подходы при построении высокоэффективных программных средств как нисходящее проектирование, модульность, структурированность, оптимизация, обмен сообщениями и т.д. Беспрецедентная сложность разработки устройств на базе СБИС делают очень критичным и решающим первоначальный этап архитектурного (поведенческого) проектирования СБИС-устройства, т.е. этапа распараллеливания алгоритма и его последующего отображения в СБИС-ориентированное пространство вычислений. Трудность здесь заключается не только в выявлении
из алгоритма подходящей для СБИС параллельной формы, но и в получении для заданного алгоритма соответствующей архитектуры, выбранной из множества альтернативных решений. Комплексное исследование этих проблем становится возможным только в рамках систематической методики проектирования, основанной на формальных преобразованиях исходного алгоритма в соответствии с требованиями и ограничениями СБИС-технологии. Таким образом, СБИС являются новой технологической средой, которая требует новых идей в организации параллельной обработки, теории вычислений, методах проектирования ЭВМ и других смежных областях.
Большой теоретический и практический вклад в становление теории и практики массовых параллельных вычислений для СБИС внесли О.Л. Бандман, В.А. Вальковский, Ю.Г. Дадаев, Ю.С. Каневский, В.В. Корнеев, Г.А. Кухарев, П.И. Соболевский, В.И. Шмерко, Я.И. Фет, М. Cosnard, S.Y. Kung, Н.Т. Kung, С. Lengauer, D. Moldovan, P. Quinton, Y. Robert, R. Thompson и др.
Первоначально высокопараллельные вычислительные структуры для непосредственной реализации регулярных матричных алгоритмов в СБИС (названных систолическими процессорными матрицами), проектировались на интуитивной основе и без связи друг с другом. Систолические структуры — это одно- или двумерные матрицы регулярно и локально связанных процессорных элементов (ПЭ) одного или нескольких типов, которые под управлением общих часов ритмически (синхронно) обрабатывают взаимодействующие потоки исходных данных задачи, поступающие на периферийные ПЭ структуры, образуя соответствующие потоки результирующих данных. К настоящему времени существуют несколько десятков методик, которые в той или иной мере систематически решают задачу проектирования процессорных матриц для СБИС-реализации матричных алгоритмов. Однако, существующие методики проектирования обладают рядом недостатков, которые затрудняют или делают невозможным их практическое использование при комплексной разработке и анализе систолических структур.
Другой важной проблемой при организации СБИС-ориентированных вычислений является задача отображения существенно нерегулярных численных алгоритмов на регулярные сети ПЭ. Большой опыт распараллеливания существующих последовательных алгоритмов показал, что многие численные методы, практически используемые при решении различных задач, часто характеризуются рядом алгоритмических особенностей, существенным образом снижающих уровень эффективного параллелизма и делающих невозможным применение формальных методов синтеза систолических процессорных матриц. В связи с этим возникает проблема распараллеливания таких алгоритмов до
ровня, нивелирующего затраты на возможно последовательное выполнение сдельных нерегулярных фракций исходного множества вычислений. В то же ремя при распараллеливании желательно сохранение крайне важного для СБИС войства систолической обработки — локальности и регулярности взаимо-ействия одновременных процессов.
В этом контексте представляется весьма актуальным рассмотрение и сследование организации параллельных вычислений на системе, представляючи систолическое кольцо компьютеров. Предполагается, что систолическое ольцо перепрограммируемых компьютеров позволит осуществить аффективную еализацию большого класса как регулярных, так и нерегулярных численных лгоритмов.
Целью работы является разработка теоретических основ, новых методов, ринципов организации и анализа высокопараллельных алгоритмов и структур для ешемия базовых задач линейной алгебры, цифровой обработки сигналов, теории эафов, ориентированных на современную и перспективную технологию ычислений.
Для достижения поставленной цели решаются следующие задачи:
теоретическое обоснование принципов и создание формализованной методики синтеза и анализа высокопараллельных алгоритмов и структур с локальными взаимодействиями и их отображения на интегральную технологию;
разработка на базе систематической методики системы автоматизированного компьютерного проектирования, анализа и поведенческого моделирования систолических алгоритмов и соответствующих им вычислительных структур;
формализованное проектирование и сложностной анализ систолических алгоритмов и структур для решения базовых алгоритмов линейной алгебры, цифровой обработки сигналов и теории графов;
теоретическое исследование организации систолических вычислений на перепрограммируемом кольце компьютеров, характеризующемся предельно простой топологией связи и высокой модульностью (масштабируемостью) структуры.
Методы исследований. Совокупность использованных в диссертационной іботе средств исследований основывается на методах линейной алгебры, іфровой обработки сигналов, теории графов, теории множеств, аналитической ометрии, теории алгоритмов и методах машинной графики. Методом :спериментальной проверки основных результатов и положений работы являет-моделирование на ЭВМ в рамках разработанной системы автоматизированно-
го проектирования большого множества систолических алгоритмов и структур. Научная новизна работы заключается в теоретическом развитии, обобщении математических и методологических принципов проектирования и анализа высокопараллельных алгоритмов и структур, ориентированных на СБИС-реализацию.
-
Расширены и конкретизированы современные представления о способах и формах разработки высокопараллельных программ и соответствующих систолических структур.
-
Разработана и теоретически обоснована систематическая методика синтеза, анализа и моделирования систолических алгоритмов и структур, суть которой заключается в формализованном переходе от математической записи матричного алгоритма к допустимому множеству корректных по построению высокопараллельных СБИС-ориентированных структур с локальными взаимодействиями, различающихся пространственно-временными характеристиками.
-
Сформулированы и теоретически доказаны условия эффективной конвейеризации (локализации) множества глобально зависимых вычислений матричных алгоритмов, исходно заданных линейными рекуррентными соотношениями.
-
Впервые введено и теоретически обосновано допустимое для СБИС-реализации пространство возможных проектных решений, позволяющее для заданного матричного алгоритма найти среди различных альтернативных проектов оптимальную (в смысле минимизации критерия "пространство-время") систолическую структуру.
-
Установлена формальная связь между предложенными ранее на эвристической основе различными систолическими алгоритмами и структурами, а также получены новые оригинальные решения.
-
Теоретически исследована для многих численных алгоритмов организация параллельно-поточных вычислений на перепрограммируемом кольце компьютеров, эффективная для осуществления как регулярной, так и нерегулярной матричной обработки.
Практическая ценность работы. Совокупность полученных в диссертационной работе научных результатов и положений расширяет и углубляет теоретические основы методов и принципов построения эффективных параллельных алюритмов и вычислительных средств с массовым параллелизмом.
Разработанные методика и графово-матричный аппарат формализованного синтеза положен в основу компьютерной системы автоматизированного проектирования, анализа и моделирования высокопараллельных алгоритмов и проблемно-ориентированных процессорных матриц систолической архитектуры.
На основе предложенной методики, разработанной и построенной системы автоматизированного проектирования синтезированы и комплексно исследованы оптимальные для СБИС-реализации параллельно-конвейерные алгоритмы и соответствующие систолические процессорные матрицы, непосредственно ориентированные на решение базовых алгоритмов линейной алгебры, цифровой обработки сигналов и теории графов. Основные структурные решения защищены авторскими свидетельствами на изобретения.
Разработанные методика и система проектирования, анализа и моделирования систолических алгоритмов и структур может быть эффективно использована при разработке параллельных и векторно-конвейерных программ для существующих и перспективных многопроцессорных систем SIMD- и MIMD-архитектуры за счет существенного снижения трудоемкости анализа зависимости частично упорядоченного множества вычислений алгоритма и автоматической генерации различных параллельных версий программ в виде наборов последовательности одновременных операций.
Практическая ценность работы заключается также в использовании основных теоретических положений и результатов, а также системы компьютерного проектирования, в учебных курсах ряда ВУЗ'ов при подготовке специалистов по прикладной математике, вычислительной технике, автоматизированным системам управления. Акты об использовании результатов приведены в Приложении 2.
Разработанные и исследованные параллельно-конвейерные версии численных алгоритмов, эффективно реализуемые на перепрограммируемом кольце компьютеров, могут быть непосредственно использованы при построении математического обеспечения для вычислительных систем с массовым параллелизмом, построенных, например, на базе транспьютероподобных элементов.
Апробация работы. Результаты работы были представлены и докладывались на Международной конференции по параллельной обработке CONPAR-S8 (Манчестер, 1988), Международной конференции по векторной и параллельной обработке CONPAR 90 — VAAP IV (Цюрих, 1990), V-м Международном симпозиуме по параллельной обработке на клеточных автоматах и массивах PARCELLA-90 (Берлин, 1990), Международной конференции "Технологии параллельных вычислений" РаСТ-91 (Новосибирск, 1991), Международной конференции "Обработка сигналов" LSPIC-90 (Рига, 1990), Всесоюзной конференции "Формальные модели параллельных вычислений" (Новосибирск, 1987), Всесоюзной школе "Отображение проблем вычислительной математики на архитектуру вычислительных систем" (Звенигород, 1983), Всесоюзной
конференции "Транспьютерные системы и их применение" (Звенигород, 1991) Всесоюзной конференции "Методы и микроэлектронные средства цифровоп преобразования и обработки сигналов" (Рига, 1989), 1-й Всесоюзної конференции "Однородные вычислительные среды и систолические структуры (Львов, 1990), Всесоюзном совещании "Конвейерные вычислительные системы (Киев, 1988), Всесоюзном семинаре "Параллельные машины и параллельна; математика" (Киев, 1977), VI-й и VII-й Всесоюзных школах-семинара: "Распараллеливание обработки информации" (Львов, 1987, 1989), 1-м Всесоюз ком семинаре "Логические методы построения однородных и систолически: структур" (Москва, 1988), Всесоюзном научно-техническом семинарі "Программное обеспечение многопроцессорных систем" (Калинин, 1988) Vlll-м Всесоюзном семинаре "Параллельное программирование і высокопроизводительные структуры" (Киев, 1988), Межотраслевок научно-технический семинаре "Системы, средства и алгоритмы первично! обработки информации" (Ленинград, 1989), семинарах ВЦ СО РАН, ИМ СО РАН ИТиПМ СО РАН, ИТК САН (Братислава, Чехо-Словакия), КЦИИТ БАН (София Болгария), Институте Вычислительных Технологий АН КНР (Шеньян, Китай) Университете г. Турку (Финляндия), Лаборатории Информационного Параллелизма при Высшей исследовательской школе г. Лион (Франция) в 1977 — 199І гг. Результаты диссертации включались в годовые отчеты Вычислительной центра СО РАН, Сибирского отделения РАН и Отделения "Вычислительной техники и информатики" РАН. В 1991 году коллективная работа, в которую был? включены основные результаты диссертации, заняли призовое место на конкурсе прикладных работ Сибирского отделения РАН.
Публикации. По результатам выполненных исследований опубликовано 62 научные работы, включая две коллективные монографии, 40 статей, тєзисое докладов и 20 авторских свидетельств на изобретения.
Структура работы. Диссертация состоит из введения, пяти глав, заключения, списка литературы (254 наименования) и трех приложений. Работа изложена на 296 страницах машинописного текста, иллюстрированных 9.5 рисунками и 19 таблицами. Приложения насчитывают 54 страницы.
Исследования проводились в соответствии с планами Вычислительного центра СО РАН по государственным научно-техническим программам: "Информатизация России" ШИП 3.58.2), "Разработка программно-технического комплекса для обработки геофизической информации" (шифр "Сибирь"), "Высокопроизводительные информационно-вычислительные системы для нового поколения центров математического моделирования" (НИП 111), программе Сибирского отделения РАН "Новые поколения вычислительной техники,
математическое моделирование и информационные технологии (п. 1.2.3. "Разработка систем автоматизации проектирования спецпроцессоров").
