Результат интеллектуальной деятельности: СПОСОБ И АППАРАТУРА ДЛЯ ОБЕСПЕЧЕНИЯ ПОДДЕРЖКИ АЛЬТЕРНАТИВНЫХ ВЫЧИСЛЕНИЙ В РЕКОНФИГУРИРУЕМЫХ СИСТЕМАХ-НА-КРИСТАЛЛЕ

ОБЛАСТЬ ТЕХНИКИ

Изобретение относится к области микроэлектроники и вычислительной техники, в частности к вычислительным системам-на-кристалле на основе архитектуры реконфигурируемых вычислительных сред, и может быть использовано для построения высокопроизводительных вычислительных систем для обработки потоков данных в режиме реального времени и для обработки больших массивов данных.

УРОВЕНЬ ТЕХНИКИ

Направление однородных вычислительных сред (структур) получило дополнительные возможности развития по мере совершенствования развития технологий производства систем - на - кристалле, позволяющих значительно повысить степень интеграции - до сотен миллионов логических вентилей на одном кристалле.

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

Для реализации конкретного вычислительного алгоритма в необходимом для этого подмножестве ячеек матрицы РСНК настраиваются межпроцессорные связи и необходимые функции используемых ячеек. Заданный набор функций из множества возможных функций, используемый в конкретном процессорном элементе для реализации прикладного алгоритма, определяется ее настройкой. Битовые поля процессорного элемента управляют конкретным аппаратным ресурсом процессорного элемента - входным коммутатором для выбора входов процессорного элемента для приема входных операндов, блоком обработки данных для задания функционального оператора, блоком хранения данных, выходным коммутатором для выбора выходов процессорного элемента, на которые передаются результаты вычислений, и т.д. Для настройки процессорного элемента на выполнение заданного набора функций используется регистр настройки, в который при процедуре конфигурировании матрицы РСНК загружается соответствующий код настройки процессорного элемента. Таким образом, загружая соответствующие настройки в соответствующее подмножество (множество) ячеек достигается конфигурирование РСНК на выполнение заданного прикладного алгоритма. Для реализации вычислений по другому прикладному алгоритму должны быть загружены другие настройки в общем случае в другое подмножество ячеек матрицы, что обеспечивает таким образом реконфигурирование вычислительной системы.

Известно (см. Edsger W. Dijkstra. Notes on structured programming, [1]), что для реализации любого прикладного вычислительного алгоритма достаточно использовать ограниченный набор вычислительных структур, составленных из простейших функциональных операторов, и включающий «конкатенацию», «выбор» и «повторение». «Конкатенация» представляет собой последовательное выполнение в заданном порядке заданного набора функциональных операторов над входными операндами. «Выбор» представляет собой вычислительную структуру, в которой только один из, в общем случае, множества возможных операторов выполняется в зависимости от состояния программы или какого-то результата промежуточных вычислений - условия. В частности, к «выбору» относится вычислительная структура типа IF <условие> THEN S1 ELSE S2. «Условие» в данном случае есть однобитовая булева переменная, принимающая значения TRUE и FALSE. При этом если ее значение TRUE, то вычислительная структура выполняет вычисления S1, в противном случае - вычисления S2. Вычисления S1, S2 могут быть как простыми функциональными операторами, так и сложными композитными или иерархическими вычислительными структурами, включающими структуры «конкатенации», «выбора» или «повторения» и функциональные операторы в том числе. «Повторение» обозначает выполнение вычислительной структуры или в пределе одного заданного функционального оператора, пока не будет достигнуто определенное состояние программы - прекращение вычислений по условию, или пока он не будет приложен ко всем элементам массива входных операндов.

Известные вычислительные системы, построенные с использованием архитектуры реконфигурируемых однородных вычислительных сред (Шмойлов В.И., Русин Б.П., Кузьо М.Н. «Ячейка пульсирующих информационных решеток», [2], Патент Российской Федерации №2180969, Бачериков Г.И., Геворкян В.И., Крохин В.М., Татур В.Ю., «Процессор однородной вычислительной среды,» [3]), обладают одним существенным недостатком в случае реализации на них прикладных алгоритмов, в которых широко используется вычислительная структура с ветвлением по условию - структура типа «выбор»: IF <условие> THEN S1 ELSE S2.

