From Circles to Silicon: Implementing the Cyclic Prime Emergence Algorithm on FPGA

The Cyclic Prime Emergence Algorithm

The core algorithm operates on the following principles:

1. Define two concentric circles with radii r and 2r.
2. Rotate them at a constant linear velocity from a common starting point.
3. Every time the first circle completes a full revolution:
   1. An incremental master counter n is updated.
   2. If no other concentric circle completes a revolution at that exact instant, the counter value n is flagged as a prime number.
   3. If n is confirmed as a prime number, a new concentric circle with a radius of nr is dynamically spawned.

The mathematical proof of the algorithm is detailed in our preprint paper.

Architecture Philosophy: Translating Geometry into Digital Logic

In software environments, classic algorithms like the Sieve of Eratosthenes rely heavily on memory arrays to flag composite elements, while trial division exhibits an escalating time complexity as numbers scale up.

An FPGA implementation allows for the direct translation of this geometric algorithm into hardware structures, where the abstract concepts are mapped as follows:

• Rotating Circles → Programmable Oscillators: Each detected prime number p is assigned to an independent countdown register (oscillator) with a period equal to p. Initially, the system only contains the oscillator for 2, while the rotation of 1 is digitized by a master counter.
• Lap Line → Zero-Detection Logic: When an oscillator countdown reaches zero, it indicates that p steps have elapsed, signaling a completed revolution.
• Divisibility Check → Combinational OR Gate Tree: The simultaneous evaluation of all coincidence (at_lap) signals is routed through a massive, wide OR gate structure.

O(1) Time Complexity per Step: If at least one oscillator fires its coincidence signal, the OR gate outputs a "1" (flagging a composite number). This combinational response depends solely on the propagation delay of the OR gate tree, regardless of the magnitude of n or the number of active oscillators. Therefore, the system exhibits O(1) evaluation latency per candidate number for a fixed hardware implementation.

A fully parallel and concurrent approach would require just two clock cycles per step (one for the state update and one for evaluation), preserving the ideal O(1) time window.

To optimize resource utilization on the physical silicon, an alternative hierarchical architecture was designed:

• Oscillators are grouped into modular clusters of 8 units, where each cluster updates its oscillators sequentially.
• All clusters operate in parallel with respect to each other.
• The coincidence outputs of the clusters are grouped into 8-bit pipeline registers.
• These intermediate registers feed the final reduction OR gate tree.

This specific layout completes the verification loop across all oscillators in exactly 11 clock cycles, keeping the overall execution time deterministic and bound to an O(1) complexity class.

Hardware Specification Table for the Detection of 1024 Primes

To identify the first 1024 prime numbers, the architectural parameters are configured as follows:

Synthesis Results on a Cyclone IV E FPGA (EP4CE15E22C6)

The circuit evaluation was performed using Altera Quartus Prime on an entry-level Intel Cyclone IV E FPGA (EP4CE15E22C6) targeting the discovery of the first 1024 primes (P = 1024, N_BITS = 13). The compilation data extracted from the Fitter and TimeQuest Timing Analyzer reports are summarized below:

Analysis of the worst-case critical path reported a positive setup slack of 3.303 ns, with a total Data Delay of 6.618 ns. The critical path was located on the routing trace from the master broadcast bus load_val[8] to the internal destination register counters[0][8] of an oscillator cluster, caused by high fan-out stress when driving signals across 128 distinct target blocks.

The architecture comfortably occupies 67% of the logic fabric on an old-generation legacy device. When targeting modern high-performance FPGAs (e.g., 28nm or finer processes), the operating frequency is expected to scale up linearly with the silicon specifications, requiring no modifications to the original VHDL source code.

Deterministic Timing & Absolute Predictability

In standard software implementations, execution times fluctuate heavily due to CPU cache misses, branch mispredictions, and operating system context switching. In this custom hardware layout, execution time is strictly deterministic.

Because the engine evaluates each candidate number $n$ inside a fixed window of exactly 11 clock cycles (8 cycles for the internal cluster loop and 3 cycles for the pipeline reduction tree and decision latching), the exact clock cycles needed to discover the $P$-th prime can be calculated with mathematical precision using the formula:

