Я писал об этом выше.
При вставке индекса или увеличении размеров данных существующего, если данные не помещаются в имеющийся блок, то в цепочку блоков вставляется свободный. Затрагивается минимум блоков и ссылок на них. При интенсивной вставке база становится рыхлой, но на производительность это почти не влияет.
Адрес первого блока глобалы и её имя хранятся в главной системной глобале. В первом блоке записываются Значение глобалы, первичные (затем вторичные и т.д.) индексы и значения первичных (вторичных) индексов. В конце блока ссылка на продолжение текущего блока. Индексация производится во время записи нового индекса. Ищется место вставки и записывается новое значение. Блоки разбиты на страницы (насколько помню, по 400 блоков). Длина линейной записи ограничена. Когда заканчивается место, строится второй слой первичных индексов. Для этого в качестве первого блока берётся блок-указатель первого уровня. В него помещаются первый индекс из уже заполненного и вводится ссылка на его расположение в исходной записи. Блок первого уровня может ссылаться на Х (~ 50-100 точно не помню) блоков нулевого уровня. Они продолжают создаваться. Когда заполняется второй блок нулевого уровня, в блоке первого создаётся индекс и ссылка на следующий. Когда полностью заполнится запись первого уровня, создаётся запись второго уровня, которая ссылается уже на записи первого уровня и так далее. Таким образом строится сбалансированное индексированное дерево. Поиск в нём очень быстрый как для чтения, так и для вставки новых индексов. Начинается с блока самого высокого уровня. Адресуется на блок нижнего уровня и до конца. Часто читаемые блоки хранятся в кэше дольше и их не надо повторно считывать с диска.
Данные в базе упакованы плотно, длина записей всегда равна длине данных. Не хранятся лишние пробелы, выравнивающие записи как в других базах. Это тоже увеличивает скорость чтения с диска.
Вообще вся структура ДИАМСа (MSM) иерархична и итерационна. Всё ядро ОС занимало 256 килобайт вместе с драйверами. Графики там не было.
А почему бы ПП не скорректировать проходимым маршрутом? Тогда поиск пути не надо будет пересчитывать для каждого юнита.
Или изначально строить ПП вдоль поиска пути. Для статических карт это будет не очень затратно. И локальных минимумов можно будет избежать.
Ещё можно предусмотреть влияние вражеских юнитов только на клетках без препятствий.
А сам язык программирования удивительно гибок и компактен. Программа экранного редактора программ (в комплекте не было) занимала у меня 15-20 строк текста с возможностью запоминать и вставлять фрагменты, сохранять и загружать текст программы.
Механизм Т9 в ДИАМСе работал мгновенно, тогда как попытка реализации подобного механизма в FOXPRO при базе в 800 человек на каждое изменение вводимого текста мог тормозить на 2 сек. — полный циклический перебор всех индексов.
В 1987-90 годах я работал и преподавал систему ДИАМС, построенную на глобалах.
Я досконально изучал структуру физических блоков хранения глобал на диске.
Вся фишка огромной скорости выборки и записи на диск заключается в чтении или изменении и записи отдельных 512 байтовых блоков. ЛЮБАЯ информация по индексам из базы десятки гигабайт извлекается чтением максимум пяти фрагментов с диска. При записи происходит отложенная запись на диск ТОЛЬКО изменённых блоков.
Есть блоки разной иерархии. В них есть ссылки на линейные блоки или на следующий уровень, если база большая. Корневой блок глобалы может ссылаться на вторичные, те на третий уровень и т.д. до 5. Индексы и значения лежат линейно в блоке в текстовом виде, но они отсортированы. Если не хватает места для данных в одном блоке, берётся другой свободный и в нём прописывается тот, который был следующим. При интенсивной вставке/удалении данных база становится рыхлой. Блоки могут быть полупустыми, но есть специальные механизмы, которые дефрагментируют базу во время простоя или по заданию. При приведённом выше тестовом задании все операции произошли в буфере в ОЗУ и один раз записались на диск, поэтому такая скорость. Если бы индексы формировались случайные, скорость была бы ниже, но незначительно.
Я изучил систему команд процессора, но остались непонятны некоторые моменты.
1. Команды с двумя операндами. Результат операции может быть только в буфере команды или в РОН? Могут ли две или более клеток в одном такте добавить к РОН свои слагаемые?
2. Что произойдёт, если операнд будет @0?
3. Команды условных и безусловного переходов могут работать только внутри параграфа или каким-то образом могут задать другой параграф?
4. Сколько тактов потребуется, чтобы подгрузить в буфер или кэш массив из памяти, например, 128 64-битных элемента.
5. Вопрос по окну видимости. Для 4 клеток 260 команда параграфа попадает в первый такт(вторая строка буфера команд) в нулевую клетку? Если она обращается к @8, операнд берётся от команды из 63 такта нулевой клетки?
Оказывается, всё совсем не так, как я предполагал. Получается, что у каждой клетки свой буфер команд и в буферах разных клеток разные команды. Раздача команд клеткам ПРИНУДИТЕЛЬНАЯ. Тогда общий буфер команд четырёх клеток имеет максимальный объём 64*4=256 команд?
В этом случае моя идея не проходит или требует серьёзного пересмотра.
Я то думал, что каждая клетка асинхронно из общего буфера выбирает готовую к исполнению команду (не обязательно по порядку) и выполняет её. При этом компилятору не надо просчитывать какую команду за какой оптимально располагать. Пример параграфа программы из п.2 — это пример НЕОПТИМАЛЬНОГО компилятора или просто вручную написанные команды. Это меня и смутило.
По моему разумению содержимое диаграммы должно выглядеть так:
Такт Cell0 Cell1 Cell2 Cell3
1 get a get b get c get e
2 add @3, @2 sub @5, @3 get f — 3 mul @3, @2 — --- mul @4, @3
4 — add @2,@1 — ---
5 — --- mv g,@1
В предыдущем комментарии (18 мая 2015 в 22:19) я описал.
Наверно, мы разные рисунки смотрим. Я имею в виду Рис 2. Распределение команд по клеткам из этой статьи и последовательность команд в буфере чуть выше рисунка.
Про более сложные и энергоёмкие процессоры с предвыборкой и предсказаниями согласен. Но пересчитаем такты снова.
404 такта Неймановский процессор
106 тактов одна четвёртая часть мультиклеточного процессора
Выигрыш во времени в 4 раза (в среднем ОДНОЙ клеткой) При этом остальные клетки могут выполнить такой же объём вычислений ещё три раза в пределах этого же промежутка времени.
Я для расчёта принял, что будем затрачивать один такт на выборку из памяти. Если учесть предвыборку памяти, то картинка становится ещё привлекательней. Четыре клетки за один такт загрузят 4 элемента массива. Тогда на загрузку ВСЕГО массива потребуется 25 тактов и формула будет выглядеть так: 4+(25+24 на суммирование)+7= 60 тактов. При этом варианте клетки будут загружены на 35%-40%.
60 тактов против 404 серьёзная заявка.
24 такта добавлены для использования уже загруженных данных. Клетки не могут загружать новые данные, они должны сначала просуммировать загруженные.
Начал анализировать рисунок 2. У меня возникла логическая нестыковка. Я чего-то не понял.
1. Из буфера команд клетка может взять на исполнение ЛЮБУЮ команду, для которой готовы источники и есть команда — приёмник данных? Не обязательно по порядку расположения в буфере? Тогда для третьей клетки на первом такте подходит команда с тегом 4. Для команды с тегом 3 данные ещё не готовы.
2. После выполнения команды её результат фиксируется в регистре-защёлке буфера команд или висит на выходе АЛУ, пока его не прочитают?
Судя по тому, что я понял из описания работы процессора, клетка не может выполнять команду в течение 2 или 3 тактов, если только сама операция не занимает столько времени. Клетка просто НЕ ДОЛЖНА начинать исполнять команду, для которой не готовы данные.
В первом такте заняты все клетки, во втором такте одна клетка не задействована, в третьем такте уже две клетки не задействованы, в четвёртом и пятом тактах работают по одной клетке. Незадействованные клетки в эти моменты могут выполнять другие команды из этого параграфа.
Поправьте меня, если я неправ.
Программа не покажет, как её будет выполнять мультиклеточный процессор. А выигрыш можно показать на пальцах.Суммируем массив из 100 элементов:
1 Выборка команды
2 Установка счётчика в 100
3 Выборка команды
4 Обнуление суммы
5 Выборка команды
6 Выборка начального адреса
7 Выборка команды
8 Выборка элемента
9 Выборка команды
10 Суммирование
11 Выборка команды
12 Декремент счётчика
13 Выборка команды
14 Проверка счётчика и переход
Каждый пункт примем за 1 такт. Пункты 7-14 повторяются 100 раз. Итого 806 тактов.
Теперь рассмотрим работу мультиклеточного процессора. Тоже грубо.
1 Выборка команды Выборка начального адреса
2 Выборка команды Выборка конечного адреса и Выборка начального адреса
3 Выборка команды суммирования массива и Выборка конечного адреса
4 Размножение команды суммирования
Теперь все действия выполняются параллельно четырьмя клетками. Команды перемежаются по мере готовности предыдущих сумм.
100 тактов выборки элементов массива, 50 попарных суммирований элементов массива четырьмя клетками — 13 тактов 25 попарных суммирований предыдущих сумм четырьмя клетками — 7 тактов, 13 попарных суммирований предыдущих сумм четырьмя клетками — 4 такта, 7 попарных суммирований предыдущих сумм четырьмя клетками — 2 такта и ещё 1 такт на получение окончательной суммы.
Таким образом имеем 4+100+2=106 тактов затраченного времени и 300 тактов для выполнения других команд.
Выигрыш примерно в 8 раз во времени при использовании ~ 25% ресурса процессора.
Не ругайте меня за большой текст.
Контроль передачи управления остаётся мультиклеточный — по готовности источника и приёмника. Клетки сами будут выбирать, готова ли команда к исполнению. Просто на момент обработки массива буфер перестанет пополняться новыми командами из программной памяти, а имеющиеся будут повторяться, пока имеют этот признак повторить. (См. ответ на комментарий ниже)
Логику ядра для такого рода команд я уже начал продумывать. Но это всё надо согласовывать с существующей логикой, чем я, к сожалению, пока ещё не владею. А польза будет ощутимая. Команды не надо будет перезагружать, только менять у них аргументы, оставляя в буфере в той же последовательности. Только на начальном этапе надо будет в буфере разместить копии этих команд в количестве клеток группы, которые заняты в этом процессе. Так как работа выполняется над массивом, его адрес (адрес памяти) присутствует в ядре процессора, его надо увеличить или уменьшить и использовать. Аппаратно в ядро процессора необходимо будет добавить компаратор конечного адреса массива. Но что-то мне подсказывает, что необходимая структура уже есть, остаётся только использовать с неё сигнал для окончания дублирования команд. Пока ещё ничего не придумал для нечётной границы массива. Возможно, придётся подставлять фиктивный аргумент, но лучше провалить этот элемент массива к заключительной команде, как результат. Естественно, в буфере команд надо будет добавить индикатор мультикоманды. Ещё уточнение: дублировать или повторять команды в буфере с изменением аргументов надо будет только те, которые считывают аргументы из памяти. Те команды, которые используют их результаты достаточно только повторять.
Большая дорога начинается с первого шага. Если несколько команд будут работать с массивами параллельно, то уже будет большой выигрыш в производительности. А обычные циклы никто отменять не будет.
P.S. Три экземпляра текста меня тоже удивили. Это вопрос к разработчикам сайта.
При вставке индекса или увеличении размеров данных существующего, если данные не помещаются в имеющийся блок, то в цепочку блоков вставляется свободный. Затрагивается минимум блоков и ссылок на них. При интенсивной вставке база становится рыхлой, но на производительность это почти не влияет.
Адрес первого блока глобалы и её имя хранятся в главной системной глобале. В первом блоке записываются Значение глобалы, первичные (затем вторичные и т.д.) индексы и значения первичных (вторичных) индексов. В конце блока ссылка на продолжение текущего блока. Индексация производится во время записи нового индекса. Ищется место вставки и записывается новое значение. Блоки разбиты на страницы (насколько помню, по 400 блоков). Длина линейной записи ограничена. Когда заканчивается место, строится второй слой первичных индексов. Для этого в качестве первого блока берётся блок-указатель первого уровня. В него помещаются первый индекс из уже заполненного и вводится ссылка на его расположение в исходной записи. Блок первого уровня может ссылаться на Х (~ 50-100 точно не помню) блоков нулевого уровня. Они продолжают создаваться. Когда заполняется второй блок нулевого уровня, в блоке первого создаётся индекс и ссылка на следующий. Когда полностью заполнится запись первого уровня, создаётся запись второго уровня, которая ссылается уже на записи первого уровня и так далее. Таким образом строится сбалансированное индексированное дерево. Поиск в нём очень быстрый как для чтения, так и для вставки новых индексов. Начинается с блока самого высокого уровня. Адресуется на блок нижнего уровня и до конца. Часто читаемые блоки хранятся в кэше дольше и их не надо повторно считывать с диска.
Данные в базе упакованы плотно, длина записей всегда равна длине данных. Не хранятся лишние пробелы, выравнивающие записи как в других базах. Это тоже увеличивает скорость чтения с диска.
Вообще вся структура ДИАМСа (MSM) иерархична и итерационна. Всё ядро ОС занимало 256 килобайт вместе с драйверами. Графики там не было.
Или изначально строить ПП вдоль поиска пути. Для статических карт это будет не очень затратно. И локальных минимумов можно будет избежать.
Ещё можно предусмотреть влияние вражеских юнитов только на клетках без препятствий.
Механизм Т9 в ДИАМСе работал мгновенно, тогда как попытка реализации подобного механизма в FOXPRO при базе в 800 человек на каждое изменение вводимого текста мог тормозить на 2 сек. — полный циклический перебор всех индексов.
Я досконально изучал структуру физических блоков хранения глобал на диске.
Вся фишка огромной скорости выборки и записи на диск заключается в чтении или изменении и записи отдельных 512 байтовых блоков. ЛЮБАЯ информация по индексам из базы десятки гигабайт извлекается чтением максимум пяти фрагментов с диска. При записи происходит отложенная запись на диск ТОЛЬКО изменённых блоков.
Есть блоки разной иерархии. В них есть ссылки на линейные блоки или на следующий уровень, если база большая. Корневой блок глобалы может ссылаться на вторичные, те на третий уровень и т.д. до 5. Индексы и значения лежат линейно в блоке в текстовом виде, но они отсортированы. Если не хватает места для данных в одном блоке, берётся другой свободный и в нём прописывается тот, который был следующим. При интенсивной вставке/удалении данных база становится рыхлой. Блоки могут быть полупустыми, но есть специальные механизмы, которые дефрагментируют базу во время простоя или по заданию. При приведённом выше тестовом задании все операции произошли в буфере в ОЗУ и один раз записались на диск, поэтому такая скорость. Если бы индексы формировались случайные, скорость была бы ниже, но незначительно.
1. Команды с двумя операндами. Результат операции может быть только в буфере команды или в РОН? Могут ли две или более клеток в одном такте добавить к РОН свои слагаемые?
2. Что произойдёт, если операнд будет @0?
3. Команды условных и безусловного переходов могут работать только внутри параграфа или каким-то образом могут задать другой параграф?
4. Сколько тактов потребуется, чтобы подгрузить в буфер или кэш массив из памяти, например, 128 64-битных элемента.
5. Вопрос по окну видимости. Для 4 клеток 260 команда параграфа попадает в первый такт(вторая строка буфера команд) в нулевую клетку? Если она обращается к @8, операнд берётся от команды из 63 такта нулевой клетки?
В этом случае моя идея не проходит или требует серьёзного пересмотра.
Я то думал, что каждая клетка асинхронно из общего буфера выбирает готовую к исполнению команду (не обязательно по порядку) и выполняет её. При этом компилятору не надо просчитывать какую команду за какой оптимально располагать. Пример параграфа программы из п.2 — это пример НЕОПТИМАЛЬНОГО компилятора или просто вручную написанные команды. Это меня и смутило.
Такт Cell0 Cell1 Cell2 Cell3
1 get a get b get c get e
2 add @3, @2 sub @5, @3 get f — 3 mul @3, @2 — --- mul @4, @3
4 — add @2,@1 — ---
5 — --- mv g,@1
В предыдущем комментарии (18 мая 2015 в 22:19) я описал.
404 такта Неймановский процессор
106 тактов одна четвёртая часть мультиклеточного процессора
Выигрыш во времени в 4 раза (в среднем ОДНОЙ клеткой) При этом остальные клетки могут выполнить такой же объём вычислений ещё три раза в пределах этого же промежутка времени.
Я для расчёта принял, что будем затрачивать один такт на выборку из памяти. Если учесть предвыборку памяти, то картинка становится ещё привлекательней. Четыре клетки за один такт загрузят 4 элемента массива. Тогда на загрузку ВСЕГО массива потребуется 25 тактов и формула будет выглядеть так: 4+(25+24 на суммирование)+7= 60 тактов. При этом варианте клетки будут загружены на 35%-40%.
60 тактов против 404 серьёзная заявка.
24 такта добавлены для использования уже загруженных данных. Клетки не могут загружать новые данные, они должны сначала просуммировать загруженные.
1. Из буфера команд клетка может взять на исполнение ЛЮБУЮ команду, для которой готовы источники и есть команда — приёмник данных? Не обязательно по порядку расположения в буфере? Тогда для третьей клетки на первом такте подходит команда с тегом 4. Для команды с тегом 3 данные ещё не готовы.
2. После выполнения команды её результат фиксируется в регистре-защёлке буфера команд или висит на выходе АЛУ, пока его не прочитают?
Судя по тому, что я понял из описания работы процессора, клетка не может выполнять команду в течение 2 или 3 тактов, если только сама операция не занимает столько времени. Клетка просто НЕ ДОЛЖНА начинать исполнять команду, для которой не готовы данные.
В первом такте заняты все клетки, во втором такте одна клетка не задействована, в третьем такте уже две клетки не задействованы, в четвёртом и пятом тактах работают по одной клетке. Незадействованные клетки в эти моменты могут выполнять другие команды из этого параграфа.
Поправьте меня, если я неправ.
1 Выборка команды
2 Установка счётчика в 100
3 Выборка команды
4 Обнуление суммы
5 Выборка команды
6 Выборка начального адреса
7 Выборка команды
8 Выборка элемента
9 Выборка команды
10 Суммирование
11 Выборка команды
12 Декремент счётчика
13 Выборка команды
14 Проверка счётчика и переход
Каждый пункт примем за 1 такт. Пункты 7-14 повторяются 100 раз. Итого 806 тактов.
Теперь рассмотрим работу мультиклеточного процессора. Тоже грубо.
1 Выборка команды Выборка начального адреса
2 Выборка команды Выборка конечного адреса и Выборка начального адреса
3 Выборка команды суммирования массива и Выборка конечного адреса
4 Размножение команды суммирования
Теперь все действия выполняются параллельно четырьмя клетками. Команды перемежаются по мере готовности предыдущих сумм.
100 тактов выборки элементов массива, 50 попарных суммирований элементов массива четырьмя клетками — 13 тактов 25 попарных суммирований предыдущих сумм четырьмя клетками — 7 тактов, 13 попарных суммирований предыдущих сумм четырьмя клетками — 4 такта, 7 попарных суммирований предыдущих сумм четырьмя клетками — 2 такта и ещё 1 такт на получение окончательной суммы.
Таким образом имеем 4+100+2=106 тактов затраченного времени и 300 тактов для выполнения других команд.
Выигрыш примерно в 8 раз во времени при использовании ~ 25% ресурса процессора.
Не ругайте меня за большой текст.
P.S. Три экземпляра текста меня тоже удивили. Это вопрос к разработчикам сайта.