Consider the process network in Figure 9-1 with three processes, A, B, and C. The numbers at the inputs and outputs of the processes denote the number of tokens a process consumes and produces at each invocation. Thus, process B reads one token from its input and emits one token to each of its outputs. Process A can emit one, two, three, or four tokens, depending on its state, which is controlled by the command input. In state α the process always emits one token, in state β it emits one token in 99.5% of the invocations and two tokens in 0.5%, in state γ it emits three tokens in 0.5% of its invocations, and in state δ four tokens in 0.5% of invocations. Commands from the command input set the state of the process. If we assume that all processes need equally long for each invocation, a simple analysis reveals that if process A is in state α, the system is in a steady state without the need for internal buffers. On the other hand, when process A is in one of the other states, it produces more tokens than B can consume, and any finite-size buffer between A and B will eventually overflow.

Figure 9-1. Buffer analysis of a process network.

Let us further assume we are dealing with some kind of telecommunication network that receives, transforms, and emits communication packets. State α is the normal mode of operation that is active most of the time. However, occasionally the system is put into a monitoring mode, for instance, to measure the performance of the network and identify broken nodes. Monitoring packets are sent out to measure the time until they arrive at a specific destination node, and to count how many are lost along the way. A monitoring phase runs through the following sequence of states: state β for 1000 tokens, state γ for 1000 tokens, state δ for 1000 tokens, state γ for 1000 tokens, and finally state β for 1000 tokens before state α is resumed again. Even if we introduce a buffer between A and B to handle one monitoring phase, the system would still be instable because the system is running under full load even in state α and cannot reduce the number of packets in the buffer between the monitoring phases. Consequently, a finite-size buffer would still overflow if we run the monitoring phases often enough.

To make the example more interesting and realistic, we also make some assumptions about the traffic and how it is processed. Some of the packets are in fact idle packets, which only keep the nodes synchronized and can be dropped and generated as needed. The packets are represented as integers, and idle packets have the value 0. Processes B and C pass on the packets unchanged, but A processes the packets according to the formula z = (x + y) mod 100, where x and y are input packets and z is the output packet. Consequently, packet values at the output of A are confined to the range 0 ... 99.

To handle the monitoring phases, we introduce a buffer between processes A and B that drops idle packets when they arrive and emits idle packets when the buffer is empty and process B requests packets. What is the required buffer size?

Analysis

Apparently, the answer depends on the characteristics of the input traffic, and in particular how many idle cells there are. Let m be the number of excess packets per normal input packet, introduced by a monitoring process, i is the fraction of idle packets, and N is the total number of input packets in the period we consider. In the first step of the monitoring phase, where process A is in state β, we have

The number of packets we have to buffer is the number of excess packets, introduced by the monitoring activity, minus the number of idle packets:

Equation 9.1. 

We need the max function because B may never become negative; that is, the number of buffered packets cannot be less than 0. For the entire monitoring phase we get

	m	N
state β	0.005	2000
state γ	0.01	2000
state δ	0.015	1000

If we assume a uniform distribution of input packet types, only 1% of the input packets are idle packets, and according to (9.1) we get

B	=	max(0, 0.005 − 0.01) · 1000 + max(0, 0.01 − 0.01) · 1000
		+ max(0, 0.015 − 0.01) · 1000 + max(0, 0.01 − 0.01) · 1000
		+ max(0, 0.005 − 0.01) · 1000
	=	5

Only state δ seems to require buffering, and a buffer of size 5 would suffice to avoid a loss of packets. However, (9.1) assumes that the excess and idle packets are evenly distributed over the considered period of N packets. This is not correct; excess packets come in bursts of 1, 2, or 3 at a time, rather than 0.005 at a time. Thus, even in state β the buffer has to be prepared to handle the bursts, until consecutive idle packets allow the buffer to empty again. Consequently, we modify (9.1) to take bursts into account, with b denoting the longest expected bursts of excess packets:

Equation 9.2. 

For the entire monitoring phase we get

