RISC Vに従うCPUの上で動作するOSをRustで書く（CPU実験余興）

お手製のCPUの上で自分で作ったOSを動かすというのは、割と夢のある行為だと思っていて、今回それを一定のレベルですることができたので、簡単に内容についてメモをしておこうと思います。

曖昧な日本語を読むより、プログラムを読むほうが速いと思う人は、駄文を読まずにGitHubを見てください。

僕が書いたのはOSだけで、コアはATPが書きました。また、乗算命令の実装はdaiが書きました。

概要

RustでフルスクラッチでRISC-V(rv32im)で動作するOSの実装をしました。OSを実装するにあたり、ページングやカーネルとユーザーモードでの権限切り分け、割り込みなどの仕様を考える必要があり、これもRISC-VのPrivilegeの仕様書に従ったものにしました。仕様自体は、RISC-Vの仕様書にあって実装されていないものはあるかもしれないが、実装したものの仕様でRISC-Vの仕様には無いようなものはない（すなわち独自に導入した仕様は存在しない）です。ページングは具体的にはSv32の方式を実装しました。

実装したOSの主な機能は、

ブートローダー
Memory mappedなUART入出力
RISC-VのPrivileged Architecture、Sv32に従ったPaging
Supervisor ModeとUser Modeの権限分離
ELFファイルのパースとプロセス管理
clock割り込みによるpreemptive multitasking
trapのハンドリング
Copy on Write fork
fork, execve, exit, mmapなどのシステムコールの実装
プロセス間通信
簡易的なファイルシステム

です。

また、これらのカーネルの機能を用いたUserモードで動作するアプリケーションとしてシェルを作成しました。このプログラム自体は簡易なものですが、一般的なLinuxにおけるシェルと同様の工程(fork, execve, wait, exit)を行うことで子プロセスを起動し実行できるようになっています。すなわち、この工程が少なくともできる程度のレベルでOSを実装したという感じです。

RISC-Vとは

ググったほうが速いと思います。最近話題のオープン・アーキテクチャのISAで、基本的にはMIPSに似ていると思いますが、所々の負の遺産が無くなった洗練されたRISCのISAになっていると思います*1 。

そもそもx86のようなCISCのコアを書くのは厳しく、今回のように全く新しくOSを遊びで作ってFPGAで動かそうと思った時、RISC-Vを選ぶのは自然な選択だと思います。ツール周りとしては、gccやllvmバックエンドなどのコンパイラ基盤は既に存在していて、また今回は自作のものを使用したので使いませんでしたが、エミュレータもSpikeなどがあるようです。

なぜRust?

世の中のカーネルの上に存在する脆弱性の原因の大きな一因として、配列外参照や型エラーのような問題があり、Rustを使うことで、より強い静的な検査により安全性の高いOSを作ることができます。もちろん、OSを作る上でunsafeなfeatureを使わざるをえない部分は出てくるため、一般的なRustのプログラムを書く時ほどではないかもしれませんが、しかしunsafeな処理というのを他と区別することができ、unsafeを極力少なくすることで、不安定な部分に注力することができるようになると言えます。

さらに言えば、stdの機能が使えないにせよ、IteratorやResult/Optionおよびパターンマッチ、traitなどの機能を使うことができ、より洗練されたコードを書くことができると言えます。

まぁ以上のような利点があると前置きした上で、今回書く言語にRustを採用したのは僕の趣味です。

実装について

実装する上で少々苦労した点、真面目に実装した点などをメモします。

ISAとそれをターゲットにしたRustプログラムのビルド

割とここは本質です。Rustは昨年からRISC-Vのtargetを公式にサポートしています。しかし、RISC-VのISAはいくつかのベース(rv32i, rv64i..)に、Extensionを追加することで定義されるので、一口にRISC-Vといっても様々なヴァリアントが存在することになります。

今回OSを動かすにあたって使用したコアは、もともとCPU実験本流のレイトレーシングプログラムを動作させるために作ったものをベースとしたので、32bitのアーキテクチャであり、その場合現時点で公式にサポートされているISAはrv32imac, rv32imcの２つでした。mはInteger Multiplication and Division、aはAtomic Instructions、cはCompressed Instructions に関するExtensionが追加されていることをそれぞれ意味しています。

