Roofline Model — Compute না Memory Bandwidth, কোনটা আপনাকে থামাচ্ছে

Arithmetic Intensity — একটা সংখ্যা যা সব বলে দেয়

Roofline model-এর কেন্দ্রে একটাই সংখ্যা: arithmetic intensity (AI) — প্রতি byte data move করতে কতগুলো floating-point operation করা হচ্ছে।

$AI = \frac{\text{মোট FLOPs}}{\text{DRAM থেকে move করা মোট byte}}$

একক: FLOPs/byte।

গুরুত্বপূর্ণ শব্দ — “DRAM থেকে move করা”। L1 cache-এ বসে থাকা data বারবার পড়লে সেটা কোনো নতুন byte “move” করে না — DRAM bandwidth একবারই খরচ হয়েছিল, বাকিটা বিনামূল্যে। এইজন্যই cache hierarchy লেসনের পুরো বিষয়বস্তু এখানে ফিরে আসে: data যতবার পারা যায় cache-এ রেখে পুনর্ব্যবহার করাই এই সংখ্যাটা বাড়ানোর একমাত্র উপায়।

দুইটা সিলিং

একটা processor-এর দুইটা হার্ড সীমা আছে:

১. Peak compute — সর্বোচ্চ কতগুলো FLOP প্রতি সেকেন্ডে করা সম্ভব (GFLOPS)। এটা ALU সংখ্যা, SIMD width, FMA unit, আর clock speed দিয়ে নির্ধারিত — একটা ধ্রুবক, AI-এর উপর নির্ভর করে না।

$\text{Attainable GFLOPS} \le \text{Peak GFLOPS}$

২. Peak memory bandwidth — সর্বোচ্চ কত byte/second DRAM থেকে আনা সম্ভব (GB/s)। ALU যতই দ্রুত হোক, data না পৌঁছালে সেটা বসে থাকবে।

$\text{Attainable GFLOPS} \le AI \times \text{Peak Bandwidth}$

দ্বিতীয় সমীকরণটা লক্ষ্য করুন — এখানেই AI ঢোকে। বেশি AI মানে প্রতি byte-এ বেশি কাজ, তাই একই bandwidth দিয়ে বেশি GFLOPS।

দুইটা একসাথে:

$\text{Attainable GFLOPS} = \min\big(\text{Peak GFLOPS},\ AI \times \text{Peak BW}\big)$

এটাই সম্পূর্ণ roofline equation। বাকি সব এই একটা সমীকরণের ব্যাখ্যা।

ছবিতে — কেন এর নাম “roofline”

Log-log axis-এ (দুই অক্ষই log scale): x-axis = AI, y-axis = attainable GFLOPS।

• Peak compute — একটা অনুভূমিক রেখা (AI-এর উপর নির্ভর করে না)
• AI × Peak BW — একটা কোণাকার রেখা, slope 1 (log-log-এ, কারণ log(GFLOPS) = log(AI) + log(BW))

দুইটা রেখা একটা বিন্দুতে মেলে — ridge point। তার বামে কোণাকার রেখা নিচে, তাই সেটাই সীমা (memory-bound)। তার ডানে অনুভূমিক রেখা নিচে, তাই সেটাই সীমা (compute-bound)।

GFLOPS (log scale)
  │
  │                    compute roof ─────────────────────
  │                   ╱
  │                  ╱  ← ridge point
  │                 ╱
  │                ╱    (compute-bound অঞ্চল, ডানে)
  │               ╱
  │              ╱
  │     memory  ╱
  │      roof  ╱
  │    (slope=1)
  │   ╱
  │  ╱   (memory-bound অঞ্চল, বামে)
  │ ╱
  └──────────────────────────────────────────────► AI (log scale)
       কম AI                              বেশি AI
    (byte-ভারী কাজ)                    (compute-ভারী কাজ)

Ridge point-এর AI মান বের করা সহজ — দুইটা রেখা যেখানে সমান:

$AI_{ridge} = \frac{\text{Peak GFLOPS}}{\text{Peak Bandwidth}}$

একটা সম্পূর্ণ সাংখ্যিক উদাহরণ

ধরা যাক আমাদের example machine — একটা আধুনিক ৮-core desktop CPU-র মতো কিছু:

• Peak compute (double precision): 400 GFLOPS (৮ core × ৩ GHz × ২টা FMA unit × ৪-wide SIMD × ২ FLOP/FMA ≈ ৪০০)
• Peak memory bandwidth: 50 GB/s (dual-channel DDR, বাস্তব সংখ্যা)

$AI_{ridge} = \frac{400}{50} = 8 \text{ FLOPs/byte}$

এখন তিনটা বাস্তব kernel-কে এই মাপকাঠিতে ফেলি।

১. SAXPY (y[i] = a*x[i] + y[i]), double precision

প্রতি element: ১ multiply + ১ add = ২ FLOP। Byte: x[i] পড়া (৮B)

• y[i] পড়া (৮B) + y[i] লেখা (৮B) = ২৪ byte।

$AI = \frac{2}{24} = 0.083 \text{ FLOPs/byte}$

0.083 \< 8 — গভীরভাবে memory-bound। Ceiling: 0.083 × 50 ≈ 4.2 GFLOPS — machine-এর ৪০০ GFLOPS ক্ষমতার ১%-ও ব্যবহার হচ্ছে না, আর AVX-512 দিয়ে ALU যতই দ্রুত করুন, এই সিলিং নড়বে না।

২. Naive (unblocked) dense matrix multiply, বড় n

অ্যালগরিদম নিজে Θ(n³) FLOP করে, আর তাত্ত্বিকভাবে মাত্র Θ(n²) data নিয়ে কাজ করে — তাই মনে হতে পারে AI n-এর সাথে বাড়বে।

কিন্তু loop order যদি cache-unfriendly হয় (naive i-j-k loop, কোনো blocking নেই), আর matrix পুরো cache-এ না আঁটে, তাহলে দ্বিতীয় matrix-এর প্রতিটা column বারবার DRAM থেকে reload হয় — কার্যত প্রতি সারির জন্য একবার করে। ফলাফল: effective byte movement Θ(n³)-এর কাছাকাছি চলে যায়, আর measured AI নেমে আসে ~0.5–1 FLOPs/byte-এ।

$AI \approx 0.75 \Rightarrow \text{Ceiling} = 0.75 \times 50 = 37.5 \text{ GFLOPS}$

এখনো 8-এর নিচে — memory-bound, যদিও অ্যালগরিদমটা “computationally heavy” মনে হয়।

৩. Tiled/blocked matrix multiply

Block size এমনভাবে বাছা যাতে A, B, C-এর একটা tile একসাথে L2 cache-এ আঁটে। এখন প্রতিটা loaded element cache-এ থাকা অবস্থায় বহুবার পুনর্ব্যবহার হয় — DRAM-এ ফিরতে হয় না।

Effective AI উঠে যায় ~20–40 FLOPs/byte-এ (block size-এর উপর নির্ভরশীল)।

$AI \approx 30 > 8 \Rightarrow \text{এখন compute-bound}$

Ceiling এখন min(400, 30×50=1500) = 400 GFLOPS — পুরো compute roof-এর নিচে, যা আগেরটার চেয়ে ১০ গুণেরও বেশি বেশি।

এই টেবিলের সবচেয়ে গুরুত্বপূর্ণ পংক্তি ২ আর ৩ — একই algorithm (matrix multiply), একই FLOP সংখ্যা, শুধু memory access পুনর্বিন্যাস করেই ridge point-এর ভুল পাশ থেকে সঠিক পাশে চলে গেছে। এটাই এই module-এর “Matrix Multiply Optimization” project-এর ঠিক কী ঘটছে — naive → tiled ধাপে GFLOPS লাফ দেয় মূলত AI বাড়ার কারণে, SIMD-এর কোনো ভূমিকা ছাড়াই। SIMD আর threading আসে পরের ধাপে, যখন আপনি ইতিমধ্যে compute-bound অঞ্চলে — তখনই ALU-কে দ্রুত করাটা অর্থবহ হয়, কারণ এখন ALU-ই বাধা।

একাধিক ছাদ — বাস্তবতা আরেকটু জটিল

সরল roofline-এ একটাই compute ছাদ আর একটাই memory ছাদ ধরা হয়েছে। বাস্তবে একাধিক আছে:

• Compute-এর ধাপ: scalar peak (SIMD ছাড়া) < SIMD peak (SIMD কিন্তু FMA ছাড়া) < SIMD+FMA peak। যদি আপনার code auto-vectorize না হয়, আপনি আসলে সবচেয়ে নিচের ছাদের নিচে আটকে আছেন — machine-এর “প্রকৃত” peak GFLOPS আপনার জন্য প্রাসঙ্গিকই না।
• Bandwidth-এর ধাপ: L1 bandwidth সবচেয়ে বেশি (~কয়েকশ GB/s প্রতি core), তারপর L2, L3, সবশেষে DRAM সবচেয়ে কম (~কয়েক দশ GB/s পুরো chip-এ ভাগ করে)। একটা “hierarchical roofline”-এ প্রতিটা cache level-এর জন্য আলাদা কোণাকার রেখা আঁকা হয় — cache hierarchy লেসনের ঠিক সেই সংখ্যাগুলো এখানে axis হয়ে ফিরে আসছে।

Empirical Roofline Toolkit (ERT)-এর মতো টুল এই সবগুলো ছাদ একসাথে মেপে একটা সম্পূর্ণ multi-roof ছবি বানায়।

Hierarchical roofline — “bound” আসলে কোন level-এর সাপেক্ষে

এতক্ষণ আমরা AI হিসাব করেছি শুধু DRAM bandwidth-এর সাপেক্ষে — কারণ সেটাই সবচেয়ে ধীর, সবচেয়ে সাধারণ bottleneck। কিন্তু বাস্তবে একটা kernel L3-এর সাপেক্ষে compute-bound হয়েও DRAM-এর সাপেক্ষে memory-bound থাকতে পারে — দুইটা ভিন্ন প্রশ্ন, দুইটা ভিন্ন উত্তর।

ধরা যাক আমাদের example machine-এর প্রতিটা level-এর bandwidth (illustrative, বড়-থেকে-ছোট cache-এ যত কাছে তত বেশি bandwidth):

একটা kernel-এর AI = 3 নিন। DRAM roofline (ridge 8)-এর সাপেক্ষে এটা memory-bound। কিন্তু L3 roofline (ridge 2.67)-এর সাপেক্ষে 3 > 2.67, তাই সেই কণিকায় এটা compute-bound — অর্থাৎ যদি data-টা L3-এই থেকে যায় (DRAM পর্যন্ত না গিয়ে), kernel-টা আসলে ALU দিয়েই সীমাবদ্ধ, bandwidth দিয়ে না।

এই পার্থক্যটাই ব্যাখ্যা করে ব্লকিং/টাইলিং-এর আসল কাজ — এটা AI-এর numerator (FLOP) বদলায় না, এটা kernel-কে একটা নিচু, দ্রুততর bandwidth ছাদের নিচে নিয়ে আসে (DRAM ছাদ থেকে L2/L3 ছাদে), যেখানে একই AI-তেই “bound” হওয়ার সিদ্ধান্তটা উল্টে যায়।

Single-core বনাম aggregate roofline — core যোগ করলে ridge point সরে যায়

Misconception অংশে আমরা দেখব কেন থ্রেড বাড়ালে memory-bound কাজে কোনো লাভ হয় না — এখানে সংখ্যা দিয়ে দেখি ঠিক কেন।

একটা single core-এর ridge point ছিল 400/50 = 8 (পুরো chip-এর peak ধরে)। কিন্তু যদি আমরা per-core হিসেবে হিসাব করি (৮ core-এর chip):

• Per-core peak compute: 400 / 8 = 50 GFLOPS
• Per-core bandwidth (bandwidth পুরো chip-এ ভাগ হয়, তাই একক core একা চালালে পুরো 50 GB/s-ই পেতে পারে, কিন্তু ৮টা core একসাথে চালালে গড়ে মাথাপিছু 50/8 ≈ 6.25 GB/s):

অর্থাৎ, সব core ব্যবহার করলে effective ridge point ৮ গুণ ডানে সরে যায় (1.0 থেকে 8.0)। একটা kernel যার AI = 2, একা একটা core-এ চললে compute-bound (2 > 1.0) মনে হতে পারে, কিন্তু সব core দিয়ে চালালে সেই একই kernel memory-bound হয়ে যায় (2 \< 8.0) — কারণ bandwidth-এর জন্য এখন সব core প্রতিযোগিতা করছে।

এই কারণেই memory-bound kernel-এ core সংখ্যা বাড়ানো throughput প্রায় বাড়ায়ই না — বাড়তি core শুধু একটা সংকীর্ণ bandwidth-এর জন্য বেশি প্রতিযোগী যোগ করে।