Классификация циклов с одним оператором для выполнения на процессоре с программируемым ускорителем

Классификация циклов с одним оператором для выполнения на процессоре с программируемым ускорителем

Автор: Штейнберг Борис Яковлевич, Штейнберг Олег Борисович, Михайлуц Юрий Вячеславович, Баглий Антон Павлович, Дубров Денис Владимирович, Штейнберг Роман Борисович

Журнал: Программные системы: теория и приложения @programmnye-sistemy

Рубрика: Информационные системы в медицине

Статья в выпуске: 3 (34) т.8, 2017 года.

Бесплатный доступ

Рассмотрена классификация программных циклов для оптимизирующего компилятора на процессор с программируемым ускорителем. Такой процессор может быть системой на кристалле, содержащем одновременно и вычислительные ядра, и программируемую схему. Программируемый ускоритель настраивается на архитектуру реконфигурируемого конвейера.Уточнена классификация по регулярным информационным зависимостям. Для каждого класса циклов рассмотрена возможность конвейерного выполнения. Если непосредственное конвейерное выполнение невозможно, то обсуждён вопрос о преобразованиях такого цикла к конвейеризуемому виду с помощью ОРС (Оптимизирующая распараллеливающая система). Информационные зависимости в цикле влияют на архитектуру конвейера, реализующего цикл.Рассматриваемый компилятор отличатся от обычных наличием конвертора с языка программирования высокого уровня в язык описания электронных схем. В нём должна быть библиотека драйверов для передачи данных с ЦПУ на ПЛИС и обратно. Численный эксперимент для одного из классов циклов показал двукратное ускорение.

Еще

ID: 14336124 Короткий адрес: https://sciup.org/14336124

