(1)#

1 巡目 ($d=1$) 終了時： 下位 1 桁目（1の位）に基づき buckets[n][y] に格納される。対象データは {12, 21, 1, 11, 2}。

• x=0: なし
• x=1: buckets[1][0]=21, buckets[1][1]=1, buckets[1][2]=11
• x=2: buckets[2][0]=12, buckets[2][1]=2

2 巡目 ($d=2$) 終了時： 1 巡目終了後の values は {21, 1, 11, 12, 2} となる。これを 2 桁目（10の位）に基づき格納する。

• x=0: buckets[0][0]=1, buckets[0][1]=2
• x=1: buckets[1][0]=11, buckets[1][1]=12
• x=2: buckets[2][0]=21

(2)#

• (2-1) 基数整列 (Radix Sort)

• (2-2) $O(k(n+r))$。各桁において $n$ 個のデータをバケツに入れ、その後 $r$ 個のバケツを走査してデータを回収する操作を、$k$ 回繰り返すため。 English: For each of the $k$ digits, the algorithm distributes the $n$ elements into their corresponding buckets and subsequently scans the $r$ buckets to collect the elements. This single pass takes $O(n+r)$ time, and the process is repeated $k$ times.

• (2-3) データの数値を基数に基づいた添字（インデックス）として利用し、バケツ（配列）の該当箇所に直接配置することで、値の大小比較を行わずに順序を決定している。 English: It determines the sorting order without performing direct value comparisons between elements. Instead, it utilizes the numerical values of the data at a specific radix as array indices to directly place the elements into their corresponding buckets

• (2-4)

  • 时间计算量：比较ソートの下限 $O(n \log n)$ に関わらず、桁数 $k$ が小さければ $O(n)$ に近い線形時間で動作する。 English: Unlike comparison-based sorting algorithms, which are bounded by a lower limit of $O(n \log n)$, Radix Sort can operate in near-linear time $O(n)$ provided that the number of digits $k$ is small or treated as a constant.
  • 空间计算量：バケツを保持するための大きなメモリ領域（このプログラムでは MAXR * MAXN）を必要とするため、比较ソートよりも効率が悪い。 English: It is less space-efficient than typical comparison-based sorts because it requires a substantially large auxiliary memory space to maintain the buckets (in this program, an array of size MAXR * MAXN).

(3)#

降顺にするためには、バケツからデータを取り出す際にインデックスの大きい方から走査する。

• (ア) b = r - 1; b >= 0; b--
• (イ) values[i++] = buckets[b][j]（変更なし）

【選択肢】#

(1-2) 一つの機械語命令 (以下, 命令と略す) の処理を $n$ 段のステージ (stage) に分け, 1 ステージを 1 クロックサイクル (clock cycle) で実行する同期型 CPU を考える. クロック周波数を $f$ [Hz] とする. 以下の (1-2-1)～(1-2-4) に答えよ.

• (1-2-1) $m$ 個の命令をパイプライン (pipeline) 処理を用いずに逐次的に実行する場合の実行時間 [s] を示せ.
• (1-2-2) $m$ 個の命令をパイプライン処理を用いて実行する場合の実行時間 [s] を示せ. 但し, パイプラインストール (pipeline stall) は無いものとする.
• (1-2-3) $m$ 個の命令をパイプライン処理を用いて実行する場合の単位時間あたりの命令実行数 [instructions/s] について, $m \to \infty$ における極限を示せ. 但し, パイプラインストールは無いものとする.
• (1-2-4) パイプライン処理を用いた CPU の性能 (単位時間あたりの命令実行数) を高める手法の一つとして, ステージ数 $n$ を増やす方法がある. この方法により CPU の性能を高めることが可能である理由を説明せよ.

