Gate Simulator

কেন এই প্রজেক্ট

Gate Universality লেসনে দেখেছেন — শুধু NAND দিয়েই যেকোনো Boolean function বানানো যায়। কিন্তু “বানানো যায়” জানা আর সেই সার্কিটটা আসলে সঠিকভাবে কাজ করে কি না যাচাই করা — দুইটা আলাদা দক্ষতা। বড় একটা সার্কিট হাতে কলমে ট্রেস করা অসম্ভব হয়ে ওঠে — কয়েক ডজন গেট পেরোলেই মানুষের মাথায় আর ধরে না।

তাই আসল হার্ডওয়্যার ডিজাইনাররা কখনো হাতে ট্রেস করেন না — তারা সার্কিটের একটা টেক্সট বর্ণনা (netlist) লেখেন আর একটা সিমুলেটর দিয়ে চালান। এই প্রজেক্টে আপনি ঠিক সেই সিমুলেটরটার একটা ছোট, কিন্তু আসল সংস্করণ বানাবেন। আর এখানেই একটা সুন্দর সংযোগ ঘটে — একটা সার্কিট মানে আসলে একটা dependency graph (কোন গেটের আউটপুট কোন গেটের ইনপুটে যায়), আর সেই গ্রাফ evaluate করার সঠিক ক্রম বের করতে লাগে ঠিক Graph Playground প্রজেক্টে (Level 0) লেখা topological sort। Mathematics মডিউলের Graph Theory লেসনের বিমূর্ত অ্যালগরিদম এখানে এসে বাস্তব সিলিকনের প্রশ্নের উত্তর দেয়।

দ্বিতীয় ধাপে আমরা আরেকটু গভীরে যাব — একটা গেটের আউটপুট বদলাতে সময় লাগে (propagation delay), আর কিছু সার্কিটে (latch, flip-flop) আউটপুট আবার ফিরে গিয়ে নিজের ইনপুটে ঢোকে (feedback loop) — তখন টপোলজিক্যাল সর্ট আর কাজ করে না, কারণ গ্রাফটা তখন আর acyclic থাকে না। এই সমস্যার সমাধান হলো event-driven simulation — সময়ের সাথে সাথে কোন সিগন্যাল কখন বদলাচ্ছে সেটার একটা টাইমলাইন তৈরি করা। এটাই Icarus Verilog, Verilator-এর মতো আসল HDL সিমুলেটরের ভেতরের কাজের নীতি — এই প্রজেক্ট সেটার একটা সরলীকৃত, কিন্তু সঠিক সংস্করণ।

লক্ষ্য

এই রকম কিছু চালাতে পারা — প্রথমে একটা combinational সার্কিট (full adder):

$ python gatesim.py fulladder.net --truth-table

 a b cin | sum cout
 0 0 0   |  0    0
 0 0 1   |  1    0
 0 1 0   |  1    0
 0 1 1   |  0    1
 1 0 0   |  1    0
 1 0 1   |  0    1
 1 1 0   |  0    1
 1 1 1   |  1    1

সব ৮টা সারি হাতে-করা full-adder truth table-এর সাথে মিলেছে ✓

তারপর একটা feedback-loop সার্কিট (SR latch), event-driven মোডে:

$ python gatesim.py srlatch.net --initial q=0,qn=1 --events "0:s=1"

t=0   s  : 0 -> 1     (input event)
t=1   qn : 1 -> 0     (qn = NOR(s, q) — s বদলাল, তাই re-evaluate; NOR delay = 1ns)
t=2   q  : 0 -> 1     (q = NOR(r, qn) — qn বদলাল, তাই re-evaluate; আরেক ধাপ delay)

final state: q=1  qn=0   (SET সফল — ২টা gate-delay hop-এ propagate হয়ে স্থির হলো)

ধাপে ধাপে

১. নেটলিস্ট ফরম্যাট ডিজাইন করুন

একটা সাদামাটা টেক্সট ফরম্যাট — প্রতি লাইনে একটা primary input, একটা গেট, অথবা একটা output ঘোষণা:

INPUT a
INPUT b
INPUT cin

