RISC-Vほぼ互換の自作CPU上で動くなにかを作った

はじめに

この記事は 東京高専プロコンゼミ① Advent Calendar 2021 3日目の記事です。

やった事

ChiselでRISC-Vの命令を一通り実装したCPUを作り、そのCPU上で動くOSもどき (コンテキストスイッチ程度のもの) を作りました。

github.com

github.com

CPU自作

RISC-VとChiselで学ぶ はじめてのCPU自作 の内容をほぼ写すような形で実装しました。
この本はChiselでRISC-V互換のCPUを作る事を目的にしていて、rv32i (RISC-Vの最も基本的な命令セット) のほぼ全ての命令の実装が解説されています。
環境構築にDockerイメージが配布されていたり riscv-tests によるテストの手順が説明されていたりしていて、僕のような専門知識のない人間にも優しかったです。(嬉しい)

www.amazon.co.jp

github.com

本で紹介されていなかったいくつかの命令 (sb命令など) は適当に自分で実装しましたが、今回は並列処理を行わないためfence系の命令は実装していません。mretなども未実装です。
また、CPUに雑に手を加えた時にハザード関連でバグらせるのを避けるため、パイプラインを実装していない物を使ってデバッグを行うようにしています。 (本では5段パイプラインでの実装が解説されていました)

OSもどき

ここまで実装するとCの普通のコードが動くようになったので、この上でなにか動かしてみます。
とりあえず今回はコンテキストスイッチがあり、タイマ割り込み処理が走ってプロセス切り替えができるOSもどきを作りたいと思います。

開発環境

Cを書きたくないのでRustを使う事にします。
同じ事をされていた他の方 の記事には公式でサポートされているISAがrv32imacとrv32imcのみと書かれていたのですが、調べてみると現在は公式でrv32iへの対応がされており、targetを適当に指定してあげるだけでrv32iのバイナリを吐かせる事ができました。
それ以外の部分は RustでRISC-V OS自作!はじめの一歩 を参考に整えました。
言語自体の安全性や構文の便利さが活きただけでなく、no_stdでもiteratorやOptionなどの機能が使えてかなり満足です。 unsafeで囲めばインラインアセンブラなどを使ってやりたい放題できるのも嬉しい。

権限とCSR周り

RISC-VのPrivileged ISAに合わせて実装をするととても辛そう & 今回は自前のコードしか動かさない ので、今回はオレオレで権限周りの実装を行っていきます。
こうするとCSRを全く使わなくなるので、元の規則を無視して各CSRに入れる値を独自に定義してしまい、雑に値を読み書きするようにしています。(CSRの各レジスタの権限設定はサボっているため、ユーザープロセスでcsrrwなどを使われるとOSが死にます)
また、独自命令を実装しようとするとコンパイル時のtargetを弄らないといけなくて辛そうなので、手抜きの為にCSRの特定レジスタへの書き込みをフラグにCPU側で特殊な処理を行ったりもしました。

プロセス管理

プロセスを雑に [Option<Process>; 16] で管理し、Process構造体には退避時のレジスタの値やpcなどを格納しています。
各プロセスには固定量のメモリを割り当てていて、CSRの特定の位置にプロセス番号を投げるとCPU側に実装したmmuもどきが対応する物理メモリの値を取ってきてくれます。(ページングは実装していないため、メモリを雑に食べていくとすぐ死にます・・・)

割り込み

CSRにタイマ用のレジスタを用意し、一定サイクルが経過するかタスクが終了した場合にinterrupt関数のアドレスに飛ぶようにします。 遷移前にはCPU側でpcの退避を行い、interrupt関数の中でレジスタの退避や各種無効化を行った後にプロセスの切り替えを行います。
切り替え時には現在実行していないプロセスを優先的に選ぶようにしていますが、真面目にやるならProcess構造体に待ち時間などを保持すると良さそうです。

おわりに

