Genny-Graph

Genny-Graph is the instance of ZOTI-Graph used with the Genny syntesis flow of the ZOTI project. As a model it represents applications as graphs of concurrent actors where nodes are hierarchically representing compute components and their mapping whereas each edge represents a type of interaction between the compute components.

As part of the Genny flow, Genny-Graph aims to act as a bridge between (completely solved) system models and their pragmatic implementation on a given (heterogeneous) target platform. In this sense it imposes enough restrictions on the design as to enable hosting behavior semantics as well as it allows custom annotations and “hacks” for aiding towards more efficient implementations. In other words its goal is to enable the use of (upstream) formal models without necesserily crippling the possibility of (downstream) efficient code generation.

To achieve hierarchy each node is considered as being connected to its surroundings via ports, effectively being able to be abstracted as a “black-box” component. By adopting this view a node can be itself cluster of interconnected nodes, as suggested in the figure below.

Drawing of a Genny-graph model

There is enough consistency between the input format schema and the model specification hence we will use the former to document both model and input format.

Notice that there are several types of nodes, as documented in the nodes section below. These nodes cannot be arranged in any arbitrary hierarchy, and there are a set of rules that need to be enforced when describing system models, as described in the Sanity rules section below. Finally, a set of Target-Agnostic Transformations are exported and can be used as reference to create own ones.

Input Schema

ZOTI-Graphs documents are specified as hierarchical tree-like objects where the root is a nodes field containing a list of definitions representing the top-level node(s). From there systems are described in a top-down manner where child nodes are specified within the scope of parent nodes (i.e. under the parent’s nodes field).

A graph is loaded from a list of serialized objects (e.g. in JSON format) using the zoti_graph.parser.parse() method, by passing them to its arguments. The document object from these arguments needs to be defined following the schema below.

nodes

A node is the base entity in ZOTI-Graph. All nodes, regardless of their type, may have the following entries:

name: <str> required

node name. Needs to be unique within the scope of its parent.

kind: <str>

denotes the type of node, see Node Kinds. Default CompositeNode.

description: <str>

free-form text.

mark: <dict>

free-form dictionary, markings passed as-is to graph transformer. Similar to parameters but should become obsolete after the transformation phase and should not be passed to the code generator,

parameters: <dict>

free-form dictionary of parameters passed as-is to the code generator. Similar to mark, but should not be touched during transformation, but rather handed over to the code generator.

nodes: nodes

list of child node entries

ports: ports

list of ports for this node

edges: edges

list of edges connecting children’s ports between them or with their parent (this node’s ports)

Node Kinds

There are several types of nodes, each one denoting a specific part of a system. Depending on type, additional fields can be used to described specific information, as documented below.

CompositeNode

A CompositeNode is simply a cluster of nodes. It does not have any semantics nor any special field and it is mainly used to group sub-systems into (modular) components.

PlatformNode

A PlatformNode denotes a computation platform and is essential for determining the synthesis details. As a general rule, all components under a platform node will be mapped to the same target (e.g. binary, kernel, container or whatever the processing unit of the target platform is defined as) It might have the following special field:

target: <obj> required

information on target platform, passd as-is to the graph processor downstream, e.g. ZOTI-Tran

ActorNode

An ActorNode is a behavioral computation unit, and denotes a (set of) reactions to the stimuli that arrive to its ports. As a modeling element it originates from a model of computation process, whose semantics are translated in terms of its detector.

NOTE: the detector definition is still under development and is likely to change in the future.

An actor node might contain the following special fields:

detector: <obj>

describes a finite state machine (FSM) that determines the behavior of this actor. If none is provided, the default behavior assumes immediate reaction and run-to-completion for every port triger. An FSM is defined using the fields below:

inputs: <list> required

list of port names to which this actor reacts

preproc: <str>

points to a child (kernel) node which acts as the port preprocessor for the inputs mentioned above. If none is mentioned the inputs are used as they are.

states: <list>

list of state names defined for this FSM. By convention the first state in the list is the initial state. If none provided, it assumes the actor has unique state, in which case it acts as a combinational process.

scenarios: <dict>

dictionary associating each state name with a child node implementing its scenario. Can be left empty in case of unique state, in which case all children constitute this actor’s unique scenario.

expr: <dict> required

dictionary associating each state name with a certain reaction described using the fields below:

cond: <str> required

simple arithmetical and logical expression on the inputs which describes the condition that triggers a reaction and a state change

goto: <str>

state name active when the previous condition is fulfilled. Not necessary in case of unique state.

