Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems

10.2 PRECEDENCE RELATION AND SCHEDULING

The precedence relation and its graphical representation—a dataflow graph—define which operations must be completed before starting a new one. Consider a first example:

Example 10.3 The precedence graph of Algorithm 4.2 (carry-chain adder), with n = 4, is shown in Figure 10.3.

If one chooses to execute the algorithm in just one cycle (parallel implementation), then the precedence graph is practically equivalent to the corresponding combinational circuit. As an example, the carry-chain adder of Figure 11.3 can be directly deduced from the precedence graph of Figure 10.3. If a sequential implementation is considered, the precedence graph allows scheduling the operations, that is, deciding in which cycle every operation is performed.

A sequential implementation is given in Example 10.4.

Example 10.4 (Complete VHDL source code available.) The data flow graph corresponding to Algorithm 4.10 (long-operand addition), with n = 128 and s = 32, is shown in Figure 10.4. A possible 4-cycle schedule is indicated. In every cycle a 32-digit addition is performed so that only one 32-digit adder is necessary. The scheduled precedence graph also gives information about the memory resources: every arc crossing a cycle dotted line corresponds to a variable computed during some cycle and to be used during one of the following ones. So some memory resource is necessary in order to store its value (except in the case of inputs assumed constant during the whole ...