OR  cout = a1, a2
AND a2   = x1, cin
XOR sum  = x1, cin
AND a1   = a, b
XOR x1   = a, b

OUTPUT sum
OUTPUT cout

লক্ষ্য করুন — cout লাইনটা ফাইলের একদম উপরে, অথচ সেটা a1 আর a2-এর উপর নির্ভর করে, যারা সংজ্ঞায়িত হয়েছে পরে। ইচ্ছাকৃতভাবে এলোমেলো ক্রমে রাখলাম — এটাই প্রমাণ করবে যে আপনার সিমুলেটর ফাইলের টেক্সট-ক্রম নয়, বরং প্রকৃত নির্ভরতা অনুসরণ করছে।

২. পার্সার

from dataclasses import dataclass, field
from typing import List

@dataclass
class Gate:
    kind: str
    output: str
    inputs: List[str] = field(default_factory=list)

def parse_netlist(text: str):
    primary_inputs, outputs, gates = [], [], []
    for lineno, raw in enumerate(text.splitlines(), 1):
        line = raw.split('#', 1)[0].strip()   # কমেন্ট ফেলে দেওয়া
        if not line:
            continue
        head, _, rest = line.partition(' ')
        kind = head.upper()
        rest = rest.strip()
        if kind == 'INPUT':
            primary_inputs.append(rest)
        elif kind == 'OUTPUT':
            outputs.append(rest)
        else:
            out_name, _, ins = rest.partition('=')
            in_names = [x.strip() for x in ins.split(',')]
            gates.append(Gate(kind=kind, output=out_name.strip(), inputs=in_names))
    return primary_inputs, outputs, gates

৩. গেট-নির্ভরতা গ্রাফ ও টপোলজিক্যাল সর্ট

প্রতিটা গেট একটা নোড। গেট G গেট H-এর উপর নির্ভরশীল যদি G-এর কোনো ইনপুট H-এর আউটপুট হয়। এটা হুবহু Graph Playground প্রজেক্টের Kahn’s algorithm — শুধু নোডগুলো এখানে “নাম” নয়, গেট।

from collections import deque

def topo_order(gates, primary_inputs):
    producer = {g.output: g for g in gates}
    in_degree = {g.output: 0 for g in gates}
    dependents = {g.output: [] for g in gates}

    for g in gates:
        for sig in g.inputs:
            if sig in producer:
                dependents[sig].append(g.output)
                in_degree[g.output] += 1
            elif sig not in primary_inputs:
                raise ValueError(f"অজানা সিগন্যাল {sig!r} — গেট {g.output}-এর ইনপুটে ব্যবহৃত")

    queue = deque(name for name, d in in_degree.items() if d == 0)
    order = []
    while queue:
        name = queue.popleft()
        order.append(name)
        for dep in dependents[name]:
            in_degree[dep] -= 1
            if in_degree[dep] == 0:
                queue.append(dep)

    if len(order) != len(gates):
        raise ValueError(
            "সার্কিটে feedback loop আছে — এটা কম্বিনেশনাল টপোলজিক্যাল সর্ট দিয়ে "
            "সমাধান করা যাবে না। ধাপ ৫-এর event-driven সিমুলেটর ব্যবহার করুন।"
        )
    return [producer[name] for name in order]

এই ফাংশনটাই আসল কাজটা করছে — টেক্সট ফাইলে যেভাবেই লেখা থাকুক না কেন, এটা নির্ভরতার সঠিক ক্রম বের করে দেবে। আর যদি সার্কিটে সত্যিকারের feedback loop থাকে (যেমন একটা latch), len(order) != len(gates) শর্তটা সেটা ধরে ফেলবে — এটাই graph-playground প্রজেক্টের cycle detection-এর সরাসরি পুনর্ব্যবহার।

৪. Steady-state এভালুয়েটর

GATE_FUNCS = {
    'AND':  lambda xs: all(xs),
    'OR':   lambda xs: any(xs),
    'NOT':  lambda xs: not xs[0],
    'NAND': lambda xs: not all(xs),
    'NOR':  lambda xs: not any(xs),
    'XOR':  lambda xs: sum(xs) % 2 == 1,
    'XNOR': lambda xs: sum(xs) % 2 == 0,
}