(where pP represents the numerical value of the target P-th prime number).

Cycle-accurate behavioral simulations carried out in ModelSim verified this behavior exactly:

• For P = 256 (p256= 1619): The system took exactly 17,789 clock cycles to complete.
• For P = 1024 (p1024 = 8161): The entire search sequence wrapped up in exactly 89,751 clock cycles.

This zero-jitter timing profile makes the design well-suited for Hard Real-Time Systems, where guaranteed bounded latency and strict execution deadlines are mandatory.

Future Scope & Horizontal Scalability

The structural decoupling of the oscillator clusters opens up avenues for further hardware optimizations:

• Minimizing CHECK_PERIOD: The current FSM requires 11 cycles for processing. By implementing an interleaving pipelining technique (overlapping active check windows), this constraint can be squeezed down to 8 cycles, yielding an immediate latency reduction of ~27%.
• Wheel Factorization: The master step counter increases monotonically by 1 at every iteration (counter + 1). Upgrading the input controller to bypass multiples of 2 and 3 would filter out 66% of candidate numbers, accelerating the prime discovery speed by roughly $3\times$.
• Block RAM (BRAM) Migration: For larger scales (e.g., P > 10,000), the internal counters and primes arrays can be mapped directly onto the embedded M9K memory blocks of the FPGA instead of relying on discrete logic registers. The serial slot scanning mechanism (driven by the slot index) matches the dual-port access pattern of BRAM blocks, minimizing Logic Element consumption.

Advantages & Disadvantages

Advantages

• O(1) Verification Per Step: The combinational OR gate reduction tree responds in constant time per candidate number, entirely independent of the bit-width of n or the volume of active oscillators. This combinational response is determined by the propagation delay of the pipelined OR-reduction tree. For any fixed configuration of P active oscillators, this evaluation delay requires a strict, constant number of clock cycles per candidate number, eliminating time fluctuations and ensuring a deterministic O(1) scheduling profile per step.
• Zero RAM Dependencies: The design eliminates large memory lookup arrays to track composite numbers, storing the current state completely within the flip-flops of the distributed oscillators.
• High Parallelism: The oscillator clusters run concurrently and autonomously, eliminating sequential data dependencies between modules.
• Deterministic Timing: The exact execution runtime can be predicted prior to runtime using the expression 11 * (pP - 2) + 2.
• Horizontal Scalability: The modular architecture can be expanded externally by daisy-chaining multiple physical FPGAs together.

Disadvantages

• Hard Resource Ceiling: The maximum number of discoverable primes P is physically capped by the available logic elements of the targeted silicon device.
• Linear Time Dependency: The overall search execution scales as O(pP), bound to the value of the final prime found rather than the total count P.
• Linear Resource Scaling: Each oscillator cluster demands a fixed footprint of Logic Elements, making BRAM or SRL32 migration necessary for massive scales.
• Simulation Overhead: Simulating large values of $P$ can slow down software-based simulators due to the massive volume of parallel processes running concurrently.

Future Work & Benchmarking

In an upcoming article, we will provide a comprehensive comparative analysis benchmarking our Cluster-Oscillator design against the three dominant hardware architectures found in literature: Hardware Trial Division implementations, Block RAM (BRAM) Based Sieves, and the current State-of-the-Art (SOTA) Pipelined Systolic Array implementations. Special focus will be given to mapping the distinct architectural tradeoffs between our constant-time O(1) evaluation loop and the high-frequency boundaries of systolic arrays in terms of throughput, scalability, and resource utilization on silicon.

Source Code Implementation

Below is the complete VHDL source code. The project is split into two modules: oscillators_cluster.vhd (implementing the 8 time-multiplexed oscillators per cluster) and primes_finder.vhd (housing the master control logic, pipeline stages, and the primary state machine).

The generics are pre-configured to look for P = 1024 primes with a bus bit-width of N_BITS = 13. Since the 1024th prime number is 8161, a 13-bit width perfectly accommodates the range (2^12 < 8161 < 2^13).

