Decomposition of large-scale Programmable logic arrays

任意逻辑功能可由与或两级电路实现。在集成电路中，两级电路通常被实现为可编程逻辑阵列(PLA)。由于PLA具有规则的结构，因此它们易于设计、易于修改和易于测试。因此，最近的超大规模集成(VLSI)在其控制部件中使用大型PLA。然而，PLA越大，阵列中的连接就越稀疏，即大型PLA往往会浪费硅片面积，解决这一问题的方法之一是对PLA进行分解，即用多个较小的PLA来实现给定的功能。PLA的分解可以分为两种类型：串联分解和并行分解。在第一类分解中，在序列分解中，输入变量被分成两组，第一组实现中间功能，第二组实现期望功能。在第二种类型的分解中，在并行分解中，输出函数被划分为两组，并且每个解放军独立地实现每组。由于这两种类型的分解都可以使PLA的总尺寸小于原始的PLA，所以它们经常被用于现代微处理器中。在本研究中，我们考虑了PLA的串行和并行分解，当分解的PLA的总尺寸小于原始的PLA的总尺寸时，串行分解是有效的。实验结果表明，串联分解使聚乳酸的总尺寸减小了10%~30%。对于并行分解，最优的分解是具有最小延迟的分解，其中我们假设PLA的延迟与乘积项的数目成正比。我们开发了PDEC，这是一个找到接近最佳分解的交互工具。我们使用PDEC将许多算法和控制PLA分解成两个。在控制电路的情况下，我们得到了平均35%的延迟和6%的总阵列面积的PLA。

An arbitrary logic function can be realized by an AND-OR two-level circuit. In integrated circuits, two-level circuits are often realized as programmable logic arrays(PLA's). Because PLAs have regular structure, they are easy to design, easy to modify, and easy to test. Thus, recent VLSIs(very large scale integrations) use large PLAs in their control parts. However, the larger PLAs, the more sparse the connections in the arrays: i.e., large PLAs tend to waste silicon chip area.One method to solve this problem is decomposition of PLAs, i.e., to realize given functions by using several smaller PLAs. Decomposition of PLAs can be classified into two types: serial decomposition and parallel decomposition. In the first type of the decomposition, in a serial decomposition, the input variables are partitioned into two groups, and the first PLA realizes intermediate functions and the second PLA realizes desired function. In the second type of the decomposition, in a parallel decomposition, the output functions are partitioned into two groups, and each PLA realizes each group independently. Because both types of decompositions can make total size of PLAs smaller than original ones, they are often used in modern micro processors.In this research, we considered the serial and parallel decompositions of PLA's. Serial decompositions are effective when the total size of the decomposed PLA's is smaller than original one. Experimental results show that the serial decomposition reduce the total PLA size by 10 to 30 percents. As for parallel decomposition, the optimum decomposition is one with minimum delay, where we assume that the delay of the PLA is proportional to the number of product terms. We developed PDEC, an interactive tool to find a near optimum decomposition. We decomposed many arithmetic and control PLAs into two by using PDEC. We obtained PLAs with, on the average, 35% smaller delay and 6% less total array area in the case of control circuits.