配列とは
はいれつ
同じ型の値を並べて記憶し、要素番号(添字)で個々の要素を指定するデータ構造。メモリ上で連続して置かれるので、要素番号から位置を計算して、どの要素も一定の時間で読み書きできる。要素番号が0から始まる言語と、1から始まる書き方がある。
「配列」は、15分野の75問の練習問題に出てきます(プログラミングの基礎(擬似言語のトレース), データ構造とアルゴリズム, GPUプログラミングなど)。
この用語の分野: プログラミングの基礎(擬似言語のトレース)
配列の練習問題に挑戦
ダイレクトマップ方式のキャッシュで、2つの配列の要素が同じキャッシュの位置に対応し、交互にアクセスするたびに互いを追い出し合っている。このミスの分類はどれか。
- A初期参照ミス
- B容量ミス
- C競合ミス
2次元配列の1行の大きさが4096バイト(2の累乗)のとき、列方向に要素をたどると、キャッシュの容量に余裕があってもミスが多くなることがある。その対策として効果があるものはどれか。
- A各行の末尾に詰め物を足し、行の大きさを2の累乗からずらす
- B配列の型を、同じ大きさの別の型に変える
- C配列全体を、大きな2の累乗のアドレス境界にそろえて置き直す
答えと解説を見る
正解：A. 各行の末尾に詰め物を足し、行の大きさを2の累乗からずらす
1行が4096バイトちょうどだと、列方向にたどる要素のアドレスはどれも4096の倍数ずつ離れ、インデックスのうち下位12ビットに含まれる部分が同じになって、ごく少数のセットに集中します(1ウェイが4 KB以下のL1キャッシュなら、すべて同じセットです)。同じセットに連想度より多い行が集まると、容量に余裕があっても追い出し合う競合ミスが起こります。各行に1ライン分程度の詰め物(パディング)を足せば、要素ごとに対応するセットがずれて分散します。2の累乗のアドレスにそろえても問題は変わらず、同じ大きさの型に変えても効果はありません。
解説の中の「配列」
1行目でiを2ビット左にずらして4×iを作り、2行目で配列の先頭番地に足してa[i]の番地を求め、3行目でその番地から4バイトを読んでいます。
a0にint型(4バイト)の配列aの先頭番地、a1に添字iが入っている。上のコードがa2に読み込むものとして正しいもの…C言語の2次元配列は行優先(row-major)で格納され、a[i][0]、a[i][1]…がメモリ上に隣り合います。
C言語の2次元配列a[i][j]を上のように内側のループをjにして走査すると、内側をiにするより速くなりやすい。その理…連想度を上げて同じセットに2つ以上置けるようにしたり、配列の先頭をずらして別のセットに対応させたりすると減らせます。
ダイレクトマップ方式のキャッシュで、2つの配列の要素が同じキャッシュの位置に対応し、交互にアクセスするたびに互いを追い…構造体の配列(AoS)では、x・y・z・massの16バイトが1組で並ぶので、xだけを読む処理でも64バイトのラインの4分の3は使わないデータになります。
上のようにx座標だけを合計する処理を、配列の構造体(各成分を別々の配列にする形)に書き換えると速くなりやすい理由はどれ…配列なら次のアドレスが計算で分かり、プリフェッチやミスの重ね合わせが働きます。
上の連結リストをたどる処理が、同じ数の要素をもつ配列を順に読むより大幅に遅くなりやすい理由はどれか。
「配列」が出てくる問題(75問)
- a0にint型(4バイト)の配列aの先頭番地、a1に添字iが入っている。上のコードがa2に読み込むものとして正しいものはどれか。
- C言語の2次元配列a[i][j]を上のように内側のループをjにして走査すると、内側をiにするより速くなりやすい。その理由はどれか。
- ダイレクトマップ方式のキャッシュで、2つの配列の要素が同じキャッシュの位置に対応し、交互にアクセスするたびに互いを追い出し合っている。このミスの分類はどれか。
- 上のループでintが4バイト、キャッシュラインが64バイト、配列はキャッシュに入っておらず先頭がラインの境界にそろっているとき、プリフェッチがなければ配列の読み込みのミス率はいくらか。
- 上のようにx座標だけを合計する処理を、配列の構造体(各成分を別々の配列にする形)に書き換えると速くなりやすい理由はどれか。
- 2次元配列の1行の大きさが4096バイト(2の累乗)のとき、列方向に要素をたどると、キャッシュの容量に余裕があってもミスが多くなることがある。その対策として効果があるものはどれか。
- 上の連結リストをたどる処理が、同じ数の要素をもつ配列を順に読むより大幅に遅くなりやすい理由はどれか。
- スレッドごとのカウンタを「long cnt[8];」のように並べた配列で偽共有が起きている。対策として最も適切なものはどれか。
- 配列の全要素の合計を複数のスレッドで求めるとき、性能のために適した方法はどれか。
- 要素数1000の配列を、1ブロック256スレッドで1スレッド1要素ずつ処理したい。起動するブロックの数として正しいものはどれか。
- 各スレッドの番号をiとして、上のように32要素おきに配列を読むと、a[i]を読む場合に比べて遅くなる。主な理由はどれか。
- 配列の要素を1回だけ足し算するような軽い処理のためにデータをGPUへ送ると、CPUで計算するより遅くなることがある。主な理由はどれか。
- GPUで2つの大きな配列の要素ごとの足し算(c[i] = a[i] + b[i])を行うとき、性能を主に決めるものはどれか。
- GPUで、条件に合う要素だけを配列から取り出して別の配列に詰めて書き出したい(各スレッドが出力する数は0か1)。各スレッドの書き込み先の番地を決めるのによく使われる並列の計算はどれか。
- 要素数 n の配列で、異なる2つの要素の組をすべて1回ずつ比べる処理(i 番目の要素を、それより後ろにあるすべての要素と比べることを、i を1つずつ進めて繰り返す二重ループ)の計算量はどれか。
プログラミングの基礎(擬似言語のトレース)の参考書を探す PR
Amazonの検索結果へのリンクです。Amazonのアソシエイトとして、半導体教室は適格販売により収入を得ています。