В данных системах, например, в самом простом случае для реализации функциональных операторов S1 и S2 потребуется использовать два процессорных элемента и один дополнительный процессорный элемент для выбора правильного результата, в зависимости от состояния внешней однобитовой булевой переменной условия, из двух результатов вычислений по S1 и S2. Вычисление в матрице переменной «условия» может рассматриваться как внешнее по отношению к реализации вычислений по операторам S1 и S2 и может быть реализовано на некотором количестве ячеек, в пределе - на одной. Таким образом, при реализации прикладных вычислительных алгоритмов, в которых широко используется вычислительная структура IF…THEN…ELSE, большое количество вычислительных ресурсов матрицы - ячеек, будет использовано для реализации альтернативных вычислительных структур и альтернативных функциональных операторов.

РАСКРЫТИЕ ИЗОБРЕТЕНИЯ

Эффективность вычислений в РСНК определяется, с одной стороны, возможностями распараллеливания прикладных вычислительных алгоритмов, а с другой - функциональными возможностями ячеек РСНК и размерностью матрицы РСНК, реализуемой в отдельном кристалле заданной площади. Таким образом, для отдельного взятого алгоритма существует возможность максимального распараллеливания вычислений, ограничиваемая размерностью матрицы и функциональными возможностями ячеек, что выражается в количестве ячеек, требуемых для реализации заданного алгоритма. Уменьшение количества ячеек, требуемых для реализации прикладного алгоритма при заданной степени распараллеливания, открывает возможности для дополнительного распараллеливания вычислений по алгоритму в рамках матрицы заданной размерности, что обеспечит повышение производительности вычислительной системы относительно вычислений по данному алгоритму. С другой стороны, уменьшение количества ячеек для реализации различных алгоритмов открывает возможности использования одной матрицы для одновременного выполнения нескольких прикладных алгоритмов, что также повышает производительность вычислительной системы относительно заданного множества вычисляемых прикладных алгоритмов.

Для повышения эффективности вычислений в РСНК предложено, в отличие от указанных известных прототипов ячеек однородной вычислительной среды, которые обеспечивают обработку потоков входных операндов в соответствии с единственным настроенным функциональным оператором, реализовывать в каждом процессорном элементе РСНК альтернативные функциональные операторы. Это позволит уменьшить количество ячеек, используемых для реализации вычислительных структур типа «выбор», поскольку в зависимости от состояния булевой переменной можно выполнять вычисления либо одного, либо другого функционального оператора в одном процессорном элементе РСНК, а не в двух.

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

При осуществлении предложенного способа повышения эффективности вычислений, во-первых, расширяется код настройки процессорного элемента и регистр кода настройки процессорного элемента для его загрузки и хранения на время выполнения конкретного прикладного вычислительного алгоритма путем введения дополнительных альтернативных полей для управления соответствующих аппаратных ресурсов процессорного элемента - входного коммутатора, блока обработки данных и выходного коммутатора. Использование прямого или альтернативного поля настройки для конкретного аппаратного ресурса процессорного элемента определяется либо состоянием внешней по отношению к процессорному элементу булевой однобитовой переменной, сигнал которой поступает на один из множества входов процессорного элемента, либо состоянием внутренней переменной, сигнал которой формируется с помощью других аппаратных ресурсов процессорного элемента, например, внутренним устройством управления процессорного элемента. Также, вводятся коммутаторы альтернативных кодов настройки для управления соответствующими аппаратными ресурсами процессорного элемента, управляемые сигналом булевой переменной условия. Также, вводится коммутатор выбора сигнала булевой переменной условия из множества возможных, включая сигналы, поступающие на все внешние входы процессорного элемента, и возможные внутренние сигналы процессорного элемента и константы «0» и «1». Кроме того, для управления коммутатором выбора сигнала булевой переменной условия в код настройки процессорного элемента вводится еще одно дополнительное поле. Таким образом, при использовании предложенного процессорного элемента при относительно небольших аппаратных издержках по сравнению с аппаратурой исходного процессорного элемента РСНК в зависимости от конкретного прикладного алгоритма в пределе может достигаться двукратное уменьшение аппаратных ресурсов (количества ячеек) для реализации алгоритма.

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