VHDL Component: oscillators_cluster.vhd

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.NUMERIC_STD.ALL;

entity oscillators_cluster is
    generic (
        BIT_WIDTH    : integer := 10
    );
    port (
        clk          : in  std_logic;
        reset        : in  std_logic;
        run_en       : in  std_logic;
        load_en      : in  std_logic;
        load_slot    : in  std_logic_vector(2 downto 0);
        load_val     : in  std_logic_vector(BIT_WIDTH-1 downto 0);
        coincidence  : out std_logic
    );
end oscillators_cluster;

architecture Behavioral of oscillators_cluster is

    type count_array is array (0 to 7) of unsigned(BIT_WIDTH-1 downto 0);

    signal counters    : count_array := (others => to_unsigned(2, BIT_WIDTH));
    signal primes     : count_array := (others => to_unsigned(2, BIT_WIDTH));
    signal slot : unsigned(2 downto 0) := (others => '0');
    signal slot_delayed : integer range 0 to 7 := 0;
    signal pipe_counter : unsigned(BIT_WIDTH-1 downto 0) := to_unsigned(2, BIT_WIDTH);
    signal pipe_prime   : unsigned(BIT_WIDTH-1 downto 0) := to_unsigned(2, BIT_WIDTH);
 
begin

    process(clk)
        variable load_slot_idx    : integer;
    begin
        if rising_edge(clk) then
            if reset = '1' then
                 slot         <= (others => '0');
                 slot_delayed <= 0;
                 pipe_counter <= to_unsigned(2, BIT_WIDTH);
                 pipe_prime   <= to_unsigned(2, BIT_WIDTH);
                 coincidence  <= '0';
            else
                load_slot_idx    := to_integer(unsigned(load_slot));

                if run_en = '1' then
                    if slot_delayed = 0 then
                        if pipe_counter = 1 then
                            counters(slot_delayed) <= pipe_prime;
                            coincidence <= '1';
                        else
                            counters(slot_delayed) <= pipe_counter - 1;
                            coincidence <= '0'; -- Clear on new frame boundary
                        end if;
                    else
                        if pipe_counter = 1 then
                            counters(slot_delayed) <= pipe_prime;
                            coincidence <= '1';
                        else
                            counters(slot_delayed) <= pipe_counter - 1;
                        end if;
                    end if;

                    pipe_counter <= counters(to_integer(slot));
                    pipe_prime   <= primes(to_integer(slot));
                    slot_delayed <= to_integer(slot); -- Cache slot index for the following cycle
                    slot <= slot + 1;
                  
                end if;

                if load_en = '1' then
                    primes(load_slot_idx) <= unsigned(load_val);
                    counters(load_slot_idx)     <= unsigned(load_val);
                end if;

            end if;
        end if;
    end process;

end Behavioral;

Master Controller: primes_finder.vhd

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity primes_finder is
    generic (
        P      : integer := 1024;
        N_BITS : integer := 13
    );
    port (
        clk         : in  std_logic;
        rst         : in  std_logic;
        counter_out : out unsigned(N_BITS-1 downto 0);
        prime_out   : out unsigned(N_BITS-1 downto 0);
        done_out        : out std_logic
    );
end entity primes_finder;

architecture rtl of primes_finder is

    constant CHECK_PERIOD : integer := 11;
    constant NUM_CLUSTERS : integer := (P + 7) / 8;
    constant NUM_GROUPS   : integer := (NUM_CLUSTERS + 7) / 8;

    signal counter                    : unsigned(N_BITS-1 downto 0) := (others => '0');
    signal timer                    : integer range 0 to CHECK_PERIOD := 0; 
    signal primes_count             : integer range 0 to P := 0;
    signal prime_found              : unsigned(N_BITS-1 downto 0);
    signal any_lap               : std_logic; 
    signal state_initialized     : std_logic := '0';
    signal done                     : std_logic := '0'; 
            
    signal run_en                : std_logic;
    signal load_en_all        : std_logic := '0';
    signal load_en_vector    : std_logic_vector(NUM_CLUSTERS-1 downto 0) := (others => '0');
    signal load_slot            : std_logic_vector(2 downto 0);
    signal load_val            : std_logic_vector(N_BITS-1 downto 0);

    signal all_coincidences  : std_logic_vector(NUM_CLUSTERS - 1 downto 0) := (others => '0');
    
    type group_regs_t is array (0 to NUM_GROUPS - 1) of std_logic_vector(7 downto 0);
    signal reg_groups : group_regs_t := (others => (others => '0'));
    signal groups_has_lap : std_logic_vector(NUM_GROUPS - 1 downto 0) := (others => '0');
     
    type state_t is (RUNNING, FINISHED);
    signal state : state_t := RUNNING;
 
