Домашнее задание №1

Государственное образовательное учреждение

высшего профессионального образования

«Московский государственный технический университет имени Н.Э. Баумана»

(МГТУ им. Н.Э.Баумана)

________________________________________________________________________

Факультет

«ФУНДАМЕНТАЛЬНЫЕ НАУКИ»

Кафедра

«ПРИКЛАДНАЯ МАТЕМАТИКА»

Домашнее задание по дисциплине

« ПРИКЛАДНОЕ ПРОГРАММИРОВАНИЕ В ЗАДАЧАХ

МАТЕМАТИЧЕСКОЙ ФИЗИКИ »

Домашнее задание №1

ИСПОЛНИТЕЛЬ

студент гр. ФН2-91 ________________ / Голубева Ю.Ю. /

ПРЕПОДАВАТЕЛЬ ________________ / Фисун В. А. /

кандидат ф.-м. наук,

старший научный сотрудник

ИПМ им. М.В.Келдыша РАН.

Москва 2019

Оглавление

1. Анализ принципов фон Неймана.

  Принципы Дж. фон Неймана содержат ряд идей организации ЭВМ. Просто и очевидно они формулируют фундаментальные положения, в результате реализации которых была создана архитектура ЭВМ. Эта структура во многих чертах сохранилась до настоящего времени. 

Основные принципы заключаются в следующем:

1. Компьютеры на электронных элементах должны работать не в десятичной, а в двоичной системе счисления.

Этот принцип расширил набор физических приборов и явлений, которые можно использовать для представления информации в операционных и запоминающих устройствах компьютера. Две цифры для отображения "1" и "0" могут отображаться состоянием любой двухстабильной системы. В двоичной системе счисления возможно построение логических схем и реализация функций алгебры логики или Булевой алгебры.

2. Компьютер управляется программой, составленной из отдельных шагов - команд. Программа должна размещаться в одном из блоков компьютера - в запоминающем устройстве, обладающем достаточной емкостью и скоростью выборки команд.

3. Команды, так же как и числа, с которыми оперирует компьютер, записываются в двоичном коде.

Реализация этого принципа приводит к следующим важным последствиям:

а) промежуточные результаты вычислений, константы и другие числа могут размещаться в том же запоминающем устройстве, что и программа;

б) числовая форма записи программы позволяет производить операции над величинами, которыми закодированы команды программы;

в) появляется возможность перехода в процессе вычислений на тот или иной участок программы в зависимости от результатов вычислений, условных переходов.

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

Принцип реализации условных переходов позволяет осуществлять программы с циклическими вычислениями с автоматическим выходом из цикла. Благодаря принципу условного перехода сокращается число команд в программе, т.к. не требуется повторять одинаковые участки программы

4. Трудности физической реализации запоминающего устройства, быстродействие которого соответствует скорости работы логических схем, требуют иерархической организации памяти.

Иерархическое построение оперативного запоминающего устройства позволяет иметь быстродействующую память небольшого объема только для данных и команд, подготовленных к выполнению. Все остальное хранится в запоминающем устройстве более низкого уровня.

5. Арифметическое устройство конструируется на основе схем, выполняющих операцию сложения - создание специальных устройств для выполнения других операций нецелесообразно.

6. Необходимо использовать параллельный принцип организации вычислительного процесса (операции над словами производятся одновременно во всех разрядах слова).

    Параллельный принцип организации вычислений позволяет значительно увеличить скорость вычислений, хотя это и приводит к более значительным затратам оборудования.

1. Ассоциативная память. Реализация и использование. В виде алгоритма / программы написать хэш-функцию хранения сильно разреженной 2D матрицы.

Ассоциативная память – это безадресная память, в которой поиск информации производится по ее ассоциативному признаку. 

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

Реализация и использование.

Поиск информации производится параллельно по всем ячейкам путем сравнения запроса с ассоциативным признаком каждой ячейки. 

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

После формирования и обработки оповещающих сигналов схемой управления производится считывание необходимой информации. При записи отыскивается свободная ячейка по значению разряда занятости, в первую найденную свободную ячейку записывается информация. 

Проверка разряда занятости производится по установке n-го разряда (разряда занятости) маски. При использовании  дополнительных комбинационных схем в ассоциативной памяти можно выполнять различные логические операции, определяя максимальное или минимальное число, количество слов, имеющих одинаковый ассоциативный признак и т.д.

Ячейки памяти ассоциативного запоминающего устройства должны быть элементами статической памяти, в ассоциативной памяти обращение производится ко всем ячейкам одновременно и не должно прерываться циклами регенерации.

