Конспект лекций по курсу Системное программирвание для специальности Информатика Лекция 1




НазваниеКонспект лекций по курсу Системное программирвание для специальности Информатика Лекция 1
страница8/41
Дата публикации03.03.2013
Размер5.22 Mb.
ТипКонспект
uchebilka.ru > Информатика > Конспект
1   ...   4   5   6   7   8   9   10   11   ...   41

Листинг 8. Поиск элемента массива, находящегося в диапазоне 50-100 (окончательный вариант)
.686

.model flat

option casemap: none

.data

al DD 34. -93. 9 13. 7. 1

len EQU $-al

g50 DB ?

1100...DB ?

code

Find_num proc

lea ESI...al

mov ECX. len

shr ECX. 2

next:

cmp dword ptr EESI]. 50

setge g50

cmp dword ptr EESI]. 100

setle 1100

mov AL. g50

mov AL, 1100

mov EAX. [ESI]

jo exit

add ESI. 4

dec ECX

jtlZ RGXt

raov EAX. 0

-exit:

ret

find_num=endp

end

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

инструкции ассемблера jmp метка
Например, следующая последовательность команд представляет собой простой цикл:
хоr ЕВХ. ЕВХ L1:

инструкции ассемблера

1nc ЕВХ

cmp ЕВХ. 100000

je exit

jmp LI

exit:
В этом цикле выполняется увеличение содержимого регистра ЕВХ от 0 до 100 000, и при достижении этого значения передается управление на метку exit.

Проанализируем этот фрагмент кода с точки зрения быстродействия. Его нельзя назвать оптимальным, поскольку для анализа условия выхода из цикла и самого выхода из цикла используется несколько команд переходов. Для цикла c фиксированным числом итераций проблему оптимизации решить несложно, как показано в следующем фрагменте кода:
mov EDX. 100000 L1:

инструкции ассемблера

dec EDX jnz LI exit:
Как видно из этого листинга, значение счетчика цикла помещается в регистр EDX. Этот фрагмент более эффективен, чем предыдущий. Команда декремента устанавливает флаг ZF, когда счетчик становится равным 0, что приводит к выходу из цикла, иначе цикл продолжается. Этот фрагмент кода требует меньшего количества команд и будет выполняться быстрее.

Еще один способ повышения быстродействия циклических вычислений состоит в том, чтобы по возможности избавиться от ветвлений и условных переходов внутри самого цикла. Рассмотрим пример (листинг 9). Пусть в массиве целых чисел необходимо заменить все отрицательные числа нулями. Это можно сделать с помощью 32-разрядной процедуры на ассемблере (назовем ее setO).
Листинг 9. Замена отрицательных элементов массива целых чисел нулевыми значениями

.686

.model flat

option casemap:none

.data

iarray DD -73. 931. -89. 92. - 67. 30

len EQU $-iarray
.code

_set0 proc

lea ESI. iarray : адрес массива -> ESI

mov EDX. Len : размер массива (в байтах) -> EDX

shr EDX. 2 : преобразовать в количество двойных

: слов
next:

cmp dword ptr [ESI]. 0 : сравнить элемент массива с

: нулем

jge no_change :если больше нуля, оставить без изменения

mov dword ptr [ESI].0 : если меньше нуля, заменить на 0
no_change:

add ESI. 4 : перейти к следующему элементу

dec EDX : уменьшить счетчик цикла на 1

jnz next : переход к следующей итерации

lea EAX. Iarray : адрес массива -> ЕАХ

ret

_set0 endp

end
В этой процедуре выполняется основной цикл, операторы которого находятся между меткой next и инструкцией jnz next и образуют тело цикла. В теле цикла присутствует команда jge nochange, выполняющая ветвление в зависимости от результата сравнения. Подобные изменения в последовательности выполнения отрицательно сказываются на быстродействии, поэтому попробуем избавиться от лишнего перехода. Сделать это можно с помощью команды setge. Посмотрим, как будет выглядеть модифицированный вариант процедуры (листинг 10).
Листинг 10. Модифицированный вариант листинга 9, в котором используется команда setge

.686

.model flat

option casemap:none

.data

iarray DD 273. 417. -31. -92. -67. 360

len EQU $-iarray

.code

_set0::proc

push EBX

tea ESI. iarray

mov EDX. len

shr EDX..2 next:

xor EBX. .EBX

cnip dword ptr EKSI]. 0

setge BL

mil EBX.:ilword::ptr [ESI]

mov dword ptr EESI]. EBX

add ESI. A

