Рисунок 1 Исходная ЯПФ алгоритма (слева) и соответствующая диаграмма ВЖД (справа, формула одновременно существующих данных “6-5-4-3-3-3-2”)

Рисунок 2 Модифицированная (один из вариантов) ЯПФ рис.1 и соответствующая ВЖД данных (формула “6-7-5-3-3-3-2”)

Из сравнения рис. 1 и 2 видим, что полезная модификация ЯПФ (позволяющая выполнить программу на двух параллельных вычислителях вместо 4-х и, соответственно, существенно повысить плотность кода) требует бо́льшей нагрузки на разделяемую память (“формула” показывает список количества обобщённых данных, существующих между ярусами  последовательно вдоль ЯПФ). Анализ ВЖД в случае полностью последовательного характера выполнения показанного на рис.3 алгоритма (линейчатые графики распределения количества данных отрисовываются  непосредственно системой SPF@home). Собственно ЯПФ здесь вырождена, имеет ширину 1 и содержит 11 исполняемых операторов (плюс уровни  исходных и выходных данных).

Рисунок 3 Количество одновременно  существующих данных для трёх (слева направо) вариантов последовательного выполнения алгоритма рис. 1  (слева от диаграммы – промежуток ярусов с указанием номеров операторов в формате “предыдущий / последующий”; in и out – входные и выходные данные соответственно, в прямоугольниках диаграммы – количество данных)

Первыми (не единственными!) претендентами на линейность исполнения являются находящиеся на ярусах 1,5,6 (рис. 1) операторы, причем вследствие  ортогональности по данным они могут быть выполнены в любой  последовательности. При этом достигаются разные качества распределения ВЖЛД (на рис. 3 варианта,  локальным оптимумом из которых является последний, характеризующийся максимумом числа данных 6 единиц). В данном случае вычислительная сложность процедуры реорганизации ЯПФ явилась незначительной - оказалось достаточным всего двух перестановок операторов (изменения в положении коснулись операторов 101,102,103.  Даже в таком простом примере  результат оптимизации “стоит свеч”, для более сложных случаев качество оптимизации будет более значительным.Следующим этапом определения параметров устройства временного хранения данных является определение необходимых объемов (данные поочередно используют одни и те же области памяти) этого устройства (например, числа регистров общего назначения); для этого применяются известные приемы (напр., “метод раскраски графов”, [10]). Такие возможности   не поддерживаются API модуля SPF@home и могут быть реализованы средствами встроенного языка Lua или внешними модулями.Т.о. исследования показывают, что не только в случае параллельного,  но и последовательного выполнения программ вполне возможна оптимизация  вычислительных систем в направлении минимизации ресурсов устройств временного хранения данных  путем реализации разумного плана выполнения отдельных операций.

Список литературы1.  J.B.Dennis, D.P.Misunas. A Preliminary Architecture for a Basic Data-Flow Processor. In Proc. Second Annual Symp. Computer Architecture, pр. 126-132, Houston, Texas, January, 1975.2.  Баканов В.М. Параллелизация обработки данных на вычислителях потоковой (Data-Flow) архитектуры.  // Журнал “Суперкомпьютеры”, — M.: 2011, № 5, с. 54-58.3.  Э.Таненбаум, Т.Остин. Архитектура компьютера. — СПб.:  Изд. Питер,   2019. — 816 c.4.  Баканов В.М. Управление динамикой вычислений  в процессорах потоковой архитектуры  для различных типов алгоритмов. // Журнал “Программная инженерия", — М.: 2015, № 9, c. 20-24.5.  Федотов И.Е. Параллельное программирование. Модели и приёмы. — М.: СОЛОН-Пресс, 2018. — 390 с.6.  Баканов В.М. Программный комплекс для  разработки методов построения оптимального каркаса параллельных программ. // Журнал “Программная инженерия", — М.: 2017, том 8, № 2, c. 58-65.7.  M.R.Gary, D.S.Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. — W.H.Freeman and Company, San Francisco, 1979. — 338 pp.8.  V.M.Bakanov.  Software complex for modeling and optimization of program implementation on parallel calculation systems. Open Computer Science, Volume 8, Issue 1, Pages 228–234, ISSN (Online) 2299-1093, DOI: https://doi.org/10.1515/comp-2018-0019.9.  Roberto Ierusalimschy. Programming in Lua. Third Edition.  PUC-Rio, Brasil, Rio de Janeiro, 2013. — 348 p.10. Карпов В.Э. Теория компиляторов. Часть 2. Двоичная трансляция. URL: http://www.rema44.ru/resurs/study/compiler2/Compiler2.pdf (дата обращения 15.12.2020).