সমান্তরাল আর্কিটেকচার — Flynn-এর শ্রেণি, NUMA আর interconnect

১ · কেন সমান্তরালতা — power wall, Amdahl আর Gustafson

প্রায় ২০০৫ সাল পর্যন্ত প্রোগ্রাম দ্রুত চালানোর সহজ উপায় ছিল অপেক্ষা করা — পরের বছরের CPU-র clock বেশি, তাই একই প্রোগ্রাম আপনাআপনি দ্রুত। তারপর সেই রাস্তা বন্ধ হয়। পর্ব ০২-এ দেখেছেন, transistor ছোট হলেও voltage আর কমানো যাচ্ছিল না (Dennard scaling-এর অবসান)। CMOS-এর dynamic power মোটামুটি C·V²·f (পর্ব ০৮) — V না কমিয়ে f বাড়ালে chip গরম হয়ে যায়। এই দেয়ালের নাম power wall. শিল্পের উত্তর ছিল: একটি দ্রুত core-এর বদলে কয়েকটি মাঝারি core. কিন্তু তাতে প্রোগ্রাম আপনাআপনি দ্রুত হয় না — প্রোগ্রামকেই সমান্তরাল হতে হয়।

Amdahl-এর সূত্র আবার — strong scaling

পর্ব ০৩-এর Amdahl's law-কে এবার core-এর ভাষায় লিখি। একটি প্রোগ্রাম একটি core-এ চলতে T সময় নেয়। তার s অংশ serial (ভাগ করা যায় না), বাকি (১ − s) N টি core-এ নিখুঁতভাবে ভাগ হয়। তাহলে N core-এ সময় = T·(s + (১ − s)/N), আর

এখানে কাজের আকার স্থির — একই সমস্যা, বেশি core. এই মাপকে বলে strong scaling. প্রতি core কতটা কাজে লাগছে, তা বলে parallel efficiency E = S/N. s = ০.০৫ (মাত্র ৫% serial) আর N = ১৬ হলে S = ১ / (০.০৫ + ০.৯৫/১৬) = ১ / ০.১০৯৪ ≈ ৯.১, অর্থাৎ efficiency মাত্র ৫৭%.

Gustafson-এর সূত্র — weak scaling

১৯৮৮ সালে John Gustafson প্রশ্নটি উল্টে দেন: বাস্তবে বড় যন্ত্র পেলে মানুষ একই ছোট সমস্যা দ্রুত শেষ করে না, বড় সমস্যা চালায় — আবহাওয়ার মডেলে আরও সূক্ষ্ম grid, ছবিতে আরও pixel. তাই N core-এ চলা প্রোগ্রামের সময়কে ১ ধরে মাপুন: তার s অংশ serial, (১ − s) অংশ N টি core-এ সমান্তরাল। একই কাজ একটি core-এ করলে লাগত s + (১ − s)·N. অনুপাতই Gustafson's law:

নিচের calculator চারটি serial ভগ্নাংশ (১%, ৫%, ১০%, ২৫%) আর ১ থেকে ১০২৪ core-এর জন্য দুই সূত্রের speedup আর efficiency ছাপে। Run চাপুন:

// Amdahl (fixed problem, strong scaling) vs Gustafson (scaled problem, weak scaling)
const amdahl = (s, N) => 1 / (s + (1 - s) / N);
const gustafson = (s, N) => s + (1 - s) * N;
const S = [0.01, 0.05, 0.10, 0.25];
const NS = [1, 4, 16, 64, 256, 1024];
const pct = e => (e < 0.01 ? "<1" : String(Math.round(100 * e))) + "%";
const cell = (sp, N) => (sp.toFixed(1) + " (" + pct(sp / N) + ")").padStart(14);
function table(name, f) {
  console.log(name + "   speedup (efficiency)");
  console.log("N".padStart(5) + S.map(s => ("s=" + s.toFixed(2)).padStart(14)).join(""));
  for (const N of NS)
    console.log(String(N).padStart(5) + S.map(s => cell(f(s, N), N)).join(""));
  console.log("");
}
table("AMDAHL    (same problem, more cores)", amdahl);
table("GUSTAFSON (problem grows with cores)", gustafson);
// Amdahl efficiency S/N >= 50%  <=>  s(N - 1) <= 1  <=>  N <= 1 + 1/s
for (const s of S)
  console.log("s=" + s.toFixed(2) + ": ceiling 1/s = " + (1 / s).toFixed(0) +
              ", efficiency >= 50% only while N <= " + (1 + 1 / s).toFixed(0));

AMDAHL    (same problem, more cores)   speedup (efficiency)
    N        s=0.01        s=0.05        s=0.10        s=0.25
    1    1.0 (100%)    1.0 (100%)    1.0 (100%)    1.0 (100%)
    4     3.9 (97%)     3.5 (87%)     3.1 (77%)     2.3 (57%)
   16    13.9 (87%)     9.1 (57%)     6.4 (40%)     3.4 (21%)
   64    39.3 (61%)    15.4 (24%)     8.8 (14%)      3.8 (6%)
  256    72.1 (28%)     18.6 (7%)      9.7 (4%)      4.0 (2%)
 1024     91.2 (9%)     19.6 (2%)     9.9 (<1%)     4.0 (<1%)

GUSTAFSON (problem grows with cores)   speedup (efficiency)
    N        s=0.01        s=0.05        s=0.10        s=0.25
    1    1.0 (100%)    1.0 (100%)    1.0 (100%)    1.0 (100%)
    4     4.0 (99%)     3.8 (96%)     3.7 (93%)     3.3 (81%)
   16    15.8 (99%)    15.3 (95%)    14.5 (91%)    12.3 (77%)
   64    63.4 (99%)    60.8 (95%)    57.7 (90%)    48.3 (75%)
  256   253.4 (99%)   243.3 (95%)   230.5 (90%)   192.3 (75%)
 1024  1013.8 (99%)   972.8 (95%)   921.7 (90%)   768.3 (75%)

