Исследование и оптимизация технологий программирования и методов анализа для мелкозернистого параллелизма задач на современных многоядерных процессорах тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Лось Денис Андреевич

• Лось Денис Андреевич
• кандидат наук
• 2026

Оглавление диссертации кандидат наук Лось Денис Андреевич

Введение

Глава 1. Исследование применения и эффективности

технологии одновременной многопоточности для параллелизации программ и улучшения однопоточной производительности

1.1 Устройство современных высокопроизводительных процессоров

1.2 Технологии многопоточности на ядрах процессора

1.3 Математическая постановка задачи

1.3.1 Выявление и трансформация параллельных участков программы

1.3.2 Исполнение мелкозернистых задач на БЫХ-ядре

1.3.3 Определение целесообразности параллелизации на БЫХ-ядре

1.3.4 Общая математическая постановка задачи

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

1.5 Исследование эффективности современных технологий параллельного программирования при мелкозернистой параллелизации на БЫХ-ядрах

1.6 Обзор применения технологии одновременной многопоточности

в реализациях метода вспомогательного потока

1.7 Обзор применения технологии одновременной многопоточности

для спекулятивной параллелизации на уровне потоков

1.8 Выводы по главе

Глава 2. Исследование и разработка специализированной системы параллельного программирования для мелкозернистого параллелизма задач на 8МХ-ядрах

2.1 Исследование причин и подходов к минимизации задержек при отправке задач на исполнение в современных технологиях параллельного программирования

2.2 Устройство системы параллельного программирования Relic для мелкозернистой параллелизации задач на SMT-ядрах

2.3 Алгоритм отправки задач на исполнение в системе параллельного программирования для мелкозернистой параллелизации на SMT-ядрах

2.3.1 Описание алгоритма отправки задач на исполнение

2.3.2 Результаты анализа эффективности алгоритма

2.3.3 Исследование эффективности мелкозернистой параллелизации на SMT-ядрах по сравнению с параллелизацией на отдельных физических ядрах

2.4 Использование функций-подсказок для предпробуждения

потоков операционной системы в системе Relic

2.5 Выводы по главе

Глава 3. Исследование средств параллелизации

последовательных программ

3.1 Принципы параллелизации последовательных программ

3.1.1 Зависимости по данным

3.1.2 Зависимости по управлению

3.1.3 Статические и динамические методы анализа зависимостей

3.1.4 Паттерны параллельного программирования

3.2 Средства анализа зависимостей по данным в программах

3.3 Автоматические средства параллелизации последовательных программ

3.4 Полуавтоматические средства параллелизации последовательных программ

3.5 Средства параллелизации с использованием методов машинного обучения

3.6 Средства параллелизации с использованием глубоких

нейронных сетей

3.7 Средства параллелизации с использованием LLM-агентов

3.8 Исследование проблем применения средств параллелизации к критичным к задержке приложениям промышленного уровня

3.9 Исследование точности выявления потенциальных параллельных участков кода средствами параллелизации в критичных к задержке приложениях промышленного уровня

3.9.1 Методология исследования

3.9.2 Результаты исследования

3.10 Выводы по главе

Глава 4. Исследование и разработка полуавтоматической системы для мелкозернистой параллелизации критичных по задержке приложений на SMT-ядрах

4.1 Устройство системы полуавтоматической параллелизации Aira

4.2 Детекция горячих участков кода

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

4.4 Методы улучшения точности выявления потенциальных параллельных участков кода в последовательных программах

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

4.4.2 Метод использования динамического анализа зависимостей

4.4.3 Результаты анализа эффективности методов

4.5 Метод определения целесообразности параллелизации на

SMT-ядрах

4.5.1 Результаты анализа эффективности использования

системы Pereplut для определения целесообразности параллелизации на SMT-ядрах

4.6 Выводы по главе

Глава 5. Улучшение производительности критичных к

задержке приложений с помощью мелкозернистой параллелизации на SMT-ядрах

5.1 Методология замеров улучшения производительности критичных к задержке приложений за счёт мелкозернистой параллелизации на SMT-ядрах

5.2 Результаты замеров улучшения производительности критичных

к задержке приложений

5.3 Выводы по главе

Заключение

Словарь терминов

Список литературы

Список рисунков

Список таблиц

Приложение А. Примеры сложных случаев параллелизации

программ с помощью модели GPT-5 Thinking

Приложение Б. Семантические запросы для различных

паттернов в методе семантического анализа в системе параллелизации последовательных программ Aira

Приложение В. Акты о внедрении

Введение диссертации (часть автореферата) на тему «Исследование и оптимизация технологий программирования и методов анализа для мелкозернистого параллелизма задач на современных многоядерных процессорах»

Введение

Крупнейшие технологические компании вкладывают значительные ресурсы в оптимизацию сервисов, критичных к задержке (latency-critical). Это оправдано: такие системы ежедневно обслуживают запросы более миллиарда пользователей. Например, инфраструктура биржи NASDAQ обрабатывает свыше миллиона сообщений в секунду.

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

Жёсткие требования по задержке предъявляются не только в серверных и облачных средах, но и на клиентских устройствах. В 2025 году около 3.6 млрд человек активно играют в видеоигры, из них 1.5 млрд — в Азии. Значительная часть геймплея приходится на мобильные устройства: к середине 2025 года в мире насчитывается более 7 млрд смартфонов в обращении, и их производительность ежегодно растёт, уже сопоставима с настольными системами трёх-пяти поколений назад.

Несмотря на значительные вложения в оптимизацию систем, критичных к задержке, анализ показывает: из-за простоев при исполнении в ряде случаев может быть в среднем задействовано лишь 40% исполнительных устройств для потоков критичных к задержке приложений [1].

Чтобы повысить утилизацию аппаратных ресурсов, современные высокопроизводительные процессоры используют одновременную многопоточность (Simultaneous Multithreading, SMT), позволяющую на каждом такте отправлять на исполнение на функциональные устройства процессорного ядра инструкции с нескольких потоков исполнения. Параллелизм на уровне инструкций повышает утилизацию ресурсов процессорного ядра, а параллелизм на уровне потоков — общую пропускную способность системы.

Однако технология SMT может снижать однопоточную производительность (single-thread performance) [2], поэтому для ключевых потоков в критичных к задержке приложениях её чаще всего отключают.

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

Критичные к задержке приложения оптимизируются в том числе за счёт их параллелизации. Крупнозернистые параллельные задачи, как правило, видны и выделяются на этапе дизайна алгоритмов и разработки приложения. Однако мелкозернистые задачи в большинстве случаев остаются невыделенными и неиспользованными при параллелизации. Под мелкозернистыми задачами в данной работе понимаются задачи, которые выполняют от 500 до 3000 инструкций, что для процессора с частотой 3 ГГц, исполняющего для данного потока в среднем одну инструкцию за такт, соответствует гранулярности от 160 до 1000 наносекунд.

Целью данной диссертационной работы является разработка методов выявления в последовательных программах потенциально параллельных мелкозернистых задач и программных средств их параллельного исполнения на БМТ-ядрах современных процессоров для улучшения производительности критичных к задержке приложений.

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

1. Исследовать эффективность использования современных технологий параллельного программирования для мелкозернистой параллелизации на БМТ-ядрах.

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

3. Разработать специализированную систему параллельного программирования для мелкозернистого параллелизма задач на БМТ-ядрах.

4. Исследовать и разработать полуавтоматическую систему для мелкозернистой параллелизации критичных к задержке приложений промышленного уровня на БМТ-ядрах.

Тема и содержание диссертационной работы соответствует паспорту научной специальности 2.3.5. Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей, в частности, пунктам:

п. 1 - Модели, методы и алгоритмы проектирования и анализа программ и программных систем, их эквивалентных преобразований, верификации и тестирования.

п. 3 - Модели, методы, алгоритмы, языки и программные инструменты для организации взаимодействия программ и программных систем.

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

п. 8 - Модели и методы создания программ и программных систем для параллельной и распределенной обработки данных, языки и инструментальные средства параллельного программирования.

Научная новизна:

1. Впервые проведено исследование эффективности использования современных технологий параллельного программирования для мелкозернистой параллелизации на SMT-ядрах.

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

3. Впервые представлена полуавтоматическая система параллелизации последовательных программ на основе LLM-агента с использованием процедурного промптинга с инструментальной поддержкой (tool-augmented procedural prompting), в которой встроенная в агента LLM используется для выявления потенциального параллелизма и синтеза параллелизующих преобразований кода, а в качестве инструментов агента могут подключаться такие средства, как средства динамического профилирования и анализа зависимостей, средства обнаружения горячих участков кода (hot spots), а также симулятор производительности SMT-ядер процессора.

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

Практическая значимость результатов диссертации заключается в том, что разработанные решения, такие как специализированная система параллельного программирования Relic для мелкозернистого параллелизма

задач на SMT-ядрах и полуавтоматическая система Aira для мелкозернистой параллелизации критичных к задержке приложений промышленного уровня на SMT-ядрах, были использованы в исследовательских проектах компании «Huawei».

