An algorithm ofk-line location for BBL in LSI/VLSI

In this paper, aK-line location algorithm for building block cells in LSI/VLSI is presented. When the relative positions of rectangular cells are given, there are 2 states according to the two orientations of a cell. It is proved that to find the optimum solution from the 2^N states can be reduced to calculate theN states inK-line algorithm. So the algorithm is shown very effective and can be used with association for cluster method in BBL placement. Under certain conditions, this method can also be used to pesudo BBL placement directly.     

混合模拟退火算法解决VLSI布局问题

VLSI布局问题是集成电路物理设计过程中的关键步骤，它直接影响整个设计的成败。Slicing结构是一种简单而高效的布局表示方法，采用正则波兰表达式编码，将模拟退火与禁忌搜索算法结合形成了一种以模拟退火算法为基础的混合算法进行求解，用MCNC benchmarks进行实验，结果表明：文章提出的混合算法比模拟退火算法在求解效率和质量上都有较大的提高。     

VLSI电路划分问题的分散搜索算法

电路划分是超大规模集成电路(VLSI)设计自动化中的一个关键阶段,是NP困难的组合优化问题.本文把基于顶点移动的Fiduccia-Mattheyses(FM)算法结合到分散搜索算法框架中,提出了电路划分的分散搜索算法.算法利用FM算法进行局部搜索,利用分散搜索的策略进行全局搜索.为满足该方法对初始解的质量和多样性的要求,采用贪心随机自适应搜索过程(GRASP)和聚类相结合的方法产生初始解.实验结果表明,算法可以求解较大规模的电路划分实例,且与基于多级框架的划分算法hMetis相比,划分的质量有明显的提高.     

Survey on Block Matching Motion Estimation Algorithms and Architectures with New Results

Block matching motion estimation is the heart of video coding systems. During the last two decades, hundreds of fast algorithms and VLSI architectures have been proposed. In this paper, we try to provide an extensive exploration of motion estimation with our new developments. The main concepts of fast algorithms can be classified into six categories: reduction in search positions, simplification of matching criterion, bitwidth reduction, predictive search, hierarchical search, and fast full search. Comparisons of various algorithms in terms of video quality and computational complexity are given as useful guidelines for software applications. As for hardware implementations, full search architectures derived from systolic mapping are first introduced. The systolic arrays can be divided into inter-type and intra-type with 1-D, 2-D, and tree structures. Hexagonal plots are presented for system designers to clearly evaluate the architectures in six aspects including gate count, required frequency, hard-ware utilization, memory bandwidth, memory bitwidth, and latency. Next, architectures supporting fast algorithms are also reviewed. Finally, we propose our algorithmic and architectural co-development. The main idea is quick checking of the entire search range with simplified matching criterion to globally eliminate impossible candidates, followed by finer selection among potential best matched candidates. The operations of the two stages are mapped to the same hardware for resource sharing. Simulation results show that our design is ten times more area-speed efficient than full search architectures while the video quality is competitively the same. Yu-Wen Huang was born in Kaohsiung, Taiwan, in 1978. He received the B.S. degree in electrical engineering and the Ph.D. degree in electronics engineering from National Taiwan University, Taipei, in June 2000 and December 2004, respectively. He joined MediaTek, Inc., Hsinchu, Taiwan, in 2004, where he develops integrated circuits related to video coding systems. His research interests include video segmentation, moving object detection and tracking, intelligent video coding technology, motion estimation, face detection and recognition, H.264/AVC video coding, and associated VLSI architectures. Ching-Yeh Chen was born in Taipei, Taiwan, in 1980. He received the B.S. degree from the Department of Electrical Engineering, National Taiwan University, Taipei, Taiwan, in 2002. He currently is pursuing the Ph.D. degree at the Graduate Institute of Electronics Engineering, National Taiwan University. His research interests include intelligent video signal processing, global/local motion estimation, scalable video coding, and associated VLSI architectures. Chen-Han Tsai received the B.S. degree in electrical engineering from National Taiwan University in 2002. Now he is working toward the Ph.D. degree in the Graduate Institute of Electronics Engineering, National Taiwan University. His major research interests include face detection and recognition, motion estimation, H.264/AVC video coding, digital TV systems, and related VLSI architectures. Chun-Fu Shen received the B.S. and M.S. degrees in electrical engineering from National Taiwan University in 1996 and 1998, respectively. After two years of military service, he joined VIVOTEK, Inc., Taipei County, Taiwan, in 2000. He developed many video coding systems and IP camera products on DSP platforms and ASICs. His major research interests include JPEG, H.263, MPEG-4, and H.264/AVC coding systems, network camera SOC, and embedded systems. Liang-Gee Chen was born in Yun-Lin, Taiwan, in 1956. He received the B.S., M.S., and Ph.D. degrees in electrical engineering from National Cheng Kung University, in 1979, 1981, and 1986, respectively. He was an instructor (1981–1986), and an associate professor (1986–1988) in the Department of Electrical Engineering, National Cheng Kung University. In the military service during 1987 and 1988, he was an associate professor in the Institute of Resource Management, Defense Management College. From 1988, he joined the Department of Electrical Engineering, National Taiwan University. During 1993 to 1994 he was a visiting consultant of DSP Research Department, AT&T Bell Lab, Murray Hill. In 1997, he was the visiting scholar of the Department of Electrical Engineering, University, of Washington, Seattle. Currently, he is a professor of National Taiwan University. From 2004, he is also the executive vice president and the general director of Electronics Research and Service Organization (ERSO) in the Industrial Technology Research Institute (ITRI). His current research interests are DSP architecture design, video processor design, and video coding systems. Dr. Chen is a Fellow of IEEE. He is also a member of the honor society Phi Tau Phi. He was the general chairman of the 7th VLSI Design CAD Symposium. He was also the general chairman of the 1999 IEEE Workshop on Signal Processing Systems: Design and Implementation. He has served as the associate editor of IEEE Transactions on Circuits and Systems for Video Technology since 1996, the associate editor of IEEE Transactions on VLSI Systems since 1999, the associate editor of Journal of Circuits, Systems, and Signal Processing since 1999, and the guest editor of Journal of VLSI Signal Processing Systems for Signal, Image, and Video Technology since 2001. Now he is also the associate editor of IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing and the associate editor of Proceedings of the IEEE. Dr. Chen received the Best Paper Awards from ROC Computer Society in 1990 and 1994. From 1991 to 2005, he received Long-Term (Acer) Paper Awards annually. In 1992, he received the Best Paper Award of the 1992 Asia-Pacific Conference on Circuits and Systems in VLSI design track. In 1993, he received the Annual Paper Award of Chinese Engineer Society. In 1996, he received the Outstanding Research Award from National Science Council (NSC) and the Dragon Excellence Award from Acer. He was elected as the IEEE Circuits and Systems Distinguished Lecturer from 2001–2002.     

