Optimal algorithms for adjacent side routing

We consider the switchbox routing problem of two-terminal nets in the case when all thek nets lie on two adjacent sides of the rectangle. Our routing model is the standard two-layer model. We develop an optimal algorithm that routes all the nets whenever a routing exists. The routing obtained uses the fewest possible number of vias. A more general version of this problem (adjacent staircase) is also optimally solved.This research was supported in part by NSA Contract No. MDA-904-85H-0015, NSF Grant No. DCR-86-00378, and by NSF Engineering Research Centers Program NSFD CDR 88003012.     

Motion Perception Using Analog VLSI

Motion perception is arguably a fundamental mechanism used by natural species to accomplish a number of tasks, such as navigating freely in an unknown environment. Traditional motion perception methods tend to be computationally intensive, requiring powerful computers and large memories. However, by copying biological mechanisms, such as elementary motion discrimination at the early stages of the visual processing paths, it should be possible to build small and efficient motion perception systems. This paper describes the manner in which a simple motion perception model based on the insect visual system has been implemented using mixed analog/digital VLSI. The device has been fabricated in a 2 micron double metal, double polysilicon process, and comprises 61 photo-detectors, and associated analog and digital circuitry. While not entirely successful in that component mismatches hamper the detection of dark-to-bright changes in contrast, the results clearly show the feasibility of using such a device in autonomous control systems.     

用边界元法提取VLSI版图电阻

介绍了ＶＬＳＩ版图验证中电阻提取的基本原理和主要方法，给出了一种新颖的基于边界元法的电阻提取算法。该算法采用变节点单元，较好地解决了实际问题中经常出现的角点问题。通过应用该算法对几个实例进行提取，证明使用本文的算法不仅在精度上而且在占用ＣＰＵ时间上都取得了令人满意的效果     

Rank order filters and priority queues

Summary A derivation of a parallel algorithm for rank order filtering is presented. Both derivation and result differ from earlier designs: the derivations are less complicated and the result allows a number of different implementations. The same derivation is used to design a collection of priority queues. Both filters and priority queues are highly efficient: they have constant response time and small latency. Anne Kaldewaij received an M.Sc. degree in Mathematics from the University of Utrecht (The Netherlands) and a Ph.D. degree in Computing Science from the Eindhoven University of Technology. Currently, he is associate professor in Computing Science at Eindhoven University. His research includes parallel programming and the design of algorithms and data structures. He enjoys teaching and he has written a number of textbooks on mathematics and programming. Jan Tijmen Udding received an M.Sc. degree in Mathematics in 1980 and a Ph.D. degree in Computing Science in 1984 from Eindhoven University of Technology. Currently, he is associate professor at Groningen University. His main research interests are mathematical aspects of VLSI, program derivation and correctness, and functional programming.     

CADRE: An Asynchronous Embedded DSP for Mobile Phone Applications

Asynchronous design techniques have a number of compelling features that make them suited for complex system on chip designs. However, it is necessary to develop practical and efficient design techniques to overcome the present shortage of commercial design tools. This paper describes the development of CADRE (Configurable Asynchronous DSP for Reduced Energy), a 750K transistor, high performance, low-power digital signal processor IP block intended for digital mobile phone chipsets. A short time period was available for the project, and so a methodology was developed that allowed high-level simulation of the design at the earliest possible stage within the conventional schematic entry environment and simulation tools used for later circuit-level performance and power consumption assessment. Initial modeling was based on C behavioral models of the various data and control components, with the many asynchronous control circuits required automatically generated from their specifications. This has enabled design options to be explored and unusual features of the design, such as the Register Bank which is designed to exploit data access patterns, are presented along with the power and performance results of the processor as a whole.     

A reconfigurable VLSI-based double-lens tracking camera

Watching and tracking an object while seeing a much wider view is one of advantages of the eye system. We proposed and developed a tracking camera system that mimics the eyes by using double-lens modules. In the system, a wide view is captured through the wide-lens module, while the target in it is tracked and magnified through the telescopic lens module. Electronic circuits for tracking control are implemented onto the reconfigurable VLSI or FPGA in order to embed the parallelism in the tracking algorithm into the hardware. A successfully developed FPGA-based prototype performs high-speed tracking at the video-rate. This work was present in part at the 12th International Symposium on Artificial Life and Robotics, Oita, Japan, January 25–27, 2007     

On problem transformability in VLSI

The two basic performance parameters that capture the complexity of any VLSI chip are the area of the chip,A, and the computation time,T. A systematic approach for establishing lower bounds onA is presented. This approach relatesA to the bisection flow, . A theory of problem transformation based on , which captures bothAT ² andA complexity, is developed. A fundamental problem, namely, element uniqueness, is chosen as a computational prototype. It is shown under general input/output protocol assumptions that any chip that decides ifn elements (each with (1+)lognbits) are unique must have =(nlogn), and thus, AT²=(n ²log² n), andA= (nlogn). A theory of VLSI transformability reveals the inherentAT ² andA complexity of a large class of related problems.This work was supported in part by the Semiconductor Research Corporation under contract RSCH 84-06-049-6.     

一种实时低成本压缩算法的VLSI实现

针对传统视频图像压缩算法时延长和成本高的问题,提出一种新的无损/近无损视频压缩算法。该算法由码率控制器和熵编码器组成,其中码率控制器通过对已有信息进行分析（上下文）来确定当前宏块的可用比特数,然后根据大量实验得出的高效Huffman码表,并结合位平面编码器对残差进行编码。实验结果表明,文中提出的视频图像压缩算法能够工作在300 MHz,吞吐量最差为1.3 pixel/cycle,同时仅用一块120＊720的SRAM来存储上一行像素值,因此很好地解决了时延和成本问题。     

VLSI布局算法分析

布局是VLSI物理设计阶段的关键步骤,用于确定模块在芯片上的位置,随着电路设计复杂度不断提高,高效的自动布局算法变得愈发重要。对布局问题进行了描述,总结了布局算法中常用的线长模型,分析了传统的3类布局算法及可布线性驱动的布局算法,并给出了布局算法的未来发展趋势。     

Probabilistic Bit Stream Neural Chip: Theory

A design for a neural network chip is proposed using probabilistic bit streams to represent real values. This paper analyzes the performance of the proposed neurons in this design and demonstrates that very simple operations can be used to obtain the desired functionality. It is also shown that a suitable ‘activation function’ for neurons of this type can be obtained using the interaction of two probability distributions. Finally, the paper introduces a variant of the back-propagation learning algorithm which involves computing the derivatives of the output with respect to individual weights in a network of such units.