ai slob

Day 27 把控制留在 GPU，也把一件更容易看走眼的事寫出來：同一個 block 裡的 32 個 workers，不是 32 條 Markov chain。它們讀同一份 current，選一個 winner，做一次轉移。

這解決了每步回 host 的問題，卻沒有讓一條 chain 變成很多條。每個新狀態仍依賴上一步的接受結果：

state[t]
    -> proposal[t]
    -> accept / reject
    -> state[t + 1]

即使一個 step 已經很快，這條相依性也不會消失。

今天要處理另一個問題：既然 GPU 擅長同時做很多工作，能不能同時跑很多條 SA chain？

答案是可以，但「同時跑很多條」至少有三種完全不同的意思：

parallel proposals
    many workers propose moves from one shared layout
    only one move is committed per round

independent SA
    every chain owns a private layout and RNG
    chains never communicate

parallel tempering
    every replica owns a private layout and temperature
    neighboring temperatures periodically exchange states

Day 27 的 proposal workers 屬於第一種。今天實作的是第三種，也就是 Parallel Tempering，以下簡稱 PT。

它不只是把相同程式複製很多份。它要讓高溫 replica 負責穿越障礙，低溫 replica 負責收斂，再讓找到的 layout 在溫度梯子上移動。

為什麼 LCN 適合拿來介紹 Parallel Tempering？

LCN 的最佳化目標是：

objective(layout) = (K, n_K, Phi, C)

K     = 單一 edge 承受的最大 crossing 數
n_K   = crossing 數等於 K 的 edge 數量
Phi   = 所有 edge crossing count 的平方和
C     = crossing pair 總數

正式排名採嚴格 lexicographic order：

先比較 K
K 相同才比較 n_K
n_K 相同才比較 Phi
Phi 相同才比較 C

這個 landscape 有兩個特性。

第一，移動一個 node 會同時改變多條 incident edges，objective 不會平滑地一點一點下降。

current
    K = 4

necessary detour
    K = 5

better basin
    K = 3

只接受改善的 local search 走不到第三個狀態。

第二，不同區域可能有相同的 K，但 bottleneck edges 完全不同。

layout A
    K = 4
    worst edges = {e3, e9}

layout B
    K = 4
    worst edges = {e17}

只看目前的數字，兩個 layout 似乎很接近；從 A 走到 B，卻可能必須重新排列一大片幾何結構。

這正適合用多個溫度分工：

hot replicas
    accept more temporary regressions
    cross barriers
    change the set of bottleneck edges

cold replicas
    reject most regressions
    refine n_K, Phi and C
    preserve promising basins

這個案例也能同時介紹三個 GPU 最佳化觀念：

1. 用 replica-level parallelism 增加 GPU throughput。
2. 讓每個 replica 的 state 留在 device，避免每一步跨 PCIe。
3. 在交換 state 時正視 global-memory traffic，而不是把 exchange 當成免費操作。

Replica 和 Proposal Worker 不一樣

這是今天最容易混淆的地方。

假設從同一個 layout 同時產生 512 個 moves：

one current layout
    + proposal 0
    + proposal 1
    + proposal 2
    ...
    + proposal 511

select one proposal
commit one next state

這 512 個 workers 只幫同一條 trajectory 看更多候選點。下一輪仍然只有一份 current layout。

真正的 512 個 replicas 則是：

replica 0   owns layout 0, objective 0, RNG 0, temperature 0
replica 1   owns layout 1, objective 1, RNG 1, temperature 1
replica 2   owns layout 2, objective 2, RNG 2, temperature 2
...
replica 511 owns layout 511, objective 511, RNG 511, temperature 511

每一個 replica 都能接受不同的 move，形成不同的 trajectory。

因此增加 replica 數量主要增加搜尋廣度：

more replicas
    -> more simultaneous trajectories
    -> more basins explored

它不會自動增加單條 chain 的深度：

512 replicas * 1,000 steps

is not

1 replica * 512,000 dependent steps

兩者的 proposal 總量相同，但能到達的搜尋路徑不同。

只跑 Independent Chains 還少了什麼？

最簡單的 parallel SA 是讓多條 chain 完全獨立：

for replica in parallel:
    run_sa(private_layout[replica], private_rng[replica])

best = min(all_replica_bests)

這已經很實用。它能降低單一 seed 運氣不好的風險，也很容易映射到 GPU。

但每條 chain 只能在自己的溫度計畫內活動。

hot chain
    explores broadly
    may never settle long enough to refine

