Редактирование: ПОД (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:Автокод#Происхождение и критика термина «язык ассемблера»|Автокод]]). |
===Второе поколение=== | ===Второе поколение=== | ||
Строка 264: | Строка 264: | ||
'''Ответ:''' Область памяти делим ровно пополам. Первая половина заполняется ключами, вторая соответствующими ключам значениями. Когда найден ключ, известен его адрес как смещение относительно начала памяти. Тогда адрес содержимого по ключу – это смещение + размер области ключей, то есть адрес ячейки из второй половины памяти, которая соответствует ключу. ''А не имеется ли тут в виду реализация hash или индексных деревьев?'' | '''Ответ:''' Область памяти делим ровно пополам. Первая половина заполняется ключами, вторая соответствующими ключам значениями. Когда найден ключ, известен его адрес как смещение относительно начала памяти. Тогда адрес содержимого по ключу – это смещение + размер области ключей, то есть адрес ячейки из второй половины памяти, которая соответствует ключу. ''А не имеется ли тут в виду реализация hash или индексных деревьев?'' | ||
- | |||
- | '''Ответ-2''': Предположим, у нас очень много оперативной памяти. Тогда рассмотрим ключ, как двоичную последовательность, то есть, это некое число. Рассмотрим это число, как адрес в памяти - там и будем хранить и искать значение, соответствующее данному ключу. | ||
= Виртуальная память. = | = Виртуальная память. = | ||
Внутри программы к моменту образования исполняемого модуля используется модель организации адресного пространства программы (эта модель, в общем случае не связана с теми ресурсами ОЗУ, которые предполагается использовать позднее). Для простоты будем считать, что данная модель представляет собой непрерывный фрагмент адресного пространства в пределах которого размещены данные и команды программы. Будем называть подобную организацию адресации в программе программной адресацией или '''логической/виртуальной адресацией'''. | Внутри программы к моменту образования исполняемого модуля используется модель организации адресного пространства программы (эта модель, в общем случае не связана с теми ресурсами ОЗУ, которые предполагается использовать позднее). Для простоты будем считать, что данная модель представляет собой непрерывный фрагмент адресного пространства в пределах которого размещены данные и команды программы. Будем называть подобную организацию адресации в программе программной адресацией или '''логической/виртуальной адресацией'''. | ||
- | Итак, повторяем, на уровне исполняемого кода имеется программа в машинных кодах, использующая адреса данных и команд. Эти адреса в общем случае не являются адресами конкретных физических ячеек памяти, в которых размещены эти данные, более того, | + | Итак, повторяем, на уровне исполняемого кода имеется программа в машинных кодах, использующая адреса данных и команд. Эти адреса в общем случае не являются адресами конкретных физических ячеек памяти, в которых размещены эти данные, более того, в последствии мы увидим, что виртуальным (или программным) адресам могут ставиться в соответствие произвольные физические адреса памяти. То есть при реальном исполнении программы далеко не всегда виртуальная адресация, используемая в программе совпадает с физической адресацией, используемой ЦП при выполнении данной программы. |
===Базирование адресов.=== | ===Базирование адресов.=== | ||
Строка 331: | Строка 329: | ||
===Алгоритм «Часы»=== | ===Алгоритм «Часы»=== | ||
- | ''(Это то же самое, что и алгоритм вторая попытка)'' | ||
#Если R=0, то выгрузка страницы и стрелка на позицию вправо. | #Если R=0, то выгрузка страницы и стрелка на позицию вправо. | ||
#Если R=1, то R-обнуляется, стрелка на позицию вправо и на П.1. | #Если R=1, то R-обнуляется, стрелка на позицию вправо и на П.1. | ||
Строка 341: | Строка 338: | ||
* Памяти N страниц. Существует битовая матрица NxN (изначально полностью обнулена). | * Памяти N страниц. Существует битовая матрица NxN (изначально полностью обнулена). | ||
* При каждом обращении к i-ой странице происходит присваивание 1 всем битам i-ой строки и 0 - всем битам i-ого столбца. | * При каждом обращении к i-ой странице происходит присваивание 1 всем битам i-ой строки и 0 - всем битам i-ого столбца. | ||
- | * Строка с наименьшим | + | * Строка с наименьшим двоичным кодом - искомая |
===Алгоритм NFU=== | ===Алгоритм NFU=== | ||
Строка 439: | Строка 436: | ||
Такой структурой будет связный список маленьких массивов. А, чтобы эту структуру сделать cache-aware, нужно, чтобы каждый узел такого связного списка был размером B (т.е. размером со строку кэша). | Такой структурой будет связный список маленьких массивов. А, чтобы эту структуру сделать cache-aware, нужно, чтобы каждый узел такого связного списка был размером B (т.е. размером со строку кэша). | ||
- | |||
- | (Комментарий от Жукова В.В.: Пусть у нас есть список, элементы которого это int'ы. Объединяем их в массивы, например по 8192 штуки (размер int'a - 4 байта, 4 * 8192 = 32768 байт - размер L1-кэша на текущей машине). Например, мы захотели вставить один int в самое начало списка. Тогда нам придётся сдвигать весь первый массив на одну позицию, затем вставлять последний элемент этого массива в начало второго, проделать ту же процедуру со вторым массивом и т.д. В итоге получаем, что нам придётся пройти по всем массивам списка и перезаписать значения в элементах этого массива. Даже обычный длинный массив будет лучше, чем это: во-первых, при прохождении по массиву у нас всё-равно он кэшируется, во-вторых он лежит в последовательном участке памяти, в отличие от предложенных нескольких маленьких массивов, которые находятся в разных местах ОП, в-третьих нам не нужно разыменовывать указатель для перехода к следующему блоку, в-четвёртых, код алгоритма работы с одним массивом будет значительно короче. В общем, плохой пример.) | ||
=== Оптимизация сортировки слиянием === | === Оптимизация сортировки слиянием === | ||
Строка 763: | Строка 758: | ||
= Метакомпъютинг. = | = Метакомпъютинг. = | ||
- | GRID-сети | + | GRID-сети это совокупность вычислительных систем, связанных через Интернет (метакомпьютинг). Используются для решения задач, допускающих сегментацию на независимые вычислительные процессы с большим объемом вычислений. Такими задачами являются задача исследования генома, обработку результатов физических испытаний, проект CETI. |
Основная схема работы в этом случае примерно такая: специальный агент, расположенный на вычислительном узле (компьютере пользователя), определяет факт простоя этого компьютера, соединяется с управляющим узлом метакомпьютера и получает от него очередную порцию работы (область в пространстве перебора). По окончании счета по данной порции вычислительный узел передает обратно отчет о фактически проделанном переборе или сигнал о достижении цели поиска. | Основная схема работы в этом случае примерно такая: специальный агент, расположенный на вычислительном узле (компьютере пользователя), определяет факт простоя этого компьютера, соединяется с управляющим узлом метакомпьютера и получает от него очередную порцию работы (область в пространстве перебора). По окончании счета по данной порции вычислительный узел передает обратно отчет о фактически проделанном переборе или сигнал о достижении цели поиска. | ||
Строка 916: | Строка 911: | ||
# Обработка векторных регулярных структур через механизмы потока данных менее эффективна, чем традиционные решения. | # Обработка векторных регулярных структур через механизмы потока данных менее эффективна, чем традиционные решения. | ||
# Языки программирования для потоковых машин существуют, в основном, в виде графических языков машинного уровня. Языки типа SISAL, ориентируемые на описания потоковых алгоритмов, достаточно сложны для программистов. | # Языки программирования для потоковых машин существуют, в основном, в виде графических языков машинного уровня. Языки типа SISAL, ориентируемые на описания потоковых алгоритмов, достаточно сложны для программистов. | ||
- | |||
- | Для тех, кто тоже не понял этот поток сознания: статья на Хабрахабре [http://habrahabr.ru/post/122479/ «Dataflow-архитектуры. Часть 1»]. | ||
= Нейронные сети как вычислители. = | = Нейронные сети как вычислители. = | ||
Строка 1635: | Строка 1628: | ||
С фиксированной запятой числа изображаются в виде последовательности цифр с постоянным для всех чисел положением запятой, отделяющей целую часть от дробной. Например, 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. Нормализованная форма представления имеет огромный диапазон чисел и является основной в современных ЭВМ. |
Каждому двоичному числу можно поставить в соответствие несколько видов кодов. Существуют следующие коды двоичных чисел: | Каждому двоичному числу можно поставить в соответствие несколько видов кодов. Существуют следующие коды двоичных чисел: |