Computing transitive closure on systolic arrays of fixed size

Summary Forming the transitive closure of a binary relation (or directed graph) is an important part of many algorithms. When the relation is represented by a bit matrix, the transitive closure can be efficiently computed in parallel in a systolic array.Here we propose two novel ways of computing the transitive closure of an arbitrarily big graph on a systolic array of fixed size. The first method is a simple partitioning of a well-known systolic algorithm for computing the transitive closure. The second is a block-structured algorithm. This algorithm is suitable for execution on a systolic array that can multiply fixed size bit matrices and compute transitive closure of graphs with a fixed number of nodes. The algorithm is, however, not limited to systolic array implementations; it works onany parallel architecture that can perform these bit matrix operatons efficiently.The shortest path problem, for directed graphs with weighted edges, can also be solved in the same manner, devised above, as the transitive closure is computed. Björn Lisper was born in 1956 in Solna, Sweden. He received the M. Eng. Physics degree in 1980 and the Ph.D. degree in Computer Science in 1987, both from the Royal Institute of Technology in Stockholm. Currently he shares his time between the Royal Institute of Technology and the Swedish Institute of Computer Science. His research interests are mainly in the area of formal methods for deriving efficient parallel implementations of algorithms, including synthesis of fixed hardware structures for specific algorithms and compilation techniques for tightly coupled parallel systems. Dr. Lisper is a member of the European Association for Theoretical Computer Science.     

On high-speed computing with a programmable linear array

It has been observed by many researchers that systolic arrays are very suitable for certain high-speed computations. Using a formal methodology, we present a design for a single simple programmable linear systolic array capable of solving large numbers of problems drawn from a variety of applications. The methodology is applicable to problems solvable by sequential algorithms that can be specified as nested for-loops of arbitrary depth. The algorithms of this form that can be computed on the array presented in this paper include 25 algorithms dealing with signal and image processing, algebraic computations, matrix arithmetic, pattern matching, database operations, sorting, and transitive closure. Assuming bounded I/O, for 18 of those algorithms the time and storage complexities are optimal, and therefore no improvement can be expected by using dedicated special-purpose linear systolic arrays designed for individual algorithms. We also describe another design which, using a sufficient large local memory and allowing data to be preloaded and unloaded, has an optimal processor/time product.An earlier version of this paper was presented at Supercomputing '88.This work was partially supported by ONR under the contract N00014-85-K-0046 and by NSF under Grant Number CCR-8906949.     

High performance set associative translation lookaside buffers for low power microprocessors

A fast low power four-way set-associative translation lookaside buffer (TLB) is proposed. The proposed TLB allows single clock phase accesses at clock frequencies above 1 GHz. Comparisons to a conventional fully associative CAM tagged TLB, which is the type most commonly used in embedded processors, with the same number of entries on a 65 nm low standby power process show that the proposed design has 28% lower delay and up to 50% lower energy delay product. Unlike previous set-associative TLBs, which replicate the TLB to support multiple page sizes, multiple page sizes are supported on a way-by-way basis. Alternative conventional CAM tagged and set-associative TLBs are investigated with regard to access latency, power dissipation and hit rates.     

Fault-tolerance in balanced sorting networks

Much research has been done on sorting networks but there are very few results concerning their robustness. Our starting point is the balanced sorting network introduced by Dowd et al. and its single-block robust design of Rudolph obtained at the cost of some redundancy and two permuters external to the network. In this article we introduce a new implementation which is more robust than Rudolph's network and needs no redundancy or external permuters. We also consider a class of single-stage designs with redundancy and compare the characteristics of networks discussed.     

小波图像编码的VLSI实现

设计了一种模块化的二维离散小波变换(2-D DWT)的VLSI结构.该结构可以实时完成小波变换,且很容易扩展.针对零树编码硬件实现方面的不足,利用一种简单的顺序扫描方式和两个标志阵列,设计了一种适合硬件实现的快速零树编码算法(FZIC)和FZIC硬件实现的VLSI结构,编写了2-D DWT和FZIC硬件结构的Veri log HDL模型,并进行了仿真和逻辑综合.结合2-D DWT和FZIC,实现了小波图像编码系统 ,并用ALTERA CPLD成功进行了验证.     

Area-time lower-bound techniques with applications to sorting

Thearea-time complexity of VLSI computations is constrained by the flow and the storage of information in the two-dimensional chip. We study here the information exchanged across the boundary of the cells of asquare-tessellation of the layout. When the information exchange is due to thefunctional dependence between variables respectively input and output on opposite sides of a cell boundary, lower bounds are obtained on theAT ² measure (which subsume bisection bounds as a special case). When information exchange is due to thestorage saturation of the tessellation cells, a new type of lower bound is obtained on theAT measure.In the above arguments, information is essentially viewed as a fluid whose flow is uniquely constrained by the available bandwidth. However, in some computations, the flow is kept below capacity by the necessity to transform information before an output is produced. We call this mechanismcomputational friction and show that it implies lower bounds on theAT/logA measure.Regimes corresponding to each of the three mechanisms described above can appear by varying the problem parameters, as we shall illustrate by analyzing the problem of sortingn keys each ofk bits, for whichAT ²,AT, andAT/logA bounds are derived. Each bound is interesting, since it dominates the other two in a suitable range of key lengths and computations times.This work was supported in part by the National Science Foundation ECS-84-10902, by an IBM predoctoral fellowship, and by the Joint Services Electronics Program under Contract N00014-84-C-0149. A preliminary version was presented at the 19th Conference on Information Sciences and Systems.     

Preparation of cross-sectional transmission electron microscopy samples by electron beam lithography and reactive ion etching

A cross-sectional sample preparation technique is described that relies on lithographic and dry-etching processing, thus avoiding metallographic polishing and ion milling. The method is capable of producing cross-sectional transmission electron microscopy samples with a large amount of transparent area (1 μm × 2.5 mm) which allows the examination of many patterned test sites on the same sample from the same chip of a silicon wafer. An example of the application of the technique is given for localized oxidation through a mask.     

基于DCT子空间失真测度的矢量量化VLSI结构设计

本文提出了一种实现离散余弦变换子空间失真测度矢量编码算法的ＶＬＳＩ结构。     

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

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

一种新的使用两种比特分辨率图象的块匹配运动估计算法及其低功耗VLSI结构

本文给出了一种新的块匹配运动估计算法,它根据视频图像内容的复杂程度自适应地选择常规的或者低比特分辨率的图像来进行块匹配,并且采用了一种混合使用两种比特分辨率图像的新望远镜搜索算法.模拟结果表明,新算法具有较低的计算复杂性,并且能够保证较好的视频质量.基于该算法,我们设计了一种新的脉动阵列结构的搜索引擎.该引擎具有可分割的数据通道,从而在使用低比特分辨率图像进行块匹配时能够通过加强处理的并行性来提高吞吐率.新的运动估计器可工作在较低的时钟频率和电源电压之下,具有低的功耗消耗.