cold chain
    refines well
    may never escape its initial basin

Parallel tempering 增加一條溝通路徑：

local SA steps at fixed temperatures
    -> exchange neighboring replicas
    -> local SA steps
    -> exchange neighboring replicas
    -> repeat

重要的是交換「state」，而不是把兩個 objective 平均，也不是把兩條 layout 混在一起。

一份 layout 可以先在高溫探索，再逐步交換到低溫精修；卡在低溫的 state 也可能被送往高溫，重新擾動後再回來。

溫度不是每個 Replica 各自一路降到底

普通 SA 常用 cooling schedule：

T[next] = cooling_rate * T[current]

Parallel tempering 常用一組固定的溫度階梯：

T[0] = hot
T[1]
T[2]
...
T[G - 1] = cold

目前 CUDA PTS 的預設 cooling_rate 是 1.0，所以 ladder 在搜尋期間保持固定。每個 rung 扮演穩定角色，state 在 rungs 之間移動。

我們使用 geometric ladder，把 hot 與 cold 的比例平均分配到每個 gap：

fraction[g] = g / (G - 1)

T[g] = T_hot * (T_cold / T_hot) ** fraction[g]

四個 replicas、hot 為 4.385635、cold 為 1.0 時：

rung 0: 4.385635
rung 1: 2.679302
rung 2: 1.636857
rung 3: 1.000000

Metropolis 看的是 reciprocal temperature：

beta = 1 / T

能量差的尺度通常也跨越倍數。Geometric spacing 比較容易讓相鄰 rungs 保持相近的相對比例，但它仍然只是起點；最後要看每個 gap 的交換統計。

Hot 和 Cold 的數字不是隨便猜的

我們先替一個 K 增加一的 move 指定接受機率。

Search H 中，K 的預設權重是：

w_K = -log(0.01)
    = 4.605170185988091

在 cold temperature T = 1 時，如果其他項目不變：

P(accept K + 1 at cold)
    = exp(-w_K / 1)
    = 0.01

Cold replica 大約只接受百分之一的這類退步。

Hot endpoint 則校準成約百分之三十五：

target_probability = 0.35

T_hot = w_K / -log(target_probability)
      = 4.385634839738656

P(accept K + 1 at hot)
    = exp(-w_K / T_hot)
    = 0.35

這種設定方法比「溫度看起來設成 100 應該很熱」更可解釋。溫度必須和 energy 的尺度一起討論。

正式答案用 Lexicographic Ranking，交換不能直接用 Tuple

LCN 的 official best 一定要保持：

(K, n_K, Phi, C)

但 Metropolis acceptance 與 replica exchange 都需要一個可計算差值的 scalar energy。

直接寫巨大權重很危險：

bad idea

energy = 1e12 * K
       + 1e8  * n_K
       + 1e4  * Phi
       + C

它會造成三個問題：

temperature becomes impossible to interpret
small terms can disappear in floating-point subtraction
exchange probabilities collapse to almost 0 or 1

目前 PTS 將兩個角色分開。

正式發布 best 時：

compare lexicographically:
    (K, n_K, Phi, C)

決定 local transition 與 replica exchange 時：

H = w_K   * K
  + w_nK  * n_K
  + w_Phi * Phi / phi_scale
  + w_C   * C   / c_scale

預設權重都有機率意義：

w_K   = -log(0.01) = 4.605170...
w_nK  = -log(0.20) = 1.609437...
w_Phi = -log(0.40) = 0.916291...
w_C   = -log(0.60) = 0.510826...

在 T = 1 且其他項目不變時，各項經過 scale 正規化後的一個單位退步，分別對應約 1%、20%、40%、60% 的接受機率。

Phi 與 C 的自然尺度較大，因此還要除以校準尺度。如果 pilot 沒有提供足夠資料，目前 CUDA fallback 使用：

phi_scale = 2 * typical_K + 1
c_scale   = 1

原因是某條 edge crossing count 從 K 增加到 K + 1 時，它對平方和的改變是：

(K + 1) ** 2 - K ** 2
    = 2 * K + 1

這避免 Phi 的數字尺度輕易淹沒 n_K。

這裡要守住一條界線：

Search H controls movement.
Lexicographic tuple defines the answer.

所以 CUDA local step 還有一個保護條件：只要 candidate 的 K 真正下降，就直接接受，不讓 secondary terms 或 proposal correction 把它拒絕。

Replica Exchange 的公式到底在做什麼？

假設相鄰兩個 temperature slots 是 a 與 b：

