Serguey Zefirov (thesz) wrote,
Serguey Zefirov
thesz

Моделирование аппаратуры на Хаскеле. Часть 2.

Игра в ассемблеры, так сказать.

Предупреждение

Как и раньше, необходимо знание синтаксиса Хаскеля. За этим я отошлю к документации.

На вопросы - отвечу.

Введение

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

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

Первая часть, как строить систему моделирования в целом.

Ассемблер

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

Если мы моделируем какой-либо процессор, то ассемблер и программирование в нём нам нужно по минимуму, но всё же необходимо.

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

Сперва речь пойдёт о самом простом варианте - ассемблер стекового процессора. Причем мы будем считать, что общение с внешним миром для него гораздо более затратно, чем выборка команд. Чтобы это не было совсем оторвано от реальности, то вот вариант похожего процессора:
Процессор Чака Мура 25x содержал матрицу 5x5 процессоров f21, каждый из которых имел 512 слов встроенной памяти. Память адресовалась быстро - на частоте процессора, внешняя память - медленно, её частота обмена была в пять раз медленней частоты ядра и она была доступна только тем ядрам, которые были к ней непосредственно подсоединены. Встроенная память использовалась для переменных и кода - в одном слове 4 команды. Разница в производительности двух видов памяти разительна.

Обсуждение на слешдоте, к сожалению, со слегка устаревшими ссылками.
Вот мы и будем думать, что с кодом у нас всё в порядке, поскольку он лежит во внутренней памяти.

Самый простой вариант системы команд

Мы будем принимать из внешнего мира воздействия в виде целых чисел и отдавать ему результаты тоже в виде целых чисел.

Теперь мы прервёмся и опишем нашу архитектуру системы команд - кратенько, без лишних объяснений:
module StackProcessor where

import S

type StackProcProg = [StackProcCmd] -- последовательность команд является программой.

data StackProcCmd =
      Nop -- Без no-op не обходится ни одна уважающая себя система команд.
   |  Dup -- дублировать верхушку стека данных.
   |  Const Int -- поместить константу на верхушку стека.
   |  Plus -- сложить два числа на вершине стека.
   |  Minus -- вычесть два числа на вершине стека. 
   |  Cmp Ordering -- Сравнить два значение на вершине на EQ/LT/GT.
                   -- Поместить 0 (ложь) или 0xFFFFFFFF (истина) на вершину стека
   |  Input -- поместить входное воздействие на верхушку стека. Ждать, если что.
   |  Output -- выдать наружу значение с верхушки стека.
   |  J StackProcProg -- безусловный переход.
   |  B StackProcProg -- переход по не-нулю на верхушке стека данных.
   |  C StackProcProg -- вызов подпрограммы.
   deriving Show
А вот и самая первая программа. Мы будем ждать, пока входное воздействие не станет равно или превысит 20 и посчитаем количество пройденных циклов:
-- продолжение модуля StackProcessor

prog1 = [Const 0]++prog1loop1 -- таким образом мы осуществляем продолжение выполнения.

prog1limit = 20

prog1loop1 = [          -- на входе: count
                        -- содержимое стека после команды:
       Const 1          -- count 1
      ,Plus             -- count
      ,Input            -- count input
      ,Const prog1limit -- count input proglimit
      ,Cmp LT           -- count flag (flag = input < proglimit)
      ,B prog1loop1     -- count (flag был использован)
      ,Output           -- (пусто)
   ]
Вот такая программа. Если вы попытаетесь её распечатать (show prog1), то отображение войдёт в бесконечный цикл.

Процессор, он же интерпретатор

Процессор мы организуем в виде уже упоминавшегося автомата Мили: функция из состояния и входного воздействия в следующее состояние и результат.

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

Стек данных хранит только целые числа, стек возврата - только ссылки на программы.

Состояние процессора - это тройка (запомненное значение входного воздействия, стек данных, стек возвратов). Входное воздействие - Maybe Int, целое число, которого может и не быть. Результат - пара (флаг остановки Bool, выходное воздействие Maybe Int).

Вот функция Мили нашего стекового процессора:
-- продолжение модуля StackProcessor

