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
Ki |
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, результаты и выводы.