Logic Synthesis for Field Programmable Gate Array (FPGA) Technology:Logic Synthesis

By -
Logic Synthesis

Logic synthesis is typically implemented as a two-phase process: a technology-independent phase, followed by a technology-mapping phase [4]. The first phase attempts to generate an optimized abstract representation

Logic Synthesis for Field Programmable Gate Array (FPGA) Technology-0290

Technology-Independent Optimization

In the technology-independent synthesis phase, the combinational logic function is represented by the Boolean network, as illustrated in Figure 67.5. The nodes of the network are initially general nodes, which can represent any arbitrary logic function. During optimization, these nodes are usually mapped from the general form to a generic form, which only consists of AND, OR, and NOT logic nodes [4]. At the end of the first synthesis phase, the complexity and number of nodes of the Boolean network has been reduced. Two classes of operations — network restructuring and node minimization — are used to optimize the network. Network restructuring operations modify the structure of the Boolean network by introducing new nodes, eliminating others, and adding and removing arcs. Node minimization simplifies the logic equations associated with nodes [5].

Restructuring Operations

Decomposition reduces the support of the function, F (denoted as sup(F)). The support of the function refers to the set of variables that F explicitly depends on. The cardinality of a function (denoted by |sup(F)|), represents the number of variables that F explicitly depends on.

Logic Synthesis for Field Programmable Gate Array (FPGA) Technology-0291

Factoring is used to transform the SOP form of a logic function into a factored form. Substitution expresses one given logic function in terms of another. Elimination merges a subfunction, G, into the function, F, so that F is expressed only in terms of its fan-in nodes of F and G (not in terms of G itself).

The efficiency of the restructuring operations depends on finding a suitable divisor, P, to factor the function, that is, given functions F, choose a divisor P, and find the functions Q and R such that F = PQ + R. The number of possible divisors is hopelessly large; thus, an effective procedure is needed in practice to restrict the search subspace for a good divisor. The Brayton and McMullen kernel matching technique has proven effective at this task.

The kernels of a function F are the set of expressions: K(F) = {gú g Ì D(F)}, where g is cube-free and D(F) are the primary divisors.

A cube is a logic function given by the product of literals. A cube of a function F is a cube whose on-set does not have vertices in the off-set of F (e.g., if F = ab(c + d), ab is a cube of F). An expression F is cube-free if no cube divides the expression evenly [6]. For example, F = ab + c is cube-free, while F = ab + ac is not cube-free. Finally, the primary divisors of F are the set of expression: D(F) = F/C |C is a cube [7].

Kernel functions can be computed effectively by several fast algorithms. Based on the kernel functions extracted, the restructuring operations can generate acceptable results usually within a reasonable amount of time [4]. Speed/quality tradeoffs are still needed, however, as is the case with MIS, which is a multilevel logic synthesis system [8].

Node Minimization

Node minimization attempts to reduce the complexity of a given network by using Boolean minimization techniques on its nodes.

A two-level logic minimization with consideration of the don’t-care inputs and outputs can be used to minimize the nodes in the circuit. Two types of don’t-care sets — satisfiability don’t care (SDC) and observability don’t care (ODC) — are used in the two-level minimizer. The SCD set represents combinations of input variables that can never occur because of the structure of the network itself, while the ODC set represents combinations of variables that will never be observed at outputs. If the SDCs and ODCs are too large, a practical running time for the algorithm can only be achieved by using a limited subset of SDCs and ODCs [8].

Another technique to reduce the complexity of a Boolean network uses a tautology checker to determine if two Boolean networks are equivalent. The result is determined by computing the XNOR of the circuit’s primary outputs [9]. A node is first tentatively simplified by deleting either variables or cubes. If the result of tautology check is 1 (equivalent), then this deletion is performed. As with the first method, an exhaustive search of all possible networks is usually not feasible because of the high computational cost of the tautology check.

Technology Mapping

The technology-mapping phase for an FPGA attempts to realize the Boolean network using a minimal number of CLBs. Synthesis algorithms fall into two main categories: algorithmic approaches and rule- based techniques.

By expressing the optimized AND/OR/NOT network as a subject graph (a network of two-input NAND gates), and a library of potential mappings as a pattern graphs, the algorithmic approach converts the mapping problem into a covering problem with the goal of finding the minimum-cost cover of the subject graph by the pattern graphs. The problem is NP-hard; thus, heuristics must be used. If the Boolean network is not a tree, a step of decomposition into forest of trees is performed; then the mapping problem is solved as a tree-covering-by-tree problem.

The rule-based technique traverses the Boolean network and replaces subnetworks with patterns in the library when a match is found. It is slow compared to the algorithmic method, but can generate better results. Hybrid approaches which perform a tree-covering step followed by a rule-based clean-up step are used in industry

Comments

Post a Comment

Popular posts from this blog

SRAM:Decoder and Word-Line Decoding Circuit [10–13].

By -
Image
Decoder and Word-Line Decoding Circuit [10–13] Two kinds of decoders are used in SRAM: the row decoder and the column decoder. Row decoders are needed to select one row of word-lines out of a set of rows in the array. A fast decoder can be implemented by using AND/NAND and OR/NOR gates. Figure 52.7 shows the schematic diagrams of static and dynamic AND gate decoders. The static NAND-type structure is chosen due to its low power consumption, that is, only the decoded row transitions. The dynamic structure is chosen due to its speed and power improvement over conventional static NAND gates. From a low-voltage operation standpoint, a dynamic NOR-base decoding would provide lower delay times through the decoder due to the limited amount of stacking of devices. Figure 52.8 shows circuit diagrams of dynamic NOR gates. The dynamic CMOS gate as shown in Figure 52.8(a) consists of input- NMOSs whose drain nodes are precharged to a high level by a PMOS when a clock signal Φ is at a low lev...
Read more

ASIC and Custom IC Cell Information Representation:GDS2

By -
Image
GDS2 The Graphical Design System (GDS) format is a binary format developed by Calma Company in 1971 to convey IC layout information between IC designers and fabricators. Calma presented GDS2 format, the improved version of GDS, in 1978. Finally in 1991, when Cadence acquired Calma, GDS2 rights were transferred to it. In the design process, after the completion of routing and placement, design rule check (DRC) and layout versus schematic (LVS) are performed to verify the final layout. Then the verified layout, dumped in a GDS2 file, is transferred to IC foundries for fabrication. GDS2 File Format GDS2 is a standard mask layout intermediate format containing a single cell or a library of cells each of which includes a number of geometrical objects such as boundaries, paths, boxes, etc. These objects correspond to different layers of a cell where each layer is specified by a layer number and data type [3]. The file format of GDS2 is in binary. A GDS2 file contains a number of variable...
Read more

Timing Description Languages:SDF

By -
Image
SDF Standard Delay Format (SDF) is an ASCII format used to convey timing information between EDA tools. SDF was first developed by Cadence in 1990. Open Verilog International (OVI) approved SDF version 2 in 1993 and SDF version 2.1 and 3 in the following years. Improving SDF version 3 features, resulted in IEEE Standard 1497 [1]. Role of SDF in Design Process SDF can be used in different levels of a design process to annotate timing specifications, including timing data and constraints. Timing constraints are used during the forward-annotation process while timing data are applied during the back-annotation process. Forward-annotation process deals with porting timing constraints to synthesis, floorplanner, layout, and routing tools to meet the required constraints. During the design process, timing data can be back-annotated to analysis tools (including simulators, static timing analysis tools, etc.) to provide more accurate timing representations. SDF Structure An SDF f...
Read more