(1-3) 一つの機械語命令 (以下, 命令と略す) の処理を, 命令フェッチ (IF: instruction fetch), デコード (D: decode), オペランドフェッチ (OF: operand fetch), 実行 (EX: execution), 結果の格納 (S: store) の 5 つのステージに分け, 1 ステージ 1 クロックサイクルのパイプライン処理を用いた同期型 CPU において, 以下の (1-3-1) および (1-3-2) に示す命令 1～3 を実行することを考える. 解答欄の命令 1 の例を参考に, 実行されるステージ名 “IF”, “D”, “OF”, “EX”, “S” を解答欄に記入せよ. パイプラインストールにより完了までに複数クロックサイクルが必要なステージは, 完了するクロックサイクルにステージ名を, それ以外のクロックサイクルに ”-” を記入すること. なお, 以下の点を仮定する.

• パイプラインストールの原因としては, 構造ハザード (structural hazard) およびデータハザード (data hazard) を考える.
• 構造ハザードはメモリアクセス (memory access) の競合 (conflict) のみ考える.
• プログラムとデータは同じメインメモリ上にある.
• ある命令でレジスタに書き込まれた値を以降の命令で参照する場合, 前者の命令の格納 (S) が完了した後, 後者の命令のオペランドフェッチ (OF) が可能となる.

(1-3-1)

• 命令 1 : MOV R1, (A) ; メインメモリアドレス A の内容をレジスタ R1 に転送
• 命令 2 : MOV R2, (B) ; メインメモリアドレス B の内容をレジスタ R2 に転送
• 命令 3 : ADD R1, R2 ; R1 + R2 の結果を R1 に代入

(1-3-2)

• 命令 1 : MOV R1, (A) ; メインメモリアドレス A の内容をレジスタ R1 に転送
• 命令 2 : INC R1 ; R1 + 1 の結果を R1 に代入
• 命令 3 : MOV (B), R1 ; レジスタ R1 の内容をメインメモリアドレス B に転送

(2) キャッシュメモリ (cache memory) 及びメインメモリ (main memory) で階層を形成しているメモリシステムを持つ計算機を考える. 以下の各小問に答えよ. 解答は全て解答用紙の太線内に書くこと.

• (2-1) キャッシュメモリに存在する命令あるいはデータを読み出す際のアクセス時間 (access time) が 2 [ns] であり, キャッシュメモリに存在しない命令あるいはデータをメインメモリから読み出す際の, キャッシュメモリ及びメインメモリへのアクセス時間の和が 50 [ns] であるとする. また, メインメモリの容量はプログラムに対して十分大きく, プログラムの命令及びデータは全てメインメモリに格納されているものとする. 以下の (2-1-1) 及び (2-1-2) に答えよ.
  • (2-1-1) プログラムを実行した結果, プログラムの命令あるいはデータを読み出す際の平均のキャッシュヒット率 (cache hit ratio, cache hit rate) が 80% であった. この時の, プログラムの命令あるいはデータを読み出す際の平均アクセス時間を求めよ. 導出根拠も示せ.
  • (2-1-2) キャッシュメモリを, 命令あるいはデータを読み出す際のアクセス時間が 2 [ns] のものから 4 [ns] のものに変更する. ただし, キャッシュメモリに存在しない命令あるいはデータをメインメモリから読み出す際の, キャッシュメモリ及びメインメモリへのアクセス時間の和は 50 [ns] のままであるとする. この時, (2-1-1) で得られた平均アクセス時間を維持するために必要となるキャッシュヒット率を求めよ. 導出根拠も示せ.
• (2-2) 一般に, プログラムを実行するためにアクセスされる命令及びデータには, 参照局所性 (locality of reference) がある. 次の 2 種類の参照局所性のそれぞれについて説明せよ.
  • (2-2-1) 空間的参照局所性 (spatial locality of reference)
  • (2-2-2) 時間的参照局所性 (temporal locality of reference)
• (2-3) キャッシュメモリとメインメモリで階層を形成することの利点をその理由と共に述べよ.

(1-1)#

• (a) (エ) アーキテクチャ (architecture)
• (b) (コ) ノイマン型 (von Neumann architecture)
• (c) (ウ) プログラムカウンタ (program counter)
• (d) (イ) オペコード (operation code, opcode)
• (e) (カ) オペランド (operand)

(1-2)#

• (1-2-1) $T = \frac{mn}{f}$ [s]

• (1-2-2) $T = \frac{n + m - 1}{f}$ [s]

