Курсовая работа (Резвяков Денис - 7 семестр) (Курсовая работа)

Ф ЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮМ ОСКОВСКИЙ АВИАЦИОННЫЙ ИНСТИТУТ(государственный технический университет)Кафедра 304(вычислительные машины, системы и сети)Курсовая работа по курсу«Организация ЭВМ и систем»Отчёт по работе№4 .Разработка алгоритма и микропрограммы(наименование работы)выполнения операции умноженияВариант задания№1 .Курсовую работу выполнил:студент гр. 13-401 Резвяков Денис Михайлович(должность)(Ф. И. О.).(подпись)Курсовую работу принял:доц. каф.304, к.т.н. Роговцев Алексей Аркадьевич(должность)(Ф.

И. О.).(подпись)«____» ________________ 2008 г.(дата приёма)ОглавлениеТеория....................................................................................................................... 4Пример метода......................................................................................................... 5Алгоритм метода. Блок-схема................................................................................ 7Функциональная схема АЛУ ................................................................................. 8Первый вариант микропрограммы ........................................................................ 9Граф переходов в первом варианте микропрограммы ...................................... 10Среднее время выполнения 1го варианта микропрограммы по Теор.

Вер. ..... 10Оптимизированная микропрограмма.................................................................. 11Граф переходов в оптимизированной микропрограмме................................... 12Среднее время выполнения оптимизир. микропрограммы по Теор. Вер. ...... 12–3–ТеорияВ ЭВМ операция умножения чисел с фиксированной точкой сводитсяк операциям сложения и сдвига.Результат произведения двух n -разрядных чисел может иметь2n разрядов, поэтому в АЛУ необходимо предусмотреть возможностьформирования результата произведения двойной длины, по сравнениюс сомножителями.Операция умножения состоит из n циклов, где n — количествозначащих разрядов множителя.

В каждом цикле анализируется очереднаяцифра множителя. Если это «1», то к сумме частичных произведенийприбавляется множимое, а если «0», то сумма частичных произведенийне изменяется. Цикл завершается сдвигом либо множимого, либо суммычастичных произведений.Различают четыре основных метода выполнения операции умножения.Один из них — умножение, начиная с младших разрядов множителя, присдвиге суммы частичных произведений вправо и неподвижном множимом.В данном методе регистры множителя и суммы частичных произведенийдолжны иметь цепи сдвига вправо. Действие очередного цикла умноженияопределяется младшим разрядом регистра множителя. Так как по мересдвига множителя старшие разряды освобождаются, его обычно используютдля хранения младших разрядов произведения, поступающих из регистрасуммы частичных произведений.Описание умножения чисел, представленных в прямом коде1.

Определить знак результата произведения и запомнить его.2. Обнулить биты, отвечающие за хранение знака числа.3. Вычислить произведение модулей чисел описанным ниже методом.4. Установить сохранённый знак результата в результат умножения.–4–Описание метода умножения1. Анализируется очередной разряд множителяY, начиная с младшего. Если он равен «1»,то к сумме частичных произведений Zприбавляется значение множимого X,а если он равен «0», то к сумме Z ничегоне прибавляется (или прибавляется нуль).2.

Далее множитель Y и сумма частичныхпроизведений Z сдвигаются вправона 1 разряд. В освободившийся старшийразряд множителя Y сохраняется значение «теряемого» младшего разрядасуммы частичных произведений Z. Таким образом АЛУ получаетвозможность формирования результата произведения двойной длины безиспользования бо́льшего регистра Z, по сравнению с сомножителями X и Y.Пример методаИсходные данные:Χ = 0.1011100 = 9210 ,Υ = 1.1010111 = –8710 ,Σ 0 = 00000000 .Обработка знака:Ζ′ = Χ[7] ⊕ Υ[7] = 1.0000000 = (−) ,Χ ′ = Χ & 0.1111111 = 0.1011100 ,Υ0 = Υ & 0.1111111 = 0.1010111 .Первый шаг цикла:Υ0 [0] = 1 :Σ1′ = Σ 0 + Χ′ = 00000000 + 01011100 = 0.01011100 ,Σ1 = (Σ1′ → 1) = 00101110 ,Υ1 = (Υ0 → 1) | (Σ1′ [0] ← 7 ) = 0.0101011 .–5–Второй шаг цикла:Υ1[0] = 1 :Σ′2 = Σ1 + Χ′ = 00101110 + 01011100 = 0.10001010 ,Σ 2 = (Σ′2 → 1) = 01000101 ,Υ2 = (Υ1 → 1) | (Σ′2 [0] ← 7 ) = 00.010101.Третий шаг цикла:Υ2 [0] = 1:Σ′3 = Σ 2 + Χ′ = 01000101 + 01011100 = 0.10100001,Σ 3 = (Σ′3 → 1) = 01010000 ,Υ3 = (Υ2 → 1) | (Σ′3 [0] ← 7 ) = 100.01010 .Четвёртый шаг цикла: Υ3 [0] = 0 :Σ′4 = Σ 3 + 0 = 01010000 + 00000000 = 0.01010000 ,Σ 4 = (Σ′4 → 1) = 00101000 ,Υ4 = (Υ3 → 1) | (Σ′4 [0] ← 7 ) = 0100.0101.Пятый шаг цикла:Υ4 [0] = 1:Σ′5 = Σ 4 + Χ′ = 00101000 + 01011100 = 0.10000100 ,Σ 5 = (Σ′5 → 1) = 01000010 ,Υ5 = (Υ4 → 1) | (Σ′5 [0] ← 7 ) = 00100.010 .Шестой шаг цикла:Υ5 [0] = 0 :Σ′6 = Σ 5 + 0 = 01000010 + 00000000 = 0.01000010 ,Σ 6 = (Σ′6 → 1) = 00100001,Υ6 = (Υ5 → 1) | (Σ′6 [0] ← 7 ) = 000100.01 .Седьмой шаг цикла:Υ6 [0] = 1 :Σ′7 = Σ 6 + Χ′ = 00100001 + 01011100 = 0.01111101 ,Σ 7 = (Σ′7 → 1) = 00111110 ,Υ7 = (Υ6 → 1) | (Σ′7 [0] ← 7 ) = 1000100.0 .Восьмой шаг цикла:Υ7 [0] = 0 :Σ′8 = Σ 7 + 0 = 00111110 + 00000000 = 0.00111110 ,Σ 8 = (Σ′8 → 1) = 00011111 ,Υ8 = (Υ7 → 1) | (Σ′8 [0] ← 7 ) = 01000100 .Результат умножения: Ζ = ((Z ′ | Σ8 ) ← 8) | Υ8 = 1.0011111.01000100 = −8 00410 .Проверка: 92 × (−87) = −8 004 .–6–Алгоритм метода.

