yumetodoの旅とプログラミングとかの記録

旅や登山の記録やプログラミング関連の話とかフリーソフト紹介とか

DeepL翻訳: Using Profile Information to Assist Classic Code Optimizations

Using Profile Information to Assist Classic Code Optimizations

http://impact.crhc.illinois.edu/shared/journal/spe.profile-classic.91.pdf

note: 興味のあるところだけ翻訳ツールに投げ込んでいる

SUMMARY

本論文では、古典的なコードの最適化を支援するためにプロファイル情報を自動的に生成する最適化コンパイラの設計と実装について説明する。 このコンパイラには、従来の最適化コンパイラにはあまり見られない、実行プロファイラとプロファイルベースのコードオプティマイザという2つの新しいコンポーネントが含まれています。 実行プロファイラでは、入力プログラムにプローブを挿入し、複数の入力に対して入力プログラムを実行し、プロファイル情報を蓄積し、この情報をオプティマイザに供給する。 プロファイルベースのコードオプティマイザは、プロファイル情報を利用して、従来の全体最適化手法では見えなかった新たな最適化の機会を明らかにします。 実験の結果、プロファイルベースコードオプティマイザは、高品質のグローバルコードオプティマイザによってすでに最適化されている量産Cプログラムの性能を大幅に向上させることがわかりました。

CODE OPTIMIZATION ALGORITHMS

Optimizing frequently executed paths

このセクションで紹介するプロファイルベースのコード最適化はすべて、最も頻繁に実行されるパスの最適化という単一のコンセプトを追求しています。このコンセプトについて、例を挙げて説明する。図2は、ループを表す重み付きオウグラフである。 をプログラムする。基本ブロック{A B C D E F}のカウントは、それぞれ{100,90,0,0,90,100}である。 {A → B , A → C , B → D , B → E , C → F , D → F , E → F , F → A} のarc_countは次の通りである。 {90,10,0,90,10,0,90,99}, respectively. 明らかに、この例で最も頻繁に実行されるパスは、基本ブロックシーケンス<A B E F>である。 従来、非ループベースの古典的コード最適化の定式化は保守的であり、いかなる基本ブロックの実行時間を増加させる可能性のある変換も実行しない。ループベースの古典的コード最適化の定式化は、ループ本体全体を全体として考慮し、非常に偏った「if」文のためにループ本体内のいくつかの基本ブロックがほとんど実行されないケースは考慮しない。このセクションの残りの部分では、より積極的な判断を行い、より多くの最適化の機会を探る、いくつかのプロファイルベースのコード最適化について説明します。

私たちは、頻繁に実行されるパスを表現するために、スーパーブロックと呼ばれるシンプルなデータ構造を使用することを提案します。スーパーブロックは、基本ブロックの線形シーケンスであり、シーケンス内の最初のブロックからしか到達できない。プログラム制御は、どの基本ブロックからでもスーパーブロックを離れることができます。 実行がスーパーブロックに達したとき、そのスーパーブロック内のすべての基本ブロックが実行される可能性が非常に高い。 スーパーブロックの基本ブロックは、コード上では連続である必要はありません。しかし、この実装では、オプティマイザが考える限り、スーパーブロックのすべてのブロックが常に連続するようにコードを再構築しています。

Forming super-blocks

スーパーブロックの形成は、トレース選択とテールデュプリケーションという2段階の手順で行われます。 トレース選択では、順番に実行される傾向がある基本ブロックを特定し、トレースにグループ化する。 トレースの定義は、プログラム制御が最初の基本ブロックから入ることに制限されないことを除いて、スーパーブロックの定義と同じである。 トレース選択は,トレーススケジューリングで初めて用いられた [7] [8] . いくつかのトレース選択アルゴリズムの実験的研究が[9]に報告されている. トレース選択アルゴリズムの概要を図 3 に示す. best_predecessor_of(node)関数は,ソース基本ブロックがまだマークされていない場合,nodeのソース基本ブロックの中で最も可能性が高いものを返す. トレースの成長は、現在のノードの最も可能性の高いソース基本ブロックがマークされたときに停止される。 best_predecessor_of(node)関数は、対称的に定義される。