begin 

    counter_out    <= counter;
    prime_out        <= prime_found;
    done_out        <= done;

    run_en <= '1' when (state = RUNNING and timer < 8) else '0';

    GEN_CLUSTERS: for i in 0 to NUM_CLUSTERS - 1 generate
        cluster_inst : entity work.oscillators_cluster
            generic map (
                BIT_WIDTH => N_BITS
            )
            port map (
                clk          => clk,
                reset        => rst,
                run_en       => run_en,
                load_en      => load_en_vector(i),
                load_slot    => load_slot,
                load_val     => load_val,
                coincidence  => all_coincidences(i)
            );
    end generate;
 
    process(clk, rst)
    begin
        if rst = '1' then
            reg_groups <= (others => (others => '0'));

        elsif rising_edge(clk) then
            reg_groups <= (others => (others => '0'));
            for i in 0 to NUM_CLUSTERS - 1 loop
                reg_groups(i / 8)(i rem 8) <= all_coincidences(i);
            end loop;
        end if;
    end process;

    GEN_GROUP_DETECTORS: for g in 0 to NUM_GROUPS - 1 generate
        groups_has_lap(g) <= '1' when reg_groups(g) /= "00000000" else '0';
    end generate;

    any_lap <= '0' when groups_has_lap = (groups_has_lap'range => '0') else '1';
     
    process(clk, rst)
    begin
        if rst = '1' then
            counter           <= to_unsigned(2, N_BITS); 
            prime_found       <= to_unsigned(2, N_BITS);
            primes_count      <= 1;         
            done                    <= '0';
            timer             <= 0;
            load_en_vector    <= (others => '0');
            state             <= RUNNING;

        elsif rising_edge(clk) then
            load_en_vector <= (others => '0');
          
            case state is
                when RUNNING =>
             
                    if timer = 0 then
                        if done /= '1' then
                              counter <= counter + 1;
                        end if;
                    end if;
             
                    if timer = CHECK_PERIOD - 1 then
                        if any_lap = '0' then
                         
                            prime_found  <= counter;
                            primes_count <= primes_count + 1;

                            load_en_vector(primes_count / 8) <= '1'; 
                            load_slot <= std_logic_vector(to_unsigned(primes_count rem 8, 3));
                            load_val  <= std_logic_vector(counter);

                            if (primes_count + 1 >= P) then
                                done  <= '1';
                                state <= FINISHED;
                            end if;
                        end if;
                        
                        timer <= 0;
                    else
                        timer <= timer + 1;
                    end if;

                when FINISHED =>
                    null;
                end case;
            end if;
    end process;

end architecture rtl;

Open Science

In accordance with open-source models and the free dissemination of scientific knowledge, the entire project is open and available to the community:

• Read the Preprint Paper on Zenodo: DOI: 10.5281/zenodo.20622711
• Download Source Files and Testbenches on GitHub: GitHub Repository

This contribution marks the first functional hardware deployment of the Cyclic Prime Emergence Algorithm. The VHDL architecture is entirely generic and open for community-driven experimentation—whether running on standard simulators or deployed directly onto hardware boards. Every new prime generated by the core acts as a persistent empirical validation of the underlying theory.

I look forward to hearing your thoughts, optimization ideas for the structural VHDL implementation, or details about your own testbench simulation runs.