Результаты данной работы внедрены в кафедральный курс «Микроархитектура современных микропроцессоров» кафедры микропроцессорных технологий в интеллектуальных системах управления МФТИ.

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

Основные положения, выносимые на защиту:

1. Специализированная система параллельного программирования, которая позволяет достичь прироста производительности до 20% по сравнению с технологиями параллельного программирования общего назначения, такими как LLVM OpenMP и OpenCilk, при мелкозернистой параллелизации на SMT-ядрах.

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

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

4. Метод определения целесообразности параллелизации на БЫХ-ядрах с помощью симулятора производительности процессора по трассам исполнения в системах параллелизации последовательных программ.

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

Апробация работы. Результаты диссертационной работы докладывались на:

1. 66-й Всероссийской научной конференции «Московского физико-технического института (национального исследовательского университета)», Москва, апрель 2024 г.

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

Публикации. Основные результаты по теме диссертации изложены в 3 печатных изданиях, 2 из которых изданы в журналах, рекомендованных ВАК, 1 —в тезисах докладов.

Объем и структура работы. Диссертация состоит из введения, 5 глав, заключения и 3 приложений. Полный объём диссертации составляет 185 страниц, включая 37 рисунков и 9 таблиц. Список литературы содержит 150 наименований.

Глава 1. Исследование применения и эффективности технологии одновременной многопоточности для параллелизации программ и улучшения однопоточной производительности

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

В параграфе 1.1 рассматривается устройство современных высокопроизводительных процессоров, а в параграфе 1.2 обсуждаются различные типы многопоточности на процессорных ядрах и принципы их работы. В параграфе 1.3 рассматривается математическая постановка задач диссертационной работы. В параграфе 1.4 рассматриваются работы по анализу эффективности использования одновременной многопоточности при параллелизации программ с помощью технологий параллельного программирования. В параграфе 1.5 исследуется эффективность мелкозернистой параллелизации на БМТ-ядрах с различными современными технологиями параллельного программирования. В параграфе 1.6 проводится обзор исследований в области применения и оптимизации технологии одновременной многопоточности для реализации метода вспомогательного потока, в то время как в параграфе 1.7 рассматривается спекулятивная параллелизация на уровне потоков на основе технологии одновременной многопоточности.

Основные результаты, представленные в данной главе, были опубликованы в работах [3; 4].

1.1 Устройство современных высокопроизводительных

процессоров

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

В то время как суперскалярные процессоры могут использовать как последовательное исполнение (in-order execution) инструкций, так и внеочередное исполнение (out-of-order execution), большинство высокопроизводительных процессоров используют внеочередное исполнение для выявления большего числа независимых операций и увеличения параллелизма на уровне инструкций. Внеочередное исполнение инструкций в современных процессорах, как правило, осуществляется на основе алгоритма Томасуло [5] с использованием множества дополнительных оптимизаций и улучшений.

В процессорах с внеочередным исполнением команд буфер переупорядочивания (Reorder Buffer, ROB) и очередь инструкций (Instruction Queue, IQ) являются ключевыми аппаратными структурами, использующимися для выделения параллелизма на уровне инструкций. Буфер переупорядочивания используется для поддержания исходного программного порядка инструкций, в котором исполнение инструкций должно быть видно

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

Инструкции помещаются в буфер переупорядочивания и очередь инструкций после переименования регистров (register renaming) на стадии аллокации (allocation). При этом из очереди инструкций инструкции удаляются после успешной отправки на исполнение на функциональных устройствах, в то время как из буфера переупорядочивания удаление (commit, retirement) происходит, когда инструкция уже исполнена и достигает начала буфера, т.е. становится самой старой инструкцией в буфере.

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

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

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

Однако как показывают проведённый анализ и ранее выполненные работы, для потоков, критичных к задержке, утилизация функциональных устройств в ряде случаев может достигать лишь 40% [1]. В связи с этим в современных процессорах часто используется оптимизация - одновременная многопоточность (Simultaneous Multithreading, SMT), при использовании которой на одном ядре процессора могут одновременно исполняться инструкции нескольких потоков за счёт хранения нескольких контекстов исполнения. Отправка на исполнение на функциональных устройствах инструкций сразу с нескольких потоков позволяет улучшить утилизацию аппаратных ресурсов.

1.2 Технологии многопоточности на ядрах процессора

Одновременная многопоточность — это не единственная оптимизация, при использовании которой на одном ядре процессора могут исполняться инструкции сразу с нескольких потоков. Существует несколько реализаций многопоточности (multithreading) на процессорных ядрах, а именно мелкозернистая многопоточность (fine-grained multithreading), крупнозернистая многопоточность (coarse-grained multithreading) и, соответственно, одновременная многопоточность (simultaneous multithreading).

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

инструкций с других потоков, однако приводит к значительному снижению однопоточной производительности. Фактически, производительность одного потока при использовании мелкозернистой многопоточности будет лишь 1/Т от исходной производительности, где Т — число аппаратных потоков. В ряде исторических процессоров Т выбирали близким к глубине конвейера. Идея мелкозернистой многопоточности известна достаточно давно и применялась в таких вычислительных системах 1960-70-х годов, как CDC 6600 [6] и HEP [7]. В CDC 6600 поток исполнения менялся на каждом такте, а инструкции одного потока исполнялись через каждые 10 тактов за счёт десяти периферийных процессоров. В HEP на процессорном ядре поддерживалось до 128 контекстов исполнения, при этом только одна инструкция каждого потока исполнения могла присутствовать в конвейере. В современных центральных процессорах мелкозернистая многопоточность практически не используется из-за значительного снижения однопоточной производительности. Однако мелкозернистая многопоточность является одной из ключевых технологий, позволяющих организовать параллельные вычисления на современных графических процессорах.

При крупнозернистой многопоточности переключение между контекстами происходит, как правило, по некоторому событию, которое может приводить к блокировке исполнения инструкций в конвейере, к примеру, промаху в кэш процессора. Так, к примеру, в процессоре APRIL [8] переключение между потоками происходило по таким событиям, как промах в кэш, доступ к сети и ошибка синхронизации. При переключении контекста в APRIL происходило очищение конвейера. По сравнению с мелкозернистой многопоточностью переключение между контекстами в крупнозернистой многопоточности занимает больше времени, однако снижение однопоточной производительности оказывается значительно меньше. Крупнозернистая многопоточность использовалась в высокопроизводительных процессорах в конце 1990-х и начале 2000-х годов, таких как IBM RS64-IV [9] и процессор Intel Montecito с архитектурой Itanium [10], однако современные процессоры, как правило, используют одновременную многопоточность.

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

многопоточности. Компания Intel реализует одновременную многопоточность под названием технология Hyper-Threading [11; 12] и использует её в линейках высокопроизводительных серверных и клиентских процессоров, а также в некоторых процессорах Atom с низким энергопотреблением. Другие компании, такие как AMD, IBM, Sun Microsystems, также выпускают чипы с поддержкой одновременной многопоточности. Кроме того, некоторые процессоры компании ARM также поддерживают технологию SMT.

Поддержка технологии одновременной многопоточности требует ряда аппаратных модификаций. Различные аппаратные ресурсы либо реплицируются, либо разделяются, либо используются совместно. В суперскалярном процессоре с внеочередным исполнением инструкций к реплицированным ресурсам относятся, к примеру, программный счётчик (Program Counter, PC), таблица соответствия архитектурных регистров физическим, регистр глобальной истории (Global History Register, GHR) в предсказателе условных переходов, стек адресов возврата (Return Address Stack, RAS). К ресурсам, разделяемым между потоками, относится буфер переупорядочивания. В большинстве случаев он разделяется на независимые части между логическими потоками, либо динамически квотируется между потоками. Удаление инструкций (commit) из каждой части происходит независимо, что позволяет другому потоку продолжать исполнять инструкции, даже если в одном из потоков произошло переполнение буфера переупорядочивания, к примеру, из-за задержек, связанных с промахами в кэш. К аппаратным ресурсам, совместно использующимся потоками, относятся, к примеру, Instruction Queue, физический регистровый файл (Physical Register File, PRF), таблицы истории паттернов (Pattern History Table, PHT) в предсказателе переходов, буфер ассоциативной трансляции (Translation Lookaside Buffer, TLB). Доступные функциональные исполнительные устройства также естественно используются совместно потоками при использовании одновременной многопоточности. Так как часть аппаратных ресурсов процессорного ядра разделяется между потоками или начинает использоваться совместно, производительность одного потока снижается.

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

ограничивается или специально настраивается на уровне операционной системы из-за возможных атак по сторонним каналам (side-channel attacks), один из примеров которых описан в [13].

1.3 Математическая постановка задачи

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

В работе рассматриваются три взаимосвязанные системы. Разработанная система Aira представляет собой систему выявления и трансформации участков последовательной программы, допускающих параллельное исполнение. Разработанная система Relic представляет собой специализированную систему исполнения мелкозернистых задач на SMT-ядре, в которой используются два логических потока одного физического ядра: главный поток и вспомогательный поток. Под главным потоком понимается логический поток, исполняющий основную последовательность инструкций программы и инициирующий отправку мелкозернистой задачи на параллельное исполнение. Под вспомогательным потоком понимается второй логический поток того же физического SMT-ядра, принимающий и исполняющий переданную ему задачу. Разработанная система Pereplut представляет собой систему оценки целесообразности параллелизации найденных и трансформированных участков программы на SMT-ядре.

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