今回、さすがにマルチコアのCPU（RISC-Vで言うところの複数のhartsが存在するCPU）を作るのは厳しいよねという話にはなったので、Atomic命令は実装しないことにしました。さらに、今回Compressed命令も削るという話になりました。Compressed命令というのは頻度の高い命令で、頻度の高い即値(0のような)やレジスタ(zeroレジスタのような）に絞った16ビットの命令の集合です。RISC-Vの仕様書によれば、これらの命令で、一般的なプログラム全体の50-60%程度を構成できるそうで、結果として、コードサイズを25-30%程度減らすことが可能になります。

後から考えると、コアにCompressed命令を追加するのはDecoderと命令フェッチの部分をいじるだけなのでそれほど大変ではなかった可能性はありますが、後に説明するMMUやCSR(Control and Status Regsiter)の処理などの実装があることを考えると、命令セットで可能な処理としては等価であることを考えれば、Compressed命令も無くしてできる限り単純化したいという気持ちになります。

その場合上述した通り、公式にはrv32imというようなターゲットは存在しないので、自分でクロスコンパイルのビルド環境を整える必要があり、これに関しては上述のWriting an OS in Rustや公式ドキュメント、The Embedded Rust Book、およびRustでRISC-V OS自作！はじめの一歩を参考に、xargo/xcargoを用いたビルド環境を整えました。詳しくは、前に書いた記事や、実際のリポジトリを見てください。

これにより、standard libraryなしでのビルドが可能になります。

Privilege Architectureについて

RISC-VのPrivilege Architectureの仕様書に沿う形で実装がなされています。これによると、RISC-Vのprivilege levelsは現状全部でMachine/Supervisor/Userの3つであり、いかなるハードウェアもいかなる権限も持つMachineモードを実装しなければならない、となっています。

ところで、今回は、ページングの実装をしたかったので、Supervisorモードも必須でこの場合M-S-Uのすべてのモードを実装する必要があります。しかし、今回は単純化のため、マシンは起動直後にただちにでSupervisorモードに移行し、割り込み命令は、常にdelegate bitが立っていると考え、すべてSupervisorで処理されるものという実装になっています。

SupervisorのCSRはほぼすべて利用しており、これに対するcsrrw/csrrc/csrrsなどの命令や、sret、ecallがSystem系命令になり、これらをATPがコアに実装したのでそれを使っています。

UART入出力周り

入出力に関してはUARTを使おうと決めていたので、UARTを用いた入出力処理をまずは書くことになると思います。UARTはメモリマップドにしたので、1byteずつ特定のメモリに書き込んだり読み込めば終わる話ですが、もう少しリッチに出力がしたくなります。そのために、print!マクロやprintln!マクロを実装し、普通のRustでやるようなフォーマット出力などができるようにします。

Rustは、 core::fmt::Write トレイトを実装すれば、かなり容易に実現できます（0x80000000は今回取り決めたUARTの入力アドレスです）。

use core::fmt::Write;

const UART_RX: *const u8 = 0x80000000 as *const u8;
const UART_TX: *mut u8 = 0x80000004 as *mut u8;

struct UART;

fn write_byte(byte: u8) {
    unsafe {
        *UART_TX = byte;
    }
}

impl Write for UART {
    fn write_str(&mut self, s: &str) -> core::fmt::Result {
        for c in s.bytes() {
            write_byte(c);
        }
        Ok(())
    }
}

pub fn print(arg: ::core::fmt::Arguments) {
    UART.write_fmt(arg).expect("failed to send by UART");
}

#[macro_export]
macro_rules! print {
    ($($arg:tt)*) => ($crate::uart::print(format_args!($($arg)*)));
}
#[macro_export]
macro_rules! println {
    () => (print!("\n"));
    ($arg:expr) => (print!(concat!($arg, "\n")));
    ($fmt:expr, $($arg:tt)*) => (print!(concat!($fmt, "\n"), $($arg)*));
}

ページング

RISC-Vにはページングに関する仕様が存在します。今回の実装は32bitなので、選択肢は一つでSv32がそれにあたります。非常に大雑把に説明すれば、Superpageを無視すれば、仮想アドレスの上位10bit、次の10bitを用いて二回テーブルを引き、引いた最後のテーブルのエントリと仮想アドレスの下位12bitのオフセットを足し合わせることで実際の物理アドレスを得るという2段のジャンプを行う形式になっています。詳しい仕様は、当然仕様書を見れば分かりますし、日本語ではmsyksphinz さんがいろいろとエントリを書いていらっしゃるのでそちらを見ると良いと思います。

今回実装するにあたり、メモリアドレス変換を入れた後で途中のページテーブルにアクセスする方法に少し苦労したのでこれについてメモをします。

まず上で書いたように仮想アドレスを物理アドレスに変換するにあたって、二回テーブルを引くことになります（ここでSuperpageは考えません）が、このテーブルを前から順にT0, T1とします。このとき、ページングの実装として問題になるのは、MMUをonにした後で途中のT1のテーブルにアクセスするのが難しいという点です。というのも、T0のテーブルは今回プロセスの数だけ起動時に用意したため、テーブルへの仮想アドレスはすでに分かっていますが、T1のテーブルは動的に割り当てる（起動時にすべてのメモリをカーネルのページ空間にマップしない）ので、そのテーブルへの物理アドレスは分かっていても、アクセスするための仮想アドレスは、定義されていないのでアクセスすることができない状態になっています。

これに対処するための手段として、例えばx86では、T0のテーブルの一つのエントリを、T0自身に割り当てることで、MMUの2回のページテーブルの遷移を打ち消すことができるという手法が存在します（Recursive pagingなどというと思います）。実際x86のページングではこれによりかなり効率良く、すなわち無駄になるアドレス空間、及び実際のメモリは最小限にして、途中のテーブルにアクセスが可能になります。

ところで、Sv32の仕様を読むと分かるように、Sv32では各ページのテーブルエントリが、Leaf、すなわち次に示すのが変換先の物理アドレスのページの先頭であるか、それとも次のページテーブルへのポインタであるかのどちらかであると定義されています。そして、2回より多くの遷移を行おうとした場合それはPageFaultになってしまうと思われます（ここらへんなにか理解を間違えていたら教えていただきたいですが）。

すると上のようなRecursiveエントリを作るという手法は使うことができないことがわかります。なぜならば、アクセスしようとしているテーブルを指すページテーブルエントリは、Leafではないからです。これに対処するため、T0のページと対になるもう一つのテーブルT0'を事前に用意し、T0の一つのエントリをそのテーブルにマップするようにし、それ以外のエントリは、T0とT0'ともに同じになるようにするという方法で上述の処理を実現しました（下図）。

f:id:moratorium08:20190302191743p:plain:w450

この方式はRecursiveなページエントリを用いる方式に比べて、メモリをPAGESIZE分余計に消費するが、しかし同等の機能を得ることができていると言えます。とはいえあまり綺麗な方法でもないので、ここらへん詳しい方がいて見ていたら教えていただけると助かります。

ELFのパース

RustにはgoblinというELFパースをするzero-copyなライブラリがありますが、同期命令の関係上今回使用することができなかったので、自分で簡単なパースをしました。

ELFはメモリの上に乗せればただちにパースしやすい構造になっているので、以下のように構造体を作れば、（少々チェックが足りないかもしれませんが）構造をそのまま取り出せます。

#[derive(Debug)]
#[repr(C)]
pub struct ElfHeader {
    pub magic: u32,
    pub elf: [u8; 12],
    pub etype: u16,
    pub machine: u16,
    pub version: u32,
    pub entry: u32,
    pub phoff: u32,
    pub shoff: u32,
    pub flags: u32,
    pub size: u16,
    pub phentsize: u16,
    pub phnum: u16,
    pub shentsize: u16,
    pub shnum: u16,
    pub shstrndx: u16,
}

/*...*/

    pub fn new(bytes: *const [u8]) -> Result<Elf<'a>, ElfError> {
        let bytes = unsafe { &*bytes };
        let elf = unsafe {
            let data: *const ElfHeader = bytes.as_ptr() as *const ElfHeader;
            &*(data)
        };
        if elf.magic != ELF_MAGIC {
            return Err(ElfError::InvalidMagic);
        }
        Ok(Elf { bytes, elf })

詳しくは、ソースコードを見てください。ここらへんの話はまぁ特定の界隈的には常識かもしれません。

Copy on Write fork

Copy on Writeなforkを実装したという話です*2 。

新しいプロセスを作る上で必要になるのが、現行のプロセスから、メモリの状態が全く同じでクローンされた別のプロセスを作る操作、すなわちforkです。

この実現には、プロセスのメモリ全体をコピーする操作が必要となります。ここで、マップされているすべてのメモリをコピーすることでも当然実現可能ですが、これは大量のメモリアクセスを発生させる非常にコストの高い操作になってしまいます。

これをある程度緩和させる手段として、ページテーブルをコピーして、書き込み可能なページに、Copy on Writeフラグを立て、その後fork前とfork後のいずれかのプロセスでそのメモリに書き込みが起こったときに、実際にコピーを実行する、というCopy on Writeの方式を取ることでメモリのコピーを遅延評価することができるという方法です。これは、forkが起こった後の処理として多くの場合、execveというアドレス空間を大きく書き換える処理が発生するので、書き換えられることのないページを余計にコピーすることが無くなり、効率が良くなることが期待されます。

f:id:moratorium08:20190302191736p:plain:w450

今回、Copy on Write forkを実装するにあたっては、ページテーブルのエントリのRSWの1bitを利用しています。

f:id:moratorium08:20190302222319p:plain:w450

trapのハンドルとpreemptive multitasking

上述のように、すべての割り込みはSupervisorがキャッチするようになっているので、以下利用するCSR(Control and Status Register)はすべてSupervisorのものになります。

まず、trapをハンドルするためには、trapが発生したときに移行する命令アドレスを設定しておく必要があります。そのためにSTVECというCSRにそのアドレスを設定します。なお、今回はVectoredモードではなくDirectモードを利用しています。

設定をすると、trap時にプログラムカウンタが設定された値になり、ここからTrapFrameを操作する処理をします。このとき、割り込み用のスタックに移動するとともに、Userモードのレジスタの退避をします。このとき、レジスタの一時退避用にsscratchというCSRを利用します。また、このトラップが発生したときのプログラムカウンタはsepcに入っているのでこれを保存します。

https://github.com/moratorium08/osmium/blob/master/kernel/src/trap.rs#L394-L437

その後、scause及びstvalの値を見て、トラップを適切にハンドリングします。

また、カーネルから元のユーザーモードに戻るには基本的に同様の処理を逆向きに行えば良く、すべてのレジスタを適切に設定し、specに戻り先のユーザープログラムのプログラムカウンタを設定した上でsretをします。

https://github.com/moratorium08/osmium/blob/master/kernel/src/trap.rs#L461-L544

クロック割り込みは上述のtrapの仕組みにより得られるものの一つです。RISC-Vでは、mtime, mtimecmpという2つのメモリマップドなレジスタを利用してタイマー割り込みを制御します。クロック割り込みを受けたときの流れは単純で、現状動いているプロセスをRunnnableな状態にして、別のRunnableなプロセスを実行に移すという処理をします。かっこいいスケジューリングを実装している余裕は無かったので、単純に直近で最もRunnableかどうかをチェックしていないものから順にRunnableかどうかをチェックしていき、最初に見つかったものをRunningにするという処理をしています。

https://github.com/moratorium08/osmium/blob/master/kernel/src/trap.rs#L340-L345

https://github.com/moratorium08/osmium/blob/master/kernel/src/proc.rs#L260-L279

プロセス間通信

プロセス間通信の一般的な手法として、通信用のキューに対する出し入れ、いわゆるメッセージパッシングと、同一物理メモリを共有するメモリシェアリングの２つの方式があります。今回それらを両方実装しました。

メッセージパッシングを用いた方法は、（コアの下図が増えるとcatch line bouncingの影響が強くなることなどがあり一概には言えないそう（Operating System Concepts)だが）、基本的には、プロセス間通信をするために毎度プロセス間通信のシステムコールを呼び出す必要があり、メモリシェアリングの方法に比べると、大量のデータをやりとりする場合は低速になります。今回の設計は、基本的にxv6の方法にかなり影響を受けていて、メッセージを受け取るMailboxを各プロセスが持ち、そのMailboxからデータを取り出すことができるプロセスは一つのみ、対して、そのMailboxにデータを送ることができるプロセスは多数になっています。また、Mailboxへのデータの送信とそのデータの受信は非同期的になっていて、特定のプロセスのIDとデータを送信し、実際にデータを受信したかどうかなどの同期は別途メッセージシェアリングの仕組みを用いてとる必要があるものになっています。

