Computational model for VLSI systems

超大规模集成电路的技术发展使得超大规模集成电路作为大型计算系统的重要组成部分。在本报告中，我们探索了一个超大规模集成电路的计算模型，该模型反映了超大规模集成电路的计算潜力，表征了超大规模集成电路的性能，并开发了实现高效算法的设计技术。在工程中得到的结果如下：在第一章中，我们将要解决的计算问题建模为一个有向无环图，节点对应计算值，弧表示依赖关系。在本章中，我们在计算一组依赖关系形成网格的值所需的通信时间和计算时间之间得到了一个重要的权衡。将图模型用于计算问题，可以将设计高效算法的问题简化为构造具有某种性质的图的问题。在文献中证明了最优排序算法是利用二部图（称为展开图）得到的，并进一步证明了连通性的一些性质。第二章给出了显式构造展开器的一种方法。第三章证明了对于任何一维线性映射的有限集，其连通性由线性映射定义的二部图不是展开式。第四章研究了基于元胞自动机的硬件算法。第五章讨论了逻辑函数放大的概念，给出了实现一定放大的布尔公式大小的上界和下界。进一步证明，利用布尔公式可以有效地实现一定的放大，从而可以构造小尺寸的阈值函数。随着超大规模集成电路芯片尺寸的增加，它们被分解成子电路，以保持每个设计人员可管理的总体复杂性。第6章处理估计布尔电路的最小子电路数的问题，以计算给定的布尔函数，以子电路之间的互连是有限的方式划分。第七章讨论了基于< lambda >-表示法的硬件验证系统。第8章讨论布尔函数的学习算法。最后，第九章研究了一种从伪随机函数生成器构造伪随机可逆许可生成器的有效方法。少

Technological evolution of VLSI makes VLSI circuits very important as components in large scale computing systems. In this report we explore a model of computation for VLSI, which reflects computational potential of VLSI, characterize performance of VLSI, and develop design technique to implement efficient algorithms. The results obtained in the project are as follows. In Chapter 1, we model the computational problem to be solved as a directed acyclic graph, with nodes corresponding to computed values, and arcs denoting dependencies. In this chapter we obtain a nontrivial trade-off between the communication time and computation time required to compute a collection of values whose dependencies form a grid. Using the graph model for computational problems, we can reduce the problem of designing efficient algorithms to the one of constructing graphs with some property. In literature it is shown that the optimal sorting algorithm is obtained by using bipartite graphs, called expanders, wi … More th some property on the connectivity. Chapter 2 gives a way of constructing the expanders explicitly. In Chapter 3 it is proved that, for any finite set of one-dimensional linear mappings, the bipartite graphs whose connectivity is defined by the linear mappings are not expanders. In Chapter 4, hardware algorithms based on cellular automata are surveryed. Chapte 5 discusses on the notion of amplification of logical functions and gives upper and lower bounds on the size of Boolean formula to realize certain amplification. Furthermore, it is shown that, using the Boolean formula which realize certain amplification efficiently, we can construct threshold functions with small size. As the size of VLSI chips increases, they are broken down into subcircuits to keep the total complexity inthe scope of each individual designer manageable. Chapter 6 deals with the problem of estimating the minimum number of the subcircuits of a Boolean circuits, to compute a given Boolean function, partitioned in a manner that interconnections between subcircuits are limited. Chapter 7 discusses about a hardware verification system based upon <lamdda>-notation. Chapter 8 deals with learning algorithms for Boolean functions. Finally, Chapter 9 studies a method for efficiently constructing a pseudo-random invertible permita-tion generator from a pseudo-random function generator. Less