19 / 20 · 実習

総合課題：タイル化N×N検証モデル

任意のNとKにパディングと停止を組み合わせ、独立した参照モデルと比較します。

完全なモデルを組み立てる

総合課題はN×N格子で形状M×KのAとK×PのBを受け取ります。各空間タイルは空から始め、パディングオペランドは有効なゼロ、格納は座標でマスクします。1タイルに1ジョブだけが入り、全体停止は論理時間を保持します。出力量子化は広い和の後の別テストです。

capstone-lab.mjsとして保存し、node capstone-lab.mjsを実行します。パッケージは不要です。入力はJavaScript Numberの正確な範囲内の小さい整数例です。より大きい範囲にはBigIntと明示的な幅検査が必要です。RTLやDDS実行とは独立に、Nodeの算術・スケジュールモデルを検査します。

import assert from 'node:assert/strict';
function golden(A,B){return A.map(r=>B[0].map((_,j)=>
 r.reduce((s,a,k)=>s+a*B[k][j],0)));}
function solve(A,B,N,pauses=new Set()){
 const M=A.length,K=A[0].length,P=B[0].length;
 assert.ok(N>=1&&Number.isInteger(N)&&K>=1);assert.equal(B.length,K);
 assert.ok(A.every(r=>r.length===K)&&B.every(r=>r.length===P));
 const C=Array.from({length:M},()=>Array(P).fill(null));
 let advances=0,physical=0;
 for(let r0=0;r0<M;r0+=N)for(let c0=0;c0<P;c0+=N){
  const job=r0*P+c0;
  let g=Array.from({length:N},()=>Array.from({length:N},()=>
   ({a:null,b:null,acc:0,count:0})));
  const token=(value,k)=>({value,k,job});let t=0,p=0;
  while(t<K+2*N-2){
   if(pauses.has(p)){p++;continue;}
   const next=g.map(r=>r.map(pe=>({...pe})));
   for(let i=0;i<N;i++)for(let j=0;j<N;j++){
    const ka=t-i,kb=t-j;
    const a=j?g[i][j-1].a:(ka>=0&&ka<K?
     token(r0+i<M?A[r0+i][ka]:0,ka):null);
    const b=i?g[i-1][j].b:(kb>=0&&kb<K?
     token(c0+j<P?B[kb][c0+j]:0,kb):null);
    const pe=next[i][j];pe.a=a;pe.b=b;
    if(a&&b){assert.equal(a.job,b.job);assert.equal(a.k,b.k);
     assert.equal(a.k,pe.count);pe.acc+=a.value*b.value;pe.count++;}}
   g=next;t++;p++;
  }
  for(let i=0;i<N;i++)for(let j=0;j<N;j++){
   assert.equal(g[i][j].count,K);
   if(r0+i<M&&c0+j<P){assert.equal(C[r0+i][c0+j],null);
    C[r0+i][c0+j]=g[i][j].acc;}}
  advances+=t;physical+=p;
 }
 return {C,advances,physical};
}
const A=[[1,2,3],[4,5,6],[7,8,9]],B=[[1,0,2],[0,1,0],[2,0,1]];
for(const N of [1,2,3])assert.deepEqual(
 solve(A,B,N,new Set([1,2])).C,golden(A,B));
const run=solve(A,B,2,new Set([1,2]));
assert.deepEqual(run.C,[[7,2,5],[16,5,14],[25,8,23]]);
assert.equal(run.advances,20);assert.equal(run.physical,28);
assert.deepEqual(solve([[2,-1],[0,3]],[[4,5],[-2,1]],2).C,
 [[10,9],[-6,3]]);
assert.deepEqual(solve([[-128]],[[-128]],1).C,[[16384]]);
console.log('Capstone lab passed');

正解関数は行列算術だけを知っています。ソルバは独立にタグ付きトークンを移動し、項順序を検査して格納をマスクします。N=2では4タイルが20 advanceエッジです。各タイルの物理エッジ1と2で停止すると8停止が加わり、計28物理エッジになります。初期化、メモリロード、直列化出力転送は除外します。

ログ、1タイルの消費kトレース、符号付き幅分析、valid/ready結果ラッパ設計を提出します。RTLへ変換するときはエッジ契約を保持します。拡張前にN=1,K=1と2×2から始めます。量子化、部分和保持、二重バッファは1つずつ追加し、新しい明示的検査を付けます。

3つの格子サイズは異なる割り当てを試します。N=1はスキューなし内積の反復、N=2は4つのパディング付きタイル、N=3は完全な1タイルです。すべて同じ数学的行列を生成する必要があります。Cをnullで初期化すると有効なゼロと未引き渡し出力を区別し、重複格納を検出できます。ここではタイル由来のjob番号が一意ですが、実RTLにはタグ幅と再利用方針の定義が必要です。拡張としてM=2,K=3,P=1と手計算期待値を試してください。内部格子は正方形でも出力行列は長方形です。各タイルが全Kを消費し、範囲外格納を抑えることを確認します。

自分で考えてみましょう

3×3例でN=3、物理エッジ1と2に停止を入れた場合、advance数と物理エッジ数はいくつですか。直前のクリア1エッジを測定に含めるとどうなりますか。

解説を見る

advanceは7エッジ、2停止を含む計算区間の物理エッジは9です。直前のクリア1エッジを含めると10で、ロードと出力転送はなお除外します。

Lesson files

capstone-lab.mjs ↓