プロセス間の同期処理は基本的にこのメッセージパッシングを用いて行うものと仮定し、大規模なデータのやりとりに関しては、同一物理メモリを多数のプロセスが共有するメモリシェアリングを用いて行います。メモリシェアリング自体は、最初にシステムコールを一度呼べば確立ができ、データのやりとりがメモリの書き込み読み込みで可能になるので、システムコールを介さずに行うことができ高速になります。

まず、プロセス間通信を用いた遊びプログラムとして、catch_ball.rs があります。このプログラムでは、まずメッセージパッシングを用いてデータのやりとりをした後、メモリシェアリングを用いて交互に特定のメモリ領域にあるデータを操作しています。

ファイルシステム（簡易）

報告会(2/19)の時点では、流石にファイルシステムを実装している余裕が無かった（悲しい）ので、execveなどで利用するファイルのサーバーとしては、静的にファイルを登録した上で、名前一致でデータを取り出すというかなり簡易なものになっていました。さすがにこれでは悲しいという気持ちになったので、報告会後に多少まともなファイルシステムを作り始めました。

マイクロカーネルと一般に呼ばれるカーネルは、以上のような「メモリ・アドレス空間管理」、「プロセス管理」、「プロセス間通信」などという基本的な機能をカーネル側の権限で実装した上で、ユーザーランドで動作するプログラムによってファイルシステムやネットワークなどの機能を提供します。このOSでもその設計方針に則っています。

