Файл: Основы теории алгоритмов учеб. пособие.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 24.10.2024

Просмотров: 91

Скачиваний: 1

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

- 35 -

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

I мости от ввда обрабатываемой информации. Такие критерии могуч : быть полезными при сравнении различных вариантов структур вн^

числительных устройств,

близких по назначению. По аналогии

!

с предыдущим обозначением совокупность параметров УВС в виде

 

множества Y *

Y<f .

YkI

Такими параметрами могут быть

I

быстродействие,

разрядность,

объем намятой' различных типов,

j

: система команд и др. Некоторые параметры могут оказаться мно-j-

покомпонентными, т .е . в

общем случав можно записать

Г

 

 

Y j - ( *

*

* ’ yi - Pi ) »

 

где

JMj

-

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

Yjj

5

 

J<

-

число параметров

структуры машины М .

Если

у

 

характеризует память машины, то

определяет

объем памяти

 

-го

типа в

общей структуре ма-

ишны. В зависимости от конкретных уолозвий может быть выбрано, подмножество Y ( Y £ У ) существенных нараметров в том смысле, что оно является достаточным для выделения данной структуры среди всех возможных структур, реализующих некото­ рый алгоритм. Тогда критерий второго типа может быть представ­ лен в виде некоторой функции

F ( m ) - f [ m ( y ')1,

I

оценивающей качество структуры по ее экстремальному значению при известных ограничениях на некоторые параметры из множест­

ва

Y

 

 

В общем олучае обобщенный критерий соответствия струк­

тур алгоритмов

структурам УВС может быть представлен в виде

 

F ( A , M )* - некоторой зависимости между параметрами

алгоритма

и структуры У . Если Д о - множеотво воз-

х )- такая зависимость была предложена к .т .н . ПОПОВЬЙ В«А»

/

- 36 -

можных модификаций алгоритма решаемой задачи & , а М© - множество возможных вариантов структур, способных реализовать множество алгоритмов Ао , то,как и в предыдущих случаях, выбор оптимального соответствия алгоритма и машины будет оп­

ределяться экстремальными значениями критерия

F ( А ,

И )

,

В

конкретных условиях множества

А« и

Me

ограничиваются

определенными требованиями по некоторым параметрам из

X

и

 

У ' . Поэтому оптимальное соответствие будет разыскиваться

в

подмножествах Ао ( д ; с А .)

и M i

( M i с м . )

 

 

Если эти подмножества каким-либо образом найдены, то решение задачи оптимального соответствия алгоритма и структуры сво­

дится к нахождению такой пары Aopt и И oft

, которые свои­

ми параметрами образуют критерий F (А, М), в

максимум или ми­

нимум, В простейшем случае задача может быть решена с исполь­ зованием буквального перебора, что возможно лишь при малом

количестве пар вида(Ао£., Hoj), где 1= 1 , 2 , . , . Н

; j =

1 , 2 , . , . ,

HI

; Н и ГП - соответственно мощности множеств

Ао

и

Мо .

 

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

рия эффективности F ( А ,М).

Рассмотрим возможности такого критерия при исследова­ нии основного цикла в адресных структурах УВМ, Такое изучение оказывается удобным проводить при помощи сравнения качествен­ ного состава операций, составляющих данный алгоритм, и вычис­ лительных возможностей машины. Анализируя особенности проте­ кания вычислительного процесса в УВМ различных структур, об­ ладающих вполне определенными основными циклами при выполнении операции, приходим к выводу, что при реализации одного и того же алгоритма такие машины затрачивают различную информацион­ ную работу. Это вызвано особенностями логической структуры

. и видом алгоритма, подлежащих реализации в машине. Логичео-

- 37 -

кую структуру можно охарактеризовать типом ооновного цикла, на который оказывают следующие факторы:

1. Число адресов в командах машины.

2 . Наличие или отсутствие совмещения выбора команды из памяти и выполнения арифметичеокой или какой-либо другой операции.

3. Наличие, различных памятей для команд и чисел и воз­ можность одновременного к ним обращения.

4. Наличие в арифметическом устройстве буферных регист­ ров записи результатов в памяти,

5. Особенность системы команд.

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

записать в виде

ор

,

(1.28)

где cL , $ , $ - содержание ячеек памяти или регистров арифметического устройства.

Если в операции JL—►2Г символы еС и if означают содержание ячеек памяти, то такая операция выполняется в ма- ' шине пооредотвом передачи информации ^ерез региотр арифмети­ ческого устройства и имеет вид

Пусть алгоритм, подлекащий реализации УВЫ, оодержит |

- 38 -

типов операций, от соотношения которых зависит количество обра­ щений к памяти и, оладовательно, окорооть работы машины. Тоща число обращений к памяти в адресной структуре выразится в ви­ де линейной функции

 

F - S i * l + 4 . * * + " "

+ 4 » * " ' >

(1.29)

где

t |i - число

обращений к памяти в конкретной структуре,

приходящихся на одну

{, -ю операцию вида

(1 .2 8 );

 

50с -чи сло

операций

t -го типа (

1 = 1 , 2 , . . . , Ю ).

Нетрудно заметить,

что

записанная функция связывает показате­

ли алгоритма и структуры машины, причем

 

F ( А , м" ) =

х Y ,

 

где X Y

-

окалярное произведение двух

ГП -мерных век­

торов .

 

 

 

 

 

При этом

t - k - 1 ,

"H I .

Оптимальное соответст­

вие алгоритма и структуры будет в

случае

F * Fmin

Найдем предельное значение критерия

F ( A , M ) при

фиксированной структуре УВМ и произвольном алгоритме в с то л е качественного и количественного состава оглраций в нем. Запи­ шем это обстоятельство в виде следующих ограничений:

 

M l +

X J + • • •

+

XJm * N

,

 

 

 

 

> 0,

( х . з о )

 

(y jeC O flii,

 

ljjt«rCo n s b ,

где

целые положительные числа.

 

Заметим,

что

*jji = О

в

том олучае,

если некоторая операция

не требует обращений к обычной памяти; в этой операции используютоя "быстрые ячейки", т .е . буферные регистры арифметичес­ кого устройства. Таким образом, задача нахождения предельных значений потерь времени на обращение к памяти сводится к за­ даче линейного программирования, в которой линейной формой > являетоя критерий (1 .29), а систему ограничений представляют выражения (1 .30). Для решения этой задачи можно применить,

- 39 -

например, оимплеко-метод и найти предельные значения критерия F(A,M) . После соответствующих выкладок получаем

( т

У д N * F ( А , И У ( т а к f r ) N

( I .3 I)

 

Бели задан некоторый клаоо адреоных структур в виде

множества

{ M l

с мощностью

Н

,

то

можно определить

предельные значения критерия

F (А, И)

и в этом олучае,

Пуоть 4 i h

-значение

t -ой компоненты вектора

У

в

К -ой структуре (

h

=

1 . 2 , . . . ,

Н

)•

При этом имеем

оледущее соотношение

 

 

 

 

 

 

 

 

 

 

 

 

 

m e n у th ^ 4 i.b ^ m a x

 

 

 

 

где макоимум (минимум) берется по всем

L

и

h

. Тогда вы­

ражение

(1 .31) перепишем в воде

 

 

 

 

 

 

 

( m i n U i O N * F ( A . M ) < ( m a * y y , ) N .

 

 

 

4

 

 

 

 

 

 

 

 

 

 

 

(1.32)

 

Для более удобного использования критерия

F C A . M )

можно использовать нормированные значения компонент вектора

j t

, для чего в

выражении

X

 

>Ci+ * ** + ЪСт ■» М

 

разделим

обе чаоти

равенотва

на

N

и получим

 

 

 

 

 

f x i - i ,

 

 

0 * * i * i .

 

 

 

 

где

 

в п

 

 

содержание операций

С-го типа в

 

- относительное

заданном алгоритме. Величину

# 1

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

час­

тоту появления операции

i

-го типа или в

предельном случае

как вероятность

появления

t

-ой операции.

 

 

 

 

 

Для УВМ интерес представляет использование критерия

F ( A , M ) для целого класса алгоритмов

 

 

 

 

 

реализуеьшх на машине. Обозначим вероятность появления

j -ой

задачи

через

^

. При этом очевидно,

что

 

 

 

 

 

i

%

-

 

i

0,

‘ v

1 - .

 

 

 

 

 

i*1

 

 

 

 

 

 

 

 

 

 

 

 

Смотрите также файлы