Лабораторная работа оптимальный выбор типов модулей устройства ВС

9. ОПТИМАЛЬНЫЙ ВЫБОР ТИПОВ МОДУЛЕЙ УСТРОЙСТВА ВС

9.1. ЦЕЛЬ РАБОТЫ -освоение методики выбора типов модулей для реализации устройства ВС заданной надежности.

9.2. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

9.2.1. Изучить раздел 9.3 указаний и рекомендованную литературу [7,9] по теме работы.

9.2.2. По заданному варианту стоимостных и надежностных параметров способа реализации модулей, входящих в устройство (процессор), выбрать оптимальный набор способов, минимизирующих общую стоимость устройства при заданной его надежности. В качестве последней задать величину Ро = 1 - q1*, где q1* - ненадежность процессора, определенная в л. р. №8. Подсчитать полученную таким способом минимальную стоимость устройства и соответствующую ему надежность.

9.2.3. Оформить отчет по работе.

9.3. ЭЛЕМЕНТЫ ТЕОРИИ И МЕТОДИЧЕСКИЕ УКАЗАНИЯ

Пусть устройство ВС (например, процессор) состоит из m функционально обособленных модулей (например, это могут быть модули сумматора, устройства управления, регистров, микропрограмм и т. д.). Модуль i может быть реализован mi различными способами, причем j-й его реализации соответствуют известные стоимость сij и надежность pij. Пусть х = (хij), где xij = 1, если i-й модуль представлен в устройстве j-й реализацией, и xij = 0 в противном случае. Тогда задача выбора типов (реализаций) модулей, минимизирующего общую стоимость С(х) устройства при заданной его ненадежности q0, математически представляется в следующем виде [1]:

минимизировать

С(х) = (9.1)

при условиях

, (9.2)

qijxij £ qo , (9.3)

ci1 < ci2 < ... < ci m , (9.4)

qi1 > qi2 > ... > qi m , (9.5)

где qij = - ln pij и qо = - ln Po. (9.6)

План х, удовлетворяющий условиям (9.2), (9.3) и минимизирующий (9.1), называется оптимальным планом выбора типа модулей. Ему соответствует минимальное значение C min стоимости (9.1) устройства.

Для решения задачи (9.1) - (9.6) предлагается [2] следующий алгоритм.

Начало.

1. Вводим массивы (сij) и (pij) , i=1, ... , m; j=1, ... , mi . Формируем массив (qij), где qij= - ln pij. Элементы массивов (сij) и (qij) должны удовлетворять условиям (9.4), (9.5), i = 1, ... , m, j = 1, ... , mi.

2. Формируем массив b = (bij), где

, j ¹ mi, bi m = 0 , (9.7)

и полагаем qо = - ln Po .

3. Задаем начальный план, полагая =1, xij = 0 для j ¹ mi .

