Tag Archives: computation model

Unifying Hardware and Software

Matt Whiteside 8,9,2017
Unifying Hardware and Software

Q: Regarding a language that “unifies hardware and software, uniformly characterizing computation through all levels of abstraction” is an attractive idea that’s also crossed my mind, but I don’t see it getting much appreciation by programmers.  To give a concrete example from my own experience of a deficiency that a unified approach would address, consider GPU programming.  You start with a nice high level, type-safe, statically analyzed language running on the CPU, which must then interface with a shader program on the GPU, and therefore throw all the type safety, static analysis, correctness guarantees, etc., out the proverbial window.  It’s hard even to imagine what possibilities could open up if even a moderate amount of progress was made towards improving this situation.

A: The unification. I see both ends doing the same computation. The processor sequences operations, the clock sequences operations. EEs actually talk about the massive concurrency at the circuit level. They don’t seem realize that they throw 99.9% of the concurrency away to actually sequence one or a few steps. They are mildly aware of inefficiency in that they include clock gating but buried in transistor details they are not sensitive to what they are doing in the context of computation. This is one of the thrusts of what I am pursuing. What is the fundamental nature of computation and its most primitive implementation consistent with that nature and how does this implementation seamlessly scale to arbitrary complexity. This is the question that CSR began addressing and which I am still working on. Computation should be uniformly characterizable in all its manifestations. It seems to me that this uniform characterization must embody concurrency as fundamental and that the notion of the sequential process is a fundamental flaw in contemporary computer science. The traditional notion that any concurrent process can be mapped to a sequential process implying that sequentiality is more fundamental than concurrency is a red herring similar to the notion that planetary motions can be mapped into uniform motion around perfect circles. Both are true enough and they both sort of work and because of that they mask access to a more effective conceptual essence.

My thesis is that the model of networks of linked oscillations spans both primitive implementation and abstract interpretation unifying both domains. Part 4 will present the flow network interpreter architecture. The view of computation is modified for both domains but then they are unified.

Rethinking Computer Science Part 4: A Network Interpreter

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, 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.

Rethinking Computer Science Part 2: A Sufficiently Expressive Logic

Part 2 presents a logical foundation for computation that does not exhibit the difficulties discussed in part 1.

A Sufficiently Expressive Logic
Consider the possibilities of a logic that manages its own flow of concurrent computation, that does not exhibit incorrect behavior, that  determines its own completeness of resolution and that stably maintains its flowing data. A logic that is sufficiently expressive to completely determine the behavior of any computation solely in terms of the logic itself. No time interval. No registers. No state machine. No timing closure. No emulated mathematician. Might we accept such a logic as a foundation of computational expression and its logically determined behavior as a foundation of computational confidence?

Such a logic is defined by introducing the notion of emptiness to variables and the notion of completeness and value holding to operators on variables.

Variable Emptiness
The current computer science notion of a variable is as a container of a data value that always contains and always asserts a data value. The contained data value can change but the container, the variable, persists and is never empty. The validity or invalidity of a variable’s data value is determined by some control behavior apart from the variable.

A value is added to the variable’s value set that explicitly means “not a data value” which will be called empty. A variable can now explicitly indicate that it does not contain a data value, that it is “empty”. A computation begins when a data value flows into an empty variable and ends when an empty value flows into the variable.

Operator Completeness and Emptiness
A computation primitive operator must now relate to this new “not data value” and the fullness and emptiness of its variables. So the notion of completeness and value holding behavior is introduced.

Each operator fulfills a completeness criterion. Only when its input variables are completely data will an operator transition its output variable to a data value that is the correct resolution of the presented input values. Only when its input variables are completely empty will an operator transition its output value to empty. For all conditions of mixed data/empty input an operator will maintain its current output value.

The output of an operator transitioning to data implies that its input is completely data and that its output is the correct resolution of the presented input. The output of an operator transitioning to empty implies that its input is completely empty and that it is ready to receive a next data input.

If the input variables to an operator monotonically transition between data completeness and completely empty then the output variable of the operator will monotonically transition between data and empty fulfilling the completeness criterion.

