Time-Optimal 2D Convolution on Mesh-Connected SIMD Computers with Bounded Number of PEs (Special Issue on Architectures Algorithms and Networks for Massively Parallel Computing)
スポンサーリンク
概要
- 論文の詳細を見る
2D (two-dimensional) convolution is a basic operation in image processing and requires intensive computation. Although the SIMD model is considered suitable for 2D convolution, previous 2D convolution algorithms on the SIMD model assume unbounded number of PEs (Processing Elements) available, which we call unbounded case. Unbounded case could not be satisfied on real computers. In this paper, time-optimal data-parallel 2D convolution is studied on mesh-connected SIMD computers with bounded number of PEs. Because the optimal computation complexity is not difficult to achieve, the main concern of this paper is how to achieve optimal communication complexity. Firstly the lower bound computation complexity is analyzed. Then the lower bound communication complexities are analyzed under two typical data-distribution strategies: block-mapping and cyclic-mapping. Based on the analysis result, an optimal algorithm is presented under the block-mapping. The algorithm achieves the lower bound complexity both in computation and in communication.
- 社団法人電子情報通信学会の論文
- 1996-08-25
著者
-
LU Jian
Department of Applied Physics, Nanjing University of Science & Technology
-
Lu Jian
Department Of Applied Physics Nanjing University Of Science And Technology
-
Yuasa Taiichi
Department Of Communications And Computer Engineering Graduate School Of Informatics Kyoto Universit
-
Yuasa Taiichi
Department Of Information And Computer Sciences Faculty Of Engineering Toyohashi University Of Techn
-
Lu Jian
Department Of Information And Computer Sciences Faculty Of Engineering Toyohashi University Of Techn
関連論文
- Optical Deflection of Technique for Investigation of Laser-Induced Oscillating Bubble on Metal Surface
- Investigation of Lamb Waves Propagation by fibre-Coupling Optical Beam Deflection Detection Technique and Finite Element Method (Electromagnetism, Optics, Acoustics, Heat Transfer, Classical Mechanics and Fluid Mechanics)
- Highly Reliable Embedded Software Development Using Advanced Software Technologies(Software Engineering for Embedded Systems)
- Effects of ischemic postconditioning on reperfusion injury in rat liver grafts after orthotopic liver transplantation
- A New Algorithm for 2D Convolution on Mesh-connected SIMD Computers
- A Novel Wet Etching Process of Pb(Zr, Ti)O_3 Thin Films for Applications in Microelectromechanical System
- Preparation of Thick Pb(Zr, Ti)O_3 (PZT) Film by Electrostatic Spray Deposition (ESD) for Application in Micro-System Technology
- Time-Optimal 2D Convolution on Mesh-Connected SIMD Computers with Bounded Number of PEs (Special Issue on Architectures Algorithms and Networks for Massively Parallel Computing)
- A Transformation-Based Implementation of Lightweight Nested Functions
- Efficient and Portable Implementation of Java-style Exception Handling in C
- Design and Implementation of Kyoto Common Lisp
- Finite Element Analysis of the Scanning Laser Line Source Technique
- A PROCEDURE DEVELOPED TO PRIORITIZE ROADWAY INTERSECTIONS FOR SAFETY AND TRAFFIC IMPROVEMENTS
- Determination of Surface Stress Distributions in Steel Using Laser-Generated Surface Acoustic Waves
- A Transformation-Based Implementation of Lightweight Nested Functions
- A Transformation-Based Implementation of Lightweight Nested Functions
- Efficient and Portable Implementation of Java-style Exception Handling in C
- Efficient and Portable Implementation of Java-style Exception Handling in C
- Dynamics of Laser-Induced Cavitation Bubble near Solid Boundary
- Numerical Simulation of Thermoelastic Stress Field and Laser Ultrasound in Transversely Isotropic Plate
- Optical Deflection Technique for Investigation of Laser-Induced Oscillating Bubble on Metal Surface
- Effect of Liquid Viscosity on a Liquid Jet Produced by the Collapse of a Laser-Induced Bubble near a Rigid Boundary