4. Проверяем условие (9.3). Если оно не выполняется, то в случае, если х - начальный план - заключаем, что задача решения не имеет, и переходим на конец. В случае, если х - не начальный план, то восстанавливаем план х`, предшествовавший х, и переходим к п.7. При выполнении (9.3) переходим к п.5.

5. Находим максимальный элемент bij в массиве b. Если их несколько, то среди них выбираем тот, которому соответствует наибольшее cij. Если же и таких оказывается несколько, то среди последних выбираем тот, которому соответствует наименьшее qij.

6. Пусть (r, s)– номер, определенный в п.5. Полагаем xrs = 1, xrj = 0 при j ≠ s. (Другими словами, в строке r плана x перемещаем единицу на место номер s). Далее полагаем brs=0 и переходим к п.4.

7. Вычисляем «запас надежности» d,

(9.8)

Затем полагаем равными нулю все элементы bij, которым соответствуют элементы qij> d, и после этого проверяем условие

. (9.9)

Если (9.9) выполнено, то план х` может быть улучшен; и поэтому возвращаемся к п.5. В противном случае, а также в случае, если b=0, полагаем xопт= х` и переходим к п.8.

8. Выводим оптимальный план xопт, соответствующую ему минимальную стоимость C(xопт), подсчитанную по формуле (9.1), и ненадежность, вычисленную как левая часть неравенства (9.3).

Конец.

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

9.4. ПРИМЕР ВЫБОРА

В качестве оптимизируемого устройства выберем процессор ВС, состоящий из четырех модулей: 1 – сумматор, 2 – модуль управления, 3 – блок регистров, 4 – память микропрограмм. Пусть первый модуль реализуется четырьмя способами (m1=4), второй – двумя (m2=2), третий – пятью (m3=5) и четвертый – тремя (m4=3).

Массивы стоимостных и надежностных характеристик таковы:

, .

Надежность процессора должна быть не менее 0,99782, или, что то же, его ненадежность Q0 - не более 2,18*10-5 (см. лаб. раб. №8).

Реализуя алгоритм, имеем следующую последовательность действий:

1. Массив (qij) в данном случае совпадает с массивом 1-p, поскольку с большой точностью qij = ln pij = 1- pij. Непосредственной проверкой исходных массивов убеждаемся, что они удовлетворяют условиям (9.4) и (9.5).

2. Формируя массив bij согласно (9.7), получаем:

Полагаем q = -lnP0 = -ln(1-Q0) =218*10 -5.

3. Задаем начальный план:

Далее, выполняя п. п. (4) – (6) алгоритма, имеем следующую последовательность приближений к оптимальному плану:

Последнее приближение в этой цепочке, план x8, не удовлетворяет условию (9.3), поскольку q0=218*10-5, а сумма qij слева в неравенстве (9.3) равна 228*10-5. Поэтому переходим к п.7 алгоритма и вычисляем запас надежности d, соответствующий плану x7, по формуле (9.8):

d = 218*10 –5 – 180*10 –5 =38*10 –5.

Рабочий массив b после «обнуления», предусмотренного в п.7, выглядит так:

Поскольку условие (9.9) выполнено, то с планом x7 возвращаемся к п.5 и по завершении работы алгоритма получаем:

Ему соответствует стоимость C(хопт) = 42,5 и ненадежность Q =208*10 -5. Ненадежности модулей при этом, в стотысячных долях: сумматора – 24, модуля управления – 80, регистров – 72 и памяти микропрограмм – 32.

Таким образом, в результате решения задачи рекомендуется для процессора выбрать первую реализацию сумматора, вторую реализацию модуля управления, первую реализацию блока регистров и вторую реализацию памяти микропрограмм. Стоимость процессора при этом составит 42,5, а его надежность – 0,99792, что удовлетворяет требованиям.

9.5. ВАРИАНТЫ ЗАДАНИЙ

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

Номер n варианта задает, согласно формулам k=n mod5, m=]n/5[, номер k массива стоимостных и номер m массива надежностных параметров модулей процессора.

Массивы стоимостных параметров приведены в табл. 9.1, надежностных – в табл. 9.2.

Таблица 9.1

K i	0	1	2	3	4
1	3,5,7,8,9	2,4,5,6,7	3,4,6,8,10	2,3,4,5,7	5,6,8,9,11
2	16,17,20	15,16,17	10,11,14	13,15,16	14,16,18
3	9,10,12,14	8,9,11,13	5,6,7,8	9,10,11,12	10,12,14,16
4	11,13,15	12,14,16	13,14,15	10,12,15	14,16,18

Стоимость модулей процессора, усл. ед.

Таблица 9.2

M	1	2	3	4	5
i
1	23,19,15,13,11	25,20,19,16,15	23,20,16,10,9	25,23,20,19,18	19,16,13,11,9
2	90,85,70	95,90,85	115,110,100	105,95,90	100,90,80
3	64,60,50,45	72,64,55,47	90,82,75,72	64,60,55,50	60,50,45,39
4	34,30,22	35,32,29	30,25,23	32,25,22	33,27,24

Ненадежность модулей процессора, (1-р)105

9.6. СОДЕРЖАНИЕ ОТЧЕТА

Постановка задачи по типу раздела 9.3, протокол реализации алгоритма по типу раздела 9.4, результаты и выводы.