Разработка алгоритма и программы сортировки массива из 20 чисел по возрастанию

Разработка алгоритма и программы сортировки массива из 20 чисел по возрастанию

КУРСОВОЙ ПРОЕКТ

по дисциплине

«Микропроцессорные устройства управления роботов и их программное обеспечение»

Разработка алгоритма и программы сортировки массива из 20 чисел по возрастанию

Исходные данные

h, 11h, 01h, 17h, 07h, 03h, 21h, 32h, 32h, 12h, 42h, 34h, 22h, 14h, 55h, 11h, 17h, 77h, 31h, 12h.

Содержание

Введение

Блок-схема алгоритма работы программы

Алгоритм работы программы

Листинг программы

Результаты выполнения программы

Заключение

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

Введение

Программы можно писать не только для x86 компьютеров. Более того, большая часть процессоров в мире - НЕ x86. Основная часть микропроцессоров сейчас - это микроконтроллеры. В большинстве учебных заведений бывшего СССР изучение микроконтроллеров начинается с легендарного Intel 8051 (официальное название - MCS 51, также он известен как i8051 и MCS-51). У этого микроконтроллера есть assembler, очень похожий на ассемблер привычных нам процессоров x86 архитектуры. Этот контроллер применялся в старых клавиатурах, да и вообще много где он применялся. Будем называть этот микропроцессор Intel 8051 или MCS 51, потому что во всем мире он известен именно под этим названием.

Цель работы:

Необходимо отсортировать по возрастанию массив из 20 шестнадцатеричных чисел. Чтобы это сделать надо найти максимальный элемент и поместить в конец массива, потом второй по величине и поставить его на предпоследнее место массива и т.д.

Особенности микроконтроллера8051 - это 8 разрядный однокристальный микроконтроллер гардвардской архитектуры, впервые произведенный компанией Intel в 1980 году и предназначенный для использования во встраиваемых (embedded) системах. Он состоит из процессорного ядра (CPU), ОЗУ, ПЗУ, последовательного и параллельного порта, и еще небольшого количества дополнительных элементов. Программы для него можно писать на специализированном ассемблере, который очень напоминает ассемблер для x86-процессоров, или на языке С. Но, конечно, есть ограничения. У нас в распоряжении всего 128 байт ОЗУ (называется память DATA), 4 кбайта встроенного ПЗУ для хранения самой программы (память программ), и 64 кбайта в ПЗУ (называется XDATA - external data, или память данных). Зато есть прерывания.

Восьмиразрядные высокопроизводительные однокристальные микроЭВМ (ОМЭВМ) семейства МК51 выполнены по высококачественной n-МОП технологий (серия 1816) и КМОП технологии (серия 1830) .

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

ОМЭВМ КР1816ВЕ51 и КР1830ВЕ51 содержат масочно-программируемое в процессе изготовления кристалла ПЗУ памяти программ емкостью 4096 байт и рассчитаны на применение в массовой продукции. За счет использования внешних микросхем памяти общий объем памяти программ может быть расширен до 64 Кбайт.

ОМЭВМ КМ1816ВЕ751 содержит ППЗУ емкостью 4096 байт со стиранием ультрафиолетовым излучением и удобна на этапе разработки системы при отладке программ, а также при производстве небольшими партиями или при создании систем, требующих в процессе эксплуатации периодической подстройки. За счет использования внешних микросхем памяти общий объем памяти программ может быть расширен до 64 Кбайт.

ОМЭВМ КР1816ВЕ31 и КР183ОВЕ31 не содержат встроенной памяти программ, однако могут использовать до 64 Кбайт внешней постоянной или перепрограммируемой памяти программ и эффективно использоваться в системах, требующих существенно большего по объему (чем 4 Кбайт на кристалле) ПЗУ памяти программ.

Каждая из перечисленных выше микросхем является соответственно аналогом БИС 8051, 80С51, 8751, 8031, 80С31 семейства MCS-51 фирмы Intel (США).

