Показатели эффективности системы операций

Качество системы операций (СО) можно характеризовать двумя свойствами; функ циональной полнотой и эффективностью.

Функциональная полнота — это достаточность системы операций для описании любых алгоритмов. Системы операций ВМ включают в себя большое количество машинных операций и практически всегда являются функционально полными.

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

Затраты оборудования С можно описать выражением

где С_ПР — затраты в процессоре на реализацию системы операций, С_ЗУ —, затраты памяти на размещение данных и программ, представляющих алгоритм в терминах заданной системы операций.

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

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

Выбор системы операций

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

В качестве примера рассмотрим один из способов решения этой задачи — выбор системы операций на основе структурирования алгоритмов.

Метод структурирования алгоритмов предполагает следующую формулировку задачи выбора системы операций: необходимо выбрать такую систему которая обеспечивает реализацию алгоритма А за заданное время Т = Т_доп при минимальной стоимости ВМ.

Иерархия операций F₁,…,F_p функционально полных для алгоритма А, может быть определена процедурой структурирования, сводящейся к следующему. Алгоритм А рассматривается как один оператор, реализующий операцию f₁, над исходными данными с целью получения требуемых результатов, то есть F₁ = {f₁}. Затем оператор разделяется на части — программируется последовательностью более простых операторов. Последовательное применение процедуры структурирования (разделения оператора на более простые операторы) позволяет выявить системы операций F₁ = {f₁},F₂={f₂,f₃},F₃={f₃,f₄,f₅},F₄={f₄,f₅,f₆,f₇},…, и тем самым построить иерархию операций F₁,…,F_p.

Для каждой операции в F_i можно определить количество n_g ее выполнений при одной реализации алгоритма. Тогда сумма

будет представлять количество операций, выполняемых при одной реализации алгоритма, запрограммированного в терминах F_i. Характеристики элементной базы позволяют задать приближенное значение средней длительности - операции в ВМ. С учетом этого время выполнения алгоритма на основе F_i составит - что дает возможность поставить в соответствие иерархии систем операций F₁,…,F_p затраты времени на реализацию алгоритма T₁,...T_p, причем T₁ < ... < Т_p. Можно предположить, что минимум аппаратных затрат достигается при , обеспечивающей время реализации алгоритма Т_n максимально близкое к заданному значению T_ДОП. В силу сказанного, выбор системы операций сводится к нахождению такой системы F_n для которой разность (T_ДОП - Т_n) имеет минимальное положительное значение.