Design of a Cellular Architecture for Fast Computation of the Skeleton

This paper presents a new algorithm to extract the skeleton and its Euclidean distance values from a binary image. The extracted skeleton reconstructs the objects in the image exactly. The algorithm runs in O(n) time for an image of size n × n. It involves simple local neighborhood operations for each pixel and hence it is quite amenable to VLSI implementation in a cellular architecture. Results of simulation of the algorithm in a sequential computer are presented. Results of implementation of a VLSI design in Xilinx FPGA are also presented and they confirm the speed and suitability of our method for real-time applications.     

A greedy switch-box router

The greedy channel router of Rivest and Fiduccia is extended into an efficient switch-box router. The algorithm is based on two simple operations called join-split-nets and jog-to-right-target derived from the channel router. Terminals are on the boundary of a rectangular region, and the router uses two orthogonal layers of wires to generate the solution. The router always succeeds in finding a solution by inserting sufficient horizontal and vertical tracks in case of insufficient routing area. The result is generated through a single column-wise scan across the routing region. The expected running time is proportional to M(N + N_net), where M, N and N_net are respectively the number of columns, rows and nets in the region. The scan direction is crucial to the algorithm and we have proposed good heuristic which is based on the augmented channel density distribution in finding it. Results from a number of examples are evaluated. The implemented router is designed for assembling custom VLSI designs, it works in parallel with other tools such as a layout editor via a simple interface. The router output is in CIF.     

Efficient programmable power‐of‐two scaler for the three‐moduli set {2n+p, 2n − 1, 2n+1 − 1}

