Blog • 自动逻辑综合原理 • 组合逻辑与 LUT 的最简单的综合

LUT

一切皆查表。 ——我自己说的

由于 FPGA 的基本结构是基于 Look Up Table 的，因此 FPGA 里实现组合逻辑的方式非常简单粗暴，就是把真值表非常暴力的存下来然后匹配。

比如说最简单的与逻辑：

assign C = A & B;

其真值表：

	0	1
0	0	0
1	0	1

那么我们就可以用一小块存储器存下这张表：

地址	值
00	0
01	0
10	0
11	1

这个存储器此时就是一个 LUT，输入 A 和 B 就能输出对应逻辑函数的值。

更多变量和更复杂的式子也是同理。

实践

我们来用最简单粗暴的方式实现一个支持简单组合逻辑电路综合的简单综合器。

为了方便快草猛的实现出一个能动的程序，我们将要综合的逻辑函数限制在 4 个以下的输入和单个输出，这样就能使用单个 LUT4 综合出可以动的成果。

注意实际的综合器实现方式肯定不是这样暴力解出真值表然后就硬带，肯定是有更先进的方案的。

目标文件格式

为了方便上硬件，我们综合到的目标是 nextpnr-ecp5 中使用的 json 文件。

经过仔细阅读 yosys 综合出来的 json 文件以及反复实验，我们可以确定这个 json 最小需要写出如下内容：

{
    "creator": "<综合器名称和版本，其实目测可以不写>",
    "modules": {
        "Module1": {<内容>},
        "Module2": {<内容>},
    }
}

其中 module 的内容：

"ports": {
    "<对外端口名称>": {
        "direction": "<input/output>",
        "bits": [<对应的线网的第1个bit的id>, <对应的线网的第2个bit的id>, ...]
    },
    ...
},
"cells": {
    "<子组件名称>": {
        "type": "<子组件类型>",
        "parameters": {
            "<子组件参数名1>": "<子组件参数值1>",
            ...
        },
        "port_directions": {
            "<子组件端口名1>": "input/output",
            ...
        },
        "connections": {
            "<子组件端口名1>": [<子组件端口1连接到的线网的第1个bit的id>, <子组件端口1连接到的线网的第2个bit的id>, ...],
            ...
        }
    }
},
"netnames": {
    "<线网名称>": {
        "bits": [<对应的线网的第1个bit的id>, <对应的线网的第2个bit的id>, ...]
    },
}

parser

略，见我以前有关 parser combinator 的文章。

总之把这样子的输入：

module Top(a: bit, b: bit) -> bit {
    return a & b;
}

parse 成这样的结构：

// Bracket、逻辑函数的实现同普通编程语言，略
pub enum Expression {
    Name(String),
    Bracket(Bracket),
    Not(Not),
    Or(Or),
    And(And),
}
pub struct Return(pub Expression);
pub struct Port {
    pub name: String,
}
pub struct Module {
    pub name: String,
    pub input: Vec<Port>,
    // todo: output type
    pub output: Vec<()>,
    // todo: `Statement` instead of `Return`
    pub statements: Vec<Return>,
}

然后将表达式编译成如下的 LUT4:

pub struct LUT4 {
    pub name: String,
    pub initial_value: u16,
    pub input_connections: [usize; 4],
    pub output_connections: usize,
}

编译过程如下，代码太丑不好意思拿出来看我就放伪代码了：

pub fn compile_expression(
    expression: frontend::Expression,
    context: &mut Context,
) -> Result<LUT4, ()> {
    // generate initial_value
    let mut initial_value = 0;
    let mut variables = expression.variables();
    while variables.len() < 4 {
        variables.push(format!("dummy_{}", variables.len()));
    }
    for i, (a, b, c, d) in tagged_cartesian_product(a: (0, 1), b: (0, 1), c: (0, 1), d: (0, 1)).enumerate() {
        let result = expression.evaluate(a, b, c, d);
        initial_value |= result << i;
    }
    // generate input connections
    let mut connections = [0usize; 4];
    for (index, variable) in variables.enumerate() {
        connections[index] = *context.wires.get(*variable).unwrap();
    }
    let id = context.next_id++;
    let name = format!("port{}_LUT4", id);
    context.wires.insert(format!("port{}_LUT4_Z", id), id);
    Ok(LUT4 {
        name,
        initial_value,
        input_connections: connections,
        output_connections: id,
    })
}

总之就是暴力把所有可能带入 expression 求出真值表，进而算出 LUT4 的初始值，再次提醒这不是生产环境下的做法。

然后就是生成 JSON，这里只展示从 LUT4 生成 Cell 的代码：

pub struct Cell {
    name: String,
    component_type: String,
    parameters: HashMap<String, String>,
    port_directions: HashMap<String, PortDirection>,
    connections: HashMap<String, Vec<usize>>,
}

impl From<LUT4> for Cell {
    fn from(lut: LUT4) -> Self {
        let port_directions = {
            let mut m = HashMap::new();
            m.insert("A".to_string(), PortDirection::Input);
            m.insert("B".to_string(), PortDirection::Input);
            m.insert("C".to_string(), PortDirection::Input);
            m.insert("D".to_string(), PortDirection::Input);
            m.insert("Z".to_string(), PortDirection::Output);
            m
        };
        let parameters = {
            let mut m = HashMap::new();
            m.insert("INIT".to_string(), format!("{:16b}", lut.initial_value));
            m
        };

        let c = ["A", "B", "C", "D"]
            .iter()
            .zip(lut.input_connections.iter())
            .chain(["Z"].iter().zip(iter::once(&lut.output_connections)));
        let mut connections = HashMap::new();
        for (name, &id) in c {
            connections.insert(name.to_string(), vec![id]);
        }

        Self {
            name: lut.name,
            component_type: "LUT4".to_string(),
            parameters,
            port_directions,
            connections,
        }
    }
}

其他部分的实现略，唯一要注意的点就是这里 Serde 的实现有些怪异，需要自己搞，具体见代码（等我写的好一点就开源），重点就是要活用 collect_map 和 serialize_map 就是了。

Run 一下试试！

我们用我们的程序综合上面提到的代码，可以得到：

{
    "creator": "Rosys 0.1",
    "modules": {
        "Top": {
            "ports": {
                "a": {
                    "direction": "input",
                    "bits": [2]
                },
                "b": {
                    "direction": "input",
                    "bits": [3]
                },
                "port4_LUT4_Z": {
                    "direction": "output",
                    "bits": [4]
                }
            },
            "cells": {
                "port4_LUT4": {
                    "type": "LUT4",
                    "parameters": {
                        "INIT": "1000100010001000"
                    },
                    "port_directions": {
                        "A": "input",
                        "Z": "output",
                        "C": "input",
                        "B": "input",
                        "D": "input"
                    },
                    "connections": {
                        "Z": [4],
                        "A": [2],
                        "D": [0],
                        "B": [3],
                        "C": [0]
                    }
                }
            },
            "netnames": {
                "a": {
                    "bits": [2]
                },
                "b": {
                    "bits": [3]
                },
                "port4_LUT4_Z": {
                    "bits": [4]
                }
            }
        }
    }
}

然后居然就可以用 nextpnr-ecp5 搓出 config 文件，然后用 ecppack 做出 bit，然后把它烧录进 FPGA 里居然就可以用了。

我们居然这么容易就写出了一个能动的综合器。接下来将会介绍更多逻辑综合的相关内容，预定会写更复杂逻辑函数的综合和时序逻辑电路的综合。