CPU自作パートは本当に楽で特にトラブルもなく動かせました、書籍には本当に感謝・・・
OSもどきはかなり手抜きでメモリの動的な割り当てすらできないような状態なんですが、割と考える事が多く、ちゃんと頭を使っている気分になって楽しかったです。 (デバッグはつらい)
結局FPGAを一切触らずにシミュレーション環境上で動かしたため、いつか時間がある時に実機で動かしたい気分になりました。

京セラプログラミングコンテスト (AtCoder Heuristic Contest 006) 参加記

はじめに

2021/11/14の16:00-20:00に行われた 京セラプログラミングコンテスト (AtCoder Heuristic Contest 006) に参加しました。結果は1953482点で、19位でした。



解法

全ての点と (400,400) との角度を求める。
(a,b)の角度 < (c,d)の角度 を満たす配達先のみを反時計回りで巡回するルートを、「ランダムに選んだ1つを削除し、ランダムに選んだ1つを適切な角度に追加する操作」を近傍にした焼きなまし法で最適化する。
これを逆向き(時計回りの場合) でも同様に行い、2つの解の中で良い解に対し、「ランダムに選んだ1つを削除し、ランダムに選んだ1つを改善量が最大となる位置に追加する操作」を近傍にして山登り法で最適化した解を出力する。


コンテスト中の流れ

概要の理解, 初手 (~20分)

まず問題を読んだ。集合を選ぶパートと巡回セールスマン問題を解くパートの2つに分かれている事が分かって、どちらも焼きなまし法が使えそうなので安心した。
2つパートがある問題は解法を2ステップに分けずにうまく一体化する事が大事という話が昔のマラソンコンテストであったはずなので、どうにか両方をまとめて最適化する事を考えたい。
巡回セールスマン問題を含むのでどう転んでも2-optは実装する事になるのかなぁと思ったけど、2-optの実装経験がない+午前中に予定が入っていて集中力が十分残っていなかったので、ひたすら高速化して焼きなますだけの勝負になると勝てなそうで少し不安。
とりあえず配送先1-50を順番に辿るvalidな解を書いてビジュアライザで答えを見たんだけど、それすら少し時間がかかってしまったので反省。

イデア探し (~100分)

とりあえず2-optは実装して損がなさそうだから後で書くとして、その前にビジュアライズした時に分かりやすい+焼きなましに移行しやすそうな見た目の初期解を貪欲法で作る事を考える事にした。
とりあえず近い点対をまとめて扱えると嬉しいのかなと思って近い点対を探したり(a1,b1)と(a2,b2)が近く(a3,b3)と(a4,b4)も近い配送先のペアを出力してみたりしたんだけど、方針が全然思いつかない。
100*100ぐらいのブロックを考えてそこをまとめるみたいな事も考えたんだけど、そうしてもいい解が出せる気がしなくて、困った。
一時間以上考えても何も分からず布団で考えたりしたんだけど、全く分からない。

初回提出 (~120分)

中心との角度でソートして並べれば適切な挿入位置が求まって高速に焼きなましの近傍が出せそうな事に気づいた。 この時点ではすごい良い解法っぽい感覚はなかったんだけど、性能が微妙だったとしてもとりあえず見た目の良い初期解が出せそうなので実装してみる事にした。
頭を使うコードを書くのがつらい+仮実装の段階 なので毎回ソートし直す O(mlogm) の近傍操作を書き、10000iterの山登り法を実装した。出力の見た目もseed=0に対する距離も思っていたより良くてウキウキで提出するとREが出て、悲しい気持ちになってしまった。(テストケースをファイルから読み込むコードのままだった事が原因だった)

2回目の提出 (~127分)

提出間隔が5分あるのでその間に自明な改善を考える。現時点では反時計回りのケースしか考慮していないが、それだと1000個あるタスクのうち約半分しか見ない事になって困るので、時計回りのケースに対しても試行を行って良い方を取るようにした。また、実行時間に余裕があったのでiter数を2e5に増やした。
提出を行った結果175万が取れて、この時点での10位になれた。

焼きなましの実装 (~160分)