Каждая ОМЭВМ рассматриваемого семейства содержит встроенное ОЗУ памяти данных емкостью 128 байт с возможностью расширения общего объема оперативной памяти данных до 64 Кбайт за счет использования внешних микросхем ЗУПВ.

Общий объем памяти ОМЭВМ семейства МК51 может достигать 128 Кбайт: 64 Кбайт памяти программ и 64 Кбайт памяти данных.

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

) центральный восьмиразрядный процессор;

) память программ объемом 4 Кбайт (только КМ1816ВЕ751, КР1816ВЕ51 и КР1830ВЕ51);

) память данных объемом 128 байт;

) четыре восьмиразрядных программируемых канала ввода-вывода;

) два 16-битовых многорежимных таймера/счетчика;

) систему прерываний с пятью векторами и двумя уровнями;

) последовательный интерфейс;

) тактовый генератор.

Аккумулятор. АСС - регистр аккумулятора. Команды, предназначенные для работы с аккумулятором, используют мнемонику "А", например, MOV А, Р2.Мнемоника "АСС" используется, к примеру, при побитовой адресации аккумулятора. Так, символическое имя пятого бита аккумулятора при использовании ассемблера ASM51 будет следующим: АСС.5.

Регистр В. Используется во время операций умножения и деления. Для других инструкций регистр В может рассматриваться как дополнительный сверхоперативный регистр.

Регистр состояния программы. Регистр PSW содержит информацию о состоянии программы.

Указатель стека SP. 8-битовый регистр, содержимое которого инкрементируется перед записью данных в стек при выполнении команд PUSH и CALL. При начальном сбросе указатель стека устанавливается в 07Н, а область стека в ОЗУ данных начинается с адреса 08Н. При необходимости путем переопределения указателя стека область стека может быть расположена в любом месте внутреннего ОЗУ данных микроЭВМ.

Указатель данных. Указатель данных (DPTR) состоит из старшего байта (DPH) и младшего байта (DPL). Содержит 16-битовый адрес при обращении к внешней памяти. Может использоваться как 16-битовый регистр или как два независимых восьмибитовых регистра.

Порт0-ПортЗ. Регистрами специальных функций Р0, Р1, Р2, РЗ являются регистры-"защелки" соответственно портов Р0, Р1, Р2, РЗ.

Буфер последовательного порта. SBUF представляет собой два отдельных регистра: буфер передатчика и буфер приемника. Когда данные записываются в SBUF, они поступают в буфер передатчика, причем запись байта в SBUF автоматически инициирует его передачу через последовательный порт. Когда данные читаются из SBUF, они выбираются из буфера приемника.

Регистры таймера. Регистровые пары (TH0.TL0) и (TH1.TL1) образуют 16- битовые счетные регистры соответственно таймера/счетчика 0 и таймера/счетчика 1.

Регистры управления. Регистры специальных функций IP, IE, TMOD, TCON, SCON и PCON содержат биты управления и биты состояния системы прерываний, таймеров/счетчиков и последовательного порта. ОМЭВМ при функционировании обеспечивает:

минимальное время выполнения команд сложения - 1 мкс;

аппаратное умножение и деление с минимальным временем выполнения команд умножения/деления - 4 мкс

Блок-схема алгоритма работы программы

Сначала программа записывает данные во внешнюю память. После этого она считывает исходные числа из внешней памяти во внутреннюю и одновременно сортирует их.

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

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

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

Процесс продолжается до использования всех чисел из внешней памяти.

После этого отсортированные элементы переписываются обратно во внешнюю память.

Использование памяти

Участки памяти:: 0000h…0019h - область сортируемых чисел: 40h…53h - область, используемая для промежуточного хранения и сортировки чисел

Регистры:: хранит адрес байта в XDATA (0000h..0019h).: используется как буфер для передачи данных из XDATA в DATA и для копирования данных из одного участка памяти в другой.: хранит адрес обрабатываемого элемента в DATA (40h..53h): используется как локальный счетчик цикла.: хранит данные из DPL для запоминания адреса текущего самого большего элемента.

