「サイゼリヤで1000円あれば最大何kcal摂れるのか」を自作CPU上で解いてみた

サイゼリヤに1000円を持って食事に言ったとき、どの料理を頼めば最大何kcalの食事をすることができるかを、FPGAに構築した自作CPU上で計算しました。

自作CPU

学校の演習課題としてFPGA上でCPU（プロセッサ）を作成しました。具体的には、PowerMedusaボードを利用し、このボード上にあるFPGAをVerilogを用いてプロセッサとして動作させました。
5段パイプラインや簡易的な分岐予測（不成立）などが実装されています。

この演習では「SIMPLE」と呼ばれるアーキテクチャが予め与えられます。
SIMPLEアーキテクチャは16bit=1wordのワードマシンで、RISC的なISAを持っています¹。基本的にはこの仕様を満たすプロセッサを作成するのですが、必要に応じて自由に仕様を変更しても良いことになっています。私の班ではADDIやCMPIなどの即値演算命令を追加したほか、無条件分岐命令であるB命令のオペランドを8bit幅即値から11bit幅即値に変更するなどしました。

さらなる詳細を知りたい方は演習の説明ページを参照してください。また過去の同一演習について記載されたjoisinoさんのブログ記事も参考になるかと思います²（計算機科学実験及演習3ハードウェア（CPU製作）記）。

サイゼリヤ問題

「サイゼリヤに1000円を握りしめて食事に行ったとき、どの料理を食べれば最大カロリーを摂取できるか」という極めて実用的な問題です。以下では便宜上これを「サイゼリヤ問題」と呼ぶことにします。

単純な問題なだけに様々な解法が考えられ、量子アニーリング計算による解法・
SMTソルバーによる解法・整数計画法ソルバーによる解法・動的計画法による解法などがすでに見つかっています（関連記事も参照）。

この記事では、これらのうち特にShinyaKatoさんの動的計画法による解法を参考にして実装を行います。

実装

まず動的計画法を用いてC言語でこの問題を解きます。後々これを自作CPU上で動かすため、二次元配列などは使用せず、メモリを対象にする操作は全て1次元配列memに対して行うようにします。

さてShinyaKatoさんの実装ではDPテーブルを144×1001要素の（動的）配列として確保していますが、自作CPU上にはメモリが33Kワード程度しか無く、このテーブル全てを保存することは不可能です。そこでテーブルとして1001ワードのメモリ領域を2本確保し、これを交互に利用することで
DPを行います³。ただしこれだけの情報では「最大カロリー」及び「最大カロリーを摂取するために必要な金額」はわかりますが、「最大カロリーを摂取するために頼むべき料理」が分からず片手落ちです。そこでこのテーブルとは別に8192ワードのメモリ領域を2本用意し、
DPのテーブルを更新するのと同時に、どの料理を頼めばそのカロリーに達するかを保存しておきます。メモリ量の上限から7個以上の料理を保存することは不可能ですが、今回の問題では（既存の記事から）3つ程度保存すれば十分であることが分かっているので、これでよしとします。

また自作CPU上には十分な表示機構がないため、とりあえず計算結果はメモリ上の決められた番地に保存することにします。具体的にはアドレス0x0800に金額を、0x801にカロリーを、続くワードに頼むべき料理のIDを連続で格納します。

結果、およそ次のようなプログラムを書くことができます。

#include <assert.h>
#include <inttypes.h>
#include <stdint.h>
#include <stdio.h>

typedef uint16_t Word;

Word mem[0x5000];

enum {
    SAIZERIYA_CALORIE_ADDR = 0x400,
    SAIZERIYA_PRICE_ADDR = 0x500,
    SAIZERIYA_SIZE = 115,
    SAIZERIYA_BUDGET = 1000,
    P_ADDR = 0x0800,
    Q_ADDR = 0x0C00,
    PATH_P_ADDR = 0x1000,
    PATH_Q_ADDR = 0x3000
};

int lte(Word lhs, Word rhs)
{
    return (int16_t)lhs <= (int16_t)rhs;
}

