Синхронизация кешей процессоров

[bondkim137]

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

Собственно, есть два процессора. Есть общая оперативная память. У каждого из процессоров есть собственная кеш-память, кеширующая как чтение, так и запись. Какие правила стоит (принято) накладывать на работу собственной кеш-памяти, что б все не накрылось медным тазом?

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

Если кто-нибудь имеет опыт в этой области, киньте парой ссылок, пожалуйста.
Мои знания в организации кешей процессорных систем (использование сквозного буфера записи вместо кеша и т.д.) устарели почти на десять лет.

[Dmitriy40]

10 лет? Так протоколы поддержания когерентности кэшей были разработаны ранее, так что Вы о них в курсе (там по ссылкам в английскую вики сильно больше полезной инфы). Насколько помню, тупо наблюдение за обращениями в общую память и блокировка цикла шины если кто-то обращается за данными, которые у меня в кэше модифицированы. Блокировка до момента сброса моих данных в память (возможно даже прямо в этом же цикле шины одновременно и запрашивающему). Остальное - оптимизации. Т.е. реализация чисто аппаратная, сделать её программной надо извращаться и это уже не будет платформеннонезависимо (понадобятся или атомарные команды типа cmpxchg или префиксы блокировки цикла шины или указание аппаратуре на некэшируемость переменной). Хотя возможно ОС поддерживает выделение памяти в гарантированно некэшируемой области, тогда туда помещаете как минимум флаг (семафор, мютекс, и т.д.), остальное реализуется классическими способами. Совсем без поддержки аппаратуры вроде бы не сделать (ну если только не обмениваться сигналами через сильно внешнее устройство, которое опять же гарантированно не кэшируется).
Извините если это известные Вам банальности, но мне кажется ничего кардинально лучшего не придумано ...

[bondkim137]

Ок, уточню - не только устарели, но и были весьма неполными, особенно в контексте многопроцессорных систем
Извращаться с атомарными инструкциями мне не надо, у меня высокоуровневая задача, софтовая. Просто очень похожая на ситуацию с процессорами, не более. Только вместо ядер ЦПУ - отдельные сервера, вместо кеша - их собственная память, в т.ч. диск, вместо общей памяти - большое общее хранилище, тоже распределенное.
Weak/Release consistency из вашей ссылки может пригодиться, спасибо.

[Dmitriy40]

Если не существует метода сброса информации из локальной памяти в общую или обмена сигналами/сообщениями, то по моему задача неразрешима (система легко может попасть в stalled состояние взаимного ожидания). Если же существует, то непонятно чем не устраивают стандартные средства типа семафоров/мютексов/прочие барьеры выполнения. Впрочем глубоко я не копал, Вам виднее.

[Pavia]

Учите теорию транзакций СУБД. Если вы овладеете терминологией, то опишете задачу в трёх словах.

Блокировка данных может проходить на 4 уровнях: базы данных, таблицы, элемента и физическом уровне.

Вместо синхронизации используется непроватеречивость данных. Она достигается тем, что транзакция неделимая операция, вернее если по завершению работы было выявлен конфликт. То транзакция откатывается на начальное положение. Факт конфликта вычисляется по версионным либо временным меткам. - в кэше этого нет.

Система транзакций может быть гибко настроенна или спланирована так что-бы откат не повторялся более 1 раза. Зато нам ненужно будет делать блокировоки для общих данных. Что в глобальном счёте приводит к ускорению в разы.

bondkim137 в сообщении #1334960 писал(а):

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

Нашли из-за чего горевать. Вот если бы был один блок, то тогда запросы надо было бы объединять в серии. Write combine sequences.

-- Вт авг 28, 2018 19:18:00 --

Dmitriy40 в сообщении #1335062 писал(а):

Если не существует метода сброса информации из локальной памяти в общую или обмена сигналами/сообщениями, то по моему задача неразрешима (система легко может попасть в stalled состояние взаимного ожидания)

Элементарно решается секвенстированием, как на первых процессорах/микроконтроллерах.

[Dmitriy40]

Pavia в сообщении #1335105 писал(а):

Элементарно решается секвенстированием, как на первых процессорах/микроконтроллерах.

