『VisualStudioを使っていると「移動したか、名前が変更されたか、またはコンピュータに存在しません。」と出る 』を解決した

タイトルの通りです。

症状は先々週の記事を参照してください。

lpha-z.hatenablog.com

「c1xx C1083」でググったところ、以下のウェブサイトを見つけ、そこに書かれていることをやったところ解決できました。

developercommunity.visualstudio.com

解決法は、問題の発生しているフォルダをzipで圧縮し、それを解凍して元の位置に戻す、たったそれだけです。

もう少し具体的には、

  1. まず問題の発生しているフォルダをzipで圧縮する。
  2. 問題の発生しているフォルダを削除する。
  3. Windowsエクスプローラーから 圧縮したzipファイルを解凍し、元の位置に作成する

どうやら、WSL上で作ったファイルは、そのファイルシステムが大文字小文字を区別するような設定になってしまい、それが悪さをするようです。 zipで圧縮した後解凍した場合、Windowsがファイルを生成するため、ファイルシステムはWindowsデフォルトの大文字小文字を区別しない設定になります。 これによりVisualStudioが望んでいる形式のファイルシステムとなり、エラーが消えることになります。

使っているgitリポジトリによっては、あまりにも大量のファイルを操作することになるため、非常に時間がかかります。 また、一部のファイルが欠けてしまうことも発生しましたが、やり直したところうまくいった、というよくわからないことも発生しました。

また、先ほどのウェブサイトには、そんな大層なことをしなくても、単にファイルシステムに大文字小文字区別をしない設定を付ける方法として、

fsutil.exe file setCaseSensitiveInfo <path> disable

を実行すればよい、とも書かれていましたが、まだ試していません。

この方法は、先々週の記事で「表示されるパスが全て大文字になる」という症状を発生させたときの対処法としてあげられていました。 先々週の段階ではその症状は発生していなかったため、この対処法を試すことはありませんでした。 しかし、他のgitリポジトリで試してみたところこの症状が発生したこと、解決策が同じだったことから、実は症状は同じであったようです。

文脈自由言語の階層について

去年もこんな話を書いた気がします。

文脈自由言語の階層についての情報ってネット上ではまとまった形ではあまり手に入らないような気がします。調べたことをまとめておきます。

文脈自由文法と文脈自由言語の違い

文脈自由文法と文脈自由言語という、二つの混同しやすい用語があります。

まず、「言語」とは（有限）文字列の（無限かもしれない）集合のことです。○○言語というのは、特定の特徴を持つ言語の集合（言語クラス）のことです。 文脈自由言語とは、与えられた文字列がその集合に属しているかの判定（メンバーシップ問題）がプッシュダウンオートマトンを用いると解けるような言語です。その集合は普通は無限集合ですが、有限集合であっても問題ありません。ただし、有限集合であれば自明に正規文法で記述できる正規言語になるため、わざわざ文脈自由言語という必要がありません（有限集合なので/foo|bar|baz/のようにすべての要素を枚挙することが可能です）。 正規言語のメンバーシップ問題は有限状態オートマトンで解かれますが、非決定性があってもなくてもどちらでも同じになります。一方、文脈自由言語のメンバーシップ問題を解くためのプッシュダウンオートマトンには、これとは違い非決定性が必要です。なお、非決定性が必要とはいっても、文脈自由言語のメンバーシップ問題は全探索的考え方で多項式時間で解くことができます。

一方、「文法」とはそのような集合を記述する方法のことです。一般にある集合を記述する方法は複数ありえるので、「言語」と「文法」の違いは重要になります。 集合の元が無限にある場合、その集合を記述するには一工夫必要です。実際の記述には、BNF記法や正規表現など、読みやすい形がいくつか提案されています。なお、いわゆる正規表現は、正規言語を超えた記述能力を持つような拡張が加えられていることがあるので注意が必要です（たとえば後方参照は、文脈自由言語すら超えた表現力を持ちます）。

LL(0)

前から読んでいき、先読みをせずに次の構造が何であるかを予言する必要があるため、LL(0)文法で記述できる集合は、単元集合のみです。

また、LL(0)言語も同様に単元集合だけであり、正規言語に真に包含されます。

LL(1)

前から読んでいき、一トークンの先読みだけにより、どの生成規則を適用するかを決めることができるような文法をLL(1)文法と言います。

また、そのような文法で記述することができる言語をLL(1)言語と言います。つまり、「頑張ればLL(1)文法であるような文法が作れる」ような言語です。LL(1)言語だからと言って、文法を適当に作った場合にはLL(1)文法である保証はないということです。また、現実的な問題として、その文法の生成する構文木が作りたい構文木と一致している保証はありません。実際、a+b*cのような「数式」はうまく作ったLL(1)文法で解析できるにはできるのですが、変な構文木になってしまいます。

正規言語はLL(1)言語の真部分集合になります。

正規言語ではなく、文脈自由言語であるような集合として有名な \lbrace a^ n b^ n | n > 0\rbrace はLL(1)言語です。その他、「対応の取れた括弧」などもLL(1)言語です。

LR(0)

前から読んでいき、先読みなしにこのトークンがどの生成規則から生成されたものかを決めることができるような文法をLR(0)文法と言います。 先読みがないとはいえ、生成規則が生成するトークンすべてがあっていることを確かめてから構文木を作成するため、ある程度強力です。 しかし、正規言語の一部は受理できないなど、偏った性能を持ちます。

具体的には、xを一文字以上の文字列、w,yを空でもよい文字列としたとき、wとwxとyが言語に含まれているならば、yxも言語に含まれている、という性質を持った言語のみ受理可能です（参考文献[1]"On LR(k) Grammars and Languages"の定理3.1）。

LL(1)だがLR(0)ではない言語

LL(1)言語であってもLR(0)言語ではない言語は、先読みが本質的に重要な言語です。 \lbrace ab^ n | n > 0\rbrace \cup \lbrace cd^ n | n > 0\rbrace がそれに当たります。ここで、b(d)の後にb(d)が続くのかが先読みの必要な情報であり、a(c)を読んだ、という情報を手放さずに先読みを行えるかという点が重要になります。一方、 \lbrace ab^ n | n > 0\rbrace を解析するためにはaを読んだという情報は不要なため、LR(0)でも解析できます。参考文献[1]によれば、aもabもcもこの言語に入っているのにcbはこの言語に入っていないのでLR(0)では解析できないと書かれていました。

LR(0)だがLL(k)ではない言語

LL(k)言語ではない、というのはどんなに大きな有限のkを持ってきてもLL(k)文法では記述できない、という言語です。 \lbrace a^ nb^ n | n > 0 \rbrace \cup \lbrace a^ nc^ n | n > 0 \rbrace がそれに当たります。aを見た時点では、それがbに対応するものかcに対応するものかわからないため、二つあるであろう生成規則のどちらを選ぶべきかわかりません。また、aが続く数は無制限であるため、kトークン先読みではこの問題を解決することができません。

LL(2)

LL(1)との違いは先読みトークン数の増加だけですが、LL(1)を厳密に包含するクラスであり、LL(1)よりも高い記述力を持った言語クラスです。

一般に、LL(k+1)言語はLL(k)言語を厳密に包含するクラスです（参考文献[2]"Properties of Deterministic Top Down Grammars"）。

LL(2)でないと記述できない言語の例はなかなか見ませんが、この論文には具体例が上がっています。具体的には、 \lbrace a^ n (b^ kd | b | cc)^ n | n > 0\rbrace という言語はLL(k+1)では記述できるものの、LL(k)では記述できない、というものだそうです。まず、 (b^ kd | b | cc) の先頭にはdが現れることがありません。そこで、k+1トークン先読みしてdが出現するかを確認することにより、 bk dを生成する規則を選ぶべきなのかbを生成する規則を選ぶべきなのかの判別が可能です。逆に直観的にわかるように、kトークンの先読みなしではそのどちらの規則を選ぶべきか判断がつきません（論文には形式的な証明が書いてありました）。ccが存在するのは、 b^ {k-1}d を自由な位置に挿入することができるような文法として書けてしまうことを防止するためだと思われます。

SLR法

Simple LR(1)法というアルゴリズムのことであり、SLR法と言ったらこれのことを指します。また、このアルゴリズムで解析可能な文法をSLR文法と呼びます。

LR(0)法により解析を行おうとして問題が発生するのは以下のパターンです。

  • 複数の異なる生成規則の右辺が完成した状況(reduce-reduce conflict)。どの生成規則だったと言うべきかわからない。
  • 生成規則の右辺が完成した状況だが、もっと長い生成規則の途中という可能性もある状況(shift-reduce conflict)。前者であればその生成規則だと言うべきタイミングは今しかないが、スルーすべきなのかもしれない。

こういう場合、次のトークンを先読みすることにより問題を解決できる可能性があります。各非終端記号の後に来うるトークンの集合(Follow-set)を事前に計算しておきます。先読みトークンの情報をこれに照らし合わせて判断するのがSLR法です。

SLR法は、LR(0)文法を全て解析することができます（真に包含します）。

LALR(1)法

LookAhead LR(1)法というアルゴリズムの名前であり、これを用いて解析可能な文法をLALR(1)文法と呼びます。

SLRでは単にその非終端記号の後に来うるトークンの集合を用いただけでした。ここにいたるまでの情報を利用し、直後に来うるトークンの集合をさらに選別したもの(Lookahead-set)を使うのがLALR(1)法です。

SLR法で解析できないがLALR(1)法で解析できる文法は、以下のような感じです。

(1) S→V=E
(2) S→E
(3) E→V
(4) V→p
(5) V→q
(6) V→*E

これが生成する言語に含まれる文字列は、**p = ***qのようなポインタ同士の代入文です。

この文法では、Vの後には=が来る可能性があります。しかしその情報を使っても、=を先読みした時に(3)の生成規則を使ってVをEに還元するべきか、それとも(1)の生成規則の途中なのでスルーすべきなのか、判断がつきません。これがSLR法で解析できない理由です。

一方、LALR(1)法では解析可能です。なぜなら、Eから生まれたVであれば後ろには文字列終端が来るはずなのでそれを先読みしたらEに還元すべきであり、Sから生まれたVであれば後ろには=が来るはずなのでそれを先読みしたらスルーすべき、とそこに至るまでの情報を活用して解析が可能だからです。

LALR(1)法は、SLR文法を全て解析できます（真に包含します）。

LR(1)法

これもアルゴリズムの名前であり、これを用いて解析可能な文法をLR(1)文法と呼びます。

LALR(1)法では、先読みトークンだけが異なる状態を同一視することで状態数を減らすということを行っています。 これを行わないのがLR(1)法です。

この違いによりLR(1)法では解析できるのにLALR(1)法では解析できない文法は、以下のようなものです。

S→[A]
S→[B)
S→(B]
S→(A)
A→a
B→a

LR(1)法は、LALR(1)文法を全て解析できます（真に包含します）。

LR(2)法、LR(k)法

先読みトークン数を増やしたLR法です。まずつかわれることがないので割愛します。LR(2)法はLR(1)文法を全て解析できるうえ、LR(1)法では解析できずLR(2)法を用いないと解析できないという文法も存在します（真に包含します）。 また、LL(k)文法はLR(k)法で解析することができます（真に包含します）。

決定性文脈自由言語

実は、SLR法、LALR(1)法、LR(1)法、LR(2)法、……LR(k)法で解析できる言語は、決定性文脈自由言語という言語クラスと一致することが知られています。

これは、SLR法＜LALR(1)法＜LR(1)法＜LR(2)法＜……という文脈自由文法の解析法の階層は、文脈自由言語には存在しないということです。つまり、うまく文法を記述しさえすれば、どんな決定性文脈自由文法でもSLR文法で書けるということです。

また、LL(k)言語やLR(0)言語は決定性文脈自由言語の真部分集合です。

あいまいでない文脈自由言語

「回文」や \lbrace a^ nb^ n | n > 0\rbrace \cup \lbrace a^ nb^ {2n} | n > 0\rbrace などは、解析に非決定性が必要な言語です。これらはLL法やLR法では解析できず、全探索的考え方で動作するGLR法などで解析されます。

本質的にあいまいな文脈自由言語

言語に含まれる文字列について、複数の導出が可能になってしまうような文法をあいまいな文法と呼びます。たとえば、以下のような文法はあいまいな文法です。

S→S+S
S→x

たとえば、x+x+xの導出は二通りあります。右結合か左結合かを明示した文法とすればあいまいでない文法として記述できます。

しかし、どのように文法を記述しても文法があいまいな文法になってしまう言語もあります。それは本質的にあいまいな言語と呼ばれます。

\lbrace a^ nb^ nc^ md^ m | n, m > 0\rbrace \cup \lbrace a^ nb^ mc^ md^ n | n, m > 0\rbrace

たとえば上に上げた言語は本質的にあいまいな言語です。 二つの集合の共通部分である \lbrace a^ nb^ nc^ nd^ n | n > 0\rbrace は文脈自由言語ではないものの典型例になっています。 つまり、その部分に特殊化された文法を書けないため、二つの集合に対応した構文木のどちらとしても解析される（＝あいまい）、という直観的な解釈が可能です。 Wikipediaには、とある本に証明が載っていると書いてありますがその証明は形式的なものではありませんでした。

文脈自由文法にまつわる決定不可能な問題

  • ある文脈自由文法が「全文字列」という言語を記述しているか否か（チューリングマシンの停止性問題を帰着できる）。
  • ある文脈自由文法が別のある文脈自由文法と同じ言語を記述しているか否か（先の問題を含むので当然決定不可能）。
  • ある文脈自由文法の記述する言語は、別のある文脈自由文法の記述する言語に包含されるか否か（ A \subseteq B \wedge B \subseteq A の判定は先の問題と等価であるため）。
  • ある文脈自由文法が記述する言語と別の文脈自由文法が記述する言語の両方に含まれる文字列はあるか否か。
  • ある文脈自由文法があいまいか否か。
  • ある文脈依存文法が実は文脈自由言語を表しているか否か。

決定不可能な問題に対するよくある誤解として「この形式をしている問題は決定不可能」というものがありますが、「この形式をしている問題を 全て 解ける（統一的な）アルゴリズムはない」という意味であり、個々の問題インスタンスは決定可能です。たとえば、特定の文脈自由文法があいまいか否か、などは頑張れば証明が可能です。

参考文献

[1] M. M. Geller, M. A. Harrison, Theoretical Computer Science, 1977, 4, 245-276.

[2] D.J. Rosenkrantz, R.E. Stearns, Inf. Control, 1970, 17, 226-256.

VisualStudioを使っていると「移動したか、名前が変更されたか、またはコンピュータに存在しません。」と出る

タイトルの通りです。

具体的な症状は以下のような感じでした。

  • エクスプローラーからそのファイルをドラッグアンドドロップでVisualStudioに持ってくると、「(そのファイルのフルパス)は移動したか、名前が変更されたか、またはコンピュータに存在しません。」と出る。開こうとしているのだからまさにそこにあるはずなのですが。
  • #includeしているファイルのところで左クリックして出てくるメニューからそのファイルを開こうとすると、見つからなかったとエラーが出る。
  • そのファイルで定義されている関数を呼び出している部分を左クリックして出てくるメニューから定義に移動しようとすると、実行するのに十分なメモリがありませんでしたとエラーになる。
  • インテリセンスが働かない。また、予約語が青くなる以外に色がつかない。
  • そのファイルを変更したあとビルドしようとしても、「変更なし」とみなされてビルドができない。
  • VisualStudioを閉じたり、再起動したりしてもやはり同じ症状が出る。
  • 新たにディレクトリを作り、ソースコードをgit cloneでコピーした後、CMakeをして作ったまっさらな状態から再度コンパイルしようとすると、No such file or directoryと出てコンパイルできない。

対処方法をググってみると、大半は、単に初心者がインクルードパスを適切に指定できていないというだけの話であって、今回の症状とは関係がなさそうに思われます。 なぜならそのフォルダにある他のファイルはちゃんとコンパイルできるし、そもそも以前はコンパイルできていたからです。

いくつか根深い問題を踏んで、解決したというウェブサイトを見つけました。

qiita.com

このウェブサイトによれば、WSL上でgitを使っていたとか、大文字小文字の区別だとか、そういった話が問題を引き起こすとのことです。 確かにgit mvでファイル名を変更した後に問題が発生したので、心当たりがあるということになります。 しかし、表示されるパスが全て大文字になっているということはないので、症状は異なります。

sgry.jp

このウェブサイトによれば、%TEMP%ディレクトリに一時ファイルが残ってしまうため、VisualStudioを再インストールするなどの方法をとってすら解決ができないとのことです。 しかし、%TEMP%ディレクトリにmsvcという文字列を含むファイルは見つからなかったため、どうも違うようです。

blogs.yahoo.co.jp

複数のソリューションを持つプロジェクトを扱っている場合にたまに出くわすと書いてあり、その条件に該当します。 .suoファイルを削除すれば問題を解決できると書いてあります（.suoファイルというのは、.suoという拡張子のファイルではなくて、.suoの四文字が名前であるファイルのことです）。 しかし削除しても症状が改善することはありませんでした。

解決方法（？）

とりあえず元の名前に変更したところ、いくつかの問題は解決しました。

  • エクスプローラーからドラッグアンドドロップでそのファイルを開くことができるようになった。
  • そのファイルを変更した後ビルドしようとすると、ちゃんと依存しているファイルが全てコンパイルされる。
  • 定義に移動しようとすると、実行するのに十分なメモリがありませんでしたとエラーが出る症状はそのまま。しかし、一日経ったら（※）改善した。
  • #includeしているファイルに飛ぼうとすると見つからなかったとエラーが出る症状はそのままだったが、やはり一日経ったら（※）改善した。
  • インテリセンスは依然働かないし、予約語が青くなる以外に色がつかないままである。

※PCは起動しっぱなしだったけれど、VisualStudioを閉じて開きなおしたのが原因かもしれないです。

典型的な「よくわからないけれどいろいろやったらなおった」という感じになって原因も対処方法もわからずじまいになってしまいました……。

makeの並列オプションは何を指定するべきか

最近何の縁があってか 鬼斬弐 というオープンソースのプロセッサシミュレータの開発を手伝っています。

github.com

ここ数日でRISC-VのRV64Gへの対応が急速に進められ、ベンチマークプログラムも動くものが増えてきたようです。 私はちまちま細かいバグを取り除く作業をやっています。

今日は、makeを並列で行うオプション-j付きで実行するとき、その引数（最大何並列にするか）を何にすべきか調査した話をします。

よく見かけるのは、以下のような言説です。

  • CPUのスレッド数を指定するべき

これはもっとも単純で、CPUの動かせるスレッド数より並列度を高くしても、本当に並列に実行できるわけではないので、これが最大の効率になるはず、といった考えから来るものでしょう。

  • CPUのコア数を指定するべき

同時マルチスレッディングで複数のスレッドが動かせるといっても、あくまで1つのCPUで行っているため、演算器が余っていなければ特に速くなることはありません。それどころか、キャッシュを複数のプロセスで共有するため、運が悪ければ並列にした方が遅くなることまであり得ます。コア数までの並列度なら、全てのプロセスが独立したコア上で動くため、そのような問題が発生することはないはずです。

  • CPUのスレッド数（あるいはコア数）より1少ない数を指定するべき

makeを行っている間、CPUはコンパイルだけを行うのではなく、OSの仕事やバックグラウンドプロセスなどを実行する必要もあります。そこで、そういったプロセスのために1スレッド（1コア）残しておこうといった発想だと思われます。実際、スレッド数以上の並列度を指定するとマウスやキーボードの反応が悪くなって他の作業をすることがほとんど不可能になることもあるので、多少コンパイルが遅くなってもよいという場合には悪くない、安定感のある選択肢でしょう。

  • CPUのスレッド数（あるいはコア数）より1大きい数を指定するべき

これはおそらく、あるプロセスですべきことが終わった瞬間、OSが次のプロセスを選ぶわけですが、このときに選ぶプロセスが存在しないと無駄な時間が発生するため、一つ余分に作っておこうという発想だと思われます。プロセスを立てるのに時間がかかる環境（CygwinやWSL）で有効な作戦かもしれません。コア数と書かれている場合もありますが、どういった理論によるものなのかはよくわかりません。論理コア数といった意味なのでしょうか？（この記事では、スレッド数＝論理コア数、コア数＝物理コア数、の意味です。）

  • 特に指定する必要はない

指定しなかった場合、プロセス数の上限がない（無限にプロセスを立てることができる）という指定をしたことになります。軽量な処理を大量に行う場合は、プロセスを立てるオーバーヘッドを隠すためにこのような指定が有効な場合もあるでしょう。ただし、コンパイルは重い処理でありかつメモリを大量に消費するため、無制限にプロセスを立てるとメモリ不足を引き起こし、スワップが発生してものすごく遅くなる可能性があります。そのため普通は何らかの数字を指定するのが一般的です。

実験

先ほど話した、鬼斬弐をmakeする時間を測ることによって、最適なオプションを探します。 使うのはmasterの現在の最新 662dea7501d48f6cd70ace0ba39d1ebf3a089715 です。一度makeをすることによりファイルをキャッシュに乗せた後、make cleanします。その後makeを並列オプションを変えて実行時間を計測し、毎回make cｌeanします。これにより、実行時間の計測は再現性の高い精度（誤差1%未満）で行うことができます。もしメジャーフォルトが発生した場合にはファイルがキャッシュから追い出されている可能性が高いため、その後の計測に悪影響を与える可能性があります。その場合、この手順を最初から行うことによりなるべく条件を均一にします。

計測は、E5-2603 v3(1.6GHz, 6Core 12Thread)上、ネイティブのGNU/Linuxで行いました。より多くのCPUの種類、環境での計測は今後の課題とさせてください。 また、コンパイルは二週間前に作ったgcc8.2.0（-O3 -march=nativeでセルフホストコンパイル済み）を使いました。コンパイルするだけならもっと古いバージョンのgccを使った方が速いようです。

オプション 実行時間 備考
指定なし(直列) 447秒
-j 2 235秒
-j 3 163秒
-j 4 128秒
-j 5 108秒
-j 6 95.2秒 コア数
-j 7 93.9秒
-j 8 94.4秒
-j 9 95.6秒
-j 10 95.2秒
-j 11 95.6秒
-j 12 95.8秒 スレッド数
-j 24 97.7秒
-j 98.1秒 メジャーフォルト発生するもスワップはなし

実験結果はこのようになりました。どうやらコンパイルする仕事は同時マルチスレッディングを使うとかえって遅くなる仕事であるようです。驚くべきことに、並列オプションは-j 7が最も速くコンパイルできるという結果になりました。コア数＋1の設定が良いという言説はなかなか理解しがたいものですが、実験してみると正しいようです。理由はよくわかりませんが……。

-jを行った場合、メジャーフォルトが発生しました。しかし、スワップは起こらなかったので、単にキャッシュを追い出したに過ぎないようです。とはいえ、OSの仕事が増えてしまったため時間が余計にかかっています（systemの実行時間が、他の場合は40秒程度に対して-jの場合のみ46秒）。鬼斬弐のコンパイルでは150プロセス程度しか同時に実行されないため劇的な性能低下はまぬがれましたが、もっと大規模なものをビルドする場合はスワップが発生して悲惨なことになるものと思われます。このようにスワップが発生しないとわかっているのであれば、よく考えずに-jを指定しても最適なオプション指定と大差ないため、最適なオプションが分からないときはとりあえず-jを指定しておく、というのもあながち間違いとは言い切れない感じがあります。

今年ももう終わりですね。皆様よいお年を。

RISC-Vのシミュレーション環境を構築した

そろそろクリスマスですね。ltmpcを作ってからもう一年たってしまったのかという思いでいっぱいです。

github.com

さて、前回作ったRISC-V用のgccですが、残念ながら手元にRISC-Vの命令セットが動くコンピュータがないため、コンパイルしたプログラムを動かすことができません。 そこで、シミュレータを使って動かします。

シミュレータにはいくつか種類がありますが、公式が出しているSpikeというシミュレータを使うことにします。 github.com

ただし、これ単体でビルドすることはできず、依存ライブラリを先にインストールしておく必要があります。さらに、Spikeのビルドに成功したとしても、proxy kernel(pk)がないとほとんどのプログラムは動きません。 proxy kernelというのは、要するにOSの仕事をやってくれるような（RISC-Vの命令を使った）プログラムコードのようです。

……という失敗があったので、Spikeだけをビルドしようとするのはやめましょう。素直に公式が出している、RISC-Vツールチェイン*1を全てビルドすることにします。

github.com

やり方は簡単で、

$ git clone https://github.com/riscv/riscv-tools.git
$ git submodule update --init --recursive
$ sudo apt-get install autoconf automake autotools-dev curl libmpc-dev libmpfr-dev libgmp-dev libusb-1.0-0-dev gawk build-essential bison flex texinfo gperf libtool patchutils bc zlib1g-dev device-tree-compiler pkg-config libexpat-dev
$ export RISCV=/home/lpha/riscv/toolchain
$ ./build.sh

とやればよさそうです。

ただ、apt-get を行った際に perl-base のバージョンと bison flex texinfo libtool-bin の依存バージョンが異なるという衝突が発生し、面倒なことになりました。 これらがインストールされていないとビルドに失敗するため、これは大きな問題となります（ビルドの途中で失敗するうえ、ビルドに失敗した後にやり直すとまた始めからになってしまうので大変な時間ロスになります）。

aptitude コマンドを使うと、この問題の解決策が三つ表示されます（これはおそらく、何がインストールされているかによると思われます）。 そのうち二つは「インストールをあきらめる」という趣旨でしたが、これでは解決になりません。 三つ目の解決策は「perlのバージョンを下げる」というものであり、これを実行することで依存関係の衝突の問題を解消することができました。

このままでは依存関係の衝突が解消されただけで、問題の bison flex texinfo libtool-bin はまだインストールできていないので、忘れずにインストールしておきます（これに気づかずに何度もビルドに失敗しました……）。

ビルドには、すごい時間がかかります。/usr/bin/timeコマンドで計測してみたところ、二時間ほどかかったようです。

RISC-V Toolchain installation completed!
2104.01user 1129.07system 1:49:00elapsed 49%CPU (0avgtext+0avgdata 543192maxresident)k
0inputs+0outputs (0major+150543612minor)pagefaults 0swaps

シミュレータを使うには、以下のようにします。

$ /home/lpha/riscv/toolchain/bin/spike pk Hello.out

あれ、おかしいですね、PCが負の番地に飛んでクラッシュしました。

どうやら、先週ビルドしたRISC-V用のgcc8.2.0が出すプログラムは微妙に狂っているようです。

ツールチェインの中に含まれるgcc7.2.0を使ってコンパイルしたものは正しく動きます。

$ /home/lpha/riscv/toolchain/bin/spike pk Hello.out
Hello, world!

一命令ごとに実行するためには、対話的デバッグ実行オプション-dをつけます。

$ /home/lpha/riscv/toolchain/bin/spike -d pk Hello.out
:

たとえば、until pc 0 1034cなどと打ち込むことで、プログラムカウンタ(PC)が0x1034cになるまで実行をスキップできます（実は落とし穴、後述）。 この時、pc 0となっているのは、0番のコアのPCがその値になるまで、という意味です。どうやらマルチコア対応もされているようですね、すごいです。

until pc 1034cなどと打ち間違えてもスルーしてしまうのはかなり不親切です。うっかりしがちなので気を付けます。

ここでエンターキーを押せば、一命令ずつ実行されていきます。

reg 0 spなどと打ち込むことでそのレジスタの値を出力することができます。このreg 0というのはやはり0番のコアのレジスタだという意味ですね。 レジスタの名前はどうもABIで定められたものしか使えず、x2のような指定ができない点は不便です。

reg 0とだけ打ち込むことで全部のレジスタの値を出力できます。

mem 0 7f7e9b50などと打ち込むことでメモリの特定番地の値を8Byte分ダンプすることができます（アラインがあっていなくても8Byte分出てきます）。

さて、0x1034c番地はHello.outのエントリーポイントなのですが、until pc 0 1034cと打ち込むとインタラプトが発生したと出力されます。 その後エンターキーを押して行ってもその付近（0x1034c番地にあるのは0x10378番地へのjal命令ですが、そこでもない）を実行している様子はないため、不可解な状況です。

これは実は、OSのローダープログラムが動いた後に本体プログラムにジャンプした瞬間であり、初めて見るメモリ番地だったので、命令メモリを参照した際にページフォルトが発生したのが原因です。 エンターキーを押して行った時に表示されるのは、プロキシカーネル内の、ページフォルトからの復帰コードだったわけです。

そのため、もう一度until pc 0 1034cと打ち込む必要があります。gdbみたいに上キーを押しても履歴が出てくるわけではないので本当に打ち込む必要があります。面倒くさいですね……。

SpikeはISAシミュレータとうたっていますが、実際にはページフォルトへの対応をproxy kernelのコード（これもRISC-Vの命令列で行ったりと、かなり深いレベルまでシミュレーションしてくれるようです。

ログを吐かせるオプション-lをつけて実行することで命令列をダンプすることができます。 これを使って0x1034c番地に来るのが何命令目なのかを数えてみたところ、285123命令目でした。本体プログラムが実行されるまでにこれだけの命令が実行されているとすると結構すごいですね。

*1:リポジトリの名前はtoolsになっているけれどなんでだろう

gcc8.2.0をソースからビルドした

環境構築がうまくいかないとつらいものです。うまくいったという情報がweb上にあるだけで助かったりします。

うまくいったので記録に残しておきます。

gcc8.2.0, x86向け

制約

  • 管理者ではないので/bin/とかそういうところにはインストールできません。/home/lpha/gcc82/以下にインストールすることにします。
  • もともとインストールされているgcc（というよりはデフォルトで指定されているアセンブラのas 2.25.1）のバージョンが低く*1、-march=nativeでコンパイルすると知らない命令だとエラーを出します*2。この部分を改善したいです。

方法

  • configureスクリプトのオプションとして、--prefix=/home/lpha/gcc82（最後にスラッシュがあってもなくても同じ）とつけることで、インストールパスを指定できます。
  • GNU binutilsも新しいものをインストールすることで、-march=nativeをつけてもアセンブラがエラーを出さないようにすることができます。

おおざっぱな手順

  1. GNU binutilsをインストールします。これにより、Haswell向けの命令をアセンブルすることができるアセンブラが手に入ります。
  2. もとからあるgccでgcc8.2.0を、Haswell向けの最適化なしでコンパイルし、gcc8.2.0（Haswell特有の命令を使わずに動作するプログラムになっている。Haswell特有の命令を出力できるコンパイラになっている*3）を手に入れます。
  3. 先ほどの成果物でもう一度gcc8.2.0をコンパイルすることでHaswell向けに最適化されたgcc8.2.0を得ることができます。
  4. さらにその成果物でもう一度gcc8.2.0をコンパイルしたとき、同じものが得られることをもって、サニティチェック（念のための確認）とします。

3.の手順は省略可能ですが、コンパイル速度は速い方がいいので最適化されたgccを手に入れることは意義があります。4.の手順も省略可能ですが、3ステージビルドの手順に従う方が楽です。一度のmakeコマンドで2.3.4.の手順が一気に行われます。代わりに三倍の時間がかかることは覚悟しなければなりません。

コマンド

wget https://ftp.gnu.org/gnu/binutils/binutils-2.31.tar.gz
wget http://ftp.gnu.org/gnu/gcc/gcc-8.2.0/gcc-8.2.0.tar.gz
tar xf binutils-2.31.tar.gz 
tar xf gcc-8.2.0.tar.gz & # 時間かかるから先に仕掛けておく、binutilsをmakeしている辺りで終わるはず
cd binutils-2.31
mkdir build
cd build
../configure --prefix=/home/lpha/gcc82/
make -j # 12スレッドで100秒くらい
make install -j
cd ..
cd ..
cd gcc-8.2.0
contrib/download_prerequisites
mkdir build
cd build
../configure --enable-languages=c,c++ --prefix=/home/lpha/gcc82/ --disable-multilib
make -j STAGE1_CFLAGS='-march=corei7-avx -O3' BOOT_CFLAGS='-march=native -O3'" #　かかる時間は、ほとんどIO性能で決まる
make install

注意点

  • 二つの./configureで指定する--prefixは同じにすること
  • ./configureなどと、configureスクリプトをtarball（.tar.gzファイル）を展開したディレクトリ直下でやらない（buildディレクトリを作るなどする）こと
  • 逆に、contrib/download_prerequisitesはtarballを展開したディレクトリ直下で行うこと（contribディレクトリに入ってはいけない）

オプションについて

多くの「gccをソースからビルドしてみた」記事では、ブートストラップ（3回ビルドするやつ）をやっておらず、どのようにオプションを設定するべきかが分かりません。

以下の記事は3ステージビルドのオプションについても詳しく解説されており、有用でした。

CentOS6.xでGCC5.2をOS標準の4.4.7と共存できるようにソースビルドした - Qiita

gcc8.2.0, RV64GC

要するに、クロスコンパイラの作成です。

RV64GCとは、RISC-Vという命令セットアーキテクチャの64bit版で、使える命令セットがGeneral Instructions（整数系命令(I)・乗除算命令(M)・アトミック命令(A)・単精度浮動小数点数演算命令(F)・倍精度浮動小数点演算命令(D)の全部が使える）+Compressed Instructions（命令の長さが32bitではなく16bitの命令群）だということを示しています。

制約

  • Linux subsystem for Windowsを使って行ったので、sudo apt-get install ...などが使えます。
  • インストール先は、/home/lpha/rv64gc/以下にします。

コマンド

git clone --recursive https://github.com/riscv/riscv-gnu-toolchain # 30分くらいかかる
cd riscv-gnu-toolchain
sudo apt-get install autoconf automake autotools-dev curl libmpc-dev libmpfr-dev libgmp-dev gawk build-essential bison flex texinfo gperf libtool patchutils bc zlib1g-dev libexpat-dev

texinfoが、バージョンの依存関係の制約を満たせないと怒られましたが、aptitudeコマンドに促されるまま、一部の依存ライブラリのバージョンをダウングレードして通しました。もっとうまい方法はあったのでしょうか……？

./configure --prefix=/home/lpha/rv64gc
make linux -j # 8スレッドで45分

依存関係の問題を解決するのに多少手間取りましたが、それ以外には難しいところはありませんでした。

*1:as 2.25.1が出たのは2014年、Haswellが発売されたのは2013年6月なのになぜ対応していないのでしょう？

*2:しかし一部のAVX2命令には対応している

*3:これはgcc8.2.0をコンパイルしたのとはあまり関係なく、デフォルトで使用するアセンブラが先ほどインストールした新しいasになっていることが重要です

CPUの浮動小数点演算性能やクロック周波数を測定する

CPUのカタログスペックはメーカーが公表しているので、それを参照することもできますが、本当にそうなのか確かめてみるという話です。 最近のIntelのCPUしか持っていないので、それでしか確かめていないませんが、四種類のCPUで試してみました。

CPUのクロック周波数

CPUのクロック周波数を求めることも、意外と簡単です。依存関係が直列につながっている一連の命令列を何クロックで処理できるかを計測し、それを実時間で割ればクロック周波数が分かります。 それ以外の命令も実行する必要があるので計算が狂ってきそうに思えますが、実際には並列かつアウトオブオーダーに実行されるため、分岐予測が当たる前提のもと、それらを考慮する必要はありません。

#include <iostream>
#include <thread>
#include <chrono>
#include <atomic>

std::atomic<bool> begin;
std::atomic<bool> end;
std::atomic<double> x;

void job() {
  double a = 0.0;
  while( !begin.load() );
  while( !end.load() ) a += 1.0;
  x.store(a);
}

int main() {
  std::thread th( &job );
  const auto startT = std::chrono::system_clock::now();
  begin.store( true );
  system( "sleep 5" );
  end.store( true );
  th.join();
  const auto endT = std::chrono::system_clock::now();
  const auto time = std::chrono::duration_cast<std::chrono::nanoseconds>( endT - startT ).count();
  std::cout << (long long)x << std::endl;
  std::cout << time << std::endl;
  std::cout << x*3 / time << " GHz" << std::endl;
}

コンパイルは、-std=c++11 -pthread -O3 -march=nativeで行います。

直列に実行すべき命令は、a += 1.0;の部分です。この部分は（SandyBridge以降のAVX命令に対応している場合）vaddsd命令となります。 この命令のレイテンシ（結果が出て次の命令で使えるようになるまでの時間）は3クロックなので、加算が行われた回数の三倍がかかったクロック数になります。 これをかかった時間で割ることにより、クロック周波数を求めることができます。

実測してみた結果はこれです。十回行ってもっともよかった結果を採用します。

  • Intel(R) Core(TM) i5 2540M(ターボブースト時3.30GHz)→3.13GHz
  • Intel(R) Core(TM) i5 7200U(ターボブースト時3.10GHz)→3.06GHz*1
  • Intel(R) Xeon(R) E5-2643 v3(ターボブースト時3.70GHz)→3.66GHz
  • Intel(R) Xeon(R) E5-2603 v3(1.60GHz)→1.58GHz

おおむねカタログスペックと同じ値を実験でも得ることができました。

CPUの浮動小数点演算性能

無駄な計算をするだけであれば、CPUの浮動小数点演算性能の理論値の90%程度を出すことは簡単です。 無駄な計算は、コンパイラの最適化が見抜けないように注意して書く必要があります。

#include <iostream>
#include <chrono>
#include <thread>
#include <atomic>
#include <cmath>

constexpr int ND = 32;
constexpr int NThreads = 4;
std::atomic<bool> ready;

void task( int N_loops ) {
    double x[ND];

    for( int i = 0; i < ND; ++i ) {
        x[i] = 1e-9 * i;
    }
    while( !ready.load() );
    for( int i = 0; i < N_loops; ++i ) {
        for( int j = 0; j < ND; ++j ) {
            x[j] = std::fma( x[j], x[j], x[j] );
        }
    }
    for( int i = 0; i < ND; ++i ) {
        std::cout << x[i] << " ";
    }
    std::cout << std::endl;
}

int main( int argc, char* argv[] ) {
    const int N = std::stoi( argv[1] );
    std::thread th[NThreads];
    for( auto& t : th ) {
        t = std::move( std::thread( &task, N ) );
    }
    const auto start = std::chrono::system_clock::now();
    ready.store( true );
    for( auto& t : th ) {
        t.join();
    }
    const auto end = std::chrono::system_clock::now();
    std::cout << N * ND*2. * NThreads / std::chrono::duration_cast<std::chrono::nanoseconds>( end - start ).count() << "GFLOPS" << std::endl;
}

