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

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

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

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

Иерархия операций 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) имеет минимальное положительное значение.