def simulate_combinational(gates, primary_inputs, input_values):
    ordered = topo_order(gates, primary_inputs)
    signals = dict(input_values)
    for g in ordered:
        args = [signals[i] for i in g.inputs]
        signals[g.output] = GATE_FUNCS[g.kind](args)
    return signals

৫. Full adder verify করা

উপরের নেটলিস্ট আসলে standard full adder — sum = a XOR b XOR cin, cout = ab + cin(a XOR b)। একটা brute-force truth table জেনারেটর দিয়ে সব ৮টা সমন্বয় যাচাই করুন:

from itertools import product

def print_truth_table(gates, primary_inputs, outputs):
    print(' '.join(primary_inputs) + ' | ' + ' '.join(outputs))
    for combo in product([False, True], repeat=len(primary_inputs)):
        values = dict(zip(primary_inputs, combo))
        result = simulate_combinational(gates, primary_inputs, values)
        row_in = ' '.join(str(int(values[n])) for n in primary_inputs)
        row_out = '  '.join(str(int(result[n])) for n in outputs)
        print(f' {row_in}   |  {row_out}')

আউটপুট মিলিয়ে দেখুন লক্ষ্য বিভাগের টেবিলের সাথে — একদম হুবহু মিলবে যদি নেটলিস্ট ঠিক থাকে।

৬. Propagation delay ও event-driven সিমুলেশন

এখন ধরে নিই প্রতিটা গেট-টাইপের একটা নির্দিষ্ট delay আছে (XOR একটু বেশি সময় নেয়, কারণ বাস্তবেও XOR ভেতরে একাধিক লজিক লেভেল দিয়ে বানানো হয়):

DELAY = {'AND': 1, 'OR': 1, 'NOT': 1, 'NAND': 1, 'NOR': 1, 'XOR': 2, 'XNOR': 2}

মূল ধারণা: যখন কোনো সিগন্যাল বদলায়, তার উপর নির্ভরশীল প্রতিটা গেটকে “re-evaluate” করার একটা ইভেন্ট শিডিউল করি, ঠিক তার delay পরে। সেই ইভেন্ট চালু হলে গেটটা তার তখনকার ইনপুট মান দিয়ে নতুন করে আউটপুট গণনা করে — যদি মান বদলায়, সেটা আবার তার fanout-এর জন্য নতুন ইভেন্ট তৈরি করে। এভাবেই পরিবর্তন সময়ের সাথে সাথে সার্কিটের ভেতর দিয়ে ঢেউয়ের মতো ছড়ায়।

import heapq

def event_driven_simulate(gates, primary_inputs, input_changes, initial=None, max_time=1000):
    fanout = {}
    for g in gates:
        for sig in g.inputs:
            fanout.setdefault(sig, []).append(g)

    current = {name: False for name in primary_inputs}
    for g in gates:
        current[g.output] = False
    if initial:
        current.update(initial)

    timeline = {name: [(0, current[name])] for name in current}
    event_queue = []
    seq = 0

    def push(t, kind, target, value=None):
        nonlocal seq
        heapq.heappush(event_queue, (t, seq, kind, target, value))
        seq += 1

    if not initial:
        for g in gates:                  # ফাঁকা "power-on" অবস্থা থেকে নেটলিস্ট একবার settle করাই
            push(0, 'EVAL', g)

    for t, sig, val in input_changes:
        push(t, 'INPUT', sig, val)

    while event_queue:
        t, _, kind, target, val = heapq.heappop(event_queue)
        if t > max_time:                 # ring-oscillator জাতীয় কখনো-না-থামা সার্কিটের নিরাপত্তা
            break

        if kind == 'INPUT':
            if current[target] == val:
                continue
            current[target] = val
            timeline[target].append((t, val))
            for g in fanout.get(target, []):
                push(t + DELAY[g.kind], 'EVAL', g)

        elif kind == 'EVAL':
            g = target
            args = [current[i] for i in g.inputs]
            new_val = GATE_FUNCS[g.kind](args)
            if new_val == current[g.output]:
                continue
            current[g.output] = new_val
            timeline[g.output].append((t, new_val))
            for g2 in fanout.get(g.output, []):
                push(t + DELAY[g2.kind], 'EVAL', g2)

    return timeline