Фиг.1. Обобщенная структурная схема исходного процессорного элемента РСНК.

Фиг.2. Конфигурация РСНК для реализации вычислительной структуры IF…THEN…ELSE на основе исходного процессорного элемента.

Фиг.3. Обобщенная структурная схема модифицированного процессорного элемента РСНК.

Фиг.4. Конфигурация РСНК для реализации вычислительной структуры IF…THEN…ELSE на основе модифицированного процессорного элемента.

Фиг.5. Схема реализации входного и выходного коммутаторов на основе элемента управляемого мультиплексора.

Фиг.6. Схема элемента управляемого мультиплексора.

ОСУЩЕСТВЛЕНИЕ ИЗОБРЕТЕНИЯ

Обобщенная структурная схема процессорного элемента (ячейки) РСНК, содержащей, в том числе, входной коммутатор 1, блок обработки данных 2 и выходной коммутатор 3, представлена на Фиг.1. Процессорный элемент, помимо иной возможной аппаратуры, содержит входной коммутатор 1, на вход которых поступают K сигналов 20, включающие все внешние входы процессорного элемента и возможно набор внутренних сигналов процессорного элемента - выходы аппаратных блоков и других узлов процессорного элемента, включая или нет, M выходов блока обработки данных 2, выходы элементов внутренней памяти, выходы транзитных каналов и выходы устройства управления процессорным элементом, a L выходов которого с помощью сигналов 21 подключены к соответствующим входам блока обработки данных 2, блок обработки данных 2, M выходов которого с помощью сигналов 22 подключены к соответствующим входам выходного коммутатора 3, выходной коммутатор 3, выходы которого поступают на S внешних выходов 23 процессорного элемента, и регистр 4 кода настройки процессорным элементом, который, в том числе, включает поле управления 5 входным коммутатором 1, поле управления 6 блоком обработки данных 2 и поле управления 7 выходным коммутатором.

Поля управления кода настройки представляют собой двоичные коды требуемой размерности для управления соответствующими аппаратными ресурсами процессорного элемента, включая представленные блоки процессорного элемента, а также любые другие - например, блоки памяти, каналы транзита, устройство управления процессорным элементом и т.д. Каждый бит кода настройки хранится в отдельном триггере регистра кода настройки 4. Каждое поле регистра кода настройки подключено к управляющим входам коммутаторов и блока обработки данных - поле 5 с помощью сигналов 24 подключается к управляющим входам входного коммутатора 2, поле 6 с помощью сигналов 25 подключается к управляющим входам блока обработки данных 2 и поле 7 с помощью сигналов 26 подключается к управляющим входам выходного коммутатора 3.

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

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

Код настройки процессорного элемента на выполнение заданного функционального оператора над входными операндами параллельно или последовательно загружается в регистр кода настройки 4 перед началом обработки данных.

Процессорный элемент выполняет функцию преобразования данных - операндов, последовательно поступающих на внешние входы по одному разряду за один такт сигнала синхронизации, в течение определенного количества тактов сигнала синхронизации. Число тактов обработки определяется собственно выполняемым функциональным оператором и форматом обрабатываемых данных, который является переменным, от 1 до N разрядов. Между операндами могут быть паузы в P тактов сигналов синхронизации.

Поле кода настройки 5 регистра кода настройки 4, управляющее входным коммутатором 1, задает адреса источников входных операндов для функционального оператора, заданного в блоке обработки данных 2 полем кода настройки 6 регистра кода настройки 4. Поле кода настройки 7 регистра настройки 4, управляющее выходным коммутатором 3, задает адреса внешних выходов процессорного элемента, на которые будут выдаваться результаты вычислений из блока обработки данных 2, последовательно, по одному разряду за один такт сигнала синхронизации.

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

