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

• Введение
• Актуальность проблемы
• Цели и задачи
• Особенности параллельных вычислений
• Виды параллельных систем
• Современные параллельные системы
• Особенности синтеза цифровых устройств
• Базис ПЛИС
• Типы ПЛИС
• Результаты
• Список литературы

Введение

Стремительное развитие средств вычислительной техники в настоящее время выдвигает серьезные требования как к быстродействию цифровых устройств, так и к аппаратурным затратам и стоимости в целом. Наряду с этими требованиями выдвигаются и другие, такие как надежность, экономичность и безопасность в эксплуатации.

Для реализации цифровых устройств широко используется базис программируемых логических интегральных схем (ПЛИС) [1]. В сравнении с заказными схемами, ПЛИС проигрывают в быстродействии и в оптимальности использования аппаратных средств, однако стоимость ПЛИС значительно меньше, чем стоимость заказной схемы, реализация устройства на базе ПЛИС занимает значительно меньше времени и, зачастую, ПЛИС являются более надежными, чем заказные схемы [2]. В сравнении с другими семействами интегральных схем, такими как: простые интегральные схемы (ПИС), малые интегральные схемы (МИС), средние интегральные схемы (СИС), большие интегральные схемы (БИС) и т.д., основным преимуществом ПЛИС является свойство реконфигурируемости, которое позволяет реализовывать различные цифровые устройства на одной и той же интегральной схеме [3].

Актуальность проблемы

Современные микросхемы ПЛИС обладают свойством реконфигурируемости, что позволяет конечному пользователю самостоятельно выполнять проектирование цифровых устройств с использованием специализированных САПР. При этом длительность процесса проектирования непосредственно зависит от вычислительной мощности используемого ПК и от сложности проектируемого устройства. Для увеличения производительности процесс проектирования можно выполнять с использованием распределенных вычислений. При этом выполнить запуск САПР на нескольких процессорах затруднительно, а вот выполнение нескольких независимых процессов одновременно может значительно сократить общее время проектирования, что значительно сократит время проектирования, при обработке более чем одного цифрового устройства [1].

Цели и задачи

Основной целью магистерской работы является уменьшение времени, затрачиваемого на процесс имплементации цифрового устройства, путем реализации этого этапа проектирования с помощью распределенных вычислений. Основной идеей данной методики является одновременное параллельное выполнение некоторого количества процессов имплементации на многопроцессорном вычислительном ресурсе. В качестве такого ресурса предполагается использовать кластер ДонНТУ NeClus – параллельную вычислительную систему MIMD-архитектуры с распределенной памятью [4] Для достижения цели необходимо в рамках магистерской работы решить ряд задач: изучить особенности организации кластера; разработать протокол взаимодействия управляющего узла с операционными узлами; разработать и исследовать методику балансирования загрузки операционных узлов; исследовать эффективность использования многопроцессорного вычислительного ресурса при массовом выполнении слабосвязанных задач.

Особенности параллельных вычислений

В общем плане под параллельными вычислениями понимаются процессы обработки данных, в которых одновременно могут выполняться нескольких машинных операций. Достижение параллелизма возможно только при выполнимости следующих требований к архитектурным принципам построения вычислительной системы:

• независимость функционирования отдельных устройств ЭВМ - данное требование относится в равной степени ко всем основным компонентам вычислительной системы – к устройствам ввода-вывода, к обрабатывающим процессорам и к устройствам памяти;
• избыточность элементов вычислительной системы;
• использование специализированных устройств таких, например, как отдельных процессоров для целочисленной и вещественной арифметики, устройств многоуровневой памяти (регистры, кэш);
• дублирование устройств ЭВМ путем использования, например, нескольких однотипных обрабатывающих процессоров или нескольких устройств оперативной памяти.

Дополнительной формой обеспечения параллелизма может служить конвейерная реализация обрабатывающих устройств, при которой выполнение операций в устройствах представляется в виде исполнения последовательности составляющих операцию подкоманд; как результат, при вычислениях на таких устройствах могут находиться на разных стадиях обработки одновременно несколько различных элементов данных [5]. При рассмотрении проблемы организации параллельных вычислений следует различать следующие возможные режимы выполнения независимых частей программы:

• многозадачный режим (режим разделения времени), при котором для выполнения процессов используется единственный процессор; данный режим является псевдопараллельным, когда активным (исполняемым) может быть один единственный процесс, а все остальные процессы находятся в состоянии ожидания своей очереди на использование процессора; использование режима разделения времени может повысить эффективность организации вычислений (например, если один из процессов не может выполняться из-за ожидании вводимых данных, процессор может быть задействован для готового к исполнению процесса, кроме того, в данном режиме проявляются многие эффекты параллельных вычислений (необходимость взаимоисключения и синхронизации процессов и др.) и, как результат, этот режим может быть использован при начальной подготовке параллельных программ;
• параллельное выполнение, когда в один и тот же момент времени может выполняться несколько команд обработки данных; данный режим вычислений может быть обеспечен не только при наличии нескольких процессоров, но реализуем и при помощи конвейерных и векторных обрабатывающих устройств;
• распределенные вычисления; данный термин обычно используют для указания параллельной обработки данных, при которой используется несколько обрабатывающих устройств, достаточно удаленных друг от друга и в которых передача данных по линиям связи приводит к существенным временным задержкам; как результат, эффективная обработка данных при таком способе организации вычислений возможна только для параллельных алгоритмов с низкой интенсивностью потоков межпроцессорных передач данных; перечисленные условия является характерными, например, при организации вычислений в многомашинных вычислительных комплексах, образуемых объединением нескольких отдельных ЭВМ с помощью каналов связи локальных или глобальных информационных сетей [5].

Виды параллельных систем

Одним из наиболее распространенных способов классификации ЭВМ является систематика Флинна (Flynn), в рамках которой основное внимание при анализе архитектуры вычислительных систем уделяется способам взаимодействия последовательностей (потоков) выполняемых команд и обрабатываемых данных. В результате такого подхода различают следующие основные типы систем:

• SISD (single instruction stream / single data stream) - одиночный поток команд и одиночный поток данных. К этому классу относятся, прежде всего, классические последовательные машины, или иначе, машины фон-неймановского типа. В таких машинах есть только один поток команд, все команды обрабатываются последовательно друг за другом и каждая команда инициирует одну операцию с одним потоком данных. Не имеет значения тот факт, что для увеличения скорости обработки команд и скорости выполнения арифметических операций может применяться конвейерная обработка.
• SIMD (single instruction stream / multiple data stream) - одиночный поток команд и множественный поток данных. В архитектурах подобного рода сохраняется один поток команд, включающий, в отличие от предыдущего класса, векторные команды. Это позволяет выполнять одну арифметическую операцию сразу над многими данными – элементами вектора. Способ выполнения векторных операций не оговаривается, поэтому обработка элементов вектора может производиться либо процессорной матрицей, либо с помощью конвейера.
• MISD (multiple instruction stream / single data stream) - множественный поток команд и одиночный поток данных. Определение подразумевает наличие в архитектуре многих процессоров, обрабатывающих один и тот же поток данных. Однако ни Флинн, ни другие специалисты в области архитектуры компьютеров до сих пор не смогли представить убедительный пример реально существующей вычислительной системы, построенной на данном принципе. Ряд исследователей относят конвейерные машины к данному классу, однако это не нашло окончательного признания в научном сообществе.
• MIMD (multiple instruction stream / multiple data stream) - множественный поток команд и множественный поток данных. Этот класс предполагает, что в вычислительной системе есть несколько устройств обработки команд, объединенных в единый комплекс и работающих каждое со своим потоком команд и данных [6].

Современные параллельные системы

Основным параметром классификации параллельных компьютеров является наличие общей (SMP) или распределенной памяти (MPP). Нечто среднее между SMP и MPP представляют собой NUMA-архитектуры, где память физически распределена, но логически общедоступна. Кластерные системы являются более дешевым вариантом MPP. При поддержке команд обработки векторных данных говорят о векторно-конвейерных процессорах, которые, в свою очередь могут объединяться в PVP-системы с использованием общей или распределенной памяти. Все большую популярность приобретают идеи комбинирования различных архитектур в одной системе и построения неоднородных систем.

При организациях распределенных вычислений в глобальных сетях (Интернет) говорят о мета-компьютерах, которые, строго говоря, не представляют из себя параллельных архитектур.

Наиболее типичные классы архитектур современных параллельных компьютеров и супер-ЭВМ:

• Массивно-параллельные системы (MPP)

  Система состоит из однородных вычислительных узлов, включающих один или несколько центральных процессоров (обычно RISC), локальную память (прямой доступ к памяти других узлов невозможен), коммуникационный процессор или сетевой адаптер иногда - жесткие диски (как в SP) и/или другие устройства В/В.К системе могут быть добавлены специальные узлы ввода-вывода и управляющие узлы. Узлы связаны через некоторую коммуникационную среду (высокоскоростная сеть, коммутатор и т.п.)

• Симметричные мультипроцессорные системы (SMP)

  Система состоит из нескольких однородных процессоров и массива общей памяти (обычно из нескольких независимых блоков). Все процессоры имеют доступ к любой точке памяти с одинаковой скоростью. Процессоры подключены к памяти либо с помощью общей шины (базовые 2-4 процессорные SMP-сервера), либо с помощью crossbar-коммутатора. Аппаратно поддерживается когерентность кэшей.

• Системы с неоднородным доступом к памяти (NUMA)

  Система состоит из однородных базовых модулей (плат), состоящих из небольшого числа процессоров и блока памяти. Модули объединены с помощью высокоскоростного коммутатора. Поддерживается единое адресное пространство, аппаратно поддерживается доступ к удаленной памяти, т.е. к памяти других модулей. При этом доступ к локальной памяти в несколько раз быстрее, чем к удаленной. В случае, если аппаратно поддерживается когерентность кэшей во всей системе (обычно это так), говорят об архитектуре cc-NUMA (cache-coherent NUMA).

• Параллельные векторные системы (PVP)

  Основным признаком PVP-систем является наличие специальных векторно-конвейерных процессоров, в которых предусмотрены команды однотипной обработки векторов независимых данных, эффективно выполняющиеся на конвейерных функциональных устройствах. Как правило, несколько таких процессоров (1-16) работают одновременно над общей памятью (аналогично SMP) в рамках многопроцессорных конфигураций. Несколько таких узлов могут быть объединены с помощью коммутатора (аналогично MPP).

• Кластерные системы

  Набор рабочих станций (или даже ПК) общего назначения, используется в качестве дешевого варианта массивно-параллельного компьютера. Для связи узлов используется одна из стандартных сетевых технологий (Fast/Gigabit Ethernet, Myrinet) на базе шинной архитектуры или коммутатора. При объединении в кластер компьютеров разной мощности или разной архитектуры, говорят о гетерогенных (неоднородных) кластерах. Узлы кластера могут одновременно использоваться в качестве пользовательских рабочих станций. В случае, когда это не нужно, узлы могут быть существенно облегчены и/или установлены в стойку [7]. На рисунке 1 приведено фото кластера ДонНТУ.

Рисунок 1 - Кластер ДонНТУ

Особенности синтеза цифровых устройств

Для синтеза цифровых устройств, в рамках магистерской, предполагается использование интегральных схем семейства ПЛИС, учитывая их преимущества, описанные ранее.

Базис ПЛИС

ПЛИС (программируемая логическая интегральная схема) - это большие интегральные микросхемы матричного типа, позволяющие программным способом реализовать логические функции большой сложности. Физическим ограничением быстродействия присущей всем традиционным архитектурам процессоров является последовательное выполнение команд [8]. В отличие от обычных цифровых микросхем, логика работы ПЛИС не определяется при изготовлении, а задаётся посредством программирования (проектирования). Для программирования используются программаторы и отладочные среды, позволяющие задать желаемую структуру цифрового устройства в виде принципиальной электрической схемы или программы на специальных языках описания аппаратуры: Verilog, VHDL, AHDL и др. Альтернативой ПЛИС являются: программируемые логические контроллеры (ПЛК), базовые матричные кристаллы (БМК), требующие заводского производственного процесса для программирования; ASIC — специализированные заказные большие интегральные схемы(БИС), которые при мелкосерийном и единичном производстве существенно дороже; специализированные компьютеры, процессоры (например, цифровой сигнальный процессор) или микроконтроллеры, которые из-за программного способа реализации алгоритмов в работе медленнее ПЛИС.

Некоторые производители ПЛИС предлагают программные процессоры для своих ПЛИС, которые могут быть модифицированы под конкретную задачу, а затем встроены в ПЛИС. Тем самым обеспечивается уменьшение места на печатной плате и упрощение проектирования самой ПЛИС, за счёт быстродействия [9]

Типы ПЛИС

В настоящее время наибольшую распространенность получили два типа архитектур ПЛИС:

1) CPLD (англ. complex programmable logic device). Примерами ПЛИС данной архитектуры является семейство MAX фирмы Altera и CoolRunner фирмы Xilinx. Для архитектур данных ПЛИС характерны крупные логические блоки - макроячейки (macrocells). Современные ПЛИС содержат до нескольких сотен макроячеек. Каждая макроячейка реализует функцию нескольких переменных и содержит триггер для хранения полученного результата. Для ПЛИС данной архитектуры характерно крайне низкая потребляемая мощность в статическом режиме (потребляемый ток порядка десятков микроампер), которая линейно возрастает с увеличением тактовой частоты. Также для данной архитектуры характерны жесткие временные задержки между макроячейками а следовательно и выводами микросхемы. Типичное время задержки между выводами (pin-to-pin) составляет единицы наносекунд. Прошивка ПЛИС данной архитектуры хранится внутри микросхемы в энергонезависимой памяти.