stackprocessorf (inputhold,execstack,datastack) input = (state',(stop,output))
   where
      -- Выбираем между запомненным значением и пришедшим.
      actualinput = case (input,inputhold) of
         (Nothing,x) -> x
         (x,_)       -> x
      -- Текущая команда на выполнение и новый стек возвратов:
      (cmd,execstack') = case execstack of
         [] -> (Nothing,[])         -- нечего выполнять.
         ([]:es) -> (Just Nop,es)   -- дошли до конца подпрограммы, возврат
         ((c:cs):es) -> (Just c,cs:es) -- есть ещё одна команда.
      -- Признак остановки:
      stop = case cmd of
         Just _  -> False
         Nothing -> True
      -- Команда осуществляет действия над входным значением и стеком данных:
      (inputhold',output,execstack'',datastack')
         | Nothing <- cmd = (actualinput,Nothing,execstack',datastack)
         | Just cmd' <- cmd = case (cmd',datastack) of
            (Nop,ds) -> holdin ds
            (Dup,(d:ds)) -> holdin $ d:d:ds
            (Const x,ds) -> holdin $ x:ds
            (Plus,(a:b:ds)) -> holdin $ a+b:ds
            (Minus,(a:b:ds)) -> holdin $ b-a:ds -- Const 3, Const 1,Minus
                                                -- должно дать 2.
            (Cmp ord,(a:b:ds)) -> holdin $ bool (ord == compare b a):ds
            (Input,ds) -> case actualinput of
                                        -- мы возвращаем указатель обратно на
                                        -- непрошедший Input. Почти хак.
               Nothing -> (Nothing,Nothing,execstack,ds)
               Just x -> (Nothing,Nothing,execstack',x:ds)
            (Output,x:ds) -> (actualinput,Just x,execstack',ds)
            (J label,ds) -> (actualinput,Nothing,label:tail execstack',ds)
            (B label,x:ds)
               | x /= 0 -> (actualinput,Nothing,label:tail execstack',ds)
               | otherwise -> (actualinput,Nothing,execstack',ds)
            (C label,ds) -> (actualinput,Nothing,label:execstack',ds)
            -- Всё остальное - ошибка:
            _ -> error "Improper combination of data stack and current command."
         where
            holdin datastack = (actualinput,Nothing,execstack',datastack)
            bool True = 0xffffffff
            bool False = 0
      state' = (inputhold',execstack'',datastack')

-- Создание законченного элемента на базе нашей функции.
stackprocessor program input = unzipS $
   loopS (Nothing,[program],[]) stackprocessorf input
В общем и целом, всё довольно просто: в нужные места подводим нужные операнды, если что не так - ругаемся. Основная задача - оправдать наличие того или иного операнда там, где он используется. Лучше всего это видно на примере Input - там нам пришлось использовать входное значение execstack, несмотря на то, что мы взяли из него команду. Но это также присутствует и в реальных процессорах, во время pipeline stall - пузыря в конвейере.

А вот функция для изучения поведения нашего процессора:
-- продолжение модуля StackProcessor

stackprocessordemo inputdelay = result
   where
      inputs = fromListS Nothing $
         concatMap (\x -> replicate inputdelay Nothing++[Just x]) [0..]
      (stop,output) = stackprocessor prog1 inputs
      result =
         zip (toList inputs) $
         map snd $
         takeWhile (not . fst) $
         zip (toList stop) (toList output)
Она создаёт входную последовательность с периодически возникающими входными воздействиями и запускает процессор. Потом смотрит, когда он остановится и наружу выдаёт и входные данные и выходные. Это позволяет посмотреть на систему в целом. Например, наш процессор начинает пропускать входные воздействия, когда inputdelay становится меньше 5, что легко понять, сравнив количество отработанных циклов для inputdelay=7 и inputedelay=4. (Хотя я думал, что критическое число равно 6.)

Неготовое

Ассемблер с кодированием в образ памяти

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

Сейчас попробуем. Одновременно напишем и создание образа памяти программы и его декодирование.

Всего у меня получилось четыре этапа. Заинтересованный читатель может попробовать разобраться, какой этап для чего нужен, для всех остальных будут объяснения чуть ниже.
-- Продолжение модуля StackProcessor.
-- Этап 1 ==========================================================
-- Страшная монада отслеживания состояния.
-- Вариант её реализации находится в Control.Monad.State,
-- но приведена здесь для большей понятности.
-- В общем и целом, интерфейс этой монады совпадает со
-- State (get, put и modify + do-синтакс)
--
-- Data.Map я тоже не стал использовать. Вместо неё ассоциативный список
-- [(ключ,данные)] и alookup.

data SM s a = SM {unSM :: s -> (a,s)}

get = SM $ \s -> (s,s)
put s = SM $ \_ -> ((),s)
modify f = SM $ \s -> ((),f s)

execSM (SM f) s0 = snd $ f s0

instance Monad (SM s) where
   return a = SM $ \s -> (a,s)
   (SM f) >>= q = SM $ \s -> (\(a,s') -> (unSM (q a)) s') (f s)

addword w = modify
   (\(addr  ,mem         ,alllabels,labelacc) ->
     (addr+1,(addr,w):mem,alllabels,labelacc))
curraddr = do
   (a,_,_,_) <- get
   return a

alookup def x [] = def
alookup def x ((a,w):aws)
   | x == a = w
   | otherwise = alookup def x aws

label n = modify
   (\(curra,mem,alllabels,acclabels          ) ->
     (curra,mem,alllabels,(n,curra):acclabels))

labeladdr n = do
   (_,_,alllabels,_) <- get
   return $ alookup 0 n alllabels

-- Этап 2 ==========================================================
   
cmd cop const = do
   addword cop
   addword const

cnop     = cmd 0  0
cdup     = cmd 1  0
cconst i = cmd 2  i
cplus    = cmd 3  0
cminus   = cmd 4  0
ccmp ord = cmd 5  (fromEnum ord)
cinput   = cmd 6  0
coutput  = cmd 7  0
cj     a = cmd 8  a -- версии, получающие адрес.
cb     a = cmd 9  a
cc     a = cmd 10 a
cret     = cmd 11 0 -- возврат из подпрограммы.
                    -- в decodemem это сигнализирует об останове.
                    -- stackprocessorf выполняет возврат из подпрограммы,
                    -- если на данном уровне больше команд нет (список пуст).

clabel c l = do
   a <- labeladdr l
   c a

cjl    l = clabel cj l -- версии, получающие метку.
cbl    l = clabel cb l
ccl    l = clabel cc l

-- Этап 3 ==========================================================

getmem program = reverse mem
   where
      (_,mem,_,alllabels) = execSM program (1024,[],alllabels,[])

decodemem a mem
   | stop = []
   | otherwise = cmd:decodemem (a+2) mem
   where
      cmd = case cop of
         1  -> Dup
         2  -> Const const
         3  -> Plus
         4  -> Minus
         5  -> Cmp $ toEnum const
         6  -> Input
         7  -> Output
         8  -> J $ decodemem const mem
         9  -> B $ decodemem const mem
         10 -> C $ decodemem const mem
         _  -> Nop -- Everything else including 0.
      cop = alookup 0 a mem
      stop = cop == 11
      const = alookup 0 (a+1) mem

-- Этап 4 ==========================================================

prog1mem = getmem $ do
   cconst 0
   label "loop1"
   inc 1
   cinput
   cconst prog1limit
   ccmp LT
   cbl "loop1"
   coutput
   cret
   where
      inc n = do
         cconst n
         cplus

stackprocessormemorydemo memory startaddr inputdelay = result
   where
      inputs = fromListS Nothing $
         concatMap (\x -> replicate inputdelay Nothing++[Just x]) [0..]
      program = decodemem startaddr memory
      (stop,output) = stackprocessor program inputs
      result =
         zip (toList inputs) $
         map snd $
         takeWhile (not . fst) $
         zip (toList stop) (toList output)
Итак, первый этап создаёт разного рода вспомогательные функции: тип монады, в которой мы будем писать наши ассемблерные программы, формирование памяти (addword), получение текущего адреса (curraddr - эквивалент $ в некоторых ассемблерах), поиск по ассоциативному списку (alookup), помещение метки в список меток с адресами (label), получение адреса метки (labaddr).

Метки мы помещаем в один список (acclabels, аккумулятор меток), а получаем из другого (alllabels).

Этап 2 задаёт кодирование команд. Некоторым из них необходим адрес, для них созданы варианты c*l - что-то с меткой.

Этап 3 создаёт образ памяти и позволяет преобразовать его обратно в программу стекового процессора. Обращаю внимание на положение alllabels слева и справа от оператора присваивания в getmem. Мы подаём на вход вычислений данные, которые мы получим в результате вычислений!

Это небольшой пример удобного использования ленивых вычислений. Все labaddr будут отложены и вычислены правильно тогда, когда это потребуется, уже после полного прогона getmem - когда alllabels, в свою очередь, будут полностью вычислены.

Этап 4 записывает нашу программу для стекового процессора в виде ассемблера. Функция inc - пример своего рода макроса для ассемблера, а на самом деле просто обычная функция языка Haskell. Главное, что её тип совпадает с типом составных частей нашего ассемблера.

stackprocessormemorydemo prog1mem 1024 задержка должен дать выход, совпадающий с выходом stackprocessordemo задержка.

Надо заметить, что в обычном честном процессоре память не столь быстра и декодировать команды придётся отдельно. Нам придётся выводить наружу запросы на выборку и обрабатывать ответы от памяти в функции управления. Нашу систему команд легко модифицировать для этого случая:
-- дополнение, в модуль StackProcessor не входит
data StackProcMemoryCmd =
      Nop -- Без no-op не обходится ни одна уважающая себя система команд.
   |  Dup -- дублировать верхушку стека данных.
   |  Const Int -- поместить константу на верхушку стека.
   |  Plus -- сложить два числа на вершине стека.
   |  Minus -- вычесть два числа на вершине стека. 
   |  Cmp Ordering -- Сравнить два значение на вершине на EQ/LT/GT.
                   -- Поместить 0 (ложь) или 0xFFFFFFFF (истина) на вершину стека
   |  Input -- поместить входное воздействие на верхушку стека. Ждать, если что.
   |  Output -- выдать наружу значение с верхушки стека.
   |  J Int -- безусловный переход.
   |  B Int -- переход по не-нулю на верхушке стека данных.
   |  C Int -- вызов подпрограммы.
   |  R     -- возврат из подпрограммы
   deriving Show
Далее вводим в состояние управляющей функции регистр PC и работаем, почти как прежде.

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

Чтение программ из ассемблерного текста

Задача настоящего ассемблера - получить образ памяти из её текстового описания. А всё для получения образа памяти у нас готово. Осталось только написать какой-никакой разборщик и соединить всё вместе.

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

В строке ассемблерного текста, однако, могут находиться и метка, и команда (и каждая из них по отдельности). В принципе, ничего сложного. Если нет метки (её название пусто) то мы ничего не делаем. Если нет команды (её название пусто или это комментарий) то мы тоже ничего не делаем. Остаётся только разобрать команды и их аргументы в функции parseasmline. Функция parseasmtext просто разобъёт текст на строки и применит parseasmline ко всем строкам текста.
-- Продолжение модуля StackProcessor.
parseasmline line = do
	case labelstr of
		"" -> return ()
                _  -> label labelstr
        asmcmd
   where
      isspace c = c <= ' '
      trim = dropWhile isspace
      rltrim l = reverse $ trim $ reverse $ trim l
      trimmed = trim line
      (labelstr,cmdline) = case span (/=':') trimmed of
         (l,':':cmdline) -> (l,trim cmdline)
         (_,_) -> ("",trimmed)
      noasmcmd = return ()
      labelled cmd label = cmd (rltrim label)
      asmcmd = case cmdline of
         "" -> noasmcmd
         (c:rest) -> case c of
            'd' -> cdup
            'C' -> cconst (read rest) -- автоматически преобразуем аргумент
            'p' -> cplus
            'm' -> cminus
                        -- то же самое, только в предикат.
            '?' -> ccmp ((read rest)::Ordering)
            'i' -> cinput
            'o' -> coutput
            'j' -> labelled cjl rest
            'b' -> labelled cbl rest
            'c' -> labelled ccl rest
            'r' -> cret
            '#' -> noasmcmd -- комментарий.
            x -> error $ "Invalid assembler line "++show line

parseasmtext text = getmem $ parselines $ lines text
   where
      parselines [] = return ()
      parselines (l:ls) = do
         parseasmline l
         parselines ls

prog1text =
      "       C 0\n"
   ++ "# Loop label (comment, you know)\n"
   ++ "loop1: C 1\n"
   ++ "       p\n"
   ++ "       i\n"
   ++ "       C 20\n"
   ++ "       ? LT\n"
   ++ "       b loop1\n"
   ++ "       o\n"
   ++ "       r\n"

prog1asmmem = parseasmtext prog1text
Вот.

Значение prog1asmmem должно совпадать со значением prog1mem. И оно совпадает, в этом легко убедиться.

Тема чтения исходных файлов немного выходит за рамки текущего обсуждения, однако вот пример:
-- дополнение, в модуль StackProcessor не входит.
parseasmfile fn = do
   text <- readFile fn
   return $ parseasmtext text
Вуаля!

Что я не использовал

Не использованные мною стандартные функции:
  • mapM из Prelude
  • isSpace из Data.Char
  • lookup из Data.List
  • Функции работы с состоянием State (get,put,modify) из Control.Monad.State
  • Data.Map вместо ассоциативного списка (empty,insert,lookup)
  • и много чего ещё.
Сам я стандартную библиотеку знаю не очень хорошо, несмотря на длительное использование Хаскеля в работе. По простой причине слабой необходимости в этом.

Я считаю это большим плюсом.
Tags: Хаскель, ассемблер, моделирование аппаратуры, стековые процессоры, типа книга, языки программирования
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 31 comments