Лабораторная работа № 1
ОПРЕДЕЛЕНИЕ ОСНОВНЫХ ПАРАМЕТРОВ РЕАЛИЗАЦИИ АЛГОРИТМОВ
НА ЭВМ
1. Цель работы.
Исследование свойств алгоритмов, реализуемых на ЭВМ, и способов определения основных параметров машинных алгоритмов. В результате выполнения лабораторной работы студент получает знания по основным параметрам и характеристикам алгоритмов и навыки по их определению для различного класса задач, с использованием двух основных методов расчета, позволяющих получить как экстремальные, так и средние значения характеристики алгоритмов.2. Задание
2.1. Изучить способы оценки основных параметров алгоритмов при их реализации на ЦВМ и в вычислительных системах.
2.2. Определить трудоемкость алгоритмов и среднюю трудоемкость этапа счета на основе марковской модели вычислительного процесса по варианту, указанному преподавателем.
2.3. Определить среднюю, минимальную и максимальную трудоемкость алгоритмов на основе сетевой модели вычислительного процесса.
2.4. Провести сравнение эффективности и сложности определения трудоемкости при использовании сетевой модели и марковской модели.

3. Рабочее место.
Работы выполняются на ПЭВМ. При выполнении работы используется программный комплекс для исследования моделей систем обработки данных.

4. Теоретическая часть

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

