Редактирование: ПОД (3 поток), Ответы
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
ПРЕДУПРЕЖДЕНИЕ: Длина этой страницы составляет 322 килобайт. Страницы, размер которых приближается к 32 КБ или превышает это значение, могут неверно отображаться в некоторых браузерах. Пожалуйста, рассмотрите вариант разбиения страницы на меньшие части.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 341: | Строка 341: | ||
* Памяти N страниц. Существует битовая матрица NxN (изначально полностью обнулена). | * Памяти N страниц. Существует битовая матрица NxN (изначально полностью обнулена). | ||
* При каждом обращении к i-ой странице происходит присваивание 1 всем битам i-ой строки и 0 - всем битам i-ого столбца. | * При каждом обращении к i-ой странице происходит присваивание 1 всем битам i-ой строки и 0 - всем битам i-ого столбца. | ||
- | * Строка с наименьшим | + | * Строка с наименьшим двоичным кодом - искомая |
===Алгоритм NFU=== | ===Алгоритм NFU=== | ||
Строка 440: | Строка 440: | ||
Такой структурой будет связный список маленьких массивов. А, чтобы эту структуру сделать cache-aware, нужно, чтобы каждый узел такого связного списка был размером B (т.е. размером со строку кэша). | Такой структурой будет связный список маленьких массивов. А, чтобы эту структуру сделать cache-aware, нужно, чтобы каждый узел такого связного списка был размером B (т.е. размером со строку кэша). | ||
- | (Комментарий от Жукова В.В.: Пусть у нас есть список, элементы которого это int'ы. Объединяем их в массивы, например по 8192 штуки (размер int'a - 4 байта, 4 * 8192 = 32768 байт - размер L1-кэша на текущей машине). Например, мы захотели вставить один int в самое начало списка. Тогда нам придётся сдвигать весь первый массив на одну позицию, затем вставлять последний элемент этого массива в начало второго, проделать ту же процедуру со вторым массивом и т.д. В итоге получаем, что нам придётся пройти по всем массивам списка и перезаписать значения в элементах этого массива. Даже обычный длинный массив будет лучше, чем это: во-первых, при прохождении по массиву у нас всё-равно он кэшируется, во-вторых он лежит в последовательном участке памяти, в отличие от предложенных нескольких маленьких массивов, которые находятся в разных местах ОП, в-третьих нам не нужно разыменовывать указатель для перехода к следующему блоку, в-четвёртых, код алгоритма работы с одним массивом будет значительно короче. В общем, плохой пример.) | + | (Комментарий от Жукова В.В.: Пусть у нас есть список, элементы которого это int'ы. Объединяем их в массивы, например по 8192 штуки (размер int'a - 4 байта, 4 * 8192 = 32768 байт - размер L1-кэша на текущей машине). Например, мы захотели вставить один int в самое начало списка. Тогда нам придётся сдвигать весь первый массив на одну позицию, затем вставлять последний элемент этого массива в начало второго, проделать ту же процедуру со вторым массивом и т.д. В итоге получаем, что нам придётся пройти по всем массивам списка и перезаписать значения в элементах этого массива. Даже обычный длинный массив будет лучше, чем это: во-первых, при прохождении по массиву у нас всё-равно он кэшируется, во-вторых он лежит в последовательном участке памяти, в отличие от предложенных нескольких маленьких массивов, которые находятся в разных местах ОП, в-третьих нам не нужно разыменовывать указатель для перехода к следующему блоку, в-четвёртых, код алгоритма работы с одним массивом будет значительно короче. В общем, плохой пример cache-aware алгоритма.) |
=== Оптимизация сортировки слиянием === | === Оптимизация сортировки слиянием === | ||
Строка 763: | Строка 763: | ||
= Метакомпъютинг. = | = Метакомпъютинг. = | ||
- | GRID-сети | + | GRID-сети это совокупность вычислительных систем, связанных через Интернет (метакомпьютинг). Используются для решения задач, допускающих сегментацию на независимые вычислительные процессы с большим объемом вычислений. Такими задачами являются задача исследования генома, обработку результатов физических испытаний, проект CETI. |
Основная схема работы в этом случае примерно такая: специальный агент, расположенный на вычислительном узле (компьютере пользователя), определяет факт простоя этого компьютера, соединяется с управляющим узлом метакомпьютера и получает от него очередную порцию работы (область в пространстве перебора). По окончании счета по данной порции вычислительный узел передает обратно отчет о фактически проделанном переборе или сигнал о достижении цели поиска. | Основная схема работы в этом случае примерно такая: специальный агент, расположенный на вычислительном узле (компьютере пользователя), определяет факт простоя этого компьютера, соединяется с управляющим узлом метакомпьютера и получает от него очередную порцию работы (область в пространстве перебора). По окончании счета по данной порции вычислительный узел передает обратно отчет о фактически проделанном переборе или сигнал о достижении цели поиска. | ||
Строка 916: | Строка 916: | ||
# Обработка векторных регулярных структур через механизмы потока данных менее эффективна, чем традиционные решения. | # Обработка векторных регулярных структур через механизмы потока данных менее эффективна, чем традиционные решения. | ||
# Языки программирования для потоковых машин существуют, в основном, в виде графических языков машинного уровня. Языки типа SISAL, ориентируемые на описания потоковых алгоритмов, достаточно сложны для программистов. | # Языки программирования для потоковых машин существуют, в основном, в виде графических языков машинного уровня. Языки типа SISAL, ориентируемые на описания потоковых алгоритмов, достаточно сложны для программистов. | ||
- | |||
- | Для тех, кто тоже не понял этот поток сознания: статья на Хабрахабре [http://habrahabr.ru/post/122479/ «Dataflow-архитектуры. Часть 1»]. | ||
= Нейронные сети как вычислители. = | = Нейронные сети как вычислители. = |