Редактирование: ПОД (3 поток), Ответы
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
ПРЕДУПРЕЖДЕНИЕ: Длина этой страницы составляет 320 килобайт. Страницы, размер которых приближается к 32 КБ или превышает это значение, могут неверно отображаться в некоторых браузерах. Пожалуйста, рассмотрите вариант разбиения страницы на меньшие части.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
| Текущая версия | Ваш текст | ||
| Строка 84: | Строка 84: | ||
===Первое поколение=== | ===Первое поколение=== | ||
| - | Первое поколение ЭВМ /1946-1957гг/ использовало в качестве основного элемента электронную лампу. Быстродействие их не превышало 2-3 т. оп./сек; емкость ОЗУ - 2-4 К слов. Это ЭВМ: БЭСМ-1 (В.А. Мельников,1955г.), Минск-1 (И.С. Брук 1952/59 гг.), Урал-4 (Б. И. Рамеев), Стрела (Ю.Я. Базилевский, 1953 г.), М-20 (М.К. Сулим 1860 г. <!-- Парень явно опередил своё время! -->). А.Н. Мямлиным была разработана и несколько лет успешно эксплуатировалась "самая большая в мире ЭВМ этого поколения" <!-- Ох уж эти советские микросхемы, самые большие микросхемы в мире! -->- машина Восток. Программирование для этих машин: однозадачный, пакетный режим, машинный язык, ассемблер ( | + | Первое поколение ЭВМ /1946-1957гг/ использовало в качестве основного элемента электронную лампу. Быстродействие их не превышало 2-3 т. оп./сек; емкость ОЗУ - 2-4 К слов. Это ЭВМ: БЭСМ-1 (В.А. Мельников,1955г.), Минск-1 (И.С. Брук 1952/59 гг.), Урал-4 (Б. И. Рамеев), Стрела (Ю.Я. Базилевский, 1953 г.), М-20 (М.К. Сулим 1860 г. <!-- Парень явно опередил своё время! -->). А.Н. Мямлиным была разработана и несколько лет успешно эксплуатировалась "самая большая в мире ЭВМ этого поколения" <!-- Ох уж эти советские микросхемы, самые большие микросхемы в мире! -->- машина Восток. Программирование для этих машин: однозадачный, пакетный режим, машинный язык, ассемблер (совковый аналог - [[wikipedia:ru:Автокод#Происхождение и критика термина «язык ассемблера»|Автокод]]). |
===Второе поколение=== | ===Второе поколение=== | ||
| Строка 136: | Строка 136: | ||
У лектора немного другая структура принципов. | У лектора немного другая структура принципов. | ||
=== Программное управление работой ЭВМ === | === Программное управление работой ЭВМ === | ||
| - | Программа -- последовательность | + | Программа -- последовательность комманд, хранимая в ОЗУ. Каждая программа задает единичный акт преобразования информации. В каждый момент времени выполняется только 1 команда программы. |
| - | + | ||
=== Принцип условного перехода === | === Принцип условного перехода === | ||
| - | Возможен переход в процессе вычисления на тот или иной участок программы в зависимости от промежуточных, получаемых | + | Возможен переход в процессе вычисления на тот или иной участок программы в зависимости от промежуточных, получаемых а ходе вычисления, результатов. |
| - | + | ||
=== Принцип хранимой программы === | === Принцип хранимой программы === | ||
Команды представляются в числовой форме и хранятся в ОЗУ, в том же виде, что и исходные данные, следовательно над командой можно производить арифметические действия, изменяя ее динамически. | Команды представляются в числовой форме и хранятся в ОЗУ, в том же виде, что и исходные данные, следовательно над командой можно производить арифметические действия, изменяя ее динамически. | ||
| Строка 213: | Строка 211: | ||
= Ассоциативная память. = | = Ассоциативная память. = | ||
| - | Оперативную память (ОП) можно представить в виде двумерной таблицы, строки которой хранят в двоичном коде команды и данные. Обращения за | + | Оперативную память (ОП) можно представить в виде двумерной таблицы, строки которой хранят в двоичном коде команды и данные. Обращения за содержимом строки производится заданием номера (адреса) нужной строки. При записи, кроме адреса строки указывается регистр, содержимое которого следует записать в эту строку. Запись занимает больше времени, чем чтение. Пусть в памяти из трех строк хранятся номера телефонов. |
{| border=1 | {| border=1 | ||
| Строка 264: | Строка 262: | ||
'''Ответ:''' Область памяти делим ровно пополам. Первая половина заполняется ключами, вторая соответствующими ключам значениями. Когда найден ключ, известен его адрес как смещение относительно начала памяти. Тогда адрес содержимого по ключу – это смещение + размер области ключей, то есть адрес ячейки из второй половины памяти, которая соответствует ключу. ''А не имеется ли тут в виду реализация hash или индексных деревьев?'' | '''Ответ:''' Область памяти делим ровно пополам. Первая половина заполняется ключами, вторая соответствующими ключам значениями. Когда найден ключ, известен его адрес как смещение относительно начала памяти. Тогда адрес содержимого по ключу – это смещение + размер области ключей, то есть адрес ячейки из второй половины памяти, которая соответствует ключу. ''А не имеется ли тут в виду реализация hash или индексных деревьев?'' | ||
| - | |||
| - | '''Ответ-2''': Предположим, у нас очень много оперативной памяти. Тогда рассмотрим ключ, как двоичную последовательность, то есть, это некое число. Рассмотрим это число, как адрес в памяти - там и будем хранить и искать значение, соответствующее данному ключу. | ||
= Виртуальная память. = | = Виртуальная память. = | ||
Внутри программы к моменту образования исполняемого модуля используется модель организации адресного пространства программы (эта модель, в общем случае не связана с теми ресурсами ОЗУ, которые предполагается использовать позднее). Для простоты будем считать, что данная модель представляет собой непрерывный фрагмент адресного пространства в пределах которого размещены данные и команды программы. Будем называть подобную организацию адресации в программе программной адресацией или '''логической/виртуальной адресацией'''. | Внутри программы к моменту образования исполняемого модуля используется модель организации адресного пространства программы (эта модель, в общем случае не связана с теми ресурсами ОЗУ, которые предполагается использовать позднее). Для простоты будем считать, что данная модель представляет собой непрерывный фрагмент адресного пространства в пределах которого размещены данные и команды программы. Будем называть подобную организацию адресации в программе программной адресацией или '''логической/виртуальной адресацией'''. | ||
| - | Итак, повторяем, на уровне исполняемого кода имеется программа в машинных кодах, использующая адреса данных и команд. Эти адреса в общем случае не являются адресами конкретных физических ячеек памяти, в которых размещены эти данные, более того, | + | Итак, повторяем, на уровне исполняемого кода имеется программа в машинных кодах, использующая адреса данных и команд. Эти адреса в общем случае не являются адресами конкретных физических ячеек памяти, в которых размещены эти данные, более того, в последствии мы увидим, что виртуальным (или программным) адресам могут ставиться в соответствие произвольные физические адреса памяти. То есть при реальном исполнении программы далеко не всегда виртуальная адресация, используемая в программе совпадает с физической адресацией, используемой ЦП при выполнении данной программы. |
===Базирование адресов.=== | ===Базирование адресов.=== | ||
| Строка 331: | Строка 327: | ||
===Алгоритм «Часы»=== | ===Алгоритм «Часы»=== | ||
| - | ''(Это то же самое, что и алгоритм вторая попытка)'' | ||
#Если R=0, то выгрузка страницы и стрелка на позицию вправо. | #Если R=0, то выгрузка страницы и стрелка на позицию вправо. | ||
#Если R=1, то R-обнуляется, стрелка на позицию вправо и на П.1. | #Если R=1, то R-обнуляется, стрелка на позицию вправо и на П.1. | ||
| Строка 341: | Строка 336: | ||
* Памяти N страниц. Существует битовая матрица NxN (изначально полностью обнулена). | * Памяти N страниц. Существует битовая матрица NxN (изначально полностью обнулена). | ||
* При каждом обращении к i-ой странице происходит присваивание 1 всем битам i-ой строки и 0 - всем битам i-ого столбца. | * При каждом обращении к i-ой странице происходит присваивание 1 всем битам i-ой строки и 0 - всем битам i-ого столбца. | ||
| - | * Строка с наименьшим | + | * Строка с наименьшим двоичным кодом - искомая |
===Алгоритм NFU=== | ===Алгоритм NFU=== | ||
| Строка 407: | Строка 402: | ||
'''Writethrough''' | '''Writethrough''' | ||
| - | При обновлении кэш-памяти методом сквозной записи контроллер кэш-памяти одновременно обновляет содержимое основной памяти. Иначе говоря, основная память отражает текущее содержимое кэш-памяти. Быстрое обновление позволяет перезаписывать любой блок в кэш-памяти в любое время без потери данных. Система со сквозной записью проста, но время, требуемое для записи в основную память, снижает производительность и увеличивает количество обращений по шине (что особенно заметно | + | При обновлении кэш-памяти методом сквозной записи контроллер кэш-памяти одновременно обновляет содержимое основной памяти. Иначе говоря, основная память отражает текущее содержимое кэш-памяти. Быстрое обновление позволяет перезаписывать любой блок в кэш-памяти в любое время без потери данных. Система со сквозной записью проста, но время, требуемое для записи в основную память, снижает производительность и увеличивает количество обращений по шине (что особенно заметно с мультизадачной системе). |
'''Буферизованная сквозная запись.''' | '''Буферизованная сквозная запись.''' | ||
| Строка 439: | Строка 434: | ||
Такой структурой будет связный список маленьких массивов. А, чтобы эту структуру сделать cache-aware, нужно, чтобы каждый узел такого связного списка был размером B (т.е. размером со строку кэша). | Такой структурой будет связный список маленьких массивов. А, чтобы эту структуру сделать cache-aware, нужно, чтобы каждый узел такого связного списка был размером B (т.е. размером со строку кэша). | ||
| - | |||
| - | (Комментарий от Жукова В.В.: Пусть у нас есть список, элементы которого это int'ы. Объединяем их в массивы, например по 8192 штуки (размер int'a - 4 байта, 4 * 8192 = 32768 байт - размер L1-кэша на текущей машине). Например, мы захотели вставить один int в самое начало списка. Тогда нам придётся сдвигать весь первый массив на одну позицию, затем вставлять последний элемент этого массива в начало второго, проделать ту же процедуру со вторым массивом и т.д. В итоге получаем, что нам придётся пройти по всем массивам списка и перезаписать значения в элементах этого массива. Даже обычный длинный массив будет лучше, чем это: во-первых, при прохождении по массиву у нас всё-равно он кэшируется, во-вторых он лежит в последовательном участке памяти, в отличие от предложенных нескольких маленьких массивов, которые находятся в разных местах ОП, в-третьих нам не нужно разыменовывать указатель для перехода к следующему блоку, в-четвёртых, код алгоритма работы с одним массивом будет значительно короче. В общем, плохой пример.) | ||
=== Оптимизация сортировки слиянием === | === Оптимизация сортировки слиянием === | ||
| Строка 763: | Строка 756: | ||
= Метакомпъютинг. = | = Метакомпъютинг. = | ||
| - | GRID-сети | + | GRID-сети это совокупность вычислительных систем, связанных через Интернет (метакомпьютинг). Используются для решения задач, допускающих сегментацию на независимые вычислительные процессы с большим объемом вычислений. Такими задачами являются задача исследования генома, обработку результатов физических испытаний, проект CETI. |
Основная схема работы в этом случае примерно такая: специальный агент, расположенный на вычислительном узле (компьютере пользователя), определяет факт простоя этого компьютера, соединяется с управляющим узлом метакомпьютера и получает от него очередную порцию работы (область в пространстве перебора). По окончании счета по данной порции вычислительный узел передает обратно отчет о фактически проделанном переборе или сигнал о достижении цели поиска. | Основная схема работы в этом случае примерно такая: специальный агент, расположенный на вычислительном узле (компьютере пользователя), определяет факт простоя этого компьютера, соединяется с управляющим узлом метакомпьютера и получает от него очередную порцию работы (область в пространстве перебора). По окончании счета по данной порции вычислительный узел передает обратно отчет о фактически проделанном переборе или сигнал о достижении цели поиска. | ||
| Строка 916: | Строка 909: | ||
# Обработка векторных регулярных структур через механизмы потока данных менее эффективна, чем традиционные решения. | # Обработка векторных регулярных структур через механизмы потока данных менее эффективна, чем традиционные решения. | ||
# Языки программирования для потоковых машин существуют, в основном, в виде графических языков машинного уровня. Языки типа SISAL, ориентируемые на описания потоковых алгоритмов, достаточно сложны для программистов. | # Языки программирования для потоковых машин существуют, в основном, в виде графических языков машинного уровня. Языки типа SISAL, ориентируемые на описания потоковых алгоритмов, достаточно сложны для программистов. | ||
| - | |||
| - | Для тех, кто тоже не понял этот поток сознания: статья на Хабрахабре [http://habrahabr.ru/post/122479/ «Dataflow-архитектуры. Часть 1»]. | ||
= Нейронные сети как вычислители. = | = Нейронные сети как вычислители. = | ||
| Строка 1635: | Строка 1626: | ||
С фиксированной запятой числа изображаются в виде последовательности цифр с постоянным для всех чисел положением запятой, отделяющей целую часть от дробной. Например, 32,54; 0,0036; –108,2. Эта форма проста, естественна, но имеет небольшой диапазон представления чисел и поэтому не всегда приемлема при вычислениях. Если в результате операции получится число, выходящее за допустимый диапазон, происходит переполнение разрядной сетки и дальнейшие вычисления теряют смысл. В современных компьютерах форма представления чисел с фиксированной запятой используется только для целых чисел. | С фиксированной запятой числа изображаются в виде последовательности цифр с постоянным для всех чисел положением запятой, отделяющей целую часть от дробной. Например, 32,54; 0,0036; –108,2. Эта форма проста, естественна, но имеет небольшой диапазон представления чисел и поэтому не всегда приемлема при вычислениях. Если в результате операции получится число, выходящее за допустимый диапазон, происходит переполнение разрядной сетки и дальнейшие вычисления теряют смысл. В современных компьютерах форма представления чисел с фиксированной запятой используется только для целых чисел. | ||
| - | С плавающей запятой числа изображаются в виде X = ±M×P±r, где M - мантисса числа (правильная дробь в пределах 0,1 ≤ M < 1), r - порядок числа (целое), P - основание системы счисления. Например, приведенные выше числа с фиксированной запятой можно преобразовать в числа с плавающей запятой так: 0, | + | С плавающей запятой числа изображаются в виде X = ±M×P±r, где M - мантисса числа (правильная дробь в пределах 0,1 ≤ M < 1), r - порядок числа (целое), P - основание системы счисления. Например, приведенные выше числа с фиксированной запятой можно преобразовать в числа с плавающей запятой так: 0,3254×102, 0,36×10–2, –0,1082×103. Нормализованная форма представления имеет огромный диапазон чисел и является основной в современных ЭВМ. |
Каждому двоичному числу можно поставить в соответствие несколько видов кодов. Существуют следующие коды двоичных чисел: | Каждому двоичному числу можно поставить в соответствие несколько видов кодов. Существуют следующие коды двоичных чисел: | ||
| Строка 1844: | Строка 1835: | ||
Y = B + E + C X = A + D + REG | Y = B + E + C X = A + D + REG | ||
Y = E + REG | Y = E + REG | ||
| - | + | ''' | |
| - | '''3. Разворачивание циклов''' | + | 3. Разворачивание циклов''' |
Разворачивание циклов (loop unrolling) - расписывание цикла последовательностью операторов присваивания: либо полностью, либо размножение тела цикла с некоторым коэффициентом (фактором) размножения. | Разворачивание циклов (loop unrolling) - расписывание цикла последовательностью операторов присваивания: либо полностью, либо размножение тела цикла с некоторым коэффициентом (фактором) размножения. | ||
Производится частичное или полное разворачивание цикла в последовательный участок кода. При частичном разворачивании используется так называемый фактор разворачивания (который можно задавать в директиве компилятору). | Производится частичное или полное разворачивание цикла в последовательный участок кода. При частичном разворачивании используется так называемый фактор разворачивания (который можно задавать в директиве компилятору). | ||
| Строка 1857: | Строка 1848: | ||
DO I=1,10 DO I=1,10,2 | DO I=1,10 DO I=1,10,2 | ||
S = S + A(I) S = S + A(I) | S = S + A(I) S = S + A(I) | ||
| - | ENDDO S1 = S1 + A( | + | ENDDO S1 = S1 + A(A+1) |
ENDDO | ENDDO | ||
S = S + S1 | S = S + S1 | ||
Здесь, суммирование проводится отдельно для четных и нечетных элементов с последующем сложением частных сумм. | Здесь, суммирование проводится отдельно для четных и нечетных элементов с последующем сложением частных сумм. | ||
| - | |||
| - | {{Курс ПОД (3 поток)}} | ||
