School of Interactive Computing, Georgia Institute of Technology, Atlanta, GA 30308-0760, USA.
IEEE Trans Vis Comput Graph. 2011 Sep;17(9):1337-51. doi: 10.1109/TVCG.2010.232.
An Expanded Boolean Expression (EBE) does not contain any XOR or EQUAL operators. The occurrence of each variable is a different literal. We provide a linear time algorithm that converts an EBE of n literals into a logically equivalent Ordered Boolean List (OBL) and show how to use the OBL to evaluate the EBE in n steps and O(log log n) space, if the values of the literals are each read once in the order prescribed by the OBL. (An evaluation workspace of 5 bits suffices for all EBEs of up to six billion literals.) The primary application is the SIMD architecture, where the same EBE is evaluated in parallel for different input vectors when rendering solid models on the GPU directly from their Constructive Solid Geometry (CSG) representation. We compare OBL to the Reduced Ordered Binary Decision Diagram (ROBDD) and suggest possible applications of OBL to logic verification and to circuit design.
扩展布尔表达式 (EBE) 不包含任何异或或等于运算符。每个变量的出现都是一个不同的文字。我们提供了一种线性时间算法，将 n 个文字的 EBE 转换为逻辑等效的有序布尔列表 (OBL)，并展示了如何使用 OBL 在 n 步和 O(log log n) 空间内评估 EBE，如果按照 OBL 规定的顺序一次读取每个文字的值。（对于多达 60 亿个文字的所有 EBE，一个 5 位的评估工作区就足够了。）主要应用是 SIMD 体系结构，其中在 GPU 上直接从其构造实体几何 (CSG) 表示渲染实体模型时，为不同的输入向量并行评估相同的 EBE。我们将 OBL 与简化有序二进制决策图 (ROBDD) 进行了比较，并提出了 OBL 在逻辑验证和电路设计中的可能应用。