コンパイルは、先ほどと同じオプションで行います。NThreadsは、そのCPUの動かせるスレッド数に応じて適宜変更してください。

std::fmaを計算するには、足し算と掛け算の二演算が必要であるため、2FLOPをこなしたことになります。

理論性能は、AVXの場合、ymmレジスタにdoubleが4個入り、二つの命令が同時に実行可能であるので8FLOP/clock・Coreとなります。 また、AVX2の場合は、2FLOPに相当するfma命令が同時に二命令実行可能であるため、16FLOP/clock・Coreとなります。

実験してみた結果はこれです。同様に、十回行ってみて最も良いものを採用します。

  • Intel(R) Core(TM) i5 2540M(8FLOP/clock×3.30GHz×2Core=52.8GFLOPS)→2.09GFLOPS
  • Intel(R) Core(TM) i5 7200U(16FLOP/clock×3.10GHz×2Core=99.2GFLOPS)→94.99GFLOPS

SandyBridge世代のi5 2540MはAVXしか動かせず、AVX2で追加されたFMA命令に対応していないため、std::fmaがライブラリ関数コールとなり、非常に低速になります。 そこで、以下のように計算部分を変更します。

    for( int i = 0; i < ND; ++i ) {
        x[i] = 1 + 1e-9 * i;
    }
    while( !ready.load() );
    for( int i = 0; i < N_loops; ++i ) {
        for( int j = 0; j < ND; ++j ) {
            x[j] = x[j] * x[j];
        }
    }

この時、計算部分は以下のようにコンパイルされており、最適になっています。

 .LBB0_13:                               # =>This Inner Loop Header: Depth=1
 vmulpd %ymm7, %ymm7, %ymm7
 vmulpd %ymm6, %ymm6, %ymm6
 vmulpd %ymm3, %ymm3, %ymm3
 vmulpd %ymm0, %ymm0, %ymm0
 vmulpd %ymm1, %ymm1, %ymm1
 vmulpd %ymm2, %ymm2, %ymm2
 vmulpd %ymm4, %ymm4, %ymm4
 vmulpd %ymm5, %ymm5, %ymm5
 vmulpd %ymm7, %ymm7, %ymm7
 vmulpd %ymm6, %ymm6, %ymm6
 vmulpd %ymm3, %ymm3, %ymm3
 vmulpd %ymm0, %ymm0, %ymm0
 vmulpd %ymm1, %ymm1, %ymm1
 vmulpd %ymm2, %ymm2, %ymm2
 vmulpd %ymm4, %ymm4, %ymm4
 vmulpd %ymm5, %ymm5, %ymm5
 addl $-2, %ecx
 jne .LBB0_13

結果は、以下の通りです。

  • Intel(R) Core(TM) i5 2540M(8FLOP/clock×3.30GHz×2Core=52.8GFLOPS)→48.11GFLOPS

元のstd::fmaを使ったソースコードで出力されるアセンブリコードは、ここまで品質が良くなく、途中でレジスタ移動が発生しています。 イントリンシックを使って最適な機械語コードになるようにしてみます。

#include <iostream>
#include <chrono>
#include <thread>
#include <atomic>
#include <immintrin.h>

constexpr int NR = 16;
constexpr int ND = 64;
constexpr int NThreads = 12;
std::atomic<bool> ready;

void task( long long N_loops ) {
  double x[ND];
  __m256d ymm[NR];

  for( int i = 0; i < ND; ++i ) {
    x[i] = 1e-9 * i;
  }
  for( int i = 0; i < NR; ++i ) {
    ymm[i] = _mm256_load_pd( &x[i*4] );
  }
  while( !ready.load() );

  for( long long i = 0; i < N_loops; ++i ) {
    for( int j = 0; j < NR; ++j ) {
      ymm[j] = _mm256_fmadd_pd( ymm[j], ymm[j], ymm[j] );
    }
  }
  for( int i = 0; i < NR; ++i ) {
    _mm256_store_pd( &x[i*4], ymm[i] );
  }
  for( int i = 0; i < ND; ++i ) {
    std::cout << x[i] << " ";
  }
  std::cout << std::endl;
}

int main( int argc, char* argv[] ) {
  const long long N = std::stoll( argv[1] );
  std::thread ts[NThreads];
  for( int i = 0; i < NThreads; ++i ) {
    ts[i] = std::move( std::thread( &task, N ) );
  }
  const auto start = std::chrono::system_clock::now();
  ready.store( true );
  for( int i = 0; i < NThreads; ++i ) {
    ts[i].join();
  }
  const auto end = std::chrono::system_clock::now();
  std::cout << N * ND * 2. * NThreads / std::chrono::duration_cast<std::chrono::nanoseconds>( end - start ).count() << " GFLOPS" << std::endl;
}

これを使った時の結果は以下の通りです。

  • Intel(R) Core(TM) i5 7200U(16FLOP/clock×3.10GHz×2Core=99.2GFLOPS)→98.02GFLOPS
  • Intel(R) Xeon(R) E5-2643 v3(16FLOPS/clock×3.70GHz×6Core×2Socket=710.4GFLOPS)→669.8GFLOPS
  • Intel(R) Xeon(R) E5-2603 v3(16FLOPS/clock×1.60GHz×6Core=153.6GFLOPS)→152.2GFLOPS

最高の場合、理論性能の99%程度を出すことに成功しています。E5-2643v3ではそこまで達成できていませんが、全てのコアをターボクロック周波数にできない制約によるもの（つまり括弧内の計算による理論性能は正しくない）だと思われます。

*1:vaddsd命令のレイテンシは4クロックなので該当部分を変更したソースコードで実験