現時点の実装は雑に山登り法を適用したのみなので、これを焼きなましに置き換える。実装してもスコアが上がらず困ったが、原因のバグ (焼きなましの遷移判定の直後に if(now_score > nex_score) が入っており、山登りの完全な劣化になっていた) を発見して解決した。178万点で21位。

焼きなましの調整, 二段階目の実装 (~215分)

iter数とスコアの関係を見た所、iter数が1e5になった辺りでスコアがほぼ改善しなくなる事が分かった。この方法だけだと限界がありそうなため、別の方針を考える。
今の手法は偏角によって配送タイミングに制約をかけているためそこに問題がありそうで、そうなると偏角に依存しない操作をしたくなる。そのため、偏角ベースの焼きなましで得られた解に対して一点挿入一転削除の山登りを実装する事にした。 挿入時にスコアが最も改善するような挿入位置の組を求める操作は累積minを使うと O(m) でできて、流石にここの O(m2) は許容できなさそうなので頑張って書いた。
集中力が切れてきた事もあって実装に時間がかかるため、5分に一度焼きなましのハイパラ調整を行って提出していた。186万点で17位。

終盤 (215分~)

二段階目の山登りが実装でき、194万で17位に戻ってきた。
残りは安定して点を稼ぎたかったため、一段階目と二段階目の実行時間のバランス調整や焼きなましの温度最適化を行い、5分に一回提出するようにした。
残り140秒で投げた最終提出がHighestで、最終的には195万点で19位となった。

反省

序盤の1時間半ぐらい全くアイデアが出なかったので反省。ただこの時にハズレ方針に手を付けて逃げられないみたいな事にならなかったのは悪くないし、結局当たりを引けたからOKかな・・・という気分。
2-optの高速化で勝負すると厳しいという事を判断して簡単な焼きなましに逃げられたのは良い判断じゃないかなぁと思う。焼きなましパートの必要以上の高速化を切って他部分の変更に時間を割けたのも良かった。
終盤の動きは適切っぽくて、自明な改善がなくなったタイミングで、可能な提出回数が少なくなるラスト数十分を手元でのスコア測定+ハイパラ調整での得点アップに割くムーブは正解そう?
あと記事を書いている時に気づいたんだけど、kick操作を全くしていないので局所最適から全然抜けられてなさそう。今回は雑にやって問題なかったけど、今後に備えてちゃんと設計ができるようになっておくべきかもしれない。

2022年度(令和4年度) 筑波大学情報学群情報科学類編入試験 受験記

はじめに

2022年度(令和4年度)の筑波大学情報学群情報科学類の編入試験を受験したので、試験の流れなどについて記録を残そうと思います。


試験内容と対策

数学/英語/情報 の3科目があり、恐らくそれぞれ100点満点で評価される。

数学

微積分と線形代数からそれぞれ一題出題される。微分方程式や数列、確率などは出題されない。

英語

TOEIC利用で、例年通りであれば730点満点らしい。
僕は運良く十分な得点を取れていたので、これは対策しなくて問題なかった。

情報

プログラミングに関する問題が二題出題される。
細かいミスにさえ気をつければ十分な点が取れる難易度だと思う。


受験記

当日の流れ

当日は9時開場で9時30分集合、試験は10:00からの120分間だった。
単願が16人、情報科学類第一志望の併願が95人の合計111人が受験していた。情報メディア創成学類は単願5人、併願46人だった。
今年から情報科学類で物理を選択できなくなり、数学2問と情報基礎2問の大問4つを解く形式となった。
英語はTOEICもしくはTOEFL iBTで、自分は3年次に受験したTOEICのスコアシートを提出した。例年通りなら100点になると思う。
僕は問題2~4 (線形代数と情報基礎2つ) を完答して、問題1は冒頭1問のみを解き、他は部分点狙いで適当な解答を書いた。
ケアレスミスが無いと仮定すると270程度、問題1の部分点なしかつケアレスミスがあり採点が厳しかったとしても240点ぐらいは取れた感じの手応えだった。

試験問題

数学1 (微積分)

  • 極座標変換で解ける二重積分
  • 前問の答えを利用する二重積分
  • 二項係数で展開してから微分する証明問題