B	=	max(0, 0.005 – 0.01) · 1000 + 1 + max(0, 0.01 – 0.01) · 1000 + 2
		+ max(0, 0.015 – 0.01) · 1000 + 3 + max(0, 0.01 – 0.01) · 1000 + 2
		+ max(0, 0.005 – 0.01) · 1000 + 1
	=	14

We are quite conservative now in assuming that the effects from bursts accumulate over the entire period. But it is more likely that at the end of a phase, say, state β, the buffer is empty although it was not during the entire phase of state β. We could try to be more accurate in taking this effect into account by distinguishing the different phases. Let P be all the phases we are looking at and m_p, i_p, N_p, b_p the respective values of phase p ∊ P.

Equation 9.3. 

Equation 9.4. 

The assumption seems to be very conservative and unrealistic because it assumes a network load of 99%. However, we have to bear in mind that we investigate the worst-case scenario, and we can conclude that with a buffer size of 8 we will not lose packets up to a network load of 99%; only above this figure will we start to lose packets. This is in fact a reasonable objective for a highly reliable network.

Simulation

In our analysis we have two potential sources of errors. First, there could be a flaw in our mathematical model. We have refined it several times, but perhaps we have not found all the subtleties or maybe we just made simple mistakes in writing down the formulas. Second, we made assumptions about the system and its environment, which must be tested. In particular, we assumed 1% idle packets in the incoming packet stream. Even if this is correct for the system input, it might not be a correct assumption for the input of the buffer we are discussing. The stream is in fact modified in a quite complex way. Process A merges the primary input packets with packets from a feedback loop inside the system. Even though processes B and C do not modify the packets, they delayed the packets on this loop by an amount of time that depends on the state of the buffer, if we ignore the time for processing and communicating the packets for the moment. This is a nonlinear process. Although we might be able to tackle our example with more sophisticated mathematical machinery (see, for instance, Cassandras 1993), in general we will find many nonlinear systems that are not tractable by an analysis aiming at deriving closed formulas. In fact, simulation is our only general-purpose tool, which may help us further in the analysis of systems of arbitrary conceptual complexity. The limits of simulation come from the size of the system and from the size of the input space.

In order to test the assumptions and to validate our model (9.3) and result (9.4), we develop a simulation model based on the untimed model of computation.

We choose untimed process networks because intuitively it fits best to our problem. It is only concerned with sequences of tokens without considering their exact timing. By selecting the relative activation rate of the processes, it should be straightforward to identify the buffer requirements. A discrete event system seems to be overly complicated because it forces us to determine the time instance for each token. A synchronous model seems to be inappropriate too because it binds the processes very tightly together, which seems to contradict our intention of investigating what happens in between processes A and B when they operate independently of each other.

We implement the processes of Figure 9-1 as untimed processes and introduce an additional process Buf. We make our model precise by using the generic process constructors (see Figures 9-2 and 9-3).

Process A is composed of three processes (A₁, A₂, and A₃), and the provided functions define how the processes act in each firing cycle. A₁ has a state consisting of two components: a counter counting from 0 through 199, and a state variable remembering the last command. Whenever the counter is 0, a 1, 2, 3, or 4 is emitted depending on the state variable; otherwise a 1 is emitted. This output is used by A₃ and function f_ctrl. Depending on this value, A₃, emits 1, 2, 3, or 4 copies of its input to its output. Process A₂ merges the input streams x and z₄ by means of function f_merge.

A few remarks are in order. Because an untimed model does not allow us to check for the presence or absence of an input value, we model the cmnd input as a stream of values with a specific value, NoUpdate, if nothing changes. This is a rather unnatural way to model control signals with rare events.

The same property of the untimed model causes some trouble for the buffer process. Process A can emit 1, 2, or any number of tokens during one activation. But Buf has to know in advance how many tokens it wants to read. If it tries to read two tokens, but only one is available, it will block and wait for the second. During this time it cannot serve requests from B. We can rectify this by bundling a number of packets into a single token between A and Buf. Buf always reads exactly one token, which may contain 1, 2, 3, or 4 packets. Consequently, in Figure 9-2 function f_ctrl produces a sequence of values at each invocation, and function f_nbuf takes a sequence as second argument.

