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

Computational model for VLSI systems

VLSI 系统的计算模型

基本信息

批准号：
60550252
负责人：
MARUOKA Akira
金额：
$ 0.83万
依托单位：
TOHOKU UNIVERSITY
依托单位国家：
日本
项目类别：
Grant-in-Aid for General Scientific Research (C)
财政年份：
1985
资助国家：
日本
起止时间：
1985 至 1987
项目状态：
已结题

项目摘要

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

超大规模集成电路技术的发展使得超大规模集成电路成为大规模计算系统中非常重要的部件。在这份报告中，我们探讨了一个模型的计算超大规模集成电路，它反映了计算潜力的超大规模集成电路，表征性能的超大规模集成电路，并开发设计技术来实现有效的算法。项目取得的成果如下。在第一章中，我们将待解决的计算问题建模为有向无环图，节点对应于计算值，弧表示依赖关系。在这一章中，我们得到了一个非平凡的通信时间和计算时间之间的权衡，计算一个值的集合，其依赖关系形成一个网格。利用计算问题的图模型，可以将设计有效算法的问题归结为构造具有某种性质的图的问题。在文献中，它表明，最佳排序算法是通过使用二分图，称为扩张， ...更多信息这是关于连通性的一些性质。第二章给出了显式构造扩展器的方法。在第三章中，我们证明了对于任何一维线性映射的有限集，其连通度由线性映射定义的二部图不是扩张图。第四章介绍了基于元胞自动机的硬件算法。第五章讨论了逻辑函数放大的概念，给出了实现一定放大的布尔公式的大小的上、下界。此外，还证明了利用有效实现一定放大的布尔公式，可以构造尺寸较小的阈值函数。随着超大规模集成电路芯片尺寸的增加，它们被分解成子电路，以保持每个设计人员可管理的范围内的总复杂性。第6章讨论了一个布尔电路的最小子电路数的估计问题，以计算一个给定的布尔函数，以有限的方式划分子电路之间的互连。第七章讨论了一个基于符号的硬件验证系统<lamdda>.第8章讨论布尔函数的学习算法。最后，第九章研究了由伪随机函数生成器构造伪随机可逆混沌生成器的方法。少