図2はトレース選択の結果である。 点線の枠がトレースを表している。 トレースは{A, B, E, F }, {C }, {D }の3つである。 トレース選択後、プログラム制御が最上位の基本ブロックにしか入らないようにするため、トレースの末尾部分を複製してスーパーブロックに変換する。 テール部の複製アルゴリズムは図4に示す。 図2の例で考えると、{A, B, E, F }トレースに入る制御経路は基本ブロックFで2つあることがわかる。 そこで、基本ブロックFから始まる{A、B、E、F}トレースの最後尾部分を複製する。 複製された各基本ブロックは、新しいスーパーブロックを形成し、関数の末尾にアプライされる。 その結果が図5である。 ジャンプ命令を排除するために、末尾の複製後にさらにコード変換が行われる。 例えば、図5のFスーパーブロックを複製し、それぞれの複製をCとDのスーパーブロックと組み合わせて、2つの大きなスーパーブロックを形成することができます。 重複を抑制するために、実行回数が閾値以下(例えば、1回の実行で100回)の基本ブロックは、トレース選択プロセスから除外している。 また、コンパイル時間の増加を抑制するために、プロファイルベースのコード最適化からも除外する。

Formulation of code optimizations

name scope
constant propagation super-block
copy propagation super-block
constant combining super-block
common sub expression elimination super-block
redundant store elimination super-block
redundant load elimination super-block
dead code removal super-block
loop invariant code removal super-block loop
loop induction variable elimination super-block loop
global variable migration super-block loop

Table 2 Super-block code optimizations.

表2は、プロファイル情報を利用するために拡張した古典的なコードの最適化のリストです。 これらの古典的なコード最適化の原型は、[1] [19] に記載されています。 表2のスコープ欄には、これらのコード最適化の拡張スコープを記述しています。 非ループベースのコード最適化は、一度に1つのスーパーブロックに対して動作する。 ループベースのコード最適化は、一度に1つのスーパーブロック・ループに作用する。 スーパーブロックループとは、最後のノデから最初のノデまで、頻繁にバックエッジが取られるスーパーブロックのことです。 オプティマイザはまず、ライブ変数分析を適用して、スーパーブロックの境界を越えてライブしている変数を検出し、次に1つのスーパーブロックを一度に最適化する。 各スーパーブロックに対して、プロファイルベースのコード最適化を1回以上適用し、限界まで、またはそれ以上の機会が検出されなくなった時点で、最適化を終了する。 以下の説明では、各コード最適化は、前提条件関数とアクション関数で構成されています。 前提条件関数は、最適化の機会を検出し、変換によってプログラム全体の性能が向上することを確認するために使用されます。 アクション関数は、実際のコード変換を実行する。 コードの最適化を行うには、オプティマイザが最適化の対象となりそうな命令群を特定します。 次に、前提条件関数が呼び出され、各セットについて最適化の判断が行われます。 前提条件関数からの承認を得て、アクション関数が対象となるセットをより効率的な同等品に変換する。 命令 $op(i)$ が変更する変数の集合を $dest(i)$ とする。 また、$op(i)$がソースオペランドとして必要とする変数の集合を$src(i)$と表記する。 また、$op(i)$の演算コードを $f_i$ とする。 したがって、$op(i)$ は $dest(i) \leftarrow f_i(src(i))$ という演算を指す。

Local optimizations extended to super-blocks

ローカルコードの最適化には、スーパーブロックに簡単に拡張できるものがいくつかあります。 これらのローカル最適化には、定数伝搬、コピー伝搬、定数結合、共通部分式消去、冗長ロード消去、冗長ストア消去などがある [1] [19].

従来、ローカル最適化は基本ブロックにまたがって適用することはできず、グローバルコード最適化は実行可能な各パスを平等に考慮する必要がありました。 しかし、実行頻度の低いパスによって最適化の機会が阻害されるケースはよくある。 そのため、実行頻度の低いパスを体系的に解析から除外しない限り、実行頻度の高いパスに最適化を適用することができない。 尾部重複によるスーパーブロックの形成は、この効果を実現する。 したがって、プロファイルベースのコード最適化は、従来のコード最適化よりも多くの機会を見つけることができます。