Figure 9-2. System level of the untimed process network for the example of Figure 9-1.

While this solves our problem, it highlights a fundamental aspect of untimed models as we have defined them. Due to the deterministic behavior with a blocking read it is not obvious how to decouple two processes A and B completely from each other. A truly asynchronous buffer is cumbersome to realize. However, what we can do, and what we want to do in this case, is to fix the relative activation rate of A and B and investigate how the buffer in between behaves. In this respect, untimed models resemble synchronous models. In synchronous models we cannot decouple processes A and B either, but we can observe the buffer in between by exchanging varying amounts of data in each activation cycle. If we want to decouple two processes in a nondeterministic or stochastic way, neither the untimed nor the synchronous model can help us.

The simulation of the model yields quite different results depending on the input sequence. Table 9-1 shows the result of 11 different runs. As input we have used 5000 integers in increasing order. For the first row in the table the input started with 0, 1, 2, ...; for the second row it started with 1, 2, 3, ...; and so on. The last row, marked with a *, the input sequence started with 1, 2, 3, ..., but the function f_merge was not merging the streams x and x₄ but just passing on x without modification. The objective for this row was to get a very regular input stream without an irregular distribution of 0s. The second column gives the number of 0s dropped by the buffer; the third column gives the number of 0s inserted by the buffer when it was empty and process B requested data.

Table 9-1. Simulation runs with 5000 samples of consecutive integers.

Sequence start	Dropped 0s	Inserted 0s	0s%	Buffer length
0	109	69	2.16	14
1	55	11	1.09	13
2	45	8	0.89	13
3	46	4	0.91	9
4	37	2	0.73	16
5	75	31	1.49	13
6	61	18	1.21	12
7	55	12	1.09	11
8	41	3	0.81	13
9	56	21	1.11	15
10	50	11	0.99	16
*	50	6	0.99	8

Table 9-1 shows that the maximum buffer length is very sensibly dependent on the input sequence. If it is a regular stream, like in the last row, the simulation corresponds to our analysis above. But for different inputs we get maximum buffer lengths of anywhere between 8 and 16. Even though the fraction of 0s on the input stream is always 1%, it varies between 0.73% and 2.16% before the buffer. But even when the fraction is similar, like in the last two rows, the maximum buffer length can deviate by a factor of 2.

Besides the great importance of realistic input vectors for any kind of performance simulation, this discussion shows that an untimed model can be used for the performance analysis of parameters unrelated to timing, or rather, to be precise, where we can keep the relative timing fixed in order to understand the relation between other parameters. In this case we examine the impact of control and data input on the maximum buffer size.

The two problems we have encountered when developing the untimed model would be somewhat easier to handle in a synchronous model. The NoUpdate events on the control input, which we had to introduce explicitly, would not be necessary, because we would use the more suitable ⊔ events, which represent absent events, indicating naturally that most of the time no control command is received. The situation of a varying data rate between process A₃ and Buf could be handled in two different ways. Either we bundle several packets into one event, as we did in the untimed model, or we reflect the fact that A₁ and Buf have to operate at a rate four times higher than other processes. In state δ these two processes have to handle four packets when all other processes have to handle only one. Thus, if we do not assume other buffers, these processes have to operate faster. In the synchronous model we would have four events between A₁ and Buf for each event on other streams. Since most of the time only one of these four events would be valid packets, most of the events would be absent (⊔) events. This had the added benefit that we could observe the impact of different relative timing behavior. In an untimed model we can achieve the same, but we have to model absent events explicitly. However, the differences for problems of this kind are not profound, and we record that untimed and synchronous models are equivalent in this respect, but require slightly different modeling techniques.