2)FPGA (англ. field-programmable gate array). ПЛИС данной архитектуры обладают намного более развитой архитектурой, по сравнению с CPLD. Основной структурной единицей ПЛИС данной архитектуры является LUT(англ. Lookup tables) - таблицы преобразования, позволяющие реализовывать логические функции. Современные ПЛИС содержат аппаратные умножители в том числе с накоплением (MAC), блоки внутренней памяти, аппаратные интерфейсы для DDRx SDRAM, аппаратные ядра PCIexpress, встроенные микропроцессорные ядра, трансиверы для организации скоростной передачи данных между ПЛИС и внешними устройствами [8]. На рисунке 2 приведена плата Xilinx Spartan 3E – типичный представитель архитектуры FPGA.

Рисунок 2 - Плата Xilinx Spartan

Результаты

На кафедре компьютерной инженерии Донецкого национального технического университета было разработано программное обеспечение (ПО), используемое для синтеза моделей управляющих автоматов. Исходными данными для синтеза является описание граф-схемы алгоритма управления в формате языка XML [1]. При помощи ПО можно получить множество моделей управляющих устройств, интерпретирующих исходную ГСА. Модель представляет собой vhd-файлы, описывающие функциональные узлы управляющих устройств, а также mif–файлы, содержащие микропрограмму (для управляющих устройств с памятью).

