コグノスケ


link 未来から過去へ表示  link 過去から未来へ表示(*)

link もっと前
2023年2月9日 >>> 2023年2月22日
link もっと後

2023年2月10日

卵が割れる階数は?問題

Twitterで見かけて面白かった問題、解法をメモしておきます。

100階建てのビルから卵を落とします。卵はある階よりも低ければ割れませんが、ある階よりも高いと割れます。卵を2つ持っているとき、卵が何階で割れるか調べる方法を提示してください。そのとき卵を落とす最大の回数をできる限り小さくしてください。

という問題です。

基本的な考え方

1階から順に落とせば確実にわかりますが、最大の投擲回数が100回(卵が割れる階数が100Fのとき)になり、最適な方法ではありません。

卵が2個あることを利用し、1個目は複数階を一気に飛ばして(例10F, 20F, 30F, ...)投擲します。例えば10F飛ばしで試すとすると10F, 20F, 30Fで割れず40Fで割れたら、2個目は「最後に割れなかった階の1つ上の階」すなわち31Fから投擲します。このように試すともっと早く卵が割れる階数がわかります。

卵の投擲回数の最大値を計算すると、例えば10F飛ばしであれば1個目が最大10回(10F, 20F, 30F, ..., 90F, 100F)、2個目が最大で9回(x1F〜x9F)なので、19回(卵が割れる階数が99Fのとき)です。100回と比べるとだいぶ少なくなりましたが、まだ無駄が残っています。

答え

固定階数を飛ばす方法だと1個目と2個目の最大の投擲回数の和を見たとき、上の階になるほど悪化します。例えば、

  • 卵が割れる階数が39F: 10F〜30Fまでで3回、31F〜39Fで最大9回 = 12回
  • 卵が割れる階数が99F: 10F〜90Fまでで9回、91F〜99Fで最大9回 = 18回

1個目の投擲方法を変えて最初は10F飛ばし、次は9F飛ばし、その次は8F飛ばし、のようにすると投擲回数の最大値が悪化しないことに気づくと思います。

こんな表で示すとわかりやすいでしょうか。

1個目を投擲する階数次に何階飛ばすか1個目の投擲回数2個目の投擲開始階2個目の最大の投擲回数最大の投擲回数
100 1298 214
97 31194 314
93 41089 414
88 5 983 514
82 6 876 614
75 7 768 714
67 8 659 814
58 9 549 914
4810 4381014
3711 3261114
2512 2131214
1213 1 11112

1個目は12F, 25F, 37F, 48F, 58F, 67F, 75F, 82F, 88F, 93F, 97F, 100Fの順に投擲します。最大で12回です。割れたら最後に成功した階の1つ上の階から投擲すると、最大14回で卵が割れる階数がわかります。

最大の回数になるケースは12通りですが、一例として卵が割れる階数が99Fの場合を示します。12, 25, ..., 100(1個目が割れる), 98, 99(2個目が割れる)の14回になります。

他には1個目を投げる階数を下記のようにしても良いです。

  • 9F, 22F, 34F, 45F, 55F, 64F, 72F, 79F, 85F, 90F, 94F, 97F, 99F, 100F
  • 10F, 23F, 35F, 48F, 56F, 65F, 73F, 80F, 86F, 91F, 95F, 98F, 100F

いずれも投擲回数は最大14回となります。

編集者:すずき(2023/02/14 11:31)

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



2023年2月13日

CoreMarkのコンパイルオプションをチューンする

目次: RISC-V

以前(2022年12月22日の日記参照)の日記でCoreMarkのスコアを測って表にしました。実はCoreMarkはOfastのみでは最速にはならず、コンパイルオプションをガチガチにチューンすると結構差が出ます。実際にNSITEXE NS31Aの測定結果でお見せしたいと思います。

どうしてNS31Aかというと、非常にシンプルなCPU&自分の会社で作っているので素性が明確であるためです。複雑なCPU、中身の分からないCPUになればなるほど、総当たりでオプションの組み合わせを試す不毛な作業になりがちです。今回はそういう組み合わせ問題を解きたいわけじゃないんで、簡単な奴で行きます。

まずはベースとなるOfastの結果です。実はO3でも結果は同じです。

CoreMark on NS31A(チューン前)
2K performance run parameters for coremark.
CoreMark Size    : 666
Total ticks      : 18912
Total time (secs): 18.912000
Iterations/Sec   : 58.164129
Iterations       : 1100
Compiler version : GCC12.2.0
Compiler flags   : -Ofast -gdwarf-4 -march=rv32im -mabi=ilp32 -mcmodel=medany
Memory location  : Please put data memory location here
                        (e.g. code in flash, data on heap etc)
seedcrc          : 0xe9f5
[0]crclist       : 0xe714
[0]crcmatrix     : 0x1fd7
[0]crcstate      : 0x8e3a
[0]crcfinal      : 0x33ff
Correct operation validated. See README.md for run and reporting rules.
CoreMark 1.0 : 58.164129 / GCC12.2.0 -Ofast -gdwarf-4 -march=rv32im -mabi=ilp32 -mcmodel=medany   / Heap

動作周波数は25MHzですので、58.164129 / 25 = 2.326 CM/MHz です。

コンパイルオプションを足そう

最適化の基本となる、ループアンローリング、インライン化(-funroll-all-loops, -finline-functions)を足します。