Блок-схема–7–Функциональная схема АЛУ–8–Первый вариант микропрограммыМК1: V1, V19. — Рг. X = Швх , Сч. Ц. = 7.Приём множимого из входной шины данных. Установка счётчика циклов в начальное значение.МК2: V2, V7, V11. — Рг. Y = Швх , Рг. 2 = 0, C0 = 0.Приём множимого из входной шины данных. Обнуление суммы частичных произведений. Установка переноса в нуль.МК3: V10.

— Тр. Зн. = Тр. X[7] ⊕ Тр. Y[7].Вычисление и сохранение знака результата произведения.МК4: V3, V4. — Тр. X[7] = 0, Тр. Y[7] = 0.Обнуление старших разрядов множимого и множителя, т.е. взятие их модулей.МК5: Идти к МК7, если R1=0.

— Рг. Y[0] == 0? => идти к МК7.Если младший разряд множителя равен нулю, то перейти на 7-ю микрокоманду.МК6: V8, идти к МК8. — Рг. 1 = Рг. X, идти к МК8.Запись в первое слагаемое значения множимого. Переход на 8-ю микрокоманду.МК7: V6. — Рг. 1 = 0.Запись в первое слагаемое нуля.МК8: V13. — Рг. См.

= Сумма(Рг. 1, Рг. 2, C0 ).Сложение двух текущих слагаемых и переноса. Запись результата в регистр суммы.МК9: V12, V15, V16, V5. — Рг. 1 = П1(Рг. 1), Рг. 1[7] = (Рг. См.[0]),Сдвиг суммы и множителя вправо,…Рг. См. = П1(Рг. См.), Рг. См.[7] = (Тр. Пр.).…а также перенос правого бита суммы в левый бит множителя и бита переполнения в левый бит суммы.МК10: Идти к МК12, если R2=0. — Сч.

Ц. == 0? => идти к МК12.Если счётчик циклов равен нулю, т.е. вычисление закончилось, то перейти на 12-ю микрокоманду.МК11: V17, V20, идти к МК5. — Рг. 2 = Рг. См., Сч. Ц. = Сч. Ц. – 1,Запись суммы во второе слагаемое, уменьшение счётчика циклов на единицу и переход на 5-ю микрокоманду.идти к МК5.МК12: V14. — Рг. См.[7] = Тр. Зн.Установка в старший бит суммы ранее вычисленного и сохранённого знака результата произведения.МК13: V18. — Швых = Рг. См.Выдача в выходную шину данных значения регистра суммы (старшая часть результата).МК14: V9. — Швых = Рг. Y.Выдача в выходную шину данных значения регистра множителя (младшая часть результата).Состояния шагов цикла–. Счётчик = 7.1.

Общий сдвиг = 1. Счётчик Циклов ≠ нулю — продолжаем, Сч. Ц. = 7–1 = 6.Сначала выполняется сдвиг регистров вправо. Затем проверка счётчика циклов на нуль. И затем уменьшение счётчика на 1.2. Общий сдвиг = 2, Счётчик Циклов ≠ нулю — продолжаем, Сч. Ц. = 6–1 = 5.3. Сдвиг = 3, Сч. Ц. ≠ 0, Сч. Ц. = 4.6. Сдвиг = 6, Сч. Ц.

