РГЗ по АВС 13 вариант


Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования
«Сибирский государственный университет телекоммуникаций и информатики»
Кафедра ВСРасчетно-графическое задание
По дисциплине
«Архитектура вычислительных сетей»
Вариант № 13
Выполнила: студентка гр. П-93
Константинова Х.О.
Проверил: профессор
Хорошевский В.Г.
Новосибирск 2011г.
Задание №1. Осуществить анализ архитектуры EDVAC.
Изготовление машины EDVAC (Electronic Discrete Variable Automatic Computer –электронный автоматический вычислитель для дискретных величин ) было осуществлено в 1944-1950 гг. в Электротехнической школе Мура Пенсильванского университета США.
В основу ЭВМ были положены оригинальные принципы работы и решения по функциональной структуре и элементарной базе, полученные Д. Мочли, П. Эккертом и Дж. Фон Нейманом. Автоматизация вычислений была одной из основных парадигм при проектировании машины: EDVAC – это автоматический компьютер, т.е. ЭВМ, способная хранить в своей памяти программу вычислений.Отмечу некоторые показатели EDVAC: тактовая частота – 1 МГц (на порядок выше, чем в ENIAC); быстродействие – 1000 опер.\с над 32-разрядными двоичными числами; емкость оперативной памяти – 32768 байт; количество электронных ламп – 3000.
615315592455Функциональная структура машины EDVAC.
Вычислительная машина EDVAC состояла из центрального арифметического устройства (АУ), оперативно запоминающего устройства (ОЗУ), внешних запоминающих устройств (ВЗУ), входного и выходного узлов (УВх, УВых) и центрального управляющего устройства (УУ).
Арифметическое устройство предназначалось для выполнения операций сложения, вычитания, умножения, деления, извлечения квадратного корня, для преобразования чисел из двоичной системы счисления в десятичную и обратно, для пересылок чисел из одних регистров АУ в другие, а также между ОЗУ и регистрами АУ и для осуществления выбора одного из двух чисел в зависимости от знака третьего числа. Последняя операция использовалась для передачи управления (условного перехода) от одной программы к другой. Числа в АУ обрабатывались последовательно, начиная с последнего значащего разряда, и в каждый момент времени выполнялась только одна операция. Регистры АУ представляют собой линии задержки на одно 32-разрядное двоичное слово.
Память (ОЗУ) содержала до 256 линий задержки, каждая из которых была способна хранить 32 слова, имеющих 32 двоичных разряда, а также переключательную схему, связывающую ячейки памяти с остальной частью машины. Память предназначалась для хранения начальных и граничных условий для дифференциальных уравнений в частных производных, произвольных числовых функций, промежуточных результатов вычислений, а также программы (последовательности команд), управляющей ходом вычислений.
Внешние ЗУ были рассчитаны на следующие носители информации: перфокарты, бумажные перфоленты, магнитные ленты, фотопленку. Предполагалось использовать ВЗУ в качестве дополнительной медленнодействующей памяти, а также для ввода и вывода информации.
Память EDVAC была последовательной, слова считывались из нее и записывались в нее последовательно бит за битом.
Входной узел предназначался для пересылки информации из ВЗУ в ОЗУ, выходной – из ОЗУ в ВЗУ. В оперативном запоминающем устройстве использовалась двоичная система счисления, а в ВЗУ – десятичная.
Устройство управления предназначалось для координации работы остальных устройств ЭВМ, в частности, оно формировало поток команд в АУ. Синхронизация работы всех устройств ЭВМ осуществлялась от единого источника импульсов, названного «часами» (сейчас это генератор тактовых или синхронизирующих импульсов).
В машине EDVAC первый двоичный разряд каждого слова служил для идентификации команд и чисел, причем единица соответствовала команде, а нуль - числу. В EDVAC использовались одноадресные команды, для задания кода операции и адреса операнда в ОЗУ отводилось соответственно 8 и 13 разрядов.
Рассмотрим типичный фрагмент программы обработки числовых данных и работы устройств ЭВМ. Пусть в АУ находится первое слагаемое, а в регистрах или ячейках ОЗУ α, (α+1) и (α+2) размещаются соответственно команда, задающая операцию сложения и адрес β, второе слагаемое и команда, которую предстоит выполнить вслед за сложением. Адекватной последовательностью действий ЭВМ будет следующее: пересылка команды из ячейки α в центральное УУ, передача слагаемого из (α+1) в АУ, выполнение операции сложения в АУ, запись суммы в ячейку β и, наконец, выполнение команды из ячейки (α+2).
Наряду с командой условного перехода в машине EDVAC имелась команда безусловной передачи управления, именно команда с адресом ϒ, обеспечивавшая возможность для центрального УУ извлечения следующей команды из ячейки ϒ ОЗУ. Кроме того, в EDVAC была заложена возможность автоматической модификации адреса в команде.
Таким образом, машина EDVAC была полностью автоматическим программируемым вычислительным средством.
Анализ машины EDVAC.
Машина имела жесткую функциональную структуру. По своей архитектуре EDVAC относится к классу SISD.
Архитектурные особенности:
1). Автоматизация вычислений (возможность хранения программы в памяти и ее автоматической модификации);
2). Последовательный способ обработки информации;
3). Фиксированность структуры (невозможность даже ручного реконфигурирования, за исключением ВЗУ);
4). Конструктивная неоднородность.
Архитектурные решения, положенные в основу EDVAC, привели к простоте ее реализации: потребовалось около 3000 электронных ламп. Уровень сложности и достигнутые технические характеристики (показатели производительности, емкости памяти и надежности) ЭВМ вполне отвечали уровню техники и потребностям 50-х годов 20-го столетия. В самом деле, машина EDVAC характеризовалась следующими параметрами:
1). Количество двоичных разрядов для представления чисел – 32;
2). Тактовая частота – 1 МГц;
3). Емкость оперативной памяти – 32 К байт.
Таким образом, ЭВМ EDVAC отражает дуализм в развитии цифровых средств информатики, говоря иначе, констатируют неизбежность двух начал: параллельных и последовательных архитектур.
Задание №2. Разработать блок-схему -алгоритма для вычисления произведения двух матриц:

