权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Basic Research on High-Speed Boolean Function Manipulator

高速布尔函数操纵器的基础研究

基本信息

批准号：
05452352
负责人：
YAJIMA Shuzo
金额：
$ 4.35万
依托单位：
KYOTO UNIVERSITY
依托单位国家：
日本
项目类别：
Grant-in-Aid for General Scientific Research (B)
财政年份：
1993
资助国家：
日本
起止时间：
1993 至 1994
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-05452352/
关键词：
Boolean Function Binary Decision Diagram Boolean Function Manipulation Computer Aided Logic Design Prallel Algorithm Computational Complexity Content Addressable Memory Combinatorial Problem 形式的設計検証

项目摘要

We have carried out basic research on high-speed manipulation of Boolean functions based on binary decision diagrams.1.Algorithms and Complexity of Manipulating Binary Decision DiagramsWe have propsed highly parallel algorithms for reduction and Booleam operations, which are basic Boolean function manipulation based on binary decision diagrams (BDDs), and clarified their computational complexity. On the expressive power of BDDs, we have defined the class of Boolean functions expressible by polynomial size BDDs and compared it with the classes based on Turing machines. We have also studied on the size of BDDs representing threshold functions.2.High-Speed Boolean Function ManipulatorWe have propsed and experimented a method using secondary memory to manipulate very large shared BDDs (SBDDs) which cannot be stored in the main memory. Breadth-first manipulation of SBDDs is adopted in this method. We have also developed a parallel method to manipulate SBDDs on content sddressable memories (CAMs). It seems that very high parallelism can be realized using CAMs.3.Computer Aided Logic Design Based on Boolean ProcessingWe have applied Boolean function manipulation based on SBDDs to computer aided logic design, First, we proposed a method to generate compace test sequences for scan-based seaquential circuits. The second one is the application to the several state assignment methods for asynchronous sequential circuits. As an application for the problems not in the field of logic design, we have proposed some methods to solve combinatorial problems using Boolean processing.

我们对基于二元决策图的布尔函数的高速运算进行了基础研究。1.二元决策图运算的算法和复杂性我们提出了基于二元决策图的基本布尔函数运算--约简和布尔运算的高度并行化算法，并阐明了它们的计算复杂性。在BDDS的表示能力方面，我们定义了可用多项式大小BDDS表示的布尔函数类，并将其与基于图灵机的类进行了比较。2.高速布尔函数管理器我们提出并实验了一种使用辅助内存来处理无法存储在主内存中的超大共享BDd(SBDd)的方法。该方法采用广度优先的方法处理SBDDS。我们还开发了一种并行方法来操作内容可寻址存储器(CAM)上的SBDD。基于布尔处理的计算机辅助逻辑设计我们将基于SBDDS的布尔函数运算应用到计算机辅助逻辑设计中，首先，我们提出了一种生成基于扫描的海洋电路的紧凑测试序列的方法。二是对异步时序电路的几种状态分配方法的应用。作为对非逻辑设计领域问题的应用，我们提出了一些利用布尔处理来解决组合问题的方法。