, (1.1)
где m – число типов операций.
Основной трудоемкостью алгоритма называют количество стандартных (условных операций, которые необходимо выполнить при реализации алгоритма без учета операций, выполняемых с целью обнаружения и исправления ошибок и ликвидации последствий сбоев и отказов.
Трудоемкость алгоритма определяется количеством операций, которые необходимо выполнить при реализации алгоритма.
Стандартной операцией называется реальная или фиктивная операция, длительность выполнения которой может быть принята постоянной при любых исходных данных. Наиболее часто в качестве стандартной операции принимают короткую операцию, например, типа сложения.
Длительность выполнения любой операции i-го типа можно выразить через стандартную операцию:
(i = 1,2,…,m), (1.2)
где — коэффициент отношения длительности выполнения операции i-го типа к стандартной операции.
Выражение для основной трудоемкости алгоритма (алгоритмической сложности) можно представить в виде
, (1.3)
Где — количество операций i-го типа.
Трудоемкость циклических и разветвляющихся алгоритмов зависит от числа циклов пути, по которому идет вычислительный процесс. В свою очередь направление вычислений и число циклов определяются исходными данными и точностью реализации алгоритма. Если исходные данные заранее точно неизвестны, то основная трудоемкость является случайной величиной, задаваемой функцией распределения. Тогда оценивается средней трудоемкостью, пред-ставляющей собой математическое ожидание .
Связностью алгоритма S называют наибольшее за время его реализации количество промежуточных результатов, которое необходимо хранить одновременно. Так как связность вычислительных ветвей разветвляющихся и циклических алгоритмов различна, то связность S таких алгоритмов является величиной случайной и задается функцией распределения. В этом случае связность оценивается математическим ожиданием M[S], называемым средней связностью. Связность алгоритма влияет на емкость оперативной памяти машины и системы.
Погрешностью алгоритма называется составляющая погрешности результата, которая определяется неточным соответствием реального алгоритма преобразования информации и идеального алгоритма, преобразующего информацию безошибочно.
Цикличностью алгоритма называют величину

, (1.4)
Где ,,,, — средняя трудоемкость алгоритма; ,,,, — средняя трудоемкость по всем разветвлениям алгоритма, определенная в предположении что все циклы реализуются один раз.
Параллельность алгоритма может быть оценена количеством его параллельных ветвей, реализуемых независимо друг от друга.

4.2. Определение трудоемкости алгоритмов
и средней трудоемкости этапа счета

На первом этапе проектирования вычислительных систем осуществляется анализ прикладных задач, для решения которых, собственно, и разрабатывается система. Определив круг решаемых задач оценивают трудоемкость алгоритмов и среднюю трудоемкость одного этапа (шага) счета. Эти параметры на ряду со значением максимально допустимого времени реализации алгоритмов являются основополагающими для определения требуемого быстродействия вычислительной системы. Оценивается трудоемкость алгоритма количеством операций, выполняемых с целью обработки, вывода и ввода информации в процессе решения задачи.
Информация, относящаяся к задаче, разделяется на программу и данные; последние включают в себя исходные данные, промежуточные величины и конечные результаты. Данные могут быть расположены как в оперативной, так и во внешней памяти. Оперативная и внешняя память между собой имеют различия в методах доступа, скоростных характеристиках. Затраты времени на обращение в оперативной памяти пропорциональны количеству читаемой или записываемой информации. Затраты времени на обращение к внешней памяти в основном определяются временем поиска области данных и в меньшей степени зависят от количества передаваемой информации. Поэтому для уменьшения затрат времени на обмен информацией с внешней памятью за каждое обращение целесообразно передавать достаточно большое количество информации.
Информация, которая хранится во внешней памяти, разделяется на файлы – упорядоченные совокупности данных, обрабатываемых одним общим для этих файлов способом. Операции обращения к внешней памяти рассматриваются обычно как операции ввода-вывода.
Сложность вычислений оценивается трудоемкостью, которая, в свою очередь, определяется количеством операций, выполняемых с целью обработки, ввода и вывода информации в процессе решения задачи. Трудоемкость алгоритма – величина вероятностная, так как длительность и число выполняемых операторов при различных исходных данных может быть различной величиной. Поэтому полная характеристика трудоемкости предполагает описание количества операций, выполняемых за одну реализацию алгоритма случайными величинами.
Применение статистических методов определения количества операций – сложный процесс, поэтому трудоемкость алгоритмов обычно описывается методами математической статистики, например, с помощью математического ожидания числа выполняемых операций.
В первом приближении трудоемкость алгоритма можно охарактеризовать следующей совокупностью параметров:
— среднее количество процессорных операций, выполняемых за одну реализацию алгоритма;
— среднее время обращения к файлам ;
— среднее количество байтов, передаваемых за одно обращение к файлам соответственно.
Значение характеризует трудоемкость счета, а значение ; — трудоемкость процесса ввода-вывода информации, где Н – количество файлов.
При решении задач анализа и синтеза ВС возникает необходимость в описании и исследовании свойств вычислительных процессов. Эти исследования можно осуществлять не только на реальных вычислительных процессах, но и на моделях. В этом случае целесообразно представлять вычислительный процесс моделями, несущими в себе информацию только о свойствах самого процесса, учет которых необходим и возможен при решении задач анализа и синтеза ВС. С учетом сведений о трудоемкости алгоритма можно сформулировать следующие требования к моделям. Модель должна определять:
1) порядок прохождения алгоритмов запросов, хранимых в каждом из файлов;
2) трудоемкость обслуживания запросов – количество операций, которые должен выполнить процессор при обслуживании запроса на счет, и количество вводимой – выводимой информации;
3) отображать вычислительные процессы как реализацию случайного процесса;
4) вычислительные процессы, порождаемые моделью, должны соответствовать реальным процессам с точностью до совпадения по крайней мере математических ожиданий их одноименных характеристик.
Первые два требования выделяют круг сведений о вычислительных процессах, наиболее существенно влияющих на порядок функционирования ВС. Необходимость третьего требования продиктовано результативностью вероятностного подхода к исследованию вычислительных процессов. Фактор случайности, вводимый в модель, позволяет порождать бесконечное число реализаций вычислительного процесса, что характерно для процессов выполнения алгоритмов. Последнее требование определяет минимальную норму «точности» модели. С учетом этих требований построим модель вычислительного процесса. На начальном этапе необходимо оценить трудоемкость алгоритмов. Применительно к задачам анализа трудоемкости операторы будем подразделять на функциональные, перехода и операторы обращения к файлам.
Функциональные операторы задают совокупность вычислительных операций. Операторы перехода задают правила выбора одно из возможных путей развития вычислительного процесса. Операторы обращения к файлам отражают процесс обмена информацией с внешними устройствами.
Как правило, в системе существует несколько внешних устройств и соответственно формируется несколько файлов. Функциональные операторы и операторы перехода называют основными операторами. Для оценки трудоемкости алгоритма необходимо разбить множество операторов на классы:

Где h = 1,…,H – номер файла, к которому осуществляет обращение i- оператор; Н – общее число файлов; и — общее число основных операторов и операторов ввода-вывода соответственно.
Для каждого основного оператора необходимо определить среднее количество операций составляющих оператор, и для каждого оператора ввода-вывода — среднее количество информации передаваемой при выполнении оператора.
Совокупность операторов и связей между ними наиболее наглядно представляется графом алгоритма, как это показано на рис. 1.1. При разработке и анализе алгоритмов необходимо провести проверку корректности графа алгоритма.

Рис 1.1. Граф алгоритма, используемый при оценке трудоемкости

Граф алгоритма является корректным, если выполняются следующие условия:
1) имеется только одна начальная и только одна конечная вершина;
2) для каждой вершины, кроме начальной, существует по крайней мере один путь, ведущий из этой вершины в конечную;
3) из каждой вершины, кроме конечной, существует по крайней мере один путь, ведущий из этой вершины в конечную;
4) выход из любой вершины должен вести только к одной вершине графа;
5) при любых значениях логических условий существует путь из начальной вершины в конечную, причем любому фиксированному набору значений условий соответствует только один такой путь.

В графе алгоритма любая дуга (i,j) отмечена вероятностью перехода из вершины к вершине . Так как вычислительный процесс не может приостанавливаться в произвольной, не считая конечной (K), вершине, то с вероятностью 1 произойдет переход к какой-либо вершине графа алгоритма. С учетом этого для любой вершины должно выполнятся условие

Вероятности зависят от вероятностей выполнения условия, проверяемого оператором , с целью выбора пути перехода и определяются исходя из диапазона, в котором распределена проверяемая величина X, и закона распределения значений в этом диапазоне. Для операторов цикла вероятность перехода определяется количеством циклов. Если за оператором i непосредственно выполняется оператор j, то = 1.
Пусть — среднее число обращений к операторам за один прогон алгоритма. В таком случае характеристики трудоемкости могут быть вычислены следующим образом:
Среднее число процессорных операций, выполняемых при одном прогоне алгоритма:

Среднее число обращений к файлу :

Среднее количество информации, передаваемое при одном обращении к файлу :

где — число операций, составляющих i-оператор, — среднее количество информации, передаваемое при выполнении оператора i.
В выражении (1.8) суммирование производится для всех вершин, относящихся к основным операторам, в выражениях (1.9) и (1.10) – для всех вершин, отражающих обращение к данному файлу.
В большинстве случаев вероятности переходов постоянны для заданного алгоритма и переход к следующему оператору определяется только распределением вероятности т.е. процесс вычисления является марковским процессом с K состояниями соответствующим пребыванию процесса в вершинах графа алгоритма. Состояния невозвратные (процесс после какого-то числа шагов немедленно покидает их), состояние поглощающее (достигнув его, процесс прекращается). Для упрощения обозначений условимся, что начальное состояние . Порядок изменений состояний определяется графом алгоритма, дуги которого отмечены вероятностями переходов . Отмеченный граф алгоритма можно рассматривать как граф марковской цепи. Среднее число пребываний марковского процесса в невозвратных состояниях определяется корнями линейных алгебраических уравнений

где — символ Кронекера ( =1 при i=j и = 0 при ).
Значения определяют решением системы линейных алгебраических уравнений (1.11) каноническая запись которых имеет вид

При формировании коэффициентов системы (1.12) необходимо обратить внимание на то, что коэффициенты записываются не по строкам, а по столбцам, то есть, например, на месте второго элемента первой строки стоит элемент с индексом 2,1, а не коэффициент с индексом 1,2 матрицы переходов.
Если при выполнении каких-то операторов происходит обращение к файлам, необходимо определить величины и . Определив таким образом величины , , можно определить среднюю трудоемкость этапа счета, на основании которой осуществляется оценка оптимального быстродействия процессора.
Средняя трудоемкость этапа счета определяется по формуле