KernelNode

A KernelNode is a leaf computation node, typically representing a function in the target platform language. It might have the following special field:

extern: <str> required

Contains the full source code of the kernel as formatted text.

BasicNode

A BasicNode is a leaf node with a specific function in the target platform. Unlike a KernelNode, it does not carry a native piece of code, and is only relevant during the transformation process where it might trigger a specific refinement. It needs to specify the following special field.

type: <str> required

the primitive type. Possible SYSTEM, marking a connection to the outside world; DROP marks that the connection is dropping the data.

OBS: Since BasicNodes are replaced during transformation, eveything passed to their parameters field will be ignored.

ports

A port is the conduit between a node and an edge and carries various functional and behavioral information relevant to different abstractions. It is defined using the following attributes:

name: <str> required

A unique identifier within the scope of its parent node.

kind: <str> required

The port kind (in, out, side). In and out ports represent event ports triggering connected nodes within the same timeline. Side ports stand for side-effects, and do not trigger their nodes, i.e. connected nodes may be part of different timelines.

port_type: <obj>

Raw dictionary containing behavioral information relevant when generating access glue. If not provided, it should be filled in by a port inference mechanism further down in the processing pipeline (e.g. ZOTI-Tran).

data_type: <obj>

Raw data passed to a type system for generating type glue (e.g. ZOTI-FTN). If not provided, it should be inferred using a port inference mechanism further down in the processing pipeline (e.g., ZOTI-Tran)

edges

An edge connects two node ports and represents a data communication medium. It can be described using the fields below:

edge_type: <obj>

raw dictionary containing information about the transmission medium relevant for generating glue code for it. It is passed as-is to the tools downstream.

connect: <list>

a 4-tuple containing information about the edge connection:

1. <path> to node where the edge originates, relative to this edge’s parent node.

2. name of port belonging to the source node. If the source is a primitive node then this place is declared none.

3. <path> to node where the edge is destined, relative to this edge’s parent node.

4. name of port belonging to the destination node. If the destination is a primitive node then this place is declared none.

Model Parser

The previous schema can describe a serialization format (e.g. JSON or YAML) that is parsed and validated using the following method exported by zoti_graph.genny.

parse(*module_args) → AppGraph

Parses a complete (schema-validated) Genny-Graph input specification tree along with its metadata and returns an application graph that can be futher process by a ZOTI tool.

module_args is a list of arguments passed to zoti_yaml.Module constructor (e.g., as loaded from a JSON or YAML file) and should consist at least of a preamble and a document. The preamble argument is expected to have a field main-is containing the path to the top (i.e. root) node.

ATTENTION: the design of this library assumes that this function is invoked only once per program instance. If for any reason you need to call it twice, any previously parsed application graph will be reset, so make sure you use deepcopy in case you need to keep more application graphs in the same program instance.

Sanity rules

After parsing and creating an application graph, a set of sanity rules need to be enforced. Genny-Graph comes with a set of generic callable assertion functions (using the zoti_graph.appgraph.AppGraph.sanity() driver). Depending on the use case or on the target platform additional sanity rules might need to be defined and enforced, or skipped, this is why it is up to the synthesis flow designer to call these rules individually. In general it is worth noting that:

• the top node of a project is a CompositeNode and all its children need to be PlatformNode. This means that no function nor behavior is left “dangling” without being mapped to a specific execution platform.

• similar to the previous rule, it makes no sense to speak of a “function” outside the scope of a “behavior”. In other words any KernelNode needs to (eventually) be part of an ActorNode which determines the context in which and the mechanisms with which a certain (native) function is being executed.”

The following sanity rules are currently defined by Genny-Graph. They are not re-exported by the Genny main module, so they need to be imported explicitly from zoti_graph.genny.sanity.

edge_direction(G, u, v)

Edge direction should be consistent with the hierarchy of its connecting elements.

forall u,v in edges(G)

u is basic and v is not basic ⇒ v.kind ∈ {IN}

v is basic and u is not basic ⇒ u.kind ∈ {OUT}

node(u) and node(v) are siblings ⇒ u.dir ∈ {OUT, SIDE} & v.dir ∈ {IN, SIDE}

node(u) is parent for node(v) ⇒ u.dir = v.dir ∈ {IN, INOUT}

node(u) is child for node(v) ⇒ u.dir = v.dir ∈ {OUT, INOUT}

edge_hierarchy(G, u, v)

Edges can only connect sibling nodes or child nodes to their parents.

