МЕТОДИКА РАСЧЕТА ТРУДОЕМКОСТИ ВЫПОЛНЕНИЯ АЛГОРИТМА

МЕТОДИЧЕСКИЕ УКАЗАНИЯ К КУРСОВОЙ РАБОТЕ ПО ДИСЦИПЛИНЕ

КОМПЬЮТЕРНЫЕ СИСТЕМЫ

ЦЕЛИ И ЗАДАЧИ ПРОЕКТИРОВАНИЯ

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

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

- структурное - разработка способов взаимодействия функциональных элементов друг с другом;

- логическое - распределение физических адресов в памяти системы и разработка прикладных программ, реализующих функции комплекса заданной конфигурации;

- техническое - конструктивная и электрическая компоновка комплекса, и разработка конструкторской и эксплуатационной документации.

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

Необходимо знать наиболее распространенные разновидности информационно-вычислительных систем:

а) цифровые управляющие и контролирующие системы;

б) системы с оперативной обработкой;

в) мультипроцессорные вычислительные системы.

г) вычислительные кластеры.

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

ТЕМАТИКА ПРОЕКТИРОВАНИЯ

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

СТРУКТУРА И СОДЕРЖАНИЕ ИНДИВИДУАЛЬНОГО ПРОЕКТА

В пояснительную записку входят следующие разделы:

Введение

1. Постановка задачи и анализ технического задания

2. Расчет характеристик вычислительной системы

3. Имитационное моделирование различных режимов работы вычислительной системы.

4. Оценка надежности системы и разработка мероприятий по ее повышению

Заключение

Список литературы

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

1. В разделе "Постановка задачи и анализ технического задания" необходимо кратко изложить назначение проектируемой системы, основные технические характеристики и условия ее эксплуатации, указать задачи и цели ее разработки, дать краткое описание объекта управления, определить эффект от ее внедрения. Также необходимо дать описание вычислительного процесса в системе, перечисление основных и дополнительных функций вычислительной системы рассматриваемого класса; описание процесса поступления заявок на обработку; характеристика потоков заявок; описание способов диспетчеризации заявок; краткая характеристика прикладных программ, реализуемых системой.

2. В разделе "Расчет характеристик вычислительной системы" необходимо произвести расчет характеристик алгоритмов, реализуемых системой, рассчитать необходимое быстродействие процессора системы, выбрать дисциплину обслуживания заявок, рассчитать время ожидания и пребывания задач в системе. Расчет указанных характеристик производится в зависимости от класса проектируемой системы. Ввиду значительной трудоемкости расчетных работ при отдельных этапах проектирования ВС необходимо использовать пакет программ для математических расчетов и анализа вычислительных систем.

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

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

1) набор ограничений на время пребывания (ожидания) заявок - существование некоторой дисциплины обслуживания, удовлетворяющей этим ограничениям;

2) выбор дисциплины обслуживания заявок, отвечающей заданным ограничениям;

3) определение оптимального быстродействия процессора для выбранной дисциплины обслуживания. Методика расчета характеристик приведена в [1].

В зависимости от требований к временным характеристикам задания разделяют на следующие разновидности:

1) с неограниченным временем пребывания заявок;

2) с относительными ограничениями на время пребывания;

3) с абсолютными ограничениями на время пребывания;

3. В разделе «Имитационное моделирование различных режимов работы вычислительной системы» необходимо с помощью методов имитационного моделирования с использованием среды GPSS WORLD создать модель компьютерной системы и провести ряд экспериментов, направленных на анализ и оптимизацию функционирования компьютерной системы при различных режимах работы.

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

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

В заключении привести результаты расчетов с анализом и выводами по курсовой работе.

МЕТОДИКА РАСЧЕТА ТРУДОЕМКОСТИ ВЫПОЛНЕНИЯ АЛГОРИТМА

Теоретические основы

Трудоемкость алгоритма – количество вычислительной работы, требуемой для реализации алгоритма.

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

Функциональный оператор задает преобразование на множестве данных, т.е. задает некоторую совокупность вычислительных операций. Оператор перехода задает порядок вычисления функциональных операторов и правило выбора одного из возможных путей развития вычислительного процесса, соответствующего текущим значениям данных. Оператор ввода-вывода задает обращение к определенному файлу с целью передачи некоторого количества информации. Функциональные операторы и операторы перехода называют основными операторами.

Совокупность операторов и связей между ними наиболее наглядно представляется графом алгоритма, где вершины соответствуют основным операторам алгоритма, а дуги отображают связи между операторами.

