Расчет характеристик алгоритмов, реализуемых системой

⇐ ПредыдущаяСтр 2 из 3Следующая ⇒

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

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

Задан алгоритм работы системы в виде графа, в таблице снизу указаны трудоемкости для каждой из операций:

Определение трудоемкости алгоритма согласно заданному графу и значениям трудоемкости посредством универсального и сетевого методов:

-универсальный метод:

- сетевой метод (индексы коэффициентов начинаются с 0 в массиве, например, элемент K0 массива соответствует трудоемкости K1):

Была найдена средняя трудоемкость алгоритма согласно двум методам: 10270. При помощи сетевого метода удалось также найти минимальную трудоемкость, которая соответствует операторам: 1,2,8,9,10. Максимальная трудоемкость зависит от количества прохода циклов алгоритма, количество которых может быть и неисчислимо великим. Но в данном случае, для отображения случая произвольно выбранных проходов цикла, внешний и внутренний цикл отработали по 5 раз по наиболее трудоемкому пути. В итоге получено значение 43060.

Расчёт характеристик и требований для работы системы

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

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

Исходные данные интенсивности и трудоемкости операций:

На основании исходных данных определяются следующие характеристики трудоёмкости:

1) Интенсивность поступления

2) Трудоемкость процессорных операций

3) Среднее число обращений к файлу Fk.

4) Общее число обращений к файлам

5) Средняя длина блока записей файлов

6) Среднее количество прерываний центрального процессора

7) Средняя трудоёмкость

8) Минимальный объем памяти

9) Объем памяти для каждой задачи:

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

Расчёт времени ожидания и пребывания задач в системе

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

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

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

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

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

Задача синтеза КС может быть разбита на 3 этапа:

1. Найти минимальное значение быстродействия, при котором существует стационарный режим обработки заданий.

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

3. Определить времена ожидания заявок в очереди для потоков с входными данными по вариантам.

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

. (2.2)

Среднее время обслуживания заявки определяется значением:

, (2.3)

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

При наличии относительных ограничений на время пребывания заявок минимально необходимое быстродействие определяется из условия: (для СРВ)

Для системы с неограниченным временем пребывания заявок оптимальное значение быстродействия процессора равно:

, (2.8)

где - некоторый коэффициент пропорциональности, равный

;

Для систем с относительными ограничениями на время пребывания заявок, кроме ограничений на время ожидания заявок, задается ограничение на коэффициент простоя процессора и задача определения оптимального быстродействия формулируется следующим образом: найти такое значение быстродействия , которое обеспечивает минимум критерия эффективности (2.7) при ограничениях:

; ; ( ); .

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

где

; ;

При смешанной дисциплине обслуживания время ожидания заявок можно определить:

, (2.9)

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

Расчет данных характеристик на основании исходных данных в среде PTC MathCAD:

Среднее быстродействие устройства должно составить 35 млрд операций за единицу времени, что позволит завершить задачи в срок – всего за 2 секунды.

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

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

Для реализации генерации задач 5 типов формируется 5 блоков кода, начинающихся с оператора GENERATE. Также присутствует отдельный блок, отвечающий за имитацию работы всей системы в целом. В данном случае этот блок задает время моделирования системы равным одним суткам – 86400 секунд. Статистические данные будут записываться в таблицы TAB1, TAB2, TAB3, TAB4, TAB5 соответственно для каждого класса задач.

Значения для формирования заявок берутся из предыдущих выполненных задач работы. Например, время на выполнение заявки указывается в блоке ADVANCE при захвате процессора.

Пример кода для генерации заявок с относительным приоритетом:

GENERATE 3.3, 0.3

QUEUE Q_CPU

PREEMPT CPU4

DEPART Q_CPU

ADVANCE 0.02,0.002

RETURN CPU4

ENTER SSD

ADVANCE 0.5,0.1

LEAVE SSD

TABULATE tab2

TERMINATE