• (1-2-3) $\lim_{m \to \infty} \frac{m}{(n+m-1)/f} = f$ [instructions/s]

• (1-2-4) 理由：ステージ数を増やすことで、1ステージあたりの論理回路が短くなり、各ステージの処理遅延が減少する。これにより、CPU をより高いクロック周波数 $f$ で動作させることが可能になり、结果として全体的な命令スループット（単位時間あたりの命令実行数）が向上するため。

  English: Increasing the number of pipeline stages ($n$) reduces the logic gate delay per stage. This reduction allows the CPU to operate at a higher clock frequency ($f$), which consequently increases the overall instruction throughput.

(1-3)#

パイプラインの動作ルール:

• 構造ハザード：プログラムとデータは同一のメインメモリにあるため、IF, OF, S が同一クロックサイクルで同時に発生するとメモリアクセス競合が起きる。
• データハザード：RAW (Read After Write)。ある命令の S ステージが完了した後のクロックサイクルでなければ、その値を参照する後続命令の OF ステージを開始できない。

(1-3-1)

(注：クロック2では命令3の IF が命令1の OF と競合してストール。続くクロック3でも命令3の IF が命令2の OF と競合してストールし、クロック4でようやく IF が実行可能となる。)

(1-3-2)

(注：前記「ある命令でレジスタに書き込まれた値を以降の命令で参照する場合, 前者の命令の格納 (S) が完了した後, 後者の命令のオペランドフェッチ (OF) が可能となる」という条件に注意してほしい。)

(2-1)#

• (2-1-1) 平均アクセス時間 = (ヒット率 $\times$ キャッシュアクセス時間) + (1 - ヒット率) $\times$ ミス時のアクセス時間の和
  • $T_{avg} = 0.8 \times 2 + 0.2 \times 50 = 1.6 + 10 = 11.6$ [ns]
• (2-1-2) 求めるキャッシュヒット率を $h$ とすると：
  • $11.6 = h \times 4 + (1 - h) \times 50$
  • $11.6 = 4h + 50 - 50h$
  • $46h = 38.4 \implies h = \frac{38.4}{46} = \frac{192}{230} \approx 0.835$
  • 答：約 83.5%

(2-2)#

• (2-2-1) 空間的参照局所性：あるメモリアドレスが参照されたとき、その近傍のメモリアドレスが近い将来に参照される可能性が高い性質。（例：配列要素の順次アクセスや、命令の逐次実行など）

  English: When a memory address is accessed, there is a high probability that nearby memory addresses will be accessed in the near future. Examples: sequential access of array elements, or the sequential execution of instructions.

• (2-2-2) 時間的参照局所性：あるメモリアドレスが参照されたとき、同じアドレスが近い将来に再び参照される可能性が高い性質。（例：ループ内の変数や命令など）

  English: When a memory address is accessed, there is a high probability that the same address will be accessed again in the near future. Examples: variables and instructions within a loop.

(2-3)#

• 利点：システムのメモリアクセスにおいて、キャッシュメモリの「高速性」とメインメモリの「大容量・低コスト性」の両立を図ることができる点。

  English: The advantage of forming a hierarchy between cache memory and main memory is the ability to achieve both the high speed of cache memory and the large capacity and low cost of main memory.

• 理由：プログラムの実行には(2-2)で説明した「参照の局所性」があるため、CPUからの要求の大部分（ヒット時）は小容量で高速なキャッシュメモリで処理できる。一部の要求（ミス時）のみ、大容量で低コストなメインメモリにアクセスすればよいため、システム全体の平均メモリアクセス時間を短縮しつつ、コストを抑えて大容量の記憶空間を提供できる。

  English:

  • Cache Memory: It leverages the principle of locality (temporal and spatial locality). Because the CPU frequently requests recently accessed or adjacent data, most memory accesses result in a cache hit. This significantly reduces the average memory access time compared to fetching data directly from the slower main memory.
  • Main Memory: It provides a significantly larger storage capacity at a lower cost per byte. This allows the overall computer system to achieve a cost-effective balance between the high-speed processing capabilities of the cache and the large capacity requirements of executing programs.