В случае необходимости реализации в матрице РСНК на основе рассмотренного процессорного элемента вычислительной структуры типа «выбор» - IF C THEN S1 ELSE S2, где C - однобитовая булева переменная условия ветвления, S1 и S2 - альтернативные функциональные операторы, должно быть использовано как минимум четыре процессорных элементов в соответствии с Фиг.2 (на Фиг.2 показаны только используемые межпроцессорные связи). Допустим, что каждый процессорный элемент имеет по два входа и по два выхода на каждую сторону для связи со смежными процессорными элементами и имеет как минимум один транзитный канал. Тогда для выполнения указанной вычислительной структуры процессорный элемент Я2 должен быть настроен для обработки потоков данных A и B с использованием функционального оператора S1, а процессорный элемент Я3 должен быть настроена для выполнения обработки потоков данных E и D с использованием функционального оператора S2. Процессорный элемент Я1 исходя из определяемого в вычислительном алгоритме условия формирует сигнал булевой переменной условия C, который определяет выдачу окончательного результата на выходе процессорного элемента Я4 из двух входных результатов S1(A,B) и S2(E,D). В процессорном элементе Я5 используется только канал транзита для передачи результата S2(E,D) на вход процессорного элемента Я4. Отметим, что сигнал булевой переменной условия должен находиться в одном состоянии («0» - FALSE или «1» - TRUE) в течение такого количества тактов сигнала синхронизации, которое достаточно для последовательной пересылки по одному биту за один такт как минимум одного результата заданной разрядности.

Модифицированный процессорный элемент, позволяющий в соответствии с изложенным способом повысить эффективность вычислений в РСНК, представлен на Фиг.3.

В соответствии с предложенным способом повышения эффективности вычислений в модифицированный процессорный элемент РСНК дополнительно введены поля 8, 9, 10, 11 в регистр кода настройки и мультиплексоры 12, 13, 14, 15. Таким образом, поля 5 и 8 используются для управления входным коммутатором 1 и задают альтернативные адреса внешних входов, являющихся источниками входных операндов для альтернативных функциональных операторов, поля 6 и 9 задают пару альтернативных функциональных операторов, используемых в блоке обработки данных 2, а поля 7 и 10 задают альтернативные адреса внешних выходов процессорного элемента, на которые будут выдаваться результаты вычислений из блока обработки данных 2 по альтернативным функциональным операторам. Таким образом, блок обработки данных выполнен с возможностью настройки на выполнение одного из двух альтернативных функциональных операторов из заданного множества возможных операторов в зависимости от состояния булевой переменной условия. Альтернативный функциональный оператор выбирает для управления блоком обработки данных соответствующее поле из двух альтернативных полей кода настройки. В частном случае поля 5 и 8 и 7 и 10 могут попарно совпадать. Поле 11 используется для определения источника сигнала булевой переменой условия.

Мультиплексоры 12, 13 и 14 используются для подачи управляющих полей регистра кода настройки на соответствующие аппаратные ресурсы в зависимости от состояния сигнала булевой переменной условия 16, формируемого мультиплексором 15. На многоразрядные информационные входы мультиплексора 12 приходят сигналы 24 и 27, несущие информацию о значении соответственно полей регистра настройки 5 и 8, а выходы мультиплексора 12 с помощью сигналов 31 подключаются к управляющим входам входного коммутатора 1. На управляющий вход мультиплексора 12 подается сигнал переменной условия 16. На многоразрядные информационные входы мультиплексора 13 приходят сигналы 25 и 28, несущие информацию о значении соответственно полей регистра настройки 6 и 9, а выходы мультиплексора 13 с помощью сигналов 32 подключаются к управляющим входам блока обработки данных 2. На управляющий вход мультиплексора 13 подается сигнал переменной условия 16. На многоразрядные информационные входы мультиплексора 14 приходят сигналы 26 и 29, несущие информацию о значении соответственно полей регистра настройки 7 и 10, а выходы мультиплексора 14 с помощью сигналов 33 подключаются к управляющим входам выходного коммутатора 3. На управляющий вход мультиплексора 14 подается сигнал переменной условия 16.