Word routine()
{
    Word src = P_ADDR, dst = Q_ADDR;
    Word path_src = PATH_P_ADDR, path_dst = PATH_Q_ADDR;

    mem[src + 0] = 0;
    for (int i = 1; i <= SAIZERIYA_BUDGET; i++) mem[src + i] = 0x8000;  // -INF
    for (int i = PATH_P_ADDR; i < PATH_P_ADDR + (0x0400 << 3); i += 8)
        mem[i] = 0;

    for (int i = 0; i < SAIZERIYA_SIZE; i++) {
        for (int j = 0; j <= SAIZERIYA_BUDGET; j++) {
            Word val = mem[src + j];
            Word price_addr = SAIZERIYA_PRICE_ADDR + i;
            Word price = mem[price_addr];
            Word addr = src + j - price;

            for (int k = 0; k < 8; k++)
                mem[path_dst + (j << 3) + k] = mem[path_src + (j << 3) + k];

            if (lte(src, addr)) {
                Word val1 = mem[addr] + mem[SAIZERIYA_CALORIE_ADDR + i];
                if (lte(val, val1)) {
                    val = val1;

                    Word addr = path_src + ((j - price) << 3);
                    for (int k = 0; k < 8; k++)
                        mem[path_dst + (j << 3) + k] = mem[addr + k];

                    Word size = mem[addr];
                    size++;
                    assert(size != 8);
                    mem[path_dst + (j << 3) + size] = i;
                    mem[path_dst + (j << 3)] = size;
                }
            }
            mem[dst + j] = val;
        }

        Word tmp = src;
        src = dst;
        dst = tmp;

        tmp = path_src;
        path_src = path_dst;
        path_dst = tmp;
    }

    Word best_price = 0, best_calorie = 0;
    for (int i = 0; i <= SAIZERIYA_BUDGET; i++) {
        Word calorie = mem[src + i];
        if (lte(best_calorie, calorie)) {
            best_calorie = calorie;
            best_price = i;
        }
    }
    Word best_path_addr = path_src + (best_price << 3);
    Word best_path_size = mem[best_path_addr];
    mem[P_ADDR] = best_price;
    mem[P_ADDR + 1] = best_calorie;
    for (int k = 0; k < 8; k++) {
        if (k >= best_path_size) break;
        mem[P_ADDR + (k + 2)] = mem[best_path_addr + k + 1];
    }

    return P_ADDR;
}

int main()
{
#include "saizeriya.inc"
    uint16_t src_index = routine();
    for (int i = 0; i < 0x4000; i++) {
        printf("%04X : %04" PRIX16 "\n", src_index + i, mem[src_index + i]);
    }
}

なお途中で#includeしているsaizeriya.incには、配列mem上に料理データを読み込むための
C言語コードが次のように記載されています。このデータは「サイゼリヤ1000円ガチャ」さんのGitHubレポジトリ（Saizeriya_1000yen）よりお借りし作成しました。

mem[SAIZERIYA_CALORIE_ADDR + 0] = 0;
mem[SAIZERIYA_CALORIE_ADDR + 1] = 130;
mem[SAIZERIYA_CALORIE_ADDR + 2] = 115;
mem[SAIZERIYA_CALORIE_ADDR + 3] = 134;
mem[SAIZERIYA_CALORIE_ADDR + 4] = 92;
// 中略
mem[SAIZERIYA_CALORIE_ADDR + 111] = 216;
mem[SAIZERIYA_CALORIE_ADDR + 112] = 166;
mem[SAIZERIYA_CALORIE_ADDR + 113] = 162;
mem[SAIZERIYA_CALORIE_ADDR + 114] = 164;

