Способ распределения данных по монофункциональным блокам процессора с управлением потоком данных Российский патент 2024 года по МПК G06F8/30 

Изобретение относится к области обработки цифровых данных с помощью электронных устройств, а именно к способам распределения данных по монофункциональным блокам, предназначенных для процессоров с управлением потоком данных (Data Flow Control (DFCJ) и может быть использовано для сокращения времени обработки цифровых данных процессорами DFC.

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

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

Недостатками данных способов являются отсутствие учета конкретной архитектуры процессора и отсутствие учета параметра времени работы монофункциональных блоков процессора.

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

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

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

1. Загрузка имеющихся значений операндов.

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

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

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

5. Определение подмножества готовых к выполнению команд и передача управляющих и арифметических операций для формирования команд готовых к выполнению.

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

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

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

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

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

Новыми признаками, обладающими существенными отличиями, являются: 1. Учет архитектуры процессора с управлением потоком данных.

2. Учет параметра времени начала выполнения операторов параллельного алгоритма в монофункциональных блоках процессора с управлением потоком данных.

Данные признаки обладают существенными отличиями, так как в известных способах не обнаружены.

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

Способ распределения данных по монофункциональным блокам процессора с управлением потоком данных реализуется следующим образом.

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

Рассмотрим пошаговое выполнение предложенного способа в описанной выше системе (Фиг. 1). Загрузка из памяти данных 7 в коммутатор операндов 1 имеющихся значений операндов (шаг 1). Загрузка из памяти данных 7 в блок выборки команд 4 нумерованных последовательностей управляющих операций, определяющих дальнейшие направления вычислительного процесса и арифметических операций (шаг 2). Определение блоком выборки команд 4 связей операций между собой, запись операций и связей в память связей команд 2, и передача коммутатору операндов 1 сигнала на дублирование значений соответствующих операндов для использования в командах различных этапов обработки данных (шаг 3). Дублирование коммутатором операндов 1 значений операндов и запись этих значений в поля первого или второго операндов соответствующих ячеек памяти команд 3 и передача из памяти команд 3 значений операндов в коммутатор команд 5 для формирования команд готовых к выполнению, т.е. имеющих значения всех ее операндов (шаг 4). Определение блоком выборки команд 4 подмножества готовых к выполнению команд и передача из памяти связей команд 2 управляющих и арифметических операций в коммутатор команд 5 для формирования команд готовых к выполнению (шаг 5). Формирование коммутатором команд 5 подмножества готовых команд, содержащих поле операции, поле значения первого операнда, поле значения второго операнда, адрес памяти для временного хранения результата выполнения операции, а также поля признаков наличия в команде значений соответствующих операндов и готовности команды к выполнению, и распределение на монофункциональные блоки 61 исполнительного устройства 6 для параллельного выполнения с учетом параметра времени, т.е. времени начала выполнения и длительности выполнения каждой операции, чем больше длительность выполнения операции, тем раньше операция должна начать выполнение (шаг 6). Выполнение монофункциональными блоками 61 исполнительного устройства 6 подмножества команд и получение результатов значений операндов для последующих команд (шаг 7). Передача исполнительным устройством 6 результатов выполнения команд для дублирования значений операндов в коммутатор операндов 2, записи в ячейки памяти данных и передача по средствам коммутатора команд 5 в последующие команды, которые используют эти результаты в качестве значения первого или второго операнда, содержащего поле значения полученного результата, поля двух номеров команд, использующих данное значение в качестве операнда, и два поля указателей, определяющих характер использования рассматриваемого значения в качестве первого операнда и/или второго операнда (шаг 8). Выполнение монофункциональными блоками 61 исполнительного устройства 6 подмножества команд и получение результата выполнения параллельной программы с временной параметризацией и передача результата для записи в память данных 7 (шаг 9).

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

Источники информации

1. Дроздов А.Ю., Новиков С.В. Способ автоматического распараллеливания программ. Патент на изобретение №2411569, бюл. №4, 2011 г. (аналог).

2. Яковлев С.В., Сафонов И.В., Быкова Т.В. Способ построения программы. Патент на изобретение №2406112, бюл. №34, 2010 г. (прототип).

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

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

загрузка из памяти данных в коммутатор операндов имеющихся значений операндов;

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

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

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

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

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

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

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

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

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