Each operator exhibits completeness behavior (control), value holding behavior (memory) and transformation behavior (data value transition mapping). An operator is still represented as a mapping but now the mapping includes the empty value and there are mappings for which the output does not transition.

A Dual Threshold Logic
Considering electronic implementation, the two electronic values that a wire/rail can assert are designated as logical values data (non-zero voltage) and empty (zero voltage) in contrast to 0 and 1 or True and False. Since there is only one data value there cannot be combinations of different data values presented to an operator, there can only be quantities of the one data value. Therefore the operator data completeness criterion is a quantity of inputs transitioned to data: a threshold operator.

The new operator is a dual threshold behavior with an input data completeness threshold and an input completely empty threshold. A dual threshold operator beginning with its output empty will transition its output to data when a specific number of its input rails transition to data fulfilling the data completeness threshold. It will maintain its output data value until all of its input rails transition to empty at which point it will transition its output to empty. It will then maintain its output empty value until its input rails transition to data completeness at which point it will transition it output to data … and so on.

Some dual threshold operators are represented graphically below with their mapping tables in which a dash represents no transition. The number in the graphic is the data completeness threshold. The input rails indicate the number of inputs. A branched rail indicates a weighted input.

Monotonic Value Completeness Transitioning
If the input rails to a dual threshold operator monotonically transition between data completeness and completely empty with an appropriate delay between transitions then the output rail of the dual threshold operator will monotonically transition between data and empty.

Multi-Rail Variable Representation
The mutually exclusive values of a variable are represented with multiple rails each representing one value which is asserted when its rail is data. It is illegal for more than one rail to transition to data at a time. When all rails are empty the variable is empty. A variable monotonically transitions between data completeness (one rail at data) and empty (all rails at empty). Below are examples of multi-rail variables.

Combinational Logic
Multi-rail variable interactions can be characterized as combinations of rails (values) transitioning to data each of which combination can be recognized by a dual threshold operator.A universal mapping can be assummed for the transition to empty (transition outputs to empty only when all inputs are empty) so a combinational network of dual threshold operator can be specified as a transition table of data value (rail) interactions

The combinational network below, specified by the table at its left, adds a binary variable to a trinary variable producing a quaternary variable. Computation begins with the input variables and the output variable and the operators empty (all rails empty). When the trinary and the binary variables transition from empty to data completeness only one dual threshold operator in the first rank will meet its data completeness threshold and transition its output to data ultimately transitioning the quaternary output variable to data completeness (one rail data) indicating that the input variables are data complete and that the quaternary value is the correct resolution of the presented input.

When the input variables transition to empty, the dual threshold operator in the first rank that had transitioned to data will transition its output to empty, emptying the output quaternary variable. The input and output variables and the operator are again empty (all rails empty) and ready to accept a next transition of input variables to data.

If the input variables monotonically transition between data completeness and empty with an appropriate delay between transitions then the dual threshold operators of the network will monotonically transition between data and empty and the output variable will monotonically transition between data and empty. The behavior of the network as a whole including all the concurrency in the network is deterministically coordinated (no glitching) by the monotonic input behavior, by the completeness behavior of individual dual threshold operators and by the logical structure of the network. The combinational network exhibits the same completeness behavior as its component dual threshold operators.

Greater Combinational Composition
In a greater combinational network constructed of first level combinational networks the output of each first level combinational network presents a single correct input transition to its successor first level combinational networks fulfilling their monotonic input requirements.

For each network input transition (to data or to empty) a wavefront of correct monotonic transitions propagates through the greater network. There are no incorrect or spurious transitions. Both concurrent and ordered flow behaviors of the greater network are fully coordinated by the monotonic transition behavior and by the completeness behaviors. The transition completeness of the output variables of the greater network implies that its input variables have completely transitioned and that the output is the correct resolution of the presented input (data complete – completely empty). The requirement for monotonic transitioning with an appropriate delay between transitions is now relegated to the input environment of the greater network.

The network as a whole behaves with the same completeness behavior including the deterministic coordination of all concurrency as its component combinational networks. A composition of logically determined networks is itself logically determined. Completeness behavior scales. A network with fully determined flow behavior emerges atop the network of dual threshold operators.

