Stfw.RuИсходными данными для выбора типа и числа МП являются результаты анализа решаемого алгоритма и графовая модель программы, рассмотренная в § 3.2. Заданный алгоритм реализуется на элементной базе, которая может быть представлена, например, в виде табл. 3.4.
Таблица 3.4
При решении задачи на различных уровнях сложности под МП могут пониматься различные конструктивно-функциональные модули. Если речь идет о реализации МПУ на базе МПК, то в данном случае под МП понимаются БИС АУ, процессорные секции и т. п. Если определяется оптимальный состав микропроцессорной системы управления ЛА или сложным радиоэлектронным комплексом, то в качестве МП (используются либо отдельные микро-ЭВМ, либо функциональные модули типа рассмотренных в § 1.2. Для одних задач МП могут конструктивно представлять собой БГИС, для других - функциональную ячейку. Кроме МП, которые программно реализуют функции, в список элементной базы включены также модули, реализующие некоторые функции аппаратным или программно-аппаратным способом. Число типов таких модулей (как и МП) очень велико: БИС умножителей, сумматоров, арифметических расширителей (арифметика с плавающей запятой); модули, реализующие сложные операции, например МП БО БПФ (см. рис. 2.3), и др.
При задании исходной совокупности МП необходимо определить множество М процессорных модулей, некоторая комбинация которых (МосМ) является оптимальным вариантом построения обрабатывающей части МПУ. Для определения Мо надо исходить из особенностей конкретного применения МПУ в составе РЭУ: условия эксплуатации, энергетические ресурсы, конструктивная совместимость с РЭУ и др. Кроме того, необходимо учитывать следующие характеристики МП:
программные возможности: разрядность; набор команд; методы адресации; время выполнения команд; число РОН, доступных пользователю; наличие стека и его характеристики; максимальная адресуемая память;
аппаратные возможности: максимальная рабочая частота синхронизации, напряжение питания, возможность совмещения с другими логическими схемами, потребляемая мощность, сложность схемы МП, наличие в его составе вспомогательных элементов для расширения функциональных возможностей; возможность комплектация вспомогательными элементами, например, аппаратные умножители, интерфейсные схемы, арифметика с плавающей запятой и др.; размеры корпуса « число выводов, число портов ввода-вывода и др.;
системные характеристики: наличие прерываний, включая их уровень, число и систему приоритетов; ПДП; наличие программного обеспечения (редактор, отладчик, ассемблер, вспомогательное ПО для записи программ в ППЗУ, пакет тригонометрических функций, диагностические программы для МП и памяти) и т. п.;
наличие документации: описания МП, руководящего технического материала по применению, вспомогательной информации;
экономические возможности: стоимость МП, наличие опыта работы с данным МП, .наличие основного и резервного поставщика и т. п.
Совокупность заданных МП М представляет собой открытое множество, которое расширяется при появлении новых МП, отвечающих перечисленным выше требованиям. Каждый МП представляет собой строку таблицы, которая характеризуется рядом элементов (параметров МП). В табл. 3.4 приведен минимальный перечень параметров. При решении конкретных задач число рассматриваемых параметров может быть увеличено.
Важнейшей характеристикой МП является набор команд и время их выполнения. Микропроцессоры, входящие в М, имеют различные системы команд. Независимость модели программы от системы команд конкретных МП достигается выбором языка моделирования.
Проектирование специализированных МПУ, ориентированных на решение задач определенного класса, обычно требует разработки своего языка моделирования. Уровень разработки этого языка может быть различным и зависит от того, какие задачи ставятся разработчиком на данном этапе проектирования.
В общем случае в качестве языка моделирования могут быть использованы алгоритмические языки, ассемблеры, системы команд специализированных вычислительных устройств, решающих подобные задачи, и т. п. В простейшем случае язык моделирования может быть получен путем анализа алгоритмов обработки и систем команд исходных МП. Упрощенный вариант анализа может представлять собой такую последовательность действий:
1. Из исходного множества различных систем команд (МК) выбирается MKi=MK, наиболее соответствующая реализуемому алгоритму (наличие операций умножения, деления, ПДП и др.).
2. MKi дополняется операторами, наиболее часто встречающимися при реализации алгоритмов данного класса (тригонометрические преобразования, комплексное умножение и т. п.). Кроме того, МКг может дополняться операторами, реализуемыми ап-паратно.
3. Система команд каждого МП расширяется путем включения в ее состав подпрограмм реализации дополнительных операторов.
Сформированная, таким образом, система команд по типу выполняемых операций имеет аналоги в системе команд любого МП. Это делает графовую модель программы, представленную в такой системе команд, независимой от типа МП. Особенности систем команд конкретных МП учитываются значением аргумента вершины модели t{j, так как в одном случае это команда и значение ta меньше, в другом - подпрограмма и значение tij соответственно больше. В отличие от МП АЛ реализует одну или несколько операторов выбранного языка моделирования. Кроме набора команд каждый МП характеризуется конструктивными параметрами: разрядностью l, потребляемой мощностью Рп, габаритами, числом выводов. Перечень этих параметров может быть расширен.
Графовая модель программы с учетом принятых в § 3.2 гипотез представляет собой цепь Маркова. Поэтому среднее значение и дисперсия времени ее выполнения определяются следующим образом [46]:
где fi - среднее значение частоты повторения i-го шага программы при однократном проходе; gij - вероятность попадания в состояние Xj, если хi является начальным состоянием: ри - вероятность перехода из вершины Xi в Xj.
Итак, исходя из (3.4), задачу выбора числа и типа МП на I этапе конструкторского синтеза МПУ можно свести к определению группы МП Мо=М, обеспечивающих решение алгоритма при выполнении ограничений Tпр
При расчете погрешности вычислений МПУ исходят из гипотезы о независимости ошибок округления в цепочке последовательных элементарных операций [47]. Среднее квадратическое значение погрешности вычислений МПУ
(3.8)
где ат, стм, аи - средние квадратические значения трансформируемой, методической и инструментальной погрешностей соответственно.
Трансформируемые ошибки порождаются ошибками задания исходных величин. Эти ошибки в процессе выполнения арифметических операций изменяют свою величину (трансформируются). Значение ат можно определить из выражения
(3.9)
где F(xi, X2, ..., хп) - вид реализуемой функции; бi - среднее квадратическое значение погрешности аргумента Xi. Значение погрешности представления входных данных где бmi, аАЦП - средние квадратические значения погрешности i-го канала и погрешности квантования АЦП соответственно. По-следовательно двигаясь от вершины к вершине графа программы, в соответствии с (3.9) определяется ат для каждой вершины хге=Х.
Методические погрешности представляют собой погрешности численных методов, принятых для вычисления функции F(xu х2, ..., хп). Поскольку алгоритм обработки задан, то, следовательно, ам определено.
Инструментальные погрешности обусловлены конечным числом разрядов, предназначенных для представления операндов и необходимостью округления результатов некоторых элементарных арифметических операций. Результирующая инструментальная погрешность представляет сумму накопившихся ошибок при последовательных округлениях элементарных операций. Величина ее определяется реализуемым алгоритмом и разрядностью МП. Результирующее значение инструментальной погрешности
Проведя предварительные вычисления, алгоритм выбора типа и числа МП можно представить в виде следующей последовательности действий:
1. Определяется разрядность ячеек ОЗУ, предназначенных для хранения входного массива данных: lBX = ]log2 UМакс/бвх[, где UMSKC - амплитуда входного сигнала; бвх - средняя квадратиче-ская погрешность входного сигнала.
2. Определяется число Дl:
3. Определяется число разрядов, требуемое для компенсации инструментальной погрешности:
где ф - длина цепочки последовательных операций с округлениями.
4. Определяется разрядность МП, обеспечивающая при данной би погрешность представления результатов вычислений не выше бдоп.
Методика расчета разрядности МП, работающих в системах счисления с плавающей запятой, рассмотрена в [48].
5. Корректируется время выполнения операций, представлен-ных в табл. 3.3 с учетом разрядности МП l и времени распространения сигналов переноса.
6. С учетом элементарных преобразований графов, представленных на рис. 3.4, упрощается исходная модель программы.
7. Частота повторения начальной вершины f1 принимается равной 1. Последовательно двигаясь от вершины к вершине, определяются средние частоты их повторения:
(3.10)
где fi - средние частоты повторения предыдущей вершины; т - число дуг, входящих в вершину Xj.
8. На основании данных табл. 3.3 (ti) и результатов, полученных в предыдущем пункте, из выражения (3.6) определяется среднее время выполнения программы каждым МП, представленным в табл. 3.3.
9. С помощью выражения (3.7) определяется D(Tnp). Для упрощения программирования выражения (3.7) оно может быть представлено IB следующем виде [46]:
(3.11)
где ij={ti}j - вектор-столбец значений выполнения шагов программы j-м МП; ij - -{tjifi}; Q=||qij|| - матрица, элементы которой определяются следующим образом:
- вероятность попадания на r-м шаге выполнения программы в состояние Xj, если Xi является начальным со-стоянием.
Значения элементов матрицы Q определяются значениями матрицы вероятности переходов ||рц||.
10. Для определения верхней границы 7ПР необходимо знать закон распределения плотности вероятности значений ГПР. Если этот закон неизвестен, то можно использовать неравенство Чебы-шева, дающее оценку вероятности того, что абсолютное отклонение случайной величины от ее среднего значения |Tпр - Tпр| не превзойдет некоторого положительного числа a с вероятностью р:
11. Полученное значение 7щ, сравнивается с Т. Микропроцессоры, имеющие значение Тпр
3.5. Матрица данных
12. Для определения возможности повышения производительности МП необходимо оценить степень параллелизма решаемого алгоритма. Две операции могут выполняться одновременно (параллельно) разными МП, если их операнды определены. Подпрограммы с независимыми данными могут быть определены на основании анализа матрицы данных O = ||ojj||, причем
Матрица О имеет размерность пхп. Строки матрицы совпадают с вершинами графа G(X, U), а столбцы представляют собой вершины-последователи. Иными словами, элементы столбца указывают вершины, результаты операции которых являются операндами данной вершины.
На рис. 3.5 приведен пример матрицы данных. Из анализа матрицы видно, что вершины х2 и х3 определяются только результатом операции вершины х1, следовательно, они могут быть выполнены одновременно.
Построение «матрицы О осуществляется по данным табл. 3.3. Анализируются столбцы матрицы О. Определяются столбцы с совпадающими элементами. Эти столбцы представляют собой начальные вершины подпрограмм, которые могут выполняться одновременно. Подпрограмма включает только те вершины, ко-торые были определены на предыдущих шагах вычислений.
13. С помощью выражений (3.10) и (3.11) определяются Tпр ij, D(Tпpij), где i, j - номер подпрограммы и шип МП соответственно.
14. Сравниваются полученные значения Тпрц с Т. Если Тпр ij<.
16. Оценивается число последовательно включенных МП:
17. После анализа результатов, полученных в пп.15 и 16, определяется число МП данного типа, необходимое для реализации алгоритма в реальном времени. Эти данные заносятся в массив Мо-
18. Определяется возможность реализации подпрограмм ап-г паратными процессорами (АП). Изменяются веса соответствующих вершин и корректируется значение Тпр. Если Тпр<.Т, то соответствующие МП и АП фиксируются в массиве Мо-
19. Каждый элемент массива Мо представляет собой один из возможных структурных вариантов реализации исходного алгоритма А на заданном наборе МП (см. табл. 3.4) в рамках заданных ограничений (б<7ДОп, Т<Тпр). Лучшим из вариантов будет тот, который размещается на меньшей площади монтажной платы.
Таким образом, данный алгоритм позволяет определить массив Мо, который включает тип и число МП этого типа, обеспечивающее решение алгоритма А в реальном масштабе времени аппаратным или программно-аппаратным путем с использованием одно- или многопроцессорной структуры построения МПУ.
Пример 3.1. Определить тип и число МП БИС, обеспечивающих выполнение БО алгоритма БПФ с прореживанием по времени при следующих ограничениях: Г=2 мкс; система счисления - с фиксированной запятой; аш=2 мВ: динамический диапазон входного сигнала d=45 дБ; тип монтажной платы - односторонняя печатная плата; размерность входного массива vV= 128; потери на выполнение БО - не более 4 дБ; рдоп = 0,1 Вт/см2.
Алгоритм БО БПФ с основанием г = 2 и прореживанием по времени рассматривался в § 2.1. Структурная схема алгоритма представлена на рис. 3.6,а [2]. Алгоритм реализуется на базе МПК БИС, представленных в табл. 1.2. Исключение составляет МПК БИС серии К588. Поскольку алгоритм БО включает операцию умножения, которая не может быть реализована на умножителе К.588ВР2 быстрее 2 мкс, что не удовлетворяет временным ограничениям. Для упрощения задачи в исходный массив МП М (табл. 3.5) включены только АУ, расширители арифметических операций и схемы обмена информацией.
Содержание табл. 3.5 соответствует табл. 3.4. Состав операторов определен из анализа алгоритма БО БПФ. При оценке времени выполнения операции были сделаны следующие допущения: операции сложения (СЛ), вычитания (ВЧТ), пересылки между регистрами общего назначения (Рг - Рг) выполняются за один такт работы МП; операции пересылки память - регистр (П - Рг) » регистр - память (Рг - П) выполняются за три такта работы МП. Операция умножения последовательным умножителем КР1802ВР2 выполняется за 2 мкс, параллельными умножителями - за один такт работы МП.
Операция умножения двух 16-разрядных чисел МП К1800ВС1 и КМ1804ВС2 выполняется программно, в первом случае за 20 тактов, во втором - за 17 тактов [5]. Действительные значения параметров некоторых БИС могут незначительно отличаться от приведенных в табл. 3.5.
Первым шагом алгоритма выбора типа и числа МП является определение разрядности МП, обеспечивающей требуемую точность вычислений. Выше приведена методика определения разрядности МП для системы счисления с фиксированной запятой. Эта методика справедлива для любых цифровых вычис-лительных устройств. Вместе с тем, в РЭА, и в частности в цифровой обработке сигналов, вместо понятия среднее квадратическое значение погрешности на выходе устройства пользуются производным от него понятием: потери (Я), вносимые вычислителем. Под потерями понимается уменьшение отношения сигнал-шум на выходе устройства, обусловленное трансформируемой и инструментальной погрешностями. Эти погрешности называют шумами вычислений. Известно [2], что при Дl + L + знаковый разряд, где L = log2N - старшие разряды кода входных данных, добавляемые для предотвращения переполнений на всех этапах вычислений Выберем lМП = 16
При коррекции времени выполнения операций с учетом разрядности необходимо учитывать следующее: в табл. 3.5 длительность программной реализации операции умножения соответствует 16-разрядным числам. Кроме того, при выполнении арифметических операций используются микросхемы ускоренного переноса К500ИП179 и КМ1804ВР1, которые вносят незначительную задержку распространения сигнала переноса (2 и 15 не соответственно). С учетом этого в табл. 3.6 приведены времена выполнения шагов программы БО.
Вычисление БО на МПК КР1802 может быть реализовано с использованием параллельного умножителя 16x16 типа КР1802ВР5. Умножитель обменивается информацией с МП БИС КР1802ВС1 по магистрали данных. При этом увеличивается время записи произведения, так как пересылка между МП БИС и умножителем эквивалентна пересылке Рг - П.
Алгоритм БО БПФ представляет собой цепочку последовательных операций, значит, TПр равно сумме времен выполнения отдельных его шагов: Tпp1 = 6,6 мкс, TПр2=3,36 мкc, Tпр3= 10 мкс. Микропроцессоры, приведенные в табл. 3.4, не обеспечивают вычисление БО в реальном времени. Для повышения быстродействия вычисления БО необходимо распараллелить ее алгоритм. Для этого в соответствии с п. 12 приведенного выше алгоритма и по данным табл. 3.6 строим матрицу данных (рис. 3.7). Из этой матрицы можно определить подпрограммы, допускающие параллельные вычисления.
3.7. Матрица данных алгоритма базовой операции быстрого преобразования Фурье
Последовательность выполнения подпрограмм по тактам представлена на рис. 3.8. При распараллеливании алгоритма БО БПФ он выполняется за пять тактов. Однако время выполнения БО может быть доведено до одного такта при использовании «конвейерной» структуры вычислений. Принципы построения таких вычислителей рассмотрены в [33, 39]. Суть «конвейерной» организации вычислений заключается в том, что для реализации некоторой программы используются N МП, каждый из которых выполняет только часть программы. Промежуточный результат вычислений 1-го МП передается i+1-му, а i-й МП принимает новые исходные данные от I - 1 МП и повторяет вычисление своей подпрограммы. Программа должна быть распределена между МП таким образом, чтобы обеспечивалась максимальная загрузка каждого МП. Это возможно лишь в случае равенства времен выполнения своих подпрограмм всеми МП, включенными в «конвейер». В любом другом случае длительность одного такта работы «конвейера» будет определяться самым медленным МП цепочки.
При конвейерном вычислении БО на первом такте вычисляются вершины хи х% х5, xs, на втором х3, х6, хд, хХч и т. д. Через пять тактов на выходе МП появится первый результат, последующие результаты будут появляться через каждый такт.
Анализ времен выполнения отдельных операций показывает, что при реализации БО на МПК БИС серий К1800 и КМ 1804 длительность умножения значительно больше длительности выполнения других операций. Поэтому в данном случае целесообразно распараллелить алгоритм БО, например при использовании двух МП K1800BG1 на первом могут быть выполнены подпрограммы I, II, III, VI, VII; на втором IV, V, VIII и IX (рис. 3.8). С учетом дополнительных операций пересылок время выполнения БО будет примерно равно 1,86 мкс, что удовлетворяет временному ограничению. Проводя формальный анализ данных табл. 3.5 и 3.6, а также матрицы данных (рис. 3.7 и 3.8), можно генерировать различные структурные варианты построения МП БО. Некоторые из них показаны на рис. 3.9.
3.8. Временная диаграмма вычисления базовой операции быстрого преобразования Фурье (I - IX - подпрограммы)
3.9. Структурные схемы микропроцессоров базовых операций на МПК К1800 (а), КР1802 и КМ1804 (б) с распараллеливанием вычислений (в) и без распараллеливания вычислений (г)
Микропроцессор, представленный на рис. 3.9,6, использует «конвейерную» организацию вычислений. В соответствии с временной диаграммой на рис. 3.8 на первом этапе осуществляется загрузка комплексного значения поворачивающего коэффициента W и одного отсчета В (вершины х1, x2, х5, x8). С целью повышения быстродействия вычислений загрузка второго отсчета А во времени может быть совмещена с умножением или первым сложением (т. е. выполнена на втором или третьем такте). Параллельный умножитель КР1802ВР5 вы-полняет четыре операции умножения (второй такт). Результаты умножений записываются в процессорную секцию КМ1804ВС2, где программно выполняются остальные вычисления. Время вычислений распределяется по тактам следующим образом: первый такт - 0,8 мкс, второй - 0,6 мкс, третий и четвертый - 1,2 мкс, пятый - 1,2 мкс. Первое значение БО будет вычислено за 2,6 (мкс, следующие значения будут поступать с задержкой 1,2 мкс.
На рис. З.Э.в приведена структурная схема МП, обеспечивающего вычисление БО с максимально возможной скоростью (для заданного в табл. 3.5 набора МП). Высокая производительность вычислений достигнута максимальным их распараллеливанием и использованием аппаратных процессоров. За время одного цикла вычислений МПК КР1802 осуществляется выполнение каждого такта (см. рис. 3.8).
На рис. 3.9,г приведена структурная схема конвейерного МП БО без рас-лараллеливания вычислений. Длительность максимального такта равна временя последовательного вычисления шести операций сложения (0,9 мкс).
Для сравнительной оценки различных вариантов МП БО определим необходимую для их размещения площадь печатной платы. Разбиение печатной платы на основные поля и зоны показано на рис. 2.23. Размеры печатной платы могут быть определены из уравнений (2.5) и (2.6).
Таблица 3.7
Параметры реализации Варианты реализаций микропроцессора базовой операции
3.9,а 3.9,6 3.9.S З.Э.г
Тип используемых микросхем К1800ВС1 К500ИШ79 КР1802ВВ1 КР1802ВР5 КМ1804ВС2 КМ1804ВР1 КР1802ВР5 КР1802ИМ1 КР1802БВ1 KPI802BP5 КР1802ИМ1
Число микросхем, шт. 8 2 4 1 4 1 4 24 4 1 4
Период вычисле-ния БО, мкс 1,86 1,2 0,2 0,9
Среднее число выводов одной микросхемы, шт. 40 40 50 43
Шаг установки микросхем, мм 50X38,5 47,5x32,5 45x38,5 42,5x32,5
Размеры краевых полей (x1; х2; у1, у2), мм 5; 5; 5; 22,5 5; 5; 5; 22,5 5; 5; 5; 22,5 5; 5; 5; 22,5
Размеры печатной платы, мм 110X220 105x190 190X297 137,5X125
Площадь печатной платы, см2 242 199,5 564,3 171,5
Потребляемая мощность, Вт 12,6 17,2 56 16,6
Удельная потребляемая мощность, Вт/см2 0,05 0,09 0,0992 0,097
Основные конструктивные параметры печатных плат для различных структурных вариантов МП БО приведены в табл. 3.7. Расчет конструктивных параметров проводился для случая, когда БИС МПК серий К1800 и КМ1804 выполняются в корпусах с шагом выводов 2,5 мм, а БИС МПК КР1802 - в корпусах с шагом выводов 1,25 мм, монтаж осуществляется гибким печатным кабелем. Шаг установки микросхем определялся исходя из среднего числа выво-лов на одну микросхему и шага выводов корпуса.
Из анализа данных табл. 3.7 вытекает, что предпочтительными вариантами реализации МП БО являются структуры, изображенные на рис. З.ЭДг.
