## Diagram: Comparison of Gibbs Update Strategies
### Overview
The image compares three computational strategies for updating probabilistic bits (p-bits) in a network:
1. **Synchronous Gibbs** (a)
2. **Pseudo-asynchronous Gibbs** (b)
3. **Truly Asynchronous Gibbs** (c)
Each section includes network diagrams, timelines, and hardware/software annotations to illustrate update mechanisms and efficiency.
---
### Components/Axes
#### (a) Synchronous Gibbs
- **Network**: Fully connected nodes labeled "N p-bits" (blue dots).
- **Timeline**:
- Sequential updates: `update p-bit 1 → update p-bit 2 with updated p-bit 1 → ... → update p-bit N with updated p-bits 1 to N-1`.
- Time complexity: `time to update all p-bits = N × T_clk` (horizontal axis labeled `T_clk`).
- **Hardware**: No explicit hardware shown.
#### (b) Pseudo-asynchronous Gibbs
- **Network**: Nodes colored in 5 distinct colors (blue, red, green, orange, purple).
- **Timeline**:
- Parallel updates by color:
- `update all p-bits with color 1 → update all p-bits with color 2 based on updated color 1 p-bits → ... → update all p-bits with color 5 based on updated color 1–4 p-bits`.
- Time complexity: `time to update all p-bits = T_clk`.
- **Legend**: "5 Colors" (color-coded phases).
#### (c) Truly Asynchronous Gibbs
- **Network**: Fully connected nodes (no color coding).
- **Timeline**:
- Uncoordinated updates: Multiple `T_clk` phases with no phase-shifting or graph coloring.
- Time complexity: `time to update all p-bits ≈ <T_p-bit>` (average clock period).
- **Hardware**: VOD (Voltage-Operated Device) with labeled `p-bit` and `VDD` (power supply).
---
### Detailed Analysis
#### (a) Synchronous Gibbs
- **Flow**: Strict sequential updates propagate dependencies (e.g., p-bit 2 uses updated p-bit 1).
- **Time Complexity**: Linear scaling with `N` (number of p-bits), as each update depends on the prior.
#### (b) Pseudo-asynchronous Gibbs
- **Flow**: Parallel updates grouped by color, reducing dependency chains.
- **Time Complexity**: Constant per phase (`T_clk`), but requires 5 phases for full update.
#### (c) Truly Asynchronous Gibbs
- **Flow**: No coordination; updates occur independently across phases.
- **Hardware**: VOD suggests analog/digital hybrid implementation for faster, less synchronized operations.
---
### Key Observations
1. **Synchronous vs. Pseudo-asynchronous**:
- Synchronous has higher latency (`N × T_clk`) but deterministic dependencies.
- Pseudo-asynchronous reduces latency to `T_clk` via parallel color-based updates.
2. **Truly Asynchronous**:
- Eliminates explicit coordination, relying on hardware (VOD) for faster average updates (`<T_p-bit>`).
- No phase-shifting or coloring implies higher concurrency but potential for race conditions.
3. **Hardware Role**:
- VOD in (c) implies physical layer optimization for asynchronous operations.
---
### Interpretation
- **Efficiency Trade-offs**:
- Synchronous ensures correctness at the cost of speed.
- Pseudo-asynchronous balances speed and coordination via color-coded phases.
- Truly asynchronous prioritizes speed using hardware but risks instability.
- **Scalability**:
- Synchronous methods become impractical for large `N` due to linear scaling.
- Asynchronous strategies (pseudo/truly) are more scalable but require careful hardware/software design.
- **Uncertainty**:
- `<T_p-bit>` in (c) suggests variability in update times, unlike fixed `T_clk` in (a) and (b).
This analysis highlights the tension between computational correctness, speed, and hardware constraints in probabilistic computing architectures.