slot a owns temperature T_a and state x_a
slot b owns temperature T_b and state x_b

交換的 log acceptance ratio 為：

H_a = SearchH(x_a)
H_b = SearchH(x_b)

log_alpha = (H_a - H_b) * (1 / T_a - 1 / T_b)

accept if:
    log(U) < min(0, log_alpha)

U 是介於 0 與 1 的 uniform random number。用 log space 比先計算巨大或極小的 exponential 更穩定：

avoid:
    U < exp(log_alpha)

prefer:
    log(U) < min(0, log_alpha)

一個具體例子

假設左邊是 hot slot，右邊是 cold slot：

T_hot  = 4
T_cold = 1

Hot slot 目前放著比較差的 state：

H_hot_state  = 10
H_cold_state = 6

log_alpha
    = (10 - 6) * (1/4 - 1/1)
    = -3

exchange probability
    = exp(-3)
    = 0.0498

這次交換會把高能量 state 塞進 cold slot，也會把低能量 state 送回 hot slot，所以大多數時候拒絕。

如果 hot slot 剛好找到更好的 state：

H_hot_state  = 6
H_cold_state = 10

log_alpha
    = (6 - 10) * (1/4 - 1/1)
    = 3

exchange probability
    = 1

好 state 會進入 cold slot 繼續精修，差 state 則進入 hot slot 重新探索。這正是 PT 想建立的 transport。

為什麼只交換相鄰溫度？

Hot 與 cold 的溫差太大時，兩邊看到的典型 energy 分布也相差很大，直接交換的接受率容易接近零。

加入中間 rungs 後，state 可以一步一步移動：

T[0] <-> T[1] <-> T[2] <-> T[3]
 hot                         cold

交換採 even/odd phases：

phase 0:
    T[0] <-> T[1]
    T[2] <-> T[3]

phase 1:
    T[1] <-> T[2]

同一個 phase 中沒有任何 slot 同時參加兩次交換，因此各 pair 可以平行執行，不需要處理寫入衝突。

四個 rungs 執行四輪 exchange 時：

round 0: 2 attempts
round 1: 1 attempt
round 2: 2 attempts
round 3: 1 attempt

不要把 exchange rounds 直接當成 exchange attempts。測試與 telemetry 必須依真正產生的 pairs 計數。

Replicas 多於 Temperature Rungs 時怎麼辦？

目前實作把 replica 數 R 與溫度 rung 數 G 分開。

R = 8 replicas
G = 4 temperature rungs

T[0]: replica slots 0, 1
T[1]: replica slots 2, 3
T[2]: replica slots 4, 5
T[3]: replica slots 6, 7

Exchange 配對相鄰 rung 的相同 copy index：

phase 0:
    slot 0 <-> slot 2
    slot 1 <-> slot 3
    slot 4 <-> slot 6
    slot 5 <-> slot 7

phase 1:
    slot 2 <-> slot 4
    slot 3 <-> slot 5

相同溫度的兩個 copies 不需要互換；交換後的統計分布與計算工作都不會改變。多 copies 的作用是增加每個溫度的搜尋 breadth，不是製造更多溫度刻度。

CPU 範例：把 PT 的控制流程寫清楚

今天新增的可執行範例是：

• parallel_tempering_demo.py

它沿用 Day 26 的 exact CPU evaluator，每一個 proposal 都完整驗證 layout 並重算 objective。

這當然不是高效版本。我選它是因為 PT 最容易出錯的地方是：

which state owns which temperature?
which probability decides exchange?
what exactly moves after acceptance?
does official best still use lexicographic order?

先用可讀、可重現的小程式確認 state machine，再把同一個 mapping 搬進 CUDA，比一開始就把 exchange、incremental crossing、shared memory 和 bandit operators 混在一起更容易除錯。

核心 state 很小：

@dataclass
class ReplicaState:
    positions: list[Point]
    objective: Objective
    lineage: int

溫度不放在 ReplicaState 裡。它屬於固定 slot。

交換接受後，程式寫的是：

states[left], states[right] = states[right], states[left]

它沒有交換：

temperatures[left], temperatures[right]

所以完整 state 搬到另一個 temperature slot，temperature ladder 仍然固定。

執行範例

在 repository root 執行：

python case_4/examples/parallel_tempering_demo.py

固定 seed 的輸出如下：