The timed model confronts us with the need to determine the detailed timing behavior of all involved processes. While this requires more work and is tedious, it gives us more flexibility and generality. We are not restricted to a fixed integer ratio between execution times of processes but can model arbitrary and data-dependent time behavior. Furthermore, we do not need to be concerned with the problem of too tight coupling of the buffer to its adjacent processes. This gained generality, however, comes at the price of less efficient simulation performance and, if a δ-delay-based model is used, a severe obstacle to parallel distributed simulation as discussed in Chapter 5.

We have already started to indicate how different models of computation constrain our ability for analyzing timing behavior that is at the core of performance analysis. To substantiate the discussion, we again use the example of the previous section. We will take the example of Figure 9-2, and replace the definitions of Figure 9-3 with the ones in Figure 9-4.

Figure 9-3. Definitions of processes and functions for the example in Figure 9-2.

Figure 9-4. Redefinitions of processes of Figures 9-2 and 9-3 to obtain a synchronous model.

All processes behave identically with the exception of A₃, which introduces a delay for the maintenance packets. We have replaced the untimed model with a synchronous one in order to measure the delay of a packet through the network.

Table 9-2 shows the result. The maximum delay of packets through the network is significant. If there is only a single buffer in the system, as in our case, the delay becomes equal to the maximum buffer size. The necessary buffer size has increased compared to Figure 9-1 because B cannot process packets as fast as before and relies on additional buffering. This kind of analysis is natural in a synchronous model because inserting delays that are integer multiples of the basic event execution cycle is straightforward.

Figure 9-5 shows the requirements definition of a functional number sorter that converts an indexed array A into another indexed array B that is sorted. The requirements only state the conditions that must hold in order that B is considered to be sorted, but it does not indicate how we could possibly compute B.

sort :: (IntArrayA) ⇒ (IntArrayB)
        Precondition: true
       Postcondition: ∀a: a ∊ A → a ∊ B
                      ∧∀b: b ∊ B → b ∊ A
                      ∧∀i, j ∊ Z, bi, bj ∊ B : i < j → bi ≤ bj

Figure 9-6 gives us two alternative functional models for sorting an array. The first, sort1, solves the problem recursively by putting sorted subarrays together to form the final sorted array. First comes the sorted array of those elements that are smaller than the first array element (first(A)), and finally the sorted array of those elements that are greater or equal to first(A). The second function, sort2, is also recursively defined and takes all elements that are smallest and puts them in front of the sorted rest of the array. Both functions are equivalent, which can be proved, but they exhibit important differences that affect performance characteristics of possible implementations. One important feature of both function definitions is that potential parallelism is only constrained by data dependences. For example, sort2 does not define if smallest(A) is computed before, in parallel with, or after the rest of the array. In fact, it does not matter for the result in which order the computations are performed. However, the computation is divided into two uneven parts. smallest(A) is inherently simpler to compute than deriving and sorting the rest of the array. This is also obvious from the fact that smallest(A) is even a part of the second computation. Thus, the data dependences will enforce a rather sequential implementation. sort1, on the other hand, has a much higher potential for a parallel implementation because the problem is broken up more evenly. Unless A is not almost sorted, the problems of sorting those elements that are less than first(A) will be as big as sorting those elements that are greater or equal to first(A). Which one of the two functional models is preferable will depend on what kind of implementation will be selected. sort1 is better for a parallel architecture such as an FPGA or a processor array. For a single-processor machine that executes purely sequential programs, sort2 should be preferred because sort1 might be hopelessly inefficient. Figure 9-7 shows a sequential algorithm of function sort2. Several design decisions were taken when refining sort2 into sort2_alg. The amount of parallelism has been fixed, basically by removing the potential parallelism. The representation of the data and how to access it has been determined. Finally, the details of how to compute all functions such as smallest() have been worked out.

sort :: (IntArrayA) → (IntArrayB)
sortl([]) = []
sort1 (A) = sort1(select_less(first(A), tail(A))) ++first(A)
            ++sort1(select_geq(first(A), tail(A)))
