entity statement entity MOORE MAChine port(X, CLK: in BIT; Z: out BIT); end MOORE MACHINE architecture statement architecture fsm of moore machine is type STATE_TYPE is(A, B, C) signal STATE: STATE_TYPE: =A; beg NEXT STATE block(CLK='1 and not CLKSTABLE) guarded conditional concurrent signal assignment statement STATE<=guarded B when(STATE=A and X='1 )else C when (STATE=B and X=0)else A when(STATE=C)else STATE; end block NEXT state unguarded selected concurrent signal assignment statement with STATE select Z<=°0 when a, °0 when B, 1 when C: end FSM: FIGURE 34. 8 VHDL model just changed value, and"CLK=, " then a rising transition has occurred on CLK. The output signal Z is driven by a nonguarded, selected concurrent signal assignment statement that executes any time STATE changes value. 34.3 Synthesis Figure 34.9 shows that the synthesis task generally follows the design entry task. After describing the desired system via design entry, synthesis Da programs are invoked to assist generating the required detailed design. of abstraction to another, more-detailed level of abstraction The more-detailed level of abstraction may be only an inter- Synthesis mediate step in the entire design process, or it may be the final implementation. Synthesis programs that yield a final that yield a final FIGURE 34.9 Design process - synthesis. implementation are sometimes called silicon compilers because the programs generate sufficient detail to proceed directly to silicon fabrication[Ayres, 1983; Gajski, 1988] Like design abstractions, synthesis techniques can be hierarchically categorized, as shown in Fig. 34.10. The higher levels of synthesis offer the advantage of less complexity, but also the disadvantage of less control over the final design. Algorithmic synthesis, also called behavioral synthesis, addresses"multicycle"behavior, which means behavior ore than one control step. A control step equates to a clock cycle of a synchronous, sequential digital ystem, i.e., a state in a finite-state machine controller or a microprogram step in a microprogrammed controller. c 2000 by CRC Press LLC
© 2000 by CRC Press LLC just changed value, and “CLK=’1’,” then a rising transition has occurred on CLK. The output signal Z is driven by a nonguarded, selected concurrent signal assignment statement that executes any time STATE changes value. 34.3 Synthesis Figure 34.9 shows that the synthesis task generally follows the design entry task. After describing the desired system via design entry, synthesis DA programs are invoked to assist generating the required detailed design. Synthesis translates or transforms a design from one level of abstraction to another, more-detailed level of abstraction. The more-detailed level of abstraction may be only an intermediate step in the entire design process, or it may be the final implementation. Synthesis programs that yield a final implementation are sometimes called silicon compilers because the programs generate sufficient detail to proceed directly to silicon fabrication [Ayres, 1983; Gajski, 1988]. Like design abstractions, synthesis techniques can be hierarchically categorized, as shown in Fig. 34.10. The higher levels of synthesis offer the advantage of less complexity, but also the disadvantage of less control over the final design. Algorithmic synthesis, also called behavioral synthesis, addresses “multicycle” behavior, which means behavior that spans more than one control step. A control step equates to a clock cycle of a synchronous, sequential digital system, i.e., a state in a finite-state machine controller or a microprogram step in a microprogrammed controller. -- entity statement entity MOORE_MACHINE is port (X, CLK : in BIT; Z : out BIT); end MOORE_MACHINE; -- architecture statement architecture FSM of MOORE_MACHINE is type STATE_TYPE is (A, B, C); signal STATE : STATE_TYPE := A; begin NEXT_STATE: block (CLK=’1’ and not CLK’STABLE) begin -- guarded conditional concurrent signal assignment statement STATE <= guarded B when (STATE=A and X=’1’) else C when (STATE=B and X=’0’) else A when (STATE=C) else STATE; end block NEXT_STATE; -- unguarded selected concurrent signal assignment statement with STATE select Z <= ‘0’ when A, ‘0’ when B, ‘1’ when C; end FSM; FIGURE 34.8 VHDL model. FIGURE 34.9 Design process — synthesis
Register Transfer Register Allocation Finite State Machine Synthesis Redundancy Removal Technology Mapping FIGURE 34.10 Taxonomy of synthesis techniques. Algorithmic synthesis typically accepts sequential design descriptions that define an input/output transform, but provide little information about the parallelism of the final design [Camposano and wolfe, 1991; Gajski etal,1992] Partitioning decomposes the design description into smaller behaviors. Partitioning is an example of a high level transformation. High-level transformations include common software programming compiler optimiz tions,such as loop unrolling, subprogram in-line expansion, constant propagation, and common subexpression Resource allocation associates behaviors with hardware computational units, and scheduling determines the order in which behaviors execute. Behaviors that are mutually exclusive can potentially share computational performed using a variety of graph clique coverin Allocation and scheduling are interdependent, and different synthesis strategies perform allocation and sched uling different ways. Sometimes scheduling is performed first, followed by allocation; sometimes allocation is performed first, followed by scheduling; and sometimes allocation and scheduling are interleaved Scheduling assigns computational units to control steps, thereby determining which behaviors execute in which clock cycles. At one extreme, all computational units can be assigned to a single control step, exploiting maximum concurrency. At the other extreme, computational units can be assigned to individual control steps, exploiting maximum sequentiality. Several popular scheduling algorithms are listed below As-soon-as-p List scheduling Force-directed scheduling, and Control step splitting/merging. ASAP and ALAP scheduling algorithms order computational units based on data dependencies List schedulin is based on ASAP and ALAP scheduling, but considers additional, more-global constraints, such as maximum number of control steps. Force-directed scheduling computes the probabilities of computational units assigned to control steps and attempts to evenly distribute computation activity among all control steps Control step splitting starts with all computational units assigned to one control step and generates a schedule by splitting the computational units into multiple control steps Control step merging starts with all computational units assigned to individual control steps and generates a schedule by merging or combining units and steps [ Paulin and Knight, 1989; Camposano and Wolfe, 1991 Register transfer synthesis takes as input the results of algorithmic synthesis and addresses "per-cycle behavior, which means the behavior during one clock cycle. Register transfer synthesis selects logic to realize the hardware computational units generated during algorithmic synthesis, such as realizing an addition oper ation with a carry-save adder or realizing addition and subtraction operations with an arithmetic logic unit
© 2000 by CRC Press LLC Algorithmic synthesis typically accepts sequential design descriptions that define an input/output transform, but provide little information about the parallelism of the final design [Camposano and Wolfe, 1991; Gajski et al., 1992]. Partitioning decomposes the design description into smaller behaviors. Partitioning is an example of a highlevel transformation. High-level transformations include common software programming compiler optimizations, such as loop unrolling, subprogram in-line expansion, constant propagation, and common subexpression elimination. Resource allocation associates behaviors with hardware computational units, and scheduling determines the order in which behaviors execute. Behaviors that are mutually exclusive can potentially share computational resources. Allocation is performed using a variety of graph clique covering or node coloring algorithms. Allocation and scheduling are interdependent, and different synthesis strategies perform allocation and scheduling different ways. Sometimes scheduling is performed first, followed by allocation; sometimes allocation is performed first, followed by scheduling; and sometimes allocation and scheduling are interleaved. Scheduling assigns computational units to control steps, thereby determining which behaviors execute in which clock cycles. At one extreme, all computational units can be assigned to a single control step, exploiting maximum concurrency. At the other extreme, computational units can be assigned to individual control steps, exploiting maximum sequentiality. Several popular scheduling algorithms are listed below: • As-soon-as-possible (ASAP), • As-late-as-possible (ALAP), • List scheduling, • Force-directed scheduling, and • Control step splitting/merging. ASAP and ALAP scheduling algorithms order computational units based on data dependencies. List scheduling is based on ASAP and ALAP scheduling, but considers additional, more-global constraints, such as maximum number of control steps. Force-directed scheduling computes the probabilities of computational units being assigned to control steps and attempts to evenly distribute computation activity among all control steps. Control step splitting starts with all computational units assigned to one control step and generates a schedule by splitting the computational units into multiple control steps. Control step merging starts with all computational units assigned to individual control steps and generates a schedule by merging or combining units and steps [Paulin and Knight, 1989; Camposano and Wolfe, 1991]. Register transfer synthesis takes as input the results of algorithmic synthesis and addresses “per-cycle” behavior, which means the behavior during one clock cycle. Register transfer synthesis selects logic to realize the hardware computational units generated during algorithmic synthesis, such as realizing an addition operation with a carry–save adder or realizing addition and subtraction operations with an arithmetic logic unit. FIGURE 34.10 Taxonomy of synthesis techniques