s=0.01: ceiling 1/s = 100, efficiency >= 50% only while N <= 101
s=0.05: ceiling 1/s = 20, efficiency >= 50% only while N <= 21
s=0.10: ceiling 1/s = 10, efficiency >= 50% only while N <= 11
s=0.25: ceiling 1/s = 4, efficiency >= 50% only while N <= 5

বাস্তবে দুটি সূত্রই আশাবাদী — দুটিই ধরে নেয় সমান্তরাল অংশ নিখুঁতভাবে ভাগ হয় আর core-দের মধ্যে কথা বলার কোনো খরচ নেই। অংশ ৮-এ দেখব, যোগাযোগ আর synchronisation-এর খরচ N-এর সাথে বাড়ে, তাই বাস্তব strong scaling-এর গ্রাফ এক সময় নিচে নামতেও শুরু করে।

২ · Flynn-এর চার শ্রেণি — পুরো ছবি, SPMD আর সীমাবদ্ধতা

পর্ব ৪২-এ Flynn's taxonomy-র সাথে পরিচয় হয়েছে — ১৯৬৬ সালে Michael Flynn-এর প্রস্তাব: একসাথে কয়টি instruction-এর ধারা আর কয়টি ডেটার ধারা চলে? এবার চারটি ঘরই পুরো দেখি:

SPMD — MIMD যন্ত্রে প্রোগ্রাম লেখার আসল ধাঁচ

MIMD মানে প্রতিটি core আলাদা প্রোগ্রাম চালাতে পারে। কিন্তু হাজার core-এর জন্য হাজারটি আলাদা প্রোগ্রাম কেউ লেখে না। বাস্তবে প্রায় সবাই লেখে একটিই প্রোগ্রাম, যা প্রতিটি core-এ চলে নিজের ডেটার টুকরায় — আর নিজের নম্বর (rank বা thread id) দেখে ঠিক করে কোন টুকরা তার। এই ধাঁচের নাম SPMD (Single Program, Multiple Data). পরীক্ষার ক্লাসরুমে সব পরীক্ষার্থী একই প্রশ্নপত্র পান, কিন্তু প্রত্যেকে নিজের খাতায় লেখেন, আর কেউ কেউ ঐচ্ছিক প্রশ্নে আলাদা পথে যান — SPMD ঠিক এমন: একই কোড, আলাদা ডেটা, branch-এ আলাদা পথ নেওয়ার স্বাধীনতা। SIMD-এর সাথে তফাত এখানেই — SIMD-এ সব lane একই মুহূর্তে একই instruction চালায়; SPMD-তে প্রতিটি core নিজের গতিতে নিজের PC নিয়ে চলে। MPI, OpenMP আর GPU-র CUDA kernel — তিনটিই মূলত SPMD.

Flynn-এর ভাগ কোথায় থেমে যায়

প্রায় ষাট বছর পরেও Flynn-এর ভাগ পরীক্ষায় আর আলোচনায় টিকে আছে কারণ এটি সরল। কিন্তু নকশাকারের কাছে এটি অনেক কিছু বলে না। একটি ৮-core ফোনের chip একসাথে MIMD (আটটি core), SIMD (প্রতিটি core-এ NEON) আর আংশিক SISD. GPU কোন ঘরে — SIMD না MIMD? সবচেয়ে বড় ফাঁক: মেমরি কীভাবে ভাগ হয় আর core-রা কীভাবে কথা বলে — Flynn-এর ভাগ এ নিয়ে নীরব, অথচ পারফরম্যান্স আর প্রোগ্রামিং-এর কষ্ট মূলত এর ওপরই নির্ভর করে। তাই আধুনিক বইয়ে MIMD-কে আরও ভাগ করা হয়: shared memory (UMA, NUMA) আর distributed memory (message passing) — পরের দুই অংশের বিষয়।

৩ · Shared memory বনাম message passing

Shared memory-তে সব core একই address space দেখে; একটি core-এর store অন্য core-এর load-এ দেখা যায়। Hardware-কে তখন দুটি জিনিস নিশ্চিত করতে হয় — cache coherence (একই ঠিকানার সব কপি মেলানো) আর memory consistency (কোন store কোন ক্রমে দেখা যাবে); দুটিই পর্ব ৫৩-এর বিষয়। প্রোগ্রামিং-এ thread — POSIX thread বা OpenMP. একটি chip বা একটি server-এর ভেতরে এটিই প্রধান মডেল।

Message passing-এ প্রতিটি node-এর নিজের মেমরি, অন্যটির মেমরি সরাসরি পড়া যায় না। ডেটা যায় স্পষ্ট send/receive দিয়ে, network-এর ওপর দিয়ে। Hardware সরল (coherence নেই), আর হাজার হাজার node পর্যন্ত বাড়ে — তাই cluster আর supercomputer-এ এর মানদণ্ড MPI. আজকের বড় যন্ত্রে দুটিই একসাথে চলে: node-এর ভেতরে thread, node-এর বাইরে MPI (“MPI + X”).

একই কাজ — একটি array-এর যোগফল — দুই মডেলে কেমন দেখায়, নিচের দুটি ছোট উদাহরণে দেখুন (এখানে চালানো যায় না; OpenMP-র জন্য gcc -fopenmp, MPI-র জন্য একটি MPI library আর mpirun লাগে):

double sum = 0.0;
#pragma omp parallel for reduction(+:sum)   /* threads share a[]; each keeps a private partial sum */
for (long i = 0; i < n; i++)
    sum += a[i];                            /* partial sums are combined at the end */

int rank, size;
MPI_Comm_rank(MPI_COMM_WORLD, &rank);       /* who am I?  (SPMD: same program everywhere) */
MPI_Comm_size(MPI_COMM_WORLD, &size);
double local = 0.0, total = 0.0;
for (long i = 0; i < n_local; i++)           /* my_part[] lives only in this node's memory */
    local += my_part[i];