temperatures: [4.385635, 2.679302, 1.636857, 1.0]
initial objectives: [{'k': 11, 'n_k': 1, 'phi': 776, 'crossings': 54},
                     {'k': 7, 'n_k': 2, 'phi': 254, 'crossings': 30},
                     {'k': 11, 'n_k': 1, 'phi': 710, 'crossings': 49},
                     {'k': 8, 'n_k': 2, 'phi': 432, 'crossings': 39}]
best objective: {'k': 1, 'n_k': 2, 'phi': 2, 'crossings': 1}
final lineage by temperature: [0, 3, 2, 1]
local accept rates: [0.31, 0.2664, 0.198, 0.1556]
T[0]<->T[1]: 22/50 accepted (observed=0.440, mean probability=0.451)
T[1]<->T[2]: 14/50 accepted (observed=0.280, mean probability=0.342)
T[2]<->T[3]: 21/50 accepted (observed=0.420, mean probability=0.439)
cold-hot-cold round trips: 2

這份輸出能檢查幾件事。

第一，hot slot 的 local acceptance rate 比 cold slot 高：

hot:  0.3100
cold: 0.1556

第二，每個 temperature gap 都真的有 exchange attempts，不是只有最熱與最冷兩端各自跑。

第三，lineage 已經從初始的 [0, 1, 2, 3] 重新排列成 [0, 3, 2, 1]。

第四，有兩次 lineage 完成：

cold -> hot -> cold

這表示 state 不只在相鄰兩格間來回抖動，確實穿越了完整 ladder。

這仍然只是固定 seed 的 correctness demonstration。它不能證明 PT 在所有 graph 都比 independent chains 快。效能結論必須用多個 seeds、相同 wall-clock budget 與正式 GPU path 測量。

CUDA 怎麼放這些 Replicas？

目前主要 local-step launch 是：

pts_fused_replica_steps_kernel<<<R, threads>>>(...);

Mapping 是：

one CUDA block
    -> one replica

threads inside the block
    -> cooperate on crossing counts and objective reduction

R blocks
    -> advance R private states in parallel

每個 replica block 內仍然有 sequential steps：

for (int step = 0; step < steps; ++step) {
    propose_one_move();
    evaluate_candidate_cooperatively();
    accept_or_reject();
    commit_if_accepted();
}

所以 GPU parallelism 有兩層：

between replicas
    many trajectories run concurrently

inside one replica evaluation
    threads cooperate over edges

Exchange 則用另一個 kernel：

pts_pt_exchange_kernel<<<number_of_pairs, 128>>>(...);

一個 block 負責一組 adjacent-temperature pair，128 個 threads 合作交換 coordinates 與 per-edge counts。

Local-step kernel 和 exchange kernel 的 launch boundary 也提供全域排序：先完成這一批 local moves，再對一致的 replica states 做 exchange。

Exchange 不是只交換兩個 Objective

如果只交換：

(K, n_K, Phi, C)

coordinates 與 cached edge counts 仍留在原位，下一個 local move 就會從互相矛盾的 state 開始。

目前接受 exchange 時會搬動：

x coordinates
y coordinates
per-edge crossing counts
objective
lineage id
round-trip transport state
hot snapshot and crossed-edge bits

不搬動 temperature：

T stays at the rung slot

Scratch delta 不代表 persistent state，下一次 proposal 會覆寫，也不必跟著交換。每個 replica 的 personal elite 代表歷史最佳記錄，同樣不等於 current state。

persistent current state
    must move together

slot policy state
    temperature stays

recomputable scratch
    does not need to move

historical archive
    has separate ownership semantics

交換整份 State，還是只交換 Temperature Label？

標準 PT 有兩種等價的表示法。

作法 A：溫度固定，交換完整 state

before
    slot 0: T_hot,  state A
    slot 1: T_cold, state B

after
    slot 0: T_hot,  state B
    slot 1: T_cold, state A

每個 slot 的 temperature 與 kernel mapping 很直觀，但接受交換時要搬 O(N + E) 的 device memory。

作法 B：state 固定，交換 temperature label

before
    state A uses T_hot
    state B uses T_cold

after
    state A uses T_cold
    state B uses T_hot

這可以只交換小型 label 或索引，接近常數大小。代價是 local kernel 每次讀溫度、記錄 rung telemetry、配對 exchange 時都要經過 indirection。Lineage、bandit state 與 per-rung statistics 的 ownership 也要重新定義。

目前 CUDA 實作選作法 A：

swap x, y, counts, objective and transport metadata
keep d_T fixed

這讓每個 slot 的資料連續、launch mapping 穩定，也比較容易驗證。

