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

Файл статьи: SE-BMSTU...o472.pdf (563.40Кб)

УДК 004.2+004.31

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

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

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

1. Орлов С.А., Цилькер Б.Я. Организация ЭВМ и систем: учебник для вузов. 2- е изд . СПб .: Питер , 2011. 688 с .
2. Harris D.M., Harris S.L. Digital Design and Computer Architecture. 2^nd ed. Boston: Morgan Kaufmann, 2012. 721 p.
3. Таненбаум Э.С., Остин Т. Архитектура компьютера: пер. с англ. 6- е изд . СПб .: Питер , 2015. 816 с . [Tanenbaum A., Austin T. Structured computer organization. 6^th ed. Prentice Hall, 2012. 800 p.].
4. Huang I.J., Peng T.C. Analysis of x86 instruction set usage for DOS/Windows applications and its implication on superscalar design // IEICE Transactions on Information and Systems. 2002. Vol. E85-D, no. 6. P. 929-939.
5. Kankowski P. x86 Machine Code Statistics // strchr.com: website. Available at: http://www.strchr.com/x86_machine_code_statistics , accessed 01.09.2015.
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. 2010. 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. Available at: http://www.intel.ru/content/dam/www/public/us/en/documents/solution-briefs/integrated-cryptographic-compression-accelerators-brief.pdf , accessed 01.09.2015.
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 / ОАО «ВПК «НПО машиностроения»; МГТУ им. Н.Э. Баумана. М.: МГТУ им. Н . Э . Баумана , 2009. С . 296-301.
14. Кнут Д. Искусство программирования. В 3 т. Т. 3. Сортировка и поиск: пер с англ. 2- е изд . М .: Вильямс , 2000. 832  с .
15. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ: пер. с англ. М.: МЦНМО, 2000. 960 с.
16. Попов А.Ю. Применение вычислительных систем с многими потоками команд и одним потоком данных для решения задач оптимизации // Инженерный журнал: наука и инновации . 2012. № 1. Режим доступа: http://engjournal.ru/catalog/it/hidden/80.html (дата обращения 01.09.2015.)
17. Попов А.Ю. Исследование производительности процессора обработки структур в системе с многими потоками команд и одним потоком данных // Инженерный журнал: наука и инновации. 2013. № 11. Режим доступа: http://engjournal.ru/catalog/it/hidden/1048.html (дата обращения 01.09.2015).
18. Попов А.Ю. О реализации алгоритма Форда-Фалкерсона в вычислительной системе с многими потоками команд и одним потоком данных // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2014. № 9. С. 162-180. DOI: 10.7463/0914.0726416
19. Подольский В.Э. Об организации параллельной работы некоторых алгоритмов поиска кратчайшего пути на графе в вычислительной системе с многими потоками команд и одним потоком данных // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2015. № 4. С . 189-214. DOI: 10.7463/0415.0764268