где N – сумма среднего числа обращений к основным операторам , т.е.

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

4.3. Сетевой подход к оценке параметров алгоритмов

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

4.3.1. Оценка средней трудоемкости алгоритмов

Алгоритм представляется в виде графа, состоящего из k операторных вершин и имеющего единственную конечную вершину с номерами K = k + 1; дуги графов отмечены вероятностями переходов . Каждой вершине графа поставлено в соответствие среднее значение трудоемкости или . С учетом формул (1.8)-(1.10) задача оценки трудоемкости алгоритма сводится к определению среднего числа обращений к операторам за один проход алгоритма.
Рассмотрим методику вычисления значений для алгоритма, не содержащего циклы. Для применения сетевого подхода к оценке трудоемкости этого алгоритма вершины графа должны быть пронумерованы в порядке их следования, т.е. так, чтобы любая вершина имела номер, больший любого номера предшествующих ей вершин. Нумерация проводится следующим образом. Начальной вершине присваивается номер 0. Очередной номер i = 1,2… присваивается вершине, в которую входят дуги от уже пронумерованных вершин с номерами, меньшими i. При этом любым двум вершинам должны соответствовать разные номера. Такой порядок нумерации является результативным для любого графа без циклов. Причем конечная вершина графа будет иметь максимальный номер K.
По аналогии с (1.11) среднее число попаданий вычислительного процесса в вершину определяется выражением

(i=2,….,k) (1.15)

где — вероятность перехода из вершины j в вершину i.
При установленном порядке нумерации вершин на момент вычисления значения уже определены. Поэтому вычисление значения сводится к суммированию произ-ведений, причем, поскольку для всех , то суммирование следует проводить только для j<i.
Совокупность операторов, входящих в цикл, и связывающих их дуг, за исключением дуги, замыкающей цикл, называют телом цикла. Тело цикла ранга 1 является графом без циклов. Применяя к этому графу вышеописанную методику, можно определить значения для каждого из операторов, принадлежащих телу цикла, и, следовательно, трудоемкость тела цикла C равна

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

и цикл C можно заменить оператором с трудоемкостью . Методика расчета для циклов с несколькими выходами приведена в примере расчета, содержащимся в программе «Определение основных параметров реализации алгоритмов на ЭВМ».
Применяя указанную процедуру замены циклов операторами ко всем циклам ранга 1, затем ранга 2 и т.д., в конце концов придем к графу без циклов, трудоемкость которого находится вышеописанным способом.

4.3.2. Оценка минимальной и максимальной трудоемкости алгоритма

Рассмотрим методику вычисления минимальной и максимальной трудоемкости алгоритмов. Вначале будем рассматривать алгоритмы без циклов, вершины графов которых нумеруются в порядке их следования, как это было описано ранее.
Минимально возможное и максимально возможное значение трудоемкости на момент окончания выполнения оператора обозначим соответственно через и . Имеем и . Тогда для остальных вершин с номерами i=1,2,…,k

Где (j,i) – дуга, выходящая из вершины j и входящая в вершину i;
D – множество дуг графа программы; минимальное и максимальное значения определяются по отношению ко всем вершинам j, из которых выходят дуги, входящие в вершину; i; значения и характеризуют минимальную и максимальную трудоемкость оператора .
Для конечной вершины K графа вычисляются значения

характеризующие минимальную и максимальную трудоемкость алгоритма.
Минимальная и максимальная трудоемкость алгоритмов, содержащих циклы, находится по аналогии с метолом определения средней трудоемкости алгоритмов t циклами. При этом выделяются циклы ранга 1. Находятся минимальная A и максимальная B трудоемкость тела цикла. Минимальная и максимальная трудоемкость цикла определяется значениями и где и — минимальное и максимальное число повторений цикла. Затем цикл заменяется оператором с трудоемкостью и и вновь применяется процедура исключения циклов. Процесс повторяется до тех пор, пока граф алгоритма не будет преобразован к форме без циклов.