(1) 有限オートマトンに関する問題#

(2) 文脈自由言語の閉包性#

(1)#

最大転送レート：

$\text{Maximum Transfer Rate} = X \times \frac{1500}{1522 + Y} \quad \text{[bps]}$

導出： 最大の転送効率を得るには、ペイロードを最大値の $1500$ バイトにする必要がある。図1 より、プリアンブルから FCS までのフレーム全体の合計サイズは以下の通りとなる。 $8 \, (\text{Preamble}) + 6 \, (\text{Dest}) + 6 \, (\text{Src}) + 2 \, (\text{Type}) + 1500 \, (\text{Payload}) + Y \, (\text{FCS}) = 1522 + Y \quad \text{[Bytes]}$ したがって、物理的な伝送レート $X$ に対して、全ビット長に占める純粋なデータ（ペイロード）の割合を乗じることで、上位層に提供される実効的な最大転送レートが求まる。

English Translation for Derivation: To achieve the maximum transfer rate, the payload must be set to its maximum value of 1500 bytes. Based on Figure 1, the total frame length is $1522 + Y$ bytes. The effective transfer rate is the physical transmission rate $X$ multiplied by the efficiency ratio of the payload to the total frame size.

(2)#

(3)#

(1-1) 命題変数の真偽#

図1の盤面に基づく命題変数 $x_{ijk}$（$i$行$j$列のマスに整数$k$が入る）の真偽は以下の通りです。

• $x_{115}$: 偽 (False) （※図1において1行1列目の数字は7であるため）
• $x_{214}$: 真 (True) （※図1において2行1列目の数字は4であるため）
• $x_{841}$: 偽 (False) （※図1において8行4列目の数字は6であるため）

(1-2) 命題変数の総数#

$n^6$

解説：行が $n^2$ 通り、列が $n^2$ 通り、入る整数が $n^2$ 通りあり、これらは独立した組み合わせであるため、全体の変数総数は $n^2 \times n^2 \times n^2 = n^6$ となります。

(1-3) 存在制約論理式（$n=3$、1行1列目のマス）#

「1行1列目のマスには、1以上9以下の整数が少なくとも一つ入る」ことを表す論理式は以下の通りです。

$x_{111} \lor x_{112} \lor x_{113} \lor x_{114} \lor x_{115} \lor x_{116} \lor x_{117} \lor x_{118} \lor x_{119}$

(1-4) CNF式 $A(i,j)$ （一般化されたマスの存在制約）#

「$i$行$j$列目のマスには1以上$n^2$以下の整数が少なくとも一つ入る」ことを表す論理式は以下の通りです。

$A(i,j) = \bigvee_{k=1}^{n^2} x_{ijk}$

(1-5) 論理式 $A$ （全マスの存在制約）#

「どのマスについても1以上$n^2$以下の整数が少なくとも一つ入る」ことを表す論理式 $A$ は以下の通りです。

$A = \bigwedge_{i=1}^{n^2} \bigwedge_{j=1}^{n^2} A(i,j) = \bigwedge_{i=1}^{n^2} \bigwedge_{j=1}^{n^2} \left( \bigvee_{k=1}^{n^2} x_{ijk} \right)$

(1-6) 論理式 $B$ の空欄（行内の競合制約）#

「どの行についても各整数は高々1回しか現れない」ことを表すための空欄に入る論理式は以下の通りです。

$\neg x_{ijk} \lor \neg x_{ilk}$

(1-7) CNF式 $C$ （列内の競合制約）#

「どの列についても各整数が高々1回しか現れない」ことを表すCNF式 $C$ は以下の通りです。

$C = \bigwedge_{j=1}^{n^2} \bigwedge_{1 \le i_1 < i_2 \le n^2} \bigwedge_{k=1}^{n^2} (\neg x_{i_1jk} \lor \neg x_{i_2jk})$

(1-8-1) 論理式 $Assign$#

図2（$n=2$）で与えられた確定マスに基づく初期配置の論理式は以下の通りです。

$Assign = x_{111} \land x_{122} \land x_{212} \land x_{224} \land x_{433}$