forall u,v in edges(G)

node(u) and node(v) have different parents ⇒ node(u) = node(v).parent ⊻ node(v) = node(u).parent

edge_sibling_kind(G, u, v)

Interconnected sibling nodes (except intrinsics and ignoring the hierarchy of composites) are of the same kind.

forall u,v in edges(G) where node(u), node(v) are not intrinsic

node(u) and node(v) have same parent ⇒ flatten(node(u)) ⋃ flatten(node(v)) are all of the same kind

node_consistent_tree(G, n)

All nodes except for the root node have only one parent.

forall n in nodes(G) - root(G):

⇒ len(n.parents) = 1

node_platform_hierarchy(G, n)

Ignoring the hierarchy of composites all platform nodes contain only actor nodes.

forall n in nodes(G) where n is platform node:

⇒ n.parent is composite node

⇒ all first children which are not composite are only intrinsic or actor nodes

node_actor_hierarchy(G, n)

Ignoring the hierarchy of composites, all actor nodes belong to a platform node and contain only kernel nodes.

forall n in nodes(G) where n is actor node:

⇒ the first parent which is not composite is platform node

⇒ all first children which are not composite are only intrinsic or kernel nodes

node_kernel_hierarchy(G, n)

Ignoring the hierarchy of composites, all kernel nodes belong to an actor node.

forall n in nodes(G) where n is kernel node:

⇒ the immediate parent which is not composite is actor node

⇒ no child nodes exist

port_dangling(G, p)

‘Dangling port’ means either an event port which is not connected (is triggered by nothing or triggers nothing) or a side-effect port which is not exposed at the actor level (that might be ignored).

Target-Agnostic Transformations

These functions need to be explicitly imported from zoti_graph.genny.translib.

flatten(G: AppGraph, **kwargs)

This transformation flattens any composite nodes rendering a system description made of only basic nodes: platforms, actors and kernels. The only exception to this rule is actor scenarios which are kept clustered as composites for further processing. After this transformation the following holds:

forall n in nodes(G):

n.parent is platform node ⇒ n is actor node

n.parent is actor node ⇒ n is kernel node or composite node marked “scenario”

n.parent is composite node ⇒ n is kernel node (i.e., belongs to a scenario)

NOTE: node IDs remain unchanged, regardless of the new hierarchy.

fuse_actors(G: AppGraph, flatten, **kwargs)

This transformation fuses all inter-dependent actors within the same timeline. After this transformation there will be no EVENT-like dependency between any two actors belonging to the same platform node, i.e., the following holds:

foreach a, b in p, where p is platform node in nodes(G):

there exists e in edges(G) such that e.src = a and e.dst = b => e.kind = STORAGE

=> (inputs(a) in p) is disjoint from (inputs(b) in p)

TODO: fuse FSMs

Core Container Types

Each graph element in a Genny-Graph is associated with a container entry used for storing information that can be used during various stages of model transformations.

These classes are re-exported by zoti_graph.genny.translib

class Dir

Bases: Flag

Values = {NONE, IN, OUT, SIDE}

Bitwise flags denoting port directions.

class Port(name, kind, port_type={}, data_type={}, mark={}, _info={}, **kwargs)

Container for port entry.

kind: Dir

port_type: Dict

data_type: Dict

is_event()

is_side()

has_dir_in()

has_dir_out()

class Edge(edge_type, mark, _info, **kwargs)

Container for edge entry.

edge_type: Dict

class CompositeNode(name, parameters={}, mark={}, _info={}, **kwargs)

Container for composite node entry

class SkeletonNode(name, type, parameters={}, mark={}, _info={}, **kwargs)

Container for a skeleton node entry

type: str

class PlatformNode(name, target, parameters={}, mark={}, _info={}, **kwargs)

Container for platform node entry

target: Dict

class ActorNode(name, parameters={}, mark={}, detector=None, _info={}, **kwargs)

Container for actor node entry

class FSM(inputs: List[str], expr: Dict[str, Dict], preproc: str | None = None, states: List[str] | None = None, scenarios: Dict[str, str] | None = None)

inputs: List[str]

expr: Dict[str, Dict]

preproc: str | None = None

states: List[str] | None = None

scenarios: Dict[str, str] | None = None

detector: FSM | None

class KernelNode(name, extern='', parameters={}, mark={}, _info={}, **kwargs)

Container for kernel node entry

extern: str

class BasicNode(name, type, parameters={}, mark={}, _info={}, **kwargs)

Container for primitive node entry

type: str