Участок 36h:хранит текущее самое большое число.

Рис 1.

Листинг программы

00h;смещение от началаstart;переход к началу50h;память данных:

; ИНИЦИАЛИЗАЦИЯ

_create_data: ;Модуль устанавливает начальные значения байтам в XDATA с адресами 00h..09hDPTR, #0000h;адресA, #13h; 1-e число@DPTR, A; занести число по адресуDPTR;увеличить адрес на 1

mov A, #11h; 2-e число@DPTR, ADPTRA, #01h; 3-e число@DPTR, ADPTRA, #17h; 4-e число@DPTR, ADPTRA, #07h; 5-e число@DPTR, ADPTRA, #03h; 6-e число@DPTR, ADPTRA, #21h; 7-e число@DPTR, ADPTRA, #32h; 8-e число@DPTR, ADPTRA, #32h; 9-e число@DPTR, ADPTRA, #12h; 10-e число@DPTR, AA, #42h; 11-e число@DPTR, ADPTRA, #34h; 12-e число@DPTR, ADPTRA, #22h; 13-e число@DPTR, ADPTRA, #14h; 14-e число@DPTR, ADPTRA, #55h; 15-e число@DPTR, ADPTRA, #11h; 16-e число@DPTR, ADPTRA, #17h; 17-e число@DPTR, ADPTRA, #77h; 18-e число@DPTR, ADPTRA, #31h; 19-e число@DPTR, ADPTRA, #12h; 20-e число@DPTR, A

;СОРТИРОВКА_sort_massiv: метка начала сортировки R0, #53h

metka1: метка главного цикла сортировки

mov 54h, #00hR2, DPL module_search_massiv переход на метку поиска макс

metka_vozvrata1: метка возврата из поиска макс эл.

mov DPL, R2A, #00hDPL@DPTR, A@R0, 54hR0R0, #3Fh, metka1 module_data_to_xdata переход на метку вывода данных

module_search_massiv: начало кода поска макс эл массива

mov DPTR, #0000h

metka2: главный цикл поиска

movx A, @DPTRDPTRR1, DPLA, 54h, metka3 _vozvrata2: перед возвратом R1, #14h, metka2 переход на метку вложенного цикла

jmp metka_vozvrata1 переход на возврат из поиска

metka3:

jc metka_vozvrata2 продолжаем сканировать

mov 54h, AR2, DPL metka_vozvrata2 пока все не переберем программа в цикле

;ПЕРЕМЕЩЕНИЕ ОТСОРТИРОВАННЫХ ЧИСЕЛ ОБРАТНО ВО ВНЕШНЮЮ ПАМЯТЬ

module_data_to_xdata:DPTR, #0000hR0, #40h: цикл выводаA, @R0@DPTR, ADPTRR0R0, #54h, metka4 на метку цикла

final:.

Результаты выполнения программы:

сортировка массив число команда

Таблица команд и число их выполнения:

Время затраченное программой на своё выполнение:= 5 + 20 + 20 + 40 + 60 + 20 + 100 + 80 + 40 + 400 + 40 + 60 + 1680 + 540 + 420 + 1200 + 800 + 280 + 1320 + 40 + 40 = 7305 тактов = 609 циклов = 203 мкс

Объём памяти занимаемый программой:= 24 * (1 + 20 + 20 + 20 + 20 + 20 + 20 + 40 + 400 + 20 + 560 + 180 + 420 + 400 + 400 + 440 + 20) + 12 * (1 + 20 + 20 + 20 + 40 + 20 + 140 + 20) = 74916 байт = 73Кб

Заключение

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

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

Герасимов В.В. «Микропроцессорное устройство и управление роботов» лекции 2012.://atdevil.ru/wp-content/uploads/2011/02/mcs51.pdf

Юсупов Ю.А. “Система команд микроконтроллеров MCS-51”, 2010.