Лабораторные работы Вычислительные системы
  • Регистрация
1 1 1 1 1 1 1 1 1 1 Рейтинг 0.00 (0 Голоса)

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 при js. (Другими словами, в строке 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, результаты и выводы.

Добавить комментарий


Защитный код
Обновить

По темам:

История Украины

Культурология

Высшая математика

Информатика

Охотоведение

Статистика

География

Военная наука

Английский язык

Генетика

Разное

Технологиеские темы

Украинский язык

Филология

Философия

Химия

Экология

Социология

Физическое воспитание

Растениевосдство

Педагогика

История

Психология

Религиоведение

Плодоводство

Экономические темы

Бухгалтерские темы

Маркетинг

Иностранные языки

Ветеринарная медицина

Технические темы

Землеустройство

Медицинские темы

Творчество

Лесное и парковое хозяйство