Оптимальное программирование в архитектуре управления каждым тактом

Расчет нейросети

Попробуем выработать рекомендации по совместному программированию обработки вариантов счета, обработки элементов массива и др., что позволяет увеличить эффективность использования многофункциональных АЛУ.

Методы вычислений отличаются регулярностью действий. На их основе можно строить эффективные схемы вычислений с использованием многофункциональных АЛУ, в том числе — в архитектурах, сводящихся к "длинным" командным словам.

Рассмотрим пример распараллеливания типичного фрагмента обработки нейросети в режиме распознавания. Он демонстрирует способ оптимальной реализации на процессоре, где АЛУ содержит несколько исполнительных устройств (ИУ) различной специализации, функций нейрокомпьютера. Максимальная загрузка всех устройств возможна тогда, когда в каждом линейном участке программы предусмотрена обработка не одного, а нескольких нейронов сети. Покажем это на фрагменте алгоритма имитации работы нейронов в режиме распознавания, т.е. в режиме, требующем максимальной производительности нейрокомпьютера.

Программирование трехадресных команд

В режиме распознавания в простейшей модели нейрона решается задача суммирования взвешенных, в соответствии с регулируемыми на этапе обучения весами {wi},i = 1, ..., n, синапсов — значений синапсических сигналов {xi} и сравнение полученной суммы с порогом h. Если сумма превышает порог, происходит возбуждение нейрона с величиной y:$$y = \left\{ \begin{array}{ll} \Delta = \sum\limits_{i=1}^n w_i x_i - h, \t{ при } \Delta > 0, \\ 0, \t{ при } \Delta \leqslant 0. \\ \end{array} \right.$$

Для n = 3 запишем в трехадресных командах программу одновременной обработки двух нейронов. Это двукратное повторение одной и той же последовательности команд, отличающейся используемыми адресами (табл. 7.1).

Очевидно, программа совместной обработки трех нейронов будет содержать трехкратное повторение такого же участка и т.д.

Компоновка "длинных" команд

Выше было показано, что при решении задач параллельного программирования для полного задания информации о частичной упорядоченности работ целесообразно использовать квадратные (размер m равен числу трехадресных команд линейного участка) нуль-единичные матрицы следования S, дополненные столбцами весов — времен выполнения работ.

Такая матрица для нашего примера представлена в таблице 7.2, где кроме весов указаны также поздние сроки $$\tau$$ начала выполнения команд (для суммы всех времен выполнения работ Т = 56 ) и объемы $$\theta$$ последующих работ. Эти значения найдены по приведенным выше алгоритмам. Если при совместном анализе двух команд ( i -й и j -й, i>j ) первый или второй адрес "нижней" команды совпадает с третьим адресом "верхней" команды, то элемент матрицы S на пересечении i -й строки и j -го столбца полагается равным единице $$\alpha _{ij} = 1$$, в противном случае он равен нулю.

Этот алгоритм формирования матрицы следования предполагает некоторые ограничения на способ программирования. В общем случае такой совместный анализ команд должен быть дополнен анализом на несовпадение третьего адреса команды со всеми адресами вышеследующих команд.

В приведенной матрице отражены и транзитивные связи.

Выберем структуру АЛУ, содержащую два ИУ сложения, два — умножения, два — логических. Остальные ИУ нам в примере не понадобятся. В командных словах также предположим обязательное присутствие позиций, соответствующих этим ИУ.

В таблице 7.3 отражена временная диаграмма условного назначения (формирования "длинного" командного слова) и имитации выполнения трехадресных команд. Алгоритм формирования, выполнение которого сопровождается исключением из матрицы S строк и столбцов, соответствующих "выполненным" командам, изложен выше.

"Назначенные" работы (трехадресные команды) и такты, в которые они назначены, соответствуют "длинным" командам. Как видно из таблицы — диаграммы, программа изобилует пропусками тактов, NOP 'ами.

Предположим наличие средств синхронизации, аналогичное использованию битов значимости. Т.е. предположим, что регистры СОЗУ имеют биты значимости, "взводящиеся" в начале выполнения тех команд, в которых предусмотрена запись в эти регистры. Тогда считывание из этих регистров невозможно до окончания выполнения тех операций, по которым в них производится запись. Отсюда следует возможность ликвидации всех NOP 'ов в программе. В данном примере окончательный вид формируемой программы представлен в таблице 7.4.

Несмотря на то, что мы не можем считать рассмотренный в основной части пример характерным, он наводит на мысль о необходимости полного статистического анализа целесообразности оптимизации компоновки "длинных" командных слов. Сложность такой компоновки, возможно, компенсируется простотой получения программы в результате "быстрой" компоновки, если учитывать совокупную стоимость разработки и выполнения программ. Очевидно, что эта проблема требует изучения на основе моделирования.

Архитектура ВС с управляемой в каждом такте работой исполнительных устройств выявляет определенные правила по организации вычислений. На примере показана целесообразность совместной обработки нескольких элементов массива — в обобщенном понятии. Такая обработка обеспечивает максимальную загрузку оборудования, т.е. максимальное значение коэффициента загрузки исполнительных устройств АЛУ.

Пример оптимизированной компоновки "длинных" командных слов для ВС с синхронными ИУ

Выше мы указывали, что все сделанное теперь требует перекомпоновки, сжатия каждого слова для получения командных слов переменной длины. Каждое слово (впереди указывается его длина) должно нести смысловую нагрузку: "что и какое именно устройство должно в данном очередном такте начать выполнять".

Рассмотрим еще один, более конкретный пример компоновки "длинного" командного слова для ВС, разрабатываемой в 1970-е годы. Проект, основанный на архитектуре "в остаточных классах", не получил должного освещения в годы "холодной войны", тем более, что авторы сами перестали настаивать на его воплощении. Но это был, по-видимому, первый в мире опыт реализации принципа "длинного" командного слова.

Пусть АЛУ процессора ВС состоит из трех многофункциональных блоков ИУ, работающих синхронно. Два блока — универсальные, они содержат специализированные по операциям ИУ (будем называть их основными ИУ) и с их помощью выполняют основной набор операций. Третий блок ИУ обеспечивает обмен СОЗУ (с регистрами которого и только которого работают основные ИУ) с памятью других уровней. Синхронизация работы блоков ИУ осуществляется заданием инструкции каждому из них в соответствующей части командного слова. Т.е. любое командное слово состоит из трех частей, в каждой из которых может быть записана одна инструкция. В первых двух частях содержатся инструкции первому и второму блокам основных ИУ, в третьей — инструкция ИУ обмена. Возможно отсутствие инструкций отдельным блокам ИУ, что эквивалентно простоям ИУ в их составе.

Для выполнения каждой основной инструкции назначается ИУ определенного типа из числа свободных. При отсутствии свободных ИУ для выполнения хотя бы одной инструкции командного слова выполнение этого командного слова (а следовательно, и программы) задерживается.

Предположим, что инструкции, назначенные для выполнения одновременно (в один машинный такт), выполняются назначенными для этого ИУ синхронно за одинаковое и равное для всех операций число машинных тактов t0 = 2.

Обмен выполняется за время t1 = 1.

Предположим, что в ВС для уплотнения записи программы используются элементы адресного распараллеливания, а именно:

Блокировка выполнения инструкции осуществляется в соответствии с адресным способом распараллеливания в том случае, если в ней в качестве операнда фигурирует адрес, являющийся в еще не выполненной инструкции более старшего приоритета адресом результата. Если выполнение второй основной инструкции задерживается, то вместе с ней задерживается выполнение и инструкции обмена. Таким образом, будем считать, что пропуск необходимого числа тактов производится автоматически.

Пусть необходимо написать оптимальную программу счета величин

$$f = b{}^2 /x{}^2 + a/b{}^2$$

$$g = af - t{}^3 (d - c)$$ (7.1)

Программа до оптимизации, написанная "в линеечку", представлена на рис. 7.1.

(рис 7.1) Исходная последовательная программа

В позициях R1 и R2 указываются первый и второй адреса операндов. Это адреса СОЗУ. R3 — адрес результата в СОЗУ, A — адрес считывания или записи в ОП. Использован набор инструкций, содержание которых ясно из их записи.

На рис. 7.2 представлен информационный граф G, отражающий взаимосвязь инструкций. Другим цветом отмечены работы по обмену.

(рис 7.2) Граф-схема алгоритма

В графе G можно найти длину Tкр критического пути. Опыт подсказывает: практические возможности распараллеливания линейного участка программы таковы, что правомерно считать достаточным количество ИУ для выполнения оптимизированной программы за время Tкр. Значит, мы заранее можем для данного линейного участка считать заданным ограничение времени его выполнения T = Tкр. При необходимости легко предусмотреть в алгоритме динамическую коррекцию этого значения. Это позволяет использовать значения поздних сроков окончания выполнения работ и сформулировать более эффективное при данном применении решающее правило, приведенное ниже:

На рис. 7.3 представлена диаграмма выполнения работ (инструкций), иллюстрирующая нахождение поздних сроков окончания их выполнения при T = Tкр = 12.

(рис 7.3) Диаграмма выполнения работ

На рис. 7.4 представлена расширенная матрица следования S*, где для j -й инструкции, j = 1, ..., 19, указано время tj ее выполнения, поздний срок окончания выполнения $$\tau _{2j}(12)$$, а также значение $$\theta _{j}$$ — суммарное время выполнения всех инструкций, которым данная инструкция предшествует. Эти значения отыскиваются в результате введения транзитивных связей в матрицу S, что также показано на рисунке.

(рис 7.4) Расширенная матрица следования