Можете капельку подробнее сказать? А то как и что ни запрещай, но если запрет так и останется в локальном кэше и не попадёт в общую память, то остальные вычислители или его не увидят и используют недействительное значение семафора, или будут вечно ждать снятия запрета. В первых процессорах была (и осталась) аппаратная поддержка атомарных операций или инвалидация кэша или не было write back кэша, чисто софтово write back кэш не обходится (хотя, если аккуратно прочитать данных больше объёма кэша, то он вынужденно сбросится на верхний уровень ... можно ли это считать чисто софтовым решением я в сомнениях, да и производительность ниже плинтуса). Да, и все транзакции, включая и флаги блокировки и завершения, тоже могут остаться в локальном кэше, не попав в общую память, так что транзакции сами по себе, без поддержки уровнем ниже, проблему не решают. По моему Вы неявно что-то подразумеваете, типа write through или некэшируемость для управляющих полей транзакций ... Либо я смотрю сильно глубже необходимого и вопрос лишь в выборе наиболее удобного стандартного механизма синхронизации данных.

[bondkim137]

Pavia, тут несколько о другом разговор. Мне неясно, как транзакции СУБД в общем смысле могут решать проблемы с пропускной способностью хранилища данных, и вообще причем тут они. Мы говорим о локальном хранении данных для уменьшения нагрузки на центральное хранилище (называйте его базой данных, если угодно). Причем организации этого локального хранения таким образом, что б требовалось минимально менять логику работы системы при добавлении подобного кеширования.

[Pavia]

bondkim137 в сообщении #1335154 писал(а):

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

Убираем последовательное исполнение заменяем его параллельным. Тем самым число обработанных операция возрастает.

bondkim137 в сообщении #1335154 писал(а):

Мы говорим о локальном хранении данных для уменьшения нагрузки на центральное хранилище

Все распределённые СУБД транзективные. Ровно как и большинство распределённых файловых систем которые позаимствовали идеи из теории СУБД.

bondkim137 в сообщении #1335154 писал(а):

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

Логику системы вы не меняете. Вы всего лишь вводите прослойку, такую же как и кэш. Просто с транзакциями проще оперировать, так как теория более проработана.
http://edu.mmcs.sfedu.ru/mod/resource/view.php?id=7845
Правда по одному источнику теорию освоить не получится - теория по большей части рассматривает с токи зрения работы с СУБД, а тут больше нужно внутреннее устройство.

bondkim137 в сообщении #1334960 писал(а):

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

В теории транзакций есть решение для повышение эффективности - это уровнями изоляции. Но так как конкретную задачу вы не описали, то и конкретного решения привести не могу.
Стратегия синхронизациями с соседями я уже описал версионность, каждый сосед имеет свою версию и они изолированы. Поэтому не надо каждый раз их обновлять. Уровни изоляции позволяют отказаться от блокировок целых блоков, а свести к их элементам. Поэтому обновлять вы будете не блоки а только считанные байты.
А если вы вынесите всё же логику наружу, то от блокировок и вовсе можно отказаться заменив их двойной проверкой.

bondkim137 в сообщении #1334960 писал(а):

Какие правила стоит (принято) накладывать на работу собственной кеш-памяти, что б все не накрылось медным тазом?

В теории транзакций эти правила именуются ACID.

[bondkim137]

Pavia в сообщении #1335172 писал(а):

Убираем последовательное исполнение заменяем его параллельным. Тем самым число обработанных операция возрастает

Пропускная способность хранилища возрастет?

Pavia в сообщении #1335172 писал(а):

Все распределённые СУБД транзективные

Хранилище тоже распределенное, как я сказал. Но этого недостаточно - упираемся в сеть. Необходимо кешировать куски хранилища локально на вычислительной машине. Либо СУБД должна быть так хитро распределенной, что б стоять в т.ч. локально на вычислительной машине, причем правильными своими частями, что я совершенно не представляю как сделать.

Pavia в сообщении #1335172 писал(а):

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

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

Pavia в сообщении #1335172 писал(а):

Но так как конкретную задачу вы не описали, то и конкретного решения привести не могу

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

-- 29.08.2018, 14:16 --

Есть следующие уточнения.
1. Попробовал использовать простой локальный кеш и оставить один сервер-обработчик, что б временно отложить задачу синхронизации. Блочный кеш пришлось научить сбрасываться в той последовательности, в которой он модернизировался. Иначе при обрывах связи в хранилище может оставаться каша. Пропускная способность удаленного хранилища настолько плохая, что иногда это работает быстрее, чем 10 обработчиков без кеша.
2. Принципиально неважно, если два обработчика запишут что-то в одно место и примерно одновременно и в нем окажется запись непонятно кого из них. Но мешает блочность - думаю попробовать ввести маску при записи. А затем, вместо незамедлительного бродкаста по локальным обработчикам информации о модифицированных блоках в общем хранилище, попробовать выкрутиться версиями блоков. И игнорировать записи, если исходные данные для расчетов к моменту записи изменились. Плюс сбрасывать старые элементы кеша в таких случаях и по таймауту.