≠ 0, Сч. Ц. = 1.4. Сдвиг = 4, Сч. Ц. ≠ 0, Сч. Ц. = 3.7. Сдвиг = 7, Сч. Ц. ≠ 0, Сч. Ц. = 0.5. Сдвиг = 5, Сч. Ц. ≠ 0, Сч. Ц. = 2.8. Сдвиг = 8, Сч. Ц. = 0, конец.–9–Граф переходов в первом варианте микропрограммыСреднее время выполнения первого варианта микропрограммыпо теории вероятностиτумн.

= τМК1 + τМК2 + τМК3 + τМК4 + n×(τМК5 + p1×τМК6 + (1–p1)×τМК7 + τМК8 + τМК9+ τМК10) + (n–1)×τМК11 + τМК12 + τМК13 + τМК14.В данной работе n=8. И пусть p1=0,5; а τМК=τ. Следовательно:τумн. = 4×τ + n×5×τ + (n–1)×τ + 3×τ. = 7×τ + 6n×τ – τ = (6n+6)×τ = 54τ.– 10 –Оптимизированная микропрограммаВ полученной выше микропрограмме выполнение операций и проверкаусловий осуществляются в разных микрокомандах, т.е. на разных тактах.Если объединить некоторые операции с проверкой некоторого условия,то количество микрокоманд в цикле микропрограммы можно сократить,а, следовательно, увеличить быстродействие.МК1: V1, V19.

— Рг. X = Швх , Сч. Ц. = 7.Приём множимого из входной шины данных. Установка счётчика циклов в начальное значение.МК2: V2, V7, V11. — Рг. Y = Швх , Рг. 2 = 0, C0 = 0.Приём множимого из входной шины данных. Обнуление суммы частичных произведений. Установка переноса в нуль.МК3: V10. — Тр. Зн. = Тр. X[7] ⊕ Тр. Y[7].Вычисление и сохранение знака результата произведения.МК4: V3, V4; идти к МК6, если R1=0. — Тр. X[7] = 0, Тр. Y[7] = 0;Обнуление старших разрядов множимого и множителя, т.е. взятие их модулей…Рг. Y[0] == 0? => идти к МК6.… Если младший разряд множителя равен нулю, то перейти на 6-ю микрокоманду.МК5: V8, идти к МК7.

— Рг. 1 = Рг. X, идти к МК7.Запись в первое слагаемое значения множимого. Переход на 7-ю микрокоманду.МК6: V6. — Рг. 1 = 0.Запись в первое слагаемое нуля.МК7: V13. — Рг. См. = Сумма(Рг. 1, Рг. 2, C0 ).Сложение двух текущих слагаемых и переноса. Запись результата в регистр суммы.МК8: V12, V15, V16, V5; идти к МК11, если R2=0.

— Рг. 1 = П1(Рг. 1),Сдвиг суммы и множителя вправо,…Рг. 1[7] = (Рг. См.[0]), Рг. См. = П1(Рг. См.),…а также перенос правого бита суммы в левый бит множителя и бита переполнения в левый бит суммы.Рг. См.[7] = (Тр. Пр.); Сч. Ц. == 0? => идти к МК11.Если счётчик циклов равен нулю, т.е. вычисление закончилось, то перейти на 11-ю микрокоманду.МК9: V17, V20; идти к МК6, если R1=0. — Рг.

2 = Рг. См.,Запись суммы во второе слагаемое, уменьшение счётчика циклов на единицу.Сч. Ц. = Сч. Ц. – 1; Рг. Y[0] == 0? => идти к МК6.Если младший разряд множителя равен нулю, то перейти на 6-ю микрокоманду.МК10: V8, идти к МК7. — Рг. 1 = Рг. X, идти к МК7.Запись в первое слагаемое значения множимого. Переход на 7-ю микрокоманду.МК11: V14. — Рг. См.[7] = Тр. Зн.Установка в старший бит суммы ранее вычисленного и сохранённого знака результата произведения.МК12: V18. — Швых = Рг. См.Выдача в выходную шину данных значения регистра суммы (старшая часть результата).МК13: V9. — Швых = Рг. Y.Выдача в выходную шину данных значения регистра множителя (младшая часть результата).– 11 –Граф переходов в оптимизированной микропрограммеСреднее время выполнения оптимизированной микропрограммыпо теории вероятностиτумн. = τМК1 + τМК2 + τМК3 + τМК4 + (1–p1)×τМК5 + (p1)×τМК6 + n×(τМК7 + τМК8)+ (n–1)×(τМК9 + (1–p1)×τМК10 + (p1)×τМК6) + τМК11 + τМК12 + τМК13.В данной работе n=8.

И пусть p1=0,5; а τМК=τ. Следовательно:τумн. = 4×τ + τ + n×2×τ + (n–1)×2×τ + 3×τ. = 8×τ + 4n×τ – 2×τ = (4n+6)×τ = 38τ.– 12 –.