Rethinking Computer Science Part 4: A Network Interpreter

Can there exist an approach to universal interpretability that relates directly to the dependency network and which preserves its distributed concurrency?

Uniform flow paths, a universal set of operations and sequencing seems the royal road to universal interpretability. A single memory and single interpreter is, in a sense, a simplest and minimal computation capable of being structured to emulate any other computation.  A structureless tabula rasa that reflects only uniform path structure and a small set of sufficient operations onto the mapping of the network to be interpreted. If the emulating computation contains any element of flow structure such as concurrency, two interpreters or two memories for instance, then the emulating computation ceases to be a structureless receptacle, reflects flow structure onto the mapping and the two structures collide mid mapping in a question with a multitude of answers and a nontrivial coordination issue.

Might there be another road to universal interpretability that does not require sequencing the entire network of oscillations, and which preserves the structure of the network and its concurrent behaviors. While it is difficult to inject concurrency into sequentiality it is straightforward to inject sequentiality into an expression of concurrency which already expresses all the necessary coordination behavior. In particular, the behavior of an individual oscillation can be implemented in any convenient manner including sequential as long as the oscillation performs its computation and the empty/full flow protocol is honored. A computation can be expressed as a flow network of sequential processes.

Each oscillation is represented with a symbolic record that specifies the computation of the oscillation as a sequence of operations and specifies the input paths and the output paths each with its associated closure path and flags indicating empty and full. The records are mapped into a distributed network of memories and interpreters.

The memories and interpreters are decoupled. Several interpreters are associated with each memory and serve the memory in turns as available. Several memories are associated with each interpreter forming overlapping neighborhoods of memory/interpreter associations. Memories are not connected to memories but are connected through interpreters. Interpreters are not connected to interpreters but are connected through memories. Neighboring memories are connected through a single interpreter.

A flow network is loaded record by record through an input memory. The first record is allocated to a memory. Subsequent records flow through it and are allocated and linked to accepting neighboring memories which in turn become conduits for records which are allocated and linked to neighboring memories until the entire flow network is loaded into the network of memories. The loaded flow network weaving through the neighborhoods of memories can fold back through the same memory multiple times. In the limit a network can flow back and forth through a single memory and a single interpreter can service it.

Each grey box below is a separate oscillation record in a separate memory showing the linking flow paths between memories.

Most records are loaded as empty. Some records may contain initial data wavefronts. Data wavefronts are presented to the network inputs, the interpreters begin servicing the records and data wavefronts begin flowing from component record to component record, from memory to memory and interact as they flow. Each independently behaving interpreter polls its connected memories opportunistically searching for an oscillation record to service. Access to each record is arbitrated so that only one interpreter at a time gains access to a record and performs the following protocol.

The interpreter Protocol

ALWAYS poll for memory access{
WHEN gained {
IF ready queue not empty
THEN access record of top entry;
IF input complete
               perform computation;
                   WHEN done{
                      FOR each output path{
                         gain access to memory with destination path oscillation record;
                         deliver output value to path and set flag full;
                         IF oscillation record input is completely full and its output completely empty;                               THEN place oscillation record onto ready queue;
}
                      FOR each input path{
                         mark as empty
                         gain access to memory of source path oscillation record
                         mark as empty
                         IF oscillation record input is completely full and its output completely empty;                               THEN place oscillation record onto ready queue;
}
                  }
            release record
      ELSE idle a bit
   }
}

Full/empty flags emulate the full/empty flow of oscillation links. Each interpreter can manage input ports, can enable acceptance of input, determine when input is complete and perform the program of the oscillation. Computation completeness occurs when an oscillation program has performed the last sequential operation. It then checks that the input ports of the destinations are empty and sends the output to the successor record input ports. When all are accepted it marks the current record’s input to enable the flow of empty which is just a manipulation of flags.

The state of the flow of the network and the state of each oscillation is maintained entirely in the oscillation records. Each interpreter is a stateless server that, with each access, updates a record, performs any housekeeping duties and leaves the memory and its oscillation record in a coherent state for a next interpreter to access and update. The arbitrated record access and the inherent flow network coordination behavior insures that processors never interfere with each other and that networks flow independently. As each interpreter performs its local duty alternating wavefronts of data and emptiness flow through the network records realizing successive instances of network computations exploiting the represented concurrency both parallel and pipeline as resources permit. There can be multiple flow networks distributed through the memories proceeding simultaneously and independently. Each memory can host multiple oscillation records of the same or different flow networks without interference.

The interpreters do not communicate among themselves. No interpreter is more important than any other interpreter. There is no central controller or explicit scheduler. There is no time referent. The network flows in its own time. There is no encompassing state. The state of each instance of a computation is in the wavefronts of data values flowing through the network and maintained in the records. Within the network, no part is greater than any other part. There is no central anything. There is no global anything. The network is a behaving whole composed of behaving localities enlivened by the servicing interpreters.

The operating system is itself a flow network distributed through the memories with one or more oscillation records in each memory. The OS flow network is enlivened by processors servicing its components just like any other flow network with its state maintained in the records themselves. Interpreters remain independent and stateless in relation to the OS.

Oscillation records can migrate among memories as long as the record state and links are maintained. A memory can be emptied and removed. A newly added memory can begin receiving oscillation records. An idle interpreter is stateless and can be removed. A newly added processor just begins looking for opportunities to service. The interpreters can keep tabs on each other by periodic conversation through the OS flow network. Rogue interpreters can be isolated, slow interpreters identified. Interpreters and memories can negotiate among themselves through the OS network to balance application load, optimize application throughput, flow to special purpose resources and so on.

The flow networks can reconfigure in relation to the memory/processor network. The memory/processor network can reconfigure in relation to the flow networks. The memory/interpreter network can be monitored with redundant flow or with periodic sets of test values or with a test flow network that continually flows test cases through the network. The interpreters treat it as just another network to service.

The memory/processor network exploits the inherent concurrency of independent flow networks and of concurrency within each flow network as resources are capable. Resources can be indefinitely extended simply by adding memories and processors. As resources dwindle the system will continue working with a single memory and a single processor.

Summary
While the behavior of each oscillation is sequentialized the flow network of oscillations is interpreted directly in the network of distributed memories and interpreters realizing the flow network in its native structure and behavior.

2 thoughts on “Rethinking Computer Science Part 4: A Network Interpreter

  1. Could you please help me understand your ideas with an example. What would a concrete record look like and what would a flow network for a simple problem look like?

    1. Hi Nicolas

      There have not been any records actually created yet and I don’t have an architecture emulator yet. The circuit examples in the sandbox are networks of oscillations and can serve as first order examples that could be interpreted by the architecture. A record is the sequential program for the logic of the oscillation, pointers to records in neighboring memories and the empty/full flags associated with each pointer. It will be some time before an architecture emulator is available. Perhaps you could help if you are so inclined.

Leave a Reply