Способ автоматического создания параллельной программы с временной параметризацией многопроцессорных вычислительных систем с одинаковым доступом к памяти Российский патент 2022 года по МПК G06F8/40 G06F9/00 

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

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

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

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

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

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

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

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

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

3. Разработка новых структур спецификации программы, описывающих исходную программу с детализацией до операций/функций:

- выделение из множества элементов постфиксной спецификации программы подмножества операторов операций/функций программы;

- сквозную нумерацию операторов;

- сквозную нумерацию входов для каждого оператора и выходов;

- ввод числового кодирования типов операторов на основе постфиксного представления каждой операции/функции;

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

- формирование для каждого оператора множества его внешних операторов (использующих результаты выполнения оператора) и задание его мощности;

- формирование, исходя из постфиксного представления операций/функций, для каждого оператора соответствующих меток.

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

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

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

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

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

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

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

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

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

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

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

Для различных «частных» алгоритмов задач приоритеты операторов могут определяться в соответствии с различными стратегиями (по максимальному времени выполнения ветвей алгоритма, содержащих данный оператор в качестве начального оператора ветви; по времени выполнения оператора; присвоение абсолютных приоритетов некоторым операторам; «динамические приоритеты» (приоритет оператора может изменяться с течением времени и устанавливаться в определенные моменты времени в зависимости от выполнения некоторых условий)).

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

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

Одновременно с назначением оператора на реализацию с помощью соответствующего процессора этот процессор переводится в состояние «занят» и рассчитывается момент завершения выполнения им оператора и перехода процессора в состояние «свободен».

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

Процедура завершается при окончании рассмотрения и расстановки на временных уровнях всех операторов задачи в новом формате.

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

- текстовых спецификаций временных нитей параллельной программы со встроенными средствами (операторами sleep) временной синхронизации;

- структур временной спецификации параллельной программы в виде индивидуальных текстов нитей программ процессоров ВС со встроенными средствами (операторами sleep) временной синхронизации;

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

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

Основные этапы разработки текстовых спецификаций временных нитей программ параллельной программы включают:

- цикл по номерам операторов основной структуры;

- определение номера процессора, реализующего оператор;

- формирование текстовой спецификации оператора/операции, включающее:

1) определение с помощью основной структуры типа процессорной команды;

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

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

4) временная параметризация операторов процессорных нитей программ;

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

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

11. Компилирование созданного параллельного кода с временной параметризацией.

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

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

1. Распараллеливание операций/функций и фрагментов исходного кода программы, не содержащих циклы.

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

3. Учет параметра времени начала выполнения инструкций параллельного алгоритма.

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

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

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

На фиг. 1 показана схема основных компонентов многопроцессорной вычислительной системы с одинаковым доступом к памяти состоящий из двух процессоров, которая реализует предложенный способ. Вычислительная система содержит главную систему 1, выполненную с возможностью оптимизации загрузки процессоров, которая соединена с устройством назначения 2 (устройством, предназначенным для создания параллельного кода с временной параметризацией) посредством интерфейса 3. Процесс выполнения операций в главной системе контролируется через интерфейс 3 с помощью устройства управления 21, которое управляет работой средств создания программы (компиляторов, компоновщики и др.), которые также хранятся в памяти 14. Информацию о процессе создания программы демонстрируют на дисплее 15. Параметры для создания программы заносят в систему с помощью устройства 13 ввода. Обмен информацией в главной системе осуществляют через шину данных 16. На выходе предложенного способа получают рабочую программу для процессоров 11, 12; ее передают в память 14 главной системы 1 через интерфейс 3. В процессе функционирования главной системы 1 процессоры 11, 12 выполняют параллельную программу с временной параметризацией. Устройство назначения 2 содержат устройство управления 21, блок выборки инструкций 22, арифметико-логическое устройство 23. Оптимизация согласно предложенному способу направлена на более эффективную загрузку процессоров за счет временной синхронизации нитей программы. Обмен информацией в устройстве назначения 2 осуществляется через шину 24.

Рассмотрим пошаговое выполнение предложенного способа создания программы в описанной выше системе (Фиг. 1). Исходный последовательный код программы строят для процессоров 11, 12 главной системы 1, через интерфейс 3 при помощи блока выборки инструкций 22 устройства назначения 2 получают упорядоченный выбор лексем исходной последовательной программы и сформировать дескрипторы лексем (шаг 1). Блок выборки инструкций 22 получает упорядоченный выбор дескрипторов лексем, формирует для этой конструкции постфиксную спецификацию и сохраняет в памяти 25 (шаг 2). Разрабатывает новые структуры спецификации программы с детализацией до операций/функций (шаг 3). Разрабатывает новые структуры спецификации программы с детализацией до фрагментов (шаг 4). Устройство управления 21 проверяет эквивалентность текстовой спецификации программы задачи и ее представления новыми структурами спецификации (шаг 5.) Арифметико-логическое устройство 23 рассчитывает для операторов новой спецификации значения приоритетов (шаг 6). Устройство управления 21 формирует множества операторов-претендентов на начало выполнения в момент времени (шаг 7). Назначает операторы с наивысшим приоритетом для реализации на свободный процессор 11 или 12 (шаг 8). Блок выборки инструкций 22 разрабатывает текстовые спецификации нитей параллельной программы с временной параметризацией; добавляет встроенные средства (операторы sleep) временной синхронизации в код для каждого процессора 11, 12 (шаг 9). Устройство управления 21 оценивает корректность результатов разработки параллельных программ с временной параметризацией (шаг 10). Устройство управления 21 через интерфейс 3 подает команду процессорам 11, 12 на компилирование созданного параллельного кода с временной параметризацией (шаг 11). Ниже приведен пример созданного параллельного кода с временной параметризацией (фиг. 2).

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

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

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

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

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