Удивительно, но никто не написал ничего про игрушку «TIS-100», которая недавно появилась в Steam (стоит всего 150 рублей, уже 460 положительных отзывов против 6 отрицательных).
Сразу оговорюсь, что к авторам игры я отношения не имею, а вот сама эта игра — отличный инструмент для всех программистов, которые хотят сразиться друг с другом в оптимизации кода на выдуманном хитром ассемблере.
Итак, о чем игра?
Суть в том, что вам дается задание, которое нужно выполнить. Например «читайте число из IN.A, сравниваете с числом из IN.B и если IN.A > IN.B, пишете в выход IN.A-IN.B, иначе — IN.B-IN.A.
На самом деле, она очень простая и освоить здешний ассемблер может каждый. У него есть две фишки.
1. Он жутко минималистичный и от того — неудобной
2. Он многопоточный. Вот, те блоки, которые вы видите на экране — все они выполняются одновременно.
Для того, чтобы понять, что тут и как — вот вам самый первый уровень:
Задача простая. Читать из входа, удваивать, писать в выход.
Вот мое (самое прямолинейное) решение:
Код в первом блоке:
MOV UP, ACC // читаем число из верхнего входа и кладем его в аккумулятор
ADD ACC // прибавляем к аккумулятору аккумулятор
MOV ACC, DOWN // отправляем значение аккумулятора вниз
Дальше уже просто число перекидывается между выходами.
Запускаем, программа проходит контрольный тест, все ОК. И мы видим результат:
Слева показано, каково ваше решение относительно других игроков. Мы видим, что по числу использованных нодов и инструкций — мы самые оптимальные. Но вот кто-то решил эту задачку за меньшее кол-во циклов. Как? Вот тут включается уже вторая ступень интереса — не просто решить задачу, но и решить ее оптимально по каждому из 3х параметров.
Немного слов об ассемблере.
Сначала — операнды. Собственно, тут все просто. Это ожидаемые LEFT, RIGHT, DOWN, UP, ACC. А так же „ANY“ (которое читает из любого порта) и „LAST“ (читает из последнего порта). Есть еще NIL для обозначения „мусорного“ порта.
Также, кроме аккумулятора, есть еще backup (BAK). С ним нельзя работать напрямую, только через swap'ы (см. ниже).
Далее — список команд.
- NOP — ничего не делает
- MOV [1], [2] — запись из [1] в [2]
- ADD [1] и SUB [1] — прибавить/вычесть к аккумулятору [1]
- NEG — инвертация значения в аккумуляторе
- SWP — обменять значения аккумулятора и BAK
- SAV — сохранить аккумулятор в BAK
- JMP — безусловный переход на метку (метки обозначаются как „LABEL:“)
- JEZ (equal zero), JNZ (not zero), JGZ (greater zero), JLZ (less zero) — условные переходы (аргументом сравнения является аккумулятор)
- JRO [1] — относительный переход (вперед/назад на [1] инструкций)
Собственно, на этом все. Т.е. по сути у вас есть всего 1 регистр (плюс 1 запасной, к которому не так-то просто добраться) и несколько команд.
Самая неудобная штука в этом ассемблере, это то, что сравнение для условий переходов производится по аккумулятору. В „настоящих“ ассемблерах (которые я видел) условие проверяется по флаговому регистру, который в свою очередь выставляется только либо специальной командой сравнения, либо после арифметический операции. Т.е. можно написать так:
CMP 2
MOV 1, ACC // это на выход
JE LABEL
В результате чего мы перейдем по LABEL только если на входе параметр был равен 2, и при этом в аккумулятор мы положим на выход единичку (т.к. операция „MOV“ не изменить флаговый регистр).
В TIS-100 все не так. Чтобы выполнить что-то подобное, придется сделать так:
SWP // сохраняем значение аккумулятора
MOV 1, ACC // это на выход
SWP // меняем назад
SUB 2
JEZ LABEL
И это при том, что мы испортили первоначальное значение аккумулятора. Если потом придется его сравнить с другим числом, мы испытаем проблемы.
Собственно, в этом вся игра. Есть задания, есть просто песочница.
Думаю, программистом должно быть интересно. Особенно скучающим по хардкорным временам.
Комментарии (21)
vk2
24.07.2015 13:47Советую всегда пробовать вывести решение на минимальное количество циклов. Как правило, это невозможно сделать без распараллеливания (которое во многом и придает интерес).
Turbo
24.07.2015 14:19А как потратить меньше циклов в тестовом задании? Там же нельзя за раз сразу два числа читать?
Dreadd
24.07.2015 15:50сразу нет, но данные приходят постоянно и их можно роутить на разные блоки для параллельных вычислений.
Например, у нас сверху идут числа :1,2,3,4
А в принимающем блоке код вроде:
mov up left
mov up right
то число 1 уйдет налево а 2 направо, 3 — снова налево и так далее.
gurux13
24.07.2015 16:06А ядра синхронные? То есть, если написать
mov up, left
mov up, down
А дальше снова объединить потоки данных, они придут синхронно?
JIghtuse
24.07.2015 19:53Это от многого зависит: числа блоков, которые проходят данные, числа выполняемых над ними операций, синхронизацией между блоками. Вроде как любая инструкция выполняется один такт.
То есть, если вы из одного блока разделяете поток данных на два, затем каждый из двух выполняет одну и ту же операцию и затем потоки объединяются в том же порядке — то да, придут синхронно. Если нет — надо ставить для синхронизации NOP или ещё что-то придумывать.
iDeBugger
24.07.2015 19:58+2Все ядра одновременно выполняют очередную команду, на которой находится курсор (у каждого процессора курсор может быть в своей, отличной от всех других процессоров, строке) и затем перемещают курсор на следующую строку, если сама команда не подразумевает перехода (JMP). Если команда последняя в блоке — курсор перескакивает на первую строку. Если команда подразумевает чтение данных из любого порта (верхнего, нижнего, левого, правого), то курсор остаётся на команде чтения пока чтение не станет возможно, то есть пока соответствующий соседний процессор не запишет что-то в порт.
В данном случае, пробрасывая в цикле сначала налево, затем направо, мы добьёмся того, что у нас с отставанием на один такт будут удваиваться числа. Сначала по левой цепочке ядер, затем по правой. И если цепочки одинаковой длины, то и к выходу они будут приходить сначала из левой цепочки, потом из правой. И, если я правильно понял ваш вопрос, то ответ — да, порядок входных данных и соответствующих результатов будет сохранён, а скорость обработки увеличится.
koltykov
24.07.2015 14:46А есть еще подобные игры?
Shekeen
24.07.2015 15:24+1Просто посмотрите все игры этого парня (http://www.zachtronics.com)
Spacechem только одна из них, есть еще из интересных Infinifactory, Codex (тоже на алгоритмизацию) и Kohctpyktop (там нужно полупроводниковые схемы делать)
KorDen32
24.07.2015 18:11+7[offtop] Всегда было интересно, как иностранцы читают название Конструктора — «кохцтпайктоп»...? :)
kibergus
24.07.2015 16:17Есть, IBM BlueGene называется. Только там хардкорнее: сетка трёхмерная и противоположные грани замкнуты. И до кучи, вместо одной системы передачи сообщений сделано три: в соседние ячейки, fat tree и широковещательная сигнальная. Ну и каждая ячейка — это 4х ядерный процессор, поэтому в ней можно распараллелиться более эффективно.
iDeBugger
24.07.2015 19:59+1Вообще, очень долго не мог привыкнуть писать в команде MOV в качестве параметров ЧТО, КУДА. Руки упорно набирали в обратном порядке. Тяжкое наследие TASM.
vk2
17.08.2015 23:26Попробуйте ассоциировать с шелловской командой cp/scp/mv и так далее. «Откуда» — «куда». Хотя понимаю, сложно избавиться от привычки.
sigod
03.08.2015 15:23Отличная игра. С удовольствием потратил на неё четверть выходных.
Теперь хочется поработать с настоящим ассемблером на многоядерной машине.
JIghtuse
Замечательная игрушка. С реальным ассемблером практически не работал, но играю с удовольствием. Здорово сделан запуск игры и завершение — загрузка TIS-100 и отключение соответственно.
Радует и кросплатформенность. Кроме Steam, можно приобрести на GOG DRM-free версию (сейчас скидка, обойдётся в 159р).