Мультиплексор 15 формирует сигнал булевой переменной условия с помощью поля 11 регистра кода настройки. При этом входами 34 мультиплексора 15 являются К внешних входов процессорного элемента, и возможный набор внутренних сигналов процессорного элемента - выходов аппаратных блоков и других узлов процессорного элемента, включая или нет, М выходов блока обработки данных 2, выходы элементов внутренней памяти, выходы транзитных каналов и выходы устройства управления процессорным элементом, а также две константы «0» и «1». Поле 11 регистра кода настройки подключается с помощью сигналов 30 к управляющим входам мультиплексора 15.

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

На Фиг.4 (на Фиг.4 показаны только используемые межпроцессорные связи) представлена конфигурация матрицы РСНК для реализации с использованием модифицированного процессорного элемента вычислительной структуры типа «выбор» - IF C THEN S1 ELSE S2, где C - однобитовая булева переменная условия ветвления, S1 и S2 - альтернативные функциональные операторы, аналогичной, рассмотренной на Фиг.2. При этом входные потоки данных A, B, D, E подаются на внешние входы модифицированного процессорного элемента Я2, который в зависимости от сигнала условия С, поступающего как и в предыдущем случае с выхода процессорного элемента Я1, формирует на выходе результат вычисления S1(A,B) или S2(E,D). В этом случае используемое для реализации вычислительной структуры количество ячеек меньше в 2 раза и также не требуется вспомогательный процессорный элемент для транзита.

На Фиг.5 представлен вариант реализации входного 1 или выходного коммутатора 2 с использованием элемента управляемого мультиплексора. Коммутатор имеет внешние входы, включающие информационные входы 41, входы двух альтернативных полей 42 и 43, поступающие из регистра настройки процессорного элемента и вход 44 сигнала булевой переменой условия выбора управляющих полей 42 и 43 и N выходов 46. Коммутатор содержит N элементов управляемых мультиплексоров 45, входы которых подключены к внешним входам коммутатора, а N выходов которых являются внешними выходами 46.

Таким образом, в зависимости от состояния на входе 44 в элементе 45 выбирается одно из полей 42 или 43 для управления подключением одного из информационных входов к выходу элемента 45, а все выходы элементов 45 формируют набор из N внешние выходы коммутатора.

На Фиг.6 представлен вариант реализации элемента управляемого мультиплексора для построения входного и выходного коммутаторов 1 и 2 модифицированного процессорного элемента.

Элемент содержит мультиплексор 51 и многоразрядный мультиплексор 52. Информационные входы мультиплексора 51 являются внешними входами 53 элемента управляемого мультиплексора, а его информационный выход является выходом 54 элемента. Мультиплексор 51 управляется с помощью двоичного кода 55, поступающего с выхода многоразрядного мультиплексора 52, который управляется входным сигналом 56, а на информационные входы которого поступают входные коды 57 и 58.

Таким образом, в зависимости от состояния входного сигнала 56 на управляющий вход мультиплексора 51 подается либо код, определяемый состоянием входа 57, либо код, определяемый состоянием входа 58. В зависимости от состояния управляющего входа мультиплексора 51 один из выбранных входных сигналов передается на выход элемента управляемого мультиплексора.

ИСТОЧНИКИ

1. Edsger W. Dijkstra. «Notes on structured programming». In Ole-Johan Dahl, Edsger W. Dijkstra, and C.A.R. Hoare, editors, Structured Programming. Academic Press, 1972.

2. Шмойлов В.И., Русин Б.П., Кузьо М.Н. «Ячейка пульсирующих информационных решеток». - Львов: Меркатор, 2001. - 34 с.

3. Патент №2180969 от 2002.03.27, Бачериков Г.И., Геворкян В.И., Крохин В.М., Татур В.Ю., «Процессор однородной вычислительной среды».