5. Порядок выполнения работы

5.1. Требуется определить основные параметры трудоемкости алгоритмов на основе марковской модели вычислительного процесса:
а) среднее число пребываний марковского процесса в невозвратных состояниях ;
б) среднее число процессорных операций, выполняемых при одном прогоне алгоритма ;
в) среднее число обращений к каждому из файлов ;
г) среднее количество информации, передаваемой при одном обращении к файлам .
Результаты расчетов свести в таблицу.
5.2. Определить среднюю трудоемкость этапа счета .
Исходные данные:
а) граф-схема алгоритма (ГСА) (рис. 1.2 – 1.5);
б) — число операций, составляющих оператор (табл. 1.1);
в) — среднее количество информации, передаваемой при выполнении оператора обращения к файлу, где m — номер файла, к которому осуществляется обращение (табл. 1.2);
г) — области изменения параметров и (табл. 1.3).
Правило выбора исходных данных
Номер варианта, по которому определяются исходные данные задается преподавателем. Например: 06-2, первая цифра («0») определяет значение и по табл. 1.1 и 1.2. Вторая цифра («6») определяет значение и по табл. 1.3, последняя цифра («2») указывает номер ГСА, в данном случае это рис. 1.3 (ГСА №2).
На этапе подготовки к лабораторной работе необходимо:
а) осуществить укрупнение заданной схемы алгоритма;
б) определить вероятности переходов из одного оператора в другой;
в) составить таблицу вероятностей переходов.
С целью уменьшения размерности системы линейных уравнений, составляемой для определения вероятностей выполнения операторов системы, осуществляется объединение последовательных операторов. Пример укрупненной ГСА, таблицы переходов, также пример расчетов, производимых при выполнении данной лабораторной работы, представлен в программе определения основных параметров реализации алгоритмов.
5.3. Определить среднюю, минимальную и максимальную трудоемкости алгоритмов на основе сетевой модели вычислительного процесса. Исходные данные берутся те же, что и для расчетов марковской модели. Результаты вычислений используются в качестве исходных данных для лабораторной работы №2.
5.4. Сделать вывод, в котором провести сравнение эффективности и сложности определения трудоемкости при использовании сетевой и марковской моделей. Сопоставить полученные результаты, определить процент расхождения значений средней трудоемкости, определенных с помощью двух методов. Объяснить полученное значение.

6. Содержание отчета

6.1. Исходная граф-схема алгоритма с указанием характеристик заданного алгоритма.
6.2. Укрупненная ГСА для данных своего варианта.
6.3. Таблица вероятностей переходов и полученная на его основе система уравнений.
6.4. Таблица с оценками параметров алгоритма.
6.5. Граф алгоритма с выделенными на нем циклами.
6.6. Расчеты средней, максимальной и минимальной трудоемкости алгоритма на основе сетевой модели.
6.7. Выводы и сравнения результатов расчетов.

7. Контрольные вопросы

7.1. Как взаимосвязаны между собой трудоемкость алгоритма и быстродействие процессора?
7.2. Почему модель вычислительного процесса носит вероятностный характер? Как оценивают трудоемкость алгоритма для систем реального времени?
7.3. Какое состояние марковского процесса называют невозвратным? Как это понятие связано с корректностью алгоритма?
7.4. На какие два процесса можно разделить алгоритм и как они зависят друг от друга?
7.5. Опишите процесс построения модели вычислительного процесса.
7.6. Какие параметры считаются наиболее важными при определении быстродействия вычислительной системы?
7.7. Что такое стандартная операция и как через ее длительность выражается длительность любой операции? Приведите пример стандартной операции.
7.8. Приведите примеры погрешностей различного вида. Какие из них оцениваются при разработке ВС?
7.9. Что такое связность, цикличность и параллельность алгоритма? Как они влияют на характеристики ВС?
7.10. Как влияет количество обращений к файлам и количество информации, передаваемой при одном обращении к файлу на характеристики вычислительного процесса?
7.11. В чем заключается суть сетевого подхода к оценке параметров алгоритмов?