^SMT = /, RSh, {^p}p€ñsh, Wooo, Л mem? Лъг)

— модель целевой вычислительной архитектуры, где:

— Н =2 — число логических потоков одного физического SMT-ядра;

— / — тактовая частота физического ядра;

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

— ц,р > 0 — эффективная пропускная способность ресурса р Е выраженная в единицах работы данного ресурса за такт;

— Wooo — эффективный размер окна внеочередного исполнения;

— Лтет ^ 0 — эффективная дополнительная задержка, связанная с длинным обращением к памяти, выраженная в тактах;

Список литературы диссертационного исследования кандидат наук Лось Денис Андреевич, 2026 год

Список литературы

1. Profiling a warehouse-scale computer [Текст] / S. Kanev [и др.] // 2015 ACM/IEEE 42nd Annual International Symposium on Computer Architecture (ISCA). — 2015. — С. 158—169.

2. Effect of Hyper-Threading in Latency-Critical Multithreaded Cloud Applications and Utilization Analysis of the Major System Resources [Текст] / L. Pons [и др.] // Future Generation Computer Systems. — 2022. — Т. 131. — С. 194—208.

3. Los, D. Exploring Fine-grained Task Parallelism on Simultaneous Multithreading Cores [Текст] / D. Los, I. Petushkov // International Journal of Open Information Technologies. — 2024. — Т. 12, № 10. — С. 144—151.

4. Los, D. Accelerating Latency-Critical Applications with AI-Powered Semi-Automatic Fine-Grained Parallelization on SMT Processors [Текст] / D. Los, I. Petushkov // International Journal of Open Information Technologies. — 2025. — Т. 13, № 9. — С. 129—134.

5. Tomasulo, R. M. An Efficient Algorithm for Exploiting Multiple Arithmetic Units [Текст] / R. M. Tomasulo // IBM Journal of Research and Development. — 1967. — Т. 11, № 1. — С. 25—33.

6. Thornton, J. E. Parallel operation in the control data 6600 [Текст] / J. E. Thornton // Proceedings of the October 27-29, 1964, Fall Joint Computer Conference, Part II: Very High Speed Computer Systems. — 1964. — С. 33—40.

7. Smith, B. J. A pipelined, shared resource MIMD computer [Текст] /

B. J. Smith // Advanced Computer Architecture. — Washington, DC, USA : IEEE Computer Society Press, 1986. — С. 39—41.

8. APRIL: a processor architecture for multiprocessing [Текст] / A. Agarwal [и др.] // SIGARCH Comput. Archit. News. — 1990. — Т. 18, 2SI. —

C. 104—114.

9. A multithreaded PowerPC processor for commercial servers [Текст] / J. M. Borkenhagen [и др.] // IBM Journal of Research and Development. — 2000. — Т. 44, № 6. — С. 885—898.

10. McNairy, C. Montecito: A Dual-Core, Dual-Thread Itanium Processor [Текст] / C. McNairy, R. Bhatia // IEEE Micro. — 2005. — Т. 25, № 2. —

C. 10—20.

11. Hyper-Threading technology architecture and microarchitecture [Текст] /

D. T. Marr [и др.] // Intel Technology Journal. — 2002. — Т. 6, № 1. — С. 4—15.

12. Koufaty, D. Hyperthreading Technology in the Netburst Microarchitecture [Текст] / D. Koufaty, D. T. Marr // IEEE Micro. — 2003. — Т. 23, № 02. — С. 56—65.

13. Port Contention for Fun and Profit [Текст] / A. C. Aldaya [и др.] // 2019 IEEE Symposium on Security and Privacy (SP). — 2019. — С. 870—887.

14. Bernstein, A. J. Analysis of Programs for Parallel Processing [Текст] / A. J. Bernstein // IEEE Transactions on Electronic Computers. — 1966. — Т. EC—15, № 5. — С. 757—763.

15. Menon, R. OpenMP: An Industry-Standard API for Shared-Memory Programming [Текст] / R. Menon, L. Dagum // Computing in Science & Engineering. — 1998. — Т. v, № 01. — С. 46—55.

16. Support for the OpenMP language [Электронный ресурс]. — URL: https: //openmp.llvm.org/ (дата обр. 16.08.2025).

17. Gomp: An openmp implementation for gcc [Электронный ресурс]. — URL: https://gcc.gnu.org/projects/gomp (дата обр. 16.08.2025).

18. Kukanov, A. The Foundations for Scalable Multi-core Software in Intel Threading Building Blocks [Текст] / A. Kukanov, M. J. Voss // Intel Technology Journal. — 2007. — Т. 11, № 4. — С. 309.

19. Cpp-Taskflow: A General-Purpose Parallel Task Programming System at Scale [Текст] / T.-W. Huang [и др.] // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. — 2021. — Т. 40, № 8. — С. 1687—1700.

20. Aldinucci, M. FastFlow: Efficient Parallel Streaming Applications on Multi-core [Текст] / M. Aldinucci, M. Torquati, M. Meneghin. — 2009. — arXiv: 0909.1187 [cs.DC]. — URL: https://arxiv.org/abs/0909.1187.

21. Schardl, T. B. OpenCilk: A Modular and Extensible Software Infrastructure for Fast Task-Parallel Code [Текст] / T. B. Schardl, I.-T. A. Lee // Proceedings of the 28th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming. — 2023. — С. 189—203.

22. OmpSs-2 Specification [Электронный ресурс]. — URL: https://pm.bsc.es/ ftp/ompss-2/doc/spec/ (дата обр. 15.08.2025).

23. Podobas, A. A Comparison of some recent Task-based Parallel Programming Models [Текст] / A. Podobas, M. Brorsson, K.-F. Faxen // 3rd workshop on programmability issues for multi-core computers. — 2010. — С. 1—14.

24. Price, G. W. A comparative analysis of fine-grain threads packages [Текст] / G. W. Price, D. K. Lowenthal //J. Parallel Distrib. Comput. — 2003. — Т. 63, № 11. — С. 1050—1063.

25. Podobas, A. A comparative performance study of common and popular task-centric programming frameworks [Текст] / A. Podobas, M. Brorsson, K.-F. Faxen // Concurr. Comput. Pract. Exper. — 2015. — Т. 27, № 1. — С. 1—28.

26. A comparison of five parallel programming models for C++ [Текст] / E. Ajkunic [и др.] // 2012 Proceedings of the 35th International Convention MIPRO. — 2012. — С. 1780—1784.

27. Executing Optimized Irregular Applications Using Task Graphs within Existing Parallel Models [Текст] / C. D. Krieger [и др.] // 2012 SC Companion: High Performance Computing, Networking Storage and Analysis. — 2012. — С. 261—268.

28. A Comparative Evaluation of Parallel Programming Models for Shared-Memory Architectures [Текст] / L. M. Sanchez [и др.] // 2012 IEEE 10th International Symposium on Parallel and Distributed Processing with Applications. — 2012. — С. 363—370.

29. Salehian, S. Comparison of Threading Programming Models [Текст] / S. Salehian, J. Liu, Y. Yan // 2017 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW). — 2017. — С. 766—774.

30. Jin, H. The OpenMP Implementation of NAS Parallel Benchmarks and Its Performance [Текст] / H. Jin, F. MA // NASA Ames Research Center. Technical Report. — 2000.

31. Exploring the performance limits of simultaneous multithreading for memory intensive applications [Текст] / E. Athanasaki [и др.] // The Journal of Supercomputing. — 2008. — Т. 44. — С. 64—97.

32. An Empirical Study of Hyper-Threading in High Performance Computing Clusters [Текст] / T. Leng [и др.] // Linux HPC Revolution. — 2002. — С. 1—12.

33. Exploring the Capacity of a Modern SMT Architecture to Deliver High Scientific Application Performance [Текст] / E. Athanasaki [и др.] // High Performance Computing and Communications. — 2006. — С. 180—189.

34. Grant, R. E. A Comprehensive Analysis of OpenMP Applications on Dual-Core Intel Xeon SMPs [Текст] / R. E. Grant, A. Afsahi // 2007 IEEE International Parallel and Distributed Processing Symposium. — 2007. — С. 1—8.

35. Effect of Hyper-Threading in Latency-Critical Multithreaded Cloud Applications and Utilization Analysis of the Major System Resources [Текст] / L. Pons [и др.] // Future Generation Computer Systems. — 2022. — Т. 131. — С. 194—208.

36. Automatic SMT threading for OpenMP applications on the Intel Xeon Phi co-processor [Текст] / W. Heirman [и др.] // Proceedings of the 4th International Workshop on Runtime and Operating Systems for Supercomputers. — 2014.

37. Exploring the use of Hyper-Threading technology for multimedia applications with Intel OpenMP compiler [Текст] / X. Tian [и др.] // Proceedings International Parallel and Distributed Processing Symposium. — 2003. — С. 36.1.