Магистерская работа направлена на организацию параллельной обработки большого числа моделей управляющих устройств. При правильной организации процесса параллельной имплементации большого количества моделей управляющих устройств, временные затраты на исследования будут значительно снижены, по сравнению с последовательной имплементацией.

В качестве САПР, для имплементации моделей будет использоваться Xilinx ISE. Процесс имплементации будет полностью автоматизирован, благодаря использованию tcl-скрипта, указывающего название проекта, перечень включаемых файлов, тип и семейство базовой микросхемы ПЛИС, а также дополнительные параметры. На рисунке 3 приведена работа алгоритма параллельной обработки.

Рисунок 3 – Работа алгоритма параллельной имплементации.

Важное замечание

При написании реферата магистерская работа еще не завершена, планируемое время завершения — декабрь 2012 года. Полный текст работы и материалы по теме могут быть получены у автора или его руководителя после указанной даты.

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

• Перкин П.В. Использование распределенных вычислений при разработке цифровых устройств управления / Перкин П.В., Мирошкин А.Н., Зеленева И.Я. Інформаційні управляючі системи та комп'ютерний моніторинг (ІУСКМ-2012): III Всеукраїнська науково-технічна конференція студентів, аспірантів та молодих вчених, 16-18 квітня 2012 р., м. Донецьк / Донец. націонал. техн. ун-т; редкол.: Є.О. Башков (голова) та ін. - Донецьк: ДонНТУ, 2012. - С. 655-657.


• Переход от заказных микросхем к ПЛИС и наоборот [Электронный ресурс] – Режим доступа: www.rlocman.ru/i /File/2007/08/13/FPGA_236-239.pdf


• Терехова О.Н. Большая интегральная схема [Электронный ресурс] – Режим доступа: www.russika.ru/t.php?t=3765


• Кластер ДонНТУ [Электронный ресурс] – Режим доступа: neclus.donntu.ru


• Гергель В.П. Учебная рабочая программа по общему курсу Многопроцессорные системы и параллельное программирование для студентов, обучающихся по программе подготовки бакалавров физико-математических наук по направлению Прикладная математика и информатика [Электронный ресурс] – Режим доступа: www.software.unn.ac.ru/ccam/files/HTML_Version/part1.html


• Высокопроизводительные компьютеры – под. ред. Воеводина В.В. [Электронный ресурс] – Режим доступа: parallel.ru/computers/taxonomy/flynn.html


• Высокопроизводительные компьютеры – под. ред. Воеводина В.В. [Электронный ресурс] – Режим доступа: parallel.ru/computers/classes.html


• Блог Чиповода ПЛИС [Электронный ресурс] – Режим доступа: www.chipovod.ru/category/plis


• ПЛИС. Материал из Википедии — свободной энциклопедии [Электронный ресурс] – Режим доступа: http://ru.wikipedia.org/wiki/%D0%9F%D0%9B%D0%98%D0%A1