При помощи оператора GENERATE здесь генерируются заявки с интервалом 3.3 и разбросом интервала 0.3. Далее сгенерированная заявка поступает в очередь Q_CPU, увеличивая счетчик очереди. Оператор PREEMT CPU0 соответствует захвату процессора CPU0 при окончании выполнения текущей заявки и при отсутствии заявок с абсолютным приоритетом в очереди. Далее происходит освобождение очереди Q_CPU с декрементом её счетчика, и посредством ADVANCE выставляется время на обработку заявки процессором, RETURN -освобождение процессора.

После освобождения процессора происходит обращение к контроллеру накопителя – ENTER SSD. Время необходимое для работы с контроллером памяти записывается также в блок ADVANCE. LEAVE освобождает контроллер. Далее следует завершение обработки заявки контроллером. Оператор TERMINATE уничтожает заявки, TABULATE прежде записывает статистические данные о них.

Для определения оптимального количества процессоров смоделируем ряд случаев, когда проектируемая система имеет разное количество процессоров.

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

Из графика следует, что оптимальным будет использование трех CPU, так как увеличение их количества не приводит к существенному росту общей производительности системы и эффективному распределению нагрузки соответственно. Причем следует отметить, что среди выполняемых задач присутствует одна особенно трудоемкая. Для неё выделяется целый процессор. Дисциплина обслуживания такова: задачи 1 выполняются на CPU0, трудоемкая задача 2 – на CPU1, задачи 3, 4 и 5 –на CPU2

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

При использовании различных объемов носителя данных получаем результат:

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

STORAGE CAP. REM. MIN. MAX. ENTRIES AVL. AVE.C. UTIL. RETRY DELAY

SSD 3 1 0 3 176826 1 2.168 0.723 0 0

При увеличении объема до 4 нагрузка более приемлема:

STORAGE CAP. REM. MIN. MAX. ENTRIES AVL. AVE.C. UTIL. RETRY DELAY

SSD 4 1 0 4 176796 1 2.167 0.542 0 0

Таким образом, в полученной системе используется 3 процессора, дисциплина обслуживания определена. Используется общий носитель информации объемом 4. Это позволило добиться требуемого результата, обработать все поступившие заявки и уложиться в поставленное ограничение на время их обработки.

Оценка надежности системы

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

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

Выражение для вычисления безотказной работы:

Где t – интервал времени;

l_i – интенсивность отказов i-го блока;

m – число блоков ВС;

Для повышения надежности ВС можно использовать резервирование ее элементов. Однако этот прием приводит к существенному увеличению стоимости системы.

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

Рисунок 7.1 – Граф надежности устройства

Где S_i – состояния системы;

S₁ – система работоспособна;

S₂ – в системе обнаружен отказ;

S₃ – состояние необнаруженного отказа;

S₄ – состояние выполнения профилактических испытаний;

S₅ – в системе установлен скрытый отказ в результате профилактических испытаний.

l₀ – интенсивность потока отказов;

l_пф – интенсивность профилактических испытаний;

m_пф- интенсивность профилактики;

H – интенсивность восстановления;

g – доля контролируемого оборудования;

Составим систему уравнение Колмогорова:

- P₁×(g×l₀+ (1-g)× l₀+ l_пф) + P₂×_×H + m_пф×P₄= 0

- P₂×H + g×l₀×P₁+ g×l₀×P₃= 0

- P₃×(g×l₀+ l_пф) + (1-g)× l₀P₃ = 0

- P₄×m_пф + P₁×l_пф + P₅×H = 0

- P₅×H + l_пф×P₃ = 0

Найдем вероятности:

P₁ определяет стационарную вероятность нахождения ВС в состоянии S₁.

Данные варианта 5 следующие:

№	l₀	l_пф	m_пф	H	g
5	0,27	0,74	0,34	1,4	0,89

Проведем расчет согласно исходным данным и формулам:

