Другие журналы

научное издание МГТУ им. Н.Э. Баумана

НАУКА и ОБРАЗОВАНИЕ

Издатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211.  ISSN 1994-0408

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

# 11, ноябрь 2015
DOI: 10.7463/1115.0820770
Файл статьи: SE-BMSTU...o527.pdf (924.83Кб)
автор: Попов А. Ю.1,*

УДК 004.2; 004.31

1 МГТУ им. Н.Э. Баумана, Москва, Россия

В МГТУ им Н.Э.Баумана ведется проект по разработке принципов функционирования вычислительной системы с принципиально новой архитектурой. Разработан действующий образец системы, позволивший оценить эффективность разработанных аппаратных и программных средств. Результаты экспериментов, приведенные в предыдущих работах, а также анализ принципов функционирования новой вычислительной системы, позволяют сделать выводы о ее эффективности при решении задач дискретной оптимизации, связанной с обработкой множеств.
Новая архитектура основана на прямой аппаратной поддержке операций дискретной математики, что выражается в применении специальных средств обработки множеств и структур данных. В рамках проекта разработано специальное устройство - Процессор обработки структур (СП), которое повышает производительность, не ограничивая области применения такой вычислительной системы.
В предыдущих работах приведены базовые принципы организации вычислительного процесса в МКОД системе, представлена структура и особенности работы Процессора обработки структур, показаны общие принципы решения задач дискретной оптимизации на графах. В данной работе рассматриваются два алгоритма поиска минимального покрывающего дерева: алгоритмы Крускала и Прима. Исследуются варианты реализации алгоритмов для двух режимов работы СП: режима сопроцессора и режима МКОД. Приводятся результаты экспериментального сравнения производительности МКОД системы в режиме сопроцессора с универсальными ЭВМ.

Список литературы
  1. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ: пер. с англ. М.: МЦНМО, 2000. 960 с.
  2. Кнут Д. Искусство программирования. В 3 т. Т. 3. Сортировка и поиск: пер. с англ. 2-е изд. М.: Вильямс, 2000. 832 с.
  3. Орлов С.А., Цилькер Б.Я. Организация ЭВМ и систем: учебник для вузов. 2- е изд . СПб .: Питер , 2011. 688 с .
  4. Harris D.M., Harris S.L. Digital Design and Computer Architecture. 2nd ed. Boston: Morgan Kaufmann, 2012. 721 p.
  5. Таненбаум Э.С., Остин Т. Архитектура компьютера: пер. с англ. 6- е изд . СПб .: Питер , 2015. 816 с .
  6. Coole J., Stitt G. Traversal Caches: A Framework for FPGA Acceleration of Pointer Data Structures // International Journal of Reconfigurable Computing. 2010. Vol. 2010. Art. ID 652620. DOI: 10.1155/2010/652620
  7. Williams J., Massie C., George A.D., Richardson J., Gosrani K., Lam H. Characterization of Fixed and Reconfigurable Multi-Core Devices for Application Acceleration // ACM Transactions on Reconfigurable Technology and Systems. 2010. Vol. 3, no. 4. Art. no. 19. DOI: 10.1145/1862648.1862649
  8. Integrated Cryptographic and Compression Accelerators on Intel Architecture Platforms. SOLUTION BRIEF. Intel QuickAssist Technology. Order No. 329879-001US. Intel Corporation, 2013. 5 p.
  9. Kumar Sn., Shriraman A., Srinivasan V., Lin D., Phillips J. SQRL: hardware accelerator for collecting software data structures // Proceedings of the 23rd international conference on Parallel architectures and compilation (PACT’14). ACM, New York, NY, USA, 2014. P. 475-476. DOI: 10.1145/2628071.2628118
  10. Singh M., Leonhardi B. Introduction to the IBM Netezza warehouse appliance // Proceedings of the 2011 Conference of the Center for Advanced Studies on Collaborative Research (CASCON’11) / ed. by M. Litoiu, E. Stroulia, S. MacKay. IBM Corp., Riverton, NJ, USA, 2011. P. 385-386.
  11. Попов А . Ю . Электронная вычислительная машина с многими потоками команд и одним потоком данных : пат . 71016 Российская Федерация . 2008. Бюл. № 5. 1 с.
  12. Попов А.Ю. Реализация электронной вычислительной машины с аппаратной поддержкой операций над структурами данных // Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2011. Спец. вып. Информационные технологии и компьютерные системы. С. 83 - 87.
  13. Попов А.Ю. Электронная вычислительная машина с аппаратной поддержкой операций над структурами данных // Аэрокосмические технологии: тр. Второй Междунар. научно-техн. конф., посвященной 95-летию со дня рождения академика В.Н. Челомея (РФ, Реутов – Москва, 19-20 мая 2009 г.). Т. 1 / ОАО «ВПК «НПО машиностроения»; МГТУ им. Н.Э. Баумана. М.: МГТУ им. Н.Э. Баумана, 2012. С. 296-301.
  14. Попов А.Ю. Исследование производительности процессора обработки структур в системе с многими потоками команд и одним потоком данных // Инженерный журнал: наука и инновации. 2013. № 11. DOI: 10.18698/2308-6033-2013-11-1048
  15. Попов А.Ю. Применение вычислительных систем с многими потоками команд и одним потоком данных для решения задач оптимизации // Инженерный журнал: наука и инновации. 2012. № 1. DOI : 10.18698/2308-6033-2012-1-80
  16. Попов А.Ю. О реализации алгоритма Форда-Фалкерсона в вычислительной системе с многими потоками команд и одним потоком данных // Наука и Образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2014. № 9. С. 162-180. DOI: 10.7463/0914.0726416
  17. Подольский В.Э. Об организации параллельной работы некоторых алгоритмов поиска кратчайшего пути на графе в вычислительной системе с многими потоками команд и одним потоком данных // Наука и Образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2015. № 4. С . 189-214. DOI: 10.7463/0415.0764268
Поделиться:
 
ПОИСК
 
elibrary crossref ulrichsweb neicon rusycon
 
ЮБИЛЕИ
ФОТОРЕПОРТАЖИ
 
СОБЫТИЯ
 
НОВОСТНАЯ ЛЕНТА



Авторы
Пресс-релизы
Библиотека
Конференции
Выставки
О проекте
Rambler's Top100
Телефон: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)
  RSS
© 2003-2020 «Наука и образование»
Перепечатка материалов журнала без согласования с редакцией запрещена
 Тел.: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)