Список литературы Классификация циклов с одним оператором для выполнения на процессоре с программируемым ускорителем

  • B. Ya. Steinberg, D. V. Dubrov, Y. V. Mikhailuts, A. S. Roshal, R. B. Steinberg. "Automatic high-level programs mapping onto programmable architectures", Parallel Computing Technologies, Proceedings of the 13th International Conference on Parallel Computing Technologies, PaCT 2015 (August 31-September 4, 2015, Petrozavodsk, Russia), Lecture Notes in Computer Science, vol. 9251, Springer Verlag. P. 474-485.
  • R. Allen, K. Kennedy. Optimizing compilers for modern architectures, Morgan Kaufmann Publishers, San Francisco-San Diego-New York-Boston-London-Sidney-Tokyo, 2002, 790 p.
  • Duo Liu, Yi Wang, Zili Shao, Minyi Guo, Jingling Xue. "Optimally maximizing iteration-level loop parallelism", IEEE Transactions on Parallel and Distributed Systems (TPDS), V. 23. No. 3. 2012. P. 564-572.
  • L. Lamport. "The parallel execution of DO loops", Commun. ACM, V. 17. No. 2. 1974. P. 83-93.
  • M. Wolfe. High performance compilers for parallel computing, Addison-Wesley Publishing Company, Redwood city, 1996, 570 p.
  • А. В. Бабичев, В. Г. Лебедев. Распараллеливание программных циклов//Программирование, 1983, №5. С. 52-63.
  • В. А. Евстигнеев, С. В. Спрогис. Векторизация программ//Векторизация программ: теория, методы, реализация, Сборник переводов статей, Мир, М., 1991. С. 246-267.
  • Б. Я. Штейнберг. Математические методы распараллеливания рекуррентных программных циклов на суперкомпьютеры с параллельной памятью, Издательство Ростовского университета, Ростов-на-Дону, 2004, 192 с.
  • О. Б. Штейнберг. Классификация программных циклов с одним оператором присваивания//Известия ВУЗов. Северо-Кавказский регион. Естественные науки, 2017, №1. С. 52-59.
  • Altera C2H Compiler (Accessed 20.11.2016), URL: https://www.altera. com/en_US/pdfs/literature/ug/ug_nios2_c2h_compiler.pdf
  • A. V. Anisimov, M. S. Yadzhak. "Construction of optimal algorithms for mass computations in digital filtering problems", Cybernetics and Systems Analysis, V. 44. No. 4. 2008. P. 465-476.
  • Y. Ben-Asher, N. Rotem, E. Shochat. "Finding the best compromise in compiling compound loops to verilog", J. Syst. Archit., V. 56. No. 9. 2010. P. 474-486.
  • K. Bondalapati. Modeling and mapping for dynamically reconfigurable hybrid architecture, Ph.D. thesis, University of Southern California, 2001, x+184 p.
  • B. Ya. Steinberg, A. P. Bugliy, D. V. Dubrov, Y. V. Mikhailuts, O. B. Steinberg, R. B. Steinberg. "A Project of compiler for a processor with programmable accelerator", 5th International Young Scientist Conference on Computational Science YSC 2016 (26-28 October 2016, Krakow, Poland), Procedia Computer Science, 101 2016. P. 435-438.
  • A. P. Bugliy, D. V. Dubrov, Y. V. Mikhailuts, B. Ya. Steinberg, R. B. Steinberg. Developing a high-level language compiler for a computer with programmable architecture//Труды Международной конференции по программной инженерии CEE SECR-2016, CEE-SECR ’16 (October 28-29, 2016, Moscow, Russian Federation), ACM, 2016.
  • D. Dubrov, A. Roshal. Generating pipeline integrated circuits using C2HDL converter//East-West Design & Test Symposium (Ростов на Дону, Россия, 27-30 сентября 2013), 2013. С. 1-4.
  • M. S. Jadzhak. "On a numerical algorithm of solving the cascade digital filtration problem", Journal of Automation and Information Sciences, V. 36. No. 6. 2004. P. 23-34.
  • M. S. Yadzhak, M. I. Tyutyunnyk. "An optimal algorithm to solve digital filtering problem with the use of adaptive smoothing", Cybernetics and Systems Analysis, V. 49. No. 3. 2013. P. 449-456.
  • M. S. Yadzhak, M. I. Tyutyunnyk. "An optimal algorithm to solve digital filtering problem with the use of adaptive smoothing", Cybernetics and Systems Analysis, V. 49. No. 3. 2013. P. 449-456.
  • Zynq-7000 all programmable SoC overview. Preliminary product specification, XILINX (Accessed 28.07.2016), URL: http://www.xilinx.com/support/documentation/data_sheets/ds190-Zynq-7000-Overview.pdf
  • Д. В. Дубров, А. С. Рошаль, Б. Я. Штейнберг, Р. Б. Штейнберг. Автоматическое отображение программ на процессор с ПЛИС-ускорителем//Вестник Южно-уральского государственного университета. Серия "Вычислительная математика и информатика", Т. 3, № 2. 2014. С. 117-121.
  • И. И. Левин, Б. Я. Штейнберг. Сравнительный анализ эффективности параллельных программ для различных архитектур параллельных ЭВМ//Искусственный интеллект, 2001, №3. С. 234-242.
  • А. В. Каляев, И. И. Левин. Модульно-наращиваемые многопроцессорные системы со структурно-процедурной организацией вычислений, Янус-К, М., 2003, 380 с.
  • И. А. Каляев, И. И. Левин, Е. А. Семерников, В. И. Шмойлов. Реконфигурируемые мультиконвейерные вычислительные структуры, 2-е, перераб. и доп. изд., ред. И. А. Каляев, Изд-во ЮНЦ РАН, Ростов-н/Д, 2009, 344 с.
  • В. В. Корнеев. Архитектура вычислительных систем с программируемой структурой, Наука, Новосибирск, 1985, 166 с.
  • К. Г. Самофалов, Г. М. Луцкий. Основы теории многоуровневых конвейерных вычислительных систем, Радио и связь, М., 1989, 272 с.
  • Р. Б. Штейнберг. Вычисление задержки в стартах конвейеров для суперкомпьютеров со структурно процедурной организацией вычислений//Искусственный интеллект, 2003, №4. С. 105-112.
  • Р. Б. Штейнберг. Использование решетчатых графов для исследования многоконвейерной модели вычислений//Известия ВУЗов. СевероКавказский регион. Естественные науки, 2009, №2. С. 16-18.
  • Р. Б. Штейнберг. Отображение гнезд циклов на многоконвейерную архитектуру//Программирование, 2010, №3. С. 69-80.
  • О. Б. Штейнберг. Распараллеливание рекуррентных циклов с нерегулярным вычислением суперпозиций//Известия ВУЗов. СевероКавказский регион. Естественные науки, 2009, №2. С. 18-21.
  • О. Б. Штейнберг, С. Е. Суховерхов. Автоматическое распараллеливание рекуррентных циклов с проверкой устойчивости//Информационные технологии, 2010, №1. С. 40-45.
  • О. Б. Штейнберг. Минимизация количества временных массивов в задаче разбиения циклов//Известия ВУЗов. Северо-Кавказский регион. Естественные науки, 2011, №5. С. 31-35.
  • Р. Н. Арапбаев. Анализ зависимостей по данным: тесты на зависимость и стратегии тестирования, Диссертация на соискание ученой степени кандидата физико-математических наук, ИСИ СО РАН, Новосибирск, 2008, 116 с.
  • А. М. Шульженко. Исследование информационных зависимостей программ для анализа распараллеливающих преобразований, Диссертация на соискание учёной степени кандидата технических наук, РГУ Ростов-на-Дону, 2006, 200 с.
  • ОРС (Оптимизирующая распараллеливающая система) (Дата обращения 20.11.2016), URL: http://www.ops.rsu.ru
  • Rose compiler infrastructure (Accessed 29.07.2016), URL: http://rosecompiler.org/?page_id=182
  • Affine transformations for optimizing parallelism and locality (Accessed 29.07.2016), URL: http://suif.stanford.edu/research/affine.html
  • P. Feautrier. "Parametric integer programming", RAIRO Recherche Operationnelle, V. 22. No. 3. 1988. P. 243-268.
  • А. М. Шульженко. Автоматическое определение циклов ParDo в программе//Известия вузов. Северо-Кавказский регион. Естественные науки. Приложение, 2011, №05. С. 77-88.
  • P. Feautrier. "Dataflow analysis of array and scalar references", International Journal of Parallel Programming, V. 20. No. 1. 1991. P. 23-53.
  • P. Feautrier. "Some efficient solutions to the affine scheduling problem. I. One-dimensional time", International Journal of Parallel Programming, V. 21. No. 5. 1992. P. 313-347.
  • P. Feautrier. "Some efficient solutions to the affine scheduling problem. Part II. Multidimensional time", International Journal of Parallel Programming, V. 21. No. 6. 1992. P. 389-420.
  • В. В. Воеводин. Математические модели и методы в параллельных процессах, Наука, М., 1986, 296 с.
  • В. В. Воеводин. Математические основы параллельных вычислений, Изд-во МГУ, М., 1991, 345 с.
  • В. В. Воеводин, Вл. В. Воеводин. Параллельные вычисления, БХВ-Петербург, СПб., 2002, 608 с.
  • С. А. Гуда. Операции над представлениями кусочно-квазиаффинных функций в виде деревьев//Информатика и её применение, Т. 7, № 1. 2013. С. 58-69.
Еще
Ред. заметка
QR-код для установки приложения SciUp Наведите камеру и скачайте бесплатное приложение SciUp