ローカルコードの最適化がスーパーブロックに適用されるとより効果的である理由を説明するために、図6に示す共通部分式除去のケースを考えてみましょう。 元のプログラムは図6(a)に示されている。 トレース選択とテール複製を行うと、図6(b)のようになる。 尾部重複のため、opBからopCに到達できないので、opAとopCに共通部分式消去を適用することができる。


www.DeepL.com/Translator(無料版)で翻訳しました。

202210蔵王紀行記: 2日目編

yumetodo.hateblo.jp

もともと計画していた2日目の工程

蔵王温泉(泊)10:20→11:05山形11:30→12:28大石田12:35→13:11銀山温泉16:35→17:02尾花沢待合所17:25→19:15仙台20:00→21:04アクティブリゾーツ宮城蔵王(遠刈田温泉)(泊)

銀山温泉に突撃して仙台に48ライナーで抜けて、遠刈田温泉に泊まるというものだ。

さて、実際はどうなったのだろうか。見ていく。

朝食と宿からの景色

朝食付きで予約したので朝食を食べた。結構量があるので案外食べるのに時間がかかった。

さて、実は親に旅行してることを報告すると紅葉の写真を所望されていた。

宿から紅葉見えたしヨシ!

もっと紅葉を味わおうとする: 樹氷高原駅

宿をチェックアウトしててくてくあるいてバスターミナルに行こうかとしていたら、別の宿泊者の方が蔵王ロープウェイまでの送迎を依頼していたらしく、ちょうど出るところであったので載せてもらった。

たどり着くと残念ながらそこのロープウェイは係員の方がコロナに感染したとかで、閉鎖されていた。

しかし蔵王には他にも2つロープウェイがある。この日やっていたのはここから更に奥に進んだもう一つのロープウェイである。

チケット売り場にはけっこう人が並んでいた。この時点でもうすぐ10時といったところであったから、銀山温泉へ行くための10:20のバスは迫っていた。つまり、銀山温泉か、それとも蔵王の紅葉か。その二者択一を迫られたわけである。

紅葉には勝てなかったよ・・・。

奥にみえる緑の鉄塔がこの日は止まっていた蔵王中央ロープウェイである。

今回乗ったロープウェイは、以前大学のスキーの授業で来たときに何度も乗っているが、秋に乗るのは初めてである。

まずは樹氷高原駅に向かった。

ゲレンデマップ - 山形蔵王温泉スキー場|蔵王索道協会

そこから林を抜けると百万人ゲレンデに出る。

28番リフト降り口

2の渡り方向。椅子に座ると吹き上げてくる風が少し肌寒い。

百万人ゲレンデを見下ろす。スキーを履いてきたときは緩斜面に思えたのに歩くと案外急である。

28番リフト降り口を見上げる

地蔵山頂駅へ

ゲレンデマップ - 山形蔵王温泉スキー場|蔵王索道協会

はじめは紅葉終わりがけの景色を駆け抜けていたが

気がつけば色を失っていく。

地蔵山頂駅の景色もすこし白い。

手すりをよく見ると斜めの同じ方向に氷がついている。

木の枝にも・・・。

これらは霜氷と呼ぶらしい。

hp.otenki.com

冬に来ると埋まりがちなお地蔵様もきちんと拝めた。

蔵王のお釜に挑む

さて、ロープウェイ登る前にはただの一ミリもそんなつもりはなかったのですが、掲示されている地図を見ると案外蔵王のお釜が近いことに気が付きます。お釜のほうにいくバスは運行終了と出ていましたから完全に想定外でしたが、コースタイムを計算すると往復2時間半、その後お昼ごはんと考えれば全然行けそうです。検討してみましょう。

まず天気は想定に反してかなり良くなっていました。数日前に見た曇り時々雨とは一体・・・。

装備ですが、風を凌ぐアウターと保温する薄手のセーターと長袖の服。そして手袋。そしてビニール傘。すこし薄い長袖のズボン。ズボンに不安が残りますが昼間に行動するぶんには問題なさそうです。ビニール傘にはこの際壊れてもいいので杖として役目を果たしてもらいましょう。

食料は東京から持ち込んでまだ食べてなかったフランスパン風味の謎のロールパンが2個あります。熊野岳で食べるのにちょうど良さそうです。