mem[SAIZERIYA_PRICE_ADDR + 0] = 0x7FFF; // INF
mem[SAIZERIYA_PRICE_ADDR + 1] = 299;
mem[SAIZERIYA_PRICE_ADDR + 2] = 349;
mem[SAIZERIYA_PRICE_ADDR + 3] = 299;
mem[SAIZERIYA_PRICE_ADDR + 4] = 299;
// 中略
mem[SAIZERIYA_PRICE_ADDR + 111] = 249;
mem[SAIZERIYA_PRICE_ADDR + 112] = 299;
mem[SAIZERIYA_PRICE_ADDR + 113] = 299;
mem[SAIZERIYA_PRICE_ADDR + 114] = 369;

次に、このC言語コードをSIMPLEアセンブリに変換する必要がありますが、この規模のコードでもハンドアセンブルは骨がおれます⁴。そこで簡易的なコンパイラを作成してアセンブリを生成しました。具体的には、まず上記のコードを次のような形に書き直します。

int SAIZERIYA_CALORIE_ADDR, SAIZERIYA_PRICE_ADDR, SAIZERIYA_SIZE,
    SAIZERIYA_BUDGET;
SAIZERIYA_CALORIE_ADDR = (4 << 8);  // 0x400
SAIZERIYA_PRICE_ADDR = (5 << 8);    // 0x500
SAIZERIYA_SIZE = 115;
SAIZERIYA_BUDGET = (125 << 3);  // 1000

int P_ADDR, Q_ADDR, PATH_P_ADDR, PATH_Q_ADDR;
P_ADDR = (8 << 8);          // 0x0800
Q_ADDR = (12 << 8);         // 0x0C00
PATH_P_ADDR = (0x10 << 8);  // 0x1000
PATH_Q_ADDR = (0x30 << 8);  // 0x3000

int src, dst, path_src, path_dst;
src = P_ADDR;
dst = Q_ADDR;
path_src = PATH_P_ADDR;
path_dst = PATH_Q_ADDR;

int MINF;
MINF = (8 << 12);  // 0x8000 == -INF

{
    // initialize memory
    int i, size;
    mem[src] = 0;
    for (i = 1; i <= SAIZERIYA_BUDGET; i = i + 1) mem[src + i] = MINF;
    size = PATH_P_ADDR + (4 << 11);
    for (i = PATH_P_ADDR; i < size; i = i + 8) mem[i] = 0;
}

{
    int i;
    for (i = 0; i < SAIZERIYA_SIZE; i = i + 1) {
        int j;
        for (j = 0; j <= SAIZERIYA_BUDGET; j = j + 1) {
            int val, price_addr, price, addr, dst_path_addr_base;
            val = mem[src + j];
            price_addr = SAIZERIYA_PRICE_ADDR + i;
            price = mem[price_addr];
            addr = src + j - price;
            dst_path_addr_base = path_dst + (j << 3);

            {
                int k, src_path_addr_base;
                src_path_addr_base = path_src + (j << 3);
                for (k = 0; k < 8; k = k + 1)
                    mem[dst_path_addr_base + k] = mem[src_path_addr_base + k];
            }

            if (src <= addr) {
                int val1;
                val1 = mem[addr] + mem[SAIZERIYA_CALORIE_ADDR + i];
                if (val <= val1) {
                    val = val1;

                    int addr, k;
                    addr = path_src + ((j - price) << 3);
                    for (k = 0; k < 8; k = k + 1)
                        mem[dst_path_addr_base + k] = mem[addr + k];

                    int size;
                    size = mem[addr] + 1;
                    mem[dst_path_addr_base + size] = i;
                    mem[dst_path_addr_base] = size;
                }
            }

            mem[dst + j] = val;
        }

        int tmp;
        tmp = src;
        src = dst;
        dst = tmp;

        tmp = path_src;
        path_src = path_dst;
        path_dst = tmp;
    }
}

{
    int i, best_price, best_calorie;
    best_price = 0;
    best_calorie = 0;
    for (i = 0; i <= SAIZERIYA_BUDGET; i = i + 1) {
        int calorie;
        calorie = mem[src + i];
        if (best_calorie <= calorie) {
            best_calorie = calorie;
            best_price = i;
        }
    }

    int best_path_addr, best_path_size;
    best_path_addr = path_src + (best_price << 3);
    best_path_size = mem[best_path_addr];
    mem[P_ADDR] = best_price;
    mem[P_ADDR + 1] = best_calorie;
    int k;
    for (k = 0; k < 8; k = k + 1) {
        if (k < best_path_size) {
            mem[P_ADDR + k + 2] = mem[best_path_addr + k + 1];
        }
    }
}