লক্ষ্য করুন EVAL ইভেন্ট গেটের আউটপুট মান নয়, বরং “এখন re-evaluate করো” — এই নির্দেশটা বহন করে। ফায়ার হওয়ার মুহূর্তে সেই মুহূর্তের বর্তমান ইনপুট মান দিয়ে হিসাব করা হয়, শিডিউল করার মুহূর্তের পুরনো মান দিয়ে নয়। এই ছোট্ট সিদ্ধান্তটাই stale-value bug এড়ায়।

৭. SR latch — feedback loop-এর আসল পরীক্ষা

INPUT s
INPUT r

NOR q  = r, qn
NOR qn = s, q

OUTPUT q
OUTPUT qn

q-এর গেট নির্ভর করে qn-এর উপর, আর qn-এর গেট নির্ভর করে q-এর উপর — এটা সত্যিকারের চক্র। topo_order() চালালে এটা ValueError দেবে, ঠিক যেমন প্রতিশ্রুতি দেওয়া হয়েছিল। কিন্তু event_driven_simulate() কোনো সমস্যা ছাড়াই এটা চালাতে পারে, কারণ প্রতিটা গেট delay-এর পর re-evaluate হয় — সার্কিট instant loop-এ আটকায় না, বরং সময়ের সাথে সাথে ধাপে ধাপে স্থির হয়।

S=0, R=0 অবস্থায় দুইটা বৈধ স্থির অবস্থা আছে — (Q=1, Qn=0) অথবা (Q=0, Qn=1) — কোনটায় সেটেল করবে তা নির্ভর করে আগে কোন অবস্থায় ছিল, এটাই SR latch-এর “মেমরি” রাখার ক্ষমতার মূল রহস্য। উপরের লক্ষ্য বিভাগের ট্রেসে আমরা S=1 পাঠিয়ে জোর করে (Q=1, Qn=0)-এ নিয়ে গেছি — সেটাই SET অপারেশন।

নিজেকে চ্যালেঞ্জ করুন

1. Ripple-carry adder — full adder নেটলিস্ট প্রোগ্রামগতভাবে জেনারেট করে N-বিট adder বানান (একটার cout পরেরটার cin-এ জোড়া দিয়ে)
2. Back-edge রিপোর্ট — cycle পেলে শুধু “cycle আছে” না বলে ঠিক কোন গেট থেকে কোন গেটে ফিরে যাওয়া edge-টা loop তৈরি করছে সেটা দেখান (graph-playground-এর DFS edge classification পুনর্ব্যবহার করুন)
3. Critical path — প্রতিটা গেটের সবচেয়ে দীর্ঘ input-থেকে-output delay path বের করুন; এটাই বলে দেয় পুরো সার্কিট কত দ্রুত ক্লক করা যাবে
4. Multi-bit bus — a[7:0]-এর মতো ভেক্টর সিগন্যাল সাপোর্ট করুন, একবারে ৮-বিট বাসে পুরো সার্কিট চালান
5. D flip-flop — একটা clock ইনপুট আর edge-detection যোগ করে সিকোয়েন্সিয়াল সার্কিট (latch থেকে এক ধাপ এগিয়ে) simulate করুন

এটা যেখানে গিয়ে মিশবে

এখানে যা শিখলেন	পরে কোথায় লাগবে
Dependency গ্রাফ + Kahn’s topological sort	mathematics/graph-theory ও Graph Playground (Level 0)-এর সরাসরি পুনর্ব্যবহার
Event-driven simulation, priority queue	Level 11 — Advanced Architecture; Icarus Verilog/Verilator বাস্তবে এভাবেই কাজ করে
Feedback loop চেনা ও সামলানো	এই মডিউলেরই পরের প্রজেক্ট — FSM Vending Machine, latch/flip-flop
Propagation delay মডেলিং	Level 3 — CPU Architecture-এর clock frequency ও timing constraint
Critical path timing	Level 11 — timing closure, performance profiling