dec EDX

jnz riext

lea EAX. iarray

pop EBX

ret

_setO endp end
Хочу отметить, что даже хорошо оптимизированный цикл иногда не работает так быстро, как ожидает разработчик. Для дальнейшего повышения эффективности прибегают к так называемому разворачиванию (unrolling) цикла. Этот термин означает на самом деле, что цикл должен выполнять больше действий в одной итерации для уменьшения количества итераций. Это дает неплохой эффект, и сейчас мы рассмотрим два фрагмента программного кода, в которых имеет место разворачивание циклов.

В качестве исходного (неоптимизированного) фрагмента кода возьмем, например, копирование данных размером в двойное слово из одного буфера памяти (обозначим его как src) в другой (dst). Исходный текст представлен в листинге 11.
Листинг 11. Копирование двойных слов без оптимизации

...

.data

src DD 34 -6 12. 99. 369. 267

len EQU S-src

dst DD 6 DUP (?)

.code

...

mov ESI. src : адрес источника src-> ESI
mov EDI. dst : адрес приемника dst -> EDI
mov ECX. Ten : значение счетчика байтов -> ECX
shr ECX. 2 : перевести значение счетчика

: в двойные слова

l;

mov EAX. [ESI]

add ESI. 4

mov [EDI].FAX

addrEDI. 4

dec ECX

jnz LI

...
Для разворачивания цикла выполним одновременно копирование двух двойных слов. Исходный текст оптимизированного фрагмента кода показан в листинге 12 (изменения выделены жирным шрифтом).
Листинг 12. Модифицированный код листинга 11
.data

src DD 34 -6 12. 99. 369. 267

len EQU $-src

dst DD 6 DUP (?)

.code

...

mov ESI. src : :Адрес источника sre->ESI

mov EDI. dst : адрес приемника::dst-> EDI

mov ECX. len : значение счетчика байтов -> ECX

shr ECX. 3 : перевести значение счетчика

: в учетверенные слова (два

: .двойных слова)

L1:

mov EAX. [ESI] : сохраняем первое двойное слово из

: пары в регистре FAX

mov EBX, [ESI+=4] : сохраняем второе двойное слово в

: регистре EBX

mov [EDI], EAX : помещаем-первоедвойное слово в

: регистр EDI

mov [EDI+=4],EBX : записываем второе двойное слово "по

: адресу в регистра EDI на 4 больше

: предыдущего
add ESI, В : продвигаем адреса источника и приемника

: так, чтобы они указывали на следующее

add EDI, 8 : двойное слово

dec ECX
jnz label : переход к следующей итерации или

: выход из цикла
Разворачивание позволяет наполовину скомпенсировать снижение производительности программы, в которой используется такой цикл. Если оперировать не двумя, а четырьмя двойными словами, то можно развернуть цикл далее.

Приведу еще один пример разворачивания циклов. Пусть имеется массив из 10 целых чисел и требуется присвоить элементам массива с четными номерами значение 0, а элементам с нечетными номерами значение 1. Если особо не задумываться над качеством программы, то можно быстро написать фрагмент программного кода, представленный в листинге 13.

Листинг 13. Обработка четных и нечетных элементов целочисленного массива

...

.data

iarray DD 10 dup (0)

len EQU $-iarray

.code

...

mov ECX, len : число элементов массива (в байтах)

: -> ЕСХ

lea ESI. i1 : адрес первого элемента массива -> ESI

mov ЕВХ. 2 : помещаем делитель 2 в регистр ЕВХ для : определения, четный или нечетный элемент next:

mov ЕАХ. ЕСХ : счетчик элементов -> ЕАХ

div ЕВХ : определяем, четный или нечетный

: порядковый номер у элемента массива

cmp EDX. О

jne store_l : если нечетный, присваиваем

:элементу значение 1

mov DWORD PTR [ESI]. 0 : если четный, присваиваем

: элементу значение О

jmp next_addr

store_l:

mov DWORD PTR [ESI]. 1
next_addr: : адрес следующего элемента массива

add ESI, 4

loop next

...
Данный фрагмент программного кода можно оптимизировать, если обрабатывать в каждой итерации два двойных слова вместо одного. Модифицируем предыдущий пример, поместив программный код в процедуру unr_l. Исходный текст измененной программы показан в листинге 14.
Листинг 14. Модифицированный код листинга.13 с разворачиванием цикла
.686

model flat

option casemap: none

.data

iarray DD 10 dop (7)

len EQU $-iarray

.code

_unr_l proc