38. Chen, Y.-K. Media Applications on Hyper-Threading Technology [Текст] / Y.-K. Chen // Intel Technology Journal. — 2002. — Т. 6, № 1. — С. 1—11.

39. Chen, Y.-K. Video applications on hyper-threading technology [Текст] / Y.-K. Chen, M. Holliman, E. Debes // Proceedings. IEEE International Conference on Multimedia and Expo. Т. 2. — 2002. — С. 193—196.

40. Ivanikovas, S. Evaluation of the hyper-threading technology for heat conduction-type problems [Текст] / S. Ivanikovas, G. Dzemyda // Mathematical Modelling and Analysis. — 2007. — Т. 12, № 4. — С. 459—468.

41. Schone, R. Simultaneous multithreading on x86-64 systems an energy efficiency evaluation [Текст] / R. Schone, D. Hackenberg, D. Molka // Proceedings of the 4th Workshop on Power-Aware Computing and Systems. — 2011. — С. 1—5.

42. SPEComp: A New Benchmark Suite for Measuring Parallel Computer Performance [Текст] / V. Aslot [и др.] // OpenMP Shared Memory Parallel Programming. — Springer Berlin Heidelberg, 2001. — С. 1—10.

43. Henning, J. L. SPEC CPU2006 benchmark descriptions [Текст] / J. L. Henning // SIGARCH Comput. Archit. News. — 2006. — Т. 34, № 4. —

C. 1—17.

44. Early performance evaluation of a "Nehalem"cluster using scientific and engineering applications [Текст] / S. Saini [и др.] // Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis. — 2009.

45. Beamer, S. The GAP Benchmark Suite [Текст] / S. Beamer, K. Asanovic,

D. Patterson. — 2017. — arXiv: 1508.03619 [cs.DC]. — URL: https://arxiv. org/abs/1508.03619.

46. JSON Example [Электронный ресурс]. — URL: https://json.org/example. html (дата обр. 16.08.2025).

47. RapidJSON: A fast JSON parser/generator for C++ with both SAX/DOM style API [Электронный ресурс]. — URL: https://rapidjson.org (дата обр. 16.08.2025).

48. Optimizing Fine-Grained Parallelism Through Dynamic Load Balancing on Multi-Socket Many-Core Systems [Текст] / W. Wang [и др.] // 2025 IEEE International Parallel and Distributed Processing Symposium (IPDPS). — 2025. — С. 81—93.

49. Speculative precomputation: long-range prefetching of delinquentloads [Текст] / J. Collins [и др.] // Proceedings 28th Annual International Symposium on Computer Architecture. — 2001. — С. 14—25.

50. Supporting fine-grained synchronization on a simultaneous multithreading processor [Текст] / D. Tullsen [и др.] // Proceedings Fifth International Symposium on High-Performance Computer Architecture. — 1999. — С. 54—58.

51. Anastopoulos, N. Facilitating efficient synchronization of asymmetric threads on hyper-threaded processors [Текст] / N. Anastopoulos, N. Koziris // 2008 IEEE International Symposium on Parallel and Distributed Processing. — 2008. — С. 1—8.

52. Kihm, J. Implementation of fine-grained cache monitoring for improved SMT scheduling [Текст] / J. Kihm, D. Connors // IEEE International Conference on Computer Design: VLSI in Computers and Processors, 2004. ICCD 2004. Proceedings. — 2004. — С. 326—331.

53. Redstone, J. Mini-threads: increasing TLP on small-scale SMT processors [Текст] / J. Redstone, S. Eggers, H. Levy // The Ninth International Symposium on High-Performance Computer Architecture, 2003. HPCA-9 2003. Proceedings. — 2003. — С. 19—30.

54. Nookala, P. X-OpenMP — eXtreme fine-grained tasking using lock-less work stealing [Текст] / P. Nookala, K. Chard, I. Raicu // Future Generation Computer Systems. — 2024. — Т. 159. — С. 444—458.

55. Faxén, K.-F. Wool-A work stealing library [Текст] / K.-F. Faxen // SIGARCH Comput. Archit. News. — 2009. — Т. 36, № 5. — С. 93—100.

56. SAM: Optimizing Multithreaded Cores for Speculative Parallelism [Текст] / M. Abeydeera [и др.] // 2017 26th International Conference on Parallel Architectures and Compilation Techniques (PACT). — 2017. — С. 64—78.

57. Evaluation of Linux Scheduler Algorithms for Low Latency [Электронный ресурс]. — URL: http://liu.diva-portal.org/smash/get/diva2%3A1884324/ FULLTEXT01.pdf (дата обр. 15.08.2025).

58. Designing a Thread Pipeline for optimal database throughput [Электронный ресурс]. — URL: https://www.rondb.com/post/designing-a-thread-pipeline-for-optimal-database-throughput (дата обр. 15.08.2025).

59. Arachne: core-aware thread management [Текст] / H. Qin [и др.] // Proceedings of the 13th USENIX Conference on Operating Systems Design and Implementation. — 2018. — С. 145—160.

60. A survey of scheduler benchmarks [Электронный ресурс]. — URL: https: //lwn.net/Articles/725238/ (дата обр. 15.08.2025).

61. Analysis of Work Stealing with latency [Текст] / N. Gast [и др.] // Journal of Parallel and Distributed Computing. — 2021. — Т. 153. — С. 119—129.

62. A new analysis of Work Stealing with latency [Текст] / N. Gast [и др.] // CoRR. — 2018. — Т. abs/1805.00857. — arXiv: 1805.00857. — URL: http: //arxiv.org/abs/1805.00857.

63. Boost.Lockfree [Электронный ресурс]. — URL: https://www.boost.org/ doc/libs/1_85_0/doc/html/lockfree.html (дата обр. 20.07.2025).

64. HaPPy: hyperthread-aware power profiling dynamically [Текст] / Y. Zhai [и др.] // Proceedings of the 2014 USENIX Conference on USENIX Annual Technical Conference. — Philadelphia, PA : USENIX Association, 2014. — С. 211—218. — (USENIX ATC'14).

65. Futex —fast user-space locking [Электронный ресурс]. — URL: https:// www.man7.org/linux/man-pages/man2/futex.2.html (дата обр. 15.08.2025).

66. Perfetto: System profiling, app tracing and trace analysis [Электронный ресурс]. — URL: https://perfetto.dev/ (дата обр. 15.08.2025).

67. Norouzi, M. Enhancing the Speed and Automation of Assisted Parallelization [Текст] : PhD thesis / Norouzi Mohammad. — Technische Universität Darmstadt, 2022.

68. Huda, Z. ul. Identification of Suitable Parallelization Patterns for Sequential Programs [Текст] : PhD thesis / ul Huda Zia. — Technische Universität Darmstadt, 2021.

69. Li, Z. Discovery of Potential Parallelism in Sequential Programs [Текст] : PhD thesis / Li Zhen. — Technische Universität Darmstadt, 2016.

70. Mustafa, D. A Survey of Performance Tuning Techniques and Tools for Parallel Applications [Текст] / D. Mustafa // IEEE Access. — 2022. — Т. 10. — С. 15036—15055.

71. OMPar: Automatic Parallelization with AI-Driven Source-to-Source Compilation [Текст] / T. Kadosh [и др.]. — 2024. — arXiv: 2409.14771 [cs.CL]. — URL: https://arxiv.org/abs/2409.14771.

72. Zhou, R. Guided Automatic Binary Parallelisation [Текст] : PhD thesis / Zhou Ruoyu. — Apollo - University of Cambridge Repository, 2018.

73. Frama-C: A software analysis perspective [Текст] / F. Kirchner [и др.] // Formal Aspects of Computing. — 2015. — Т. 27, № 3. — С. 573—609.

74. Aristotle a system for development of program analysis based tools [Текст] / M. J. Harrold [и др.] // Proceedings of the 33rd Annual ACM Southeast Conference. — 1995. — С. 110—119.

75. DMS® Software Reengineering Toolkit™ [Электронный ресурс]. — URL: https : / / www . semanticdesigns . com / Products / DMS / DMSToolkit. html (дата обр. 20.07.2025).

76. Grosser, T. Polly — performing polyhedral optimizations on a low-level intermediate representation [Текст] / T. Grosser, A. Groesslinger, C. Lengauer // Parallel Processing Letters. — 2012. — Т. 22, № 04. —

C. 1250010.

77. GRAPHITE: Polyhedral analyses and optimizations for GCC [Текст] / S. Pop [и др.] // Proceedings of the GCC Developers' Summit 2006. — 2006.

78. Loechner, V. Parameterized polyhedra and their vertices [Текст] / V. Loechner, D. K. Wilde // Int. J. Parallel Program. — 1997. — Т. 25, № 6. — С. 525—549.

79. Pugh, W. Static analysis of upper and lower bounds on dependences and parallelism [Текст] / W. Pugh, D. Wonnacott // ACM Trans. Program. Lang. Syst. — 1994. — Т. 16, № 4. — С. 1248—1278.

80. Semantic-Aware Automatic Parallelization of Modern Applications Using High-Level Abstractions [Текст] / C. Liao [и др.] // International Journal of Parallel Programming. — 2010. — Т. 38. — С. 361—378.