反直覺的地方是：exchange kernel 沒有 host-device transfer，仍然可能付出可觀的 global-memory bandwidth。

一次 Accepted Exchange 搬多少資料？

只看 current layout 的主要整數陣列，一個 replica 有：

2 * N coordinate integers
E per-edge crossing-count integers

兩個 replicas 互換時，每個元素至少要讀一次、寫一次。忽略 objective 與 telemetry 的下限估算是：

traffic_bytes
    = 2 states
    * 2 operations per value
    * (2*N + E) integers per state
    * 4 bytes per integer

    = 16 * (2*N + E) bytes

假設一個示意 instance 有：

N = 1000
E = 2379

traffic
    = 16 * (2*1000 + 2379)
    = 70,064 bytes
    = 68.4 KiB

這不是 PCIe traffic，而是 GPU global-memory traffic。128 個 threads 可以合併存取並平行搬動，成本仍然不是零。

因此 exchange interval 有實際 trade-off：

interval too short
    frequent kernel boundaries
    frequent state swaps
    local chains do too little work between exchanges

interval too long
    useful states diffuse through ladder too slowly
    cold and hot replicas behave almost independently

目前預設每個 replica 做 150 個 local proposals，再嘗試一次 adjacent-rung exchange round。這是可調參數，不是普遍最佳值。

Replica 數量也會增加 Workspace

目前的估算 helper 對每個 replica 計入：

current x/y
elite x/y
current per-edge counts
trial delta counts
small fixed overhead

估算式是：

workspace_per_replica
    = 4 * (4*N + 2*E) + 256 bytes

它還不是整個 solver 的完整顯存帳單。Production path 另外有 objective、operator weights、RNG/control、telemetry、lineage 與 hot crossed-edge bitsets。

總量會隨 replica 數近似線性增加：

total replica workspace
    approximately R * workspace_per_replica

所以 512 replicas 並不自動比 32 replicas 好。它可能帶來：

more search breadth
more resident blocks
more device memory
more proposals competing for edge-evaluation bandwidth
more exchange pairs

如果一個 replica block 已經因 shared memory 或 registers 限制 occupancy，繼續增加 replicas 只能延長 block queue，不會讓所有 replicas 真正同時執行。

要看的是固定 wall-clock 下完成多少有效 steps、探索多少不同 basins，以及最佳 K 何時出現。

初始 Layout 不同，RNG 不同，才是真的多條搜尋

如果所有 replicas 從相同 layout 開始，又不小心使用相同 RNG stream：

same current state
same proposed node
same destination
same acceptance draw

-> identical trajectory

此時配置 512 份 state 只是在重複相同工作。

目前初始化會優先配置不同的 portfolio layouts，再對不足的 copies 做真實座標 jitter。Telemetry 也應記錄：

distinct initial layout hashes

RNG 則要有可重現但不同的 streams：

stream_seed[replica]
    = base_seed + deterministic_offset(replica)

「不同」和「不可重現」是兩件事。Debug 時仍要能用同一個 base seed 重播整次實驗。

Local Proposal 不對稱時，普通 Metropolis 公式會錯

如果 proposal 從所有空 grid points 均勻抽樣，forward 與 reverse proposal probability 通常相同，可以使用：

log_alpha = min(0, -DeltaH / T)

LCN 的 production operators 不全是均勻 proposal。它可能先挑 worst edge 附近的 node，再從 local 或 regional 區域找 destination。

current state
    -> focus sampler strongly prefers node v

candidate state
    -> after crossings change, reverse sampler may rarely choose v

此時要加入 Hastings correction：

log_alpha
    = min(
        0,
        -DeltaH / T
        + log(q_reverse)
        - log(q_forward)
      )

目前 CUDA PTS 對 focus 加 local/regional 的 operators 計算 forward/reverse probability；對明確對稱的 local/regional proposals 使用：

log(q_reverse) - log(q_forward) = 0

若 reverse support 是空集合，就不能假裝 correction 是零。

這也是為什麼今天的 CPU 範例使用 uniform free-position proposal：它讓 exchange 與 replica ownership 成為主角，不需要同時塞進另一套 proposal-density 計算。

Production PTS 是最佳化 Heuristic，不是精確取樣器

這裡必須誠實說明目前實作的限制。

有些 operator，例如 centroid destination 與 SDG candidate selection，沒有容易取得的 reverse proposal probability。Production kernel 對這些 moves 保留 LexKey-greedy 行為；其他可計算的 operators 才使用 Metropolis-Hastings。