The Emergent Oscillation – Liveness and Flow Control
Data completeness and emptiness of the output data variables can be recognized with dual threshold operators, fed back to the input, inverted and presented to a spanning rank of dual threshold operators which regulate the input of the network. Output data completeness will allow transitions to empty into the network. Output empty completeness will allow transitions to data into the network. Once a transition wavefront is allowed the enabling rank of dual threshold operators will maintain the allowed wavefront until the network detects the completeness of its flow and allows the next transition wavefront.

The network self regulates the monotonic transitioning of its input. The input environment still has an imposed requirement for monotonic transitioning but now the network itself determines the appropriate delay between transitions. The input environment must now wait for each input transition wavefront to be allowed into the network.

The network is a closed circuit with delay and a single inverter, the form of a ring oscillator. The closed network continually strives to transition between two states, data and empty, the behavior of a ring oscillator. However the transitioning is not necessarily periodic as is the familiar case with free unencumbered oscillators. The transitioning of these oscillators can be delayed, modulated by signals external to the oscillator. Nevertheless, they continually strive to transition and as long as their transitions are externally allowed they transition alternately between two states, oscillate, however aperiodically. The network fulfills two and a half properties of the conventional view of a ring oscillator so it will be referred to as a ring oscillator in this context.

With the inversion of the completeness feedback the network of dual threshold operators becomes a spontaneously alive ring oscillator(animation) continually striving to monotonically transition between data completeness and completely empty. The oscillation provides liveness. The input enable rank provides memory. The output completeness provides flow control. The encompassed combinational network provides value transformation behavior. It is a spontaneously alive, self regulating computation expressed solely in terms of logical relationships. No time interval. No register. No controller. No timing closure. No mathematician.

 Linked Oscillations: Pipeline Flow Networks
Placing the input regulation logic of one oscillation before the output completeness logic of another oscillation links the two oscillations with a shared completeness behavior coordinating their oscillation behavior. Each oscillation maintains its input and its output and does not oscillate until its output is stably passed to its successor oscillations. As oscillations individually oscillate, alternating wavefronts of data and empty flow from oscillation to oscillation with data wavefronts being transformed as they flow through the combinational logic within each oscillation.

The requirement of monotonic transitioning is now relegated to the input environment of the network of linked oscillations as a whole, and if fulfilled, successive waves of monotonic transitions will flow through the network with full coordination of all concurrent and ordered behaviors realizing a logically determined computation. In the network below, for instance, the flows of the concurrent oscillations A and B are coordinated by the completeness behavior of oscillation C.

In a network of linked oscillations the behaviors of data transformation, memory, flow coordination and liveness are fully integrated and uniformly distributed. No time interval. No registers. No controller. No timing closure. No mathematician. Only logical relationships

Structured Flow Paths and Abstract Components
A flow path can be a structure of multiple multi-rail variables with a spanning enable and spanning completeness as shown below with the 4 bit adder. Stylized operator symbols are introduced that abstractly represent computations with flow paths of any width and structure. The abstract representations can be composed and further abstracted.

The Ring: Memory
A pipeline can feed back on itself forming a ring of oscillations creating a local memory of previous behavior. A network of linked rings produces a computation with memories of previous behavior distributed throughout the network.

In the network below, implementing a state machine, the remembered previous behavior is the transition to the current state which is fed back through D, and presented as input A. The fed back transition wavefront will sit at A and wait indefinitely for a B transition wavefront to arrive and form input completeness at which point the wavefronts will flow through the update computation producing the next state. A and B are concurrent flows coordinated by the completeness behavior of oscillation C.

The state machine, realized as a network of dual threshold operators, is spontaneously alive and self sequencing with no external support except for the presentation of the input.

Self Contained Computation
If the feedback associated with the input controls the transitioning of the input (memory read request or sensor sample request) then the requirement for monotonic transitioning relegated to the input environment of the network is satisfied and is no longer imposed on the input environment. The network becomes self contained, self coordinated and spontaneously alive; independently and continually performing its computation. There is no referent for the network and its behavior other than the network itself. No external controller. No external time referent. No mathematician Within the network there is no part that is greater than any other part. There is no central anything. There is no global anything. It is a spontaneously behaving whole composed of spontaneously behaving parts.

