Image processing with VLSI

The development and implementation of systems for the more complex realtime image processing and scene understanding tasks, such as robot vision and remote surveillance, calls for faster computation than that possible using the traditional serial computer. The advent of VLSI has made feasible the consideration of more specialized processing architectures, designed to support these datarates, while keeping systems compact and relatively cheap. Two approaches are discussed: the use of a programmable processor array, and the customizing of image processing algorithms in silicon. This paper examines designs based upon each approach in the light of the techniques and constraints of VLSI. In particular we describe in some detail an example of a VLSI parallel array processor, the Grid (GEC rectangular image and data processor), and a number of special-purpose CMOS/SOS chips based on systolic design techniques.     

A Tale of Two Classifier Systems

This paper describes two classifier systems that learn. These are rule-based systems that use genetic algorithms, which are based on an analogy with natural selection and genetics, as their principal learning mechanism, and an economic model as their principal mechanism for apportioning credit. CFS-C is a domain-independent learning system that has been widely tested on serial computers. CFS is a parallel implementation of CFS-C that makes full use of the inherent parallelism of classifier systems and genetic algorithms, and that allows the exploration of large-scale tasks that were formerly impractical. As with other approaches to learning, classifier systems in their current form work well for moderately-sized tasks but break down for larger tasks. In order to shed light on this issue, we present several empirical studies of known issues in classifier systems, including the effects of population size, the actual contribution of genetic algorithms, the use of rule chaining in solving higher-order tasks, and issues of task representation and dynamic population convergence. We conclude with a discussion of some major unresolved issues in learning classifier systems and some possible approaches to making them more effective on complex tasks.     

New architectures: Performance highlights and new algorithms

Parallel computers are having a profound impact on computational science. Recently highly parallel machines have taken the lead as the fastest supercomputers, a trend that is likely to accelerate in the future. We describe some of these new computers, and issues involved in using them. We present elliptic PDE solutions currently running at 3.8 gigaflops, and an atmospheric dynamics model running at 1.7 gigaflops, on a 65 536-processor computer.

One intrinsic disadvantage of a parallel machine is the need to perform inter-processor communication. It is important to ensure that such communication time is maintained at a small fraction of computation time. We analyze standard multigrid algorithms in two and three dimensions from this point of view, indicating that performance efficiencies in excess of 95% are attainable under suitable conditions on moderately parallel machines. We also demonstrate that such performance is not attainable for multigrid on massively parallel computers, as indicated by an example of poor multigrid efficiency on 65 536 processors. The fundamental difficulty is the inability to keep 65 536 processors busy when operating on very coarse grids.

Most algorithms used for implementing applications on parallel machines have been derived directly from algorithms designed for serial machines. The previously mentioned multigrid example indicates that such ‘parallelized’ algorithms may not always be optimal. Parallel machines open the possibility of finding totally new approaches to solving standard tasks—intrinsically parallel algorithms. In particular, we present a class of superconvergent multiple scale methods that were motivated directly by massevely parallel machines. These methods differ from standard multigrid methods in an intrinsic way, and allow all processors to be used at all times, even when processing on the coarsest grid levels. Their serial versions are not sensible algorithms. The idea that parallel hardware—the Connection Machine in this case—can lead to discovery of new mathematical algorithms was surprising for us.     

一个VLIW体系结构的单片多处理机

本介绍一个采用ＶＬＩＷ超长指令字体系结构的高性能单片多处理机，在这个体系结构中采用流水寄存器堆来消除循环程序内的数据相关，从而使程序能够在指令级以极高的并行度并行运行。模拟实验结果表明这个体系结构具有很高的运算速度和很好的性能价格比。     

Improving the numerical stability and the performance of a parallel sparse solver

Coarse grain parallel codes for solving sparse systems of linear algebraic equations can be developed in several different ways. The following procedure is suitable for some parallel computers. A preliminary reordering of the matrix is first applied to move as many zero elements as possible to the lower left corner. After that the matrix is partitioned into large blocks and the blocks in the lower left corner contain only zero elements. An attempt to obtain a good load-balance is carried out by allowing the diagonal blocks to be rectangular.

While the algorithm based on the above ideas has good parallel properties, some stability problems may arise during the factorization because the pivotal search is restricted to the diagonal blocks. A simple a priori procedure has been used in a previous version in an attempt to stabilize the algorithm. In this paper it is shown that three enhanced stability devices can successfully be incorporated in the algorithm so that it is further stabilized and, moreover, the parallel properties of the original algorithm are preserved.

The first device is based on a dynamic check of the stability. In the second device a slightly modified reordering is used in an attempt to get more nonzero elements in the diagonal blocks (the number of candidates for pivots tends to increase in this situation and, therefore, there is a better chance to select more stable pivots). The third device applies a P⁵-like ordering as a secondary criterion in the basic reordering procedure. This tends to improve the reordering and the performance of the solver. Moreover, the device is stable, while the original P⁵ ordering is often unstable.

Numerical results obtained by using the three new devices are presented. The well-known sparse matrices from the Harwell-Boeing set are used in the experiments.     

Three solutions for a robot arm controller using Pascal-Plus,occam and edison