(1-8-2) 導出原理（Resolution Principle）を用いた命題 P の証明#

【日本語解答】 空いたマス $c(2,4)$ に着目する。制約 $A$ より、このマスには 1 から 4 のいずれかが入るため、以下の和項が存在する。

$C_0: x_{241} \lor x_{242} \lor x_{243} \lor x_{244}$

また、$Assign$ および制約 $B$（行）, $C$（列）, $D$（ブロック）より、以下の和項が CNF 式に含まれる。

• $C_1: \neg x_{122} \lor \neg x_{242}$ （制約 D：ブロック1内に 2 は複数存在しない）
• $C_2: \neg x_{212} \lor \neg x_{242}$ （制約 B：2行目に 2 は複数存在しない）
• $C_3: \neg x_{224} \lor \neg x_{244}$ （制約 B：2行目に 4 は複数存在しない）

$Assign$ の各要素はすべて真であるため、単一リテラル（Unit Clause）として導出に用いる。

1. $x_{212}$ と $C_2$ から導出原理により $\neg x_{242}$ を得る。
2. 同様に、ブロック制約 D と $Assign$ の要素から $\neg x_{241}$ を得る。
3. 同様に、行制約 B と $x_{224}$ から $\neg x_{244}$ を得る。
4. 同様に、列制約 C（あるいはブロック制約 D）と $Assign$ の要素から $\neg x_{243}$ を得る。

これら 4 つの否定リテラル $\neg x_{241}, \neg x_{242}, \neg x_{243}, \neg x_{244}$ を $C_0$ に対して順次導出（Unit Resolution）すると、すべてのリテラルが消去され、最終的に 空節（$\emptyset$、矛盾） が導出される。 したがって、CNF式は充足不能（Unsatisfiable）であり、パズルを解くことはできない。

[English Translation] Focus on the empty cell $c(2,4)$. From constraint $A$, this cell must contain an integer from 1 to 4, yielding the following clause: $C_0: x_{241} \lor x_{242} \lor x_{243} \lor x_{244}$

Given $Assign$ and the conflict constraints $B$ (row), $C$ (column), and $D$ (block), the CNF formula includes clauses such as:

• $C_2: \neg x_{212} \lor \neg x_{242}$ (Constraint B: no duplicate ‘2’s in row 2)
• $C_3: \neg x_{224} \lor \neg x_{244}$ (Constraint B: no duplicate ‘4’s in row 2)

Since elements in $Assign$ are all true, they act as unit clauses.

1. Applying the resolution principle on $x_{212}$ and $C_2$ yields $\neg x_{242}$.
2. Similarly, applying resolution with block constraint D and an element of $Assign$ yields $\neg x_{241}$.
3. Applying resolution with $x_{224}$ and row constraint B yields $\neg x_{244}$.
4. Applying resolution with column/block constraints and $Assign$ yields $\neg x_{243}$.

By sequentially resolving these four negated literals against the initial clause $C_0$ (Unit Resolution), all literals are eliminated, ultimately deriving the empty clause ($\emptyset$, contradiction). Therefore, the CNF formula is unsatisfiable, proving that the puzzle cannot be solved.

(2-1) $R_3$ の算出#

【日本語解答】 $R_3$ は、与えられた有向グラフ $G$ において、任意の頂点 $u$ から有向辺を正確に「3歩（3エッジ）」辿って到達できる頂点 $v$ のペア $(u, v)$ の集合である。

$R_3 = \{ (u, v) \mid \text{グラフ } G \text{ 上で } u \text{ から } v \text{ への長さ3のパスが存在する} \}$

(2-2) $S_n = S_{n+1}$ となる非負整数 $n$ の存在証明#

【日本語解答】 背理法を用いて証明する。 頂点集合 $V$ は有限集合であるため、直積集合 $V \times V$ の要素数も有限である（$|V| = k$ とすると $|V \times V| = k^2$）。 定義 $S_{i+1} = S_i \cup R_{i+1}$ より、$S_0 \subseteq S_1 \subseteq S_2 \subseteq \dots \subseteq V \times V$ が成り立つ。