Вершины графа бывают трех типов: начальная, конечная и операторная. Начальная вершина определяет начало алгоритма. Эта вершина не имеет ни одного входа и имеет только один выход. Конечная вершина определяет конец алгоритма и имеет не менее одного входа и ни одного выхода. Операторная вершина соответствует основному оператору или оператору ввода-вывода. Если она представляет функциональный оператор или ввода-вывода, то может иметь не меньше одного входа и только один выход. Если она представляет оператор перехода, то может иметь не меньше одного входа и не меньше двух выходов.

Граф алгоритма является корректным, если выполняются условия:

- имеется только одна начальная и только одна конечная вершина;

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

- из каждой вершины кроме конечной существует по крайней мере один путь, ведущий из этой вершины в конечную;

- выход из любой вершины должен вести только к одной вершине графа;

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

Пример графа алгоритма приведен на рис. 5.1.

Рис. 5.1. Пример представления графа алгоритма

Вершины графа обозначены номерами ; (0 - начальная вершина, K - конечная; 1,...,K-1 идентифицируют операторы алгоритма). Граф выявляет структуру алгоритма, определяя множество операторов и дуг , и , связывающих операторы.

Для оценки трудоемкости алгоритма необходимо:

1. разбить множество операторов на классы:

o основных операторов , ,

o операторов ввода-вывода

2. для каждого основного оператора определить количество операций , составляющих оператор и для каждого оператора ввода-вывода - среднее количество информации , передаваемой при выполнении оператора;

3. переходы между операторами и следует рассматривать как случайные события и характеризовать их вероятностями , т.е. каждая дуга графа алгоритма отмечается вероятностью перехода , с которой переход из вершины к выполняется именно по этой дуге.

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

, ( ); (5.1)

Значения зависят от вероятностей выполнения условия, проверяемого оператором с целью выбора пути перехода.

Пусть - среднее число обращений к операторам за один прогон алгоритма. Тогда характеристика трудоемкости может быть вычислена следующим образом:

среднее число операций, выполняемых при одном прогоне алгоритма

(5.2)

где - множество операторных вершин рассматриваемого графа алгоритма; -количество операций, порождаемых оператором .

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

Состояния - невозвратные (процесс после какого-то числа шагов покидает их), состояние - поглощающее (в нем процесс прекращается). Начальное состояние определяется дугой ( ), выходящей из начальной вершины графа. Граф алгоритма, дуги которого отмечены вероятностями переходов _, рассматривают как граф марковской цепи (марковская цепь – марковский процесс с дискретными состояниями).

Решение задачи определения трудоемкости алгоритма сводится к вычислению среднего числа пребываний марковского процесса в невозвратных состояниях _.Одним из способов расчета указанных величин является нахождение корней системы линейных алгебраических уравнений

( ), (5.3)

где - символ Кронекера ( = 1 при и = 0 при ).

Каноническая запись системы уравнений (5.3) имеет вид

. (5.4)

Решив систему (5.4), определяем среднее число попаданий вычислительного процесса в состояния . При заданных значениях т.е. среднем количестве операций, порождаемых каждым функциональным оператором , по формуле (5.2) можно вычислить трудоемкость алгоритма, характеризующую его как среднее число операций, выполняемых при одном прогоне.

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

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

Для расчета алгоритма, не содержащего циклы, необходимо:

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

2. для каждой вершины можно вычислить среднее количество попаданий вычислительного процесса в эту вершину по формуле

( ) (5.5)

где - вероятность перехода из вершины в вершину .

При установленном порядке нумерации вершин на момент вычисления значения уже определены. Поэтому вычисление значения n_i сводится к суммированию произведений, причем поскольку для всех , то суммирование следует проводить только для .

Характеристика трудоемкости вычисляется по формуле (5.2).

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

где - вершины, содержащиеся в цикле C.

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

. (5.6)

Тогда средняя трудоемкость цикла

(5.7)

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

Минимально и максимально возможное значения трудоемкости на момент окончания выполнения оператора обозначим соответственно через и . Для начальной вершины имеем и . Тогда для остальных вершин с номерами

, (5.8)

, (5.9)

где ( ) - дуга, выходящая из вершины и входящая в вершину ; - множество дуг графа программы; минимальное и максимальное значения определяются по отношению ко всем вершинам , из которых выходят дуги, входящие в вершину ; значения и характеризуют минимальную и максимальную трудоемкость оператора .

Для конечной вершины графа вычисляются значения

, (5.10)

, (5.11)

характеризующие минимальную и максимальную трудоемкость алгоритма.

Дата добавления: 2019-09-08; просмотров: 480; Мы поможем в написании вашей работы!

Поделиться с друзьями:

12 3 4 Следующая ⇒

Мы поможем в написании ваших работ!