[Pavia]

bondkim137 в сообщении #1335248 писал(а):

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

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

bondkim137 в сообщении #1335248 писал(а):

выкрутиться версиями блоков.

С версиями блоков много проблем. Откуда взять начальное значение? Что делать при переполнении# Тут лучше использовать дату-время.

А так пожалуй пока ваш пункт 2 самое хорошее решение.

bondkim137 в сообщении #1335248 писал(а):

Собственно, транзакции элементарные (и атомарные) - запись блока в таблицу и чтение блока из таблицы. Язык не поворачивается называть их транзакциями.

Ссылку выше я давал открываем определение читаем.
«Под транзакцией понимается неделимая с точки зрения воздействия на БД последовательность операторов манипулирования данными
Основное назначение транзакций в базе данных — переводить ее из одного согласованного состояния в другое.»
Видим что транзакция последовательность, то отдельно чтение и отдельно запись не является транзакциями.

Транзакция состоит в общем случае из 5 стадий.
Начало транзакции;
чтение данных;
обработка;
запись данных;
фиксация результата.

Отсюда вывод, надо подняться на ступеньку выше, над чтением и записью. А там мы можем обнаружить следующие операции:
- вставка
- удаление
- добавление
- изменение
- поиск
- выборка
- обработка
-- расчёт с накоплением
-- преобразование, трансформация.

Каждая такая операция кодируется своей транзакцией. Для каждой транзакции Вы должны указать её характеристики(READ UNCOMMITTED, WAIT | NO WAIT и тд).
Для каждой транзакции мы можем использовать свою стратегию планирования и оптимизации. Стратегия выбирается частично вручную, частично автоматически.

bondkim137 в сообщении #1335248 писал(а):

Пропускная способность хранилища возрастет?

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

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

bondkim137 в сообщении #1335248 писал(а):

Но мешает блочность

Прочитайте учебник возможно откроете для себя много нового: Дэвид М. Хэррис, Сара Л. Хэррис Цифровая схемотехника и архитектура компьютера.

[bondkim137]

Pavia в сообщении #1335363 писал(а):

Это громкое заявление.

Это элементарно следует из общих соображений: если два обработчика решили одновременно записать что-то в общую память - то им что без кеша, что с кешем - все равно, чья запись там останется.
А так как понятие одновременности весьма относительно, следует от него вообще отказаться.

Pavia в сообщении #1335363 писал(а):

Тогда вам синхронизация как таковая не нужна, не нужны броудкасты и..

соответсвенно - ерунда.

Pavia в сообщении #1335363 писал(а):

С версиями блоков много проблем. Откуда взять начальное значение? Что делать при переполнении# Тут лучше использовать дату-время

Не очень понял. Расшифруйте. Единица и инкремент-единица в i64 на кеш-промах чем хуже даты? Чем лучше - понятно - уникальностью.

Pavia в сообщении #1335363 писал(а):

Ссылку выше я давал открываем определение читаем. «Под транзакцией понимается неделимая с точки зрения воздействия на БД последовательность операторов манипулирования данными
Основное назначение транзакций в базе данных — переводить ее из одного согласованного состояния в другое.»..

Это все банально понятно. Я раза два уже говорил, что хочется прикрутить кеш-костыль к имеющемуся коду, работающему на уровне чтение-запись. Ну а если менять его, то минимально. А не переписывать его, как велит "религия правильных СУБД". Где, кстати, придется двухэтажную систему лепить все равно.

Pavia в сообщении #1335363 писал(а):

Во-первых. Убираем блокировки пропускная способность возрастает

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

Pavia в сообщении #1335363 писал(а):

нужно ли для этой транзакции выполнять Write-update обновление кэша либо не нужно

Распишите конкретно для данной задачи - что конкретно делать. Так мне совершенно непонятно.

Pavia в сообщении #1335363 писал(а):

Прочитайте учебник возможно откроете для себя много нового: Дэвид М. Хэррис, Сара Л. Хэррис Цифровая схемотехника

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

[Dmitriy40]