Scaling is an important operation because of the iterative nature of arithmetic processes in digital signal processors (DSPs). In residue number system (RNS)–based DSPs, scaling represents a performance bottleneck based on the complexity of inter‐modulo operations. To design an efficient RNS scaler for special moduli sets, a body of literature has been dedicated to the study of the well‐known moduli sets {2ⁿ ? 1, 2ⁿ, 2ⁿ + 1} and {2ⁿ, 2ⁿ ? 1, 2ⁿ⁺¹ ? 1}, and their extension in vertical or horizontal forms. In this study, we propose an efficient programmable RNS scaler for the arithmetic‐friendly moduli set {2^n+p, 2ⁿ ? 1, 2ⁿ⁺¹ ? 1}. The proposed algorithm yields high speed and energy‐efficient realization of an RNS programmable scaler based on the effective exploitation of the mixed‐radix representation, parallelism, and a hardware sharing technique. Experimental results obtained for a 130 nm CMOS ASIC technology demonstrate the superiority of the proposed programmable scaler compared to the only available and highly effective hybrid programmable scaler for an identical moduli set. The proposed scaler provides 43.28% less power consumption, 33.27% faster execution, and 28.55% more area saving on average compared to the hybrid programmable scaler.     

遗传算法应用于VLSI布局的研究

本文是应用遗传算法实现ＶＬＳ门阵列模式布局,从建立相应的数学模型入手,提出一个较完备的综合布局目标函数,引入通道拥挤度的概念,从而改变了传统的常以总线长度或刻线数目的单一目标函数,使布局的构形更趋合理。在遗传３参数选取方面,提出了几种改善收性的措施,大大加快了遗传算法的收敛速度。     

一种新的基于遗传算法的快速运动估计方法

本文提出了一种新的基于遗传算法的快速运动估计方法.该方法对遗传算法进行了改进,采用"阈值法"确定选择算子,并将基因变异所导致的随机搜索与特定目标搜索相结合,解决了以往快速搜索算法易陷于局部最优的问题,大大提高了运动估计速度.该方法还将运动矢量空间一致性原则用于初始种群的选取,进一步提高了算法性能.由于其具备遗传算法固有的规则性和高度并行性,该方法适合于采用VLSI实现实时视频编码器.     

An efficient multiple shortest augmenting paths algorithm for constructing high performance VLSI subarray

Reconfiguring a high-performance subarray of a VLSI array with faults is to construct a maximum target array with the minimum number of long interconnects, which can reduce communication costs, capacitance and dynamic energy dissipation. An existing work proved that the high performance VLSI subarray can be constructed in polynomial time using network flow algorithm. However, because of the disadvantage of the previous network model and the low-performing of standard network flow algorithms for reconfiguration, the efficiency of these algorithms is poor for constructing the high performance VLSI subarray. In this paper, we present an efficient multiple shortest augmenting paths algorithm for rapidly constructing high performance VLSI array. Firstly, we proposed an efficient data structure to construct the network model of the VLSI array with faults, which can dramatically reduce the size of the model compared with previous algorithm. Secondly, a multiple shortest augmenting path algorithm based on the new data structure is proposed, which can significant reduce the running time. Finally, we conduct solid experiments to highlight the efficiency of the proposed method in terms of the running time compared to the standard network flow algorithms. The experimental results show that on a 64 × 64 host array with 0.1% faults, the size of the network model can be reduced by about 50% and the average improvements in running time is up to 85.10% compared with four standard network flow algorithms.     

一种快速高效MPEG-4运动估计硬件结构的研究和实现

提出一种高度并行和多流水线处理的硬件结构,实现MPEG-4视频部分的全搜索块匹配运动估计算法.该硬件结构能实时地通过全搜索块匹配运动估计算法来搜索每个像素块最佳匹配运动向量,具有计算速度高、运动向量准确、较少的内置存储器要求、低运行时钟和低功耗等诸多优点,从而可满足移动视频业务和高清晰视频业务的需求.该硬件结构基于富士通的CE66库实现.     

用可变形模板进行基于内容的图像分割算法

 本文提出一种采用可变形模板匹配技术进行基于内容的图像分割算法.通过预先计算出可变形模板沿着变形的正交曲线,并对模板曲线及正交曲线进行离散抽样,建立一基于正交曲线的二维(2-D)可变形模板,针对图像分割问题定义控制可变形模板进行变形的内、外部能量函数,本文采用遗传算法搜索能量函数最小的全局最优解.该新算法比传统的可变形模板匹配方法降低了搜索空间的维数,减少了算法对模板初始位置的敏感.对实际图像及模拟低信噪比图像处理的结果表明,新算法具有良好的分割精度及稳定性.     

基于节点搜索的可变形块运动补偿

本文讨论可变形块匹配(DBMA)的运动补偿和预测方法,提出基于节点搜索的可变形块匹配算法(NS-DBMA),并在此基础上提出分数像素精度预测和双模式混合预测方法.实验结果表明,NS-DBMA比全搜索方块匹配法(EBMA)平均改善约2dB;其运算量仅为基于梯度的可变形块匹配算法(GB-DBMA)的一半,但能得到更好的主客观预测质量,且更易于VLSI硬件实现.     