MPI_Reduce(&local, &total, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD);  /* messages */

OpenMP-এ a[] সবার, MPI-তে প্রতিটি rank শুধু নিজের my_part[] জানে, আর MPI_Reduce network দিয়ে আংশিক যোগফলগুলো জড়ো করে। দুটিতেই একটি কৌশল একই — প্রতিটি কর্মী আগে নিজের ব্যক্তিগত আংশিক যোগফল রাখে, শেষে একবার মেলায়। এটি পর্ব ৪২-এর reduction tree-রই বড় রূপ।

নিজের হাতে — POSIX thread দিয়ে সমান্তরাল যোগফল

নিচের C প্রোগ্রাম একই হিসাব (১২ কোটি সংখ্যার একটি যোগফল) ১, ২ আর ৪টি POSIX thread-এ ভাগ করে চালায় আর সময়, speedup আর efficiency ছাপে। প্রতিটি thread-এর ফল আলাদা ৬৪-byte struct-এ, যাতে দুটি thread একই cache line-এ না লেখে (false sharing, পর্ব ৪৮)। প্রোগ্রামটি শুরুতে শুধু জানায় এই যন্ত্রে কয়টি logical CPU আছে:

#define _GNU_SOURCE
#include <stdio.h>
#include <pthread.h>
#include <time.h>
#include <unistd.h>
#define N 120000000UL                         /* total work, split among threads */
typedef struct { unsigned long lo, hi, sum; char pad[40]; } Job;   /* 64 B each: no false sharing */

static void *work(void *p) {
    Job *j = p; unsigned long s = 0;           /* private accumulator, written once */
    for (unsigned long i = j->lo; i < j->hi; i++) s += (i ^ (i >> 3)) & 0xFF;
    j->sum = s; return NULL;
}
static double now(void) {
    struct timespec t; clock_gettime(CLOCK_MONOTONIC, &t);
    return (double)t.tv_sec + (double)t.tv_nsec / 1e9;
}
int main(void) {
    printf("logical CPUs online here: %ld\n", sysconf(_SC_NPROCESSORS_ONLN));
    double t1 = 0;
    for (int T = 1; T <= 4; T *= 2) {
        pthread_t th[4]; Job job[4]; unsigned long total = 0;
        double t0 = now();
        for (int k = 0; k < T; k++) {
            job[k].lo = N / (unsigned long)T * (unsigned long)k;
            job[k].hi = (k == T - 1) ? N : N / (unsigned long)T * (unsigned long)(k + 1);
            pthread_create(&th[k], NULL, work, &job[k]);
        }
        for (int k = 0; k < T; k++) { pthread_join(th[k], NULL); total += job[k].sum; }
        double dt = now() - t0; if (T == 1) t1 = dt;
        printf("threads=%d  sum=%lu  time=%.2f s  speedup=%.2f  efficiency=%.0f%%\n",
               T, total, dt, t1 / dt, 100.0 * t1 / dt / T);
    }
    return 0;
}

logical CPUs online here: 2
threads=1  sum=15300000000  time=0.28 s  speedup=1.00  efficiency=100%
threads=2  sum=15300000000  time=0.21 s  speedup=1.30  efficiency=65%
threads=4  sum=15300000000  time=0.21 s  speedup=1.36  efficiency=34%

৪ · UMA, NUMA আর ccNUMA — মেমরি কত দূরে

প্রথম দিকের shared memory যন্ত্রে সব প্রসেসর একটি bus দিয়ে একটি মেমরির সাথে যুক্ত ছিল; যেকোনো প্রসেসর থেকে যেকোনো ঠিকানায় যেতে একই সময় লাগত। একে বলে UMA (Uniform Memory Access), বা symmetric multiprocessor (SMP). সমস্যা — সবাই একটি bus আর একটি memory controller ভাগ করে, তাই প্রসেসর বাড়লে লাইন লম্বা হয়।

সমাধান হলো মেমরিকে ভাগ করে প্রতিটি প্রসেসর-গুচ্ছের (একে বলে NUMA node, সাধারণত একটি socket) পাশে রাখা। প্রতিটি node-এর নিজের memory controller আর DRAM; সব node মিলে তবু একটিই address space, শুধু দূরের node-এর মেমরিতে যেতে interconnect পেরোতে হয়। এটি NUMA (Non-Uniform Memory Access). x86 server-এ এটি মূলধারায় আসে ২০০০-এর দশকে, যখন memory controller CPU chip-এর ভেতরে ঢোকে (AMD Opteron, পরে Intel Nehalem). আজ দুই-socket server তো বটেই, অনেক বড় একক chip-এর ভেতরেও কয়েকটি NUMA অঞ্চল থাকে।

কত ধীর? সংখ্যা প্রজন্ম আর সংযোগভেদে অনেক আলাদা, তাই মোটামুটি ধারণা হিসেবে নিন: একটি দুই-socket server-এ অন্য socket-এর DRAM-এ যাওয়া প্রায় দেড় থেকে দুই গুণ বেশি সময় নিতে পারে, আর পাওয়া bandwidth-ও কমে, কারণ socket-দের সংযোগটি মেমরি-বাসের চেয়ে সরু। Linux-এ numactl --hardware firmware-এর দেওয়া একটি “দূরত্বের টেবিল” দেখায়, যেখানে নিজের node-কে প্রথা অনুযায়ী 10 ধরা হয়:

available: 2 nodes (0-1)
node distances:
node   0   1
  0:  10  21
  1:  21  10

(উদাহরণ — একটি কাল্পনিক দুই-socket server-এর ছাঁচ; আপনার যন্ত্রের সংখ্যা আলাদা হবে।) 21 মানে মোটামুটি “নিজের চেয়ে দুই গুণের কাছাকাছি দূর” — এটি আপেক্ষিক ইঙ্গিত, nanosecond-এর মাপ নয়।