因此整套 operator mixture 不能宣稱是嚴格滿足 detailed balance 的 MCMC sampler。

safe conclusion
    heuristic tempered search for optimization

unsafe conclusion
    exact samples from a known Boltzmann distribution

對 LCN 最佳化，我們最在意的是：

validated best (K, n_K, Phi, C)
time to target K
robustness across seeds

如果任務改成統計物理取樣，operator mixture、Hastings ratio 與 exchange invariance 就必須全部重新審核。

這是一個很有價值的反直覺點：用了標準 replica-exchange 公式，不代表整個 solver 自動成為精確的 parallel-tempering sampler。Local transitions 也必須符合相同的機率模型。

Acceptance Rate 高，不代表 Ladder 好

假設所有 rungs 的溫度幾乎相同：

T = [1.00, 0.99, 0.98, 0.97]

Exchange rate 可能很高，因為相鄰 distributions 很接近。但 hot replica 根本不夠熱，沒有穿越 barrier 的能力。

另一個極端是：

T = [1000, 10, 1, 0.01]

相鄰 energy distributions 幾乎不重疊，exchange acceptance 接近零，state 無法走完整條 ladder。

所以至少要一起看：

local acceptance rate per temperature
exchange attempts per gap
exchange acceptance per gap
mean theoretical exchange probability per gap
cold -> hot -> cold round trips
hot-state decorrelation

Round trip 比單一 exchange rate 更接近我們真正想知道的事：state 能不能從 cold 到 hot、發生有意義的改變，再回到 cold。

目前 CUDA telemetry 還會比較 hot visit 前後的 crossed-edge sets。若 lineage 到過 hot rung，卻總是帶著幾乎相同的 bottleneck structure 回來，單看 round-trip count 仍可能過度樂觀。

Benchmark Parallel SA 應該固定什麼？

比較 single SA、independent replicas 與 PT 時，最公平的主軸是相同 wall-clock budget：

same graph
same legality and crossing semantics
same official lexicographic comparator
same hardware
same wall-clock budget
multiple base seeds
final best re-evaluated by exact checker

記錄：

best K
best full tuple
time to first target K
proposals per second
legal proposal rate
local acceptance per rung
exchange attempts and accepts per gap
round trips
distinct initial layouts
peak GPU memory

另外可以做一個 proposal-budget 實驗，但要清楚標示它回答不同問題：

fixed proposal count
    compares search efficiency per attempted move

fixed wall-clock
    compares delivered result on actual hardware

GPU 最佳化最終要以第二種為主。PT 可能每個 proposal 做更多管理工作，卻因為更早到達較好的 basin 而有更好的 time-to-target；也可能 exchange 與額外 replicas 只增加成本。兩種結果都要由 measurements 決定。

今天真正搬進 GPU 的是什麼？

Day 27 搬的是一條 chain 的 control loop。

Day 28 再增加：

R private current states
R private objectives and per-edge counts
R temperature slots
R independent search trajectories
adjacent-rung exchange kernel
lineage and round-trip telemetry
protected global lexicographic best

完整資料流變成：

CPU
    allocate replica workspace
    upload graph and initial layouts
    launch fused local steps
              |
              v
GPU
    R replica blocks advance private states
              |
              v
    adjacent exchange blocks swap accepted states
              |
              v
    repeat without per-proposal host decisions
              |
              v
CPU
    retrieve final elite and telemetry
    exact re-evaluate published answer

這個例子介紹的 GPU 加速不只是「多開幾個 threads」。真正的設計問題是：

parallel work unit
    one private replica state

state placement
    persistent arrays stay in device memory

cooperation
    threads reduce crossings inside each replica

communication
    neighboring replicas exchange at controlled boundaries

bandwidth cost
    accepted swaps move O(N + E) state

correctness
    Search H controls motion; lexicographic tuple controls the answer

Parallel SA 的價值不是讓同一條 chain 違反時間相依性，而是讓 GPU 同時維持多條真正不同的搜尋路徑，並用溫度交換讓探索與收斂互相傳遞成果。

下一篇可以把 Day 22 到 Day 28 的 optimization stages 放進同一套 benchmark contract：到底該量 kernel time、end-to-end time、time-to-target，還是解的品質，以及哪些數字不能混在一起比較。

對照實作

• CUDA PTS local steps 與 replica exchange
• CUDA PTS config
• Search H objective
• Python ladder、pairing 與 workspace helpers
• Day 28 可執行 PT 範例
• CUDA PTS parity tests
• Search H tests
• Hastings tests