lea ESI, iarray

mov EBX, len

shr EBX, 2

dec EBX

xor EDX, EOX
next:

mov DWORD PTR [ESI], 0

mov DWORD PTR [ESI+4], 1

add EDX, 2

cmp EDX, EBX

jae exit

add ESI, В

jmp next
-exit:

lea EAX. iarray

ret

_unr_l endp

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

В каждой итерации обрабатываются одновременно два элемента массива командами
mov DWORD PTR [ESI]. 0

mov DWORD PTR [ESI+4].l
В конце каждой итерации содержимое регистра ESI увеличивается на 8 с помощью команды add ESI .8, указывая на следующую пару элементов. Количество обрабатываемых пар элементов помещается в регистр ЕВХ:
mov EBX. Len

shr EBX. 2

dec EBX
Здесь хочу сделать важное замечание. В нашей процедуре обрабатывается 10 двойных слов, поэтому регистр ЕВХ должен содержать значение 9 для корректной работы цикла. Если количество элементов массива будет нечетным, то необходимо обрабатывать последнее двойное слово вне цикла. Это потребует дополнительных команд, но в целом не окажет существенного влияния на быстродействие процедуры, особенно при больших размерах обрабатываемых массивов. Например, чтобы обработать 1589 двойных слов, объединив каждые два элемента, необходимо выполнить 397 итераций для учетверенных слов и после окончания цикла обработать одно двойное слово. При желании читатели могут самостоятельно разработать подобную процедуру, обрабатывающую произвольное количество двойных слов.

Для организации циклических вычислений очень часто используются команда loop и ее модификации. Соответствующие примеры мы рассматривали ранее в этой главе. Эта команда очень удобна, поскольку избавляет программиста от необходимости постоянно проверять условие окончания цикла. Модификации команды loop, такие, например, как loope и loopne, еще больше упрощают программирование циклов.

Несмотря на очевидные удобства в применении, команда 1оор имеет средние показатели производительности. Если на первое место выходит скорость выполнения программного кода, то команду loop лучше не использовать, особенно при обработке большого числа элементов строк или массивов. В таких случаях желательно заменить команду 1оор группой команд. Это замечание касается, в первую очередь, приложений, разрабатываемых для процессоров Intel Pentium, поскольку на более ранних процессорах команда loop работает быстрее своих программных аналогов.

Вот пример замены команды loop эквивалентными ей командами:
dest:

...

dec cx

jnz dest

...
Что же касается команд loope и loopne, то они работают значительно медленнее, чем эквивалентный им код, включающий обычные команды процессоров Intel Pentium. При очень интенсивных вычислениях команды loopCC (СС = е, пе, z, nz) в программах лучше не использовать. Стандартной эквивалентной замены для таких команд не существует, поскольку в каждом конкретном случае программный код может быть уникальным. Рассмотрим вариант замены команды loope в приведенном ранее примере 16-разрядного приложения (см. листинг 3).

Напомню, что программный код примера выводит на экран строку без начальных символов пробела. В листинге 15 показан исходный текст модифицированной программы.
Листинг 1 Модифицированный код листинга 3

.model small
.data

sl DB " String with leading blanks !$"

len EQU $=sl
msg DB "Blank.:string!:$"
.code

start:

mov AX. @data

mov DS. AX

lea SI. Sl

dec SI

mov CX. len

mov AL. ' '
next:

inc .SI

cmp byte ptr [SI]. Al.

jne $7

dec CX

jnz next

jmp fail

mov dx. si
show:

mov -AH, 9h

int 21h

mov AH. lh

int 21h

mov AX. 4C00h

int 21h
fail:

lea DX. msg

jmp show

end start
end
В этой программе команда lооре заменена следующим фрагментом кода (выделен жирным шрифтом):
...

jne $+7

dec CX

jnz next

...

Как работает эта группа команд? На каждой итерации выполняется поиск символа пробела с помощью команды
cmp byte ptr [SI]. AL
Предположим, что обнаружен символ, отличный от пробела. В этом случае команда cmp устанавливает флаг ZF в 0. Следующая команда jne $+7 анализирует флаг ZF и передает управление команде, находящейся по адресу со смещением +7 в сегменте программного кода. Это смещение определяется как разность адресов следующей выполняемой команды и текущей. Следующей командой является
mov DX. SI
Она загружает адрес оставшейся части строки в регистр DX для вывода на экран. Эта команда отстоит на 7 байт от выполняемой в данный момент команды. Таким образом, команда jne $+7 передает управление по адресу команды
mov DX. SI
Если обнаруженный символ является пробелом, то выполняется декремент содержимого регистра СХ, и если оно не равно 0, то цикл повторяется. Если строка состоит из одних пробелов, то после окончания цикла управление передается команде
jmp fail
Попробуем теперь подобрать аналог программного кода для команды lооре, которая используется в программе, отображающей часть строки после знака + (см. листинг 4). Исходный текст модифицированной программы представлен в листинге 16.