-алгоритм должен обеспечить распределение элементов матрицы по горизонтальным полосам в элементарных машинах ВС.
Определить максимум коэффициента накладных расходов при реализации -алгоритма на модифицированной ВС СУММА.
Необходимо разработать блок-схему р-алгоритма для вычисления произведения двух матриц:
E [1:N; 1:M] = D [1:K;1:M] * C [1:N;1:K],
применив распределения в машинах BC матрицы E по горизонтальным полосам.
Структуры параллельных алгоритмов (р-программ) определяются графами информационных и управляющих связей, вершинам которых сопоставлены операторы ветвей, а ребрам информационные и управляющие связи между операторами. Анализ прямых и итерационных методов вычислительной математики показывает, что в их основе лежат, как правило, операции над матрицами и векторами данных.
Проиллюстрируем методику крупноблочного распараллеливания на примере умножения матриц больших размеров. Требуется построить параллельный алгоритм, вычисляющий произведение двух прямоугольных матриц:
E [1:N; 1:M] = C [1:N;1:K] * D [1:K;1:M],
или
c11c12⋯c1p⋯c1Kc21c22⋯c2p⋯c2K⋮⋮⋱⋮⋯⋮ci1ci2⋯cip⋯ciK⋮⋮⋯⋮⋱⋮cN1cN2⋯cNp⋯cNK×d11d12⋯d1j⋯d1Md21d22⋯d2j⋯d2M⋮⋮⋱⋮⋯⋮dp1dp2⋯dpj⋯dpM⋮⋮⋯⋮⋱⋮dK1dK2⋯dKj⋯dKM=e11e12⋯e1j⋯e1Me21e22⋯e2j⋯e2M⋮⋮⋱⋮⋯⋮ei1ei2⋯eij⋯eiM⋮⋮⋯⋮⋱⋮eN1eN2⋯eNj⋯eNMгде элементы матрицы-произведения E[1 : N; 1 : M] вычисляются по формуле
eij=p=1KcipdpjРазмеры матриц C и D N×K и K×M достаточно большие. Следовательно, имеют место неравенства N>>n, K>>n, M>>n, где n – это вычислители.
Вычислитель 1 × Вычислитель 1 Вычислитель 2 … Вычислитель k … Вычислитель n = Вычислитель 1
Вычислитель 2 Вычислитель 2
… …
Вычислитель k Вычислитель k
… …
Вычислитель n Вычислитель n
H × A = B
На этом рисунке показано распределение данных по вычислителям ВС.
Рассмотрим блок-схему ралгоритма:
Вычисление
eij=p=1KcipdpjДа
Да
Нет
Передача
|| a1j,…,apj,…,akj||
α=n
?
Нет
Нет
Да
Начало
Конец
α=k
?
α:=0
j:=1
α:=α+1
Прием
|| a1j,…,apj,…,aKj||
j>α]M/n[
?
j:=j+1

α – номер передающего вычислителя, – номера принимающих вычислителей.
Нахождение максимума коэффициента Е накладных расходов при реализации р-алгоритма на ВС СУММА.
Известно
время пересылки элементов матрицы tn=4,5мкс.
время выполнения операции умножения ty=350мкс.
время выполнения операции сложения tc=4,5мкс.
Коэффициент накладных расходов рассчитывается по формуле:
Е=t/T
где t - время, расходуемое на обмен информацией;
T - время, расходуемое на вычисление логических операций;
В соответствии с алгоритмом при пересылки строки матрицы А, состоящей из N – элементов, в каждом вычислители производится N*]M/n[ - операций умножения и (N-1)*]M/n[ - операций сложения.
Так как используется матрицы с большой размерностью, т.е. M>>n,
следовательно, можно считать, что после пересылки одного элемента из любого вычислителя во все остальные вычислители производится ρ=]M/n[ - операций сложения и умножения.
Получаем:
E=tn/(ρ*(tc+ty))
В параллельных алгоритмах показатель ρ не может быть меньше единицы, в противном случае нет необходимости распараллеливания.
Итак, максимум коэффициента накладных расходов достигается при ρ=1.
Подставим, известные численные значения в формулу:
Е=4,5мкс/(1*(350мкс+4,5мкс))=0,0127мкс.
Ответ: Максимум коэффициента накладных расходов равен 0,0127мкс.

Приложенные файлы

  • docx 8814683
    Размер файла: 52 kB Загрузок: 0

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