First-touch — page কোথায় বসবে

প্রোগ্রাম malloc করলে OS সাথে সাথে physical page দেয় না; প্রথম যেদিন কোনো thread সেই page-এ লেখে বা পড়ে (page fault), তখন দেয় (পর্ব ৫০)। Linux-এর ডিফল্ট নীতিতে page বসে যে CPU প্রথম ছুঁয়েছে, তার node-এ। এর নাম first-touch নীতি। ফাঁদটি সাধারণ: main thread একা পুরো array শূন্য দিয়ে ভরে (initialise), তারপর দুই socket-এর ১৬টি thread কাজ করে। সব page তখন main thread-এর node-এ — অন্য socket-এর আটটি thread-এর প্রতিটি load দূরের মেমরিতে যায়, আর একটি socket-এর memory controller-এ সবার ভিড়।

প্রতিকার: যে thread যে টুকরায় কাজ করবে, সেই thread-ই সেটি প্রথমে ছোঁবে (সমান্তরাল initialisation, একই ভাগে); thread-কে নির্দিষ্ট core-এ আটকে রাখা (pinning), যাতে OS তাকে অন্য socket-এ না সরায়; প্রয়োজনে numactl --interleave বা mbind দিয়ে page ছড়িয়ে দেওয়া। নতুন Linux kernel চলার সময় page-কে ব্যবহারকারী thread-এর কাছে সরাতেও পারে (automatic NUMA balancing), তবে তার নিজের খরচ আছে। OS-এর দিকের scheduling আর affinity নিয়ে বিস্তারিত আছে OS কোর্সের multiprocessor scheduling পর্বে।

আজকের প্রায় সব NUMA যন্ত্রে hardware cache coherence-ও রাখে — যেকোনো node-এর cache-এ রাখা যেকোনো ঠিকানার কপি মেলানো থাকে। একে বলে ccNUMA (cache-coherent NUMA). Coherence না থাকলে সফটওয়্যারকে নিজে cache flush করতে হতো, যা প্রায় অসম্ভব কঠিন। কিন্তু অনেক node-এ coherence কীভাবে টানা যায়? উত্তর — directory.

৫ · Directory-based coherence — গভীরে

পর্ব ৫৩-এ snooping protocol দেখেছেন: প্রতিটি miss সবাইকে broadcast করা হয়, আর সব cache “আড়ি পেতে” শোনে। চার-আট core-এ এটি সুন্দর কাজ করে। কিন্তু ৬৪ core-এ প্রতিটি miss-এ ৬৩টি cache-কে জিজ্ঞাসা করা মানে network আর cache-এর tag-এ বিপুল বাড়তি ট্রাফিক, যার বেশিরভাগ উত্তর “আমার কাছে নেই”। Directory-based coherence broadcast-এর বদলে একটি খাতা রাখে: প্রতিটি মেমরি block-এর জন্য — এটি এখন কোন কোন cache-এ আছে, আর কারো কাছে পরিবর্তিত (dirty) কপি আছে কি না।

প্রতিটি block-এর একটি home node থাকে — যে node-এর মেমরিতে ঠিকানাটি পড়ে, সাধারণত ঠিকানার কিছু bit দেখে ঠিক হয়। Block-এর directory entry থাকে সেই home-এ। সবচেয়ে সরল রূপ full bit-vector directory: প্রতিটি block-এর জন্য N core-এর জন্য N টি presence bit (কোন cache-এ কপি আছে) আর একটি-দুটি state bit.

খাতার দাম — storage overhead

Block-এর আকার B byte = ৮B bit, আর entry-তে N + ১ bit (N presence + ১ dirty) হলে overhead = (N + ১) / ৮B. ৬৪-byte line (৫১২ bit) ধরে:

অর্থাৎ overhead N-এর সাথে রৈখিকভাবে বাড়ে। একটি ৬৪-core যন্ত্রে ১৬ GiB মেমরি হলে block = ২^৩৪ / ২^৬ = ২^২৮টি, directory = ২^২৮ × ৬৫ bit ≈ ২.০৩ GiB — শুধু খাতার জন্য। তাই বাস্তব নকশা এর চেয়ে চালাক: limited pointer (কয়েকটি core-এর নম্বর রাখা, বেশি হলে broadcast), coarse vector (একটি bit একদল core-এর জন্য), আর sparse directory — সব মেমরির জন্য নয়, শুধু এখন কোনো cache-এ আছে এমন block-এর জন্য একটি cache-এর মতো টেবিল। আধুনিক multicore chip-এর shared L3-এর পাশে থাকা “snoop filter” মূলত এই শেষ ধারণা।

৩-hop read miss — dirty block পড়া

সবচেয়ে কঠিন ঘটনাটি ধাপে ধাপে দেখুন: P0 এমন একটি block X পড়তে চায়, যার home P2, আর যার পরিবর্তিত (Modified) কপি এখন P3-এর cache-এ। Presence bit লেখা হয়েছে P0 P1 P2 P3 ক্রমে:

লেখার ক্ষেত্রেও একই খাতা কাজে লাগে: P0 X-এ লিখতে চাইলে home presence vector দেখে শুধু যাদের কপি আছে তাদের invalidate বার্তা পাঠায় আর তাদের ack জড়ো করে। ১০২৪ core-এ ২টি কপি থাকলে বার্তা ২টি — broadcast-এ হতো ১০২৩টি। এটাই directory-র স্কেল করার রহস্য।

৬ · Interconnection network — bus থেকে fat tree

Core, cache, memory controller বা পুরো কম্পিউটার — যাদের জুড়তে হবে তাদের বলি node, আর জোড়ার নকশাকে interconnection network. মহল্লার গলির নকশার মতো: কোন বাড়ি থেকে কোন বাড়িতে কত মোড় পেরোতে হয়, আর একসাথে কতগুলো রিকশা চলতে পারে — এই দুই প্রশ্নই আসল।

