Введение к работе
Актуальность тени. Репение систем линейных алгебраичес-. них.уравнений (СЛАУ), особенно СЛАУ с патрицами большой размерности , принадлежит к тому кругу задач , которые , с одной стороны , являются чрезвычайно важными как в области научных вычислений , так и при реиении значительного числа практических задач . а с другой стороны, имеют очень высокую операционную сложность (порядка N ? операций с плавающей запятой , где N - размерность матрицы СЛАУ), При этом целый ряд прикладных задач , в частности задачи акустики , гидро-и радиолокации , аэродинамики . автоматического управления и регулирования . іїдлагают жесткие ограничения на допустимое время вычислений . требуя их выполнения в режиме "реального времени". Кроме того, существует большое количество науч- . но-практических задач, которые не требуют вычислений в режиме "реального времени", но объем, вычислений для их решения ' настолько велик , что требует от вычислительной'системы необычайно высокой производительности.. К числу таких задач, например , можно отнести задачи численного моделирования физических процессов , в основе которого лежит решение дифференциальных уравнений и систем уравнений большого порядка , своди! '.ых к решению СЛАУ.
В сзязи с этим , задача разработки вычислительных систем и алгоритмов для решения СЛАУ-является одним из наиболее привлекательных и практически значимых направлений научных исследований как е нашей стране , так и за рубежом.
В целом , названные выше задачи требуют от вычислительной системы производитель :ости порядка 10 " - 10 :4 операций с плавающей запятой в секунду (FLOPS). Традиционные универ-. сальные ЭВМ. основанные на архитектуре Д. фон Неймана . не могут на имеющемся в настоящее время уровне техники и технологии обеспечить подобную производительность. В связи с этим, в последнее время были предложены вычислительные системы с матричной архитектурой . выполненные, как правило, на основе универсальных сверхбольших интегральных схем (СБИС). Матричная архитектура предполагает частичный переход от программирования вычисления во времени , что характерно для традиционных универсальных ЭВМ, к программированию в пространстве, когда части решаемой задачи распределяются по отдельным СБИС
процессорных элементов (ПЭ) . образующим матрицу ПЭ (процессорную сеть) и в ходе обработки передаются от одного ПЗ і. другому. При этом задача решается в процессе "прокачивания"
ее через такую сеть. Этот подход позволяет разработать сис
темы , обладающие высокой производительностью при сравни
тельно невысокой стоимости.
Однако . универсальный характер вычислений , выполняемых подобными системами . является серьезным препятствием для дальнейшего увеличения их производительности. Это связано с
тем , что рост числа процессоров в. системе присадит к значи
тельному усложнению управляющих функций и функций обмена
данными таких ЭВМ , связанных с необходимостью распределения
по процессорам вычислительных задач различного характера. В
конечном итоге это приводит к значительному снижению реаль
ной производительности подобных ЭВМ, и . как следствие, к
неоправданным расходам. Другим серьезным препятствием для
увеличения производительности является проектирование уни
версальных ПЭ на основе фоннеймановской архитектуры. Это
приводит к невозможности использования всех достоинств мат
ричной архитектуры на уровне отдельных операций , так как
все операции , закрепление за данным ПЭ , выполняются после
довательно во времени.
С другой стороны , существует ряд прикладных задач , к примеру, в области цифровой обработки сигналов (ЦОС) . которые требуют решения одной и той же задачи с максимально возможной скоростью. При этом использование передовых методов обработки информации часто ограничивается.отсутствием в настоящее время недорогих малогабаритных вычислительных систем . обладающих требуемой производительностью.
Одним из путей решения этой проблемы является использование в вычислительных системах с матричной архитектурой специализированных СБИС , . ориентированных на решение одной задачи , в частности на решение СЛАУ. Это позволит крайне упростить устройство управления такой системой , обеспечить построение ПЭ на основе матричной архитектуры . то есть использования распараллеливания и конвейеризации вычислитель-. ного процесса на уровне отдельных операций ,- и за счет этого резко увеличить реальное значение производительности. При этом внутренняя структура специализированных СБИС однозначно определяется используемым вычислительным алгоритмом.
Однако, специфические ограничения , накладываемые техно
логией производства СБИС и связанные с ограниченной степенью
интеграции , конечным временем переключения транзисторов ,
ограниченным количеством выводов кристалла , сложностью меж
соединений и рядом других факторов . выдвигают специфические
требования к вычислительным алгоритмам, 'ориентированным на
аппаратурную реализацию , связанные с ограничением набора
операций и их типа для наиболее эффективной реализации таких
алгоритмов на СБИС. Вычислительные алгоритмы решения СЛАУ по
классическим методам , разработанные для универсальных ЭВМ ,
в абсолютном большинстве не удовлетворяют названным выше
требованиям. В связи с этим актуальной проблемой является
разработка аппарату, но-ориентированных алгоритмов для' их ре
ализации на СБИС. . '
Целью диссертации является создание и исследование класса ' аппаратурно-ориентированных алгоритмов решения СЛАУ на основе известных математических методов , полностью удовлетворяющих требованиям технологии производства СБИС и позволяющих в несколько раз уменьшить время решения СЛАУ и снизить аппаратурные затраты по сравнению с аппаратурной реализацией соответствующих классических вычислительных алгоритмов.
Достижение поставленной цели требует решения следую:." основных задач теоретического и прикладного характера;
-
Анализ возможностей аппаратурной реализации в виде СБИС классических вычислительныхалгоритмов решения СЛАУ по методам Гаусса , Гаусса-Жордана и Гивенса.
-
Разработка класса аппаратурно-ориентированных алгоритмов решения СЛАУ и обращения матриц на основе соответствующих классических мате' этических методов.
-
Исследование и сравнительный- анализ основных характеристик разработанных алгоритмов и соответствующих классических алгоритмов при их аппаратурной реализации в виде СБИС.
Методы исследования. В работе использовались методы математического моделирования , теория вычислительных систем , методы вычислительной математики , методы построения векторных и. параллельных вычислительных систем и алгоритмов для них , итерационные методы вычислений , теория графов.
Научная новизна работы. В диссертации разработаны и вынесены на защиту следующие основные положения:
аппаратурно-ориентированные алгоритмы выполнения триан-
'гуляции матрица {прямого хода pczemy. СЛАУ) по методам Гаусса. Гаусса-Ксрдана для вещественных и комплексных матриц;
аппаратурно-ориентированные алгоритмы реиения СЛАУ с треугольной матрицей (обратного хода решения СЛАУ);
аппаратурно-ориентированные алгоритмы обращения вещественных и комплексных матриц по истодам Гаусса и Гаусса-ЗХор-~ дана;
аппаратурно-ориентированный алгоритм решения СЛАУ.по ме
тоду Гивонса;
методика сравнения основных количественных «v качественных характеристик аппаратфно-ориентированных алгоритмов решения СЛАУ.
Практ^ч^скад_цснность. Разработаны алгоритмы решения СЛАУ с вещественной и комплексной матрицей и алгоритмы обращения вещественных и комплексных матриц , ориентированные на аппаратурную реализацию на специализированых СБИС , предназначенных для использования в системах с матричной архитектурой. Использование разработанных алгоритмов позволит'существенно (в 1.5-3 раза) снизить время решения СЛАУ и одновременно во столько же раз уменьшить необходимые, аппаратурные затраты при их реализации на СБИС по сравнению с аппаратурной реализацией классических вычислительных алгоритмов при прочих равных условиях и более чем на порядок уменьшить время решения названных задач по сравнению с их решением на универс? 'ьных ЭВМ при сопсстазишх аппаратурных затратах.
Реализация результатов работы. Результаты работы были внедрены в ОКР по созданию платы-акселератора ПЭВМ IBM PC AT по заказу АООТ "Волгограднефтегеофизика".
Кроме того , результаты диссертации были также использованы при проведении госбюджетной научно-исследовательской работы "Разработка и исследование алгоритмов для реализации в виде СБИС процесса решения задач линейной алгебры" , проводимой в ВолгГТУ (Волгоград) под руководством д.т. н.. профессора Духнича Е. И. :
Апробация работы. Результаты диссертации докладывались и обсуждались на I межвузовской научно-практической конференции студентов и молодых ученых Волгоградской области (Волгоград , 1994) . Волаской Городской научно-практической конференции (Волжский , 1995) . а также на ежегодных научных конференциях ВолгГТУ (Волгоград . 1993- 1995).
Публикации. По материалам диссертации опубликовано 6 печатных работ и получено решение о выдаче патента РФ на изобретение.
Структура и объем работы. Диссертация состоит из введения , четырех разделов . заключения , списка использованных источников , содержащего 63 наименования', и приложения. Работа изложена на 148 страницах основного текста . 56 страницах . рисунков и таблиц ,. 5 страницах списка использованных источников , 8,страницах приложения.