Мне кажется логичнее будет смотреть не про кэши, а про синхронизацию данных для параллельных потоков. Хотел я прямо тут всё расписать, но столкнулся с необходимостью сигнализации всем вычислителям о произошедшем изменении служебной структуры, причём быстрее чем они сами опрашивают общую память. Основная идея: пока никто писать никуда не хочет - разрешаем всем читать блоки (незалоченные под запись, иначе ждать освобождения), но для каждого закэшированного блока ведём счётчик у скольких он в локальном кэше. Когда кто-то хочет записать блок, то рассылаем всем (или только тем у кого он реально есть - тут нужен будет не просто счётчик, а список) требование удалить его из локального кэша, выставляем счётчик в спецсостояние залоченности под запись конкретному вычислителю и блокировки чтений и ждём пока все не выполнят удаление (определяем по изменению счётчика), после этого блок залочен от чтения до момента завершения записи и освобождения. Собственно всё, остальное детали, атомарные операции с этим счётчиком, массив их для всех блоков, вопрос где его хранить (в общей памяти слишком много операций нужно, хоть они и мелкие, но бедный трафик), начальная инициализация вычислителя (с пустым кэшем блоков и уникальным номером), восстановление после аварии (отключения вычислителя с потерей инфы об его кэше и рассинхронизации счётчиков). Чем-то похоже на выделение памяти под переменные из кучи и сборку мусора. Кажется даже название у этого метода есть, но не помню. Транзакции сильно помогут лишь в последней ситуации, восстановления после аварии, для остальных они избыточны.

[bondkim137]

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

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

-- 30.08.2018, 02:51 --

Наиболее простой (урощенный) пример:
1) вычислитель A долго пишет сообщение вычислителю B (допустим в оговоренном месте)
2) вычислитель A ставит галочку - мол, сообщение можно читать (оставим пока за скобками сигналинг для ускорения реакции вычислителя B)
3) вычислитель B, прочитав галочку, начинает читать сообщение.
и т.д.
надо, что б прочитав галочку, вычислитель B не достал из кеша каку вместо сообщения.

[Pavia]

bondkim137 в сообщении #1335421 писал(а):

Это элементарно следует из общих соображений: если два обработчика решили одновременно записать что-то в общую память - то им что без кеша, что с кешем - все равно, чья запись там останется.
А так как понятие одновременности весьма относительно, следует от него вообще отказаться.

Вы делаете логическую ошибку. "Выбор формулы определяет природа, условие задачи". Так и тут допустимость одновременной записи определяет задача.
Если рассмотреть хорошо известную задачу о паролельном инкременте. То если мы не в ведём барьерную синхронизацию(блокировку) то переработка сверх нормы может составить от 110% до 200%.

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

А если рассмотреть другую задачу ... паралельная закачка файла. То она вполне решается без блокировок.

bondkim137 в сообщении #1335421 писал(а):

Не очень понял. Расшифруйте. Единица и инкремент-единица в i64 на кеш-промах чем хуже даты? Чем лучше - понятно - уникальностью

Время это f64. Чем f64 лучше i64? Да ничем. Вопрос лишь в удобстве кодирования. Вам нужно будет засинхронизировать вашу i64 со всеми распределёнными процессорами. А СЕВ вам доступен из коробки, время уже засенхронизированно ОС по SNTP.

bondkim137 в сообщении #1335421 писал(а):

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

А о каких вы подумали? Я уже писал про уровни изоляции. Для вашей задачи можно убрать все кроме самого нижнего уровня физического. Dmitriy40 писал о том что на низком уровне должны быть механизмы. Я думаю это оспариваемое утверждение. Но не в рамках данной темы.
Транзакции вместо полной блокировки используют
двойное сравнение. Double checked locking. Описание в википе очень не внятное.

.

bondkim137 в сообщении #1335465 писал(а):

х, но мне не нравится блокировать на чтение

Либо вы делаете частное тогда без блокировки либо общий(универсальный) метод, но тогда с блокировкой.
Что-бы не блокировать каждый раз на чтение используйте TLB - в учебнике описано.

[bondkim137]

Pavia, эта ветка разговора, на мой взгляд, давно утратила смысл, уйдя от топика в широкую демагогию с массой непонятных или просто неверных утверждений и вредных советов.

В частности, точность синхронизации часов "ОС по SNTP" на отдельных машинах может и часто будет ниже, чем характерное время выполнения операции с хранилищем - и такие (созданные на разных машинах) тайм-маркеры ни в коем случае нельзя использовать для определения - чья запись свежее в кешах.

Я, пожалуй, не буду дальше отвечать.