চারটি মাপকাঠি

• Degree — একটি node থেকে কয়টি link বের হয়। বেশি মানে বেশি port, বেশি তার, বেশি খরচ।
• Diameter — সবচেয়ে দূরের দুটি node-এর মধ্যে ন্যূনতম hop-সংখ্যা; সবচেয়ে খারাপ latency-র ইঙ্গিত। গড় দূরত্ব (average hops) সাধারণ latency বলে।
• Link-সংখ্যা — মোট তার; খরচের মোটা মাপ।
• Bisection bandwidth — node-গুলোকে সমান দুই ভাগ করতে সবচেয়ে কম যতগুলো link কাটতে হয় (সবচেয়ে খারাপ ভাগে), প্রতিটি link-এর bandwidth দিয়ে গুণ। অর্ধেক node যখন বাকি অর্ধেকের সাথে কথা বলে (যেমন বড় matrix transpose বা FFT), তখন এটিই বাধা।

টপোলজিগুলো

• Bus — একটি ভাগাভাগি করা তার; এক সময়ে একজনই কথা বলতে পারে। Broadcast বিনামূল্যে (snooping-এর জন্য আদর্শ), কিন্তু bandwidth node বাড়লেও বাড়ে না।
• Crossbar — N × N switch-এর জাল; যেকোনো node যেকোনো মুক্ত node-এর সাথে একসাথে কথা বলতে পারে। সেরা পারফরম্যান্স, কিন্তু N²টি crosspoint — বড় N-এ খরচ অসম্ভব।
• Ring — প্রতিটি node দুই পাশের প্রতিবেশীর সাথে। সস্তা আর সহজ, কিন্তু diameter N/2.
• 2D mesh — √N × √N ছক, প্রতিটি node উত্তর-দক্ষিণ-পূর্ব-পশ্চিমে জোড়া; ছাপা chip-এর সমতলে সুন্দর বসে।
• 2D torus — mesh-এর কিনারা ঘুরিয়ে উল্টো কিনারায় জোড়া (প্রতিটি সারি আর কলাম একটি ring). Diameter প্রায় অর্ধেক, bisection দ্বিগুণ।
• Hypercube — N = ২ⁿ node, প্রতিটির n-bit নম্বর; ঠিক এক bit-এ আলাদা দুটি node জোড়া। Diameter আর degree দুটিই log₂N.
• Fat tree — node-গুলো একটি গাছের পাতায়, switch-গুলো ডালে; ওপরের দিকে link “মোটা” (বেশি link বা বেশি bandwidth), যাতে গোড়ার কাছে ভিড় না হয়। পূর্ণ রূপে bisection N/2, আর যেকোনো দুই node-এর মধ্যে ওপরে উঠে নেমে আসার একাধিক পথ। আজকের data center-এর নেটওয়ার্ক মূলত এর আত্মীয় (Clos network).

নিচের simulator প্রতিটি টপোলজিকে একটি graph হিসেবে বানায়, প্রতিটি node থেকে BFS চালিয়ে diameter আর গড় hop গোনে, link গোনে, আর bisection সূত্র থেকে বসায় (bus আর crossbar-এ যেকোনো দুই node এক “hop”-এ ধরা হয়েছে):

// Interconnect metrics: build each topology as a graph, BFS for hop distances
function build(kind, N) {
  const adj = Array.from({ length: N }, () => []), k = Math.round(Math.sqrt(N));
  const link = (a, b) => { if (a !== b && !adj[a].includes(b)) { adj[a].push(b); adj[b].push(a); } };
  for (let v = 0; v < N; v++) {
    const r = Math.floor(v / k), c = v % k;
    if (kind === "ring") link(v, (v + 1) % N);
    if (kind === "mesh") { if (c + 1 < k) link(v, v + 1); if (r + 1 < k) link(v, v + k); }
    if (kind === "torus") { link(v, r * k + (c + 1) % k); link(v, ((r + 1) % k) * k + c); }
    if (kind === "hypercube") for (let b = 1; b < N; b <<= 1) link(v, v ^ b);
  }
  return adj; }
function hops(adj) {                       // diameter and average over all ordered pairs
  let max = 0, sum = 0, N = adj.length;
  for (let s = 0; s < N; s++) {
    const d = new Array(N).fill(-1), q = [s]; d[s] = 0;
    while (q.length) { const u = q.shift(); for (const w of adj[u]) if (d[w] < 0) { d[w] = d[u] + 1; q.push(w); } }
    for (const x of d) { max = Math.max(max, x); sum += x; }
  }
  return [max, sum / (N * (N - 1))]; }
const bisect = { bus: N => 1, crossbar: N => N / 2, ring: N => 2,     // formulas, in links
  mesh: N => Math.sqrt(N), torus: N => 2 * Math.sqrt(N), hypercube: N => N / 2 };
const row = a => a.map((x, i) => String(x)[i ? "padStart" : "padEnd"]([11, 7, 10, 9, 9, 10][i])).join("");
for (const N of [16, 64]) {
  console.log("N = " + N); console.log(row(["topology", "degree", "links", "diameter", "avg-hops", "bisection"]));
  for (const kind of ["bus", "crossbar", "ring", "mesh", "torus", "hypercube"]) {
    let deg = 1, links = kind === "bus" ? "1 shared" : N * N + " xpts", dia = 1, avg = 1;  // bus, crossbar: 1 hop
    if (kind in { ring: 1, mesh: 1, torus: 1, hypercube: 1 }) {
      const adj = build(kind, N); [dia, avg] = hops(adj);
      deg = Math.max(...adj.map(a => a.length)); links = adj.reduce((t, a) => t + a.length, 0) / 2;
    }
    console.log(row([kind, deg, links, dia, avg.toFixed(2), bisect[kind](N)]));
  }
}