ファイルシステムの仕様は独自のものなので簡単に説明すると、一般的なファイルシステムと同様にブロックごとに管理をしていて、一番先頭のブロックにファイルシステムの情報を持つスーパーブロック、その次からどのブロックが使われているかを管理するマネージメントブロックが続き、その後ろに実際にデータを保存するブロックが続きます。

現状は、ファイルシステムは、レギュラーファイルとディレクトリの二種類のデータを管理していて、ディレクトリは再帰的にこれらを内包しています。

レギュラーファイル、ディレクトリはそれぞれ自分自身のメタデータを持つ領域を持ち、実際のデータへの二段間接ポインタを持ちます。例えばレギュラーファイルは以下のように、テーブルを二度辿ることで実際のデータへアクセスできるようになっています

f:id:moratorium08:20190317130346p:plain:w450

ディレクトリは、同様の構造で、自分が配下に持つファイルへのポインタを保持します。

ディスクのフォーマッタは、 Pythonで書きました。まぁここまで書いておいてなんなんですが（書きながら作っていたんですが）、ファイルシステム周りの機能は用意した（ファイルはosmium/fs にあります）んですが、疲れてきてしまってOSにこれを組み込むところまでしていません。一人でやっていると寂しいので、誰か一緒にやってくれる人がいるといいですね（ほんまか）。まぁそのうちちゃんと実装すると思います。