Three currently available concurrent language systems, Pascal-Plus, occam and Edison, are used to implement a controller for a robot arm. The robot arm allows real parallelism of operation within the movements of the arm. The feasibility and restrictions placed upon the resultant solution for each of the language systems is then analysed and discussed. A Petri-net solution is also presented for the generalized problem and it is shown that each of the solutions is a different folding of the general net.     

细粒度并行与多线程计算

为实现高性能有必要采用细粒度的并行，但必须解决其中增大的通信开销问题。多线程计算不仅用来实现细粒度的并行，合理的调度策略还有助于隐藏通信延迟。但其中存在着线程切换开销的问题，多线程处理器可能是一种解决办法。     

On Design of Parallel Memory Access Schemes for Video Coding

Some of the modern powerful digital signal processors (DSPs) have byte-addressable internal data memory. This property is valuable especially in computationally demanding inter frame video encoding, where data accesses are typically unaligned according to word boundaries. The byte-addressable memory allows load or store command to start accessing from any byte-address, providing at most as many successive bytes from subsequent addresses as data bus can handle in parallel. Maybe the simplest way to construct such a byte-addressable memory is to use N 8-bit memory modules or banks to be accessed in parallel, when N is data bus width in bytes. However, in addition to byte-addressable subsequent bytes, memory consisting of parallel memory modules can provide much more versatile addressing capabilities with reasonable implementation cost. Versatile access formats can significantly reduce the need for data reordering in the register file. At first, we provide motivation for using parallel memory architecture with versatile access formats as an internal on-chip data memory of modern DSP. After this, notations are described and general view of parallel memory design is given. We propose some example parallel data memory architecture designs with data access formats especially helpful in H.263 encoding and MPEG-4 core profile motion and texture encoding. The examples are given for different data bus widths (16, 32, 64, and 128 bits). Finally, performance is shortly compared to other memory architectures and area, delay, and power figures are estimated.Jarno K. Tanskanen was born in Joensuu, Finland in 1975. He studied analog and digital electronics in the Department of Electrical Engineering, and computer architecture in the Department of Information Technology at Tampere University of Technology, where he received his M.Sc. degree in 1999. He is currently working as a research scientist in the Institute of Digital and Computer Systems at TUT. His Dr.Tech. research concerns parallel processing of video compression. jarno.tanskanen@tut.fiReiner Creutzburg received his Diploma in Mathematics in 1976 and attained his Ph.D. in Mathematics in 1984 from the Rostock University, Germany. Prof. Creutzburg has published 3 books, filed 2 patents, and produced approximately 100 articles, preprint, and conference papers. Professional Experience: Since 2000—Part-time Professor for Multimedia technology, Tampere University of Technology, Finland. Since 1992—Full-time Professor of Computer Science, Fachhochschule Brandenburg-University of Applied Sciences, Brandenburg, Germany. 1990 to 1992—Assistant Professor, University of Karlsruhe, Institute of Algorithms and Cognitive Systems, Germany. 1987 to 1989—Head of the Research Section Image Processing. 1986 to 1989—Founder and Head of the International Base Laboratory of Image Processing and Computer Graphics for East European countries at the Central Institute of Cybernetics and Information Processes of the Academy of Sciences (Berlin), Germany. 1976 to 1989—Researcher and Assistant Professor in various Universities and the Academy of Sciences, Central Institute of Cybernetics and Information, Berlin. creutzburg@fh-brandenburg.deJarkko T. Niittylahti was born in Orivesi, Finland, in 1962. He received the M.Sc, Lic.Tech, and Dr.Tech degrees at Tampere University of Technology (TUT) in 1988, 1992, and 1995, respectively. From 1987 to 1992, he was a researcher at TUT. In 1992–93, he was a researcher at CERN in Geneva, Switzerland. In 1993–95, he was with Nokia Consumer Electronics, Bochum, Germany, and in 1995–97 with Nokia Research Center, Tampere, Finland. In 1997–2000, he was a Professor at Signal Processing Laboratory, TUT, and in 2000–2002 at Institute of Digital and Computer Systems, TUT. Currently, he is a Docent of Digital Techniques at TUT and the managing director of Staselog Ltd. He is also a co-founder and President of Atostek Ltd. He is interested in designing digital systems and architectures. jarkko.niittylahti@tut.fi     

基于四边形平行度识别变压器励磁涌流的方法

基于励磁涌流明显的奇异特征和内部短路电流近似正弦波的特点,提出一种利用四边形平行度来识别变压器励磁涌流的方法。当励磁涌流时,波形呈现出严重的上下及前后半波不对称,通过提取四边形的4个顶点,所构成的四边形很不规则,而变压器发生内部故障的情况,所构成的四边形则近似为平行四边形,所以通过平行度的大小可以有效区分变压器励磁涌流和内部故障。变压器各种运行情况的动模试验验证了所提方法的可行性和判据的正确性。     

空间旋转多光谱多光轴校准技术研究

论文总结了多光轴在空间旋转时形成的原因及其误差量,形成了兼顾安全和便捷的技术途径：首先以摄像机模拟非可见且对人眼有危害的激光器;其次设计加工出一种专用的回转基准调校基座和基准光源,通过转动基座,检测出摄像机光轴和可见光轴在空间不同相对位置的误差,采用双光楔方法进行调节;最后依托过渡工装使激光器光轴相对其安装面的精度与摄像机一致,由此保证了激光轴与可见光轴在任意方位角处均保持平行;其平行度误差不超过0.1mrad。