81. Quinlan, D. ROSE: compiler support for object-oriented frameworks [Текст] /

D. Quinlan // Parallel Processing Letters. — 2000. — Т. 10, 02n03. — С. 215—226.

82. Rauchwerger, L. The LRPD test: speculative run-time parallelization of loops with privatization and reduction parallelization [Текст] / L. Rauchwerger, D. Padua // Proceedings of the ACM SIGPLAN 1995 Conference on Programming Language Design and Implementation. — 1995. — С. 218—232. — URL: https://doi.org/10.1145/207110.207148.

83. Par4All: From Convex Array Regions to Heterogeneous Computing [Текст] / M. Amini [и др.] // Second International Workshop on Polyhedral Compilation Techniques. — 2012.

84. Adapting the polyhedral model as a framework for efficient speculative parallelization [Текст] / A. Jimborean [и др.] // Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. — 2012. — С. 295—296.

85. VMAD: An Advanced Dynamic Program Analysis and Instrumentation Framework [Текст] / A. Jimborean [и др.] // Compiler Construction / под ред. M. O'Boyle. — Springer Berlin Heidelberg, 2012. — С. 220—239.

86. Dynamic and Speculative Polyhedral Parallelization Using Compiler-Generated Skeletons [Текст] / A. Jimborean [и др.] // Int. J. Parallel Program. — 2014. — Т. 42, № 4. — С. 529—545.

87. Automatic Transformations for Communication-Minimized Parallelization and Locality Optimization in the Polyhedral Model [Текст] / U. Bondhugula [и др.] // Compiler Construction. — Springer Berlin Heidelberg, 2008. — С. 132—146.

88. A practical automatic polyhedral parallelizer and locality optimizer [Текст] / U. Bondhugula [и др.] // SIGPLAN Not. — 2008. — Т. 43, № 6. — С. 101—113.

89. Lee, S.-I. Cetus - An Extensible Compiler Infrastructure for Source-to-Source Transformation [Текст] / S.-I. Lee, T. A. Johnson, R. Eigenmann // Languages and Compilers for Parallel Computing. — Springer Berlin Heidelberg, 2004. — С. 539—553.

90. Norouzi, M. Automatic construct selection and variable classification in OpenMP [Текст] / M. Norouzi, F. Wolf, A. Jannesari // Proceedings of the ACM International Conference on Supercomputing (ICS '19). — 2019. — С. 330—341.

91. Ketterlin, A. Profiling Data-Dependence to Assist Parallelization: Framework, Scope, and Optimization [Текст] / A. Ketterlin, P. Clauss // 2012 45th Annual IEEE/ACM International Symposium on Microarchitecture. — 2012. — С. 437—448.

92. Automatic Exploration of Potential Parallelism in Sequential Applications [Текст] / V. Subotic [и др.] // Supercomputing / под ред. J. M. Kunkel, T. Ludwig, H. W. Meuer. — Springer International Publishing, 2014. — С. 156—171.

93. Zhang, X. Alchemist: A Transparent Dependence Distance Profiling Infrastructure [Текст] / X. Zhang, A. Navabi, S. Jagannathan // Proceedings of the 7th Annual IEEE/ACM International Symposium on Code Generation and Optimization. — 2009. — С. 47—58.

94. Kremlin: rethinking and rebooting gprof for the multicore age [Текст] / S. Garcia [и др.] // Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation. — 2011. — С. 458—469.

95. Attention Is All You Need [Текст] / A. Vaswani [и др.] // CoRR. — 2017. — Т. abs/1706.03762. — arXiv: 1706.03762. — URL: http://arxiv.org/abs/1706. 03762.

96. Predicting Parallelization of Sequential Programs Using Supervised Learning [Текст] / D. Fried [и др.] // 2013 12th International Conference on Machine Learning and Applications. Т. 2. — 2013. — С. 72—77.

97. Towards a holistic approach to auto-parallelization: integrating profile-driven parallelism detection and machine-learning based mapping [Текст] / G. Tournavitis [и др.] // SIGPLAN Not. — 2009. — Т. 44, № 6. — С. 177—187.

98. Freund, Y. A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting [Текст] / Y. Freund, R. E. Schapire // Journal of Computer and System Sciences. — 1997. — Т. 55, № 1. — С. 119—139.

99. PragFormer: Data-Driven Parallel Source Code Classification with Transformers [Текст] / R. Harel [и др.] // Int. J. Parallel Program. — 2024. — Окт. — Т. 53, № 1.

100. DeepSCC: Source Code Classification Based on Fine-Tuned RoBERTa [Текст] / G. Yang [и др.] // CoRR. — 2021. — Т. abs/2110.00914. — arXiv: 2110.00914. — URL: https://arxiv.org/abs/2110.00914.

101. ComPar: Optimized Multi-compiler for Automatic OpenMP S2S Parallelization [Текст] / I. Mosseri [и др.] // OpenMP: Portable Multi-Level Parallelism on Modern Systems: 16th International Workshop on OpenMP, IWOMP 2020, Austin, TX, USA, September 22-24, 2020, Proceedings. — 2020. — С. 247—262.

102. OpenAI: OpenAI ChatGPT [Электронный ресурс]. — URL: https://openai. com/index/chatgpt/ (дата обр. 15.08.2025).

103. Learning to Parallelize with OpenMP by Augmented Heterogeneous AST Representation [Текст] / L. Chen [и др.]. — 2023. — arXiv: 2305.05779 [cs.LG]. — URL: https://arxiv.org/abs/2305.05779.

104. Advising OpenMP Parallelization via A Graph-Based Approach with Transformers [Текст] / T. Kadosh [и др.] // OpenMP: Advanced Task-Based, Device and Compiler Programming: 19th International Workshop on OpenMP, IWOMP 2023, Bristol, UK, September 13-15, 2023, Proceedings. — 2023. — С. 3—17.

105. GraphCodeBERT: Pre-training Code Representations with Data Flow [Текст] / D. Guo [и др.] // CoRR. — 2020. — Т. abs/2009.08366. — arXiv: 2009.08366. — URL: https://arxiv.org/abs/2009.08366.

106. Polybench [Электронный ресурс]. — URL: https://web.cse.ohio-state.edu/ ~pouchet.2/software/polybench/ (дата обр. 15.08.2025).

107. LM4HPC: Towards Effective Language Model Application in High-Performance Computing [Текст] / L. Chen [и др.] // OpenMP: Advanced Task-Based, Device and Compiler Programming / под ред. S. McIntosh-Smith [и др.]. — Springer Nature Switzerland, 2023. — С. 18—33.

108. LangChain [Электронный ресурс]. — URL: www.langchain.com (дата обр. 15.08.2025).

109. Evaluation of OpenAI Codex for HPC Parallel Programming Models Kernel Generation [Текст] / W. Godoy [и др.] // Proceedings of the 52nd International Conference on Parallel Processing Workshops. — 2023. — С. 136—144.

110. Github Copilot [Электронный ресурс]. — URL: https:/ /github.com/ features/copilot (дата обр. 15.08.2025).

111. Comparing Llama-2 and GPT-3 LLMs for HPC kernels generation [Текст] / P. Valero-Lara [и др.]. — 2023. — arXiv: 2309.07103 [cs.SE]. — URL: https: //arxiv.org/abs/2309.07103.

112. AutoParLLM: GNN-guided Context Generation for Zero-Shot Code Parallelization using LLMs [Текст] / Q. I. Mahmud [и др.]. — 2025. — arXiv: 2310.04047 [cs.LG]. — URL: https://arxiv.org/abs/2310.04047.

113. Rodinia: A benchmark suite for heterogeneous computing [Текст] / S. Che [и др.] // 2009 IEEE International Symposium on Workload Characterization (IISWC). — 2009. — С. 44—54.

114. Parallelizable Loop Detection using Pre-trained Transformer Models for Code Understanding [Текст] / S. Pornmaneerattanatri [и др.] // Parallel and Distributed Computing, Applications and Technologies / под ред. J. S. Park [и др.]. — Springer Nature Singapore, 2024. — С. 32—42.

115. CodeT5: Identifier-aware Unified Pre-trained Encoder-Decoder Models for Code Understanding and Generation [Текст] / Y. Wang [и др.] // Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing / под ред. M.-F. Moens [и др.]. — Association for Computational Linguistics, 2021. — С. 8696—8708.

116. GitHub [Электронный ресурс]. — URL: https://github.com (дата обр. 15.08.2025).

117. MonoCoder: Domain-Specific Code Language Model for HPC Codes and Tasks [Текст] / T. Kadosh [и др.]. — 2024. — arXiv: 2312.13322 [cs.PL]. — URL: https://arxiv.org/abs/2312.13322.

118. Can Large Language Models Write Parallel Code? [Текст] / D. Nichols [и др.] // Proceedings of the 33rd International Symposium on High-Performance Parallel and Distributed Computing. — ACM, 2024. — С. 281—294.

119. OMPGPT: A Generative Pre-trained Transformer Model for OpenMP [Текст] / L. Chen [и др.] // Euro-Par 2024: Parallel Processing / под ред. J. Carretero [и др.]. — Springer Nature Switzerland, 2024. — С. 121—134.