数学2 (線形代数)

  • 掃き出し法で線形独立なベクトルを求める
  • ベクトルの集合を部分空間の和で表して、部分空間とならない事を証明する問題

情報基礎1

  • ビンソート、分布数え上げソートに関する問題 (穴埋め、動作不備の指摘など)
  • 安定ソートの説明

情報基礎2

  • バーコードを2進で受け取って数値列に変換するコードに関する問題

2022年度(令和4年度) 山梨大学工学部コンピュータ理工学科 編入試験 受験記

はじめに

2022年度(令和4年度)の山梨大学工学部コンピュータ理工学科の編入試験を受験したので、試験の流れなどについて記録を残そうと思います。


試験内容と対策

調査書/面接/筆記試験(情報)の3つがあり、それぞれ50/50/400点がつけられている。

情報

プログラミング(アルゴリズムとデータ構造)、計算機アーキテクチャ、情報数学の3つの内から2つを選ぶ事になる。
プログラミングは普段コードを書いているなら問題なく解ける難易度で、ここは普通に解けば落とす事はないと思う。
計算機アーキテクチャと情報数学は(自分の)未履修な範囲から出題される事があったが、これも高専の授業内容を覚えていれば解ける難易度になっている。
大問の間に大きな難易度の差はないため、出題された問題ジャンルに合わせて好きな方を解けばよいと思う。

面接

普通の面接であり、形式や教員の態度などに特筆すべき点はない。
他が満点でも面接の内容次第で落とされる可能性があるらしいので、少し気を付けた方がよい気がする。

受験記

当日の流れ

当日は8時45分集合で、筆記試験は09:20から80分間だった。(試験時間は募集要項等には書かれていなかったが、例年80分らしい)
定員5人に対して出願者数は15人で、受験者数は14人だった。
筆記問題は下記の通りで、僕はハフマン符号を習っていなかったためプログラミングと計算機アーキテクチャを解いた。
特に難しい所はなかったため、細かいミスがなければ満点だと思う。
面接では志望動機ややりたい事、最近興味を持っている技術的な話題について聞かれた。

試験問題

プログラミング

  • 素数判定プログラムの穴埋め、計算量の記述 ( O(√N)と O(N) の2つについて)
  • 単方向連結リストのプログラムが与えられ、出力書き出しや動作説明
  • 部分和問題 ( O(N2N) のプログラムが与えられるため説明、O(NK) のアルゴリズムがどのような物か説明)

計算機アーキテクチャ

情報数学

#procon31 非公式競技部門に参加しました

はじめに

12/19に開催された第31回全国高等専門学校プログラミングコンテスト非公式競技部門に参加してきました。

ルール

  • 基本的には去年と同じルール
  • 囲んだ領域マスは消えない(囲みが消えても領域マスは保持される)
  • 領域は4近傍で囲まれている必要がある

方針

  • 各エージェント毎に多様性を持たせてビームサーチしてから、焼きなましで経路の組み合わせを検索
  • 評価関数は得点、領域、エージェント間の距離、経路のコンフリクト度合いなどに対して適当に係数をかけたりする
  • ハイパーパラメータはoptunaで最適化

実装

Rustで実装しました。GUIにはdruidを使って、APIJSON周りはserde-jsonreqwestを利用しています。
リポジトリこちらです。

できなかった事

  • 並列化
  • 情報の自動取得や自動送信
  • 特定の盤面に対する対応
  • 相手の領域を予測した除去
  • 相手の行動を考慮に入れた評価関数の設計

反省

  • 本番のコードに対するバグが多すぎた(当日になって解決するケースが多かった)
  • 準備期間が不足していた
  • ルールの誤読が複数あって、片方は当日朝、もう片方は本番で気づいた (エージェント配置でタイルが変わらない事、囲みが4近傍になっている事)
  • アルゴリズムがランダム配置のマップ前提の物になっていて、人工ケースで動かす時に問題が多かった

おわりに

