Содержание к диссертации
ВВЕДЕНИЕ 4
ГЛАВА I. МЕТОДЫ И СРЕДСТВА РЕШЕНИЯ ТИПОВЫХ
ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕДУР В СПЕЦИАЛИЗИРОВАННЫХ МИКРОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ ... 12
1.1. Алгоритмы решения типовых
вычислительных процедур 12
Итерационный метод "цифра за цифрой"... 13
Методы расчета математического ожидания и перевода информации из одной системы счисления в другую 16
1.2. Микропроцессорные средства решения ТВП 19
1.2.1. Характеристики МПС, тенденции
развития 19
Использование матричных вычислительных устройств в МПС 22
Программно-аппаратная реализация
типовых вычислительных процедур ....... 23
1.2.4. Математическое обеспечение
микропроцессорных систем 27
Выводы по главе I 30
ГЛАВА 2. АНАЛИЗ И ВЫБОР МЕТОДОВ И АЛГОРИТМОВ РЕШЕНИЯ
ТИПОВЫХ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕДУР 31
Расчет математического ожидания 32
Вычисление полиномов и нахождение их корней методом "цифра за цифрой" 40
Процедура расчета преобразования координат ... 54
Вычисление составных функций, скалярного
и векторного произведений 64
2.5. Перевод информации из одной системы
счисления в другую 69
Выводы по главе 2 73
ГЛАВА 3. СТРУКТУРНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМОВ 74
ЗЛ. Процедура получения оценок времени реализации
алгоритмов на МПК 74
3.2. Организация микропроцессорных систем
с использованием функциональных
расширителей 84
3.3. Разработка функциональных расширителей,
реализующих типовые вычислительные
процедуры 89
3.3.1. Устройства, реализующие задачи
преобразования координат и работающие
по методу "цифра за цифрой" 91
3.3.2. Аппаратная реализация алгоритмов
расчета значения полинома и
нахождения его корней ................ 93
3.3.3. Конвейерное устройство для вычисления
составных функций sin (arctg У/х)
и cos (arctg у/х) 99
3.3.4. Устройство для преобразования данных
из двоичной системы счисления
в двоично-десятичную 102
3.3.5. Аппаратная реализация алгоритма
расчета математического ожидания 105
Выводы по главе 3 108
ЗА КЛЮЧ ЕНИ Е 109
СПИСОК ЛИТЕРАТУРЫ III
ПРИЛОЖЕНИЕ I о 126
ПРИЛОЖЕНИЕ 2 151
Введение к работе
В решениях ХХУІ съезда КПСС определено: "Опережающими темпами развивать производство управляющих и вычислительных комплексов, периферийного оборудования и программных средств к ним, систем комплексной автоматизации технологических процессов". Решениями предусмотрено также значительное расширение производства миниатюрных электронных управляющих машин, как составной части основного технологического оборудования, приборов, различных систем и средств управления и контроля"ClJ.
Успешное выполнение этих задач связано с совершенствованием технологической базы, развитием новых научно-технических принципов построения средств ВТ и широким их внедрением в наиболее важные отрасли народного хозяйства.
За последние годы особенно интенсивно расширяется сфера применения микропроцессорных систем (МПС) - вычислительных и управляющих систем различного назначения, реализуемых на основе микропроцессорных комплектов (МПК) БИС. К 1975 году было известно 2000 применений МПС, в 1983 году их насчитывалось уже 350000.
Основными областями применения МПК БИС являются Г 2]:
управление производством (18 %);
информационно-измерительная техника (16 %);
авиация и космические системы (15 %);
системы связи (14- %);
вычислительная техника (13 %);
военная техника (9 %);
другие области (15 %).
5 В перечисленных областях применения МПК БИС решаются самые разнообразные задачи. Тем не менее в каждой из них можно выделить наиболее часто встречающиеся вычислительные процедуры, реализуемые программным или аппаратным способами. К специализированным МПС, как правило, предъявляются жесткие требования во времени решения задач. Поэтому от совершенствования методов и средств реализации типовых вычислительных процедур (ТВП) можно ожидать значительного повышения эффективности функционирования МПС. К числу часто встречающихся ТВП в перечисленных областях применения МПК относятся:
расчет математического ожидания;
вычисление векторного и скалярного произведений;
расчет значений составных функций sin (aictg ?/х), cos(aictq #/х), xty'i>
преобразования координат;
вычисление полиномов и нахождение их корней;
- преобразование данных из одной системы счисления в дру
гую.
Очевидно, что в МПС реализуются и многие другие ТВП. Поэтому, не претендуя на общность решения поставленной задачи в смысле полноты охвата ТВП для МПС, на примере перечисленных ТВП, выявляются все основные аспекты их реализации, К ним относятся: выбор алгоритмов и структур, получение их оценок, методика проектирования и ряд других вопросов, инвариантных к конкретным приложениям.
Выбор анализируемых процедур и их общность обусловлены следующими факторами:
- перечисленные ТВП не только сами по себе достаточно рас
пространены, но и являются базовыми для решения более слож-
ных задач и процедур, таких как БПФ, цифровая фильтрация, расчет эквидистанты и формообразования в системах ЧПУ станками и роботами, распознавание образов, организация систем ввода-вывода для специализированных МПС и др.;
общность указанных ТВП состоит в том, что для них удалось разработать алгоритмы, эффективно реализуемые как аппаратными, так и микропрограммными средствами, причем для большинства ТВП данные алгоритмы основаны на методе "цифра за цифрой";
большинство МПС, в которых используются рассматриваемые ТВП, работают в реальном масштабе времени (РМВ) в темпе поступления данных.
Термин РМВ в современной системотехнике общепринят, распространен и имеет большое число самых разных определений и трактовок. Связано это с тем, что требуемое время решения задач в СРВ в зависимости от их назначения может лежать в диапазонах,измеряемых наносекундами, миллисекундами, минутами, часами и т.д.
Анализ областей применения исследуемых ТВП и требования к специализированным МПС позволяют сделать вывод, что задача повышения быстродействия в них является основной. Например, для управления шестикоординатным роботом цикл преобразований составляет 100 мкс (основные вычислительные процедуры: интерполяция, расчет эквидистанты, преобразование координат)Г3J. Для решения задач первичной и вторичной обработки в системах навигации (цифровая фильтрация, преобразование координат, вычисление элементарных и составных функций) цикл обработки может составлять единицы миллисекунд С 4,57. При этом получе-
ниє требуемых временных характеристик должно достигаться минимальной ценой (затраты оборудования, технологичность, вес, габариты, надежность, стоимость и т.д.).
Существующие МПК и МПС на их основе без разработки новых методов, алгоритмов и дополнительных аппаратурных средств (функциональных расширителей) в большинстве случаев не удовлетворяют требованиям реализации ТВП для практических систем в рассматриваемых областях применения. Причинами этого являются:
малая производительность МПС ввиду ограниченности системы команд, разрядности, аппаратурных средств и т.д.;
отсутствие развитого системного и прикладного математического обеспечения, так как теоретические и практические разработки в этом направлении для универсальных ЭВМ, накопленные многолетним опытом, не могут без коренной переработки применяться в МПС.
В литературе практически отсутствуют сведения по методам, алгоритмам и дополнительным аппаратурным средствам реализации рассматриваемых ТВП на МПС. Большинство из известных работ Г 5-20J посвящено программной реажзации методов и алгоритмов решения ТВП на универсальных ЭВМ и их аппаратной реализации с использованием устаревшей элементной базы. Отсутствуют также работы, содержащие требования и характеристики, предъявляемые к микропроцессорной реализации рассмотренных в работе ТВП. Слабо разработаны вопросы выбора структур специализированных МПС для исследуемых ТВП. Известные в литературе методики получения временных оценок реализации алгоритмов в МПС для выбора МПК и проектирования МПС очень сложны, громоздки, требуют больших временных затрат и не учитывают особенностей
рассматриваемых алгоритмов Г2,21-29J.
Приведенные выше доводы позволяют считать актуальными теоретические и практические задачи, решаемые в диссертации.
Целью работы является исследование возможностей сокращения времени реализации некоторых типовых вычислительных процедур в специализированных МПС на основе новых методов, алгоритмов и структур. Для достижения поставленной цели в диссертации рассматриваются и решаются следующие основные задачи:
Анализ характеристик известных алгоритмов и микропроцессорных средств, применяемых в МПС при решении рассматриваемых в диссертации ТВП по критериям времени и аппаратурным затратам.
Улучшение известных и разработка новых методов и алгоритмов микропрограммной и аппаратной реализации ТВП.
Разработка программ выполнения ТВП и количественная оценка времени их реализации на некоторых универсальных микро-ЭВМ и специализированных МПС.
Автоматизированная процедура получения приближенных временных оценок реализации алгоритмов, содержащих ТВП, на различных МПК.
Разработка быстродействующих функциональных расширителей (спецпроцессоров) для воспроизведения ТВП.
Предмет исследования: алгоритмы решения, а также микропрограммная и аппаратная реализация рассматриваемого класса ТВП в МПС.
Метод исследования базируется на применении аппарата численного анализа, теории приближения и интерполяции функций, математической статистике и методе вычислений "цифра за цифрой". Достоверность полученных результатов подтверждается
9 корректностью использования математического аппарата, а также моделированием на универсальных ЭВМ и экспериментами на МПК БИС К580, К589, KI804.
Новые научные результаты, В процессе решения поставленных задач получены следующие основные результаты:
Проведен анализ характеристик известных алгоритмов и микропроцессорных средств, на основе которого предложены методы и алгоритмы реализации типовых вычислительных процедур, отличающиеся от известных более высоким быстродействием и расширяющие прикладное математическое обеспечение микропроцессорных систем.
Разработана процедура получения оценки времени реализации алгоритмов, содержащих ТВП, учитывающая их особенности.
Получены количественные оценки времени выполнения типовых вычислительных процедур и затрат памяти хранения программ для некоторых универсальных микро-ЭВМ и специализированных микропроцессорных систем.
Исследованы и предложены структуры быстродействующих функциональных расширителей (спецпроцессоров ТВП) для микропроцессорных систем, в которых микропрограммная реализация не удовлетворяет критерию времени.
Практическая ценность. Проведено моделирование предложенных алгоритмов на ЭВМ EC-I060 и СМ-4, на основе которого разработаны программы, написанные на языке АССЕМБЛЕР в системе команд МПК К580, системе!... _>команд KI804- и системе микрокоманд К589, которые могут быть использованы в качестве прикладного математического обеспечения микропроцессорных систем.
Разработан и отлажен пакет прикладных программ получения
10 приближенных оценок времени выполнения алгоритмов, содержащих рассматриваемые и другие, предлагаемые разработчиком ТВП на различных МПК.
Проведенные в работе теоретические исследования послужили основой для создания прикладного математического обеспечения ряда устройств и приборов на МПК БИС.
Реализация и внедрение результатов работы. Практические результаты использованы в научно-исследовательских работах кафедры ВТ Ленинградского электротехнического института им. Ульянова (Ленина): "Разработка принципов построения устройств числового программного управления станками и роботами на основе микро-ЭВМ" и "Исследование и разработка встроенных микропроцессоров для радиотехнических измерительных приборов".
Алгоритмы и методы вычисления математического ожидания и преобразования систем счисления вошли в состав математического обеспечения анализатора ошибок, в приборе "Галактика", который внедрен в серийное производство. Экономический эффект от внедрения составил 138 тыс.рублей, что подтверждено соответствующим актом.
Апробация работы. Основные результаты работы докладывались и обсуждались на:
Ш Всесоюзном совещании-семинаре молодых ученых и специалистов "Совершенствование устройств и методов приема и передачи информации", Ростов-Ярославский, 1982 г.;
XI Всесоюзном совещании-семинаре "Современная элементная база ЭВМ и методы ее проектирования с помощью ЭВМ", Крымская область, 1983 г.;
ХІЇ Всесоюзном совещании-семинаре "Автоматизация проектирования микропроцессоров, микропроцессорных систем и СБИС',1 Крымская область, 1984 г.;
Всесоюзной конференции "Специализированные микропроцессорные системы", Челябинск, 1984 г.;
научно-технической конференции "Методы и средства повышения эффективности обработки информации в системах управления реального времени", Киев, 1982 г.;
научно-техническом семинаре "Микропроцессоры и их применение", Пенза, 1983 г.;
научно-технических конференциях профессорско-преподавательского состава ЛЭТИ им. В.И.Ульянова(Ленина), Ленинград, І98І-І983 гг.
Публикации. По материалам диссертационной работы опубликовано 10 печатных работ, получено авторское свидетельство и положительное решение на выдачу авторского свидетельства.
Структура и объем работы. Диссертационная работа состоит из введения, трех глав, заключения, списка использованной литературы и приложений.
