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

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

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

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

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

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

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

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

1. Загрузка последовательного кода программы.

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

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

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

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

6. Определение подмножества готовых к выполнению команд, т.е. имеющих значения всех ее операндов и передача для формирования команд готовых к выполнению;

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

8. Выполнение подмножества команд и получение результатов значений операндов для последующих команд;

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

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

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

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

1. Учет архитектуры вычислительной системы с управлением потоком данных.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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