N = 16
topology    degree     links diameter avg-hops bisection
bus              1  1 shared        1     1.00         1
crossbar         1  256 xpts        1     1.00         8
ring             2        16        8     4.27         2
mesh             4        24        6     2.67         4
torus            4        32        4     2.13         8
hypercube        4        32        4     2.13         8
N = 64
topology    degree     links diameter avg-hops bisection
bus              1  1 shared        1     1.00         1
crossbar         1 4096 xpts        1     1.00        32
ring             2        64       32    16.25         2
mesh             4       112       14     5.33         8
torus            4       128        8     4.06        16
hypercube        6       192        6     3.05        32

Hypercube-এ routing — bit ঠিক করে করে

Hypercube-এর সৌন্দর্য হলো routing-এর জন্য কোনো টেবিল লাগে না। উৎস আর গন্তব্যের নম্বর XOR করলে যে bit-গুলো ১, ঠিক সেই মাত্রাগুলো পেরোতে হবে; hop-সংখ্যা = XOR-এর ১-এর সংখ্যা। প্রতিটি switch একটি নির্দিষ্ট ক্রমে (নিচের bit থেকে ওপরে) প্রথম অমিল bit-টি উল্টে পরের node-এ পাঠায় — একে বলে dimension-order বা e-cube routing:

৭ · Chip থেকে data center — on-chip network, cluster আর supercomputer

Chip-এর ভেতরের network

একই নীতি chip-এর ভেতরেও খাটে, শুধু মাপ millimeter-এ। কয়েকটি core-এ crossbar বা bus চলে; দশ-বিশটি core আর L3-এর টুকরা জুড়তে অনেক নকশা ring ব্যবহার করেছে (যেমন ২০১১-র দিকের Intel-এর desktop chip, প্রকাশিত বিবরণ অনুযায়ী); আরও বেশি core-এ 2D mesh (যেমন Intel-এর পরের প্রজন্মের server chip). এদের বলে network-on-chip (NoC): প্রতিটি tile-এ একটি ছোট router, packet-এর মতো বার্তা। AMD-র chiplet নকশায় আবার কয়েকটি আলাদা die একটি package-এর ভেতরে নিজস্ব সংযোগে জোড়া। ঠিক কোন chip-এ কোন টপোলজি, তা প্রজন্মভেদে বদলায় — নির্মাতার প্রকাশিত নথি দেখে নিশ্চিত হবেন।

Cluster আর warehouse-scale computer

একাধিক সাধারণ server-কে একটি দ্রুত network দিয়ে জুড়ে একটি যন্ত্রের মতো ব্যবহার করলে তা cluster. প্রতিটি server-এর ভেতরে shared memory, বাইরে message passing. এর চরম রূপ হলো warehouse-scale computer (WSC) — একটি বিশাল ভবনে হাজার হাজার server, যারা মিলে একটি সেবা চালায় (সার্চ, ভিডিও, ইমেইল, AI). এখানে নকশার মাপকাঠি বদলে যায়: প্রতি টাকায় আর প্রতি watt-এ কত কাজ, আর অংশ নষ্ট হলেও সেবা চালু রাখা — এত যন্ত্রে প্রতিদিনই কোনো না কোনো disk বা server বিকল হয়, তাই সফটওয়্যারকে ধরে নিতে হয় যে hardware ভাঙবে। এদের নেটওয়ার্ক সাধারণত fat tree বা Clos ধাঁচের, সস্তা সাধারণ switch দিয়ে (বিস্তারিত: Computer Networks কোর্সের data center network পর্ব)।

Supercomputer আর TOP500

Supercomputer মূলত বিশেষভাবে টিউন করা cluster: খুব দ্রুত আর কম latency-র interconnect (torus, dragonfly, fat tree), প্রায়ই প্রতি node-এ GPU, আর বৈজ্ঞানিক হিসাবের জন্য সাজানো সফটওয়্যার। ১৯৯৩ সাল থেকে বছরে দুবার TOP500 তালিকা প্রকাশিত হয়, যা যন্ত্রগুলোকে সাজায় একটি নির্দিষ্ট benchmark — LINPACK (HPL), একটি বড় dense linear equation system সমাধান — এ পাওয়া FLOP/s দিয়ে। ২০২২ সালে প্রথমবার একটি যন্ত্র এই তালিকায় HPL-এ ১ exaFLOP/s (১০^১৮) ছাড়ায় বলে ঘোষণা করা হয়। তালিকা প্রতি ছয় মাসে বদলায়, তাই এখন কে শীর্ষে তা তালিকার ওয়েবসাইটে দেখে নিন। মনে রাখবেন HPL প্রায় পুরোটাই dense matrix গুণ — অংশ ৮-এর ভাষায় খুব উঁচু operational intensity — তাই বাস্তবের অনেক প্রোগ্রাম একই যন্ত্রে peak-এর অনেক কম পায়।

শক্তির চোখে

বড় যন্ত্রে বিদ্যুৎই প্রথম সীমা: একটি বড় supercomputer বা data center কয়েক থেকে কয়েক দশ megawatt পর্যন্ত টানতে পারে, যা একটি ছোট শহরের চাহিদার কাছাকাছি। তাই TOP500-এর পাশে Green500 তালিকা যন্ত্রগুলোকে সাজায় প্রতি watt-এ FLOP/s দিয়ে, আর data center মাপা হয় PUE দিয়ে — মোট বিদ্যুৎ ÷ শুধু কম্পিউটারের বিদ্যুৎ (বাকিটা ঠান্ডা রাখা আর বিদ্যুৎ রূপান্তরে)। Chip-এর ভেতরেও একই সত্য: একটি সংখ্যা DRAM থেকে আনতে যে energy লাগে, তা একটি floating point গুণের চেয়ে বহু গুণ বেশি — বিভিন্ন প্রকাশিত হিসাবে শতগুণের কাছাকাছি বা তারও বেশি। সমান্তরাল নকশায় তাই হিসাব সস্তা, ডেটা সরানো দামি; বিস্তারিত পর্ব ৫৬-এ।