キャッシュラインが32バイトなので、関数の先頭を32バイト境界に配置します(-falign-functions=32)。関数先頭で命令キャッシュミスヒットが発生したときに、同じキャッシュラインに後続の命令(1ラインに32 / 4 = 8命令)が載ります。後続の命令フェッチがキャッシュヒットすれば、最初のミスヒットを挽回できるだろうという目的です。

ジャンプやループの際に実行しない命令が中途半端にキャッシュに取り込まれないよう(= 利用効率の向上)、ジャンプやループの位置は8バイト境界に配置します(-falign-jumps=8 -falign-loops=8)。これも32バイト境界にすべきかと思いましたが、コード領域が散逸しすぎるためか逆に遅いです。

基本的に関数はインライン化した方がcall, retを省略、レジスタ共用など全体的に最適化できて速いです。しかしNS31Aは命令キャッシュが小さめ(FPGA向けコンフィグでは16KB)なので、無差別に関数をインライン化すると命令キャッシュがあふれてキャッシュミスヒットが発生してしまい、逆に遅くなります。

従ってあまりにも大きな関数はインライン化しないように設定します(-finline-limit=300)。デフォルト値600の1/2にしています(※)。

CoreMark on NS31A(チューン後)
2K performance run parameters for coremark.
CoreMark Size    : 666
Total ticks      : 15819
Total time (secs): 15.819000
Iterations/Sec   : 69.536633
Iterations       : 1100
Compiler version : GCC12.2.0
Compiler flags   : -Ofast -gdwarf-4 -march=rv32im -mabi=ilp32 -mcmodel=medany -funroll-all-loops -finline-functions -finline-limit=300 -falign-functions=32 -falign-jumps=8 -falign-loops=8
Memory location  : Please put data memory location here
                        (e.g. code in flash, data on heap etc)
seedcrc          : 0xe9f5
[0]crclist       : 0xe714
[0]crcmatrix     : 0x1fd7
[0]crcstate      : 0x8e3a
[0]crcfinal      : 0x33ff
Correct operation validated. See README.md for run and reporting rules.
CoreMark 1.0 : 69.536633 / GCC12.2.0 -Ofast -gdwarf-4 -march=rv32im -mabi=ilp32 -mcmodel=medany -funroll-all-loops -finline-functions -finline-limit=300 -falign-functions=32 -falign-jumps=8 -falign-loops=8  / Heap

動作周波数は25MHzですので、69.536633 / 25 = 2.781 CM/MHzです。ハードウェアは何も変えていませんが、性能1.2倍です。コンパイルオプションの威力恐るべし。

(※)この数値はGCC内部で使う仮想命令のライン数らしく、300が本当に適切か示すのは不可能です。マニュアルを見ると1/2や1/4に調整することが多いようなので、それに倣っています(参考: GCCのマニュアル)。

編集者:すずき(2023/02/13 19:52)

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



link もっと前
2023年2月9日 >>> 2023年2月22日
link もっと後

管理用メニュー

link 記事を新規作成

<2023>
<<<02>>>
---1234
567891011
12131415161718
19202122232425
262728----

最近のコメント5件

  • link 24年10月1日
    すずきさん (10/06 03:41)
    「xrdpで十分動作しているので、Wayl...」
  • link 24年10月1日
    hdkさん (10/03 19:05)
    「GNOMEをお使いでしたら今はWayla...」
  • link 24年10月1日
    すずきさん (10/03 10:12)
    「私は逆にVNCサーバーに繋ぐ使い方をした...」
  • link 24年10月1日
    hdkさん (10/03 08:30)
    「おー、面白いですね。xrdpはすでに立ち...」
  • link 14年6月13日
    2048player...さん (09/26 01:04)
    「最後に、この式を出すのに紙4枚(A4)も...」

最近の記事3件

  • link 24年10月28日
    すずき (10/30 23:49)
    「[Linuxからリモートデスクトップ] 目次: Linux開発用のLinuxマシンの画面を見るにはいろいろな手段がありますが、...」
  • link 23年4月10日
    すずき (10/30 23:46)
    「[Linux - まとめリンク] 目次: Linux関係の深いまとめリンク。目次: RISC-V目次: ROCK64/ROCK...」
  • link 24年10月24日
    すずき (10/25 02:35)
    「[ONKYOからM-AUDIOのUSB DACへ] 目次: PCかれこれ10年以上(2013年3月16日の日記参照)活躍してく...」
link もっとみる

こんてんつ

open/close wiki
open/close Linux JM
open/close Java API

過去の日記

open/close 2002年
open/close 2003年
open/close 2004年
open/close 2005年
open/close 2006年
open/close 2007年
open/close 2008年
open/close 2009年
open/close 2010年
open/close 2011年
open/close 2012年
open/close 2013年
open/close 2014年
open/close 2015年
open/close 2016年
open/close 2017年
open/close 2018年
open/close 2019年
open/close 2020年
open/close 2021年
open/close 2022年
open/close 2023年
open/close 2024年
open/close 過去日記について

その他の情報

open/close アクセス統計
open/close サーバ一覧
open/close サイトの情報

合計:  counter total
本日:  counter today

link About www2.katsuster.net
RDFファイル RSS 1.0

最終更新: 10/30 23:49