Исходный текст фрагмента кода, используемого вместо команды lооре, выделен жирным шрифтом. Он очень напоминает программный код из предыдущего примера, с той лишь разницей, что команда jne по смыслу программы заменена командой je, кроме того, изменилась величина смещения (8 вместо 7). Смещение зависит от объема памяти, занимаемого пропускаемыми командами, а в этом фрагменте вместо dec CX используется для разнообразия команда dec CL, занимающая объем памяти на 1 байт больше.
Листинг : 16.Замена команды Ioopne в программе из листинга 4
.model small

.data

s1 DB "String 1+String 2$"

len EQU $-sl

msg BB "Char + not found!$"

.code

start:

mov AX, @data

mov DS, AX

1ea SI, S1

dec SI

mov CI, len

mov AL '+'

next:

inc SI

cmp byte ptr [SI]. AL

je $+8

dec CL

jnz next

jmp fuil

mov DX, SI

inc DX
show:

mov All. 9h

int 21h

mov All. lh

int 21h

mov AX.-4C00h

int 21h
fail:

lea DX.insg

Jmp show

end start

end
Помимо рассмотренных простейших вариантов можно разработать и другие способы модификации программного кода с командами loopCC. Автор надеется, что материал этой главы окажет помощь в создании новых, более эффективных алгоритмов обработки данных и модификации уже существующих.
1   ...   4   5   6   7   8   9   10   11   ...   41

Похожие:

Конспект лекций по курсу Системное программирвание для специальности Информатика Лекция 1 iconКонспект лекций для студентов заочной формы обучения направления 080201 (Информатика)
Предлагаемый конспект лекций представляет собой пособие по предмету “Теория информации”, который читается в Сумском государственном...

Конспект лекций по курсу Системное программирвание для специальности Информатика Лекция 1 iconКонспект лекций 2007 Экология. Конспект лекций. Для студентов специальностей...
Экология. Конспект лекций. Для студентов специальностей 080201 «Информатика», 090220 «Оборудование химических производств и предприятий...

Конспект лекций по курсу Системное программирвание для специальности Информатика Лекция 1 iconКонспект лекций по дисциплине информационные и телекоммуникационные...

Конспект лекций по курсу Системное программирвание для специальности Информатика Лекция 1 iconКонспект лекций по дисциплине “
«Компьютерная инженерия», специальности 091501 «Компьютерные сети и системы», 091502 «Системное программирование»

Конспект лекций по курсу Системное программирвание для специальности Информатика Лекция 1 iconКонспект лекций по курсу Выбранные вопросы информатики (часть 2)...
Точно так же как художник может выбирать для рисования различные инструменты, программист, создающий аплет Java, может выбирать различные...

Конспект лекций по курсу Системное программирвание для специальности Информатика Лекция 1 iconКонспект лекций по дисциплине “Статистика в машиностроении ” для студентов специальности
Конспект лекций предназначен для самостоятельного изучения студентами теоретической части курса “ Статистика в машиностроении ” (для...

Конспект лекций по курсу Системное программирвание для специальности Информатика Лекция 1 iconКонспект лекций по дисциплине “ основы защиты информации” для направления...
Министерство образования и науки украины восточноукраинский государственный университеТ

Конспект лекций по курсу Системное программирвание для специальности Информатика Лекция 1 iconКонспект лекций по курсу Начертательная геометрия
Конспект лекций по курсу начертательная геометрия (для студентов заочной формы обучения всех специальностей академии). Сост. Лусь...

Конспект лекций по курсу Системное программирвание для специальности Информатика Лекция 1 iconКонспект лекций и методические указания к выполнению контрольной работы к изучению курса
Конспект лекций и методические указания к выполнению контрольной работы по курсу “Проектирование специальных станочных и контрольных...

Конспект лекций по курсу Системное программирвание для специальности Информатика Лекция 1 iconКонспект лекций по курсу «Организация производства»
Конспект лекций по курсу «Организация производства» (для студентов и слушателей заочной формы обучения фпоизо специальностей 050100...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
uchebilka.ru
Главная страница


<