{
    // set the result to registers
    //__builtin_output(mem[P_ADDR]);
    int res0, res1, res2, res3, res4;
    res0 = mem[P_ADDR + 0];
    res1 = mem[P_ADDR + 1];
    res2 = mem[P_ADDR + 2];
    res3 = mem[P_ADDR + 3];
    res4 = mem[P_ADDR + 4];
    __builtin_load(R3, res0);
    __builtin_load(R4, res1);
    __builtin_load(R5, res2);
    __builtin_load(R6, res3);
    __builtin_load(R7, res4);
}

__builtin_halt();

およそ先程のコードと同じですが、コンパイラデザインを極力簡単にするため、一部冗長な書き方をしています⁵。また、このコードの末尾では__builtin_load()を連続して用いることで、得た結果をレジスタに読み込んでいます。これによりデバッグ用の7SEG
LEDに結果を表示することができます（後述します）。

さて、次にこれを受理してアセンブリを生成するためのコンパイラを作成します⁶。そのコンパイラにこの入力を与えて、以下のようなアセンブリを出力として得ることができます⁷。

    define SP R0
    LI SP, 0
    LI R1, 4
    SLL R1, 8
    ST R1, 0(SP)
    LI R1, 5
    SLL R1, 8
    ST R1, 1(SP)
    LI R1, 115
    ST R1, 2(SP)
## 中略
    LD R1, (R1)
    ST R1, 39(SP)
    LD R1, 4(SP)
    LI R2, 4
    ADD R1, R2
    LD R1, (R1)
    ST R1, 40(SP)
    LD R3, 36(SP)
    LD R4, 37(SP)
    LD R5, 38(SP)
    LD R6, 39(SP)
    LD R7, 40(SP)
    HLT

先程述べたコード末尾の__builtin_load()がLD命令として展開されていることがわかります。

最後にこの生成されたアセンブリコードをマクロアセンブラとアセンブラに通し、次のようなMIF
(Memory Initialization File)形式として出力させます。

0000 : 8000;
0001 : 8104;
0002 : C188;
0003 : 4800;
0004 : 8105;
-- 中略
0141 : D100;
0142 : 0900;
0143 : 4828;
0144 : 1824;
0145 : 2025;
0146 : 2826;
0147 : 3027;
0148 : 3828;
0149 : C0F0;

これを命令メモリに書き込んでFPGAを始動させると、プロセッサがサイゼリヤ問題を解決してくれます⁸。

結果

実際に実行すると、次のように表示されました。

上記画像にもあるように結果は次のようになりました。

最大カロリー　1940kcal
使用金額　992円
頼む料理　3品
- ポテトのグリル　199円　366kcal
- アーリオ・オーリオ(Wサイズ)　574円　1120kcal
- ラージライス　219円　454kcal

イメージ画像

せっかく計算したので、実際にサイゼリヤ百万遍店で注文してみました。

「ポテトのグリル」のみ現行のメニューには記載されていなかったため頼めず「アーリオ・オーリオ(Wサイズ)」と「ラージライス」のみを注文しました。それでも計1486kcalで793円です。全部食べきって場所を移し、いまこの記事を書いています。とりあえず私から言えることは、二度と同じようなチャレンジをしたくありません。体を大切に^9,¹⁰。

感想など

本文中につけた脚注を見てください。

コードなど

サイゼリヤ問題のために作成したコードと、それを動かすためのコンパイラ・マクロアセンブラ・アセンブラ・エミュレータなどはここから入手することが出来ます。プロセッサのコードは演習が終わり次第どこかに上げたり上げなかったりするかも知れません。

