[Digi 0]

Не могу понять, как в один *.out файл поместить програмные модули, которые должны работать в разных ядрах.

И вообще я еще не понял принцип работы программы в многоядерном процессоре. Я понял я так: К примеру Ядро 0 выполняет задачи передачи данных, обобщение результатов вычислений. Ядра 1-4 вычисляют принятые во внутреннюю память данные и укладывают туда же результаты. Связь между ядрами осуществялется через внутренюю память.

Это правильно или как то иначе ?

[megajohn 8]

связь должна быть через spinlock

 

если не ошибаюсь, нужно смотреть Inter-Processor Communication (IPC) 1.25

[jcxz 242]

И вообще я еще не понял принцип работы программы в многоядерном процессоре. Я понял я так: К примеру Ядро 0 выполняет задачи передачи данных, обобщение результатов вычислений. Ядра 1-4 вычисляют принятые во внутреннюю память данные и укладывают туда же результаты. Связь между ядрами осуществялется через внутренюю память.

Это правильно или как то иначе ?

Правильно. Что-ж тут непонятного? Ядра работают как независимые CPU, только память у них общая (не вся).

Связь через общую память и межядерные прерывания.

[vpd 0]

Ну, еще бывают кольцевые очереди (FIFO), через которые можно сообщения слать из одного ядра в другое через общую память. Главная фича FIFO, в отличие от связанных списков списков и spinlock-ов, в том, что они гарантируют корректную работу очередей при асинхронном взаимодействии ядер, без спец. команд типа compare and exchange. Ну и операции с FIFO атомарные, O(1).

[jcxz 242]

А FIFO что - разве не в общей памяти находятся?

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

 

Ну и операции с FIFO атомарные, O(1).

В FIFO достаточно чтобы были только операции записи указателей атомарными (а это верно практически для всех CPU). Запись самих данных в FIFO не обязательно должна быть атомарна.

[vpd 0]

Так я же написал, что в общей. Дело не в памяти, а в том, как именно через нее взаимодействовать. (Хотя, если совсем точно, то у FIFO в интерфейсе нет адреса, он скрыт внутри реализации). Межъядерные прерывания - не самый удобный механизм синхронизации, впрочем как и spinlock. При нормальной загрузке процессора это слишком большой оверхед, либо малая вероятность захватить spinlock. Простейшая аналогия - дозвониться в call-центр, где звонки в очередь не ставятся.

 

Формально двусвязный список тоже можно считать очередью (FIFO), если один в него пишет, а другой читает. Однако операции с указателями списка производят обе стороны, и поэтому любая операция постановки/выборки из очереди требует критической секции (spinlock или mutex), что и становится узким местом. В случае кольцевого буфера не нужен ни spinlock, ни mutex. Вот. В общем-то даже прерывания не нужны, хотя с ними можно снизить частоту опроса до минимума и не будить ядро без надобности. По моему опыту вполне жизнеспособный вариант IPC. Я его не никому не хочу навязывать, просто хочу обратить внимание, что бывает, что городят связку список+спинлок там, где хорошо бы подошла именно асинхронная кольцевая очередь (FIFO).

 

 

 

Да, и еще хочу добавить, что такая модель довольно легко масштабируется на случай отсутствия общей памяти между ядрами. Например, у нас была как-то связка HOST+DSP, которые общались между собой вообще через разогнанный до мегабит UART. И такой способ обмена данными тоже довольно удачно лег на модель кольцевых очередей, никто и не заметил.

Изменено 25 декабря, 2013 пользователем Hoodwin

[jcxz 242]

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

Только кольцевые FIFO, а прерывания использовал для нотификаций (уведомлений) о событии в соответствующем ядре. В частности - нотификации о добавлении инфы в FIFO.

Нотификации у меня были асинхронные (без ожидания приёма на той стороне) или синхронные (с ожиданием приёма той стороной). В основном использовал асинхронные.

 

Ну ещё (на этапе старта ПО) использовал, что типа state-машины для простой синхронизации (одно ядро выполняет какой-то кусок кода, заканчивает, переключает состояние

state-машины, другое ядро начинает работать, а первое - ждёт, до того как 2-е ядро не выполнит свой кусок и не изменит состояние state-машины и так далее).

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

[andrewn 0]

FIFO, в отличие от связанных списков

Ну-ну. FIFO и есть связанный список. Какие отличия???

FIFO [...] гарантируют корректную работу очередей при асинхронном взаимодействии ядер, без спец. команд

Ничего FIFO не гарантирует, синхронизацию доступа надо аппаратными средствами осуществлять, причем в 667х эти средства есть.

операции с FIFO атомарные, O(1)

Экие у вас странные представления о необходимых и достаточных условиях. Из О(1) вовсе не следует атомарность, этот термин для других целей используется.

Формально двусвязный список тоже можно считать очередью (FIFO)

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

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

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

 

 

Не могу понять, как в один *.out файл поместить програмные модули, которые должны работать в разных ядрах.

Что бы долго не думать, я собираю несколько исполняемых файлов. В максимуме - восемь.

 

[jcxz 242]

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

Причём тут везение и какие индексы в очереди? Очереди у меня безиндексные - они там не нужны, это не массив.

И искалечить процессы (или процессоры) ничего не могут в принципе, если у вас правильно построены очереди и алгоритм работы с ними.

В очереди есть два указателя: один - позиция записи, другой - позиция чтения.