Analysis of Application of the IDDQ Technique to the Deep Sub-Micron VLSI Testing

In this work, IDDQ current for the deep sub-micron VLSI in year 2011 is estimated with a statistical approach according to the International Technology Roadmap for Semiconductors 1999 Edition considering process variations and different input vectors. The estimated results show that the standard deviation of the IDDQ current is proportional to the square root of the circuit size and the IDDQ currents of the defect-free and the defective devices, which are of the size up to 1 × 10⁷ gates, are still differentiable under the condition of random process deviations and input vectors. Two new IDDQ testing schemes, which detect the defective current based on the two separate IDDQ distributions, are proposed. From the study, it is concluded that IDDQ testing is still applicable for the deep sub-micron VLSI for the next ten years.     

并行算法在VLSICAD中的应用

本文简介并算法在ＶＬＳＩＣＡＤ中的应用，介绍了这一领域的研究现状，所采用的关键技术以及进一步的研究发展方向。     

一种矢量编码器的VLSI结构

我们提出了一种基于最小绝对值误差测试（ＭＭＡＥ）矢量编码器的ＶＬＳＩ结构，这一结构采用了误差测度的值不等式判据、预排序的码书和最近邻搜索算法，并采用二分搜索方法和特殊的误差测度计算及比较结构，大大降低了系统的实现规模，同时采用并行流水线等设计技术，可以获得每８个时钟周期编码一个矢量的处理速度。整个系统采用硬件描述语言ＶＨＤＬ和Ｓｙｎｏｐｓｙｓ系统中进行了设计验证和综合。     

一种VLSI设计到赋权超图的转换系统

本文基于VLSI划分问题的需要,提出了一种VLSI设计到赋权超图转换算法.该算法解决的关键问题是,它读取和遍历Verilog语言描述的树状结构VLSI设计,将其转换为赋权超图并存储为指定的文件存储格式,从而有效地将VLSI划分问题转换为超图划分优化问题.进而,本文给出了VLSI设计到赋权超图的转换系统（VLSI/Hypergraph Converter,VHC）的处理流程图,并在Windows平台下用C＋＋设计实现了VHC系统.实验及分析表明,该系统能正确地将Verilog语言描述的门级CPU测试用例转换为赋权超图,避免了直接在VLSI线网上进行划分,提高了VLSI划分的效率.     

通用多层区域布线算法

文中提出了一种多用途的ＶＬＳＩ多层区域详细布线算法，该算法使用模拟进化技术进行拆线重布线，对单一网使用改进型多层迷宫算法进行布线。实验结果证明，运算法能得到较好的布线。     

A VLSI-oriented algorithm and its implementation for AVS chroma interpolation

AVS (audio video coding standard) is the latest multimedia coding standard of China. Similar to H.264/AVC, AVS adopted the technology of fractional-pel-accurate motion compensation, which enhanced the compression efficiency. To obtain fractional pels, 4-tap FIR filters and bilinear filters are used for luma and chroma interpolation respectively. Unlike the VLSI-optimized FIR filters which could be implemented by adders and shifters, the bilinear filter for chroma is not so convenient for direct VLSI implementation due to its multiplications. In this paper, we propose a VLSI-oriented algorithm named SHAM (x–y-separated halved-approaching method) to accomplish the bilinear filtering. The proposed SHAM algorithm adopts a halved-approaching method which is an addition-and-shift-only method and with simpler data path. VLSI structures are also provide to implement the SHAM algorithm in this paper. Experiments based on UMC $0.18\mathrm{\mu }\mathrm{m}$ process show that the SHAM algorithm could be implemented with about 48% less silicon area or at doubled frequency compared with the direct implementation of the bilinear filter.     

An area-efficient very large scale integration architecture for modified Euclidean algorithm with dynamic storage technique

A Modified Euclidean (ME) algorithm has been used to solve the key equations in Reed-Solomon (RS) decoding. In this article, the degree properties of the ME algorithm are derived. On the basis of the degree properties, an area-efficient very large scale integration (VLSI) architecture with dynamic storage technique is proposed to perform the ME algorithm. The dynamic storage technique is used to avoid data exchange and save hardware resources. The proposed architecture with dynamic storage technique can reduce 50% computation hardware area and about 30% memory hardware area. VLSI implementation results of different RS codes show that the proposed architecture is significantly area-efficient, especially for RS codes with long code lengths.