ЭТЮДЫ

[Bolt]

ccf и sbc можно заменить на adc:

rra
adc a,0FFh
rla
sbc a,a

Для проверки A>B:

rra
adc a,07Fh
rla
sbc a,a

5 байт, 19 тактов.

[blackmirror]

Имеется многоядерная система, в которой отсутствует блокировка памяти для выполнения атомарных операций. Совсем отсутствует. Требуется сконструировать функцию AtomicInc, которую можно будет вызывать на разных ядрах и получать уникальные значения счётчика. Посылать выделенному ядру прерывания не вариант, не факт что нашей программе это разрешат, кроме этого мы не знаем на каких ядрах нас запустили, но номер своего ядра каждый поток узнать может. Изначально обнулённый общий блок памяти для синхронизации решения задачи у них тоже имеется, кеширование для него отключёно. Единственный вариант который пока удалось придумать:
0) сделать каждому ядру свой флаг, изначально сброшенный
1) установить свой флаг перед чтением счётчика
2) прочитать флаги остальных ядер и счётчик
3) если стоит только наш, записываем новый счётчик и снимаем флаг, и на этом выходим
4) если стоят флаги с большим номером, переходим к пункту 2 ожидая пока их снимут
5) если стоят флаги с меньшим номером, снимаем свой и ждём пока снимут остальные чтобы перейти к пункту 1 для новой попытки
Будет ли такой алгоритм работать или есть варианты проще и надёжнее?

[Bolt]

Многозадачность вытесняющая? Зашёл поток на ядре в функцию, а диспетчер прервал на полуслове и на это ядро другой поток повесил, который зашёл в функцию...
Нужно больше информации о системе.

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

Скрытый текст

Создаём массив по количеству ядер. В массиве: флаг запроса, значение.

Запускаем некий главный процесс.
0. Процесс в цикле ищет установленный флаг запроса.
Если нашёл:
1. Прочитать счётчик.
2. Инкремент.
3. Записать новое значение в счётчик и в элемент массива, в котором найден флаг.
4. Сбросить флаг запроса.
5. Перейти в пункт 0 и искать новый запрос.

Получение значения (работа ведётся со своим элементом массива, по номеру ядра):
1. Установить флаг запроса.
2. Дождаться сброса флага запроса.
3. Прочитать значение.

Но одно ядро занято.

[свернуть]

[blackmirror]

Многозадачность вытесняющая?

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

[Bolt]

Может тогда типа как в сетях используется CSMA/CD?

1. Зашли в функцию, сразу поставили флаг.
2. Просмотрели флаги, если никого нет - инкремент, сброс флага, выход.
Если есть кто-то ещё:
3. Сбросить свой флаг.
4. Выждать некий случайный интервал.
5. Начать заново с пункта 1.

Если кто-то уже работает - он работает до конца, остальные будут сбрасывать-устанавливать флаги.

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

Примерно так разруливает коллизии Ethernet.

[blackmirror]

Bolt, там проблема в том, что при шине в 16 байт реальное обращение в память занимает 50 тактов, то есть пока мы ждём этот флаг, можно успеть прочитать 800 байт(и столько же записать, так как шины отдельные). Моя версия алгоритма именно поэтому начинается с записи, а не чтения флага, так как такой подход вроде как уменьшает время блокировки свободного ресурса, но это еще нужно проверить. А вот если ресурс часто оказывается занят, возможно имеет смысл вместо освобождения поставить флаг, что нам он тоже нужен, чтобы захвативший ресурс раздал уникальные счётчики всем кто ждёт.

[Bolt]

blackmirror, какая-то сложная там у вас система

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

Во. Кто первый зашёл, тот становится вон тем супервизором, который в цикле просматривает флаги и раздаёт всем номера. Всем раздал - сам взял номер и вышел.
Да, он может застрять надолго. Если приложению это критично, то супервизор передаёт кому-то эту роль и выходит.

[Destr]

Народ, есть идеи как оптимизировать такую конструкцию?

	PUSH DE
PMID	LD A,L:ADD A,E:LD C,A:RRA:XOR L:XOR E:RLA:RR C
	LD A,H:ADD A,D:SRA A:LD B,A
	JP P,BPOS
	LD HL,BC
	JP PMID
BPOS	JP Z,BZER
	LD DE,BC
	JP PMID
BZER	POP DE
	LD HL,BC
	RET

Всю голову сломал, хочется развернуть в DUP-EDUP чтоб избавится от JP (для ускорения), но условные ветвления мешают...

[Bolt]

Условия мешают, но ускорить можно.

	PUSH DE
	JP PMID
PMID_2
	LD HL,BC
PMID
	LD A,L:ADD A,E:LD C,A:RRA:XOR L:XOR E:RLA:RR C
	LD A,H:ADD A,D:SRA A:LD B,A

	JP NP,PMID_2 ; не помню как правильно not P
BPOS ; метка не используется
	LD DE,BC
	JP NZ,PMID
BZER ; метка не используется
	POP DE
	LD HL,BC
	RET

[blackmirror]

Destr, нужно три ветки, одна вычисляет BC=func(DE,HL), вторая DE=func(BC,HL) и третья HL=func(BC,DE). Тогда LD DE(или HL),BC можно будет оставить только в конце, а внутри переходим к правильной ветке, примерно так:

	PUSH DE
L1:	BC=DE+HL
	JM L3
	JZ X1
L2:	DE=BC+HL
	JM L1
	JZ X2
L3:	HL=BC+DE
	JM L2
	JNZ L1
	POP DE
	RET
X1:	LD HL,BC
	POP DE
	RET
X2:	LD HL,DE
	POP DE
	RET