Ассоциативная память наиболее быстродействующая, но очень дорогая, так как требует введения дополнительно схемы сравнения, позволяющей осуществить поиск,  для каждой ячейки памяти. Поэтому такая память обычно не используется в чистом виде, а быстродействующие устройства памяти типа «кэш» обычно выполняются как частично ассоциативные.

  В микропроцессорах, например, ассоциативная память (память с выборкой по содержанию) используются в составе кэш-памяти для хранения адресной части команд и операндов исполняемой программы. При этом нет необходимости обращаться к ОЗУ за следующей командой или требуемым операндом, достаточно поместить в регистр ассоциативного признака необходимый адрес и, если искомая информация имеется в кэш памяти, то она сразу будет выдана. Обращение к оперативной памяти будет необходимо лишь при отсутствии требуемой информации в кэш. За счет такого использования кэш сокращается число обращений к ОЗУ, а это позволяет экономить время, так как обращение к кэш требует приблизительно в 10 раз меньше времени, чем обращение к ОЗУ.

В виде алгоритма / программы написать хэш-функцию хранения сильно разреженной 2D матрицы.

Для больших сильно разряженных матриц экономия памяти является очень актуальной проблемой. С такими матрицами можно работать, используя квадратичное повторное хэширование.

Алгоритм:

1. определение максимального размера хэш-таблицы (M) для хранения разряженного массива (значение зависит от максимально возможного количества ненулевых элементов), но не менее где n – простое число;

2. задание

3. вычисление ключа доступа к элементу хэш-таблицы (хэш-адреса) через пару индексов (i,j), где по одной из формул:

1. если ячейка свободна или ключ элемента в ней совпадает с исходным ключом, то завершение процесса поиска. Иначе

2. вычисление

3. если то переход к шагу 4. Иначе ( ) таблица полностью заполнена.

1. Тэги в КЭШ-памяти.

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

Вариантом решения проблемы является добавление кэш-памяти, в которой хранятся наиболее часто используемые слова, за счет чего повышается скорость доступа к ним.

Любая кэш-память подразделяется на строки (lines). У каждой строки в свою очередь имеется адресное поле, которое  состоит из двух основных частей: динамической (tag), которая содержит старшие биты адреса, и статической (index), которая содержит младшие биты адреса. Первая часть может быть изменена в процессе работы, значение второй зафиксировано.

Поле адресного тега состоит из уникального 16-разрядного значения, указывающего соответствующую строку памяти, из которой поступили данные. Такой тег обычно одновременно сравнивается с выработанным процессором адресом блока памяти.

Размер тэга строки кэш-памяти зависит от трех основных факторов:

• размера кэш-памяти;

• ассоциативности кэш-памяти;

• кэшируемого размера оперативной памяти.
  Этот размер рассчитывается по следующей формуле: 

где - размер одного тэга в кэш-памяти, в битах; - максимальный кэшируемый размер оперативной памяти, в байтах; - размер кэш-памяти, в байтах; A – ассоциативность кэш-памяти, в каналах.

Таким образом, для абстрактной системы с максимальным кэшируемым объёмом оперативной памяти в 1Гб и кэш-памятью (неважно какого уровня) размером в 1Мб с 2-канальной ассоциативностью потребуется ровно 11 бит для каждого тэга. Другими словами, для адресации любым отдельным тэгом 1Гб / 512Кб = 2048 сегментов памяти потребуется log₂(2048) = 11 бит. Следует уточнить, что ровно столько бит на тэг необходимо для кэширования именно 1Гб оперативной памяти при данной организации кэш-памяти. Если сократить количество бит, то такой кэш останется работоспособным, однако кэшируемый размер оперативной памяти уменьшится. Например, 8 бит на тэг позволят адресовать уже только 2⁸ = 256 сегментов памяти по 512Кб, что позволит кэшировать лишь 128Мб оперативной памяти. Информация, находящаяся выше этой границы, кэшироваться не будет.

1. Многоуровневая КЭШ-память.

Ключевой проблемой многоуровневой кэш-памяти является баланс между задержками КЭШа и интенсивностью попаданий¹. Большие КЭШи обладают более высоким процентом попаданий однако, при этом имеют и большую задержку. Для устранения остроты противоречия двух главных характеристик, в большинстве компьютеров применяется несколько уровней КЭШа: после маленьких и быстрых кэшей расположены более медленные и большие КЭШи. На сегодняшний день, суммарно применяется до 3 уровней в иерархии КЭШей.