TIS-100 — паззл про многопоточный ассемблер, который никто не ждал

    image

    Удивительно, но никто не написал ничего про игрушку «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
    

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

    Собственно, в этом вся игра. Есть задания, есть просто песочница.

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

    Подробнее
    Реклама
    Комментарии 23
    • +2
      Замечательная игрушка. С реальным ассемблером практически не работал, но играю с удовольствием. Здорово сделан запуск игры и завершение — загрузка TIS-100 и отключение соответственно.
      Радует и кросплатформенность. Кроме Steam, можно приобрести на GOG DRM-free версию (сейчас скидка, обойдётся в 159р).
      • 0
        Советую всегда пробовать вывести решение на минимальное количество циклов. Как правило, это невозможно сделать без распараллеливания (которое во многом и придает интерес).
        • 0
          А как потратить меньше циклов в тестовом задании? Там же нельзя за раз сразу два числа читать?
          • 0
            сразу нет, но данные приходят постоянно и их можно роутить на разные блоки для параллельных вычислений.
            Например, у нас сверху идут числа :1,2,3,4
            А в принимающем блоке код вроде:

            mov up left
            mov up right

            то число 1 уйдет налево а 2 направо, 3 — снова налево и так далее.
            • 0
              А ядра синхронные? То есть, если написать
              mov up, left
              mov up, down
              А дальше снова объединить потоки данных, они придут синхронно?
              • 0
                Это от многого зависит: числа блоков, которые проходят данные, числа выполняемых над ними операций, синхронизацией между блоками. Вроде как любая инструкция выполняется один такт.

                То есть, если вы из одного блока разделяете поток данных на два, затем каждый из двух выполняет одну и ту же операцию и затем потоки объединяются в том же порядке — то да, придут синхронно. Если нет — надо ставить для синхронизации NOP или ещё что-то придумывать.
                • +2
                  Все ядра одновременно выполняют очередную команду, на которой находится курсор (у каждого процессора курсор может быть в своей, отличной от всех других процессоров, строке) и затем перемещают курсор на следующую строку, если сама команда не подразумевает перехода (JMP). Если команда последняя в блоке — курсор перескакивает на первую строку. Если команда подразумевает чтение данных из любого порта (верхнего, нижнего, левого, правого), то курсор остаётся на команде чтения пока чтение не станет возможно, то есть пока соответствующий соседний процессор не запишет что-то в порт.

                  В данном случае, пробрасывая в цикле сначала налево, затем направо, мы добьёмся того, что у нас с отставанием на один такт будут удваиваться числа. Сначала по левой цепочке ядер, затем по правой. И если цепочки одинаковой длины, то и к выходу они будут приходить сначала из левой цепочки, потом из правой. И, если я правильно понял ваш вопрос, то ответ — да, порядок входных данных и соответствующих результатов будет сохранён, а скорость обработки увеличится.
            • 0
              А есть еще подобные игры?
              • НЛО прилетело и опубликовало эту надпись здесь
                • +1
                  Просто посмотрите все игры этого парня (http://www.zachtronics.com)
                  Spacechem только одна из них, есть еще из интересных Infinifactory, Codex (тоже на алгоритмизацию) и Kohctpyktop (там нужно полупроводниковые схемы делать)
                  • +7
                    [offtop] Всегда было интересно, как иностранцы читают название Конструктора — «кохцтпайктоп»...? :)
                  • 0
                    Есть, IBM BlueGene называется. Только там хардкорнее: сетка трёхмерная и противоположные грани замкнуты. И до кучи, вместо одной системы передачи сообщений сделано три: в соседние ячейки, fat tree и широковещательная сигнальная. Ну и каждая ячейка — это 4х ядерный процессор, поэтому в ней можно распараллелиться более эффективно.
                    • +1
                      Есть еще Lightbot, Lightbot-2.
                    • +1
                      Ctrl+Y в редакторе не работает, а зря :)
                      • 0
                        Ctrl+Z — отменить действие
                        Ctrl+Y — повторить действие

                        Если не ошибаюсь.
                      • +1
                        Вообще, очень долго не мог привыкнуть писать в команде MOV в качестве параметров ЧТО, КУДА. Руки упорно набирали в обратном порядке. Тяжкое наследие TASM.
                        • 0
                          GAS-syntax же :-)
                          • 0
                            Попробуйте ассоциировать с шелловской командой cp/scp/mv и так далее. «Откуда» — «куда». Хотя понимаю, сложно избавиться от привычки.
                          • 0
                            Надо же, угадал создателя игры по скриншоту.
                            • +1
                              www.tis100pad.com
                              Полезный gist для сохранения результатов.
                              • 0
                                Слегка не работает.
                                «Congratulations on your first Django-powered page.»
                                • 0
                                  Жаль, прикрыли…
                              • 0
                                Отличная игра. С удовольствием потратил на неё четверть выходных.

                                Теперь хочется поработать с настоящим ассемблером на многоядерной машине.

                                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.