Вероятность нахождение системы в состоянии работоспособности составила всего 0.247.

При этом, общая отказоустойчивость системы, которая определяется с учетом количества каналов(в данном случае - процессоров) системы в виде степени 3:

где P_k – надежность 1 канала, n – количество каналов в системе.

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

Полученные вероятности переходов из состояний в состояния относительно времени:

График вероятностей переходов:

Вероятность перехода в состояние работоспособности составило 0.2885.

При данных значениях общая отказоустойчивость:

Итоговое значение машинного расчета не совпало со значением, найденным аналитическим расчетом. Вероятность оказалась равной 0.543, что недостаточно для СРВ.

Определим методы повышения надежности системы. Для того чтобы повысить P1, необходимо увеличить m_пф, чтобы с большей скоростью переходить в состояние S1.

Также можно увеличить интенсивность восстановления H, чтобы поднять скорость перехода из S5 (скрытый отказ) в S4, и из S2 (отказ в системе) в S1. Кроме этого, необходимо уменьшить вероятность перехода из S1 в состояние S3 (необнаруженный отказ). Это делается путем увеличения g.

При уменьшении профилактических действий до 0.1, увеличение интенсивности профилактики до 0.7 и увеличения интенсивности восстановления до 1.8 получаем следующие результаты:

Используем машинный расчет:

Полученные вероятности переходов из состояний в состояния относительно времени:

Графический результат вероятностей и показание надёжности:

Из графика видно, что измененный параметр надежности помог добиться повышения надёжности до 0.72. Т.е. вероятность безотказной работы составляет теперь 0.72, что для СРВ является допустимым, так как итоговая вероятность отказоустойчивости близка к 0.98:

Базовые методы повышения надежности помогли достичь нужной отказоустойчивости. Реализация резерва поможет добавить надежность системе, что весьма актуально в случае СРВ. Для более быстрого восстановления системы, что труднодостижимо в случае холодного резерва (человеческий фактор усугубляет положение) и отсутствия постоянной нагрузки на устройствах применим к системе ждущий резерв. Дополнительное резервирующее оборудование будет находиться в состоянии готовности обработать заявки вышедшего из строя устройства, но при этом не выполняет операции в рабочем состоянии всех составляющих системы, как это было бы в случае горячего резерва. Таким образом, система будет иметь тип резервирования N+1 и общее количество процессоров будет равным 4, появится дополнительный физический модуль памяти.

Заключение

В ходе работы были изучены методы проектирования компьютерных систем, разработан проект вычислительного комплекса СРВ, который должен обеспечивать вычисления в рамках установленного времени с достаточно высокой степенью надёжности. Были проведены расчеты, позволившие найти необходимые параметры системы, удовлетворяющей условию поставленной к ней задачи. Также удалось оптимизировать данные параметры.

Рассчитав основные характеристики системы можно приступать к подбору реального оборудования, соответствующего параметрам системы. Общей процессорной мощности должно хватить, чтобы закрыть потребность в 35 ГГц. Так как система имеет 3 процессора, не считая резерва, каждый процессор должен иметь быстродействие как минимум в 12 ГГц. Таковым является Intel Xeon E3-1240 v6. Он имеет 4 ядра по 3700МГц. Суммарное быстродействие трех таких процессоров составит 44 ГГц, оставляя большой запас производительности. C учетом ждущего резерва, суммарная их стоимость составит 1533$. Так как память общая и если говорить об ОЗУ, то, беря в расчет требуемые для каждой задачи объемы памяти и факт того, что для каждой задачи в ОЗУ присутствуют собственные экземпляры файлов, требуемый объем ОЗУ равен 7 ГБ. Пусть в систему будет установлена ОЗУ Apacer [EL.08G2T.GFH] 8 ГБ стоимостью в 150$ с учетом резерва. Итоговая стоимость данной системы составит 1683$.

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

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

⇐ Предыдущая 123 Следующая ⇒

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