У каждой очереди есть пишущий процесс (процессор) и читающий процесс (процессор). У очереди может быть ТОЛЬКО ОДИН пишущий процесс (CPU) и ТОЛЬКО ОДИН читающий процесс (CPU).

В процессе записи модифицируется ТОЛЬКО указатель записи, указатель чтения при этом используется только как read-only.

В процессе чтения модифицируется ТОЛЬКО указатель чтения, указатель записи при этом используется только как read-only.

Таким образом - каждый из указателей модифицирует только свой процесс (CPU) и другой процесс (CPU) его использует только на чтение.

Такой алгоритм работы очередей позволяет не использовать критические секции (сериализацию доступа к ресурсу), что очень ценно для межъядерного взаимодействия.

Да, конечно, операция модификации (записи) указателя очереди должна быть атомарной, но это не проблема в любом CPU.

 

PS: А чтобы не "вляпываться в ситуации", надо продумывать алгоритм, а не рассчитывать на везение :)

[vpd 0]

FIFO и есть связанный список. Какие отличия???

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

 

Ничего FIFO не гарантирует, синхронизацию доступа надо аппаратными средствами осуществлять, причем в 667х эти средства есть.

...

Не вляпались в ситуацию, когда оба процесса одновременно искалечат индексы первого и последнего элементов очереди. Это же элементарно и называется оверран.

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

1) ему не нужна особая специальная поддержка в аппаратных средствах.

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

3) overrun и underrun не является проблемой FIFO, и тут вам jcxz все правильно написал. Я только еще раз суть подчеркну: любая сторона может асинхронно проверить ситуацию на overrun/underrun и сделать правильные выводы. Для этого не нужно делать критическую секцию вокруг FIFO. Вообще говоря это не дается бесплатно, но платой является то, что писатель может увидеть overrun даже когда место на самом деле еще есть, а читатель может увидеть пустое fifo еще какое-то время после того, как там данные уже появились. Или, проще, цена состоит в том, что один-два слота памяти FIFO будут зарезервированы на крайний случай, но не будут использоваться фактически. Так вот, эта цена обычно абсолютно приемлема, так как памяти в нем гораздо больше.

4) FIFO могут использоваться для передачи данных в другие клоковые домены, хотя это уже больше относится к их реализации в ПЛИС. В этом случае им также нет конкурентов по совокупности характеристик, главной из которых является возможность асинхронной передачи данных.

 

[andrewn 0]

Причём тут везение и какие индексы в очереди?

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

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

Да, конечно, операция модификации (записи) указателя очереди должна быть атомарной, но это не проблема в любом CPU.

Это и есть синхронизация. Только кто же эту атомарность-то обеспечит? Какой механизм вы используете? В некоторых (далеко не во всех) ЦПУ есть аппаратные атомарные операции, а в остальных - это проблема...

атомарной операцией (то есть не зависящей от состояния структуры) является вставка и удаление

Еще раз - атомарная операция - это совершенно другое. И весь ваш способ работы с FIFO, если он явно не использует атомарные (в смысле истинного определения) операции - опасен и ошибочен.

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

Ещё раз - FIFO не способ синхронизации. FIFO - способ организации данных.

 

Больше того, не просто так появился аппаратный IPC контроллер. Он-то и осуществляет алгоритм межпроцессорной синхронизации.

 

2), 3) - всё без исключения ложь. Когда вляпаетесь, не говорите, что мол, наколдовал.

 

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

 

[jcxz 242]

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

...

2), 3) - всё без исключения ложь. Когда вляпаетесь, не говорите, что мол, наколдовал.

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

Похоже Вы плохо представляете как правильно организовать FIFO, устойчивую к перекрывающимся вызовам из разных процессов (CPU) без критических секций.

И совершенно не поняли п.3 который написал Hoodwin. Перечитайте его ещё и ещё. Там всё достаточно описано.

Поймите простой принцип использования FIFO: один процесс ТОЛЬКО ПИШЕТ, другой - ТОЛЬКО ЧИТАЕТ.

Указатель записи модифицирует ТОЛЬКО пишущий процесс, указатель чтения - ТОЛЬКО читающий. Никаких других переменных (изменяющихся в ходе работы FIFO)

быть не должно. Размер свободного места и размер занятого места в FIFO должны вычисляться только из текущих значений указателей и полного размера FIFO

(который - const). После модификации указателей, полезно вставлять инструкции барьеров (типа DMB в Cortex-ах).

Если следовать этому принципу, то FIFO можно использовать для передачи сообщений между процессами (CPU) без критических секций.

И никаких проблем с переполнением там нет. Пишущий процесс всегда может проверить сколько осталось места в очереди и отреагировать на это.

Как тогда скажите произойдёт ваше неожиданное переполнение??? Ведь другой процесс НЕ МОЖЕТ туда писать.

 

Насчёт атомарности операций записи: если в данном CPU имеются ассемблерные команды записи соответствующей разрядности (и нет проблем с выравниванием),

то запись указателя (позиции, индекса и т.п.) будет атомарной. Если у вас указатели FIFO 32-битные, то на ядрах C667х и ARM9 (в OMAP) запись будет одной командой.

Советую смотреть в листинг-файлы компилятора и изучать ассемблер.

 

[andrewn 0]

Если следовать этому принципу, то FIFO можно использовать для передачи сообщений между процессами (CPU) без критических секций.

Да, да. Вы мне честно скажите, на какой самолёт работаете? Я в него никогда в жизни не сяду, под страхом смертной казни. И вам лично не советую - я же не зверь :)