Введение к работе
Актуальность работы
Современный уровень полупроводниковых технологий характеризуется все возрастающей миниатюризацией и увеличением количества транзисторов в пределах одного кристалла. Благодаря этому системы на кристалле (СнК) получили широкое распространение в области IT-технологий, военном и авиакосмическом секторах, медицине, многих других отраслях промышленности. Дальнейшим развитием этих систем стали многопроцессорные СнК, которые уже сейчас определяют будущее компьютерной электроники. Данное научное направление является весьма перспективным, мировое сообщество инвестирует миллионы долларов в проектирование многопроцессорных систем с количеством ядер в сотни единиц. Примерами таких проектов являются 80-ядерный исследовательский чип TeraFLOPS компании Intel, 100-ядерный чип TILE-Gx компании Tilera и др.
С увеличением количества ядер в многопроцессорных системах стало очевидно, что стандартные способы объединения микропроцессоров с помощью высокопроизводительных шин малоэффективны. Повышение требований к пропускной способности СнК обусловило возникновение современного инновационного подхода к построению многопроцессорных СнК в виде сетей на кристалле (СтнК), обеспечивающих одновременную передачу данных между узлами с помощью множества коротких соединений, управляемых маршрутизаторами.
Подход к объединению вычислительных ядер многопроцессорных СнК в виде СтнК
достаточно нов. Это объясняется тем, что микросхемы, выполненные по технологиям
ASIC (Application-Specific Integrated Circuit) и FPGA (Field-Programmable Gate Array) лишь
недавно обрели достаточные объемы логических блоков для организации на них целых сетей IP-ядер. В то же время существует ряд различных решений, связанных с построением СтнК, однако многие из них, учитывая их немалую коммерческую ценность, носят закрытый характер. Примерами таких разработок являются продукты компаний Sonix, Silistix, Arteris, iNoCs, Philips, а также разработки отдельных научных групп на базе университетов и исследовательских институтов мира, в частности: University of Glasgow, UK; University of Toronto, Canada; CHREC (NSF Center for High Performance Reconfigurable Computing); ОАО НПЦ «ЭЛВИС», ОАО «НИЦЭВТ», ИПС РАН, РСК «СКИФ», НИИ МВС ЮФУ, Россия. Крупнейшие компании-производители FPGA (Xilinx, Altera) поддерживают свои продукты и распространяют коммерческие и бесплатные IP-ядра для реализации отдельных узлов СтнК. Также существуют компании, специализирующиеся только на разработке программных IP-ядер (например, OpenCores).
Значительный вклад в развитие теории и практики СтнК сделали, прежде всего, такие известные зарубежные ученые, как, Л. Бенини, У. Делли, Р. Муллинз, А. Янтс. Среди трудов отечественных исследователей, следует отметить работы Ю. Ладыженского, А. Лысенко, С. Мосина, Ф. Путри, А. Румянцева и др. Несмотря на то, что данная проблематика еще относительно мало изучена отечественными учеными, существуют все необходимые предпосылки (распространение технологии FPGA, дешевизна, доступность отечественному производителю) для развития указанного выше научного направления в нашей стране.
С развитием электроники постоянно растут требования к подсистеме связи СтнК, которая является достаточно ресурсозатратной, энергоемкой и может занимать до 30 % ресурсов кристалла, потребляя при этом около 40 % электрической мощности. Значительное влияние на характеристики СтнК оказывает и ее топология, которая может быть или специализированной, если известна предварительная информация о задаче, которую будет выполнять система (что не всегда возможно), или одной из регулярных топологий, которые являются не всегда оптимальными с точки зрения требований к пропускной способности и затрат ресурсов за счет дискретности количества узлов и значительного интервала в пропускной способности. Поэтому задача оптимизации подсистемы связи СтнК и усовершенствования топологий СтнК является весьма важной и актуальной. Существует необходимость разработки универсального подхода к
синтезу СтнК - то есть синтезированные топологии должны соответствовать оптимальным параметрам по заданному количеству узлов и конструктивным ограничениям.
Цель и задачи диссертационного исследования
Целью исследования является повышение пропускной способности и сокращение аппаратурных затрат СтнК путем разработки новых квазиоптимальных топологий сетей, дальнейшего развития методов и инструментов их синтеза и моделирования.
Для достижения поставленной цели в работе решаются следующие задачи:
анализ принципов построения и оптимизации СтнК, их типовых топологий и алгоритмов маршрутизации;
определение критерия оптимальности топологии СтнК и требований к квазиоптимальным топологиям СтнК;
распространение метода исчерпывающего поиска на синтез квазиоптимальных топологий с заданными характеристиками и оптимизацией в соответствии с критериями уменьшения среднего расстояния между узлами и количества соединений;
интеграция методов исчерпывающего поиска, ветвей и границ, параллельных вычислений и метода Монте-Карло для ускорения синтеза квазиоптимальных топологий СтнК;
распространение метода эволюционных вычислений на синтез квазиоптимальных топологий с целью его ускорения;
усовершенствование и адаптация модулей библиотеки Netmaker для проведения сравнительного анализа результатов HDL-моделирования СтнК с регулярными и квазиоптимальными топологиями;
разработка библиотеки NoCSimp на основе упрощенного wormhole маршрутизатора для проведения сравнительного анализа результатов моделирования и синтеза СтнК с регулярными и квазиоптимальными топологиями;
моделирование СтнК на основе разработанной программной модели сетей On-Chip Network Simulator и сравнительный анализ полученных результатов.
Объектом исследования является процесс передачи данных в СтнК. Предметом исследования является СтнК на основе квазиоптимальных топологий.
Методы исследования
В работе использованы методы исчерпывающего поиска, параллельных и эволюционных вычислений, Монте-Карло; методы HDL-моделирования и имитационного моделирования; методы структурного и функционального программирования, статистической обработки, анализа и интерполяции данных.
Научная новизна полученных результатов состоит в следующем:
на основе разработанных критериев оптимальности СтнК предложено определение квазиоптимальных и предельно квазиоптимальных топологий СтнК, что позволило разработать новый класс топологических решений сетей с меньшими аппаратурными затратами и большей пропускной способностью по сравнению с топологиями mesh и torus;
впервые синтезирован ряд новых квазиоптимальных топологий СтнК с количеством узлов до 100, что дало возможность сократить до 29,4 % аппаратурные затраты на их реализацию без потери пропускной способности по сравнению с сетями на основе топологии mesh и повысить до 14,5 % пропускную способность при тех же аппаратурных затратах по сравнению с сетями на основе топологии torus;
предложена интеграция методов исчерпывающего поиска, ветвей и границ, параллельных вычислений и метода Монте-Карло для синтеза квазиоптимальных топологий СтнК, в результате чего путем отбрасывания заведомо неоптимальных альтернатив и распараллеливания синтезированы квазиоптимальные топологические решения сетей с количеством узлов до 16, которые имеют до 12,5 % меньшие аппаратурные затраты на реализацию по сравнению с регулярными топологиями mesh и torus;
метод эволюционных вычислений был адаптирован для синтеза квазиоптимальных топологий, что позволило разработать на его основе новый генетический алгоритм GeNoC и, как следствие, ускорить процедуру синтеза квазиоптимальных топологических решений с количеством узлов до 100;
разработаны новые и адаптированы существующие модели СтнК разного уровня абстракции, что обеспечило проведение сравнительного анализа результатов моделирования квазиоптимальных и регулярных топологий СтнК и дало возможность подтвердить вышеупомянутые преимущества предложенных квазиоптимальных топологических решений.
Практическое значение полученных результатов заключается в том, что:
разработаны алгоритм и программные средства синтеза квазиоптимальных топологий СтнК с количеством узлов до 16, которые реализуют объединенные методы исчерпывающего поиска, ветвей и границ, параллельных вычислений и метод Монте-Карло;
разработаны генетический алгоритм и программные средства GeNoC, которые реализуют модифицированный метод эволюционных вычислений и позволяют синтезировать квазиоптимальные топологии СтнК с количеством узлов до 100;
разработана методика проверки полученных квазиоптимальных топологических решений на их соответствие теоретическому глобальному оптимуму, что дало возможность провести анализ синтезированных квазиоптимальных топологий и показать, что они приближены к теоретически возможному глобальному оптимуму не менее чем на 96,3 %;
усовершенствованы и адаптированы модули библиотеки Netmaker для проведения моделирования нерегулярных топологий, что позволило выполнить сравнительный анализ полученных результатов моделирования регулярных и квазиоптимальных топологий СтнК с 8-9 узлами;
разработана новая библиотека NoCSimp, которая реализует модель wormhole маршрутизатора без виртуальных каналов и HDL-модель СтнК на его основе, что позволило на порядок по сравнению с Netmaker повысить скорость моделирования сетей и провести сравнительный анализ затрат ресурсов на реализацию подсистем связи СтнК с квазиоптимальными и регулярными топологиями;
разработаны программные средства, которые реализуют высокоуровневую модель СтнК с количеством узлов до 100 и ускоряют на 2 порядка процедуру моделирования сетей с произвольными топологиями по сравнению с Netmaker.
Основные научные положения, выносимые на защиту:
новый класс топологических решений - квазиоптимальные топологии СтнК - полученный на основе разработанных критериев оптимальности и квазиоптимальности СтнК, который позволяет уменьшить аппаратурные затраты и увеличить пропускную способностью СтнК по сравнению с топологиями mesh и torus;
алгоритм и его реализация ScaNoC, объединяющие методы исчерпывающего поиска, ветвей и границ, параллельных вычислений и метод Монте-Карло, а также генетический алгоритм и программные средства GeNoC, позволяющие синтезировать квазиоптимальные топологии СтнК с количеством узлов до 100;
новые и адаптированные существующие модели СтнК разного уровня абстракции Netmaker, NoCSimp и OCNS, обеспечивающие проведение сравнительного анализа результатов моделирования квазиоптимальных и регулярных топологий СтнК и подтверждающие преимущества квазиоптимальных топологических решений над регулярными.
преимущества квазиоптимальных топологий, требующих (по результатам моделировании СтнК с 49 и 50 узлами, а также СтнК с 99 и 100 узлами) для своей реализации меньше ресурсов (на 29,4 %), обеспечивающих большую пропускную способность (на 14,5 %) по сравнению с топологиями неоптимальной прямоугольной формы, и независимость квазиоптимальных топологий от их геометрической формы.
Реализация и внедрение результатов работы
Предлагаемые в диссертации новые результаты внедрены в учебный процесс МИЭМ НИУ ВШЭ, нашли применение в ОКР АО «МНИРТИ», а также использованы в рамках НИР ИППМ РАН, что подтверждается соответствующими актами:
– акт внедрения в учебный процесс департамента компьютерной инженерии Московского института электроники и математики Национального исследовательского университета «Высшая школа экономики» № 2.35.20–15/32 от 27.04.2015 г. Использование современных теоретических и практических разработок в области сетей на кристалле (СтнК) (синтез и моделирование СтнК в САПР Altera Quartus II), генетических алгоритмов и методов поиска, а также кластерных вычислений для решения задач оптимизации топологий СтнК позволило повысить уровень подготовки студентов в процессе преподавания таких дисциплин, как «Микропроцессорные системы», «Инструментальные средства программирования», «Программирование», а также при подготовке выпускных квалификационных работ бакалавров;
– акт № 20/1243 от 08.09.2015 г. о внедрении квазиоптимальных топологий и разработанных моделей СтнК в виде ускорителя специализированных вычислений в ОКР АО «МНИРТИ» при разработке системы управления беспилотных летательных аппаратов;
– акт № 11612–215 от 21.09.2015 г. об использовании научных результатов
диссертационной работы, в частности, синтезированных квазиоптимальных топологий сетей на кристалле, разработанных моделей сетей NoCSimp и OCNS, а также модифицированной модели Netmaker в ИППМ РАН в рамках НИР «Вега-Г-2015» «Комплекс вычислительных методов и алгоритмов для систем автоматизации проектирования сложных цифровых схем и микросистем».
Апробация результатов диссертации
Основные положения диссертационной работы и ее отдельные разделы были изложены в виде докладов и обсуждались на 23 международных конференциях:
– VIII и IX Международных научно-практических конференциях «Информационные
технологии: наука, техника, технология, образование, здоровье», г. Харьков, НТУ «ХПИ», 2010–2011 гг.;
– IV и V научно-практических конференциях молодых ученых, аспирантов, студентов
«Современная информационная Украина: информатика, экономика, философия»,
г. Донецк, ИИИИ, 2010–2011 гг.;
– X и XI Международных научно-технических конференциях «Проблемы информатики и моделирования», г. Харьков, НТУ «ХПИ», 2010–2011 гг.;
– IX Международной научно-технической конференции молодых ученых «Электроника – 2011», г. Киев, НТУУ «КПИ», 2011 г.;
– XXXI Международной научной конференции «Electronics and Nanotechnology», г. Киев, НТУУ «КПИ», 2011 г.;
– VIII Международной научно-технической конференции студентов и молодежи
«Мир информации и телекоммуникаций – 2011», г. Киев, ГУИКТ, 2011 г.;
– VII научно-практической конференции студентов, аспирантов и молодых ученых «Эффективность инженерных решений в приборостроении», г. Киев, НТУУ «КПИ», 2011 г.;
– V Международной конференции молодых ученых CSE-2011 «Компьютерные науки и инженерия», г. Львов, Львовская политехника, 2011 г.;
– научно-технических конференциях «ИМА 2012/2013/2014: Информатика, математика, автоматика», г. Сумы, СумГУ, 2012–2014 гг.;
– V Международной студенческой научно-технической конференции «Новые направления развития приборостроения», г. Минск, БНТУ, 2012 г.;
– XVI Международном молодежном форуме «Радиоэлектроника и молодежь в XXI веке», г. Харьков, ХНУРЭ, 2012 г.;
– IX Международной студенческой конференции «Innovations in science and technology», г. Киев, 2013 г.;
– научно-технической конференции «ФЭЭ 2013: Физика, электроника, электротехника», г. Сумы, СумГУ, 2013 г.;
– V научно-практической конференции молодых ученых «Вычислительные системы и сети (Майоровские чтения)», г. Санкт-Петербург, ИТМО, 2013 г.;
– научно-технической конференции «Информатика, управление и искусственный интеллект», г. Харьков, НТУ «ХПИ», 2014 г.;
– международной научно-практической конференции «Инновации на основе
информационных и коммуникационных технологий», г. Сочи, НИУ ВШЭ, 2014 г.;
– I Средиземноморской научно-технической конференции «Mediterranean Conference on Embedded Computing MECO–2012», г. Бар, 2012 г.;
– XXXIV и XXXV Международных научных конференциях «IEEE International Scientific Conference on Electronics and Nanotechnology (ELNANO 2014/2015)», г. Киев, НТУУ «КПИ», 2014–2015 гг.
Публикации. Результаты диссертационной работы отражены в 34 печатных работах. 2 работы опубликованы в изданиях из перечня ВАК России [1, 2], 3 статьи – в изданиях, включенных в международные наукометрические базы WoS, Scopus [3, 4] и IEEE Xplore [5], 9 работ – в рецензируемых научных изданиях СНГ [6–14], 3 – в сборниках статей, изданных по итогам работы научных конференций [15–17], и 17 работ – в сборниках трудов (тезисов) конференций.
Структура и объем диссертации. Диссертация состоит из введения, 4 глав, заключения, списка использованных источников литературы из 237 наименований и 5 приложений. Общий объем диссертации составляет 188 страниц, из которых – 151 страница основного текста (50 рисунков и 20 таблиц), список использованных источников на 28 страницах и 5 приложений на 9 страницах.