৮ · Hardware-এর চোখে সমান্তরালতার বাধা — আর roofline model

Amdahl-এর সূত্রের বাইরেও তিনটি বাধা বাস্তব speedup খেয়ে ফেলে:

• Load imbalance — কাজ সমান ভাগ হয়নি। ১৬টি thread-এর ১৫টি ১ সেকেন্ডে শেষ, একটি ২ সেকেন্ডে — সবাইকে ২ সেকেন্ড অপেক্ষা করতে হয়, efficiency প্রায় অর্ধেক। প্রতিকার: ছোট টুকরায় ভাগ করে যে আগে শেষ করে সে নতুন টুকরা নেয় (dynamic scheduling, work stealing).
• যোগাযোগ (communication) — ডেটা এক core থেকে আরেক core-এ বা node-এ নেওয়া। Shared memory-তে এটি লুকানো থাকে coherence miss আর দূরের NUMA মেমরির মধ্যে; message passing-এ প্রতিটি বার্তার একটি স্থির খরচ (latency) আর আকার ÷ bandwidth. টুকরা ছোট করলে load balance ভালো হয়, কিন্তু যোগাযোগের অনুপাত বাড়ে — এই টানাপোড়েন সমান্তরাল নকশার কেন্দ্রে।
• Synchronisation-এর দাম — barrier-এ সবার অপেক্ষা, lock-এর জন্য লাইন, atomic instruction-এ একটি cache line-এর core থেকে core-এ লাফালাফি। একটি জনপ্রিয় counter-এ ৬৪টি core একসাথে atomic_add করলে প্রতিবার line-টিকে নতুন মালিকের কাছে যেতে হয় — কাজটি কার্যত serial হয়ে যায় (software-এর দিক: OS কোর্সের atomics আর spinlock পর্ব)।

Roofline model — একটি ছবিতে সীমা

একটি kernel (প্রোগ্রামের ভারী লুপ) দ্রুত চলবে কি না, তা দুটি ছাদের নিচের একটি ঠিক করে: যন্ত্রের সর্বোচ্চ হিসাবের গতি (peak FLOP/s), আর মেমরি থেকে ডেটা আনার গতি (bandwidth, GB/s). এদের যোগসূত্র হলো kernel-এর operational intensity (I) = মোট floating point কাজ ÷ DRAM-এর সাথে আনা-নেওয়া byte. ২০০৯ সালে Samuel Williams, Andrew Waterman আর David Patterson এটিকে একটি সরল ছবিতে আনেন — roofline model:

দুই ছাদ যেখানে মেলে — I = Peak ÷ Bandwidth — তাকে বলে ridge point. এর বাঁয়ে kernel memory-bound (core অলস বসে ডেটার অপেক্ষায়), ডানে compute-bound. একটি kernel কোথায় বসে, ধাপে ধাপে দেখুন। যন্ত্রের সংখ্যাগুলো বোঝার জন্য ধরা অনুমান, কোনো নির্দিষ্ট chip-এর নয়:

এবার কয়েকটি পরিচিত kernel একসাথে। ঘন matrix গুণে (n × n) কাজ ২n³ FLOP, কিন্তু আদর্শভাবে প্রতিটি matrix একবারই আনা-নেওয়া হয় (১২n² byte), তাই I = n/৬ — n বড় হলে বিশাল। কিন্তু সাধারণ তিন-লুপের রূপে ভেতরের লুপ প্রতি ২ FLOP-এ দুটি নতুন সংখ্যা আনে (I = ০.২৫); b × b tile-এ ভাগ করলে (পর্ব ৪৮-এর blocking) দুটি tile আনায় (৮b² byte) ২b³ FLOP হয়, I = b/৪:

// Roofline: attainable GFLOP/s = min(peak, bandwidth x operational intensity)
const PEAK = 1000, BW = 100;          // ASSUMED machine: 1000 GFLOP/s (fp32), 100 GB/s DRAM
const ridge = PEAK / BW;
console.log("assumed peak " + PEAK + " GFLOP/s, bandwidth " + BW + " GB/s, ridge point = " + ridge + " FLOP/byte\n");
// operational intensity = FLOPs / bytes moved to and from DRAM (fp32 = 4 bytes)
const kernels = [
  ["saxpy y=a*x+y", 2, 3 * 4],               // 1 mul + 1 add; read x, read y, write y
  ["dot product", 2, 2 * 4],                 // 1 mul + 1 add; read x, read y
  ["5-point stencil", 5, 2 * 4],             // 4 adds + 1 mul; read in once (cache reuse), write out
  ["matmul naive", 2, 2 * 4],                // inner loop: a[i][k]*b[k][j], both from DRAM
  ["matmul tile b=32", 2 * 32 ** 3, 2 * 32 * 32 * 4],   // two 32x32 tiles in, 2*b^3 FLOPs
  ["matmul n=1024 ideal", 2 * 1024 ** 3, 3 * 1024 * 1024 * 4], // each matrix moved once
];
console.log("kernel".padEnd(21) + "FLOP/byte".padStart(10) + "attainable".padStart(12) + "  % of peak  bound");
for (const [name, flops, bytes] of kernels) {
  const oi = flops / bytes, att = Math.min(PEAK, BW * oi);
  console.log(name.padEnd(21) + oi.toFixed(3).padStart(10) + att.toFixed(1).padStart(12) +
    (100 * att / PEAK).toFixed(1).padStart(10) + "%  " + (oi < ridge ? "memory" : "compute"));
}
// what if we double the cores (peak) or the bandwidth?
const att = (oi, p, b) => Math.min(p, b * oi);
console.log("\nstencil (0.625): 2x peak -> " + att(0.625, 2 * PEAK, BW) + ", 2x bandwidth -> " + att(0.625, PEAK, 2 * BW));
console.log("tile b=32 (8.0): 2x peak -> " + att(8, 2 * PEAK, BW) + ", 2x bandwidth -> " + att(8, PEAK, 2 * BW));

