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

Изобретение относится к области обработки цифровых данных с помощью электронных устройств, а именно к способам распределения данных по уровням памяти вычислительной системы, предназначенных для многопроцессорных вычислительных систем с разноуровневой общей памятью (Non-Uniform Memory Access (NUMA)) и может быть использовано для сокращения времени обработки цифровых данных вычислительной системы NUMA.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6. Расчет суммарного количества вхождений оператора во все нити задачи и ранжирование входных данных, промежуточных и выходных результатов выполняется в три этапа:

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

2) определение значений суммарного количества вхождений оператора во все нити задачи, т.е. определение мощности внешнего множества оператора. Формирование структуры не ранжированных данных по суммарным количествам вхождений каждого оператора во все нити задачи.

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

7. Распределение данных по уровням оперативной памяти с учетом минимального времени обращения к оперативной памяти:

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

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

- проверка наличия свободной памяти в данном уровне:

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

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

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

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

10. Формирование множества свободных в момент времени процессоров.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2. Учет параметра времени обращения к различным уровням памяти при решении задачи.

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

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

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

На фиг.1 показана схема основных компонентов многопроцессорной вычислительной системы с разноуровневой общей памятью, состоящий из сети соединений 4, блока выборки инструкций 5, устройства управления 6, арифметико-логического устройства 7 и трех вычислительных узлов 1, 2, 3, которые включают процессоры 11, 21, 31, КЭШ-памяти 12, 22, 32, справочники 13, 23, 33, локальные шины 14, 24, 34, оперативные памяти 15, 25, 35 и интерфейсы вводов/выводов 16, 26, 36, которые реализуют предложенный способ. Вычислительная система содержит три вычислительных узла 1, 2, 3, выполненные с возможностью оптимизации распределения данных программы по различным уровням оперативной памяти, которые соединены с блоком выборки инструкций 5, устройством управления 6, арифметико-логическим устройством 7, предназначенными для создания параллельного кода с временной параметризацией посредством сети соединений 4.

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

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

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

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

2. Викторов Д.С., Брежнев Д.Ю., Толмачев А.А., Калачников А.С., Якунина Г.Р. Способ автоматического создания параллельной программы с временной параметризацией многопроцессорных вычислительных систем с одинаковым доступом к памяти. Патент на изобретение № 2786347, бюл. № 35, 2022 г. (прототип).

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

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