システムコール

RISC-Vでは、Environment Callと言い、ecallという命令を用いることでEnvironment Call のExceptionを起こすことができます。システムコールの引数はa0, a1, ..で扱い、返り値はa0で返すという典型的な実装になっています。

シェル

以上の機能を体現できるユーザープログラムとして、シェルがあります。時間も無かったので最も基本的な機能しか積まれていませんが、fork -> execve -> exitという最も基本的なシェルの処理の流れを実際に行うことができるようにはなっていています。

pub extern "C" fn _start() -> ! {
    let mut buf = [0u8; 256];
    println!("** Osh **");
    loop {
        print!("$ ");
        let (len, b) = uart::buffered_readline(&mut buf);
        if len == 0 {
            continue;
        }
        if !b {
            println!("Sorry. too long. Please enter shorter command");
            continue;
        }
        let cmd = match str::from_utf8(&buf) {
            Ok(s) => s,
            Err(_) => {
                println!("Failed to parse your input. Try again.");
                continue;
            }
        };
        if buf[0] == b'e' && buf[1] == b'x' && buf[2] == b'i' && buf[3] == b't'  && len == 4{
            syscall::sys_exit(0);
        }
        match syscall::sys_fork() {
            syscall::ForkResult::Parent(id) => {
                loop {
                    match syscall::sys_check_process_status(id) {
                        syscall::ProcessStatus::Running | syscall::ProcessStatus::Runnable => {
                            syscall::sys_yield();
                        },
                        _ => {
                            break;
                        }
                    }
                }
            },
            syscall::ForkResult::Fail => {
                println!("fork failed");
            },
            syscall::ForkResult::Child => {
                syscall::sys_execve(cmd, len as u32, &[], &[]);
            }
        }
    }
}

