19 / 20 · 실습

캡스톤: 타일링된 N×N 검증 모델

임의 N, K와 패딩·pause를 결합하여 독립적인 행렬 참조와 비교합니다.

완성할 계약

캡스톤은 앞 단원의 출력 고정 배열을 일반화합니다. 행렬 A의 크기는 M×K, B는 K×P, 배열은 N×N이며 N과 K는 1 이상입니다. 공간 타일마다 초기화하고, 범위 밖 입력은 valid 0, 출력은 좌표 마스크로 처리합니다. 단일 작업만 배열에 들어가며 논리 단계는 전역 pause로 멈춥니다. 전체 K의 넓은 정수 합을 유지하고 출력 양자화는 이 프로그램 밖에서 따로 검사합니다.

아래를 capstone-lab.mjs로 저장하여 node capstone-lab.mjs를 실행합니다. 패키지 설치가 필요 없으며 Capstone lab passed를 출력해야 합니다. 입력 값은 이 과정의 작은 정수 fixture로 제한하여 JavaScript Number의 정확한 정수 범위 안에 둡니다. 더 큰 정수나 긴 K로 확장하면 BigInt 모델과 폭 범위 검사를 사용해야 합니다. 이 실습은 Node 수치·스케줄 실행이며 RTL 컴파일·합성·DDS 실행은 별도입니다.

import assert from 'node:assert/strict';
function golden(A,B){return A.map(row=>B[0].map((_,j)=>
 row.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(row=>row.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]){
 const run=solve(A,B,N,new Set([1,2]));
 assert.deepEqual(run.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');

동작을 설명하고 확장하기

첫 golden 함수는 이동이나 스큐를 전혀 모르고 행렬 식만 계산합니다. solve는 토큰을 옛 상태에서 읽어 한 칸씩 전달하고 매칭 job·k·count를 단언합니다. 좌표 검사 후에만 C에 써서 패딩 출력과 중복 쓰기를 막습니다. N=2의 3×3 예제는 네 타일×5 advance=20개를 사용하며 각 타일의 물리 에지 1·2를 멈춰 총 8 pause, 28 물리 에지입니다. 타일 초기화·로드·출력 버스 전송은 이 수치에서 제외됩니다.

제출물에는 프로그램의 성공 로그, 한 타일의 에지별 소비 k목록, signed 폭 계산과 valid/ready 출력 래퍼 설계를 포함합니다. 모델의 숫자를 RTL에 연결할 때는 AW=2W+ceil(log2 K), 등록 전달과 clear 우선순위를 유지합니다. 먼저 N=1,K=1과 2×2를 재현한 후 배열 크기를 늘리세요. 다음 확장으로 결과 양자화, K축 타일 부분합 보존, 출력 이중 버퍼를 하나씩 추가하고 각 변경이 만드는 새로운 계약을 검증합니다.

세 배열 크기를 시험하는 반복문은 단순히 큰 N이 동작하는지만 확인하지 않습니다. N=1은 스큐 없는 내적을 여러 출력 좌표에 반복하고, N=2는 경계 패딩과 네 타일을 사용하며, N=3은 패딩 없이 전체 결과를 한 타일에 계산합니다. 같은 golden 결과와 비교하므로 배치 방식이 수치를 바꾸지 않는지 검사합니다. 정답 비교 뒤에 물리 에지 수를 별도로 검사하여 숫자만 맞고 pause를 무시하는 모델을 구별합니다.

토큰의 job 값은 타일 좌표에서 만들어 이 예제에서 타일마다 고유합니다. job 태그의 실제 RTL 폭과 재사용 규칙은 별도 인터페이스 계약으로 정해야 합니다. 이전 타일 상태를 남긴 채 새 타일을 시작하면 count 검사나 태그 검사에서 실패해야 합니다. C를 null로 시작하고 저장 전에 null을 검사하는 것은 유효 0과 미수신 출력을 구분하고 같은 좌표에 두 번 쓰는 것을 막습니다.

추가 과제에서는 M=2,K=3,P=1처럼 정사각형이 아닌 입력을 먼저 넣고, 직접 계산한 C 두 값을 고정하세요. 내부 배열은 여전히 N×N이지만 전역 출력 크기는 M×P입니다. N을 행렬 크기와 같은 값으로 강제하지 않는지, 패딩된 결과를 출력하지 않는지, 매 타일에서 전체 K를 소비하는지 확인하면 매개변수화의 의미가 분명해집니다.

직접 생각해 보기

위 3×3 예제에서 N=3으로 한 타일을 쓰고 physical edge 1·2를 pause하면 advance와 물리 에지 수는? 초기화 에지 1개를 포함해 새 작업의 clear부터 세면?

해설 보기

K=3,N=3이므로 advance=3+6−2=7개, pause 2개를 포함한 계산 물리 에지는 9개입니다. 앞 clear 1개를 포함한 구간은 10개입니다. 로드와 출력 전송은 여전히 제외입니다.

실습 파일

capstone-lab.mjs ↓