120. Chain-of-thought prompting elicits reasoning in large language models [Текст] / J. Wei [и др.] // Proceedings of the 36th International Conference on Neural Information Processing Systems. — 2022.

121. Romero Rosas, M. A. Should AI Optimize Your Code? A Comparative Study of Classical Optimizing Compilers Versus Current Large Language Models [Текст] / M. A. Romero Rosas, M. A. Torres Sanchez, R. Eigenmann //. — 2025. — С. 22—29.

122. ConTraPh: Contrastive Learning for Parallelization and Performance Optimization [Текст] / Q. I. Mahmud [и др.] // Proceedings of the 39th ACM International Conference on Supercomputing. — 2025. — С. 596—610.

123. Cursor The AI Code Editor [Электронный ресурс]. — URL: https://cursor. com (дата обр. 15.08.2025).

124. Claude Code [Электронный ресурс]. — URL: https://claude.com/product/ claude-code (дата обр. 16.08.2025).

125. Introducing Codex [Электронный ресурс]. — URL: https://openai.com/ index/introducing-codex/ (дата обр. 16.08.2025).

126. Compilable Neural Code Generation with Compiler Feedback [Текст] / X. Wang [и др.]. — 2022. — arXiv: 2203.05132 [cs.CL]. — URL: https: //arxiv.org/abs/2203.05132.

127. OpenAI GPT-5 [Электронный ресурс]. — URL: https://openai.com/gpt-5/ (дата обр. 15.08.2025).

128. BOLT: A Practical Binary Optimizer for Data Centers and Beyond [Текст] / M. Panchenko [и др.]. — 2018. — arXiv: 1807.06735 [cs.PL]. — URL: https: //arxiv.org/abs/1807.06735.

129. Potvin, R. Why Google stores billions of lines of code in a single repository [Текст] / R. Potvin, J. Levenberg // Commun. ACM. — 2016. — Т. 59, № 7. — С. 78—87.

130. Chen, D. AutoFDO: Automatic feedback-directed optimization for warehouse-scale applications [Текст] / D. Chen, D. X. Li, T. Moseley // Proceedings of the 2016 International Symposium on Code Generation and Optimization. — 2016. — С. 12—23.

131. Revamping Sampling-Based PGO with Context-Sensitivity and Pseudo-instrumentation [Текст] / W. He [и др.] // 2024 IEEE/ACM International Symposium on Code Generation and Optimization (CGO). — 2024. — С. 322—333.

132. Abdullah, W. M. P4OMP: Retrieval-Augmented Prompting for OpenMP Parallelism in Serial Code [Текст] / W. M. Abdullah, A. Kabir // CoRR. — 2025. — Т. abs/2506.22703. — arXiv: 2506.22703. — URL: https://doi.org/ 10.48550/arXiv.2506.22703.

133. StackOverflow [Электронный ресурс]. — URL: https://stackoverflow.com (дата обр. 15.08.2025).

134. Meyer, U. Д-stepping: a parallelizable shortest path algorithm [Текст] / U. Meyer, P. Sanders // Journal of Algorithms. — 2003. — Т. 49, № 1. — С. 114—152.

135. HeCBench [Электронный ресурс]. — URL: https://github.com/zjin-lcf/ HeCBench (дата обр. 16.08.2025).

136. Mendonga, G. S. D. AutoParBench: a unified test framework for OpenMP-based parallelizers [Текст] / G. S. D. Mendonca, C. Liao, F. M. Q. Pereira // Proceedings of the 34th ACM International Conference on Supercomputing. — Barcelona, Spain : Association for Computing Machinery, 2020. — (ICS '20).

137. Introducing Claude Sonnet 4 [Электронный ресурс]. — URL: https://www. anthropic.com/news/claude-4 (дата обр. 16.08.2025).

138. Grok 4 [Электронный ресурс]. — URL: https://x.ai/news/grok-4 (дата обр. 16.08.2025).

139. GigaChat 2 Max [Электронный ресурс]. — URL: https://developers.sber. ru/docs/ru/gigachat/models/gigachat-2-max (дата обр. 16.08.2025).

140. Хайдари, Ф. Г. Аналитическая система оптимизации трасс исполнения для исследования программной предподкачки данных [Текст] / Ф. Г. Хайдари, Д. А. Лось, И. В. Петушков // Труды 66-й Всероссийской научной конференции МФТИ. Радиотехника и компьютерные технологии. — 2024. — С. 27—28.

141. Model Context Protocol [Электронный ресурс]. — URL: https : / / modelcontextprotocol.io/docs/getting-started/intro (дата обр. 15.08.2025).

142. FastMCP [Электронный ресурс]. — URL: https://gofastmcp.com/getting-started/welcome (дата обр. 15.08.2025).

143. Bruening, D. An infrastructure for adaptive dynamic optimization [Текст] / D. Bruening, T. Garnett, S. Amarasinghe // International Symposium on Code Generation and Optimization, 2003. CGO 2003. — 2003. — С. 265—275.

144. Лисицын, С. А. Сбор профильной информации с помощью трасс исполнения приложения для статической оптимизирующей бинарной трансляции [Текст] / С. А. Лисицын // Современные информационные технологии и ИТ-образование. — 2021. — Т. 17, № 2. — С. 369—378.

145. Лисицын, С. А. Исследование влияния бинарных оптимизаций на модификацию таблиц переходов в архитектуре ARM [Текст] / С. А. Лисицын, Д. А. Колобаев // Труды 65-й Всероссийской научной конференции МФТИ. Радиотехника и компьютерные технологии. — 2023. — С. 22—23.

146. Лисицын, С. А. Изучение проблем статической двоичной трансляции под RISC архитектуры [Текст] / С. А. Лисицын // Труды 63-й Всероссийской научной конференции МФТИ. Радиотехника и компьютерные технологии. — 2020. — С. 12.

147. Лисицын, С. А. Верификация статической двоичной оптимизирующей трансляции под RISC архитектуры [Текст] / С. А. Лисицын, А. А. Шурыгин // Труды 64-й Всероссийской научной конференции МФТИ. Радиотехника и компьютерные технологии. — 2021. — С. 33—34.

148. The Championship Simulator: Architectural Simulation for Education and Competition [Текст] / N. Gober [и др.]. — 2022. — arXiv: 2210.14324 [cs.AR]. — URL: https://arxiv.org/abs/2210.14324.

149. An Evaluation of High-Level Mechanistic Core Models [Текст] / T. E. Carlson [и др.] // ACM Trans. Archit. Code Optim. — 2014. — Т. 11, № 3.

150. The gem5 Simulator: Version 20.0+ [Текст] / J. Lowe-Power [и др.]. — 2020. — arXiv: 2007.03152 [cs.AR]. — URL: https://arxiv.org/abs/2007.03152.

Список рисунков

1.1 Прирост производительности при мелкозернистой параллелизации на SMT-ядре с различными технологиями параллельного программирования для бенчмарка BC.................. 41

1.2 Прирост производительности при мелкозернистой параллелизации на SMT-ядре с различными технологиями параллельного программирования для бенчмарка BFS................. 41

1.3 Прирост производительности при мелкозернистой параллелизации на SMT-ядре с различными технологиями параллельного программирования для бенчмарка CC .................. 42

1.4 Прирост производительности при мелкозернистой параллелизации на SMT-ядре с различными технологиями параллельного программирования для бенчмарка PR.................. 42

1.5 Прирост производительности при мелкозернистой параллелизации на SMT-ядре с различными технологиями параллельного программирования для бенчмарка SSSP ................ 43

1.6 Прирост производительности при мелкозернистой параллелизации на SMT-ядре с различными технологиями параллельного программирования для бенчмарка TC .................. 44

2.1 Иллюстрация использования технологии OpenMP совместно со

специализированной системой параллельного программирования Relic 51

2.2 Прирост производительности при мелкозернистой параллелизации на SMT-ядре с системой параллельного программирования Relic

для бенчмарка BC............................. 58

2.3 Прирост производительности при мелкозернистой параллелизации на SMT-ядре с системой параллельного программирования Relic

для бенчмарка BFS............................ 59

2.4 Прирост производительности при мелкозернистой параллелизации на SMT-ядре с системой параллельного программирования Relic

для бенчмарка CC ............................. 59

2.5 Прирост производительности при мелкозернистой параллелизации на SMT-ядре с системой параллельного программирования Relic

для бенчмарка PR ............................. 60

2.6 Прирост производительности при мелкозернистой параллелизации на SMT-ядре с системой параллельного программирования Relic

для бенчмарка SSSP ............................ 60

2.7 Прирост производительности при мелкозернистой параллелизации на SMT-ядре с системой параллельного программирования Relic

для бенчмарка TC ............................. 61

2.8 Приросты производительности при мелкозернистой параллелизации на SMT-ядре с различными технологиями параллельного программирования для графовых бенчмарков с входным графом Кронекера с 8 вершинами и бенчмарка JSON ... 62

2.9 Среднегеометрические приросты производительности (без негативных случаев) при мелкозернистой параллелизации на SMT-ядре с различными технологиями параллельного программирования для графовых бенчмарков с входным графом Кронекера с 8 вершинами и бенчмарка JSON .............. 63

