<?xml version="1.0" encoding="UTF-8"?>
<article article-type="research-article" dtd-version="1.3" xml:lang="ru" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:noNamespaceSchemaLocation="https://metafora.rcsi.science/xsd_files/journal3.xsd">
  <front>
    <journal-meta>
      <journal-id journal-id-type="publisher-id">moitvivt</journal-id>
      <journal-title-group>
        <journal-title xml:lang="ru">Моделирование, оптимизация и информационные технологии</journal-title>
        <trans-title-group xml:lang="en">
          <trans-title>Modeling, Optimization and Information Technology</trans-title>
        </trans-title-group>
      </journal-title-group>
      <issn pub-type="epub">2310-6018</issn>
      <publisher>
        <publisher-name>Издательство</publisher-name>
      </publisher>
    </journal-meta>
    <article-meta>
      <article-id pub-id-type="doi">10.26102/2310-6018/2026.58.7.009</article-id>
      <article-id pub-id-type="custom" custom-type="elpub">2456</article-id>
      <title-group>
        <article-title xml:lang="ru">Фазовая оптимизация однопоточного выполнения независимых программных последовательностей</article-title>
        <trans-title-group xml:lang="en">
          <trans-title>Phase optimization of single-threaded execution of independent program sequences</trans-title>
        </trans-title-group>
      </title-group>
      <contrib-group>
        <contrib contrib-type="author">
          <name-alternatives>
            <name name-style="eastern" xml:lang="ru">
              <surname>Буевич</surname>
              <given-names>Евгений Андреевич</given-names>
            </name>
            <name name-style="western" xml:lang="en">
              <surname>Buevich</surname>
              <given-names>Evgeniy Andreevich</given-names>
            </name>
          </name-alternatives>
          <email>gftregs@gmail.com</email>
          <xref ref-type="aff">aff-1</xref>
        </contrib>
      </contrib-group>
      <aff-alternatives id="aff-1">
        <aff xml:lang="ru">Московский государственный технологический университет “СТАНКИН”</aff>
        <aff xml:lang="en">Moscow State Technological University "STANKIN"</aff>
      </aff-alternatives>
      <pub-date pub-type="epub">
        <day>01</day>
        <month>01</month>
        <year>2026</year>
      </pub-date>
      <volume>1</volume>
      <issue>1</issue>
      <elocation-id>10.26102/2310-6018/2026.58.7.009</elocation-id>
      <permissions>
        <copyright-statement>Copyright © Авторы, 2026</copyright-statement>
        <copyright-year>2026</copyright-year>
        <license license-type="creative-commons-attribution" xlink:href="https://creativecommons.org/licenses/by/4.0/">
          <license-p>This work is licensed under a Creative Commons Attribution 4.0 International License</license-p>
        </license>
      </permissions>
      <self-uri xlink:href="https://moitvivt.ru/ru/journal/article?id=2456"/>
      <abstract xml:lang="ru">
        <p>В работе рассматривается один из аспектов совместного выполнения в одном потоке нескольких независимых друг от друга по данным программных последовательностей, что достигается чередованием их инструкций в исходном коде. Эта задача является NP-сложной. В работе рассматривается метод поиска оптимального сдвига старта последовательностей через быстрое преобразование Фурье для различных вариантов постановки задачи (числа последовательностей). Цепочки инструкций представляются в виде временных рядов использования ресурсов (исполнительных портов) и регистров вычислительного ядра. При работе с регистрами ряды взаимной корреляции строятся через преобразование Фурье размерностью K, где K – число рядов. При работе с портами каждый ряд разделяется на несколько каналов, соответствующих различной нагрузке порта, для каждого канала выполняется преобразование Фурье размерностью K-1, далее результаты суммируются с заданными весами. Показано, что при K=3 в обоих случаях частотное представление имеет меньшую вычислительную сложность, чем прямой перебор. Метод также подходит для поиска оптимальной точки разреза последовательности с целью конвейерного исполнения в рамках одного потока. Алгоритм успешно находит точки оптимального совмещения для набора тестовых последовательностей с высокой дисперсией локальных средних интенсивностей использования индивидуального ресурса и сочетаний ресурсов.</p>
      </abstract>
      <trans-abstract xml:lang="en">
        <p>This paper considers one aspect of the joint execution of several data-independent program sequences in a single thread, achieved by interleaving their instructions in the source code. This problem is NP-hard. The paper considers a method for finding the optimal sequence start shift using the fast Fourier transform for various problem formulations (number of sequences). Instruction chains are represented as time series of resource (execution ports) and core register utilization. When working with registers, cross-correlation series are constructed using the Fourier transform of dimension K, where K is the number of series. When working with ports, each series is divided into several channels corresponding to different port loads. A Fourier transform of dimension K-1 is performed for each channel, and the results are then summed with the specified weights. It is shown that for K=3, in both cases, the frequency representation has lower computational complexity than brute force. The method is also suitable for finding the optimal sequence cut point for pipelined execution within a single thread. The algorithm successfully finds optimal matching points for a set of test sequences with high variance of local average usage intensities of individual resources and combinations of resources.</p>
      </trans-abstract>
      <kwd-group xml:lang="ru">
        <kwd>быстрое преобразование Фурье</kwd>
        <kwd>взаимная корреляция</kwd>
        <kwd>планирование инструкций</kwd>
        <kwd>регистровое давление</kwd>
        <kwd>исполнительные порты</kwd>
        <kwd>слияние потоков</kwd>
        <kwd>оптимизация компилятора</kwd>
      </kwd-group>
      <kwd-group xml:lang="en">
        <kwd>fast Fourier transform</kwd>
        <kwd>cross-correlation</kwd>
        <kwd>instruction scheduling</kwd>
        <kwd>register pressure</kwd>
        <kwd>execution ports</kwd>
        <kwd>thread fusion</kwd>
        <kwd>compiler optimization</kwd>
      </kwd-group>
      <funding-group>
        <funding-statement xml:lang="ru">Исследование выполнено без спонсорской поддержки.</funding-statement>
        <funding-statement xml:lang="en">The study was performed without external funding.</funding-statement>
      </funding-group>
    </article-meta>
  </front>
  <back>
    <ref-list>
      <title>References</title>
      <ref id="cit1">
        <label>1</label>
        <mixed-citation xml:lang="ru">Ferrante J., Ottenstein K.J., Warren J.D. The Program Dependence Graph and Its Use in Optimization. ACM Transactions on Programming Languages and Systems (TOPLAS). 1987;9(3):319–349.</mixed-citation>
      </ref>
      <ref id="cit2">
        <label>2</label>
        <mixed-citation xml:lang="ru">Llosa J., González A., Ayguadé E., et al. Swing Modulo Scheduling: A Lifetime-Sensitive Approach. In: Proceedings of the 1996 Conference on Parallel Architectures and Compilation Technique, 20-23 October 1996, Boston, MA, USA. IEEE; 1996. P. 80–91. https://doi.org/10.1109/PACT.1996.554030</mixed-citation>
      </ref>
      <ref id="cit3">
        <label>3</label>
        <mixed-citation xml:lang="ru">Zhang Z., Liu B. SDC-based modulo scheduling for pipeline synthesis. In: Proceedings of the 2013 IEEE/ACM International Conference on Computer-Aided Design (ICCAD), 18–21 November 2013, San Jose, CA, USA. IEEE; 2013. P. 211–218. https://doi.org/10.1109/ICCAD.2013.6691121</mixed-citation>
      </ref>
      <ref id="cit4">
        <label>4</label>
        <mixed-citation xml:lang="ru">Lattner C., Amini M., Bondhugula U., et al. MLIR: Scaling Compiler Infrastructure for Domain Specific Computation. In: Proceedings of the 2021 IEEE/ACM International Symposium on Code Generation and Optimization (CGO), 27 February – 3 March 2021, Seoul, Korea (South). IEEE; 2021. P. 2–14. https://doi.org/10.1109/CGO51591.2021.9370308</mixed-citation>
      </ref>
      <ref id="cit5">
        <label>5</label>
        <mixed-citation xml:lang="ru">Gupta R., Bodík R. Register Pressure Sensitive Redundancy Elimination. In: Proceedings of the 8th International Conference, CC'99, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS'99, March 22–28 1999, Amsterdam, Netherlands. Berlin, Heidelberg: Springer; 1999. P. 107–121. https://doi.org/10.1007/978-3-540-49051-7_8</mixed-citation>
      </ref>
      <ref id="cit6">
        <label>6</label>
        <mixed-citation xml:lang="ru">Yang Y., Xiang P., Kong J., et al. A GPGPU compiler for memory optimization and parallelism management. In: Proceedings of the 2010 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 5–10 June 2010, Toronto, Ontario, Canada. New York: Association for Computing Machinery; 2010. P. 86–97. https://doi.org/10.1145/1806596.1806606</mixed-citation>
      </ref>
      <ref id="cit7">
        <label>7</label>
        <mixed-citation xml:lang="ru">Cui Q., Rong V., Chen D., et al. Dense, Interlocking-Free and Scalable Spectral Packing of Generic 3D Objects. ACM Transactions on Graphics. 2023;42(4):1–14. https://doi.org/10.1145/3592126</mixed-citation>
      </ref>
      <ref id="cit8">
        <label>8</label>
        <mixed-citation xml:lang="ru">Sorensen H.V., Burrus C.S. Efficient computation of the DFT with only a subset of input or output points. IEEE Transactions on Signal Processing. 1993;41(3):1184–1200. https://doi.org/10.1109/78.205723</mixed-citation>
      </ref>
      <ref id="cit9">
        <label>9</label>
        <mixed-citation xml:lang="ru">Perreault-Lafleur C., Carvalho M., Desaulniers G. A stochastic integer programming approach to reserve staff scheduling with preferences. International Transactions in Operational Research. 2025;32(1):289–313. https://doi.org/10.1111/itor.13298</mixed-citation>
      </ref>
      <ref id="cit10">
        <label>10</label>
        <mixed-citation xml:lang="ru">Cooley J.W., Tukey J.W. An algorithm for the machine calculation of complex Fourier series. Mathematics of Computation. 1965;19(90):297–301. https://doi.org/10.2307/2003354</mixed-citation>
      </ref>
    </ref-list>
    <fn-group>
      <fn fn-type="conflict">
        <p>The authors declare that there are no conflicts of interest present.</p>
      </fn>
    </fn-group>
  </back>
</article>