Internet-Based Micro-Electronic Design Automation (IMEDA) Framework:Formal Representation of Design Process
Formal Representation of Design Process
IMEDA uses a methodology specification based on a process flow graphs and process grammars (Baldwin, 1995). The grammar is an extension of graph grammar originally proposed by Ehrig (1979) and has been applied to interconnection network (Derk, 1998) and software engineering (Heiman, 1997).
A process flow graph depicts tasks, data, and the relationships among them, describing the sequence of tasks for an activity. Three basic symbols are used to represent a process flow graph. Oval nodes represent Logical Tasks, two-concentric oval nodes represent Atomic Tasks, rectangular nodes represent Data Specifications and diamond nodes represent Selectors. A task that can be decomposed into subtasks is called logical. Logical task nodes represent abstract tasks that could be done with several different tools or tool combinations. A task that cannot be decomposed is atomic. An atomic task node, commonly called a tool invocation, represents a run of an application program.
A selector is a task node that selects data or parameter. Data specifications are design data, where the output specification produced by a task can be consumed by another task as an input specification. Each data specification node, identified by a rectangle, is labeled with a data specification type. Using the graphical elements of the flow graph, engineers can create a process flow in a top-down fashion. These elements can be combined into a process flow graph using directed arcs. The result is a bipartite acyclic directed graph that identifies clearly the task and data flow relationships among the tasks in a design activity. The set of edges indicates those data specifications used and produced by each task. Each specification must have at most one incoming edge. Data specifications with no incoming edges are inputs of the design exercise. T(G), S(G), and E(G) are the sets of task nodes, specification nodes, and edges of graph G, respectively. Figure 75.4 shows a process flow graph that describes a possible rapid prototyping design process, in which a state diagram is transformed into a field-programmable gate array (FPGA) configuration file.
The various specification types form a class hierarchy where each child is a specialization of the parent. There may be several incompatible children. For example, VHDL and Verilog descriptions are both children of simulation models. We utilize these specification types to avoid data format incompatibilities between tools (see Figure 75.5a). Process flow graphs can describe design processes to varying levels of detail. A graph containing many logical nodes abstractly describes what should be done without describ- ing how it should be done (i.e., specifying which tools to use). Conversely, a graph in which all task nodes are atomic completely describes a methodology.
In our prototype, we use the following definitions: In(N) is the set of input nodes of node N: In(N) = {M | (M,N) ∈ E}. Out(N) is the set of output nodes of node N : Out(N) = {M | (N,M) ∈ E}. I(G) is the set of input specifications of graph G : {N ∈ S(G) | In(N) = ∅}.
The designer specifies the overall objectives with the initial graph that lists available input specifications, desired output specifications, and the logical tasks to be performed. By means of process grammars, logical task nodes are replaced by the flows of detailed subtasks and intermediate specifications. The output specification nodes are also replaced by nodes that may have a child specification type.
The productions in a graph grammar permit the replacement of one subgraph by another. A produc- tion in a design process grammar can be expressed formally as a tuple P = (GLHS, GRHS, σin, σout), where GLHS and GRHS are process flow graphs for the left side and the right side of the production, respectively, such that (i) GLHS has one logical task node representing the task to be replaced, (ii) σin is a mapping from the input specifications I (GLHS) to I(GRHS), indicating the relationship between two input specifications (each input specification of I(GRHS) is a subtype of I(GLHS)), and (iii) σout is a mapping from the output specifications of GLHS to output specifications of GRHS indicating the correspondence between them. (each output specification must be mapped to a specification with the same type or a subtype). Figure 75.5 illustrates productions for two tasks, simulate and FPGA partitioning. The mappings are indicated by the numbers beside the specification nodes. Alternative productions may be necessary to handle different input specification types (as in Figure 75.5a), or because they represent different processes- separated by the word “or’’—for performing the abstract task (as in Figure 75.5b).
Let A be the logical task node in GLHS and A′ be a logical task node in the original process flow graph G such that A has the same task label as A′. The production rule P can be applied to A′, which means that A′ can be replaced with GRHS only if each input and output specifications of A′ matches to input and output specifications of GLHS, respectively. If there are several production rules with the same left side flow graph, it implies that there are alternative production rules for the logical task. Formally, the production matches A′ if
(i) A′ has the same task label as A.
(ii) There is a mapping ρin, from In(A) to In(A′), indicating how the inputs should be mapped. For all nodes N ∈In(A), ρin(N) should have the same type as N or a subtype.
(iii) There is a mapping, ρout, from Out(A′) to Out(A), indicating how the outputs should be mapped.
For all nodes N ∈ Out(A′), ρout(N) should have the same type as N or a subtype.
The mappings are used to determine how edges that connected the replaced subgraph to the remainder should be redirected to nodes in the new subgraph. Once a match is found in graph G, the production is applied as follows:
(i) Insert GRHS –I(GRHS) into G. The inputs of the replaced tasks are not replaced.
(ii) For every N in I(GRHS) and edge (N,M) in GRHS, add edge (ρin(σin(N)),M) to G. That is to connect the inputs of A′ to the new task nodes that will use them.
(iii) For every N in Out (A′) and edge (N,M) in G, replace edge (N,M) with edge (σout(ρout(N)),M).
That is to connect the new output nodes to the tasks that will use them.
(iv) Remove A′ and Out (A′) from G, along with all edges incident on them.
Figure 75.6 illustrates a derivation in which the FPGA partitioning task is planned, using a production from Figure 75.5b.
The process grammar provides mechanism of specifying alternative methods for a logical task. A high- level flow graph can then be decomposed into detailed flow graphs by applying production rules to a logical task. A production rule is a substitution that permits the replacement of a logical task node with a flow graph that represents a possible way of performing the task. The concept of applying productions to logical tasks is somewhat analogous to the idea of productions in traditional (i.e., non-graph) gram- mars. In this sense, logical tasks correspond to logical symbols in grammar, and atomic tasks correspond to terminal symbols.
Comments
Post a Comment