エミュレータ上の動作

以上に実装したことについてつらつらと書きましたが、エミュレータの上で動作させることができるので、もし暇があればやってみてください。dockerが入っていれば

docker run -it moratorium08/osmium

で実行できます。ビルド環境の上に作ったイメージなので、割とでかくて、ダウンロードにはそれなりに時間かかると思います。

まぁもっとも、絵面はあまり面白くないと思います（以下の実装が動作していることが確認できます）。

感想

実装周りで特筆すべき内容は基本的に以上になります。ネットワーク周りについては何もしていないので、ここもきちんとできるとよりユーザー側でできることが増えるので良さそうです。さらに言えば、現状絵面的にはあまりおもしろくないと思うので、VGAだったりを使えるようにして、ウィンドウシステム実装したりしたらかなり楽しそうですね。まぁあと細部が雑（メモリallocしたは良いが回収していない、プロセスを回収できない、権限周りがだめなどなど）なので、ちゃんとしたらよりしゃきっとしたOSになるんじゃないでしょうか

自分のOSに関する知識のバックグラウンドとしては、

UnixV6のソースコードを読んだ
MITのxv6のコースの課題を一通り解いた
Rustのblog_os を読んだ（＆言われるがままに実装した）
理学部情報科学科のシステムプログラミング実験（livaさんのやつ）をした（＆オペレーティングシステムの授業を受けた）

程度で、一度もOSを自分で実装したことが無かったので、良い経験になりました。現状実装したOSの機能はどれも典型的であまり新規性に富んだものではないので、興味深い機能を追加したりしたいものです。

それと、コアを実装したATPが非常にコアを書くのが上手で助かり続けたわけではありますが、複数人で短期間でオラオラと実装するのは楽しかったです。

参考にしたもの

余白：CPU実験について

あまり言及しませんでしたが、もともとこれは大学の情報科学科の実験科目であるCPU実験の余興として、好きなプログラムを動かしたい人が趣味で動かそうという気持ちでやった話になります。余興の先人はいろいろな人々がいますが、OS関連でいうと、xv6を移植して動かした人々、OSを１から作った人々がそれぞれいます。実際いざCPUが動くと感動するし*3 、さらにいろいろ動かしてみたくなるという気持ちは生えがちで、まぁ毎年余興をする人々が現れるようです（よく知りませんが）。

CPU実験本流の方は、同じ代でもっと高速化を真面目にやっていたり、強いコアを作っている人がいるため書くのもおこがましいなあという感じですが（コアに関することは、3つのアーキテクチャでレイトレーシングを完動させて余興コア作ったATPが明らかに詳しい、コンパイラは、2言語でmin-camlフルスクラッチしてLLVMバックエンド書いた uenokuが明らかに詳しい）、まぁ感想を残しておくのも悪くないのかもなあと思い、余白として書き残しておきます*4 。

CPU実験とは、 VerilogでコアやFPUを作り、OCamlでコンパイラを書くことで、お題となるレイトレーシングプログラムをFPGAの上で動作させ速度を競うという実験です。

この授業の本流としては、完動*5 をした上で、よりIPCが高く、動作周波数の高いコアの設計、および動的に実行する命令数を減らし、コアの命令レベル並列などにより生じる制約に対するより良いスケジュールを行うコンパイラの設計をすることにあります。

僕自身はコア係だったので、コアを作りました。それと、コンパイラの命令数の削減をしました。アーキテクチャは、210MHzの単純なパイプライン（命令レベル並列なし、レジスタフォワーディングあり、ロード命令にアウトオブオーダー完了あり）というそんなに複雑じゃないやつです。

また、命令数の削減としては、基本的にはアーキテクチャの最適化が効くので、これをまずして、グローバルに定義されている配列は静的にマップして良いので（そういうルール）、マップした上で静的にアドレスを解決して1命令でロードしたり、そもそもRISC-Vからだいぶ逸脱して*6 、load命令は、word単位のみとした上で、4byte一単位で扱うようにしたり、いくつかのpeephole最適化と共通部分式除去の追加で17.8億程度の命令数になりました（実際には結局sqrtはソフトウェア実装を使ったので1億ほど増えました）。おそらくここらへんからがむしろコンパイラとしては本番で、データフロー解析/グローバルレジスタ割当くらいは時間があればやりたかったですね*7 。