2.10 Приросты производительности при мелкозернистой параллелизации на SMT-ядре с различными технологиями параллельного программирования для графовых бенчмарков с входным графом Кронекера с 16 вершинами и бенчмарка JSON ... 63

2.11 Среднегеометрические приросты производительности (без негативных случаев) при мелкозернистой параллелизации на SMT-ядре с различными технологиями параллельного программирования для графовых бенчмарков с входным графом Кронекера с 16 вершинами и бенчмарка JSON............. 64

2.12 Приросты производительности при мелкозернистой параллелизации на SMT-ядре с различными технологиями параллельного программирования для графовых бенчмарков с входным графом Кронекера с 32 вершинами и бенчмарка JSON . . . 64

2.13 Среднегеометрические приросты производительности (без негативных случаев) при мелкозернистой параллелизации на БМТ-ядре с различными технологиями параллельного программирования для графовых бенчмарков с входным графом Кронекера с 32 вершинами и бенчмарка ЛБОК............. 65

2.14 Прирост производительности при мелкозернистой параллелизации на БМТ-ядре и двух различных физических ядрах с различными технологиями параллельного программирования для бенчмарка ВС . 67

2.15 Прирост производительности при мелкозернистой параллелизации на БМТ-ядре и двух различных физических ядрах с различными технологиями параллельного программирования для бенчмарка ВЕБ 68

2.16 Прирост производительности при мелкозернистой параллелизации на БМТ-ядре и двух различных физических ядрах с различными технологиями параллельного программирования для бенчмарка СС . 68

2.17 Прирост производительности при мелкозернистой параллелизации на БМТ-ядре и двух различных физических ядрах с различными технологиями параллельного программирования для бенчмарка РЯ . 69

2.18 Прирост производительности при мелкозернистой параллелизации на БМТ-ядре с различными технологиями параллельного программирования для бенчмарка ЗЯБР ................ 69

2.19 Прирост производительности при мелкозернистой параллелизации на БМТ-ядре и двух различных физических ядрах с различными технологиями параллельного программирования для бенчмарка ТС . 70

3.1 Ответ на запрос о параллелизации цикла из листинга 3.1, сформированный моделью СЬа1СРТ-5 [127] в автоматическом

режиме в 2025 году............................ 99

3.2 Ответ на запрос о параллелизации цикла из листинга 3.3, сформированный моделью СЬа1СРТ-5 [127] в автоматическом

режиме в 2025 году............................100

3.3 Ответ на запрос о параллелизации цикла из листинга 3.4, сформированный моделью СЬа1СРТ-5 [127] в автоматическом режиме в 2025 году при предоставлении информации о динамических зависимостях ....................... 101

3.4 Ответ на запрос о параллелизации цикла из листинга 3.4,

сформированный моделью ChatGPT-5 [127] в автоматическом режиме в 2025 году при предоставлении определений функций в качестве контекста.............................102

4.1 Архитектура системы параллелизации последовательных программ Aira.....................................110

4.2 Пример описания MCP-сервера в «mcp.json» для подключения инструментов Aira к LLM-агенту в ИИ-редакторе Cursor.......111

4.3 Иллюстрация алгоритма работы системы Aira.............114

4.4 Схема работы динамического анализа в системе Aira.........125

4.5 Схема работы аналитической системы Pereplut [140]..........133

5.1 Прирост производительности при параллелизации критичных к задержке приложений с помощью системы параллелизации Aira и системы параллельного программирования Relic............144

5.2 Ухудшение производительности при параллелизации критичных к задержке приложений с помощью системы параллелизации Aira и системы параллельного программирования Relic............145

5.3 Прирост производительности при параллелизации критичных к задержке приложений с помощью OpenMP (LLVM) для параллельных участков кода, найденных системой Aira........146

Список таблиц

1 Сводные результаты выявления потенциально параллельных

циклов на наборе бенчмарков РагаБеш.................106

2 Результаты выявления потенциально параллельных циклов на РагаБеш для «статической» категории .................107

3 Результаты выявления потенциально параллельных циклов на РагаБеш для «динамической» категории ................107

4 Результаты выявления потенциально параллельных циклов на РагаБеш для «семантической» категории................107

5 Таблица с общими результатами выявления потенциальных

параллельных циклов с системой Aira на наборе бенчмарков ParaSem 129

6 Таблица с результатами выявления потенциальных параллельных циклов с системой Aira на наборе бенчмарков ParaSem для «статической» категории ......................... 129

7 Таблица с результатами выявления потенциальных параллельных циклов с системой Aira на наборе бенчмарков ParaSem для «динамической» категории........................129

8 Таблица с результатами выявления потенциальных параллельных циклов с системой Aira на наборе бенчмарков ParaSem для «семантической» категории........................130

9 Сравнение точности определения целесообразности от мелкозернистой параллелизации на SMT-ядрах с помощью Pereplut

и модели Claude Sonnet 4.........................139

Приложение А

Примеры сложных случаев параллелизации программ с помощью

модели GPT-5 Thinking

Листинг А.1: Исходный код функции поиска в графе кратчайшего пути от начальной вершины до остальных, преставленной в листинге 3.5, после оптимизиции GPT-5 Thinking моделью

std::vector<int> dijkstra(int source) {

// Parallel delta -st epping SSSP (non-negative weights) const int numVertices = vertices; if (source <0 || source >= numVertices) {

5 return std::vector<int>() ;

}

// Choose delta heuristically as average edge weight (>=1) long long sumWeights = 0; 10 long long edgeCount = 0;

for (int u = 0; u < numVertices; ++u) {

for (const Edge& e : adjacencyList[u]) { sumWeights += e.weight; edgeCount += 1 ;

15 }

}

int delta = 1; if ( edgeCount > 0) {

long long avg = sumWeights / edgeCount; if (avg >= 1) delta = static_cast<int>(avg);

}

// Atomic distances for thread - safe relaxations std: : vector<std: :atomic<int>> dist(numVertices) ; 25 for (int i = 0; i < numVertices; ++i) {

dist [i] .store(INT_MAX, std: :memory_order_relaxed) ;

}

dist [source] .store (0 , std: :memory_order_relaxed) ;

30 // Work buckets

std: : vector<std: : vector<int>> buckets(1) ; buckets [0] .push_back(source) ;

40

45

50

55

60

65

70

int currentBucket = 0;

std::vector<int> S; S.reserve (1024) ;

while (true) {

// Find next non-empty bucket

while (currentBucket < (int)buckets.size ()

&& buckets[currentBucket].empty()) { currentBucket++;

}

if (currentBucket >= (int)buckets.size ()) break; S.clear () ;

while (! buckets[currentBucket].empty ()) { std::vector<int> R; R.swap(buckets[currentBucket]);

// Accumulate processed vertices for heavy-edge phase S . insert (S . end () , R.begin(), R.end());

const int Rsize = (int)R.size () ; const int numThreads = omp_get_max_threads () ; std: :vector<std : :vector<int>> threadLocalNext ( numThreads

);

#pragma omp parallel {

const int tid = omp_get_thread_num();

std::vector<int>& localNext = threadLocalNext [tid] ;

localNext.reserve (64) ;

#pragma omp for schedule(dynamic, 64) for (int idx = 0; idx < Rsize; ++idx) { int u = R [ idx] ;

int du = dist[u].load(std::memory_order_relaxed); for (const Edge& edge : adjacencyList[u]) { if (edge.weight <= delta) {

int v = edge.destination; int alt = (du == INT_MAX)

? INT_MAX : du + edge.weight;

85

90

95

100

105

110

}

if (alt < 0) alt = INT_MAX; int old =

dist [v] .load(std: :memory_order_relaxed) ; bool updated = false; while (alt < old) {

if (dist[v] .compare_exchange_weak ( old , alt ,

std::memory_order_rel axed)) { updated = true; break;

}

} if

(updated) { localNext.push_back(v);

}

size_t totalNew = 0;

for (const auto& vec : threadLocalNext)

totalNew += vec.size(); if (totalNew) {

std::vector<int>& B = buckets [currentBucket] ; B.reserve(B.size () + (size_t)totalNew); for (auto& vec : threadLocalNext) { B.insert(B.end() ,

vec.begin() ,

vec.end ()) ;

}

}

(int)S.size () ;

const int Ssize if (Ssize) {

const int numThreads = omp_get_max_threads () ; std: :vector<std : :vector<std : :pair<int , int>>> threadLocallnserts(numThreads);

}

}

}

}

#pragma omp parallel

125

130

135

140

145

150

155

const int tid = omp_get_thread_num(); auto& inserts =

threadLocallnserts[tid]; inserts.reserve (64) ;

#pragma omp for schedule(dynamic, 64) for (int idx = 0; idx < Ssize; ++idx) { int u = S [ idx] ;