Immersed Computation
If the input sensor is sensitive to the output behavior then an external feedback path around the network is established forming the network as a whole into a ring, part of which is the logical network and part of which is the environment; a self contained, self referential, continually computing network sensitive to its environment and, with memory of previous behavior, capable of adjusting its behavior. It is an integral locality of a larger computation that it does not, itself, encompass and, in turn is composed of localities that do not encompass its wholeness.

Computation Primitives
Variables that can indicate their own validity and invalidity of value, completeness operators that can manage their own behavior in cooperation with the variables, which combine in networks that coordinate their concurrent flow with completeness behavior, which networks close on themselves to create oscillations, which oscillations, linked with completeness behaviors, form pipeline networks, which pipeline networks, closing on themselves, form ring networks which can remember past behavior and which ring networks finally control their own input becoming independently and spontaneously behaving computations. These concepts, all encompassed in a single coherent logic(1) are primitive concepts of computation that are sufficiently expressive on their own behavioral merit, and that can serve computer science better than computation primitives that assume the behavior of a real or emulated mathematician.

Computational Confidence
We trust sequenced state, because, given knowledge of the input and the sequence one can predict the values in the state space between steps, pause the sequence of steps and observe the state values.

Why might we trust spontaneously flowing, concurrent, fully determined logic? Given knowledge of the input and the network structure of linked oscillations one can predict the sequence of values that will flow through and out of of each oscillation The output of selected oscillations can be tapped and the succession of wavefronts observed.

The mechanisms of observation are different but the predictability and observability of computational progress correspond because the structure and behavior of the state space is one of the possible sequences derived from a dependency specification and the network of linked oscillations is a direct realization of the same dependency specification.

But what if the input is random and prediction is not possible? Then confidence must reside in the expression of the computation. A key factor of sequential confidence is the “precisely defined step”. But the behavior of a step containing a Boolean network with its timing anomalies (glitches) and its reliance on external control is determined by human coordination.

An oscillation, the counterpart of step, contains a network of dual threshold logic operators and logical links with other oscillations that fully determine its behavior solely in terms of logical relationships.

Should we trust the behavior of a coherent determinate logic or the behavior of an ad hoc construction of heterogeneous parts coordinated by humans?

Summary
Mathematics is a world of abstract relations. But integral to the meaning and functioning of mathematical abstractions is a mathematician to actualize them and manage their behavior. The task of computer science is to directly actualize abstractions of computation, without the mathematician. But the mathematical abstractions without the mathematician are incomplete and do not behave correctly on their own merits. A boolean equation in the hands of a mathematician provides a single correct answer. A directly instantiated Boolean equation provides incorrect answers because of concurrent behaviors that the mathematician can coordinate but that the directly instantiated Boolean equation cannot.

Computer science has addressed this quandary by managing the unruly concurrent behavior with time and sequence. Isolating the unpredictable concurrent behavior within a time interval transforming a Boolean network, as a whole, into a predictable sequential step. One can then consider the sequential step as a primitive behavior and consider the concurrent behavior within the step as rendered inconsequential. Isolation might be a reasonable approach if the chaos of primitive concurrent behavior were an existential inevitability. But it is not. There is a logic that can manage its primitive concurrent behavior with deterministic predictability

It is a logic that serves as a primitive abstraction of computation specification as well as a primitive abstraction of computation behavior, a logic that does not assume the behavior of a mathematician but that stands on its own expressional and behavioral merits, a logic that models primitive concurrent computation behavior delivering logical determinism rather than logico-temporal-anthropic adequacy, a computer science logic in contrast to a mathematical logic.

Computer science is different from mathematics. While mathematics uses the mathematician for computation computer science strives to transcend the mathematician and, ultimately, to account for the mathematician as itself a computation. The ghost of the mathematician in computer science creates a referential circle that undermines both ambitions.

1. Karl M. Fant, Logically Determined Design: Clockless System Design with NULL Convention Logic, (Hoboken, New Jersey, Wiley Interscience, 2005).