というわけで登り始めました。まずは標高差70mを登って地蔵山

足元の霧氷と奥の低い山の紅葉の対比がいいですね。しらんけど。

一旦下って木道を進みます。そこから少し歩きにくい石畳を進みます。

地蔵山山頂をまく道と合流するとそこはワサ小屋跡です。

どんどん進む。

熊野岳付近、そしてお釜

熊野岳避難小屋に到着。熊野岳に直登するルートも地図上はあるはずが、当日の私はその分岐を見つけられなかった。

登ってきた道

避難小屋

お釜は避難小屋からだと影に隠れて中まで見えなかった。。

これも避難小屋の跡地?

とにかく尾根なので風が強いわけで、これを利用して風をしのいで小休憩を取った。

ここから熊野岳山頂へはすぐで、歩きやすい道なので駆け足で進んでいると立て看が・・・。

避難小屋から5分、山頂に到着です。

この神社の小屋で休憩をしました。

中で出会った年配の男性2人組のかたとお話をしていていたら、たくさん水を持ってきたからとお湯を沸かしてもらってスティックコーヒーときゅうりの漬物をごちそうになりました。自分が変わりに渡せるものがなかったのですこし恐縮しつつ、話していると、福島の方から来た方らしく、刈田岳からピストンしようと熊野岳に来たようです。

この蔵王も近年火山活動が活発なので、話は御嶽山噴火の話になり、ここなら噴石が来ても助かるかもしれない、いやだめだろうみたいな話をしていました。

さて、いよいよお釜を見に行こうと、馬の背分岐へ向かって下っていきます。

馬の背分岐に到着です。奥には先程見た避難小屋が見えますね。

そして振り返ってもうすこし崖際に近づくと・・・

お釜です。緑色の水が見えます。きれいですね!

下山

蔵王では風の向きが常に一定なので、霧氷の付き方も指向性があります。したがって、同じ道でも行きと帰りではだいぶ表情を変えるわけです。

山形駅へ、遠刈田温泉

昼食を食べ、お土産とか記念品を買いました。

バスターミナルに戻り山形駅にいきます。

バス待ちをしているときに、年配の女性2人組の方々と話が盛り上がって蔵王のお釜の写真を見せたりしてました。

山形駅に到着です。途中からたくさんの高校生が乗り込んで来ました。まあ路線バスですからね。見た目が高速バス感ありますが路線バスです。

山形駅からは仙山線で仙台を目指します。バスVS鉄道乗り継ぎ対決旅で話題の山寺駅作並駅東北福祉大前駅を通ります。

tabiris.com

仙台駅で遠刈田温泉行きの高速バスに乗ります。遠刈田温泉に行くバスは34番乗り場、ところで48ライナーは21番乗り場ということでちょうど道路挟んで向かいにあるようですね。48ライナーの乗り場には結構人が並んでいました。

www.daiwaresort.jp

202210蔵王紀行記: 計画~1日目編

動機

7月から10月前半まで、猛烈に仕事に追われて疲れていた私は、消化できなかった夏季休暇2日分と代休1日分を10/21~10/25につぎ込んだ。

疲れた体には温泉だよなーということで最初は草津を考えていたが、場所によっては紅葉の季節かということもあり、山形県銀山温泉に行こうかなとおもった。

以前銀山温泉に行ったのは免許を取りにさくらんぼ東根に合宿しに行ったときであった。このときは到着の時間が遅くて日帰り入浴を堪能できなかったのでそのリベンジを試みようというわけだ。

ところが21日の夜に調べると銀山温泉の宿泊の空きは存在しなかった。であるならば銀山温泉の日帰り入浴が行われる11時から14時台を狙うことにしようということで、宿泊地を同じ山形県蔵王温泉にした。

どういうわけか蔵王温泉で2泊3日の予約ができなかったので次なる宿泊地を探すと蔵王山を挟んで反対側に遠刈田温泉という温泉があることがわかった。

遠刈田温泉はバス旅界隈では有名で、福島から仙台に抜けるときに、福島-国見役場-(徒歩)-越河清水-白石-遠刈田温泉-(徒歩or 村田役場前/村田中央経由)-川崎役場前-仙台という乗り継ぎルートが知られている。

tabiris.com

上記ローカル路線バスの旅Z 第19弾の実際ルートでは季節運行土日のみの遠刈田温泉-蔵王刈田山頂-山交バスターミナルというルートを使っていることからもわかるように、蔵王温泉遠刈田温泉は近い位置にある。

記事中にもあるように仙台-さくらんぼ東根-尾花沢待合所-新庄を結ぶ長距離路線バス、48ライナーが運行されている。これも乗ってみたいと考えた。

計画

銀山温泉直行案

銀山温泉へは山形新幹線大石田駅からバスとなる。

(有)はながさバス 

ところがこのバスがとても使い勝手がよくない。東京始発のつばさに接続する9:50発を逃すと12:35発までない。11時から12時台という日帰り入浴ゴールデンタイムを逃してしまうのだ。

それに目をつぶると次のようなルートが考えられる。

東京→大石田銀山温泉大石田→山形→蔵王温泉(泊)→山形→さくらんぼ東根→仙台→遠刈田温泉(泊)→白石→東京

蔵王温泉先行案

www.yamakobus.co.jp

銀山温泉大石田駅を結ぶバスは途中尾花沢待合所を経由する。この尾花沢待合所には仙台までを結ぶ48ライナーが通る。すると渋滞を加味しなければ、奥羽線から仙山線に乗り継ぐよりも早く仙台にたどり着ける。

24日は平日であることをいかし、休日運休の17:25尾花沢待合所発の48ライナーを捕まえることを考えてみる。

東京→仙台→さくらんぼ東根→山形→蔵王温泉(泊)10:20→11:05山形11:30→12:28大石田12:35→13:11銀山温泉16:35→17:02尾花沢待合所17:25→19:15仙台20:00→21:04アクティブリゾーツ宮城蔵王(遠刈田温泉)(泊)→白石→東京

銀山温泉発を一つ早めるとこうなる

銀山温泉14:55→15:22尾花沢待合所15:35→17:25仙台17:40→18:44アクティブリゾーツ宮城蔵王(遠刈田温泉)

この案のいいところは23日東京発のつばさの時間が自由が効くというところにある。

そんなわけで蔵王温泉先行案を採用することとした。

仙台経由山形入り案

お昼ごはんはさくらんぼ東根にある肉そばやの「そば処 東亭」でどうしても食べたいと思った。

tabelog.com

ここでさくらんぼ東根は48ライナーの経由地である。わんちゃん仙台から48ライナーのほうが福島から先低速運転する山形新幹線より早いのではないかと思った。

東京9:08→10:39仙台11:05→12:13さくらんぼ東根
東京9:24→12:07さくらんぼ東根

さすがに山形新幹線のほうが速かった。

山形新幹線つかうと11930円、仙台まではやぶさ+48ライナーつかうと12250円。値段的にも山形新幹線が勝った。というわけでこの案は没となった。

1日目

新幹線に乗り遅れた、そうだ、越中島に行こう

お昼時にさくらんぼ東根に着けるよう、東京9:24-12:07さくらんぼ東根の新幹線を予約していた。

ところが案の定寝坊し、最寄り駅発で1本乗り遅れた。

新幹線のチケットは駅ネットで予約したものの、紙発券していたた。 指定席券は列車の発車前までなら紙の場合1度だけ変更ができる。

ところが私は東京メトロ東西線に乗っていて大手町駅を目指していた。東西線の大手町09:21着では、東京駅の指定席券売機に9:24までにたどり着くのは困難である。

どうにかならないかと東西線の車内で探し回っていたところあることに気がつく。門前仲町とJR京葉線越中島駅の距離が案外近いのである。

門前仲町に9:15に到着する。Googleの検索では8分となっているから9:23着、少し走れば9:24発の列車が出発する前にたどり着けることがわかる。

当日のGPS記録によれば、5分で門前仲町駅から越中島駅に乗り換え、指定席券売機で指定の変更に成功している。ちなみに門前仲町駅からバスで越中島駅に行くこともできて、当日はバスが後ろを追いかけてきたがバスより20秒先着したのを記憶している。