int du = dist[u].load(std::memory_order_relaxed); for (const Edge& edge : adjacencyList[u]) { if (edge.weight > delta) {

int v = edge.destination; int alt = (du == INT_MAX)

? INT_MAX : du + edge.weight; if (alt < 0) alt = INT_MAX;

i nt o l d =

dist [v] .load(std: :memory_order_relaxed) ; bool updated = false; while (alt < old) {

if (dist [v] .compare_exchange_weak( old , alt ,

std::memory_order_relaxed)) { updated = true; break;

}

}

if (updated && alt != INT_MAX) {

int bucketIndex = alt / delta; inserts.emplace_back(bucketIndex, v);

}

}

// Merge inserts to global buckets (resize once) int maxIdx = (int)buckets.size() - 1; for (auto& vec : threadLocalInserts) { for (auto& p : vec) {

if (p.first > maxIdx) maxIdx = p.first;

{

}

}

}

}

}

if (maxIdx >= (int)buckets.size ()) {

165 buckets.resize(maxIdx + 1);

}

for (auto& vec : threadLocallnserts) { for (auto& p : vec) {

buckets [p.first] .push_back(p.second) ;

170 }

}

}

currentBucket++;

175 }

// Produce result distances

std::vector<int> result(numVertices);

for (int i = 0; i < numVertices; ++i) {

result [i] = dist [i] .load(std::memory_order_rel axed) ;

}

return result;

}

Приложение Б

Семантические запросы для различных паттернов в методе семантического анализа в системе параллелизации последовательных программ Aira

Для паттерна FOLD генерируются следующие 6 семантических запросов UPDATE_code:

@codebase At file:line there is a loop that folds an accumulator of type acc_type using one or more variables acc_vars over per-element contributions of type elem_type. The loop has been classified as a FOLD pattern. Please locate the implementation(s) of the function(s) that perform the per-element accumulator update for this loop. These are likely functions or methods named callee_names, or inline logic in the loop body where the accumulator acc_vars is updated as acc — F(acc, expr) or acc +— expr.

Return the full code body (signature + body) of the most relevant implementation(s) actually used at this callsite, along with any nearby comments. Focus on the accumulator update logic, not unrelated utility code.

UPDATE_docs:

@codebase For the accumulator update used in the FOLD loop at file:line (involving accumulator(s) acc_vars and function(s) callee_names if named), show any documentation, comments, or test descriptions that explain what this accumulator computes (for example, sum, min/max, checksum, hash, rolling checksum, streaming checksum, etc.).

Prefer documentation, comments, and test descriptions over raw implementation code. If possible, include only the most relevant snippets.

COMBINE_code:

@codebase Show any function in this codebase that combines or merges partial acc_type accumulator results for the same operation used at

file:line. For example, a function like combine(left, right, lengthRight) or similar, which corresponds to concatenating two processed segments or merging chunk results.

Return the single most relevant function signature + body, along with any nearby comments explaining how it merges partial accumulators

COMBINE_docs:

@codebase Show documentation, comments, or tests that describe combining or merging partial accumulator results for the accumulator used at file:line, for example in chunked or parallel checksum computations, parallel reductions, or segmented processing. Prefer docs/tests/comments over implementation code. Return the most relevant snippets that describe how partial results are merged and whether this is safe for parallel execution.

DEPEND_code:

@codebase Show implementations of the accumulator update used at file:line that exhibit prefix or rolling dependence, or that are explicitly described as streaming/prefix/rolling checksums or hashes. This includes code where multiple running sums or states are updated in a way that depends on the order of elements (e.g., rolling hashes). Also show implementations that clearly behave as pure associative reductions over independent per-element contributions (such as sums, XORs, min/max over an array), where the operation can be safely regrouped.

Return the most relevant code bodies and any nearby comments that help identify whether the accumulator is prefix/rolling or pure associative.

DEPEND_docs:

@codebase Show documentation, comments, or tests that describe the accumulator used at file:line as a "prefix "rolling or "streaming"checksum or hash, or that explicitly state its associativity and suitability for parallel reduction. Include any text indicating that: the order of processing matters (prefix/streaming), or the operation is associative and can be safely reduced in parallel or in arbitrary groupings.

Prefer docs/tests/comments over raw code. Return the most relevant snippets.

Для паттерна STENCIL генерируются следующие 5 семантических запросов:

NEIGHBOORHOOD_code:

@codebase At file:line there is a loop (possibly nested over indices loop_indices) that has been classified as a STENCIL pattern, reading neighbors from input arrays InArrays and writing to output arrays OutArrays. Please show the full code of this loop nest and the implementation of the stencil computation, including: - the exact neighbor accesses (e.g. in[y+dy][x+dx], in[i+k]), - any helper function(s) callee_names that compute the stencil value, - any comments immediately around this code that describe the neighborhood. Return the loop nest and the relevant function bodies with enough context to see the neighborhood pattern clearly.

NEIGHBOORHOOD_docs:

@codebase For the stencil computation used in the loop at file:line (over indices loop_indices and arrays InArrays ^ OutArrays), show documentation, comments, or design docs that: - describe this as a stencil, convolution, filter, kernel, or neighborhood operator, - mention the radius or size of the neighborhood (e.g., 3x3, 5x5), - explain what physical/algorithmic operation it represents (e.g., blur, Laplacian, Jacobi/Gauss-Seidel update, finite-difference scheme).

Prefer documentation, comments, and test descriptions over raw implementation code. Return the most relevant snippets.

UPDATE_MODE_code:

@codebase For the STENCIL loop at file:line, show code that illustrates: whether the stencil is computed out-of-place (reading from InArrays, writing only to distinct OutArrays), or in-place (reading and writing the same array),whether each output element is written exactly once, or may be written multiple times by different iterations, whether the

iteration space is tiled (e.g., tiles or blocks of the grid) and whether halos or ghost cells are used around tiles.

Please return: - the loop nest structure, - the assignments to OutArrays, -any tiling loops or data structures related to halos/borders, - and nearby comments describing tiling or in-place updates.

PARALLEL_code:

@codebase Show code examples in this repository where the same stencil computation (or function(s) callee_names) is already used inside a parallel context: for example, inside a #pragma omp parallel for loop over rows, inside a tiled parallel decomposition with halos, on GPU kernels, or with another parallel runtime.

Include nearby comments that explain the intended parallelization strategy for this stencil, if any. Return the most relevant usage sites.

PARALLEL_docs:

@codebase Show documentation, comments, or tests that describe how the stencil at file:line should be parallelized. In particular, look for text that states: - that it is safe to parallelize over rows or over the outermost index, - that a tile+halo or ghost-cell scheme should be used, - that certain boundary conditions or dependencies prohibit naive parallelization, - or that this stencil must be executed serially (e.g., Gauss-Seidel dependencies).

Include any explicit statements such as "safe to parallelize by rows "use tiles with halos for parallel execution or "must not be parallelized". Prefer docs, comments, and tests over raw code. Return the most relevant snippets.

Для паттерна SCATTER генерируются следующие 6 семантических запросов:

STRUCTURE_code:

@codebase At file:line there is a loop over indices loop_indices that has been classified as a SCATTER pattern. It updates one or more target structures target_structs using data-dependent keys such as key_exprs.

Please show: - the full code of this loop, - the declarations and definitions of the structures target_structs, - the exact key/index expressions used (for example, bucket(a[i]), hash(points[i]) % M), - the update operations or helper functions update_callees that modify target_structs. Return the loop body and the relevant structure/update definitions with enough context to see how keys and updates are computed.

STRUCTURE_docs:

@codebase For the scatter target structure(s) target_structs used in the loop at file:line, show documentation, comments, or design docs that: -describe what these structures represent (e.g., histograms, counters per key, clustering buckets, adjacency lists), - explain how keys are derived from data, - and describe the intended usage pattern (single-threaded, aggregated counts, concurrent updates, etc.). Prefer documentation, comments, and test descriptions over raw code. Return the most relevant snippets.

PRIVATIZE_code:

@codebase Show code examples in this repository where the same kind of scatter operation on target_structs (or related helper functions update_callees) is implemented using per-thread or per-task private structures that are later merged. For example: - per-thread histograms or bins that are merged into a global histogram, - partial maps per worker thread that are combined in a second pass, - any "private then merge"pattern involving target_structs.

Include the loops that build the private structures, the code that merges them, and any nearby comments describing this pattern. Return the most relevant usage sites.

PRIVATIZE_docs:

@codebase Show documentation, comments, or design docs that recommend using per-thread or per-task private versions of target_structs (or similar scatter structures) and then merging them, for example: - "Use thread-local histograms then reduce into the global histogram "Each worker builds its own counts and we merge them at the end "Parallel histogram: per-thread bins + merge".

Prefer explicit recommendations and examples. Return the most relevant snippets.

CONCURRENCY_code:

@codebase Show code examples in this repository where the same target structure(s) target_structs or update helper(s) update_callees are used in a parallel context, for example: - inside a #pragma omp parallel for loop, - inside a thread pool or explicit std::thread-based parallel loop, - inside GPU kernels, or other concurrent environments. In particular, highlight: - uses of atomics to update target_structs, - uses of locks or other synchronization around target_structs, - uses of explicitly thread-safe container types (e.g., concurrent maps/queues).

Include nearby comments explaining concurrency assumptions for these structures. Return the most relevant snippets.

CONCURRENCY_docs: