ДонНТУ   Портал магистров

Реферат по теме выпускной работы

Содержание

Введение

На сегодняшний день в мире существует более 130 миллионов компьютеров и более 80 % из них объединены в различные информационно-вычислительные сети от малых локальных сетей в офисах до глобальных сетей типа Internet. Всемирная тенденция к объединению компьютеров в сети обусловлена рядом важных причин, таких как ускорение передачи информационных сообщений, возможность быстрого обмена информацией между пользователями, получение и передача сообщений (факсов, E - Mail писем и прочего) не отходя от рабочего места, возможность мгновенного получения любой информации из любой точки земного шара, а так же обмен информацией между компьютерами разных фирм производителей работающих под разным программным обеспечением.

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

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

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

Особенно эта перегруженность касается сенсорных локальных вычислительных систем. Где происходит одновременный контроль большого количества параметров, постоянный «опрос» датчиков и детекторов. Это создает большой поток информации, который необходимо принять и вовремя обработать.

Возникает потребность динамически изменять очередность обслуживания заявок от однородных объектов с одноранговыми приоритетами, состояния которых может отличаться и стать критическим в потоке информации.

1. Актуальность темы

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

2. Цель магистерской работы

Цель магистерской работы заключается в исследовании существующих алгоритмов сортировки и обработки очереди данных на обслуживание, а так же создание наиболее выгодного алгоритма. Основой для разработки нового метода сортировки и обработки данных являются современные ПЛИС FPGA.

Постановка задачи:

На основе анализа традиционных методов управления обслуживанием информационных потоков, алгоритмов аппаратного и программного упорядочивания данных, необходимо представить оптимальный по времени метод динамического управления потоками информации и осуществить синтез системы со следующими функциями: формирование управляющей информации для перестройки дисциплины обслуживания на основании параметров состояния входного потока (статического приоритета, величины штрафа за потерю заявки, скорости «старения» заявки в очереди на обслуживание); выбор оптимального алгоритма управления в реальном масштабе времени в зависимости от загрузки системы.

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

3. Новые технологии обработки данных

Реконфигурируемая обработка данных (reconfigurable computing), является новейшей технологией, которая использует кристаллы ПЛИС типа FPGA (Field Programmable Gate Array) для аппаратной реализации алгоритмов. В отличие от традиционной фон-Неймановской архитектуры, обеспечивающей универсальное решение для всех алгоритмов, архитектура, основанная на кристаллах FPGA, позволяет разработчику проектировать структуру для каждого отдельного алгоритма. Логическая плотность или количество вентилей кристаллов FPGA определяет, какой сложности алгоритм может быть реализован. Алгоритм может также быть разбит на фрагменты, которые многократно передаются в то же самое устройство, приводя к технике, называемой реконфигурацией во время выполнения. Таким образом, технология “reconfigurable computing” представляет изменение парадигмы в проектировании компьютера. Кроме того, линия раздела между программируемыми процессорами и кристаллами FPGA становится менее различимой: современные кристаллы FPGA (серии Virtex II-Pro) включают увеличенную локальную память, аппаратные умножители, которые являются стандартными составляющими современных микропроцессоров, а также аппаратные ядра RISC процессоров PowerPC. Под конфигурируемыми вычислительными системами понимаются вычислительные платформы, архитектура которых может быть изменена программно для реализации каждого конкретного приложения. Код программного обеспечения, загружаемый в конфигурируемый компьютер, является форматированным проектом, разработанным для определенного алгоритма.

Проблема объединения аппаратных и программных средств является более значимой, чем увеличение логической плотности и расширение области приложений. В отличие от систем проектирования прошлого новые платформы должны удовлетворять потребностям и навыкам специалистов - инженеров-разработчиков аппаратных и программных средств. Использование таких платформ делает возможным верификацию проектов в реальном масштабе времени за счет объединения разрабатываемых аппаратных средств системы с окружающей средой. Барьеры между аппаратными и программными средствами начинают стираться, так как программное обеспечение позволяет конфигурировать аппаратные средства во время его работы. Такая технология разработки объектных аппаратных средств предоставляет проектировщику возможность работы с проектами, написанными на стандартном языке программирования "C", и загрузки этих проектов соответствующей прикладной программой, используемой как функция языка "C". Уникальное свойство реконфигурируемости позволяет в реальном времени эффективно выполнять отладку цифровых проектов [2].

4. Используемые в данный момент методы сортировки

4.1 Сортировка вставкой

Сортировка вставкой является последней из класса простых алгоритмов сортировки. При сортировке вставкой сначала упорядочиваются два элемента массива. Затем делается вставка третьего элемента в соответствующее место по отношению к первым двум элементам. Затем делается вставка четвертого элемента в список из трех элементов. Этот процесс повторяется до тех пор, пока все элементы не будут упорядочены. Например, для массива «dcab» сортировка вставкой будет проходить следующим образом:

  1. исходное состояние: d c a b;
  2. первый проход: c d a b;
  3. второй проход: a c d b;
  4. третий проход: a b c d [3].

4.2 Сортировка пузырьком

Расположим массив сверху вниз, от нулевого элемента - к последнему. Идея метода: шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами.

Начальное положение сортировки

Рисунок 1 – Начальное положение сортировки

После нулевого прохода по массиву «вверху» оказывается самый «легкий« элемент - отсюда аналогия с пузырьком. Следующий проход делается до второго сверху элемента, таким образом второй по величине элемент поднимается на правильную позицию... Делаем проходы по все уменьшающейся нижней части массива до тех пор, пока в ней не останется только один элемент. На этом сортировка заканчивается, так как последовательность упорядочена по возрастанию [4].

Конечный результат сортировки

Рисунок 2 – Конечный результат сортировки

5. Обзор разработок по теме

Данной проблематикой в нашем университете занимаются в специальной лаборатории ПЛИС FPGA, основанной специалистами из Германии.

5.1 Модуль сортировки с последовательным вводом данных

Ряд авторов (А.А. Гриценко, С.Ю. Сероштан, Ю.Е. Зинченко) разработали аппаратный модуль сортировки с последовательным вводом данных и минимальным временем обработки.

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

Использование специальных аппаратных модулей для решения тех задач, которые раньше, по большей части, решались программно, стало на данный момент актуальной задачей в связи с активным развитием, а также распространением, различных видов программируемых логических интегральных схем (ПЛИС). Современные ПЛИС принято разделять на классы, основываясь, в частности, на способе их программирования. В соответствии с данной классификацией можно выделить ПЛИС FPGA, которые пользуются все большей популярностью среди разработчиков. В свою очередь, ПЛИС FPGA разделяют на ПЛИС с низкой и с высокой стоимостью. Ключевое различие заключается, в первую очередь, в сложности их архитектуры. В частности, это выражается в сложности базового элемента, то есть, генератора функции. В данной статье рассматриваются схемы, которые имеют низкую стоимость, то есть, это ПЛИС семейств Altera Cyclone и Xilinx Spartan. Причиной для разработки предлагаемого модуля сортировки стало исследование подходов к минимизации времени работы модуля. То есть, минимизации времени, которое необходимо для обработки одного элемента последовательности, которая упорядочивается. Основной для разрабатываемого модуля стала схема, которая была описана в. Следует отметить, что данное описание имеет достаточно низкий уровень детализации. Поэтому в данной статье рассматривается вариант его реализации, который может использоваться в базисе ПЛИС FPGA [5].

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

Рисунок 3 – Классификация аппаратных модулей сортировки по критерию способа ввода данных

5.2 Модуль сортировки с параллельным вводом данных

Тематика моей работы переплетается с разработками вышеуказанных авторов и является альтернативным вариантом. Отличие заключается во вводе данных.

Работа данного модуля осуществляется в два этапа.
Этап 1.

Происходит накопление информации. Сенсорные датчики снимают показания и передают их на входы данных регистров (A-D), где преобразуются в двоичные последовательности. Эти последовательности попарно поступают из регистров на схемы сравнения. В компараторе происходит сравнение, и в зависимости от того какое значение больше, появится сигнал на выходе GT или LT. В случае, если значения какой-то пары окажутся равными, предусмотрена цепочка с логическими элементами OR и NOR. Тогда для дальнейшего сравнения берется одно из значений (в данном варианте значение с выхода GT).

цепочка с логическими элементами OR и NOR

Рисунок 4 – Цепочка с логическими элементами OR и NOR

Кроме компаратора входные данные поступают на мультиплексор, в котором осуществляется выбор на основе данных схемы сравнения. Аналогично происходит и на другой паре регистров С и D. Далее мы имеем уже 2 максимальных значения из 4-х регистров. Эти 2 значения так же проходят цепь компаратора и мультиплексора, на выходе которого остается одно максимальное значение. Это значение по цепи обратной связи поступает на второй вход мультиплексора, который установлен в начале нашей схемы.

Выбор наибольшего значения в схеме

Рисунок 4 – Выбор наибольшего значения в схеме
(анимация: 8 кадров, 250 килобайт)

Этап 2.

Включение в работу схемы флага (триггера) происходит через интервал времени, равный прохождению входных данных от датчиков, через мультиплексоры на регистры + время прохождения схемы упорядочивания. Его основная задача – разрешение на пересылку информации из регистра с критическим значением диагностического параметра в регистр, содержимое которого будет первым в очереди заявок на обработку.

Так как схема состоит из одинаковых ступеней, то их количество будет составлять , где n – количество регистров на входе.

Выводы

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

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

Список источников

  1. Компьютерные сети [Электронный ресурс]. http://www.radioland.net.ua.
  2. Палагин А.В., Опанасенко В.Н., Сахарин В.Г. Системы верификации на основе реконфигурируемых устройств. – ISSN 1028-9763. Математические машины и системы, 2004, № 2.
  3. Сортировка вставкой. http://borlpasc.narod.ru/inzik/glava1/sortivs.htm.
  4. Сортировка пузырьком. http://algolist.manual.ru/sort/bubble_sort.php.
  5. Гриценко А. А., Сероштан С.Ю., Зинченко Ю.Е. Разработка аппаратного модуля сортировки с последовательным вводом данных и минимальным временем обработки. / Наукові праці ДонНТУ ISSN 1996-1588, Серія "Інформатика, кібернетика та обчислювальна техніка" випуск 13(185), 2011.
  6. Поляков А. К. Языки VHDL и VERILOG в проектировании цифровой аппаратуры / А.К. Поляков. – М.: СОЛОН-Пресс, 2003. – 320 с.
  7. Максфилд К. Проектирование на ПЛИС. Курс молодого бойца / К. Максфилд. – М.: Издательский дом «Додэка-XXI», 2007. – 408 с.
  8. Палагин А. В. Реконфигурируемые вычислительные системы: Основы и приложения / А. В. Палагин, В. Н Опанасенко. – К.: Просвіта, 2006. – 280 с.: ил.
  9. Grout I. Digital systems design with FPGAs / I. Grout. – Elsevier, 2008. – 724 pp.
  10. Batcher K. E. Sorting networks and their applications / K. E. Batcher. – "Goodyear Aerospace Corporation", 1968. – 8 pp.
  11. Жабин В.И. Исследование методов построения вычислительных устройств на основе FPGA / В.И. Жабин, Н.А. Ковалев // Технология и конструирование в электронной аппаратуре. – 2002. – № 2. – С. 35-39.