assumed peak 1000 GFLOP/s, bandwidth 100 GB/s, ridge point = 10 FLOP/byte

kernel                FLOP/byte  attainable  % of peak  bound
saxpy y=a*x+y             0.167        16.7       1.7%  memory
dot product               0.250        25.0       2.5%  memory
5-point stencil           0.625        62.5       6.3%  memory
matmul naive              0.250        25.0       2.5%  memory
matmul tile b=32          8.000       800.0      80.0%  memory
matmul n=1024 ideal     170.667      1000.0     100.0%  compute

stencil (0.625): 2x peak -> 62.5, 2x bandwidth -> 125
tile b=32 (8.0): 2x peak -> 800, 2x bandwidth -> 1000

৯ · Heterogeneous system — big.LITTLE, P-core আর E-core, accelerator

এতক্ষণ ধরে নিয়েছি সব core একই রকম। আজকের ফোন আর ল্যাপটপের chip তা নয়। ২০১১ সালে ARM ঘোষণা করে big.LITTLE: একই chip-এ কয়েকটি বড়, দ্রুত, বেশি power-খাওয়া core আর কয়েকটি ছোট, ধীর, সাশ্রয়ী core — একই ISA-তে, তাই একই প্রোগ্রাম যেকোনোটিতে চলে। WhatsApp-এ বার্তা আসার খবর ছোট core-এ, গেম বা ভিডিও এডিট বড় core-এ। পরে Apple-এর ল্যাপটপ chip আর ২০২১ সালে Intel-এর desktop chip-ও একই ধারণা আনে — Intel এদের বলে P-core (performance) আর E-core (efficiency); chip OS-কে কোন thread কোথায় ভালো চলবে সে বিষয়ে ইঙ্গিত দেয়, যদিও শেষ সিদ্ধান্ত OS scheduler-এর।

যুক্তিটি power wall থেকেই আসে। একটি বড় out-of-order core-এর পারফরম্যান্স আকারের সাথে মোটামুটি বর্গমূলের মতো ধীরে বাড়ে, কিন্তু power প্রায় আকারের সমানুপাতে — তাই হালকা কাজে ছোট core প্রতি joule-এ অনেক বেশি কাজ দেয়। এর পরের ধাপ হলো সম্পূর্ণ আলাদা ধরনের core — GPU, AI-এর NPU, ভিডিও আর ছবির encoder — যা নির্দিষ্ট কাজে CPU-র চেয়ে বহু গুণ দক্ষ। এমন মিশ্র chip-কে বলে heterogeneous system; accelerator নিয়ে পুরো আলোচনা পর্ব ৫৫-এ। প্রোগ্রামারের জন্য এর অর্থ: “কয়টি core আছে” প্রশ্নের উত্তর আর একটি সংখ্যা নয় — কোন ধরনের core, কোন কাজের জন্য।

১০ · AI-এর যুগে — সমান্তরালতার হিসাব AI দিয়ে, যাচাই নিজে

“এই কোড ৬৪ core-এ কত দ্রুত হবে?” বা “এই server-এর NUMA latency কত?” — এমন প্রশ্নে AI আত্মবিশ্বাসী সংখ্যা দেয়। এই বিষয়ে তার সাধারণ ভুলগুলো:

• Amdahl আর Gustafson-এর s গুলিয়ে ফেলা, বা strong scaling-এর প্রশ্নে Gustafson বসিয়ে অবাস্তব রৈখিক speedup দেখানো।
• Topology-র সূত্রে ভুল — mesh আর torus-এর diameter বা bisection অদলবদল, hypercube-এর link-সংখ্যায় ২ দিয়ে ভাগ ভুলে যাওয়া (N·log₂N বনাম (N/2)·log₂N).
• Directory overhead-এ bit আর byte গুলিয়ে ফেলা (৬৪ bit ÷ ৬৪ byte-কে ১০০% বলা), আর state bit বাদ দেওয়া।
• Roofline-এ byte গোনায় ভুল — write-এর byte বাদ, বা cache reuse ধরে নেওয়া/না-নেওয়া স্পষ্ট না করা; peak আর bandwidth-এর একক মেলানো (GB/s বনাম GiB/s, fp32 বনাম fp64) ভুলে যাওয়া।
• নির্দিষ্ট chip-এর core-সংখ্যা, NUMA latency, interconnect-এর টপোলজি বা TOP500-এর বর্তমান ক্রম বানিয়ে বলা — এগুলো বদলায়, আর AI-এর জ্ঞান পুরোনো হতে পারে।

AI-এর দেওয়া সমান্তরাল-হিসাব যাচাইয়ের চেকলিস্ট

• Speedup-এর সূত্র প্রশ্নের ধরন (স্থির কাজ না বাড়ন্ত কাজ) দেখে নিজে বেছেছি, আর s কোন run-এ মাপা তা মিলিয়েছি
• Topology-র diameter আর bisection ছোট N-এ (যেমন ১৬) কাগজে ছবি এঁকে বা BFS script চালিয়ে যাচাই করেছি
• Directory overhead-এ bit আর byte আলাদা রেখেছি, state bit ধরেছি কি না স্পষ্ট করেছি
• Roofline-এ FLOP আর byte নিজে গুনেছি, read-write দুটোই, আর cache reuse-এর অনুমান লিখে রেখেছি
• Chip-এর বা যন্ত্রের সংখ্যা নির্মাতার নথি, lscpu/numactl --hardware বা নিজের মাপজোখে মিলিয়েছি — AI-এর কথায় নয়