sort2([]) = []
sort2(A)  = smallest(A)++(sort2(select_not(smallest(A), A)))

sort2_alg (IntArraySc A)
{ for (i = 2; i < = length(A); i++)
      { for (j = length(A); j > = i; i--)
            {if (B [j -1] > B [j])
                {
                int tmp = input [j -1];
                B[j-l] = B[j];
                B [j] = tmp;
                }
            }
       }
}

The packet multiplexer merges four 150 packets/second streams into one 600 packets/second stream as shown in Figure 9-8. The requirements definition would be mostly concerned with the constraints on the interfaces and the performance of the input and output streams. The functional requirements would state that all packets on the inputs should appear on the output and that the ordering on the input streams should be preserved on the output stream.

Figure 9-8. Packet multiplexer.

A functional model fulfilling these requirements is shown in Figure 9-9. We assume that we have a process constructor zipWith4U, which is a generalization of the previously defined zipWithU and merges four signals into one.

Mux(s1, s2, s3, s4) =  zlpWlth4U(1, 1, 1, 1, f)
  f(x1, x2, x3, x4) = 〈(x1, x2, x3, x4〉

Since the functionality we are asking for is simple, the functional model is short. But a further refined design model could be more involved, as is shown in Figure 9-10. It is based on three simple two-input multiplexers that merge the input stream in two steps. It is refined, although it implements the same functionality, because we made a decision to realize the required function by means of a network of more primitive elements.

Figure 9-10. A refined packet multiplexer based on simpler multiplexer units.

Let’s assume that our requirements change and the output does not have a capacity of 600 packets/second but only 450. That means we have to drop one out of four packets and, according to the new requirements, we should avoid buffering packets and drop one packet in each multiplex cycle. If there is an idle packet, we should drop it; otherwise it does not matter which one we lose. A new functional description, which meets the new requirements, is shown in Figure 9-11. The function f outputs only three of the four input packets, and it drops the packet from stream s₄ if none of the other packets is idle. When we propagate the modification down to the design model, we have several possibilities, depending on where we insert the new functionality. It could become part of modified Mux-2 blocks, or it could be realized by a separate new block before the output. We could also distribute it and filter out all idle packets at the inputs, and either insert idle packets or filter out a packet from stream s₄ before the output. The solution we have chosen, as shown in Figure 9-12, inserts two new blocks, filter_idle, which communicate with each other to filter out the right packet.

Mux2(sl, s2, s3, s4) =  zipWith4U(1, 1, 1, 1, f)
   f(xl, x2, x3, x4) = 〈x2, x3, x4〉 if x1 = idle
                      〈x1, x3, x4〉 if x2 = idle
                      〈x1, x2, x4〉 if x3 = idle
                      〈x1, x2, x3〉 otherwise

Figure 9-12. A modified design of the packet multiplexer.

The borderlines between requirements definition, functional specification, and design are blurred because in principle it is a gradual refinement process. Design decisions are added step by step, and the models are steadily enriched with details, which eventually leads hopefully to a working system that meets the requirements. Hence, to some degree it is arbitrary which model is called the requirements definition, functional specification, or design description, and in which phase which decisions are taken. On the other hand, organizing the design process into distinct phases and using different modeling concepts for different tasks is unavoidable.

In the number sorter example, we have made several design decisions on the way from the requirements definition to a sequential program. We have not made all the decisions at once but rather in two steps. In the first step, which ended with a functional model (Figure 9-6), we broke the problem up into smaller subproblems and defined how to generate the solution from the subsolutions. The way we do this constrains the potential parallelism. In addition, the breaking the problem up into subproblems will also constrain the type of communication necessary between the computations solving the subproblems. This may have severe consequences for performance if a distributed implementation is selected.

While these observations may be self-evident, for the number sorter it is less obvious that we need a functional model at all. It might be preferable to develop a detailed implementation directly from the requirements definition because the best choice on how to break up the problem only becomes apparent when we work on the detailed implementation with a concrete architecture in mind. Neither sort1 nor sort2 is clearly better than the other; it depends on the concrete route to implementation.

Although this is correct and might render a functional model for simple examples useless, the situation is more difficult for the development of larger systems. First, with the introduction of a functional model the design decisions between requirements definition and implementation model are separated into two groups. Since the number of decisions may be very large and overwhelming, to group them in a systematic way will lead to better decisions. This is true in particular if certain issues are better analyzed and explored with one kind of model than with another. One issue that is better investigated with a functional model, as we have exposed with the number sorter example, is the potential parallelism and, as a consequence, the constraints on dataflow and communication between the computations of subproblems. However, this does not rule out taking into account the different architectures for the implementation. On the contrary, in order to analyze sensibly different functional alternatives, we must do this with respect to the characteristics of alternative architectures and implementations.

Another issue where a functional model may support a systematic exploration is revealed by the second example, the packet multiplexer. The functional design phase must explore the function space. Which functions should be included or excluded? Can a given set of functions meet user needs and requirements? These user needs and requirements are sometimes only vaguely specified and may require extensive analysis and simulation. For instance, the convenience of a user interface can often only be assessed when simulated and tried by a user. The impact of adding or deleting a function on other parts of the system is sometimes not obvious. For instance, the change of functionality in the packet multiplexer example, which means that up to 100% of the packets in stream s₄ are lost, may have undesirable consequences for the rest of the telecommunication network. It might be worthwhile to evaluate the impact of this change by an extensive simulation. A functional model can greatly facilitate these explorations provided we can quickly modify, add, and remove functions. In contrast, the consecutive design phase is much more concerned with mapping a functionality onto a network of available or synthesizable components, evaluating alternative topologies of this network, and, in general, finding efficient and feasible implementations for a fixed functionality. If these two distinct objectives are unconsciously mixed up, it may lead to an inefficient and unsystematic exploration of alternatives. In the case of the packet multiplexer it is unnecessary to investigate with great effort the best place to insert the new filter functionality or to modify the existing Mux-2 blocks if a functional system simulation reveals that the new functionality has undesirable consequences and must be modified or withdrawn.

From these considerations we can draw some conclusions on how best to support purpose P-I of a functional specification. In order to efficiently write and modify a specification document, we should avoid all irrelevant details. Unfortunately, what is relevant and what is not relevant is not constant and depends on the context.

With respect to purpose P-II we refer to the following discussion of design and synthesis.

We use a simple design flow as illustrated in Figure 9-13 to discuss the major design tasks and their relation. This flow is simplified and idealistic in that it does not show feedback loops, while in reality we always have iterations and many dependences. For instance, some requirements may depend on specific assumptions of the architecture, and the development of the task graph may influence all earlier phases. But this simple flow suffices here to identify all important design and synthesis activities and to put them in the proper context.

Figure 9-13. System design flow from requirements engineering to code generation of hardware and software.

This brief review of design problems allows us to identify some requirements on modeling. One obvious observation is that the assessment of nonfunctional properties is an integral task of most design activities. Unfortunately, nonfunctional properties, with the notable exception of time, are not an integral part of most modeling techniques and modeling languages. Since our theme is the analysis of computational models, we can only acknowledge this situation and restrict further discussion to issues of functionality and time.

To model components and networks of components realistically, we should employ a timed model because it is the only metamodel that can capture the timing behavior with arbitrary precision. This may not always be necessary; in fact in many cases it is not. When we only deal with the functionality, the delay of individual components is irrelevant. In other cases we are content with a more abstract notion of time corresponding to a synchronous model. For instance, in hardware design the very popular synchronous logic partitions a design into combinatorial blocks separated by latches or registers, as illustrated in Figure 9-14. The edge-triggered registers at the inputs and outputs of the combinatorial block are controlled by the rising edge of a clock signal. Thus, when the clock signal rises, the inputs a, b, c, and d to the combinatorial block change and the gates react by changing their respective outputs as appropriate. When the clock signal rises the next time, the outputs y and z are stored in the output registers and are thus available for the next combinatorial block.

Figure 9-14. A combinatorial network of gates.

This allows us to separate timing issues from functionality issues; in the first step we assume that all combinatorial blocks are fast enough to deliver a result within a clock period, and in the second step we verify that this assumption is in fact correct. Thus, the first step does not require a timed model but only an untimed or a synchronous model. It is indeed an order of magnitude more efficient to simulate such designs in a synchronous timing model as the cycle-true simulators have proven. Only the second step requires a timed model, but even there we can separate timing from functionality by means of a static timing analysis. For the example in Figure 9-14 the static timing analysis would calculate the longest path, which is from input a to output y, and takes 8 ns. Thus, when any of the inputs change, all outputs would be available after 8 ns and the clock cycle needs to be no longer than 8 ns.

Consequently we could describe the functionality of a component based on an untimed model that just represents the input-output behavior, and store the timing information as a separate annotation. But even though the actual use of accurate timing information is limited, using the timed model for component modeling is still recommended for two reasons. First, almost always comes a situation where it is mandatory, for instance, when the behavior depends on the precise timing or vice versa, and this is relevant. Static timing analysis can only reveal the worst-case delay. However, when this worst case can never happen because the input vector to a combinatorial block is inherently restricted by another block, static timing analysis would be too conservative. For instance, assume that in the example of Figure 9-14 the inputs are constrained such that a is always equal to b. The AND gate that connects NOT a and b would always have an output of 0 and would never change, no matter what the inputs were, if we ignore glitches. The longest path would be 5 ns from d to y. Such situations cannot be detected by static analysis or functional simulation alone. Only when we analyze the functional behavior and the timing of the components together can we detect this. The second reason why we prefer a timed model for modeling components and structure is that timing information can be easily ignored when components are included in a simulation based on another computational model, as has been shown with functional and cycle true simulations.

Another main concern for modeling is the transformation of functionality during the design process. System functions are partitioned into tasks, communication between tasks is refined from high-level to low-level protocols, parallel computations are serialized and vice versa, functions are transformed until they can be mapped onto a given network of primitive components, and so on and so on. If all this is done manually, we do not have much to worry about, at least not for the design process itself. We must still worry about validation. For an automatic synthesis process the situation is more delicate because all the transformations and refinements must be correct. While it is possible—and even popular—to hardwire rules into the synthesis tool, this process can be supported more systematically and in a more general way by providing large classes of equivalences. Whenever we have a case of semantic equivalence a tool can use this to transform a given design into a more optimal implementation. For instance, for a function over integers f₁(x) = h(x) + g(x), the commutative law tells us that this is equivalent to f₂(x) = g(x) + h(x). A synthesis tool could then transform f₁ into f₂ if the hardware structure is such that the latter represents a more efficient implementation. However, if this is not guaranteed by the semantics of the language, such a transformation is not possible and the exploration space of the synthesis tool is significantly restricted. For instance in C this particular equivalence is not guaranteed because g and h may have side effects that may change the result if they are evaluated in a different order.

The essential difference of the three main computational models that we introduced in Chapters 3 through 5 is the representation of time. This feature alone weighs heavily with respect to their suitability for design tasks and development phases.

Untimed Model

As we saw in Section 3.15, the dataflow process networks and their variants have nice mathematical features that facilitate certain synthesis tasks. The tedious scheduling problem for software implementations is well understood and efficiently solvable for synchronous and boolean dataflow graphs. The same can be said for determining the right buffer sizes between processes, which is a necessary and critical task for hardware, software, and mixed implementations. How well the individual processes can be compiled to hardware or software depends on the language used to describe them. The dataflow process model does not restrict the choice of these languages and is therefore not responsible for their support. For what it is responsible—the communication between processes and their relative timing—it provides excellent support due to a carefully devised mathematical model.

Figure 9-15 summarizes this discussion and indicates in which design phases the different MoCs are most suitable.

Figure 9-15. Suitability of MoCs in different design phases.