ちゃんとルール理解していたり本番にバグがなければもう少しいい成績が取れていたと思うのでかなしい
骨組みを前もって作っておいたとはいえ、アルゴや通信部分等を3日で完成させられたのは良かったと思う

このような環境を用意して頂いた運営のみなさんに、感謝・・・

食事最適化入門 美味しい完全食

はじめに

健康的な人間になるためにはバランスの取れた食事が必要です。

しかし、食事には時間がかかり、かなり辛いです。
栄養を摂取するためだけの食事に長時間かけるのは、非本質の経路復元が実装時間の8割を占めるICPCの実装問ぐらい不毛です。(まぁICPCエアプなのでそんな感じの問題があるかどうか知らないんですけど)

そのため、手早く食べられて栄養満点な食事が必要とされています。


本題


これ、めっちゃうまい

f:id:shibh308:20201204231046j:plain
うまい!

basefood.co.jp

Suffix Treeで解ける有名っぽい問題

はじめに

Suffix Treeで解ける有名っぽい問題(Gusfield本に載ってるやつ)の中で競プロで使う事がありそうなものの解法をまとめる 記法とか定義とかがものすごくガバガバなのは許してください

定義

以下を適当に定義する

  • 文字について

    • $\$$ と $\$_i (1 \leq i)$ を区切り文字とし、入力で与えられていないような入力中のどの文字よりも辞書順で小さい文字とする
  • 文字列 $S$ について

    • $S[i, j]$ を $S$ の $i$ 文字目から $j$ 文字目までの文字列とする ($i > j$ なら $S[i, j]$ は空文字列)
  • Suffix Tree, Generalized Suffix Tree中のノード $v$ について

    • 根と $v$ のパスが表す文字列を ${\rm str} (v)$ とする

    • ${\rm depth} (v) = |{\rm str} (v)|$ とする

  • Suffix Arrayについて

    • ${\rm SA}_S$ を $S\$$ のSuffix Arrayとする(特に区別する必要がなければ ${\rm SA} _ S = {\rm SA }$ と省略して表記する)
  • Suffix Treeについて

    • ${\rm ST} (S)$ を $S\$$ を表現するSuffix Treeとする
  • Suffix Tree中のノード $v$ について

    • ${\rm str} (v) = S[i, i + {\rm depth} (v)]$ であるような適当な $i$ に対して、 ${\rm pos} (v) = i$ とする
  • Generalized Suffix Treeについて

    • ${\rm GST} (\mathcal{S})$ を $ S_1 \$_1 S_2 \$_2 \dots S_{|\mathcal{S}|} \$_{|\mathcal{S}|}$ を表現するGeneralized Suffix Treeとする
  • Generalized Suffix Tree中のノード $v$ について

    • ${\rm str} (v) = S_i[j, j + {\rm depth} (v)]$ であるような適当な $i, j$ に対して、 ${\rm label} (v) = i, {\rm pos} (v) = j$ とする

問題

Maximal repeats

定義

  • 文字列 $T$ と$1 \leq i \leq j \leq |S|$ に対し $T[i,j] = T[i',j'] ,\ T[i-1,j] \neq T[i'-1,j'] ,\ T[i,j+1] \neq T[i',j'+1], (i, j) \neq (i', j')$ を満たす $(i', j')$ が存在する場合、 $(i, j)$ を $T$ の maximal repeatと定義する

問題概要

  • 文字列 $S$ が与えられる

  • $S$ の全てのmaximal repeat $(i, j)$ についての $S[i, j]$ の集合 $\mathcal{S}$ を求める

  • 文字列を出力すると出力サイズが $ \Theta ( |S| ^ 2 )$ になる事があるため、 $S[l,r] \in \mathcal{S}$ であるような $(l, r)$ の集合の形で表す