この演習では作成したプロセッサの外部仕様がオリジナルのSIMPLEアーキテクチャを包含していることのみが求められます。そのためプロセッサの内部仕様についてはある程度自由がききます。そこで私の班では、回路を簡単にするためハーバード・アーキテクチャを採用しました。したがってこの記事で登場するmemはすべてデータメモリのことをさし、そのどこにもプログラム自体は格納されていません。↩
この演習における全班共通の目標として「1024個の整数値のソート」が設定されています。joisinoさんの班はこのソートコンテストにおいて0.05040msを叩き出し、その年度の2位と10倍の差をつけて優勝しました。「計算機科学実験及演習3ハードウェア（CPU製作）記」にはこのときのことが書かれておりとても面白いので、ご一読をおすすめします。なおこの記録は未だに正攻法では破られていませんが、今年度組み合わせ回路によって「ソート回路」を作成した班が0.04611msを出し、参考記録ではありますが現在暫定1位になっています。詳細を知りたい方はソート速度コンテストのページを参照してください↩
この手法など動的計画法の一般論については『問題解決のアルゴリズム活用力とコーディングテクニックを鍛える
プログラミングコンテストチャレンジブック　第2版』（秋葉拓哉・岩田陽一・北川宜稔、マイナビ、2012）を参考にしました。↩
実際マクロアセンブラを拡張しハンドアセンブルをしやすくした状態でも、上記C言語コードをアセンブリに変換することはできませんでした――正確には、書くことはできたのですが、正常に動作しませんでした。一応簡易的なデバッガを作っていたのでそれで追いかけることもできたのですが、令和に人がやるべき作業ではないと思ったので、代わりにコンパイラを書き始めました。↩
例えばSIMPLEのISAでは即値読み込み命令であるLI命令が8bit符号付き即値しか取れないためSAIZERIYA_BUDGETに1000を代入するためにSAIZERIYA_BUDGET = (125 << 3)と記述しています。またi++やi += 1などの実装も省略するためi = i + 1と記述しています。このように制限した機能しかありませんが、それでもアセンブリと比べれば圧倒的に記述が楽でした。↩
過去にCコンパイラのサブセットを書いた経験が幸いして、このコンパイラ自体はそれほど時間がかからず作成することができました。↩
今回作成したコンパイラではレジスタ割当を（ほとんど）行っていません。したがってすべての変数は必ずメモリ上に領域確保がなされます。例えばa
= a + bではi) aをメモリから読み出し ii) bをメモリから読み出し iii)
それらを足し合わせ iv)
結果をメモリ上のaに格納する、といった手順を踏むことになり、見かけ4クロックサイクルで処理が済むように見えます。しかし実際はiii)の処理を行うためにはii)でメモリから読み出した値を使う必要があり、それは1サイクル余計に使わなければ入手することができません（データストール）。したがって実際は5サイクル要することになります。これを回避するにはコンパイラ側で命令の並び替えを行うか、あるいはプロセッサ側でアウト・オブ・オーダ実行などを行う必要があります。↩
サラッと書いていますが、正常に動くまでにはかなり時間がかかりました。コンパイラやアセンブラの開発はテストを利用して行ったため、問題があるのはおそらくプロセッサだろうということがわかっていました。しかし実機上ではメモリの状態とレジスタの状態が部分的に分かるだけのため、遅々としてデバッグが進みません。データをFPGAに流し込もうとするとQuartusが2回に1回異常終了するのにも困りました。仕方がないので回路の遅延を含めシミュレーションしてくれるGate
Level
Simulationを行うと、今度はシミュレーションに時間がかかりすぎるため実用に耐えません。ではRTL
SimulationはというとQuartusとModelSimが受け付けるSystemVerilogの文法が異なりコンパイルが通りません。なんとかこれを直してシミュレーションを行い、パイプラインのせいでタイムリープが起こっているかのような波形をうんざりするほど眺めて、結局間違っていたのは算術命令が設定するオーバーフローフラグでした。神は細部にやどる。知らんけど。↩
吐きそう。↩
しかもすでに「実際に食べてみる」ネタはより完全な形で既出でした。私の苦労は一体。↩