結果としては、命令数が18.8億程度で20.7秒でした。過去の記録的には2006年ですでに18.8秒程度の記録があり、昨年まででは2016年の4秒台の記録があるので、まぁ全然良くないわけですが、なんかやってみた感想としては、命令レベル並列ないし何らかの並列性が無いと、割とこのあたりになるんだなあということです（多分floating point周りのマルチサイクル命令をアウトオブオーダー完了にしたり、もう少し頑張って周波数を上げたり、命令数をもう少し減らせるので15秒程度までは頑張ればいけるかも）。

逆に命令数削減はやっていると分かることですが、命令セットやアーキテクチャにはよるものの11~13億あたりが上限の相場だと思われます（過去にwataさんの班が8.8億程度の命令数まで減らしているようですが）。

まぁ要するに現代のCPUの作りからも分かるように、いかに並列に実行していくかというのが（多分）高速化のキモで、そこを楽しむことができなかったのが唯一CPU実験で悔いが残る部分です。とはいえ、コア、コンパイラ高速化、余興とCPU実験の各部分を触ることができて個人的には楽しかったです。

今年は他の班で強い高速化（GPU実験？）を行なっている人々がいるのでどうなったか気になるところですね*8 。

CPU実験、批判はあって、レイトレプログラムがOCamlっぽくなかったり、レイトレが使うメモリ量少ないので、メモリのキャッシュがいらなかったりするのが現代に沿わない、"完動"の定義があいまい *9 、そもそもコンパイラにはmin-camlがあるので、コンパイラとはみたいな話があったりしますが、その上で個人的にはCPU実験を通して *10 、いろいろなアーキテクチャやコンパイラの最適化の概念にふれることができ、それを通して先人の知恵（どんなISAが効率よくデコードできるか、パイプラインの設計はどうあるべきか、、、）を一つ一つ確かめることができる良い実験だったと思います。

実際上で書いたような機能を持ったOSをmin-camlで実装して、その上で動作するプログラム（並列に動作することをより意識したもの）を高速化するというのを課題にしてみたりするのは実際やろうと思えばできるだろうし（min-osみたいなのをある程度実装しておいて（誰かが）、重要な機能の仕様、例えばpagingやtrapの仕様を自分達で決めてその部分は自分で実装するみたいな感じで）、より理情的要素が増えるし面白いんじゃないかなあと思います。とはいえ、CPU実験、レイトレーシングの高速化がちょうど良い課題で、それでいて面白いから良いという話はあるので（実際このセメスターもCPU実験しているだけではないし、CPU実験みんなが好きなわけじゃないので）、まぁこの形態が今後も続いていきそうな感じはしますね（2004erのunnoさんがこの話題に既に言及していて、それでいて特に何も変わっていないので、まぁそういうことなんだろうなあという感じはあります）。まぁなんにせよ、僕には楽しい実験でしたが、ところでVivadoとはもうお付き合いしたくない気持ちにもなりました。終わり

*1:実際CPU実験をするという意味においてRISC-Vを選ぶのはかなり良い選択肢だと思います。もっとも、高速化のためにはいくつかの逸脱が必要だと思いますが

*2:まぁこれもOS界隈的には何をアタリマエのことをという可能性はありますが。。

*3:完動なので

*4:それはそうですが、それほど強くないアーキテクチャのときどれくらいの記録が出るのかというのは意外と知見が無いです

*5:実装したコアとそのシミュレータの動作でそれぞれの結果同士にdiffが無い状態のことを指し、ただし真っ黒な画像や"人間が見て"画像が壊れている場合は完動ではないとされている

*6:実は僕の班のアーキテクチャももともとはRISC-Vベースでした

*7:今後やるかもしれません

*8:まぁあんまこういう文章書きたがらない感じがしますが（ほんまか）

*9:シミュレータとのdiffがないのと同時に、完成画像に対して一定以内のdiffのような条件もほしい？

*10:教えてはくれませんが

欣快の至り