解法

  • ${\rm ST} (S)$ の内部節点を全て見る

  • 内部節点 $v$ の子孫であり ${\rm pos} (u) = k$ であるような葉 $u$ について $S_{k - 1}$ を調べ、これが全て一致していなければ $(k, k + {\rm depth} (v))$ はmaximal repeatになる

  • 子孫となる葉の集合は $\rm SA$ 中の区間になるため、$V [i] = S_{{\rm SA} [i] -1}$ であるような配列 $V$ 中で種類数が$1$になる区間を前計算しておけば解ける

  • 列挙する際は全ての $v$ に対して適当な $u$ を選んで $(k, k + {\rm depth} (v))$ を報告すればよい

Supermaximal repeats

定義

  • $(i, j)$ が文字列 $T$ のmaximal repeatであり、 $(i, j) \neq (i', j')$ である任意の $T$ のmaximal repeat $(i', j')$ と非負整数 $l, r$ に対して $(i'+l, j'-r) \neq (i, j)$ が成り立つ時、$(i, j)$ を $T$ のsupermaximal repeatと定義する

問題概要

  • 文字列 $S$ が与えられる

  • $S$ の全てのsupermaximal repeat $(i, j)$ についての $S[i, j]$ の集合 $\mathcal{S}$ を求める

  • maximal repeat と同様、$( l, r )$ の集合の形で表す

解法

  • maximal repeatと同様に ${\rm ST} (S)$ を考える

  • 子が全て葉である内部節点 $v$ の子で ${\rm pos} (u) = k$ であるような葉 $u$ について $ S _ { k - 1 } $ が全て異なっているならば $(k, k + {\rm depth} (v))$ はsupermaximal repeatになるため、それを報告すればよい

  • $S_ { k - 1 } $ が全て異なるような区間はしゃくとり法で前計算できる

Longest common substring

定義

  • 文字列集合 $\mathcal{S} = \{ S_1, S_2, \dots S_m \}$ に対して、$S_i[l_i, r_i] = T$ であるような $(l_i, r_i) \ (1 \leq l_i \leq r_i \leq |S_i|)$ が存在するような $S_i$ の個数が $k$ 以上である時、文字列 $T$ を $\mathcal{S}$ の種類数 $k$ のlongest common substringと定義する

問題概要

  • 文字列集合 $\mathcal{S}$ が与えられる

  • $1 \leq k \leq |\mathcal{S}|$ を満たす全ての $k$ に対して種類数 $k$ のlongest common substringの最大の長さを求める

解法

  • ${\rm GST} (\mathcal{S})$ を構築する

  • 内部節点 $v$ の子孫であるようなノード $u$ についての ${\rm label} (u)$ の集合を求め、集合の要素数が $k$ 以上である時、${\rm str} (v)$ は種類数 $k$ のlongest common substringである

  • これはmaximal repeatと同様に区間種類数になって、解ける

All-pairs suffix-prefix matching

定義

  • 文字列の組 $(S, T)$ に対して $S[1, k] = T[|T| + 1 - k, |T|]$ を満たす最大の $k\ (0 \leq k \leq {\rm min} (|S|, |T|))$ をsuffix-prefix matchingと定義する

問題概要

  • $ M $ 個の文字列からなる文字列集合 $\mathcal{S}$ が与えられる

  • $1 \leq i , j \leq M $ を満たす全ての $(i, j)$ の組について、$(S_i, S_j)$ のsuffix-prefix matchingを求める

解法

  • ${\rm GST} (\mathcal{S})$ を構築する

  • ノード $v$ の子にラベル $\$_k$ の辺が存在する時、ノード $v$ をk-terminateと呼ぶ

  • ${\rm str} (v) = S_i[1, k]\ (1 \leq k \leq |S_i|)$ であるノード $v$ がj-terminateである時、$(S_i, S_j)$ のsuffix-prefix matchingは $k$ 以上になる

  • stackを $|\mathcal{S}|$ 個管理してDFSをする 今見ているノード $v$ がj-terminateである場合、 $j$ 個目のstackに ${\rm depth} (v)$ をpushする(探索終了時にpopする)

  • ${\rm label} = i, {\rm pos} = 1$ であるようなノードに到達した時に、$1 \leq j \leq |\mathcal{S}|$ を満たす全ての $j$ に対して $j$ 番目のstackのtopを確認すればいい