infmachine

InfMachine

This is library provide the execution environment for the Infinite machine. Execution environment allow to run machines at CPU and GPU using an OpenCL devices. A machine executed in parallel way and massive processors of that machines are executed parallel way. It possible to run machines with multiple millions processors simultaneously thanks limited states and memories of that processors.

The library uses gatesim library to operate on machine's circuits. The library uses gatenative library to run machine and simulate circuit execution of that machines.

InfMachine model

The Infinite Machine is simple model of infinite machine that has infinite memory and infinite number of processors. Machine described by circuit that has inputs and outputs.

The machine contains main memory. Main memory shared by every processor and it can be read and written by any processor. Main memory address starts from 0 and no end of this memory. Main Memory cell length is power of two.

Next type of memory is mem_address - memory address. Any processor has own private memory address and no other processor can access to this memory address. Memory address is sequential memory with start and no end. Position of memory address points to current part of memory address. Length of part of memory address specified by data part length and it can be any non-zero number. Processor can move position of memory address forward and backward. Memory address points main memory cell of that address that will accessed by processor.

Additional type of memory is temp_buffer - temporary buffer. Temporary buffer is only name of that memory and it means usage of that memory. Any processor has own private temp buffer and no other processor can access to this temp buffer. Same memory is not temporary. Likewise memory address, temp buffer is sequential memory divided by data parts of length specified by data part length and given position can be moved forward and backward as in memory address.

Processor id is private read only memory that contains processor id (private number of processor). It is sequential memory likewise memory address of temp buffer.

Internal data is memory address and temp buffer.

Any read or write from/to memory address or temp buffer can be done to its part of length data part length at current position. Read from memory address or temp buffer done before write to same part of that memory. Position going to be changed after any access to part of internal data.

Three parameters defines machine:

• state length - length of internal state in bits.
• data part length - length of data part of sequential (internal data) memory in bits. For temp_buffer, memory address and processor id.
• cell_len_bits - power of two of length of cell of main memory. cell_len_bits=3, then cell is byte (8 bits).

Execution of machine divided by cycles. Cycle stage in library starts from 0. Cycles divided by four stages:

1. Circuit execution and handling internal data.
   1. Fetch read memory cells to circuit input.
   2. Fetch internal data.
   3. Execute circuit.
   4. Process read/write of internal data.
   5. Process position of internal data.
2. Read memory.
3. Clear memory to write.
4. Write memory and stop machine if needed.

Initial state of machine is all memories and positions are zeroed.

Read from main memory will be done parallel way in stage 2. Write to main memory done in stages 3 and 4. Any cell of main memory going to be cleared before write in stage 3. In stage 4 aggregated write to cell of main memory done by making logical OR operation on bits of cell with all writes from all processors. If any processor writes 1 to some bit same cell of main memory then will be 1 in this bit, otherwise bit will be 0.

For model that includes infinite processors we distinguish unique processing: processor that doing different processing by writing different values to memories and having different states. Number of unique processing for any cycle are finite. Main memory writing is computable because: for bit that not set to 1 no processor that store this bit and no duplicate of processor that do it, for bit that set to 1 any duplicate of processing make same operation. For bit that set 1 it requires to only one processor to set that bit, other processor doesn't change result.

Details of circuits. The circuit of machine describes behavior of machine. Input of circuit is:

[STATE, MEMCELL, DATAPART, DATAPART_MOVE_DONE].

Output of circuit is:

[STATE, MEMCELL, DATAPART, MEMRW, DATAPART_RW, DATAPART_MOVE_DIR, DATA_KIND, STOP_MACHINE].

Descriptin of fields:

• STATE - internal state of processor (circuit). Any length.
• MEMCELL - memory cell value to load or store.
• DATAPART - part of internal data loaded or stored from current position of that internal data (temp_buffer of mem_address).
• DATAPART_MOVE_DONE - 1-bit. if 1 then position of part changed.
• DATAPART_RW - 2-bit control of internal data access:
  • 0b00 - nothing,
  • 0b01 - read,
  • 0b10 - write,
  • 0b11 - read and write.
• DATAPART_MOVE_DIR - 2-bit direction of position movement:
  • 0b00 - nothing,
  • 0b01 - move forward,
  • 0b10 - move backward,
  • 0b11 - move backward.
• DATA_KIND - 2-bit kind of internal data:
  • 0b00 - memory address,
  • 0b01 - temporary buffer,
  • 0b10 - id of processor,
  • 0b11 - id of processor.
• STOP_MACHINE - 1-bit. If value is 1 in any processor then machine going to be stopped.

Illegal states

Illegal state means in only executor environment, but not in machine model. Illegal state happens if any processor try write memory above specified size, move position above maximal value, write internal data above maximal size. Any read above specified size or maximal length are legal and causes read zeroes.

Examples and other crates.

Example machines in infmachine_examples. Toolkit to create machines is infmachine_gen. Executor and debugger of machines is infmachine_exec.