読者の皆様も東西線にのっていて、やばい、どうやっても発車時刻に間に合わない!というときは門前仲町駅から越中島駅に乗り換えてみてはどうだろうか。

西船橋駅時点で間に合わないことがわかっていたのだからそこで変更すればよかったのではないかという指摘があるかもしれないが極めてそのとおりでありぐうの音も出ない。

指定変更したあとは走ったときにお腹を冷やしたのが行けなかったのか、お腹がぐるぐるなったのでトイレに駆け込んだ。

さくらんぼ東根にて肉そばを食べる

指定変更した山形新幹線にどうにか乗り、福島駅で山形新幹線上りアプローチ線工事の様子を眺めつつ、無事に懐かしのさくらんぼ東根駅に到着した。

「そば処 東亭」は駅から歩いて3分くらいしかかからない。

tabelog.com

うまい。持ち帰りセットもあるが、一人暮らしでは面倒極まるのでなくなく買わなかった。

なぜか山形空港

言ってしまうと悪いのだが、さくらんぼ東根周辺で見どころのある観光地はまあさっぱりない。かといって山形駅方面の電車は出てしまったし、バスもちょうどない。あまりにも暇なのでタクシーを拾って山形空港に行くことにした。

タクシーに乗って空港の手前でちょうど飛行機が離陸していった。空港につくとそこには

なにもなかった。ラフランスの缶ジュースをのみ、景色を眺めようとデッキにむかうと子連れの親子がいた。

「飛行機いないよ、さっき飛んでいったばかりだから数時間飛行機はないんだよ」

と親が子どもに諭すとすこししょぼんとして、しばらくするとかえっていった。

奥羽山脈を眺めて数分。風が寒いので私もあとを追うように退散した。

蔵王温泉までローカル路線バス乗り継ぎの旅

山形空港奥羽本線の直ぐ側にあるが、ターミナルビルが滑走路を挟んで線路と反対側にあるために、鉄道駅からのアクセスが極めてよろしくない。山形駅までリムジンバスは出ているが、飛行機が飛び去ったばかりの時間にバスが出ていようはずもない。

ところが30分ばかり歩いたところに「林木育種場前」というバス停がある。このバス停は天童駅-さくらんぼ東根-北町と結ぶ路線バスである。

ちょうど15:14のバスに乗ると次のようにして蔵王温泉まで乗り継げることがわかった(カッコ内は当日の実際の時刻)。

林木育種場前15:14(15:16)→15:22(15:25)天童駅前15:35(15:37)→16:12(16:15)山交ビルBT→センタービル前16:22(16:23)→16:57(17:04)蔵王温泉バスターミナル

天童駅方面の林木育種場前のバス停はなんと停留所標識がなく、さまよったものの、反対方面行きのバス停の近くでバスに乗ることができた。。

天童駅のバス乗り場は建物内にあり、そういえばローカル路線バス乗り継ぎの旅で見たようなきがする。

天童発のバスで終点の山形駅前まで行っても良かったのだが、遅延気味だったので一つ手前の山交ビルBTで降り、信号斜め向かいのセンタービル前から蔵王温泉行きのバスを捕まえた。

蔵王温泉バスターミナルにつくと、ちょうど別の方が呼んでいたと思われる宿の送迎バスが出発しようとしていたので慌てて飛び乗った。バスターミナルから宿はそこそこ登っていくから、歩いてとなれば大変であったからとても助かった。

ちょうど前日で今年の蔵王刈田山頂行きの山形側のバスが終了した案内があった。

宿泊地はルベール蔵王

www.levert-zao.co.jp

夕食

宿の人に教えてもらって、「桃園」という店に行った。

tabelog.com

陶板焼きを頼んだが、美味しさのあまり写真を取り忘れた。これは深刻なバグである。その後に頼んだ湯豆腐はどうにか写真を撮影したので載せておく。なかなか一人暮らしだと湯豆腐なんてしないので、頼んで正解であった。

近くの席では店の方と地酒の話が盛り上がっていた。「自分は旅行に行ったらそこの地酒を3種類は少なくとも飲むことにしてます」という店員さんの語りを横で聞きつつとても飲みたい気持ちに駆られたが、その後温泉に入るのでワイングラス1杯だけで我慢した。ぐぬぬ